霍夫变换

介绍与应用场景

霍夫变换(Hough Transform)是图像处理中的一种特征提取技术，该过程在一个参数空间中通过计算累计结果的局部最大值得到一个符合该特定形状的集合作为霍夫变换结果。经典霍夫变换用来检测图像中的直线，后来霍夫变换扩展到任意形状物体的识别，多为圆和椭圆。霍夫变换运用两个坐标空间之间的变换将在一个空间中具有相同形状的曲线或直线映射到另一个坐标空间的一个点上形成峰值，从而把检测任意形状的问题转化为统计峰值问题。

基本原理

考虑点$(x_i,y_i)$及通过这个点的线,有无穷多的线通过点$(x_i,y_i)$，针对a和b的一些值，满足斜截式$y_i = ax_i + b$的所有线都通过该点。该公式也可以写为$b = -ax_i + y_i$，考虑ab平面(即参数空间)对固定点$(x_i,y_i)$得到一条线的方程。另外，第二个点$(x_j,y_j)$也有一条在参数空间中与之相关的线，这条线和与$(x_i,y_i)$相关的线交于点$(a’,b’)$，其中$a’$是斜率，$b’$是在xy平面上包含点$(x_i,y_i)$和$(x_j,y_j)$的线的截距。在参数空间中，这条线包含的所有点都有相交于$(a’,b’)$点的直线。
简单理解，直线由两个点$A(x_1,y_1)$和$B(x_2,y_2)$定义，在参数空间中，两条直线的唯一公共点是在原图像空间中表示连接点A和B的唯一存在的直线

因此，给定很多点，判断这些点是否共线的问题，经由霍夫变换之后，变成判断一堆曲线(每一个点在$(r, \theta)$平面上代表一条曲线)是否在 $(r,\theta)$平面上相交于同一点的问题
另外用法线表示法:
$$xcos\theta + ysin\theta = \rho$$
水平线的$\theta$=0,$\rho$等于正的x的截距，垂直线的$\theta=90$度，$\rho$等于正的y的截距

在坐标(i, j)的单元位置，累加器的值是 A(i, j)，对应于参数空间坐标$(\rho_i,\theta_j)$的正方形。最初，这些单元位置为零。然后，对于每个图像平面上的非背景点$(x_k,y_k)$(就是 xy 平面)，我们令 θ 等于在 θ 轴上允许的细分值，并通过公式$\rho = x_kcos\theta+y_ksin\theta$解出相应的 ρ 值。然后，得到的 ρ 值四舍五入为最接近的 ρ 轴上允许的单元值。相应的累加器单元增加一个增量。在这个过程的最后，累加单元 A(i, j)中的值 Q 就意味着 xy 平面上位于线$xcos\theta_j+ysin\theta_j = \rho_i$上的点有 Q 个。在$\rho\theta$平面上，细分的数目决定了这些点的共线的精确度。累加器数组在工具箱中叫做霍夫变换矩阵，简称霍夫变换。

MATLAB工具箱函数

hough函数

默认语法

[H, theta, rho] = hough(f)

H是霍夫变换矩阵，theta和rho是$\theta$和$\rho$的值
下面这个例子可以加深对霍夫变换的理解

f = zeros(101,101);

f(1,1) = 1;

f(101,1) = 1;

f(1,101) = 1;

f(101, 101) = 1;

f(51, 51) = 1;

% H = hough(f);

[H, theta, rho] = hough(f);

imshow(H, [],'XData', theta,'YData', rho, 'InitialMagnification', 'fit')

axis on, axis normal

xlabel('\theta'),ylabel('\rho')

结果:

观察图可以看打到三条曲线在+45度和-45度处的交点指出:f中有两组三个共线的点。两条曲线在$(\rho,\theta)$ = (0,-90)、(-100,-90)、(0,0)、(100,0)处的交点指出:有4组位于垂直线和水平线上的公共点

houghpeaks函数

寻找指定的峰值数
默认语法

peaks = houghpeaks(H, NumPeaks)

H是霍夫变换矩阵

houghlines函数

决定线的起点和终点
默认语法

lines = houghlines(f, theta, rho, peaks)

输出lines是结构数组，长度等于找到的线段。结构中的每个元素可以看成一条线，并含有下列字段:

point1:两元素向量[r1,c1]，指定了线段终点的行列坐标。
point2:两元素向量[r2,c2]，指定了线段其他终点的行列坐标。
theta:与线相关的霍夫变换的以度计量的角度。
rho:与线相关的霍夫变换的$\rho$轴位置。

MATLAB使用霍夫变换检测和连接线

f = imread('timg1.jpg');

f = rgb2gray(f);

BW = edge(f,'canny');

[H ,theta, rho] = hough(BW, 'ThetaResolution', 0.2);

imshow(H, [],'XData', theta,'YData', rho, 'InitialMagnification', 'fit')

axis on, axis normal

xlabel('\theta'),ylabel('\rho')

peaks = houghpeaks(H, 5);

hold on

plot(theta(peaks( :, 2)), rho(peaks(:, 1)),...

    'linestyle', 'none', 'marker', 's', 'color', 'w');


lines = houghlines(f, theta, rho, peaks);

figure, imshow(f), hold on

for k = 1:length(lines)

    xy = [lines(k).point1 ; lines(k).point2];

    plot(xy(:,1), xy(:,2), 'LineWidth', 4, 'color', 'red');

end

结果: