Đề tài Nghiên cứu về một số thuật toán tách biến ảnh

Bé quèc phßng Häc viÖn kü thuËt qu©n sù ----------------------------------------------- Hå s¬ Ph­¬ng ph¸p nghiªn cøu khoa häc Tªn ®Ò tµi: Nghiªn cøu vÒ mét sè thuËt to¸n t¸ch biªn ¶nh. Gi¸o viªn h­íng dÉn:NGUYEN VĂN CHÂU Häc viªn thùc hiÖn : ĐỖ KHOA BÌNH §¬n vÞ : Lop Dien Tu Y Sinh Hoà sô bao goàm: 1.phieáu ñaêng kyù ñeà taøi 2.Ñeà cöông nghieân cöùu 3.Thuyeát minh ñeà taøi 4.Bieân baûn baûo veä ñeà taøi Hµ Néi,ngµy30 /8/2007 PhiÕu ®¨ng ký ®Ò tµi 1.C¬ quan chñ tr×: Boä Moân: Voâ Tuyeán Ñieän Töû-Nhaø H1-taàng2 –HVKTQS Ñieän thoaïi :069.515.124 2.C¬ quan chñ qu¶n: Phoøng khoa hoïc vaø moâi tröôøng- Nhµ A2-HVKTQS §iÖn tho¹i: 069.515.223 3.Tªn ®Ò tµi:Nghiªn cøu mét sè thuËt to¸n t¸ch biªn ¶nh 4.M· sè ®Ò tµi: 5.Sè ®¨ng ký: 6.ChØ sè ph©n lo¹i: 7.Chñ nhiÖm ®Ò tµi: Phan §øc Huy CÊp bËc: trung sü Chøc vô: Häc viªn 8.Tãm t¾t ®Ò tµi: §Ò tµi “ Nghiªn cøu vÒ mét sè thuËt to¸n t¸ch biªn ¶nh” bao gåm 2 ch­¬ng vµ 28 môc ®Ò cËp ®Õn mét sè thuËt to¸n hay vµ cã tÝnh kh¸i qu¸t trong lÜnh vùc t¸ch vµ xö lý ¶nh, mét lÜnh vùc t­¬ng ®èi m¬Ý mÎ ë ViÖt Nam. Trong ®ã néi dung cña ch­¬ng 1 tr×nh bµy c¸c kh¸i niªm còng nh­ c¸c phÐp biÕn ®æi c¬ b¶n vÒ kÜ thuËt xö lÝ ¶nh, c¸c phÐp lµm t¨ng chÊt l­îng ¶nh… . Ch­¬ng hai ®Ò cËp ®Õn c¸c ph­¬ng ph¸p t×m biªn cña ¶nh bao gåm “Ph­¬ng ph¸p t×m biªn dùa trªn kü thuËt läc tuyÕn tÝnh” vµ “Mét sè ph­¬ng ph¸p t×m biªn phi tuyÕn”. Toµn bé ®Ò tµi gi¶i quyÕt mét c¸ch kh¸ s©u c¸c thuËt to¸n, mét sè thuËt to¸n cã thÓ ¸p dông ®Ó t¹o nªn mét c«ng cô lËp tr×nh xö lÝ ¶nh kh¸ hoµn chØnh vµ h÷u hiÖu ®èi víi ng­êi lËp tr×nh. Cô thÓ tªn c¸c ch­¬ng vµ c¸c môc nh­ sau: Më ®Çu……………………………… .1 Ch­¬ng I: Tæng quan vÒ c¸c kh¸i iÖm vµ mét sè kÜ thuËt xö lÝ ¶nh…..2 1. C¸c kh¸i niÖm c¬ b¶n………………………………………………..2 1.1. Xö lÝ ¶nh…………………………………………………………...2 1.2. Qóa tr×nh thu nhËn,biÓu diÔn vµ l­u gi÷ ¶nh 1.2.1. Qóa tr×nh thu nhËn ¶nh…………………………………………..2 1.2.2.Qóa tr×nh biÓu diÔn ¶nh…………………………………………..2 1.2.3. L­u gi÷ ¶nh……………………………………………………...3 9.S¶n phÈm cña ®Ò tµi: 10.Tõ kho¸: 11. Thêi gian thùc hiÖn: 12. Tæng kinh phÝ thùc hiÖn: 1.100.000ÑVN B¾t ®Çu KÕt thóc 19/8/2005 19/8/2006 13.Lo¹i h×nh nghiªn cøu: Nghiªn cøu øng dông Nghiªn cøu c¬ b¶n Nghiªn cøu øng dông TriÓn khai thùc nghiÖm 14. LÜnh vùc khoa häc: Kü thuËt c«ng nghÖ Tù nhiªn Kü thuËt c«ng nghÖ N«ng nghiÖp X· héi nh©n v¨n CNTT Ngµy 26 thaùng 9 naêm 2005 Ngaøy 30 thaùng 9 naêm 2005 Chñ nhiÖm ®Ò tµi Cô quan chuû trì Khoa VT§T Phan §øc Huy Ngµy 30 th¸ng9 n¨m 2006 C¬ quan chñ qu¶n Phoøng Khoa Hoïc vaø Moâi Tröôøng Bé quèc phßng Häc viÖn kü thuËt qu©n sù ----------------------------------------------- ThuyÕt minh ®Ò tµi nghiªn cøu khoa häc vµ ph¸t triÓn c«ng nghÖ Tªn ®Ò tµi: Nghiªn cøu vÒ mét sè thuËt to¸n t¸ch biªn ¶nh. Hµ Néi,ngµy 30/9/2006 I.Th«ng tin chung vÒ ®Ò tµi. 1.Tªn ®Ò tµi: Nghiªn cøu mét sè thuËt to¸n t¸ch biªn ¶nh 2.M· sè: 3.Thêi gian thùc hiÖn:1 naêm 4.CÊp qu¶n lý: 5.Kinh phÝ:1.100.000 ñoàng VN 6.Thuéc ch­¬ng tr×nh: M«n häc “Ph­¬ng ph¸p nghiªn cøu khoa häc.” 7.Chñ nhiÖm ®Ò tµi: Hä vµ tªn: Phan §øc Huy CÊp bËc Trung sü Chøc vô:Häc viªn §iÖn tho¹i: 0912347983 Fax: §Þa chØ c¬ quan: §Þa chØ nhµ riªng: Yªn ThÕ_B¾c Giang 8.C¬ quan chñ tr× ®Ò tai: Boä Moân VTÑT Tªn tæ chøc Khoa häc vµ C«ng nghÖ: Khoa CNTT – Häc viÖn KTQS II.Néi dung khoa häc vµ c«ng nghÖ cña ®Ò tµi. 9.Môc tiªu ®Ò tµi: Lµ phôc vô trong c«ng viÖc nhËn d¹ng ¶nh, mét trong nh÷ng mÆt øng dông quan trong nhÊt cña xö lý ¶nh ®­îc øng dông rÊt nhiÒu trong lÜnh vùc qu©n sù nh­ sè ho¸ b¶n ®å, nhËn d¹ng nguy c¬… 10.T×nh h×nh nghiªn cøu trong vµ ngoµi n­íc: 11.C¸ch tiÕp cËn-ph­¬ng ph¸p nghiªn cøu-kü thuËt sÏ sö dông: 12.Néi dung nghiªn cøu: Néi dung chÝnh cña ®Ò tµi bao gåm: 2.3.C¸c ph­¬ng ph¸p lµm t¨ng chÊt l­îng ¶nh. 2.3.1.C©n b»ng Histogram Histogram dïng ®Ó biÓu diÔn tÇn suÊt xuÊt hiÖn cña c¸c ®iÓm ¶nh ®èi víi c¸c møc s¸ng kh¸c nhau. Kü thuËt c©n b»ng histogram söa ®æi ®Ó histogram cña ¶nh cã h×nh d¸ng c©n b»ng nh­ mong muÊn. Gi¶ sö cã ¶nh víi L møc s¸ng (0,L-1), mét ®Çu vµo u, khi ®ã: (10) vµ ®Çu ra v ®­îc ®Þnh nghÜa nh­ sau: (11) (12) trong ®ã vmin lµ gi¸ trÞ nhá nhÊt cña v tõ c«ng thøc (11) nÕu u = xk th× (10) trë thµnh : (13) do ®ã pu(xk) vµ pv(xk) lµ gièng nhau. 2.3.2. §¶o ®é t­¬ng ph¶n vµ tû sè thèng kª Trong qu¸ tr×nh xö lý ¶nh, ®«i khi cÇn thiÕt n©mg cao kh¶ n¨ng t×mmét ®èi t­îng nµo ®ã trªn nÒn ¶nh.Kh¶ n¨ng t×m nµy cña mét hÖ thèng trùc quan phô thuéc vµo kÝch th­íc vµ tû lÖ t­¬ng ph¶n g ®­îc ®Þnh nghi· nh­ sau: (14) trong ®ã : m : lµ ®é s¸ng trung b×nh cña ®èi t­îng (15) d : lµ ®é lÖch chuÈn cña ®é s¸ng cña ®èi t­îng so víi xung quanh nã. XÐt ¸nh x¹ ®¶o sau : ë ®©y m(m,n) lµ trung b×nh ®Þa ph­¬ng d(m,n) : lµ ®é lÖch chuÈn cña u(m,n) lÊy trªn ph¹m vi côc bé lµ cöa sæ w vµ ®­îc tÝnh bëi: (16) (17) Tõ c«ng thøc 15,16,17 thÊy r»ng, t¹i nh÷ng ®iÓm mµ sù chªnh lÖch ®é s¸ng cña nã so víi c¸c ®iÓm xung quanh lµ nhá th× kÕt qu¶ ®Çu ra sÏ lín. V× vËy, phÐp biÕn ®æi nµy lµm næi lªn c¸c ®iÓm biªn yÕu cña ¶nh. 2.3.3. Phãng to ¶nh vµ phÐp néi suy Trong qu¸ tr×nh xö lý ¶nh, th«ng th­êng hay cã nhu cÇu phãng to mét vïng nµo ®ã cña ¶nh. V× vËy cÇn ph¶i cã mét phÐp to¸n thùc hiÖn nã. Cã thÓ thùc hiÖn nh­ sau: T¹o ra ¶nh cã kÝch th­íc gÊp ®«i trªn mçi chiÒu, trong ®ã mçi mét ®iÓm trªn mét hµng ®­îc lÆp l¹i vµ mçi hµng còng ®­îc lÆp l¹i mét lÇn n÷a. §iÒu nµy t­¬ng ®­¬ng víi phÐp xÕp chång ¶nh 2M´2N (t¹o ra bëi kÕt hîp ¶nh ®· cho víi c¸c hµng vµ c¸c cét toµn sè 0) víi cöa sæ H nh­ sau : NÕu biÓu diÔn b»ng c«ng thøc ta ®­îc: V(m,n)=u(k,l) k=Int [m/2] l=Int [n/2] n=0,1,2,..... m=0,1,2,..... Mét ph­¬ng ph¸p kh¸c lµ phÐp néi suy tuyÕn tÝnh, nã ®­îc thùc hiÖn bëi c«ng thøc sau: Tõ ¶nh 2M´2N ®· t¹o ra ë trªn ®· t¹o ra bëi chÌn thªm c¸c hµng vµ cét zero, néi suy tuyÕn tÝnh trªn c¸c hµng: V1(m,2n)=u(m,n) V1(m,2n+1)=1/2[u(m,n)+u(m,n+1)] Víi 0<= m<= M-1 Víi 0<= n<= N-1 Sau ®ã néi suy trªn c¸c cét ta ®­îc : V(2m,n)= V1(m,n) Vµ V(2m+1,n)=1/2[V1(m,n)+ V1(m+1,n)] Víi m, n: 0<= m<= M-1 0<= n<= N-1 Nã t­¬ng ®­¬ng víi phÐp xÕp chång t¹i trung t©m ¶nh 2M´2N ®ã víi mÉu H sau H = 1/ 4 1/ 2 1/ 4 1/ 2 1 1/ 2 1/ 4 1/ 2 1/ 4 Hoµn toµn cã thÓ ¸p dông víi phÐp néi suy cÊp cao h¬n ®Ó phãng to ¶nh h¬n bëi thªm vµo p hµng vµ p cét c¸c sè zero, sau ®ã ¸p dông xÕp chång p lÇn víi mÉu H ta ®­îc kÕt qu¶ phãng to (p+1) lÇn nh­ mong muèn. Ch­¬ng 2 TæNG QUAN VÒ C¸C PH¦¥NG PH¸P T×M BI£N 1.C¬ së vÒ c¸c phÐp to¸n t×m biªn. T×m biªn, lµ ®i t×m c¸c ®­êng bao quanh c¸c ®èi t­îng trong ¶nh. Trong thùc tÕ ¶nh th­êng ®i kÌm theo nhiÔu, v× vËy t×m biªn lµ mét c«ng viÖc rÊt khã, vµ hÇu nh­ tr­íc khi sö dông c¸c thuËt to¸n t×m biªn, ph¶i tr¶i qua mét b­íc tiÒn xö lý, ®ã lµ qu¸ tr×nh lo¹i bá nhiÔu. C¬ së cña c¸c ph­¬ng ph¸p t×m biªn, ®ã lµ qu¸ tr×nh biÕn ®æi lín vÒ gi¸ trÞ ®é s¸ng cña c¸c ®iÓm ¶nh khi ®i qua biªn. §iÒu ®ã cã nghÜa lµ, ®iÓm biªn lµ ®iÓm t¹i ®ã cã sù biÕn ®æi lín vÒ gi¸ trÞ ®é s¸ng. Trong khi ®ã, sù biÕn ®æi vÒ gi¸ trÞ ®é s¸ng cña c¸c ®iÓm thuéc mét ®èi t­îng lµ nhá. Nh­ vËy, nÕu chóng ta lµm næi lªn ®­îc nh÷ng ®iÓm ¶nh mµ t¹i ®ã cã sù biÕn ®æi lín vÒ gi¸ trÞ ®é s¸ng, hoÆc lµm næi ®­îc c¸c vïng kh¸c nhau cña ¶nh, mµ sù biÕn thiªn ®é s¸ng cña c¸c vïng lµ ®Òu, th× cã nghÜa lµ lµm næi ®­îc biªn cña ¶nh. §©y chÝnh lµ c¬ së cña c¸c thuËt to¸n t×m biªn xuÊt ph¸t tõ c¬ së nµy, cã hai ph­¬ng ph¸p t×m biªn tæng qu¸t, ®ã lµ ph­¬ng ph¸p t×m biªn trùc tiÕp vµ ph­¬ng ph¸p t×m biªn gi¸n tiÕp. T×m biªn trùc tiÕp, lµ qu¸ tr×nh trùc tiÕp lµm næi lªn nh÷ng ®iÓm biªn dùa vµo sù biÕn thiªn lín vÒ gi¸ trÞ ®é s¸ng t¹i chóng. Ph­¬ng ph¸p t×m biªn gi¸n tiÕp lµ ph©n vïng ¶nh dùa vµo phÐp xö lý kÕt cÊu ®èi t­îng, cô thÓ lµ dùa vµo sù biÕn thiªn nhá vµ ®ång ®Òu ®é s¸ng cña c¸c ®iÓm ¶nh thuéc mét ®èi t­îng. Tuy nhiªn, ph­¬ng ph¸p t×m biªn trùc tiÕp, th­êng ®­îc sö dông cã hiÖu qu¶ ®èi víi líp c¸c ¶nh Ýt chÞu ¶nh h­ëng cña nhiÔu. Ph­¬ng ph¸p t×m biªn gi¸n tiÕp dùa trªn c¸c vïng, ®ßi hái ¸p dông lý thuyÕt vÒ xö lý kÕt cÊu ®èi t­îng phøc t¹p. §èi víi c¸c ph­¬ng ph¸p t×m biªn trùc tiÕp, cã hai d¹ng c¬ b¶n sau: Ph­¬ng ph¸p t×m biªn dïng bé läc tuyÕn tÝnh, ph­¬ng ph¸p nµy dùa trªn phÐp to¸n xö lý l©n cËn côc bé hoÆc xö lý tæng thÓ, nã l¹i cã thÓ ph©n chia thµnh hai d¹ng c¬ b¶n n÷a sau ®©y: + PhÐp to¸n xö lý l©n cËn: sö dông c¸c ma trËn hÖ sè läc kÝch th­íc nhá (3´3, 5´5, ...). + PhÐp xö lý tæng thÓ: thùc hiÖn trªn toµn ¶nh vµ cã thÓ coi nã nh­ sö dông ma trËn hÖ sè läc cã kÝch th­íc b»ng kÝch th­íc cña ¶nh. Ph­¬ng ph¸p t×m biªn phi tuyÕn: ph­¬ng ph¸p nµy kh«ng dùa trªn phÐp läc tuyÕn tÝnh mµ sö dông c¸c phÐp to¸n phi tuyÕn, nh­ phÐp lùa chän, so s¸nh, ... 2.C¸c ph­¬ng ph¸p t×m biªn dùa trªn kü thuËt läc tuyÕn tÝnh. Thùc chÊt, lµ qu¸ tr×nh xÕp chång ¶nh ®Çu vµo víi mét h¹t nh©n xÕp chång t­¬ng øng. C¸c h¹t nh©n xÕp chång nµy ®­îc x©y dùng trªn c¬ së hai phÐp to¸n c¬ b¶n, ®ã lµ phÐp to¸n Gradient vµ phÐp to¸n Laplace. VÒ lý thuyÕt, mçi ph­¬ng ph¸p x¸c ®Þnh biªn nµy th­êng tr¶i qua c¸c giai ®o¹n chÝnh sau: Lo¹i bá nhiÔu Chän to¸n tö thùc hiÖn. Chän ph­¬ng ph¸p x¸c ®Þnh ®iÓm biªn. Liªn kÕt c¸c ®iÓm biªn. Sau ®©y sÏ xÐt c¸c to¸n tö t×m biªn c¬ b¶n, ®Ó tõ ®ã thÊy r· h¬n c¸c b­íc thùc hiÖn trªn. 2.1. PhÐp to¸n Gradient. PhÐp to¸n Gradient lµ phÐp to¸n c¬ së cho tÊt c¶ c¸c phÐp läc tuyÕn tÝnh dïng ®Ó t×m biªn theo ph­¬ng ph¸p t×m biªn trùc tiÕp. §©y lµ phÐp to¸n lÊy ®¹o hµm bËc nhÊt trong kh«ng gian hai chiÒu, nã ®­îc ®Þnh nghÜa nh­ sau: (19) Trong ®ã : X lµ hµm ®é s¸ng cña hai biÕn liªn tôc x,y. C«ng thøc trªn ®©y ®­îc tÝnh mét c¸ch gÇn ®óng ®èi víi ¶nh sè, trong ®ã phÐp to¸n ®¹o hµm ®­îc tÝnh mét c¸ch gÇn ®óng b»ng phÐp to¸n sai ph©n nh­ sau: (20) (21) PhÐp to¸n Gradient ®èi víi ¶nh sè chÝnh lµ phÐp to¸n nh©n chËp ¶nh víi h¹t nh©n Dx, Dy : Ta cã thÓ tÝnh ®é lín Gradient bëi kÕt hîp ®¹o hµm theo hai h­íng: (22) dn Víi Gm, Gn lµ ®¹o hµm theo ph­¬ng m,n. Nh­ ®· nghiªn cøu trong to¸n häc, phÐp tÝnh ®¹o hµm cña ¶nh cho phÐp thÓ hiÖn sù biÕn ®æi lín vÒ ®é s¸ng cña ®iÓm ¶nh. Do ®ã, qua phÐp to¸n Gradient, c¸c ®iÓm biªn ®­îc lµm næi lªn. §©y lµ c¬ së ®Ó thùc hiÖn trong c¸c b­íc cña qu¸ tr×nh t×mtrªn ®èi víi ph­¬ng ph¸p t×mbiªn nµy lµ ®Þnh vÞ biªn. Cã thÓ ®Þnh vÞ biªn theo c¸c ph­¬ng ph¸p sau: Ph­¬ng ph¸p ng­ìng ®¬n gi¶n Ph­¬ng ph¸p nµy cho kÕt luËn ®iÓm biªn mét c¸ch ®¬n gi¶n bëi viÖc lÊy ng­ìng ®èi víi ®é lín Gradient: + NÕu N(m,n)>=T th× (m,n) lµ mét ®iÓm biªn. + NÕu N(m,n) < T th× (m,n) kh«ng ph¶i lµ mét ®iÓm biªn. trong ®ã T lµ ng­ìng. Ph­¬ng ph¸p x¸c ®Þnh gÇn ®óng cùc trÞ ®Þa ph­¬ng cña ®é lín Gradient. Ph­¬ng ph¸p nµy dùa trªn viÖc lùa chän cùc trÞ ®Þa ph­¬ng. Víi mçi ®iÓm M(m,n) cÇn xÐt, ta tÝnh Gradient t¹i M-G(M) vµ c¸c ®iÓm phô trong giíi h¹n kho¶ng c¸ch D. M lµ mét diÓm biªn khi G(M)>G(M1) vµ G(M)>G(M2) Trong ®ã M1, M2 lµ hai ®iÓm thuéc l©ncËn giíi h¹n trong kho¶ng c¸ch D Chän cùc trÞ ®Þa ph­¬ng theo hai møc ng­ìng: Ph­¬ng ph¸p nµy ®­a ra hai møc ng­ìng thÊp vµ cao T¹i mét diÓm M nµo ®ã, ta tÝnh Xl vµ Xh cña nã + Xl(M)=0 nÕu N(M)<Tl + Xl(M)=1 nÕu N(M)>=Tl + Xh(M)=0 nÕu N(M)<Th + Xh(M)=1 nÕu N(M)>=Th C¨n cø vµo Xl(M) vµ Xh(M) ®Ó chän cùc trÞ ®Þa ph­¬ng theo mét hoÆc nhiÒu h­íng. Tõ ®ã, t×m ®­îc ®iÓm biªn t­¬ng øng. TiÕp theo lµ b­íc liªn kÕt c¸c ®iÓm biªn l¹i ®Ó chóng ta thu ®­îc mét ®­êng biªn hoµn chØnh. §Ó ý ®Õn c¸c h¹t nh©n nh©n chËp Dx, Dy cho thÊy ®©y lµ mét tr­êng hîp ®Æc biÖt cña bé läc th«ng cao vµ phÐp to¸n Gradient trë thµnh mét phÐp läc tuyÕn tÝnhvíi bé läc th«ng cao t­¬ng øng cña nã. Më réng thªm ta cã c¸c bé läc th«ng cao dùa trªn c¬ së cña phÐp to¸n Gradient sau: Ngoµi c¸c kh¸i niÖm vÒ ®é lín Gradient theo h­íng x vµ y, ng­êi ta cßn ®­a ra kh¸i niÖm vÒ h­íng cña Gradient. H­íng Gradient lµ gãc ®­îc ®Þnh nghÜa bëi : Gradient_Direction(x,y)=tan-1{ Gm/Gn} (23). Trong ®ã Gm, Gn lµ ®é lín Gradient theo trôc x vµ y ®· nãi ë trªn. H­íng Gradient rÊt quan träng trong viÖc n©ng cao hiÖu qu¶ cña qu¸ tr×nh t×m biªn. §èi víi c¸c bµi to¸n t×m biªn lín, khi yªu cÇu t×m ra ®­êng biªn chÝnh x¸c vµ nhanh chãng, ng­êi ta th­êng xuÊt ph¸t tõ mét ®iÓm biªn ®· biÕt. C¨n cø vµo h­íng cña Gradient, cã thÓ t×m ra ®iÓm biªn tiÕp theo mét c¸ch nhanh chãng víi x¸c suÊt cao h¬n. Nh­ vËy, hiÖu qu¶ cña qu¸ tr×nh t×m biªn ®­îc t¨ng lªn. Sau ®©y lµ mét vÝ dô minh ho¹ cho ph­¬ng ph¸p t×m biªn dùa trªn phÐp to¸n Gradient nµy: ¶nh X_Direction Y_ Direction 0 0 0 0 0 0 2 0 3 3 0 0 0 1 0 0 0 2 4 2 0 0 2 0 3 4 3 3 2 3 -1 0 1 1 2 1 0 0 1 3 3 4 3 3 3 3 -2 0 2 0 0 0 0 1 0 4 3 3 2 4 3 2 -1 0 1 -1 -2 -1 0 0 1 2 3 3 4 4 4 3 C¸c mÉu xÕp chång trªn ®©y gäi lµ c¸c mÉu xÕp chång Sobel. Ph­¬ng ph¸p t×m biªn dùa trªn mÉu nµy gäi lµ ph­¬ng ph¸p t×m biªn Sobel. Tõ ¶nh trªn sau khi thùc hiÖn xÕp chång víi c¸c mÉu ®ã, ta ®­îc c¸c kÕt qu¶ thÓ hiÖn sù biÕn ®æi ®é s¸ng theo c¸c trôc x vµ y nh­ sau: A B 2 2 1 2 2 3 8 3 -2 -4 -5 -10 -12 -9 -6 -1 5 4 4 8 0 -1 2 0 -1 -4 -8 -12 -14 -11 -4 0 4 9 8 5 -1 -1 0 -2 0 -1 -6 -3 3 2 -2 -2 2 11 10 0 -1 2 2 5 1 1 2 2 1 -2 -4 -3 abs(A)+abs(B) 4 6 6 12 14 12 14 4 6 8 12 20 14 12 6 0 4 10 14 8 4 3 2 4 3 12 12 2 2 4 6 8 Sau ®ã tÝnh tæng gi¸ trÞ tuyÖt ®èi sù biÕn ®æi ®é s¸ng theo hai trôc t¹i c¸c ®iÓm ta cã: NÕu chän ng­ìng lµ 12 (theo ph­¬ng ph¸p ®¬n gi¶n ), ta sÏ ®­îc ¶nh ®Çu ra cã ®­êng biªn ®­îc x¸c ®Þnh. 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 Râ rµng, ¶nh kÕt qu¶ cuèi cïng ®· cho mét h×nh d¸ng c¬ b¶n vÒ biªn cña c¸c ®èi t­îng trong ¶nh gèc. 2.2. To¸n tö Laplace PhÐp to¸n Laplace dùa trªn viÖc tÝnh ®¹o hµm bËc hai cña ¶nh ®é s¸ng theo c¸c chiÒu, nã ®­îc thÓ hiÖn bëi c«ng thøc sau: (24) Còng t­¬ng tù nh­ phÐp tÝnh Gradient, ¸p dông c«ng thøc nµy ®èi víi ¶nh sè nh­ sau: (25) » [X(m+1,n)-2X(m,n)+X(m-1,n)]+ [X(m,n+1)-2X(m,n)+X(m,n-1)] Do ®ã: (26) C«ng thøc (26) chÝnh lµ phÐp nh©n chËp gi÷a ¶nh ®Çu vµo víi h¹t nh©n nh©n chËp PhÐp to¸n Laplace lµ phÐp to¸n tÝnh ®¹o hµm bËc hai, b¶n chÊt to¸n häc cña nã lµ thÓ hiÖn ®iÓm uèn cña hµm ®é s¸ng. B­íc ®Þnh vÞ biªn ®èi víi ph­¬ng ph¸p nµy ®­îc thùc hiÖn nh­ sau: T¹i mçi ®iÓm ¶nh tÝnh gi¸ trÞ L(M) b»ng L(X) t­¬ng øng X¸c ®Þnh ¶nh míi Xp(M) theo: Xp(M)=0 nÕu L(M)>=0 Xp(M)=1 nÕu L(M)<0 Cuèi cïng xÐt mét ¶nh XZ(M) nh­ sau: XZ(M)=1 nÕu Xp(M-1)=0 vµ Xp(M+1)=1 hoÆc ng­îc l¹i. XZ(M)=0 ®èi víi c¸c tr­êng hîp cßn l¹i. Trong ph­¬ng ph¸p nµy, qu¸ tr×nh ®Þnh vÞ biªn ®­îc thùc hiÖn trªn c¬ së xÐt sù qua zero cña to¸n tö Laplace. ¶nh XZ(M) sÏ cho kÕt qu¶ c¸c ®iÓm t­¬ng øng víi ®iÓm uèn. Nh­ vËy, c¸c ®iÓm biªn ®· ®­îc ®Þnh vÞ qua b­íc nµy. Trong thùc tÕ, cã nh÷ng bµi to¸n kh«ng ®ßi hái t×m ra vÞ trÝ chÝnh x¸c cña c¸c ®­êng biªn mµ chØ cÇn lµm næi lªn h×nh d¸ng cña ®­êng biªn ®ã. Trong nh÷ng tr­êng hîp nh­ vËy, cã thÓ kh«ng cÇn c¸c b­íc ®Þnh vÞ biªn n÷a. DÔ dµng nhËn thÊy to¸n tö Laplace chÝnh lµ bé läc th«ng cao víi h¹t nh©n cã tæng träng l­îng c¸c hÖ sè SK=0. PhÐp to¸n Laplace ®­îc tÝnh trªn c¬ së ®¹o hµm bËc hai, nã lµm t¨ng vµ næi râ h¬n sù biÕn ®æi ®é s¸ng t¹i c¸c ®iÓm biªn. §©y chÝnh lµ ­u ®iÓm lín trong viÖc t×m biªn. Ngoµi ra, ng­êi ta cßn më réng cho c¸c h¹t nh©n xÕp chång kh¸c nh­: HoÆcc 2.3 Mét sè ph­¬ng t×m biªn phi tuyÕn C¸c to¸n tö ®Ó t×m biªn ®· tr×nh bµy ë trªn lµ c¸c to¸n tö tuyÕn tÝnh tæng qu¸t. Víi mét ¶nh ®Çu vµo, qua to¸n të nµy, t¹o ¶nh ®Çu ra mµ mçi ®iÓm cña nã lµ tæ hîp tuyÕn tÝnh cña c¸c ®iÓm ®Çu vµo víi c¸c hÖ sè cña bé läc t­¬ng øng. Nh­ vËy kh«ng cã qu¸ tr×nh trung gian, so s¸nh, s¾p xÕp hay lùa chän ë ®©y. Trong thùc tÕ, cã thÓ ¸p dông mét sè ph­¬ng ph¸p t×m biªn phi tuyÕn, ®ã lµ c¸c ph­¬ng ph¸p cã sö dông c¸c phÐp to¸n s¾p xÕp, so s¸nh vµ lùa chän hay c¸c phÐp tÝnh ph©n chia phøc t¹p kh¸c. Trong phÇn nµy t«i sÏ giíi thiÖu mét sè kü thuËt c¬ b¶n theo ph­¬ng ph¸p nµy. 2.3.1. T×m biªn h×nh chãp ( Pyramid edge detection ). Th«ng th­êng, trong mét sè tr­êng hîp, ¶nh bao gåm nhiÒu c¸c ®­êng biªn trong ®ã cã ®­êng biªn dµi, cã ®­êng biªn ng¾n, cã ®­êng biªn hoÆc kh«ng. VÊn ®Ò ë ®©y cÇn lo¹i bá ®i mét sè biªn trong ¶nh kh«ng ®¸ng quan t©m l¾m ®èi víi ng­êi sö dông, ®ã lµ c¸c ®­êng biªn ng¾n, mê, vµ kh«ng ®­îc kÕt nèi víi nhau, trong khi cÇn ph¶i lµm næi ®­îc nh÷ng ®­êng biªn thùc sù, ®ã lµ nh÷ng ®­êng biªn ®Ëm vµ dµi. Mét gi¶i ph¸p ®ã lµ ph­¬ng ph¸p t×m biªn h×nh chãp. Ph­¬ng ph¸p nµy ®­îc thùc hiÖn nh­ sau: ¶nh gèc ®­îc chia thµnh bèn phÇn bëi chia ®«i ®é dµi mçi chiÒu. Mçi gi¸ trÞ ®iÓm ¶nh trong ¶nh nhá mét phÇn t­ míi lµ trung b×nh céng cña bèn ®iÓm ¶nh t­¬ng øng trong ¶nh gèc theo c«ng thøc sau: (27) Cø thÕ lÆp l¹i cho ®Õn khi ¶nh míi ®­îc t¹o ra, víi biªn thùc ®· ®­îc ph¸t hiÖn, c¸c biªn kh¸c ®· mÊt. Sau ®ã, sö dông mét ph­¬ng ph¸p t×m biªn ®èi víi ¶nh nhá nhÊt, t¹i c¸c ®iÓm biªn ®· ®­îc ph¸t hiÖn ®ã, l¹i sö dông ph­¬ng ph¸p t×m biªn ®èi víi bèn ®iÓm t­¬ng øng trong ¶nh lín h¬n. Qu¸ tr×ng cø tiÕp tôc nh­ thÕ cho ®Õn khi ®­îc ¶nh gèc víi ®­êng biªn thùc ®­îc t×m ra. Qu¸ tr×nh thùc hiÖn nµy sÏ lµm lê ®i nh÷ng ®­êng biªn ng¾n vµ mê, mµ chØ lµm næi lªn nh÷ng ®­êng biªn thùc. ThËt vËy, sau mçi b­íc t×m biªn tõ ¶nh nhá, chØ xÐt ®Õn c¸c ®iÓm t­¬ng øng víi nh÷ng ®iÓm ®· lµ biªn cña ¶nh nhá, mµ bá qua c¸c ®iÓm kh«ng ph¶i lµ biªn, mÆc dï nh÷ng ®iÓm nµy vÉn cã thÓ t¹o ra biªn ®èi víi bèn ®iÓm t­¬ng øng cña nã trong ¶nh lín. XÐt vÝ dô sau: ¶nh gèc Inew (chia 4) (B) nÕu chän ng­ìng lµ 1.5 ta cã biªn lµ: Biªn (B) Víi mçi ®iÓm biªn cña B, ta l¹i t×m biªn víi bèn ®iÓm t­¬ng øng cña nã trªn ¶nh gèc sÏ ®­îc biªn thùc (C) C(biªn thùc) * * 1 1 * * 1 0 1 1 1 1 1 0 1 1 2.3.2. To¸n tö t×m biªn Kirsch To¸n tö nµy ®­îc x©y dùng trªn c¬ së cöa sæ cã trung t©m (3´3,5´5,...). Trong tr­êng hîp cöa sæ 3´3, nã cã thÓ ®­îc m« t¶ ng¾n gän nh­ sau: Mçi ®iÓm ¶nh ®Çu ra lµ gi¸ trÞ lín nhÊt trong t¸m kÕt qu¶ xÕp chång cña cöa sæ (a) d­íi ®©y víi ma trËn ¶nh. Sau mçi lÇn xÕp chång, ta quay cöa sæ läc nµy ®i mét gãc 450 vµ lÊy lµm cöa sæ xÕp ch«ng cho lÇn sau. LÇn mét, dïng cöa sæ xÕp chång sau: (a) (a) LÇn hai, quay cöa sæ ®i mét gãc 450 thu ®­îc: (b) ... LÇn thø t¸m, sau khi quay (a) ®i mét gãc 3150 lµ: (c) Gi¸ trÞ lín nhÊt trong t¸m lÇn xÕp chång t­¬ng øng víi ®iÓm ¶nh vµo ®ã, sÏ cho kÕt qu¶ ®iÓm ¶nh ®Çu ra. M« t¶ b»ng to¸n häc, nã t­¬ng øng víi : (28) ë ®©y , phÐp to¸n a b ®­îc ®Þnh nghÜa lµ phÇn d­ cña phÐp chia (a+b ) cho 8 vµ F(j) lµ trÞ sè cña phÇn d­ thø j cña cöa sæ läc. Thø tù cña c¸c phÇn tö cña cöa sæ läc theo chiÒu (hoÆc ng­îc chiÒu ) kim ®ång hå, riªng phÇn tö thø 9 lµ phÇn tö trung t©m cña cöa sæ. 2.3.3. T×m biªn b»ng phÐp to¸n h×nh th¸i. (Morphological edge operator) PhÐp to¸n nµy thùc hiÖn trªn c¬ së ¶nh ban ®Çu ®· ®­îc lµm tr¬n b»ng phÐp läc trung vÞ. Gi¶ sö P lµ mét ®iÓm cña ¶nh ®· ®­îc lµm tr¬n, tÝnh hai ®é lÖch cña ®iÓm ®ã víi c¸c gi¸ trÞ lín nhÊt vµ nhá nhÊt cña cöa sæ xung quanh P (cöa sæ 3´3). Gi¸ trÞ nhá h¬n trong hai gi¸ trÞ ®ã sÏ ®­îc chän lµm gi¸ trÞ ®iÓm ¶nh ®Çu ra. Qu¸ tr×nh nµy sÏ ®­îc m« t¶ mh­ sau: (28) Gi¶ sö ¶nh gèc I(m,n) ®­îc lµm tr¬n b»ng bé läc trung b×nh t¹o ra ¶nh O1(m,n): W(m,n) lµ cöa sæ cña (m,n) nhËn ®iÓm nµy lµm trung t©m (phÐp xÕp chång t¹i trung t©m ) ®­îc chän thÝch hîp. Nw lµ sè ®iÓm cña cöa sæ nµy. Mét ®iÓm ¶nh ®Çu ra O2 (m,n) ®­îc tÝnh tõ ¶nh O1(m,n) th«ng qua phÐp so s¸nh vµ lùa chän bëi: (29) Trong ®ã F(m,n) lµ cöa sæ l©n cËn cña ®iÓm (m,n) còng ®­îc chän thÝch hîp Nh­ vËy, ®©y còng lµ phÐp to¸n phi tuyÕn. C¸c ®iÓm biªn ®­îc lµm næi lªn, nhê phÐp so s¸nh, chän ra ®é sai kh¸c nhá nhÊt gi÷a nã vµ gi¸ trÞ ®é s¸ng cña c¸c ®iÓm ¶nh thuéc l©n cËn. Sai kh¸c nµy cµng lín th× ®iÓm biªn cµng ®­îc lµm næi. 13.Hîp t¸c quèc tÕ: 14.TiÕn ®é thùc hiÖn ®Ò tµi. STT Néi dung c«ng viÖc S¶n phÈm ph¶i ®¹t ®­îc Thêi gian (B§-KT) Ng­êi,c¬ quan thùc hiÖn. 1 X©y dùng ®Ò c­¬ng nghiªn cøu tæng qu¸t. B¶n ®Ò c­¬ng. 01 Thaùng Ban ®Ò tµi 2 Thu thËp tµi liÖu kh¶o s¸t thùc tÕ B¶n th¶o vÒ c¸c c¬ së lý luËn. 05 Thaùng Ban ®Ò tµi 3 §¨ng ký víi bé m«n b¾t ®Çu tiÕn hµnh lµm. -PhiÕu ®¨ng ký ®Ò tµi. -B¶n thuyÕt minh ®Ò tµi. 01 ngµy Chñ nhiÖm ®Ò tµi 4 So¹n ®Ò c­¬ng chi tiÕt B¶n ®Ò c­¬ng ch