霍夫变换

霍夫变换是一种特征提取技术，被广泛应用在图像分析、电脑视觉以及数位影像处理。 霍夫变换用于辨别找出物件中的特征，例如：线条。演算法流程大致如下，给定一个物件、要辨别的形状的种类，演算法会在参数空间中执行投票来决定物体的形状，而这是由累加空间（accumulator space）里的局部最大值来决定。

现在广泛使用的霍夫变换是由 Richard Duda 和 Peter Hart 在西元1972年发明，并称之为广义霍夫变换，广义霍夫变换和更早前1962年的Paul Hough 的专利有关 。 经典的霍夫变换是侦测图片中的直线，之后，霍夫变换不仅能识别直线，也能够识别任何形状，常见的有圆形、椭圆形。1981年，因为Dana H. Ballard 的一篇期刊论文 "Generalizing the Hough transform to detect arbitrary shapes"，让霍夫变换开始流行于计算机视觉界。

历史

这个变换为了解析气泡室 (bubble chamber)的图片才诞生的(Hough, 1959)。

霍夫变换在1962年申请为专利U.S. Patent 3,069,654 （页面存档备份，存于互联网档案馆），其专利名为"辨识复杂图案的方法及手段"(Method and Means for Recognizing Complex Patterns)。 任一条直线可以由斜率和截距来表示，在该专利中，利用斜率和截距来将一条直线参数化，然而这会导致无界的转换空间(unbounded transform space)，因为斜率有可能是无限大。

而现在被广泛使用的$(\rho ,\theta )$表示式，第一次出现在

Duda, R. O. and P. E. Hart, "Use of the Hough Transformation to Detect Lines and Curves in Pictures," Comm. ACM, Vol. 15, pp. 11–15 (January, 1972),

虽然这早已经是拉东变换的标准。

O'Gorman and Clowes' variation出自

O'Gorman, Frank; Clowes, MB. Finding Picture Edges Through Collinearity of Feature Points. IEEE Trans. Comput. 1976, 25 (4): 449–456. ,

而现代的霍夫变换的发明故事纪载于

Hart, P. E., "How the Hough Transform was Invented" (PDF, 268 kB), IEEE Signal Processing Magazine, Vol 26, Issue 6, pp 18 – 22 (November, 2009).

理论

在自动化分析数位图片的问题里，其中一个常有的子问题是侦测某些简单的直线、圆形、椭圆形。在多数情况下，边缘侦测器(edge detector)会先用来做图片前处理，将原本的图片变成只含有边缘的图片。 因为图片的不完美或是边缘侦测的不完美，导致有些点(point)或像素(pixel)缺漏，或是有杂讯使得边缘侦测器所得的边界偏离了实际的边界。所以无法直观的将检测出的边缘分成直线、圆形、椭圆形的集合， 而霍夫变换解决上述问题，借由霍夫变换演算法中的投票步骤，在复杂的参数空间中找到图形的参数，电脑可以由参数得知该边缘(edge)是哪种形状。

最简单的霍夫变换是在图像中识别直线。在平面直角坐标系(x-y)中，一条直线可以用方程式

$y=m_{0}x+b_{0}$

表示，$b_{0}$是直线的截距，$m_{0}$是直线的斜率。 而$(m_{0},b_{0})$可以视为参数空间$(m,b)$中的一点。当直线垂直于$x$轴时，斜率为无限大， 若用电脑数值计算时会很不方便，因此Duda 和 Hart 提出使用Hesse normal form来表示直线的参数

$r=x\cos \theta +y\sin \theta$

$r$是从原点到直线的距离，$\theta$是${\vec {r}}$和$x$轴的夹角。利用参数空间$(r,\theta )$解决了原本参数空间$(m,b)$发散的问题， 进而能够比较每一个线段的参数，有人将$(r,\theta )$平面称为二维直线的霍夫空间(Hough space)。这个表示方法让霍夫变换跟二维的拉东变换非常相似，可以说是一体两面 。

给定一个点$(x_{0},y_{0})$，通过该点的所有直线的参数$(r,\theta )$的集合，会在$(r,\theta )$平面上形成一个三角函数，可由下方程式证明

$r=x_{0}\cos \theta +y_{0}\sin \theta \Rightarrow r={\sqrt {x_{0}^{2}+y_{0}^{2}}}\left({\frac {x_{0}}{\sqrt {x_{0}^{2}+y_{0}^{2}}}}\cos \theta +{\frac {y_{0}}{\sqrt {x_{0}^{2}+y_{0}^{2}}}}\sin \theta \right)\Rightarrow r={\sqrt {x_{0}^{2}+y_{0}^{2}}}\left(\cos \phi \cos \theta +\sin \phi \sin \theta \right)$

$\Rightarrow r={\sqrt {x_{0}^{2}+y_{0}^{2}}}\cos(\theta -\phi )$

因此，给定很多点，判断这些点是否共线的问题，经由霍夫变换之后，变成判断平面上一堆曲线（每一个点在$(r,\theta )$平面上代表一条曲线）是否共点（concurrent）的问题。

演算法实作

侦测直线的霍夫变换演算法使用一个称作累加器(accumulator)二维的矩阵，来侦测图片中是否有直线可以用方程式$r=x\cos \theta +y\sin \theta$来描述。 Accumulator矩阵的维度等于未知的参数的总数，举例来说，要寻找是否有一条直线，他的参数空间的变数总共有两个$r$和$\theta$ ，因此Accumulator矩阵的维度是2。 而这个二维的accumulator矩阵，一个维度代表经过量化(quantized)的$r$，另一个维度则是代表量化的$\theta$，因此每一个矩阵的元素(element)的值，是可以用该元素表示的直线 的数量总和，因此矩阵元素的最大值的意义是，该张图片里出现该元素代表的直线的信心最大。

对于每一个像素(pixel) $(x,y)$与其邻近的点，演算法会依据一些证据来判断是否有一条直线通过该像素$(x,y)$与其邻近的点，如果有，演算法就会把该条直线的参数 $(r,\theta )$所对应到的Accumulator矩阵里的元素增加1，最后在选出Accumulator矩阵里，大于阈值(threshold)的一些局部最大值(local maximum)，就可能找到真地存在于图片上的直线， 在其他状况下，不使用threshold改用其他的技巧可以让演算法的表现(performance)更好。然而，霍夫变换只能求得线的参数，无法求得该条线的长度，所以，必须在霍夫变换完的下一步，将线条配对到 图上的线条。而霍夫变换的误差来源，可能是图片的不完美(杂讯、遗漏像素)，使得边缘侦测器(edge detector)的侦测出错误的边界。

范例

输入的图片中有两条粗直线，经过霍夫变换后的结果得到accumulator矩阵，右图就是把accumulator矩阵画出来，越亮值越大，越黑值越小。在右图中，有两个很明显的亮点， 这两个亮点分别代表两条不同参数的直线，与输入的图片(左图)吻合。然后读取矩阵的两个最大值就可以得出这两条线距画面中心距离以及角度。

霍夫变换的变形与延伸

利用梯度的方向(gradient direction)减少投票数

Kernel-based Hough transform (KHT)

限制

霍夫变换透过由投票机制(accumulator矩阵的极大值)来找出线条的参数，这种机制让霍夫变换能够在有杂讯的图片中找出线段。在有杂讯的情况下，如果量化(quantization)的间距(step)太细， 会让票数分散，换句话说使得应该集中的值分散到极大值附近的矩阵元素。

当参数空间的变数变多，每个矩阵元素的平均大小也会下降，使得正确的参数跟其他参数之间的差变小。另外，每增加一个参数，霍夫变换的复杂度就会增加一个${\bf {O}}(A^{m-2})$， $m$是参数的总数、$A$是图片的大小。因此使用霍夫变换侦测直线和圆以外的形状时，必须要非常小心上述的问题。

最后，霍夫变换的效率取决于输入图片的品质，边缘必须要正确呈现才能让霍夫变换有效率，当图片有杂讯的时候，在霍夫变换的前一级要做抑制杂讯的动作。

参见

• 广义霍夫变换
• Randomized Hough transform
• 拉东变换
• 傅里叶变换