2
MỤC LỤC

DANH MỤC CÁC HÌNH VẼ 4
Chƣơng 1: MỞ ĐẦU 6
Chƣơng I: Các khái niệm cơ bản về toán học hình thái 8
I.1. Quan hệ giữa khái niệm tập hợp và phép toán hình thái 8
I.1.1. Một số khái niệm cơ bản về tập hợp 9
I.1.2. Các phép toán logic trên ảnh nhị phân 11
I.2. Phép toán làm béo (Dilation) và làm gầy (Erosion) 12
I.2.1. Làm béo 12
I.2.2. Làm gầy 14
I.2.3. Phép toán Opening và Closing 14
I.2.4. Biến đổi Hit or Miss 17
I.3. Một số thuật toán dựa trên phép toán hình thái 19
I.3.1. Trích chọn biên 19
I.3.2. Tô miền 20
I.3.3. Tách các thành phần liên thông 21
I.3.4. Làm mảnh 23
I.3.5. Làm dầy 24
I.3.6. Tìm xƣơng của ảnh 25
Chƣơng II: Thuật toán di truyền 27
II.1. Thuật toán di truyền là gì? 27
II.2. Sử dụng thuật toán di truyền trong toán học hình thái 27


Hình I.1.2. Ảnh đa cấp xám 9
Hình I.1.3. Các phép toán cơ bản trên tập hợp 10
HÌnh I.1.4. Các phép toán cơ bản 12
Hình I.2.1. Phép toán dilation 13
Hình I.2.2. Ứng dụng của phép toán dilation 13
Hình I.2.3. Loại bỏ thành phần nhiễu 14
Hình I.2.4. Phép toán Opening 15
Hình I.2.5. Phép toán Closing 15
Hình I.2.6. Phép toán Opening và Closing 16
Hình I.2.7. Xử lý nhiễu trong ảnh vân tay 17
Hình I.2.8. Phép toán Hit ỏ Miss 18
Hình I.3.1. Trích chọn biên 19
Hình I.3.2. Ảnh đƣợc trích chọn biên 20
Hình I.3.3. Ví dụ thuật toán tô miền 21
Hình I.3.4. Tìm các thành phần liên thông trong ảnh 22
Hình I.3.5. Xác định vật thể lạ trong ảnh 23
Hình I.3.6. Làm mảnh ảnh 24
Hình I.3.7. Làm dầy ảnh 25
5
Hình I.3.8. Tìm xƣơng của ảnh 26
Hình II.1. Mô phỏng quá trình tiến hóa 29
Hình II.2. Lai ghép một điểm 30
Hình II.3. Lai ghép hai điểm 31
Hình II.4. Cắt và ghép 31
Hình II.5. Ví dụ về phép lai 32
Hình II.6. Đột biến tại bít thứ 6 32
Hình II.7. Mô tả hoạt động thuật toán 33

Phần tử cấu trúc là phần tử tham gia trong các phép toán hình thái, và việc phân rã
phần tử cấu trúc hoặc nói một cách khác là ma trận điểm ảnh có ba lợi ích quan trọng:
Thứ nhất, làm giảm phép toán trong các ứng dụng mà phần tử đó tham gia. Thứ hai,
giảm không gian lƣu trữ ảnh. Thứ ba, đối với các hệ thống chỉ hỗ trợ tập lệnh SIMD
trên các phần tử nhỏ hơn nhiều phần tử cấu trúc, thì việc phân rã phần tử cấu trúc thành
các phần tử cấu trúc nhỏ hơn là cần thiết.
Trong khuôn khổ của luận văn thạc sỹ này, tôi muốn tập trung đi sâu vào tìm
hiểu các phép toán hình thái và một số ứng dụng của phép toán hình thái trong xử lý
ảnh. Phần chính của luận văn, tôi sẽ trình bày một số kết quả đạt đƣợc trong việc ứng
7
dụng thuật toán di truyền để giải quyết bài toán phân rã phần tử cấu trúc trong xử lý
ảnh. Bố cục của luận văn này đƣợc tổ chức thành 3 chƣơng:
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.
9
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 đó. Hình I.1.2[17] mô tả một thể hiện đơn giản của
ảnh đa cấp xám Hình I.1.2. Ả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.
I.1.1. 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
2
Z
. Nếu a=(a1,a2) là một phần tử của A, thì ta kí
hiệu là:
aA


Hình I.1.3. 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 wwA

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 :
11
{ | , }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 :
{ | , }
z

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. Hình I.1.4[26]. 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.
12



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.
13
Hình I.2.1[26](a) thể hiện ảnh tham gia thuật toán làm béo, hình I.2.1(b) mô tả
phần tử cấu trúc và tập ngƣợc của nó( những điểm chấm đen mô tả các phần tử gốc).
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.
Hình I.2.1. 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. Hình I.2.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. Độ

Hình I.2.3. Loại bỏ thành phần nhiễu

I.2.3. 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   

15
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
AB
đƣợ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.
16 Hình I.2.6. Phép toán Opening Một số tính chất cơ bản của phép toán opening:
-
AB
là tập con của
A

- Nếu C là tập con của D thì

17
phần vân tay ít nhất có thể. Để lọc các thành phần nhiễu, ta sử dụng phần tử cấu trúc
đƣợc mô tả trong hình I.2.7(b) . Toàn bộ hình I.2.7 thể hiện từng bƣớc của quá trình lọc
ảnh. Các nhiễu đƣợc hoàn toàn loại bỏ trong phép toán làm gầy ở giai đoạn đầu do kích
thƣớc của các điểm nhiễu là nhỏ hơn kích thƣớc của phần tử cấu trúc và sau đó đƣợc
khôi phục lại nguyên dạng nhƣ ảnh lúc đầu. Chú ý rằng, sau quá trình này gần nhƣ toàn
bộ các thành phần nhiễu đã bị lọc bỏ.
Hình I.2.7. Xử lý nhiễu trong ảnh vân tay
I.2.4. Biến đổi Hit or Miss
Biến đổi Hit or Miss là một công cụ cơ bản để dò tìm ảnh. Tôi giới thiệu khái
niệm này với sự trợ giúp của hình I.2.8. Trong hình, tập A bao gồm 3 ảnh X, Y, Z. mục
tiêu là tìm vị trí của một trong 3 ảnh trên, giả sử là X
Giả sử gốc của mỗi ảnh là tại trung tâm của ảnh. Giả sử X đƣợc bao bởi một cửa
sổ nhỏ W. Ta định nghĩa nền của tập X trên ảnh W là tập tất cả các điểm ảnh thuộc W
mà không thuộc X, ký hiệu là W-X nhƣ đƣợc mô tả trong hình I.2.8(b). Trong hình
I.2.8(c) mô tả phần bù của tập A. Hình I.2.8(d) thể hiện tập A gầy . Nhớ lại rằng tập
gầy A bởi X là tập tất cả các vị trí của điểm gốc X sao cho X hoàn toàn nằm trong tập
A. Hiểu theo cách hình học thuần túy thì có thể coi nhƣ là tập hợp tất cả các

Chú ý rằng trong hình I.2.8(d) và (e), tập tất cả các vị trí mà X hoàn toàn nằm
trong A là giao của ảnh gầy A bởi X với ảnh gầy
C
A
bởi
(W )X
nhƣ trong hình
I.2.8(f). Nói một cách khác nếu ký hiệu B là tập cấu thành lên X và nền của nó, tập các
điểm phù hợp (match) của B trong A, ký hiệu là đƣợc định nghĩa bởi:

Chúng ta có thể ký hiệu
12
( , )B B B
, trong đó
1
B
là tập đƣợc tạo thành từ B và
đối tƣợng, còn
2
B
đƣợc tạo thành từ B và nền. Khi đó, công thức trên có dạng biến đổi
khác:

19
I.3. Một số thuật toán dựa trên phép toán hình thái
I.3.1. Trích chọn biên
Biên của A đƣợc ký hiệu là

thuộc vào mục tiêu cũng nhƣ các ứng dụng cụ thể.
Hình I.3.2[26]. cho ta một ứng dụng thuật toán tách biên cụ thể hơn. Trong ví dụ
này, phần tử 1 đại diện cho điểm ảnh trắng, phần tử 0 tƣơng ứng với điểm ảnh đen. Do
phần tử cấu trúc là phần tử cấu trúc trong ví dụ ở hình I.3.1, cho nên biên của ảnh đạt
đƣợc chỉ có kích thƣớc là một điểm ảnh.
(I.3-1)
20 Hình I.3.2. Ảnh đƣợc trích chọn biên

I.3.2. Tô miền
Trong hình I.3.3, tập A chứa một tập con mà các phần tử liên thông 8. Xuất phát
với một điểm p nằm bên trong, mục tiêu là tô toàn bộ miền có biên bởi các điểm đó.
Ta xây dựng thuật toán nhƣ sau:
1
()
c

21
Hình I.3.3. Ví dụ thuật toán tô miền

I.3.3. Tách các thành phần liên thông
Trong rất nhiều ứng dụng, việc phân tích ảnh đòi hỏi ta phải tách các thành phần
liên thông để phục vụ cho tác vụ xử lý. Ví dụ nhƣ trong ứng dụng nhận dạng mặt
ngƣời, việc đầu tiên cần phải xử lý là phải tách các thành phần liên thông, sau đó thực
hiện việc nhận dạng trên các thành phần đó.
Giả sử A chứa thành phần liên thông Y và p là một điểm của Y đã đƣợc biết

trình (I.3-2) thành phần bù của tập A tham gia thuật toán. Hình I.3.4. Tìm các thành phần liên thông trong ảnh

Thành phần liên thông đƣợc sử dụng rộng rãi trong chẩn đoán tự động. Hình
I.3.5[16](a) thể hiện ảnh X quang cấu trúc xƣơng của một con cá. Mục tiêu là phải xác
định đƣợc vật lạ trong quá trình xử lý cá trƣớc khi đóng gói và gửi đi. Trong trƣờng
hợp này, các điểm ảnh thể hiện đối tƣợng (xƣơng và vật lạ) có mật độ nhiều hơn so với
mật độ các điểm ảnh cấu thành nền. Nhƣ vậy dẫn tới mức xám của đối tƣợng so với
nền của ảnh sẽ có sự chênh lệch. Bằng cách đƣa ra một ngƣỡng đơn, ta có thể tách
đƣợc đối tƣợng ra khỏi nền. Kết quả của quá trình tách nền đƣợc thể hiện trên hình
I.3.5(b).
Đặc trƣng quan trọng nhất của các hình phía dƣới đó chính là các điểm cấu
thành xƣơng chứ không phải là các cô lập, các vật lạ. Chúng ta có thể giả thuyết rằng
chỉ có các điểm còn lại sau khi ta thực hiện phép toán làm gầy bởi phần tử cấu trúc 5x5
là thành phần của xƣơng. Kết quả của quá trình làm gầy là ảnh I.3.5(c). Chúng ta thực


nghĩa thông qua biến đổi hit-or-miss:
()
( * )
c
A B A A B
A A B
   


Nhƣ trong phần trƣớc đã nói, chúng ta chỉ quan tâm đến các mẫu phù hợp với
các phần tử cấu trúc, bởi vậy không một phép toán nền nào đƣợc yêu cầu trong biến đổi
hit-or-miss. Một cách biểu diễn hình học hữu ích cho việc làm mảnh ảnh A là dựa trên
dãy các phần tử cấu trúc:
12
{}{, , , }
n
BBB B

(I.3-4)
24
Trong đó
i
B
chính là phần tử
1i
B


, sau đó tiếp tục
với
2
B
, quá trình làm mảnh kết thúc cho đến khi không có sự thay đổi nào xảy ra.
Hình I.3.6(a) thể hiện tập tất cả các phần tử cấu trúc thƣờng đƣợc sử dụng cho
quá trình làm mảnh và I.3.6(b) biểu diễn ảnh A sau khi đƣợc làm mảnh bởi dãy các
phần tử cấu trúc trong hình I.3.6(a).
I.3.5. Làm dầy
Quá trình làm dầy một ảnh đƣợc thể hiện bởi công thức

(I.3-5)
(I.3-6)
25
Trong đó B là phần tử cấu trúc phù hợp. Tƣơng tự nhƣ quá trình làm mảnh, làm
dầy có thể đƣợc định nghĩa dƣới dạng một dãy các phép toán

Các phần tử cấu trúc đƣợc sử dụng trong phép toán làm dầy có cùng cấu trúc
nhƣ các phần tử cấu trúc trong hình I.3.6(a), nhƣng có sự chuyển đổi giá trị tại mỗi
điểm ảnh. Nói cách khác là tƣơng phản của nhau. Tuy nhiên thuật toán làm dầy hiếm
khi đƣợc sử dụng trong thực tế. Thay vào đó ngƣời ta thƣờng làm mảnh nền của ảnh để
thu đƣợc hiệu quả làm dầy ảnh. (I.3-7)
(I.3-8)
(I.3-9)
(I.3-10)