霍夫变换

直线变换
霍夫变换(Hough)是一个非常重要的检测间断点边界形状的方法。它通过将图像坐标空间变换到参数空间，来实现直线与曲线的拟合。

1.直线检测
1.1 直线坐标参数空间
在图像x−y坐标空间中，经过点(xi,yi)的直线表示为：
yi=axi+b(1)
其中，参数a为斜率，b为截矩。
通过点(xi,yi)的直线有无数条，且对应于不同的a和b值。

如果将xi和yi视为常数，而将原本的参数a和b看作变量，则式子(1)可以表示为：

b=−xia+yi(2)
这样就变换到了参数平面a−b。这个变换就是直角坐标中对于(xi,yi)点的Hough变换。

该直线是图像坐标空间中的点(xi,yi)在参数空间的唯一方程。考虑到图像坐标空间中的另一袋奶(xj,yj)，它在参数空间中也有相应的一条直线，表示为：

b=−xja+yj(3)
这条直线与点(xi,yi)在参数空间的直线相交于一点(a0,b0)，如图所示：
这里写图片描述
图像坐标空间中过点(xi,yi)和点(xj,yj)的直线上的每一点在参数空间a−b上各自对应一条直线，这些直线都相交于点(a0,b0),而a0、b0就是图像坐标空间x−y中点(xi,yi)和点(xj,yj)所确定的直线的参数。
反之，在参数空间相交于同一点的所有直线，在图像坐标空间都有共线的点与之对应。根据这个特性，给定图像坐标空间的一些边缘点，就可以通过Hough变换确定连接这些点的直线方程。

具体计算时，可以将参数空间视为离散的。建立一个二维累加数组A(a,b),第一维的范围是图像坐标空间中直线斜率的可能范围，第二维的范围是图像坐标空间中直线截矩的可能范围。开始时A(a,b)初始化为0，然后对图像坐标空间的每一个前景点(xi,yi),将参数空间中每一个a的离散值代入式子(2)中，从而计算出对应的b值。每计算出一对(a,b),都将对应的数组元素A(a,b)加1，即A(a,b)=A(a,b)+1。所有的计算结束之后，在参数计算表决结果中找到A(a,b)的最大峰值，所对应的a0、b0就是源图像*线点数目最多(共A(a,b)个共线点)的直线方程的参数；接下来可以继续寻找次峰值和第3峰值和第4峰值等等，它们对应于原图*线点略少一些的直线。

上面这个图中，A 比B是直线的可能性大，因为A点经过的线条越多，说明该（k,b）下的直线
y= kx+b 上的点越多，点越多，则越可能表现为是一条直线。

圆变换

其实检测圆形和检测直线的原理差别不大，只不过直线是在二维空间，因为y=kx+b，只有k和b两个*度。而圆形的一般性方程表示为(x-a)²+(y-b)²=r²。那么就有三个*度圆心坐标a,b,和半径r。这就意味着需要更多的计算量，而OpenCV中提供的cvHoughCircle()函数里面可以设定半径r的取值范围，相当于有一个先验设定，在每一个r来说，在二维空间内寻找a和b就可以了，能够减少计算量。

具体步骤如下：

1.对输入图像进行边缘检测，获取边界点，即前景点。

2.假如图像中存在圆形，那么其轮廓必定属于前景点（此时请忽略边缘提取的准确性）。

3.同霍夫变换检测直线一样，将圆形的一般性方程换一种方式表示，进行坐标变换。由x-y坐标系转换到a-b坐标系。写成如下形式(a-x)²+(b-y)²=r²。那么x-y坐标系中圆形边界上的一点对应到a-b坐标系中即为一个圆。（这里就和直线检测是一个思路了）

4.那x-y坐标系中一个圆形边界上有很多个点，对应到a-b坐标系中就会有很多个圆。由于原图像中这些点都在同一个圆形上，那么转换后a,b必定也满足a-b坐标系下的所有圆形的方程式。直观表现为这许多点对应的圆都会相交于一个点，那么这个交点就可能是圆心(a, b)。

5.统计局部交点处圆的个数，取每一个局部最大值，就可以获得原图像中对应的圆形的圆心坐标(a,b)。一旦在某一个r下面检测到圆，那么r的值也就随之确定。

通过上面这个图，寻找交汇点最多的那个（a,b） 就是需要找的圆心。半径r，我们事先已经设置了一个阈值了，在这个阈值范围内的都可以被检测出来。

参考：
https://blog.csdn.net/yizhaoyanbo/article/details/59172991

https://blog.csdn.net/sudohello/article/details/51335237