PHÂN ĐOẠN ẢNH

NGÔ QUỐC VIỆT
TPHCM-2014


Bài giảng giúp

Người học hiểu về mục tiêu và ứng dụng của bài
toán phân đoạn ảnh
 Người học hiểu về lý thuyết và các phương pháp
phân đoạn ảnh
 Người học hiểu và cài đặt được phân đoạn ảnh tĩnh
hay động với thư viện OpenCV


Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt

2


Giới thiệu bài toán phân đoạn
Phân đoạn ảnh dựa trên các phương pháp phân
ngưỡng sắc xám

1.
2.



3.

Phân ngưỡng toàn cục
Phân ngưỡng thích nghi, và dựa trên phương pháp Otsu.

Phân đoạn ảnh dựa trên các phương pháp tương
tự

Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt

3




Phân đoạn nhằm chia ảnh thành các vùng hoặc đối
tượng có thể xử lý được

Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt

4


5


Nếu phân đoạn tốt, các contours của objects sẽ xuất
hiện và có thể trích để sử dụng.
 Có thể xác định hình dáng đối tượng.
 Dựa trên màu sắc, hình dáng, texture, có thể xác
định rõ đối tượng.



Phân đoạn ảnh được sử dụng nhiều trong ‘tìm kiếm
tương tự (similarity searches)
 Phân đoạn ảnh là bài toán khó trong Xử lý ảnh. Vẫn
là một chủ đề trong các hội thảo/hội nghị liên quan
đến thị giác máy tính, xử lý ảnh.


Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt

6









Phân đoạn cho phép trích đối tượng trong ảnh.
Các thuật giải phân đoạn dựa trên các tính chất
cơ bản như màu sắc, giá trị xám, hay texture:
discontinuity và similarity.
Phân chia ảnh dựa trên các thay đổi độ sáng đột
ngột, nhằm phát hiện biên trong ảnh. Tuy
nhiên, không luôn xác định được biên để tạo
vùng.
Phân chia ảnh thành các vùng tương tự theo

tiêu chuẩn xác định (mức xám, texture, color,
motion). Dựa trên sự tương tự giữa các pixel kề
nhau nhằm xây dựng các đối tượng.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt

7





Kiểu phân đoạn phụ thuộc vào ứng dụng
Có nhiều thuật giải phân đoạn
 Phân đoạn dựa trên đường viền vùng (edge detection)
 Phân đoạn dựa trên clustering (hoặc grouping)
 Phân đoạn dựa trên phân hoạch (partition) đồ thị



Các ứng dụng như finding people, summarizing
video, annotation figures, background subtraction,
finding buildings/rivers in trong ảnh vệ tinh.

Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt

8


Edges dựa trên KHÁC NHAU (DIFFERENCES hay
DISCONTINUITY) giữa các pixel kề nhau.

 Regions dựa trên sự TƯƠNG TỰ (SIMILARITIES)
giữa các pixel kề nhau.


Discontinuity

Similarity

Point Detection (dựa trên
sắc xám)
Line Detection (dò đường
thẳng có trong ảnh)
Edge Detection (đạo hàm
bậc 1, 2)
Active Countouring

Thresholding
(phân
ngưỡng)
Region Growing & Merging
Watershed
Clustering

Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt

9





Ảnh R được phân hoạch thành các vùng con R1, R2,
R3, …, Rn sao cho

R

R

a.

Hội các Ri bằng với R

b.

Các Ri không giao nhau Ri  R j  0, i  j

i

i 1,..,n

Q(Ri)=TRUE
d. Q(Ri  Rj) =FALSE, với hai vùng Ri, Rj kề nhau (vì
nếu có thì đã tạo thành một vùng)
Với Q(Rk) là vị từ logic xác định trên pixel thuộc Rk
(ví dụ: tất cả pixel trên ngưỡng T)
c.

Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt

10



Phân đoạn bằng
mắt thường
Old man và các
thứ khác
 Hai người và con
chó


Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt

11






Tạo thành ảnh nhị phân từ ảnh xám đầu vào.
Nhằm tách được foreground và forground.
Thực hiện bằng cách chọn ngưỡng T, và tạo ảnh
ouput theo công thức
1
g ( x, y)  
0



f ( x, y)  T
f ( x, y)  T


Chỉ làm việc tốt với ảnh có bi-model histogram, ít
nhiễu. Có thể dùng nhiều ngưỡng Ti.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt

12


Chọn ngưỡng ban đầu T (vd: chọn mean của mọi
pixels)
2. Phân đoạn thành hai nhóm G1, G2, với mean tương
ứng m1, m2.
3. Tính toán ngưỡng mới theo cách T = ½ (m1+m2)
4. Lặp lại bước 2 và 3 cho đến khi sự thay đổi của T
mới so với T ở lần trước đó nhỏ hơn giá trị cho
trước
1.

Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt

13




Tự động thực hiện phân ngưỡng ảnh dựa trên hình
dáng histogram

/>
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt


14






Cho ảnh 𝑀𝑥𝑁 và L mức sáng q = 0, 1, 2, …, L – 1
Histogram
chuẩn
hóa:
𝑝𝑖 = 𝑛𝑖/𝑀. 𝑁 ,
𝑖 = 0, 1, 2, … , 𝐿 – 1, ni là số pixel cường độ sáng i.
Ngưỡng k chia ảnh thành hai tập:

với

 𝐶0: các pixel mức sáng trong ,0, 1, … , 𝑘 𝐶1: các pixel mức sáng trong ,𝑘 + 1, … , 𝐿 − 1-

𝑃1 𝑘 =

𝑘
𝑖=0 𝑝𝑖

, 𝑃2 𝑘 =

𝐿−1
𝑖=𝑘+1 𝑝𝑖


= 1 − 𝑃1 (𝑘).

là tổng tích lũy các p của 𝐶0 và 𝐶1.
1
𝜇1 𝑘 =
𝑃1 𝑘
𝜇𝐺 =

𝑘

𝑖=0

1
𝑖. 𝑝𝑖 , 𝜇2 𝑘 =
𝑃2 𝑘

𝐿−1

𝑖. 𝑝𝑖
𝑖=𝑘+1

𝐿−1
𝑖=0 𝑖. 𝑝𝑖 , là global mean

Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt

15





Variance của mỗi nhóm
𝑘
𝑖=0

𝜎12 =
𝜎22 =


Variance của toàn bộ ảnh:

𝐿−1
𝑖=𝑘+1

𝜎2

2

𝑖 − 𝜇1 𝑘
𝑃1 𝑘

=

𝑖 − 𝜇2 𝑘
𝑃2 (𝑘)
𝐿−1
𝑖=0

.𝑝 𝑖
2


.𝑝 𝑖

𝑖 − 𝜇𝐺 𝑖

2

.𝑝 𝑖

𝜎 2 = 𝑃1 𝑘 𝜎12 + 𝑃2 𝑘 𝜎22 + 𝑃1 𝑘 𝜇1 𝑘 − 𝜇𝐺 𝑘
+ 𝑃2 𝑘 𝜇2 𝑘 − 𝜇𝐺 𝑘 2

2

Trong đó:𝜎𝑤2 𝑘 = 𝑃1 𝑘 𝜎12 + 𝑃2 𝑘 𝜎22 : within-class variance;
𝜎𝐵2 𝑘 = 𝑃1 𝑘 𝜇1 𝑘 − 𝜇𝐺 𝑘
variance

2

+ 𝑃2 𝑘 𝜇2 𝑘 − 𝜇𝐺 𝑘

Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt

2

:

inter-class


16




Xác định k sao cho:
m𝑖𝑛 𝜎𝑤2 𝑘 , 𝑘 = 0,1, . . , 𝐿 − 1



Tương đương tìm k sao cho max variance giữa hai lớp
𝑚𝑎𝑥 𝜎𝐵2 𝑘 , 𝑘 = 0,1, . . , 𝐿 − 1
𝜎𝐵2 𝑘 = 𝑃1 𝑘 𝜇1 𝑘 − 𝜇𝐺 𝑘 2
+ 𝑃2 𝑘 𝜇2 𝑘 − 𝜇𝐺 𝑘 2
𝜎𝐵2 𝑘 = 𝑃1 𝑘 𝑃2 𝑘 𝜇1 𝑘 − 𝜇2 𝑘
𝜇 𝑘 − 𝜇𝐺 𝑃1 𝑘
=
𝑃1 𝑘 𝑃2 𝑘

2
𝑘

2

,𝜇 𝑘 =

Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt

𝑖. 𝑝𝑖 ,
𝑖=0

17


Phân đoạn 𝑘 ≥ 3 ngưỡng
𝜎𝐵2 𝑘 = 𝑃1 𝑘 𝜇1 𝑘 − 𝜇𝐺 𝑘
+ 𝑃2 𝑘 𝜇2 𝑘 − 𝜇𝐺 𝑘 2
+ 𝑃3 𝑘 𝜇3 𝑘 − 𝜇𝐺 𝑘 2
 Cần xác định


2

𝜎𝐵2 𝑘1∗ , 𝑘2∗ = 𝑚𝑎𝑥 *𝜎𝐵2 𝑘1 , 𝑘2 , 0 < 𝑘1 < 𝑘2 < 𝐿 − 1+


Phức tạp để giải phương trình trên với 𝑘 > 3.

Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt

18


Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt

19


Chia ảnh thành các vùng
 Thực hiện phân ngưỡng thích nghi trên từng vùng



Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt

20


Tham khảo mã nguồn openCV_AdaptiveThresHold

Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt

21


Mean shift là thuật giải lặp nonparametric hoặc còn
gọi là nonparametric density gradient estimation
dựa trên cách tiếp cận kernel tổng quát.
 Mục tiêu: tìm cực đại của hàm mật độ xác suất
(density modes) theo mẫu.
 Thực hiện bằng cách với mỗi điểm dữ liệu, chọn
một window có kích thước cho trước, sau đó xác
định mean point. Dời cửa sổ này đến điểm đó, lại
tiếp tục tính mean point. Lặp liên tục cho đến khi
mean point “không thay đổi" (hội tụ) cho cửa sổ đó.
 Mean-shift được dùng trong
segmentation,
clustering, visual tracking, etc.


Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt


22


1.
2.
3.
4.
5.

Mean Shift Algorithm
Xác định kích thước cửa sổ tìm kiếm (search window).
Xác định vị trí ban đầu của search window cho mỗi điểm
data.
Tính toán vị trí mean (centroid của dữ liệu) trong search
window.
Xác định tâm của search window tại vị trí mean location có
được ở bước 3.
Lặp lại bước 3 và 4 đến khi hội tụ

Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt

23




Đặt {xi}i=1..n ,là ảnh, {zi}i=1..n là các điểm hội tụ, và
{Li}i=1..n là các nhãn

Mean-shift segmentation

 Lặp i = 1…n, tìm mean shift cho xi và lưu điểm hội tụ
vào zi.
 Tìm m clusters {Cp}p=1…m các điểm hội tụ bằng cách
gom các điểm khoảng cách gần nhau vào một nhóm
(khoảng cách nhỏ hơn ngưỡng cho trước – ví dụ 0.5)
 Lặp i= 1…n , gán Li= {p | zi ϵCp}.


Rõ ràng cần xác định cách di chuyển của search
window
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt

24


Nguồn: Dorin Comaniciu and Peter Meer, Distribution Free Decomposition of Multivariate Data,
Pattern Analysis & Applications (1999)2:22–30

Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt

25