Hough(霍夫)变换识别各种图形（直线、圆、椭圆、任意闭合图形）

前提： 在霍夫变换之前，我们要对图像进行边缘检测，提取出图像的边缘，然后检测图像的边缘是否为目标图形（直线、圆、椭圆、任意闭合图形）。

霍夫曼变换，用于识别形如$$f(\mathbf{x},\alpha )=0\text{\hspace{1em}(*)}$$形式的图形边缘，其中 x = { x , y , …   } \bold{x}=\{x,y,\dots\} x={x,y,…}为自变量向量， α = { a , b , …   } \bold{\alpha}=\{a,b,\dots\} α={a,b,…}为参数向量，对就像(1.1)那样。

1.霍夫变换识别直线

1.1引言

在$x-y$平面中，直线方程:$$y=ax+b\text{\hspace{1em}(1.1)}$$
确定了参数$a$、$b$便确定了直线(1.1)。

考虑： 构建一个参数平面——$a-b$平面，那么$a-b$平面上的一个点$(a,b)$便对应$x-y$平面上的一个直线$y=ax+b$。那么能否在$a-b$平面上找到一个显著的点$(a,b)$来确定直线$y=ax+b$呢？

取$a-b$平面，将$a$、$b$视为自变量，$x$、$y$视为变量，则(1.1)变换为$$a=\frac{b}{x}-\frac{y}{x}\text{\hspace{1em}(1.2)}$$

思路： 设$(x_0,y_0)$、$(x_1,y_1)$是平面$x-y$内直线$y=ax+b$上的两个点，则$(x_0,y_0)$、$(x_1,y_1)$均满足(1,1)，即
$$\{\begin{array}{l}{y}_0=a{x}_0+b\\ y_1=a{x}_1+b\end{array}\text{\hspace{1em}(1.3)}$$
将(1.3)变形，得到
$$\{\begin{array}{l}a=\frac{b}{x_0}-\frac{y_0}{x_0}\\ a=\frac{b}{x_1}-\frac{y_1}{x_1}\end{array}\text{\hspace{1em}(1.4)}$$
(1.4)的上、下两式分别对应平面$a-b$上的两条直线，且两条直线交汇于点(a,b)。

这样，平面$a-b$上的点$(a,b)$便对应平面$x-y$上的直线(1.1)。

由于(1.3)的表示形式可能出现$x=0$的情况，无法计算，于是我们采用极坐标平面来进行变换。

1.2极坐标下的霍夫曼直线识别

对于参数平面，不再采用$x-y$平面，而采取极坐标平面，极坐标平面$r-\theta$下的直线方程为
$$r=xcos\theta +ysin\theta \text{\hspace{1em}(1.5)}$$
其中，$x$、$y$为参数，$r$、$\theta$为自变量。与1.1节中的讨论一致，确定了点$(r,\theta )$，则确定了直线(1.1)。

设点$(x_0,y_0)$和$(x_1,y_1)$为直线(1.1)上的点，则该两点同时满足直线(1.1)对应的极坐标方程
$$\{\begin{array}{l}r=x_{0}cos\theta +y_{0}sin\theta \\ r=x_{1}cos\theta +y_{1}bsin\theta \end{array}\text{\hspace{1em}(1.6)}$$
观察(1.6)，可以解出$r$和$\theta$。但故事就这么简单就结束，好像有点“索然无味”

我们观察$$r=x_{0}cos\theta +y_{0}sin\theta$$有
$$r=x_{0}cos\theta +y_{0}sin\theta =\sqrt{x_0^2+y_0^2}sin(\theta +{\beta }_0)=\sqrt{x_0^2+y_0^2}cos(\theta -{\beta }_0)\text{\hspace{1em}(1.7)}$$
其中，$tan{\beta }_0=x_0/y_0$。(1.7)说明，原$x-y$平面上的一个点$(x_0,y_0)$,对应$r-\theta$平面上的一个正弦(余弦)曲线。而对于点$(x_1,y_1)$则有
$$r=x_{1}cos\theta +y_{1}sin\theta =\sqrt{x_1^2+y_1^2}sin(\theta +{\beta }_1)=\sqrt{x_1^2+y_1^2}cos(\theta -{\beta }_1)\text{\hspace{1em}(1.8)}$$。其中，$tan{\beta }_1=x_1/y_1$。

(1.6)、(1.7)和(1.8)可归结为
$$\{\begin{array}{l}r=\sqrt{x_0^2+y_0^2}sin(\theta +{\beta }_0)\\ r=\sqrt{x_1^2+y_1^2}sin(\theta +{\beta }_1)\end{array}\text{\hspace{1em}(1.9)}$$
其中，$tan{\beta }_0=x_0/y_0$，$tan{\beta }_1=x_1/y_1$。
(1.9)表示，平面$x-y$上的点$(x_0,y_0)$和$(x_1,y_1)$分别对应平面$r-\theta$上的一条正弦(余弦)曲线。而这两条正弦(余弦)曲线的交点$(r,\theta )$便是极坐标下直线方程(1.5)的参数。

小结： Hough变换的核心思想就是，$x-y$平面上一条直线上的两个点$(x_0,y_0)$、$(x_1,y_1)$，分别对应参数平面上的两条直线。参数平面上两条线(若为$r-\theta$平面，则为正、余弦线)的交点，即为$x-y$平面上直线$y=ax-b$的参数$a$和$b$(若是极坐标平面，即为$r$和$\theta$)。

1.3识别圆形

圆形坐标$$(x-a{)}^2+(y-b{)}^2=r^2\text{\hspace{1em}(1.10)}$$
根据1.2、1.3节中的思路，取参数空间$a-b-r$，当确定一个点$(x_0,y_0)$时，对应超平面$$(x_0-a{)}^2+(y_0-b{)}^2=r^2\text{\hspace{1em}(1.11)}$$ 即，以点$(a=x_0,b=y_0)$为圆心，半径为$r$的一个圆锥。So，给定待识别圆形上的三个点$(x_0,y_0)$、$(x_1,y_1)$和$(x_2,y_2)$，那么对应下图右图的三个圆锥。这三个圆锥的共同交叉点$(a^{\prime },b^{\prime },c^{\prime })$便是(1.10)的参数。

图片借用自/jiangsgyx/article/details/83755739

依照上面的原理，我们在实际计算的时候需要一个“三维累加器”（后面讲），显然带来计算上维度的增加。于是有人提出了，在(1.10)对$x$求导，得到

$$2(x-a)+2(y-b)\frac{dy}{dx}=0\text{\hspace{1em}(1.12)}$$
这样就将(1.10)中的三个待定参数降为两个。但是，微分运算会损失信息，导致算法的精度下降。

Note： 但这种改进的Hough变换检测圆的方法其检测精度并不高，原因在于，此种方法利用了边界斜率。从本质上讲，边界斜率其实是用曲线在某一点的弦的斜率来代替的，这种情况下，要保证不存在误差，只有在弦长为零的情况。但在数字图像中，曲线的表现形式是离散的，其在某一点处的斜率指的是此点右向n步斜率或是左向n步斜率。如果弦长过小了，斜率的量化误差就会增大。这种方法比较适用于干扰较少的完整圆形目标。/jiangsgyx/article/details/83755739

1.4任意图形的识别

记形状物边界上的点为$(x,y)$，形状物内任意确定一个点$(x_c,y_c)$为参考点。从边界上的点$(x,y)$到参考点$(x_c,y_c)$的距离为$r$。$r$是$\psi$的函数，$\psi$为边界点$(x,y)$的梯度方向。(这里有点类似傅里叶描述子，参见我没写完的blog。没写完，当然是看不见了。) $\alpha$是$(x_c,y_c)$到边界$(x,y)$连线的角度。如此，$(x_c,y_c)$与$(x,y)$的几何关系便简单了，它们应满足
$$\{\begin{array}{l}{x}_c=x+rcos\alpha \\ y_c=y+rsin\alpha \end{array}\text{\hspace{1em}(1.13)}$$

由于$r$和$\alpha$都是与$(x,y)$相关，而$(x,y)$直接对应该点的梯度方向$\psi$，故$r$和$\alpha$为$\psi$的函数，即$r(\psi )$和$\alpha (\psi )$，于是(1.13)为

$$\{\begin{array}{l}{x}_c=x+r(\psi )cos\alpha (\psi )\\ y_c=y+r(\psi )sin\alpha (\psi )\end{array}\text{\hspace{1em}(1.14)}$$

考虑形状上任意点$(x_i,y_i)$都对应自己的梯度方向${\psi }_i$，而${\psi }_i$显然有${\psi }_i\in [0,2\pi )$。

我们现在已知标准形状R，已知内部选定的参考点$(x_c,y_c)$。根据 { ψ i } \{\psi_i\} {ψi​}的划分，填写表-1.

于是，对

		表-1
${\psi }_1$	$(r_1,{\alpha }_1)$	$(r_1^2,{\alpha }_1^2)$	$\dots$	$(r_1^m,{\alpha }_1^m)$
${\psi }_2$	$(r_2,{\alpha }_2)$	$(r_2^2,{\alpha }_2^2)$	$\dots$	$(r_2^m,{\alpha }_2^m)$
$\dots$	$\dots$	$\dots$	$\dots$
${\psi }_n$	$(r_n,{\alpha }_n)$	$(r_n^2,{\alpha }_n^2)$	$\dots$	$(r_n^m,{\alpha }_n^m)$

为了方面理解，我认为，表-1可以简化为表-2

	表-2
${\psi }_1$	$(r_1,{\alpha }_1)$
${\psi }_2$	$(r_2,{\alpha }_2)$
$\dots$	$\dots$
${\psi }_n$	$(r_n,{\alpha }_n)$

填写好表-2后，在待检测的边缘上依次取点 { ( x i , y j ) } \{(x_i,y_j)\} {(xi​,yj​)}，由点 { ( x i , y j ) } \{(x_i,y_j)\} {(xi​,yj​)}得到${\psi }_i^{\prime }$，按照临近原则，取到${\psi }_i$对应的$(r_i,{\alpha }_i)$，并根据(1.14)计算$(x_c^{\prime },y_c^{\prime })$。
在区域$A(x,y)$中，执行
$$A(x_c^{\prime },y_c^{\prime })=A(x_c^{\prime },y_c^{\prime })+1\text{\hspace{1em}(1.15)}$$
即累加投票。如果$(x_c^{\prime },y_c^{\prime })$的值相对足够显著，且与$(x_c,y_c)$近似，则认为图形匹配。

推荐阅读
/shenziheng1/article/details/75307410
/tercel_zhang/article/details/79928687