基于改进轮廓提取的Hough变换椭圆检测方法

翟永立 丁雷 裴浩东

关键词： 椭圆目标; 边缘点分类; 检测方法; 轮廓提取; 随机Hough变换; 采样次数

中图分类号： TN911.23?34; TP391.9            文献标识码： A                   文章编号： 1004?373X（2019）06?0034?04

Abstract： The characteristic of the elliptical object on the imaging plane is analyzed， and a Hough transform ellipse detection method based on improved contour extraction is proposed， which can effectively extract the outline of the ellipse in the image. The edge points of images are classified after edge detection， so as to remove cross points and isolated points， and save endpoints. The non?closed contour in the image is extracted according to the endpoints. The remaining closed contour is extracted by scanning images. In allusion to the random Hough transform， the times of sampling and calculation are determined for the contour according to the length of each contour. A threshold value is set to judge the statistical value of each group of elliptic parameters inside each loop， so as to jump out of the loop. The experimental results show that the memory consumption and calculation amount of the algorithm are greatly reduced in comparison with the ordinary random Hough transform.

Keywords： elliptical object; edge point classification; detection method; contour extraction; random Hough transform; sampling times

0  引  言

椭圆形物体在现实生活中大量存在，随着计算机视觉技术的发展，人们需要计算机从图像中确定椭圆的位置和形状大小，如自动化生产线上圆形物体的检测、目标上面的圆形或者椭圆特征的识别等。并且椭圆检测是图像处理研究中的一项基础任务，它在模式识别和机器视觉等领域内有着广泛的应用。

近年来，研究人员提出了大量的椭圆检测方法，如最小二乘拟合算法[1?3]、基于Hough变换拟合算法[4?6]、基于几何特征的拟合方法[7?8]等。最小二乘拟合原理简单，但是对噪声和孤立点存在较差的鲁棒性，拟合结果误差较大。随机Hough变换[9]采用参数空间多对一映射，降低了计算复杂度和内存占用量，但大量随机采样和累计问题严重影响了RHT的性能。基于几何特征的拟合方法是利用椭圆本身的几何特征，如弦中点、椭圆极和极弦性质[10]和点与切线方向[11]等进行椭圆拟合，但是由于噪声等的影响，梯度的计算值与方向受到很大的影响，所以大大影响了计算的精度。

本文采用基于随机Hough变换的椭圆拟合方法，首先改进常规的轮廓提取方法，然后采用随机Hough变换进行椭圆检测，并对Hough变换进行一定的优化，降低计算量。该方法的时间空间消耗都较小，有一定的实用价值。

2.1  改进的轮廓提取方法

常用的轮廓提取方法是根据轮廓点间8?邻接性质对细化图像中的轮廓像素点进行跟踪提取，跟踪采用逐行扫描的方法。但是该方法会把交叉轮廓认为是同一个轮廓。

针对这一点，本文对此方法进行改进，首先进行边缘点的分类，如图3所示，去除孤立点和交叉点;然后再次去除因为交叉点造成的孤立点，并提取端点坐标;最后先根据端点坐标提取非封闭的轮廓边缘，根据轮廓的长度，去除较短的轮廓，再扫描整幅图像，提取封闭的轮廓边缘并置零。至此，图像中的轮廓提取完毕，避免了交叉轮廓分类为同一个轮廓。

2.2  改进的随机Hough变换检测方法

随机Hough变换检测椭圆的基本思想是采用多对一的映射关系，主要通过随机采样和动态链表存储，随机选取5个点计算椭圆的参数，对计算所得的参数进行累加，减少了使用传统Hough变换所需要的计算量和占用的内存。但是，RHT的无目标采样会引入大量的无效累积，浪费大量的计算时间和存储空间。

2.2.1  随机采样总次数[Ncy]的确定

传统的随机Hough变换的每个轮廓的采样次数都是采用一个统一的固定值，这样就造成不管轮廓的长短，都要进行同样的采样次数，这就产生了大量的冗余计算。本文算法在循环外部控制每个轮廓上进行随机采样的总次数，根据轮廓的长度进行自适应的调节采样次數，设第i个轮廓长度为[Li]，取采样次数为[Lin]，[n]为调节参数，根据轮廓的长短在1～4内变化。通过该方法节省了程序的运行时间。

2.2.2  循环内部采样次数的确定

随机Hough变换在计算每个轮廓的参数时，需要进行固定次数的采样计算，然后对参数存储数组进行统计次数的比较，数组中统计次数最大的参数对应的椭圆就是该轮廓的椭圆表达式参数。

在对每一个轮廓进行参数计算的循环内部，本文设计一个阈值[Tc]，当统计数值不小于该阈值时，就认为该统计值对应的椭圆参数就是轮廓的椭圆参数保存椭圆参数，并跳出该循环。根据轮廓的长短，[Tc]可取8～30。通过此方法可以大大减少椭圆检测所占用的时间与内存。

3  实验结果分析

为了验证本文算法的有效性，在PC上对图像进行处理，该算法利用Matlab 2016平台编程实现。首先采用人工合成图像，对普通轮廓提取算法和本文所用轮廓算法的效果进行对比，如图4所示。

由图4a）、图4b）对比可以看出，本文算法能准确地区分出每一个物体的轮廓，而普通轮廓提取方法并不能很好地把重叠物体的轮廓分离开来。这是由于本文算法在提取轮廓时利用像素的邻域信息，判断出交叉点并进行分离，这样在提取时就可防止重叠物体轮廓被认为是一个物体的轮廓。

为了对比算法检测椭圆的效果，对一张246×300大小的硬币图，分别使用本文算法、基于轮廓的随机Hough变换算法和最小二乘方法进行椭圆检测，效果如图5所示。

检测算法运行时间对比如表1所示。

对比图5的4张图和表1可以看出，三种方法都可以检测出硬币的轮廓。最小二乘法会检测出虚假的椭圆，这是因为最小二乘法的抗噪声能力较弱，容易受到其他点的影响。本文算法与随机Hough变换的检测效果在直观上看均能准确地检测出所有轮廓，但是从运行时间上看，随机Hough变换的运行时间要多于本文算法，这是由于随机Hough在计算每条轮廓时都要进行固定次数的采样，进行大量的冗余计算。而本文算法首先根据每条轮廓的长度来确定该条轮廓的采样次数，然后在每个循环内部，对每个参数出现的次数进行统计，大于一定阈值时就认为找到该轮廓椭圆参数，结束该循环，因此减少了许多的冗余计算和内存占用。

使用人工合成的图像来检验前两种方法的精确性，对同一个椭圆进行检测，对比连续20次椭圆中心的定位误差。根据图6可以看出两种方法对于同一个椭圆定位的误差，相差不大，都能够较准确地检测出椭圆参数。

4  结  论

为了实现对光电图像中的椭圆形目标的快速检测，本文研究了Hough变换、最小二乘法等椭圆检测方法。为了提高检测速度，本文提出一种基于改进轮廓提取的随机Hough检测算法。先对常规轮廓提取算法进行改进，能够实现交叉轮廓的分离，避免把交叉轮廓提取为同一个轮廓;然后改进随机Hough变换，减少计算过程中的冗余采样，缩减运行时间和内存空间。采集图像数据对算法进行验证，结果表明，此方法可以很大程度上降低计算量，可实现对图像中椭圆的快速检测。

参考文献

[1] 熊风光，李希，韩燮.基于整体最小二乘的椭圆拟合方法[J].微电子学与计算机，2017，34（1）：102?105.

XIONG Fengguang， LI Xi， HAN Xie. A method of ellipse fitting based on total least squares [J]. Microelectronics & computer， 2017， 34（1）： 102?105.

[2] BEKTAS S. Least squares fitting of ellipsoid using orthogonal distances [J]. Boletim de ciências geodésicas， 2015， 21（2）： 329?339.

[3] 何志强，曹彪，张立新.基于改进最小二乘的缺陷椭圆定位方法[J].计算机与数字工程，2017，45（11）：2113?2117.

HE Zhiqiang， CAO Biao， ZHANG Lixin. A defect ellipse locating method based on least squares [J]. Computer and digital engineering， 2017， 45（11）： 2113?2117.

[4] 陆路.基于Hough变换的医学显微细胞检测技术研究[D].湘潭：湘潭大学，2015.

LU Lu. Research on the detection technology of medical microscopic cell based on Hough transform [D]. Xiangtan： Xiangtan University， 2015.

[5] 陈余根，杨艳.基于霍夫变换椭圆检测的两种改进算法[J].半导体光电，2017，38（5）：745?750.

CHEN Yugen， YANG Yan. Two improved algorithms for ellipse detection based on Hough transform [J]. Semiconductor optoelectronics， 2017， 38（5）： 745?750.

[6] 邵刚，屈保平，曹鹏，等.基于Hough变换的摄像机跟踪系统设计[J].测控技术，2013，32（8）：32?35.

SHAO Gang， QU Baoping， CAO Peng， et al. Design of camera tracking system based on Hough transform [J]. Measurement & control technology， 2013， 32（8）： 32?35.

[7] 李艳荻，徐熙平，钟岩.特征弦约束随机Hough变换在椭圆检测中的应用[J].仪器仪表学报，2017，38（1）：50?56.

LI Yandi， XU Xiping， ZHONG Yan. Application of RHT based on character string constraint in ellipse detection [J]. Chinese journal of scientific instrument， 2017， 38（1）： 50?56.

[8] 高煜妤，王春芳.基于欧氏距离图的随机Hough变换椭圆检测方法[J].现代电子技术，2016，39（21）：61?64.

GAO Yuyu， WANG Chunfang. Ellipse detection method based on random Hough transform and Euclidean distance graph [J]. Modern electronics technique， 2016， 39（21）： 61?64.

[9] MUKHOPADHYAY P， CHAUDHURI B B. A survey of Hough transform [J]. Pattern recognition， 2015， 48（3）： 993?1010.

[10] KWON B K， ZHU T， ROH T J. Fast ellipse detection based on three point algorithm with edge angle information [J]. International journal of control， automation and systems， 2016， 14（3）： 804?813.

[11] 宦海，黄凌霄，张雨，等.基于最大内切圆的椭圆孔组检测[J].计算机应用，2015，35（4）：1101?1105.

HUAN Hai， HUANG Lingxiao， ZHANG Yu， et al. Detection of ellipse hole group based on maximum inscribed circle [J]. Journal of computer applications， 2015， 35（4）： 1101?1105.