Bài giảng Xử lý ảnh số: Chương 9

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

1. Giới thiệu bài toán phân đoạn 2. Phân đoạn ảnh dựa trên các phương pháp phân

ngưỡng sắc xám



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. 3. 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

 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.

(phân

Discontinuity Point Detection (dựa trên sắc xám)

Similarity Thresholding ngưỡng)

Region Growing & Merging

Line Detection (dò đường thẳng có trong ảnh)

Watershed

Edge Detection (đạo hàm bậc 1, 2)

Active Countouring

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

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

b. Các Ri không giao nhau

c. 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)

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

 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

1. 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

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

http://en.wikipedia.org/wiki/Otsu's_method

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

chuẩn

hóa:

với

 Cho ảnh 𝑀𝑥𝑁 và L mức sáng q = 0, 1, 2, …, L – 1 𝑝𝑖 = 𝑛𝑖/𝑀. 𝑁 ,  Histogram 𝑖 = 0, 1, 2, … , 𝐿 – 1, ni là số pixel cường độ sáng i.

 Ngưỡng k chia ảnh thành hai tập:

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

𝑃1 𝑘 = 𝑝𝑖

, 𝑃2 𝑘 =

𝑝𝑖 = 1 − 𝑃1(𝑘)

𝐿−1 𝑖=𝑘+1

𝑘 𝑖=0

𝜇2 𝑘 =

𝜇1 𝑘 =

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

1 𝑃1 𝑘

𝑘 𝑖. 𝑝𝑖, 𝑖=0

𝐿−1 𝑖. 𝑝𝑖 𝑖=𝑘+1

𝜇𝐺 =

𝑖. 𝑝𝑖, là global mean

𝐿−1 𝑖=0

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

 Variance của mỗi nhóm

. 𝑝 𝑖

𝑘 𝑖=0

2 =

𝜎1

𝑖 − 𝜇1 𝑘 𝑃1 𝑘

. 𝑝 𝑖

𝐿−1 𝑖=𝑘+1

2 =

𝜎2

𝑖 − 𝜇2 𝑘 𝑃2(𝑘)

. 𝑝 𝑖

𝑖 − 𝜇𝐺 𝑖

𝐿−1 𝑖=0

2 + 𝑃1 𝑘 𝜇1 𝑘 − 𝜇𝐺 𝑘 2

 Variance của toàn bộ ảnh: 𝜎2 = 2 + 𝑃2 𝑘 𝜎2 𝜎2 = 𝑃1 𝑘 𝜎1

2 𝑘 = 𝑃1 𝑘 𝜎1

inter-class

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

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

2 𝑘 , 𝑘 = 0,1, . . , 𝐿 − 1

 Xác định k sao cho: m𝑖𝑛 𝜎𝑤

 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 𝑘 2 𝜎𝐵

𝑘

, 𝜇 𝑘 = 𝑖. 𝑝𝑖,

𝜇 𝑘 − 𝜇𝐺𝑃1 𝑘 2 𝑃1 𝑘 𝑃2 𝑘

𝑖=0

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

 Phân đoạn 𝑘 ≥ 3 ngưỡng

2 𝑘 = 𝑃1 𝑘 𝜇1 𝑘 − 𝜇𝐺 𝑘 2 𝜎𝐵 + 𝑃2 𝑘 𝜇2 𝑘 − 𝜇𝐺 𝑘 2 + 𝑃3 𝑘 𝜇3 𝑘 − 𝜇𝐺 𝑘 2

 Cần xác định

2 𝑘1, 𝑘2 , 0 < 𝑘1 < 𝑘2 < 𝐿 − 1+

∗, 𝑘2

∗ = 𝑚𝑎𝑥 *𝜎𝐵

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ổ đó. segmentation,

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

 Mean-shift được dùng trong clustering, visual tracking, etc.

Mean Shift Algorithm

1. Xác định kích thước cửa sổ tìm kiếm (search window). 2. Xác định vị trí ban đầu của search window cho mỗi điểm

data.

3. Tính toán vị trí mean (centroid của dữ liệu) trong search

window.

4. Xác định tâm của search window tại vị trí mean location có

được ở bước 3.

5. 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

 Mục tiêu của mean shift algorithm là tìm cực trị cục bộ của density theo phân phối xác định. Nghĩa là, xác định cách di chuyển search window trong mỗi bước lặp

 Xác định thông qua mean shift vector để di chuyển

search window.

 Sử dụng khái niệm kernel density estimation để xác

định mean shift vector

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

 Kernel density estimation là phương pháp non parametric để ước lượng density function của biến ngẫu nhiên. Được dùng để ước lượng probability density

Tìm Mean shift mode

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

 Cho n điểm {xi}i=1,..,n thuộc Rd, cửa sổ bán kính h.  Đặt kernel density với kernel K(x) là:

 Kernel K(x) có thể xác định bởi

ck,d là hằng chuẩn hóa

 Hàm k được gọi là profile của K. Có nhiều dạng hàm

k. Đơn giản nhất là flat kernel.

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

 Estimate của density gradient được xác định bởi

gradient của kernel density estimate.

 Modes của density function định vị tại các zeros của

gradient function. Nghĩa là f(x) = 0.

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

 Thành phần

 Được gọi là mean shift vector. Chính là vector di

chuyển của search window sau mỗi bước lặp.

Thủ tục di chuyển search window như sau

 Tính toán ở bước t, mh(xt).  Translate window: xt+1 = xt+mh(xt).

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

 Flat kernel

 Gaussian kernel:

 Epanechikov kernel

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

Search window

Center of mass

Mean Shift vector