Hough变换理解

reference:
http://blog.csdn.net/app_12062011/article/details/11307053

一、简单介绍

Hough变换是图像处理中从图像识别几何形状的基本方法之一，霍夫变换寻找直线和圆的方法相比其他方法，可以更好的减少噪声干扰。经典的霍夫变换常用来检测直线，圆，椭圆等。

Hough变换的基本原理在于利用点与线的对偶性，将原始图像空间的给定曲线通过曲线表达形式变为参数空间的一个点。这样就把原始图像给定曲线的检测问题，转化为检测参数空间的峰值问题。也就是把检测整体特性转化为检测局部特性。比如直线，椭圆，圆，弧线等。

二、Hough变换的基本思想

基本问题： 设已知一黑白图像上画了一条直线，要求出这条直线所在的位置。

问题分析： 我们知道，直线的方程可以用y=k*x+b 来表示，其中k和b是参数，分别是斜率和截距。也就是说，我们将原始图像需要检测的直线，表示成y = k*x + b, 只要找出唯一的k，b即可检测出该直线。

求解： 该直线在原始图中是一系列离散点的集合，假设直线上一点（x0, y0）, 过该直线上某一点(x0,y0)的所有直线的参数都会满足方程y0=kx0+b。即点(x0,y0)确定了一族直线。 方程y0=kx0+b在参数k–b平面上是一条直线，(即方程b=-x0*k+y0对应的直线)。即点（x0,y0）在参数空间确定了一条直线。这样，图像x–y平面上的一个前景像素点就对应到参数平面上的一条直线。因此，图像x-y内需检测直线上的N个点，在参数平面会有N条直线。而图像x-y内的直线有唯一一个k，b，因此，相应的参数平面N条直线必然有唯一一个交点。

我们举个例子说明解决前面那个问题的原理。设图像上的直线是y=x, 我们先取上面的三个点：A(0, 0), B(1, 1), C(2, 2)。可以求出，过A点的直线的参数要满足方程b=0, 过B点的直线的参数要满足方程1=k+b, 过C点的直线的参数要满足方程2=2k+b, 这三个方程就对应着参数平面上的三条直线，而这三条直线会相交于一点(k=1,b=0)。　同理，原图像上直线y=x上的其它点(如(3,3),(4,4)等)　对应参数平面上的直线也会通过点(k=1,b=0)。

这个性质就为我们解决问题提供了方法，就是把图像平面上的点对应到参数平面上的线，最后通过统计特性来解决问题。假如图像平面上有两条直线，那么最终在参数平面上就会看到两个峰值点，依此类推。

简而言之，Hough变换思想为：在原始图像坐标系下的一个点对应了参数坐标系中的一条直线，同样参数坐标系的一条直线对应了原始坐标系下的一个点，然后，原始坐标系下呈现直线的所有点，它们的斜率和截距是相同的，所以它们在参数坐标系下对应于同一个点。这样在将原始坐标系下的各个点投影到参数坐标系下之后，看参数坐标系下有没有聚集点，这样的聚集点就对应了原始坐标系下的直线。

在实际应用中，y=k*x+b形式的直线方程没有办法表示x=c形式的直线(这时候，直线的斜率为无穷大)。所以实际应用中，利用极坐标的方式，将直线方程表示成：ρ=x*cos(ξ)+y*sin(ξ)。其中ρ表示直角坐标系中原点到直线的距离，ξ表示x轴与直线法线的夹角，取逆时针方向。这样，图像平面上的一个点就对应到ρξ平面上的一条曲线上，其它的还是一样。

在实现的图像处理领域，图像的像素坐标P(x, y)是已知的，而ρ,ξ 则是我们要寻找的变量。如果我们能根据像素点坐标P(x, y)值绘制每个(ρ,ξ)值的话，那么就从图像笛卡尔坐标系统转换到极坐标霍夫空间系统，这种从点到曲线的变换称为直线的霍夫变换。变换通过量化霍夫参数空间为有限个值间隔等分或者累加格子。当霍夫变换算法开始，每个像素坐标点P(x, y)被转换到(r, theta)的曲线点上面，累加到对应的格子数据点，当一个波峰出现时候，说明有直线存在。同样的原理，我们可以用来检测圆，只是对于圆的参数方程变为如下等式：
(x –a ) ^2 + (y-b) ^ 2 = r^2其中(a, b)为圆的中心点坐标，r圆的半径。这样霍夫的参数空间就变成一个三维参数空间。给定圆半径转为二维霍夫参数空间，变换相对简单，也比较常用。

三、Hough变换推广

1、已知半径的圆
其实Hough变换可以检测任意的已知表达形式的曲线，关键是看其参数空间的选择，参数空间的选择可以根据它的表达形式而定。比如圆的表达形式为，所以当检测某一半径的圆的时候，可以选择与原图像空间同样的空间作为参数空间。那么圆图像空间中的一个圆对应了参数空间中的一个点，参数空间中的一个点对应了图像空间中的一个圆，圆图像空间中在同一个圆上的点，它们的参数相同即a，b相同，那么它们在参数空间中的对应的圆就会过同一个点（a，b），所以，将原图像空间中的所有点变换到参数空间后，根据参数空间中点的聚集程度就可以判断出图像空间中有没有近似于圆的图形。如果有的话，这个参数就是圆的参数。
2、未知半径的圆
对于圆的半径未知的情况下，可以看作是有三个参数的圆的检测，中心和半径。这个时候原理仍然相同，只是参数空间的维数升高，计算量增大。图像空间中的任意一个点都对应了参数空间中的一簇圆曲线。，其实是一个圆锥型。参数空间中的任意一个点对应了图像空间中的一个圆。
3、椭圆
椭圆有5个自由参数，所以它的参数空间是5维的，因此他的计算量非常大，所以提出了许多的改进算法。

四、总结

图像空间中的在同一个圆，直线，椭圆上的点，每一个点都对应了参数空间中的一个图形，在图像空间中这些点都满足它们的方程这一个条件，所以这些点，每个投影后得到的图像都会经过这个参数空间中的点。也就是在参数空间中它们会相交于一点。所以，当参数空间中的这个相交点的越大的话，那么说明元图像空间中满足这个参数的图形越饱满。越象我们要检测的东西。
Hough变换能够查找任意的曲线，只要你给定它的方程。Hough变换在检验已知形状的目标方面具有受曲线间断影响小和不受图形旋转的影响的优点，即使目标有稍许缺损或污染也能被正确识别。