nhận dạng ảnh Pattern recognition

Ch¬ng B¶y: nhËn d¹ng ¶nh

7

nhËn d¹ng ¶nh

Pattern recognition

Nh chØ ra trong h×nh 1.1-a ch¬ng Mét, nhËn d¹ng ¶nh lµ giai ®o¹n cuèi cïng cña c¸c hÖ thèng xö lý ¶nh. NhËn

d¹ng ¶nh dùa trªn nÒn t¶ng lý thuyÕt nhËn d¹ng (pattern recognition) nãi chung vµ ®· ®îc ®Ò cËp trong nhiÒu s¸ch vÒ

nhËn d¹ng. ë ®©y, ta kh«ng nh¾c l¹i mµ chØ tr×nh bµy mang tÝnh chÊt giíi thiÖu mét sè kh¸i niÖm c¬ b¶n vµ c¸c ph¬ng

ph¸p thêng ®îc sö dông trong kü thuËt nhËn d¹ng. Vµ cuèi cïng sÏ ®Ò cËp ®Õn mét trêng hîp cô thÓ vÒ nhËn d¹ng ®ã lµ

nhËn d¹ng ch÷ viÕt, mét vÊn ®Ò ®· vµ ®ang ®îc quan t©m nhiÒu.

Trong lý thuyÕt nhËn d¹ng nãi chung vµ nhËn d¹ng ¶nh nãi riªng cã 3 c¸ch tiÕp cËn kh¸c nhau:

- NhËn d¹ng dùa vµo ph©n ho¹ch kh«ng gian.

- NhËn d¹ng cÊu tróc.

- NhËn d¹ng dùa vµo kü thuËt m¹ng n¬ ron.

Hai c¸ch tiÕp cËn ®Çu lµ c¸c kü thuËt kinh ®iÓn. C¸c ®èi tîng ¶nh quan s¸t vµ thu nhËn ®îc ph¶i tr¶i qua giai

®o¹n tiÒn xö lý nh»m t¨ng cêng chÊt lîng, lµm næi c¸c chi tiÕt (ch¬ng 4), tiÕp theo lµ trÝch chän vµ biÓu diÔn c¸c ®Æc tr￾ng (ch¬ng 5 vµ ch¬ng 6), vµ cuèi cïng míi qua giai ®o¹n nhËn d¹ng. C¸ch tiÕp cËn thø ba hoµn toµn kh¸c. Nã dùa vµo

c¬ chÕ ®o¸n nhËn, lu trò vµ ph©n biÖt ®èi tîng m« pháng theo ho¹t ®éng cña hÖ thÇn kinh con ngêi. Do c¬ chÕ ®Æc biÖt,

c¸c ®èi tîng thu nhËn bëi thÞ gi¸c ngêi kh«ng cÇn qua giai ®o¹n c¶i thiÖn mµ chuyÓn ngay sang giai ®o¹n tæng hîp, ®èi

s¸nh víi c¸c mÉu ®· lu tr÷ ®Ó nhËn d¹ng. §©y lµ c¸ch tiÕp cËn cã nhiÒu høa hÑn. C¸c c¸ch tiÕp cËn trªn sÏ tr×nh bµy chi

tiÕt trong c¸c phÇn díi ®©y.

7.1 tæng quan vÒ nhËn d¹ng

NhËn d¹ng lµ qu¸ tr×nh ph©n lo¹i c¸c ®èi tîng ®îc biÓu diÔn theo mét m« h×nh nµo ®ã vµ g¸n cho chóng vµo

mét líp (g¸n cho ®èi tîng mét tªn gäi) dùa theo nh÷ng quy luËt vµ c¸c mÉu chuÈn. Qu¸ tr×nh nhËn d¹ng dùa vµo nh÷ng

mÉu häc biÕt tríc gäi lµ nhËn d¹ng cã thµy hay häc cã thµy (supervised learning); trong trêng hîp ngîc l¹i gäi lµ häc

kh«ng cã thµy (non supervised learning). Chóng ta sÏ lÇn lît giíi thiÖu c¸c kh¸i niÖm nµy.

7.1.1 Kh«ng gian biÓu diÔn ®èi tîng, kh«ng gian diÔn dÞch

Kh«ng gian biÓu diÔn ®èi tîng

C¸c ®èi tîng khi quan s¸t hay thu thËp ®îc, thêng ®îc biÓu diÔn bëi tËp c¸c ®Æc trng hay ®Æc tÝnh. Nh trong tr￾êng hîp xö lý ¶nh, ¶nh sau khi ®îc t¨ng cêng ®Ó n©ng cao chÊt lîng, ph©n vïng vµ trÝch chän ®Æc tÝnh nh ®· tr×nh bµy

trong c¸c ch¬ng tõ ch¬ng Bèn ®Õn ch¬ng S¸u, ®îc biÓu diÔn bëi c¸c ®Æc trng nh biªn, miÒn ®ång nhÊt, v...,v. Ngêi ta th￾êng ph©n c¸c ®Æc trng nµy theo c¸c lo¹i nh: ®Æc trng t« p«, ®Æc trng h×nh häc vµ ®Æc trng chøc n¨ng. ViÖc biÓu diÔn ¶nh

theo ®Æc trng nµo lµ phô thuéc vµo øng dông tiÕp theo.

ë ®©y ta ®a ra mét c¸ch h×nh thøc viÖc biÓu diÔn c¸c ®èi tîng. Gi¶ sö ®èi tîng X (¶nh, ch÷ viÕt, dÊu v©n tay,

v...,v) ®îc biÓu diÔn bëi n thµnh phÇn (n ®Æc trng): X = {x1, x2,..., xn}; mçi xi biÓu diÔn mét ®Æc tÝnh. Kh«ng gian biÓu

diÔn ®èi tîng thêng gäi t¾t lµ kh«ng gian ®èi tîng X ®îc ®Þnh nghÜa:

X = {X1, X2,..., Xm}

NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 164

Ch¬ng B¶y: nhËn d¹ng ¶nh

trong ®ã mçi Xi biÓu diÔn mét ®èi tîng. Kh«ng gian nµy cã thÓ lµ v« h¹n. §Ó tiÖn xem xÐt chóng ta chØ xÐt tËp X lµ h÷u

h¹n.

Kh«ng gian diÔn dÞch

Kh«ng gian diÔn dÞch lµ tËp c¸c tªn gäi cña ®èi tîng. KÕt thóc qu¸ tr×nh nhËn d¹ng ta x¸c ®Þnh ®îc

tªn gäi cho c¸c ®èi tîng trong tËp kh«ng gian ®èi tîng hay nãi lµ ®· nhËn d¹ng ®îc ®èi tîng Mét c¸ch h×nh thøc gäi Ω

lµ tËp tªn ®èi tîng:

Ω = {w1, w2,...,wk} víi wi, i = 1, 2,..., k lµ tªn c¸c ®èi tîng

Qu¸ tr×nh nhËn d¹ng ®èi tîng f lµ mét ¸nh x¹ f: X ---> Ω víi f lµ tËp c¸c quy luËt ®Ó

®Þnh mét phÇn tö trong X øng víi mét phÇn tö trong Ω. NÕu tËp c¸c quy luËt vµ tËp tªn c¸c ®èi tîng lµ biÕt tríc nh trong

nhËn d¹ng ch÷ viÕt (cã 26 líp tõ A ®Õn Z), ngêi ta gäi lµ nhËn d¹ng cã thµy. Trêng hîp thø hai lµ nhËn d¹ng kh«ng cã

thµy. §¬ng nhiªn trong trêng hîp nµy viÖc nhËn d¹ng cã khã kh¨n h¬n.

7.1.2 M« h×nh vµ b¶n chÊt cña qu¸ tr×nh nhËn d¹ng

7.1.2.1 M« h×nh

ViÖc chän lùa mét qu¸ tr×nh nhËn d¹ng cã liªn quan mËt thiÕt ®Õn kiÓu m« t¶ mµ ngêi ta sö dông ®Ó ®Æc t¶ ®èi

tîng. Trong nhËn d¹ng, ngêi ta ph©n chia lµm 2 hä lín:

- Hä m« t¶ theo tham sè

- Hä m« t¶ theo cÊu tróc.

C¸ch m« t¶ ®îc lùa chän sÏ x¸c ®Þnh m« h×nh cña ®èi tîng. Nh vËy, chóng ta sÏ cã 2 lo¹i m« h×nh: m« h×nh theo tham

sè vµ m« h×nh cÊu tróc.

• M« h×nh tham sè sö dông mét vÐct¬ ®Ó ®Æc t¶ ®èi tîng. Mçi phÇn tö cña vÐct¬ m« t¶ mét ®Æc tÝnh cña ®èi tîng.

ThÝ dô nh trong c¸c ®Æc trng chøc n¨ng, ngêi ta sö dông c¸c hµm c¬ së trùc giao ®Ó biÓu diÔn. Vµ nh vËy ¶nh sÏ ®îc

biÓu diÔn bëi mét chuçi c¸c hµm trùc giao. Gi¶ sö C lµ ®êng bao cña ¶nh vµ C(i,j) lµ ®iÓm thø i trªn ®êng bao, i = 1,

2,..., N (®êng bao gåm N ®iÓm).

Gi¶ sö tiÕp :

x0 =

1

N i 1

N

=

∑ xi

y0 =

1

N i 1

N

=

∑ yi

lµ to¹ ®é t©m ®iÓm. Nh vËy, moment trung t©m bËc p, q cña ®êng bao lµ:

µpq =

1

N i 1

N

=

∑ (xi-x0)

p

(yi-y0)

q

(7.1)

VÐct¬ tham sè trong trêng hîp nµy chÝnh lµ c¸c moment µij víi i=1, 2,...,p vµ j=1, 2,...,q. Cßn trong sè c¸c ®Æc

trng h×nh häc, ngêi ta hay sö dông chu tuyÕn , ®êng bao, diÖn tÝch vµ tØ lÖ T = 4πS/p2

, víi S lµ

diÖn tÝch, p lµ chu tuyÕn.

ViÖc lùa chän ph¬ng ph¸p biÓu diÔn sÏ lµm ®¬n gi¶n c¸ch x©y dùng. Tuy nhiªn, viÖc lùa chän ®Æc trng nµo lµ

hoµn toµn phô thuéc vµo øng dông. ThÝ dô , trong nhËn d¹ng ch÷ (sÏ tr×nh bµy sau), c¸c tham sè lµ c¸c dÊu hiÖu:

- sè ®iÓm ch¹c ba, ch¹c t,

- sè ®iÓm chu tr×nh,

- sè ®iÓm ngoÆt,

- sè ®iÓm kÕt thóc,

NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 165

Ch¬ng B¶y: nhËn d¹ng ¶nh

•

ch¼ng h¹n víi ch÷ t • • cã 4 ®iÓm kÕt thóc, 1 ®iÓm ch¹c t,...

•

• M« h×nh cÊu tróc: C¸ch tiÕp cËn cña m« h×nh nµy dùa vµo viÖc m« t¶ ®èi tîng nhê mét sè kh¸i niÖm biÓu thÞ c¸c

®èi tîng c¬ së trong ng«n ng÷ tù nhiªn. §Ó m« t¶ ®èi tîng, ngêi ta dïng mét sè d¹ng nguyªn thuû nh ®o¹n th¼ng,

cung, v,...,v. Ch¼ng h¹n mét h×nh ch÷ nhËt ®îc ®Þnh nghÜa gåm 4 ®o¹n th¼ng vu«ng gãc víi nhau tõng ®«i mét.

Trong m« h×nh nµy ngêi ta sö dông mét bé kÝ hiÖu kÕt thóc Vt, mét bé kÝ hiÖu kh«ng kÕt thóc gäi lµ Vn. Ngoµi ra cã

dïng mét tËp c¸c luËt s¶n xuÊt ®Ó m« t¶ c¸ch x©y dùng c¸c ®èi tîng phï hîp dùa trªn c¸c ®èi tîng ®¬n gi¶n h¬n

hoÆc ®èi tîng nguyªn thuû (tËp Vt). Trong c¸ch tiÕp cËn nµy, ta chÊp nhËn mét kh¼ng ®inh lµ: cÊu tróc mét d¹ng lµ

kÕt qu¶ cña viÖc ¸p dông luËt s¶n xuÊt theo theo nh÷ng nguyªn t¾c x¸c ®Þnh b¾t ®Çu tõ mét d¹ng gèc b¾t ®Çu. Mét

c¸ch h×nh thøc, ta cã thÓ coi m« h×nh nµy t¬ng ®¬ng mét v¨n ph¹m G = (Vt, Vn, P, S) víi:

- Vt lµ bé ký hiÖu kÕt thóc,

- Vn lµ bé ký hiÖu kh«ng kÕt thóc,

- P lµ luËt s¶n xuÊt,

- S lµ d¹ng (ký hiÖu b¾t ®Çu).

ThÝ dô, ®èi tîng nhµ gåm m¸i vµ têng, m¸i lµ mét tam gi¸c gåm 3 c¹nh lµ 3 ®o¹n th¼ng, têng lµ mét h×nh ch÷ nhËt gåm

4 c¹nh vu«ng gãc víi nhau tõng ®«i mét sÏ ®îc m« t¶ th«ng qua cÊu tróc m« t¶ dùa vµo v¨n ph¹m sinh nh chØ ra trong

h×nh 7.1 díi ®©y.

(1) (2) Nhµ

(3)

M¸i Têng

(6) (4)

§ä¹n 1 §o¹n 2 §o¹n 3 §o¹n 3 §o¹n 4 §o¹n 5 §o¹n 6

(5)

H×nh 7.1 M« h×nh cÊu tróc cña mét ®èi tîng nhµ.

7.1.2.2 B¶n chÊt cña qu¸ tr×nh nhËn d¹ng

Qu¸ tr×nh nhËn d¹ng gåm 3 giai ®o¹n chÝnh:

- Lùa chän m« h×nh biÓu diÔn ®èi tîng.

- Lùa chän luËt ra quyÕt ®Þnh (ph¬ng ph¸p nhËn d¹ng) vµ suy diÔn qu¸ tr×nh häc.

- Häc nhËn d¹ng.

Khi m« h×nh biÓu diÔn ®èi tîng ®· ®îc x¸c ®Þnh, cã thÓ lµ ®Þnh lîng (m« h×nh tham sè) hay ®Þnh tÝnh (m« h×nh

cÊu tróc), qu¸ tr×nh nhËn d¹ng chuyÓn sang giai ®o¹n häc. Häc lµ giai ®o¹n rÊt quan träng. Thao t¸c häc nh»m c¶i thiÖn,

®iÒu chØnh viÖc ph©n ho¹ch tËp ®èi tîng thµnh c¸c líp.

ViÖc nhËn d¹ng chÝnh lµ t×m ra quy luËt vµ c¸c thuËt to¸n ®Ó cã thÓ g¸n ®èi tîng vµo mét líp hay nãi mét c¸ch

kh¸c g¸n cho ®èi tîng mét tªn.

Häc cã thµy (supervised learning)

NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 166

Ch¬ng B¶y: nhËn d¹ng ¶nh

Kü thuËt ph©n lo¹i nhê kiÕn thøc biÕt tríc gäi lµ häc cã thµy. §Æc ®iÓm c¬ b¶n cña kü thuËt nµy lµ ngêi ta cã

mét th viÖn c¸c mÉu chuÈn. MÉu cÇn nhËn d¹ng sÏ ®îc ®em s¸nh víi mÉu chuÈn ®Ó xem nã thuéc lo¹i nµo. ThÝ dô nh

trong mét ¶nh viÔn th¸m, ngêi ta muèn ph©n biÖt mét c¸nh ®ång lóa, mét c¸nh rõng hay mét vïng ®Êt hoang mµ ®· cã

c¸c miªu t¶ vÒ c¸c ®èi tîng ®ã. VÊn ®Ò chñ yÕu lµ thiÕt kÕ mét hÖ thèng ®Ó cã thÓ ®èi s¸nh ®èi tîng trong ¶nh víi mÉu

chuÈn vµ quyÕt ®Þnh g¸n cho chóng vµo mét líp. ViÖc ®èi s¸nh nhê vµo c¸c thñ tôc ra quyÕt ®Þnh dùa trªn mét c«ng cô

gäi lµ hµm ph©n líp hay hµm ra quyÕt ®Þnh. Hµm nµy sÏ ®îc ®Ò cËp trong phÇn sau.

Häc kh«ng cã thµy(unsupervised learning)

Kü thuËt häc nµy ph¶i tù ®Þnh ra c¸c líp kh¸c nhau vµ x¸c ®Þnh c¸c tham sè ®Æc trng cho tõng líp. Häc kh«ng

cã thµy ®¬ng nhiªn lµ khã kh¨n h¬n. Mét mÆt, do sè líp kh«ng ®îc biÕt tríc, mÆt kh¸c nh÷ng ®Æc trng cña c¸c líp còng

kh«ng biÕt tríc. Kü thuËt nµy nh»m tiÕn hµnh mäi c¸ch gép nhãm cã thÓ vµ chän lùa c¸ch tèt nhÊt. B¾t ®Çu tõ tËp d÷

liÖu, nhiÒu thñ tôc xö lý kh¸c nhau nh»m ph©n líp vµ n©ng cÊp dÇn ®Ó ®¹t ®îc mét ph¬ng ¸n ph©n lo¹i. Mét sè kü thuËt

tù häc sÏ ®îc tr×nh bµy trong phÇn 7.2.4.

Nh×n chung, dï lµ m« h×nh nµo vµ kü thuËt nhËn d¹ng ra sao, mét hÖ thèng nhËn d¹ng cã thÓ tãm t¾t theo s¬ ®å

sau:

TrÝch chän ®Æc tÝnh Ph©n líp tr¶ lêi §¸nh

biÓu diÔn ®èi tîng ra quyÕt ®Þnh gi¸

Qu¸ tr×nh tiÒn xö lý Khèi nhËn d¹ng

H×nh 7.2 S¬ ®å tæng qu¸t mét hÖ nhËn d¹ng.

7.2 nhËn d¹ng dùa trªn ph©n ho¹ch kh«ng gian

Trong kü thuËt nµy, c¸c ®èi tîng nhËn d¹ng lµ c¸c ®èi tîng ®Þnh lîng. Mçi ®èi tîng ®îc biÓu diÔn bëi mét

vÐct¬ nhiÒu chiÒu. Tríc tiªn, ta xem xÐt mét sè kh¸i niÖm nh: ph©n ho¹ch kh«ng gian, hµm ph©n biÖt sau ®ã sÏ ®i vµo

mét sè kü thuËt cô thÓ.

7.2.1 Ph©n ho¹ch kh«ng gian

Gi¶ sö kh«ng gian ®èi tîng X ®îc ®Þnh nghÜa : X = {Xi, i=1, 2,...,m}, Xi lµ mét vÐct¬. Ngêi ta nãi p lµ mét

ph©n ho¹ch cña kh«ng gian X thµnh c¸c líp Ci, Ci ⊂ X nÕu:

Ci ∩ Cj = víi i ≠ j vµ ∪ Ci = X

Nãi chung, ®©y lµ trêng hîp lý tëng: tËp X t¸ch ®îc hoµn toµn. Trong thùc tÕ, thêng gÆp kh«ng gian biÓu diÔn

t¸ch ®îc tõng phÇn. Nh vËy ph©n lo¹i lµ dùa vµo viÖc x©y dùng mét ¸nh x¹ f: X ---> p. C«ng cô x©y dùng ¸nh x¹

nµy lµ c¸c hµm ph©n biÖt (Descriminant functions).

7.2.2 Hµm ph©n líp hay hµm ra quyÕt ®Þnh

§Ó ph©n ®èi tîng vµo c¸c líp, ta ph¶i x¸c ®Þnh sè líp vµ ranh giíi gi÷a c¸c líp ®ã. Hµm ph©n líp hay hµm

ph©n biÖt lµ mét c«ng cô rÊt quan träng. Gäi {gi} lµ líp c¸c hµm ph©n líp. Líp hµm nµy ®îc ®Þnh nghÜa nh sau:

nÕu ∀ i ≠ k, gk(X) > gi(X) th× ta quyÕt ®Þnh X ∈ líp k.

Nh vËy ®Ó ph©n biÖt k líp, ta cÇn k-1 hµm ph©n biÖt. Hµm ph©n biÖt g cña mét líp nµo ®ã thêng dïng lµ hµm tuyÕn tÝnh,

cã nghÜa lµ:

NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 167