結(jié)構(gòu)模式識別

用模式的基本組成元素（基元）及其相互間的結(jié)構(gòu)關(guān)系對模式進(jìn)行描述和識別的方法結(jié)構(gòu)模式識別01基本信息與傳統(tǒng)的區(qū)別識別系統(tǒng)基本原理優(yōu)點(diǎn)與缺點(diǎn)目錄03050204基本信息對于比較復(fù)雜的模式，把它作為一個(gè)整體進(jìn)行分類是相當(dāng)困難的，這就需要把它分解為若干較簡單的子模式，而子模式又分解為若干基元，然后，通過對基元的識別，來識別子模式，最終達(dá)到識別模式的目標(biāo)，這樣對模式進(jìn)行識別的方法，稱為結(jié)構(gòu)模式識別。簡言之，結(jié)構(gòu)模式識別是用模式的基本組成元素（基元）及其相互間的結(jié)構(gòu)關(guān)系對模式進(jìn)行描述和識別的方法。在多數(shù)情況下，可以有效地用形式語言理論中的文法表示模式的結(jié)構(gòu)信息，因此也常稱為句法模式識別。一個(gè)結(jié)構(gòu)摸式識別系統(tǒng)可認(rèn)為由三個(gè)主要部分組成，它們分別是預(yù)處理、模式描述、語法分析?；拘畔⒒拘畔⒔Y(jié)構(gòu)模式識別又稱句法模式識別，它采用一些比較簡單的子模式組成多級結(jié)構(gòu)來描述一個(gè)復(fù)雜模式，先將模式分為子模式，子模式又分為更簡單的子模式，依次分解，直至在某個(gè)研究水平上不再需要細(xì)分。最后一級最簡單的子模式稱為模式基元，識別模式基元比識別原模式要簡單得多。結(jié)構(gòu)模式識別主要突出模式的結(jié)構(gòu)信息，常用于以結(jié)構(gòu)特征為主的目標(biāo)識別中，例如指紋、染色體和漢字識別等。圖7-1所示是一個(gè)模式多級分解的例子。圖7-1結(jié)構(gòu)模式識別法將觀察對象表達(dá)為一個(gè)由基元組成的句子，將模式類表達(dá)為由有限或無限個(gè)具有相似結(jié)構(gòu)特性的模式組成的集合。基元構(gòu)成模式所遵循的規(guī)則即為文法，或稱句法。與統(tǒng)計(jì)模式識別類似，用已知類別的訓(xùn)練樣本進(jìn)行學(xué)習(xí)，產(chǎn)生該類或至少是這些樣本的文法，這個(gè)學(xué)習(xí)和訓(xùn)練過程稱為文法推斷。結(jié)構(gòu)模式識別方法立足于分析模式的結(jié)構(gòu)信息，至今比較成功的是句法結(jié)構(gòu)模式識別方法。句法結(jié)構(gòu)模式識別方法是美籍平人傅京孫教授提出的，它將物體的結(jié)構(gòu)視為基元（primitives），采用規(guī)則或語法（rule，grammar）函數(shù)作為識別函數(shù)，選擇接受錯(cuò)誤率作為準(zhǔn)則函數(shù)，進(jìn)行模式識別。基本原理基本原理圖9-13結(jié)構(gòu)模式識別亦稱句法模式識別。所謂句法，是描述語言規(guī)則的一種法則。一個(gè)完整的句子一定由主語+謂語或主語+謂語+賓語（或表語）的基本結(jié)構(gòu)構(gòu)成；一種特定的語言，一定類型的句子，應(yīng)有一定的結(jié)構(gòu)順序。無規(guī)則的任意組合，必然達(dá)不到正確的思想交流。形容詞、副詞、冠詞等可以與名詞、動詞構(gòu)成“短語”，豐富句子要表達(dá)的思想內(nèi)容。而這短語的構(gòu)成也是有特定規(guī)律的。如果用一個(gè)樹狀結(jié)構(gòu)來描述一個(gè)句子，則如圖9-13所示。只有按照上述層狀結(jié)構(gòu)規(guī)則（或稱為寫作規(guī)則）才能組合成一定規(guī)則的句子，讀者或聽眾才能正確理解你所表達(dá)的思想。

圖9-14自然句法規(guī)則的思想怎樣用于模式識別呢？自然界的景物組合是千變?nèi)f化的，但仔細(xì)分析某一對象的結(jié)構(gòu)，也存在一些不變的規(guī)則。分析圖9-14（a）所示的一座房子。它一定是由屋頂和墻面構(gòu)成的，組成屋頂?shù)膸缀螆D像，可以是三角形、梯形、四邊形、圓形等。組成墻平面的幾何圖像也是由矩形、平行四邊形（透視效果）等構(gòu)成，至少有一個(gè)墻面應(yīng)該有門，而窗在高度上不低于門，等等。你還可以進(jìn)一步提出一些用來刻畫構(gòu)成一棟房子的規(guī)則，如屋頂一定在墻面之上，且由墻面支承等。一棟房子的這些規(guī)則就像構(gòu)成一個(gè)句子的句法規(guī)則一樣，是不能改變的，如果將描述房子的規(guī)則（構(gòu)成一棟房子的模式）存于計(jì)算機(jī)，若我們的任務(wù)是要在一張風(fēng)景照照片上去識別有無房子，那么你可以按照照片上所有景物的外形匹配是否符合房子的模式（房子構(gòu)成規(guī)則符合房子模式的就輸出為“有房子”，否則，輸出“無房子”）。與傳統(tǒng)的區(qū)別與傳統(tǒng)的區(qū)別表1-1給出了統(tǒng)計(jì)模式識別和結(jié)構(gòu)模式識別的異同比較。統(tǒng)計(jì)模式識別與結(jié)構(gòu)模式識別最本質(zhì)的區(qū)別有兩點(diǎn)：①統(tǒng)計(jì)模式識別中的特征描述是定量描述，結(jié)構(gòu)模式識別的特征描述由子模式給出；②統(tǒng)計(jì)模式識別是以不同類別之間的特征量的不同來分類，結(jié)構(gòu)模式識別采用文法，通過定義描述類結(jié)構(gòu)的“語言”來完成模式識別的。從表1-1可以看出：統(tǒng)計(jì)模式識別和結(jié)構(gòu)模式識別在不同方面，各自有著自己的優(yōu)點(diǎn)，也存在著一定的不足。結(jié)構(gòu)模式識別在描述與分類的過程中是基于領(lǐng)域知識的，傳統(tǒng)的結(jié)構(gòu)模式識別方法應(yīng)用于新領(lǐng)域是受限的。因此，關(guān)于結(jié)構(gòu)句法模式識別，最大的問題是沒有提取數(shù)據(jù)結(jié)構(gòu)子模式的一般化方法。在模式識別的著作中，幾乎很少提及原始數(shù)據(jù)結(jié)構(gòu)特征選擇問題，而大部分工作集中在描述特定領(lǐng)域的模式識別過程。例如，F(xiàn)riedman這樣強(qiáng)調(diào)他的觀點(diǎn)：原始特征選擇，并基于此特征得到的模式，依賴于數(shù)據(jù)類型與相關(guān)的應(yīng)用。Nadler支持該觀點(diǎn)：一般根據(jù)設(shè)計(jì)者的經(jīng)驗(yàn)、直覺與智慧提取特征。缺乏一般化的特征提取與描述方法，使結(jié)構(gòu)模式識別研究者們陷入了困境，并阻礙了結(jié)構(gòu)模式識別的進(jìn)程與發(fā)展。為了克服這種限制，建立一種與領(lǐng)域知識無關(guān)的數(shù)據(jù)結(jié)構(gòu)子模式提取方法勢在必行。

基于對大量文獻(xiàn)的分析，研究者發(fā)現(xiàn)有兩個(gè)重要的問題需要研究：①沒有一種與領(lǐng)域知識無關(guān)的數(shù)據(jù)結(jié)構(gòu)的特征提取方法；②將統(tǒng)計(jì)與句法相結(jié)合的混合分類器的研究還沒有突破性成果。

混合方法指的是將統(tǒng)計(jì)模式識別與結(jié)構(gòu)模式識別相結(jié)合的一種統(tǒng)一的方法，混合方法保留每一種模式識別方法的優(yōu)勢而避開了各自的不足。那么，在統(tǒng)計(jì)與結(jié)構(gòu)的混合分類器設(shè)計(jì)過程中，基于統(tǒng)計(jì)知識來實(shí)現(xiàn)結(jié)構(gòu)子模式的描述是一種可行的方法。優(yōu)點(diǎn)與缺點(diǎn)優(yōu)點(diǎn)與缺點(diǎn)結(jié)構(gòu)模式識別又稱結(jié)構(gòu)方法或語言學(xué)方法。結(jié)構(gòu)模式識別理論是早期漢字識別研究的主要方法，其思想是先把漢字圖像劃分為很多個(gè)基元組合，再用結(jié)構(gòu)方法描述這些基元組合所代表的結(jié)構(gòu)和關(guān)系。通常抽取筆段或基本筆畫作為基元，由這些基元及其組合關(guān)系可以精確地對漢字加以描述，最后利用形式語言及自動機(jī)理論進(jìn)行文法推斷，即識別。

結(jié)構(gòu)模式識別方法地主要優(yōu)點(diǎn)是對字體變化的適應(yīng)性強(qiáng)，區(qū)分相似字能力強(qiáng)，缺點(diǎn)是抗干擾能力差，從漢字圖像中精確地抽取基元、輪廊，特征點(diǎn)比較困難，匹配過程復(fù)雜，若采用漢字輪廓結(jié)構(gòu)信息作為特征，則需要進(jìn)行松弛迭代匹配，耗時(shí)太長，而對于筆畫較為模糊的漢字圖像，抽取輪廓會遇到極大的麻煩。若采用抽取漢字圖像中關(guān)鍵特征點(diǎn)來描述漢字，則特征點(diǎn)的抽取易受噪聲點(diǎn)、筆畫的粘連與斷裂等影響，總之，單純采用結(jié)構(gòu)模式識別方法的印刷體漢字識別系統(tǒng)的識別率是很低的。

識別系統(tǒng)識別系統(tǒng)圖9-29一個(gè)結(jié)構(gòu)摸式識別系統(tǒng)可認(rèn)為由三個(gè)主要部分組成，它們分別是預(yù)處理、模式描述、語法分析。該系統(tǒng)的簡單框圖如圖9-29所示。每一種經(jīng)過預(yù)處理的模式，在模式描述階段被表示成類語句結(jié)構(gòu)（例如一個(gè)串、一個(gè)圖）。這一階段的處理包括兩部分：①模式分割；②基元抽取。為了將一個(gè)模式用若干子模式來表示，我們應(yīng)該對該模式予以分割，與此同時(shí)，抽取基元和基元間的關(guān)系。換言之，每一種經(jīng)過預(yù)處理的模式，均按照預(yù)先制訂的語法或合成操作規(guī)則，分割為子模式。進(jìn)而，每一種子模式分割為一組基元。當(dāng)然，若待識模式較簡單，則也可以直接分割為基元。例如，借助于鏈接操作，每一種模式可用一串鏈接起來的基元表示。在語法分析階段，系統(tǒng)應(yīng)對已完成描述的模式作語法檢查，以判定它是按何種語法結(jié)合成的，從而完成待識模式的分類。

一般說來，識別的最簡單的方式可能是“樣板匹配”。用表示一種輸入模式的基元串與各種模型（也是用基元串表示的）相比較，按照選定的匹配準(zhǔn)則，輸入模式被劃入匹配“最好”的那一類。在這種“樣板匹配”方式下，層次結(jié)構(gòu)信息基本上不予考慮。上述“樣板匹配”是一種方法，另一種