XỬ LÝ ẢNH DỰA TRÊN MORPHOLOGICAL
NGÔ QUỐC VIỆT TPHCM-2014
1. Giới thiệu Binary Morphology 2. Một số khái niệm về tập hợp 3. Các phép toán cơ bản
Phát triển và bào mòn (Dilation and erosion)
Mở và đóng (Opening and closing)
Biến đổi trúng hay trật (Hit-or-miss transformation) 4. Ứng dụng morphology vào các bài toán xử lý ảnh
Dò biên
Trích các thành phần liên thông (Extraction of Connected Components) Tìm bao lồi (Convex Hull) Tô vùng (Region Filling) Làm mảnh (Thinning) Làm dầy (Thickening) Lọc xương/Lấy cạnh trung tâm (Skeleton)
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 2
Trang bị kiến thức về cách tiếp cận cấu trúc (tập hợp) vào giải quyết các bài toán xử lý ảnh đã được giải quyết bằng các biến đổi giải tích trước đó, và một số xử lý khác.
Trang bị các kỹ năng sử dụng OpenCV để thực hiện
các xử lý dựa trên morphology
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 3
Phương pháp phi tuyến Dựa trên lý thuyết tập hợp Minkowski Là một phần của lý thuyết finite lattices Dùng để phân tích ảnh dựa trên hình dáng Phương pháp hiệu quả, nhưng chưa được sử
dụng nhiều.
Morphology nhị phân là morphology trên ảnh đen trắng cho những bài toán xử lý ảnh cơ bản
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 4
Phân
tích hình dáng
ảnh
Cải
(image
(shape analysis)
Nén
(Image
(image
ảnh compression)
tiến enhancement) Phân đoạn ảnh segmentation) Phục hồi ảnh
(image
Phân tích thành phần (Component analysis)
restoration)
Curve filling Làm mỏng tổng quát
Dò cạnh Phân tích Texture (texture
(General thinning)
analysis)
Tìm đặc trưng (Feature
detection)
Phân tích particle sinh đặc Phát
trưng
Giảm
nhiễu
(Noise
(feature generation)
reduction)
Trích
xương
Lọc
không-thời
gian
(Skeletonization)
(Space-time filtering) Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt
5
Ảnh là một ánh xạ I từ tập SP các tọa độ pixel đến tập G các giá trị sao cho mỗi vector tọa độ p = (r,c) trong SP, có một vector I(p) thuộc G. SP được gọi là image plane.
Ảnh nhị phân có hai giá trị. Nghĩa là, G = {vfg , vbg}, với vfg là giá trị foreground và vbg là giá trị background.
Thông thường, foreground vfg = 0, và background vbg = –. Một số khả năng kháclà {vfg , vbg} = {0,}, {0,1}, {1,0}, {0,255}, và {255,0}.
Bài giảng sử dụng {vfg , vbg} = {255, 0} mà không làm mất tính tổng quát.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 6
Foreground của ảnh nhị phân
Tập các vị trí p, với I(p) = vfg. Tương tự background là
Chú ý
và
và
và
Background là bù của foreground và ngược lại.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 7
A ={(3,1), (4,1),(3,2),(4,2),(3,3)}.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 8
Structuring element là ảnh nhỏ – được dùng làm cửa sổ dịch chuyển – giá của SE thể hiện các pixel lân cận
F G
B G
l
i s w h i t e
i s g r a y ;
s E S e p m a x E
SE có thể có hình dáng và kích thước bất kỳ, hoặc liên thông (nhiều hơn 1 piece, có lỗ). Dấu tròn trên hình thể hiện gốc của SE. Gốc này có thể đặt bất kỳ đâu trong SE.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 9
Cho ảnh I và Z là SE.
Z+p nghĩa là Z được dịch chuyển sao cho gốc trùng với vị trí p trong SP.
Z+p là translate của Z đến p trong SP.
Tập các vị trí trong ảnh ký hiệu bởi Z+p được là Z-neighborhood gọi của p trong I. Ký hiệu là N{I,Z}(p).
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 10
Cho Z là SE và S lưới vuông các vị trí pixlel chứa tập {(r,c), (-r,-c) | (r,c)supp(Z)}. Thì
Là phản chiếu của structuring element.
quay 180º quanh gốc của nó.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 11
Phép toán Dilation đối tượng A theo đối tượng Z (thường là
SE) được định nghĩa bởi
Đối tượng A tịnh tiến theo từng vectơ (vị trí) trong Z. Kết quả sau khi tịnh tiến tạo ra các đối tượng A1,A2,…. An
(n là số phần tử trong Z). D(A,Z) là hợp các Ai.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 12
Một số định nghĩa khác về dilation.
Tập tất cả vị trí pixel p, trong ảnh mà phần giao của Ž+p với I khác rỗng.
Hội những copies của SE, mỗi bản copy là dịch chuyển đến vị trí pixel foreground trong ảnh.
Hội những copies của ảnh, mỗi bản là dịch chuyển đến vị trí pixel foreground của SE.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 13
A = {(2,1),(3,1),(4,1),(3,2)}
Z = {(0,0),(0,1)}
AZ
A1 = {(2,1),(3,1),(4,1),(3,2)}
A2 = A tịnh tiến bởi vector (0,1) của Z A2 = {(2,2),(3,2),(4,2),(3,3)}
A1 = A tịnh tiến bởi vector (0,0) của Z
D(A,B) = A1 U A2 = {(2,1),(3,1),(4,1),(3,2), (2,2),(4,2),(3,3)}
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 14
Sử dụng SE 3x3 – Z8 có dạng cho phép mở rộng đều về cả 8
hướng.
Kết quả dilate trên ảnh mẫu như sau
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 15
SE được áp lên mọi pixel của ảnh. Tâm của SE được kết hợp với từng pixel, toàn bộ SE được áp cho pixel đang xét theo cách thay thế pixel đó bằng SE. Khái niệp “áp” là hoạt động “công logic nhị phân giữa các giá trị 0, 1”.
SE
Đã giãn
Ảnh nguồn
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 16
Tham khảo mã nguồn openCV_Dilate
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 17
Phép toán Erosion đối tượng A theo đối tượng Z được định
nghĩa bởi:
Với vector a bất kỳ , khi tịnh tiến a theo từng vectơ trong Z. Kết quả sau khi tịnh tiến a là các vectơ mới: a1,a2,..an (n là số lượng phần tử trong Z).
Nếu tất cả các vector a1,a2,..an đều thuộc A a sẽ thuộc tập
E(A,Z).
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 18
Một số định nghĩa khác
Tập tất cả các pixel p, trong ảnh sao cho Z+p chứa trong I.
Phần giao của các copies của reflected. SE, mỗi cái dịch chuyển đến vị trí pixel thuộc foreground của ảnh.
Phần giao của các copies của mỗi bản sao - là dịch chuyển đến vị trí pixel thuộc goreground của refl. SE.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 19
A = {(1,1),(2,1),(3,1),(4,1),(1,2),(3,2),(1,3),(2,3)}
Z= {(1,0),(0,1)}
E(A,Z) = {(1,1),(3,1),(2,2)}
Lấy Vector (1,1) tịnh tiến theo các vector trong Z a1 = (1,1) + (1,0) = (2,1) thuộc A a2 = (1,1) + (0,1) = (1,2) thuộc A (1,1) thuộc E(A,B). Lấy Vecto (3,1) tịnh tiến theo các vector trong Z a1 = (3,1) + (1,0) = (4,1) thuộc A a2 = (3,1) + (0,1) = (3,2) thuộc A (3,1) thuộc E(A,Z). Lấy Vecto (2,2) tịnh tiến theo các vector trong Z a1 = (2,2) + (1,0) = (3,2) thuộc A a2 = (2,2) + (0,1) = (2,3) thuộc A (2,2) thuộc E(A,Z). Các vectơ khác khi tịnh tiến sẽ có vectơ không thuộc A. Không thuộc E(A,Z)
20
SE
Ảnh nguồn
Eroded
Xét pixel của ảnh, nếu mọi phần tử của SE trùng với phần ảnh tương ứng, thì logical disjunction (OR operation) được thực hiện giữa tâm của SE với pixel tương ứng để tạo ra pixel trong ảnh output . Các đối tượng nhỏ hơn SE sẽ bị xóa, các đối tượng nối với nhau bởi đường mảnh sẽ tách rời và kích cỡ đối tượng sẽ giảm
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 21
Tham khảo mã nguồn openCV_Erode
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 22
Dilate: nhằm tăng kích thước, bịt các lỗ hổng
Có tính giao hoán
Có tính kết hợp
Erode : co kích thước, mở rộng khoảng hở
Không có tính giao hoán Không có tính kết hợp
Dilate và erode có tính đối ngẫu Có thể cài đặt erode từ dilate và ngược lại
và
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 23
Hai phép toán phát triển và bào mòn thường được sử dụng cùng nhau. Từ nhu cầu đó, người ta kết hợp 2 phép toán này để tạo nên một số phép toán có mức độ quan trọng cao hơn: phép mở và phép đóng.
Phép mở của tập A bởi phần tử cấu trúc B được định
nghĩa như sau:
Phép đóng của tập A bởi phần tử cấu trúc B :
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 24
Opening
Closing
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 25
Phép mở
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 26
Phép đóng
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 27
Kết quả của phép mở và phép đóng :
Kết quả Phép đóng
Kết quả Phép mở
Ứng dụng Phép mở có thể sử dụng để loại bỏ các cầu nối, các
cành hoặc phần nhô ra của ảnh.
Phép đóng có thể sử dụng để lấp đầy các lỗ hổng,
các khe hở nhỏ.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 28
Foreground: white pixels
“L” shaped SE
Cross-hatched pixels are indeterminate.
O marks origin
Background: black pixels
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 29
Một số tính chất của phép mở: Tính phản mở rộng :
Tính đơn điệu tăng :
Tính dừng : Một số tính chất của phép đóng : Tính mở rộng :
Tính đơn điệu tăng :
Tính dừng :
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 30
Tham khảo mã nguồn openCV_OpenClose
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 31
Hit-and-miss được dùng để xác định patterns của
foreground và background pixels trong ảnh
Xét tập A và một tập hợp B gồm 2 phần tử (B1,B2) với B1 ∩ B2 = Ø, định nghĩa phép biến đổi trúng-trật
với công thức như sau (công thức 1) :
Một định nghĩa khác về phép biến đổi trúng-trật
được xác định bởi (công thức 2):
Đụng B1 nhưng không đụng B2.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 32
Xét một ví dụ ứng dụng của phép biến đổi trúng- trật: Xác định vị trí các điểm góc trên bên phải của tập A
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 33
Theo công thức 1, kết quả biến đổi là
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 34
Theo công thức 2, kết quả là
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 35
Top hat được xác định
𝑇ℎ𝑎𝑡 𝐴 = 𝐴 − 𝐴 ∘ 𝐵 với B là SE
Bottom-hat được xác định bởi
𝐵ℎ𝑎𝑡 𝐴 = 𝐴 ∙ 𝐵 − 𝐴 với B là SE Sinh viên làm thực nghiệm với ảnh sau và cho nhận
xét (đọc tài liệu Gonzalez từ 695-700)
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 36
binary image
8-connected SE
4-conn inside bdry
original
erosion by square
difference
Hình ảnh minh họa trích từ nguồn Vanderbilt University
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 37
Gọi biên của đối tượng A là ∂A, lúc đó công thức để
tính ∂A như sau:
∂A = A – (A Θ B)
B
∂A
A Θ B
A
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 38
Ảnh nhị phân
4-connected SE
8-conn inside bdry.
original
erosion by plus
Ảnh hiệu - Difference
Hình ảnh minh họa trích từ nguồn Vanderbilt University
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 39
binary image
4-connected SE
8-conn outside bdry.
original
dilation by plus
difference
Hình ảnh minh họa trích từ nguồn Vanderbilt University
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 40
binary image
8-connected SE
4-conn outside bdry
original
dilation by square
difference
Hình ảnh minh họa trích từ nguồn Vanderbilt University
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 41
binary image
erosion by square is
8-conn inside bdry is
original
in erosion by plus
in 4-conn inside bdry
Hình ảnh minh họa trích từ nguồn Vanderbilt University
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 42
binary image
dilation by plus is
8-conn outside bdry is
original
in dilation by square
in 4-conn outside bdry
Hình ảnh minh họa trích từ nguồn Vanderbilt University
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 43
inside boundaries
are disjoint from
outside boundaries
8-bdry/4-bdry/orig
all 4 boundaries
orig/8-bdry/4-bdry
Hình ảnh minh họa trích từ nguồn Vanderbilt University
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 44
Đa giác A được gọi là đa giác lồi (convex) nếu một đường thẳng nối 2 điểm bất kì thuộc A phải nằm trong A
Bao lồi (convex hull) H của một tập bất kì S là một đa giác lồi nhỏ nhất chứa tất cả các điểm thuộc S
Tập được tạo thành bởi H-S được gọi là tập
thiếu của S
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 45
Cho Bi, i=1,2,3,4 biểu diễn 4 thành phần cấu trúc Quy trình bao gồm việc thực hiện các phương trình
Đặt , khi bước thực hiện phương trình
trên đạt được Bao lồi của A là
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 46
Đặt Thực hiện với B1
Thực hiện biến đổi Hit or Miss tập A với B1 cho đến khi không biến đổi được nữa, ta được tập đích Xn.
Hợp Xn với A, gọi là D1
Thực hiện tương tự với B2, B3, và B4; thu được D2,
D3 và D4
Hợp của D1, D2, D3, D4 là bao lồi tìm theo thuật toán
này
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 47
x
Don’t care
B2
B4
x
x
x
B3 x
B1 x
Background
x
x
x
x
x
x
x
x
x x x
x
x x x
Foreground
A
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 48
x
x
x x x
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 49
x
x
x
x
x
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 50
x
x x x
x
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 51
x
x
x
x
x
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 52
D1
D3
D2
D4
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 53
Tham khảo mã nguồn openCV_ConvexHull
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 54
Làm mỏng một tập A theo một phần tử cấu trúc B
Hit-or-miss transformation
được xác định:
Có thể dùng nhiều SE để làm mảnh A
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 55
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 56
Quá trình làm dày A theo phần tử cấu trúc B được
Hit-or-miss transformation
xác định
Quá trình làm dày cũng được xác định qua một
chuỗi phần tử cấu trúc.
SE của thickening tương tự như SE của thinning
nhưng hoán vị vai trò của zero và 1
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 57
Tham khảo mã nguồn openCV_ConvexHull
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 58
Đặt Skel(I,r) là tập các pixel trong I sao cho nếu p Skel(I,r) thì Dp(r), là maximal disk bán kính r trong I. Nghĩa là, Skel(I,r) là quỹ đạo của các tâm của maximal disks bán kính r trong I. Thì
Xương của I là hội của tập tất cả tâm của maximal
disk.
Maximal disk Dp(r) tiếp xúc với biên của I ít nhất tại
hai điểm.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 59
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 60
Ảnh gốc
skeleton thô (đỏ)
Tỉa nhánh và connected
skeleton
Là tập những tâm của maximal disks.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 61
non maximal “disks”
maximal disks (red)
non max & max disks
non max disks (blue)
“disks” are squares
over skeleton
Maximal disk tại pixel p là đĩa lớn nhất fg có chứa p.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 62
non maximal “disks”
maximal disks (red)
non max & max disks
non max disks (blue)
“disks” là các square
over skeleton
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 63
• SE = Z8 = = Sq(3) • n = 0: SE = 1 pixel
l
• n = 1: SE = Sq(3)
i
1 = n e d o r e
3 = n e d o r e
0 = n e d o r e
2 = n e d o r e
a n g i r o
• n = 2: SE = Sq(5)
• n = 3: SE = Sq(7)
l
) 1 = n ( Z
) 1 = n ( Z
) 1 = n ( Z
) 1 = n ( Z
/
/
/
/
e v o b a n e p o
w
e v o b a n e p o
w
e v o b a n e p o
w
e v o b a n e p o
w
n o t e e k s
4
l l
l
l
l
l
i
i
i
i
e d d m
e d d m
e d d m
e d d m
i
) 1 , I ( l e k S
) 3 , I ( l e k S
) 0 , I ( l e k S
) 2 , I ( l e k S
a f o n o n u
t h g i r e h t o t
- p o t
- p o t
- p o t
- p o t
Note that the result is disconnected and has spurious points.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 64
Skeleton thô
Xem các pixel giả là
Tỉa nhánh
Có các pixel “giả”
Tốt hơn
Thành phần liên thông Ít hơn 3 pix.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 65
2 components
2 other components
Giao của
of pruned skel dilated.
pruned skel. dilated.
Các thành phần dilated.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 66
Skeleton thô
Skeleton tỉa nhánh
reconnected skeleton
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 67
Một trong những cách biểu diển Skeleton của một
tập hợp là biểu diển qua openning và erosion.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 68
Quá trình rút xương có thể được biểu diển qua các các thao tác xói mòn (erosion) và mở (opening).
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 69
Tham khảo mã nguồn openCV_Skeleton
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 70
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 71
