我对霍夫变换（Hough transform）的理解
霍夫变换是图像处理识别领域用于识别几何形状的方法，这种方法和我前一段时间使用的机器学习方法有很大不同，它从几何图形的解析方程出发，通过一种类似于穷举的方法来寻找解析方程中决定形状的参数。
霍夫直线变换原理
霍夫直线变换是最常见的应用，用于寻找图像中的直线，它十分巧妙的把一个空间问题转换成了一个纯“数数字”的过程。
一般来说直线在直角坐标系下的方程是这样的：
其中m,c决定了直接斜率和截距，霍夫直线变换的目的就是通过一种转换，把这个m和c找出来。
稍微转换一下思路，在x轴和y轴组成的空间下：是一条直线，如果我们把方程稍加改写成如下形式：
坐标系换成m轴和y轴组成的指教坐标系，那么这条直接相当于空间中的(m, c)一个点。更进一步想，对于上的所有点，他们都满足这个方程下，我们从这条直线上去一个已知点(x, y)带入到：
此时(x,y)作为该直线的斜率和截距使用，这样我们就能得到一条新的直线，直线肯定能通过(m,c)点，我们继续取一个点(x2, y2)，继续做第二条直线，这第二条直线也一定通过(m,c)点...反复这样操作，我们会发现只要我们取的点位于：
上，那么在mc坐标系中的直线一定通过(m,c)点。理论上，一条直线上有无数个点，但实际图像上一条直线可能只有有限个像素点，假设一条直线长为一百个像素，那么一定有100条直线通过了同一个点，这个点在mc空间的坐标就是我们要辨别的直线。
以一个实际例子来更进一步说明，我们假设有一条直线的为：
随意取了四个点，如下图所示：
以这四个点的坐标为mc空间中直线的参数分别画出四条直线：
可以看到这四条直线都能够相交于同一点，这个点的坐标（-1, 2)就是我们要找的直线的截距和斜率。
在具体实现这个算法上，一般不会采用mc空间，因为m和c的取值范围无限，计算代价太大，而是将直线换成另外一种表达方式，其形式类似于极坐标系。
除了斜率和截距可以唯一确定一条直线外，如上图，从原点到直线的垂线的长度r以及这条垂线与x轴大于零方向的夹角可以唯一确定一条直线，即(ρ, θ）可以唯一确定一条直线,对于ρ和θ的关系，可以这样描述：
由于ρ不会大于垂线长度，θ也在（0， π）之间，所以整个ρθ空间的搜索范围有限，极大减少计算量。
只要x,y在我们要找的直线上，那么它一定是满足：
同样的，我们取一个直线上的点(x1, y1)，带入上式中，让θ从0变动到π，得到对应的ρ，这样的图像是一条曲线，由于这个点在我们要找的直线上，所以它是一定通过唯一确定一条直线的点(ρ, θ)的，重复这一步骤会得到相交于同一点的很多曲线。
仍然用上面的例子：
还是
它对应的(ρ, θ)=(sqrt(2),0.25π)，取的四个点坐标依次为：
1:(1,-1),2:(2,0),3:(3,-1),4:(4,-2)
把他们带入到中，得到下面四个关系：
把它们在(ρ, θ)空间中表示出来：
的确，这些曲线都相交于同一个点，这个点的坐标就是我们要找的直线(sqrt(2),0.25π)
霍夫直线变换实现思路：
在
形式下的直线，可以用一个(ρ, θ)空间来存储所有的可能的直线参数取值， 在程序语言中就是一个二维的表，其中ρ作为行，θ为列，对于一张图片，这张图片中可能的直线最大长度不超过这张图的对角线长度，θ在[0,π]之间，所以这张表格的维度就是对角线长度*θ列数，θ列数越多，表明角度划分越小，就角度的估计约精确。在初始化这种表格后，可以采取如下步骤：
- 二值化图像
- 初始化(ρ, θ)表，所有值为0
- 选取一个点(x,y)，带入
中，对所有θ列计算，得到一系列(ρ, θ)，把二维表中对应位置加1
- 遍历所有像素，执行2中操作
- 确定一个阈值T，对表中的每个元素，如果大于T就说明这个元素对于的行号和列号（即ρ和θ的值）是一条直线
- 根据ρ, θ值，输出结果
以上就是一个完整的霍夫直线变换检测流程，一张图片中也许有很多直线，对于一张100*100的图片，如果有长100，80,20像素的直线，那么二维表中的一定会有数值为100， 80， 20的元素存在，如果我们设置的阈值小于20，那么所有的直线都会检测出来。