我們在前文《模式識別的基本概念與理論體系》中就已經提及“模式分類”。

具體內容看我的CSDN文章：模式識別的基本概念與理論體系-CSDN博客?

模式的識別方法主要有統計模式識別方法和結構模式識別方法兩大類。統計模式識別方法提出得較早，理論也較成熟，其要點是提取待識別模式的一組統計特征，然后按照一定準則所確定的決策函數進行分類判決。例如在漢字識別中，國外學者大多采用這種方法，從效果上看，對單一字體的漢字識別效果較好，但對不同字體混排的印刷資料，由于這種方法沒有考慮漢字的結構特征，因而很難適用。結構模式識別的要點是把待識別模式看作是由若干較簡單子模式構成的集合，每個子模式再分為若干基元，這樣，任何一個模式都可以用一組基元及一定的組合關系來描述，就像一篇文章由單字、詞、短語和句子按語法規則構成一樣，所以這種方法又稱為句法模式識別。用這種方法描述漢字字形結構是比較合適的，因此它在手寫漢字的識別方面已經得到了應用。把統計識別方法與結構識別方法結合起來是近年來發展的一種趨勢，它既可以吸取統計識別方法的優點，又可利用結構識別方法所得到的結構信息，可取得較好的識別效果。

另外，隨著模糊數學及人工智能中某些領域研究的發展，人們已開始逐漸將其有關技術應用于模式識別的各個環節之中。尤其是人工神經網絡所取得的成就以及它與模式識別的結合，使模式識別的研究進人了一個新的發展階段，出現了模糊模式識別及智能模式識別的提法。

接下來，我們將對統計模式識別、結構模式識別、模糊模式識別及智能模式識別進行討論。

有關“統計模式識別”的內容：統計模式識別理論與方法-CSDN博客?

結構模式識別通過分析模式的結構信息，將復雜模式分解為基本單元（基元），并利用文法規則描述基元間的組合關系，從而實現對模式的描述、分類與分析。相較于統計模式識別側重數值特征的統計分布，結構方法更關注模式的層次化結構和句法規則，適用于圖像、語言、化學分子等具有明顯結構特征的領域。

一、結構模式識別的基本過程

結構模式識別的核心是從“基元”到“模式”的層次化解析，其基本流程包括預處理與分割、基元抽取、文法建模、句法分析與識別四個關鍵步驟。

在上圖中，模式分割用于將模式劃分為若干子模式；基元及關系抽取用于選擇并抽取基

元和基元間的關系，并按事先制訂的語法或合成規則把模式用基元及其組合表示出來，例如可借助于鏈操作，把模式用一串鏈接起來的基元表示；句法分析用于對模式作句法檢查，以判定它是按何種句法合成的，從而實現對它的識別。

在結構模式識別中，由于模式要被劃分為子模式，子模式又被劃分為基元，然后再由基元、子模式按某種合成規則把模式表示出來，這類似于語言中由字構成詞，由詞構成句子的過程。因此人們就在模式的結構和語言的文法之間建立起一種類推關系，把對模式的識別通過用一組給定的句法規則對模式結構進行句法分析來實現。通常一個文法表示一個模式類，上圖中的句法分析就是用來判定當前待識別的模式遵循哪個文法，從而確定它應屬哪一類的。一類模式的結構信息需要用一個文法來描述，以指出它與其它類的區別。為了得到文法，

就需要給它提供一組訓練模式，使之通過推理進行學習，最后歸納出文法，這類似于統計模式識別中用訓練模式來訓練判決函數，圖中的文法推理就是起這個作用的。

（一）預處理與分割

1. 目標：

將原始數據（如圖像、符號序列）轉換為可解析的結構化單元，去除噪聲并分割出潛在基元。

2. 技術手段：

（1）圖像預處理：

邊緣檢測（Canny算子、Sobel算子）提取輪廓：

邊緣強度，方向。

二值化與形態學操作（膨脹、腐蝕）連接斷裂邊緣。

（2）序列分割：

對符號序列（如DNA序列）進行分詞，例如通過空格、標點或特定規則分割為基元候選。

3. 示例：手寫數字“7”的預處理

輸入28×28灰度圖像，二值化得到黑白圖像?B。

應用Sobel算子檢測邊緣，得到邊緣圖?E，其中“7”由兩條直線段組成（水平段和右斜段）。

（二）基元抽取與表示

1. 基元（Primitive）定義：

基元是構成模式的基本成分，對模式的識別起著重要作用，這就要求對基元的選擇既要有利于對模式的識別，又能方便地進行抽取。但這是很難兩全的，例如，筆劃被認為是描述手寫體漢字的較好基元，但它卻不易被機器所抽取。因此，只能在這兩者之間進行折衷。另外，由于受到模式自身的特征、用途、技術可行性等因素的影響，基元可在不同的情況下有不同的選擇，沒有固定的方法。例如，對圖（a）所示的矩形，若不考慮每條邊的長度，則可選用四條邊作為基元，并且把該矩形用鏈接法表示為a1+a2+a3+a4。但若還要考慮每條邊的長度，此時基元只能是邊上的單位長度，對圖（b)用鏈接法可表示為a+a+a+a+b+b+c+c+c+c+d+d。

基元是不可再分的最小結構單元，分為視覺基元（如圖像中的線段、弧、角）和符號基元（如語言中的單詞、化學中的化學鍵）。

視覺基元分類（以圖像為例）：

（1）按幾何形狀：直線段（→）、圓弧（⌒）、拐點（\corner）。

（2）按方向：定義8個方向基元，對應 0°、45°、…、315°。

2. 基元抽取算法：

（1）邊緣跟蹤法：從邊緣圖中提取連續邊緣段，按方向變化點分割為基元。

算法步驟：

1）找到邊緣起點?(x_0, y_0)。

2）沿邊緣方向逐像素跟蹤，記錄方向序列?{d_i}。

3）當方向變化超過閾值（如30°）時，分割當前基元，開始新基元。

（2）符號化方法：將數值特征轉換為符號，如將邊緣方向量化為4個主方向?{→, ↗, ↑, ↖}。

3. 基元表示形式：

（1）符號表示：如?a, b, c?代表不同基元。

（2）屬性向量：基元附帶屬性（長度、方向、曲率），如直線段基元表示為?(d, l, θ)，其中?d?為類型，l?為長度，θ為方向角。

4. 示例：手寫數字“7”的基元抽取

（1）邊緣跟蹤得到兩條連續線段：

基元 1：水平線段（方向0°，長度15像素），符號?a。

基元 2：右斜線段（方向45°，長度20像素），符號?b。

（2）基元序列為?a →?b（水平段后接右斜段）。

（三）文法建模（模式描述）

1. 形式文法（Formal Grammar）定義：

在結構模式識別中，人們希望有一種具有學習功能的推理機，它可以自動地從給定的模式集合中推斷出文法來，但目前還缺少可達到這一目標的算法，因此當今多數情況下還需要設計者自己來設計所需要的文法。下面簡要介紹一種稱為串文法的一維文法，它又稱為鏈文法。

文法?G = (V_T, V_N, S, P)，其中：

V_T：終結符集合（基元符號，如?{a, b, c}）。

V_N：非終結符集合（中間變量，如?{S, A, B}，表示模式類別或子結構）。

S ∈?V_N：起始符，表示整個模式。

P：產生式規則集合（非空有限集），每個產生式有形式為?α→β，其中。

2. 文法類型（喬姆斯基層次）：

類型	規則限制	對應自動機	應用場景
0 型	無限制文法	圖靈機	理論研究
1 型	上下文有關文法（CSG）	線性有界自動機	復雜結構（如自然語言）
2 型	上下文無關文法（CFG）	下推自動機	樹形結構（如程序語言）
3 型	正則文法（RG）	有限狀態自動機	字符串（如 DNA 序列）

3. 模式文法構造示例：

手寫數字“7”的正則文法：

（1）V_T = {a, b}（a?為水平段，b?為右斜段）

（2）V_N = {S}（起始符表示數字“7”）

（3）產生式?P：S →?a b（“7”由水平段后接右斜段構成）

更復雜的上下文無關文法（用于描述帶分支結構的模式）：

描述化學分子式：（??表示空串）

所謂“與上下文有關”，實際上是指僅當非終止符A出現在子串α1、α2的上下文之間時，才能被重寫為β。而所謂“與上下文無關”是指允許非終止符A被串α替換，不考慮其上下文。在模式識別中，經常用到上下文有關文法及上下文無關文法，它們都可以在有窮步內判定一個模式是否屬于某個確定的類別。

（四）句法分析與識別

1. 目標：

判斷輸入基元序列是否符合文法規則，即是否屬于某個模式類，并解析其結構。

2. 句法分析算法：

正則文法：有限狀態自動機（FSM）

狀態轉移圖：初始狀態?q_0，接收基元符號轉移狀態，終止狀態?q_f?表示合法模式。

示例：正則文法?S →?a S?| b?的FSM：

（1）狀態：q_0（初始），q_1（接收?a），q_f（接收?b，終止）

（2）轉移：

上下文無關文法：CYK 算法（Cocke-Younger-Kasami）

動態規劃方法，構建?n×n?表格?T[i,j]，表示從位置?i?到?j?的子串可由哪些非終結符推導。

算法步驟（輸入串?w = x_1x_2...?x_n）：

（1）初始化：（長度 1 的子串）。

（2）遞推：對長度?l=2?到?n，計算?

。

（3）判定：若?S ∈?T[1,n]，則輸入串合法。

3. 示例：CYK算法分析字符串ab**

文法?P: S →?AB, A →?a, B →?b

（1）表格初始化：T[1,1] = {A}, T[2,2] = {B}

（2）長度 2：T[1,2] = {S}（因?S →?AB，A∈T[1,1], B∈T[2,2]）

（3）判定：S∈T[1,2]，合法。

二、基元抽取與模式文法的深度解析

（一）基元設計的關鍵問題

1. 基元的選擇原則：

（1）完備性：基元集合能表示所有目標模式（如識別手寫數字需包含直線、曲線等基元）。

（2）獨立性：基元間無冗余（如避免同時定義“水平線”和“0°方向線段”作為不同基元）。

（3）可分割性：能通過預處理算法可靠提取（如邊緣檢測后的連續線段）。

2. 基元屬性的數學建模：

設基元?p?具有屬性向量，如：

（1）線段基元：長度?l、方向θ、曲率κ（直線曲率為 0）。

（2）符號基元：詞性（名詞、動詞）、語義類別（如WordNet中的概念標簽）。

3. 基元抽取的不確定性處理：

當邊緣分割存在噪聲時，引入模糊基元，定義基元屬于某類別的隸屬度函數：

例如，某邊緣段可能以0.8屬于“直線”基元，0.2屬于“曲線”基元。

（二）模式文法的擴展與應用

1. 樹狀文法（Tree Grammar）：

用于描述層次化結構（如語法樹、組織結構圖），產生式規則定義父節點與子節點的關系：Sentence →?NP、VP?NP →?Det Noun?（NP = 名詞短語，VP = 動詞短語，Det = 冠詞）

2. 圖文法（Graph Grammar）：

處理圖結構模式（如電路圖、分子結構），基元為圖的節點和邊，規則定義子圖的替換：

（1）節點標簽：V_T = {C, H, O}（化學元素）

（2）邊標簽：{單鍵, 雙鍵}

（3）產生式：苯環結構?C-C-C-C-C-C（環狀單雙鍵交替）

3. 文法推斷（Grammar Inference）：

從樣本集合中自動學習文法規則，分為生成式推斷（學習產生式）和分析式推斷（學習自動機狀態轉移）。

正則文法推斷算法：

（1）收集正例（屬于某類的基元序列）和反例（不屬于的序列）。

（2）構建最小確定有限自動機（DFA），通過合并等價狀態簡化規則。

三、模式的識別與分析

（一）句法分析中的歧義與容錯

1. 歧義處理：

當同一基元序列可被多個文法規則推導時（如自然語言中的結構歧義），需引入優先級規則或統計消歧：?

選擇后驗概率最大的文法?G_i。

2. 錯誤校正：

允許輸入序列存在少量基元錯誤或缺失，通過編輯距離定義校正代價：

（1）基元操作：插入、刪除、替換，代價分別為?c_i, c_d, c_r。

（2）校正后的最小代價路徑：

3. 示例：校正錯誤基元序列aab到合法序列ab**

假設?c_d = c_i = c_r = 1，編輯距離?D(3,2) = 1（刪除第二個?a），判定為“7”類。

（二）結構匹配與模式分析

1. 樹結構匹配：

計算兩棵樹的同構或最大公共子樹，用于XML文檔比對、程序代碼克隆檢測。

樹編輯距離：節點插入、刪除、替換的最小代價，遞歸定義：

2. 圖結構分析：

（1）子圖同構：判斷圖?G1?是否包含與?G2?同構的子圖，用于化學分子相似性檢索。

（2）圖不變量：計算圖的特征值（如鄰接矩陣的特征向量），轉化為統計特征進行分類。

3. 示例：化學分子結構匹配

目標：檢測分子圖中是否存在苯環結構（6節點環狀圖，單雙鍵交替）。

（1）提取分子圖的鄰接矩陣?A?和邊標簽矩陣?E。

（2）搜索所有6節點環，檢查邊標簽是否符合單雙鍵交替規則。

（三）結構模式識別與統計方法的結合

1. 混合模型：

（1）屬性文法（Attribute Grammar）：為文法規則附加數值屬性，如基元的長度、角度作為約束條件：

（2）隨機文法（Stochastic Grammar）：為產生式規則賦予概率，如?S →?A B (0.7), ?S →?C ?(0.3)，結合統計概率進行模糊識別。

2. 應用案例：手寫漢字識別

（1）基元層：提取筆畫基元（橫、豎、撇、捺），表示為帶方向和長度的屬性向量。

（2）文法層：上下文無關文法定義筆畫間的結構關系（如“橫”在“豎”上方，距離< 5像素）。

（3）識別層：CYK 算法結合屬性約束，排除不符合結構規則的候選類別。

四、理論拓展與應用前沿

（一）結構模式識別的數學基礎

1. 形式語言理論：

（1）喬姆斯基范式：將上下文無關文法轉換為二叉樹結構（A →?BC?或?A →?a），便于句法分析。

（2）泵引理：用于證明某個語言不屬于某類文法（如證明非正則語言）。

2. 自動機理論：

（1）有限狀態自動機（DFA/NFA）與正則文法的等價性：每個正則文法對應一個DFA，反之亦然。

（2）下推自動機（PDA）的棧機制用于處理上下文無關文法的遞歸結構。

（二）前沿應用領域

1. 生物醫學工程：

（1）蛋白質結構分類：將蛋白質二級結構（α- 螺旋、β- 折疊）作為基元，用樹文法描述三級結構。

（2）心電圖波形分析：提取P波、QRS波、T波作為基元，用正則文法識別異常心律模式。

2. 計算機視覺：

（1）場景解析：將圖像分割為物體（基元），用圖文法描述物體間的空間關系（如“桌子上有杯子”）。

（2）手勢識別：將手部關節運動軌跡分解為方向基元，用動態文法識別連續手勢（如“揮手”“點贊”）。

3. 自然語言處理：

（1）句法分析：構建上下文無關文法解析句子結構，生成句法樹（如Penn Treebank標注）。

（2）低資源語言處理：通過文法推斷從少量語料中學習形態規則（如黏著語的詞法分析）。

（三）挑戰與未來方向

（1）高噪聲環境下的基元分割：如何在復雜背景中準確提取基元（如遙感圖像中的道路網分割）。

（2）動態結構處理：針對視頻、時序數據，設計支持時間維度的動態文法（如事件序列的因果關系建模）。

（3）可解釋性與深度學習結合：將神經網絡提取的深層特征映射到結構基元，實現“端到端 + 可解釋”的模式識別（如視覺問答中的句法 - 語義聯合解析）。

五、總結

????????結構模式識別通過“基元 - 文法 - 句法分析”的三層架構，為具有層次化結構的模式提供了清晰的語義解析框架。從正則文法處理簡單字符串到上下文無關文法解析復雜樹結構，其核心優勢在于對模式內部結構關系的顯式建模。未來研究需聚焦于噪聲魯棒性、動態結構處理及與統計學習的深度融合，推動結構方法在跨模態、高維復雜數據中的應用，實現從“識別模式”到“理解結構”的跨越。