Tài liệu Luận văn nghiên cứu phương pháp nhận dạng hình dạng

Bé gi¸o dôc vµ ®µo t¹o Tr−êng ®¹i häc b¸ch khoa Hµ néi --------------------------------------------- LuËn v¨n th¹c sÜ khoa häc Nghiªn cøu ph−¬ng ph¸p nhËn d¹ng h×nh d¹ng Ngµnh: xö lý th«ng tin vµ truyÒn th«ng M∙ sè: 421 ®inh thÞ kim ph−îng Ng−êi h−íng dÉn khoa häc: T.S. NguyÔn kim anh Hµ néi 2006 -2- Lêi cam ®oan T«i xin cam ®oan b¶n luËn v¨n nµy lµ kÕt qu¶ nghiªn cøu cña b¶n th©n d−íi sù h−íng dÉn cña TS. NguyÔn Kim Anh. NÕu cã g× sai ph¹m, t«i xin hoµn toµn chÞu tr¸ch nhiÖm. Ng−êi lµm cam ®oan §inh ThÞ Kim Ph−îng -3- Môc Lôc Lêi cam ®oan .......................................................................................................... 2 Môc Lôc ................................................................................................................. 3 Danh Môc C¸c tõ viÕt t¾t........................................................................................ 6 Danh môc h×nh vÏ................................................................................................... 7 Lêi nãi ®Çu ............................................................................................................. 9 Ch−¬ng 1:Tæng quan vÒ t×m kiÕm ¶nh dùa trªn h×nh d¹ng .Error! Bookmark not defined. 1.1. Giíi thiÖu...................................................................................................12 1.2. TrÝch chän ®Æc tr−ng..................................................................................13 1.2.1.BiÕn ®æi Fourier...................................................................................12 1.2.1.1.Chuçi Fourier....................................................................................13 1.2.1.2. Sù héi tô cña chuçi Fourier..............................................................14 1.2.1.3. BiÕn ®æi Fourier...............................................................................14 1.2.1.4. BiÕn ®æi Fourier rêi r¹c ...................................................................15 1.2.1.5. BiÕn ®æi Fourier hai chiÒu ...............................................................16 1.2.1.6. Ph¹m vi cña biÕn ®æi Fourier...........................................................16 1.2.2. Kh«ng gian ®é chia (Scale space).......................................................17 1.2.2.1. C¬ së ................................................................................................17 1.2.2.2. Kh«ng gian ®é chia Gaussian..........................................................19 1.2.2.3. Ph¹m vi cña sù kh«ng t¹o c¸c ®Æc tr−ng míi ..................................19 1.2.2.4. Kh«ng gian ®é chia m©u thuÉn víi viÖc ®a quyÕt ®Þnh ...................20 1.2.3.Th¶o luËn .............................................................................................22 1.3. PhÐp ®o t−¬ng ®−¬ng vµ thùc hiÖn phÐp ®o...............................................22 1.3.1. PhÐp ®o sù gièng nhau........................................................................23 1.3.1.1. Kh«ng gian phÐp ®o kho¶ng c¸ch (Distance Metric Spaces) .........24 1.3.1.2. Kho¶ng c¸ch d¹ng Minkowski ........................................................24 1.3.1.3. Kho¶ng c¸ch Cosin..........................................................................24 1.3.1.4. Th«ng tin thèng kª χ ...................................................................25 1.3.1.5. §−êng giao biÓu ®å .........................................................................25 2 -4- 1.3.1.6. Kho¶ng c¸ch bËc hai........................................................................26 1.3.1.7. Kho¶ng c¸ch Mahalanobis ..............................................................27 1.3.2.Thùc hiÖn phÐp ®o ...............................................................................27 1.3.2.1. §é nh¹y vµ ®é chÝnh x¸c(RPP). ......................................................28 1.3.2.2. Tû lÖ träng sè thµnh c«ng (PWH- Percentage of Weighted Hits) ...28 1.3.2.3. PhÇn tr¨m cña thø bËc gièng nhau (PSR-Percentage of Similarity Ranking ) ......................................................................................................29 1.3.2.4. Th¶o luËn .........................................................................................30 1.3.3. TrÝch chän ®Æc tr−ng h×nh d¹ng..........................................................30 1.4. Th¶o luËn...................................................................................................32 Ch−¬ng 2 Ph−¬ng ph¸p t¸ch contrario .................................................................33 2.1. Cluster cã thø bËc vµ ®¸nh gi¸ gi¸ trÞ........................................................34 2.1.1.Gi¸ trÞ nhãm Contrario ........................................................................34 2.1.1.1. C¬ së:...............................................................................................34 2.1.1.2. Nhãm cã ý nghÜa. ............................................................................35 2.1.2. Tiªu chuÈn kÕt hîp tèt nhÊt. ...............................................................37 2.1.3. VÊn ®Ò tÝnh to¸n .................................................................................40 2.1.3.1. Lùa chän vïng thö. ..........................................................................40 2.1.3.2. Riªng rÏ vµ cùc ®¹i. .........................................................................42 2.2.1. NhiÔu ®iÓm .........................................................................................43 2.2.2. Ph©n ®o¹n ...........................................................................................43 2.3. KÕt cÊu nhãm vµ kh«ng gian t−¬ng øng....................................................46 2.3.1. T¹i sao ph¶i t¸ch kÕt cÊu kh«ng gian. ................................................46 2.3.2. §èi s¸nh nh©n tè h×nh d¹ng................................................................47 2.3.3. BiÕn ®æi m« t¶.....................................................................................49 2.3.3.1. Tr−êng hîp t−¬ng ®ång ...................................................................49 2.3.3.2. Tr−êng hîp biÕn ®æi mèi quan hÖ ...................................................50 2.3.4. Cluster cã ý nghÜa cña biÕn ®æi ..........................................................52 2.3.4.1. PhÐp ®o sù kh«ng t−¬ng ®−¬ng gi÷a c¸c biÕn ®æi. ..........................52 2.3.4.2 Ph−¬ng thøc nÒn ...............................................................................52 2.3.4.3. Kü thuËt nhãm .................................................................................54 2.4. Th¶o luËn...................................................................................................55 Ch−¬ng 3:Ph−¬ng ph¸p ra quyÕt ®Þnh Contrario..................................................56 3.1. Mét quyÕt ®Þnh Contrario ......................................................................58 3.1.1. Ph−¬ng ph¸p h×nh d¹ng tr¸i ng−îc ph−¬ng ph¸p nÒn ........................58 3.1.2. Ph−¬ng thøc quyÕt ®Þnh Contrario......................................................59 3.1.3. ¦íc l−îng x¸c suÊt c¶nh b¸o sai ........................................................61 -5- 3.1.4. LuËt ra quyÕt ®Þnh Contrario ..............................................................61 3.2. Tù ®éng thiÕt lËp ng−ìng kho¶ng c¸ch .................................................62 3.2.1. Sè c¸c c¶nh b¸o sai NFA ....................................................................62 3.2.2. §èi s¸nh cã ý nghÜa ............................................................................63 3.2.3. Ng−ìng nhËn d¹ng t−¬ng øng víi ng÷ c¶nh.......................................64 3.2.4. T¹i sao quyÕt ®Þnh Contrario ..............................................................65 3.3. X©y dùng ®Æc tr−ng ®éc lËp thèng kª....................................................66 3.4.ChuÈn hãa nh©n tè h×nh d¹ng tõ ¶nh cho ®Æc tr−ng ®éc lËp...................68 3.4.1. BiÓu diÔn h×nh d¹ng b»ng c¸c møc ®−êng..........................................68 3.4.2.Tiªu chuÈn hãa vµ m· hãa b¸n côc bé.................................................70 3.4.2.1. M· hãa / Tiªu chuÈn hãa trÞ kh«ng ®æi t−¬ng ®−¬ng ......................71 3.4.2.2. M· hãa / ChuÈn hãa quan hÖ bÊt biÕn .............................................73 3.4.3. Tõ chuÈn hãa nh©n tè h×nh d¹ng ®Õn ®Æc tr−ng ®éc lËp.....................73 3.5. Th¶o luËn ...............................................................................................76 Ch−¬ng 4Thö nghiÖm ...........................................................................................78 4.1. Thö nghiÖm ph−¬ng ph¸p nÒn...................................................................78 4.2. Thö nghiÖm ph−¬ng ph¸p Contrario..........................................................80 4.2.1. Hai ¶nh kh«ng quan hÖ víi nhau ........................................................80 4.2.2. MÐo d¹ng quan s¸t xa gÇn ..................................................................81 4.2.3. Quan hÖ víi sù nghÏn côc bé vµ thay ®æi ®é t−¬ng ph¶n...................83 KÕt luËn ................................................................................................................88 Tµi liÖu tham kh¶o................................................................................................89 Tãm t¾t luËn v¨n...................................................................................................90 -6- Danh Môc C¸c tõ viÕt t¾t STT Tõ viÕt t¾t ý nghÜa 1 CBIR Content Based Image Retrieval 2 FD Fourie Descriptor 3 FFT Fast Fourie Transform 4 CSDL C¬ së d÷ liÖu 5 NFA Number of Fasle Alarm 6 PFA Pridicion Fasle Alarm 7 FT Fourie Transform 8 NFAg NFA of region 9 NFAgg NFA of region-region 10 Pro Proposition 11 PFA Probability of False Alarm -7- Danh môc h×nh vÏ H×nh 1.1: §èi t−îng bÞ lµm nhiÔu bëi biÕn ®æi phæ. ............................................13 H×nh 1.2: ¶nh vµ c¸c biÕn ®æi kh¸c .....................................................................13 H×nh 1.3: §iÓm qua 0 t¹i vÞ trÝ x vµ ®é chia t cña tÝn hiÖu ...................................20 H×nh 1.4: (a) Kho¶ng c¸ch Ocolit, .......................................................................25 (b) kho¶ng c¸ch Cosin, (c) kho¶ng c¸ch L1.........................................................25 H×nh 1:a) ¶nh ký tù,b) møc ®−êng t−¬ng øng, c) §o¹n møc ®−êng ...................31 H×nh 2.2: Nhãm d÷ liÖu 950 ®iÓm ®ång d¹ng......................................................37 H×nh 2.5: VÊn ®Ò quan träng cña ph©n bè ph−¬ng thøc nÒn................................43 H×nh 2.6: Ph©n ®o¹n ¶nh ®· scan vµ 71 ®−êng møc cã møc ý nghÜa cùc ®¹i. .....44 H×nh 2.7: Nhãm víi mèi quan hÖ tíi h−íng.........................................................45 H×nh 2.8: Nhãm trong kh«ng gian(to¹ ®é x, h−íng)............................................46 H×nh 2.9: Thö nghiÖm Guernica...........................................................................48 H×nh 2.10: Thö nghiÖm “ Guernica “ quan hÖ t−¬ng øng ý nghÜa kh«ng ®æi ......49 H×nh 2.11: Hai ®o¹n møc ®−êng vµ khung t−¬ng øng .........................................50 H×nh 2.12: Thö nghiÖm “ Guernica “ ...................................................................51 H×nh 3.1: TrÝch chän møc ®−êng cã ý nghÜa.......................................................70 H×nh 3.3: M· ho¸ sù kh«ng ®æi t−¬ng ®−¬ng b¸n côc bé ....................................73 H×nh 3.4 : M· hãa b¸n côc bé mèi quan hÖ kh«ng ®æi. . .....................................74 H×nh 3.5 : M· hãa h×nh d¹ng b¸n côc bé quan hÖ bÊt biÕn..................................75 -8- H×nh 3.6: M· ho¸ sù t−¬ng ®ång kh«ng ®æi.........................................................76 H×nh 4.1: ¶nh vµ møc ®−êng cã ý nghÜa .............................................................80 H×nh 4.2: Thö nghiÖm hitchcook..........................................................................82 H×nh 4.3: Ph−¬ng ph¸p nhËn d¹ng b¸n côc bé quan hÖ kh«ng ®æi......................83 H×nh 4.4: Ph−¬ng ph¸p nhËn d¹ng quan hÖ b¸n côc bé kh«ng ®æi......................83 H×nh 4.5 Ph−¬ng ph¸p nhËn d¹ng b¸n côc bé .....................................................84 H×nh 4.6: TËp c¸c ®o¹n ®−êng møc ®èi s¸nh víi ¶nh trong CSDL......................85 H×nh 4.7: Ph−¬ng ph¸p b¸n côc bé t−¬ng ®ång kh«ng ®æi ..................................85 H×nh 4.8: ¶nh gèc vµ møc ®−êng cã ý nghÜa.......................................................86 H×nh 4.9: ¶nh Menima vµ møc ®−êng cã ý nghÜa ...............................................86 -9- Lêi nãi ®Çu Ngµy nay th«ng tin nãi chung sö dông trong ¶nh lµ phæ biÕn. RÊt nhiÒu lÜnh vùc sö dông ¶nh nh− mét c«ng cô ®Ó thùc hiÖn c«ng viÖc. Nh÷ng n¨m gÇn ®©y, chøng kiÕn tèc ®é gia t¨ng m¹nh cña ¶nh sè trªn toµn thÕ giíi, bëi sù gia t¨ng m¹nh mÏ cña c¸c tr¹m lµm viÖc t¹i mÆt ®Êt còng nh− tr¹m vÖ tinh, khã kh¨n trong l−u tr÷, chi phÝ cao cho xö lý vµ internet. Sù ®a d¹ng c¸c øng dông cña ¶nh gãp phÇn ra ®êi thÕ hÖ ¶nh sè. C¸c øng dông cña ¶nh bao gåm: gi¶i trÝ sè, th− viÖn sè, gi¸o dôc vµ World Wide Web (www). C¸c øng dông ngµy cµng trë nªn phô thuéc vµo viÖc sö dông ¶nh gèc. Lîi Ých tr−íc m¾t cña ¶nh sè gåm c¶ mÆt x· héi vµ th−¬ng m¹i. Sö dông ¶nh gèc gióp s¸ng t¹o s¶n phÈm míi, tiÕt kiÖm thêi gian vµ tiÒn b¹c. Tuy nhiªn, ®é lín cña kho l−u tr÷ ¶nh sè trªn toµn thÕ giíi cã giíi h¹n, sù tËn dông ¶nh sè tõ CSDL hiÖn t¹i khã h¬n. §iÒu nµy lµ v× thiÕu c¸ch ®¸nh chØ môc vµ qu¶n lý ¶nh sè chuÈn. Th«ng th−êng c¸c ¶nh ®−îc l−u tr÷ trong CSDL sö dông d−íi d¹ng c¸c th«ng tin thuéc tÝnh. ThuËn lîi cña viÖc ®¸nh chØ môc thuéc tÝnh ¶nh: nã cã thÓ cung cÊp cho ng−êi sö dông tõ kho¸ t×m kiÕm l−ít qua môc lôc, thËm chÝ th«ng qua giao diÖn truy vÊn; vÝ dô nh− ng«n ng÷ truy vÊn cÊu tróc (SQL). Tuy nhiªn, nh×n tõ bªn ngoµi cã h¹n chÕ; mét trong nh÷ng h¹n chÕ ®ã lµ thêi gian tÝnh to¸n khi CSDL lín, nã d−êng nh− kh«ng thÓ chó gi¶i thñ c«ng tÊt c¶ c¸c ¶nh. MÆt kh¸c c¸c ®Æc tr−ng thÞ gi¸c cña ¶nh rÊt khã m« t¶ b»ng tõ ng÷ mét c¸ch kh¸ch quan, cã mét tiªu ®iÓm míi trªn viÖc ph¸t triÓn c«ng nghÖ ®¸nh chØ môc ¶nh, ®ã lµ kh¶ n¨ng t×m kiÕm ¶nh dùa trªn ng÷ c¶nh: nã cã thÓ ®éc lËp vµ cã thÓ tù ®éng ho¸. C¸c c«ng nghÖ hiÖn t¹i ®a phÇn qui vÒ t×m kiÕm ¶nh dùa trªn ng÷ nghÜa (CBIR). CBIR ®−îc giíi thiÖu nh− phÇn bæ xung cho viÖc tiÕn tíi ®¸nh chØ môc thuéc tÝnh truyÒn thèng, nã lµ cÇn thiÕt ®Ó cÊu thµnh CSDL multimedia. V× nh÷ng - 10 - tiÒm n¨ng øng dông réng r·i cña nã, CBIR ®· thu hót ®−îc sè l−îng lín c¸c chó ý trong nh÷ng n¨m gÇn ®©y (KAT 92, NIB 93, YOS 99). Trong CBIR, ¶nh trong CSDL lµ d÷ liÖu kh«ng cÊu tróc, ¶nh sè hoµn toµn chØ bao gåm m¶ng c¸c pixel ®é chãi, kh«ng cã ý nghÜ vèn cã. Mét trong nh÷ng ch×a kho¸ b¾t nguån CBIR lµ sù cÇn thiÕt ®Ó trÝch chän th«ng tin h÷u Ých tõ d÷ liÖu th«, ®Ó ph¶n ¸nh ng÷ nghÜa ¶nh. V× vËy viÖc trÝch chän hiÖu qu¶ c¸c ®Æc tr−ng ng÷ nghÜa ®ã lµ ®iÒu cèt yÕu sù thµnh c«ng cña CBIR. Nghiªn cøu trªn nh÷ng yªu cÇu cña ng−êi sö dông ®èi víi ¶nh tõ bé s−u tËp ¶nh biÓu thÞ nh÷ng ®Æc tr−ng nguyªn thuû ®ã nh− mµu s¾c, kÕt cÊu, h×nh d¹ng hoÆc hçn hîp cña chóng lµ rÊt h÷u Ých ®èi víi viÖc m« t¶ vµ kh«i phôc ¶nh (EAK 99). Nh÷ng ®Æc tr−ng nµy lµ kh¸ch quan vµ trùc tiÕp b¾t nguån tõ tù b¶n th©n ¶nh mµ kh«ng cÇn tham kh¶o bÊt kú mét kiÕn thøc c¬ b¶n nµo tõ bªn ngoµi. V× vËy ®Æc tr−ng nguyªn thuû cña ¶nh ë møc thÊp cã thÓ ®−îc b¾t nguån vµ khai th¸c ®Ó khuyÕn khÝch viÖc CBIR tù ®éng ho¸. *§èi t−îng nghiªn cøu Tõ c¸c th«ng tin c¬ b¶n trªn ®©y c¸c ¶nh trong CSDL cã thÓ ®−îc ®¸nh chØ môc b»ng c¸ch sö dông th«ng tin thuéc tÝnh hoÆc th«ng tin ng÷ nghÜa. Ng÷ nghÜa cña ¶nh cã thÓ ®−îc m« t¶ sö dông c¸c ®Æc tr−ng nguyªn thuû; vÝ dô: mµu s¾c, cÊu tróc, h×nh d¹ng hoÆc tæ hîp cña chóng. KÕt qu¶ nghiªn cøu nµy chÊp nhËn tiÕn tíi CBIR, ®ã lµ viÖc ®¸nh chØ môc vµ t×m kiÕm ¶nh b»ng ng÷ nghÜa cña ¶nh. §Æc biÖt, viÖc t×m kiÕm héi tô ë viÖc ®¸nh chØ môc vµ t×m kiÕm ¶nh dùa trªn h×nh d¹ng. Môc ®Ých chñ yÕu cña c¸ch t×m kiÕm nµy lµ t×m kiÕm vµ khai th¸c h×nh d¹ng rÊt kh¶ thi ®Ó t×m kiÕm vµ nhËn d¹ng h×nh d¹ng. §iÒu tra c¸c c«ng nghÖ vµ ph¸t triÓn trong nghiªn cøu nµy cã thÓ lµ trùc tiÕp øng dông cho c¸c øng dông ®Æc thï; vÝ dô t×m kiÕm nh·n m¸c, nhËn d¹ng ®èi t−îng… hoÆc cã thÓ hîp nhÊt trong bÊt cø hÖ thèng CBIR nµo ®Ó dÔ dµng nhËn d¹ng h×nh d¹ng sö dông c¸c ®Æc tr−ng hçn hîp cña ¶nh. - 11 - NhËn d¹ng nãi chung héi tô c¸c vÊn ®Ò cña nhËn d¹ng trùc quan dùa trªn th«ng tin h×nh d¹ng h×nh häc. Ph−¬ng ph¸p nhËn d¹ng h×nh d¹ng th−êng bao gåm 3 tiÕn tr×nh: trÝch chän ®Æc tr−ng, ®èi s¸nh (cèt lâi cña tiÕn tr×nh nµy lµ ®Þnh nghÜa 1 kho¶ng c¸ch hoÆc phÐp ®o sù t−¬ng ®ång gi÷a c¸c ®Æc tr−ng h×nh d¹ng ®−îc m« t¶) vµ ra quyÕt ®Þnh. PhÇn nµy chñ yÕu nghiªn cøu vÊn ®Ò ra quyÕt ®Þnh cho ®èi s¸nh h×nh d¹ng, ®Æc biÖt trong khung chung gi÷a hai h×nh d¹ng gièng nhau ®Ó ®èi s¸nh, nã cã thÓ ®i tíi quyÕt ®Þnh nh− thÕ nµo? Môc ®Ých ®Ó ®Þnh nghÜa tiªu chuÈn thèng kª dÉn tíi quyÕt ®Þnh 2 h×nh d¹ng lµ gièng hay kh«ng. Nghiªn cøu c¸c tiÕn tr×nh thùc hiÖnnhËn d¹ng h×nh d¹ng theo tr×nh tù c¸c c«ng ®o¹n: tõ c«ng ®o¹n s¬ khai biÓu diÔn ¶nh, trÝch chän ®Æc tr−ng, t¸ch nhãm nh©n tè h×nh d¹ng thµnh 1 h×nh d¹ng vµ chñ yÕu lµ ph−¬ng ph¸p ra quyÕt ®Þnh Contrario cho nhËn d¹ng h×nh d¹ng. *CÊu tróc luËn v¨n Ch−¬ng 1 : Tæng quan vÒ t×m kiÕm ¶nh dùa trªn h×nh d¹ng Ch−¬ng 2: T¸ch nhãm Ch−¬ng 3: Ph−¬ng ph¸p Contrario cho nhËn d¹ng h×nh d¹ng Ch−¬ng 4: Thö nghiÖm Do thêi gian vµ kh¶ n¨ng cã h¹n nªn luËn v¨n nµy sÏ cßn nhiÒu thiÕu sãt. RÊt mong ®−îc sù gãp ý vµ th«ng c¶m cña c¸c thÇy gi¸o, c« gi¸o. Hµ néi, ngµy 6 th¸ng 11 n¨m 2006 Häc viªn §inh ThÞ Kim Ph−îng - 12 - Ch−¬ng 1 Tæng quan t×m kiÕm ¶nh dùa trªn h×nh d¹ng 1.1. Giíi thiÖu VÊn ®Ò c¬ b¶n cña t×m kiÕm ¶nh dùa trªn h×nh d¹ng lµ phÐp ®o sù t−¬ng ®ång gi÷a c¸c c¸c h×nh d¹ng ®−îc m« t¶ bëi c¸c ®Æc tr−ng cña chóng. V× vËy, hai b−íc cÇn thiÕt trong t×m kiÕm vµ nhËn d¹ng ¶nh dùa trªn h×nh d¹ng ®ã lµ trÝch chän ®Æc tr−ng vµ phÐp ®o t−¬ng ®−¬ng gi÷a c¸c ®Æc tr−ng ®· ®−îc trÝch chän. Hai c«ng cô c¬ b¶n cÇn thiÕt ®−îc sö dông trong trÝch chän ®Æc tr−ng h×nh d¹ng lµ biÕn ®æi Fourier vµ kh«ng gian ®é chia. MÆc dï trÝch chän ®Æc tr−ng lµ mÊu chèt ®Ó t×m kiÕm ¶nh dùa trªn h×nh d¹ng vµ nhËn d¹ng h×nh d¹ng, phÐp ®o sù t−¬ng ®ång gi÷a c¸c ®Æc tr−ng ®−îc trÝch chän còng rÊt quan träng. yªu cÇu hiÖu qu¶ t×m kiÕm ¶nh ®ã lµ nhËn biÕt nhanh c¸c h×nh d¹ng t−¬ng ®ång - sù t−¬ng ®ång trong giíi h¹n cña c¸c ®Æc tr−ng ®−îc trÝch chän. 1.2. C«ng cô trÝch chän ®Æc tr−ng BiÕn ®æi Fourie lµ mét c«ng cô kinh ®iÓn. Nã ®· ®−îc sö dông tõ nhiÒu n¨m nay trong mäi hÖ thèng xö lý tÝn hiÖu vµ hÖ thèng m¸y tÝnh. Cßn kh«ng gian ®é chia lµ mét c«ng cô míi ®ang ®−îc chó ý gÇn ®©y. 1.2.1.BiÕn ®æi Fourier BiÕn ®æi Fourie lµ mÊu chèt trong xö lý ¶nh nã ®−îc øng dông réng r·i trong lý thuyÕt còng nh− trong thùc tÕ. Nguyªn t¾c c¬ b¶n cña biÕn ®æi Fourie ®ã lµ mét ®èi t−îng ®−îc coi nh− mét tÝn hiÖu vµ nh− vËy cã thÓ biÓu diÔn ®èi t−îng thµnh c¸c thµnh phÇn c¬ b¶n cña tÝn hiÖu. BiÕn ®æi Fourie rÊt h÷u Ých cho ph©n tÝch c¸c ®èi t−îng kh¸c nhau: cã thÓ ®èi t−îng bÞ lµm nhiÔu bëi biÕn ®æi phæ - 13 - (H×nh 1.1), trong khi c¸c ®èi t−îng t−¬ng ®−¬ng kh¸c sÏ cã biÕn ®æi phæ t−¬ng tù thËm chÝ c¶ khi chóng bÞ ¶nh h−ëng bëi nhiÔu vµ c¸c biÕn ®æi kh¸c(h×nh 1.2). H×nh 1.1: §èi t−îng bÞ lµm nhiÔu bëi biÕn ®æi phæ. H×nh 1.2: ¶nh vµ c¸c biÕn ®æi kh¸c 1.2.1.1.Chuçi Fourier §Æt f(x) lµ hµm tuÇn hoµn chu kú 2π vµ nguyªn trong mét chu kú, theo lý thuyÕt Fourie f(x) cã thÓ khai triÓn thµnh chuçi fourie nh− sau: (1.1) (1.2) - 14 - (1.3) (1.5) (1.6) (1.4) Víi chu kú T: 1.2.1.2. Sù héi tô cña chuçi Fourier NÕu mét hµm f(x) lµ tuÇn hoµn vµ nguyªn trong chu kú cña nã th× sÏ tån t¹i chuçi Fourie nh−ng kh«ng ®¶m b¶o ch¾c ch¾n r»ng chuçi Fourie sÏ héi tô tíi f(x). Tuy nhiªn theo ®iÒu kiÖn Fourie Dirichcle phÇn lín hoÆc c¸c líp chung cña hµm cã thÓ biÓu diÔn b»ng chuçi Fourie. §iÒu kiÖn chuçi Fourie Dicrichcle nÕu lµ mét ®o¹n hµm f(x) liªn tôc : 1. Giíi h¹n sè c¸c ®iÓm kh«ng liªn tôc 2. Giíi h¹n c¸c ®iÓm cùc trÞ. Hµm nµy cã thÓ më réng thµnh chuçi Fourie héi tô t¹i c¸c ®iÓm liªn tôc vµ ý nghÜa cña ®iÓm giíi h¹n thùc vµ giíi h¹n ¶o cña hµm t¹i ®iÓm giíi h¹n: §èi víi tÝn hiÖu sè hoÆc ®èi t−îng sè ®iÒu kiÖn Dirichcle ®−îc chøng minh v× vËy nã cã thÓ ®−îc biÓu diÔn bëi chuçi Fourie: 1.2.1.3. BiÕn ®æi Fourier - 15 - NÕu hµm f(x) cã thÓ biÓu diÔn b»ng chuçi Fourie cña nã. Sau ®ã f(x) ®−îc x¸c ®Þnh duy nhÊt bëi hÖ sè Cn. Ng−îc l¹i nÕu hÖ sè Cn cña chuçi Fourie cña hµm ®· biÕt tr−íc th× f(x) cã thÓ ®−îc x©y dùng l¹i tõ tËp Cn. Chuçi Fourie thiÕt lËp mèi quan hÖ duy nhÊt gi÷a f(x) vµ hÖ sè Cn. BiÓu diÔn theo c«ng thøc : (1.7) T−¬ng øng c«ng thøc: (1.8) 1.2.1.4. BiÕn ®æi Fourier rêi r¹c BiÕn ®æi Fourie ®Æc biÖt h÷u Ých ®èi víi ph©n tÝch ®èi t−îng sè v× ®èi t−îng sè tån t¹i ë d¹ng rêi r¹c. §Ó biÕn ®æi c«ng thøc 1.7 vµ 1.8 thµnh d¹ng rêi r¹c, f(x) ®−îc lÊy N mÉu trong chu kú [0, T] f(x0); f(x0+∆x); f(x0+2∆x);… f(x0+(N-1)∆x) ∆x gäi lµ b−íc lÊy mÉu trong ph¹m vi kh«ng gian xem xÐt f(x) biÓu diÔn thµnh: (1.9) (1.10) B−íc lÊy mÉu ∆u trong miÒn tÇn sè vµ b−íc lÊy mÉu ∆x trong miÒn kh«ng gian cã quan hÖ theo biÓu thøc : - 16 - Mèi quan hÖ nµy dÔ thay ®æi chØ râ sù chÝnh x¸c cña biÓu diÔn ®èi t−îng trong miÒn kh«ng gian vµ trong miÒn tÇn sè lµ ng−îc víi nhau. Chó ý, khi bè trÝ mét tËp d÷ liÖu kh¸c th× chóng kh«ng thÓ biÕn ®æi ®éc lËp víi nhau. §iÒu nµy cÇn l−u ý khi trÝch chän ®Æc tr−ng trong miÒn kh«ng gian lÊy mÉu ®èi t−îng. 1.2.1.5. BiÕn ®æi Fourier hai chiÒu §èi víi hµm hai biÕn f(x,y) x¸c ®Þnh 0 ≤ x, y ≤ N. CÆp biÕn ®æi Fourie lµ: (1.11) (1.12) MÆc dï, sè l−îng F(u,v) tõ biÕn ®æi Fourie cña biÓu thøc lµ rÊt lín nh−ng sè l−îng F(u,v) cã Ých lµ rÊt bÐ. §©y lµ lý do biÓu diÔn ®èi t−îng trong miÒn tÇn sè tèt h¬n (HÖ sè cã nghÜa Ýt). §iÒu nµy thùc sù h÷u Ých trong nhiÒu øng dông ®Æc biÖt trong viÖc ph©n tÝch h×nh d¹ng v× nã cã thÓ xÊp xØ ý nghÜa cña ®èi t−îng gèc f(x,y) hoÆc f(x) cã thÓ x©y dung tõ F(u,v) nhá. §©y lµ vÊn ®Ò c¬ b¶n cña xö lý tÝn hiÖu Fourie vµ ph©n tÝch ®èi t−îng Fourie. 1.2.1.6. Ph¹m vi cña biÕn ®æi Fourier BiÕn ®æi Fourie tu©n theo ph¹m vi h÷u Ých cña viÖc ph©n tÝch ®èi t−îng • Sù riªng rÏ: BiÕn ®æi Fourie rêi r¹c (1.11) cã thÓ m« t¶ riªng rÏ nh− sau: (1.13) • Lîi Ých cña viÖc riªng rÏ nµy ®ã lµ F(u,v) cã thÓ thu ®−îc trong 2 b−íc b»ng c¸ch sö dông liªn tiÕp biÕn ®æi Fourie 1 chiÒu. FT 1 chiÒu cã thÓ ®−îc tÝnh to¸n sö dông biÕn ®æi Fourie nhanh FFT. • BiÕn ®æi: BiÕn ®æi ph¹m vi cña FT (1.14) - 17 - • §iÒu nµy chØ ra: 1 sù thay ®æi trong miÒn kh«ng gian sÏ dÉn ®Õn sù thay ®æi trong miÒn tÇn sè. • PhÐp quay: NÕu g¾n vµo hÖ to¹ ®é cùc Sau ®ã thay thÕ vµo biÓu thøc cã : (1.15) §iÒu nµy cã nghÜa viÖc quay f(x,y) trong miÒn kh«ng gian gãc θ0 còng t−¬ng øng viÖc quay F(u,v) mét gãc t−¬ng tù trong miÒn tÇn sè. • §é chia: ®èi víi hai hÖ sè a, b, ph¹m vi ®é chia cña FT ®−îc viÕt nh− sau: (1.16) §iÒu nµy chØ ra r»ng: ®é chia cña f(x,y) víi a vµ b theo x,y trong miÒn kh«ng gian tû lÖ nghÞch víi biªn ®é F(U,V) trong miÒn tÇn sè. §iÒu nµy còng gi¶m bít hÖ sè F(u,v) bëi 1/a vµ 1/b theo u, v trong miÒn tÇn sè. Tæng qu¸t, phãng to mét ®èi t−îng ¶nh trong miÒn tÇn sè sÏ lµm næi møc tÇn sè thÊp trong miÒn kh«ng gian trong khi viÖc thu nhá ®èi t−îng trong ¶nh sÏ lµm t¨ng vïng tÇn sè cao trong miÒn kh«ng gian. 1.2.2. Kh«ng gian ®é chia (Scale space) §èi víi FT th× kh«ng gian ®é chia lµ c«ng cô kh¸ míi trong ph©n tÝch ®èi t−îng. Nã ®· ®−îc ph¸t triÓn trong c¸c hÖ thèng tÝnh to¸n. PhÇn nµy sÏ giíi thiÖu kh«ng gian ®é chia tuyÕn tÝnh vµ ph¹m vi quan träng cña nã. 1.2.2.1. C¬ së Lý thuyÕt kh«ng gian ®é chia gióp ta quan s¸t c¸c ®èi t−îng trong c¸c ®é chia kh¸c nhau vµ c¸c ®èi t−îng chØ cã ý nghÜa duy nhÊt theo ®é chia chÝnh. Mét vÝ dô ®¬n gi¶n nÕu lµ ¶nh mét sù vËt th× dï cã lµ ®é chia 1m hay 1cm th× ý nghÜa cña sù vËt kh«ng thay ®æi. Trong vËt lý c¸c ®èi t−îng tån t¹i trong sù s¾p xÕp ®é - 18 - chia. C¸c dông cô quan s¸t nh− camera c¸c dông cô nµy cã thÓ quan s¸t còng lµ mét sù s¾p xÕp ®é chia. §Ó më réng c¸c ®é chia t−¬ng øng víi sù phãng to hay thu nhá nhê c¸c dông cô quan s¸t. §é chia cña mét dông cô lu«n cã hai giíi h¹n: ®é chia gióp ph©n biÖt chi tiÕt ¶nh tèt nhÊt vµ kÐm nhÊt vµ khi quan s¸t sù vËt th× ®é chia n»m trong kho¶ng giíi h¹n hai phÝa nµy. §Ó tÝnh to¸n bÊt kú d¹ng biÓu diÔn nµo tõ d÷ liÖu ¶nh, th«ng tin cÇn ®−îc trÝch chän b»ng c¸ch sö dông to¸n tö nµo ®ã víi d÷ liÖu. C¸c to¸n tö t−¬ng tù nh− èng kÝnh m¸y quay sö dông ®Ó m« t¶ thÕ giíi thùc. Mét vµi vÊn ®Ò ®Æt ra khi ®Ò cËp tíi c¸c to¸n tö ®ã ®−îc sö dông nh− thÕ nµo, thùc hiÖn ë ®©u vµ thùc hiÖn c«ng viÖc ra sao, ®é lín nh− thÕ nµo. Nh− vËy th«ng tin thu ®−îc x¸c ®Þnh rÊt phong phó th«ng qua mèi quan hÖ cña c¸c cÊu tróc thùc tÕ trong d÷ liÖu vµ kÝch cì cña to¸n tö. §é chia gÇn ®óng khi ph©n tÝch ®èi t−îng cã thÓ biÕt tr−íc. Tuy nhiªn trong phÇn lín c¸c vÊn ®Ò th× ®iÒu nµy kh«ng quan träng. Lý do chÝnh ®Ó x©y dùng kh«ng gian ®é chia ®ã lµ nÕu cã kiÕn thøc biÕt tr−íc vÒ kh«ng gian ®é chia thÝch hîp lÊy tõ tËp CSDL cã nhiÒu ®é chia th× kh«ng gian ®é chia sÏ ®−îc ¸p dông ®Ó thu gän c«ng thøc tÝnh to¸n thÝch hîp. ViÖc sö dông c¸c hµm lµm tr¬n nhiÔu Gauss t¹i c¸c ®é chia kh¸c nhau ®· ®−îc ¸p dông trong ph©n tÝch ¶nh cho thÊy mèi liªn hÖ gi÷a c¸c ®é chia kh¸c nhau víi cÊu tróc ¶nh vµ kh«ng gian ®é chia lµ cã giíi h¹n. Tuy nhiªn ®é chia kÝch th−íc hoµn toµn cã thÓ thªm vµo trong kh«ng gian miªu t¶ ®èi t−îng v× c¸c cÊu tróc cã thÓ ®−îc nghiªn cøu th«ng qua ®é chia. §Æc biÖt khi g¾n vµo tÝn hiÖu f(x): R N → R vµ 1 tËp liªn tôc {L(x, t ) / t 〉 0} lµm mÞn dÇn dÇn (cã nghÜa lµ viÖc nh©n chËp tÝn hiÖu f(x) víi mét hµm liªn tôc g(x,t)) L ( x , t ) = g ( x, t ) ∗ f ( x ) (1.17) ë ®©y g(x,t) lµ hµm lµm mÞn hoÆc hµm mÆt n¹, l(x,t) lµ tÝn hiÖu ®−îc lµm mÞn, * lµ phÐp nh©n chËp. Víi tÝn hiÖu liªn tôc th× f(x)®−îc khai triÓn nh− sau: (1.18) - 19 - 1.2.2.2. Kh«ng gian ®é chia Gaussian Hµm Gausss lµ hµm mÆt n¹ h÷u Ých nhÊt cho kh«ng gian ®é chia tæng qu¸t nhÊt. Mang tíi mét tÝn biÖu f(x): R N → R lµ m« t¶ ®é chia L: R N × Rt → R ®−îc ®Þnh nghÜa nh− mét m« t¶ t¹i ®é chia 0 ®èi víi tÝn hiÖu gèc L(x,0) = f (x ) 1.19 (1.20) Vµ sù miªu t¶ ®é chia kÐm h¬n mang l¹i b»ng phÐp nh©n chËp víi mÆt n¹ Gauss khi ®ã kÝch th−íc ¶nh t¨ng lªn: (1.21) (1.22) 1.2.2.3. Ph¹m vi cña sù kh«ng t¹o c¸c ®Æc tr−ng míi Ph¹m vi quan träng nhÊt trong kh«ng gian ®é chia ®ã lµ sù kh«ng t¹o c¸c ®Æc tr−ng míi. Cã nghÜa lµ sù biÕn ®æi tõ mét ®é chia tèt sang mét ®é chia xÊu h¬n sÏ thiÕt lËp mét tÝn hiÖu ®¬n gi¶n h¬n, v× thÕ ®Æc tr−ng trong kh«ng gian ®é chia mÊt tÝnh ®¬n ®iÖu khi ®é chia gia t¨ng. Nã lµ nguyªn nh©n lµm ¶nh h−ëng tíi tÝn hiÖu vµ lµm mê ¶nh h−ëng ®èi víi tÝn hiÖu hai chiÒu. - 20 - H×nh 1.3: §iÓm qua 0 t¹i vÞ trÝ x vµ ®é chia t cña tÝn hiÖu C¸c ®Æc tr−ng h÷u Ých ®Æc biÖt t¹i ®iÓm qua 0 cña ®¹o hµm bËc thø n. Thùc tÕ ®¹o hµm bËc hai cña tÝn hiÖu ®−îc sö dông trong ph©n tÝch ®èi t−îng, bëi ®¹o hµm bËc hai ph¶n ¸nh ®iÓm uèn cong cña tÝn hiÖu. §iÓm cong (mét ®Æc tr−ng h÷u Ých ®èi víi ph©n tÝch ®èi t−îng). §iÓm qua 0 cña ®¹o hµm bËc hai lµ ®iÓm uèn cong ®ã lµ ®Æc tr−ng cho gãc låi ra cña ®èi t−îng. Víi tÝn hiÖu mét chiÒu, ®iÒu ®ã ®−îc ¸p dông víi kh«ng gian ®é chia Gauss. §iÓm qua 0 cña tÝn hiÖu t¹i tÊt c¶ c¸c ®é chia gäi lµ lÊy dÊu hoÆc c©y kho¶ng c¸ch. (h×nh 1.3 b). Bëi ph¹m vi kh«ng s¸ng t¹o cña ®Æc tr−ng míi, viÖc lµm mÞn cuèi cïng cña tÝn hiÖu ®−îc b¶o ®¶m. V× vËy chiÒu cao cña c©y kho¶ng c¸ch lµ cã giíi h¹n. Witkin(Wit 83) gi¶i thÝch c©y kho¶ng c¸ch nµy víi kinh nghiÖm quan s¸t, cµnh c©y trong c©y kho¶ng c¸ch t−¬ng øng víi vÞ trÝ låi ra cña ®èi t−îng. ASA 84: ®Çu tiªn trÝch chän ®Ønh tõ c©y kho¶ng c¸ch thu ®−îc vµ gi¶i thÝch chóng nh− c¸c ®Æc tr−ng vËt lý( nh− gãc, ®iÓm nèi, ®iÓm kÕt thóc, ®iÓm ®Æc biÖt…) Mok96 còng trÝch chän ®Ønh tõ c©y kho¶ng c¸ch thu ®−îc vµ ®Ò nghÞ viÖc sö dông c¸c ®Æc tr−ng ®Ønh th«ng th−êng cho t×m kiÕm h×nh d¹ng. Hoµn toµn cã thÓ ¸p dông kh«ng gian ®é chia ®Ó biÓu diÔn h×nh d¹ng. 1.2.2.4. Kh«ng gian ®é chia m©u thuÉn víi viÖc ®a quyÕt ®Þnh Trong ph©n tÝch ®èi t−îng hai ph−¬ng ph¸p ph©n tÝch cã thø bËc th−êng ®−îc sö dông: mét lµ ph−¬ng ph¸p kh«ng gian ®é chia, ph−¬ng ph¸p kh¸c c©y quyÕt ®Þnh, vÝ dô nh− ph−¬ng ph¸p h×nh chãp vµ ph−¬ng ph¸p sãng. Hai ph−¬ng ph¸p nµy kh¸c nhau: ®iÓm kh¸c biÖt chÝnh cña hai c«ng cô thÓ hiÖn ë 3 khÝa c¹nh: +LÊy mÉu kh«ng nhÊt qu¸n, chèng l¹i viÖc lÊy mÉu c¸c kh«ng gian kh¸c. BiÓu diÔn kh«ng gian ®é chia ®−îc ®Þnh nghÜa b»ng viÖc lµm mÞn vµ l−u gi÷ c¸c mÉu kh«ng gian gièng nhau t¹i tÊt c¶ c¸c ®é chia. Trong khi lÊy mÉu kh«ng gian ®a quyÕt ®Þnh t¹i c¸c ®é chia kh¸c nhau lµ kh¸c nhau. §èi t−îng