高分辨率遥感影像圆特征提取算法研究

欧阳晖，张俊前

(1.重庆市勘测院，重庆 401121； 2.重庆市地理国情监测工程技术研究中心，重庆 401121)



高分辨率遥感影像圆特征提取算法研究

欧阳晖1，2*，张俊前1，2

(1.重庆市勘测院，重庆 401121； 2.重庆市地理国情监测工程技术研究中心，重庆 401121)

高分辨率遥感影像的圆特征提取广泛应用于摄影测量中，其精度高低对相机标定和特殊目标监测有着重大的影响。在实际应用中，圆特征提取的精度高低主要取决于所使用的圆特征提取算法。本文研究总结了重心法、中心收缩法和基于边缘跟踪的最小二乘圆拟合算法等常用的圆特征提取算法的原理和实现步骤，并根据实验数据的比较分析，给出了这3种常用圆特征提取算法各自的优缺点和适用情况。最后，提出并实现了一种基于边缘二次跟踪的双圆检测算法，解决了由成像目标缺损引起的提取圆心位置偏差的问题。

圆特征提取；二值化；双圆检测

1 引 言

特征提取是模式识别和计算机视觉的重要内容，它是对图像进行进一步分析的重要基础。因为圆具有同向扩散性，相对于方形或十字形目标靶能很好地降低摄影测量误差，因而被广泛用于摄影测量中。如相机定标中采用圆形栅格形式的标定靶标，二维运动测量中也常以圆斑作为标记物。在这些应用中，圆的中心定位精度对测量精度和相机定标精度都有着至关重要的影响。因此圆特征提取方法的研究，对模式识别及摄影测量具有重大意义。

常用的圆特征提取算法有重心法、Hough变换法、圆拟合算法和中心收缩法。孔兵等人针对重心法、Hough变换法等在检测精度和速度上的不足，提出了一种基于圆拟合的激光光斑中心检测算法，根据最小二乘原理用圆来逼近激光光斑轮廓，从而提取光斑中心和半径[1]；朱桂英等对经典Hough变换算法、随机Hough变换算算法及广义Hough变换算法进行了总结，并提出了一种改进的Hough变换应用于圆检测，检测速度有所提高[2]；霍建亮等人提出了一种利用最小二乘法迭代修正随机圆检测的改进算法，对圆局部信息缺损和噪声具有很好的鲁棒性[3]；李婷等提出结合Blob分析和最小二乘法实现对圆形物体的自动检测，提高了检测的准确性和检测的效率[4]；Chung等分析了影响随机圆检测算法速度和精度的因素，提出了采样策略和校准策略，使用梯度编码约束随机采样和利用了圆直径特性校准初次检测结果，同时提升了速度和精度[5]；刘好龙等分析了重心法、Hough变换法、圆拟合算法的圆特征提取应用中的局限性，提出了一种提高圆拟合精度的一种方法[6]；陈珂等针对现有圆检测算法运算复杂度高，难以达到复杂自然场景中的实时检测要求的问题，提出一种利用一维概率Hough累积提取有效圆及其初始半径，最后利用圆的直接最小二乘拟合进一步定位圆半径和圆心[7]。

在参数不超过二维的情况下，Hough变换有着很理想的想过，但当参数达到或超过三维时(圆的参数空间为三维：圆心(x，y)，半径r)，这种变换的计算时间和存储空间急剧增大，很难在实际应用中使用[3]，因此本文不做研究。本文分析总结了重心法、中心收缩法和基于边缘跟踪的最小二乘圆拟合算法在圆特征提取应用中的优缺点和适用性，并针对成像目标缺损影响圆特征提取精度的问题，提出了一种全新的基于边缘二次跟踪的双圆检测算法。

2 数据预处理

2.1 图像增强

在图像的生成、传输、接收和处理过程中往往会受到噪声干扰，这些噪声使得图像上像素点的灰度值不能正确地反映空间物体对应点的灰度值，降低了图像质量，影响了图像的可判读性。图像增强是在不追究图像降质原因的情况下，通过作用于图像的空间域或频率域，突出感兴趣目标物，衰减其他次要信息，以求改善图像的视觉效果，提高图像的目视可读性和机器识别性，使图像更适合于人或机器处理。

图像增强按目的可分为两类：一类是图像平滑，另一类是图像锐化。前者是为了抑制噪声、改善图像的视觉效果，而后者则是为了突出边缘，使图像更易于机器识别和处理。

本课题主要采用中值滤波算法来增强图像，具体原理及实现步骤参见参考文献[8]。

2.2 二值化

图像二值化是一种图像分割方法，它将图像中感兴趣的目标物从背景中分割出来，其过程类似于按近似属性进行聚类。它将像素点按灰度分成两部分，使得图像上所有的像素点的灰度值不是“0”就是“255”，从而从多值的数字图像中提取出目标物体以供进一步研究。

本文选用最常用的全局阈值法——OTSU算法。

OTSU算法，又称大津法、最大类间法，由Otsu于1979年提出，因计算简单、自适应强而被公认为效果最好、应用面最广的全局阈值法。该方法的主要思想是找到一个灰度值，将图像中所有像素分为两类，并使得类内方差最小，类间方差最大，那么此灰度值就是最佳二值化阈值。具体原理及实现步骤参见参考文献[10]。

3 常用圆特征提取算法

3.1 重心法

重心法，又称一阶矩法，它将组成圆的所有像素的x坐标和y坐标的平均值作为该圆的灰度质心，亦即圆心，再由位于圆最外侧的点到该圆心的距离作为半径。该算法简单明了，计算速度快，但抗噪能力差，对于图像中圆斑有缺损，区域轮廓呈凹形时，得到的中心有可能位于区域外，产生较大误差。

为了减少计算量，本文对重心法做了改进，通过计算圆的最外一层像素点的x坐标和y坐标的平均值得到圆的灰度质心，即圆心坐标，然后将边缘跟踪起始点到圆心的距离作为圆的半径。其具体实现过程如下：

(1)对整幅图像按从上到下，从左往右的顺序进行逐行扫描，开始8-邻域跟踪；

(2)跟踪完一个区域(即圆)后，得到圆的最外层点的x坐标之和M10以及y坐标之和M01，还有该圆的最外层像素点的数量num和起始点坐标(StartPt.x，StartPt.y)。那么该圆的圆心坐标X，Y和半径R可由下式计算得到：

X=M10/num

(1)

Y=M01/num

(2)

(3)

(3)由圆的圆心坐标和半径可以得到圆的外接矩形，按照自上而下，从左往右的顺序遍历矩形内的像素点，并计算矩形内像素点到圆心得距离Range，对Range小于或等于圆半径R的点进行标记(灰度值赋0)，防止对该区域进行重复跟踪遍历。

(4)继续跟踪检测下一个圆，直到遍历完整幅图像像素。

3.2 中心收缩法

中心收缩法假设圆形区域是封闭、连通的平面，无空洞，且是可塑的，若在保持区域连通条件下，由区域边缘各处同时向里均匀收缩，使区域逐渐缩小，类似于逐层剥去圆的边缘像素。最终会出现以下两种情况：①最后只剩下一个像素，如图1左侧圆所示，则将此点作为该区域的中心；②最后没有剩下像素，且最后一次收缩对象为4个像素点，如图1右侧圆所示，则将最后一次收缩的4个像素点的几何中心作为该区域的中心。因此，中心收缩法又叫剥皮法。

图1 圆域重心收缩的两种可能结果

在具体实现时主要采用对图像进行反复边缘跟踪的方法达到“剥皮”的效果。实现过程如下：

(1)对整幅图像按自上而下，从左到右的顺序逐行扫描，当找到一个区域的起始点后进行8-邻域跟踪；

(2)在对一个区域进行8-邻域跟踪的过程中，对除了起始点以外的被跟踪像素的灰度赋值为0，起始点的灰度赋为250；如此一个圆被逐层跟踪多次后，就只剩下由灰度值为250的已跟踪起始点和灰度值为255的单点组成的线段；

(3)再次按自上而下，从左到右的顺序对整幅图像进行扫描，当遇到第一个灰度值大于等于250的像素点时，便以此像素点为起始点，对上一步得到的直线进行8-邻域跟踪。

(4)每跟踪完一条线段，判读跟踪的最后一个像素点的灰度：若灰度值为255，则说明该点在第一次遍历时是一个孤立点，没有被跟踪，因此将该点的坐标作为圆心坐标，跟踪的第一个点到该点的距离即为半径；若灰度值为250，则表明该点在第一次遍历过程中曾作为起始点被跟踪，因此以该点为起始点的由4个像素组成的最小封闭区域的几何中心即为圆心，半径为跟踪第一个点到圆心的距离。

3.3 基于边缘跟踪的最小二乘圆拟合

最小二乘法(Least Squares Analysis)是一种数学优化技术，它通过最小化误差的平方和找到一组数据的最佳函数匹配。它用最简的方法求得一些绝对不可知的真值，而令误差平方和为最小。一般最小二乘法用于曲线拟合(Least Squares Fitting)。

圆的解析方程为：

(X-A)2+(Y-B)2=R2

(4)

拟合的目的就是根据一组数据计算A，B，R值。

展开公式(4)得：

X2-2AX+A2+Y2-2BY+B2=R2

(5)

令a=-2A，b=-2B，c=A2+B2-R2，可得圆曲线的另一种形式：

X2+Y2+aX+bY+c=0

(6)

因此只要求出参数a，b，c就可以求得圆心和半径：

(7)

(8)

(9)

具体实现过程如下：

(1)对整幅图像按自上而下，从左到右的顺序逐行进行扫描，当找到第一个区域的起始点后，暂停扫描，开始以此点为起始点进行8-邻域跟踪；

(2)对该区域的边界点一边进行跟踪，一边将跟踪过的点的x坐标和y坐标分别存储在两个数组中；

(3)跟踪完毕后得到所有边界点的x坐标和y坐标，带入以上推导公式，即可求得该圆的拟合圆心和半径；

(4)以所得拟合圆的圆心和半径求得该圆的外接矩形，然后对矩形内的像素点按自上而下，从左到右的顺序进行遍历，计算每个像素点到圆心的距离range，凡是range≤R的点，都一律赋值为0，防止重复对该区域进行遍历；

(5)继续对图像进行扫描，寻找下一个区域，直到扫描完图像的所有像素。

4 实验与分析

4.1 实验平台

操作系统：windows 7旗舰版32位SP1，处理器：AMD Phenom Ⅱ N660双核，内存4G。

4.2 实验过程

采用控制单一变量的方法，对同一张影像l-1.bmp进行相同的图像预处理操作，然后分别用不同的圆检测方法提取影像中的圆特征信息，最后对不同的圆特征提取方法所得到的数据进行对比分析。原始影像如图2所示：

图2 原始影像

主要过程如下：

(1)读取影像数据；

(2)图像平滑：进行中值滤波，减少噪声干扰；

(3)二值化：采用OTSU算法分离背景和目标；

(4)利用重心法对影像圆特征进行提取，得到影像中圆的圆心位置和半径大小；

(5)图像还原；

(6)重复(1)～(4)操作，分别利用基于边缘跟踪的最小二乘圆拟合算法、中心收缩法对影像进行圆特征提取，得到影像中圆的圆心位置和半径大小；

(7)比较分析各算法提取的圆心坐标精度。

4.3 实验结果与分析

影像中一共有50个大小不同的圆，用三种不同的圆特征提取算法对影像中的圆特征进行了提取，得到三组不同数据。下表1中，(X1，Y1)为重心法所测圆心坐标，(X2，Y2)为基于边缘跟踪的最小二乘圆拟合法所测圆心坐标，(X3，Y3)为中心收缩法所测圆心坐标。

三种圆特征提取算法结果比较 表1

(1)提取精度分析

对这三组数据两两进行比较，从圆心X、Y坐标和半径R的差值的平均值以及方差大小进行比较，结果如图3、图4所示：

图3 差值平均值比较结果

图4 差值方差比较结果

由此可见，重心法和基于边缘跟踪的最小二乘圆拟合算法的提取精度要优于中心收缩法，三种圆特征提取算法的提取精度相差在亚像素级，基于边缘跟踪的最小二乘圆拟合算法和重心法提取精度相差不大，二者的圆心坐标提取差值的平均值小于0.2个像素，方差也在0.16～0.21之间，半径提取的差值平均值为0.33，方差为1.02，这是因为半径的提取是通过已提取圆心与圆外围点的距离运算得到，存在误差累积。中心收缩法圆心提取的精度只能达到像素级，与前两种能达到亚像素级精度的方法提取的圆心坐标差值的平均值达到了0.74个像素，接近一个像素，半径差值在0.53个像素，且差值分布较分散，圆心坐标的差值方差在2.6～10.2之间，半径差值的方差最高达到5.95。

(2)提取效率分析

对同一幅影像采用同一种二值化方法处理后，分别用三种圆检测算法进行圆特征提取，统计不同算法的运行时间，每种算法重复试验10次，然后取该算法这10次运行的平均时间作为算法一般运行时间，并与其他算法的一般运行时间进行比较。结果如表2所示：

三种圆特征提取算法运行时间比较 表2

由上表可知，重心法和基于边缘跟踪的最小二乘圆拟合算法的运行效率较中心收缩法高。因为重心法和基于边缘跟踪的最小二乘圆拟合算法都只需对圆的最外围一圈像素进行跟踪和解算处理，而中心收缩算法则需要对同一个圆重复进行边缘跟踪处理，计算量大，所需计算时间长。

(3)抗噪性分析

对图像进行二值化后，在目标物的周围加入椒盐噪声，以此含有椒盐噪声的二值化图像作为原图像，分别用三种圆特征提取方法提取该图像中的圆特征，并将提取得到的圆心在图中用十字丝进行标记，方便直观地进行比较。图5中(a)为原图像，(b)为重心法提取结果，(c)为基于边界的最小二乘圆拟合算法提取结果，(d)为中心收缩法的提取结果。

图5 不同圆特征提取算法的抗噪性实验结果

由上图不难看出，基于边缘跟踪的最小二乘圆拟合算法的抗噪性能最好，几乎不受椒盐噪声的影响，能够准确提取出圆特征信息；而重心法和中心收缩法的抗噪性则相对较差，出现了很多误检圆心。从误检点的分布和数量来比较，重心法的抗噪性较之于中心收缩法较好，误检点数量少，且其分布较之于重心法误检点的分布离正确圆心位置较远。

5 基于边缘二次跟踪的双圆检测算法

该方法主要针对双圆目标靶，能够在一定程度上提高解算的目标靶位置精度。使用双圆检测算法前必须对目标进行边缘锐化，提取出双圆边缘，然后在利用基于边缘跟踪的最小二乘圆拟合检测出外圆特征的条件下，再对内圆用同样的方法进行圆特征提取，然后比较两次提取圆心坐标的差值，如果该差值小于给定阈值，则取两圆圆心的平均坐标作为双圆的共同圆心，否则不对该目标进行解算。

该方法不仅能提高目标圆心的测量精度，而且可有效避免因为成像目标缺损引起的圆心位置偏差。

主要实现过程如下：

(1)对整幅图像自上而下，从左往右进行逐行扫描，直到遇到第一个非零点；

(2)将该非零点作为第一个圆的起始点，对该圆进行8-邻域跟踪，并记录被跟踪点的x坐标和y坐标；

(3)跟踪完毕后，利用跟踪得到了圆的边界点的x坐标和y坐标进行最小二乘拟合，得到外圆的拟合圆心(A1，B1)和半径R1；

(4)由上一步得到的外圆的圆心和半径可以得到外圆的外接矩形，按自上而下，从左到右的顺序扫描该矩形内的像素，并计算像素点到外圆圆心的距离range1，对于range1∈[R-2，R+2]的点赋值为0，以消除外圆轮廓余点(外轮廓在跟踪后未被标记的点)的干扰；

(5)对外圆的外接矩形内的点再次按照自上而下，从左到右的顺序进行扫描，直到遇到第一个非零点，即为内圆的起始点；

(6)对内圆进行8-邻域跟踪，利用跟踪得到的内圆边界点的x坐标和y坐标通过最小二乘圆拟合法得到内圆的圆心坐标(A2，B2)和半径R2；

(7)对内圆的外接矩形内的点进行扫描，并计算扫描像素点到内圆圆心的距离range2，对于range2∈[0，R+2]的点全部赋值为0，防止重复遍历；

(8)比较得到外圆和内圆的圆心坐标的差值(A1-A2)、(B1-B2)，若二者都小于设定阈值I=1，则双圆的圆心坐标为：

A=(A1+A2)/2

(10)

B=(B1+B2)/2

(11)

否则，跳出循环，舍弃对该圆的检测；

(9)继续对图像进行扫描，寻找下一个双圆区域，直到扫描完图像中的所有像素点。

6 结 语

本文在研究总结三种常用圆特征提取算法原理的基础上，通过实验分析，比较了三种圆特征提取算法在提取精度、提取效率和抗噪性等方面的差异，发现重心法和基于边缘跟踪的最小二乘圆拟合算法精度和运行效率相近，明显优于中心收缩法，且基于边缘跟踪的最小二乘圆拟合算法相对其余两种算法的抗噪能力突出。最后，针对成像目标缺损引起的提取圆心位置偏差的现象，提出并实现了一种基于边缘二次跟踪的双圆检测算法。本文研究发现，在效率和精度方面，各提取算法已经接近极限，发展空间有限，这一点在本文的实验数据中可以看出。因此，未来的发展方向在于发现一种高稳定性、高适应性的圆特征提取算法或提取流程。

[1] 孔兵，王昭，谭玉山. 基于圆拟合的激光光斑中心检测算法[J]. 红外与激光工程，2002，31(3)：276～279.

[2] 朱桂英，张瑞林. 基于Hough变换的圆检测方法[J]. 计算机工程与设计，2008，29(6)：1462～1464.

[3] 霍建亮，曾翎，王德胜等. 基于最小二乘法改进的随机圆检测算法[J]. 光电工程，2011，38(5)：145～150.

[4] 李婷，柳宁. 基于机器视觉的圆定位技术研究[J]. 计算机工程与应用，2012，48(9)：153～156.

[5] Chung Kuo-Liang，Huang Yong-Huai，Shen Shi-Ming，et al. Efficient sampling strategy and refinement strategy for randomized circle detection[J]. Pattern Recognition，2012，45(1)：252～263.

[6] 刘好龙，侯文，范亚龙等. 一种改进的激光光斑中心定位算法[J]. 计算机测量与控制，2014，22(1)：139～141.

[7] 陈珂，吴建平，李金祥等. 一维概率Hough变换的实时鲁棒多圆检测方法[J]. 计算机辅助设计与图形学学报，2015(10)：1831～1841.

[8] 朱明胜. 图像增强技术研究与实现[D]. 合肥：安徽大学，2014.

[9] 童立靖，张艳，舒巍等. 几种文本图像二值化方法的对比分析[J] . 北方工业大学学报，2011(1)：25～33.

[10] 郭佳，刘晓玉，吴冰等. 一种光照不均匀图像的二值化方法[J] . 计算机应用与软件，2014(3)：183～186.

Circular Feature Extraction and Precision Evaluation of the High Resolution Image

Ou Yanghui1，2，Zhang Junqian1，2

(1.Chongqing Survey Institute，Chongqing 401121，China；2.Chongqing Engineering Research Center of Geographic National Condition Monitoringr，Chongqing 401121，China)

Circular feature extraction of the high resolution image has been widely used in photogrammetry，and the precision of the extraction has a great effect on digital camera calibration and specific target monitoring. Based on the summarize of 3 common circular feature extraction algorithms，according to the results of the tests，this paper calculated that the advantages and disadvantages of the 3 different circular feature extraction algorithms，include gravity algorithm、center shrink algorithm and least squares analysis algorithm based on edge tracking. At last，this paper suggested a double circle extraction algorithm，solved the problem of inaccurate center position caused by deviation of the target.

circular feature extraction；image binarization；double circle extraction

1672-8262(2016)05-58-06

P231.1，TP751

A

2016—03—17

欧阳晖(1990—)，男，助理工程师，主要从事航空摄影测量数据获取和数据处理工作。

住房和城乡建设部科学技术计划项目(2015-K8-009)