【视觉算法】广义霍夫变换(Generalized Hough Transform)

在上一篇文章中，我们学习了经典霍夫变换，用以识别图像中的可解析图形；而广义霍夫变换(Generalized Hough Transform)旨在解决不可解析的不规则图形的识别问题。
以下，结合Generalized Hough Transform (GHT)(Ballard and Brown, section 4.3.4, Sonka et al., section 5.2.6)这篇文章学习。
首先思考，我们人在一张图片中寻找指定的物体，需要哪些步骤？
一、先验信息，也就是我们要事先知道物体长什么样(它具有哪些特征)；
二、在图片中寻找长的像的物体(寻找相似的特征)。
事实上，GHT也是按照这个步骤进行的，为了便于理解，由简入繁，先看一个特殊(简单)情形：固定待识别物体的方向和尺寸，即保持与模型(先验信息的来源)中的一致。

解释上图，首先看坐标系中的图形，它是一个不规则图形；在图形中寻找任一参考点p(Xc,Yc)，以及边缘点q(X,Y)；由p向q引一条线段，它的长度为r，角度为α(与x轴正方向的夹角)，后面的公式就是由r和α表示p和q之间的关系，很好理解。再看下图：

这里的预处理其实就是从模型中学习先验信息，即将模型中的一些特征保存下来；说到特征，就要知道特征点，这里的特征点是图形的所有边缘点。
特征中，除了上面提到的r和α，还有Φ，它是特征点(边缘点)p的切线与x轴正方向的夹角；显然，Φ不受参考点选取的影响，它是图形的固有属性；因此选取Φ作为R-table的索引。
由于图形是不规则的，一个Φ可能对应多个r和α；先验信息就是这样保存在R-table中的。
这里，再观察一下这个式子：

观察这个式子，回想经典霍夫变换中，x,y和参数m,b之间的关系，是不是有些熟悉？
实际上，上式中的Xc,Yc构造了霍夫(广义的)参数空间，而X,Y是在图像空间中的。再继续看：

这里的检测，是在新的图像中，寻找和模型一致的图形。
量化参数空间，实际上就构造了用以投票的网格；对于每一个特征点，计算它的Φ，在R-table中以Φ为索引检索对应的r和α(上面提到过，可能对应着多个)；对于每一个(α,r)，计算Xc,Yc的值，对应的网格的累加器加一(投票)。
当所有的特征点都计算完成，寻找参数空间中票数大于阈值的网格，我们就认为对该网格投过票的那些特征点为目标边缘，即完成了物体的识别。注意，上图中说的边缘点定位在Xc,Yc说的是参数空间内。
至此，特殊(简单)情况就说完了，下面开始讨论一般(复杂)情况：即考虑旋转和缩放。看下图：

加入了旋转角度θ和缩放因子s，很基础；上图的X’‘是旋转和缩放后的Xc和X的差值，即参考点p和特征点q在x轴上(水平)的距离；Y’‘是在y轴上(垂直)的方向距离。X’,Y’是未经过旋转和缩放的，前面图中有提到。很好理解，接着看：

这里量化参数空间，注意到加入了两个未知参数θ和s，维度已经扩展到四维。
首先，根据特征点的Φ索引(α,r)，计算未经过旋转和平移的X’，Y’；然后，以步长为1遍历θ和s，对相应的网格进行投票；选取票数大于阈值的网格，即完成了不规则物体的识别(和姿态估计)。
至此，广义的霍夫变换基本学习完了，下面分析它的优点和缺点(引自原文)：
优点：
1、广义霍夫变换本质上是一种用于物体识别的方法。
2、它对部分或轻微变形的形状鲁棒性好(即对遮挡下的识别鲁棒性好)。
3、对于图像中存在其他结构(即其他线条，曲线等)干扰，鲁棒性好。
4、抗噪声能力强。
5、一次遍历即可找到多个同类目标。
缺点：
1、它需要大量的存储和大量的计算(但是它本质上是可并行化的)。这里说一下自己的理解：参数空间维度高，有穷举过程。
下一篇文章学习广义霍夫变换在三维物体识别中的改进和应用。