Hough变换原理

article/2025/9/29 5:28:02

霍夫变换在识别方程式已知的曲线是常用的一种方法，本文通过识别直线方程为向导，说明霍夫变换的原理。

话不多说，开始今天的主题，我们处理的对象是二值黑白图像，如下图：

上图是我自绘的五个点，考虑到这些点中的任何一个——经过这个点有无穷条直线，如果这个点能够对这些线投票，那么每条可能经过这个点的直线都会收到一票，现在考虑另外一个类似的点，它也给所有可能经过他的直线投票，这样就有一条线（两个点都在这条直线上）将会收到这两个点的投票，总共有两票，而其他的线只能收到 0 票或者 1 票。

现在我们需要用最少参数来描述每一条直线，但是标准形式 Y = KX + b，对于竖直线（k = $\infty$ ）是有问题的，因此通常用（ $\LARGE (p, \theta )$ 参数来表示一条直线：

$\LARGE v = -utan\theta + \frac{p}{cos\theta }$

其中 $\LARGE \theta \in[- \frac{\pi}{2}, \frac{\pi}{2} )$ ，是水平轴与该直线垂线的夹角， $\LARGE p\in[- p_{max}, p_{max}]$ ,是原点到该直线的垂直距离，水平线的 $\LARGE \theta = 0$ ，竖直线 $\LARGE \theta =-\frac {\pi}{2}$ ,因此，没一条直线可以看做是二维空间的一个点 $\LARGE (p , \theta )$ ,该二维空间代表了所有的直线。

事实上，我们无法考虑经过每一个点的无数条直线，所以只考虑有限集合中的直线，把 $\LARGE \theta p$ 空间离散化，并用一个相应的二维数组 $\LARGE N_\theta \chi N_p$ 数组 $\LARGE A$ 来记录票数， $\LARGE A$ 被称为累加数组，对于一副 $\LARGE W\chi H$ 输入图像，有

$\LARGE p_{max} = - p_{max} = \sqrt{W^2 + H^2}$

$\LARGE A$ 有 $\LARGE N_p$ 个元素位于区间 $\LARGE p \inp\in[- p_{max}, p_{max}]$ ，还有 $\LARGE N_\theta$ 个元素位于区间 $\LARGE \theta \in[- \frac{\pi}{2}, \frac{\pi}{2} )$ 。数组的索引是整数 $\LARGE （i， j）$ $\LARGE (i, j) \subset Z^2$ ，因此有：

$\LARGE i\in [i, N_\theta ] \mapsto\theta \in [-\frac{\pi}{2}, \frac{\pi}{2})$

$\LARGE j\in [i, N_p ] \mapsto p\in [-p_{max},p_{max})$

边缘点 $\LARGE （u, v）$ $\LARGE (u, v)$ 将投票给所有满足方程 $\LARGE v = -utan\theta + \frac{p}{cos\theta }$ 的直线，它包括所有的 $\LARGE （i， j）$ $\LARGE (i, j)$ 对，满足

$\LARGE p = usin\theta + vcos\theta$
并且元素 $\LARGE A[i,j]$ 都增大了。对于没一个 $\LARGE i \in [i,N_\theta ]$ ，都可以计算出相应的 $\LARGE \theta$ 值，然后根据等式 $\LARGE p = usin\theta + vcos\theta$ 计算 $\LARGE p$ ，再把 $\LARGE p$ ，再把 $\LARGE p$ 映射到相应的整数 $\LARGE j$ 。