基于原型匹配的模式識(shí)別方法

1、基于原型匹配的模式識(shí)別方法（計(jì)算機(jī)學(xué)院張仰銳3120602007）摘要：現(xiàn)有的模式識(shí)別主要基于事物的區(qū)分機(jī)理，而不是基于認(rèn)知機(jī)理。文中結(jié)合認(rèn)知心理學(xué)中有關(guān)模式識(shí)別的研究成果，提出了一種基于原型匹配的模式識(shí)別方法，給出了該方法的識(shí)別機(jī)理、數(shù)學(xué)模型和識(shí)別算法。該方法將一個(gè)模式識(shí)別問(wèn)題定義為由原型、結(jié)構(gòu)、組合法則構(gòu)成，由這三要素組成原型庫(kù)和知識(shí)庫(kù)對(duì)被識(shí)別客體進(jìn)行識(shí)別,對(duì)數(shù)字字符圖像識(shí)別問(wèn)題的實(shí)驗(yàn)結(jié)果表明了文中方法的有效性。關(guān)鍵詞：模式識(shí)別認(rèn)知系統(tǒng)原型覆蓋引言認(rèn)知心理學(xué)興起于20世紀(jì)50年代中期，以信息加工理論為核心，是認(rèn)知科學(xué)的主要組成部分。人的視知覺(jué)是指對(duì)外界刺激投射到視網(wǎng)膜中的圖像進(jìn)行處理以獲得

2、對(duì)外部世界感知的過(guò)程，其實(shí)質(zhì)是把外界客體的明暗、顏色、位置、深度和長(zhǎng)寬等特性映射到視知覺(jué)空間中，然后對(duì)這些特性在視知覺(jué)空間中所形成的象的“形狀”進(jìn)行分析，實(shí)現(xiàn)對(duì)外界客體的識(shí)別。顯然，視知覺(jué)空間是一個(gè)描述空間，視知覺(jué)是一個(gè)把外界客體映射到描述空間并獲得外界客體描述的過(guò)程。認(rèn)知心理學(xué)關(guān)于模式識(shí)別的研究成果主要有:模板匹配理論、特征匹配理論和原型匹配理論，它們?cè)跈C(jī)器模式識(shí)別的應(yīng)用都是對(duì)對(duì)象的一種描述方法，沒(méi)有本質(zhì)的區(qū)別。模板匹配理論和特征匹配理論已經(jīng)廣泛應(yīng)用于機(jī)器模式識(shí)別中，文中研究原型匹配在計(jì)算機(jī)識(shí)別中的應(yīng)用。1基于原型匹配的識(shí)別機(jī)理原型匹配理論指出任意模式都可由原型組成，原型是指一類客體的內(nèi)部表

3、征，即一個(gè)類別或范疇的所有個(gè)體的概括表征，代表某類客觀世界基本成分的抽象形式；當(dāng)一個(gè)外界刺激作用發(fā)生時(shí)，通過(guò)將外界刺激拆分成原型并與存儲(chǔ)的原型進(jìn)行匹配來(lái)實(shí)現(xiàn)對(duì)刺激的識(shí)別。相關(guān)的成分識(shí)別理論指出物體是由一些基本形狀或成分即幾何子組成的。因此，如何描述組成模式的原型或幾何子之間的關(guān)系，成為自下而上信息加工的一個(gè)問(wèn)題。把原型匹配理論應(yīng)用于計(jì)算機(jī)識(shí)別，將一個(gè)識(shí)別對(duì)象分解成各種原型，需解決原型之間的組成關(guān)系問(wèn)題。例如，文字“ear”和“are”都是由原型字母“a”、“e”、“r”組成，但因原型間的關(guān)系不同而組成了不同的文字。因此，在采用原型匹配理論進(jìn)行模式識(shí)別時(shí)，有必要對(duì)原型之間的關(guān)系進(jìn)行恰當(dāng)?shù)拿枋觥Ｎ?/p>

4、中用“結(jié)構(gòu)”來(lái)描述原型間的關(guān)系。相應(yīng)地，模式由原型和結(jié)構(gòu)組成。2數(shù)學(xué)模型在視知覺(jué)中，通過(guò)把外界客體映射到描述空間并分析外界客體在描述空間中所成的象的“形狀”來(lái)實(shí)現(xiàn)對(duì)外界客體的感知。視知覺(jué)的認(rèn)知機(jī)理表明，通過(guò)某種特定的映射，物體的識(shí)別可以在視知覺(jué)空間中完成。換言之，利用映射，任意模式的識(shí)別可以在某一特定的描述空間中實(shí)現(xiàn)。外界客體映射到描述空間中的“象”是一個(gè)或多個(gè)原型遵循某種“結(jié)構(gòu)”所形成的集合，是一個(gè)以原型和結(jié)構(gòu)為元素的點(diǎn)集。因此，基于原型匹配的模式識(shí)別實(shí)質(zhì)上是對(duì)外界客體映射到描述空間(拓?fù)淇臻g)中點(diǎn)集“形狀”的分析，是點(diǎn)集對(duì)應(yīng)問(wèn)題。點(diǎn)集拓?fù)鋵W(xué)是一門采用點(diǎn)集方法來(lái)研究空間結(jié)構(gòu)及空間圖形拓?fù)湫再|(zhì)

5、的學(xué)科，用集合來(lái)論述拓?fù)鋵W(xué)中一些需精確化描述的問(wèn)題。基于原型匹配的模式識(shí)別方法的理論分析工具是點(diǎn)集拓?fù)鋵W(xué)。某一特定環(huán)境e可以表述為一個(gè)可測(cè)物理量Ei(x)的集合:e=Ei(x)i=i,2，而待研究的“問(wèn)題范圍”是環(huán)境e的一個(gè)子集。q=f(X)v=l,2，那么對(duì)于確定的模式識(shí)別問(wèn)題，模式空間可表示為Q=Ev=fv(X)v=1,2,(1)式中:模式Ev是一個(gè)集合。對(duì)于已確定的模式識(shí)別問(wèn)題，原型來(lái)源于確定的原型集P，結(jié)構(gòu)來(lái)源于確定的結(jié)構(gòu)集S。模式由原型和結(jié)構(gòu)組成，根據(jù)點(diǎn)集拓?fù)鋵W(xué)知識(shí)，描述空間3也由原型及結(jié)構(gòu)組成。具體定義如下：P=L2(2)TOC o 1-5 h zS=SjI；=LX(V0=/(pi

6、t51p,P,呼S(4)如果存在一個(gè)連續(xù)映射g:Q-0，那么，模式空間Q中的模式Ev映射到描述空間3中的點(diǎn)集可表示為：a=g(Eu)(5)因此，一個(gè)模式識(shí)別問(wèn)題用原型Pv、結(jié)構(gòu)Sv和組合法則屮()描述為0口=卬(SJ)(6)根據(jù)式(1)(6)，n和t有界且對(duì)于EvQ有屮()恒定不變。描述空間0是一個(gè)拓?fù)淇臻g，是被識(shí)別客體的全體在0中所形成的“象”的集合,對(duì)模式Ev的識(shí)別就是在描述空間0中對(duì)點(diǎn)集Qv的“形狀”的理解。因此，基于原型匹配的模式識(shí)別方法的識(shí)別任務(wù)就是找到模式Ev映射到描述空間0中的象所形成的點(diǎn)集Qv的一個(gè)覆蓋。3識(shí)別算法基于原型匹配的模式識(shí)別方法是以解決模式空間與描述空間的點(diǎn)集映射問(wèn)

7、題為目標(biāo)的，識(shí)別的過(guò)程是一個(gè)構(gòu)建映射及尋求覆蓋的過(guò)程。定義被識(shí)別客體在描述空間0中的映射集斤=M=(陽(yáng)皿)IA-只罐S;k=lt2t皿(1)式中：ek表示被識(shí)別模式；對(duì)于已確定的識(shí)別客體，m有界。/m；全部覆蓋對(duì)COVER(ek)組成(P:S代入屮()，屮(P:SJ即為識(shí)別結(jié)果。4實(shí)驗(yàn)及結(jié)果分析文中以數(shù)字字符圖像(見(jiàn)圖1)為實(shí)驗(yàn)對(duì)象，考察數(shù)字字符圖像的識(shí)別問(wèn)題。嗎9271H0B圖】數(shù)字字符圖像圖1中包圍數(shù)字字符圖像外邊界的網(wǎng)格是原型分解和結(jié)構(gòu)分析的工具，網(wǎng)格把字符圖像平面劃分出9個(gè)區(qū)域(A、B、C、D、E、F、G、H、W)，它們確定了原型組合間的結(jié)構(gòu)，見(jiàn)圖2。圖2結(jié)構(gòu)區(qū)域?qū)嶒?yàn)步驟如下：(1)在

8、深入分析數(shù)字字符圖像基礎(chǔ)上構(gòu)建原型庫(kù)，如圖3所示.封閉曲線直線圖3數(shù)字字符原型(2)根據(jù)數(shù)字字符圖像的構(gòu)成信息建立知識(shí)庫(kù)。數(shù)字字符的組成原型及其結(jié)構(gòu)是識(shí)別中比較關(guān)鍵的先驗(yàn)知識(shí)。根據(jù)上述建立的原型集和結(jié)構(gòu)集，結(jié)合圖2中的結(jié)構(gòu)區(qū)域可求得全部數(shù)字字符的原型和結(jié)構(gòu)對(duì)應(yīng)關(guān)系的量化描述.以數(shù)字字符“2”為例說(shuō)明的生成過(guò)程，區(qū)域E中有一條弧線，區(qū)域C中有一條放置成45的直線，區(qū)域F中有一條水平放置的直線，那么=(p2,s5)，(p3,s3),(p3,s6)。同一原型在組成不同數(shù)字字符時(shí)其大小和位置需做出改變；對(duì)于同一個(gè)數(shù)字字符,其組成原型之間的交接處存在斜率突變，它們之間存在一個(gè)上下、左右的次序關(guān)系，這些都

9、屬于面幾何圖形的問(wèn)題。因此，組合法則屮()取平面幾何圖形的變換規(guī)則:平移、旋轉(zhuǎn)、先上后下、先左后右。輸入圖像在描述空間中的映射結(jié)合圖2中的結(jié)構(gòu)區(qū)域?qū)斎雸D像做原型分解和結(jié)構(gòu)分析，得到其在描述空間中的映射ek=(Pk,Sk)。取原型與輸入圖像的距離測(cè)度作為覆蓋度，兩者的最小距離為最佳覆蓋度。以14種不同大小(14磅、16磅、18磅、22磅、26磅、32磅、40磅、48磅、58磅、70磅、82磅、96磅、110鎊、124磅)的數(shù)字字符圖像為實(shí)驗(yàn)樣本集，實(shí)驗(yàn)結(jié)果如表1所示：表1數(shù)字字符圖像的識(shí)別結(jié)果Table1Recognitionresultsofdigitalcharacierinages字號(hào)，

10、磅拒識(shí)的數(shù)字字符識(shí)別率/%14K3S光K016V=光S0IS9022124100本實(shí)驗(yàn)的平均識(shí)別率取14種不同大小的數(shù)字字符識(shí)別率之和的平均值。根據(jù)表1,可計(jì)算得到平均識(shí)別率為96.4%。實(shí)驗(yàn)結(jié)果表明了文中識(shí)別方法的有效性。對(duì)于實(shí)驗(yàn)中的拒識(shí)問(wèn)題，這可能是在小字號(hào)情況下，各原型之間已失去了可區(qū)分的界定，此時(shí)進(jìn)行原型分解會(huì)得到錯(cuò)誤的原型.由于文中實(shí)驗(yàn)是對(duì)基于原型匹配理論的模式識(shí)別方法的原理性驗(yàn)證，因此，識(shí)別前的預(yù)處理不多，沒(méi)有進(jìn)行“標(biāo)配”預(yù)處理，即把所有輸入變換到同一標(biāo)準(zhǔn)環(huán)境，這也是出現(xiàn)拒識(shí)現(xiàn)象的原因。然而，實(shí)驗(yàn)基本達(dá)到了目的，在一定程度上驗(yàn)證了文中所提方法的有效性。5結(jié)語(yǔ)研究人類認(rèn)知機(jī)理并以機(jī)器實(shí)現(xiàn)一直是科學(xué)發(fā)展中最有意義的重大問(wèn)題。認(rèn)知科學(xué)作為一門研究人類心智的學(xué)科，目前已取得大量的研究成果。文中借鑒認(rèn)知科學(xué)的研究成果，提出了一種基于原型匹配的模式識(shí)別方法，該方法可以描述為:模式二原型+結(jié)構(gòu)。原型表示組成該模式的基本單元，結(jié)構(gòu)表示組成該模式的基本單元之間的關(guān)系。文中方法的識(shí)別實(shí)質(zhì)上是關(guān)于點(diǎn)集的不變性映射和點(diǎn)集“形狀”的分析及認(rèn)識(shí)的問(wèn)題;識(shí)別任務(wù)是以尋求被識(shí)別客體映射到描述空間中的象的一個(gè)最佳覆蓋為目標(biāo)；識(shí)別過(guò)程是一個(gè)包含原型分解、結(jié)構(gòu)判別及覆蓋的過(guò)程；理論分析工具是點(diǎn)集拓?fù)鋵W(xué)。實(shí)驗(yàn)結(jié)果表明了文中方法的有效性。參考文獻(xiàn)1張?jiān)迄i.