Bài giảng Xử lý ảnh số - Chương 7: Xử lý ảnh dựa trên Morphological - Ngô Quang Việt

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) 2 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt  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 3 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt  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 4 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 5  Cải tiến ảnh (image enhancement)  Phân đoạn ảnh (image segmentation)  Phục hồi ảnh (image restoration)  Dò cạnh  Phân tích Texture (texture analysis)  Phân tích particle  Phát sinh đặc trưng (feature generation)  Trích xương (Skeletonization)  Phân tích hình dáng (shape analysis)  Nén ảnh (Image compression)  Phân tích thành phần (Component analysis)  Curve filling  Làm mỏng tổng quát (General thinning)  Tìm đặc trưng (Feature detection)  Giảm nhiễu (Noise reduction)  Lọc không-thời gian (Space-time filtering) Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 6 Ả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 7 Foreground của ảnh nhị phân Tập các vị trí p, với I(p) = vfg. Tương tự background là       P fgFG I I , , I( ) ,r c S v   p p p       P bgBG I I , , I( ) .r c S v   p p p Chú ý     IIBGIFG       IBGIFGvà và     CIFGIBG  và      .IBGIFG C Background là bù của foreground và ngược lại. Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 8 A ={(3,1), (4,1),(3,2),(4,2),(3,3)}. Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 9 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 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. E xa m p le S E s FG is g ray ; B G is w h ite Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 10 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 gọi là Z-neighborhood 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 11 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ó. )(sup),(),,(),( ZpbabaZbaZ   ZlàZ   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  BzAazaZAZAD  ,|),( Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 13 Một số định nghĩa khác về dilation.   . I)(I P  pp ZSZ   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.   .)(I Isupp    p pZZ 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.   .)I(I supp  Z Z   p p 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 14 A1 = A tịnh tiến bởi vector (0,0) của Z A2 = A tịnh tiến bởi vector (0,1) của Z A = {(2,1),(3,1),(4,1),(3,2)} Z = {(0,0),(0,1)} A2 = {(2,2),(3,2),(4,2),(3,3)} D(A,B) = A1 U A2 = {(2,1),(3,1),(4,1),(3,2), (2,2),(4,2),(3,3)} A1 = {(2,1),(3,1),(4,1),(3,2)} AZ Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 15  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           111 111 111 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”. Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 16 Ảnh nguồn SE Đã giãn 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 ky ̀ , 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 },|{),( ZzAzxxZAE  Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 19 Một số định nghĩa khác     .I I Zsupp     p pZ 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. Tập tất cả các pixel p, trong ảnh sao cho Z+p chứa trong I.  Ipp I p  ZSZ 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.     . I Isupp     p pZZ  20 A = {(1,1),(2,1),(3,1),(4,1),(1,2),(3,2),(1,3),(2,3)} Z= {(1,0),(0,1)} 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) E(A,Z) = {(1,1),(3,1),(2,2)} 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 Ảnh nguồn SE Eroded 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 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 23 )()( CBACBA  ),(),( ABDABBABAA   cc ZZ II      .I I cc ZZ   và Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 24  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 25 Opening Closing  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 : Ứ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 Kết quả Phép mở Kết quả Phép đóng Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 29 “L” shaped SE O marks origin Foreground: white pixels Background: black pixels Cross-hatched pixels are indeterminate. Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 30 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 : 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 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 37 original binary image erosion by square 8-connected SE difference 4-conn inside bdry Hình ảnh minh họa trích từ nguồn Vanderbilt University  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ài giảng Xử lý ảnh - TS. Ngô Quốc Việt 38 B A A Θ B ∂A Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 39 original Ảnh nhị phân erosion by plus 4-connected SE Ảnh hiệu - Difference 8-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 40 original binary image dilation by plus 4-connected SE difference 8-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 41 original binary image dilation by square 8-connected SE difference 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 42 original binary image in erosion by plus erosion by square is in 4-conn inside bdry 8-conn inside bdry is 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 original binary image in dilation by square dilation by plus is in 4-conn outside bdry 8-conn outside bdry is 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 8-bdry/4-bdry/orig inside boundaries all 4 boundaries are disjoint from orig/8-bdry/4-bdry outside boundaries Hình ảnh minh họa trích từ nguồn Vanderbilt University  Đ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 ,...3,2,1;4,3,2,1,)( 1   kiABXX i k i k AX i 0 i conv i XD   4 1 )(   i iDAC i k i k XX 1  Đặ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à D 1  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 AXXXX  40 3 0 2 0 1 0 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 48 x x x x x x x x x x x x x x x x x x x x B1 B2 B3 B4 x Don’t care Background Foreground A 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 x x x x x Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 53  4 1 )(   i iDAC D1 D2 D3 D4 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 đượ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 Hit-or-miss transformation 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 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 Hit-or-miss transformation 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 ),I(Skel 0 rS r     Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 60 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 61 Ảnh gốc skeleton thô (đỏ) Là tập những tâm của maximal disks. Tỉa nhánh và connected skeleton Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 62 maximal disks (red) non max disks (blue) non max & max disks over skeleton non maximal “disks” “disks” are squares 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 63 maximal disks (red) non max disks (blue) non max & max disks over skeleton non maximal “disks” “disks” là các square Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 64 o ri g in al er o d e n = 0 er o d e n = 1 er o d e n = 2 er o d e n = 3 o p en a b o ve w / Z ( n = 1) o p en a b o ve w / Z ( n = 1) o p en a b o ve w / Z ( n = 1) o p en a b o ve w / Z ( n = 1) to p - m id d le to p - m id d le to p - m id d le to p - m id d le u n io n o f al l 4 t o t h e ri g h t sk el et o n • SE = Z8 = = Sq(3) • n = 0: SE = 1 pixel • n = 1: SE = Sq(3) • n = 2: SE = Sq(5) • n = 3: SE = Sq(7) Note that the result is disconnected and has spurious points. S ke l( I, 0 ) S ke l( I, 1 ) S ke l( I, 2 ) S ke l( I, 3 ) Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 65 Xem các pixel giả là Thành phần liên thông Ít hơn 3 pix. Tỉa nhánh Tốt hơn Skeleton thô Có các pixel “giả” Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 66 2 other components of pruned skel dilated. Giao của Các thành phần dilated. 2 components pruned skel. dilated. Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 67 Skeleton thô Skeleton tỉa nhánh reconnected skeleton  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