ĐẠI HỌC QUỐC GIA HÀ NỘI
KHOA CÔNG NGHỆ
NGUYỄN MINH ĐỨC NÂNG CAO CHẤT LƯỢNG HÌNH ẢNH BẰNG PHÉP TOÁN HÌNH
THÁI, KỸ THUẬT TÌM XƯƠNG VÀ LÀM MẢNH LUẬN VĂN THẠC SỸ
Người hướng dẫn: PGS.TS. Ngô Quốc Tạo Hà nội - 2004
2.2.6. Dãn theo điều kiện. 36
Chương III: Nâng cao chất lượng ảnh bằng phương pháp tìm xương
và làm mảnh. 39
3.1 Xương và làm mảnh. 39
3.2 Các phương pháp lặp hình thái học. 41
3.3 Phân rã các phần tử cấu trúc hình thái nhị phân có dạng tuỳ ý sử dụng
thuật toán di truyền. 53
Nâng cao chất lượng hình ảnh bằng phép toán hình thái, kỹ thuật tìm xương và làm mảnh
2
3.3.1 Giới thiệu. 53
3.3.2 Phân rã phần tử cấu trúc . 55
3.3.2.1 Mục đích . 55
3.3.2.2.1 Hệ thống Serial. 56
3.3.2.2.2 Hệ thống tế bào SIM . 57
3.3.2.2 Tiêu chuẩn tối ưu. 60
3.3.3 Tiếp cận ngẫu nhiên. 60
3.3.3.1 Cấu trúc dữ liệu. 62
3.3.3.2 Khởi taọ quần thể. 63
3.3.3.3 Hàm thích nghi. 64
3.3.3.4 Tìm kiếm di truyền. 66
3.3.4 Phân tích kết quả. 69
3.3.4.1 Phân rã các phần tử cấu trúc lồi. 69
3.3.4.2 Phân rã các phần tử cấu trúc không lồi. 70
3.3.5 Kết luận. 74
Chương IV: Cài đặt chương trình thử nghiệm. 76
Kết luận. 84
Tài liệu tham khảo. 87
Nâng cao chất lượng hình ảnh bằng phép toán hình thái, kỹ thuật tìm xương và làm mảnh
4
chúng một cách dễ dàng. Việc sử dụng các thao tác hình thái và ứng dụng của
chúng, đặc biệt là ứng dụng kỹ thuật làm mảnh ảnh để nâng cao chất lượng hình
ảnh cho bước tiền xử lý, trước khi thực hiện những bước kế tiếp cho công việc
xử lý ảnh.
Trong các kỹ thuật tìm xương truyền thống, việc sử dụng một mẩu phần tử
cấu trúc (cũng là một ảnh nhị phân) được khởi tạo ngay từ ban đầu xuyên suốt
quá trình lặp để xử lý ảnh thường chỉ xử lý được một vài đặc điểm của đối
tượng, vì thế trong luận văn này em cũng đề cập đến một phương pháp phân rã
phân tử cấu trúc hình dạng tuỳ ý sử dụng thuật toán di truyền để lựa chọn phân
tử cấu trúc tối ưu cho các phép toán hình thái.
Luận văn gồm 89 trang được chia làm 4 chương:
Chƣơng 1: Tổng quan về phƣơng pháp nâng cao chất lƣợng hình ảnh.
Giới thiệu sơ bộ về xử lý ảnh và ứng dụng. Khái niệm ảnh nhị phân, Hình
thái học.
Chƣơng 2: Nâng cao chất lƣợng ảnh bằng phép toán hình thái
Chương này giới thiệu về các thao tác với ảnh nhị phân. Cụ thể đó là các
thao tác như: Phép dãn, phép co, phép đóng, mở ảnh, kỹ thuật đánh trúng đánh
trượt, nhận dạng biên, dãn theo điều kiện. Bên cạnh các thao tác có kèm theo ý
nghĩa của chúng, có thuật toán và có hình minh hoạ.
Chƣơng 3: Nâng cao chất lƣợng hình ảnh bằng phƣơng pháp tìm xƣơng và
làm mảnh.
Trong chương này của luận văn giới thiệu về ý nghĩa của hình thái học
trong thực tiễn và các ứng dụng nói chung của thao tác hình thái, trong đó chú
trọng vào thao tác làm mảnh. Đặc biệt, trong chương này có trình bày khá chi
Nâng cao chất lượng hình ảnh bằng phép toán hình thái, kỹ thuật tìm xương và làm mảnh
5
tiết một ứng dụng của phép toán hình thái có tính thiết thực, đó là kỹ thuật tìm
Nhận biết và đánh giá các nội dung của ảnh là sự phân tích một hình ảnh
thành những phần có nghĩa để phân biệt đối tượng này với đối tượng khác. Dựa
vào đó ta có thể mô tả cấu trúc của hình ảnh ban đầu.
Có thể liệt kê một số phương pháp nhận dạng cơ bản như nhận dạng biên
của một đối tượng trên ảnh, tách cạnh, phân đoạn hình ảnh Kỹ thuật này
được sử dụng nhiều trong y học (xử lý tế bào, nhiễm sắc thể).
Trong thực tế, người ta đã áp dụng kỹ thuật nhận dạng khá thành công với
nhiều đối tượng khác nhau như: Nhận dạng ảnh vân tay, nhận dạng chữ (chữ cái,
Nâng cao chất lượng hình ảnh bằng phép toán hình thái, kỹ thuật tìm xương và làm mảnh
7
chữ số, chữ có dấu). Nhận dạng chữ in hoặc đánh máy trong văn bản phục vụ
cho việc tự động hoá quá trình đọc tài liệu, tăng nhanh tốc độ và chất lượng thu
nhận thông tin từ máy tính, nhận dạng chữ viết tay (với mức độ ràng buộc khác
nhau về cách viết, kiểu chữ,
Các quá trình của xử lý ảnh:
Các quá trình của xử lý ảnh được tiến hành theo sơ đồ sau:
Trước hết là quá trình thu nhận ảnh. ảnh có thể thu nhận qua camera.
Thường ảnh thu nhận qua camera là tín hiệu tương tự (loại camera ống kiểu
CCIR), nhưng cũng có thể là tín hiệu số hoá (loại CCD - Charge Coupled
Device).
Ảnh có thể thu nhận từ vệ tinh qua các bộ cảm ứng (sensor), hay ảnh, tranh
được quét qua scanner. Tiếp theo là quá trình số hóa (Digitalizer) để biến đổi tín
Như đã giới thiệu ở trên. Trong quá trình xử lý ảnh, một ảnh thu nhập vào
máy tính phải được mã hoá. Hình ảnh khi lưu trữ dưới dạng tập tin phải được số
hoá. Tiêu chuẩn đặt ra là ảnh phải lưu trữ thế nào sao cho các ứng dụng khác
nhau có thể thao tác trên các loại dữ liệu này. Hiện nay có trên 30 kiểu lưu trữ
ảnh khác nhau, trong đó ta thường gặp các dạng ảnh sau: TIFF, GIF, BMP,
PCX, JPEG, Nói chung mỗi kiểu lưu ảnh có ưu điểm riêng.
1.2.1 Một số khái niệm:
Pixel (Picture Element): Phần tử ảnh.
Ảnh trong thực tế là một ảnh liên tục về không gian và về giá trị độ sáng. Để
có thể xử lý ảnh bằng máy tính cần thiết phải tiến hành số hoá ảnh. Trong quá
trình số hoá, người ta biến đổi tín hiệu liên tục sang tín hiệu rời rạc thông qua
quá trình lấy mẫu (rời rạc hoá về không gian) và lượng hoá thành phần giá trị mà
về nguyên tắc, mắt thường không phân biệt được hai điểm kề nhau. Trong quá
trình này, người ta sử dụng khái niệm Picture Element mà ta quen gọi hay viết là
pixel - phần tử ảnh. Như vậy một ảnh là một tập hợp các pixel. ở đây cũng cần
phân biệt khái niệm pixel hay đề cập đến trong các hệ thống đồ hoạ máy tính. Để
tránh nhầm lẫn, ta tạm gọi khái niệm pixel này là pixel thiết bị. Khái niệm pixel
Nâng cao chất lượng hình ảnh bằng phép toán hình thái, kỹ thuật tìm xương và làm mảnh
9
thiết bị có thể xem xét như sau: Khi ta quan sát màn hình (trong chế độ đồ hoạ),
màn hình không liên tục mà gồm nhiều điểm nhỏ, gọi là pixel. Mỗi pixel gồm một
cặp toạ độ x, y và màu.
ảnh nhị phân: Tuỳ theo vùng các giá trị mức xám của điểm ảnh, mà các
ảnh được phân chia ra thành ảnh màu, ảnh xám, hay ảnh nhị phân. Khi trên một
ảnh chỉ có giá trị 0 hoặc 1 thì ta nói đó là một ảnh nhị phân hoặc ảnh đen trắng
và các điểm ảnh của nó gọi là điểm ảnh nhị phân.
1.2.2 Đặt bài toán nâng cao chất lượng ảnh bằng các phép toán hình thái.
Hình ảnh trong thực tế khi nhận được qua các thiết bị như: Photocopy, Fax,
ít nhiều đều bị nhiễu, thậm chí có thể biến dạng đến mức độ có thể khiến
cng c nh ngha gii quyt bi toỏn nờu trờn.
1.2.3 t bi toỏn nõng cao cht lng nh bng k thut tỡm xng v lm
mnh:
Trong x lý nh v nhn dng nh, cú mt s loi nh ng nột gm cỏc
i tng (objects) l cỏc ng cong cú di ln hn nhiu so vi dy ca
nú, vớ d nh l nh cỏc kớ t, du võn tay, s mch in t, bn v k thut,
bn v.v x lý cỏc loi nh ny ngi ta thng xõy dng cỏc h mụ
phng theo cỏch phõn tớch nh ca con ngi gi l h thng th giỏc mỏy
(Computer Vision System). Cú nhiu h thng c ci t theo phng phỏp
ny nh h thng nhn dng ch vit bng thit b quang hc OCR (Optical
Character Recognition), h thng nhn dng võn tay AFIS (Automated
Fingerprint Identification System) v.v
Đọc ảnh
(Scanner/Camera)
Tiền xử lý (Nâng cấp và
khôi phục)
Trích trọn đặc điểm
Đối sánh Nhận dạng
Hỡnh 1.2: Mụ hỡnh tng quỏt ca h thng nhn dng nh.
Nâng cao chất lượng hình ảnh bằng phép toán hình thái, kỹ thuật tìm xương và làm mảnh
11
quan sát.
Tính khoa học của Hình thái học số chỉ mới thực sự phát huy khả năng của
nó kể từ khi máy tính điện tử số ra đời và đã làm cho Hình thái học trở nên
thông dụng, có nhiều tính năng mới. Những đối tượng ảnh trong Hình thái học
có thể coi là tập hợp của các điểm ảnh, nhóm lại theo cấu trúc hai chiều. Những
thao tác toán học rời rạc trên tập hợp điểm đó được sử dụng để làm rõ (tái hiện)
những nét đặc trưng của những hình dạng, do vậy có thể tính toán được hay
nhận biết được chúng một cách dễ dàng.
Phần lớn các phép toán hình thái học được định nghĩa từ hai phép toán cơ
bản là: Dãn ảnh (Dilation) và Co ảnh (Erosion).
Nâng cao chất lượng hình ảnh bằng phép toán hình thái, kỹ thuật tìm xương và làm mảnh
13
Nâng cao chất lượng hình ảnh bằng phép toán hình thái, kỹ thuật tìm xương và làm mảnh
14
2.2 Thao tác trên ảnh nhị phân:
Những thao tác hình thái nhị phân được xây dựng trên ảnh có 2 cấp xám
bao gồm chỉ những điểm ảnh, ta kí hiệu đen (1) hoặc trắng (0). Trong luận văn
này, ta coi đối tượng ảnh là những điểm đen và nền là những điểm trắng. Trước
hết, để bắt đầu ta hãy xem hình 2.1a. Tập hợp các điểm ảnh đen tạo nên đối
tượng ảnh hình vuông và trong 2.1b, đối tượng ảnh cũng là hình vuông nhưng là
hình vuông lớn hơn so với 2.1a một điểm ảnh về mọi phía, nghĩa là thay mọi lân
cận trắng của các điểm ảnh trong 2.1a thành các điểm ảnh đen. Đối tượng trong
2.1c cũng được thao tác tương tự, tức là 2.1b được tăng thêm một điểm ảnh về
mọi phía. Thao tác đó có thể coi như một phép dãn đơn giản, phép dãn một
điểm
 = {c | c = - a, a A } (EQ 2.2)
đó chính là phép quay A một góc 180 quanh gốc tọa độ.
Phần bù của tập A là tập các điểm ảnh không thuộc đối tượng A, ở đây
chính là các điểm ảnh trắng. Theo lý thuyết tập hợp thì:
A
c
= {c | c A} (EQ 2.3)
Giao của hai tập hợp A và B là tập các phần tử thuộc về cả A lẫn B. Kí
hiệu:
A B = {c | ( c A) ( c B)} (EQ 2.4)
Nâng cao chất lượng hình ảnh bằng phép toán hình thái, kỹ thuật tìm xương và làm mảnh
16
Hợp của hai tập hợp A và B là tập các phần tử thuộc A hoặc / và B. Kí
hiệu:
A B = {c | ( c A) ( c B)} (EQ 2.5)
Hiệu của hai tập hợp A và B là tập:
A - B = { c | ( c A) ( c B)} (EQ 2.6)
Đó là tập các các phần tử thuộc A nhưng không thuộc B
hay A - B = A B
c
Bây giờ ta có thể định nghĩa phép dãn (dilation) qua lý thuyết tập hợp như
sau: Phép dãn tập A bởi tập B, đó là tập:
A B = {c | c = a + b, a A, b B} (EQ 2.7)
Dễ thấy trong toán học, đây là phép tổng trực tiếp A và B. A là đối tượng
ảnh được thao tác và B được gọi là phần tử cấu trúc (viết tắt là cấu trúc). Để
hiểu kỹ hơn về điều này, ta hãy coi A là đối tượng 2.1a và B = {(0, 0), (0, 1)}
Những phần tử trong tập C = A B được tính dựa trên biểu thức (EQ 2.7),
có thể viết lại như sau:
có thể quyết định hướng co, dãn của ảnh. Nếu gốc ở bên trái, thì ảnh có xu
hướng co, dãn về bên phải, gốc ở bên phải thì co, dãn về trái và nếu gốc ở giữa,
tất nhiên, ảnh sẽ dãn đều. Trong thí dụ trên do gốc của cấu trúc B ở bên trái nên
ta thấy ảnh được dãn về bên phải.
Hình 2.2 Dãn A bơỉ B
a) Tập A ban đầu.
b) Tập A cộng phần tử (0, 0).
c) Tập A cộng phần tử (0, 1).
d) Hợp của (b) và (c) - Kết quả của phép
dãn
Phần tử cấu trúc
Nâng cao chất lượng hình ảnh bằng phép toán hình thái, kỹ thuật tìm xương và làm mảnh
18
Nếu như gốc chứa một điểm ảnh trắng, khi đó ta nói rằng gốc không được
bao gồm trong tập B. Thông thường, để dãn ảnh đều về tất cả các phía, ta
thường sử dụng cấu trúc có dạng ma trận 3 3 với gốc ở chính giữa. Ta hãy xét
thêm một ví dụ nữa, ví dụ này sẽ cho ta thấy sự dãn về hai phía nếu như ta sử
dụng cấu trúc có gốc ở giữa và gốc chứa một điểm ảnh trắng. Trong trường hợp
cấu trúc có điểm ảnh trắng ở gốc ta nói rằng gốc không được bao gồm trong cấu
trúc.
Nhìn vào hình 2.3 dưới đây, ta có:
A
1
= {(1, 1), (1, 2), (2, 2), (2, 3), (3, 2), (3, 3), (4, 4)}.
Phần tử cấu trúc B
1
= {(0, -1), (0, 1)}.
Dịch A
1
Nhận thấy rằng trong hình 2.3, có một số phần tử của đối tượng ban đầu sẽ
không có mặt trong ảnh kết quả, chẳng hạn (4, 4). Đó chính là do gốc của phần
tử cấu trúc không phải là một phần tử đối tượng (bởi ta coi phần tử đối tượng là
điểm ảnh đen mà ở đây gốc lại là một điểm trắng).
Tổng quát hơn, ta có thể coi phép dãn (dilation) là hợp của tất cả các phép
dịch bởi các phần tử của cấu trúc, kí hiệu:
(EQ 2.9)
(EQ 2.9)
Tuy nhiên với vai trò bình đẳng của A và B, ta coi A là cấu trúc và B là ảnh
thì khi đó:
(EQ
2.10)
Từ những điều trên, giúp ta tiếp cận đến một thao tác dãn ảnh có thể được
“máy tính hóa”. Ta hãy xem những phần tử cấu trúc như là một mẫu và dịch nó
trên ảnh. Khi mà gốc của phần tử cấu trúc, hay mẫu, khớp với một điểm ảnh
đen trên ảnh thì tất cả các điểm ảnh tương ứng với các điểm đen trên cấu trúc sẽ
được đánh dấu và thay thế sau. Sau khi toàn bộ ảnh đã được quét qua bởi mẫu,
thao tác dãn ảnh coi như hoàn chỉnh. Thông thường, máy tính sẽ làm như sau:
Bb
b
ảnh ban đầu, ta thay các điểm đen mà lân cận của nó có ít nhất một điểm trắng
thành trắng. Khi đó ảnh nhận được là ảnh được co bằng phép co đơn giản.
Trong phép co này, mẫu được sử dụng chính là mảng 3 3 của các điểm ảnh
đen, đã được nói đến trong phép dãn nhị phân trước đây.
Nhìn chung, phép co một ảnh A bởi cấu trúc B có thể được định nghĩa như
là tập:
A B = {c |(B)
c
A} (EQ 2.11)
Nói cách khác, đó là tập hợp các điểm ảnh c A, mà nếu cấu trúc B dịch
chuyển theo các toạ độ của c, thì B vẫn nằm trong đối tượng ảnh A, tức B là
một tập con của đối tượng ảnh cần co A. Tuy nhiên điều đó sẽ chưa chắc đã
Nâng cao chất lượng hình ảnh bằng phép toán hình thái, kỹ thuật tìm xương và làm mảnh
21
đúng nếu như phần tử cấu trúc B không chứa gốc (tức điểm ảnh gốc màu trắng).
Đầu tiên, ta hãy xét một ví dụ đơn giản sau đây: Xét phần tử cấu trúc B ={(0,
0), (0, 1)}và đối tượng ảnh A = {(3, 3), (3,4), (4,3), (4,4)} như trong hình 2.2.
Không cần thiết phải quan tâm đến toạ độ các điểm đen của A, mà chỉ cần quan
tâm đến những toạ độ của các điểm đen của A mà khi ta di mẫu B trên đối tượng
ảnh A thì gốc của B trùng một điểm ảnh đen của A. ở đây ta quan tâm tới bốn
toạ độ của bốn điểm đen của A sau:
B
(3, 3)
= {(3, 3), (3, 4)}, tức là dịch các điểm ảnh của B sang phải 3 và
xuống dưới 3
Tương tự có:
B
(4, 3)
= {(4, 3), (4, 4)}
(3, 4)
= { (4, 4) }
Nâng cao chất lượng hình ảnh bằng phép toán hình thái, kỹ thuật tìm xương và làm mảnh
22
Điều này có nghĩa kết quả của phép co là {(2, 3), (2, 4), (3, 3), (3, 4)}, thế
nhưng lại không phải là một tập con của A, mà lí do gây ra điều đó chính là gốc
không được chứa trong mẫu B
2
.
Ta nhận thấy một điều quan trọng là: Phép co và phép dãn không phải là
những thao tác ngược nhau. Có thể trong một số trường hợp đúng là phép co sẽ
giải hoạt hiệu quả của phép dãn. Nhưng nhìn chung thì điều đó là không đúng, ta
sẽ quan sát chúng một cách cụ thể hơn ở sau. Tuy nhiên, giữa phép co và phép
dãn có mối quan hệ qua biểu thức sau đây:
(A B)
c
= A
c
BÂ (EQ 2.12)
Hình 2.5:Phép co nhị phân dùng cấu trúc đơn giản
Nâng cao chất lượng hình ảnh bằng phép toán hình thái, kỹ thuật tìm xương và làm mảnh
23
Tức là phần bù của phép co ảnh A bởi phần tử cấu trúc B được xem như
phép dãn phần bù của A bởi phần tử cấu trúc đối của B. Nếu như phần tử cấu
trúc B là đối xứng (ở đây ta quan niệm đối xứng theo toạ độ) thì tập đối của B
không thay đổi, nghĩa là B = B, và quan hệ của biểu thức (EQ 2.12) là: phần bù
thì rỗng:
= {z|((B)
z
A
c
) = }
cVà tập các điểm ảnh không có thuộc tính này là phần bù của tập đó:
= {z|(B)
z
A
c
}
Mặt khác theo định nghĩa của phép dịch chuyển trong biểu thức (EQ 2.1),
nếu (B)
z
giao với A
c
thì
= {z|b + z A
c
, b B}
Điều đó là giống như:
= {z|(b + z) = a, a A
c
,
Hình 2.6 sẽ đưa ra cho ta một vài ví dụ của phép co đơn giản một ảnh bằng
tập các phần tử cấu trúc và kết quả của từng cấu trúc gây ra cho ảnh ban đầu.
Copyright: Tài liệu đại học ©