東巴象形文字特征曲線簡化算法研究

楊玉婷，康厚良，廖國富

東巴象形文字特征曲線簡化算法研究

楊玉婷1，康厚良2，廖國富3

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

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

東巴文字特征提取；特征曲線簡化；離散曲線演化算法；二次簡化

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

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

表1 東巴字素的分類

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

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

1 東巴象形文字特征曲線簡化算法

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

1.1 離散曲線演化算法

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

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

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

1.2 基于區域最大面積差的臨界點選取法

特征曲線在每一階段的演化都會導致曲線形態的變化，并進一步引起曲線所圍面積的變化。因此，當兩次演化中曲線所圍面積的差值最大時，說明此時丟失的字符細節特征最多，從而得出基于區域最大面積差的臨界點選取法的核心思想，即：

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

圖2(a)為字符的原始特征曲線，圖2(b)為采用基于區域最大面積差的臨界點選取法去除特征曲線中88%的特征點后的簡化結果。可以看出，在去除曲線中的大量冗余點后，字符的特征曲線并未丟失過多的細節，說明該臨界點選取法對于輪廓型字素是可行的。

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

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

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

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

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

1.3 二次簡化

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

因此，對于包含個特征點的字符簡化曲線，設曲線的總長度為，若曲線中的特征點P滿足以下條件，則為異常點，即

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

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

圖4 特征曲線二次簡化前后對比

1.4 復雜度分析

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

(1) 順序計算曲線中每個頂點的權值及曲線所圍成的面積，由于僅遍歷曲線頂點序列1次，其時間復雜度(1)=()。

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

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

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

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

2 實驗與分析

2.1 通用性測試

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

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

表2 輪廓型和結構型字素的10種類型

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

2.2 魯棒性測試

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

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

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

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

圖7 東巴文字特征曲線簡化前后的比較

3 結束語

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

[1] 方國瑜. 納西象形文字譜[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]. 云南社會科學, 2004(1): 83-87.

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

[5] 和志武. 試論納西象形文字的特點: 兼論原始圖畫字、象形文字和表意文字的區別[J]. 云南社會科學, 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] 鄭飛洲. 關于建設東巴文字字素檢索數據庫的構想[J]. 中國文字研究, 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] 鄭飛洲. 關于納西族東巴文字信息處理的設想[J]. 學術探索, 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] 楊萌, 徐小力, 吳國新, 等. 東巴象形文字識別方法[J]. 北京信息科技大學學報:自然科學版, 2014, 29(3): 72-76.

[14] 王海燕, 王紅軍, 徐小力. 基于支持向量機的納西東巴象形文字符識別[J]. 云南大學學報:自然科學版, 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]. 自動化學報, 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

云南省科學研究基金項目(2018JS748，2019J1152)；國家社會科學基金項目(15BTY038)

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

康厚良(1979-)，男，四川瀘州人，教授，碩士。主要研究方向為民族體育與民族文化。E-mail：kangfu1979110@163.com