基于链码特征的几何图形快速识别算法*

胡 晓 宏

(北华大学 计算机科学技术学院,吉林 吉林 132021)



基于链码特征的几何图形快速识别算法*

胡 晓 宏

(北华大学 计算机科学技术学院,吉林 吉林 132021)

针对目前几何图形识别算法计算复杂度高、处理时间长、识别种类少等问题,提出一种基于链码特征的几何图形快速识别算法.该算法结合链码直方图和链码空间分布熵,兼顾链码的统计特性和空间分布特性,具有尺度、旋转、平移不变性及链码起点无关性.仿真实验表明,该算法能够识别较多种类的图形,且识别准确率较高、较快.

几何图形;链码特征;信息熵;识别

根据物体的几何形状对其属性进行判别的方法在图像处理、目标跟踪、路径规划、场景识别等领域应用广泛[1-2].物体形状识别的过程主要是先提取几何形状的某种特征,再通过Hough变换、模糊聚类、形状匹配、人工神经网络等方法进行识别[3-4].目前,较常用的图像特征包括颜色特征、纹理特征及形状特征3类.其中形状特征能直观地描述物体的几何特性,与被识别目标的匹配性较高,因此属于更高层次的特征.形状特征的描述必须符合目标的平移、旋转和尺度不变性,一般包括区域法和边缘法两种,本文主要研究边缘特征.

在图像边缘特征中,链码特征是其主要特征之一,目前已有许多研究结果.例如:文献[5]研究了方向链码及其曲线描述在纤维图像识别中的应用,利用整数描述边缘相邻像素间的转动角度得到物体边界的方向链码,并根据链码值和像素间距离进行序列点插值、平滑、拟合后得到链码的曲线描述,效果较好；文献[6]利用一种改进的链码特征对抽油系统阻尼系数进行识别,先将封闭曲线链码化,然后利用Fourier系数计算封闭曲线的形状特征,建立以形状特征为参数的欧氏距离,以该距离为优化目标函数计算合理的参数；文献[7]研究了链码特征在气象预报领域的应用,在构建基于气象图像内容层次结构模型的基础上,提出了相对极坐标系下的距离链码和基于八方向链码的累积导数和差码方法,用于轮廓形态特征的提取,较好解决了非刚体图像的相关特征提取；文献[8]提出了一种改进的Freeman链码并将其应用到人民币的面额识别中,通过统计纸币轮廓点横、纵坐标值出现的频率确定链码起始点,并定义一种新的多方向链码解决图像边界点的间断问题,有效提高了识别准确率.但上述方法都是针对某一特定应用领域,普适性和推广性较差,当实际应用背景变化时,算法的识别准确率较低.基于此,本文提出一种通用的几何图形链码特征提取方法.首先提出了链码空间分布的概念,在此基础上,计算图形链码统计直方图的空间分布熵,并将其作为形状特征用于几何图形的识别.此外,还给出了一种有效的图形相似性度量方法.仿真实验表明,本文提出的基于链码空间分布熵的几何图形识别方法正确、有效.

1 方向链码

方向链码是一种有效描述图形边界形状的编码方法,其特点是定义一种方向,然后根据该方向对图形边界进行编码,得到一组相连的具有特定长度和方向的字符串.目前较常用的方向链码包括Freeman链码和Bribiesca链码,如图1所示.

图1 链码编码方式Fig.1 Encoding modes of chain code

图2 示例形状Fig.2 Example shapes

2 算法描述

2.1链码空间分布熵特征

链码空间分布是指不同方向链码在链码串中的空间位置变化,图形的形状不同,其链码空间分布也不同,因此链码直方图的空间分布也必不相同.

图3 链码空间分布示例Fig.3 Examples of chain code distribution

下面以图3为例描述链码直方图的空间分布特征.由图3可见,链码串1的链码直方图空间分布为

(1)

链码串2的链码直方图空间分布为

(2)

(3)

(4)

其中:n表示方向个数;m表示某一方向链码的子串个数.从而可定义一个链码特征为

(5)

该链码特征结合了链码直方图和链码空间分布熵,因此具有起点无关性以及尺度、平移不变性.此时,再以图2所示的两个几何图形为例,可得它们的链码特征分别为〈(0.21,0),(0.04,0),(0.21,0),(0.04,0),(0.21,0),(0.04,0),(0.21,0),(0.04,0)〉和〈(0.21,0.29),(0.04,0),(0.21,0.29),(0.04,0),(0.21,0.29),(0.04,0),(0.21,0.22),(0.04,0)〉,可见它们的Fc特征区分性较强,特别有利于识别.

此外,为了使该特征具有旋转不变性,参考文献[10]的方法,在计算链码直方图和链码空间分布熵前,先对链码串进行旋转归一化处理.

2.2相似性度量

在得到几何图形的链码特征后,再考虑如何评价待识别图形与标准图形之间的相似性.目前较常用的评价方法包括欧氏距离、马氏距离、余弦相似等,但这些常用方法对于本文提出的图形链码特征并不适用,因此本文提出一种新的相似性度量方法.

假设有两个几何图形分别为X和Y,根据链码特征Fc定义相似性为

(6)

以图2所示几何图形为例,分别使用式(6)的相似性计算公式及欧氏距离、马氏距离、余弦相似方法,在得到链码特征的基础上,分别计算图中两个几何图形的相似性,结果列于表1.

表1 相似性计算结果Table 1 Similarity results

由表1可见,利用本文方法计算的相似性远低于其他方法的计算结果,因此本文提出的相似性度量指标更适合于本文的几何图形链码特征.

2.3算法实现

本文提出的基于链码空间分布熵和链码直方图特征的几何图形识别算法实现步骤如下：

1)根据八方向编码规则计算几何图形的基本方向链码串；

2)对基本方向链码串进行旋转归一化处理；

3)计算链码串的统计直方图；

4)计算链码串的空间分布熵；

5)根据式(5)构造图形链码特征；

6)根据式(6)计算待识别图形与数据库中图形链码特征之间的相似度,最终实现对几何图形的识别.

3 仿真实验

选取SQUID图像库为实验对象,该图像库是几何图形识别领域较常用的测试数据库,其中包含1 100幅不同类型鱼类的轮廓,图形种类丰富.但SQUID图像库中的图形基本为不规则几何图形,因此本文又利用MATLAB软件随机生成了700幅规则几何图形(256×256),其中包括圆形、椭圆形、矩形、三角形、五边形、六边形及八边形各100幅,共1 800幅图像.

为了保证评价的客观性和有效性,同时将本文算法与基本链码特征方法、链码直方图方法及文献[11]的方法进行比较分析.首先定义识别准确率,在一次识别过程中,会出现“准确识别”、“错误识别”及“未知”3种识别结果,因此定义识别准确率为

(7)

在相同条件下,共进行20次重复实验,每次随机从图像库中抽取500幅图像进行实验,识别结果如图4所示.由图4可见,本文方法的识别效果最好,评价识别准确率为90.70%,单次最高为93.88%,单次最低为88.67%；文献[11]方法的识别效果略低于本文方法,平均达到了88.40%,最高为90.70%,最低为86.85%；链码直方图方法的效果一般,平均仅为71.15%,最高为73.58%,最低为68.49%；基本链码法的结果最差,平均只有52.74%,最高为54.82%,最低为51.06%.

识别用时也是评价识别算法的一个重要评价指标,对算法的实际应用有较大影响.本文计算的识别用时是对单幅图像识别的平均用时,测试图像的选取方法和测试方法同上,测试结果如图5所示.由图5可见,基本链码法的识别用时最少,平均仅为0.650 8 s；链码直方图方法略高,平均为0.686 0 s；文献[11]方法与本文方法的用时基本相同,平均约为0.85 s.

图4 不同方法识别准确率的比较Fig.4 Comparison of recognition accuracyrate by different method

图5 不同方法识别用时的比较Fig.5 Comparison of recognition timeconsuming by different method

综合比较识别准确率和识别用时两个评价指标,本文算法的识别准确率在4种方法中最高,说明结合了链码空间分布熵和链码直方图的特征有利于几何图形的识别,特征区分性较好,对于同一种图形,不会因为链码起点的改变及图形的平移、旋转和尺度变化,而影响识别结果的准确性.但由于需要计算链码空间分布熵,所以算法的识别用时相对较长,但由测试结果可见,平均0.85 s的识别用时完全可以满足实际应用的需要.

综上所述,本文研究了基于链码特征的几何图形识别.在链码直方图特征的基础上,提出了链码空间分布熵特征,并将二者结合构成几何图形识别的形状特征.同时,本文给出了一种新的衡量图像之间相似性的度量方法.仿真实验表明,本文方法具有较好的识别准确率和较低的识别用时,能够较好地克服链码起点变化及图形平移、旋转和尺寸变化带来的影响.

[1] 孙来军,李江游,候影,等.一种规则几何图形的计算机识别方法 [J].微型机与应用,2011,30(9):42-45.(SUN Laijun,LI Jiangyou,HOU Ying,et al.A Computer Recognition Method of Regular Geometry Graphics [J].Microcomputer &Its Applications,2011,30(9):42-45.)

[2] 杨凯,华庆一,陈新胜.一种交互式识别几何图形的简易方法 [J].计算机技术与发展,2008,18(3):21-23.(YANG Kai,HUA Qingyi,CHEN Xinsheng.A Simple Approach to Recognize Geometric Shapes Interactively [J].Computer Technology and Development,2008,18(3):21-23.)

[3] 段汝娇,赵伟,黄松岭,等.一种基于改进Hough变换的直线快速检测算法 [J].仪器仪表学报,2010,31(12):2774-2780.(DUAN Rujiao,ZHAO Wei,HUANG Songling,et al.Fast Line Detection Algorithm Based on Improved Hough Transformation [J].Chinese Journal of Scientific Instrument,2010,31(12):2774-2780.)

[4] 张坤艳,钟宜亚,苗松池,等.一种基于全局阈值二值化方法的BP神经网络车牌字符识别系统 [J].计算机工程与科学,2010,32(2):88-90.(ZHANG Kunyan,ZHONG Yiya,MIAO Songchi,et al.A Plate-Character Identification System Based on Global Valve Binarization and the BP Neural Network [J].Computer Engineering &Science,2010,32(2):88-90.)

[5] 孙建成,曾培峰,禹素萍,等.方向链码及其曲线描述在纤维图像识别中的应用 [J].上海工程技术大学学报,2005,19(3):239-243.(SUN Jiancheng,ZENG Peifeng,YU Suping,et al.Directional Chain Code and Curve Description Based Fiber Image Recognition [J].Journal of Shanghai University of Engineering Science,2005,19(3):239-243.)

[6] 刘柏希,刘宏昭,饶建华,等.改进的链码特征识别方法及在抽油系统阻尼系数辨识中的应用 [J].机械工程学报,2007,43(12):212-216.(LIU Baixi,LIU Hongzhao,RAO Jianhua,et al.Ameliorative Characteristic Recognition Method Based on Modified Chain Code and Its Application in Damping Coefficients Identification for Rod Pumping System [J].Chinese Journal of Mechanical Engineering,2007,43(12):212-216.)

[7] 王萍,强兆庆,许晋玮,等.基于链码描述的图像图形特征提取 [J].计算机应用,2009,29(8):2065-2067.(WANG Ping,QIANG Zhaoqing,XU Jinwei,et al.Feature Extraction of Images and Graphics Based on Chain Code Description [J].Journal of Computer Applications,2009,29(8):2065-2067.)

[8] 杜京义,殷姣.改进的Freeman链码进行人民币的面额识别 [J].计算机工程与设计,2012,33(12):4643-4646.(DU Jingyi,YIN Jiao.Using Improved Freeman Chain Code to RMB Denomination Identification [J].Computer Engineering and Design,2012,33(12):4643-4646.)

[9] Iivarinen J,Visa A.Shape Recognition of Irregular Objects [J].SPIE,1996,2904：25-32.

[10] 韩光,赵春霞,陆建峰,等.面向彩色图像的尺度和旋转不变性特征提取方法及应用 [J].中国图象图形学报,2011,16(3):398-405.(HAN Guang,ZHAO Chunxia,LU Jianfeng,et al.Scale and Rotation Invariant Feature Extraction Method Based on Color Image and Its Applications [J].Journal of Image and Graphics,2011,16(3):398-405.)

[11] 姚雷博,郭超,张伟民.基于边缘点特征值的快速几何图形识别算法 [J].计算机应用研究,2011,28(11):4386-4388.(YAO Leibo,GUO Chao,ZHANG Weimin.Fast Geometry Figure Recognition Algorithm Based on Edge Pixel Point Eigenvalues [J].Application Research of Computers,2011,28(11):4386-4388.)

(责任编辑：韩 啸)

QuickRecognitionAlgorithmforGeometryFigureBasedonChainCodeFeature

HU Xiaohong

(CollegeofComputerScienceandTechnology,BeihuaUniversity,Jilin132021,JilinProvince,China)

In view of some shortcomings about currently shape recognition algorithms such as a large amount of calculation,long processing time,fewer species recognition,a fast geometry figure recognition algorithm based on chain code feature was presented.The algorithm combines the chain code histogram and chain code spatial distribution entropy,which considers both the statistical feature and the spatial feature of the chain code,having the advantages of being invariant to the position,rotation and scale of the image content and having nothing to do with the start point of the chain code.The simulation results show that the algorithm is able to identify many types of graphics with high recognition accuracy and shorter time consuming,and the overall performance is excellent.

geometry figure;chain code feature;information entropy;recognition

10.13413/j.cnki.jdxblxb.2015.03.27

2014-12-11. *“吉林省计算机学会2015年学术年会(JLPCF2015)”征集论文.

胡晓宏(1969—),女,汉族,硕士,副教授,从事计算机应用技术的研究,E-mail:Bhhxh69@163.com.

吉林省科技厅项目(批准号:20130102030JC).

TP317.4

：A

：1671-5489(2015)03-0489-05