康厚良,楊玉婷

(1.蘇州市職業(yè)大學(xué) 體育部,江蘇 蘇州 215000;2.蘇州市職業(yè)大學(xué) 計(jì)算機(jī)工程學(xué)院,江蘇 蘇州 215000)

東巴文是一種十分原始的圖畫(huà)象形文字[1]，作為人類(lèi)早期圖畫(huà)文字向象形文字、標(biāo)音文字過(guò)渡的文字形式，它既具有圖畫(huà)文字以圖表意的特點(diǎn)，又具有象形文字象形、會(huì)意、指事、形聲的功能[2].2003年，使用東巴文撰寫(xiě)的東巴古籍被聯(lián)合國(guó)教科文組織列入世界記憶遺產(chǎn)名錄[3-4].

表1 東巴字素的分類(lèi)
Tab.1 Classification of Dongba hieroglyphic

圖1 字符的二值圖及不同分辨率的采樣結(jié)果Fig.1 Binary map and sampling results of different resolutions

(1)小圖的特征曲線及簡(jiǎn)化圖 (2)大圖的特征曲線及簡(jiǎn)化圖圖2 不同采樣下東巴字的特征曲線和簡(jiǎn)化曲線Fig.2 The feature curve and simplified curve of Dongba character under different sampling

從文字的結(jié)構(gòu)要素分析[5-7]，東巴字可細(xì)分為單素字和復(fù)素字，如表1所示.單素字作為東巴文字的基本結(jié)構(gòu)，它的圖畫(huà)特性使人們研究文字特征時(shí)可以參考計(jì)算機(jī)視覺(jué)中形狀的處理方法[8-12].提取單素字輪廓的特征部件，分析其中所包含的共性元素，對(duì)于研究東巴象形文字的分類(lèi)算法，分析同類(lèi)單素字的結(jié)構(gòu)特征，研究東巴文字的造字方法有著非常重要的意義.

目前，對(duì)東巴字的檢索和識(shí)別研究主要圍繞東巴字的預(yù)處理[13-14]、東巴字的特征提取[15-17]、文字識(shí)別[18-21]等3方面展開(kāi)，涉及東巴字的基礎(chǔ)分類(lèi)[13]、文字圖像去噪、線條細(xì)化、字符特征曲線提取[15-16]、簡(jiǎn)化[16]及識(shí)別[17-20]等內(nèi)容.而關(guān)于東巴文字特征部件提取的相關(guān)研究很少，僅在討論CDPM算法時(shí)有少量涉及字符局部特征曲線提取的內(nèi)容[16].

在形狀匹配領(lǐng)域中廣泛應(yīng)用的部件表示法(part-based representations)能夠有效提高形狀識(shí)別算法的健壯性，同時(shí)在形狀分類(lèi)理論中也發(fā)揮著重要作用[21].因此，深入分析東巴象形文字的圖畫(huà)特征，結(jié)合形狀匹配領(lǐng)域中的部件表示法，給出了一種適用于東巴象形文字的特征部件自動(dòng)計(jì)算與提取算法(automatic calculating and extracting feature parts，ACEFP).該算法通過(guò)雙分辨率采樣獨(dú)立分析單個(gè)文字的輪廓特征曲線并自動(dòng)提取東巴字的特征部件，然后使用少量樣本即可準(zhǔn)確計(jì)算同類(lèi)字符的特征部件數(shù)量，與傳統(tǒng)的形狀局部特征曲線提取算法相比[22-24]，ACEFP能夠自動(dòng)完成對(duì)象特征曲線中特征部件的提取和統(tǒng)計(jì)工作，得到的解穩(wěn)定、可靠，保證了同類(lèi)文字所包含的特征部件及數(shù)量完全保持一致.

ACEFP算法包括3個(gè)部分：①獨(dú)立分析單個(gè)文字的特征，提取字符的特征曲線；②提取東巴字的特征部件；③使用少量樣本統(tǒng)計(jì)同類(lèi)文字應(yīng)包含的部件數(shù)量.

1 東巴字的特征分析

特征部件指的是從對(duì)象特征曲線中提取的直觀的、容易被觀察者直接獲取的包含對(duì)象局部特征的曲線[21].為了保持人類(lèi)觀察事物的習(xí)慣并使用計(jì)算機(jī)自動(dòng)提取東巴字的特征部件，使用雙分辨率采樣法在快速獲取東巴字整體特征的同時(shí)，還能保留其細(xì)節(jié)特征.其中，低分辨率采樣能夠保留字符的整體特征，減少字符特征曲線中潛在的異常點(diǎn)(特別是凹點(diǎn))，更容易確定局部曲線的分割點(diǎn).但是，由于低分辨率采樣可能存在細(xì)節(jié)特征丟失過(guò)多的情況.因此，以高分辨率采樣獲得的字符特征曲線作為部件提取的對(duì)象，參考低分辨率特征曲線中獲得的分割點(diǎn)完成高分辨率特征曲線的分割，使得到的特征部件完整、有效，且能夠保留字符的絕大多數(shù)特征.雖然高分辨率采樣也包含字符的總體特征，但是由于其中存在較多的噪音點(diǎn)和異常點(diǎn)，容易影響特征部件分割點(diǎn)提取的準(zhǔn)確性，因此將兩者結(jié)合起來(lái)，最大限度彌補(bǔ)各自的不足.

以字符外接矩形中較短的邊為基準(zhǔn)，通過(guò)多次試驗(yàn)，最終選擇短邊長(zhǎng)為50像素的采樣作為低分辨率采樣，而短邊長(zhǎng)為75像素的采樣作為高分辨率采樣，采樣結(jié)果如圖1所示.為了方便描述，將低分辨率采樣得到的采樣圖稱(chēng)為小圖，而將高分辨率采樣得到的采樣圖稱(chēng)為大圖.

然后，采用基于鏈碼的連通域優(yōu)先級(jí)標(biāo)記算法(CDPM)和東巴象形文字特征曲線簡(jiǎn)化算法[16]提取東巴字的特征曲線、去除曲線中的冗余點(diǎn)和異常點(diǎn).對(duì)圖1中采樣字符的處理效果如圖2(1)、(2)所示.此時(shí)，由小圖得到的簡(jiǎn)化結(jié)果，其局部特征曲線分割點(diǎn)顯著，噪音點(diǎn)較少，但部分細(xì)節(jié)特征丟失嚴(yán)重；而大圖得到的簡(jiǎn)化結(jié)果，幾乎保留了文字的所有細(xì)節(jié)，但曲線中存在較多的噪音點(diǎn)和冗余點(diǎn).因此，采用兩種不同分辨率采樣彌補(bǔ)了各自的不足.

(1)輪廓曲線 (2)曲線中的凹點(diǎn) (3)分割圖圖3 小圖采樣的字符輪廓及分割Fig.3 Character contour and segmentation of small image sampling

圖4 直線段的合并Fig.4 Merging of straight line segments

(1)曲線分割 (2)2點(diǎn)曲線的合并 (3)3點(diǎn)曲線的合并圖5 局部曲線的合并Fig.5 Merging of local curve

2 特征部件的提取

曲線的凹凸特性是人類(lèi)視覺(jué)識(shí)別的重要特性[25]，在形狀匹配領(lǐng)域常使用形狀中的凸弧來(lái)表示形狀的局部特征[26]，因此，以字符特征曲線中的凹點(diǎn)[27]作為分割點(diǎn)完成曲線的分割.

由于小圖中包含的頂點(diǎn)數(shù)量較少，意味著其中可能潛在的冗余點(diǎn)和異常點(diǎn)也較少，更容易得到準(zhǔn)確的特征部件分割點(diǎn).因此，以小圖的字符特征曲線為處理對(duì)象，標(biāo)記曲線上的凹點(diǎn)，并以凹點(diǎn)為分割點(diǎn)實(shí)現(xiàn)字符特征曲線的初次分割，分割過(guò)程如圖3(2)、(3)所示.

顯然，僅僅依靠凹點(diǎn)分割得到的局部特征曲線過(guò)細(xì)、過(guò)碎，并且還包含若干無(wú)效曲線.為保證每個(gè)特征部件都至少包含一個(gè)特征，需要對(duì)曲線的分割結(jié)果進(jìn)行合并.分析圖3(3)的分割結(jié)果可知，需要合并的局部曲線包含兩種類(lèi)型.

1)由兩個(gè)連續(xù)凹點(diǎn)組成的曲線，如圖3(3)中的①所示.它實(shí)際上是一條直線段，線段的端點(diǎn)是兩個(gè)連續(xù)的凹頂點(diǎn)，這類(lèi)曲線不包含字符的任何特征，可以合并.

2)由1個(gè)凹頂點(diǎn)+1個(gè)凸頂點(diǎn)+1個(gè)凹頂點(diǎn)等3個(gè)頂點(diǎn)組成的局部曲線，這類(lèi)曲線有的包含了字符的特征，如圖3(3)中的②包含了“鹿”犄角的一個(gè)尖端，不應(yīng)被合并；而與②相鄰的曲線段③，它雖然也和②具有相同的結(jié)構(gòu)，但是它不包含任何字符特征，應(yīng)被合并.因此，對(duì)于此類(lèi)曲線，若滿足條件，才可以合并；否則，保留.

2.1 直線段合并

根據(jù)東巴象形文字特征曲線簡(jiǎn)化算法可知[16]，在曲線簡(jiǎn)化的每個(gè)階段，一般使用一條新的線段替換原有的一對(duì)相鄰的線段s1和s2，這條新的線段是通過(guò)連接s1∪s2的兩個(gè)端點(diǎn)得到的，而線段的合并順序按照度量K值從小到大的順序進(jìn)行，K的計(jì)算公式為：

其中，β(s1,s2)為線段s1和s2的頂點(diǎn)轉(zhuǎn)向角，而l表示歸一化后的線段長(zhǎng)度.由于K(s1,s2)∝β(s1,s2).因此，局部直線段應(yīng)與K值(或β值)較小的一端合并，保留K值較大的一端.如圖4所示，假設(shè)待合并的直線段是由頂點(diǎn)P1和P2組成的C2，而C1和C3是與C2相鄰的局部曲線段，那么若轉(zhuǎn)向角β12>β23，則C2與C3合并；否則，C2與C1合并.

2.2 由三個(gè)頂點(diǎn)組成的曲線合并

由三個(gè)頂點(diǎn)組成的局部曲線可能包含字符的獨(dú)立特征，例如“嘴巴”、“耳朵”或者“犄角”等，此時(shí)組成曲線的兩條線段一般都有較大的轉(zhuǎn)向角以表征字符特征，并且該轉(zhuǎn)向角與曲線段中唯一的凸頂點(diǎn)相對(duì)應(yīng)，因此當(dāng)曲線中凸頂點(diǎn)的轉(zhuǎn)向角≥90°時(shí)，保留原曲線；否則，合并.

合并時(shí)，由于三個(gè)頂點(diǎn)組成的曲線中包含兩條線段，因此，將兩條線段分別與它鄰近的曲線合并即可.如圖5所示，小圖的特征曲線經(jīng)過(guò)兩次合并，字符中所包含的局部曲線由原來(lái)的13條減少到7條，且每條都包括至少一個(gè)或多個(gè)字符特征.

通過(guò)合并，每條局部曲線都至少包含一個(gè)或多個(gè)形狀特征，但是合并過(guò)程也可能造成原有分割點(diǎn)由凹點(diǎn)變?yōu)橥裹c(diǎn)，使局部特征曲線的完整性受到影響.因此，合并后需進(jìn)一步校正分割點(diǎn)，保證所有分割點(diǎn)都為凹頂點(diǎn)，如圖6所示.

(1)分割點(diǎn)校正前 (2)分割點(diǎn)校正后圖6 分割點(diǎn)的校正Fig.6 Correction of split point

圖7 提取字符的特征部件Fig.7 Extracting feature parts for characters

2.3 提取字符的特征部件

通過(guò)合并，組成小圖輪廓的局部特征曲線已相對(duì)合理，如圖7(1)、(2)所示.因此，以小圖得到的分割點(diǎn)為參考，對(duì)大圖的特征曲線進(jìn)行分割，從而獲得字符最終的特征部件.

提取大圖特征部件的關(guān)鍵是找到大圖特征曲線中與小圖中對(duì)應(yīng)分割點(diǎn)最相似的凹點(diǎn)，并將其作為大圖特征曲線的分割點(diǎn).為判斷凹點(diǎn)的相似性，分別做輪廓外接矩形中心點(diǎn)與分割點(diǎn)的連線，則特征曲線中的頂點(diǎn)(包括分割點(diǎn))均可以用中心點(diǎn)與頂點(diǎn)組成的向量來(lái)表示.那么，判斷兩個(gè)頂點(diǎn)(或頂點(diǎn)與分割點(diǎn))的相似性，實(shí)際上就是判斷兩個(gè)向量的相似性，因此滿足兩個(gè)條件：①向量間的夾角應(yīng)最?。虎跉w一化的向量模的差值最小，即：

則θi為：

由于字符特征曲線中的分割點(diǎn)是特殊的頂點(diǎn)，它除了具有頂點(diǎn)的屬性外，還起到分割局部曲線的作用.因此，使用下標(biāo)vi和svi分別表示普通頂點(diǎn)和分割點(diǎn)，則對(duì)于由m個(gè)頂點(diǎn)組成的小圖，它的頂點(diǎn)和分割點(diǎn)的下標(biāo)為svi和ssvi；而由n個(gè)頂點(diǎn)組成的大圖，它的下標(biāo)為bvj和bsvj.那么，小圖特征曲線中的分割點(diǎn)向量與大圖中頂點(diǎn)向量間的夾角Δθ為：

Δθij=|θsvi-θbvj|i∈{1,2,…,m},j∈{1,2,…,n}.

同時(shí)，設(shè)大圖的外接矩形在x方向上的長(zhǎng)度為L(zhǎng)enbx，y方向?yàn)長(zhǎng)enby，而小圖的分別為L(zhǎng)ensx和Lensx.則將大圖統(tǒng)一為小圖的比例，大圖中的頂點(diǎn)向量表示為：

而小圖中的分割點(diǎn)向量表示為：

則大圖的頂點(diǎn)向量和小圖的分割點(diǎn)向量之間的模長(zhǎng)差為：

因此，在所有的大圖頂點(diǎn)中，與小圖中的第i個(gè)分割點(diǎn)Pssvi最為相似的大圖頂點(diǎn)Pbvj為：

Similar(Pssvi,Pbvi)={Pssvi→Pbvi|min{Δθij*ΔLenij}},i∈{1,2,…,m},j∈{1,2,…,n}}.

如圖7(3)所示，根據(jù)小圖的分割點(diǎn)重新分割大圖的特征曲線，大圖所包含的局部特征曲線由原來(lái)的10條減少到了8條.顯然，通過(guò)二次分割及合并，已得到相對(duì)合理的字符特征部件.

3 同類(lèi)東巴字的特征部件數(shù)量統(tǒng)計(jì)

使用第2章中的操作步驟提取“牲畜”類(lèi)中10個(gè)東巴字的特征部件結(jié)果如表2所示.除了兩個(gè)較特殊的字符外，其他字符的特征部件均為5個(gè)，分別描述了字符的兩個(gè)犄角、耳朵、嘴巴和上半身.由此可知，“牲畜”類(lèi)東巴字的特征部件數(shù)量為5條.

表2 同類(lèi)字符的特征曲線
Tab.2 Feature curves of the same type of characters

圖8 按同類(lèi)型字符部件數(shù)量合并字符的局部曲線Fig.8 Merging local curves according to the number of character parts of the same type

東巴字“鹿”的特征部件過(guò)多是由于與其他文字相比，它的犄角包含了過(guò)多的細(xì)節(jié)特征.但是，這并未影響到“牲畜”類(lèi)字符特征部件數(shù)量的統(tǒng)計(jì).說(shuō)明，即使字符包含較多細(xì)節(jié)特征，也不會(huì)對(duì)統(tǒng)計(jì)結(jié)果產(chǎn)生過(guò)大的影響，并且通過(guò)對(duì)字符“鹿”在圖7(3)中的局部曲線進(jìn)行進(jìn)一步合并，發(fā)現(xiàn)它的特征部件呈現(xiàn)出與“牲畜”類(lèi)字符相一致的局部形態(tài)特征，如圖8所示.

4 算法的復(fù)雜度分析

ACEFP包括3個(gè)組成部分.若假設(shè)字符G的特征曲線為Cur，其中包含p個(gè)頂點(diǎn)，m條局部曲線，k個(gè)特征部件，且m≥k.本質(zhì)上k即為最終統(tǒng)計(jì)得出的部件數(shù)量，那么：

1)提取字符特征曲線.本階段采用CDPM算法和東巴文字簡(jiǎn)化算法實(shí)現(xiàn)字符特征曲線的提取及簡(jiǎn)化操作，由于兩種算法的時(shí)間復(fù)雜度均為O(p)，因此本階段的時(shí)間復(fù)雜度O(n1)≈O(p).

2)提取字符的特征部件.本階段包括3個(gè)步驟：①以凹點(diǎn)為分割點(diǎn)完成字符特征曲線的初次分割，時(shí)間復(fù)雜度為O(p)；②判定m條局部曲線的類(lèi)型完成局部曲線的初次合并(包括直線段合并和三點(diǎn)合并)，時(shí)間復(fù)雜度為O(m)；③將局部曲線合并為指定的k個(gè)特征部件.最壞情況下，在上一個(gè)步驟中沒(méi)有任何曲線發(fā)生合并，則此時(shí)的時(shí)間復(fù)雜度為O(m).因此，本階段的時(shí)間復(fù)雜度O(n2)=O(p)+O(m)+O(m)，由于p?m>k，可得O(n2)≈O(p).

3)統(tǒng)計(jì)同類(lèi)型東巴字的部件數(shù)量.由于同類(lèi)型東巴字的個(gè)數(shù)十分有限，因此本階段的時(shí)間復(fù)雜度O(n3)=1.

由上可知，東巴象形文字特征部件的自動(dòng)計(jì)算與提取算法的綜合時(shí)間復(fù)雜度O(n)=O(n1)+O(n2)+O(n3)≈O(p)，說(shuō)明算法的時(shí)間復(fù)雜度是線性的.

5 驗(yàn)證性試驗(yàn)

5.1 準(zhǔn)確性測(cè)試

為驗(yàn)證ACEFP的正確性，選取10類(lèi)具有相同特征的東巴字符作為樣本，其中包括：魚(yú)蟲(chóng)、鳥(niǎo)、花、手、山、房屋、水、祭祀、牲畜和山坡等.由于每種類(lèi)型所包含的字符數(shù)量不同，隨機(jī)選擇每類(lèi)的前一半作為訓(xùn)練樣本用于計(jì)算該類(lèi)型所包含的特征部件數(shù)量，而剩下的另一半作為測(cè)試樣本，用來(lái)檢測(cè)分割及合并算法的準(zhǔn)確性，如表3所示.

表3 10類(lèi)東巴字符列表
Tab.3 List of 10 types of Dongba characters

測(cè)試時(shí)，根據(jù)每類(lèi)特征部件的數(shù)量分割測(cè)試文字，測(cè)試結(jié)果如圖9所示.測(cè)試文字中，小圖的特征部件提取正確率為100%，而大圖的為93.5%，其中，鳥(niǎo)類(lèi)、手類(lèi)和牲畜類(lèi)的大圖部件提取均出現(xiàn)了1個(gè)錯(cuò)誤，這是因?yàn)榕c其他類(lèi)型的文字相比，它們?cè)谀承┚植康淖儺愝^大而引起的.

圖9 測(cè)試文字的分割結(jié)果Fig.9 The segmentation result of testing characters

圖10 按照不同類(lèi)別的特征部件數(shù)量合并待測(cè)字符的局部曲線Fig.10 Merge local curves of characters according to the number of feature parts of different types

另外，在實(shí)際應(yīng)用中，由于待測(cè)文字的類(lèi)別是未知的，需按照各類(lèi)字符所包含的部件數(shù)量對(duì)待測(cè)字符進(jìn)行合并，然后將得到的結(jié)果與模板字符的特征部件逐個(gè)進(jìn)行比較，以此確定待測(cè)字符所屬的類(lèi)別及所包含的部件數(shù)量.根據(jù)表3中的分類(lèi)可知，“山”類(lèi)和“房屋”類(lèi)均包含1個(gè)部件，“水”類(lèi)、“手”類(lèi)、“祭祀”類(lèi)和“山坡”類(lèi)包含2個(gè)部件，“鳥(niǎo)”類(lèi)包含3個(gè)部件，“魚(yú)蟲(chóng)”類(lèi)和“花”類(lèi)包含4個(gè)部件，“牲畜”類(lèi)包含5個(gè)部件.因此，以字符“鹿”為待測(cè)文字，從表3的每一類(lèi)中選擇1個(gè)東巴字作為模板字符，按照特征部件數(shù)量為1～5的順序提取各模板字符的部件，同時(shí)合并待測(cè)字符的8個(gè)部件，合并結(jié)果如圖10所示.

圖10中，根據(jù)模板字符所屬類(lèi)別包含的部件數(shù)提取部件并按照部件數(shù)量進(jìn)行歸類(lèi)，然后將待測(cè)字符“鹿”的部件數(shù)按照1～5的順序進(jìn)行合并，并按部件數(shù)量歸類(lèi)到每一行.容易發(fā)現(xiàn)，與每行的前幾個(gè)模板字符比較，當(dāng)“鹿”的部件數(shù)為5時(shí)，部件的分割點(diǎn)選擇合理、獨(dú)立性好，并與模板字符有較好的對(duì)應(yīng)性；而當(dāng)“鹿”的部件數(shù)為其他值時(shí)，它與該行的前幾個(gè)模板字符也具有較為明顯的差異性，說(shuō)明ACEFP算法在保證字符局部特征完整性的同時(shí)，也能與其他無(wú)關(guān)字符顯著區(qū)分，在顯示字符整體曲線特征的同時(shí)，通過(guò)特征部件也能充分反映字符的局部特征.

5.2 魯棒性測(cè)試

測(cè)試算法魯棒性時(shí)，首先采用數(shù)據(jù)增廣技術(shù)通過(guò)對(duì)待測(cè)字符進(jìn)行旋轉(zhuǎn)、壓縮和拉伸、左/右傾斜等變換，然后使用ACEFP算法提取各個(gè)字符的特征部件，結(jié)果如圖11(見(jiàn)下頁(yè))所示.圖11中的第1行為字符“鹿”的變換結(jié)果，第2行為字符小圖采樣的特征部件，第3行為字符大圖采樣的特征部件.顯然，當(dāng)字符發(fā)生少許形變時(shí)，仍然能夠得到正確的、基本一致的特征部件，說(shuō)明算法的魯棒性較好，且具有良好的尺度、平移和旋轉(zhuǎn)不變性.

6 結(jié)語(yǔ)

東巴文字作為一種圖畫(huà)象形文字，具有非常濃厚的圖畫(huà)特征，因此，結(jié)合形狀匹配領(lǐng)域中的部件表示法，給出了適用于東巴象形文字的特征部件自動(dòng)計(jì)算與提取算法(ACEFP).與傳統(tǒng)的形狀局部特征曲線提取算法相比，ACEFP算法對(duì)字符特征部件的提取及部件數(shù)量的統(tǒng)計(jì)都是自動(dòng)完成的，不需要任何人為的干預(yù)，這使得整個(gè)部件提取過(guò)程更加客觀，而由此所得出的確定解也為研究東巴文字的組成結(jié)構(gòu)、造字過(guò)程等提供有力的技術(shù)支持.

圖11 形變字符的特征部件Fig.11 Feature parts of deformed characters