Luận án tiến sỹ " Một số vấn đề tối ưu hóa và nâng cao hiệu quả trong xử lý thông tin hình ảnh "

Chia sẻ: Nguyen Nhi | Ngày: | Loại File: PDF | Số trang:28

Thêm vào BST

Báo xấu

242
lượt xem 60
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo Luận án tiến sỹ toán học " Một sốc vấn đề tối ưu hóa và nâng cao hiệu quả trong xử lý thông tin hình ảnh " chuyên ngành bảo đảm toán học cho máy tính và hệ thống tính toán.Thông tin (inform) có nghĩa là thông báo tin tức. Nên dùng như động từ, không nên dùng như danh từ. Tin tức có thể dùng như danh từ chẳng hạn: tin tức về máy móc, điện toán, hay nói gọn là tin về ... Ngày nay, thuật ngữ thu thập tin tức được sử dụng...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án tiến sỹ " Một số vấn đề tối ưu hóa và nâng cao hiệu quả trong xử lý thông tin hình ảnh "

£)~I HOC QU6C GIA TP. HO CHI MINH TRUONG D~I HOC KHOA HOC TV NHIEN * _uuu__u* *_u uu DU'dNG ANH DUC MOT SO VAN DE TOllJU HoA vA. ~ ~? NANG CAD HII;U QUA ? I' TRONG xU' LY ~ ,? THONG TIN HINH ANH Chuyen nganh: Bao dam toaD hcho may tinh c va M th6ng tinh toaD Ma s(f: 01.01.10 TOM TAT LU~N AN TIEN STTOAN HOC Tp.Ho Chi Minh, 2002
~,liD! 5f~ UJj Cong trlnhduQc hoan thanh t~i~.. Truong D;;tihQc Khoa hQc TV Nhien, D;;tihQc Qu6c Gia Tp. H6 Chi Minh. NguOi huang diin khoa hQc: 1. GS.TS Bili Doan Khanh D;;tihQc Paris VI, CQngboa Phap 2. GS.TSKH Hoang Van KiGm Truong D;;tihQc KHTN, DHQG Tp.HCM Phh bj~n 1: Phh bi9n 2: Phh bi~n 3: Lu~n an se duQc baa v
Mi'ldtlu Chlldng1 1.1. yeu CUllthrjc tt va Ii do thrjc hifll di tlli Co 'the noi, ngay nay vi~c xay d\l'ng va quail Iy cac h~ th6ng thong tin hlnh anh mQt cach hi~u qua la mQt nhu du buc thie't. Truoc he't, cac M thong nay d€u chua d\fng mQt h.tQngthong tin nit Ion. Khai thac hi~u qua cac thong tin lo~i nay se mang I~i nhii'ng IQi ich khong the ch6i ciii. Trong y hQc, cac thong tin v€ con nguoi, ban d6 gen, cac lo~i b~nh kern theo nhii'ng hlnh iinh C\l the, duQCt6 chuc va lu'u trii' hQp Iy se giup nganh nay khai thac t6t nh:it cac k€t qua nghien CUll cua mlnh ph\lc v\l cho baa vf; suc khoe cua con nguoi. Vif;c t~o ra kha Dang th\fc hi~n ca m6 ao la mQt vi d\l. Trong cac nganh cong nghi~p thie't ke' ch€ t~o may, thie't bi, ...,cac mo hlnh thi€t ke' duQc t~o I~p lu'u trii'va xli Iy trong may tinh giup giam chi phi ch€ t~o, thli nghif;m, ... Voi s\f giup do cua cac hf; th6ng thong tin dja Iy (GIS), vi~c qUail Iy nha nuoc se hif;u qua hdn. Kinh nghi~m cua cac nuoc phat trieD the hi~n r6 di€u nay. Cac v:in d€ lien quail dEn cac thong tin hlnh anh da duQc r:it nhi€u nha khoa hQc y nghla quail tam nghien cUu VI t~m quail trQng cling nhu khoa hQc ciia no. Tuy v~y, con r5t nhi~u v5n d~ m0 dn phiii nghiCn CUlllrong Iiinh vt.1'c nay. ViGc lOi u'u de tang tinh hif;u qua cua cac h~ th6ng thong tin trong lu'u trii', xii'Iy va baa m~t la r:it dang quail tam. 90 la Iy do de th\fc hif;n d€ tai nay. 1.2. M{lc lieu di tlLi Voi cac nhu du th\l'c ti€n (j tren, d€ tai nay duQcxay d\l'ng dE gap mQtph~n vao vi~c Dang cao kha nail ung d\lng cua cac M th6ng thong tin hlnh anh. Chung toi se huang cac nghien' , .mlph vao mQtso' bai loan t6i u'uC\lthe. Do cac hi; lh6ng thong tin hlnh anh rii'tda d~ng, chung toi khong th~ khao sat h€t cac vii'n de lien quail. Trong khuon kh6 cua lu~n an nay, chung toi t~p trung vao cac nghien cUu lien quail de'n cac thong tin hlnh anh d
T[JoIljp va bill tril dillifU anh vector Chtld45 2. Trang khuon kh6 lu?n an nay, chUng toi sf!:chi ban d€n cae dcr li~u hlnh anh d
~ Node thl!C' CltC clint! co th6 giao 1)(\ (hi tl~, node liGn t6ng qUilt ket va nhau. I I ClIng. T~p h nguyen trong khoang [0,255] . Djnh gia trj ciia kieh thu'oc bucket: la s61u'Qng t6i da cae d6i tWng n~m trang 1 cell (d~ nghj: bucket = 8) 3
. Cell ban d~u Ja hlnh vuong 256x256 (0..255) . N€u cell co s61uQng cac d6i tuQng vuQt qua bucket thl cell duQc ti€p t\lc chia ra . T6 chlic cac cell t~o duQc thanh cay nhj phan tlm ki€m VOlm6i a la mQt node tren diy, hat nhanh trai phili Luongling VOldc cell thuQc ph~n bell trai hoi!.c phili (tren hoi!.cduoi) cua cell dang xet. 2.2. Tfl-Odel /i{}u anh veCtor 2.2.1. Vector hod anh bitmap Thu~t loan vector hoa ilnh g(')mcac buoc chinh sau: Blidc 1: Lam manh dlliJng bi~n Blidc 2: EJanh dau GaG glaD diem va GaG diem dau mut. Blidc 3: Vector hoa 2.2.1.1. Lam manh dUang bien va danh dilu dc giao die'm Trang cang trlnh cua minh, chung tai dii dtfa tren thu~n loan Zhang - Suen de' giiii quy€t bat loan cua mlnh. Ly do chQn thu~t loan nay la no rilt thu~n ti~n cho vi~c ti~n xii"Iy cac thong tin co ich lien quail d€n ca'u truc topo. Hon Qua, qua phan rich ky thu~t loan, trang qua trlnh lam milnh, ta co the' k€t hQp vii,:c chinh da'u dc diem co ti~m niing la node sau nay, dIng nhuciii thi~n dang k6 k€l quit cua thu~t loan g6c. 2.2.1.2. Vector hoa ThuJjt toan 2.1: Blidc 1: ChonmOtnode(dau mut hay glaDdiem) chlla xuII'P,. Blidc2: Lan rheaGaG diem bi~n,ghj nh~nI~i VaGdanh sach L cho den khi g~p nodeP2khac. Blidc 3: Chondllong P'P2lam dlliJnggia dinh ban dau. Blidc 4: Xacdinha vadiemxanhatM. BlIlfc 5: Neu a < Echon P'P2jam ket qua. NgllQC chia P'P2lam hai phan P,Mva MP2. uII'P,Mva MP2nhll dii lam vol P,P2. X I~i BlIlfc 6: Ghi nh~nGaGthOngtin tapa d1nhc~nh. Blilfc 7: Neucon nodechlla xu iy thi quayI~i BlioC1. Nh~n xet: Thu~t loan 2.1 se ho~t dQilgrilt t6t n€u cac duang tren anh can vector hoa kh6ng qua phlic t~p. Tuy nhien, trong truang hQp t6ng quat, thu~t loan nay kh6ng cho k€t qua chinh xac. ThuJjt toan 2.2: BlIlfc 1: ChonmOtnode(dau mut hay giaodiem) chllaxuII'P,. Blilfc 2: Ghinh~n P, la nodedang xet. i = O. LIiUP, VaGL[i++J. 3: Chon la diembi~nkeP, chlla xe!. M Blilfc Neuchon dllQc thi danh ctauM dii xe!. P = M. NgllQc I~i: chuyen sang BlIiJc8. Blilfc 4: Chon P2 la diem ke P. 4
5: NA'u P,la mOt ode n tht Bltcfe L[I++] = P,. LIfUL vao file kA'tqua. C~pnl1~tcae thOngtin topo dlnh - e~nhIIAnquan. Quay'~I Bltae2. 6: Neud(M,P,P,)< dIP,P,P,)thl M = P;//C~pnh~tM M luOn diemxado~n la P,P,nha:t. Bltcfe Bltde 7: NeukhoangeachdIM, P,P,) > € thl: L[i++] = M; P, = M; M = P; P = P,. Quay'~i Bltae 4. Blide 8: Neueon nodeehltaXlIIy thl quayI~i Billie 1. Tim phiin giao cua hai da gitic biftky 2.2.2. Trudc lien, ta hay th6ng nh5t m(Jtso' thu~t ngu [39], [41]: . M(Jt loop bit3u di6n bien cua m(Jt da giac bao g6m m(Jt chu6i cac qnh da giac djnh hudng khep kin. M6i da giac co dung m(Jt loop. . M(Jt ring bit3u di€n mQt 16 trong da gik Co tht3 co nhi€u 16 ho~c khong co 16 nao trang mQt da giac. Cac ring co tht316ngnhau bao nhieu c5p tuy y. . M(Jtsweepline 1a duong th~ng song song vdi trl]c tung. . M(Jtscanline la duong th~ng song song vdi tfIJChoanh. 2.2.2.1. So luQc v€ thu?t loan y Thu?t loan cua chung toi dl!a tn~n tudng ban diiu cua thu?t loan Weiler- Atherton. Thu?t loan nay xac dinh phiin giao hai da giac khong tl! dt b5t ky bao g6m 3 budc chinh [30]: 1. TIm cae giao di€m giua cae qnh eua 2 da giae. MQt thu?t loan ling dl]ng sweep line dfi duQe chung toi xay dl!ng d€ thl!e hi~n eong vi~e nay.. 2. Sau khi dfi xac djnh duQe cae giao dit3m, m(Jt so' thong tin "!win chuyin" be) sung se duQe them vao cae giao di€m d€ phl]e VI] eho bude eu6i eua thu?t loan. 3. Trang phh eu6i, thu?t loan dl!a tren cae dli li~u cling c5p bCiihai bude trude va xay dl!ng da giae giao b~ng caeh "bllftc" luan phien qua l
Phep biendili Radon & Hough trong xa.c dinh 3 Chtldll8 doL tll(/Ilg tren dnll Do d~c di€m cua chuyen nganh hyp cua mInh, chung toi se thi t~p trung vao mQt phin cua phep bie'n d6i Radon lien quail Mn vit;c xac dint cac d6i tuQng d
3.2. Phep bitll dtfi Radoll ehufill 3.2.1.1'IIep hie;, ddi Radoll (p, OJclla d,lullg tl"lllg MOt trang nhang l g(x,y) g(p,O)=[o(p * -(pros 0 - s sin O)cos 0 * -(psin 0 + scos O)sin 0 *)is = [o(p*-pcos(O-O*)+ssin(O-O*))is . 1 (3.4) p*-pcos(O-O*) ( } =[-~ I' (0-0* S111 S111-0* ) . (0 ~o +s s,neus111(0-0*)",,0 1 -lsin(O-O*~ va nEu e = e', nghia la since - e') = 0, ta se c6: o - nriu p* "" p [-~ o(p*-p)is ={ f-~u (3.1) g(x,y)= [[g(x*.y*)o(r- y*+px*)ix*dy* Ta c6 th6 xem phcp biEn d6i Hough lien tvc la mQt tru'ang hQp d~c bi~t cua phep biEn d6i Radon. Tuy nhien, d d~ng roi r~c n6i chung hai phep biEn d6i khac nhau. Cltn hm y r~ng phep biEn d6i Hough I~i thuang du'QC dvng d d~ng sa roi r~c.
TiYbi6u thuc (3.1) c6 th6 dua ra mQtthu~ttoan xiiy dt!ng kh6ng gian tham 56 roi r
Khong ian anh Khong gian tham 56 Tham s
dU
(4-6) X=Xm =Xmm +m~,m=O,I,...,M-I (4-7) Y=Y"=Y",;o+l1~y,I1=O,I,...,N-1 Thay bien thue (4.9), (4.11) va (4.12) vao phuong trlnh duong eong du
( ) ( ) =O a/PM=O (M N),ftJI (4-11) MIT JI °ORT ,., /.1 trang d6 (MN), chI ra ding chI mOt 56 gidi h~n cac diEm anh (cac gia tri khac 0) la du
y t\tong I(y m~u th\ta va khii nang bo qua cac vung iinh c6 gia tri O. San day la chinh cua thu~t toan: 1. Xfiy dl!ng khong gian tham s6 rCiir~c, nghia la chQn qi,min, va Liqj. Ji 2. Xay dl!ng khong gian tham s6 rut gQncho IMP biing cach chQn: (4-12) = !2V:'+ 11- = (2V"i J;= ';;nnn + I) b.';i + V"i b.';" b.';; ~nUn rxlky hi~u trong d6 s6 tr~n eila x (s6 nguyen nhiS nhilt IOn hdn x) va V,,/]a mQt . s6 nguyen lien quail Mn qua tdnh tai ]ily m~u (xem bell du'
troll, trtI'octieD ta lu'u 9 la vol mQtdiem ba'tky P Be xac djnh tam ciia cac du'Clng ireD du'Clngiron, du'Clngvuong goc vol ti6p tuy6n cua du'Clngiron tq.i diEm P di qua tam (xem Hlnh 4.2). Nhu' v~y,voi mQt 56 diem ireD du'Clngtron, cac du'Clng vuong goc vol ti6p tuy6n di qua nhii'ng diem nay se d6ng qui tq.itam cua no. Vol m6i diem ilnh, b~ng phu'ong phap b1nh phuong t6i thieu, ta co the xac djnh duqc dltClngtiSp tuySn phil hqp nha't di qua diem nay d1,1'a cac diem ilnh n~m vao trong Hinc~n ciia diem nay. IDnh 4.2. Cach xac dinh Him dLii'fngtron Sail khi xac djnh duqc ta't cii.cac vj tri co the la tam cua mQt hay nhi~u duClng iron ta phili xac djnh ban kinh cua cac vong iron tuong ling. Vol m6i tam ta xiiy dlfng 1 histogram nhu' sail: vol m6i diem ilnh ta tinh khoilng dch d6n tam va lu'U no vao histogram tuong ling. Gia trj clfc dq.i cua histogram se cho ta gia tri cua ban kinh vong tron dn t1m. -@B ITmh4.3. Cae xac dinh tam qua cae dLiilngtrung tn/e Sail kill xac djnh xong ta phili lam them mQt bu'oc Mu xii' 19 de tal khhg dinh dc vong iron dii phat hi~n duqc b~ng each Mm sO'diem n~m ireD du'ClngtrOll. Chia s6 diem nay cho ban kinh tuong ling ta nMn du'QcmQt gia trio NSu gia trj nay nha hon mQt ngu'ong nao d6 vong troll se bj buy. Rieng 0 buoc xac dinh tam duClngiron, ngoai thu~t loan dii tr1nh bay 0 ireD, chung toi con di d~t mQt thu~t loan dlfa tren mQt tinh cha't khac cua dttClngtrOll. (xem Hlnh 4.3) BE tang t6c dQ tinh loan, ta c6 the si\' d1,1ngphcp biSn dai Hough ng5u nhi6n (Randomized Hough Transform - RHT). 14
4.7. Xac djllh cae doLtll(lllg d{l1lg Ellipse 4.7.1. 1'111/(11 loall/(tlllIollgh MQt ellipse hoan roan duQe xae dinh bCii5 tham s6 (tCladQ tam, 2 ban kinh va g6e quay so VOltl1Jehoanh - Hlnh 4.4). Tuong tv nhu caeh xae dinh cae duang troll dil trlnh bay d tren, vi~e xae dinh cae ellipse duQe ehia ra lam 2 giai do
\ ,., i ;, ! /~':"::;'-\i(:'-~tr,\ ,..., ; , /"\ . '\ i \ \' /. " \, """f- --,' " ".,../\ / ,/' , \ Anh vUi mQt slJ ellipse Cae ellipse xac djnh dri(jc Irmh 4,6, MQt slJ k€t qua thtjc hi~n thu4t loan ......... - i"'. a, Anh mil ung thri h, Anh sau phfin ngriilng ' -' / '-"'. '--~/ r- cO ) ) ~ )\ .,,/'" : "".~ -- ~- ./ " ,. c, Anh sau loc hi/!n d, Cae ellipse Hm dri(jc Irmh 4.7. K€t qua ung d\mg thu4t loan xae djnh mil ung thri Nhtt dii philo tich CItrong cac chttcJngtruoc, phep bie'n d6i Hough va Radon c6 quail h~ m~t thie't voi nhau. TiJy da li~u dn xU'ly va nhu du thlfc te', ta c6 th€ de dang hit$u chlnh thu~t loan tren d€ dung phep bie'n d6i Radon thay cho Hough, Cha't lu
a~ NE u LU NE L RD (0) Ibl mnh 4.8. (a) Trinh bay sf! pMn IcJpcae di/fm bien eua mOt dol tu'!Jng (b) SlcJp eua cae dit'm bien Ian eijn 4 eua di/fm P VA,(-X"-Y2) HA(x\,YJ E VA(x..Yt) mnb 4.9. Ala dit'm bien eua do'! tu'
Djnh nghia 4.3: Cho A(x., y.) Ia