主要内容：
- 霍夫变换的作用
- 霍夫变换检测直线的原理
- 霍夫变换检测圆的原理
- OpenCV中的霍夫变换
1、霍夫变换检测直线原理
霍夫变换，英文名称Hough Transform，作用是用来检测图像中的直线或者圆等几何图形的。
一条直线的表示方法有好多种，最常见的是 y=mx+b 的形式。 假设有一幅图像，经过滤波，边缘检测等操作，变成了下面这张图的形状，怎么把这张图片中的直线提取出来。基本的思考流程是：如果直线 y=mx+b 在图片中，那么图片中，必需有N多点在直线上（像素点代入表达式成立），只要有这条直线上的两个点，就能确定这条直线。该问题可以转换为：求解所有的(m,b)组合。
设置两个坐标系，左边的坐标系表示的是(x,y)值，右边的坐标系表达的是(m,b)的值，即直线的参数值。那么一个(x,y)点在右边对应的就是是一条线，左边坐标系的一条直线就是右边坐标系中的一个点。这样，右边左边系中的交点表示有多个点经过(m,b)确定的直线。但是，该方法存在一个问题(m,b)的取值范围太大。
为了解决(m,n)取值范围过大的问题，在直线的表示方面用 xcosθ+ysinθ=p 的规范式代替一般表达式，参数空间变成(θ,p)，0=<θ<=2PI。这样图像空间中的一个像素点在参数空间中就是一条曲线（三角函数曲线）。
Hough Line算法表述如下：
1、初始化(θ,p)空间，N(θ,p)=0 （N（θ,p）表示在该参数表示的直线上的像素点的个数）
2、对于每一个像素点(x,y)，在参数空间中找出令 xcosθ+ysinθ=p 的（θ,p）坐标，N（θ,p）+=1
3、统计所有N（θ,p）的大小，取出N（θ,p）>threasold的参数 （threadsold是预设的阈值）
2、OpenCV中的HoughLines
OpenCV检测直线的方法名称为HoughLines，方法包含在 imgproc/imgproc.hpp 头文件中，方法的具体参数介绍如下
void HoughLines(InputArray image, OutputArray lines, double rho, double theta, int threshold, double srn=, double stn=
image:输入图像
lines：检测到的直线（表示其实为直线参数(θ,p)集合）
rho：像素每次迭代的大小（即每一次选取像素的过程跳跃多少，一般设置为1）
theta：角度累加器的大小（即选取的直线参数θ的变化），一般为CV_PI/180
thresold：阈值大小（即每个参数对至少经过的像素点数）
下面这段代码具体实现了读取图片，提取直线，并且把直线显示出来的功能，一般情况下，我们在提取直线之前会对原始图像做一次Canny边缘检测。
#include <iostream> #include "opencv2/highgui/highgui.hpp"
#include "opencv2/imgproc/imgproc.hpp" using namespace std;
using namespace cv; int main(){ //读取图片，转换成灰度图像，并且对其执行一次高斯滤波，去除噪声点
Mat img=imread("img//yifulou.jpg");
Mat result;
cvtColor(img,result,CV_RGB2GRAY);
GaussianBlur(result,result,Size(,),);
imshow("逸夫楼",result); //Cany边缘提取
Canny(result,result,,,); //利用Hough计算直线
vector<Vec2f> lines;
HoughLines(result,lines,,CV_PI/,);
cvtColor(result,result,CV_GRAY2RGB); //为了展示需要，把灰度图像转换成RGB格式
for(size_t i=;i<lines.size();i++){
float rho = lines[i][], theta = lines[i][];
Point pt1, pt2;
double a = cos(theta), b = sin(theta);
double x0 = a*rho, y0 = b*rho;
pt1.x = cvRound(x0 + *(-b));
pt1.y = cvRound(y0 + *(a));
pt2.x = cvRound(x0 - *(-b));
pt2.y = cvRound(y0 - *(a));
line( result, pt1, pt2, Scalar(,,), , CV_AA);
}
cout<<"检测到直线"<<lines.size()<<endl;
imshow("Hough Line",result); cv::waitKey();
}
结果如下：（左边为经过滤波的图像，右边为检测的结果图像）
3、霍夫变换检测圆的原理
霍夫变换检测圆形的原理跟检测直线的原理是一样的。圆的表达式为 (x-a)2+(y-b)2=r2 ， 把问题转换成在求解经过像素点最多的 (a,b,r) 参数对。这里分析一下图像中的一个像素点，对应参数空间的图形。如果r确定，那么一个像素点对应参数空间的一个圆，那么r不确定，则对于每一个r都是一个圆，这个图形是一个三维的圆台。如下图。
这里会发现(a,b,r)的参数空间特别大，计算量特别大。如果像素点，知道其所属的圆形的半径和指向圆心的角度，a,b其实是可以计算出来的。那么如下面这个课件上写的那样，参数空间变成了二维的，计算量大大降低。
看课件上的左上角的图形，如果一个圆上的点，都沿着其梯度方向画线，那么所有线的角点就是圆心。OpenCV中的霍夫梯度算法就利用这个原理，先计算可能的圆心，然后再去计算可能的半径。OK，现在的问题是这个梯度值怎么得到，第一我们检测的圆肯定是边界，那么用Soebl算子去计算局部一位导数，肯定值是比较大的，这样可以用Sobel计算出来的梯度值去近似角度。因此。霍夫梯度检测圆形的算法如下（下面的算法描述来源于 http://blog.csdn.net/hhyh612/article/details/54947205）：
I、估计圆心
1、把原图做一次Canny边缘检测，得到边缘检测的二值图
2、对原始图像执行一次Sobel算子，计算出所有像素的邻域梯度值
3、初始化圆心空间N(a,b)，令所有的N(a,b)=0
4、遍历Canny边缘二值图中的所有非零像素点，沿着梯度方向画线，将线段经过的所有累加器中的点(a,b)的N(a,b)+=1
5、统计排序N(a,b)，得到可能的圆心
II、估计半径（针对某一个圆心a,b）
1、计算Canny图中所有非0点距离圆心的距离
2、距离从小到大排序，根据阈值，选取合适的可能半径（比如3和3.5都被划为半径值3中）
3、初始化半径空间r,N(r)=0
4、遍历Canny图中的非0点，对于点所满足的半径r，N(r)+=1
5、统计得到可能的半径值
利用霍夫变换检测其他图形的原理也是这样。找出表达式以及参数空间，遍历图像，找出参数空间中符合要求的参数。最近，看到一个利用最小二乘去寻找圆的算法，那个算法的大致思路是列出圆形的表达式，然后通过最小二乘去求迭代求解参数值。这个方案认为更适合解决，利用图像中的点尽可能去拟合一个圆或者几个圆，不适合检测图像中有多少个圆，而且最小二乘的计算量感人。
4、OpenCV中的HoughCircles
OpenCV中的HoughCircles方法实现了检测圆形的功能。方法包含在 imgproc/imgproc.hpp 头文件中，具体方法如下
void HoughCircles(InputArray image, OutputArray circles, int method, double dp, double minDist, double param1=, double param2=, int minRadius=, int maxRadius= )
image：输入图像
circles：检测的圆形，（a,b,r）的参数集合
method：检测使用的方法，目前OpenCV只提供了CV_HOUGH_GRADIENT方法，即霍夫梯度法
dp：图像像素分辨率与参数空间分辨率的比值（官方文档上写的是图像分辨率与累加器分辨率的比值，它把参数空间认为是一个累加器，毕竟里面存储的都是经过的像素点的数量），dp=1，则参数空间与图像像素空间（分辨率）一样大，dp=2，参数空间的分辨率只有像素空间的一半大
minDist：两个圆心之间的最小距离。这个距离设置过小，会导致本来属于一个圆上的点被分散成几个小圆，过大则导致部分小圆检测不出来
param1：CV_HOUGH_GRADIENT过程中执行Canny边缘检测的阈值
param2：参数空间阈值（即至少多少点经过该参数表示的圆）
minRadius：半径最小值
maxRadius：半径最大值
下面，这段代码实现的是在图像中检测圆形。
#include <iostream> #include "opencv2/highgui/highgui.hpp"
#include "opencv2/imgproc/imgproc.hpp" using namespace std;
using namespace cv; int main(){ //读取图片
Mat img=imread("img/xiaohui.jpg");
imshow("校徽",img); //执行一次高斯过滤与灰度变换
Mat copy;
cvtColor(img,copy,CV_RGB2GRAY);
GaussianBlur(copy,copy,Size(,),); //提取圆
vector<Vec3f> circles;
HoughCircles(copy,circles,CV_HOUGH_GRADIENT,,,,,,);
for(size_t i=;i<circles.size();i++){
Vec3i c=circles[i]; //这里用Vec3i的原因是像素点必须为int类型
circle(img,Point(c[],c[]),c[],Scalar(,,),,CV_AA);//绘制圆弧
circle(img,Point(c[],c[]),,Scalar(,,),,CV_AA);//绘制圆心
} imshow("circle",img); cv::waitKey();
}
代码执行的效果如下，左边为原图，右图是检测之后的图形。
5、其他参考资料
- [OpenCV入门教程之十四]OpenCV霍夫变换：霍夫线变换、霍夫圆变换合辑 浅墨、毛星云大神的文章，对于OpenCV中的HoughLins和HoughCircles方法的源码进行了简单的分析。
- OpenCV霍夫变换找圆算法 对于霍夫梯度法进行了比较详细的介绍，深入浅出。