霍夫变换（Hough Transform）的原理以及代码实现

第一次在博客上写技术文章总结一下最近所做的，还希望大家多多批评指正。

霍夫变换是一种常用的图像算法，在线状物和圆形物检测等应用中具有很重要的意义。特别地，Hough变换能够较好的克服目标被部分遮挡的情况。因此，在图像检测应用场合中，霍夫变换具有重要的意义。本文首先介绍霍夫变换的基本思想，然后结合matlab代码谈谈具体应用方法，最后给出Hough变换的C++代码并针对检测应用中常常要求的实时性给出一些优化策略。

一、霍夫变换的基本思想

在计算机中，图像一般被表示为二维矩阵$I​$I​。图像中像素$I(x,y)​$I(x,y)​所反映的位置信息即图像像素的空间信息，而像素值则是该空间位置下亮度信息的反映。霍夫变换所针对的是图像中形状特征的检测，所用到的是图像的像素排列的空间信息。所以，霍夫变换输入的图像要求为二值图像（仅反映图像中待检测的感兴趣像素集），一般为阈值变换或边缘检测算子处理后的输出。

下面以霍夫直线检测为例谈谈霍夫变换的基本思想。如图1所示，在图像$I$I中通过像素$I(x,y)$I(x,y)的直线共有$n$n条，那么将这些直线所对应的直线参数映射到由这些直线参数张成的二维参数空间$\{K,B\}​${K,B}​中，可以形成一条曲线。而若将存在直线的二值图像中所有像素点都用类似方法将其对应直线映射到二维参数空间中去，并对参数频次进行统计叠加（类似灰度直方图，但这里参数不再是一维灰度，而是二维直线参数），那么可以形成一簇明暗不均的曲线：曲线上的像素点越明亮，说明该像素对应参数所生成的直线在原图像中通过的感兴趣像素点越多，则该直线为所期望探测的直线概率越大。不难看出，霍夫变换实际上是一种统计投票决策算法，是利用参数空间域中参数“拟合”直线的过程。

图1 霍夫变换思想

根据上述思想，我们不难得到霍夫变换算法的基本流程：

1. 初始化参数空间，将参数空间矩阵每一个像素置0；
2. 遍历图像当中不为0的像素点，记录所有经过该像素点直线的直线参数，将参数空间中对应该直线参数的像素值加1；
3. 根据先验知识，分析参数矩阵，获取参数矩阵某些峰值作为检测结果。

注意到，直线方程所构成的参数空间对竖直方向的直线难以表达（斜率无穷大），且斜率分量难以均匀量化。故在实际应用中，我们一般采用先将直线方程转换为直线极坐标方程，再利用极坐标方程建立参数矩阵的方式避免上述问题。即先将坐标点$(x,y)$(x,y)转化为$(\rho,\theta)$(ρ,θ)，再映射到$\{\Rho,\Theta\}${R,Θ}参数空间。直线的参数方程为
$\rho=x\cos\theta+y\sin\theta$ρ=xcosθ+ysinθ

二、Matlab代码分析

了解基本思想之后，下面来看一下matlab中霍夫变换的实现方法，代码如下¹：

I  = imread('circuit.tif');
rotI = imrotate(I,33,'crop');
BW = edge(rotI,'canny');
[H,T,R] = hough(BW);
imshow(H,[],'XData',T,'YData',R,...
            'InitialMagnification','fit');
xlabel('\theta'), ylabel('\rho');
axis on, axis normal, hold on;
P  = houghpeaks(H,5,'threshold',ceil(0.3*max(H(:))));
x = T(P(:,2)); y = R(P(:,1));
plot(x,y,'s','color','white');
% Find lines and plot them
lines = houghlines(BW,T,R,P,'FillGap',5,'MinLength',7);
figure, imshow(rotI), hold on
max_len = 0;
for k = 1:length(lines)
   xy = [lines(k).point1; lines(k).point2];
   plot(xy(:,1),xy(:,2),'LineWidth',2,'Color','green');

   % Plot beginnings and ends of lines
   plot(xy(1,1),xy(1,2),'x','LineWidth',2,'Color','yellow');
   plot(xy(2,1),xy(2,2),'x','LineWidth',2,'Color','red');

   % Determine the endpoints of the longest line segment
   len = norm(lines(k).point1 - lines(k).point2);
   if ( len > max_len)
      max_len = len;
      xy_long = xy;
   end
end

% highlight the longest line segment
plot(xy_long(:,1),xy_long(:,2),'LineWidth',2,'Color','blue');

变量BW是由Canny算子得到的二值图像，利用hough函数可将二值图像进行霍夫变换，得到H为参数矩阵，T和R分别给出的是角度$\theta$θ （以度为单位）和径向$\rho$ρ 的范围，该代码采用的是默认设置。待变换之后，输出的H参数矩阵如下图2

图2 霍夫变换矩阵显示

之后houghpeaks函数设置大于0.3倍最大H矩阵值为阈值、选取最大5个点作为待提取直线进行H矩阵分析，得到下图3中点5个点作为直线检测结果。

图3 霍夫变换直线检测结果

最后的houghlines则是根据间隔间距等启发式策略，筛选出合适的霍夫变换直线，并存储到结构体数组lines中；之后的循环代码则是对结构体数组中检测到的直线在原始图像上进行绘制，最终得到的结果如图4。

图4 霍夫变换结果显示

三、C++代码简析

根据matlab代码设计方法，我尝试写了C++语言代码。该代码构造了一个霍夫直线检测类来组织代码，代码实现采用纯C语言。下面将简述类中的代码组织方式。

class HoughCheckLines
{
public:
	HoughCheckLines(UCHAR *ucData, int nWidth, int nHeight, int PeaksNum);
	~HoughCheckLines();

	//under - construction

	// reference matlab hough function
	void GenerateHough(); 

	//reference matlab huoghpeaks function
	void GenerateHoughPeaks(int Threshold); 

	// reference matlab houghlines funciton
	void GenerateHoughLines(int GapFillNum, int MinLength); 

	void Houghpixels(int *x, int *y, int peakflag, int *r, int *c);

	int *GetH(){return H;};
	int *GetTheta(){return Theta;};
	int *GetRho(){return Rho;};
	HoughPoint *GetPeak(){return Peaks;};
	HoughLine *GetLines(){return Lines;};


private:
	UCHAR *ImageData;
	int ImageWidth;
	int ImageHeight;
	int PeakNumber;
	int *H;
	int *Theta;//角度制
	int ThetaLength;
	int *Rho; 
	int RhoLength;
	HoughPoint *Peaks;
	HoughLine *Lines;
};

HoughCheckLines类中成员变量包含了输入的图像数据（0~255），图像数据在实际参与运算中将非零值视为感兴趣点，零像素值视为背景；除此之外，在调用该类的构造函数时要求给出输入图像的宽度和高度，以及Hough变换中拟获取的峰值个数。类中数据成员Theta，ThetaLength，Rho，RhoLength分别为Hough变换角度和径向长度的范围数组和长度，Peaks存储的是Hough矩阵峰值参数，Lines存储的是最终所绘制直线的参数。

代码使用类似Mattlab，首先调用构造函数生成该类实例，之后连续分别调用GenerateHough()、GenerateHoughPeaks()、GenerateHoughLines()三个函数完成matlab对应三个函数的运算，之后根据Lines中所得到的数据即为所求。目前代码内GenerateHoughLines函数的阈值操作等启发式方法尚待完善当中。详细的代码请移步我的github项目²中。

四、几点改进思路

霍夫变换作为一种性能良好的直线检测技术具有良好的检测效果。曾经由于其巨量的计算导致其被应用开发者广为诟病，尤其是在实时形状检测任务中往往难以达到实时性。Ding³等人给出了霍夫直线变换实现实时性的一些策略，其中包括：

• 裁剪原始图像，缩小搜索范围
• 平方根，正弦，余弦计算的查表化
• “多尺度”搜索策略，即先对原图抽样数据进行粗搜索定位，再对原图在一定的角度范围内进行搜索

使用了这些策略并配置好参数之后，文献指出在2003年的计算条件下霍夫变换能够保证实时性。因此，在目前的计算条件下，加之应用当中一些先验知识（直线走向，长度等限制）的使用以及一些多线程/并行计算策略，在图像尺寸不太大的情况下，利用霍夫变换完成实时直线检测任务将不难实现。

参考文献

---

1. Matlab Help houghlines： https://www.mathworks.com/help/images/ref/houghlines.html ↩︎

2. ljwcdtj的HoughTransform项目： https://github.com/ljwcdtj/HoughTransform ↩︎

3. Ding M , Fenster A . A real-time biopsy needle segmentation technique using Hough Transform[J]. Medical Physics, 2003, 30(8):2222. ↩︎