康厚良 楊玉婷

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

0 引 言

東巴字是一種十分原始的圖畫象形文字[1-2]，作為人類早期圖畫文字向象形文字、標(biāo)音文字過渡的文字形式，它具有圖畫文字以圖表意及現(xiàn)代文字使用簡單線條表意的特點[3-4]。為獨立分析不同文字的特征，一般將東巴文字的基本字素細(xì)分為輪廓型字素和結(jié)構(gòu)型字素2類。輪廓型字素一般通過描摹物體的外在形體[5]來表達(dá)實際含義；而結(jié)構(gòu)型字素則是使用簡單的字符筆畫通過描繪事物的結(jié)構(gòu)或骨架來表達(dá)含義[6]，如表1所示。

表1 東巴基本字素的分類

東巴字以象形符號為基礎(chǔ)，屬于能代表和書寫語言的象形文字符號體系，但仍保留濃厚的原始圖畫意味，未能完全去除掉非文字的圖畫式表意手法，往往和圖像混在一起使用[5]。這使我們無法直接借鑒計算機(jī)視覺領(lǐng)域的形狀處理方法或手寫漢字的識別算法。

東巴文在特征提取、檢索和識別方面的研究起步較晚，相關(guān)文獻(xiàn)較少且連貫性不強(qiáng)，研究內(nèi)容主要圍繞東巴字的預(yù)處理[6-7]、東巴字的特征提取[8-10]、文字識別[11-14]等三方面展開，涉及東巴字的基礎(chǔ)分類[6]、文字圖像去噪、線條細(xì)化、字符特征曲線提取[8-9]、簡化[10]及識別[11-14]等內(nèi)容。其中大多數(shù)的研究都是直接套用已有的形狀特征提取算法或通用的識別算法，忽略了東巴字本身的形態(tài)和結(jié)構(gòu)，無法為研究文字本身提供支持。

圖1 結(jié)構(gòu)型字素的可視化部件

因此，借鑒形狀匹配領(lǐng)域中的部件表示(part-based representations)理論[15-16]，結(jié)合東巴象形文字特征曲線提取及簡化算法，給出了適用于輪廓型字素的可視化部件提取算法(Visual Part Extraction，VPE)，該算法不僅能解決東巴基本字素的一致性表示，提高文字識別算法的健壯性和精確度，同時也為研究東巴字的筆畫、偏旁部首等內(nèi)容提供技術(shù)支持。

1 可視化部件提取算法(VPE)

在形狀匹配領(lǐng)域，部件表示法(part-based representations)能夠有效提高形狀識別算法的健壯性[15]，并且在形狀分類理論中也發(fā)揮著重要作用[16]。Latecki等[17-18]在部件表示法的基礎(chǔ)上提出了可視化部件的概念，并通過使用離散輪廓演化(Discrete Contour Evolution，DCE)算法從對象特征曲線中提取直觀的、容易被觀察者直接獲取的、包含對象可視化局部特征的曲線作為可視化部件[17]。與很多其他方法相比，該方法直觀、容易理解，也更符合人類提取事物特征的習(xí)慣，但存在復(fù)雜度高、多尺度難以定義、參數(shù)解不穩(wěn)定等問題[19]。

東巴文字與形狀極其相似，但它在書寫時具有一定的規(guī)范，直接使用DCE算法提取文字的可視化部件可能會增加算法復(fù)雜度。因此，基于可視化部件的基本理論，結(jié)合東巴字特征曲線提取[9]及簡化[10]算法給出了適用于東巴輪廓型字素的VPE。它的基本思路是：首先將待測字符的特征曲線分割為若干包含字符特征的凸弧；然后，以模板字符的可視化部件為參考實現(xiàn)凸弧的合并及字符間可視化部件的對應(yīng)；最后，完成異常對應(yīng)關(guān)系的調(diào)整。VPE算法簡單、直觀、易于實現(xiàn)，并且保留了人類視覺提取對象特征的習(xí)慣。

1.1 東巴字的預(yù)處理

(a) 模板字符的二值化 (b) 線條細(xì)化 (c) 去除離散冗余元素

(d) 提取特征曲線 (e) 特征曲線的簡化 (f) 提取可視化部件圖2 模板字符“麻雀”的預(yù)處理過程及可視化部件提取

1.2 輪廓型字素特征曲線的過分割

1) 以凹點為起點：凸弧(convex arcs)是特征曲線中被凹點分割開的凸的曲線段[19]。以凹點為起點保證了凸弧的完整性和獨立性。因此，結(jié)合簡單多邊形頂點凸凹性識別算法[21]快速確定字符簡化曲線中的凹點，如圖3(b)中的黑色圓點所示。

(a) 東巴字 (b) 標(biāo)記特征曲線上的凹點

(c) 凸弧的提取 (d) 凸弧的部分合并圖3 東巴字“鴿子”的凸弧提取

2) 按照規(guī)定的方向，順序提取：保證所提取的凸弧在原始特征曲線中方向一致、首尾相連(以前、后兩條凸弧共有的凹端點作為連接點)且排列順序相同。如圖3(c)所示，按照順時針方向順序提取簡化曲線中的凸弧，并使用不同類型的曲線加以區(qū)分。

3) 凸弧的部分合并：提取的凸弧中，可能存在僅由一條直線段組成的凸弧(例如，圖3(c)中的凸?、?，這樣的凸弧是沒有意義的，因此通過計算線段兩個凹端點的權(quán)值大小，將直線段與端點權(quán)值較小的一端合并(詳細(xì)的論證過程見文獻(xiàn)[22])，效果如圖3(d)所示。通過合并，過分割過程中產(chǎn)生的一些無效短弧線得到了合并，留下的均為由3個及以上特征點組成的、包含部分或完整局部字符特征的凸弧[22]。但是，在一些文字中由于粘連點的影響，部分凸弧的合并操作仍無法解決所有的過分割問題，如圖3(d)中的黑色空心圈所示，因此下一階段將進(jìn)一步完成凸弧的合并。

1.3 過分割凸弧的合并及字符間可視化部件的對應(yīng)

按照東巴字的書寫順序[3]可確定模板字符的可視化部件(如圖2(f)所示)，然后將其作為待測字符凸弧合并的參考并完成字符間部件對應(yīng)關(guān)系的確定及待測字符中多余凸弧的合并，從而解決字符簡化曲線中少量噪聲點對可視化部件提取的干擾。因此，定義過分割凸弧的合并規(guī)則為：

以模板字符中可視化部件的位置為參考，合并待測字符中與其有對應(yīng)關(guān)系的鄰近凸弧，直到待測字符中的凸弧數(shù)量與模板字符的部件數(shù)量相同且一一對應(yīng)為止。具體步驟如下：

1) 確定部件/凸弧的位置。在前一階段中，通過部分合并操作去除了曲線中的無效凸弧，保證了剩余凸弧的長度(由3個及以上特征點組成)和有效性，此時使用凸弧/部件的局部中心點表示它們的全局位置，可有效避免當(dāng)凸弧出現(xiàn)少量形變或旋轉(zhuǎn)變化時對凸弧與模板字符部件間對應(yīng)關(guān)系確定的影響。因此，以字符特征曲線的中心點為原點，建立直角坐標(biāo)系，使用部件/凸弧局部中心點在坐標(biāo)系中的向量夾角來表示它的位置。即：

設(shè)字符G的特征曲線為Cur，其中包含p個特征點、n個部件/凸??；字符G的中心點為g0，各部件/凸弧gCuri的局部中心點為gi(i={1,2,…,n})。

Step1以g0為坐標(biāo)原點建立直角坐標(biāo)系。

Step2連接g0和gi，建立部件/凸弧的中心點向量g0gi。

Step3計算g0gi與水平向量g0X的夾角θi(i={1,2,…,n})。使用θi表示部件/凸弧gCuri在整個字符特征曲線中的位置。

(a) 麻雀的部件及中心 (b) 鴿子的凸弧及中心

(c) 兩個字符坐標(biāo)系的疊加圖4 字符的坐標(biāo)系及部件/凸弧的位置信息

2) 找出待測字符中凸弧與模板字符中可視化部件的對應(yīng)關(guān)系。由圖4可知，可視化部件和凸弧在特征曲線中都是按照順時針方向排列的，要確定部件和凸弧之間的對應(yīng)關(guān)系，實際上就是要找出局部中心點向量夾角最小的一對凸弧和部件，而剩余凸弧/部件的對應(yīng)關(guān)系只需沿順時針方向繼續(xù)判斷即可。

由于凸弧具有一定的長度和有效性，使用局部中心點表示提高了它本身的魯棒性，此時將模板字符和待測字符的特征曲線放在同一坐標(biāo)系中，可快速找出局部中心點向量夾角最小的一對，并且當(dāng)待測字符發(fā)生少量形變或旋轉(zhuǎn)時，也不會對部件與凸弧間對應(yīng)關(guān)系的確定產(chǎn)生過大的影響。因此，我們首先歸一化字符中凸弧/部件的中心點向量，使不同字符具有可比較性；然后，移動待測字符坐標(biāo)系至模板字符坐標(biāo)系，使凸弧與部件處于相同坐標(biāo)系中，便于找出對應(yīng)關(guān)系。

為方便描述，設(shè)模板字符為A，特征曲線為Cura，中心點為a0，包含m個可視化部件，部件的局部中心點為ai(i={1,2,…,m})，夾角為θai(i={1,2,…,m})；待測字符為B，特征曲線為Curb，中心點為b0，包含k條凸弧，且m

PartRelationB→A={(bCurj→aCuri)|min(|θbj-θai|)}

式中：j={1,2,…,k},i={1,2,…,m}。因此，字符A中可視化部件和B中凸弧的對應(yīng)關(guān)系如表2所示。

表2 字符間可視化部件/凸弧的對應(yīng)關(guān)系

由于bCur2與aCur1、aCur2存在潛在對應(yīng)關(guān)系，又有bCur1?aCur1且bCur3?aCur2。那么，若bCur1與bCur2合并后的曲線與aCur1的對應(yīng)性更好，則有bCur2?aCur1；反之，若bCur3與bCur2合并后的曲線與aCur2的對應(yīng)性更好，則有bCur2?aCur2。因此，可結(jié)合已確定的關(guān)系進(jìn)一步判斷部件/凸弧間的潛在對應(yīng)關(guān)系。

3) 合并待測字符B中的凸弧。合并時，應(yīng)選擇待測字符B中凸弧與模板字符A中部件相對應(yīng)且夾角和最小的兩條凸弧。因此，對于字符B中的兩條相鄰?fù)够Curx和bCury，如果它們都與字符A中的可視化部件aCuri相對應(yīng)且夾角和最小，則合并。即：

CombineConvexArcsx∪y={(bCurx∪bCury)→aCuri|

min(|θbx-θai|+|θby-θai|)}

式中：i={1,2,…,m},x<<{1,2,…,k},y<<{1,2,…,k}。

(a) 模板字符A(b) 待測字符B

(c) 合并bCur3和bCur4(d) 合并bCur2和圖5 合并待測字符B中的凸弧

(a)(b)(c)(d)圖6 以模板字符部件為依據(jù)提取待測字符的可視化部件

1.4 特殊情況的處理

(a) 模板字符(m=2) (b) 待測字符(c) 合并后的待測字符

(d) 模板字符(m=3) (e) 合并的待測字符圖7 字符的變異對可視化部件提取的影響

由于東巴字的可視化部件反映的是事物的外部形態(tài)，如果兩個字符包含的部件數(shù)量相同且都按照順時針方向排序，那么若仍需要調(diào)整部件間的對應(yīng)關(guān)系，則說明原始的對應(yīng)關(guān)系完全錯誤，如圖8(b)-圖8(d)所示；或者部件間本身就存在較大差異，沒有對應(yīng)關(guān)系。

(a) (b) (c) (d)

(e) (f) (g)圖8 模板字符和待測字符間部件的對應(yīng)關(guān)系校正

因此，若要校正字符間部件的對應(yīng)關(guān)系，首先需找出兩個字符中相似度[23]最高的一對作為字符間對應(yīng)的起始部件，然后按照順時針方向遍歷，即可找出其他部件的對應(yīng)關(guān)系，部件對應(yīng)關(guān)系的校正結(jié)果如圖8(e)-圖8(g)所示。其中：(a)為模板字符和待測字符的整體效果；(b)-(d)為部件的原始對應(yīng)關(guān)系；(e)-(g)為校正后的部件對應(yīng)關(guān)系。

值得注意的是，在東巴字的造字過程中，更多是通過突出顯著特征、形態(tài)變異、綴加元素[4]等方式來區(qū)分不同文字，僅有少量是直接通過旋轉(zhuǎn)文字本身來產(chǎn)生新文字的。因此，為了提高算法的整體效率，在具體實施過程中，一般先對模板字符和待測字符進(jìn)行一次相似性比較[23]，若字符間已有較多可視化部件具有相似性，則1.4節(jié)中所討論的步驟可以忽略。

1.5 復(fù)雜度分析

VPE算法的實施過程主要包括三個步驟，若假設(shè)字符G的特征曲線為Cur，其中：包含p個特征點，m條凸弧，n個可視化部件，且m≥n。本質(zhì)上n即為合并后最終待測字符與模板字符包含的部件數(shù)量，那么：

1) 字符特征曲線Cur的過分割，包括兩步：(1) 曲線中特征點的凹凸性判斷，時間復(fù)雜度O(n11)=O(p)；(2) 凸弧的順序分割，時間復(fù)雜度為O(n12)=O(p)，則該階段的時間復(fù)雜度O(n1)=O(n11)+O(n12)≈O(p)。

2) 過分割凸弧的合并及字符間可視化部件的對應(yīng)，包括三步：(1) 確定字符中可視化部件/凸弧的位置，時間復(fù)雜度O(n21)=O(m)；(2) 找出待測字符中凸弧與模板字符中可視化部件的對應(yīng)關(guān)系，最壞情況下，待測字符中的每條凸弧都需要與模板字符中的部件進(jìn)行比較，所以時間復(fù)雜度O(n22)=O(m×n)；(3) 合并待測字符B中的凸弧，對于模板字符中的n個部件，均需要計算與之對應(yīng)的待測字符中的相鄰兩條凸弧的夾角和，并按照夾角和的大小進(jìn)行排序，最壞情況下，兩兩相鄰的凸弧都需要計算，然后才能判斷可合并的凸弧數(shù)量，因此時間復(fù)雜度O(n23)=O((m-1)×n)。由此，該階段的時間復(fù)雜度O(n2)=O(n21)+O(n22)+O(n23)=O(m)+O(m×n)+O((m-1)×n)，由于m

3) 字符間部件對應(yīng)關(guān)系的校正，包括兩步：(1) 計算待測字符中一個部件與模板字符中所有部件的相似度，時間復(fù)雜度O(n31)=O(n)；(2) 校正待測字符中部件的排列順序，時間復(fù)雜度O(n32)=O(n)。由此，該階段的時間復(fù)雜度O(n3)=O(n31)+O(n32)≈O(n)。

上述3個步驟相互獨立且在計算中沒有交叉，由于步驟3是可選步驟，因此，VPE算法在最壞情況下的整體時間復(fù)雜度O(nPVCE)=O(n1)+O(n2)+O(n3)=O(p)+O(n2)+O(n)。由于VPE算法處理的均是已簡化過的字符特征曲線，p和n均為有限整數(shù)，且p>>n，因此O(nPVCE)≈O(p)+O(p)+O(p)≈O(p)。由此可知，VPE算法的時間復(fù)雜度是線性的。

2 實 驗

2.1 準(zhǔn)確性測試

圖9 提取輪廓型字素的可視化部件

但是，對于從基本字素變異/延伸而來的變形字，它們本身具有較多相似性，且僅通過少量的局部變異相互區(qū)分，那么準(zhǔn)確提取它們所包含的可視化部件，并通過部件實現(xiàn)文字的區(qū)分，則要求VPE算法應(yīng)具有更高的準(zhǔn)確性。因此，為進(jìn)一步驗證VPE算法的正確率，選取10類輪廓型字素作為模板，而與其對應(yīng)的變形字作為樣本進(jìn)行測試，模板及測試樣本如表3所示。

表3 10類輪廓型字素及變形字列表

首先，按照東巴字的書寫順序[3]確定每類模板字符的可視化部件及其數(shù)量，然后使用VPE算法確定模板字符和測試字符間部件的對應(yīng)關(guān)系，并提取測試字符的可視化部件。由于部件提取時，可能會出現(xiàn)局部提取錯誤，為準(zhǔn)確衡量算法的有效性，定義VPE算法的正確率計算公式為：

針對變形字，VPE算法提取10類東巴變形字可視化部件的正確率如圖10所示，其平均正確率為93.96%。

圖10 使用VPE算法提取變形字的可視化部件

2.2 魯棒性測試

為模擬書寫東巴字時可能引入的誤差，采用數(shù)據(jù)增廣技術(shù)對文字分別進(jìn)行逆時針旋轉(zhuǎn)20度、順時針旋轉(zhuǎn)20度、沿y軸拉伸50%、沿y軸壓縮50%、向左傾斜50%、向右傾斜50%等6種變換，如圖11所示。通過數(shù)據(jù)增廣技術(shù)，東巴字的數(shù)量從原來的1 590個擴(kuò)充到了9 552個。

(a) 模板(b) 逆時針旋轉(zhuǎn)(c) 順時針旋轉(zhuǎn)(d) 壓縮

(e) 拉伸(f) 左傾斜(g) 右傾斜圖11 對原始文字進(jìn)行數(shù)據(jù)增廣變換

圖12 形變東巴字部件提取的正確率

另外，為了觀察兩種算法在同一字符發(fā)生不同類型變換時提取可視化部件的準(zhǔn)確性，從原有字符集中隨機(jī)選取70個字符，然后按照逆時針旋轉(zhuǎn)20度、順時針旋轉(zhuǎn)20度、沿y軸拉伸50%、沿y軸壓縮50%、向左傾斜50%、向右傾斜50%的字符形態(tài)變換順序提取字符的可視化部件，各種變換類型可視化部件提取的正確率如圖13所示。

圖13 按字符變換類型提取部件的正確率

2.3 與DCE算法的比較

與DCE算法相比，VPE算法更加直觀、簡單，且使用VPE算法提取的可視化部件包含更多的文字細(xì)節(jié)，能夠更好地表示文字的原始形態(tài)。在10類輪廓型字素中分別使用DCE算法和VPE算法完成字符部件的提取。統(tǒng)計每類文字此時所包含的有效特征點平均數(shù)量可知，當(dāng)字符中提取的可視化部件數(shù)量相同時，使用VPE算法得到的部件包含更多的有效特征點，即包含文字更多的細(xì)節(jié)特征，如圖14和圖15所示。并且，對于文字線條比較簡單的東巴字(例如，“山”“房屋”等兩類文字)，兩種算法所保留的有效特征點的數(shù)量基本相同，滿足使用最少特征點表示最多特征的需求；但對于線條比較復(fù)雜的東巴字(例如，牲畜1、2、3類)，VPE算法提取的可視化部件仍能保有較多的細(xì)節(jié)特征，而DCE算法得到的部件細(xì)節(jié)特征丟失較多，形變較為嚴(yán)重，特別是當(dāng)字符中包含較多細(xì)節(jié)特征，而提取的可視化部件數(shù)量較少時，這一問題尤為突出，如圖15所示。

圖14 對10類輪廓型字素提取數(shù)量相同的可視化部件時，DCE算法和VPE算法保留的有效特征點數(shù)量比較

圖15 同一字符采用DCE和PVE提取相同數(shù)量的可視化部件

3 結(jié) 語

VPE算法是一種適用于東巴輪廓型字素的可視化部件提取算法，它以部件表示法的理論為基礎(chǔ)，結(jié)合文字的可視化特征，以符合人類觀察習(xí)慣的方式提取包含文字局部特征且按照固定順序排列的可視化部件。實驗表明，該算法準(zhǔn)確性高、健壯性好，具有良好的尺度、平移和旋轉(zhuǎn)不變性。并且，與DCE算法比較，VPE算法得到的可視化部件較好地保留了東巴字的細(xì)節(jié)特征，從而為設(shè)計高效的東巴文字識別算法奠定基礎(chǔ)。