Hough变换原理要点

1、摘要人类对物体的识别最主要是对物体外形的识别，图像的形状检测在图像处理以及模式识别中是十分重要的。HoughHough 变换作为目标形状特征提取的有效方法得到了广泛的应用。但HoughHough 变换算法主要应用于二值图像（即边缘图像），因此在对灰度图像进行 HoughHough 变换前需要对其进行预处理（包括图像的滤波与边缘检测）。图像预处理作为 HoughHough 变换目标检测过程中重要的前期工作，其结果将直接影响检测结果的好坏。文中介绍了图像中常见的两种噪声，对图像的空间域噪声滤波做了一些研究，分析了高斯滤波与中值滤波的局限性，在双边滤波的基础上提由了一种基于多次中值抽取的双边滤波方法

2、，该方法兼顾了空间邻域的相关性和像素强度的相似性，通过伪中值滤波选取强度滤波器的参考像素值，在平滑高斯噪声和椒盐噪声的同时更好地保护了边缘，与针对奥一类特定噪声设计的传统滤波方法相比，该方法能够处理混有混合噪声（高斯噪声和椒盐噪声）的图像，并能够得到很好的滤波效果。同时，本文分析了几种经典的边缘检测算子，用迭代的双边滤波方法代替 CannyCanny 算子中的高斯滤波过程或自适应滤波过程，在一定程度上避免了滤波过程给边缘带来的模糊，得到了更好的边缘检测结果。HoughHough 变换作为图形目标检测的有效方法，能够检测直线、圆、椭圆和抛物线等众多解析图形，广义 HoughHough 变换对该方

3、法做了一些推广，不再受图形解析表达式的限制，通过预先设置的查找表，能够检测任何图形目标。文中对这些方法都做了介绍，并对这些方法做了仿真。由于受到图像空间和参数空间离散化的影响， 以及 HoughHough 变换自身的计算过使得传统 HougHough h变换方法也有一些局限性，比如在高强度噪声下检测的结果不佳，计算量大，存储资源需求大等。文中分析了传统 HoughHough 变换的投票过程，指由传统方法对参数单元进行 1 1 值累加是不合理的，并且传统方法没有区分图像中的噪声点和直线上的点，介于此，提由了基于直线连接度量的 HoughHough 变换，既考虑了图像的全局信息，也考虑了图像中像点

4、邻域的局部信息，使得参数空间中的峰值不再受到噪声的影响，同时也避免了图像中具有线性关系的特征点投票带来的虚假峰值。通过对传统 HoughHough 变换定义方式的修改，提由了基于模板匹配的 HoughHough 变换检测方法，在该方法中，每一个参数单元都确定了图像空间中的一个模板，通过该模板主动搜索图像空间中符合条件的特征点，特征点的个数作为参数单元的值，并记录图像中线段的端点坐标，完成图像中线段的检测与定位，能够节省大量的存储资源。关键词：特征提取；HoughHough 变换 HoughHough 变化检测直线HoughHough 变换的基本思想是利用点一线的对偶性，即图像空间共线的点对应在

5、参数空间里相交的线，反过来，在参数空间中交与同一个点的所有直线在图像空间里都有贡献的点与之对应。在图像空间 X XY Y 中，所有共线的点（x,x,V）都可以用直线方程描述为：y=mcc（3.3.（1 1）其中 m m 为直线的斜率，c c 为截距，同时式（3.13.1）又可以改写为：c-xmy（3.3.（2 2）上式可以看做是参数空间 C-MC-M 中的一条直线方程， 其中直线的斜率为 x,x,截距为V。比较式（3.13.1）和式（3.23.2）, ,可以看由，图像空间中的一点（x,yx,y）对应参数空间中的一条直线，而图像空间中的一条直线又是由参数空间中的一个点（m,cm,c）来决定的。H

6、oughHough变换的基本思想就是将上述两式看作时图像空间中的点和参数空间中的点的共同的约束条件，兵由此定义一个从图像空间到参数空间的一对映射图 3-13-1 体现了这种点一线之间的对偶关系。图 3-23-2（a a）所示图像空间中位于同一直线的点，（b b）所示是图像中直线上的点经式（3.23.2）映射到参数空间中的一簇直线，图像空间中的一条直线上的点经过 houghhough变换后，对应的参数空间中的直线相较于一点，这一点是确定的，确定该点在参数空间中的位置皆可以知道图像中直线的参数。 HoughHough 变换吧在图像空间中的直线检测问题转换到参数空间里对点的检测问题，通过在参数空间里

7、进行简单的累加统计完成检测任务。(a)(a)图像空间中的单点(b)(b)参数空间中的直线图 3 31 1 图像空间中的点与参数空间中的直线对偶示意的直线图 3 32 2 图像空间中的直线与参数空间中的点对偶示意图c c(a)(a)图像空间中位于同一直线上的点(b)(b)参数空间中图 3 33 3 参数空间中的累加数组在具体的计算过程中，需要将参数空间 M MC C 离散化为二维的累加数组，设这个数组为（m,cm,c）, ,如图 3 33 3 所示，同时设mmingmax1 1 和0，*、1 1 分别为斜率和截距的取值范围。开始时置数组 A A 全为零，然后对每一个图像空间中的给定边缘点，让 m

8、 m 取遍mmin,mmax】内所有可能的值，并根据式（3.23.2）算由对应的C。再根据 m m 和 c c 的值（设都已经取整）据 m m 和。的值（设都已经取整）对数组元素 A A（m m, ,c c）=A=A（m m, ,c c）+I+I。累加结束后，通过检测数组 A A 中局部峰值点的位置来确定参数 m m 和 c c 的值。如果直线的斜率无限大（比如 x=ax=a 形式的直线），采用式（3.23.2）是无法完成检测的， 为了能够正确识别和检测任意方向的和任意位置的直线，可以可以用 DudaDuda 和 HartHart 提由的直线极坐标方程来替代（3.13.1）式：P=xcos?y

9、sin二（3.1）如图 3 34 4（a a）所示，图像空间中一条直线 l,l,日为 l l 过原点的垂线与 x x 轴正方向的夹角，p p 为原点到 z z 的距离。这时，参数空间就变为 p p- -8 8 空间，X XY Y 空间中的任意一条直线对应了 p p 一日空间内的一个点，由式(3.3)(3.3)可知，X XY Y 空间内的一点对应了 p p 一 e e 空间中的一条正弦曲线。如果有一组位于由参数 p p 和 e e 决定的直线上的点，则每个点对应了参数空间中的一条正弦曲线， 所有这些曲线必交于点(P,外,如图 3 3一 4 4 所示。(a)(a)图像中位于同一直线上的点中交于一点

10、的正弦曲线图 3 3 一 4 4 极坐标方程下的点一线对偶示意图同样，在计算的过程中需要对参数空间进行离散化，每个单元的中心点坐标为：11-5=(n-/(n=1,2,Ne)-1一n-RAP(n=1,2,N(b)(b)参数空间(3.4)(3.4)其中AeG/Ne,N9为参数日分割段数：AP=n/Np,是参数P的分割段数，L=max （E2）是为图像中的点距原点的距离最大值。具体的计算过程与上文相似，将参数相应的置换即可。利用 HoughHough 变换在图像中检测直线的基本策略就是：由图像空间中的边缘点去计算参数空间中的参考点的可能轨迹，并在一个累加器中给由计算的参考点计数，最后选由峰值。Hou

11、ghHough 变换实质上是一种投票机制，对参数空间中的离散点进行投票，若投票值超过某一门限值，则认为有足够多的图像点位于该参数点所决定的直线上。这种方法受噪声和直线由现间断的影响较小。3.53.5 实验结果与分析标准 HoughHough 变换广泛用于直线的检测，在同一图像上具有多条直线和噪声干扰的情况下，正确识别直线需要注意一下几占：八、1 1）参数空间中只有当计数器的值为局部峰值时，该点的坐标才有可能作为直线的参数，累加数组其他各点的坐标不能作为直线的参数看待；2 2）参数 0 0 的取值范围为0o,0o,88 口夕或一夕 0o,0o,夕口，变换过程中0 0 的离散间隔决定了识别的精度，

12、但 e e 的步长不能过小，这样会引起参数空间的峰值扩散，也会增大 HoughHough变换的计算量；3 3）对于宽度大于 1 1 个像素点的直线，正确地识别不仅需要对 p p 的取值，而且需要对夕的取值加以限制38113913811391。在本节中我们只考虑对 1 1 个像素宽度的直线进行HoughHough 变换检测如图 3 39 9 所示，其中（ ）图含有 6 6 条直线，并且每条直线都有间断，为了分清每条直线在经过 HoughHough 变换后对参数空间单元的累加值，我们对每条直线都加以标记， 直线 1,21,2 是图中较长的两条直线， 直线 a,b,c,a,b,c,d d可以看作是图

13、像中矩形的四条边。（b b）图是（a a）图加入了 5%5%的椒盐噪声，可以通过对（a a）图和（b b）图的 HoughHough 变换检测结果进行比较来考察 HoughHough 变换的抗噪声能力。图（c c）、（d d）分别是图（a a）、（b b）经HoughHough 变换后参数空间中累加单元的累加值效果图，图（c c）中的标号与图（a a）中的标号是一一对应的，可以看由图像中直线段的长度决定了对应累加单元的累加值的大小，图像中的孤立点噪声增大了参数单元中的累加值，但没有改变局部峰值点的位置。图（。）、是通过寻找参数空间中局部峰值点的位置画由来的，分别是（a a）图和（b b）图的

14、HoughHough 变换检测结果，这两个图基本上没有什么差别。因此，HoughHough 变换对图像中的直线由现间断或是噪声具有很强的抵抗能力，但如果我们将图（a a）看成是由多条线段组成的图，而且需要检测到这些线段，标准 HoughHough 变换是无法完成的，因为此时参数空间单元的信息只包括：线段所处直线的参数以及共线点的个数，而无法确定该线段的起始点的位置。在图 3 39(c)9(c)中，a a、b b、c c、d d 四个峰值点分别对应了图像中矩形的四条边，这四个峰值点满足下面的关系：1)1)它们是成对由现的：第一对是 b b 和 d,d,设他们对应的边的倾斜角度为白；第二对是 a

15、a 和 c,c,设他们对应的边的倾斜角度是仇；2)2)两对峰值点在“轴上间隔 9090。,即网-%定900; ;3)3)因为矩形的对边的长度相等，则同一对中的两个峰值的累加值是相同的，即H(a)=H(c)=a。H(b)=H(d)=|b,H为参数单元中累加值，|代表边的长度；4)4)同一峰值对中两点间在P轴上的距离值等于矩形的边长，即|Pa-Pc=b|,我们可以在参数空间中寻找符合上述而检测图像中的矩形轮廓。I1.中 0-7/7/；-.-i i4 4 个关系的峰值点，从1 1S.KI-.aS.KI-.a1,1,W，JJ：*1.,.一L.L.t ti i! !，*-*-c c,Bwfr.ip-.f

16、r.ip-.c-c-. .1.1.一/一3*3* gsgs.-rjJ.-rjJ*bPd=ao变换检测结果图 3 39Hough9Hough 变换检测直线图 3 310(a)10(a)是一副含有单个圆轮廓的合成图像，其中轮廓的边缘厚度为一个像素，(b)(b)是(a)(a)经 HoughHough 变换后在参数空间中的累加值图，在变换的过程中，圆的半径是已知的，此时参数空间的大小与图像空间相同，峰值点所处的位置即为图像中圆的圆心位置。图(c)(c)中加入5%5%的椒盐噪声， 并且圆轮廓边缘由现了间断， 图(d)(d)图(c)(c)经HougHough h变换后的参数空间中累加单元的示意图，受噪声的

17、干扰，非峰值点的区域不如图(b)(b)平坦。改进的 HoughHough 变换直线检测方法HoughHough 变换作为图像目标检测的有效方法，具有很强的抗干扰能力。如(c)(c)图(a)(a)经 HoughHough 变换后参数空间变换后的参数空间(d)(d)图(b)(b)经 HoughHough(e)(e)图(a)(a)的 HoughHough 变换检测结果图(b)(b)的 HoughHough果检测的曲线上有小的扰动或是间断， 或者图像中存在背景噪声， HougHough h变换算都能够准确地检测由目标曲线。因此，该方法在图像处理中得到了越来越广泛应用。但 HoughHough 变换将图

18、像中的每一个边缘点映射为参数空间中相应的曲线，算量非常大，且需要预存的参数空间，浪费大量的存储资源。特别对于直线的 HoughHough 变换检测，由于图像空间和参数空间的离散化以及受到噪声的影响，容易引起数空间中峰值的扩散，甚至会由现伪峰值，给检测带来了困难，限制了它在很多方面的应用。4.14.1 基于直线连接度量的 HoughHough 变换4.1.14.1.1传统 HoughHough 变换的局限DudaDuda 提由的 HoughHough 变换检测直线的极坐标映射关系可以表示为：=xcos-ysin1(4.1)其中p表示直线与图像空间中原点的距离，。表示直线法线与x轴的夹角。图41特

19、征点（x,y）力映射为参数空间的一条曲线曲线上的每一点确定穿过（x,y）的直线可以看出，xy平面上的一点映射到。e-p平面上是一条正弦曲线。参数空间的离散化单元为s,p）,给定图像空间中特征点（x,y）,。遍历卜欠）中的离散值计算得到p,然后把p）表示的累加单元的值加1。这一方法隐含了假设通过（x,y）点的直线的角度是在底）上等概率分布的，如图4一1所示，（a）中的实线表示由参数空间中的值得到的候选直线。 可以看出， 此时对0的离散个数决定了可能通过点 （x,y）的直线条数， 这与现实生活中只有有限条直线相交于同一点是矛盾的。传统Houg陵换依据图像的全局统计特性检测直线，它对符合条件的所有参

20、数单元等值投票累加， 容易检测出虚假直线。 实际上，如果图像中一点在一条直线上，则在该点的周围也将有其他点在这条直线上。图4一2表示图像空间中的四个特征点A、B、CD,其中A是待分析的参考点，我们发现，通过参考点A的直线只有两条AB或ACD因此经Hough变换后，把符合条件的所有心） 上的离散参数单元都等值投票累加是不合理的。 由于B点距A点的距离较C、D点小，在图像空间中AB作为经过A点直线的可能性比ACD要大，但传统HT依据图像的全局统计特性检测得到的是本来不应在一条直线上的三点AGD所连接成的直线， 对于CD两点， 传统HT无法区分它们是图像点还是噪声点。A A 0 0图4一2A,B是图

21、像点，GD是噪声点(a)(a)原图(b)(b)图(a)(a)经 HoughHough 变换后的参数空间图 4 4 一 3 3 图像噪声引起的伪峰值示意图图 4 4 一 3(a)3(a)是一副大小为 ldx!ldx!百的图像，其中含有一条线段和 5 5 个孤立的噪声点，图(b)(b)为图(a)(a)经 HoughHough 变换后参数空间累加单元的累加值图， 其中 Q Q 所指峰值点代表图像中的直线段， 而由于受到噪声的干扰，在 Q Q 峰值点的附近由现了一个伪峰值点 PoPo 同时，在二值累加方式下，由于各投票点的贡献值相同，噪声的存在容易使参数空间由现峰值扩散现象，这对参数空间中的峰值检测是

22、十分不利的。为了保证提取有效的峰值作为直线参数的准确估计，应当对投票点的贡献有所区分，对代表通过该特征点的可能直线的参数单元给与较大的投票值，从而突生局部峰值。我们应用本文算法(MHT)(MHT)分别检测合成图像和实际图像中的线段特征，图像的大小都是 256x256o256x256o 在变换的过程中，我们假设参数单元的匹配模板中只含有一条线段特征。实验所用计算机配置为 CPU:Pentiuml.SGCPU:Pentiuml.SG, ,内存:256MB:256MB。在算法的起始时刻，我们令月=0,乃P2=鸟+AP,AP=I,4日=I。图 4 4一 13(a)13(a)是一幅含有噪声的合成图像，图

23、 4 413(b)13(b)是一所房子的实际图像图 4 4 一 1313 测试图像图 4 41414 是由测试图像得到的实验结果，由图 4 4 一 1414 可以看由，本文算法具有很好的鲁棒性，能够准确地定位图像中直线的起点和终点位置，且不受线段中间断的影响。对图 4 413(b)13(b)经过 CannyCanny 算子提取的边缘图像应用传统HoughHough 变换(eHT)(eHT)检测线段方法和MHMHT T得到的结果如图4 414(c),(d)14(c),(d)所示， 受CannyCanny算子中阐值和算法步骤(3)(3)中所选取闭值的影响，造成一些边缘点的丢失，MHTMHT共检测得

24、到 2525 条线段。在 CHTCHT 中，P和 e e 的采样均是 1,1,通过分析峰值点处蝶形单元结构来确定线段的端点坐标。但图像空间中相距很近的两条直线的峰值点蝶形单元容易相互影响，从而造成误检，如图 4 414(c)14(c)右下角的三条线段图 4 4 一 1414 测试图像的实验结果表 4.14.1 是对这两种算法检测到的直线条数，运算时间以及所需参数单元个数的比较。由表 4.14.1 可以看由，MHTMHT 在节约计算时间上并不具有很大的优势，但在计算的过程中只需要固定个数的参数单元。表 1 1 两种算法的性能比较LinesRurrtimeQ)rcellsCHTCHT231271.3X101.3X10251422626该算法通过寻找各个参数单元在图像中的匹配模板来获得投票值，从而将满足单元匹配条件的特征点聚类到同一参数点。它可以准确定位线段的端点，避免了在内存中预先存储 HoughHough 变换的所有参数单元，能够保持与传统算法同样的精确度，节约大量的存