Hough 变换算法

直线的极座标表示

考虑一条直线 $ax+by+c=0$ ，过原点 $O$ 做这条直线的垂线交于 $N$ 。不妨令 $N$ 点的极座标为 $(r_N, \theta_N)$ ，再任取直线上的一点 $P(x,y)$ ，显然应该有 $ON\perp NP$ ，所以两向量垂直，故

\vec{ON}\cdot \vec{NP}=0

代入 $\vec{ON}=(r_N\cos(\theta_N), r_N\sin(\theta_N)), \vec{NP}=(x-r_N\cos(\theta_N), y-r_N\sin(\theta_N))$ ，化简并代入点乘公式有

\begin{aligned} r_N \cos(\theta_N)\cdot\Big( x-r_N\cos(\theta_N) \Big) + r_N\sin(\theta_N)\cdot\Big( y-r_N\sin(\theta_N) \Big)&=0\\ x\cdot r_N\cos(\theta_N)-r_N^2\cos^2(\theta_N) + y\cdot r_N\sin(\theta_N) - r_N^2\sin^2(\theta_N)&=0\\ x\cdot r_N\cos(\theta_N) + y\cdot r_N\sin(\theta_N)&=r_N^2\\ x\cos(\theta_N) + y\sin(\theta_N)&=r_N \end{aligned}

所以直线的表达式是

\boxed{x\cos\theta + y\sin\theta=r}

令 $(x_0,y_0)$ 为图像上一点，对于图像空间来说，横轴为 $x$ ，纵轴为 $y$ .

我们找出所有 $(\theta,r)$ 满足

x_0\cos\theta + y_0\sin\theta=r

把这些点标在 Hough Space 中。Hough Space 的横轴为 $\theta$ ，纵轴为 $r$ . 那么满足条件的 $(\theta,r)$ 在 Hough Space 上的图像为正弦函数的一部分。

这是因为，我们可以把直线的极座标表达式转化成

$\frac{1}{\sqrt{x_0^2+y_0^2}}\sin(\theta+\varphi)=r$
所以 Hough Space 上的曲线是正弦函数.

对于每一个点 $(x,y)$ ，计算所有 $(\theta,r)$ ，然后在计数器 $A$ 里 +1，即 $A(\theta, r)\gets A(\theta, r)+1$ ，最后，我们取得票数最多的 $(\theta, r)$ 视作 Linked Edge.

这个就类似于，我们对每一个点计算它可能属于什么直线，然后对所有点找出那条公共的直线。