Đa giác A được gọi là đa giác lồi (convex) nếu
một đường thẳng nối 2 điểm bất kì thuộc A
phải nằm trong A
Bao lồi (convex hull) H của một tập bất kì S là
một đa giác lồi nhỏ nhất chứa tất cả các điểm
thuộc S
Tập được tạo thành bởi H-S được gọi là tập
thiếu của S
71 trang |
Chia sẻ: nguyenlam99 | Lượt xem: 1872 | 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ố - Xử lý ảnh dựa trên morphological, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
XỬ LÝ ẢNH DỰA TRÊN
MORPHOLOGICAL
NGÔ QUỐC VIỆT
TPHCM-2014
1. Giới thiệu Binary Morphology
2. Một số khái niệm về tập hợp
3. Các phép toán cơ bản
Phát triển và bào mòn (Dilation and erosion)
Mở và đóng (Opening and closing)
Biến đổi trúng hay trật (Hit-or-miss transformation)
4. Ứng dụng morphology vào các bài toán xử lý ảnh
Dò biên
Trích các thành phần liên thông (Extraction of Connected
Components)
Tìm bao lồi (Convex Hull)
Tô vùng (Region Filling)
Làm mảnh (Thinning)
Làm dầy (Thickening)
Lọc xương/Lấy cạnh trung tâm (Skeleton)
2 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt
Trang bị kiến thức về cách tiếp cận cấu trúc (tập
hợp) vào giải quyết các bài toán xử lý ảnh đã được
giải quyết bằng các biến đổi giải tích trước đó, và
một số xử lý khác.
Trang bị các kỹ năng sử dụng OpenCV để thực hiện
các xử lý dựa trên morphology
3 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt
Phương pháp phi tuyến
Dựa trên lý thuyết tập hợp Minkowski
Là một phần của lý thuyết finite lattices
Dùng để phân tích ảnh dựa trên hình dáng
Phương pháp hiệu quả, nhưng chưa được sử
dụng nhiều.
Morphology nhị phân là morphology trên ảnh
đen trắng cho những bài toán xử lý ảnh cơ
bản
4 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt
5
Cải tiến ảnh (image
enhancement)
Phân đoạn ảnh (image
segmentation)
Phục hồi ảnh (image
restoration)
Dò cạnh
Phân tích Texture (texture
analysis)
Phân tích particle
Phát sinh đặc trưng
(feature generation)
Trích xương
(Skeletonization)
Phân tích hình dáng
(shape analysis)
Nén ảnh (Image
compression)
Phân tích thành phần
(Component analysis)
Curve filling
Làm mỏng tổng quát
(General thinning)
Tìm đặc trưng (Feature
detection)
Giảm nhiễu (Noise
reduction)
Lọc không-thời gian
(Space-time filtering)
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt
6
Ảnh là một ánh xạ I từ tập SP các tọa độ pixel đến tập G các giá
trị sao cho mỗi vector tọa độ p = (r,c) trong SP, có một vector
I(p) thuộc G. SP được gọi là image plane.
Ảnh nhị phân có hai giá trị. Nghĩa là, G = {vfg , vbg}, với vfg là giá
trị foreground và vbg là giá trị background.
Thông thường, foreground vfg = 0, và background vbg = –.
Một số khả năng kháclà {vfg , vbg} = {0,}, {0,1}, {1,0}, {0,255}, và
{255,0}.
Bài giảng sử dụng {vfg , vbg} = {255, 0} mà không làm mất tính
tổng quát.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt
7
Foreground của ảnh nhị phân
Tập các vị trí p, với I(p) = vfg. Tương tự background là
P fgFG I I , , I( ) ,r c S v p p p
P bgBG I I , , I( ) .r c S v p p p
Chú ý
IIBGIFG IBGIFGvà
và
CIFGIBG và .IBGIFG C
Background là bù của foreground và ngược lại.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt
8
A ={(3,1), (4,1),(3,2),(4,2),(3,3)}.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 9
Structuring element là ảnh nhỏ – được dùng
làm cửa sổ dịch chuyển – giá của SE thể hiện
các pixel lân cận
SE có thể có hình dáng và kích thước bất kỳ,
hoặc liên thông (nhiều hơn 1 piece, có lỗ). Dấu
tròn trên hình thể hiện gốc của SE. Gốc này có
thể đặt bất kỳ đâu trong SE.
E
xa
m
p
le
S
E
s FG
is g
ray ;
B
G
is w
h
ite
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 10
Cho ảnh I và Z là SE.
Z+p nghĩa là Z được dịch
chuyển sao cho gốc
trùng với vị trí p trong
SP.
Z+p là translate của Z
đến p trong SP.
Tập các vị trí trong ảnh
ký hiệu bởi Z+p được
gọi là Z-neighborhood
của p trong I. Ký hiệu là
N{I,Z}(p).
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 11
Cho Z là SE và S lưới vuông các vị trí pixlel chứa
tập {(r,c), (-r,-c) | (r,c)supp(Z)}. Thì
Là phản chiếu của structuring element.
quay 180º quanh gốc của nó.
)(sup),(),,(),( ZpbabaZbaZ
ZlàZ
Phép toán Dilation đối tượng A theo đối tượng Z (thường là
SE) được định nghĩa bởi
Đối tượng A tịnh tiến theo từng vectơ (vị trí) trong Z.
Kết quả sau khi tịnh tiến tạo ra các đối tượng A1,A2,. An
(n là số phần tử trong Z). D(A,Z) là hợp các Ai.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 12
BzAazaZAZAD ,|),(
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 13
Một số định nghĩa khác về dilation.
. I)(I P pp ZSZ
Tập tất cả vị trí pixel p, trong
ảnh mà phần giao của Ž+p với I
khác rỗng.
.)(I
Isupp
p
pZZ Hội những copies của SE, mỗi bản copy
là dịch chuyển đến vị trí pixel foreground
trong ảnh.
.)I(I
supp
Z
Z
p
p Hội những copies của ảnh, mỗi bản là dịch
chuyển đến vị trí pixel foreground của SE.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 14
A1 = A tịnh tiến bởi
vector (0,0) của Z
A2 = A tịnh tiến bởi
vector (0,1) của Z
A = {(2,1),(3,1),(4,1),(3,2)} Z = {(0,0),(0,1)}
A2 = {(2,2),(3,2),(4,2),(3,3)}
D(A,B) = A1 U A2 = {(2,1),(3,1),(4,1),(3,2), (2,2),(4,2),(3,3)}
A1 = {(2,1),(3,1),(4,1),(3,2)}
AZ
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 15
Sử dụng SE 3x3 – Z8 có dạng cho phép mở rộng đều về cả 8
hướng.
Kết quả dilate trên ảnh mẫu như sau
111
111
111
SE được áp lên mọi pixel của ảnh. Tâm của SE được kết hợp với
từng pixel, toàn bộ SE được áp cho pixel đang xét theo cách
thay thế pixel đó bằng SE.
Khái niệp “áp” là hoạt động “công logic nhị phân giữa các giá
trị 0, 1”.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 16
Ảnh nguồn
SE
Đã giãn
Tham khảo mã nguồn openCV_Dilate
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 17
Phép toán Erosion đối tượng A theo đối tượng Z được định
nghĩa bởi:
Với vector a bất ky ̀ , khi tịnh tiến a theo từng vectơ trong Z.
Kết quả sau khi tịnh tiến a là các vectơ mới: a1,a2,..an (n là số
lượng phần tử trong Z).
Nếu tất cả các vector a1,a2,..an đều thuộc A a sẽ thuộc tập
E(A,Z).
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 18
},|{),( ZzAzxxZAE
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 19
Một số định nghĩa khác
.I I
Zsupp
p
pZ Phần giao của các copies của mỗi bản
sao - là dịch chuyển đến vị trí pixel
thuộc goreground của refl. SE.
Tập tất cả các pixel p,
trong ảnh sao cho Z+p
chứa trong I.
Ipp I p ZSZ
Phần giao của các copies của reflected.
SE, mỗi cái dịch chuyển đến vị trí pixel
thuộc foreground của ảnh.
. I
Isupp
p
pZZ
20
A = {(1,1),(2,1),(3,1),(4,1),(1,2),(3,2),(1,3),(2,3)} Z= {(1,0),(0,1)}
Lấy Vector (1,1) tịnh tiến theo các vector trong Z
a1 = (1,1) + (1,0) = (2,1) thuộc A
a2 = (1,1) + (0,1) = (1,2) thuộc A
(1,1) thuộc E(A,B).
Lấy Vecto (3,1) tịnh tiến theo các vector trong Z
a1 = (3,1) + (1,0) = (4,1) thuộc A
a2 = (3,1) + (0,1) = (3,2) thuộc A
(3,1) thuộc E(A,Z).
Lấy Vecto (2,2) tịnh tiến theo các vector trong Z
a1 = (2,2) + (1,0) = (3,2) thuộc A
a2 = (2,2) + (0,1) = (2,3) thuộc A
(2,2) thuộc E(A,Z).
Các vectơ khác khi tịnh tiến sẽ có vectơ không thuộc
A. Không thuộc E(A,Z)
E(A,Z) = {(1,1),(3,1),(2,2)}
Xét pixel của ảnh, nếu mọi phần tử của SE trùng với phần ảnh
tương ứng, thì logical disjunction (OR operation) được thực
hiện giữa tâm của SE với pixel tương ứng để tạo ra pixel trong
ảnh output .
Các đối tượng nhỏ hơn SE sẽ bị xóa, các đối tượng nối với nhau
bởi đường mảnh sẽ tách rời và kích cỡ đối tượng sẽ giảm
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 21
Ảnh nguồn
SE
Eroded
Tham khảo mã nguồn openCV_Erode
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 22
Dilate: nhằm tăng kích thước, bịt các lỗ hổng
Có tính giao hoán
Có tính kết hợp
Erode : co kích thước, mở rộng khoảng hở
Không có tính giao hoán
Không có tính kết hợp
Dilate và erode có tính đối ngẫu
Có thể cài đặt erode từ dilate và ngược lại
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 23
)()( CBACBA
),(),( ABDABBABAA
cc ZZ II
.I I cc ZZ
và
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 24
Hai phép toán phát triển và bào mòn thường được
sử dụng cùng nhau. Từ nhu cầu đó, người ta kết hợp
2 phép toán này để tạo nên một số phép toán có
mức độ quan trọng cao hơn: phép mở và phép đóng.
Phép mở của tập A bởi phần tử cấu trúc B được định
nghĩa như sau:
Phép đóng của tập A bởi phần tử cấu trúc B :
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 25
Opening
Closing
Phép mở
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 26
Phép đóng
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 27
Kết quả của phép mở và phép đóng :
Ứng dụng
Phép mở có thể sử dụng để loại bỏ các cầu nối, các
cành hoặc phần nhô ra của ảnh.
Phép đóng có thể sử dụng để lấp đầy các lỗ hổng,
các khe hở nhỏ.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 28
Kết quả Phép mở Kết quả Phép đóng
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 29
“L” shaped SE
O marks origin
Foreground: white pixels
Background: black pixels
Cross-hatched
pixels are
indeterminate.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 30
Một số tính chất của phép mở:
Tính phản mở rộng :
Tính đơn điệu tăng :
Tính dừng :
Một số tính chất của phép đóng :
Tính mở rộng :
Tính đơn điệu tăng :
Tính dừng :
Tham khảo mã nguồn openCV_OpenClose
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 31
Hit-and-miss được dùng để xác định patterns của
foreground và background pixels trong ảnh
Xét tập A và một tập hợp B gồm 2 phần tử (B1,B2)
với B1 ∩ B2 = Ø, định nghĩa phép biến đổi trúng-trật
với công thức như sau (công thức 1) :
Một định nghĩa khác về phép biến đổi trúng-trật
được xác định bởi (công thức 2):
Đụng B1 nhưng không đụng B2.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 32
Xét một ví dụ ứng dụng của phép biến đổi trúng-
trật: Xác định vị trí các điểm góc trên bên phải của
tập A
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 33
Theo công thức 1, kết quả biến đổi là
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 34
Theo công thức 2, kết quả là
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 35
Top hat được xác định
𝑇ℎ𝑎𝑡 𝐴 = 𝐴 − 𝐴 ∘ 𝐵 với B là SE
Bottom-hat được xác định bởi
𝐵ℎ𝑎𝑡 𝐴 = 𝐴 ∙ 𝐵 − 𝐴 với B là SE
Sinh viên làm thực nghiệm với ảnh sau và cho nhận
xét (đọc tài liệu Gonzalez từ 695-700)
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 36
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 37
original
binary image
erosion by square
8-connected SE
difference
4-conn inside bdry
Hình ảnh minh họa trích từ nguồn Vanderbilt University
Gọi biên của đối tượng A là ∂A, lúc đó công thức để
tính ∂A như sau:
∂A = A – (A Θ B)
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 38
B
A
A Θ B ∂A
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 39
original
Ảnh nhị phân
erosion by plus
4-connected SE
Ảnh hiệu - Difference
8-conn inside bdry.
Hình ảnh minh họa trích từ nguồn Vanderbilt University
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 40
original
binary image
dilation by plus
4-connected SE
difference
8-conn outside bdry.
Hình ảnh minh họa trích từ nguồn Vanderbilt University
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 41
original
binary image
dilation by square
8-connected SE
difference
4-conn outside bdry
Hình ảnh minh họa trích từ nguồn Vanderbilt University
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 42
original
binary image
in erosion by plus
erosion by square is
in 4-conn inside bdry
8-conn inside bdry is
Hình ảnh minh họa trích từ nguồn Vanderbilt University
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 43
original
binary image
in dilation by square
dilation by plus is
in 4-conn outside bdry
8-conn outside bdry is
Hình ảnh minh họa trích từ nguồn Vanderbilt University
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 44
8-bdry/4-bdry/orig
inside boundaries
all 4 boundaries
are disjoint from
orig/8-bdry/4-bdry
outside boundaries
Hình ảnh minh họa trích từ nguồn Vanderbilt University
Đa giác A được gọi là đa giác lồi (convex) nếu
một đường thẳng nối 2 điểm bất kì thuộc A
phải nằm trong A
Bao lồi (convex hull) H của một tập bất kì S là
một đa giác lồi nhỏ nhất chứa tất cả các điểm
thuộc S
Tập được tạo thành bởi H-S được gọi là tập
thiếu của S
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 45
Cho Bi, i=1,2,3,4 biểu diễn 4 thành phần cấu trúc
Quy trình bao gồm việc thực hiện các phương trình
Đặt , khi bước thực hiện phương trình
trên đạt được
Bao lồi của A là
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 46
,...3,2,1;4,3,2,1,)( 1 kiABXX
i
k
i
k
AX i 0
i
conv
i XD
4
1
)(
i
iDAC
i
k
i
k XX 1
Đặt
Thực hiện với B1
Thực hiện biến đổi Hit or Miss tập A với B1 cho đến
khi không biến đổi được nữa, ta được tập đích Xn.
Hợp Xn với A, gọi là D
1
Thực hiện tương tự với B2, B3, và B4; thu được D2,
D3 và D4
Hợp của D1, D2, D3, D4 là bao lồi tìm theo thuật toán
này
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 47
AXXXX 40
3
0
2
0
1
0
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 48
x
x
x
x
x
x x
x x x
x
x
x
x
x
x x
x x x
B1 B2 B3 B4 x
Don’t care
Background
Foreground
A
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 49
x
x
x
x
x
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 50
x
x
x
x
x
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 51
x
x
x
x
x
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 52
x
x
x
x
x
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 53
4
1
)(
i
iDAC
D1
D2
D3
D4
Tham khảo mã nguồn openCV_ConvexHull
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 54
Làm mỏng một tập A theo một phần tử cấu trúc B
được xác định:
Có thể dùng nhiều SE để làm mảnh A
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 55
Hit-or-miss transformation
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 56
Quá trình làm dày A theo phần tử cấu trúc B được
xác định
Quá trình làm dày cũng được xác định qua một
chuỗi phần tử cấu trúc.
SE của thickening tương tự như SE của thinning
nhưng hoán vị vai trò của zero và 1
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 57
Hit-or-miss transformation
Tham khảo mã nguồn openCV_ConvexHull
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 58
Đặt Skel(I,r) là tập các pixel trong I sao cho nếu
p Skel(I,r) thì Dp(r), là maximal disk bán kính r
trong I. Nghĩa là, Skel(I,r) là quỹ đạo của các tâm
của maximal disks bán kính r trong I. Thì
Xương của I là hội của tập tất cả tâm của maximal
disk.
Maximal disk Dp(r) tiếp xúc với biên của I ít nhất tại
hai điểm.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 59
),I(Skel
0
rS
r
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 60
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 61
Ảnh gốc skeleton thô (đỏ)
Là tập những tâm
của maximal disks.
Tỉa nhánh và connected
skeleton
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 62
maximal disks (red)
non max disks (blue)
non max & max disks
over skeleton
non maximal “disks”
“disks” are squares
Maximal disk tại pixel p là đĩa lớn nhất fg có chứa p.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 63
maximal disks (red)
non max disks (blue)
non max & max disks
over skeleton
non maximal “disks”
“disks” là các square
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 64
o
ri
g
in
al
er
o
d
e
n
=
0
er
o
d
e
n
=
1
er
o
d
e
n
=
2
er
o
d
e
n
=
3
o
p
en
a
b
o
ve
w
/ Z
(
n
=
1)
o
p
en
a
b
o
ve
w
/ Z
(
n
=
1)
o
p
en
a
b
o
ve
w
/ Z
(
n
=
1)
o
p
en
a
b
o
ve
w
/ Z
(
n
=
1)
to
p
-
m
id
d
le
to
p
-
m
id
d
le
to
p
-
m
id
d
le
to
p
-
m
id
d
le
u
n
io
n
o
f
al
l 4
t
o
t
h
e
ri
g
h
t
sk
el
et
o
n
• SE = Z8 = = Sq(3)
• n = 0: SE = 1 pixel
• n = 1: SE = Sq(3)
• n = 2: SE = Sq(5)
• n = 3: SE = Sq(7)
Note that the
result is
disconnected
and has
spurious points. S
ke
l(
I,
0
)
S
ke
l(
I,
1
)
S
ke
l(
I,
2
)
S
ke
l(
I,
3
)
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 65
Xem các pixel giả là
Thành phần liên thông
Ít hơn 3 pix.
Tỉa nhánh
Tốt hơn
Skeleton thô
Có các pixel “giả”
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 66
2 other components
of pruned skel dilated.
Giao của
Các thành phần dilated.
2 components
pruned skel. dilated.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 67
Skeleton thô Skeleton tỉa nhánh reconnected skeleton
Một trong những cách biểu diển Skeleton của một
tập hợp là biểu diển qua openning và erosion.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 68
Quá trình rút xương có thể được biểu diển qua các
các thao tác xói mòn (erosion) và mở (opening).
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 69
Tham khảo mã nguồn openCV_Skeleton
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 70
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 71
Các file đính kèm theo tài liệu này:
- xla_baigiang_07_0031.pdf