中科院《模式識(shí)別》——第七章

1、第七章 句法模式識(shí)別第七章 句法模式識(shí)別 統(tǒng)計(jì)模式識(shí)別是基于模式特征的一組測(cè)量值來(lái)組成特征向量，用決策理論劃分特征空間的方法進(jìn)行分類。 基于描述模式的結(jié)構(gòu)信息，用形式語(yǔ)言中的規(guī)則進(jìn)行分類，可以更典型地應(yīng)用于景物圖片的分析。 因?yàn)樵谶@類問(wèn)題中，所研究的模式通常十分復(fù)雜，需要的特征也很多，僅用數(shù)值上的特征不足以反映它們的類別。第七章 句法模式識(shí)別 句法模式識(shí)別系統(tǒng)的組成 圖像預(yù)處理 圖像分割 基元及其關(guān)系識(shí)別 句法分析第七章 句法模式識(shí)別 句法模式識(shí)別系統(tǒng)框圖第七章 句法模式識(shí)別 對(duì)圖像的結(jié)構(gòu)信息描述第七章 句法模式識(shí)別 句法模式識(shí)別系統(tǒng)處理過(guò)程 待識(shí)別的輸入圖像，經(jīng)過(guò)增強(qiáng)、去噪聲等處理后，按識(shí)別

2、的具體對(duì)象分割成子圖； 三角體D和長(zhǎng)方體E 然后將子圖分割成更簡(jiǎn)單的模式基元； 組成三角體和長(zhǎng)方體的各個(gè)面L,T和X,Y,Z 判別基元之間的關(guān)系。 三角體D是由相互鄰接的四邊形L和三角形T組成 長(zhǎng)方體E是有三個(gè)相互鄰接的四邊形X,Y和Z組成第七章 句法模式識(shí)別 句法模式識(shí)別系統(tǒng)處理過(guò)程 基元本身包含的結(jié)構(gòu)信息已不多，僅需少量特征即可識(shí)別。 如果用有限個(gè)字符代表不同的基元，則由基元按一定結(jié)構(gòu)關(guān)系組成的子圖或圖形可以用一個(gè)有序的字符串來(lái)代表。 假如事先用形式語(yǔ)言的規(guī)則從字符串中推斷出能生成它的文法，則可以通過(guò)句法分析，按給定的句法（文法）來(lái)辨識(shí)由基元字符組成的句子，從而判別它是否屬于由該給定文法所

3、能描述的模式類，達(dá)到分類的目的。第七章 句法模式識(shí)別 句法模式識(shí)別學(xué)習(xí)過(guò)程 為了要事先確定一個(gè)文法來(lái)描述所要研究模式的結(jié)構(gòu)信息，同樣需要采用模式的訓(xùn)練樣本集把文法推斷出來(lái)。 有了推斷出來(lái)的文法，才可以對(duì)未知類別的字符串進(jìn)行句法分析，達(dá)到分類的目的。 這一過(guò)程類似于統(tǒng)計(jì)模式識(shí)別中的學(xué)習(xí)過(guò)程，但文法推斷過(guò)程遠(yuǎn)不及統(tǒng)計(jì)學(xué)習(xí)來(lái)的成熟。7.1 集合論中的關(guān)系運(yùn)算 要進(jìn)行句法識(shí)別中基元之間關(guān)系的判別，首先要明確關(guān)系運(yùn)算。 “關(guān)系”在客觀世界中廣泛存在 社會(huì)生活：父子關(guān)系，母子關(guān)系，兄弟關(guān)系，等等； 數(shù)學(xué)運(yùn)算：大于、等于和小于關(guān)系，函數(shù)關(guān)系，等等。 二元關(guān)系 凡是一對(duì)對(duì)象之間的關(guān)系，都是二元關(guān)系。7.1 集

4、合論中的關(guān)系運(yùn)算 二元關(guān)系的相關(guān)概念 有序偶 設(shè)用表示一有序偶，它可以代表迪卡兒坐標(biāo)，例如，等，它們表示平面坐標(biāo)上的不同點(diǎn)。 兩個(gè)有序偶和相等，定義為 迪卡兒積 設(shè)A和B是任意兩個(gè)集合，由A中的一個(gè)元素和B中的一個(gè)元素組成有序偶，那么由A和B中所有元素組成的有序偶集合，稱為A和B的迪卡兒積，寫成A x B。 公式表達(dá)： 例子)By()Ax( | )y, x(BA7.1 集合論中的關(guān)系運(yùn)算 二元關(guān)系的相關(guān)概念 二元關(guān)系的定義及表示 任意有序?qū)Φ募隙x一種二元關(guān)系，簡(jiǎn)稱為關(guān)系 表示 設(shè)一有序?qū)?，其中R是一種關(guān)系，則記為xRy 例子7.1 集合論中的關(guān)系運(yùn)算 二元關(guān)系的性質(zhì) 定義：自反 集合X中

5、的關(guān)系R是自反的，只要對(duì)X中的每個(gè)x，有xRx，則屬于R。 寫法：X中的R是自反的 定義：對(duì)稱 集合X中的關(guān)系R是對(duì)稱的，只要對(duì)X中的每個(gè)x和y，每當(dāng)xRy時(shí)總有yRx。 寫法： X中的R是對(duì)稱的 例：實(shí)數(shù)集合中的“=”不是對(duì)稱的，但“=”關(guān)系是對(duì)稱的。 例：全體人的集合中，師生關(guān)系不是對(duì)稱的，但同學(xué)關(guān)系是對(duì)稱的。 例：平面上三角形集合中的相似關(guān)系是自反的和對(duì)稱的。7.1 集合論中的關(guān)系運(yùn)算 二元關(guān)系的性質(zhì) 定義：傳遞 集合X中的關(guān)系R是傳遞的，只要對(duì)X中的每個(gè)x, y和z，一旦xRy且yRz，則有xRz。 寫法：X中的R是傳遞的 例：若abc，則ac，表明”“關(guān)系是傳遞的 定義：非自反 集合

6、X中的關(guān)系R是非自反的，只要對(duì)X中的每個(gè)x，有不屬于R。 例7.1 集合論中的關(guān)系運(yùn)算 二元關(guān)系的性質(zhì) 定義：反對(duì)稱 集合X中的關(guān)系R是反對(duì)稱的，只要對(duì)X中的每個(gè)x和y，一旦xRy且yRx，則有x=y。 寫法： X中的R是反對(duì)稱的 例7.1 集合論中的關(guān)系運(yùn)算 關(guān)系圖 關(guān)系可以用圖形表示 設(shè)R為集合X=x, y, z中的一種關(guān)系，X中的元素用結(jié)點(diǎn)表示，并用相應(yīng)的元素名稱標(biāo)志。如果xRy，則用帶箭頭的弧線連接結(jié)點(diǎn)x和y。7.1 集合論中的關(guān)系運(yùn)算 等價(jià)關(guān)系 如果集合X中的關(guān)系R是自反的、對(duì)稱的和傳遞的，則稱它是一個(gè)等價(jià)關(guān)系。 實(shí)數(shù)集合中的數(shù)值相等 三角形集合中的三角形相似 一個(gè)班內(nèi)同學(xué)之間的同班

7、關(guān)系 等價(jià)類定義 等價(jià)類性質(zhì) 集合X上的等價(jià)關(guān)系R所構(gòu)成的類兩兩不相交，且覆蓋了整個(gè)集合X。7.1 集合論中的關(guān)系運(yùn)算 等價(jià)關(guān)系 可以用圖形方法分析研究等價(jià)劃分：由于等價(jià)關(guān)系是自反的、對(duì)稱的、傳遞的，因此由這些性質(zhì)的圖形特點(diǎn)可知： 一個(gè)集合X上的等價(jià)關(guān)系R的關(guān)系圖，其每個(gè)結(jié)點(diǎn)必有環(huán)； 若兩個(gè)結(jié)點(diǎn)間有邊相連，則必有方向彼此相反的兩條有向邊； 若圖中任何兩個(gè)結(jié)點(diǎn)是可達(dá)的，則必有邊直接相連。 例子7.1 集合論中的關(guān)系運(yùn)算 兼容關(guān)系 如果X中的關(guān)系R是自反的而且是對(duì)稱的，則稱R是一個(gè)兼容關(guān)系。 所有的等價(jià)關(guān)系是兼容關(guān)系； 兼容關(guān)系不一定是傳遞的。 偏序關(guān)系 集合P上的二元關(guān)系R稱為P上的一個(gè)偏序關(guān)系

8、，當(dāng)且僅當(dāng)R是自反的、反對(duì)稱的和傳遞的。 偏序關(guān)系通常用“=”表示，但注意“ A”叔侄”C7.1 集合論中的關(guān)系運(yùn)算 二元關(guān)系的復(fù)合 關(guān)系圖7.1 集合論中的關(guān)系運(yùn)算 二元關(guān)系的復(fù)合 關(guān)系的復(fù)合運(yùn)算可以施加于自身 表示為：RR =R2，RRR =R3 ， 傳遞閉包 例子7.2 形式語(yǔ)言理論和句法模式識(shí)別 形式語(yǔ)言的起源可以追溯到二十世紀(jì)五十年代； 喬姆斯基(Chomsky)等科學(xué)家在研究語(yǔ)言的工作中發(fā)展了文法的數(shù)學(xué)模型； 其基本目的是發(fā)展一種應(yīng)用于計(jì)算機(jī)的文法，使它有描述自然語(yǔ)言的能力，例如英文。 如果能做到這一點(diǎn)，則有希望“教”計(jì)算機(jī)理解自然語(yǔ)言，以達(dá)到翻譯的目的。7.2 形式語(yǔ)言理論和句法

9、模式識(shí)別 形式語(yǔ)言的基本目的迄今為止尚未完全實(shí)現(xiàn)，但在這個(gè)領(lǐng)域的研究成果卻大大沖擊了其它一些領(lǐng)域 計(jì)算機(jī)編譯系統(tǒng)的設(shè)計(jì) 計(jì)算機(jī)語(yǔ)言 自動(dòng)機(jī)理論 模式識(shí)別7.2 形式語(yǔ)言理論和句法模式識(shí)別 在模式識(shí)別中，如果大量復(fù)雜的模式的集合，能用一組為數(shù)不多的簡(jiǎn)單的模式基元和文法規(guī)則來(lái)描述，則對(duì)每一個(gè)模式的識(shí)別，就可以按給定的一組文法結(jié)構(gòu)規(guī)則來(lái)剖析； 如果解析的結(jié)果表明，模式基元能為給定的文法規(guī)則所接受，則可判別它屬于該模式類，否則就不屬于該模式類。7.2 形式語(yǔ)言理論和句法模式識(shí)別7.2.1 形式語(yǔ)言理論中的某些定義 形式語(yǔ)言是一種抽象語(yǔ)言，它可以包括人類使用的自然語(yǔ)言、計(jì)算機(jī)使用的各種語(yǔ)言、數(shù)學(xué)中的公式

10、語(yǔ)言等。 自然語(yǔ)言（英文）：它的基本組成是有限個(gè)字母，將字母（組成的單詞）按一定的文法規(guī)則排列，可以構(gòu)成句子，而一種語(yǔ)言則是所有句子的集合。 人類的自然語(yǔ)言是一個(gè)不可數(shù)的有窮集 英文：26個(gè)字母按一定的文法規(guī)則組合，可以表達(dá)無(wú)數(shù)的思想內(nèi)容。7.2 形式語(yǔ)言理論和句法模式識(shí)別7.2.1 形式語(yǔ)言理論中的某些定義 字母表和符號(hào)串 字母表：以某些符號(hào)作為元素的非空有窮集，以V或表示。 符號(hào)串：由字母表中符號(hào)組成的任何有窮序列。 例子 空符號(hào)串：不包含任何符號(hào)的串，用表示。 符號(hào)串的長(zhǎng)度：符號(hào)串x所包含的符號(hào)個(gè)數(shù)，用|x|表示。 例子 符號(hào)串的聯(lián)接：若x和y都是符號(hào)串，則把y符號(hào)串寫在x符號(hào)串之后，就

11、得到聯(lián)接的符號(hào)串xy。 例子7.2 形式語(yǔ)言理論和句法模式識(shí)別7.2.1 形式語(yǔ)言理論中的某些定義 字母表和符號(hào)串 符號(hào)串集合的乘積 例子 如果A和B只是代表一個(gè)符號(hào)串，而不是符號(hào)串的集合，則乘積AB與符號(hào)串的聯(lián)接結(jié)果相同。 符號(hào)串和符號(hào)串集合A的冪 集合A的正閉包、閉包 字母表V的冪 集合V的正閉包、閉包 例子7.2 形式語(yǔ)言理論和句法模式識(shí)別7.2.1 形式語(yǔ)言理論中的某些定義 文法 一種語(yǔ)言中構(gòu)成句子所必須遵守的規(guī)則； 由某種語(yǔ)言的字母表中的字母所組成的串不一定都是該語(yǔ)言的句子； 只有當(dāng)一個(gè)串符合該語(yǔ)言的文法規(guī)則時(shí)，才能算是該語(yǔ)言的句子，否則就不是該語(yǔ)言的句子。7.2 形式語(yǔ)言理論和句法

12、模式識(shí)別7.2.1 形式語(yǔ)言理論中的某些定義 文法定義 文法舉例 在生成規(guī)則P中，帶的符號(hào)稱為語(yǔ)法元，不帶的符號(hào)稱為單詞； 一個(gè)簡(jiǎn)單句的生成由語(yǔ)法元()開(kāi)始，反復(fù)把生成規(guī)則中箭頭左邊的部分用其右邊的部分替換，直到所得的形式中不再出現(xiàn)語(yǔ)法元而只有單詞為止。 簡(jiǎn)單句“The boy runs.”符合給定的文法規(guī)則，因?yàn)樗梢杂缮鲜龅奈姆ㄒ?guī)則產(chǎn)生。 生成過(guò)程7.2 形式語(yǔ)言理論和句法模式識(shí)別7.2.1 形式語(yǔ)言理論中的某些定義 文法舉例 文法樹(shù)7.2 形式語(yǔ)言理論和句法模式識(shí)別7.2.1 形式語(yǔ)言理論中的某些定義 利用文法樹(shù)可以闡明文法的形式化定義： 文法樹(shù)的根一定是文法G的起始符S； 樹(shù)的葉一定是

13、終止符； 樹(shù)的每一個(gè)分支（子樹(shù)）在沿著根到葉的方向上可以表示成一個(gè)直接推導(dǎo)的生成式； 如果利用文法樹(shù)的逆過(guò)程，則可將生成過(guò)程重新構(gòu)造出來(lái)。7.2 形式語(yǔ)言理論和句法模式識(shí)別7.2.2 語(yǔ)言的生成過(guò)程 利用文法G來(lái)生成語(yǔ)言的過(guò)程中的一些規(guī)定 非終止符VN用大寫英文字母：S, A, B, C, 終止符VT用英文字母表起始部分的小寫字母：a, b, c, 終止符組成的字符串用英文字母表中尾部的小寫字母：u, v, w, x, 終止符和非終止符混合組成的字符串用希臘字母：, , , , 7.2 形式語(yǔ)言理論和句法模式識(shí)別7.2.2 語(yǔ)言的生成過(guò)程 利用文法G來(lái)生成語(yǔ)言的過(guò)程中的一些規(guī)定 生成式P由以下

14、形式的表達(dá)式組成：-，其中是V+中的字符串， 是V*中的字符串，“- ”表示字符串被所取代。 =表示根據(jù)文法G，由一字符串直接推導(dǎo)出另一字符串。 例子7.2 形式語(yǔ)言理論和句法模式識(shí)別7.2.2 語(yǔ)言的生成過(guò)程 句型和句子 定義 句型是由起始符開(kāi)始進(jìn)行推導(dǎo)而得到的由字母表中的符號(hào)（包括VN 、VT和）組成的任意字符串； 句型和句子關(guān)系 句子一定是由字母表中終止符組成的字符串。7.2 形式語(yǔ)言理論和句法模式識(shí)別7.2.2 語(yǔ)言的生成過(guò)程 語(yǔ)言 定義 短語(yǔ) 定義 從起始符推導(dǎo)一個(gè)句子的過(guò)程，實(shí)際上就是將推導(dǎo)過(guò)程中句型的一部分不斷用短語(yǔ)來(lái)取代的過(guò)程，這種文法稱為短語(yǔ)結(jié)構(gòu)文法。7.2 形式語(yǔ)言理論和句

15、法模式識(shí)別7.2.2 語(yǔ)言的生成過(guò)程 例子 從生成規(guī)則P中可以看出，只有第二生成式A-aAc中出現(xiàn)了a和c，可見(jiàn)由此生成的字符串中a和c的個(gè)數(shù)是同樣多的，且a和c只能分別地連續(xù)出現(xiàn)。 如果不用第二生成式A-aAc而用第三生成式A-B時(shí)，則只能往下用第四生成式B-bB和第五生成式B-b，這樣再也不會(huì)出現(xiàn)a和c。 因此由P生成的字符串只能是anbmcn的形式。L(G)=anbmcn|m,n=1且僅為整數(shù)7.2 形式語(yǔ)言理論和句法模式識(shí)別7.2.2 語(yǔ)言的生成過(guò)程 文法G產(chǎn)生語(yǔ)言的描述 一個(gè)文法G=(VN, VT , P, S)所產(chǎn)生的語(yǔ)言，是由S開(kāi)始所推導(dǎo)出的所有終止符的集合，它滿足兩個(gè)條件 每一

16、個(gè)字符串只能由終止符組成，即每一個(gè)字符串都是終止符句子； 每一個(gè)字符串都能從S開(kāi)始，適當(dāng)應(yīng)用P中的生成式來(lái)導(dǎo)出。7.2 形式語(yǔ)言理論和句法模式識(shí)別7.2.2 文法的分類 文法可定義為一個(gè)四元組G=(VN,VT,P,S)，喬姆斯基按照文法所允許的生成形式的不同，定義四種文法類型： 0型文法：稱為無(wú)約束文法 1型文法：稱為上下文有關(guān)文法 2型文法：稱為上下文無(wú)關(guān)文法 3型文法：稱為正則文法7.2 形式語(yǔ)言理論和句法模式識(shí)別7.2.2 文法的分類 0型文法（無(wú)約束文法） 生成式形式 說(shuō)明 可以有=，但不能有=； 只有0型文法才允許有產(chǎn)生空句的生成式。7.2 形式語(yǔ)言理論和句法模式識(shí)別7.2.2 文法

17、的分類 1型文法（上下文有關(guān)文法） 生成式形式 說(shuō)明 在1和2之間的非終止符可以重寫為，這里1和2稱為句型1A2對(duì)于A的上下文； 不是在1和2之間的A不能使用此規(guī)則。 例子 從表面上看似乎上下文并不完整； 但根據(jù)1型文法的定義， 1、2屬于V*，可以有1=2 =； 因此生成規(guī)則P可以改寫成例中生成式右側(cè)所示形式。7.2 形式語(yǔ)言理論和句法模式識(shí)別7.2.2 文法的分類 2型文法（上下文無(wú)關(guān)文法） 生成式形式 說(shuō)明 該文法表明生成式左側(cè)為單變量，可由右側(cè)的字符串來(lái)取代，因此是上下文無(wú)關(guān)的。7.2 形式語(yǔ)言理論和句法模式識(shí)別7.2.2 文法的分類 3型文法（正則文法） 生成式形式 說(shuō)明 該文法表明

18、規(guī)則右側(cè)一定要首先含有非終止符。7.2 形式語(yǔ)言理論和句法模式識(shí)別7.2.2 文法的分類 四種文法比較 正則文法（3型文法）生成規(guī)則的右側(cè)若不強(qiáng)調(diào)終止符的首先出現(xiàn)，就變成上下文無(wú)關(guān)文法（2型文法）； 上下文無(wú)關(guān)文法（2型文法）生成規(guī)則的左側(cè)若不強(qiáng)調(diào)單變量，而加以上下文限制，就變成上下文有關(guān)文法（1型文法）； 上下文有關(guān)文法（1型文法）去掉上下文的限制，就變成無(wú)約束文法（0型文法）。7.2 形式語(yǔ)言理論和句法模式識(shí)別7.2.2 文法的分類 四種文法比較 包含關(guān)系： 正則文法 上下文無(wú)關(guān)文法 上下文有關(guān)文法 無(wú)約束文法 所有正則文法都是上下文無(wú)關(guān)的； 所有上下文無(wú)關(guān)文法都是上下文有關(guān)的； 所有上下

19、文有關(guān)文法都是無(wú)約束的。 在句法模式識(shí)別中，多采用上下文無(wú)關(guān)文法和正則文法。7.2 形式語(yǔ)言理論和句法模式識(shí)別7.2.2 文法的分類 例1：無(wú)約束文法 例2：上下文有關(guān)文法 例3：上下文無(wú)關(guān)文法 例4：正則文法作業(yè) 寫出上下文無(wú)關(guān)文法，其終止符集VT=a,b能生成語(yǔ)言L(G)=ab,ba,aba,bab,abab,baba,7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別 一種類別的模式，可以用一個(gè)文法來(lái)描述。 要識(shí)別一個(gè)未知的模式，可以先用其基元表征成一個(gè)字符串或句子，然后再用該文法進(jìn)行判斷。 若能被接受，則說(shuō)明它是屬于該文法所生成的語(yǔ)言，亦即它是屬于該類模式，否則就不屬于該類模式。 自動(dòng)機(jī)就是一種句法識(shí)別器，

20、它可以判斷一個(gè)句子是否屬于某種語(yǔ)言，并且自動(dòng)機(jī)的類型與文法的類型有著某種對(duì)應(yīng)關(guān)系。7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.1 有限態(tài)自動(dòng)機(jī) 有限態(tài)自動(dòng)機(jī)是研究自動(dòng)系統(tǒng)的一種數(shù)學(xué)模型，它能模擬多種離散的自動(dòng)系統(tǒng)。 結(jié)構(gòu)概念實(shí)例：八進(jìn)制計(jì)數(shù)器和有限態(tài)自動(dòng)機(jī)模型 一個(gè)八進(jìn)制計(jì)數(shù)器，要求每逢計(jì)數(shù)到6輸出一脈沖。 將該裝置看成是一個(gè)離散系統(tǒng)。7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.1 有限態(tài)自動(dòng)機(jī) 結(jié)構(gòu)概念實(shí)例：八進(jìn)制計(jì)數(shù)器和有限態(tài)自動(dòng)機(jī)組成 輸入信息：接受順序輸入的計(jì)數(shù)脈沖作為輸入信息，有脈沖時(shí)為1，無(wú)脈沖時(shí)為0，以0,1組成的字符串作為輸入。 輸出信息：當(dāng)計(jì)數(shù)器的狀態(tài)到達(dá)6時(shí)，輸出一脈沖，其余情況均輸出為0

21、 ，以0,1組成的字符串作為輸出。 內(nèi)部狀態(tài)：觸發(fā)器q1、q2和q3所處的0或1的狀態(tài)。 該計(jì)數(shù)裝置是否有脈沖輸出，不僅依賴于當(dāng)前的輸入信息，而且還依賴于前一時(shí)刻觸發(fā)器所處的狀態(tài)亦即該觸發(fā)器的內(nèi)部狀態(tài)。這里三個(gè)觸發(fā)器所處的狀態(tài)的集合q1, q2, q3屬于有限個(gè)狀態(tài)的集合。7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.1 有限態(tài)自動(dòng)機(jī) 結(jié)構(gòu)概念實(shí)例：八進(jìn)制計(jì)數(shù)器和有限態(tài)自動(dòng)機(jī)組成 狀態(tài)轉(zhuǎn)換：設(shè)以表示輸入0,1的集合，以Q表示內(nèi)部狀態(tài)的集合q1, q2 , q3，則狀態(tài)轉(zhuǎn)換函數(shù)可以表示成Q和到Q的映射，寫成迪卡兒乘積的形式為：Q x - Q， 稱為狀態(tài)轉(zhuǎn)移函數(shù)。 內(nèi)部狀態(tài)的轉(zhuǎn)換既依賴于輸入，也依賴于前一時(shí)

22、刻的內(nèi)部狀態(tài)。 輸出函數(shù)：在某時(shí)刻的輸出信息，一般由同一時(shí)刻的輸入信息和內(nèi)部狀態(tài)所決定。 它也是內(nèi)部狀態(tài)與輸入的映射 從上述組成可以看出，一個(gè)離散的有限狀態(tài)的自動(dòng)系統(tǒng)由五部分組成。一個(gè)有限態(tài)自動(dòng)機(jī)A是模擬多種離散自動(dòng)系統(tǒng)的一種數(shù)學(xué)模型。7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.1 有限態(tài)自動(dòng)機(jī) 有限態(tài)自動(dòng)機(jī)定義 映射的狀態(tài)圖表示： 并不是全部可能的輸出函數(shù)都一定是需要的輸出終止?fàn)顟B(tài)，只有其中部分輸出狀態(tài)才是感興趣的輸出終止?fàn)顟B(tài)。 有限態(tài)自動(dòng)機(jī)抽象結(jié)構(gòu)示意圖7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.1 有限態(tài)自動(dòng)機(jī) 結(jié)構(gòu)示意圖描述 控制器上記錄了各種狀態(tài)，并且各種狀態(tài)之間按一定的規(guī)則在控制器中變化，而變化的

23、改變是受輸入支配的。 具體來(lái)說(shuō)，控制器相對(duì)于輸入磁帶自左向右移動(dòng)，每接受一個(gè)輸入符號(hào)便右移一個(gè)單位，并改變一次狀態(tài)，直至一個(gè)句子的全部符號(hào)輸入結(jié)束。 同時(shí)，每輸入一個(gè)符號(hào)，控制器要根據(jù)狀態(tài)規(guī)則來(lái)判斷能否接受該符號(hào)，若所有的符號(hào)都能被接受，就說(shuō)明該句子屬于該自動(dòng)機(jī)所能接受的那種語(yǔ)言。 此時(shí)，狀態(tài)變換(q,a)=q表示“處于狀態(tài)q并正在掃描輸入符號(hào)a”的自動(dòng)機(jī)A，將讀入磁頭右移一個(gè)單元，并轉(zhuǎn)到狀態(tài)q。 自動(dòng)機(jī)輸入句子后，若(q,x)=q且q在F中，則稱句子x被有限態(tài)自動(dòng)機(jī)A所接受。7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.1 有限態(tài)自動(dòng)機(jī) 正規(guī)集 由有限態(tài)自動(dòng)機(jī)A接受的所有句子x的集合表示為： T(A)

24、=x|(q,x)在F中，F(xiàn)是終止?fàn)顟B(tài)集。 由有限態(tài)自動(dòng)機(jī)接受的句子的任何集合，稱為正規(guī)集。7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.1 有限態(tài)自動(dòng)機(jī) 例子 狀態(tài)圖7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.2 非確定有限態(tài)自動(dòng)機(jī) 確定有限態(tài)自動(dòng)機(jī) 映射關(guān)系唯一 非確定的有限態(tài)自動(dòng)機(jī) 它所確定的狀態(tài)不是唯一的，可以由若干個(gè)狀態(tài)可供選擇，亦即是一個(gè)狀態(tài)集。 映射關(guān)系：(q, x) =p1, p2, , pk 自動(dòng)機(jī)A在狀態(tài)q若輸入字母為x，則其轉(zhuǎn)換到下一時(shí)刻的狀態(tài)可以從p1, p2, pk這k個(gè)狀態(tài)中任選一個(gè)，這樣的一種自動(dòng)機(jī)稱為非確定有限態(tài)自動(dòng)機(jī)。7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.2 非確定有限態(tài)自動(dòng)機(jī) 形

25、式化定義 例子7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.2 非確定有限態(tài)自動(dòng)機(jī) 非確定有限態(tài)自動(dòng)機(jī)與確定有限態(tài)自動(dòng)機(jī)的關(guān)系 非確定有限態(tài)自動(dòng)機(jī)是確定有限態(tài)自動(dòng)機(jī)的推廣 形式化描述7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.2 非確定有限態(tài)自動(dòng)機(jī) 非確定有限態(tài)自動(dòng)機(jī)與確定有限態(tài)自動(dòng)機(jī)的關(guān)系 例子 非確定的有限態(tài)自動(dòng)機(jī)和確定的有限態(tài)自動(dòng)機(jī)統(tǒng)稱為有限態(tài)自動(dòng)機(jī)7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.3 按正則文法構(gòu)造有限態(tài)自動(dòng)機(jī) 形式化描述 例子7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.4 按有限態(tài)自動(dòng)機(jī)確定正則文法 形式化描述 例子作業(yè) 求一有限態(tài)自動(dòng)機(jī)，它只能接受由“偶數(shù)個(gè)a”與/或“偶數(shù)個(gè)b”組成的任意字符串，例如：a

26、a, bb, abab, abba, baba等。7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.5 下推自動(dòng)機(jī)和上下文無(wú)關(guān)文法 上下文無(wú)關(guān)語(yǔ)言的范式 任何上下文無(wú)關(guān)文法的生成式A-都可以寫成喬姆斯基范式或格雷巴赫標(biāo)準(zhǔn)式 喬姆斯基范式 形式：A-BC，A-a，其中 例子 格雷巴赫標(biāo)準(zhǔn)式 形式：A-a ，其中 例子7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.5 下推自動(dòng)機(jī)和上下文無(wú)關(guān)文法 構(gòu)造下推自動(dòng)機(jī)的原因 若正則文法的生成規(guī)則為A-aB，生成式的左側(cè)和右側(cè)都只有一個(gè)非終止符，則用有限態(tài)自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換來(lái)表達(dá)就已經(jīng)足夠了。 但在上下文無(wú)關(guān)文法中，生成式左側(cè)只有一個(gè)非終止符，但右側(cè)不止一個(gè)非終止符，如A-aBC。

27、對(duì)于A-a的一般情況，生成式右側(cè)可以是任意數(shù)目的非終止符，如寫成A-aA1A2An。 在這種情況下，如果仍舊用有限態(tài)自動(dòng)機(jī)來(lái)識(shí)別，當(dāng)自動(dòng)機(jī)接受了a后，狀態(tài)A只能轉(zhuǎn)換到A1，下一步僅能考慮從A1開(kāi)始， A2An都被忽略了。 結(jié)論：用有限態(tài)自動(dòng)機(jī)不能識(shí)別上下文無(wú)關(guān)文法。7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.5 下推自動(dòng)機(jī)和上下文無(wú)關(guān)文法 下推自動(dòng)機(jī)的概念 下推自動(dòng)機(jī)針對(duì)上述情況，另行配置一個(gè)堆棧來(lái)壓入任意數(shù)目的非終止符。這些非終止符都應(yīng)包括在上下文無(wú)關(guān)文法之中。 堆棧：后進(jìn)先出，就是最后一個(gè)被壓入的非終止符始終處于棧的頂部。 在沒(méi)有壓入任何符號(hào)串之前，棧頂內(nèi)容為起始符。 在處理過(guò)程中，棧頂?shù)姆墙K止符

28、Ai與輸入字符串中的終止符a共同決定了自動(dòng)機(jī)狀態(tài)的轉(zhuǎn)移，而在輸入終止符使自動(dòng)機(jī)狀態(tài)轉(zhuǎn)移的同時(shí)，棧頂內(nèi)容亦改變。 帶有這種堆棧結(jié)構(gòu)成為下推自動(dòng)機(jī)的特點(diǎn)。7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.5 下推自動(dòng)機(jī)和上下文無(wú)關(guān)文法 下推自動(dòng)機(jī)的概念 根據(jù)下推自動(dòng)機(jī)的特點(diǎn)，下推自動(dòng)機(jī)不能只用一個(gè)狀態(tài)參數(shù)qi來(lái)描述，而必須加上棧頂內(nèi)容ri 。 若將棧頂內(nèi)容也看作是一個(gè)狀態(tài)，則兩個(gè)參數(shù)聯(lián)合的格局(qi, ri)才能準(zhǔn)確地描述自動(dòng)機(jī)的當(dāng)前狀態(tài)。 輸入終止符a，將引起自動(dòng)機(jī)的格局轉(zhuǎn)移，每個(gè)輸入終止符所引起的新格局，都和原格局有關(guān)，即與以前的輸入內(nèi)容有關(guān)。所以，每個(gè)新格局都能反映當(dāng)時(shí)及以前的輸入符號(hào)串。 按此推理，自動(dòng)

29、機(jī)的最后格局也就反映了輸入句子的全部符號(hào)，可用它來(lái)進(jìn)行句子的識(shí)別。7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.5 下推自動(dòng)機(jī)和上下文無(wú)關(guān)文法 下推自動(dòng)機(jī)的模型和定義 下推自動(dòng)機(jī)構(gòu)造模型7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.5 下推自動(dòng)機(jī)和上下文無(wú)關(guān)文法 下推自動(dòng)機(jī)的模型和定義 下推自動(dòng)機(jī)實(shí)質(zhì)上是在有限態(tài)自動(dòng)機(jī)上再加上一個(gè)后進(jìn)先出的堆棧，堆棧的一段固定，只能在另一端上存或取。 通常用代表轉(zhuǎn)換過(guò)程中處于棧頂?shù)挠邢拮帜讣?=Zi|i=1,2,n7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.5 下推自動(dòng)機(jī)和上下文無(wú)關(guān)文法 下推自動(dòng)機(jī)的模型和定義 下推自動(dòng)機(jī)定義 映射的含義：在自動(dòng)機(jī)q狀態(tài)下和堆棧頂為Z時(shí)，輸入符號(hào)a，這

30、時(shí)造成的映射使自動(dòng)機(jī)進(jìn)入下一個(gè)格局(qi, ri)，即原來(lái)處于棧頂?shù)姆?hào)Z被壓入棧內(nèi)，而棧頂變成ri串中的首位符號(hào)，自動(dòng)機(jī)進(jìn)入狀態(tài)qi 。7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.5 下推自動(dòng)機(jī)和上下文無(wú)關(guān)文法 下推自動(dòng)機(jī)的模型和定義 格局變幻的表達(dá)式： 變換式的含義： 對(duì)應(yīng)于映射規(guī)則，輸入一個(gè)符號(hào)a，可使下推自動(dòng)機(jī)M從格局(q, Zr)轉(zhuǎn)向(qi, rir)，這里Z為轉(zhuǎn)換前的棧頂符號(hào)，ri為轉(zhuǎn)換后的棧頂符號(hào)串。 ri代表一個(gè)符號(hào)串，這時(shí)棧頂符號(hào)應(yīng)為ri串中的首位符號(hào)。 一個(gè)連串導(dǎo)出關(guān)系 若存在 ，則對(duì)1n之間的所有i，有7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.5 下推自動(dòng)機(jī)和上下文無(wú)關(guān)文法 下推自動(dòng)機(jī)

31、接受語(yǔ)言的方式 終止?fàn)顟B(tài)方式 定義：下推自動(dòng)機(jī)用終止?fàn)顟B(tài)方式所接受的語(yǔ)言T(M)定義為： 含義：當(dāng)下推自動(dòng)機(jī)M從起始狀態(tài)q0開(kāi)始到達(dá)終止?fàn)顟B(tài)q，同時(shí)其堆棧棧頂符號(hào)從起始符號(hào)Z0開(kāi)始變成r，則接受一個(gè)句子x，這是利用狀態(tài)參數(shù)q是否到達(dá)終止?fàn)顟B(tài)集F來(lái)識(shí)別語(yǔ)言的方式。 所有識(shí)別的句子x的集合就是下推自動(dòng)機(jī)所接受的語(yǔ)言T(M)。rF,qr),(q,| )Z,(q:x|xT(M)*007.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.5 下推自動(dòng)機(jī)和上下文無(wú)關(guān)文法 下推自動(dòng)機(jī)接受語(yǔ)言的方式 空堆棧方式 定義：下推自動(dòng)機(jī)用空堆棧方式所接受的語(yǔ)言N(M)定義為： 含義：不管q是否到達(dá)終止?fàn)顟B(tài)，只要堆棧變空，輸入句子x就被

32、接受，這是利用輸入x的過(guò)程中堆棧符號(hào)r的變換來(lái)識(shí)別語(yǔ)言的方式。7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.5 下推自動(dòng)機(jī)和上下文無(wú)關(guān)文法 下推自動(dòng)機(jī)接受語(yǔ)言的方式 例子 在接受xcxR, x=0,1*的句型時(shí)： 在狀態(tài)q1時(shí)可反復(fù)使用(q1,a,A)接受x，其中a=0或1，A=R,B或G，并使下推自動(dòng)機(jī)存有符號(hào)串=(RUB,G*)R 接受符號(hào)c后，狀態(tài)變?yōu)閝2 在狀態(tài)q2時(shí)，每接受一個(gè)符號(hào)（0或1），堆棧中的符號(hào)被上推，被取出時(shí)的次序與存入時(shí)的次序恰好相反，故在q2狀態(tài)下接受xR 因此，L(G)為xcxR7.3 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別7.3.5 下推自動(dòng)機(jī)和上下文無(wú)關(guān)文法 下推自動(dòng)機(jī)與上下文無(wú)關(guān)語(yǔ)言的聯(lián)

33、系 描述 例子7.4 基元的提取 模式識(shí)別的主要任務(wù)之一就是圖形的識(shí)別。描述一個(gè)待識(shí)別的圖形模式可以借助于一組基元，用語(yǔ)言結(jié)構(gòu)法進(jìn)行識(shí)別。 基元對(duì)應(yīng)于文法中的終止符，它是構(gòu)成句子的最基本單位。 選擇好的基元對(duì)有效地進(jìn)行句法模式識(shí)別是十分重要的，可惜的是目前基元選擇還沒(méi)有一個(gè)通用的方法，只能根據(jù)具體因素而定。 模式的數(shù)據(jù)性質(zhì) 待識(shí)別對(duì)象的具體應(yīng)用 識(shí)別系統(tǒng)所用的技術(shù)7.4 基元的提取 基元選擇應(yīng)注意的兩點(diǎn) 基元應(yīng)是模式的基本單元，且易于利用它們之間的結(jié)構(gòu)關(guān)系來(lái)緊湊方便地描述模式。 例如：圖形識(shí)別中各子圖形之間的連接關(guān)系就可以用基元的結(jié)構(gòu)關(guān)系來(lái)表達(dá) 基元是最簡(jiǎn)單的子模式，它本身的結(jié)構(gòu)信息已不重要，

34、可用非語(yǔ)言方法（如統(tǒng)計(jì)方法、幾何尺寸度量等）來(lái)提取。 例如：識(shí)別手寫文字用筆畫作為基元比較有效，語(yǔ)音識(shí)別采用音素作為基元比較方便，心電圖識(shí)別采用收縮波和擴(kuò)張波的波形變化特征作為基元比較直接，等等。7.4 基元的提取 在圖形識(shí)別中，對(duì)平面圖形可以采用兩種類型的基元。 從圖形的邊界、輪廓或骨架提取基元； 以圖形的基本組成區(qū)域作為基元。7.4 基元的提取7.4.1 圖形邊界或骨架的基元選擇 Freeman鏈碼可以用來(lái)描述圖形的邊界和骨架。7.4 基元的提取7.4.1 圖形邊界或骨架的基元選擇 Freeman鏈碼可以用來(lái)描述圖形的邊界和骨架。 將待描述的曲線量化，曲線落在每一個(gè)方格中的各個(gè)分段可用8個(gè)

35、方向之一來(lái)近似。 例如，圖中的曲線可表示為字符串：4444570767077 可以通過(guò)句法分析來(lái)判別待識(shí)別的曲線。7.4 基元的提取7.4.1 圖形邊界或骨架的基元選擇 Freeman鏈碼可以用來(lái)描述圖形的邊界和骨架。 在實(shí)際應(yīng)用中，直接采用Freeman鏈碼中的元素作為基元，會(huì)將曲線圖形分割的太細(xì)，造成句法分析的復(fù)雜化。 若選用若干種有共性特點(diǎn)的弧形曲線段作為基元，亦能描述圖形，但比直接用Freeman鏈碼簡(jiǎn)單。 可用一種變換把原來(lái)的8種基本方向變換成一組弧形曲線基元，使描述模式的句子短一些。7.4 基元的提取7.4.1 圖形邊界或骨架的基元選擇 可將模式的描述用字符串的形式表示為：V=V1

36、 V2 Vn，其中Vi是串中的一個(gè)基元，它可以是一段不變曲率的弧，多邊形的一條邊，或一段二次曲線的弧等等。 若Vi取自有窮字母表，則可直接采用句法分析。 進(jìn)行句法分析之前要消除噪聲，對(duì)邊界曲線進(jìn)行預(yù)處理。7.4 基元的提取7.4.1 圖形邊界或骨架的基元選擇 例子：亞中央著絲點(diǎn)染色體的多級(jí)結(jié)構(gòu)描述7.4 基元的提取7.4.1 圖形邊界或骨架的基元選擇 例子：亞中央著絲點(diǎn)染色體的多級(jí)結(jié)構(gòu)描述 基元采用曲線段a,b,c,d 從左到右把樹(shù)的葉子匯集起來(lái)，就構(gòu)成了一個(gè)字符串，恰好表達(dá)了染色體的邊界形狀。 用符號(hào)編碼表示為：babcbabdbabcbabd，表達(dá)了這類染色體的一個(gè)句子。7.4 基元的提取

37、7.4.1 圖形邊界或骨架的基元選擇 討論 描述一種圖形采用哪種基元最合適沒(méi)有統(tǒng)一的標(biāo)準(zhǔn)和方法，因圖形曲線的不同而異。 一般可兼顧兩點(diǎn) 基元的提取方法盡可能簡(jiǎn)單 描述曲線的句子盡量短一些7.4 基元的提取7.4.2 按區(qū)域劃分成多邊形近似的基元 這種基元著眼于待識(shí)別圖形的區(qū)域。 將待識(shí)別的圖形理想化為一個(gè)多邊形，再以若干個(gè)凸多邊形的“并”來(lái)表示該多邊形，而凸多邊形又用若干半平面的“交”來(lái)組成。 用形式語(yǔ)言表示 半平面是字母 凸多邊形是由這些字母組成的字 由這些字組成的句子就相當(dāng)于代表圖形的多邊形 可采用凸多邊形作為基元7.4 基元的提取7.4.2 按區(qū)域劃分成多邊形近似的基元 例子：采用凸多邊

38、形作為基元的五邊形 用窮舉試探法求取基元的試探步驟 例子7.5 形式語(yǔ)言在圖形識(shí)別中的應(yīng)用7.5.1 各種文法用于模式識(shí)別的功能比較 前面討論了基元的提取問(wèn)題，下面要根據(jù)各種提取的基元來(lái)構(gòu)造適當(dāng)?shù)奈姆ǎ援a(chǎn)生出描述所要識(shí)別的圖形的一種語(yǔ)言。 從理論上講，最好是能有一個(gè)推斷文法的機(jī)器，它能根據(jù)給定的一些符號(hào)串的集合，推斷出一個(gè)合適的文法。 但遺憾的是，在實(shí)際中除了某些非常特殊的情況外，至今還沒(méi)有這樣一種有效的機(jī)器。 一般上仍是由設(shè)計(jì)者憑自己的經(jīng)驗(yàn)和所謂的先驗(yàn)知識(shí)來(lái)構(gòu)造文法。7.5 形式語(yǔ)言在圖形識(shí)別中的應(yīng)用7.5.1 各種文法用于模式識(shí)別的功能比較 構(gòu)造圖形識(shí)別的文法仍以前面介紹的形式語(yǔ)言為基礎(chǔ)

39、。 一般來(lái)說(shuō)，希望采用有很強(qiáng)描述圖形能力的文法，但這樣做反過(guò)來(lái)又增加識(shí)別器的復(fù)雜性。7.5 形式語(yǔ)言在圖形識(shí)別中的應(yīng)用7.5.1 各種文法用于模式識(shí)別的功能比較 正則文法的生成式最為簡(jiǎn)單，它所受的限制也最多，描述圖形模式的能力最差，但在句法分析中是最容易實(shí)現(xiàn)的，因?yàn)橐欢ù嬖谝粋€(gè)確定的有限態(tài)自動(dòng)機(jī)與之對(duì)應(yīng)。 上下文無(wú)關(guān)文法所受的限制要少一些，描述能力要強(qiáng)一些，但為了接受這種文法產(chǎn)生的語(yǔ)言，通常要求非有限、非確定性的句法分析步驟，與之對(duì)應(yīng)的是一個(gè)不確定的下推自動(dòng)機(jī)，因而實(shí)現(xiàn)起來(lái)比確定的有限態(tài)自動(dòng)機(jī)復(fù)雜。 上下文有關(guān)文法所產(chǎn)生的語(yǔ)言的分析，就更困難了。7.5 形式語(yǔ)言在圖形識(shí)別中的應(yīng)用7.5.1 各

40、種文法用于模式識(shí)別的功能比較 例子 采用上下文有關(guān)文法 采用上下文無(wú)關(guān)文法 采用正則文法 結(jié)果分析 n為有限整數(shù)時(shí)可構(gòu)造上下文無(wú)關(guān)文法，n限于3以內(nèi)可構(gòu)造正則文法。 但顯然，正則文法由于其規(guī)則數(shù)增多，造成其復(fù)雜性增加，而且隨著n的增大，規(guī)則數(shù)更是倍增，相比而言，上下文無(wú)關(guān)文法就簡(jiǎn)潔得多。7.5 形式語(yǔ)言在圖形識(shí)別中的應(yīng)用7.5.1 各種文法用于模式識(shí)別的功能比較 討論 在具體應(yīng)用時(shí)，只能根據(jù)問(wèn)題，在增加文法描述能力和簡(jiǎn)化句法分析之間權(quán)衡，采取一些辦法來(lái)進(jìn)行折衷，針對(duì)具體問(wèn)題來(lái)構(gòu)造文法。 一般可通過(guò)對(duì)正則文法進(jìn)行某些修改而使問(wèn)題簡(jiǎn)化。 例如文法的形式可能是上下文無(wú)關(guān)的，但設(shè)計(jì)語(yǔ)言則可以用有限態(tài)語(yǔ)

41、言來(lái)近似。7.5 形式語(yǔ)言在圖形識(shí)別中的應(yīng)用7.5.1 各種文法用于模式識(shí)別的功能比較 討論 此外，還要注意不要使構(gòu)造的文法所產(chǎn)生的符號(hào)串過(guò)剩。 圖形符號(hào)串的數(shù)目總是有限的，但多數(shù)情況下所構(gòu)造的文法，可能產(chǎn)生數(shù)目很大或無(wú)限多的符號(hào)串。 雖然希望過(guò)剩的符號(hào)串與代表圖形的符號(hào)串相似，但遺憾的是實(shí)際情況往往不是這樣，過(guò)剩的符號(hào)串常常是由文法自行構(gòu)造出來(lái)的。 當(dāng)過(guò)剩的符號(hào)串包含了屬于其它類別的圖形符號(hào)串時(shí)，問(wèn)題就會(huì)變得非常嚴(yán)重，這是必須進(jìn)行校正，把過(guò)剩的符號(hào)串從該文法所產(chǎn)生的語(yǔ)句中排除掉。7.5 形式語(yǔ)言在圖形識(shí)別中的應(yīng)用7.5.1 各種文法用于模式識(shí)別的功能比較 討論 綜上所述，建立一個(gè)文法，要同時(shí)

42、考慮圖形基元的選擇和文法的構(gòu)成，要兼顧文法的描述能力和句法分析系統(tǒng)的簡(jiǎn)潔性，所以文法一般由設(shè)計(jì)者根據(jù)具體情況來(lái)構(gòu)造。 可以先由設(shè)計(jì)者提出基本性的文法和各種折衷方案，然后利用人機(jī)交互系統(tǒng)在計(jì)算機(jī)上進(jìn)行修改和實(shí)驗(yàn)，最終獲得一種高效文法及其推斷。7.5 形式語(yǔ)言在圖形識(shí)別中的應(yīng)用7.5.2 程序文法 為了使字符串文法的結(jié)構(gòu)更為緊湊，可在喬姆斯基文法上加上生成式去向的標(biāo)號(hào)，以規(guī)定某幾條生成式使用之后，下一次只能用規(guī)定的另外哪幾條生成式。 這樣可以使原來(lái)的字符串文法使用起來(lái)更為方便，易于檢查。7.5 形式語(yǔ)言在圖形識(shí)別中的應(yīng)用7.5.2 程序文法 定義和例子 例1 這里，生成式(1)采用成功后可繼續(xù)執(zhí)行

43、(1),(2)或(3)，而且其本身可反復(fù)使用。 生成式(2)成功后去向范圍是(2),(3)，即使用(2)后不能再使用(1)，但可用(2),(3)，這使P的生成語(yǔ)句中a,b,c只能各自連續(xù)地出現(xiàn)。 當(dāng)應(yīng)用的去向范圍遇到空時(shí)，則生成停止。7.5 形式語(yǔ)言在圖形識(shí)別中的應(yīng)用7.5.2 程序文法 例2 程序文法屬于喬姆斯基文法的哪一種形式，決定于生成式的核。 如果生成式的核為上下文無(wú)關(guān)形式，則這個(gè)文法是上下文無(wú)關(guān)的。 如果程序文法的核是正則形式，則該文法是正則文法。7.5 形式語(yǔ)言在圖形識(shí)別中的應(yīng)用7.5.2 程序文法 例3 可以證明，該上下文無(wú)關(guān)文法可以生成an bn cn |n=1 這個(gè)程序文法的

44、簡(jiǎn)潔程度和剛才介紹的生成同樣語(yǔ)言的上下文有關(guān)文法相類似。7.5 形式語(yǔ)言在圖形識(shí)別中的應(yīng)用7.5.3 圖形描述語(yǔ)言PDL(Picture Description Language) 字符串文法中的基元與子模式的連接，按語(yǔ)法規(guī)則只能是左右連接，不能同時(shí)從四面八方連接，這種一維的連接方式不能滿足描述復(fù)雜圖形的要求。 PDL中的基元是由兩個(gè)點(diǎn)（稱為“頭”和“尾”）構(gòu)成的矢量，它可以組成任一復(fù)雜結(jié)構(gòu)的圖形。 對(duì)于二維圖形，該基元就是平面上的一個(gè)有向線段，它只需有兩個(gè)定義點(diǎn)，即頭和尾。 PDL用于描述圖形模式識(shí)別是比較成功的。7.5 形式語(yǔ)言在圖形識(shí)別中的應(yīng)用7.5.3 圖形描述語(yǔ)言PDL PDL基元的

45、連接規(guī)則7.5 形式語(yǔ)言在圖形識(shí)別中的應(yīng)用7.5.3 圖形描述語(yǔ)言PDL PDL基元的連接規(guī)則 一個(gè)基元只能在頭和尾兩點(diǎn)上與其它基元連接，因此它是具有有向支路的圖形結(jié)構(gòu)，可用字符串文法來(lái)處理。 空白基元：用來(lái)產(chǎn)生不連接的結(jié)構(gòu) 零點(diǎn)基元：表示頭和尾處于相同的位置 b：表示基元的頭尾反轉(zhuǎn)7.5 形式語(yǔ)言在圖形識(shí)別中的應(yīng)用7.5.3 圖形描述語(yǔ)言PDL 例子 生成式中無(wú)循環(huán)性 生成式中有循環(huán)性7.5 形式語(yǔ)言在圖形識(shí)別中的應(yīng)用7.5.3 圖形描述語(yǔ)言PDL 討論 采用句法模式識(shí)別，可以提供兩種或多種文法，并用每一種文法對(duì)不同模式樣本進(jìn)行句法分析。 如果一個(gè)樣本能成功地被某一種文法所分析，便可歸為這一

46、類。 如果一個(gè)樣本對(duì)各種文法都得不到被成功分析的結(jié)果，則該文法被拒絕。7.5 形式語(yǔ)言在圖形識(shí)別中的應(yīng)用7.5.3 圖形描述語(yǔ)言PDL 例子作業(yè) 自己定義基元，用PDL文法生成0到5的字符，字符筆劃用七劃樣式。 提示：可參照例題中的基元定義7.5 形式語(yǔ)言在圖形識(shí)別中的應(yīng)用7.5.4 樹(shù)文法 如果一個(gè)圖形模式易于用樹(shù)的結(jié)構(gòu)來(lái)描述，則可采用樹(shù)文法。 它可將一維連接的符號(hào)串文法向多維推廣，是一種應(yīng)用較廣泛的高維文法。7.5 形式語(yǔ)言在圖形識(shí)別中的應(yīng)用7.5.4 樹(shù)文法 例子 對(duì)一個(gè)邊長(zhǎng)為a, b和c的立方體，如果用一維字符串描述，有的邊會(huì)重復(fù)，用樹(shù)表示可直接分成三個(gè)叉，每條邊僅出現(xiàn)一次。7.5 形

47、式語(yǔ)言在圖形識(shí)別中的應(yīng)用7.5.4 樹(shù)文法 樹(shù)的定義：樹(shù)是具有一個(gè)或一個(gè)以上結(jié)點(diǎn)的有限集T，它具有以下性質(zhì)： 具有唯一的被指定為根的結(jié)點(diǎn)。 其余的結(jié)點(diǎn)被分到m個(gè)不相交的集合T1,T2,Tm中，且這些子集的每一個(gè)又都是樹(shù)，稱為T的子樹(shù)。 從定義可以看出，樹(shù)的每個(gè)結(jié)點(diǎn)都是這個(gè)樹(shù)中所包含的某個(gè)子樹(shù)的根。 一個(gè)結(jié)點(diǎn)具有子樹(shù)的個(gè)數(shù)稱為該結(jié)點(diǎn)的秩。秩的相關(guān)定義 秩：一個(gè)結(jié)點(diǎn)的直接分支數(shù)定義為該結(jié)點(diǎn)的秩。 葉結(jié)點(diǎn)：秩為零的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)（終端結(jié)點(diǎn)）。(i)分支結(jié)點(diǎn)：秩不為零的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)（非終端結(jié)點(diǎn)）。7.5 形式語(yǔ)言在圖形識(shí)別中的應(yīng)用7.5.4 樹(shù)文法 討論 在計(jì)算機(jī)中數(shù)據(jù)的表示是有序的，所以子樹(shù)的排

48、列也是有一定的相對(duì)次序。 同一層上各子樹(shù)間相互交換位置就構(gòu)成不同的樹(shù)。 因此，樹(shù)是有序的。 比如前面的立方體，葉結(jié)點(diǎn)就是有序的。7.5 形式語(yǔ)言在圖形識(shí)別中的應(yīng)用7.5.4 樹(shù)文法 結(jié)論 用樹(shù)來(lái)描述圖形時(shí)，不但要知道樹(shù)的結(jié)點(diǎn)，還要知道與其相鄰結(jié)點(diǎn)的關(guān)系。 這里，相鄰結(jié)點(diǎn)的關(guān)系確定了基元與圖形的其它子結(jié)構(gòu)間的物理關(guān)系。7.5 形式語(yǔ)言在圖形識(shí)別中的應(yīng)用7.5.4 樹(shù)文法 秩的集合的表示 設(shè)X是結(jié)點(diǎn)符號(hào)的有窮集，a是結(jié)點(diǎn)的編號(hào)，(a)是結(jié)點(diǎn)a上的一棵樹(shù)，則(a)的秩的集合可用r(a)表示。 若(a)能夠具有的秩為r1,r2,rn，可寫成r(a)=r1,r2,rn 例子 樹(shù)的另一種表示法 圓括號(hào)法

49、與左括號(hào)緊挨著的字母表示根。 其子樹(shù)是緊挨著根字母的一串左右成對(duì)的括號(hào)中的內(nèi)容。 例子7.5 形式語(yǔ)言在圖形識(shí)別中的應(yīng)用7.5.4 樹(shù)文法 樹(shù)文法的定義 上下文無(wú)關(guān)文法和樹(shù)文法的對(duì)應(yīng)關(guān)系 如果將樹(shù)用圓括號(hào)法表示，則上下文無(wú)關(guān)語(yǔ)言中的字符串和由樹(shù)文法生成的樹(shù)之間存在對(duì)應(yīng)關(guān)系。 描述 GT中的每一次推導(dǎo)，就用圓括號(hào)表示出了推導(dǎo)過(guò)程中生成式的使用次序，根據(jù)它可確定生成式的構(gòu)造。 例子作業(yè) 試用樹(shù)文法生成單位邊長(zhǎng)的立方體，定義三個(gè)基元為立方體的三種方向的邊。7.6 句法分析 若對(duì)兩類模式進(jìn)行分類，應(yīng)判別描述模式的字符串x是否可由文法G產(chǎn)生。 假若G能生成x，則x屬于1，否則x屬于2。 推廣到M類模式，

50、應(yīng)先確定M種文法，它能生成M類語(yǔ)言L(Gi)，i=1,2,M。 一個(gè)未知類別的模式字符串x，當(dāng)它是屬于L(Gi)中的一個(gè)句子，則x屬于i。 假如x不屬于任何一種語(yǔ)言，則它可被拒識(shí)，即x不被接受為M類中的任一類。7.6 句法分析 句法識(shí)別其原理圖7.6 句法分析 采用有限態(tài)自動(dòng)機(jī)對(duì)未知模式進(jìn)行識(shí)別，實(shí)質(zhì)上是對(duì)輸入字符串從左向右進(jìn)行推導(dǎo)，判斷它是否為機(jī)器所接受。 這種識(shí)別方法計(jì)算工作量小，但是沒(méi)有對(duì)語(yǔ)法結(jié)構(gòu)進(jìn)行分析。 在某些情況下，不僅需要判斷字符串是否屬于L(G)，還要知道它的語(yǔ)法結(jié)構(gòu)，以便改進(jìn)文法，這就需要采用句法分析（句法剖析）。7.6 句法分析7.7.1 通過(guò)生成樹(shù)的句法分析 生成樹(shù)構(gòu)造原

51、則 已知一個(gè)句子x和文法G，若x是用上下文無(wú)關(guān)文法生成的，則其生成樹(shù)可用如下原則構(gòu)造： 把推導(dǎo)中出現(xiàn)的屬于VT的元素作為樹(shù)的葉，屬于VN的元素作為樹(shù)的結(jié)點(diǎn)，每一片葉和每一個(gè)結(jié)點(diǎn)都設(shè)置一個(gè)標(biāo)號(hào)。 將S作為樹(shù)根的標(biāo)號(hào)。 如果一個(gè)結(jié)點(diǎn)的后代子句中，至少有一個(gè)字符與它本身不同，則該結(jié)點(diǎn)的標(biāo)號(hào)必屬于VN 。 如果結(jié)點(diǎn)A有k個(gè)直接后代A1, A2, ,Ak，且它們是從左到右排列。則一定存在這樣一條生成式：A- A1A2Ak 。7.6 句法分析7.7.1 通過(guò)生成樹(shù)的句法分析 分析的兩種方法：“自上而下”和“自下而上” “自上而下”分析法是從G中的起始符S著手，應(yīng)用P中的生成式從左至右逐個(gè)代換非終止符，以得

52、到x。 “自下而上”分析法是從x本身著手，反方向使用生成式，尋找其中與某個(gè)生成式右側(cè)部分相同的字符子串，將它用生成式左邊的字符代換，直至最后達(dá)到起始符S。7.6 句法分析7.7.1 通過(guò)生成樹(shù)的句法分析 例子 分析a2b2c2 分析a2bc 自下而上 自上而下7.6 句法分析7.7.2 CKY(Cocke-Kasami-Younger)分析算法 采用樹(shù)結(jié)構(gòu)的分析算法實(shí)質(zhì)上是窮舉試探，它對(duì)任意上下文無(wú)關(guān)文法所需的分析時(shí)間，可能按字符串長(zhǎng)度呈指數(shù)增長(zhǎng)。 為此，采用CKY的分析算法，其時(shí)間為輸入串長(zhǎng)度的三次方。7.6 句法分析7.7.2 CKY(Cocke-Kasami-Younger)分析算法 問(wèn)

53、題描述 設(shè)描述某類模式的文法是上下文無(wú)關(guān)的，G=(VN,VT,P,S)，其生成式是喬姆斯基范式。 設(shè)輸入字符串x=a1a2an, |x|=n，要求設(shè)計(jì)CKY算法來(lái)判斷x是否屬于L(G)。 CKY算法的關(guān)鍵 構(gòu)表原則 構(gòu)表步驟7.6 句法分析7.7.2 CKY(Cocke-Kasami-Younger)分析算法 CKY算法實(shí)例7.6 句法分析7.7.3 最小距離誤差的句法校正分析 上面的識(shí)別過(guò)程并未考慮圖形模式的隨機(jī)干擾。 實(shí)際上，在獲取模式的基元描述時(shí)，由于隨機(jī)噪聲的干擾，可能發(fā)生部分的基元描述錯(cuò)誤。 例：模式的正確描述字符串為abcbbc，受干擾后成為一有誤差的字符串a(chǎn)bbbbac。 為了識(shí)

54、別這種存在某些誤差的串，在比較簡(jiǎn)單的場(chǎng)合，可以采用通過(guò)計(jì)算最小距離誤差的校正句法分析。7.6 句法分析7.7.3 最小距離誤差的句法校正分析 字符串的相似性度量 字符串中的誤差通常歸納為三類：代換誤差、抹去誤差和插入誤差，可將它們用相應(yīng)的轉(zhuǎn)換式來(lái)表示。 代換誤差的轉(zhuǎn)換 抹去誤差的轉(zhuǎn)換 插入誤差的轉(zhuǎn)換 轉(zhuǎn)換距離 例子7.6 句法分析7.7.3 最小距離誤差的句法校正分析 誤差覆蓋文法的構(gòu)成 最小距離誤差的句法校正分析 設(shè)L(G)是一給定文法，y是一個(gè)給定的帶有誤差的句子，則最小距離誤差的句法校正分析實(shí)質(zhì)上就是在L(G)中找出x，使其滿足最小距離準(zhǔn)則。 d(x,y)的計(jì)算： 構(gòu)成一個(gè)誤差校正程序的

55、過(guò)程時(shí)，修改給定文法G，把它擴(kuò)大為G，使得L(G)不僅包括L(G)，而且包括能生成具有上述三類誤差的所有可能的句子。 根據(jù)G對(duì)帶有誤差的句子進(jìn)行分析，計(jì)算能產(chǎn)生三類誤差的生成式的最少應(yīng)用次數(shù)，從而求得關(guān)于最小距離的度量。 構(gòu)成誤差覆蓋文法G的過(guò)程7.6 句法分析7.7.3 最小距離誤差的句法校正分析 最近鄰分類 兩類模式 若已知兩類模式，分別用文法G1和G2來(lái)描述，其誤差覆蓋文法分別為G1和G2。對(duì)于一個(gè)待分類的輸入模式x，用最小距離誤差分析算法計(jì)算出它與L(G1)和L(G2)之間的距離分別為d(x, L(G1)和d(x, L(G2)。如果有d(x, L(G1)d(x,L(G2)，則x屬于L(

56、G1) ，否則x屬于L(G2)。 c類模式 對(duì)于c類模式情況，可對(duì)相應(yīng)的c個(gè)文法G1,G2,GL分別進(jìn)行最小距離誤差校正句法分析，計(jì)算出待分類的輸入模式x和各類語(yǔ)言間的距離d(x,L(Gk)，k=1,2,c。若對(duì)于所有的ji，有d(x, L(Gi)d(x, L(Gj)，則x屬于L(Gi) 。ji 7.7 句法模式識(shí)別的隨機(jī)文法 在模式識(shí)別中，由于測(cè)量噪聲的影響以及對(duì)模式識(shí)別的特征可能缺乏全面的知識(shí)，使得被研究的過(guò)程存在著某種程度的不確定性，造成描述這類模式的語(yǔ)言的歧異性。 對(duì)于一個(gè)特定模式類產(chǎn)生的字符串，本來(lái)是由某一種文法說(shuō)明的，但實(shí)際上除了該文法外還有其它文法也能產(chǎn)生該類中的字符串。 例子

57、由文法G1產(chǎn)生的語(yǔ)言L(G1)中有句子aaab，由文法G2產(chǎn)生的語(yǔ)言L(G2)中有句子baab。由于測(cè)量上的誤差，可能使aaab變成abab，也可能使baab變成abab。如果以此為訓(xùn)練樣本來(lái)推斷G1和G2，兩種語(yǔ)言L(G1)和L(G2)就變成相交的了。7.7 句法模式識(shí)別的隨機(jī)文法 為了解決這類問(wèn)題，提出了用隨機(jī)語(yǔ)言的處理方法 對(duì)于一種語(yǔ)言L中的每一條字符串x，分配一個(gè)概率p(x)，它用來(lái)表征L的不確定性。 如果一個(gè)模式文法可能產(chǎn)生某些“不想要”的句子，就可分配以很小的概率。 “不想要”的句子是由噪聲產(chǎn)生的，并不真正代表該類中的模式。 把形式語(yǔ)言的概念推廣到隨機(jī)語(yǔ)言有兩種途徑 把文法的生成式隨機(jī)化 把識(shí)別裝置的狀態(tài)轉(zhuǎn)移條件隨機(jī)化7.7 句法模式識(shí)別的隨機(jī)文法7.7.1 隨機(jī)文法 定義 例子 由隨機(jī)文法GS生成隨機(jī)語(yǔ)言L