东巴象形文字特征曲线提取算法研究

2019-08-08杨玉婷康厚良

图学学报 2019年3期

杨玉婷，康厚良

东巴象形文字特征曲线提取算法研究

杨玉婷1，康厚良2

(1. 云南开放大学文化旅游学院，云南昆明 650000；2.苏州市职业大学体育部，江苏苏州 215000)

东巴文是一种原始的图画象形文字，要提高东巴文字的识别率，准确提取字符的特征曲线是关键。现阶段对东巴文字的检索和识别研究大多仍停留在使用已有的、通用的及成熟的识别技术，对东巴文字本身的分析和讨论较少。因此，结合东巴象形文字的形态特征和结构要素，给出了基于链码的连通域优先级标记算法(CDPM)，该算法通过扩展Freeman链码在边缘检测及曲线局部分割方面的功能，实现了使用一种算法完成轮廓型及结构型两种不同类型东巴字素的特征曲线提取，通过大量实验及与其他经典边缘检测算法的比较表明，CDPM算法具有良好的通用性、可扩展性及健壮性，并且准确率达到了98.2%，从而为东巴文字的检索和识别奠定坚实的基础。

CDPM算法；东巴象形文字；边缘检测；字符分割

1 东巴文字及特征

东巴文是一种十分原始的图画象形文字[1]，作为人类早期图画文字向象形文字、标音文字过渡的文字形式，其既具有图画文字以图表意，又具有现代文字使用简单线条表意的特点[2]。2003年，使用东巴文撰写的东巴古籍被联合国教科文组织列入世界记忆遗产名录[3]。

东巴文在检索和识别方面的研究起步较晚，相关文献较少且连贯性不强。其中，GUO等[4-7]给出了多种用于东巴象形文字识别的方法，LI等[8]提出了东巴文字识别的预处理系统。杨萌等[9]提出了基于神经网络的东巴文字识别算法，王海燕等[10-11]使用支持向量机的方法实现了对东巴文字的识别。另外，WANG等[12]提出了构建纳西东巴手稿语料和知识数据库的设想，而YANG等[13]则基于链码(chain code)在.Net平台上实现了用于单个东巴字符的输入与识别系统。

分析相关文献可知，现阶段对东巴文字的检索和识别研究大多仍停留在使用已有的、通用的及成熟的识别技术，对东巴字本身的分析和讨论较少。分析东巴文字的结构，准确提取能够反映文字本质特征的曲线，有利于提高东巴文字检索和识别的准确率，同时也有助于分析东巴文字的结构和形态、比较东巴文与其他象形文字的演变过程等方面的研究。为了独立分析不同文字的特征，将东巴文字的基本字素再细分为轮廓型字素和结构型2类字素。轮廓型字素通过临摹物体的外在形状来表达实际含义，并且文字的线条细化后，轮廓特征仍非常明显且闭合性好；而结构型字素一般使用简单的字符笔划通过描绘事物的结构或骨架来表达含义，文字的线条细化后能够得到显著的文字结构或骨架特征，其中人形字最具代表性，见表1。

表1 东巴字素的分类

显然，轮廓型字素的特征曲线应为文字的外在轮廓，而结构型字素的特征曲线应为文字局部细化线条的有序组合。为了满足2类东巴字素特征曲线提取的需求，结合东巴象形文字的形态特征和结构要素，给出了基于链码的连通域优先级标记算法(chain code based connected domain priority marking, CDPM)，该算法通过扩展Freeman链码[14]在边缘检测及曲线局部分割方面的功能，实现了使用一种算法完成2种不同类型东巴字素的特征曲线提取，为东巴文字的检索和识别奠定基础。

2 基于链码的连通域优先级标记算法

CDPM算法的基本思想是：首先，确定字符特征曲线的提取方向为逆时针方向；然后，将字符的起点作为参考点，根据初始参考向量方向计算与参考点相邻的8个邻域点的权值，选择权值最大的点作为特征点；接着，以新的特征点作为参考点，计算新的参考向量方向及与参考点相邻的8个邻域点的权值，重复上述操作，直到回到字符的起点或者完成字符所有终端点的遍历为止。其中，对于轮廓型字素，当算法回到字符起点，说明字符的特征曲线提取完成；而对于结构型字素，当算法遍历完字符的所有终端点，说明已完成字符局部曲线的分割和排序。

2.1 确定字符特征曲线的起点及初始参考向量

统一起点使不同字符的特征曲线也能具有相同的对应关系。假设给定的东巴字为,P(x,y)是所包含的像素点，若设置始终位于坐标的第一象限，则选取字符中距离坐标原点最近的终端点或像素点作为特征曲线的起点，则起点的选取步骤为：

(2) 细化文字线条，获得包含个像素点的细化字符。由于东巴文字是使用“竹笔”书写的，线条宽度基本一致，线条的细化不会对文字本身产生太大的影响；

(4) 若1，则将该终端点作为特征曲线的起点；若1，则选取距离坐标原点最近的终端点作为起点；若1，说明具有闭合的外在轮廓，则选取中距离坐标原点最近的像素点P作为起点。因此，特征曲线的起点1为

2.2 计算邻近点的优先级权值

高中学生在生物学科中的核心素养体现高中学生在生物教学中核心素养的培养，就是为了让学生对生物学科的全面了解，也帮助学生情感态度的培养与形成.知识素养是培养学生核心素养的基础，而核心素养则是学生各个方面的培养，情感态度的培养与价值观的培养是建立在知识教育能力的培养之上.

图1 CDPM算法的基本原理(以终端点P1为起点，为初始参考向量，按照逆时针方向提取字符轮廓)

表2 方向向量对点Pi的8个邻接点优先级的影响

2.3 CDPM算法在轮廓型字素中的应用

图2 包含单像素线条的轮廓型字素的特征曲线提取

结论1. 当轮廓型字素中包含由单像素点组成的线条时，使用CDPM算法同样能够得到连续、按逆时针顺序排列的特征曲线。

2.4 CDPM算法在结构型字素中的应用

结构型字素的特征曲线是局部细化线条的有序组合，为了验证CDPM算法能实现字符局部细化线条的分割并按照逆时针顺序排列，使用图3中的例子进行说明。

由于存入交点队列的候选像素点也是按照权值从大到小的顺序存储的，因此，若字符的骨架具有相似结构，则得到的分割结果及分割顺序也应具有相似性，如图3(c)所示，由此可得结论2。

(a) 确定算法的起点和方向

(b) 使用CDPM算法进行分割

以(人)、(抖，装模作样)、(立)和(坐)为例，使用CDPM算法分割并按先后顺序排列字符的局部骨架曲线，如图4所示。显然，第1行2个字符的第j~m条局部曲线与第2行2个字符的第k~n条局部曲线段不但形态相似，而且曲线段的排列顺序也一一对应，说明结论2是正确的。

图4 结构型字素的骨架分割及排序实例

2.5 复杂度分析

CDPM算法根据参考点和参考向量的方向来标记参考点的8邻域点的优先级权值，选择权值最大的邻接点作为新的参考点，并计算新的参考向量方向，继续计算参考点的8邻域优先级权值，反复执行上述过程直到遇到字符的终端点或回到起点为止。由于计算参考点的8邻域点权值及查找最大权值点的计算在最坏情况下将执行8次，若共有n个待测特征点，则算法的时间复杂度为O(8×n)≈O(n)。因此，CDPM算法的时间复杂度是线性的。

3 实验分析

为方便测试，从1 591个东巴文字中为结构型字素和轮廓型字素分别选取10类字符，每类包括数量不等的东巴字(表3)。

表3 轮廓型和结构型字素的10种类型类别结构型(基本型)结构型(扩展型)类别轮廓型(基本型)轮廓型(扩展型) 人鱼虫蹲鸟单手持物花双手持物手右侧偏移山头戴冠房屋心水植物祭祀行走牲畜坐山坡

其中，轮廓型字素包括鱼虫、鸟、花、手、山、房屋、水、东巴祭祀、牲畜和山坡等，结构型字素包括人、蹲、单手持物、双手持物、右侧偏移、头戴冠、心、植物、行走和坐等。并且，每种类型的东巴字都分为基本型和扩展型。基本型中的东巴字基本保持了字素的原有特征，变异较少；而扩展型一般是对基本型的扩展，在形态上具有一定的变异。

3.1 基础性测试

基础性测试是将2种类型中的“基本型”作为测试对象，验证当待测字符仅包含轮廓型或结构型单素字的基本特征时，使用CDPM算法提取轮廓特征曲线或分割骨架曲线段的正确性。在使用CDPM算法提取字符特征曲线前，首先需要对东巴字符的图片进行二值化、笔画线条细化和字符中离散缀加元素的去除等预处理操作。

图5显示了使用CDPM算法提取轮廓型字素(基本型)的轮廓特征曲线并按照逆时针顺序排列的效果。其中，绿色的线条为文字的细化线条，而黑色线条为文字的轮廓特征曲线。通过测试，CDPM提取“基本型”轮廓特征曲线的准确率为100%。

图6显示了使用CDPM算法实现结构型字素(基本型)的骨架分割，且局部骨架曲线按照先后顺序排列的效果。各局部曲线段排序时对应的颜色顺序为：蓝色、绿色、红色、青绿色、桃红色、黑色。当局部曲线段超过6条时，重复上述颜色。对10种结构型字素中的46个“基本型”字符的测试中，错误分割1个(红框标记)，正确率为97.83%。发生错误的原因是，字符的2个组成部分在构字中均为主成分，导致成分提取错误。

解法1：设u=，v=，则u2+v2=1且u≥0，v≥0，该曲线方程为四分之一圆，于是问题转化为：y为何值时，直线u+v=y与该四分之一圆有交点。由图1容易得到，y的取值范围为，即为所求函数值域。

图5 使用CDPM提取轮廓型(基本型)字素的特征曲线

图6 使用CDPM提取结构型字素(基本型)的特征曲线

3.2 扩展性测试

扩展性测试是将2种类型中的“扩展型”作为测试对象。与“基本型”相比，“扩展型”中的字符存在少量变异，而不同类型字符的变异又各不相同。其中，轮廓型字素的变异内容包括：缀加离散或粘连元素(包括缀加点、线或字块)、轮廓闭合不完全等。而结构型的变异内容包括：缀加离散或粘连元素、少量旋转(≤60°)、平移及大幅度旋转(>60°且<120°)等。

当然，园方防止人流拥堵引发安全隐患的初衷是好的，只是方法过于简单。其实，游乐园门票不少都是网上预订或团购的，完全可以提前告知游客验票时持儿童票者须出示身份证件。此外，不少游乐园的广告宣传力度也很大，在推介游乐项目的同时，顺带讲一下“验票须知”也非难事。儿童票与成人票相差几百元，家长们算得清这笔账，多半不会嫌麻烦。

图7显示了使用CDPM算法提取轮廓型字素(扩展型)的轮廓特征曲线并按照逆时针顺序排列的效果。其中，有2个字符(红框标记)由于轮廓闭合性不好，使用CDPM算法得到的结果不正确。因此，对于轮廓型单素字，当字符的轮廓闭合性不好时，使用CDPM算法可能无法得到正确的特征曲线，对(扩展型)轮廓型字素测试的正确率为95%。

图7 使用CDPM提取轮廓型(扩展型)字素的特征曲线

图8显示了使用CDPM算法实现结构型字素(扩展型)的骨架分割，并按照先后顺序排列局部骨架曲线。其中，有6个字符(红框标记)得到的结果与其他同类型的字符不同，准确率为87.17%。产生错误的原因是，CDPM算法一般选取距离坐标原点最近的终端点作为起点，当左下角的字符线条存在较多变异(例如，发生大弧度的旋转，或者附加了较多具有粘连性的缀加线条或字块)时，将对分割结果和局部骨架曲线的排列顺序产生影响。

图8 使用CDPM提取结构型字素(扩展型)的特征曲线

3.3 有效性实验

为进一步验证CDPM算法的有效性，连续选取10组数据，每组数据从1 591个东巴字符中随机选取100个不重复的东巴字符作为测试对象。并且，分别采用基于Sobel算子[15]和Canny算子[16]的边缘检测算法与CDPM算法进行比较，结果如图9所示。

在法学诠释学中，应用体现的最为明显。一个法律文本是在历史中制定出来的，而且作为法律文本其必然具有普遍的约束力，然而在法律实践中，每一个具体的案件都是特殊的。将一条法律应用于某一个既定的法律场合，如执行一个法律判决，就包含着对该法律条文的理解和解释。“不论怎样，这意味着各种法律规范的每一次运用(即得到公正的结果)都同时是对某一条既定法律之涵义的具体化和进一步阐明。”[5]因此，将普遍化的法律文本应用于某一具体的法律情境，就是对该法律文本的进一步的理解和解释，体现了理解、解释和应用的统一。

图9 CDPM算法的通用性测试

通过测试，CDPM算法的平均准确率为98.2%，而Sobel算子和Canny算子分别为58.2%和59.2%。后两者准确率较低的主要原因是，测试数据是从东巴字符库中随机选取的，其中所包含的结构型字素和轮廓型字素的数量是随机的，虽然Sobel算子和Canny算子能准确提取轮廓型字素的特征曲线，但是对结构型字素的特征曲线提取结果却非常不理想，错误率较高，导致平均准确率过低。说明，CDPM算法能够更好的适应不同类型东巴字素的特征曲线提取要求。

4 小结

CDPM算法实现简单，通过扩展Freeman链码在边缘检测及曲线局部分割方面的功能，满足了轮廓型和结构型两类东巴字素特征曲线提取的需求，具有良好的通用性、可扩展性及健壮性，并且当字素中存在少量变异(字素中存在缀加、离散或粘连元素，少量旋转(≤60°)及平移)时也能得出正确结果。但是，当轮廓型字素中的字符轮廓闭合不完全，或者结构型字素变异较大(大幅度旋转(>60°且<120°)或粘连元素较多)时，所提取的字符特征曲线仍可能发生错误。因此，在后续的工作中还需对CDPM算法不断改进以提高特征曲线提取的准确率。

参考文献

[1] 和力民. 试论东巴文化的传承[J]. 云南社会科学, 2004(1): 83-87.

[2] 和金光. 纳西族东巴文化研究发展趋势[J]. 云南民族大学学报:哲学社会科学版, 2007, 24(1): 81-84.

[3] 戈阿干. 东巴文化揽胜[J]. 民族艺术研究, 1999, 12(2): 71-80.

[4] GUO H, ZHAO J Y, DA M J, et al. NaXi pictographs edge detection using lifting wavelet transform [J]. Journal of Convergence Information Technology, 2010, 5(5): 203-210.

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

[6] GUO H, JYIN 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.

[7] GUO H, ZHAO J Y. Segmentation method for NaXi pictograph character recognition [J]. Journal of Convergence Information Technology, 2010, 5(6): 87-98.

[8] LI X, GUO H, SUO G J, et al. The design and realization of NAXI pictograph character recognition preprocessing system [C]//International Workshop on Computer Science for Environmental Engineering and EcoInformatics. Heidelberg: Springer, 2011: 54-59.

[9] 杨萌, 徐小力, 吴国新, 等. 东巴象形文字识别方法[J]. 北京信息科技大学学报:自然科学版, 2014, 29(3): 72-76.

[10] 王海燕, 王红军, 徐小力. 基于支持向量机的纳西东巴象形文字符识别[J]. 云南大学学报: 自然科学版, 2016, 38(5): 730-736.

[11] DA M J, ZHAO J Y, SUO G J, et al. Online handwritten Naxi pictograph digits recognition system using coarse grid [C]//International Workshop on Computer Science for Environmental Engineering and EcoInformatics. Heidelberg: Springer, 2011: 390-396.

[12] WANG H Y, WANG H J, CHEN X. Construction of corpus and knowledge database for Naxi dongba manuscripts based on internationally sharing platform [C]//Proceedings of the 6th International Asia Conference on Industrial Engineering and Management Innovation. Paris: Atlantis Press, 2015: 325-331.

[13] YANG L P, GUO H, ZHAO J Y, et al. The research on software of individual characters recognition about the Naxi pictographs based on.Net and chain code [J]. Procedia Engineering, 2012, 29: 4068-4072.

[14] FREEMAN H. Boundary Encoding and Processing [C]// Proceedings of Picture Processing and Psy-chopictorics. New York: Academic Press, 1970: 241-266

[15] KANOPOULOS N, VASANTHAVADA N, BAKER R L. Design of an image edge detection filter using the Sobel operator [J]. IEEE Journal of Solid-State Circuits, 1988, 23(2): 358-367.

[16] DING L J, GOSHTASBY A. On the Canny edge detector [J]. Pattern Recognition, 2001, 34(3): 721-725.

Research on the Extracting Algorithm of Dongba Hieroglyphic Feature Curves

YANG Yu-ting1, KANG Hou-liang2

(1. Culture and Tourism College, Yunnan Open University, Kunming Yunnan 650000, China;2. Spotrs Department, Suzhou Vocational University, Suzhou Jiangsu 215000, China)

Abstract: Dongba hieroglyphic is a kind of very primitive picture hieroglyphs. In order to increase the recognition rate of Dongba words, extracting the feature curves of glyphs is the key. At present, the retrieval and recognition of Dongba hieroglyphs still use the existing, universal and mature technology, and there is less analysis and discussion on the Dongba hieroglyphs themselves. Therefore, we analyze the shape and structure of the Dongba hieroglyphs in depth, and give a connected-domain priority marking algorithm based on chain codes. It extends the characteristic of Freeman chain code in edge detection and local segmentation of curves, and satisfies the requirements of contour and structure type of feature curve extraction. We use a large number of experiments and comparison with other classical edge detection algorithms to show that the CDPM algorithm has good versatility, scalability and robustness, and the accuracy reaches 98.2%. It lays a foundation for the retrieval and identification of Dongba hieroglyphs.

Keywords: CDPM algorithm; dongba hieroglyphic; edge detection; words partitioning

中图分类号：TP 391

DOI：10.11996/JG.j.2095-302X.2019030591

文献标识码：A

文章编号：2095-302X(2019)03-0591-09

收稿日期：2018-07-24；

定稿日期：2018-09-12

基金项目：云南省教育科学研究基金项目(2018JS748，2019J1152)；国家社会科学基金项目(15BTY038)

第一作者：杨玉婷(1983-)，女，云南昆明人，副教授，硕士。主要研究方向为图形图像处理、计算机视觉等。E-mail：tudou-yeah@163.com

通信作者：康厚良(1979-)，男，四川泸州人，教授，硕士。主要研究方向为民族文化及民族体育的传承与保护。E-mail：kangfu1979110@163.com