Chương 4: Các Phương Pháp Phát Hiện Biên

84
Chương 4

CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN
4.1 Giới thiệu biên ảnh và kỹ thuật phát hiện biên
4.1.1 Một số khái niệm
 ðiểm biên: Một ñiểm ảnh ñược coi là ñiểm biên nếu có sự thay ñổi nhanh hoặc
ñột ngột về mức xám (hay màu).
Ví dụ: trong ảnh nhị phân, ñiểm ñen gọi là ñiểm biên nếu lân cận nó có ít
nhất một ñiểm trắng.
 ðường biên (ñường bao: boundary): tập hợp các ñiểm biên liên tiếp tạo thành
một ñường biên hay ñường bao.
Nhìn chung về mặt toán học người ta coi ñiểm biên của ảnh là ñiểm có sự
biến ñổi ñột ngột về ñộ xám như chỉ ra trong hình 4.1 dưới ñây:

Hình 4.1 Các ñồ thị biểu diễn biên
 Ý nghĩa của ñường biên trong xử lý: ý nghĩa ñầu tiên, ñường biên là một loại
ñặc trưng cục bộ tiêu biểu trong phân tích, nhận dạng ảnh. Thứ hai, người ta sử
dụng biên làm phân cách các vùng xám (màu) cách biệt. Ngược lại, người ta
cũng sử dụng các vùng ảnh ñể tìm ñường phân cách.

Chương 4: Các Phương Pháp Phát Hiện Biên

86
Nói tóm lại: Phương pháp phát hiện biên trực tiếp nhằm làm nổi ñường biên
dựa vào biến thiên về giá trị ñộ sáng của ñiểm ảnh. Kỹ thuật chủ yếu là dùng kỹ
thuật ñạo hàm. Nếu lấy ñạo hàm bậc nhất của ảnh ta có phương pháp Gradient,
nếu lấy ñạo hàm bậc 2 ta có kỹ thuật Laplace.
b. Phương pháp phát hiện biên gián tiếp
Nếu bằng cách nào ñó ta phân ñược
ảnh thành các vùng thì ranh giới
giữa các vùng ñó gọi là biên. Kỹ thuật dò biên và phân vùng ảnh là hai bài toán
ñối ngẫu nhau vì dò biên ñể thực hiện phân lớp ñối tượng mà khi ñã phân lớp
xong nghĩa là ñã phân vùng ñược ảnh và ngược lại, khi ñã phân vùng ảnh ñã ñược
phân lớp thành các ñối tượng, do ñó có thể phát hiện ñược biên.
Phương pháp phát hiện biên trực tiếp tỏ ra khá hiệu quả và ít chịu ảnh
hưởng của nhiễu, song nếu sự biến thiên ñộ sáng không ñột ngột, phương pháp
tỏ ra kém hiệu quả, phương pháp phát hiện biên gián tiếp tuy khó cài ñặt, song
lại áp dụng khá tốt trong trường hợp này.
4.1.3 Quy trình phát hiện biên
o
Bước 1: Lọc nhiễu theo các phương pháp ñã tìm hiểu ở các chương trước.
o
Bước 2: Làm nổi biên sử dụng các toán tử phát hiện biên.
o
Bước 3: ðịnh vị biên. Chú ý rằng kỹ thuật nổi biên gây tác dụng phụ là gây
nhiễu làm một số biên giả xuất hiện do vậy cần loại bỏ biên giả.
o
Bước 4: Liên kết và trích chọn biên.
4.2 Phương pháp phát hiện biên trực tiếp
Phát hiện biên theo phương pháp cục bộ thường dùng một hàm biến ñổi
theo một dạng thức nào ñó ñể tìm ra ñường biên. Các hàm phát hiện biên thường
dùng như sau:


=
227
121
554
112
421
I
Th
ực hiện phép nhân

Chương 4:
Các Phươn
87
Hình 4.4
Các hàm thường dùng phát hi
ện bi
p dùng l
ọc ñặc biệt
h chuyển cửa sổ (Moving
-
Window Transfor
ñổi dịch chuyển cửa sổ (Moving
-
Window Tra
ích th
ước M × N, cửa sổ T có kích thước
m × n
eo cửa sổ T ñ
ược xác ñịnh bởi công thức:

0
),(*,
m
i
n
j
jiTiyixI

số I nh
ư sau








251
441
288
224
785
và cửa sổ







1
0
1
0
TyxITyxIjiTiyixIyxTI
i j
+++=++=⊗
∑∑
= =

(
)
(
)
1,1,
+
+
+
=
yxIyxINếu:
( )
∑∑
−
=
−
=
++=⊗

*66243
*1212666
*412967
*107832
TI

Hay:
( )
∑∑
−
=
−
=
−−=⊗
1
0
1
0
),(*,),(
m
i
n
j
jiTiyixIyxTI

Thì:




Hình 4.5
b. Phương pháp d
ịch v
Sử dụng ph
ươn
copy m
ột lần trong m
chuyển ñi trên
ảnh g
nạ. M
ỗi lần copy sẽ n
pixel ñược dịch v
à di
Hình
c. Dịch và di chuy
ển dạ
Một xung là
ảnh
ñược mô tả bởi:
(
,
r c
δ ρ χ
− −


ảnh số m
à pixel có hai giá tr
ị 0 hay 1, Một x
)
1, if and
,
0,
r c
ρ χ
χ
= =

− =

≠


ương Pháp Phát Hi
ện Biên

uyển

er).
Các phần tử ñược
n copy ñ
ược dịch và di
ương
ứng trong mặt
ặt nạ với nhau.
Tập các


Hình 4.7 Ảnh minh họa phép dịch chuyển dạng xung

4.2.2 Phương pháp Gradient
4.2.2.1 Các kỹ thuật Gradient
Phép toán Gradient là kỹ thuật phát hiện biên trực tiếp thường sử dụng các
toán tử sau:
o
Toán tử Robert (1965).
o
Toán tử (mặt nạ) Sobel.
o
Mặt nạ Prewitt.
o
Mặt nạ ñẳng hướng.
o
Toán tử 4-lân cận (4-Neighbour Operator).
 ðịnh nghĩa:
Gradient là một vector f(x,y) có các thành phần biểu thị tốc ñộ thay
ñổi mức xám của ñiểm ảnh (theo hai hướng x, y trong không gian hai chiều)
ñược biểu diễn theo các biểu thức sau:

Chương 4: Các Phương Pháp Phát Hiện Biên

91
( )
(

f x y f x dx y f x y
f
x dx
f x y f x y dy f x y
f
y dy
∂ + −
= ≈
∂
∂ + −
= ≈
∂

(4.5)
Trong ñó dx, dy là khoảng cách giữa 2 ñiểm kế cận theo hướng x, y tương ứng
(thực tế chọn dx= dy=1). ðây là phương pháp dựa theo ñạo hàm riêng bậc nhất theo
hướng x, y.
Như vậy ta có
o
ðộ lớn Gradient:( ) ( )
( )
( )
( )
2
2
, , ,
x y

 

(4.7)
o
ðộ lớn Gradient xấp xỉ:
(
)
(
)
(
)
, , ,
x y
f x y h f x y h f x y
∇ = ⊗ + ⊗

(4.8)
o
Các mặt nạ theo các hướng sau: Hình 4.8
Ảnh
o
Ví d
ụ với dx=dy
( )

( ) ( )
( ) ( )
, ,
, ,
f x dx y f x y
f x y dy f x y
= + −
= + −

nhân ch
ập:
ớng x l
à:
)1,1(−=A

eo hư
ớng y là:








−
=
1
1
B

=
3
30
3
30
3
30
0
00
I
Thì:






=⊗
**
03
03
00
AI
( ) (
⊗+⊗
B
IAI

Trong k
ỹ thuật grad

0
;
)1,1(−=A
,








−
=
1
1
B







**
*0
*0
*0
;



=
****
*003
*003
*330
B

ật gradient, ng
ười ta chia nhỏ thành 2 k
ỹ thuật
row i-1
row i
row i+1
col j-1
col j
I(i-1,j-1)
I(i,j-1)
I(i+1,j-1)
I
(i-1,j)
I
(i,j)
I
(i+1,j)
ương Pháp Phát Hi
ện Biên

thuật (do d
ùng 2 toán tử

( , ) 1, ,
( , ) , 1 ,
x
y
I m n I m n I m n
I m n I m n I m n

= + −


= + −



(4.10)

( ) ( ) ( )
( )
( ) ( )
( )
( ) ( ) ( ) ( ) ( )
, 1, , , 1 ,
, 1, , , 1 ,
x y
I m n I m n I m n i I m n I m n i
I m n I m n I m n I m n I m n
→ →
⇒ ∇ = + − + + −
⇒ ∇ = + − + + −
(4.11)

[
]
[
]
[
]
101 −==
T
yx
hh

(4.13)
a. Toán tử Robert
Robert áp dụng công thức tính Gradient tại ñiểm (x,y). Với mỗi ñiểm ảnh
I(x,y) ñạo hàm theo x, y ñược ký hiệu tương ứng: g
x
, g
y
:
(
)
( )
1, ( , )
, 1 ( , )
x
y
g I x y I x y
g I x y I x y

= + −

=
10
01
01
10
yx
HH

(4.15)

Coi như ñạo hàm tại ñiểm (i+1/2, j+1/2) theo hướng 2 ñường chéo

Hình 4.11 Tọa ñộ ñiểm sau khi dùng toán tử Robert

ðối với ảnh số, các ñạo hàm vừa nêu có thể xấp xỉ bằng các sai phân
(difference)
1
2
( , ) ( 1, 1)
( 1, ) ( , 1)
a i j a i j
a i j a i j
∇ = − + +
∇ = + − +

(4.16)

2 2
1 2
⇒ ∇ = ∇ +∇

−
−
=
101
202
101
h
hay










−
−
−
101
202
101

(4.18)Hình 4.13 ðồ thị mặt nạ lọc Sobel theo chiều x


000
121

(4.19)
Hìn
Ví d
ụ: hai mặt n
[ ]
[ ]
=
=
T
yx
hh
[ ]
1
2
1
4
1





ồ thị mặt nạ lọc Sobel theo chiều
mặt nạ sẽ thực hiện theo
hai chi
ều có dạng nh

Hình 4.15 Cửa sổ của toán tử Sobel

[ ]
101 −
=

[ ]
101
1
2
1
4
1
10
20
10
−•












−
=





−−

ta th
ấy h
x
và h
y
ñều tách ñư
ợc, mỗi bộ lọc lấy
ơng tr
ình [h
x
] và làm trơn theo hướng trực
giao
giác 1
- chiều.
ương Pháp Phát Hi
ện Biên

iều y

( 1, 1
a i j
a i j
∇ = −
− + +
(
2
1,
( 1, 1
a i j
a i j
∇ = −
− − −
2
1
∇ = ∇ + ∇
o
Cách tính toán t
+
Mặt nạ v
ào
ñược ñặt l
ên
+
M
ặt nạ sobe
trị
và sau ñó
j a i j a i j
+ + − + − −
+ − + − + −

)
1, 1 2 ( , 1) ( 1, 1)
1, 1) 2 ( , 1) ( 1, 1)
j a i j a i j
j a i j a i j
+ + + + + +
− − − − + −

2
2
+ ∇

toán t
ử Sobel:
ào
: là giá trị các pixel có cùng kích thư
ớc
ên
ảnh vào có dạng như sau:
P1

P2

P3

P4

ện Biên (4.23)

(4.24)
(4.25)
ớc với mặt nạ cửa sổ
ợc tính theo từng giá
ống d
ưới

Chương 4: Các Phương Pháp Phát Hiện Biên

99
1

0

-1

+
Mặt nạ sobel theo chiều dọc tính S2. Giá trị ñược tính theo từng giá trị
và sau ñó dịch từ trái sang phải rồi từ trên xuống dưới
-1

-2

S1 = (P1+2P4+P7) - (P3+2P6+P9)
S2 = (P7+2P8+P9) - (P1+2P2+P3)
(
)
2 2
1 2 1 2
f S S S S
∇ = + ≈ +

(4.26)
+
Nếu
∇f >=threshold
thì S=0
+
Nếu
∇f <=threshold
thì S=1
o
Ví dụ toán tử Sobel: Tương tự như kỹ thuật kỹ Prewitt kỹ thuật Sobel sử
dụng 2 mặt nạ nhân chập theo 2 hướng x, y là:










−
−
−
=
101
202
101
x
H
,










−−−
=
121
000
121
y
H

Tìm:
∇

ình 4.1
6 Kết quả của ảnh dùng lọc Sobel

17
Ảnh kết quả làm nổi biên dùng toán t
ử So
ặt nạ có khả năng phát hiện ñ
ường bi
ên khác n
ện ñ
ường biên sử dụng hai mặt nạ thì b
ằng g
mặt nạ theo chiều ngang v
à theo chiều dọc.
ỡng
càng nhỏ thì khả năng phát hiện ñư
ờng
ương Pháp Phát Hi
ện Biên Sobel

khác nhau.

ằng ghép ñ
ường biên sử
ờng bi
ên càng lớn.


00
11
Ví d
ụ: hai mặt nạ sẽ t
Hình 4.18
Hai
[ ]
[ ]
=
=
T
yx
hh
[ ]
0
1
0
1
0
1
3
1





=
x
h

ùng toán t
ử Prewitt theo chiều x





−
−
−
1
1
1
cho ra
x
I

ùng toán t
ử Prewitt theo chiều y





−1
0
1
cho ra
y
I






=





−
−
−

[ ]
111
1
0
1
3
1
11
00
11
•





ện Biên
. C
ũng như các phép
àm b
ậc 1 của ảnh vào.
ình 4.18oán tử Prewitt

(4.27)

(4.28)

(4.29)
ọc lấy ñạo h
àm theo một
c giao với h
ướng ñó nhờ

Chương 4: Các Phương Pháp Phát Hiện Biên

102
o
Ví dụ toán tử Prewitt : kỹ thuật sử dụng 2 mặt nạ nhân chập xấp xỉ ñạo hàm
theo 2 hướng x và y là:


101










−
−
−
=
x
H

;
111
000
111









=⊗
******
******
**5101515
**5101515
**0000
**5101515
y
HI




















−−






=⊗+⊗
******
******
**10151515
**15201515
**151500
**501515
yx
HIHI

o
Cách tính toán tử Prewitt:
Ta có thể sử dụng 2 mặt nạ theo dạng ñường chéo h
D1
và h
D2
ñều tách ñược,
mỗi bộ lọc lấy ñạo hàm theo một ñường chéo nhờ phương trình [h
D
] và làm trơn
theo hướng trực giao với hướng ñó nhờ một bộ lọc tam giác 1- chiều.
+

Tương tự toán tử Sobel, toán tử Prewitt dùng mặt nạ vào là giá trị các
pixel có cùng kích thước với mặt nạ cửa sổ ñược ñặt lên ảnh vào có

, toán tử Prewitt dùng mặt nạ vào theo
chiều ngang ñể tính P
D1
. Giá trị ñược tính theo từng giá trị và sau ñó
dịch từ trái sang phải rồi từ trên xuống dưới
0

1

1

-1

0

1

-1

-1

0

+

Mặt nạ Prewitt theo chiều tính P
D2
, toán tử Prewitt dùng mặt nạ vào
theo chiều ngang ñể tính P
D2o
Giải thuật:
P
d1
= (Z2+Z3+Z6) – (Z4+Z7+Z8) (4.30)
P
d2
= (Z6+Z8+Z9) – (Z1+Z2+Z4) (4.31)
Tính giá trị P: (Z5)
(
)
2 2
1 2 1 2
D D D D
f P P P P
∇ = + ≈ +

(4.32)

Chương 4: Các Phương Pháp Phát Hiện Biên

104


1 2 1
2 0 2 0 0 0
1 0 1
1 2 1
x y
H H
−
   
− − −
   
= − =
   
   
−
   

e. Toán tử 4 lân cận:
Toán tử 4 - lân cận ñược Chaudhuri và Chandor (1984) nêu ra, trong ñó mặt
nạ có kích thước 3x3 ñược thay cho mặt nạ 2x2 của toán tử Robert. Các mặt nạ
này ñược cho:
o
Mặt nạ theo chiều tính trục x
0

-1

0

0



0

0

0

0

f. Khớp nối lỏng:
Với ñiểm P ñược bao phủ xung quanh bởi 8 ñiểm: P0, P1, …P8:
P3

P2

P1

P4

P

P0

P5

P6

P7

o

5

7

1

2

8

5

7

1

4 g. Nhận xét
o
Toán t
ử Prewitt
o

cos .
h h
θ
θ
=
Có nhi
ều toán tử
toán t
ử Kirsh. Toán tử

Chương 4:
Các Phươn
107
rewitt có thể tách bi
ên ñứng tốt hơn toán t
ử Sob
obel tách các s
ườn trên các ñiểm ở ñư
ờng chéo
ử Robert v
à toán tử 4-lân cận có như
ợc ñiểm l
ñể ñạt ñ
ư
ợc kết quả mong muốn các toán tử
ớc ñể l
àm sạch nhiễu.
ạ của các toán tử tr
ên có kích thư
ớc 2x2 hoặc 3

oán tử n
ày sử dụng mặt nạ 3x3
ương Pháp Phát Hi
ện Biên
ử Sobel,

chéo tốt h
ơn.
iểm l
à nhạy với nhiễu.
toán tử
Gradient thường
hoặc 3x3 chiều. Các mặt
ai chiều (x,y) tức l
à bốn
ọn. Nếu kí hiệu g
k
là
7. Nh
ư vậy ta có gradient
(4.33)

ình bày m
ột cách chi tiết

Chương 4: Các Phương Pháp Phát Hiện Biên


5 3 3 5 5 3
5 0 3 5 0 3
5 3 3 3 3 3
H H
− − −
   
   
= − = −
   
   
− − − − −
   

Trong ñó H1, H2, H3, …H8 tương ứng với 8 hướng: 0
0
, 45
0
, 90
0
, 135
0
,
180
0
, 225
0
, 315
0
. Nếu ta kí hiệu












−−
−−
=










−
−−−
=
111
121
111
111

−=










−−
−−=
111
121
111
111
121
111
111
121
111
654
HHH







Tóm lại:
Các kỹ thuật sử dụng phương pháp Gradient khá tốt khi ñộ sáng có tốc ñộ
thay ñổi nhanh, khá ñơn giản trên cơ sở các mặt nạ theo các hướng. Nhược