东巴轮廓型字素可视化部件提取算法研究

2023-03-15康厚良杨玉婷

计算机应用与软件 2023年2期

康厚良杨玉婷

1(苏州市职业大学体育部江苏苏州 215000) 2(苏州市职业大学计算机工程学院江苏苏州 215000)

0 引言

东巴字是一种十分原始的图画象形文字[1-2]，作为人类早期图画文字向象形文字、标音文字过渡的文字形式，它具有图画文字以图表意及现代文字使用简单线条表意的特点[3-4]。为独立分析不同文字的特征，一般将东巴文字的基本字素细分为轮廓型字素和结构型字素2类。轮廓型字素一般通过描摹物体的外在形体[5]来表达实际含义；而结构型字素则是使用简单的字符笔画通过描绘事物的结构或骨架来表达含义[6]，如表1所示。

表1 东巴基本字素的分类

东巴字以象形符号为基础，属于能代表和书写语言的象形文字符号体系，但仍保留浓厚的原始图画意味，未能完全去除掉非文字的图画式表意手法，往往和图像混在一起使用[5]。这使我们无法直接借鉴计算机视觉领域的形状处理方法或手写汉字的识别算法。

东巴文在特征提取、检索和识别方面的研究起步较晚，相关文献较少且连贯性不强，研究内容主要围绕东巴字的预处理[6-7]、东巴字的特征提取[8-10]、文字识别[11-14]等三方面展开，涉及东巴字的基础分类[6]、文字图像去噪、线条细化、字符特征曲线提取[8-9]、简化[10]及识别[11-14]等内容。其中大多数的研究都是直接套用已有的形状特征提取算法或通用的识别算法，忽略了东巴字本身的形态和结构，无法为研究文字本身提供支持。

图1 结构型字素的可视化部件

因此，借鉴形状匹配领域中的部件表示(part-based representations)理论[15-16]，结合东巴象形文字特征曲线提取及简化算法，给出了适用于轮廓型字素的可视化部件提取算法(Visual Part Extraction，VPE)，该算法不仅能解决东巴基本字素的一致性表示，提高文字识别算法的健壮性和精确度，同时也为研究东巴字的笔画、偏旁部首等内容提供技术支持。

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

在形状匹配领域，部件表示法(part-based representations)能够有效提高形状识别算法的健壮性[15]，并且在形状分类理论中也发挥着重要作用[16]。Latecki等[17-18]在部件表示法的基础上提出了可视化部件的概念，并通过使用离散轮廓演化(Discrete Contour Evolution，DCE)算法从对象特征曲线中提取直观的、容易被观察者直接获取的、包含对象可视化局部特征的曲线作为可视化部件[17]。与很多其他方法相比，该方法直观、容易理解，也更符合人类提取事物特征的习惯，但存在复杂度高、多尺度难以定义、参数解不稳定等问题[19]。

东巴文字与形状极其相似，但它在书写时具有一定的规范，直接使用DCE算法提取文字的可视化部件可能会增加算法复杂度。因此，基于可视化部件的基本理论，结合东巴字特征曲线提取[9]及简化[10]算法给出了适用于东巴轮廓型字素的VPE。它的基本思路是：首先将待测字符的特征曲线分割为若干包含字符特征的凸弧；然后，以模板字符的可视化部件为参考实现凸弧的合并及字符间可视化部件的对应；最后，完成异常对应关系的调整。VPE算法简单、直观、易于实现，并且保留了人类视觉提取对象特征的习惯。

1.1 东巴字的预处理

(a) 模板字符的二值化 (b) 线条细化 (c) 去除离散冗余元素

(d) 提取特征曲线 (e) 特征曲线的简化 (f) 提取可视化部件图2 模板字符“麻雀”的预处理过程及可视化部件提取

1.2 轮廓型字素特征曲线的过分割

1) 以凹点为起点：凸弧(convex arcs)是特征曲线中被凹点分割开的凸的曲线段[19]。以凹点为起点保证了凸弧的完整性和独立性。因此，结合简单多边形顶点凸凹性识别算法[21]快速确定字符简化曲线中的凹点，如图3(b)中的黑色圆点所示。

(a) 东巴字 (b) 标记特征曲线上的凹点

2) 按照规定的方向，顺序提取：保证所提取的凸弧在原始特征曲线中方向一致、首尾相连(以前、后两条凸弧共有的凹端点作为连接点)且排列顺序相同。如图3(c)所示，按照顺时针方向顺序提取简化曲线中的凸弧，并使用不同类型的曲线加以区分。

3) 凸弧的部分合并：提取的凸弧中，可能存在仅由一条直线段组成的凸弧(例如，图3(c)中的凸弧②)，这样的凸弧是没有意义的，因此通过计算线段两个凹端点的权值大小，将直线段与端点权值较小的一端合并(详细的论证过程见文献[22])，效果如图3(d)所示。通过合并，过分割过程中产生的一些无效短弧线得到了合并，留下的均为由3个及以上特征点组成的、包含部分或完整局部字符特征的凸弧[22]。但是，在一些文字中由于粘连点的影响，部分凸弧的合并操作仍无法解决所有的过分割问题，如图3(d)中的黑色空心圈所示，因此下一阶段将进一步完成凸弧的合并。

1.3 过分割凸弧的合并及字符间可视化部件的对应

按照东巴字的书写顺序[3]可确定模板字符的可视化部件(如图2(f)所示)，然后将其作为待测字符凸弧合并的参考并完成字符间部件对应关系的确定及待测字符中多余凸弧的合并，从而解决字符简化曲线中少量噪声点对可视化部件提取的干扰。因此，定义过分割凸弧的合并规则为：

以模板字符中可视化部件的位置为参考，合并待测字符中与其有对应关系的邻近凸弧，直到待测字符中的凸弧数量与模板字符的部件数量相同且一一对应为止。具体步骤如下：

1) 确定部件/凸弧的位置。在前一阶段中，通过部分合并操作去除了曲线中的无效凸弧，保证了剩余凸弧的长度(由3个及以上特征点组成)和有效性，此时使用凸弧/部件的局部中心点表示它们的全局位置，可有效避免当凸弧出现少量形变或旋转变化时对凸弧与模板字符部件间对应关系确定的影响。因此，以字符特征曲线的中心点为原点，建立直角坐标系，使用部件/凸弧局部中心点在坐标系中的向量夹角来表示它的位置。即：

设字符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) 鸽子的凸弧及中心

2) 找出待测字符中凸弧与模板字符中可视化部件的对应关系。由图4可知，可视化部件和凸弧在特征曲线中都是按照顺时针方向排列的，要确定部件和凸弧之间的对应关系，实际上就是要找出局部中心点向量夹角最小的一对凸弧和部件，而剩余凸弧/部件的对应关系只需沿顺时针方向继续判断即可。

由于凸弧具有一定的长度和有效性，使用局部中心点表示提高了它本身的鲁棒性，此时将模板字符和待测字符的特征曲线放在同一坐标系中，可快速找出局部中心点向量夹角最小的一对，并且当待测字符发生少量形变或旋转时，也不会对部件与凸弧间对应关系的确定产生过大的影响。因此，我们首先归一化字符中凸弧/部件的中心点向量，使不同字符具有可比较性；然后，移动待测字符坐标系至模板字符坐标系，使凸弧与部件处于相同坐标系中，便于找出对应关系。

为方便描述，设模板字符为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中凸弧的对应关系如表2所示。

表2 字符间可视化部件/凸弧的对应关系

由于bCur2与aCur1、aCur2存在潜在对应关系，又有bCur1↔aCur1且bCur3↔aCur2。那么，若bCur1与bCur2合并后的曲线与aCur1的对应性更好，则有bCur2↔aCur1；反之，若bCur3与bCur2合并后的曲线与aCur2的对应性更好，则有bCur2↔aCur2。因此，可结合已确定的关系进一步判断部件/凸弧间的潜在对应关系。

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

(a)(b)(c)(d)图6 以模板字符部件为依据提取待测字符的可视化部件

1.4 特殊情况的处理

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

(d) 模板字符(m=3) (e) 合并的待测字符图7 字符的变异对可视化部件提取的影响

由于东巴字的可视化部件反映的是事物的外部形态，如果两个字符包含的部件数量相同且都按照顺时针方向排序，那么若仍需要调整部件间的对应关系，则说明原始的对应关系完全错误，如图8(b)-图8(d)所示；或者部件间本身就存在较大差异，没有对应关系。

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

(e) (f) (g)图8 模板字符和待测字符间部件的对应关系校正

因此，若要校正字符间部件的对应关系，首先需找出两个字符中相似度[23]最高的一对作为字符间对应的起始部件，然后按照顺时针方向遍历，即可找出其他部件的对应关系，部件对应关系的校正结果如图8(e)-图8(g)所示。其中：(a)为模板字符和待测字符的整体效果；(b)-(d)为部件的原始对应关系；(e)-(g)为校正后的部件对应关系。

值得注意的是，在东巴字的造字过程中，更多是通过突出显著特征、形态变异、缀加元素[4]等方式来区分不同文字，仅有少量是直接通过旋转文字本身来产生新文字的。因此，为了提高算法的整体效率，在具体实施过程中，一般先对模板字符和待测字符进行一次相似性比较[23]，若字符间已有较多可视化部件具有相似性，则1.4节中所讨论的步骤可以忽略。

1.5 复杂度分析

VPE算法的实施过程主要包括三个步骤，若假设字符G的特征曲线为Cur，其中：包含p个特征点，m条凸弧，n个可视化部件，且m≥n。本质上n即为合并后最终待测字符与模板字符包含的部件数量，那么：

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) 找出待测字符中凸弧与模板字符中可视化部件的对应关系，最坏情况下，待测字符中的每条凸弧都需要与模板字符中的部件进行比较，所以时间复杂度O(n22)=O(m×n)；(3) 合并待测字符B中的凸弧，对于模板字符中的n个部件，均需要计算与之对应的待测字符中的相邻两条凸弧的夹角和，并按照夹角和的大小进行排序，最坏情况下，两两相邻的凸弧都需要计算，然后才能判断可合并的凸弧数量，因此时间复杂度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) 字符间部件对应关系的校正，包括两步：(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均为有限整数，且p>>n，因此O(nPVCE)≈O(p)+O(p)+O(p)≈O(p)。由此可知，VPE算法的时间复杂度是线性的。

2 实验

2.1 准确性测试

图9 提取轮廓型字素的可视化部件

但是，对于从基本字素变异/延伸而来的变形字，它们本身具有较多相似性，且仅通过少量的局部变异相互区分，那么准确提取它们所包含的可视化部件，并通过部件实现文字的区分，则要求VPE算法应具有更高的准确性。因此，为进一步验证VPE算法的正确率，选取10类轮廓型字素作为模板，而与其对应的变形字作为样本进行测试，模板及测试样本如表3所示。

表3 10类轮廓型字素及变形字列表

首先，按照东巴字的书写顺序[3]确定每类模板字符的可视化部件及其数量，然后使用VPE算法确定模板字符和测试字符间部件的对应关系，并提取测试字符的可视化部件。由于部件提取时，可能会出现局部提取错误，为准确衡量算法的有效性，定义VPE算法的正确率计算公式为：

针对变形字，VPE算法提取10类东巴变形字可视化部件的正确率如图10所示，其平均正确率为93.96%。

图10 使用VPE算法提取变形字的可视化部件

2.2 鲁棒性测试

为模拟书写东巴字时可能引入的误差，采用数据增广技术对文字分别进行逆时针旋转20度、顺时针旋转20度、沿y轴拉伸50%、沿y轴压缩50%、向左倾斜50%、向右倾斜50%等6种变换，如图11所示。通过数据增广技术，东巴字的数量从原来的1 590个扩充到了9 552个。

(a) 模板(b) 逆时针旋转(c) 顺时针旋转(d) 压缩

(e) 拉伸(f) 左倾斜(g) 右倾斜图11 对原始文字进行数据增广变换

图12 形变东巴字部件提取的正确率

另外，为了观察两种算法在同一字符发生不同类型变换时提取可视化部件的准确性，从原有字符集中随机选取70个字符，然后按照逆时针旋转20度、顺时针旋转20度、沿y轴拉伸50%、沿y轴压缩50%、向左倾斜50%、向右倾斜50%的字符形态变换顺序提取字符的可视化部件，各种变换类型可视化部件提取的正确率如图13所示。

图13 按字符变换类型提取部件的正确率

2.3 与DCE算法的比较

与DCE算法相比，VPE算法更加直观、简单，且使用VPE算法提取的可视化部件包含更多的文字细节，能够更好地表示文字的原始形态。在10类轮廓型字素中分别使用DCE算法和VPE算法完成字符部件的提取。统计每类文字此时所包含的有效特征点平均数量可知，当字符中提取的可视化部件数量相同时，使用VPE算法得到的部件包含更多的有效特征点，即包含文字更多的细节特征，如图14和图15所示。并且，对于文字线条比较简单的东巴字(例如，“山”“房屋”等两类文字)，两种算法所保留的有效特征点的数量基本相同，满足使用最少特征点表示最多特征的需求；但对于线条比较复杂的东巴字(例如，牲畜1、2、3类)，VPE算法提取的可视化部件仍能保有较多的细节特征，而DCE算法得到的部件细节特征丢失较多，形变较为严重，特别是当字符中包含较多细节特征，而提取的可视化部件数量较少时，这一问题尤为突出，如图15所示。

图14 对10类轮廓型字素提取数量相同的可视化部件时，DCE算法和VPE算法保留的有效特征点数量比较

图15 同一字符采用DCE和PVE提取相同数量的可视化部件

3 结语

VPE算法是一种适用于东巴轮廓型字素的可视化部件提取算法，它以部件表示法的理论为基础，结合文字的可视化特征，以符合人类观察习惯的方式提取包含文字局部特征且按照固定顺序排列的可视化部件。实验表明，该算法准确性高、健壮性好，具有良好的尺度、平移和旋转不变性。并且，与DCE算法比较，VPE算法得到的可视化部件较好地保留了东巴字的细节特征，从而为设计高效的东巴文字识别算法奠定基础。