Chương 1: Trình bày các kiến thức cơ bản về phép toán hình thái bao gồm các khái niệm, các thuật toán và các ứng dụng tiêu biểu của phép toán hình thái. Chương 2: Trình bày ngắn gọn các khái niệm liên quan đến thuật toán di truyền. Chương 3: Tập trung giải quyết bài toán phân rã phần tử cấu trúc bằng phƣơng pháp tiếp cận ngẫu nhiên dựa trên thuật toán di truyền. Chương 4: Trình bày kết quả thực nghiệm: Phân rã phần tử cấu trúc kích thƣớc 9x9 thành các phần tử cấu trúc kích thƣớc 3x3.
Phần kết luận nêu tóm tắt các kết quả đạt đƣợc và đƣa ra các những vấn đề còn tồn đọng để nâng cao hiệu năng của thuật toán. 7 TIEU LUAN MOI download : skknchat@gmail.com Chƣơng I: Các khái niệm cơ bản về toán học hình thái I. Quan hệ giữa khái niệm tập hợp và phép toán hình thái Toán học hình thái (MM) dựa trên khái niệm về tập hợp, và chính nhờ có khái niệm này mà toán học hình thái mang lại một cách tiếp mới cận đối với các bài toán xử lý ảnh. Trong hầu hết các trƣờng hợp, phép toán hình thái đều thể hiện một tính chất nào đó của phép toán liên quan đến khái niệm tập hợp.
Bằng các khái niệm đơn giản về phép toán hợp, giao, phần bù.v, chúng ta có thể xây dựng các phép toán rất hữu ích cho các kỹ thuật xử lý ảnh. Ảnh số là sự biểu diễn ảnh dƣới dạng tín hiệu tƣơng tự hoặc tín hiệu số. Trong biểu diễn số của các ảnh đa mức xám, tập hợp các điểm ảnh đƣợc biểu diễn dƣới dạng một ma trận hai chiều. Mỗi phần tử của ma trận biểu diễn cho mức xám hay cƣờng độ của ảnh tại vị trí đó, phần tử trong ma trận đƣợc gọi là một phần tử ảnh, thông thƣờng kí hiệu là PEL (Picture Element) hoặc là điểm ảnh (Pixel).
Đối với ảnh nhị phân, ta ngầm định các điểm ảnh thể hiện đối tƣợng ảnh đƣợc mã hóa bởi các điểm ảnh có giá trị 1. Tƣơng ứng với đó, nền sẽ đƣợc mã hóa bởi các điểm ảnh có giá trị 0. Ảnh đa cấp xám có thể đƣợc biểu diễn bởi các tập hợp tập con của tập Z3. Ảnh nhị phân 8 TIEU LUAN MOI download : skknchat@gmail.com Mỗi một phần tử đƣợc đại diện bởi một bộ 3 phần tử (x1,x2,x3) tƣơng ứng là toạ độ điểm ảnh và mức xám tại ảnh đó.2[17] mô tả một thể hiện đơn giản của ảnh đa cấp xám Hình I.
Ảnh đa cấp xám Nhƣ vậy, ta đã hình dung đƣợc mối quan hệ giữa ảnh và khái niệm tập hợp. Đối với mỗi ảnh thì sẽ có tƣơng ứng một tập hợp thể hiện ảnh và ngƣợc lại, từ một tập hợp, ta có thể dựng lại ảnh tƣơng ứng. Một số khái niệm cơ bản về tập hợp Giả sử A là một tập thuộc Z 2. Nếu a=(a1,a2) là một phần tử của A, thì ta kí hiệu là: a A Tƣơng tự nhƣ vậy, trong trƣờng hợp a không phải là phần tử con của A thì kí hiệu: a A Tập hợp không chứa phần tử nào thì đƣợc gọi là tập rỗng 9 TIEU LUAN MOI download : skknchat@gmail.com Trong khuôn khổ của luận văn này, chúng ta sẽ quan tâm tới khái niệm phần tử của một tập hợp trong phạm vi của ảnh nhị phân.
Ví dụ, khi ta viết Cw {|wd, dD}thì nghĩa là C là tập các phần tử w là đối của các phần tử tƣơng ứng của tập D qua gốc tọa độ. Nếu nhƣ với mọi phần tử A đều thuộc tập B thì ta nói rằng tập A là một tập con của tập B và kí hiệu là : A B Hợp của hai tập A và tập B là tập tất cả các phần tử hoặc thuộc A hoặc thuộc B. CAB Tƣơng tự nhƣ vậy giao của hai tập A và tập B là tất cả các phần tử vừa thuộc A lại đồng thời thuộc B : Hình I. Các phép toán cơ bản trên tập hợp Phần bù của tập A là tập tất cả các phần tử không thuộc A C A{ w } |wA Hiệu A và B, kí hiệu là A-B đƣợc định nghĩa bởi Ngoài ra, trong toán học hình thái ngƣời ta còn đƣa ra hai định nghĩa khác, tập nghịch của A : 10 TIEU LUAN MOI download : skknchat@gmail.com B {w | w b, b B} và tập tịnh tiến của tập A bởi véc tơ z(z1,z2), đƣợc định nghĩa là tập tất cả các phần tử là ảnh của tập A trong phép tịnh tiến theo véc tơ z : Az {c | c a z, a A} I.
Các phép toán logic trên ảnh nhị phân Phần lớn các ứng dụng trong chƣơng này là đề cập tới ảnh nhị phân. Các phép toán logic dù đơn giản nhƣng cung cấp một cách thực thi hiệu quả để có thể triển khai các thuật toán xử lý ảnh dựa trên phép toán hình thái. Phép toán cơ bản nhất đƣợc sử dụng trong xử lý ảnh là : phép toán AND, phép toán OR và phép toán NOT. Các tính chất của chúng đƣợc định nghĩa trong bảng dƣới đây : P Q P AND Q P OR q NOT p 0 0 0 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 0 Dựa trên ba phép toán cơ bản trên, ta có thể xây dựng đƣợc các phép toán phức tạp hơn bằng cách kết hợp chúng lại với nhau.
dƣới đây thể hiện các phép toán dựa trên bộ các phép toán cơ bản ở trên. 11 TIEU LUAN MOI download : skknchat@gmail. Các phép toán cơ bản I. Phép toán làm béo (Dilation) và làm gầy (Erosion) Ta bắt đầu thảo luận về phép toán hình thái, bƣớc đầu xem xét 2 phép toán hình thái cơ bản: làm béo và làm gầy.
Đây là 2 phép toán cơ bản nhất và thực tế rằng đa số các thuật toán đều dựa trên 2 phép toán này. Làm béo Với A và B là 2 tập trong Z 2 , tập béo của A gây bởi tập B đƣợc ký hiệu là: A B {z | ( B) z A } Tập B thƣờng đƣợc gọi là phần tử cấu trúc do sự tác động của nó gây sự ảnh hƣởng về cấu trúc lên tập A. Phƣơng trình trên không chỉ nhằm đƣa ra định nghĩa của phép toán làm béo mà còn mang lại những lợi thế khác, nó mang lại một cảm giác trực quan rằng các phần tử cấu trúc này nhƣ là một mặt nạ xoắn làm thay đổi cấu trúc của ảnh ban đầu. 12 TIEU LUAN MOI download : skknchat@gmail.1[26](a) thể hiện ảnh tham gia thuật toán làm béo, hình I.
Trong trƣờng hợp này phần tử cấu trúc và phần tử cấu trúc nghịch của nó trùng nhau do B đối xứng. Phép toán làm béo Một trong các ứng dụng đơn giản nhất của phép toán làm béo là nối các nét đứt trong quá trình nâng cao chất lƣợng ảnh.2 dƣới đây là một ví dụ ảnh với các kí tự đứt gãy do quá trình quét ảnh không đƣợc tốt hay do việc zoom ảnh quá lớn. Độ dài lớn nhất của mỗi phần gãy trong ví dụ này là 2 pixel. Ta có thể dùng một phần tử cấu trúc đơn giản để nối các nét đứt này lại với nhau.
Kết quả của việc thực hiện phép toán làm béo này là ảnh đƣợc khôi phục, các vết đứt gãy đƣợc thay thế bởi các điểm ảnh tạo cho các nét chữ đƣợc trơn và liên tục. Ứng dụng của phép toán dilation 13 TIEU LUAN MOI download : skknchat@gmail. Làm gầy Cho tập A và B trong Z 2 , tập gầy của A gây bởi B đƣợc kí hiệu là Một trong các ứng dụng đơn giản nhất của phép toán làm gầy là loại bỏ các thành phần dƣ thừa hay các thành phần nhiễu. mô tả một ảnh nhị phân đƣợc cấu tạo bởi các hình vuông với các kích thƣớc là 1,2,5,7,9 và 15 điểm ảnh.
Bằng cách sử dụng phần tử cấu trúc với kích thƣớc phù hợp và sử dụng phép toán làm gầy, chúng ta có thể loại bỏ các hình vuông điểm ảnh nhỏ (nhiễu) và giữ lại các hình vuông điểm ảnh với kích thƣớc lớn (các thành phần chính của ảnh) Hình I. Loại bỏ thành phần nhiễu I. Phép toán Opening và Closing Nhƣ chúng ta đã thấy, phép toán làm béo tăng kích thƣớc của ảnh còn phép toán làm gầy giảm kích thƣớc của ảnh. Trong phần này, chúng ta sẽ bàn đến 2 trong những phép toán quan trọng nhất: Opening và Closing.
Opening ban đầu làm mịn đƣờng biên của đối tƣợng sau đó loại bỏ các phần lồi ra. Closing cũng nhằm mục đích làm mịn đƣờng biên nhƣng khác với phép toán Opening, phép toán Closing ban đầu sẽ làm dày đối tƣợng và sau đó mới thực hiện việc làm mịn biên của ảnh Opening của tập A bởi phần tử cấu trúc B đƣợc ký hiệu là A B ( A B) B Tƣơng tự Closing của A bởi B là : A B ( A B) B 14 TIEU LUAN MOI download : skknchat@gmail.com Phép toán Opening có một cách thể hiện hình học đơn giản. Giả sử chúng ta coi phần tử cấu trúc B nhƣ là một quả bóng. Đƣờng bao của tập A B đƣợc hình thành bằng cách cho B lăn trong cấu trúc hình học của A.
Phép toán Opening Ngƣợc lại, phép toán Closing cũng có một thể hiện tƣơng tự, nhƣng bằng cách ngƣợc lại. Quả bóng sẽ đƣợc lăn ở phía ngoài cấu trúc hình học của A. Phép toán Closing 15 TIEU LUAN MOI download : skknchat@gmail. Phép toán Opening Một số tính chất cơ bản của phép toán opening: - A B là tập con của A - Nếu C là tập con của D thì C B là tập con của D B - (A ) B BBA Tƣơng tự nhƣ vậy, phép toán closing thỏa mãn các tính chất sau: - A là tập con của A B - Nếu C là tập con của D thì C B là tập con của D B - ( A B) B A B Các phép toán hình thái còn đƣợc sử dụng để xây dựng các bộ lọc.
Ví dụ nhƣ trong bài toán nhận dạnh vân tay ngƣời, ảnh cần nhận dạng có nhiễu (nhƣ thể hiện trong hình I. Các nhiễu là các chấm trắng nhỏ (khác với các ví dụ trƣớc, trong ví dụ này nội dung của ảnh đƣợc thể hiện bởi các điểm ảnh sáng còn nền là các điểm ảnh sẫm mầu). Mục tiêu của quá trình tiền xử lý ảnh trƣớc khi nhận dạng là việc lọc các thành phần nhiễu nhƣng đồng thời phải đảm bảo sự ảnh hƣởng đến các thành 16 TIEU LUAN MOI download : skknchat@gmail.com phần vân tay ít nhất có thể.