基于霍夫变换的圆形检测

霍夫变换的原理

Hough 变换就是利用图像全局特征将边缘像素连接起来组成区域封闭边界，它将图像空间转换到参数空间，在参数空间对点进行描述，达到检测图像边缘的目的。该方法把所有可能落在边缘上的点进行统计计算，根据对数据的统计结果确定属于边缘的程度。Hough 变换的实质就是对图像进行坐标变换，把平面坐标变换为参数坐标，使变换的结果更易识别和检测。
具体原理: 霍夫变换

对霍夫变换圆形检测的原理的理解:

已知圆的一般方程为:
$$(x-a)^2 + (y-b)^2 = r^2 $$
其中(a,b)代表圆心，r是圆的半径
依旧是把图像空间转换成参数空间，这里是将X-Y平面转化成a-b-r参数空间，则在图像空间中的一个过(x,y)点的圆，对应参数空间中高度变化的三维锥面。

同理，过图像空间的任意一点的圆都对应于参数空间的一个三维锥面，因此，过图像空间上同一圆的点，对应的参数空间中的三维锥面，在r平面必然相交于一点(a,b,r)，这样通过这一点就可以得到一个圆的参数。

这里霍夫变换的圆检测就是在这三个参数组成的三维空间内进行的
换一种理解思路:在笛卡尔坐标下的圆的方程已给出，在极坐标系下，假设圆心为$(x_0,y_0)$,圆上的点可以表示为:
$$x = x_0 + rcos\theta, y = y_0 + rsin\theta$$
对于一个圆，假如中心像素点$(x_0,y_0)$，半径r已知，那么旋转360°，圆上的所有点就可以求得。同样，假如圆上的所有点，半径r已知，旋转360°，则会得到一个累加的极值点，那么这个点就是圆心了。

理论上霍夫变换可以检测任何形状，但复杂的形状需要的参数就多，霍夫空间的维数就多，因此在程序实现上所需的内存空间以及运行效率上都不利于把标准霍夫变换应用于实际复杂图形的检测中。所以一些改进的霍夫变换就相继提出，它们的基本原理就是尽可能减小霍夫空间的维数。

在OpenCV中，HoughCircles函数实现了圆形检测，它使用的算法也是改进的霍夫变换——2-1霍夫变换（21HT）。也就是把霍夫变换分为两个阶段，从而减小了霍夫空间的维数。第一阶段用于检测圆心，第二阶段从圆心推导出圆半径。
检测圆心的原理是圆心是它所在圆周所有法线的交汇处，因此只要找到这个交点，即可确定圆心，该方法所用的霍夫空间与图像空间的性质相同，因此它仅仅是二维空间。检测圆半径的方法是从圆心到圆周上的任意一点的距离（即半径）是相同，只要确定一个阈值，只要相同距离的数量大于该阈值，我们就认为该距离就是该圆心所对应的圆半径，该方法只需要计算半径直方图，不使用霍夫空间。圆和半径知道了，圆自然就能求得。

21HT的具体步骤:
第一阶段：检测圆心

1.1、对输入图像边缘检测；

1.2、计算图形的梯度，并确定圆周线，其中圆周的梯度就是它的法线；

1.3、在二维霍夫空间内，绘出所有图形的梯度直线，某坐标点上累加和的值越大，说明在该点上直线相交的次数越多，也就是越有可能是圆心；

1.4、在霍夫空间的4邻域内进行非最大值抑制；

1.5、设定一个阈值，霍夫空间内累加和大于该阈值的点就对应于圆心。

第二阶段：检测圆半径

2.1、计算某一个圆心到所有圆周线的距离，这些距离中就有该圆心所对应的圆的半径的值，这些半径值当然是相等的，并且这些圆半径的数量要远远大于其他距离值相等的数量；

2.2、设定两个阈值，定义为最大半径和最小半径，保留距离在这两个半径之间的值，这意味着我们检测的圆不能太大，也不能太小；

2.3、对保留下来的距离进行排序；

2.4、找到距离相同的那些值，并计算相同值的数量；

2.5、设定一个阈值，只有相同值的数量大于该阈值，才认为该值是该圆心对应的圆半径；

2.6、对每一个圆心，完成上面的2.1～2.5步骤，得到所有的圆半径。

HoughCircles函数的原型为：
void HoughCircles (InputArray image,OutputArray circles, int method, double dp, double minDist,double param1=100, double param2=100, int minRadius=0,int maxRadius=0 )
image为输入图像，要求是灰度图像
circles为输出圆向量，每个向量包括三个浮点型的元素——圆心横坐标，圆心纵坐标和圆半径
method为使用霍夫变换圆检测的算法，Opencv2.4.9只实现了2-1霍夫变换，它的参数是CV_HOUGH_GRADIENT
dp为第一阶段所使用的霍夫空间的分辨率，dp=1时表示霍夫空间与输入图像空间的大小一致，dp=2时霍夫空间是输入图像空间的一半，以此类推
minDist为圆心之间的最小距离，如果检测到的两个圆心之间距离小于该值，则认为它们是同一个圆心
param1为边缘检测时使用Canny算子的高阈值
param2为步骤1.5和步骤2.5中所共有的阈值
minRadius和maxRadius为所检测到的圆半径的最小值和最大值

霍夫变换椭圆检测的实现

运行环境: vs2017 + Opencv3.4
由于HoughCircles函数是调用Canny函数进行边缘检测，OpenCV的Canny函数不包括平滑滤波，所以先对原图进行滤波处理，在这里使用的是高斯模糊

#include "opencv2/core/core.hpp"
#include "opencv2/highgui/highgui.hpp"
#include "opencv2/imgproc/imgproc.hpp"
#include <iostream>
using namespace cv;
using namespace std;

int main( int argc, char** argv )
{
     Mat src, gray;
    src=imread("coins.jpg");
    if( !src.data )  
        return -1;  

    cvtColor( src, gray, CV_BGR2GRAY );
    //高斯模糊平滑
    GaussianBlur( gray, gray, Size(9, 9), 2, 2 );

    vector<Vec3f> circles;
    //霍夫变换
    HoughCircles( gray, circles, CV_HOUGH_GRADIENT, 1, gray.rows/20, 100, 60, 0, 0 );

    //在原图中画出圆心和圆
    for( size_t i = 0; i < circles.size(); i++ )
    {
        //提取出圆心坐标
        Point center(cvRound(circles[i][0]), cvRound(circles[i][1]));
        //提取出圆半径
        int radius = cvRound(circles[i][2]);
        //圆心
        circle( src, center, 3, Scalar(0,255,0), -1, 8, 0 );
        //圆
        circle( src, center, radius, Scalar(0,0,255), 3, 8, 0 );
   }

    imshow( "霍夫变换检测圆图", src );

    waitKey(0);
    return 0;
}

结果: