Hough变换

最近在看图像处理的东西，为了检测直线，可以用的一个神奇的东西---Hough变换。

一条直线可以用如下的方程来表示：y=kx+b，k是直线的斜率，b是截距。

图像是一个个离散的像素点构成的，如果在图像中有一条直线，那也是一系列的离散点构成的。那么怎样检测这些离散的点构成了直线呢？

我们再看上面的直线方程：y=kx+b,(x,y)就是点。我们转换下变成：b=-kx+y。我们是不是也可以把（k，b）看作另外一个空间中的点？这就是k-b参数空间。

图1

我们看到，图1中，在x-y图像空间中的一个点，变成了k-b参数空间中的一条直线，而x-y图像空间中的2点连成的直线，变成了k-b参数空间中的一个交点。

如果x-y图像空间中有很多点在k-b空间中相交于一点，那么这个交点就是我们要检测的直线。这就是霍夫变换检测直线的基本原理。

当然，有一个问题需要注意，图像空间中如果一条直线是垂直的，那么斜率k是没有定义的（或者说无穷大）。为了避免这个问题，霍夫变换采用了另一个参数空间：距离-角度参数空间。

平面上的一个点也可以用距离-角度来定义，也就是极坐标：

图2

那么在图像中，每一个点都可以用距离和角度来表达： 但是，使用距离-角度后，点（x，y）与距离，角度的关系变成了：

ρ=xcosθ+ysinθ   （1）

x=ρcosθ，xcosθ=ρcosθ^2  （2）   y=ρsinθ,    ysinθ=ρsinθ^2     （3）

由（2）加（3）便可得到（1）

于是，在新的距离-角度参数空间中，图像中的一个点变成了一个正弦曲线（比如，当x=1，y=1时，ρ=xcosθ+ysinθ=cosθ+2sinθ=根号2*sin（θ+pi/4） ），而不是k-b参数空间中的直线了。这些正弦曲线的交点就是图像空间中我们要检测的直线了。

我们普通图片是的线条可以表示为 y=m0x+b0 ，在霍夫（参数）空间就是一个点

图3

相反，图片上的点在霍夫空间就可以表示为线，我们要检测线条的话，就可以把图像上的每个点转换到霍夫空间去，找到霍夫空间上线条相交的点，就可以确定参数m, b

但是我们知道如果是垂直线的话，它的斜率不存在，那又怎么办呢?

这样就有了另一种直线表达方法 ρ=xcosθ+ysinθ

无论采用xy坐标还是极坐标，原空间的点都对应参数空间的曲线，原空间的直线都对应着参数空间中曲线的交点。如下图所示，可以根据在参数空间中每个grid相交点的出现次数寻找原空间中的直线。

意思就是，属于同一条直线上点在极坐标空间(ρ,θ)必然在一个点上有最强的信号出现，根据此反算到平面坐标中就可以得到直线上各点的像素坐标，从而得到直线。

说了这么多原理，那么对于一张具体的图片，我们如何检测其中的直线呢？

首先对图像边缘检测，二值化（即灰度值为0（黑），灰度值为255（白）），这样我们的图像中就只看到了白色的物体边缘，其他的都是黑的，然后提取出这些灰度值为255（白色）的像素，对每个像素进行Hough变换。

一个像素点在参数空间对应一条正弦曲线（上面的理论说过），也有原图像中的一条直线在参数空间中对应一点（ρ，θ）。这也就是说，找到像素点对应正弦曲线的交点（ρ0，θ0），反变换回来便得到由像素点构成的直线（把ρ0，θ0带入 ρ=xcosθ+ysinθ中，就是ax+by-c=0，这是一条直线啊）。

就说这么多吧，以后有新的体会再补充。