基于Freeman链码的几何图形识别算法

裴姗 章腾

摘 要：目前关于几何图形识别的算法存在的问题主要有准确率低，计算复杂度较高，运行时间较长等。利用简洁高效的Freeman链码算法结合几何图形特有的几何属性设计出新的算法，使其能够快速识别几何图形的顶点分布，并反映在一张边界震荡（boundary vibration，BV）曲线图上。该曲线图能够刻画几何图形的属性，如顶点的个数、距离分布，角度的大小，线段的曲直和图形的周长等。因此通过对曲线图的特征分析可以准确识别对应的几何图形。该算法不受图形的平移、旋转、放缩、噪声影响。为了测试算法的稳定性，仿真试验针对九种不同的随机生成且带噪声的几何图形，结果识别率较高，运行速度较快，达到了预期的效果。

关键词：几何图形；识别；Freeman链码；边界震荡曲线

中图分类号：TP317.4 文献标识码：A

Abstract： Currently there exist some problems about recognition algorithm for geometry figure，such as low rate of accuracy，high order of complexity，long time of running and so forth.This article designs a new algorithm by using the laconic efficient Freeman chain code algorithm with geometry properties of geometry figures，so that it can recognize the distribution of vertexes of geometry figures quickly，and it is displayed in a figure of boundary vibration（BV） curve.By analyzing，we see this figure of curve can describe the properties of geometry figures，such as the number and distance distribution of vertexes，the size of angles，the curvity of line segments，the perimeter of figures and so on.Hence we can recognize the relevant geometry figure accurately by analyzing the characteristic of the figure of curve.This algorithm isn't influenced by translation，rotation，extension and noise of figures.In order to test the stability of the algorithm，the simulation is in connection with nine different kinds of geometry figures which are generated arbitrarily and carry noise，the result shows the rate of accuracy is high and the speed of running is fast，we acquire the prospective effect.

Key words： geometry figure；recognition；Freeman chain code；boundary vibration curve

目前图像识别技术应用十分广泛，如在实验室监控中的应用[1]，在编组站驼峰作业过程控制中的应用等[2]。也有学者专门研究了图像识别的技术现状与发展趋势[3]。而对基本的几何图形的识别在实际的图像识别中十分关键，通过几何图形的识别可以快速掌握实际图像的轮廓，属性等特征。目前已有许多学者在几何图形的识别算法研究中卓有成效，文献[4]中依据多边形顶点和其它边缘像素点的特征值变化规律设计了一种简洁高效的识别算法；文献[5]中采用了霍夫变换理论来研究图形的识别。另外，还有一些学者的研究基于深度学习、神经网络、遗传算法、特征分布等技术与方法[6-9]。

考虑到算法的简洁高效性，借助Freeman链码技术[10]提出一种新的几何图形识别算法。在文献[11]中虽也采用了类似的方法，并考虑了链码直方图和链码空间分布熵。但本文试图充分利用几何性质来设计出一种新的算法，该算法不受图形的平移、旋转、伸缩、噪声影响。仿真结果准确率较高，算法运行时间较短，实现了预期的效果。

2 Freeman链码技术

Freeman链码技术是一种用来刻画数字图像的边界的方法。该方法首先需要定义一个方向坐标，常用的两个方向坐标是如图1的四方向和八方向坐标。然后根据坐标来对图像的边界按照Moore边界追踪算法 进行数字编码，使得图像的边界被一一地转换成一个数字序列。

如上图所示，采用四方向坐标只能刻画出的具有四个方向的边界，因此本文采用八方向坐標。

3 算法描述

算法将考虑九种不同形状的几何图形，分别是圆、椭圆、正方形、长方形、菱形、三角形、五边形、六边形，以及不规则图形。把整个图形的识别过程分为四个步骤。

3.1 去噪、二值化

在实际的图像识别中，经常会出现噪声的干扰，如模糊的监控画面等。为了增加算法的适用范围，考虑随机生成的带有椒盐噪声和高斯噪声的几何形状，采用均值滤波来处理高斯噪声、中值滤波来处理椒盐噪声。由于二值图像比灰度图像更容易处理，所以通过设定阈值来进行二值化。但是多次运行程序发现，二值化后的图像有时会出现孔洞，于是进行孔洞填充，取得了不错的效果，如下图所示。

3.2 顶点搜索

基于Freeman链码技术的边界搜索启发，设计了顶点搜索算法，其思想是：构造一个大小合适的正方形，将正方形中心沿图形边界移动，用y来记录正方形落入图形的面积，即正方形与图形重合的部分，随着正方形中心沿着边界移动，y的值也在不断的变化。分析发现，当正方形中心在几何图形的边上时，y的值大约为正方形面积的一半；当正方形中心靠近到图形的顶点时，y的值会迅速变小。我们根据y的值来判断图形顶点的个数。搜索示意图如下：

通过简单的平面几何的知识，在理论上证明了：当正方形的中心移动到矩形的顶点时，正方形与矩形重合的面积正好是正方形的1/4，不受矩形旋转的影响。这个事实将帮助在后续区分矩形和菱形。

正方形中心沿图形边界移动的过程中，模仿Freeman链码的边界点的搜索来操作。首先模仿Freeman链码中的八方向：1为右上，2为右，3为右下，4为下，5为左下，6为左，7为左上，8为上。搜索过程类似Freeman链码：

（1）起始点为左上角边界点，起始方向为起始点的下边。

（2）当前点取为起始点，当前方向取为起始方向，记录一次y的值。

（3）在当前点的八连通邻域内从当前方向顺时针搜索到下一个边界点。

（4）当前点改为搜索到的点，当前方向改为搜索方向的反方向的下一个方向，并记录y的值。

（5）若当前点和当前方向为起始点和起始方

向，则终止搜索，否则重复3和4。

相应的，在具体的代码中，取图像左上方的点作为初始点，设该点坐标为（I，J），同时也为正方形的中心，起始方向设为direct=4。如果（I-1，J+1）=1，即检测到在（I，J）的右上方有一个边界点，则将当前点（I，J）取为（I-1，J+1），当前方向direct=4取为direct=1；否则（I，J）顺时针移到下一个检索点（I，J+1），如果（I，J+1）=1，则当前点（I，J）取为（I，J+1），当前方向direct=4取为direct=2；以此类推直到检索完当前点（I，J）所有的相邻点。

3.3 确定顶点个数

通过上述操作，在每一个边界点上都得到一个y值，这就将图形的边界转化成一个数字序列，将序列反映在坐标轴上，横坐标表示图形的周长area，纵坐标表示正方形与几何图形重合的面积y。称该图像为边界震荡曲线（BV曲线），用该曲线就能分析出图形顶点的个数。首先对曲线做预处理，以便后续的判定。

（1）由于比较毛糙，因此对曲线进行多值化，多值化的目的除了使曲线平滑外，还为了后续判定图形角度的大小。

（2）通过算法的设计知道，图像的波谷代表顶点出现的位置。由于几何图形的边界都是闭合的，所以BV曲线的头部与尾部应当是相接的，故将靠近头部和尾部的波谷算成同一个波谷。

3.4 图形的判定

对曲线进行多值化后，仅波谷所在的位置会出现极小值点。如果极值点个数为2，判定为椭圆。如果极值点个数等于3，则几何图形为三角形。如果极值点个数等于4，但是最大波谷只有2个，则几何图形为菱形，因为菱形有2个大波谷，2个小波谷；否则，若波谷之间距离大致相同，则几何图形为正方形；若波谷之间距离明显不相同，则几何图形为长方形。如果极值点个数等于5，则几何图形为五边形。如果极值点个数等于6，则几何图形为六边形。如果极值点个数大于6，则几何图形为其它图形。否则，如果图形的偏心率小于0.1，则几何图形为圆；否则为椭圆。

4 仿真结果

根据上述设计的算法得到相应的MATLAB程序，运行得到如下结果。

设计的顶点搜索算法可以较为准确的判定出几何图形的形状。为了更直观的看出图形与BV曲线的联系，把两者在图6中同时呈现出来。

规整的几何图形相对应的BV曲线的特征是十分明显的。尤其是前面六种图形，如圆的BV曲线是正弦形的，正方形的BV曲线是呈现四个大小和间距一致的波谷。通过简单的几何证明发现结果与理论是相符的。

通过程序的多次运行发现，该算法对前六种图形的识别率接近100%，而对边数较多且像素较小的图形识别率相对较低。在BV曲线中也可以看出后三种图形的周长明显小于前六种。为了克服这个问题，在识别前将像素较小的图形放大一倍，使得识别率有了显著的提高。

5 结束语

利用Freeman链码的思想得到了一种识别基本几何图形的算法，该算法最大的特点是充分利用了图形的几何性质，并且依然具备Freeman链码算法的简洁高效性，而且识别率较高。同时利用该算法提出了能够刻画边界属性的BV曲线概念，该曲线很好地反映出图形边界的特征，如顶点数目与分布，角的大小，线段的曲直等。不同图形的BV曲线具有显著的差异。因此接下来的研究方向是BV曲线的代数刻画与分类，用以更精准地提取曲线的特征以及对几何图形的判定。

参考文献

[1] 刘胤，冯军焕，尹帮旭.图像识别技术在实验室监控中的应用[J].实验室研究与探索，2013，32（10）：210—213.

[2] 邢群雁.图像识别在编组站驼峰作业过程控制中的应用[D].北京：铁道科学研究院，2005.

[3] 张家怡.图像识别的技术现状与发展趋势[J].电脑知识与技术，2010，06（21）：6045—6046.

[4] 姚雷博，郭超，张伟民.基于边缘点特征值的快速几何图形识别算法[J].计算机应用研究，2011，28（11）：4386- 4388.

[5] 杨治明，周齐国.基于霍夫变换理论的图形识别[J].重庆工业高等专科学校学报，2002，17（4）：16—17.

[6] 丰晓霞.基于深度学习的图像识别算法研究[D].太原：太原理工大学，2015.

[7] 王麗华.基于神经网络的图像识别系统的研究[D].青岛：中国石油大学（华东），2008.

[8] 范宁.基于遗传算法的图像识别方法研究[D].长春：吉林大学，2015.

[9] 王宇新.基于特征分布的图像识别方法研究与应用[D].大连：大连理工大学，2012.

[10] GONZALEZ R C，WOODS R E.Digital image processing，Third Edition[M].Pearson Education，2008：796—801.

[11] 胡晓宏.基于链码特征的几何图形快速识别算法[J].吉林大学学报：理学版，2015，53（3）：489—493.