Bài giảng Xử lý ảnh số - Phân tích ảnh. Phân vùng ảnh - Nguyễn Linh Giang

Xử lý ảnh số
Phân tích ảnh
Phân vùng ảnh ( Segmentation )
Chương trình dành cho kỹ sư CNTT
Nguyễn Linh Giang
Phân vùng ảnh
• Khái niệm vùng ảnh và phân vùng ảnh;
• Phân vùng ảnh dựa trên ngưỡng;
• Phân vùng ảnh dựa trên đường biên;
• Phân vùng ảnh dựa trên các miền;
• Đối sánh;
• Các hướng tiếp cận tiên tiến
• Bài toán phân vùng ảnh:
– Phân tách ảnh thành những tập hợp điểm không 
giao nhau ( phân hoạch )
– Mục đích: phục vụ bài toán nhận dạng ảnh, hiểu 
ảnh và những bài toán liên quan tới xử lý vùng;
– Phân vùng ảnh là bài toán xác định yếu ( ill-
defined ):
• Việc xác định các vùng ảnh phụ thuộc vào ngữ cảnh.
Vùng ảnh và phân vùng ảnh
Vùng ảnh và phân vùng ảnh
• Khái niệm vùng ảnh:
– Xác định toán tử P là phép toán xác định trên vùng ảnh. Điểm 
ảnh x được coi là nằm trong vùng ảnh xác định qua toán tử P: 
P(x) = true nếu điểm ảnh x thỏa mãn những tính chất xác định.
– Ví dụ về các toán tử vùng:
• Các giá trị mức xám trong một khoảng ( ngưỡng )
• Gradient của các giá trị mức xám trong một khoảng ( biên )
• Phân bố thống kê như nhau ( kết cấu bề mặt ) 
– Sau khi áp dụng các toán tử xác định vùng, ảnh trở thành ảnh 
nhị phân. Sử dụng các định nghĩa về tính liên thông, ta có thể 
xác định được các vùng ảnh.
• Các phương pháp phân vùng ảnh
– Phân vùng dựa trên đường biên:
• Xác định đường ranh giới giữa những vùng lân cận;
– Phân vùng dựa trên ngưỡng:
• Tìm các vùng ảnh bằng cách nhóm các điểm có giá trị mức 
xám tương tự nhau;
– Phân vùng ảnh dựa trên các miền:
• Xác định trực tiếp các vùng ảnh dựa trên việc gia tăng hoặc 
phân chia vùng; 
– Phân vùng dựa trên chuyển động:
• Xác định vùng dựa trên việc so sánh các khung video liên 
tiếp trong một chuỗi video để xác định các vùng tương ứng 
với đối tượng chuyển động;
Vùng ảnh và phân vùng ảnh
Vùng ảnh phân vùng ảnh
• Biểu diễn vùng ảnh:
– Biểu diễn bằng mã loạt dài ( run-length code )
• Vùng trên ảnh nhị phân là chuỗi các giá trị 0 và 1;
– Biểu diễn bằng các miền và cây tứ phân
Vùng ảnh phân vùng ảnh
Phân vùng ảnh dựa trên ngưỡng
• Cơ sở phương pháp
– Khi đối tượng và nền được nhóm lại trong các vùng
– Lựa chọn ngưỡng T để phân tách vùng:
– Điểm ảnh p(x, y): 
• Nếu: F(x, y) > T => p(x, y) thuộc đối tượng;
• Nếu: F(x, y) p(x, y) thuộc nền.
– Mở rộng: lấy đa ngưỡng:
• Khi có nhiều vùng ảnh phân tách, có thể lấy nhiều ngưỡng T1, T2, T3, 
...
Phân vùng ảnh dựa trên ngưỡng
– Lấy ngưỡng có thể coi là bài toán xác định hàm T: 
T = T[ x, y, p(x, y), f( x, y )]
• f(x, y ): biểu diễn mức xámcủa điểm (x, y);
• p(x, y): là hàm mô tả thuộc tính cục bộ của điểm ảnh;
– Ví dụ: p(x, y) là mức xám trung bình trong lân cận điểm (x, y);
– Ảnh sau khi lấy ngưỡng là:
– Nếu:
• Ngưỡng T chỉ phụ thuộc f(x,y): ngưỡng toàn cục;
• Ngưỡng T phụ thuộc vào cả f(x, y) và p(x, y): ngưỡng cục bộ;
• Ngưỡng T phụ thuộc vào các tọa độ x, y: ngưỡng động
⎩⎨
⎧
<
>=
T yxf 
T yxf 
yxg
),( if ,0
 ),( if ,1
),(
Phân vùng ảnh dựa trên ngưỡng
– Kết quả phương pháp:
– Ví dụ lấy ngưỡng toàn cục:
j , , 
1
≠∅=∩=
=
iRRRR jii
n
i
U
• Các tiêu chuẩn lựa chọn ngưỡng:
– Xác suất lỗi cực tiểu
– Giá cực tiểu
– Phương sai trong nhóm cực tiểu
– Kiểm tra bằng mắt
Phân vùng ảnh dựa trên ngưỡng
• Ví dụ lấy ngưỡng:
Ngưỡng quá thấp
Ngưỡng thích hợp
Ngưỡng quá cao
Phân vùng ảnh dựa trên ngưỡng
• Lấy ngưỡng theo kiểm chứng
– Đặt vấn đề: điểm (x,y) với cường độ sáng u nằm trong 
vùng hay không ?
– Hai khả năng:
• H0: không nằm trong vùng;
• H1: nằm trong vùng;
– Các xác suất:
• Xác suất tiên nghiệm: P1 = p(z∈H0) , P2 = p(z∈H1)
• Hàm khả năng: p(z|z∈H0) = p1(z), p(z| z∈ H1) = p2(z)
Phân vùng ảnh dựa trên ngưỡng
– Các tiêu chuẩn xác định ngưỡng:
• Khả năng cực đại (Maximum likelihood):
– Điểm (x, y) có giá trị z nằm trong vùng nếu:
p(z|H1) > p(z|H0)
• Luật Bayes:
P2 p(z|H1) > P1 p(z|H0)
Phân vùng ảnh dựa trên ngưỡng
Phân vùng ảnh dựa trên ngưỡng
• Ví dụ trường hợp phân bố Gauss:
– Cho 
– Xác định ngưỡng T, giải phương trình:
P1 p1(T) = P2 p2(T) 
– Lấy logarithm cả hai vế ta đưa về phương trình:
AT2 + BT + C = 0
( )
⎟⎟⎠
⎞
⎜⎜⎝
⎛ −−= 2
2
2
exp
2
1)(
i
i
i
zzp σ
µ
σπ
2
2
2
1 σσ −=A ( )2122212 σµσµ −=B
⎟⎟⎠
⎞
⎜⎜⎝
⎛+−=
21
122
2
2
1
2
1
2
2
2
2
2
1 ln2 P
PC σ
σσσµσµσ
⎟⎟⎠
⎞
⎜⎜⎝
⎛⋅−+
+===
1
2
21
2
21
21 ln2
 then, If
P
PT µµ
σµµσσσ
Phân vùng ảnh dựa trên ngưỡng
• Phương pháp sử dụng phân nhóm:
– Mỗi điểm tương ứng với một vector đặc trưng:
s = [s1, s2, ..., sn]
– Các đặc trưng có thể có:
• Các giá trị đa phổ;
• Giá trị các thành phần màu sắc;
• Các độ đo các lân cận điểm như trung bình trong các 
cửa sổ chạy;
• Độ lệch tiêu chuẩn
– Phân nhóm các điểm với những đặc trưng gần 
giống nhau vào cùng một phân nhóm.
– Bài toán phân nhóm: 
• Cho tập các vector: {sk; 1 ≤ k ≤ K},
• Xác định M phân nhóm với các tâm {w(i); 1 ≤ i ≤ c}, sao 
cho các vector sk được đưa vào một phân nhóm thỏa mãn 
điều kiện tối thiểu hóa sai số khoảng cách:
– Trong đó
• I(sk,i) = 1 nếu sk được gán vào phân nhóm i với trọng tâm 
w(i); 
• I(sk,i) = 0 trong những trường hợp khác.
∑∑
= =
=
c
i
K
k
kk iWxdixIK
D
1 1
))(,(),(1
Phân vùng ảnh dựa trên ngưỡng
– Các thuật toán phân nhóm: K-means, ISODATA
– Thuật toán K-means:
• Số phân lớp – K, số điểm: n;
• B1: Lựa chọn bất kỳ K tâm các phân nhóm;
• B2: Phân loại n điểm vào K phân lớp theo tiêu chuẩn 
khoảng cách gần nhất;
• B3: Tính lại các tâm phân nhóm theo luật trung bình; 
Quay lại bước phân loại
• ....
• Lần phân loại thứ i+1: nếu tâm các phân nhóm ở lần thứ 
i+1 không dịch chuyển so với lần thứ i: dừng thuật toán.
Phân vùng ảnh dựa trên ngưỡng
– Thuật toán ISODATA:
• Cải tiến so với K-means:
– Thay đổi số phân nhóm một cách tự động:
– Nếu một phân nhóm quá tản mạn thì được tách làm 2;
– Nếu hai phân nhóm khá gần nhau thì nhập làm một.
– Bổ sung thêm:
» Tính khoảng cách trung bình giữa những phần tử trong 
một phân nhóm Ci với tâm zi;
» Tính khoảng cách trung bình của tất cả các phần tử trong 
các phân nhóm đến các tâm;
» Tính độ lệch tiêu chuẩn trung bình giữa các phần tử trong 
phân nhóm với tâm theo từng chiều
– Các giá trị này phục vụ quá trình phân tách và kết hợp các 
phân nhóm.
Phân vùng ảnh dựa trên ngưỡng
• Các phương pháp dựa trên vùng thích hợp trong trường 
hợp ảnh có nhiễu và xác định đường biên giữa các vùng 
khá phức tạp. 
• Tiêu chuẩn xác định tính đồng nhất của vùng đóng vai 
trò quan trọng trong các phương pháp dựa trên miền; 
• Một số tiêu chuẩn tính đồng nhất:
– Theo giá trị mức xám;
– Theo màu sắc, kết cấu bề mặt;color, texture 
– Theo hình dạng;
– Theo mô hình;
– Các phương pháp khác.
Phân vùng ảnh dựa trên miền ảnh
Phân vùng ảnh dựa trên miền ảnh
• Vị từ xác định vùng ảnh:
– Xác định các vùng trực tiếp
– Quá trình phân vùng chia ảnh thành các miền {Ri} 
thỏa mãn:
– Các vùng ảnh được xác định theo vị từ P sao cho:
• P(Ri) = TRUE nếu tất cả các điểm trong vùng thỏa mãn 
những thuộc tính xác định;
• P(Ri∩Rj) = FALSE đối với i ≠j. 
j , , 
1
≠∅=∩=
=
iRRRR jii
n
i
U
• Các phương pháp:
– Phương pháp gia tăng vùng ( Region-Growing )
• Quá trình bắt đầu từ những điểm hạt giống
• Quá trình gia tăng thực hiện bao quanh điểm hạt giống 
bằng cách gắn những điểm lân cận có cùng tính chất với 
vùng ảnh.
– Phân chia và kết hợp vùng
• Áp dụng vị từ xác định vùng cho những vùng con;
• Nếu vị từ cho giá trị TRUE, dừng quá trình phân chia;
• Nếu vị từ cho giá trị FALSE, phân chia vùng;
• Cây tứ phân là một phương pháp chí vùng;
• Những vùng con có cùng một tính chất ( xác định theo vị 
từ P ) sẽ được hợp lại.
Phân vùng ảnh dựa trên miền ảnh
• Phương pháp kết hợp vùng
– Thuật toán cơ sở:
• Xác định phương pháp phân chia ảnh thành những vùng 
nhỏ thỏa mãn điều kiện P(Ri) = TRUE ;
• Xác định tiêu chuẩn hợp hai miền liền kề;
• Kết hợp các miền liền kề thỏa mãn điều kiện hợp. Nếu 
không có hai miền nào có thể hợp mà không phá vỡ 
điều kiện vùng, dùng thuật toán.
– Các phương pháp hợp vùng ảnh khác nhau ở quá 
trình xác định vùng ban đầu và tiêu chuẩn hợp;
– Kết quả hợp vùng phụ thuộc vào trình tự hợp của 
các vùng.
Phân vùng ảnh dựa trên miền ảnh
– Phương pháp đơn giản nhất bắt đầu bằng cách sử dungnj 
vùng ảnh kích thước 2x2, 4x4 hoặc 8x8 điểm; 
– Các vùng được mô tả bằng các thuộc tính thống kê mức xám; 
– Các biểu diễn vùng được so sánh với điều kiện liền kề.
• Nếu điều kiện liền kề được thỏa mãn, các vùng này được kết hợp lại 
thành vùng lớn hơn và thuộc tính vùng mới được xác định;
• Nếu điều kiện này không được thỏa mãn, các vùng được đánh dấu là 
không tương hợp;
– Quá trình hợp các vùng liền kề được thực hiện giữa tất cả các 
lân cận, kể cả những vunngf lân cận mới được tạo ra;
– Nếu một vùng không thể hợp với bất kỳ vùng lân cận nào, 
vùng sẽ được đánh dấu là kết thúc và quá trình hợp vùng 
dừng lại khi tất cả các vùng được đánh dấu là kết thúc.
Phân vùng ảnh dựa trên miền ảnh
Phân vùng ảnh dựa trên miền ảnh
– Cấu trúc lưới chứa thông tin phục vụ quá trình hợp vùng 4-liên 
thông sử dụng các giá trị biên.
– Một số heuristic: 
• Hai vùng liền kề có thể kết hợp lại nếu phần lớn biên chung chứa các 
điểm biên yếu;
• Hai vùng liền kề có thể kết hợp lại nếu phần lớn biên chung chứa các 
điểm biên yếu nhưng trong trường hợp này không tính đến độ dài tổng 
cộng của đường biên của vùng.
Phân vùng ảnh dựa trên miền ảnh
– Tính quan trọng của biên được tính theo hệ thức:
Trong đó vij = 1 có nghĩa là điểm biên quan trọng
vij = 0 chỉ biên yếu
T1 ngưỡng cho trước
sij là giá trị biên và bằng sij = |f(xi) - f(xj)|
⎩⎨
⎧
>
<=
 s if ,1
s if ,0
1ji,
1ji,
T
T
vij
Phân vùng ảnh dựa trên miền ảnh
– Thuật toán kết hợp vùng qua đường biên:
• Xác định các vùng với mức xám không đổi. Xây dựng cấu trúc lưới 
chứa thông tin giá trị biên;
• Loại bỏ các điểm biên có giá trị biên nhỏ hơn ngưỡng;
• Loại bỏ các biên chung giữa hai miền liền kề Ri, Rj bằng đệ quy nếu
Trong đó W là số lượng các điểm biên yếu trên đường biên chung, li
và lj là độ dài chu vi ngoài của các vùng Ri, Rj, T2 là ngưỡng;
• Loại bỏ các biên chung giữa hai miền liền kề Ri, Rj bằng đệ quy nếu
hoặc W >= T3 
trong đó l là độ dài đường biên chung và T3 là ngưỡng
2),min(
T
ll
W
ji
≥
3Tl
W ≥
• Phân chia vùng ảnh
– Phân chia vùng là bài toán ngược với hợp vùng;
– Quá trình phân chia bắt đầu từ toàn bộ ảnh như một vùng lớn 
và không thỏa mãn điều kiện đồng nhất;
– Các vùng ảnh được phân chia tuần tự để thỏa mãn các điều 
kiện đồng nhất;
– Quá trình phân chia vùng không cho cùng một kết quả thậm 
chí cả khi sử dụng cùng một tuêi chí đồng nhất;
– Bài toán phân chia vùng sử dụng cùng một tiêu chuẩn đồng 
nhất như trong phương pháp hợp vùng. Điểm khác biệt: 
hướng ứng dụng.
Phân vùng ảnh dựa trên miền ảnh
Phân vùng ảnh dựa trên miền ảnh
• Phương pháp kết hợp: phân 
chia và hợp vùng:
– Xác định các vùng khởi tạo, 
các điều kiện đồng nhất, cấu 
trúc tứ diện;
– Nếu vùng R trong cấu trúc tứ 
diện không đồng nhất ( 
H(R)=FALSE ), chia vùng 
thành 4 vùng con; Nếu 4 
vunngf có cùng một cha có 
thể kêt hợp thì kết hợp thành 
một;
– Nếu hai vùng liền kề không 
cùng cha và thỏa mãn điều 
kiện đồng nhất, hợp hai vùng 
này lại.