直线检测论文20487 (2).doc

《直线检测论文20487 (2).doc》由会员分享，可在线阅读，更多相关《直线检测论文20487 (2).doc（47页珍藏版）》请在三一文库上搜索。

1、直线检测是计算机视觉和模式识别中最重要的任务之一。直线是图像的重要特征，直线特征提取方法的研究对图像的理解、模式识别有重要的意义。文章首先介绍了直线检测的研究状态，并对比了当前几种主流的直线检测方法。然后针对具有经典意义的基于Hough变换的直线检测进行了详细的说明，并介绍了其几种改进算法。最后，编写了一款基于Hough直线检测和对比的软件方便读者更加深刻的理解Hough算法。关键词：直线检测，Hough变换AbstractLine detection has become one of the most important tasks in computer vision and patte

2、rn recognition. The research of the algorithm of extracting straight lines is meaningful to the understanding and recognition of a graph because the line is the major character to a graph. In the paper, it shows the trend and method in line detection in this situation, and it tell us the details how

3、 to design the Hough transform then it achieves and contrasts some line detection which are based on the Hough transform.Keyword: Line detection, Hough transform第1章 引言目录第1章 引言11.1 图像工程与直线检测11.2 图像检测技术发展历史及现状11.3 课题的难点3第2章 直线检测算法42.1 Hough直线检测算法42.2 Freeman直线检测算法52.3 尺蠖蠕行算法92.3.1 尺蠖蠕行的过程和环境102.3.2 基本

4、原理11第3章 Hough算法的改进和实现133.1 编程环境的搭建133.1.1 OpenCV133.1.2 Microsoft Visual Studio133.1.3 环境搭建143.2 Hough算法的改进163.2.1 Randomized Hough Transform(RHT)163.2.2 RHT-LSM173.2.3 PCA-HT183.3 经典Hough算法的实现203.3.1 获取图片类（GetBMP）233.3.2 获得直线类（GetLine）283.3.3 图像输出类（OutputBMP）323.4 软件效果展示363.4.1 软件结果展示363.4.2 直线检测效果

5、363.5 经典Hough算法的性能39第4章 结束语42参考文献43致谢44外文资料原文46外文资料译文49第1章 引言1.1 图像工程与直线检测图像工程将图像技术发展过程中出现的各种新理论、新方法、新算法、新手段、新设备等进行综合研究和集成应用的一个整体框架，可分为3个层次1：1) 图像处理（Image Processing） 强调在图像之间进行的变换，狭义上的图像处理主要满足对图像进行各种加工以改善图像的视觉效果并为自动识别打下基础，或对图像进行压缩编码以减少所需存储空间或存储时间、传输通路的要求。图像处理是图像工程最底层的操作，主要在图像像素级上进行处理，处理的数据量非常大。 2) 图

6、像分析（Image Analysis） 图像分析是对图像中感兴趣的目标进行检测和测量，以获得目标的客观信息从而建立对图像的描述。图像分析是一个从图像到数据的过程。这里的数据可以是对目标特征测量的结果，或是基于测量的符号表示，其主要是以观察着为中心研究客观世界。图像分析是图像工程中层的操作，分割和特征值提取把原来以像素描述的图像转变成比较简洁的非图形式的描述。3) 图像理解（Image Understanding） 图像理解进一步研究图像中各目标的性质和它们之间的相互联系，并得出对图像内容含义的理解以及对原来客观场景的解释，从而指导和规划行动。图像理解在一定程度上是以客观世界为中心，借助知识、经

7、验等来把握整个客观世界(包括没有直接观察到的事物)。图像理解是处于图像工程最高层的操作，基本上是对从描述抽象出来的符号进行运算，其处理过程和方法与人类的思维推理可以有许多类似之处。 直线段的检测属于图像分析阶段，对其研究的意义在于：直线段是图像的基本组成元素，任何图形微观上都是由直线段组成；直线段的检测为图像分析阶段中更高层的处理诸如目标的表达提取和识别提供数据支持，它的影响可以达到图像理解阶段。在实际应用中，道路识别、建筑物识别、医学图像分析、航空和卫星图像分析等领域都需要借重于直线检测技术。1.2 图像检测技术发展历史及现状 图像检测作为图像分析技术的一个研究内容，它也是伴随着数字图像处理

8、的发展而发展的。数字图像处理这门学科的形成也是和社会生产力发展的需要分不开的。早期的图像处理是由于通讯方面的要求而发展起来的，这就是本世纪20年代传真技术的发明和发展。其后，则是由于宇宙方面的要求，需要处理大量的宇宙探测器上拍摄下来的不清楚的其他天体(如月球、火星等)以及地球本身的照片。然而，图像处理技术的发展，远远突破了这两个领域，到今天，它已经广泛的应用到科学研究、工农业生产、军事技术、政府部门、医疗卫生等许多领域，进一步推动着社会生产力的发展。图像检测是图像分析研究内容的一部分。目前，在图像分析领域已经有很大的发展。图像分析是一种从一幅图像中通过自动的或半自动的方法提取图像尺寸、数据或信

9、息的方法。图像分析方法通常因图像分析系统最后的输出是数字而不是画面，使它与其他类型的图像处理方法，如编码、恢复、放大等不同。图像分析源于经典的模式识别方法，根据定义，分析系统并不局限于对一个固定数量类别的场景区域的分类，而是更倾向于可设计成用于描绘复杂场景。根据事先预测，该场景的种类可能是非常多的和不确定的。目前，图像分析领域主要包括形态学图像处理、边缘检测、图像特征提取、图像分割、形状分析、图像检测和配准等几个方面的内容2：(1)形态学图像处理：它的基本概念可以追朔到Mnikowski对空间集合代数的研究和Matheron对拓扑的研究。形态学图像处理是这样的一种处理类型，它对图像中的物体的空

10、间形态或结构进行修改。膨胀、腐蚀和骨架化是三种基本的形态学计算。(2)边缘检测：一幅图像的振幅属性(如亮度或三色值)的变化或突变是对图像进行描述的重要特性，因为它们常指示图像中物体的物理特性。从一个层面到另一个层面的图像亮度的局部突变叫亮度边缘。对于亮度图像中的边缘检测、直线检测和点检测有两类近似方法：微分检测和模型拟合。(3)图像特征提取：图像的特征是指图像显著的基本特征或特性。一些图像是其本质的特性，在一定程度上这样的特征可以从视觉上分辨出来，另一些则是通过某些变换产生的人为特征。本质特征包括像素区域和灰度纹理区域的亮度。(4)图像分割：图像分割法使图像被划分成或分隔成具有相近特征的区域。

11、对于图像分割法，其最基本的特征是:单色照片图像的亮度振幅和彩色图像的彩色因素。图像边缘和纹理也是对分割法很有用的特征。(5)形状分析：目前已经提出了几种定性的和定量的方法来描述图像中物体的形状，这些方法对于在模式识别系统中对物体进行分类和在图像理解系统中象征性的描述物体是很有用的。在这些方法中，有一些只能应用在二进制图像中，另外的一些则可以被扩展到灰度图像中。(6)图像检测和配准：图像检测主要是确定位于图像内被猜测的物体是存在还是不存在的。而图像配准主要是涉及到一对图像区域的空间配准问题。在一个图像区域中，物体检测的一种最基本方法是通过模板匹配来进行。在目前的实际应用中，广泛的利用Hough变

12、换来进行圆形或椭圆性的物体检测。1.3 课题的难点传统的Hough 变换法首先是运算量大,由于对所有源像素点都要进行无差别的Hough 转换运算,对像素较大的图像进行转换时相应的计算时间也太长。传统的Hough 变换法最主要的缺陷在于它会将中断的直线无差别地连接起来,在某些场合有助于修补图像,但是对源数据处理阶段会产生错误的数据,导致了与源图像的偏差。第2章 直线检测算法第2章 直线检测算法直线检测现在已经成为计算机视觉中的一个研究重点，近年来许多学者就这一领域展开了广泛研究并提出了许多直线检测算法。目前直线检测算法主要可以分为以下几类：1） Hough变换法2） 相位编组法3） 链码检测法

13、以下将就直线检测中的一些经典和高效算法进行原理的介绍。2.1 Hough直线检测算法Hough算法及其改进算法是利用坐标域变换的代表3。此类算法的优点是抗干扰能力强，对图像中的噪声不敏感。但是由于其算法特点使得其时间复杂度和空间复杂度都很高，并且在变换过程中丢失了线段的长度信息。 Hough 变换的基本思想是点线的对偶性。一方面,图像空间中共线的点对应在参数空间里相交的线;另一方面,在参数空间中相交于同一个点的所有直线在图像空间里都有共线的点与之对应。因此Hough 变换把在图像空间中的直线检测问题转换到参数空间中对点的检测问题,通过在参数空间里进行简单的累加统计完成检测任务。如果参数空间中使

14、用直线方程,当图像空间直线斜率为无穷大时,会使累加器尺寸和变很大,从而使计算复杂度过大。为解决这一问题,采用直线极坐标方程,变换方程下所示。 = xcos+ ysin （2-1）根据这个方程,原图像空间中的点对应新参数空间中的一条正弦曲线,即点- 正弦曲线对偶。检测直线的具体过程就是让取遍可能的值,然后计算的值,再根据和的值对累加数组累加,从而得到共线点的个数。下面介绍和取值范围的确定。设被检测的直线在第一象限, 右上角坐标为( m , n) , 则第一象限中直线的位置情况如图2-1所示。 图2-1 检测位置图由图可见,当直线从与x 轴重合处逆时针旋转时,的值开始由0增大,直到180,所以的取

15、值范围为0 180。由直线极坐标方程可知： （2-2）由、的取值范围和它们的分辨率就可以确定累加器的大小, 从而检测直线。2.2 Freeman直线检测算法Hough由于其应用广泛和简洁获得了很大程度上的认可，但同时有学者对Hough算法的低效率和高空间占用并不满意，而且在Hough变换时直线将丧失其长度和具体位置的问题也令一些学者不满意。于是，他们提出了改进的方案。与Hough算法通过坐标转换的方式不同，改进的方案更倾向与从直线的直接特征中寻找突破点。Yuan 等提出了一种在链码中检测直线的算法。该算法从起始链码开始,对每一链码确定一个直线穿行区域以及两条用于确定下一链码是否属于同一直线的上

16、下边界线。如果下一链码位于上下边界线之内,则该链码与上一链码属于同一直线;否则该链码属于另一直线。由于该算法仅对目标的边界链码进行处理, 因此其算法的复杂度较小, 为O ( n) ,其中n 为边界链码的个数。但该算法在跟踪得到每一链码时需确定下一直线链码的存在范围,这是一比较耗时的过程,利用数字直线的特征可以简化该过程。计算机处理的图像是经过采样、量化等数字过程后形成的离散图像,离散空间中的直线呈现出连续空间的直线所不具备的一些特征。Freeman 总结了这些特征并提出了数字直线的链码应遵循的三条准则(简称Freeman 准则)4: 1) 一条数字直线的8邻域链码中最多包括两个方向,其中一个为

17、主方向,它是决定直线方向的主要因素; 2) 这两个方向的链码值相差为1 (mod 8) ; 3) 主方向上链码值相同的连续像素组成一个线段子元,除去第一个和最后一个线段子元,其余各线段子元的长度至多相差一个像素。Freeman算法直接从直线的特征找到突破点，通过比对直线的特征从而就可以找出隐藏在图像中的直线。这为从多的学者从迷茫中指明了方向，一些比较经典的基于Freeman准则的想法被相继提出。其中最有里程意义的应该是Chan 等提出一个基于Freeman准则直线检测算法。该算法完整而全面的理解了Freeman准则，并且在现实上并不困难。该算法的具体思想如下：首先跟踪线段子元,然后根据两相邻线

18、段子元间的偏转角度确定这两线段子元是否相似,最后若两子元相似则连接两线段子元。该算法的计算复杂度为O( n) , n 为目标边界像素的数目。虽然该算法与Yuan 等算法的计算复杂度相同,但该算法在跟踪得到一个线段子元后才进行偏转角度的计算,因此,该算法比Yuan 等算法更高效5。首先我们需要定义一个新概念：量化方向子集（Quantized Directional Subsets，下文简称QDSs），在对一个图像进行数字化之后，一条连续的直线段将成为一系列短直线段的集合，而这些短直线段被定为在八个等同的量化方向上，如图2-2所示。 图2-2 像素的量化定位这些具有相同的方向而长度不同的短直线段被

19、成为量化方向子集（QDSs）。对于一个数字化直线任意的QDSs，可能存在不同长度的短直线和相同长度的短直线，我们称为量化方向元素（Quantized Directional Elements，下文简称QDEs）。现在我们来考虑下一条数字化直线段的参数方程式为l1：y=a*x+b并且其终点为P1（x1，y1）和PN（xN，yN）。我们已经定义了QDEs，而且可以认为一条数字化直线就是那些处在不同x，y坐标占一个像素点QDE的QDEs。最初的拥有QDEs联系的数字化已经划分完全了。为了不失广泛性，现在考虑tan-1/8（注意：主要QDS在方向0上）和主要点序列q（在主要QDE上像素的数目）QDEs

20、的结束点： （2-3）同样的具有以下等式：, （2-4）.i是第i个点和（xqn，yqn）=（xn,yn)的公差。 QDEs混合的情况如下：, （2-5）因此，第n个直线段和第n-1个直线段之间推导的夹角方程式是： （2-6）i被定义为数字化直线的定位的推导结果。相同的结果可以推论到其他的方位。明显的，取值n将从0直到无穷。我们现在可以得到一个推论：一条数字化直线角度的变化趋势将会趋于稳定（注意：更多的相同数字化直线的QDEs被连接）。这个收敛的特性对决定QDEs的连接是非常有用的（注意：如果和之前一个QDE的推导结果小于临界值，QDE将会被连接）。通过以上的补充定义我们可以方便的提出chan

21、关于Freeman准则的算法实现。整个算法分为3步：1） QDE（s）的存储 在遍历所有的QDEs之后，检查每一个直线段能否和上一个直线段连接。如果不能连接，我们将认为这个QDE是一个新的直线段。QDE的数据结构将会存储在一个LSL（Line Segment List）的直线段缓冲区（lp）中，储存方式如下：; ; （2-7）; 点（x1，y1）和（xn，yn）代表了每个检测QDE的起始点和结束点。每个像素的QDE将被标记为（line_number）放进缓冲区中。2） 相邻直线段的搜索 一旦一个QDE被检测，它的相邻点将会被以a-b-c-d-e的顺序检测是否存在一条直线段（如图2-3）。在图2

22、-3中，被标记为“1”的是存储在直线缓冲区中的已知的直线段。被标记为“N”的是现在正在追踪的QDE。如果一条直线处于检测状态，我们将按QDEs的近似化准则来判定是否连接。 图2-3 搜索相邻像素的准则3） QDEs的近似化 近似化的QDEs必须满足一下两个条件： 1）一条直线所有的QDEs都小于/4 2）数字化直线现在方位推导结果必须小于临界值， , （2-8） 是一个正实数，x代表当前QDE的公差，其定义为： , （2-9） mi是在第i个时期像素点的个数，q被定义为两个QDEs之间所拥有的最小像素的数目。理论上，x等于1或者0。 如果QDE（s）相似，他们将会同以前已经发现的直线段连接起来

23、。同时，参数也将会更新。Freeman直线检测算法的优点在于其具有较低的计算复杂度，实时性强。此外，由于在直线检测之前首先进行了边界跟踪，因此能比较方便地得到线段的长度、方向等信息。但Freeman直线检测算法的缺点在于，Freeman准则来源于理想数字直线。因此当边界噪声较大时，外观上呈现出直线特征的线段也不能很好的满足Freeman准则。2.3 尺蠖蠕行算法 利用大自然中生物的生活习性，可以巧妙的解决人类社会的许多难题，尺蠖蠕行算法就是一种利用尺蠖蠕行的规律的算法。该算法首先是将图像中的直线检测问题分解成为若干个平行或近似于平行的直线族的检测,然后采用蠕行算法分别检测各组的平行直线6。2.

24、3.1 尺蠖蠕行的过程和环境 尺蠖是一种蛾类的幼虫,善于沿着树枝爬行吃食,其蠕动行进的过程如下: (1) 选择初始目标。尺蠖在寻找食物源时,根据自己的触觉和对重力的感知作用搜索第一个攀援点,然后在向上的邻域内继续寻找下一个攀援点,逐步挪动身体向上攀援。(2) 选择行进方向。尺蠖的整个身体在爬行到一条树枝上之后,根据身体在当前的位置所确定的直线方向向前爬行。若身体正前方没有落脚点,它将在以身体为轴线的小扇形区域内摆动前足寻找下一个落脚点,如图2-4(a) 所示。因此,它对行进方向具有一定的选择性和容错性,从而使其行进轨迹在一定距离内近似为一条直线。图2-4 尺蠖的蠕行行为 (3) 蠕行。尺蠖利用

25、身体的屈伸运动依次带动身体后端和前端的足,从而完成向前的蠕行(图2-4(b) 图2-4(c) ) 。它的身体中间没有足的分布,其身体中部的轴线在爬行平面上的投影始终为一直线段。由于它的身体自身的柔性特性,其前后足间的距离可在一定范围内伸缩,从而在爬行时可跨越一定的距离间隔和障碍,降低了它对爬行路径连续性的要求。当爬行路径上的间隔或障碍超过其身体长度而无法跨越时,尺蠖认为它已经走到了树枝的尽头,从而完成一个搜索过程。 尺蠖蠕行的环境可以是一棵枝桠遍布、纵横交错的树,也可以是一棵棵互相平行的植株(图2-5) 。当它在如图2-5(a) 的树上爬行时,由于树枝的交叉,在某处的行进方向可能有多种选择,其

26、爬行的轨迹将可能偏离原有的直线方向; 在平行的植株(图2-5(b) ) 上爬行时,其行进方向是唯一确定的,从而保持了爬行轨迹的直线方向。图2-5 尺蠖的蠕行环境2.3.2 基本原理 对应于尺蠖的仿生学特点,CCA 在边缘像素子集内检测直线的原理如下: (1) 选择直线的初始搜索点。在选择直线的初始搜索点时,尺蠖是在地面爬行碰到树干时才向上探行。因此CCA 检测直线时也首先从图像的左下角(本文将图像的左下角定义为图像的坐标原点) 开始逐行扫描,搜索图像中的边缘点。当扫描到第一个边缘点时, 将其作为直线的初始搜索点( XS0 ,YS0) ,该点对应于尺蠖在树干上的第一个攀援点。 (2) 直线搜索的

27、方向选择。尺蠖在向前行进时,将根据自身当前的状态来判断行进的方向,将下一个落足点限制在以身体为轴线的小扇形区域内,从而使运动轨迹在身体附近的小区域内近似为一条直线。 在直线像素的搜索过程中,为了减少扫描区域,增加搜索的准确性,同样可以将直线的搜索方向角限定在一定范围内。如前所述,本文根据边缘像素的梯度方向将其划分成为4 个子集,每个子集在梯度方向上的参数空间占据两个关于原点对称的45扇形区域(图4) 。由于边缘走向与梯度方向的垂直关系,当在边缘像素子集中检测直线时,搜索的方向也可以相应的限定在两个45的扇形区域内(其中心线分别与梯度方向参数空间的两个扇区中心线互相垂直) 。由于本文给出的直线初

28、始点的搜索均从图像的左下角开始,直线特征的搜索可限制在直角坐标系的上半个平面,因此直线搜索的方向可进一步限定在一个夹角为45的扇形区域内。图5 (a) 给出了图1 (b) 中矩形框所在直线的搜索方向范围(0 45) 。 (3) 直线特征搜索。尺蠖利用身体的屈伸运动依次带动身体后端和前端的足,从而完成向前的爬行。它的身体中间没有足分布,其身体中部的轴线在爬行平面上的投影始终为一直线段。由于它身体自身的柔性特性,其前后足间的距离可在一定范围内伸缩(0 2。若支持集内为理想直线，那么2=0。根据Freeman准则，数字图像中的直线并非真正的直线，而是成阶梯状。因此，2并不一定等于0。但是，2的取值具

29、有极大的不确定性，所以一般认为为0。然后利用1求的主支持元方向 （3-10） 依上述计算就可求得所有局部方向信息，将其映射到参数空间，进而建立参数空间中参数对应的直方分布图。3） Hough 变换参数局部范围选择 标准Hough 变换在计算的时候把(，)的参数空间细分，并将它们映射到累加器单元中。的取值范围为0-180度。由于有了PCA的统计数据结果，可以对的取值范围进行约束，其范围为： （3-11） 此方法通过的取值范围的约束从而实现了计算时间的降低和存储空间的减少。3.3 经典Hough算法的实现现在，我们将实现一种简单的Hough算法。由于Hough 变换的原理是把在图像空间中的直线检测问题转换到参数空间中对点的检测问题,通过在参数空间里进行简单的累加统计完成检测任务，同时直线检测都是建立在图像的边缘之上的，而往往一般的图像并不是边缘图像。所以要实现一例Hough算法的实现需要经过以下步骤：1） 获取目标图像2） 对图像进行边缘检测3） 由图像具体情况设置累加器大小4） 对图像进行Hough变换并存储结果5） 由累加器决定是否存在直线6） 根据最后结果绘制直线通过以上步骤的实现我们可以首先得知整个系统的系统流程图。系统流程图如图3.1所示。在整个系统中，我们将其划分成为了获取图