Chọn không gian màu (trong phân đoạn ảnh màu).
Cách chọn vector biểu diễn điểm ảnh
Ảnh xám: (grey_level, x, y).
Ảnh màu: (la, lb, lc, x, y). Với la, lb, lc là giá trị màu trong
không gian màu. Không gian CIE Lab thích hợp để phân
đoạn với thuật giải K-Mean
Cách tính khoảng cách giữa 2 điểm dữ liệu trong
biểu thức so sánh
53 trang |
Chia sẻ: nguyenlam99 | Lượt xem: 1117 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Bài giảng Xử lý ảnh số - Phân đoạn ảnh, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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
2 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt
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ự
3 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt
Phân đoạn nhằm chia ảnh thành các vùng hoặc đối
tượng có thể xử lý được
4 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt
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.
6 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt
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.
7 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt
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.
8 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt
Discontinuity Similarity
Point Detection (dựa trên
sắc xám)
Thresholding (phân
ngưỡng)
Line Detection (dò đường
thẳng có trong ảnh)
Region Growing & Merging
Edge Detection (đạo hàm
bậc 1, 2)
Watershed
Active Countouring Clustering
9 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt
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.
Ả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
ni
i RR
,..,1
jiRR ji ,0
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
Tyxf
Tyxf
yxg
),(0
),(1
),(
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
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: 𝑝𝑖 = 𝑛𝑖/𝑀.𝑁 , với
𝑖 = 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 𝑘 = 𝑝𝑖
𝑘
𝑖=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
𝜇2 𝑘 =
1
𝑃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
𝜎1
2 =
𝑖 − 𝜇1 𝑘
2
. 𝑝 𝑖𝑘𝑖=0
𝑃1 𝑘
𝜎2
2 =
𝑖 − 𝜇2 𝑘
2
. 𝑝 𝑖𝐿−1𝑖=𝑘+1
𝑃2(𝑘)
Variance của toàn bộ ảnh: 𝜎2 = 𝑖 − 𝜇𝐺 𝑖
2
. 𝑝 𝑖𝐿−1𝑖=0
𝜎2 = 𝑃1 𝑘 𝜎1
2 + 𝑃2 𝑘 𝜎2
2 + 𝑃1 𝑘 𝜇1 𝑘 − 𝜇𝐺 𝑘
2
+ 𝑃2 𝑘 𝜇2 𝑘 − 𝜇𝐺 𝑘
2
Trong đó:𝜎𝑤
2 𝑘 = 𝑃1 𝑘 𝜎1
2 + 𝑃2 𝑘 𝜎2
2: within-class variance;
𝜎𝐵
2 𝑘 = 𝑃1 𝑘 𝜇1 𝑘 − 𝜇𝐺 𝑘
2 + 𝑃2 𝑘 𝜇2 𝑘 − 𝜇𝐺 𝑘
2 : inter-class
variance
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 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 𝑘
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
∗ = 𝑚𝑎𝑥 *𝜎𝐵
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
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ụ
23 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt
Đặ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 = 1n, tìm mean shift cho xi và lưu điểm hội tụ
vào zi.
Tìm m clusters {Cp}p=1m 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= 1n , 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
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 25
Nguồn: Dorin Comaniciu and Peter Meer, Distribution Free Decomposition of Multivariate Data,
Pattern Analysis & Applications (1999)2:22–30
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
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 27
Tìm Mean shift mode
Cho n điểm {xi}i=1,..,n thuộc R
d, 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
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
n
k
i
d h
xx
K
nh
xf
1
1
)(
2,)( xkcxK dk
10
11
)(
x
x
xf
ck,d là hằng chuẩn hóa
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
n
i
i
d h
xx
K
nh
xf
1
1
)(
n
i
i
id
dk
h
xx
gxx
nh
C
xf
1
2
2
,2
)(
x
h
xx
g
h
xx
gx
h
xx
g
nh
C
xf
n
i
i
n
i
i
i
n
i
i
d
dk
1
2
1
2
1
2
2
,2
)(
)(')( sksg
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(x
t).
Translate window: xt+1 = xt+mh(x
t).
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 30
x
h
xx
g
x
h
xx
g
xm
n
i
i
n
i i
i
h
1
2
1
2
)(
Flat kernel
Gaussian kernel:
Epanechikov kernel
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 31
10
11
)(
x
x
xf
2exp)( xxK
10
1)1(4/3
)(
2
x
xx
xE
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 32
Search
window
Center of
mass
Mean Shift
vector
Nguồn: Y. Ukrainitz & B. Sarel
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 33
Search
window
Center of
mass
Mean Shift
vector
Nguồn: Y. Ukrainitz & B. Sarel
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 34
Search
window
Center of
mass
Mean Shift
vector
Nguồn: Y. Ukrainitz & B. Sarel
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 35
Search
window
Center of
mass
Mean Shift
vector
Nguồn: Y. Ukrainitz & B. Sarel
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 36
Search
window
Center of
mass
Mean Shift
vector
Nguồn: Y. Ukrainitz & B. Sarel
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 37
Search
window
Center of
mass
Mean Shift
vector
Nguồn: Y. Ukrainitz & B. Sarel
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 38
Search
window
Center of
mass
Nguồn: Y. Ukrainitz & B. Sarel
Tham khảo openCV_MeanShiftSegmentation
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 39
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 40
input image
intensity
p
ix
e
l
c
o
u
n
t
• Now how to determine the three main intensities that
define our groups?
• We need to cluster.
With this objective, it is a “chicken and egg” problem:
If we knew the cluster centers, we could allocate points to
groups by assigning each to its closest center.
If we knew the group memberships, we could get the
centers by computing the mean per group.
42
Phân hoạch tập các ‘pattern’ thành những clusters
Xác định subsets các điểm ‘gần nhau’
Các tiêu chuẩn “gần nhau” : Dựa trên giá trị cường
độ; Các độ đo Texture, etc.
Input – tập các giá trị x1, x2, , xn (các điểm ảnh).
Output – tập các clusters và tâm của chúng. K-mean
Clustering phân hoạch n input thành K tập (K ≤ n)
S = {S1, S2, , Sk} sao cho cực tiểu within-cluster
sum of squares (WCSS)
43 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt
k
i Sx
ij
S
ij
x
1
2
minarg
1. Khởi động ngẫu nhiên các tâm cluster c1, ..., cK
2. Với mỗi tâm cluster, xác định các điểm thuộc
cluster
• Với mỗi điểm p, tìm gần nhất ci. Gán p vào
cluster i
3. Với các điểm thuộc cluster, tìm tâm ci
• Chọn ci là mean của points trong cluster i
4. Nếu ci thay đổi, lặp lại bước 2
Tính chất
• Luôn hội tụ some solution
• Có thể bị “local minimum”: ie, không luôn tìm được global minimum
của hàm mục tiêu
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 44
Chọn K mean (hay là tâm) ngẫu nhiên từ dữ
liệu: m1
(1),,mk
(1)
Bước gán: xác định điểm xp thuộc cluster nào theo
công thức
Cập nhận mean của các cluster theo
Câu hỏi: chọn ngẫu nhiên như thế nào?
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 45
kjmxmxxS tjptippti 1: )()()(
)(
)(
)1( 1
t
ij Sx
jt
i
t
i x
S
m
Chọn không gian màu (trong phân đoạn ảnh màu).
Cách chọn vector biểu diễn điểm ảnh
Ảnh xám: (grey_level, x, y).
Ảnh màu: (la, lb, lc, x, y). Với la, lb, lc là giá trị màu trong
không gian màu. Không gian CIE Lab thích hợp để phân
đoạn với thuật giải K-Mean
Cách tính khoảng cách giữa 2 điểm dữ liệu trong
biểu thức so sánh
Sử dụng khoảng cách Euclidean.
Cách chọn K tâm khởi động ứng với K cluster
Cách xách định giá trị K tự động ?
Phân đoạn ảnh texture như thế nào?
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 46
Việc gán cluster label cho từng pixel có thể phát
sinh
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 47
1 2
3
?
Original (nhiều
điểm trắng xen kẽ)
Gán nhãn theo cluster
center’s intensity
Cần bảo đảm phân đoạn
trơn. Cách nào?
Xem xét sự phụ thuộc giữa các pixel, xác định bởi
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 48
P(foreground | image)
edgesji
ji
Ni
i datayyfdatayf
Z
dataP
,
2
..1
1 ),;,(),;(
1
),;( y
Labels to be predicted Individual predictions Pairwise predictions
Normalizing constant
Likelihood as an “Energy”
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 49
edgesji
ji
Ni
i datayypdatayp
Z
dataP
,
2
..1
1 ),;,(),;(
1
),;( y
edgesji
ji
i
i datayydataydataEnergy
,
21 ),;,(),;(),;( y
“Cost” of assignment yi
“Cost” of pairwise assignment yi ,yj
Markov Random Fields
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 50
edgesji
ji
i
i datayydataydataEnergy
,
21 ),;,(),;(),;( y
Node yi: pixel label
Edge: constrained
pairs
Cost to assign a label to
each pixel
Cost to assign a pair of labels to
connected pixels
Example: “label smoothing” grid
Unary potential
0 1
0 0 K
1 K 0
Pairwise Potential
0: -logP(yi = 0 ; data)
1: -logP(yi = 1 ; data)
edgesji
ji
i
i datayydataydataEnergy
,
21 ),;,(),;(),;( y
51
edgesji
ji
i
i datayydataydataEnergy
,
21 ),;,(),;(),;( y
Source (Label 0)
Sink (Label 1)
Cost to assign to 1
Cost to assign to 0
Cost to split nodes
52
edgesji
ji
i
i datayydataydataEnergy
,
21 ),;,(),;(),;( y
Source (Label 0)
Sink (Label 1)
Cost to assign to 0
Cost to assign to 1
Cost to split nodes
53
Watershed
Region Growing
Dựa trên phân hoạch đồ thị (Shi & Malik , 97)
Active Contour (Snake) – Cass, Witkin, Terzopoulos
1997
54 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt
Các file đính kèm theo tài liệu này:
- xla_baigiang_09_4663.pdf