hough 变换

变换是一门非常棒的技术，在图像处理中经常用来进行对图像的检测和分割，比如在图像中检测直线、圆这样的几何体。为方便介绍hough变换，我们先从检测直线入手。

下图的坐标轴是x,y，它是基于图像平面。hough 变换的本质是从图像空间转化到 $\rho$ , $\Theta$ 空间。如下图， $\rho$ 是从原点引出来，垂直于红色线， $\Theta$ 是蓝线与x轴的夹角。所以（ $\rho$ , $\Theta$ ）的组合就确定了一条线。

相信大家都知道如何表示一条直线。

对直线上的每一点，这个方程式都成立。这就从x,y 坐标系转换到了 $\rho$ , $\Theta$ 坐标系。我们需要对 $\rho$ , $\Theta$ 离散化，因为计算机无法处理连续的情况，离散化的精度根据实际的情况设定，同时 $\rho$ , $\Theta$ 都是有界的，比如 $\rho$ 不可能超过图像的大小。

hough 变换是通过投票的方式来找到最可能的线。我们知道每个点处可以有无数条直线通过，该点会为这无数条直线都投上一票。先将 $\rho$ , $\Theta$ 离散化，并通过不同的点对这些 $\rho$ , $\Theta$ 进行投票，假设我们现在将 $\Theta$ 化的精度设置为1，那么接下来，我们依次对 $\Theta$ = 1，2，3.....进行得票计数；对离散化后不同的 $\rho$ 也做同样的投票计数。最后，我们选择票数最多的前几条线作为检测到直线，或者也可以设定一个最低得票阈值，得票高于阈值的 $\rho$ , $\Theta$ 即为检测到的直线。非常简单，但是很强大的技术。

除了直线，hough 变化还能用来检测图像中的圆。圆在图像平面的表达式为：

处理的方法也是一样的，只是对于直线来说，我们需要对 $\rho$ , $\Theta$ 进行投票，对于圆来说，我们需要对 $x_{0} y_{0} r$ 进行投票。也就是说直线的参数是二维的，但圆的参数是三维的。同样的，我们也可以对圆心和圆的半径进行限制，因为我们知道r 不可能超过图像的大小。

理论上来说，hough 变换可以用来检测任意复杂的形状，但是也伴随着需要投票参数的增加，需要的计算量显著增加。所以hough 变换一般只用来检测很简单的几何形状，比如，直线，圆，椭圆。