一种改进的图像轮廓离散曲线演化算法研究

宋建辉，樊思萌，于 洋，刘砚菊

(沈阳理工大学 自动化与电气工程学院，沈阳 110159)

轮廓是一种高级的视觉信息，当目标失去颜色等其他特征时，人眼仍能根据轮廓识别出目标的类别[1]。目标图像的轮廓特征常用到智能监控等领域[2]。在提取目标对象的轮廓时，由于数字噪声和分割误差的影响，提取完轮廓的目标对象轮廓的部分轮廓段可能发生变形，或者轮廓上产生变形点，这会对后续识别工作产生干扰。在提取图像轮廓时采用了Sobel算子，尽管Sobel算子输出的边缘清晰准确，耗时短，同时抗噪能力强，但是Sobel算子并不能识别或去除变形部分[3-4]。针对这一问题，一些专家学者通过计算轮廓坐标和高斯核函数的卷积来消除边界变形部分，一定程度上解决了这个问题。但是这个方法可能导致轮廓的过度形变。Latecki等[5]提出了基于视觉成分的离散曲线演化(DCE)算法进行轮廓描述，该算法可以消除轮廓演化过程中的变形部分，并保留人眼视觉形状识别的重要部分。因此，本文引入DCE算法，通过DCE算法对轮廓特征进行描述改进。

离散曲线演化算法具有很强的鲁棒性，但不能适时地终止轮廓演化，如果数据量很大的话，DCE算法不能很好地完成轮廓演化工作。为了弥补这个缺陷，本文定义了三个演化终止函数并分别设定阈值，提出了一种改进离散曲线演化算法(N-DCE)，将该算法用于轮廓的去噪、简化以及特征描述中。实验表明，DCE算法不仅可以去除边界的变形部分，还可以减少原始轮廓角点的数量，从而可以降低轮廓的复杂度，提高效率。

1 传统DCE轮廓简化算法

离散曲线演化的基本原理如下[6]：对于目标对象上的任意一段轮廓，其每经过一次演化，就删掉轮廓段上对目标识别贡献度最小的点，假设有s1={v1,v2}和s2={v2,v3}两条线段，其中v1、v2、v3分别表示轮廓段上的点，若这3个点中，v2对目标识别贡献度最小，就删除点v2，之后连接点v1和v3形成一条新线段s3={v1,v3}，离散曲线演化如图1。

图1 离散曲线演化示例图

关于目标识别贡献度的函数定义为

(1)

式中：β(s1,s2)是线段s1、s2的转角；l(s1)、l(s2)是线段s1、s2长度。K(s1,s2)的值越小，线段s1、s2的目标识别贡献度越小，其视觉重要性较低。

DCE算法在轮廓演化中能够剔除轮廓变形部分，但仍存在不足[7]。

首先，DCE算法演化程度很难得到保证。图2为离散曲线演化过程。如图2b中的轮廓演化程度不足，目标对象的轮廓依旧有比较多的噪声干扰；而图2d、2e、2f中发生了过演化，目标对象的轮廓演化成为一个不规则的多边形，已经不具备识别价值；只有图2c中轮廓演化程度较为理想。

其次，Latecki等提出的DCE算法中的重视函数是基于视觉部件的切空间函数，切空间函数的阈值不能实现动态自适应，该函数计算量大且算法复杂，不利于实际应用。

因此，本文提出一种改进的离散曲线演化算法(N-DCE)，该算法用面积比函数、平均角点距离函数和点与质心平均距离函数作为终止函数。在进行轮廓演化算法时，只需要为同一个形状数据库中的所有形状 设定一个阈值，并不要求终值函数的阈值具有动态自适应能力。

图2 离散曲线演化过程

2 N-DCE轮廓简化算法

随着轮廓演化程度的变化，演化后目标对象轮廓区域的面积会发生一定的改变。演化后目标对象的轮廓所围成的区域与原始目标对象轮廓所围成的区域比率可以更好地表示目标对象形状相似性程度。面积比函数可以如下定义[8]：定义集合{C0,C1,…,Cm}为原轮廓C离散演化后的轮廓，C0表示目标对象原轮廓，Cm演化得到的凸多边形，原轮廓C0围成的几何图形的面积为S0，第i次演化后的轮廓Ci围成的封闭几何图形面积为Si，则定义函数

(2)

式中n0表示原轮廓C0采样角点数。设定面积比阈值TS，当DS(Ci)>TS时，终止演化。

不难发现面积比函数存在问题，首先，如果原轮廓图像的图像分辨率较低，则其轮廓段上可能存在若干个变形点或变形片段，这些变形部分的累加可能会在计算面积时产生很大的偏差，造成演化程度不足或过度；其次面积比函数不能很好地反映离散后的目标轮廓与原轮廓的相似度，可能会出现面积比值接近于1但实际上演化前后所产生的图像形状有较大的差别。

为了弥补面积比函数的缺陷，本文在面积比函数的基础上又提出了平均角点距离函数和点与质心平均距离函数的演化终止函数。增加新的终值函数后，可以改进轮廓演化算法，提高轮廓演化效果。平均角点距离的定义为：当原轮廓C0经过i次演化后得到Ci时，原轮廓C0上任意一角点到Ci中的相对应角点的距离的平均值。角点与质心平均距离的定义为：当原轮廓C0经过i次演化后得到Ci时，Ci上的任意一角点到轮廓图像质心距离的平均值。具体步骤如下。

(1)图3为轮廓垂距示意图。假设曲线段AB是原轮廓C0上的一部分，Pi是曲线段AB上的点，当原轮廓C0经过i次演化后得到Ci时，曲线段AB离散演化后得到直线段AB；

(2)设曲线段AB上的任意一角点到直线段AB上的垂距表示为hk，则平均角点距离DH(Ci)的数学表达式为

(3)

(3)给定阈值TH，当DH(Ci)>TH时，终止离散曲线演化。

图3 轮廓垂距示意图

关于轮廓的质心概念，其与重心常放在一起进行分析。质心和重心是两个不同的力学概念。重心是由目标对象的重力所组成的平行力系统的中心。质心与目标对象的质量分布有关，可以被视为一个特殊的“质点”，其质量等于整个目标对象的质量。通常，质心和重心并不处在同一个点。然而，当把一个小尺寸的物体放置在重力场中时，则该物体上各质元所处的重力加速度g是相等的。此时，物体的质量分布与重力分布相同，因此该物体的质心和重心处在同一点。利用物体质心和重心位置相重合这一特性，可以通过实验得到不规则物体的质心位置所在。综上所述，在这里可将轮廓质心与轮廓重心视为一点。具体步骤如下。

(1)根据灰度重心法[9-12]，将区域内每一像素位置处的灰度值作为该点的“质量”，其求区域中心的数学公式为[13-14]

(4)

(5)

(6)

(3)角点与质心平均距离DO(Ci)的数学表达式为

(7)

(4)给定阈值TO，当DO(Ci)>TO时，终止离散曲线演化。

3 实验结果与分析

表1～表3为不同终止函数控制N-DCE演化的结果比较。点数是指轮廓采样点的数量。时间是指从原轮廓演化到该轮廓的运行总时长，包括两部分，一是在进行完一次轮廓演化过程后，重新计算控制函数的时间；二是运行轮廓演化的时间。从表1～表3来看，当原轮廓图像分辨率较低时(轮廓上变形部分较多)，本文采用面积比函数、平均角点距离函数和点与质心平均距离函数三个终止函数的轮廓演化控制效果比仅采用面积比函数控制的效果(角点数较少)要好。当原轮廓图像分辨率较高时，二者的运行结果相似。就轮廓演化运行时间这个方面而言，采用本文三个终止函数来控制轮廓演化的时间要比仅使用面积比终止函数控制轮廓演化的时间更长，不仅是因为终止函数更多，更重要的原因是高分辨率轮廓图像上的点数更多，而当轮廓进行完一次演化后，都需要重新计算个垂距来作为下一次轮廓演化终止函数，需要更长的计算时间。因此，针对分辨率不同的轮廓形状数据库：当轮廓图像分辨率较高时，采用面积比终值函数就可基本满足要求；当轮廓图像分辨率较低时，宜采用本文算法。

表1 大型车辆测试结果对比

表2 小型车辆测试结果对比

表3 昆虫类测试结果对比

4 结束语

定义基于面积比函数、平均角点距离、角点与质心平均距离函数三者作为终值函数的N-DCE算法，与传统DCE算法相比可以大幅度减少轮廓的采样点数目和去除轮廓噪声，对后续目标识别具有重要意义。