查找图像中椭圆轮廓的快速随机hough变换

　　图像中椭圆轮廓的查找在视频监控等领域有着广泛的应用，经典hough变换给我们提供了一种查找各种图形轮廓的方法，特别是在直线查找方面具有非常高的精确度。但是由于经典hough变换的基本原理是将图像空间转换到参数空间，所以对于椭圆这种参数较多的图形轮廓来说计算量较大，实时性有所降低。

　　随机hough变换是经典hough变换的一个变型，这种算法在查找直线、圆以及椭圆等方法都具有较高的鲁棒性。从Range的角度来看，随机hough变换的本质就是一种基于可更新模板的模板匹配方法。下图是一张Range基于这种方法检测行人头部的效果。

　　

　　下面对随机hough进行一个简单的介绍：

　　

　　随机hough变换是经典hough变换的盖然论变型。被广泛应用到圆弧等图形（线、圆、椭圆等）的检测中。Hough变换的基本思想是对图像上的潜在圆弧采用一种投票机制，最后算法通过检查最高的投票分数来确定具有最高分圆弧的存在。随机hough变换和经典hough的不同在于通过分析几何性质避免把时间浪费在给每个非零像素投票的过程上。因此，有效地改进了处理时间并且减少了所需要的存储空间。

产生背景

虽然hough变换被广泛应用到图形检测上，但它主要有两点不足：(1) 对于图像上的每个非零像素，不管是不是要查找的形状的参数都会在投票过程中被累加；(2) 累加器数组（或者hough空间）以一种启发方式定义。要想计算的精度越好，就需要定义越高的参数空间。这两点往往使得系统需要较大的存储开销，而且影响系统的实时性。

实现

圆弧可以完全由它上面的一定数量的点来决定，和HT比起来，RHT正是利用了这个优势。例如，两点决定一条直线，一个椭圆或圆可由三点确定。为了阐述RHT的思想，我们可以想象下一个椭圆的确定过程：1) 由随机选择的点进行椭圆拟合；2) 更新累加器数组以及相应的匹配度；3) 输出那些大于预定义阈值的椭圆。

椭圆拟合

定义椭圆的一般公式为：a(x − p)² + 2b(x − p)(y − q) + c(y − q)² + 1 = 0，约束条件：ac − b² > 0。

但是要确定一个椭圆我们仅需要三个点。

RHT由在椭圆上随机选择三个点开始，设为X₁,X₂和X₃。第一步是找到这三个点处的切线，可以通过对其相邻像素的一个小窗口进行最小二乘拟合一条直线来找到该点处的切线；

第二步是要找出这些切线的交叉点，这点很容易做到。设交叉点为T12和T23，设两条线段X₁X₂以及X₂X₃的中点分别是M₁₂和M₂₃。然后椭圆的中心就是T₁₂M₁₂和T₂₃M₂₃的交点。

假设上步求出的椭圆中心坐标为(X₀,Y₀)，设x’=x-x₀，y’=y-y₀，那么椭圆方程为：

ax'² + 2bx'y' + cy'² = 1。现在，我们可以通过带入X₁,X₂和X₃的坐标来解方程求出参数a、b和c。

累加

椭圆参数被计算出来后，累加器数组就可以相应的更新了。和经典的hough变换不同，RHT没有维护一个"grid of buckets"作为累加器数组。它首先计算新检测到得椭圆和已保存在累加器数组中的椭圆的相似度。可以采用不同计算标准来计算相似度。一旦相似度超出了预定义的门限值，就用这两个椭圆的平均来替换掉累加器数组中的椭圆，同时将它的score加1。.

终止

一旦某个候选椭圆的score超过了门限值，这个椭圆就是一个被检测出的椭圆。将其从图像和累加器数组中删除，以便该算法更快的找到其他椭圆。当算法循环数目达到最大值或者所有椭圆都被检测出时，算法停止。

伪代码

while (we find ellipses OR not reached the maximum epoch) {

    for(a fixed number of iterations) {

        Find a potential ellipse.

        if(the ellipse is similar to an ellipse in the accumulator)

            Replace the one in the accumulator with the average of two ellipses and add 1 to the score;

        else

            Insert the ellipse into an empty position in the accumulator with a score of 1;

    }

    Select the ellipse with the best score and save it in a best ellipse table;

    Elliminate the pixels of the best ellipse from the image;

    Empty the accumulator;

}

　　随机hough和经典的hough有些不同，如果你不了解经典hough可以参考下《hough变换原理》一文，这里不再赘述。

相关参考

1.http://blog.csdn.net/icerain_3321/article/details/1665280

2. D.H. Ballard, "Generalizing the Hough Transform to Detect Arbitrary Shapes", Pattern Recognition, Vol.13, No.2, p.111-122, 1981

3. L. Xu, E. Oja, and P. Kultanan, "A new curve detection method: Randomized Hough transform (RHT)", Pattern Recog. Lett. 11, 1990, 331-338.

4. S. Inverso, “Ellipse Detection Using Randomized Hough Transform”, www.saminverso.com/res/vision/EllipseDetectionOld.pdf, May 20, 2002