B CÔNG TH NGỘ ƯƠ
TR NG Đ I H C CÔNG NGHI P HÀ N IƯỜ Ạ Ọ Ệ Ộ
KHOA CÔNG NGH THÔNG TINỆ
BÁO CÁO X LÝ NHỬ Ả
Đ Tàiề: Dò biên
Giáo viên h ng d n: Tr n Hùng C ngướ ẫ ầ ườ
Nhóm sinh viên th c hiên: Nguy n Văn Đi pự ễ ệ
Nguy n Huy Đôngễ
Nguy n H ng Hi uễ ồ ế
Ph n 1 ầT NG QUAN V BIÊN VÀ CÁC PH NG PHÁP PHÁT HI NỔ Ề ƯƠ Ệ
BIÊN
1.1. V trí c a biên trong phân tích nh ị ủ ả
Phân tích nh là m t qua trình g m nhi u giai đo n. Đ u tiên là giai đo nả ộ ồ ề ạ ầ ạ
ti n x lý nh. Sau giai đo n này, nh đ c tăng c ng hay đ c khôi ph c đề ử ả ạ ả ượ ườ ượ ụ ề
làm n i các đ c tính ( feature extraction ), ti p theo là phân đo n nhồ ặ ế ạ ả
(segmentation) thành các ph n t . Thí d , nh phân đo n d a theo biên, d a theoầ ử ụ ư ạ ự ự
vùng,… Và tuỳ theo các ng d ng, giai đo n ti p theo có th là nh n d ng nh (ứ ự ạ ế ể ậ ạ ả
phân thành các l p có miêu t ) hay là gi i thích và miêu t nh. Hình 1.1 mô tớ ả ả ả ả ả
tóm l c các b c c a quá trình phân tích nh:ượ ướ ủ ả
nh đ u ra c aẢ ầ ủ
quá trình ti n XL ề
Hình 1.1. Các b c trong phân tích nhướ ả
Các đ c tr ng c a nh th ng g m: m t đ xám, phân b xác xu t, phân bặ ư ủ ả ườ ồ ậ ộ ổ ấ ồ
không gian, biên nh. Các k thu t phân đo n nh ch y u d a vào biên.ả ỹ ậ ạ ả ủ ế ự
Do đó, biên có t m quan tr ng đ c bi t trong qua trình phân tích nh.ầ ọ ặ ệ ả
1.2. Biên và các k thu t dò biênỹ ậ
Trong ph n này chúng ta s đ c p đ n m t s n i dung: khái ni m vầ ẽ ề ậ ế ộ ố ộ ệ ề
biên, phân lo i các ph ng pháp phát hi n biên và qui trình phát hi n biên.ạ ươ ệ ệ
1.2.1. Khái ni m v biênệ ề
Biên là m t v n đ ch y u trong phân tích nh vì các k thu t phân đo nộ ấ ề ủ ế ả ỹ ậ ạ
nh ch y u d a vào biên. ả ủ ế ự
M t đi m nh có th coi là đi m biên n u đó có s thay đ i đ t ng tộ ể ả ể ể ế ở ự ổ ộ ộ
v m c xám. T p h p các đi m biên t o thành biên hay đ ng bao nh c a nhề ứ ậ ợ ể ạ ườ ả ủ ả
(boundary).
Thí d , trong m t nh nh phân, m t đi m có th g i là biên n u đó làụ ộ ả ị ộ ể ể ọ ế
đi m đen và có ít nh t m t đi m tr ng là lân c n.ể ấ ộ ể ắ ậ
Đ hình dung t m quan tr ng c a biên ta xét ví d sau: Khi ng i ho sĩể ầ ọ ủ ụ ườ ạ
v m t cái bàn g , ch c n vài nét phác th o v hình dáng nh cái m t bàn, chânẽ ộ ỗ ỉ ầ ả ề ư ặ
bàn mà không c n thêm các chi ti t khác, ng i xem đã có th nh n ra nó là m tầ ế ườ ể ậ ộ
cái bàn. n u ng d ng c a ta là phân l p nh n di n đ i t ng, thì coi nhế ứ ụ ủ ớ ậ ệ ố ượ ư
nhi m v đã hoàn thành. Tuy nhiên n u đòi h i thêm v các chi ti t khác nhệ ụ ế ỏ ề ế ư
vân g hay màu s c,…thì v i ch ng y thông tin là ch a đ .ỗ ắ ớ ừ ấ ư ủ
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 v y phát hi n biên m t cách lý t ng làự ế ổ ộ ộ ề ộ ư ậ ệ ộ ưở
xác đ nh đ c t t c các đ ng bao trong các đ i t ng. Đ nh nghĩa toán h cị ượ ấ ả ườ ố ượ ị ọ
c a biên trên là c s cho các k thu t phát hi n biên. Đi u quan tr ng là sủ ở ơ ở ỹ ậ ệ ề ọ ự
bi n thiên m c xám gi a các nh trong m t vùng th ng là nh , trong khi đóế ứ ữ ả ộ ườ ỏ
bi n thiên m c xám c a đi m vùng giáp ranh (khi qua biên) l i khá l n.ế ứ ủ ể ạ ớ
1.2.2. Phân lo i các k thu t phát hi n biênạ ỹ ậ ệ
Xu t phát t đ nh nghĩa toán h c c a biên ng i ta th ng s d ng 2ấ ừ ị ọ ủ ườ ườ ử ụ
ph ng pháp phát hi n biên sau:ươ ệ
1.2.2.1.Ph ng pháp phát hi n biên tr c ti p: ươ ệ ự ế
Ph ng pháp này nh m làm n i biên d a vào s bi n thiên v giá tr đ sángươ ằ ổ ự ự ế ề ị ộ
c a đi m nh. k thu t ch y u dùng phát hi n biên đây là 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 hai ta có k thu t Laplace. Hai ph ng pháp trên đ c g i là ph ngậ ỹ ậ ươ ượ ọ ươ
pháp dò biên c c b . ngoài ra ng i ta còn s d ng ph ng pháp “đii theoụ ộ ườ ử ụ ươ
đ ng bao”: d a vào nguyên lý qui ho ch ho t đ ng và đ c g i là ph ngườ ự ạ ạ ộ ượ ọ ươ
pháp dò biên t ng th .ổ ể
1.2.2.2.Ph ng pháp gián ti p: ươ ế
N u b ng cách nào đ y , ta phân đ c nh thành các vùng thì đ ng phânế ằ ấ ượ ả ườ
ranh gi a các vùng đó chính là biên. vi c phân vùng nh th ng d a vào k t c uữ ệ ả ườ ự ế ấ
(texture) b m t c a nh. ề ặ ủ ả
Cũng c n l u ý r ng, k thu t dò biên và phân vùng nh là hai bài toán đ iầ ư ằ ỹ ậ ả ố
ng u c a nhau. Th c v y, dò biên đ th c hi n phân l p đ i t ng và m t khiẫ ủ ự ậ ể ự ệ ớ ố ượ ộ
đã phân l p xong có nghĩa là đã phân vùng đ c nh. Và ng c l i, khi phânớ ượ ả ượ ạ
vùng, nh đã phân l p đ c thành các đ i t ng, ta có th phát hi n đ c biên.ả ậ ượ ố ượ ể ệ ượ
Ph ng pháp dò 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 này l i kémễ ế ự ế ộ ộ ộ ươ ạ
hi u qu . Ph ng pháp dò biên gián ti p tuy có khó cài đ t song l i áp d ng kháệ ả ươ ế ặ ạ ụ
t t khi s bi n thiên đ sáng nh .ố ự ế ộ ỏ
1.2.3. Qui trình phát hi n biên tr c ti pệ ự ế
b1) Kh nhi u nhử ễ ả
Vì nh thu nh n th ng có nhi u, nên b c đ u tiên là ph i kh nhi u.ả ậ ườ ễ ướ ầ ả ử ễ
vi c kh nhi u đ c th c hi n b ng các k thu t kh nhi u khác nhau. ệ ử ễ ượ ự ệ ằ ỹ ậ ử ễ
b2) Làm n i biên ổ
Ti p theo là làm n i biên b i các toán t đ o hàmế ổ ở ử ạ
b3) Đ nh v đi m biênị ị ể
Vì các k thu t làm n i biên có hi u ng ph là tăng nhi u , do v y s cóỹ ậ ổ ệ ứ ụ ễ ậ ẽ
m t s đi m biên gi c n lo i b .ộ ố ể ả ầ ạ ỏ
b4) liên k t và trích ch n biên.ế ọ
Nh đã nói, phát hi n biên và phân vùng nh là m t bài toán đ i ng u. vìư ệ ả ộ ố ẫ
th cũng có th phát hi n biên thông qua vi c phân vùng nh.ế ể ệ ệ ả
1.3. M t s ph ng pháp phát hi n biên c c bộ ố ươ ệ ụ ộ
1.3.1. Ph ng pháp gradientươ
Ph ng pháp gradient là ph ng pháp dò biên c c b d a vào c c đ iiươ ươ ụ ộ ự ự ạ
c a đ o hàm. Theo đ nh nghĩa, gradient là m t véct có các thành ph n bi u thủ ạ ị ộ ơ ầ ể ị
t c đ thay đ i giá tr c a đi m nh theo hai h ng x và y . các thành ph n c aố ộ ổ ị ủ ể ả ướ ầ ủ
gradient đ c tính b i:ượ ở
df(x,y) = fx ≈f(x+dx,y) – f(x,y)
dx dx
df(x,y) = fy ≈f(x,y+dy) – f(x,y)
dy dy
v i dx là kho ng cách gi a các đi m theo h ng x ( kho ng các tính b ng sớ ả ữ ể ướ ả ằ ố
đi m) và t ng t v i dy. Trên th c t , ng i ta hay dùng v iể ươ ự ớ ự ế ườ ớ
dx = dy = 1
Trong k thu t gradient, ng i ta chia thành 2 k thu t (do dùng 2 toán tỹ ậ ườ ỹ ậ ử
khác nhau): k thu t gradient và k thu t la bàn. k thu t gradient dùng toán tỹ ậ ỹ ậ ỹ ậ ử
gradient l y đ o hàm theo hai h ng; còn k thu t la bàn l y đ o hàm theo 8ấ ạ ướ ỹ ậ ấ ạ
h ng chính: B c, Nam, Đông ,Tây và Đông B c, Tây B c, Đông Nam, Tâyướ ắ ắ ắ
Nam.
1.3.1.1.K thu t gradient ỹ ậ
K thu t này s d ng m t c p m t n Hỹ ậ ử ụ ộ ặ ặ ạ 1 và H2 tr c giao ( theo 2 h ngự ướ
vuông góc). N u đ nh nghĩa gế ị 1,g2 là gradient t ng ng theo 2 h ng x và y, thìươ ứ ướ
biên đ c a gradient, ký hi u là g t i đi m (m,n) đ c tính theo công th c:ộ ủ ệ ạ ể ượ ứ
A0 = g(m,n) = √ g² 1(m,n) + g22(m,n) (1.2)
θr(m,n) = tan-1g2(m,n)/ g1(m,n) (1.3)
Chú ý: đ gi m tính toán, công th c 1-2 đ c tính g n đúng b i:ể ả ứ ượ ầ ở
A0 = | g1(m,n) | + | g2(m,n) |
Các toán t đ o hàm đ c áp d ng là khá nhi u. đây ta ch xét m t sử ạ ượ ụ ề ở ỉ ộ ố
toán t tiêu bi u: toán t Robert, Sobel, Prewitt…ử ể ử
Tr c tiên chúng ta xét toán t Robert. Toán t này do Robert đ xu t vàoướ ử ử ề ấ
năm 1965. Nó áp d ng tr c ti p c a các công th c đ o hàm t i đi m (x,y). v iụ ự ế ủ ứ ạ ạ ể ớ
m i đi m nh I(x,y) c a I, đ o hàm theo x, theo y đ c ký hi u t ng ng b iỗ ể ả ủ ạ ượ ệ ươ ứ ở
gx, gy đ c tính:ượ
gx = I(x +1,y) – I(x,y)
gy =I(x,y+1) – I(x,y)
đi u này t ng đ ng v i vi c ch p nh v i 2 m t n Hề ươ ươ ớ ệ ậ ả ớ ặ ạ 1 và H2:
H1 = 0 1 H2 = -1 0
-1 0 0 -1
Ta g i Họ1,H2 là m t n Robert.ặ ạ
Trong tr ng h p t ng quát, giá tr gradient biên đ g và gradient h ng ườ ợ ổ ị ộ ướ θr
đ c tính b i công th c 1.2 và 1.3. Th ng đ gi m th i gian tính toán, ng i taượ ở ứ ườ ể ả ờ ườ
còn tính gradient theo các chu n sau:ẩ
A1 = | g1(m,n) + g2(m,n) |
ho cặ
A2 = max( | g1(m,n) | , | g2(m,n) |)
C n l u ý r ng, do l m d ng v ngôn t , tuy ta l y đ o hàm c a nhầ ư ằ ạ ụ ề ừ ấ ạ ủ ả
nh ng th c ra ch là mô ph ng và x p x đ o hàm b ng k thu t nhân ch p doư ự ỉ ỏ ấ ỉ ạ ằ ỹ ậ ậ
nh s là tín hi u r i r c, do v y đ o hàm không t n t i.ả ố ệ ờ ạ ậ ạ ồ ạ
Trong k thu t Sobel và prewtt ng i ta s d ng 2 m t n :ỹ ậ ườ ử ụ ặ ạ
H1 =
-1 0 1
H2 =
-1 -1 -1
-1 0 1 0 0 0
-1 0 1 1 0 1