楊玉婷，康厚良，廖國(guó)富

東巴象形文字特征曲線簡(jiǎn)化算法研究

楊玉婷1，康厚良2，廖國(guó)富3

(1. 云南開放大學(xué)文化旅游學(xué)院，云南 昆明 650000；2.蘇州市職業(yè)大學(xué)體育部，江蘇 蘇州 215000；3. 昆明理工大學(xué)津橋?qū)W院電氣與信息工程學(xué)院，云南 昆明 650000)

東巴文作為一種原始的圖畫象形文字，在檢索和識(shí)別方面的研究較多，且從不同角度應(yīng)用各類算法進(jìn)行了實(shí)現(xiàn)，但是在文字特征提取和簡(jiǎn)化方面的研究卻很少。由于字符特征提取的精練性和完全性將直接影響識(shí)別算法的精度和復(fù)雜度，因此結(jié)合計(jì)算機(jī)視覺中形狀簡(jiǎn)化的相關(guān)研究成果，給出了適用于東巴象形文字特征曲線簡(jiǎn)化的改進(jìn)算法。該算法以離散曲線演化算法為基礎(chǔ)，進(jìn)一步給出了區(qū)域最大面積差的臨界點(diǎn)選取法和二次簡(jiǎn)化算法，有效去除了東巴字符特征曲線中的冗余點(diǎn)和潛在異常點(diǎn)。通過通用性和魯棒性實(shí)驗(yàn)表明，該算法在保留原有字符特征的基礎(chǔ)上可以去除曲線中87%以上的冗余點(diǎn)，實(shí)現(xiàn)了特征曲線的最簡(jiǎn)化，從而為東巴文字的相似性度量奠定基礎(chǔ)。

東巴文字特征提?。惶卣髑€簡(jiǎn)化；離散曲線演化算法；二次簡(jiǎn)化

納西東巴文字是通行于納西族西部方言區(qū)的一種古老的圖畫象形文字[1]，其保留了人類早期文字演變的珍貴信息[2]，是當(dāng)今世界上唯一存活的象形文字[3]。2003年，使用東巴文撰寫的東巴古籍被聯(lián)合國(guó)教科文組織列入世界記憶遺產(chǎn)名錄[4]。

東巴文字具有較為濃厚的原始圖畫意味，從文字的結(jié)構(gòu)要素分析[5]，字素可細(xì)分為輪廓型和結(jié)構(gòu)型2類。輪廓型字素通過臨摹物體的外在形狀來表達(dá)實(shí)際含義，具有輪廓特征明顯且閉合性好的特點(diǎn)；而結(jié)構(gòu)型字素一般使用簡(jiǎn)單的字符筆劃通過描繪事物的結(jié)構(gòu)或骨架來表達(dá)含義，其中人形字最具代表性[6]，見表1。

表1 東巴字素的分類

當(dāng)前，東巴文字在檢索和識(shí)別方面的研究較多[7-11]，且應(yīng)用各類算法進(jìn)行了實(shí)現(xiàn)，但是在文字特征提取和簡(jiǎn)化方面的研究卻相對(duì)較少，即使在相關(guān)文獻(xiàn)中包括與文字特征提取有關(guān)的內(nèi)容，也僅僅是使用常見的灰度化、二值化、直方圖等通用方法[12-15]。顯然，字符特征提取的不精練、不完全，不僅影響識(shí)別算法的精度，同時(shí)也會(huì)增加識(shí)別算法的復(fù)雜度。

基于鏈碼的連通域優(yōu)先級(jí)標(biāo)記(connected domain priority marking, CDPM)算法[6]為東巴文字的特征提取提供了一種新的思路，針對(duì)東巴文字的結(jié)構(gòu)特征，準(zhǔn)確提取2類不同結(jié)構(gòu)東巴文字的特征曲線。但是，曲線中過多的頂點(diǎn)序列仍會(huì)對(duì)文字識(shí)別的效率和準(zhǔn)確性造成影響。因此，本文在CDPM算法的基礎(chǔ)上，結(jié)合東巴文字的書寫習(xí)慣及計(jì)算機(jī)視覺中形狀簡(jiǎn)化的相關(guān)研究成果[16]，給出了適用于東巴象形文字特征曲線的簡(jiǎn)化算法。該算法能有效去除字符特征曲線中的大量冗余點(diǎn)及潛在異常點(diǎn)，實(shí)現(xiàn)使用最少的特征點(diǎn)序列表示最多的字符特征。另外，該算法也可與其他特征曲線提取算法相結(jié)合用于曲線的簡(jiǎn)化和特征提取。

1 東巴象形文字特征曲線簡(jiǎn)化算法

東巴象形文字特征曲線簡(jiǎn)化算法是基于CDPM算法在東巴文字特征提取方面的進(jìn)一步優(yōu)化，其思想是：首先采用離散曲線演化算法(discrete curve evolution, DCE)和區(qū)域最大面積差的臨界點(diǎn)選取法去除特征曲線中的大量冗余點(diǎn)，統(tǒng)稱為一次簡(jiǎn)化；然后，使用二次簡(jiǎn)化算法進(jìn)一步去除特征曲線中的剩余冗余點(diǎn)及潛在異常點(diǎn)。

1.1 離散曲線演化算法

DCE在保持曲線特征的同時(shí)，可快速去除曲線中的大量冗余點(diǎn)[17]，即在演化的每一個(gè)階段，使用一條新的線段替換原有的一對(duì)相鄰的線段1和2，該線段是通過連接12的2個(gè)端點(diǎn)而得到的。演化過程中，線段的合并順序由度量決定，即

其中，(1,2)為線段1和2的頂點(diǎn)轉(zhuǎn)向角；為歸一化之后的線段長(zhǎng)度[18-19]。

由于東巴字符的特征曲線中除了存在大量冗余點(diǎn)之外，還有一些潛在異常點(diǎn)，若直接使用DCE算法的結(jié)束條件可能會(huì)產(chǎn)生曲線中的關(guān)鍵點(diǎn)被刪除，而異常點(diǎn)仍存在的問題，容易導(dǎo)致曲線的過度簡(jiǎn)化或簡(jiǎn)化結(jié)果異常。因此，通過分析東巴字符特征曲線在實(shí)際演化過程中所反映的外在變化，采用基于區(qū)域最大面積差的臨界點(diǎn)作為演化的結(jié)束條件，達(dá)到使用最少特征點(diǎn)表示最多字符特征的目的。

1.2 基于區(qū)域最大面積差的臨界點(diǎn)選取法

特征曲線在每一階段的演化都會(huì)導(dǎo)致曲線形態(tài)的變化，并進(jìn)一步引起曲線所圍面積的變化。因此，當(dāng)兩次演化中曲線所圍面積的差值最大時(shí)，說明此時(shí)丟失的字符細(xì)節(jié)特征最多，從而得出基于區(qū)域最大面積差的臨界點(diǎn)選取法的核心思想，即：

顯然，當(dāng)曲線中的特征點(diǎn)較多時(shí)，每次刪除部分特征點(diǎn)不會(huì)對(duì)曲線產(chǎn)生太大影響。但是，當(dāng)特征點(diǎn)較少時(shí)，每次曲線演化都可能造成曲線中字符特征的大量丟失。因此，在曲線演化過程中，當(dāng)簡(jiǎn)化曲線的特征點(diǎn)數(shù)量小于原有總量的50% (即，完成第50次演化)時(shí)，則在后續(xù)的每次演化中加入曲線所圍面積的計(jì)算，以減少算法的總體計(jì)算量；另外，當(dāng)完成第99次曲線演化時(shí)，曲線中僅剩原有總量1%的特征點(diǎn)，若繼續(xù)進(jìn)行演化，則特征點(diǎn)將被全部刪除。因此，演化次數(shù)最大值為99。以字符為例，圖1顯示了在曲線演化的每個(gè)階段，字符特征曲線所圍面積的值。其中，當(dāng)完成第89次演化(即，去除了總量89%的特征點(diǎn))時(shí)，曲線所包含的字符特征丟失最多。因此，第88次演化(去除總量88%的特征點(diǎn))得到的字符特征曲線為最簡(jiǎn)。

圖2(a)為字符的原始特征曲線，圖2(b)為采用基于區(qū)域最大面積差的臨界點(diǎn)選取法去除特征曲線中88%的特征點(diǎn)后的簡(jiǎn)化結(jié)果?？梢钥闯?，在去除曲線中的大量冗余點(diǎn)后，字符的特征曲線并未丟失過多的細(xì)節(jié)，說明該臨界點(diǎn)選取法對(duì)于輪廓型字素是可行的。

在結(jié)構(gòu)型字素中，由于字符的特征曲線已被劃分為多條局部曲線，不同曲線間差異較大，如圖3(a)所示。因此，以字符的各局部曲線為單位，首先使用基于區(qū)域最大面積差的臨界點(diǎn)選取法計(jì)算各條局部曲線的臨界點(diǎn)完成曲線的簡(jiǎn)化，然后再進(jìn)行曲線的拼接。

(a) 字符的原始 特征曲線(b) 基于臨界值的DCE演化 (去除總量88%的特征點(diǎn) 后的簡(jiǎn)化曲線)

(a) 原輪廓 (初始特征 曲線段)(b) 區(qū)域最大面積差 的臨界點(diǎn)(進(jìn)行DEC 演化后的效果)(c) 改進(jìn)的 臨界點(diǎn) (簡(jiǎn)化效果)

由于結(jié)構(gòu)型字素各局部曲線包含的特征點(diǎn)總體較少，加之曲線中潛在異常點(diǎn)的存在，當(dāng)去除的特征點(diǎn)超過總量的90%時(shí)，部分局部曲線中的關(guān)鍵點(diǎn)出現(xiàn)了誤刪，使曲線特征發(fā)生了丟失，如圖3(b)所示，且該問題在結(jié)構(gòu)型字素的演化過程中經(jīng)常發(fā)生。因此，為了避免過度簡(jiǎn)化，定義了曲線演化臨界值選取規(guī)則，即：在東巴字素的曲線演化中，若特征曲線中去除的特征點(diǎn)大于或等于總量的90%時(shí)，選擇次大面積差所對(duì)應(yīng)的值作為新的臨界值。若新的臨界值仍然大于等于90%，則重復(fù)上述過程直到所選擇的臨界值小于90%為止。

通過限制，圖3(b)得到了優(yōu)化，效果如圖3(c)所示。此時(shí)，字符的頭部和腳部的過度簡(jiǎn)化得到了改善，但其他部分并未受到影響。

1.3 二次簡(jiǎn)化

分析DCE的演化過程可知，簡(jiǎn)化時(shí)無法刪除的無效特征點(diǎn)大多為凹點(diǎn)，這是因?yàn)樘卣鼽c(diǎn)的權(quán)值與轉(zhuǎn)向角的大小成正比(即，K)，使得曲線中的凹點(diǎn)具有較大的權(quán)值，即便是一個(gè)無效點(diǎn)也無法被及時(shí)刪除，如圖3(b)所示。結(jié)合東巴字的書寫習(xí)慣可知：東巴字的書寫一般使用線描法，即“靠線條狀物、靠線條造型，以線條描繪的方法作為其基本特征”。由于東巴字的書寫過程具有筆畫線條流暢、連貫，曲線幅度變化均勻等特點(diǎn)。因此，可結(jié)合其書寫習(xí)慣進(jìn)一步去除字符特征曲線中的異常點(diǎn)。

因此，對(duì)于包含個(gè)特征點(diǎn)的字符簡(jiǎn)化曲線，設(shè)曲線的總長(zhǎng)度為，若曲線中的特征點(diǎn)P滿足以下條件，則為異常點(diǎn)，即

其中，由P和P+1所組成的線段的歸一化長(zhǎng)度()有如下約束

對(duì)圖2(b)和圖3(c)中的字符使用二次簡(jiǎn)化算法后的效果如圖4所示。此時(shí)，輪廓型字素和結(jié)構(gòu)型字素中的冗余點(diǎn)均得到了進(jìn)一步去除，簡(jiǎn)化效果明顯。但需要注意的是，二次簡(jiǎn)化算法僅能用于包含少量冗余點(diǎn)的曲線優(yōu)化，并不能直接用于原始字符特征曲線的簡(jiǎn)化。

圖4 特征曲線二次簡(jiǎn)化前后對(duì)比

1.4 復(fù)雜度分析

東巴象形文字特征曲線簡(jiǎn)化算法包括4個(gè)步驟(設(shè)字符的特征曲線包含個(gè)頂點(diǎn))：

(1) 順序計(jì)算曲線中每個(gè)頂點(diǎn)的權(quán)值及曲線所圍成的面積，由于僅遍歷曲線頂點(diǎn)序列1次，其時(shí)間復(fù)雜度(1)=()。

(3) 遍歷曲線面積差值序列確定DCE算法的結(jié)束條件，得到曲線的一次簡(jiǎn)化結(jié)果。由于僅需遍歷1次，時(shí)間復(fù)雜度(3)=()。

(4) 依次遍歷簡(jiǎn)化曲線中的特征點(diǎn)，判斷并刪除簡(jiǎn)化曲線中的潛在冗余點(diǎn)和異常點(diǎn)，得到二次簡(jiǎn)化結(jié)果。假設(shè)一次簡(jiǎn)化后，特征曲線中剩余的頂點(diǎn)數(shù)為(<<)，但在二次簡(jiǎn)化中，刪除噪音點(diǎn)的同時(shí)仍需重新計(jì)算相鄰點(diǎn)的權(quán)值，因此其時(shí)間復(fù)雜度與步驟(2)相似，則(4)≈()<()。

上述4個(gè)計(jì)算步驟相互獨(dú)立且在計(jì)算中沒有交叉，因此，東巴象形文字特征曲線簡(jiǎn)化算法的整體時(shí)間復(fù)雜度為：(1)+(2)+(3)+(4)≈4×()≈()。由此可知，整個(gè)算法的時(shí)間復(fù)雜度是線性的。

另外，由于曲線的二次簡(jiǎn)化是在一次簡(jiǎn)化的基礎(chǔ)上完成的，而一次簡(jiǎn)化的處理結(jié)果又取決于臨界點(diǎn)的選取，錯(cuò)誤的臨界點(diǎn)將會(huì)影響最終的簡(jiǎn)化效果，如圖3(b)所示。因此，臨界點(diǎn)選取是東巴文字特征曲線簡(jiǎn)化算法的核心。

2 實(shí)驗(yàn)與分析

2.1 通用性測(cè)試

為測(cè)試算法的通用性，從1 340個(gè)東巴文字中為結(jié)構(gòu)型字素和輪廓型字素分別選取10類字符，每類字符包括5~12個(gè)數(shù)量不等的東巴字。其中，結(jié)構(gòu)型字素包括人、蹲、單手持物、雙手持物、右側(cè)偏移、頭戴冠、心、植物、行走和坐等，輪廓型字素包括魚蟲、鳥、花、手、山、房屋、水、東巴祭祀、牲畜和山坡等，見表2。

首先，從2類東巴字的20個(gè)子類中，每類隨機(jī)提取1個(gè)東巴字；然后，使用CDPM算法提取東巴字中字素的特征曲線；接著，結(jié)合基于區(qū)域最大面積差的臨界點(diǎn)選取法和DCE演化算法去除特征曲線中的大量冗余特征點(diǎn)；最后，采用二次簡(jiǎn)化算法進(jìn)一步去除曲線中的冗余點(diǎn)和潛在異常點(diǎn)，具體效果如圖5和圖6所示。

表2 輪廓型和結(jié)構(gòu)型字素的10種類型

與原始曲線相比，經(jīng)過兩次簡(jiǎn)化處理，特征曲線中的大量冗余特征點(diǎn)和部分異常點(diǎn)被去除。同時(shí)，在簡(jiǎn)化曲線中，幅度變化較大的部分保留的特征點(diǎn)較多，而較為平滑的部分保留的特征點(diǎn)較少，保證僅用較少的特征點(diǎn)就能完整表示字符的原有特征。另外，通過測(cè)試說明，東巴象形文字特征曲線簡(jiǎn)化算法能夠用于不同類型、不同結(jié)構(gòu)和具有不同特征的東巴字符的特征曲線簡(jiǎn)化。

2.2 魯棒性測(cè)試

為進(jìn)一步測(cè)試特征曲線簡(jiǎn)化算法的魯棒性，從1 591個(gè)東巴字符圖片中隨機(jī)選取100個(gè)東巴字符的特征曲線作為測(cè)試對(duì)象，比較字符特征曲線簡(jiǎn)化前后的差異。首先，使用DCE算法結(jié)合區(qū)域最大面積差的臨界點(diǎn)選取法實(shí)現(xiàn)字符特征曲線中大量冗余點(diǎn)的去除。在100個(gè)隨機(jī)選取的字符中，最多去除了原曲線總量87.83%的特征點(diǎn)，最少去除了81.03%的特征點(diǎn)；平均去除量為85.33%。

其次，使用二次簡(jiǎn)化算法實(shí)現(xiàn)字符特征曲線中部分冗余點(diǎn)和異常點(diǎn)的去除。100個(gè)隨機(jī)選取的字符中，最多去除了原曲線總量94.55%的特征點(diǎn)，最少去除了82.16%的特征點(diǎn)；平均去除量為87.75%。與第一階段的簡(jiǎn)化相比，使用二次簡(jiǎn)化算法，在DCE簡(jiǎn)化的基礎(chǔ)上平均又減少了原有總量2.42%的特征點(diǎn)，進(jìn)一步剔除特征曲線中的冗余點(diǎn)和潛在異常點(diǎn)，使字符特性更加顯著，如圖7所示。

(a) 東巴字 原圖(b) 特征 曲線(c) 基于 DCE的 簡(jiǎn)化曲線(d) 二次簡(jiǎn) 化曲線

(a) 東巴字 原圖(b) 特征 曲線(c) 基于 DCE的 簡(jiǎn)化曲線(d) 二次簡(jiǎn) 化曲線

圖7 東巴文字特征曲線簡(jiǎn)化前后的比較

3 結(jié)束語

東巴象形文字特征曲線簡(jiǎn)化算法充分利用了現(xiàn)有算法的優(yōu)勢(shì)，同時(shí)又結(jié)合了東巴文字的書寫習(xí)慣和文字特征，更好的適用于東巴字的特征曲線簡(jiǎn)化。但是，由于不同文字自身結(jié)構(gòu)的差異性，使得其簡(jiǎn)化精煉度和完全性各不相同，這將直接影響文字準(zhǔn)確識(shí)別的精度和復(fù)雜度。因此，為了將字符特征曲線的簡(jiǎn)化效果限定在一定范圍內(nèi)，可通過計(jì)算曲線在簡(jiǎn)化過程中所圍面積的累計(jì)差值(即，特征損失)在原始曲線面積中所占的比例來判斷曲線簡(jiǎn)化的精煉度，但這一判斷方法的合理性還需要在后續(xù)工作中進(jìn)一步進(jìn)行驗(yàn)證。

[1] 方國(guó)瑜. 納西象形文字譜[M]. 和志武, 參訂. 2版. 昆明: 云南人民出版社, 2005: 56-87.

[2] YANG Y T, KANG H L. The digital measures for protection and heritage of dongba culture [M]// Advances in Intelligent Systems and Computing. Singapore: Springer Singapore, 2018: 1203-1208.

[3] 和力民. 試論東巴文化的傳承[J]. 云南社會(huì)科學(xué), 2004(1): 83-87.

[4] 王元鹿. 漢古文字與納西東巴文字比較研究[M]. 上海: 華東師范大學(xué)出版社, 1988: 20-35.

[5] 和志武. 試論納西象形文字的特點(diǎn): 兼論原始圖畫字、象形文字和表意文字的區(qū)別[J]. 云南社會(huì)科學(xué), 1981(3): 67-78.

[6] YANG Y T, KANG H L. A novel algorithm of contour tracking and partition for dongba hieroglyph [M]// Image and Graphics Technologies and Applications. Singapore: Springer Singapore, 2018: 157-167.

[7] 鄭飛洲. 關(guān)于建設(shè)東巴文字字素檢索數(shù)據(jù)庫的構(gòu)想[J]. 中國(guó)文字研究, 2002(3): 76-81.

[8] GUO H, ZHAO J Y. Research on feature extraction for character recognition of NaXi pictograph [J]. Journal of Computers, 2011, 6(5): 947-954.

[9] GUO H, YIN J H, ZHAO J Y. Feature dimension reduction of NaXi pictograph recognition based on LDA [J]. International Journal of Computer Science, 2012, 9(1): 90-96.

[10] 鄭飛洲. 關(guān)于納西族東巴文字信息處理的設(shè)想[J]. 學(xué)術(shù)探索, 2003(2): 83-86.

[11] LI X, GUO H, SUOG J, et al. The design and realization of NAXI pictograph character recognition preprocessing system [M]//Computer Science for Environmental Engineering and EcoInformatics. Heidelberg: Springer, 2011: 54-59.

[12] SONG W J, WANG K Q, XU R P, et al. The analysis and application of associative element combining configuration of Dongba Characters [C]//2010 IEEE 11th International Conference on Computer-Aided Industrial Design & Conceptual Design (CAIDCD). New York: IEEE Press, 2010, 1(11): 753-756.

[13] 楊萌, 徐小力, 吳國(guó)新, 等. 東巴象形文字識(shí)別方法[J]. 北京信息科技大學(xué)學(xué)報(bào):自然科學(xué)版, 2014, 29(3): 72-76.

[14] 王海燕, 王紅軍, 徐小力. 基于支持向量機(jī)的納西東巴象形文字符識(shí)別[J]. 云南大學(xué)學(xué)報(bào):自然科學(xué)版, 2016, 38(5): 730-736.

[15] DA M J, ZHAO J Y, SUO G J, et al. Online handwritten Naxi pictograph digits recognition system using coarse grid [M]//ComputerSciencefor Environmental Engineering and EcoInformatics. Heidelberg: Springer, 2011: 390-396.

[16] 周瑜, 劉俊濤, 白翔. 形狀匹配方法研究與展望[J]. 自動(dòng)化學(xué)報(bào), 2012, 38(6): 889-910.

[17] LATECKI L J, LAK?MPER R. Polygon evolution by vertex deletion [M]//Scale-Space Theories in Computer Vision. Heidelberg: Springer, 1999: 398-409.

[18] LATECKI L J. Shape similarity measure based on correspondence of visual parts [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(10): 1185-1190.

[19] LATECKI L J, LAK?MPER R. Convexity rule for shape decomposition based on discrete contour evolution [J]. Computer Vision and Image Understanding, 1999, 73(3): 441-454.

Research on Simplification Algorithm of Dongba Hieroglyphic Feature Curve

YANG Yu-ting1, KANG Hou-liang2, LIAO Guo-fu3

(1. Culture and Tourism College, Yunnan Open University, Kunming Yunnan 650000, China; 2. Sports Department, Suzhou Vocational University, Suzhou Jiangsu 215000, China; 3. Faculty of Electrical and Information Engineering, Oxbridge College, Kunming University of Science and Technology, Kunming Yunnan 650000, China)

Dongba hieroglyph is a primitive ideographic script. Many researchers have done a lot of research on the retrieval and recognition of Dongba hieroglyph, and applied various algorithms from different angles, but few of them are on the feature extraction and simplification. In view of the fact that the succinctness and completeness of charactefeature extraction will directly affect the accuracy and complexity of the recognition algorithm, we combine the related research of shape simplification in computer vision and present an improved algorithm which is helpful to the simplification of Dongba hieroglyph feature curve. Based on the discrete curve evolution algorithm, our algorithm further gives the critical point selection method based on the maximum area difference and the second simplification algorithm, which effectively remove the redundant points and potential anomalies in the character feature curve. The universality and robustness experiments show that our algorithm can remove more than 87% redundant points in the curve while retaining the original character features, and achieving the most simplified feature curve. It lays the foundation for retrieval and recognition of Dongba hieroglyph.

extracting feature of Dongba hieroglyphs; feature curve simplification; discrete curve evolution algorithm; secondary simplification algorithm

TP 391

10.11996/JG.j.2095-302X.2019040697

A

2095-302X(2019)04-0697-07

2018-10-16；

定稿日期：2018-12-08

云南省科學(xué)研究基金項(xiàng)目(2018JS748，2019J1152)；國(guó)家社會(huì)科學(xué)基金項(xiàng)目(15BTY038)

楊玉婷(1983-)，女，云南昆明人，副教授，碩士。主要研究方向?yàn)閳D形圖像處理、計(jì)算機(jī)視覺等。E-mail：tudou-yeah@163.com

康厚良(1979-)，男，四川瀘州人，教授，碩士。主要研究方向?yàn)槊褡弩w育與民族文化。E-mail：kangfu1979110@163.com