[图像处理] 实验笔记系列是以图像处理算法为主的文章专栏，以我在算法研究中的实验笔记资料为基础加以整理推出的。该系列内容涉及常见的图像处理算法理论以及常见的算法应用，每篇博客都会介绍相关的算法原理，代码实现和算法在实际应用中的技巧。 　　本文主要整理自笔者在一项图像处理任务中的直线检测（line detection）部分的笔记资料，采用了基于霍夫变换（Hough Transform）的直线检测算法。文中给出了直线检测常用的算法介绍，论文资料等，以及笔者的实验笔记和实验结果。 　　 　　文章小节安排如下： 　　1）直线检测相关算法 　　2）霍夫直线检测的基本原理 　　3）霍夫直线检测的OpenCV实现 　　4）直线检测的应用 　　 　　

　　霍夫变换（Hough Transform）换于1962年由Paul Hough 首次提出，后于1972年由Richard Duda和Peter Hart推广使用，是图像处理中从图像中检测几何形状的基本方法之一。经典霍夫变换用来检测图像中的直线，后来霍夫变换经过扩展可以进行任意形状物体的识别，例如圆和椭圆。 　　 　　霍夫变换运用两个坐标空间之间的变换将在一个空间中具有相同形状的曲线或直线映射到另一个坐标空间的一个点上形成峰值，从而把检测任意形状的问题转化为统计峰值问题。 　　 　　参考论文： 　　[1] P.V.C. Hough,Machine Analysis of Bubble Chamber Pictures, Proc. Int. Conf. High Energy Accelerators and Instrumentation, 1959. 　　[2] Duda, R. O. and P. E. Hart, “Use of the Hough Transformation to Detect Lines and Curves in Pictures,”Comm. ACM, Vol. 15, pp. 11–15 (January, 1972). 　　 　　

　　Hough直线检测的基本原理在于利用点与线的对偶性，在我们的直线检测任务中，即图像空间中的直线与参数空间中的点是一一对应的，参数空间中的直线与图像空间中的点也是一一对应的。这意味着我们可以得出两个非常有用的结论： 　　1）图像空间中的每条直线在参数空间中都对应着单独一个点来表示； 　　2）图像空间中的直线上任何一部分线段在参数空间对应的是同一个点。 　　 　　因此Hough直线检测算法就是把在图像空间中的直线检测问题转换到参数空间中对点的检测问题，通过在参数空间里寻找峰值来完成直线检测任务。 　　

　　-待续- 　　

　　首先，我们通过实例来解释一下对偶性的意义。 　　1）图像空间中的点与参数空间中的直线一一对应 　　在图像空间x-y中一条直线在直角坐标系下可以表示为： 　　

　　上述为了方便讲解对偶性和霍夫变换的基本原理，我们的参数空间也选择了笛卡尔直角坐标系。但在实际应用中，参数空间是不能选择直角坐标系的，因为原始图像直角坐标空间中的特殊直线x=c（垂直x轴，直线的斜率为无穷大）是没办法在基于直角坐标系的参数空间中表示的。 　　 　　所以在实际应用中，参数空间采用极坐标系ρ-θ，图示如下： 　　

　　化简便可得到： 　　

　　如前所述，霍夫直线检测就是把图像空间中的直线变换到参数空间中的点，通过统计特性来解决检测问题。具体来说，如果一幅图像中的像素构成一条直线，那么这些像素坐标值（x, y）在参数空间对应的曲线一定相交于一个点，所以我们只需要将图像中的所有像素点（坐标值）变换成参数空间的曲线，并在参数空间检测曲线交点就可以确定直线了。 　　 　　在理论上，一个点对应无数条直线或者说任意方向的直线，但在实际应用中，我们必须限定直线的数量（即有限数量的方向）才能够进行计算。 　　 　　因此，我们将直线的方向θ离散化为有限个等间距的离散值，参数ρ也就对应离散化为有限个值，于是参数空间不再是连续的，而是被离散量化为一个个等大小网格单元。将图像空间（直角坐标系）中每个像素点坐标值变换到参数空间（极坐标系）后，所得值会落在某个网格内，使该网格单元的累加计数器加1。当图像空间中所有的像素都经过霍夫变换后，对网格单元进行检查，累加计数值最大的网格，其坐标值（ρ0, θ0）就对应图像空间中所求的直线。 　　

　　优点： 　　Hough直线检测的优点是抗干扰能力强，对图像中直线的殘缺部分、噪声以及其它共存的非直线结构不敏感。 　　缺点： 　　Hough变换算法的特点导致其时间复杂度和空间复杂度都很高，并且在检测过程中只能确定直线方向，丢失了线段的长度信息。 　　 　　

　　OpenCV支持三种霍夫直线检测算法： 　　1）Standard Hough Transform(SHT，标准霍夫变换) 　　2）Multiscale Hough Transform(MSHT，多尺度霍夫变换) 　　3）Progressive Probability Houth Transform(PPHT，渐进概率式霍夫变换) 　　

　　在OpenCV2.1之前的版本，霍夫直线检测函数如下： 　　 　　函数原型：

CVAPI(CvSeq*) cvHoughLines2( CvArr* image, void* line_storage, int method, 　　double rho, double theta, int threshold, 　　double param1 CV_DEFAULT(0), double param2 CV_DEFAULT(0), 　　double min_theta CV_DEFAULT(0), double max_theta CV_DEFAULT(CV_PI));

　　函数说明： 　　cvHoughLines2老版OpenCV的霍夫直线检测函数，通过method参数可以支持三种霍夫直线检测算法，分别是CV_HOUGH_STANDARD、CV_HOUGH_PROBABILISTIC =1、CV_HOUGH_MULTI_SCALE。 　　 　　 　　在OpenCV新版本下，霍夫直线检测算法定义了两个函数：HoughLines、HoughLinesP 　　1）HoughLines：标准霍夫变换、多尺度霍夫变换 　　函数原型：

CV_EXPORTS_W void HoughLines( InputArray image, OutputArray lines, 　　double rho, double theta, int threshold, 　　double srn = 0, double stn = 0, 　　double min_theta = 0, double max_theta = CV_PI ); 　　

　　参数说明： 　　InputArray image：输入图像，必须是8位单通道图像。 　　OutputArray lines：检测到的线条参数集合。 　　double rho：以像素为单位的距离步长。 　　double theta：以弧度为单位的角度步长。 　　int threshold：累加计数值的阈值参数，当参数空间某个交点的累加计数的值超过该阈值，则认为该交点对应了图像空间的一条直线。 　　double srn：默认值为0，用于在多尺度霍夫变换中作为参数rho的除数，rho=rho/srn。 　　double stn：默认值为0，用于在多尺度霍夫变换中作为参数theta的除数，theta=theta/stn。 　　 　　函数说明： 　　HoughLines函数输出检测到直线的矢量表示集合，每一条直线由具有两个元素的矢量（ρ, θ）表示，其中ρ表示直线距离原点（0, 0）的长度，θ表示直线的角度（以弧度为单位）。 HoughLines函数无法输出图像空间中线段的长度，这也是霍夫变换本身的弱点。 　　 　　备注说明： 　　如果srn和stn同时为0，就表示HoughLines函数执行标准霍夫变换，否则就是执行多尺度霍夫变换。 　　 　　 　　2）HoughLinesP：渐进概率式霍夫变换 　　函数原型：

CV_EXPORTS_W void HoughLinesP( InputArray image, OutputArray lines, 　　double rho, double theta, int threshold, 　　double minLineLength = 0, double maxLineGap = 0 ); 　　

　　参数说明： 　　InputArray image：输入图像，必须是8位单通道图像。 　　OutputArray lines：检测到的线条参数集合。 　　double rho：直线搜索时的距离步长，以像素为单位。 　　double theta：直线搜索时的角度步长，以弧度为单位。 　　int threshold：累加计数值的阈值参数，当参数空间某个交点的累加计数的值超过该阈值，则认为该交点对应了图像空间的一条直线。 　　double minLineLength：默认值为0，表示最小线段长度阈值（像素）。 　　double maxLineGap：默认值为0，表示直线断裂的最大间隔距离阈值。即如果有两条线段是在一条直线上，但它们之间有间隙，那么如果这个间隔距离大于该值，则被认为是一条线段，否则认为是两条线段。 　　 　　函数说明： 　　HoughLinesP函数输出检测到直线的矢量表示集合，每一条直线由具有四个元素的矢量（x1, y1, x2, y2）表示，其中(x1, y1)表示线段的起点，(x2, y2)表示线段的终点。 　　HoughLinesP函数可以检测出图像空间中线段的长度。 　　 　　

　　霍夫直线变换是一种用来在图像空间寻找直线的方法，输入图像要求是二值图像，同时为了提高检测直线的效率和准确率，在使用霍夫线变换之前，最好对图像进行边缘检测生成边缘二值图像，这样的检测效果是最好的。 　　 　　1）HoughLines函数 　　代码：