Bài giảng môn Xử lý ảnh số - Chương 6: Phân đoạn ảnh (phần 3)

Chương 6: PHÂN ĐOẠN ẢNH (P3) Võ Quang Hoàng Khang TPHCM - 2016  Phương pháp dựa trên Watersheds  Cách tiếp cận vấn đề  Mô tả thuật toán  Ví dụminh họa 2 3of 17 Topographic principle  Ảnh được xem như là một bề mặt địa hình 3D với các vùng thấp và cao khác nhau, mỗi pixel (x,y) tương ứngmột điểm (x,y, h) trên bề mặt, với chiều cao h là mức xám (gray level) của điểm ảnh 4of 17 Idea proposal(by flooding) – Ý tưởng  S. Beucher and C. Lantuejoul (1979). “Use of watershed in contour detection”. In Proceedings of the International Workshop on Image Processing, Real-time Edge and Motion Detection (1979). 5of 17 Các biến đổi - Variants  Watershed by flooding  Inter-pixel watershed  Watershed by topographic distance (xem thêm)  Topological watershed (xem thêm)  etc 6of 17 Watershed by flooding  Bề mặt địa hình 3D của một ảnh: − Ảnh được hình dung như bề mặt 3D bằng cách sử dụng tọa độ không gian và mức xám của điểm ảnh  Mỗi điểm ảnh được xác định bởi bộ ba (x,y,g), với x,y là tọa độ không gian và g là mức xám của nó. original image 7of 17 3 types of points - 3 loại điểm  Điểm cực tiểu vùng (regional minimum)  Điểm catchment basin hay watershed của điểm cực tiểu vùng: là điểm chỉ giảm về duy nhất 1 cực tiểu vùng  Điểm crest line hay watershed lines. Mỗi điểm crest là điểm có khả năng giảm về nhiều hơn một cực tiểu vùng  Phương pháp này mục tiêu là xác định tất cả các pixel thuộc về loại thứ 3 (point of watershed line) 8of 17 3 types of points 9of 17 Mục tiêu  Tìm watershed line 10 of 17 Ý tưởng cơ bản  Ý tưởng đơn giản:  Tưởng tưởng một lỗ được thực hiện thông qua mỗi cực tiểu vùng do đó toàn bộ địa hình sẽ bị ngập nước khi tăng dần mức nước từ dưới lên  Khi nước dâng cao đến mức các catchment basin bắt đầu hòa nhập, Dam sẽ được xây dựng để ngăn chặn việc hòa nhập. Những đường biên Dam chính là watershed line 11 of 17 Ý tưởng cơ bản 12 of 17 Flooding paradigm 13 of 17 Thuật toán  Các bước cơ bản: − Bắt đầu với tất cả các điểm ảnh có giá trị thấp nhất: khởi tạo ban đầu cho watershed − Với mỗi cường độ k  Với mỗi tập pixels có cường độ = k If tiếp giáp với duy nhất một vùng hiện có, thêm các điểm đó vào vùng hiện tại Else If tiếp giáp với nhiều hơn 1 vùng, đánh dấu điểm này là biên Else phát hiện vùng mới 14 of 17 Example 15 of 17 Flooding algorithm - Example 3 3 5 5 105 10 3 3 5 10 10 10 5 5 3 5 10 1 1 3 3 5 5 1 10 1 15 1 15 10 5 13 5 10 15 11 10 15 20 15 20 1515 1 1 115 15 20 1 1 110 10 10 1 1 1 1 1 5 5 5 0 30 30 30 30 3020 20 20 20 20 20 10 5 10 10 10 10 40 40 40 40 40 40 40 4020 20 20 20 20 2040 40 40 40 1 1 0 3 3 10 5 3 40 1 1 3 3 5 5 105 10 10 1 1 110 15 203 15 10 5 13 5 10 15 201 01 1 1 20 20 120 110 1 1 5 0 40 0 120 0 16 of 17 Flooding algorithm - Example 3 3 5 5 105 10 3 3 5 10 10 10 5 5 3 5 10 1 1 3 3 5 5 1 10 1 15 1 15 10 5 13 5 10 15 11 10 15 20 15 20 1515 1 1 115 15 20 1 1 110 10 10 1 1 1 1 1 5 5 5 0 30 30 30 30 3020 20 20 20 20 20 10 5 10 10 10 10 40 40 40 40 40 40 40 4020 20 20 20 20 2040 40 40 40 1 1 0 3 3 10 5 3 40 1 1 3 3 5 5 105 10 10 1 1 110 15 203 15 10 5 13 5 10 15 201 01 1 1 20 20 120 110 1 1 5 0 40 0 120 0 17 of 17 Flooding algorithm - Example 3 3 5 5 105 10 3 3 5 10 10 10 5 5 3 5 10 1 1 3 3 5 5 1 10 1 15 1 15 10 5 13 5 10 15 11 10 15 20 15 20 1515 1 1 115 15 20 1 1 110 10 10 1 1 1 1 1 5 5 5 0 30 30 30 30 3020 20 20 20 20 20 10 5 10 10 10 10 40 40 40 40 40 40 40 4020 20 20 20 20 2040 40 40 40 1 1 0 3 3 10 5 3 40 1 1 3 3 5 5 105 10 10 1 1 110 15 203 15 10 5 13 5 10 15 201 01 1 1 20 20 120 110 1 1 5 0 40 0 120 0 18 of 17 Flooding algorithm - Example 3 3 5 5 105 10 3 3 5 10 10 10 5 5 3 5 10 1 1 3 3 5 5 1 10 1 15 1 15 10 5 13 5 10 15 11 10 15 20 15 20 1515 1 1 115 15 20 1 1 110 10 10 1 1 1 1 1 5 5 5 0 30 30 30 30 3020 20 20 20 20 20 10 5 10 10 10 10 40 40 40 40 40 40 40 4020 20 20 20 20 2040 40 40 40 1 1 0 3 3 10 5 3 40 1 1 3 3 5 5 105 10 10 1 1 110 15 203 15 10 5 13 5 10 15 201 01 1 1 20 20 120 110 1 1 5 0 40 0 120 0 19 of 17 Flooding algorithm - Example 3 3 5 5 105 10 3 3 5 10 10 10 5 5 3 5 10 1 1 3 3 5 5 1 10 1 15 1 15 10 5 13 5 10 15 11 10 15 20 15 20 1515 1 1 115 15 20 1 1 110 10 10 1 1 1 1 1 5 5 5 0 30 30 30 30 3020 20 20 20 20 20 10 5 10 10 10 10 40 40 40 40 40 40 40 4020 20 20 20 20 2040 40 40 40 1 1 0 3 3 10 5 3 40 1 1 3 3 5 5 105 10 10 1 1 110 15 203 15 10 5 13 5 10 15 201 01 1 1 20 20 120 110 1 1 5 0 40 0 120 0 20 of 17 Flooding algorithm - Example 3 3 5 5 105 10 3 3 5 10 10 10 5 5 3 5 10 1 1 3 3 5 5 1 10 1 15 1 15 10 5 13 5 10 15 11 10 15 20 15 20 1515 1 1 115 15 20 1 1 110 10 10 1 1 1 1 1 5 5 5 0 30 30 30 30 3020 20 20 20 20 20 10 5 10 10 10 10 40 40 40 40 40 40 40 4020 20 20 20 20 2040 40 40 40 1 1 0 3 3 10 5 3 40 1 1 3 3 5 5 105 10 10 1 1 110 15 203 15 10 5 13 5 10 15 201 01 1 1 20 20 120 110 1 1 5 0 40 0 120 0 21 of 17 30 30 3030 Flooding algorithm - Example 3 3 5 5 105 10 3 3 5 10 10 10 5 5 3 5 10 1 1 3 3 5 5 1 10 1 15 1 15 10 5 13 5 10 15 11 10 15 20 15 20 1515 1 1 115 15 20 1 1 110 10 10 1 1 1 1 1 5 5 5 0 30 20 20 20 20 20 20 10 5 10 10 10 10 40 40 40 40 40 40 40 4020 20 20 20 20 2040 40 40 40 1 1 0 3 3 10 5 3 40 1 1 3 3 5 5 105 10 10 1 1 110 15 203 15 10 5 13 5 10 15 201 01 1 1 20 20 120 110 1 1 5 0 40 0 120 0 22 of 17 Flooding algorithm - Example 3 3 5 5 105 10 3 3 5 10 10 10 5 5 3 5 10 1 1 3 3 5 5 1 10 1 15 1 15 10 5 13 5 10 15 11 10 15 20 15 20 1515 1 1 115 15 20 1 1 110 10 10 1 1 1 1 1 5 5 5 0 30 30 30 30 3020 20 20 20 20 20 10 5 10 10 10 10 40 40 40 40 40 40 40 4020 20 20 20 20 2040 40 40 40 1 1 0 3 3 10 5 3 40 1 1 3 3 5 5 105 10 10 1 1 110 15 203 15 10 5 13 5 10 15 201 01 1 1 20 20 120 110 1 1 5 0 40 0 120 0 23 of 17 Flooding algorithm - Example 3 3 5 5 105 10 3 3 5 10 10 10 5 5 3 5 10 1 1 3 3 5 5 1 10 1 15 1 15 10 5 13 5 10 15 11 10 15 20 15 20 1515 1 1 115 15 20 1 1 110 10 10 1 1 1 1 1 5 5 5 0 30 30 30 30 3020 20 20 20 20 20 10 5 10 10 10 10 40 40 40 40 40 40 40 4020 20 20 20 20 2040 40 40 40 1 1 0 3 3 10 5 3 40 1 1 3 3 5 5 105 10 10 1 1 110 15 203 15 10 5 13 5 10 15 201 01 1 1 20 20 120 110 1 1 5 0 40 0 120 0 24 of 17 Xây dựng Dam – Dam construction  Nguyên tắc:  Dam được xây dựng để ngăn chặn việc sáp nhập của 2 catchment basins  Thuật toán: − Khởi tạo, tập các pixel mức xám cực tiểu là 1, còn lại là 0. − Làm ngập bề mặt địa hình 3D từ dưới lên − Nếu tại mức n-1, có hai thành phần kết nối và tại mức n chỉ có một thành phần kết nối thì:  Hai catchment basin được trộn lại tại mức n  Bắt đầu xây dựng Dam cho thành phần kết nối đơn này. 25 of 17 Xây dựng Dam – Dam construction  Nguyên tắc:  Dam được xây dựng để ngăn chặn việc sáp nhập của 2 catchment basins  Thuật toán: − Khởi tạo, tập các pixel mức xám cực tiểu là 1, còn lại là 0. − Làm ngập bề mặt địa hình 3D từ dưới lên − Nếu tại mức n-1, có hai thành phần kết nối và tại mức n chỉ có một thành phần kết nối thì:  Hai catchment basin được trộn lại tại mức n  Bắt đầu xây dựng Dam cho thành phần kết nối đơn này. 26 of 17 Watershed Transform  M1, M2, , MR: các cực tiểu địa phương của ảnh (gradient) g(x,y)  C(Mi): tập các điểm thuộc về catchment basin kết hợp với cực tiểuMi  T[n]: tập các điểm (s,t) sao cho g(s,t)<n. g(s,t) là cường độ. Mi C(Mi) n-1 T(n) 27 of 17 Watershed Transform  Cn(Mi): tập các pixel thuộc về catchment basin kết hợp với cực tiểuMi tại mức n. Cn(Mi)= C(Mi) T[n]  C[n]: hợp của các catchment basin tại mức n.  Tại mức n, giả sử C[n-1] đã được xây dựng. Mục tiêu là xây dựng C[n] từ C[n-1] Mi C(Mi) n-1 T(n) Cn(Mi) C(n) R i i R i in MCCMCnC 11 )(]1[max and )(][   28 of 17 Watershed Transform  Khởi tạo: C[min+1]=T[min+1]  Với mỗi qT[n], có 3 khả năng xảy ra: 1. q C[n-1] rỗng (q1)  Phát hiện cực tiểu mới  q được đưa vào C[n-1] để tạo thành C[n] 2. q  C[n-1] chứa một thành phần kết nối của C[n-1] (q2)  q được đưa vào C[n-1] để tạo thành C[n] 3. q  C[n-1] chứa nhiều hơn một thành phần kết nối của C[n-1] (q3)  Dam được xây dựng để ngăn chặn sự hòa nhập giữa các catchment basin. (watershed line) 4. Lặp lại cho đến khi n=max+1 Cn-1(Mi) Mi C(Mi) n-2 T(n-1) C(n-1) n-1 T(n) q1 q2q3 Dam C(n) 29 of 17 Watershed segmentation 30 of 17 Over-segmentation problem  Hiện tượng over-segmentation có thể xảy ra 31 of 17 Over-segmentation: solution Marker-controlled watershed segmentation  Over-segmentation có thể được làm giảm bằng cách đánh dấu các mẫu trước khi qua biến đổi watershed  Loại bỏ một số cực tiểu giả (không đáng kể)  Ví dụ: giá trị mức xám có thể được sử dụng như là markers 32 of 17 Over-segmentation: solution 33 of 17 Over-segmentation: solution  FIRST: mark each blob of protein of the original image (bằng cách lấy các cực tiểu của các hàm ảnh) 34 of 17 Over-segmentation: solution  SECOND: by applying the watershed on the initial image we can mark the background with connected marker surrounding the blobs 35 of 17 Inter-pixel watershed segmentation  Ý tưởng đề xuất: − S. Beucher and F. Meyer (1993). The morphological approach to segmention: the watershed transformation. In Mathematical Morphology in Image Processing (Ed. E.R. Dougherty) pages 433-481 36 of 17 Thuật toán − Step 1: Gán nhãn khác biệt cho mỗi minimum. Khởi tạo tập S các điểm đã gán nhãn, V tập watershed line − Step 2: Chèn các pixel lân cận và chưa có nhãn vào hàng đợi ưu tiên Q, sắp xếp theo giá trị − Step 3: Lấy pixel x từ đầu hàng đợi Q sao cho thỏa F(x)=min{F(y) | y ∈ Q}:  Nếu x là lân cận với một nhãn, gán nhãn cho x (cùng nhãn), bổ sung vào S  Nếu x là lân cận với nhiều hơn một nhãn thì gán nhãn cho x là watershed line, bổ sung và V  Thêm các lân cận chưa được gán nhãn vào hàng đợi Q − Step 4: Lặp lại Step 3 cho đến khi Q rỗng 37 of 17 Bài tập 1. Ứng dụng thuật giải watershed trong phân tích vi ảnh grain 2. Tìm hiểu tài liệu, vấn đề, bài báo, chương trình máy tính liên quan đến nội dung bài học