Nội dung

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.