数字图像中的Hough变换应用--直线检测

1、沈阳理工大学数字图像处理课程设计摘 要为能够有效解决实时直线图形提取问题，提出了一种基于Hough变换(HT)的直线提取算法。它所实现的是一种从图像空间到参数空间的映射关系。由于具有一些明显优点和可贵性质，它引起了许多国内外学者和工程技术人员的普遍关注。由于其根据局部度量来计算全面描述参数，因而对于区域边界被噪声干扰或被其他目标遮盖而引起边界发生某些间断的情况，具有很好的容错性和鲁棒性。多年来，专家们对Hough变换的理论性质和应用方法进行了深入而广泛的研究，目前应用于生物医学、自动化和机器人视觉、空间技术和军事防御、办公自动化等各个方面。本次课称设计首先分析了数字图像中直线边缘的三种结构特征

2、，提出采用基元结构表示目标边缘点，并在约束条件下计算基元结构的基元倾角。在此基础上，结合传统的HT的思想对基元结构进行极角约束HT，以获得最终的直线参数。最后，再用MATLAB软件对该算法进行编程仿真。实验结果表明，对合成图像和自然图像，该算法能够有效的识别图像中的直线段。关键词：直线提取；Hough变换；MATLAB 2目 录1. 课程设计的目的12. MATLAB简介及应用12.1 MATLAB简介12.2 MATLAB应用12.3 MATLAB特点23. Hough变换原理23.1 Hough变换的基本原理23.2 Hough变换的不足之处43.3 Hough变换的应用44. Hough

3、变换检测直线设计54.1 Hough变换检测直线基本原理54.2 Hough变换的几种基本算法64.3 Hough变换算法的比较与选择74.4 Hough变换检测直线的算法流程图94.5 Hough变换检测直线算法的实现95. 仿真结果及分析115.1 仿真结果115.2 结果分析14结论15参考文献162数字图像中的Hough变换应用直线的检测1. 课程设计的目的本次课程设计的目的在于提高发现问题、分析问题、解决问题的能力，进一步巩固数字图像处理系统中的基本原理与方法。熟悉掌握一门计算机语言，可以进行数字图像的应用处理的开发设计。综合运用MATLAB软件实现图像高通滤波程序设计最终达到以下目

4、的：1) 通过课程设计把自己在大学中所学的知识应用到实践当中。2) 深入了解利用Matlab设计FIR数字滤波器的基本方法。3) 在课程设计的过程中掌握程序编译及软件设计的基本方法。4) 提高自己对于新知识的学习能力及进行实际操作的能力。锻炼自己通过网络及各种资料解决实际问题的能力。2. MATLAB简介及应用2.1 MATLAB简介MATLAB 是美国MathWorks公司出品的商业数学软件，用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，主要包括MATLAB和Simulink两大部分。MATLAB是矩阵实验室（Matrix Laboratory）的简称，和Ma

5、thematica、Maple并称为三大数学软件。它在数学类科技应用软件中在数值计算方面首屈一指。MATLAB可以进行矩阵运算、绘制函数和数据、实现算法、创建用户界面、连接其他编程语言的程序等，主要应用于工程计算、控制设计、信号处理与通讯、图像处理、信号检测、金融建模设计与分析等领域。2.2 MATLAB应用MATLAB 产品族可以用来进行以下各种工作：1) 数值分析2) 数值和符号计算3) 工程与科学绘图4) 控制系统的设计与仿真5) 数字图像处理 技术6) 数字信号处理 技术7) 通讯系统设计与仿真8) 财务与金融工程MATLAB 的应用范围非常广，包括信号和图像处理、通讯、控制系统设计、

6、测试和测量、财务建模和分析以及计算生物学等众多应用领域。附加的工具箱（单独提供的专用 MATLAB 函数集）扩展了 MATLAB 环境，以解决这些应用领域内特定类型的问题。2.3 MATLAB特点此高级语言可用于技术计算1) 此开发环境可对代码、文件和数据进行管理2) 交互式工具可以按迭代的方式探查、设计及求解问题3) 数学函数可用于线性代数、统计、傅立叶分析、筛选、优化以及数值积分等4) 二维和三维图形函数可用于可视化数据5) 各种工具可用于构建自定义的图形用户界面6) 各种函数可将基于MATLAB的算法与外部应用程序和语言（如 C、C+、Fortran、Java、COM 以及 Micros

7、oft Excel）集成7) 不支持大写输入，内核仅仅支持小写。3. Hough变换原理3.1 Hough变换的基本原理Hough变换是一种使用表决原理的参数估计技术。其原理是利用图像空间和Hough参数空间的点线对偶性，把图像空间中的检测问题转换到参数空间。通过在参数空间里进行简单的累加统计，然后在Hough参数空间寻找累加器峰值的方法检测直线。Hough变换的实质是将图像空间内具有一定关系的像元进行聚类，寻找能把这些像元用某一解析形式联系起来的参数空间累积对应点。在参数空间不超过二维的情况下，这种变换有着理想的效果。Hough变换的实质是将图像空间内具有一定关系的像元进行聚类，寻找能把这些

8、像元用某一解析形式联系起来的参数空间累积对应点。在参数空间不超过二维的情况下， 这种变换有着理想的效果。但是，一旦参数空间增大，计算量便会急剧上升，同时耗费巨大的存储空间，耗时也随之猛增。就此，多年来国内外众多学者针对具体情况对常规Hough变换进行了多方面的探索，并提出了许多有价值的改进方法：1） 扩展应用范围，提出多种参数化的方法在早期的研究中，Hough变换由只检测图像中的直线扩展到检测圆弧、二次曲线和任意曲线构成的形状；线条的参数化方法也由最初的截距型参数发展到斜率倾角和截距型参数、双Hough空间型参数、以及检测圆的圆心坐标、半径型参数和检测物体复杂形状的基于模板的多维关键点参数等。

9、2） 提高实用性，提出多种减少计算量的算法针对Hough变换计算量大的不足，相继提出了四分树结构的Hough变换、以梯度信息为引导的Hough变换、分层Hough变换、自适应Hough变换、快速自适应Hough变换、随机Hough变换（RHT）等；对于高维Hough变换采用降维处理，数据结构多采用动态量化空间等。3） 增强抗干扰能力，提高检测精度Hough变换提取精度问题始终受到普遍关注，例如Hough变换的离散化误差、混叠干扰、抗噪声干扰性能等。就此类问题的研究例如，Kiryati、Buckstein提出采用最佳Kaider窗函数对参数域进行平滑滤波以减少混叠误差；Hunt、Nolte等人应

10、用信号检测理论对Hough变换的抗干扰性能和基于最大后验概率的最佳算法进行了抗干扰性能比较，并指出了影响Hough变换抗干扰性能的原因。4） 多种峰值检测方法Hough变换中参数空间的峰值检测是一个聚类检测问题，阈值的选取是成功与否的关键所在。其中，一种方法是对图像空间进行加权，以改变参数空间的峰值分布；一种方法是直接对参数空间进行极大值的搜索。3.2 Hough变换的不足之处本课题的研究内容，如上所述，常规Hough变换虽然具有显著的优势，但其不足也不容忽视，如不加改进，有时将会令人无所适从，例如检测速度太慢，无法做到实时控制；精度不够高，期望的信息检测不到反而做出错误判断，进而产生大量的冗

11、余数据。就圆检测而言，常规Hough变换的不足主要有以下几点：（1）参数由直线的两个参数，即截距和斜率，上升到三个，即圆心坐标和半径，每个点映射成参数空间的一个曲面，是一到多映射，因而计算量急剧增大；（2）需要占用大量内存空间，耗时久、实时性差；（3）现实中的图像一般都受到外界噪声的干扰，信噪比较低，此时常规Hough变换的性能将急剧下降，进行参数空间极大值的搜索时由于合适的阈值难以确定，往往出现“虚峰”和“漏检”的问题。3.3 Hough变换的应用理论与实践向来是形影不离，相辅相成，Hough变换之所以有如此长足的发展，主要原因还是在于实践应用上的广泛需求；而在实践中所暴露出的不足又进而促进

12、了它的发展，循环往复，就如同生命的演化。现枚举其主要应用领域如下：1） 生物医学： Hough变换已被成功应用于基于人工智能的专家诊断系统；X射线人体照片和CT图像的处理和判读；光学显微镜和电子显微镜中的细胞核自动分析系统；从超声波诊断中提取三维动脉特征，等等。2） 自动化和机器人视觉: Hough变换已被用于产品部件的自动监视、缺陷诊断、生产过程的自动监控、计算机辅助制造（CAM）等。例如基于Hough变换的机械零件检测和定位系统；基于Hough变换采用直线、圆弧等作为基本特征的工业产品检查系统;3） 空间技术和军事防御: Hough变换已被用于运动目标轨迹的检测与识别，高空侦察机、间谍卫星

13、和军事雷达等目标自动识别系统的特征提取。例如应用Hough变换对战斗机的外形特征进行提取和自动识别；应用Hough变换辅以信号检测理论解决并行多运动目标的跟踪问题。4） 办公自动化: Hough变换在许多应用系统中得到了很好的应用。例如采用Hough变换进行英文字符特征提取并自动识别，其对印刷体字符识别率为99.6%，对手写体字符的平均识别率也达到了86.9%，并已成功应用于邮政信件的自动分拣、文件处理等。由以上分析可见，Hough变换有着广泛的关注程度以及良好的应用前景。在计算机视觉和自动目标识别系统中，Hough变换是一个用于边缘线条特征提取的强有力工具。4. Hough变换检测直线设计4

14、.1 Hough变换检测直线基本原理Hough变换检测直线就是选取图像空间中一条直线L的某些特征，作为参数空间的一个点M，并且该直线L上所有点，通过某种算法，都能够对应着这些特征 ，从而在图像空间和参数空间之间建立起“线点”的对偶性。Hough变换就是根据这种对偶性，将图像空间中直线的检测问题，转化为参数空间中点的检 测问题,而后者的处理比前者要简单得多，进行累加统计即可。下图4.1给出了数字图像中三类直线的结构分布情况，图中一个小方格代表一个像素，黑方格代表边缘像素点，白方格代表背景像素点。可以看出，近水平直线段由相距很近的行基元集合组成；近垂直直线段由相距很近的列基元集合组成；近45

15、76;直线依据其斜率分别由45°或135°扫描线上的斜基元集合组成。综上可知，任何直线段都可以表示为总体走向趋势基本一致且缝隙很小、相距很近的相应基元的集合。以此结构特点为基础建立本文的直线提取方法。图4.1数字图像中直线的分布4.2 Hough变换的几种基本算法常用的Hough变换检测直线的方法，是运用下式在图像空间和参数空间之间，建立对偶变换。 = x cos + y sin （4.1） （a）直角坐标系 （b）参数空间图4.2 Hough变换示意图在式（4.1）中，为极径；为极角，取 0 180 °；x为像素点相对图像原点的行坐标；y 为像素点相对图像原点的

16、列坐标。对偶变换示意图如图4.2所示。为了检测出直角坐标系中，由非零点所构成的直线，需要根据检测分辨率的要求，将离散化为N个参数区间，将离散化为N个参数区间，也就是说将极坐标系量化成许多小格，建立参数空间。这种方法被称为标准 Hough变换方法 ( standard hough transform，SHT)。 其优点是：无论直线怎样变化,参数空间中和的取值范围是有限的。所以，目前的直线检测大多数都是基于这种方法。 但是，这种方法在N值较大的情况下，存在以下两个缺陷：( 1 ) 计算量大 N越大，的步长越小，计算量就越大。在要求检测精度很高的场合，N的值往往非常大，这样会使计算量大增。 ( 2

17、) 需要大的存储空间 如果和都占 4 个字节，参数空间所需要的存储空间的字节数S 可由下式求出 : S = 4 NN （4.2）图4.3 Hough变换从图像空间到参数空间的转换在式（4.2）中，N为在 0，) 间取的离散值的个数；N为的采样个数。对较大的图像，S将大于数兆字节 ( G B )，单靠物理内存，难以满足这样的要求。为了减少这种 Hough 变换的计算量，减小所需要的存储空间，在此基础上出现了很多改进的Hough 变换算法，例如分块检测法、两次检测法、全整数 Hough变换等，为讨论方便，将其统称为正弦 Hough 变换方法。但这些方法由于受的步长限制，有时候检测结果不尽人意，难以

18、实现对任意斜率直线 的快速、精确检测，尤其是对超大型图像（例如像素在2048×2048 以上）。如果能够建立一个不受步长限制的参数空间，就有可能实现对任意斜率直线的快速、精 确检测。其中，Hough变换从图像空间到参数空间的转换如图4.3所示。4.3 Hough变换算法的比较与选择图像空间中，直线 L0 : y=k0x+b0 上每一个点，在参数空间中都代表一条直线，这些直线都相当于一点 M ( k0，b0)。与用极坐标建立参数空间的方法相比，这种方法不受的步长限制，检测了所有的可能出现的直线，不会有任何遗漏，在像素允许的情况下，能精确地检测出图像中的任意直线。这种 优点决定了它非常适

19、合用来对直线进行精确检测。为便于讨论，将其称为kb Hough变换方法。虽然这种方法在原理上非常明确，但在具体实现过程中，如 果简单地用浮点数进行斜率和截距的计算，还有以下 3个问题需要解决：( 1 ) 如果同时计算斜率和截距，参数空间结构数组可能异常庞大，而且计算量非常大。一幅像素为m×n的图像，假设图像中可能出现的不重复的斜率有 u种( u大于图像的像素总数 )。若这些数据都占4个字节，那么要求的计算机内存为： W=8umn （4.3）对较大的图像，要求的计算机内存超过上千兆字节(GB)，这显然是不现实的。如何解决这个问题？很多时候，如果将一个2维问题分解为两个1维问题来解决，往

20、往非常方便。参数空间数组之所以异常庞大，是因为同时包含了待测的斜率和截距，而斜率和截距的组合，决定了其数组的元素个数必然非常多。如果将斜率 k和截距b分步进行检测，先检测斜率，找出出现次数最多的斜率 k0，然后再检测截距，找出斜率为k0的，出现次数最多的直线的截b0，也就是说，将一个2维问题分解为两个1维问题。 由于斜率为k0的二点对的数量往往非常有限，这样就能有效地减小参数空间。但是，即使将斜率k和截距b分步进行检测，如果用浮点数进行计算斜率，并采用普通的Hough变换的投票方式，即先计算完由非零点组成的所有的二点对的斜率，再对斜率进行统计，也可能需要很大的参数空间。1幅800×6

21、00的图像，如果非零点非常多，需要的参数空间仍然可能超过数千兆字节( GB )。所以，用浮点数计算斜率，要减小参数空间，只能一边计算斜率，一边统计斜率相同的情况( 与前面的斜率进行比较 )。 即边投票，边计票。但是，这样计算量非常大。( 2 ) 程序的复杂程度高 根据定量度量程序的复杂程度的McCabe方法，流图 (也称为程序图) 的环形复杂度可由下式求出 : V(G) = R + 1 （4.4）在式（4.4）中，V ( G)为环形复杂度；R为流图中的判定节点数目。通常V ( G)10 为宜。根据McCabe方法求出该方法的流图的判定节点数R为10， 由式( 3 )可知，其环形复杂度为11，显

22、然复杂程度太高。 ( 3 ) 如果直接采用浮点数计算斜率，无法处理斜率为无穷大的垂直直线斜率为无穷大，给计算带来不便，这正是极少有人采用这种方法的原因。 综上所述，除了需要分步检测斜率和截距外，还不能简单地采用浮点数计算斜率。 因此采用了斜率分式查表方法来解决这些问题。4.4 Hough变换检测直线的算法流程图原始输入的彩色图像 变换得到灰度图像提取灰度图像边缘Hough变换得到变换矩阵图像计算检测图像中的直线计算标注出最长直线图4.4算法流程图4.5 Hough变换检测直线算法的实现clearI = imread('abc.jpg');%输入原图像I = rgb2gray(I

23、);%将输入的彩色图像转换成灰度图像输出%I = imrotate(I,33,'crop');% figure% imshow(rotI);figureimshow(I);BW = edge(I,'canny');%提取图像边缘figureimshow(BW);H,T,R = hough(BW);% 计算二值图像的标准霍夫变换，H为霍夫变换矩阵，theta,rho为计算霍夫变换的角度和半径值 figureimshow(H,'XData',T,'YData',R, 'InitialMagnification',

24、9;fit');xlabel('theta'), ylabel('rho');axis onaxis normalhold onP = houghpeaks(H,5,'threshold',ceil(0.3*max(H(:);%在Hough矩阵图像中寻找前5个大于最大值0.3倍的峰值x = T(P(:,2); y = R(P(:,1);plot(x,y,'s','color','white');% Find lines and plot themlines = houghlines(BW,T

25、,R,P,'FillGap',5,'MinLength',7); %找出图中的直线figure,imshow(rotI),hold on  figure, imshow(I),hold onmax_len = 0;for k = 1:length(lines) xy = lines(k).point1; lines(k).point2; plot(xy(:,1),xy(:,2),'LineWidth',2,'Color','green'); % % 绘制线的起点（黄色）、终点（红色） plot(

26、xy(1,1),xy(1,2),'x','LineWidth',2,'Color','yellow'); plot(xy(2,1),xy(2,2),'x','LineWidth',2,'Color','red'); % 计算线的长度，找最长线段 len = norm(lines(k).point1 - lines(k).point2); if ( len > max_len) max_len = len; xy_long = xy; endendplot(xy_

27、long(:,1),xy_long(:,2),'LineWidth',2,'Color','blue'); 5. 仿真结果及分析在MATLAB7.1环境运行程序源代码，对输入彩色图像通过变换得到灰度图像，并进行边界提取、Hough变换和直线检测，得到如下结果。5.1 仿真结果如图5.1，输入图像为一幅后缀为jpg格式的彩色图像，在matlab程序代码中首先使用imread（）函数将图像读入，以便于后续的处理和操作。 图5.1原图像由图5.2可知，输入图像为一幅彩色图像时，可以使用rgb2gray（）函数，先将彩色图像转换为灰度图像（RGB不发生变

28、化），使图像适合于边界提取，为下一步做准备。 图5.2灰度图像由图5.3可知，采用edge（）函数，对灰度图像进一步进行处理，将图像的边缘地方的像素值设为1，其余地方的像素设为0，可以得到图像的边界，且提取出的图像边界清晰完整。 图5.3边界图像由图5.4可知，可以采用hough（）函数对边界图像进行Hough变换，并绘制出Hough变换得到的变换矩阵坐标图，其中在峰值为520时，标注出的5个点为前5个大于最大值0.3倍峰值的点。 图5.4 Hough变换图像由图5.5可知，在Hough变换后的矩阵中选出前5个大于最大值0.3倍峰值的点，并将这些点用“x”标出后，便可简单地绘制线的起点（用黄色

29、表示）、终点（用红色表示）并检测出直线；最后通过计算，使用蓝色线段标注出最长的线. 图5.5直线检测图像5.2 结果分析本次课程设计原始的输入图像为一幅彩色图像，并采用了如下算法：首先，在matlab代码中可用imread（）函数将其读入；然后，为了便于处理，需要采用rgb2gray（）函数，将其从彩色图像变换为灰度图像，使其适合于边界的提取；得到灰度图像后，采用Canny边缘检测算子进行边界提取，在代码中输入BW = edge(I,'canny')；即可实现，其中I为变换得到的灰度图像；对于提取边缘后的图像，应对其进行Hough变换，得到Hough变换矩阵，直接采用hough（）函数即可实现；最后，计算检测图像中的直线，将图像中的直线以及直线的起始点一一标出，对于最长的直线可用不同于其他颜色的直线标出，这里普通直线采用绿色直线标注，最长的直线采用蓝色直线标注。通过对图