一种基于结构特征的光学刻划字符边缘提取和边缘拟合方法

技术领域

本发明涉及一种基于结构特征的光学刻划字符边缘提取和边缘拟合方法。

背景技术

字符边缘提取及其拟合可以构成字符的完整轮廓，是字符识别过程中的重要环节。对于光学刻划字符，常用的边缘提取方法和拟合方法都不能得到良好的结果。由于刻划字符图像的产生过程中，采用条形光源使得与光源平行的笔划会产生高灰度值的像素，而与光源垂直的笔划会产生低灰度值的像素，背景的像素值介于以上两种像素之间，如图1所示。因而，Canny算子无法提取刻划字符的真实边缘，这是因为Canny算子本质上是基于梯度的边缘提取方法。在一个笔划的中间由于光照方向的不同产生了低灰度值像素和高灰度值两种像素，在其交界处产生了大幅度的灰度变化，Canny算子的梯度非最大值抑制算法捕捉到这些变化，把相应位置的像素作为边缘，但它们并不是刻划字符的真实边缘点。

即使采用某种方法去除伪边缘点，也会产生断续间隔比较大的不连续边缘。若要采用常用的边缘拟和方法如阈值化顺序边缘连接的轮廓提取方法多阈值选取与边缘连接的边缘检测算法以及神经网络边缘拟合都不会取得良好的结果，这是因为这些方法都只是适合于断续点之间的距离较近的情形。

发明内容

本发明为了解决上述问题，提出了一种基于结构特征的光学刻划字符边缘提取和边缘拟合方法，本方法首先使用Canny算子提取边缘，基于灰度信息和结构信息提取像素特征，使用k最近邻方法消除Canny算子产生的伪边缘点，继而基于字符的结构特征实现断续边缘的拟合形成字符的轮廓，形成的刻划字符轮廓完整、准确。

为了实现上述目的，本发明采用如下技术方案：

一种基于结构特征的光学刻划字符边缘提取和边缘拟合方法，包括以下步骤：

(1)使用Canny算子提取边缘，将真伪边缘模板对应的像素灰度矩阵转换成特征向量，进行标记，利用K最近邻算法根据标记的特征向量去除样本的伪边缘；

(2)根据字符的笔画结构特征和断续边缘线段的端点之间的距离构建不同的连接模式，形成像素场景；

(3)依照各个像素场景中各边缘线段的位置关系、线段的灰度信息以及线段之间的距离，确定线段端点的连接方式，进行边缘拟合，形成字符轮廓。

所述步骤(1)中，具体步骤包括：

(1-1)将真伪边缘模板对应的像素灰度矩阵转换成特征向量，同时分配相应的分类标号；

(1-2)根据欧式距离在特征空间中选择k个距离最近的样本；

(1-3)统计K-最近邻样本中每个分类标号出现的次数；

(1-4)选择出现频率最大的类标号作为待分类边缘点的类标号。

优选的，所述步骤(1-1)中，将真伪边缘模板对应的像素灰度矩阵转换成长度为9的特征向量。

所述步骤(2)中，综合考虑字符的笔画结构特征和断续边缘线段的端点之间的距离概括出多种连接模式，将每种连接模式作为一个像素场景，不同的连接模式采取不同的边缘拟和方法。

所述步骤(2)中，根据待拟合的边缘线段位于笔画的位置，彼此之间的排列结构，像素灰度值的大小关系和位置关系的不同来确定不同的像素场景。

所述步骤(3)中，将各个像素场景的线段的端点作为元素，形成链表，进行边缘拟合，从链表的第一个边缘线段的第一个端点开始，通过链表确定每个端点与下一端点的距离和端点周围设定距离范围内的线段数目。

所述步骤(3)中，在链表中开始搜索是否存在与第一端点的距离小于设定值的端点，若存在，则将两个端点进行连接，端点坐标采用一次多项式拟和，删除链表中的所述两个端点的连接线段，同时链表长度减1。

所述步骤(3)中，在链表中搜索距离第一端点小于设定距离范围的线段，若存在上述线段，则记录线段的端点，统计线段数目，根据线段的数目、灰度级线段位置与像素场景相对应，确定其所属像素场景。

所述步骤(3)中，端点的连接采用坐标拟合的方法。

优选的，所述设定距离范围为字符笔画宽度的2-3倍。

本发明的有益效果为：

(1)本发明提取的边缘准确，拟合得到的刻划字符轮廓完整，为后续的字符特征提取带来了很大方便。

(2)本发明基于字符的结构特征去确定断续边缘线段方式，实际上是模拟人的视觉和认知原理；无论第一个线段是哪一个线段，也无论这些线段端点之间的距离多大，由于它们都是字符某个或相邻的两个笔画上，都能实现正确的连接。

附图说明

图1为本发明的刻划字符图像示意图；

图2为本发明的伪边缘模板集合示意图；

图3为本发明的真边缘模板集合示意图；

图4为本发明的场景模板集合示意图；

图5为本发明的连接模式3示意图；

图6为传统方法Canny算子提取的边缘图，有伪边缘点；

图7为本发明去除伪边缘的结果示意图；

图8为拟合过程及其结果图；

图9为本发明的流程图。

具体实施方式：

下面结合附图与实施例对本发明作进一步说明。

基于结构特征的光学刻划字符边缘提取和边缘拟合方法，包括以下步骤：

步骤一，基于k最近邻算法去除伪边缘。

特征空间的合理选择是正确分类的最关键要素，既要考虑特征描述的准确性，还要考虑样本的平衡问题。K最近邻算法的缺点是当样本不平衡时，有可能导致当输入一个新样本时，该样本的k个邻居中大容量类的样本占多数。

分析canny算子提取的边缘点周边像素的灰度分布发现，真边缘点和假边缘点的8邻域灰度分布具有明显的不同。伪边缘点总是处于一个笔画中高灰度像素和低灰度像素的交界，真边缘点要么处于高灰度像素和背景中灰度像素的交界，要么处于低灰度像素和背景中灰度像素的交界。为此使用像素的8邻域作为其特征，为叙述方便，称像素的8邻域为边缘模板，真边缘像素点的8邻域叫做真边缘模板，伪边缘像素点的8邻域叫做伪边缘模板，真、伪边缘模板构成了运用k最近邻算法的特征空间。

由于伪边缘点总是处于一个笔画中两种灰度级别的像素区域的交界，按照伪边缘点上下左右周围像素点的灰度取值情况将伪边缘模板分为以下8类，共32种结构。前16种模板中处于中心的伪边缘点为低灰度值，后16种模板中伪边缘点为高灰度值，如图2所示。

真边缘点要么处于高灰度像素区域和背景的交界，要么处于低灰度区域和背景的交界。因而按照边缘点上下左右周围像素点的灰度取值情况将真边缘模板分为以下六类，24种结构，如图3所示。

需要说明，模板中三种灰度的取值是通过直方图分析用高、中、低三种灰度像素的灰度均值来表示的。

算法步骤：

将真伪边缘模板对应的像素灰度矩阵转换成长度为9的特征向量，同时分配相应的分类标号；

根据欧式距离在特征空间中选择k个距离最近的样本；

统计K-最近邻样本中每个分类标号出现的次数；

选择出现频率最大的类标号作为待分类边缘点的类标号。

步骤二，基于结构特征的断续边缘拟合。

1.特征描述

综合考虑字符的笔画结构特征和断续边缘线段的端点之间的距离概括出16种连接模式，涉及16种实际的像素场景，不同的连接模式采取不同的边缘拟和方法。具体来说就是在不同的连接模式下，根据各边缘线段的位置关系、线段的灰度信息以及线段之间的距离等三个要素选择正确的边缘端点连接关系。

16种像素场景如图4所示，它们的笔画特征描述如下。

场景1，待拟和的三个边缘线段处于一个笔画的末端，两条平行边缘线段具有相同的灰度级别，另外一个边缘线段的像素灰度高于前者，一个边缘端点附近有两个其它边缘的端点，需要选择其中的一个进行边缘拟合。

场景2待拟和的四个边缘线段处于一个笔画的中部，且呈对称排列结构，像素灰度值高的一对线段相对位置处于右上方，像素灰度值低的一对线段相对位置处于左下方。一个边缘端点附近有三个其它边缘的端点，需要选择其中的一个进行边缘拟合。

场景3到场景5都和场景2相似，区别在于场景3中像素灰度值高的一对线段相对位置处于左上方，像素灰度值低的一对线段相对位置处于右下方；场景4中像素灰度值高的一对线段相对位置处于右下方，像素灰度值低的一对线段相对位置处于左上方；场景5中像素灰度值高的一对线段相对位置处于左下方，像素灰度值低的一对线段相对位置处于右上方；

场景6至场景8是后叙场景15经过边缘拟合后衍生出的几种情形。场景6和5相似，区别在于像素灰度值低的一对线段相对位置一个处于右下方，另一个处于右上方。场景8和3相似，像素灰度值高的一对线段相对位置一个处于左上方，一个处于右上方。场景7中像素灰度值高的一对线段相对位置是左右关系，像素灰度值高的一对线段相对位置是上下关系。

场景9至场景12是后续场景13和场景14经过边缘拟合后衍生出的几种情形。待拟和的四个边缘线段中，有三个线段是低灰度像素值，另一个是高灰度值。像素灰度值低的三条线段都是垂直或接近垂直的线段，呈平行或上下一致的规则排列关系。像素灰度值高的线段是水平的线段。一个边缘端点附近有三个其它边缘的端点，需要选择其中的一个进行边缘拟合。

场景13，待拟和的六个边缘线段处于横笔画与竖笔画交界处，且呈对称排列结构，像素灰度值高的一对线段相对位置处于右侧，像素灰度值低的两对线段相对位置分别处于左上方和左下方。一个边缘端点附近有5个其它边缘的端点，需要选择其中的一个进行边缘拟合。场景14相似于场景13，二者呈水平景象关系。

场景15，待拟和的六个边缘线段呈星形对称分布关系，按照斜率大小分为三组线段，斜率为零的一对线段都具有较高的像素灰度值，斜率为负的一对线段具有较低的像素灰度值，另一对线段则一条具有较高的像素灰度值一条具有较低的像素灰度值。

场景16，待拟和的八个边缘线段呈星形对称分布关系，按照斜率大小和坐标位置分为四对线段，分别处于左上、左下、右上、右下方。一个边缘端点附近有7个其它边缘的端点，需要选择其中的一个进行边缘拟合。

2.具体描述：

用Ci(i＝1,2....n)表示链表中的任一边缘线段，Ci(1)和Ci(2)表示其第1端点和第2端点。边缘拟合时，总是从链表中的第一个边缘线段的C1(1)开始，我们关心C1(1)与其它边缘线段Ci(i＝2....n)的端点Ci(1)和端点Ci(2)的距离D1i(1)和D1i(2)。边缘拟合还关心端点C1(1)周围一定距离范围Dn内的线段数目N，以便判断当前连接属于哪一种连接模式。使用投影法检测字符笔划的宽度w，观察和实验发现取Dn＝2.5W是合适的。

首先，在{Ci(1)，Ci(2)i＝2,3...}中搜索D1i(1)或D1i(2)小于0.3*w的端点Cj(k)(j＝2,3...k＝1,2)，如果Cj(k)存在，C1(1)与Cj(k)直接连接，端点坐标采用一次多项式拟和，删除链表中的Cj，链表长度减1。此为连接模式1。

其次，在{Ci i＝2,3...}中搜索min(D1i(1),D1i(2))小于2.5*w的线段Cj，如果Cj存在，记 录这些端点Cj(k)k＝1,2。根据线段数目Number，划分为以下几种方式：

(1)如果Number＝1,且不是字符轮廓的最后一个断续边缘线段，C1(1)与Cj(k)直接连接。此为连接模式1。

(2)如果Number＝2，，对应于场景1，使用灰度和斜率信息选择连接路径。此为连接模式2。

(3)如果Number＝3，对应于场景2到场景12，使用线段的灰度信息以及线段的位置关系进行区分，选择不同的端点连接方法。相应地称为连接模式3，6......13。

(4)如果Number＝4，5，去掉距离最远的线段，按照Number＝3处理。

(5)如果Number＝6对应于场景13，14，15，使用线段的灰度信息、斜率信息以及位置关系进行区分，选择不同的连接方法。称为连接模式14，15，16。

(6)如果Number>7，通常发生在断续边缘线段长度较短，在2.5W范围内断续边缘线段比较稠密的情形，如字符“B”的中间部分就属于这种情况。其中当Number＝8时，可以根据线段的斜率判断如果对应于场景16(两对平行线段)，就根据线段的位置关系进行连接，称为连接模式16；否则和其它Number>7的情况一样作如下相同的处理，减小搜索范围，取Dn＝1.5W，重新搜索端点C1(1)周围Dn范围内的线段数目N，使得N<＝6,然后按照上述方法确定连接模式。

3.边缘拟合方法

实际上是场景识别从而确定连接模式，下面以连接模式3为例说明。当Number＝3时,共有场景2到场景12等十种场景，C1(1)周围有3个线段，需要确定C1(1)和另外三条线段中的哪一条线段的哪一个端点去连接，在场景2到场景12等十一种场景产生连接模式3到连接模式13等十一种连接模式。

采用集合分解的方法进行场景识别，识别时需要使用各线段的灰度信息、距离信息和斜率信息。线段C1随着线段连接长度不断增加，从C1(1)开始取其10个点求其平均坐标XY1(x,y)和平均灰度Bgray1；其余三条线段的平均坐标和平均灰度分别用XY2(x,y)，XY3(x,y)，XY4(x,y)和Bgray1，Bgray2，Bgray3，Bgray4表示。

十一种场景构成集合B。首先，根据三条线段的灰度信息将集合B划分成子集B1和B2。B1包含场景2到场景8共七个场景，四条线段的平均灰度Bgray1，Bgray2，Bgray3，Bgray4中，一对线段的像素灰度值较高，而另一对线段的像素灰度值较低；B2包含场景9到场景12，四条线段中一条线段的像素灰度值较高，另外三条线段的像素灰度值较低。

其次，根据集合线段的距离信息将B1划分成子集B11和B12。使用平均坐标XY1(x,y)计算两个灰度相等(近)的线段的距离，高灰度值的一对线段之间的距离用Hgd表示,低灰度值的一对线段之间的距离为Lgd。B11包含场景3，4，5，6，四个场景，Hgd和Lgd都小于1.5W；B12包含场景6、7、8三个场景，Hgd和Lgd中只有一个小于1.5W。

集合B11、B12和B2都是不能再分的最小集合。集合B11的四种场景对应于连接模式3、4、5、6；集合B12的三种场景对应于连接模式7、8、9；集合B2的四种场景对应于连接模式10、11、12、13。

在集合B11中，根据线段的相对位置关系来区分四种场景。低灰度值的一对线段对的行、列平均值用LL和LH表示，高灰度值的一对线段对的行、列平均值用HL和HH表示，若LL>HL且LH<HH则为场景2，亦即连接模式3；若LL>HL且LH>HH则为场景3，亦即连接模式4；若LL<HL且LH<HH则为场景4，亦即连接模式5；若LL<HL且LH>HH则为场景5，亦即连接模式6。

在集合B12中，使用线段的斜率信息区分三种场景。高灰度线段对的斜率分别用HS1和HS2表示，低灰度线段对的斜率分别用LS1和LS2表示。若HS1＝HS2则为场景6亦即连接模式7，若LS1＝LS2则为场景8亦即连接模式9，否则为场景7亦即连接模式8。

在集合B2中，需要根据灰度信息和列位置信息从三条低灰度线段中排除左右平行排列的一对低灰度线段，计算剩余的一条低灰度线段各像素的行平均LL1值与列平均值LH1,同时计算高灰度线段各像素的行平均HL1值与列平均值HH1，利用位置信息LL1、LH1、HL1、HH1确定二者的位置关系从而区分出场景9到场景12，亦即连接模式10到13。

确定连接模式后，需要进一步确定各个线段的在其场景中的具体位置，方能确定具体的端点连接关系，从而实现边缘拟和。仍以连接模式3为例说明。

共有四个线段{C1 Ci Cj Ck}，ij k＝2,3,4...N，集合中的第一条线段总是C1。上述特征识别中的灰度排序结果用{Ca Cb Cc Cd}表示，Ca和Cb是一对像素灰度值较低的一对线段，Cc和Cd则是一对像素灰度值较高的一对线段。

比较Ca和Cb的列平均值，列平均值小的赋之标号④，列平均值大的赋之标号③；比较Cc和Cd的行平均值，行平均值小的赋之标号①，行平均值大的赋之标号②。如果线段C1的标号为①，就选择标号为④的线段作为连接线段，如果线段C1的标号为④，就选择标号为①的线段作为连接线段；如果线段C1的标号为②，就选择标号为③的线段作为连接线段，如果线段C1的标号为③，就选择标号为②的线段作为连接线段。线段C1的连接端点总是取 C1(1),被连接线段的连接端点在上述特征识别中已经确定。

端点连接采用坐标拟和的方法，如果端点之间的距离小于0.8W，采用1次多项式拟和，否则采用2次多项式拟和。

仿真结果：

以典型字符G为例进行说明，如图6所示，现有单纯使用Canny算子提取的边缘，有伪边缘点。如图7所示，采用步骤一去除伪边缘的结果，结合图8中步骤二拟合过程及其结果，可以看出，本发明能够很好地去除不连续的问题，且没有伪边缘，识别准确度高，拟合得到的刻划字符轮廓完整。

上述虽然结合附图对本发明的具体实施方式进行了描述，但并非对本发明保护范围的限制，所属领域技术人员应该明白，在本发明的技术方案的基础上，本领域技术人员不需要付出创造性劳动即可做出的各种修改或变形仍在本发明的保护范围以内。