Bài giảng Xử lý ảnh số - Chương 6: Phân đoạn ảnh - Võ Quang Hoàng Khang (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