利用长轴检测椭圆

姜春涛

利用长轴检测椭圆

姜春涛

(四川大学 计算机学院，四川 成都 610000)

利用霍夫变换进行椭圆检测，需要寻找椭圆的参数。使用椭圆主半轴的长度，可以快速地寻找椭圆的参数。这种方法需要将椭圆的短半轴长度求解出来，然后仅使用一维的聚集数组收集椭圆短半轴的长度信息。该方法不需要计算椭圆的边的切线或者曲率，因此不易受到噪声的影响。该方法的实现不需要大量的内存。合成的图像和真实的图像测试表明，这种方法是有效的。

图像处理；霍夫变换；椭圆检测

0 引言

椭圆检测是图像处理中的一个重要的问题，已经有很多种椭圆检测的方法[1-10]。完全定义一个椭圆需要五个参数，因此变化霍夫变换[11]进行椭圆检测需要五维的参数空间。这需要很大的内存和时间，所以需要使用几何上的限制以减少参数空间。为了减少椭圆检测中时间和空间的需求，以前的技术大部分将 5 维的参数空间分为更少维数的子空间。参考文献[1]介绍了一种基于几何属性的椭圆检测方法。 参考文献[2]通过在相同的水平和垂直位置上的边缘点构造两个中间点矩阵，然后，利用霍夫变换从这两个矩阵中检测出直线[12-13]，这些直线的交提供了可能的椭圆中心。 文献[3]提出了一种包含切线信息的用于椭圆提取的映射方法。文献[4]提出了一种有效的从图像的边中检测椭圆的方法，其思路是在霍夫变换基础上从边缘中检测对称轴，一个高维的问题转化成两个二维的问题。先从边缘中找到对称轴，然后从边缘中找到椭圆。文献[4]介绍了一种利用椭圆长轴进行椭圆检测的方法。利用短半轴的长度获取在同一椭圆上的点，然后椭圆的参数被计算出来。

本文的椭圆检测方法基于文献[9]介绍的方法。这种方法使用新的方式计算椭圆的短半轴，需要的运算量稍微少一些。对于给定的椭圆长轴的两个端点，文中提供了一种用于减少计算短半轴长度的点数的方法。

1 椭圆参数的寻找

一个椭圆具有五个参数，它们分别是椭圆的中心坐标O(x0,y0)、椭圆的长半轴a、椭圆的短半轴b、椭圆的长轴与x轴的夹角T。椭圆的五个参数如图1所示。

图2是与图1相对应的椭圆，它是将原椭圆的中心平移到坐标原点，然后顺时针旋转角度T后得到的。对应于图2的椭圆方程是:

(1)

从式(1)中，可以得到：

图1 椭圆及其参数

图2 变换后的椭圆

其中a2-x2>0。

(2)

从图1到图2的线性变换，先是将椭圆的中心平移到坐标原点，其对应的变换矩阵为P，然后将椭圆顺时针旋转角度T，其对应的变换矩阵为R。整个变换的复合矩阵为A[14-15]。变换矩阵P，T，R如下：

(3)

(4)

(5)

假设点B(x,y)是位于图1椭圆上的一点，而点C(xt,yt)是位于图2椭圆上由点B经过线性变换A后的对应点,则C的坐标为:

(6)

将式(6)代入式(2)中，得到

(7)

位于图2椭圆上的点需要满足式(8)、(9)两个条件:

(8)

(9)

从式(8)和(9)中可以得到

(10)

(11)

使用霍夫变换检测椭圆的基本算法[9]为：首先查找图像中的边缘点，找到距离满足给定条件的两点，这两点被看成是椭圆主轴上的两个端点，然后对图像边缘上的每一个点根据式(6)将其转化到图2所对应的坐标系中，若得到的点的坐标满足条件(10)和(11)，则由式(2)计算出椭圆的短半轴的长度，最后根据短半轴长度将短半轴聚集矩阵中对应项的值加1。如果最终聚集矩阵中的某一项的值大于给定的阈值，则该项对应的边缘像素点在同一椭圆上。假设椭圆的主轴上的两个端点分别为(x1,y1)和(x2,y2)，则椭圆的中心O(x0,y0)、长半轴a及椭圆长轴与x轴的夹角T如下:

(12)

(13)

(14)

cosT=

(15)

(16)

2 减少用于计算短半轴长度的点数

图3 椭圆边界示意图

在前面介绍的椭圆检测算法中，需要将边缘像素点转化到图2所示的坐标系后才能判断该点是否在某一个椭圆上，然后计算该椭圆的短半轴的长度。明显不在椭圆上的点不必要进行转化，这样可以减少计算量。在椭圆边界盒子外的点明显不在椭圆上，不必转化而将其排出。使用与坐标轴平行的边界盒子，如图3所示，图中最大的长方形即为边界盒子。设椭圆边界盒子的宽为W， 高为H。边界盒子的宽和高的计算式如下：

H=2a|cosT|+2bsinT

(17)

W=2asinT+2b|cosT|

(18)

上式中，b为椭圆的短半轴的最大长度，其最大值为a。椭圆的中心为O(x0,y0)，若点的坐标满足条件

(19)

和

(20)

则将其转化到图2所示的坐标系后求解短半轴的长度。

3 椭圆检测的步骤

算法的输入是从图像中取得的边缘像素点的列表L，输出是找到的椭圆的中心O(x0,y0)，长半轴a，短半轴b，长轴与x轴的夹角T以及椭圆的边上的点。

根据前面对椭圆检测算法的描述，椭圆检测的步骤如下：

(1)在L中寻找距离在给定范围内的两点A,B，如果存在这样的两点，则跳到第(2)步，否则结束。

(2)将A,B作为椭圆长轴的两个端点，按照式(12)、(13)、(14)、(15)、(16)计算出椭圆的中心O(x0,y0)、长半轴a、椭圆长轴与x轴的夹角T。

(3)按照式(17)、(18)分别计算出椭圆边界盒子的高H和宽W。

(4)将短半轴聚集累加器中的每一项清零。

(5)对于L中的每一个点，如果点的坐标满足式(19)、(20)，则将其坐标由式(6)转化到图2所对应的坐标系中，然后判断得到的坐标是否满足式(10)和(11)，如果满足，则按照式(2)计算出短半轴的长度及聚集累加器中的对应项加1。

(6)在短半轴聚集累加器中查找值大于给定阈值的项，输出该项对应的椭圆的长半轴长度a、短半轴长度b、中心坐标(x0,y0)、长轴与x轴的夹角T以及该椭圆对应的边上的点。将该椭圆边上的点从L中删除。跳到第(1)步。

4 合成图像和真实图像测试结果

使用合成的图像作为测试数据，先使用Sobel算子计算出图像的梯度，然后使用简单阈值算法找到图像的边缘像素点列表。使用从图像中获取的边缘像素点列表，根据前面的椭圆检测步骤检测图像中的椭圆。测试使用的图像以及检测到的椭圆和椭圆边缘点如图4所示。测试用的图像大小为640×480。检测到的图像中的椭圆的参数如表1所示。按照测试图像中椭圆从左到右，从上到下，同心椭圆 (圆) 从小到大的顺序，椭圆的数据在表中以这个顺序列出。表中的 “数据无效” 表示检测对象是圆，其长轴与x轴的夹角无意义；夹角T的单位为弧度。

图4 合成图像中的椭圆检测

从检测结果来看，测试图像中的椭圆 (圆) 被全部检测到，得到的椭圆 (圆) 的参数比较准确。从图4中检测到的椭圆图像看，在长轴端点附近的点没有被检测到，这是由于当边缘点靠近长轴端点时，由式(2)求得的椭圆的短半轴的长度误差大。

表1 椭圆检测数据

使用真实的图像进行测试。先对测试图使用高斯低通虑波器除噪声，然后使用Sobel算子求图像的梯度，接着使用简单阈值算法得到图像的边缘，再进行痩边处理[8，16]，得到图像的边缘像素点列表，最后根据前面的椭圆检测步骤检测图像中的椭圆。测试图像的大小为 640×480。测试结果如图5所示，从测试结果看，图中的椭圆被全部检测出。椭圆检测算法所找到的椭圆 (圆) 的边缘点在图中使用实线标示出。

图5 真实图像中的椭圆检测

5 结论

本文介绍的椭圆检测算法使用一维的聚集累加器，需要的内存少，受噪声的影响小，算法对椭圆的检测比较准确。椭圆检测算法需要椭圆长轴上的两个端点，如果椭圆长轴上的两个端点不存在，则椭圆不会被检测到。算法需要先找椭圆长轴上的两个端点，然后令一个点在以这两个端点为长轴的椭圆上，计算出这个椭圆的短半轴的长度，图像的边缘点很多，算法的运算量很大。通过Sobel算子求解图像中的边缘点方向[8]，根据边缘点的方向将边缘点分成两部分，方向相对的各为一部分，然后分别在这两部分中查找椭圆的长轴端点，以减少可能的椭圆长轴的端点数目。由于图像中的边存在大量的直线，如果一个边缘点不是可能的椭圆长轴端点，则其附近的点为椭圆的长轴上的端点的可能性比较小。如果一个点被作为椭圆的长轴上的点被检测，则它附近的点可以不再作为长轴的端点进行检测，利用Sobel算子求解出的边缘点的方向信息，将图像中临近的边缘点中方向很相近的点只保留一个进行可能的长轴端点检测，因为如果边缘点的方向相同，则认为在同一直线上，不大可能成为椭圆的边，这种方法能减少大量的运算量，但是误差较大。

[1] YIN P Y, CHEN L H. New method for ellipse detection by means for symmetry[J]. Journal of Electronic Imaging, 1994, 3(1): 20-29.

[2] HO C, CHEN L. A fast ellipse/circle detector using geometric symmetry[J]. Pattern Recognition, 1995, 28(1): 117-124.

[3] AGUADO A S, MONTIEL M E, NIXON M S. On using directional information for parameter space decomposition in ellipse detection[J]. Pattern Recognition, 1996, 29(3): 369-381.

[4] LEI Y, WONG C. Ellipse detection based on symmetry[J]. Pattern Recognition, 1999, 20: 41-47.

[5] DAVIES E R. Finding ellipses using the generalized Hough Transform[J]. Pattern Recognition, 1989,9(2): 87-96.

[6] TSUJI S, MATSUMOTO F. Detection of ellipses by modified Hough Transform[J]. IEEE Transaction On Computers, 1978, 27(8): 777-781.

[7] YIP R K K, TAM P K S, LEUNG D N K. Modification of Hough Transform for circles and ellipses detection using a 2-dimensional array[J]. Pattern Recognition, 1992, 25(9): 1007-1022.

[8] DAVIES E R. Computer & Machine Vision[M]. 北京：机械工业出版社, 2013.

[9] Xie Yonghong, Ji Qiang. A new efficient ellipse detection method[C]. 16th International Conference Pattern Recgnition, Proceedings. Quebec, Canada, 2002， IEEE, 2002: 957-960.

[10] Ji Qiang, HARALICK R M. A statistically efficient method for ellipse detection[C]. Proceedings of 1999 International Conference on Image Processing USA: IEEE Computer Society Press, 1999:730-734.

[11] BALLARD D H. Generalizing the Hough transform to detect arbitrary shapes[J]. Pattern Recognition, 1981, 13(2): 111-122.

[12] HART P E. How the Hough Transform was invented[C]. IEEE Signal Processing, 2009: 18-22.

[13] DUDA R O, HART P E. Use of the Hough Transform to detect lines and curves in pictures[J]. Communications of the ACM, 1972, 15(1): 11-15.

[14] HEARN D, BAKER M P. Computer graphics with OpenGL[M]. 北京：电子工业出版社, 2006.

[15] LAY D C. Linear algebra and its applications[M]. 北京：电子工业出版社, 2010.

[16] GONZALEZ R C, WOODS R E. Digital image processing[M]. 北京：电子工业出版社, 2007.

Ellipse detection by major axis

Jiang Chuntao

(School of Computer Science, University of Sichuan, Chengdu 610000, China )

Using Hough transform to detect ellipses, the parameters of the ellipses need to be found. The parameters of the ellipses can be found by the major axes. The half-lengths of the minor axes need to be first computed, then one one-dimensional accumulator array is used to gather the information of the half-lengths. Because this method does not calculate the tangents or curvatures of the edge contours of the ellipses, it is not sensitive to noise. The implementation does not need much storage. By synthetic and real images, the method is proved effectively.

image processing; Hough transform; ellipse detection

TP751

A

10.19358/j.issn.1674- 7720.2017.04.013

姜春涛.利用长轴检测椭圆[J].微型机与应用，2017,36(4)：43-46.

2016-09-16)

姜春涛(1985-)，男，硕士研究生，主要研究方向：图形图像处理。