結構模式識別

對於比較複雜的模式,把它作為一個整體進行分類是相當困難的，這就需要把它分解為若干較簡單的子模式，而子模式又分解為若干基元，然後，通過對基元的識別,來識別子模式，最終達到識別模式的目標，這樣對模式進行識別的方法，稱為結構模式識別。

簡言之，結構模式識別是用模式的基本組成元素（基元）及其相互間的結構關係對模式進行描述和識別的方法。在多數情況下，可以有效地用形式語言理論中的文法表示模式的結構信息，因此也常稱為句法模式識別。

一個結構摸式識別系統可認為由三個主要部分組成，它們分別是預處理、模式描述、語法分析。

基本介紹

• 中文名：結構模式識別
• 外文名：structural pattern recognation
• 性質：描述和識別的方法
• 途徑：基元及其相互間的結構關係
• 又名：句法模式識別

概述

結構模式識別又稱句法模式識別，它採用一些比較簡單的子模式組成多級結構來描述 一個複雜模式，先將模式分為子模式.子模式又分為更簡單的子模式，依次分解，直至在 某個研究水平上不再需要細分.最後一級最簡單的子模式稱為模式基元，識別模式基元比識別原模式要簡單得多.

結構模式識別主要突出模式的結構信息，常用於以結構特徵為主的目標識別中，例如指紋、染色體和漢字識別等.

圖7 -1所示是一個模式多級分解的例子.

結構模式識別法將觀察對象表達為一個由基元組成的句子，將模式類表達為由有限或無限個具有相似結構特性的模式組成的集合。基元構成模式所遵循的規則即為文法.或稱句法.與統計模式識別類似，用已知類別的訓練樣本進行學習，產生該類或至少是這些樣本的文法，這個學習和訓練過程稱為文法推斷。

結構模式識別方法立足於分析模式的結構信息，至今比較成功的是句法結構模式識別方法。句法結構模式識別方法是美籍平人傅京孫教授提出的，它將物體 的結構視為基元（primitives)，採用規則或語法（rule，grammar)函式作為識別函式， 選擇接受錯誤率作為準則函式，進行模式識別。在這個方法中，把模式的分層結構類比於語言中句子的構造，這樣，就可利用形式語言學的理論來分析模式。句子由單詞按文法規則構成，同樣,模式由一些模式基元按一定的結構規則組合而成，分析模式如何由基元構成的規則就是結構分析的內容,這相當於在形式語言學中對一個句子作句法分析。句法結構模式識別就是檢査代表這個模式的句子是否符合事先規定的某一類文法規則。如果符合，那么這個模式就屬於這個文法所代表的那個模式類。除了分類信息外，句法結構模式識別方法還能給出模式的結構信息， 它為模式識別提供了用簡單的、有限的模式基元和文法規則的有限集來描述一個複雜模式大（可能是無限的）集合的可能性。

基本原理

結構模式識別亦稱句法模式識別.所謂句法，是描述語言規則的一種法則.一個完整的句 子一定由主語+謂語或主語+謂語+賓語（或表語）的基本結構構成；—種特定的語言，一定類型的句子，應有一定的結構順序.無規則的任意組合，必然達不到正確的思想交流。形容詞、副詞、 冠詞等可以與名詞、動詞構成“短語”，豐富句子要表達的思想內容。而這短語的構成也是有特定 規律的。如果用一個樹狀結構來描述一個句子，則如圖9-13所示。

只有按照上述層狀結構規則（或稱為寫作規則）才能組合成一定規則的句子，讀者或聽眾才能正確理解你所表達的思想。

自然句法規則的思想怎樣用於模式識別呢？自然界的景物組合是千變萬化的，但仔細分析某一對象的結構，也存在一些不變的規則。分析圖9-14（a）所示的一座房子。它一定是由屋頂 和牆面構成的，組成屋頂的幾何圖像，可以是三角形、梯形、四邊形、圓形等。組成牆平面的幾何圖像也是由矩形、平行四邊形（透視效果）等構成，至少有一個牆面應該有門，而窗在高度上不低於門，等等。你還可以進一步提出一些用來刻畫構成一棟房子的規則，如屋頂一定在牆面之上，且由牆面支承等。一棟房子的這些規則就像構成一個句子的句法規則一樣.是不能改變的，如果將描述房子的規則（構成一棟房子的模式)存於計算機，若我們的任務是要在一張風景照照片上去識別有無房子，那么你可以按照照片上所有景物的外形匹配是否符合房子的模式（房子構成規則符合房子模式的就輸出為“有房子”，否則，輸出“無房子”。如果風景照片上有一棵樹，如圖 9-14 （b）所示，儘管頂部有三角形存在，也能尋找到一個支撐的矩形，但卻找不到有“門”存在，這不符合一棟房子的結構規則，因而不會把它當成是一棟房子。

可見，結構模式識別是以形式語言為理論基礎的，它將一個複雜的模式分解成一系列更簡單的模式（子模式），對子模式繼續分解，最後分解成最簡單的子模式（或稱基元）.藉助於一種形式語言對模式的結構進行描述，從而識別圖像.模式、子模式、基元類似於英文句子的短語、單詞、字母.這種識別方法類似語言的句法結構分析.因此稱為句法模式識別.

句法模式識別系統框圖如圖9-15所示，它由識別和分析兩部分組成。

分析部分包括基元的選擇和句法推斷。分析部分是用一些已知結構信息的圖像作為訓練樣本.構造出一些句法規則。它類似於統計分類法中的“學習”過程。

識別部分包括預處理、分割描述、基元提取和結構分析。預處理主要包括編碼、增強等系列操作。結構分析是用學習所得的句法規則對未知結構信息的圖像所表示的句子進行句法分析。如果能夠被抑制結構信息的句法分析出來.那么這個未知圖像就有這種結構信息，否則，就不具 有這種結構。

與傳統的區別

表1-1給出了統計模式識別和結構模式識別的異同比較。統計模式識別與結構模式識別最本質的區別有兩點:①統計模式識別中的特徵描述是定量描述，結 構模式識別的特徵描述由子模式給出；②統計模式識別是以不同類別之間的特徵量的不同來分類，結構模式識別採用文法，通過定義描述類結構的“語言"來完成模式識別的。從表1-1可以看出：統計模式識別和結構模式識別在不同方面，各自有著自己的優點，也存在著一定的不足。結構模式識別在描述與分類的過程中是基於領域知識的，傳統的結構模式識別方法套用於新領域是受限的。因此，關於結構句法模式識別，目前最大的問題是沒有提取數據結構子模式的一般化方法。 在模式識別的著作中，幾乎很少提及原始數據結構特徵選擇問題，而大部分工作集中在描述特定領域的模式識別過程。例如，Friedman這樣強調他的觀點：原始特徵選擇，並基於此特徵得到的模式，依賴於數據類型與相關的套用。Nadler支持該觀點:一般根據設計者的經驗、直覺與智慧提取特徵。缺乏一般化的特徵提取與描述方法，使結構模式識別研究者們陷入了困境，並阻礙了結構模式識別的進程與發展。為了克服這種限制，建立一種與領域知識無關的數據結構子模式提取方法勢在必行。

基於對大量文獻的分析，研究者發現有兩個重要的問題需要研究:①沒有一種與領域知識無關的數據結構的特徵提取方法;②將統計與句法相結合的混合分類器的研究還沒有突破性成果。

混合方法指的是將統計模式識別與結構模式識別相結合的一種統一的方法， 混合方法保留每一種模式識別方法的優勢而避開了各自的不足。那么，在統計與結構的混合分類器設計過程中，基於統計知識來實現結構子模式的描述是一種可行的方法。如何將統計模式識別與結構模式識別結合,發揮各自特長，使統計模式識別與結構模式識別兩種方法得以統一，進而完成混合分類器最佳化算法的設計與實現，將是一個新的問題。

優點與缺點

結構模式識別又稱結構方法或語言學方法。結構模式識別理論是早期漢字識別研究的主要方法， 其思想是先把漢字圖像劃分為很多個基元組合，再用結構方法描述這些基元組合所代表的結構和關 系。通常抽取筆段或基本筆畫作為基元，由這些基元及其組合關係可以精確地對漢字加以描述，最後利用形式語言及自動機理論進行文法推斷，即識別。

結構模式識別方法地主要優點是對字型變化的適應性強，區分相似字能力強，缺點是抗干擾能力差，從漢字圖像中精確地抽取基元、輪廊.特徵點比較困難，匹配過程複雜，若採用漢字輪廓結構信息作為特徵，則需要進行鬆弛疊代匹配，耗時太長，而對於筆畫較為模糊的漢字圖像，抽取輪廓會遇到極大的麻煩。若採用抽取漢字圖像中關鍵特徵點來描述漢字，則特徵點的抽取易受噪聲點、 筆畫的粘連與斷裂等影響，總之，單純採用結構模式識別方法的印刷體漢字識別系統的識別率是很低的。

識別系統

一個結構摸式識別系統可認為由三個主要部分組成，它們分別是預處理、模式描述、語法分析。該系統的簡單框圖如圖9-29所示。

每一種經過預處理的模式，在模式描述階段被表示成類語句結構（例如一個串、一個 圖）。這一階段的處理包括兩部分：①模式分割；②基元抽取。為了將一個模式用若干子模 式來表示，我們應該對該模式予以分割，與此同時.抽取基元和基元間的關係。換言之，每一種經過預處理的模式，均按照預先制訂的語法或合成操作規則，分割為子模式。進而，每一種子模式分割為一組基元。當然，若待識模式較簡單，則也可以直接分割為基元。例如，藉助於連結操作，每一種模式可用一串連結起來的基元表示。在語法分析階段，系統應對已完成描述的模式作語法檢査，以判定它是按何種語法結合成的，從而完成待識模式的分類。

一般說來，識別的最簡單的方式可能是“樣板匹配"。用表示一種輸入模式的基元串與 各種模型（也是用基元串表示的）相比較，按照選定的匹配準則，輸入模式被劃入匹配 “最好”的那一類。在這種“樣板匹配”方式下，層次結構信息基本上不予考慮。上述“樣板匹配”是一種方法，另一種識別方法是研究全部層次結構信息。此外還有若干介於這兩種方法之間的研究方法。例如，設計一系列測試，以測定某些子模式（或某些基元）是否存在，或測定某些子模式的特定組合（或某些基元的特定組合）是否存在，測定的結果， 用作分類判決。注意，這裡所說的一次測試，可以是一次樣板匹配，也可以是對表達一個子模式的一棵子樹的分析。要知道：識別方法的選取，通常取決於待識別的模式，若識別要求完整的模式描述，就要分析全部層次結構信息，反之就可用較簡單的方法提高識別過程的效率.避免作完整的層次結構分析。

一類模式的結構信息，要有一個文法來推述（實際上就是描述該類的結構，以與其他類相區別），這就需要文法推理，它能從給它的訓練模式集中，歸納出一個文法，這類似於統計模式識別中用樣本來訓練判決函式。從圖9-29可以看出，一類樣品被送入語法推理機構，形成了該類的結構描述，作為語法分析機構入口之一的“樣板”（如果按前面所說用樣板匹配的話），或是層次結構分析的“文法”（如果用前述的層次結構分析）。其實，更廣義的學習，還應包括基元的位置選定，這也是該推理機構的一種能力。