霍夫变换实际上有2个关键点：

 1. 通过转换矩阵把欧式空间转换成参数空间

 2. 对参数空间中的点进行投票

下面先看直线的例子，在上面的参考中已经详细讨论过直线，圆，椭圆等形状的例子：

因为直线和圆等标准形状的函数是已知的，因此可以利用这个函数来作为转换矩阵来进行参数空间的转换，比如直线:

y = kx + b

在欧式空间x-y坐标系中，x，y作为未知数，而k,b是作为已知数的。选择k,b作为参数空间的坐标系k-b坐标系，这时候x,y就是参数空间的已知数，对于任何一个(x,y)可以得到K-b空间中的一条直线,比如x=1,y=1 =>

b= 1-k => y'= 1- x'

假设现在已知直线为y=2x+1, k=2,b=1，那么在x-y坐标系中的一条直线，在K-b坐标系中对于一个点(2,1),这个点就是在x-y坐标系中直线上的其它点在k-b空间中得到的无数条直线的交点.

y = 2x + 1 

2个x,y对如下：

（0,1），（1,3）

转换到k-b空间为y = kx +b 

b= y -kx

把x,y对代入：

b = 1; //(0,1)

b = 3-k //（1,3）

 

这两条在K-b参数空间中的直线的交点是:b=1, k =2 ， 也就是(2,1)点。

如果在x-y空间中取任意的点，如果该点是这条直线上的点，每一个点映射到在k-b参数空间的直线都是通过（2,1）这个点的直线，也就是会对这个点进行投票，看投票数目的多少就知道是否存在直线了。

当然，因为截距表达有局限，因此转换成极坐标表示来确定参数空间比较合适。

对圆和椭圆这些已知表达式的形状可以利用表达式来生成参数空间。

但是对于不规则的形状，没有表达式可以使用，那么就需要使用广义霍夫变换了。广义霍夫变换利用的是形状的边缘点来表示该形状，也就是利用这些边缘点来生成一个大的特征向量来表示这个形状。

如果要在图像中检测某种不规则的形状(当然这种不规则的形状是预先知道的，这样可以对这个形状预先利用特征向量生成的方法来产生这个表示形状的特征向量)，然后在要检测的图像中去找到具有这个特征向量的形状。

具体的可以看下面的过程：

广义霍夫变换的目的是要在一个具体场景中寻找一个不规则已知物体的位置，我们把这个不规则已知物体叫做模板，这个已知物体的模板由一系列点组成。通过参数空间转换，我们把目标转换为寻找一个转换矩阵，通过该矩阵，可以使得模板与场景中模板出现的位置相匹配。只要我们确定了这个转换矩阵的参数，那么模板在场景中的位置也就确定了。

那么这个转换矩阵的参数如何确定呢？这就要通过投票机制，如果一个参数获得的投票最多，那么就认为这个参数是正确的。

一般情况下，要进行Generalised Hough transform，先要选取一个参考点，然后将普通的坐标转换为(r，, ɸ)这种形式，r为边界点到选取参考点的长度，ɸ为参考点到边界点的连线与边界点切线的夹角。如下图所示：

http://img.blog.csdn.net/20150115151637582?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMDI3ODMwNQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center

之后建立一个R-table，列出边界点上所有点的角度与其长度的对应关系，这样便能完整的表述我们的模板物体。(利用的是边缘点和形状内的一个参考点连接得到长度和切向角作为表示这个边缘点的特征向量,把所有的边缘点都提取这样的一个特征向量，最后把这些点的特征向量组合成一个大的特征向量(这里使用的是R table)来表示了这个不规则的形状).

R-table的建立过程如下：

http://img.blog.csdn.net/20150115152345632?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMDI3ODMwNQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center

R-table如下：

http://img.blog.csdn.net/20150115151859984?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMDI3ODMwNQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center

在之后的步骤中，我们可以通过角度来寻找匹配，再用计算出的值填充累加单元。但由于我们已经寻得各特征点的匹配关系，在实施的过程中，我们跳过这一步。直接进入下一步。

该算法的具体实施过程如下：

1、选取模板的（0，0）为参考点，代表模板的位置。模板的每一个特征点与参考点相减。（由于参考点选为（0，0），故各特征点不变。

2、初始化累加表.A[xcmin. . . xcmax][ycmin. . . ycmax][qmin . . .qmax][smin . . . smax]。其中q代表旋转角度，s代表缩放尺度。在A的大小选取上，我们按David G. Lowe给出的建议，We use broad bin sizes of 30 degrees for orientation, a factor of 2 for scale, and 0.25 times the maximum projected training image dimension (using the predicted scale) for location.

3、遍历场景中的每一点，记x',y'为模板中特征点的坐标。则可以用下式推出场景中模板的坐标，并对累加单元进行累加。（对theta和半径r进行遍历，求的是在这个theta和r下的参考点(xc,yc),这样就可以得到4D参数(xc,yc,r,theta)，因为这个形状选择的参考点是同一个，因此如果确实是要寻找的形状，那么A[xc][yc][theta][s]应该最大.而xc,yc正好就是模板的左上角点，这样就定位了这个形状在图像中的左上角点位置，因为形状是已知的，因此也就找到了这个形状。（theta max, s max确定了模板的大小)

http://img.blog.csdn.net/20150115152946171?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMDI3ODMwNQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center

4、找到所有累加单元的最大值，并找到其索引，则其对应的（xc，yc）为模板中（0，0）点在场景中对应的坐标。

5、找到没有为最大累加单元做出贡献的点，并认为它是奇异点，进行排除。

6、存储剩下的点。

OK，Generalised Hough transform过程到此为止。之后，我按照David G. Lowe在Distinctive Image Features from Scale-Invariant Keypoints一文中给出的说明，对最终的匹配点进行仿射变换，求出仿射变换的参数。模板到场景坐标的转换矩阵为：

http://img.blog.csdn.net/20150115154225234?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMDI3ODMwNQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center

我们将上式记为Ax=b；那么我们的目标就是求解x，x的求解方式如下：

http://img.blog.csdn.net/20150115154508905?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMDI3ODMwNQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center

到此，我们完成了所有工作。