東巴輪廓型字素可視化部件提取算法研究

康厚良 楊玉婷

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

0 引 言

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

表1 東巴基本字素的分類

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

東巴文在特征提取、檢索和識別方面的研究起步較晚，相關(guān)文獻較少且連貫性不強，研究內(nèi)容主要圍繞東巴字的預處理[6-7]、東巴字的特征提取[8-10]、文字識別[11-14]等三方面展開，涉及東巴字的基礎(chǔ)分類[6]、文字圖像去噪、線條細化、字符特征曲線提取[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]。與很多其他方法相比，該方法直觀、容易理解，也更符合人類提取事物特征的習慣，但存在復雜度高、多尺度難以定義、參數(shù)解不穩(wěn)定等問題[19]。

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

1.1 東巴字的預處理

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

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

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

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

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

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

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

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

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

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

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

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

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

Step1以g0為坐標原點建立直角坐標系。

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

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

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

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

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

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

為方便描述，設模板字符為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中凸弧的對應關(guān)系如表2所示。

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

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

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

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)整部件間的對應關(guān)系，則說明原始的對應關(guān)系完全錯誤，如圖8(b)-圖8(d)所示；或者部件間本身就存在較大差異，沒有對應關(guān)系。

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

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

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

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

1.5 復雜度分析

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

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

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

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

上述3個步驟相互獨立且在計算中沒有交叉，由于步驟3是可選步驟，因此，VPE算法在最壞情況下的整體時間復雜度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算法的時間復雜度是線性的。

2 實 驗

2.1 準確性測試

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

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

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

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

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

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

2.2 魯棒性測試

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

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

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

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

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

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

2.3 與DCE算法的比較

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

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

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

3 結(jié) 語

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