霍夫变换

算法实作

侦测直线的霍夫变换算法使用一个称作累加器(accumulator)二维的矩阵，来侦测图片中是否有直线可以用方程式来描述。
Accumulator矩阵的维度等于未知的参数的总数，举例来说，要寻找是否有一条直线，他的参数空间的变数总共有两个和 ，因此Accumulator矩阵的维度是2。
而这个二维的accumulator矩阵，一个维度代表经过量化(quantized)的，另一个维度则是代表量化的，因此每一个矩阵的元素(element)的值，是可以用该元素表示的直线
的数量总和，因此矩阵元素的最大值的意义是，该张图片里出现该元素代表的直线的信心最大。
对于每一个像素(pixel) 与其邻近的点，算法会依据一些证据来判断是否有一条直线通过该像素与其邻近的点，如果有，算法就会把该条直线的参数所对应到的Accumulator矩阵里的元素增加1，最后在选出Accumulator矩阵里，大于阈值(threshold)的一些局部最大值(local maximum)，就可能找到真地存在于图片上的直线，
在其他状况下，不使用threshold改用其他的技巧可以让算法的表现(performance)更好。然而，霍夫变换只能求得线的参数，无法求得该条线的长度，所以，必须在霍夫变换完的下一步，将线条配对到
图上的线条。而霍夫变换的误差来源，可能是图片的不完美(噪声、遗漏像素)，使得边缘侦测器(edge detector)的侦测出错误的边界。

范例

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

霍夫变换的变形与延伸

利用梯度的方向(gradient direction)减少投票数
Kernel-based Hough transform (KHT)

限制

霍夫变换透过由投票机制(accumaltor矩阵的极大值)来找出线条的参数，这种机制让霍夫变换能够在有噪声的图片中找出线段。在有噪声的情况下，如果量化(quantization)的间距(step)太细，
会让票数分散，换句话说使得应该集中的值分散到极大值附近的矩阵元素。
当参数空间的变数变多，每个矩阵元素的平均大小也会下降，使得正确的参数跟其他参数之间的差变小。另外，每增加一个参数，霍夫变换的复杂度就会增加一个，
是参数的总数、是图片的大小。因此使用霍夫变换侦测直线和圆以外的形状时，必须要非常小心上述的问题。
最后，霍夫变换的效率取决于输入图片的品质，边缘必须要正确呈现才能让霍夫变换有效率，当图片有噪声的时候，在霍夫变换的前一级要做抑制噪声的动作。