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.5. §−êng giao biÓu ®å .........................................................................25

1.3.1.4. Th«ng tin thèng kª

...................................................................25

- 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

ý nghÜa

STT

1

Tõ viÕt t¾t

CBIR

FD

Content Based Image Retrieval

Fourie Descriptor

Fast Fourie Transform

C¬ së d÷ liÖu

2

3

FFT

4

CSDL

NFA

PFA

5

Number of Fasle Alarm

Pridicion Fasle Alarm

Fourie Transform

NFA of region

6

7

FT

8

NFA_g

NFA_gg

Pro

9

NFA of region-region

Proposition

10

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è C_n. Ng−îc l¹i nÕu hÖ sè C_ncñ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 C_n. Chuçi Fourie thiÕt lËp

mèi quan hÖ duy nhÊt gi÷a f(x) vµ hÖ sè C_n. 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(x₀); f(x₀+∆x); f(x₀+2∆x);… f(x₀+(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 θ₀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

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

)

/t〉0 lµm mÞn dÇn dÇn (cã nghÜa lµ viÖc

}

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× R_t→ 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

- 21 -

chÝnh cña ®a quyÕt ®Þnh lµ gi¶m bít lÊy mÉu tõ mét ®é chia tíi c¸c ®é chia cao

h¬n, v× thÕ qu¸ tr×nh xö lý tÝn hiÖu cã thÓ hiÖu qu¶ h¬n.

+T−¬ng quan ®é chia ®èi nghÞch víi sù ph©n ly ®é chia, ph−¬ng

ph¸p ®a quyÕt ®Þnh kh«ng khai th¸c ®iÓm kh¸c biÖt cña cÊu tróc th«ng qua ®é

chia. C¸c kÕt qu¶ tÝnh to¸n t¹i mçi mét ®é chia ®−îc sö dông duy nhÊt ®Ó h−íng

dÉn tÝnh to¸n t¹i ®é chia tiÕp theo nhá h¬n vµ ®−îc lo¹i bá mét khi ®iÒu nµy ®−îc

hoµn thµnh. ChØ thùc hiÖn thuËt to¸n t¹i mét ®é chia vµ t¹i mét thêi ®iÓm. Ph−¬ng

ph¸p kh«ng gian ®é chia chÝnh lµ viÖc ph©n tÝch ®é chia nh− mét phÇn cÇn thiÕt

cña qu¸ tr×nh ph©n tÝch sù quan s¸t vµ nhËn d¹ng. Ph¹m vi c¸c phÐp ®o t¹i c¸c ®é

chia kh¸c nhau cã thÓ cã c¬ së v÷ng ch¾c phô thuéc nhiÖm vô chøa trong nã.

B»ng ®Þnh nghÜa, giíi thiÖu kh«ng gian ®é chia mang ®Õn mét gi¶i ph¸p cho viÖc

phæ biÕn l−îng bï sai, ®iÒu ®ã cã nghÜa c¸c ®Æc tr−ng ë c¸c ®é chia kh¸c nhau cã

thÓ liªn quan tíi nh÷ng ®Æc tr−ng kh¸c mét c¸ch râ rµng.

+LÊy mÉu ®é chia liªn tôc chèng l¹i viÖc lÊy mÉu ®é chia cè ®Þnh.

Gi÷a c¸c ph−¬ng ph¸p kh«ng gian ®é chia vµ ph−¬ng ph¸p ®a quyÕt ®Þnh ®ã lµ sù

miªu t¶ ®a quyÕt ®Þnh chÊp nhËn mét b−íc lÊy mÉu cè ®Þnh trong ®é chia hoÆc

quyÕt ®Þnh ®ã kh«ng bÞ suy gi¶m, trong khi ph−¬ng ph¸p ®é chia ph©n tÝch tÝn

hiÖu t¹i ®é chia liªn tôc. V× vËy nhiÖm vô cña viÖc t×m ®Æc tr−ng qua ®é chia dÔ

dµng h¬n trong kh«ng gian ®é chia so víi viÖc miªu t¶ ®a quyÕt ®Þnh. Sù tinh x¶o

cña lÊy mÉu ®é chia cã thÓ thùc hiÖn khi cã yªu cÇu.

Sù kh¸c biÖt c¸c ®Æc tr−ng cña hai lo¹i ph−¬ng ph¸p x¸c ®Þnh ë c¸ch øng

dông cña chóng. Ph−¬ng ph¸p kh«ng gian ®é chia th−êng ®−îc sö dông cho ph©n

tÝch vµ t×m hiÓu tÝn hiÖu, trong khi ph−¬ng ph¸p ®a quyÕt ®Þnh th−êng ®−îc sö

dông cho m· ho¸. Nã còng cÇn thiÕt ®Ó kÕt hîp ph−¬ng ph¸p kh«ng gian ®é chia

víi ph−¬ng ph¸p ®a ®é chia. Ph−¬ng ph¸p ®a ®é chia ®−îc chó ý h¬n ®a quyÕt

®Þnh trong ®iÒu kiÖn ph©n tÝch hoÆc miªu t¶ tÝn hiÖu t¹i mét ®é chia t¹i mét thêi

®iÓm. Nã kh«ng khai th¸c kh¸i niÖm ph©n tÝch, miªu t¶ tÝn hiÖu ë ®é chia liªn

- 22 -

tôc. Mèi t−¬ng quan t¸c ®éng cÊu tróc tÝn hiÖu th«ng qua ®é chia lµm mÊt ý

nghÜa cña ph−¬ng ph¸p ®a ®é chia.

1.2.3.Th¶o luËn

ë phÇn trªn, hai c«ng cô ph©n tÝch: BiÕn ®æi Fourier vµ kh«ng gian ®é chia

®· ®−îc m« t¶ vµ th¶o luËn. Ph¹m vi quan träng cña hai c«ng cô nµy ®· ®−îc

ph©n tÝch vµ chän läc. BiÕn ®æi Fourier miªu t¶ mét ®èi t−îng sö dông c¸c thµnh

phÇn c¬ b¶n cña c¸c tÝnh chÊt kh¸c nhau. Kh«ng gian ®é chia quan s¸t mét ®èi

t−îng víi vector c¬ b¶n cã chiÒu kh¸c nhau (c¸c sè chiÒu cña vector kh¸c nhau).

Th«ng tin phæ thu ®−îc tõ biÕn ®æi Fourier cã thÓ ®−îc sö dông trùc tiÕp

cho viÖc m« t¶ hoÆc miªu t¶ ®èi t−îng. Trong khi th«ng tin trong kh«ng gian ®o

®¹c thu ®−îc tõ kh«ng gian ®é chia cÇn thiÕt sù gi¶i thÝch s©u xa h¬n tr−íc khi sö

dông m« t¶ ®èi t−îng. Sù gi¶i thÝch th«ng tin kh«ng gian ®é chia vÉn cßn lµ th¸ch

thøc. §iÒu ®ã rÊt quan träng ®Ó lµm lÉn lén gi÷a gi¶i thÝch ®èi t−îng vµ m« t¶ ®èi

t−îng t¹i ®a ®é chia víi gi¶i thÝch ®èi t−îng vµ m« t¶ ®èi t−îng trong kh«ng gian

®é chia, ®©y lµ mét vÊn ®Ò rÊt khã.

Trong c¸c d¹ng cña th«ng tin thu ®−îc, biÕn ®æi Fourier thu ®−îc th«ng tin

®èi t−îng víi hÖ sè tÇn sè thÊp, trong khi miªu t¶ th«ng tin ®èi t−îng thu ®−îc

víi hÖ sè rÊt cao. §èi víi kh«ng gian ®é chia, th«ng tin ®èi t−îng chung cã thÓ

®−îc gi¶i thÝch tõ ®é chia cao h¬n, trong khi th«ng tin m« t¶ ®èi t−îng cã thÓ

®−îc gi¶i thÝch tõ ®é chia thÊp h¬n.

Søc m¹nh cña hai c«ng cô cho ph©n tÝch ®èi t−îng lµ rÊt râ rµng. Nã ®−îc

biÕt ®Õn ®ã lµ ph©n tÝch ®èi t−îng hoÆc trÝch chän ®Æc tr−ng trong miÒn kh«ng

gian lµ rÊt khã v× vÊn ®Ò nhiÔu vµ c¸c ®èi t−îng thay ®æi. Nh÷ng vÊn ®Ò nµy cã

thÓ dÔ dµng v−ît qua bëi viÖc ph©n tÝch ®èi t−îng trong miÒn phæ hoÆc trong

miÒn kh«ng gian ®é chia. C¶ hai ph−¬ng ph¸p chÊp nhËn viÖc ph©n tÝch ®èi t−îng

t¨ng dÇn tÝnh chi tiÕt. B»ng viÖc lo¹i trõ hoÆc bá qua nh÷ng chi tiÕt tinh tÕ nhÊt

trong mét ®èi t−îng. §èi t−îng cã thÓ ®−îc biÓu diÔn vµ thÓ hiÖn hiÖu qu¶ h¬n.

- 23 -

Tõ c¸ch nh×n nhËn nµy, kh«ng gian ®é chia xö lý t−¬ng tù víi biÕn ®æi Fourier.

Tuy nhiªn trong kh«ng gian ®é chia, nh÷ng chi tiÕt cña ®èi t−îng ®−îc dÞch

chuyÓn trong miÒn tÇn sè.

1.3. PhÐp ®o t−¬ng ®ång vµ thùc hiÖn c¸c phÐp ®o

§èi víi viÖc t×m kiÕm ¶nh dùa trªn h×nh d¹ng vµ c¸c ®Æc tr−ng ¶nh ®−îc

trÝch chän th−êng lµ vector ®Æc tr−ng N chiÒu, nã cã thÓ ®−îc ®Ò cËp tíi nh− mét

®iÓm trong kh«ng gian N chiÒu. Mét bøc ¶nh ®−îc ®¸nh chØ môc trong c¬ së d÷

liÖu sö dông c¸c vector ®Æc tr−ng ®−îc trÝch chän. ViÖc t×m kiÕm ¶nh thùc chÊt lµ

viÖc x¸c ®Þnh sù gièng nhau gi÷a ¶nh truy vÊn vµ c¸c ¶nh môc tiªu trong c¬ së d÷

liÖu mµ thùc chÊt lµ sù x¸c ®Þnh kho¶ng c¸ch gi÷a c¸c vector ®Æc tr−ng miªu t¶

h×nh ¶nh. Sù ®o ®¹c kho¶ng c¸ch mong muèn cÇn ph¶i tham chiÕu víi nhËn thøc

cña ng−êi. V× vËy, ®èi víi mét ®Æc tr−ng h×nh d¹ng dÉn tíi sù chÝnh x¸c cña viÖc

t×m kiÕm ¶nh cao h¬n, phÐp ®o kho¶ng c¸ch tèt h¬n. §èi víi viÖc t×m kiÕm ¶nh

trùc tuyÕn th× hiÖu qu¶ cÇn ph¶i ®−îc xem xÐt khi lùa chän mét phÐp ®o kho¶ng

c¸ch. NhiÒu phÐp ®o kho¶ng c¸ch kh¸c ®· ®−îc khai th¸c trong viÖc t×m kiÕm

¶nh, chóng bao gåm kho¶ng c¸ch c¸c khèi trung t©m (SWA91);(STR95); kho¶ng

c¸ch ¥c¬lit (VOO88); kho¶ng c¸ch Cosin(VOO 88), kho¶ng c¸ch giao nhau cña

biÓu ®å histoogram, hai kho¶ng c¸ch thèng kª(RUB99), kho¶ng c¸ch bËc hai

(NiB93, DEN99, WOL96, SEI97) vµ kho¶ng c¸ch Mahalanobis…(TRE71,

SMI97). Trong môc nµy, mét vµi phÐp ®o kho¶ng c¸ch sÏ ®−îc m« t¶ vµ −íc

l−îng. Môc ®Ých cña viÖc −íc l−îng nµy ®Ó t×m ra mét phÐp ®o t−¬ng ®ång sù

mong ®îi cho c¸c bé m« t¶ −íc l−îng h×nh d¹ng kh¸c nhau. §Ó biÕt t×m kiÕm ¶nh

tèt nh− thÕ nµo, cÇn ph¶i cã mét phÐp ®o kh¶ thi. Nãi chung, thùc hiÖn c¸c phÐp

®o ®o ®−îc sù chÝnh x¸c cña viÖc t×m kiÕm ¶nh. Tuy nhiªn, phô thuéc vµo sù x¸c

®Þnh ®é chÝnh x¸c kh¸c nhau, cã c¸c phÐp ®o sù thùc hiÖn kh¸c nhau.

1.3.1. PhÐp ®o sù gièng nhau

- 24 -

Mét phÐp ®o t−¬ng ®ång th−êng ®−îc ®Þnh nghÜa nh− mét phÐp ®o kho¶ng

c¸ch. Trong phÇn nµy m« t¶ chi tiÕt c¸c phÐp ®o sù gièng nhau kh¸c nhau.

1.3.1.1. Kh«ng gian phÐp ®o kho¶ng c¸ch

Mét kh«ng gian R^Nlµ mét kh«ng gian phÐp ®o nÕu cho bÊt kú hai phÇn tö

X vµ Y cña nã, ë ®ã tån t¹i mét sè thùc d(x,y) gäi lµ kho¶ng c¸ch tho¶ m·n c¸c

thuéc tÝnh sau:

(1) d(x,y) ≥ 0 {Kh«ng phñ ®Þnh}

(2) d(x,y) = 0 nÕu x = y {TÝnh ®ång nhÊt}

(3) d(x,y) = d(y,x)

{TÝnh ®èi xøng}

(4) d(x,z) < d(x,y) + d(y,z) {BÊt ®¼ng thøc trong tam gi¸c} (1.23)

1.3.1.2. Kho¶ng c¸ch d¹ng Minkowski

Kho¶ng c¸ch d¹ng Minkowski ®−îc ®Þnh nghÜa dùa trªn tiªu chuÈn Lp:

1

N −1

p

⎛

⎞

⎟

p

d _p

(

Q,T

)

= ⎜

(

Q −T

)

(1.24)

∑

i

⎝

i=0

⎠

ë ®©y

Q = {Q₀, Q₁,…….Q_N-1} lµ vector ®Æc tr−ng truy vÊn

T = {T₀, T₁, …….T_N-n} lµ vector ®Æc tÝnh t−¬ng øng

Khi p = 1; d₁(Q,T) lµ kho¶ng c¸ch khèi trung t©m hoÆc kho¶ng c¸ch

N −1

Manhattan (L₁).

d₁

(

Q,T

)

=

(

Q −T

)

(1.25)

∑

i

i−0

Khi p = 2; d₂(Q,T) gäi lµ kho¶ng c¸ch ¥c¬lit (L₂)

1

N −1

2

⎛

⎜

⎞

⎟

2

d₂

(

Q,T

)

=

(

Q −T

)

(1.26)

∑

i

⎝

i−0

⎠

Khi p →∞ ta cã L_∞

L_∞(Q,T) = max {(Q_i- T_i)} ; 0 ≤ i ≤ N (1.27)

1.3.1.3. Kho¶ng c¸ch Cosin

- 25 -

Kho¶ng c¸ch Cosin tÝnh to¸n sù kh¸c nhau vÒ ph−¬ng h−íng mµ kh«ng ®Ó

ý tíi chiÒu dµi vector. Kho¶ng c¸ch nµy thu ®−îc tõ viÖc ®o gãc gi÷a hai vector.

Q.T = Q^t.T = Q.T .cosθ

B»ng qui t¾c tÝch v« h−íng:

Q^t.T

d_cos

(

Q,T

)

= 1− cosθ = 1−

(1.28)

Q.T

H×nh 1.4: (a) kho¶ng c¸ch Ocolit,

(b) kho¶ng c¸ch Cosin, (c) kho¶ng c¸ch L₁

Nh− cã thÓ thÊy: kho¶ng c¸ch ¥c¬lit cã ®−îc tÝnh ®Õn c¶ gãc lÉn chiÒu dµi

vector ®Ó tÝnh to¸n. Trong khi kho¶ng c¸ch Cosin chØ tÝnh ®Õn gãc ®ã khi tÝnh

to¸n. Nh− kÕt qu¶: Q₁vµ Q sÏ cã kho¶ng c¸ch gièng nh− ®èi víi T.

d_cos(Q, T) = d_cos(Q₁, T) .

Kho¶ng c¸ch tÝnh to¸n d₁gi÷a mçi kÝch th−íc cña vector ®Æc tr−ng (h×nh 1.4)

χ²

1.3.1.4. Th«ng tin thèng kª

χ²

(th«ng tin thèng kª) ®−îc ®Þnh nghÜa nh− sau:

2

N −1

(

Q_i− m_i

)

Q_i+T_i

d_χ₂

(

Q,T

)

=

(1.29) ; m_i=

∑

m_i

2

i=0

biÓu diÔn th«ng dông bëi c¸c kÕt qu¶ kh¸c (RMB 99).

1.3.1.5. §−êng giao biÓu ®å

- 26 -

§−êng giao biÓu ®å ®−îc ®Ò xuÊt bëi Swain vµ Ballard {Swa 91}. T×m thÊy

nh÷ng ®èi t−îng bªn trong c¸c bøc ¶nh mét c¸ch kh¸ch quan b»ng viÖc sö dông

biÓu ®å mµu s¾c. Nã còng cã thÓ vËn dông ®èi s¸nh côc bé. Khi kÝch th−íc ®èi

t−îng( víi ®Æc tr−ng Q) nhá h¬n kÝch th−íc ¶nh( víi ®Æc tr−ng trong T). §Þnh

nghÜa gèc cña kho¶ng c¸ch biÓu ®å cho bëi c«ng thøc:

N −1

min

(

Q_i,T_i

)

∑

i=0

d_h

(

Q,T

)

= 1−

(1.30)

i

Q

Më réng trong kho¶ng c¸ch ®o ®−îc cã c«ng thøc nh− {SMI 97}:

N −1

min

(

Q_i,T_i

)

∑

i=0

d_h

(

Q,T

)

= 1−

(1.31)

i

min

(

Q , T

)

1.3.1.6. Kho¶ng c¸ch bËc hai

Nh÷ng kho¶ng c¸ch ®−îc tÝnh to¸n tõ phÐp ®o kho¶ng c¸ch ®−îc m« t¶ ë

trªn chØ tÝnh to¸n sù t−¬ng øng gi÷a mçi kÝch th−íc vµ kh«ng lµm cho th«ng tin

sö dông th«ng qua c¸c kÝch th−íc. VÊn ®Ò nµy nhËn ra trong sù thÝch øng cña

biÓu ®å. Kho¶ng c¸ch bËc hai ®−îc ®Ò xuÊt ®Ó tÝnh to¸n ®Õn sù gièng nhau th«ng

qua kÝch th−íc (NIB93, SMI97). Nã cung cÊp nhØÒu kÕt qu¶ h¬n lµ sù ®èi s¸nh

duy nhÊt gi÷a c¸c biÓu ®å mÉu. Kho¶ng c¸ch mÉu bËc hai gi÷a hai vector ®Æc

tr−ng Q vµ T ®−îc tÝnh:

1

2

d_qad

(

Q,T

)

=

[

(

Q −T

)

^tA

(

Q −T

)]

(1.32)

ë ®©y A =

[

a_ij

]

ma trËn N*N vµ a_ijlµ hÖ sè gièng nhau gi÷a nh÷ng chØ sè

kÝch th−íc i vµ j. a_ij®−îc tÝnh:

d_ij

a_ij= 1−

; trong ®ã d_ij=

[

Q_i−T_i

]

d_max

§Ó tÝnh to¸n, kho¶ng c¸ch mÉu bËc hai ®−îc viÕt l¹i (DEN 99)

- 27 -

1

2

N −1 N −1

⎡

⎢

⎣

⎤

⎥

⎦

d_qad

(

Q,T

)

=

a Q Q +

a T T +

Q T

(1.33)

∑∑

ij

i

j

ij

i

j

i

j

i=0 j=0

1.3.1.7. Kho¶ng c¸ch Mahalanobis

Kho¶ng c¸ch Mahalanobis lµ mét tr−êng hîp ®Æc biÖt cña phÐp ®o kho¶ng

c¸ch d¹ng bËc hai. ë ®ã ma trËn chuyÓn ®æi cã ®−îc nhê ma trËn hiÖp ph−îng sai

- 1

thu ®−îc tõ mét tËp häc cña c¸c vector ®Æc tr−ng ®ã lµ A = Σ . §Ó ¸p dông

kho¶ng c¸ch Mahalanobis, vector ®Æc tr−ng ®−îc coi nh− kh«ng gian biÕn

X =

[x₀, x₁,...x_{N −1}

]

[

r

]

víi

ij

{

}

{ }

r = E x_i, y _j.E y ®−îc lÊy tõ kh«ng gian biÕn y. Sau ®ã ma trËn hiÖp ph−¬ng sai

ij

lµ Σ ; Σ =

[

σ_i²_j

]

vµ σ_i²_j= r − E

{

x_i

}

E

{

x_j

}

.

ij

Kho¶ng c¸ch Mahalanobis gi÷a hai vector ®Æc tr−ng Q vµ T thu ®−îc b»ng

X_Q= Q vµ X_T= T.

1

2

.Σ⁻¹

X_Q− X_T

(1.34)

)

(

)

]

d_mah

=

[

(

X_Q− X_T

Trong tr−êng hîp ®Æc biÖt khi x_i®éc lËp thèng kª nh−ng x¸c suÊt kh«ng

2

⎡

⎤

⎥

σ₀

0

⎢

σ₁²

2

⎢

⎥

σ

σ _{N −1}

⎣

⎦

Trong tr−êng hîp nµy, kho¶ng c¸ch Mahalanobis ®−îc tÝnh l¹i cã d¹ng

2

N −1

(

Q_i−T_i

)

t−¬ng ®−¬ng sau : d_mah

(

Q,T

)

=

(1.35)

∑

σ_i²

i=0

Nã lµ mét kho¶ng c¸ch cã träng sè L₂. Nã ®em l¹i träng sè nhiÒu ®èi víi

kÝch th−íc thay ®æi Ýt h¬n víi sù thay ®æi nhá h¬n vµ träng sè Ýt h¬n víi kÝch

th−íc biÕn ®æi nhiÒu h¬n.

1.3.2.Thùc hiÖn phÐp ®o

- 28 -

§Ó ®Þnh l−îng c¸c gi¶i thuËt kh¸c nhau cho t×m kiÕm ¶nh, mét phÐp ®o

hiÖu qu¶ thùc hiÖn lµ cÇn thiÕt. C¸c phÐp ®o hiÖu qu¶ thùc hiÖn ®· ®−îc ®Ò x−íng

LU98, BMI99 , phÐp ®o sù thùc hiÖn th−êng dùa trªn viÖc thèng kª c¸c b−íc thö

[ ]

chñ quan. C¸c phÐp ®o sù thùc hiÖn kh¸c th−êng sö dông c¸c phÐp thö chñ quan

kh¸c, dÉn ®Õn c¸c ®Þnh nghÜa kh¸c nhau vÒ sù chÝnh x¸c trong t×m kiÕm ¶nh. C¸c

phÐp ®o sù thùc hiÖn kh¸c nhau ®−îc th¶o luËn trong phÇn nµy.

1.3.2.1. §é nh¹y vµ ®é chÝnh x¸c(RPP).

RPP lµ phÐp ®o sù thùc hiÖn t×m kiÕm ¶nh ®−îc sö dông réng r·i nhÊt

trong c¸c bµi gi¶ng. VÒ c¬ b¶n nã dùa trªn sù ®èi s¸nh tuyÖt ®èi. Trong ph−¬ng

hîp víi truy vÊn dùa trªn phÐp thö chñ quan. Trong c¸c phÐp thö chñ quan, mçi

mét ®èi t−îng lùa chän mét tin tøc t−¬ng øng víi d¹ng truy vÊn tõ CSDL. C¸c

môc ®Ých ®−îc lùa chän cho mçi truy vÊn s¸t víi c¸c ®èi t−îng cã s½n ®−îc xem

xÐt thÝch hîp tíi truy vÊn. Ng−îc l¹i, chóng ®−îc coi lµ kh«ng thÝch hîp. §é

chÝnh x¸c vµ ®é nh¹y ®−îc ®Þnh nghÜa nh− sau:

r

P =

r : Sè l−îng c¸c ¶nh t×m kiÕm phï hîp

n₁

n₁: Sè l−îng ¶nh ®−îc t×m kiÕm

r

R =

(1.36)

n₂: Tæng sè l−îng c¸c ¶nh thÝch hîp trong CSDL

n₂

§é chÝnh x¸c ®o b»ng t×m kiÕm ¶nh chÝnh x¸c trong khi ®é nh¹y ®o b»ng

kh¶ n¨ng t×m kiÕm môc ®Ých thÝch hîp tõ CSDL. §é chÝnh x¸c vµ ®é nh¹y cã mèi

hÖ ng−îc nhau. Sù chÝnh x¸c th«ng th−êng gi¶m t−¬ng øng sù gia t¨ng ®é nh¹y

(c¸i nµy t¨ng th× c¸i kia gi¶m).

1.3.2.2. Tû lÖ träng sè thµnh c«ng (PWH- Percentage of Weighted Hits)

- 29 -

PWH t−¬ng ®−¬ng nh− phÐp ®o ®é nh¹y ë RPP. PhÐp thö chñ quan gièng

nh− ®é chÝnh x¸c, ®ã lµ mçi ®èi t−îng lùa chän mét vµi môc phï hîp víi truy vÊn

nh− trong RPP, PWH g¸n mét träng sè thÝch hîp w_icho mçi Iterm w_it−¬ng øng.

V× vËy PWH ®−îc ®Þnh nghÜa nh− sau:

(1.37)

tr−êng hîp ®Æc biÖt cña PWH khi w_inhËn c¸c gi¸ trÞ 0 vµ 1.

1.3.2.3. PhÇn tr¨m cña thø bËc gièng nhau (PSR-Percentage of Similarity

Ranking )

PSR ®−îc ®Ò xuÊt bëi Bimbo vµ Pala[bim 97], trong phÐp ®o nµy mçi ®èi

t−îng g¸n mét d·y gièng nhau cho mçi iterm trong CSDL dùa trªn sù t−¬ng ®ång

cña iterm víi truy vÊn. §iÒu nµy h¬n h¼n viÖc g¸n sù thÝch hîp / kh«ng thÝch hîp

nh− trong RPP vµ PWH. KÕt qu¶ cuèi cïng cña phÐp thö lµ ma trËn Q_j(i,k)- chØ

mçi hµng ®· ®−îc tÝnh. P_j(i) vµ σ_j(i) giíi thiÖu thø tù trung b×nh cña bøc ¶nh thø i

cho truy vÊn j vµ phÐp ®o ®−îc tho¶ thuËn trong mét thø bËc khÐp kÝn t−¬ng øng

víi P_j(i). NÕu mçi truy vÊn j, mét thuËt to¸n t×m kiÕm trë thµnh mét iterm I t¹i

thø tù P_j(i) th× khi ®ã tho¶ thuËn gi÷a thuËt to¸n xÕp h¹ng vµ sù xÕp thø bËc do

con ng−êi thùc hiÖn ®−îc ®o bëi PSR S_j(i):

- 30 -

(1.38)

§å thÞ cña S_j(i) nh− hµm cña P_j(i) chØ ra hiÖu qu¶ t×m kiÕm cña thuËt to¸n

t−¬ng ®èi cao. S_j(i) cao chøng tá ®é chÝnh x¸c t×m kiÕm cao.

1.3.2.4. Th¶o luËn

Ba phÐp ®o sù thùc hiÖn ®−îc giíi thiÖu, PWH chØ ra trong tÝnh to¸n sè

l−îng c¸c chñ ®Ò kh¸c nhau lùa chän cho iterm t−¬ng øng. Nã ®¸p øng sù s¾p

xÕp cña con ng−êi nhiÒu h¬n trong recall ë RPP. Tuy nhiªn PWH kh«ng ®o kh¶

n¨ng lo¹i bá c¸c iterm kh«ng phï hîp trong danh s¸ch hoµn l¹i. Sù bÊt lîi cña

PWH lµ nã l¹i gi¶ thiÕt mét sè iterm cè ®Þnh ®−îc hoµn tr¶, ®iÒu nµy lµ kh«ng

thùc tÕ v× sè iterm hoµn tr¶ cã thÓ kh¸c nhau. §èi víi PSR mang l¹i trong tÝnh

to¸n sè l−îng vµ tho¶ thuËn cña viÖc con ng−êi s¾p xÕp thø bËc. Tuy nhiªn víi

mét truy vÊn PSR mang l¹i mét iterm chi tiÕt t¹i mét thø tù chi tiÕt lµ cao khi ®ã

xÕp cña thuËt to¸n t×m kiÕm kh¸c víi sù s¾p xÕp cña con ng−êi. MÆt kh¸c nÕu

h¼n s¾p xÕp cña chñ ®Ò. PhÐp ®o RPP cã kh¶ n¨ng kh«i phôc iterm phï hîp vµ c¶

kh¶ n¨ng lo¹i bá iterm kh«ng phï hîp. Sù bÊt lîi duy nhÊt cña RPP lµ bá qua sù

phï hîp cña víi truy vÊn. Sù bÊt lîi nµy lµ kh«ng quan träng nÕu tËp d÷ liÖu lµ

líp.

1.3.3. TrÝch chän ®Æc tr−ng h×nh d¹ng.

TrÝch chän th«ng tin h×nh d¹ng tõ d÷ liÖu ¶nh tËp trung ë ®−êng viÒn vµ

nhËn thøc vÒ h×nh d¹ng lµ kh«ng thay ®æi ®èi víi thay ®æi ®é t−¬ng ph¶n( thay

®æi trong ®é chia mµu s¾c vµ ®é chãi) . H×nh d¹ng h×nh häc cã ®−îc m« h×nh nh−