Hough变换原理.doc

摘要
人类对物体的识别最主要是对物体外形的识别，图像的形状检测在图像处理以及模式识别中是十分重要的。Hough变换作为目标形状特征提取的有效方法得到了广泛的应用。但Hough变换算法主要应用于二值图像(即边缘图像)，因此在对灰度图像进行Hough变换前需要对其进行预处理(包括图像的滤波与边缘检测)。图像预处理作为Hough变换目标检测过程中重要的前期工作，其结果将直接影响检测结果的好坏。文中介绍了图像中常见的两种噪声，对图像的空间域噪声滤波做了一些研究，分析了高斯滤波与中值滤波的局限性，在双边滤波的基础上提出了一种基于多次中值抽取的双边滤波方法，该方法兼顾了空间邻域的相关性和像素强度的相似性通过伪中值滤波选取强度滤波器的参考像素值，在平滑高斯噪声和椒盐噪声的同时更好地保护了边缘，与针对某一类特定噪声设计的传统滤波方法相比，该方法能够处理混有混合噪声(高斯噪声和椒盐噪声)的图像，并能够得到很好的滤波效果。同时，本文分析了几种经典的边缘检测算子，用迭代的双边滤波方法代替Canny算子中的高斯滤波过程或自适应滤波过程，在一定程度上避免了滤波过程给边缘带来的模糊，得到了更好的边缘检测结果。Hough变换作为图形目标检测的有效方法，能够检测直线、圆、椭圆和抛物线等众多解析图形，广义Hough变换对该方法做了一些推广，不再受图形解析表达式的限制，通过预先设置的查找表，能够检测任何图形目标。文中对这些方法都做了介绍，并对这些方法做了仿真。由于受到图像空间和参数空间离散化的影响，以及Hough变换自身的计算过使得传统Hough变换方法也有一些局限性，比如在高强度噪声下检测的结果不佳，计算量大，存储资源需求大等。文中分析了传统Hough变换的投票过程，指出传统方法对参数单元进行1值累加是不合理的，并且传统方法没有区分图像中的噪声点和直线上的点，介于此，提出了基于直线连接度量的Hough变换，既考虑了图像的全局信息，也考虑了图像中像点邻域的局部信息，使得参数空间中的峰值不再受到噪声的影响，同时也避免了图像中具有线性关系的特征点投票带来的虚假峰值。通过对传统Hough变换定义方式的修改，提出了基于模板匹配的Hough变换检测方法，在该方法中，每一个参数单元都确定了图像空间中的一个模板，通过该模板主动搜索图像空间中符合条件的特征点，特征点的个数作为参数单元的值，并记录图像中线段的端点坐标，完成图像中线段的检测与定位，能够节省大量的存储资源。
关键词:特征提取；Hough变换
Hough变化检测直线
Hough变换的基本思想是利用点—线的对偶性，即图像空间共线的点对应在参数空间里相交的线，反过来，在参数空间中交与同一个点的所有直线在图像空间里都有贡献的点与之对应。
在图像空间X—Y中，所有共线的点（x，y）都可以用直线方程描述为：
（3.1）
其中m为直线的斜率，c为截距，同时式（3.1）又可以改写为：
（3.2）
上式可以看做是参数空间C—M中的一条直线方程，其中直线的斜率为-x，截距为y。
比较式（3.1）和式（3.2），可以看出，图像空间中的一点（x，y）对应参数空间中的一条直线，而图像空间中的一条直线又是由参数空间中的一个点（m，c）来决定的。Hough变换的基本思想就是将上述两式看作是图像空间中的点和参数空间中的点的共同的约束条件，兵由此定义一个从图像空间到参数空间的一对映射图3—1体现了这种点—线之间的对偶关系。图3—2（a）所示图像空间中位于同一直线的点，（b）所示是图像中直线上的点经式（3.2）映射到参数空间中的一簇直线，图像空间中的一条直线上的点经过hough变换后，对应的参数空间中的直线相较于一点，这一点是确定的，确定该点在参数空间中的位置皆可以知道图像中直线的参数。Hough变换把在图像空间中的直线检测问题转换到参数空间里对点的检测问题，通过在参数空间里进行简单的累加统计完成检测任务。

(a)图像空间中的单点 (b)参数空间中的直线
图3一1图像空间中的点与参数空间中的直线对偶示意图

（a）图像空间中位于同一直线上的点 (b)参数空间中的直线
图3一2图像空间中的直线与参数空间中的点对偶示意图

图3一3参数空间中的累加数组
在具体的计算过程中，需要将参数空间M一C离散化为二维的累加数组，设这个数组为(m，c)，如图3一3所示，同时设[和分别为斜率和截距的取值范围。开始时置数组A全为零，然后对每一个图像空间中的给定边缘点，
让m取遍内所有可能的值，并根据式 (3.2)算出对应的。再根据m和c的值(设都已经取整)据m和。的值(设都已经取整)对数组元素A(m，c)=A(m，c)+I。累加结束后，通过检测数组A中局部峰值点的位置来确定参数m和c的值。
如果直线的斜率无限大(比如x=a形式的直线)，采用式(3.2)是无法完成检测的，为了能够正确识别和检测任意方向的和任意位置的直线，可以可以用Duda和Hart提出的直线极坐标方程来替代 (3.1)式:
（3.1）
如图3一4(a)所示，图像空间中一条直线l，为l过原点的垂线与x轴正方向的夹角，p为原点到z的距离。这时，参数空间就变为p一空间，X一Y空间中的任意一条直线对应了p一空间内的一个点，由式(3.3)可知，X一Y空间内的一点对应了p一空间中的一条正弦曲线。如果有一组位于由参数p和决定的直线上的点，则每个点对应了参数空间中的一条正弦曲线，所有这些曲线必交于点，如图3一4所示。

(a)图像中位于同一直线上的点 (b)参数空间中交于一点的正弦曲线
图3一4极坐标方程下的点一线对偶示意图
同样，在计算的过程中需要对参数空间进行离散化，每个单元的中心点坐标为：
（3.4）
其中，为参数分割段数：，是参数的分割段数，是为图像中的点距原点的距离最大值。具体的计算过程与上文相似，将参数相应的置换即可。
利用Hough变换在图像中检测直线的基本策略就是:由图像空间中的边缘点去计算参数空间中的参考点的可能轨迹，并在一个累加器中给出计算的参考点计数，最后选出峰值。Hough变换实质上是一种投票机制，对参数空间中的离散点进行投票，若投票值超过某一门限值，则认为有足够多的图像点位于该参数点所决定的直线上。这种方法受噪声和直线出现间断的影响较小。
35实验结果与分析
标准Hough变换广泛用于直线的检测，在同一图像上具有多条直线和噪声干扰的情况下，正确识别直线需要注意一下几点:
1)参数空间中只有当计数器的值为局部峰值时，该点的坐标才有可能作为直线的参数，累加数组其他各点的坐标不能作为直线的参数看待;
2)参数0的取值范围为[0o，]8口’夕或[一夕0o，夕口，，变换过程中0的离散间隔决定了识别的精度，但e的步长不能过小，这样会引起参数空间的峰值扩散，也会增大 Hough变换的计算量;
3)对于宽度大于1个像素点的直线，正确地识别不仅需要对p的取值，而且需要对夕的取值加以限制 [3811391。在本节中我们只考虑对1个像素宽度的直线进行
Hough变换检测
如图3一9所示，其中(“)图含有6条直线，并且每条直线都有间断，为了分清每条直线在经过Hough变换后对参数空间单元的累加值，我们对每条直线都加以标记，直线1，2是图中较长的两条直线，直线a，b，c，d可以看作是图像中矩形的四条边。(b)图是(a)图加入了5%的椒盐噪声，可以通过对(a)图和(b)图的Hough变换检测结果进行比较来考察Hough变换的抗噪声能力。图(c)、(d)分别是图(a)、(b)经Hough变换后参数空间中累加单元的累加值效果
图，图(c)中的标号与图(a)中的标号是一一对应的，可以看出图像中直线段的长度决定了对应累加单元的累加值的大小图像中的孤立点噪声增大了参数单元中的累加值，但没有改变局部峰值点的位置。图(。)、(f)是通过寻找参数空间中局部峰值点的位置画出来的，分别是(a)图和(b)图的Hough变换检测结果，这两个图基本上没有什么差别。因此，Hough变换对图像中的直线出现间断或是噪声具有很强的抵抗能力，但如果我们将图(a)看成是由多条线段组成的图，而且需要检测到这些线段，标准Hough变换是无法完成的，因为此时参数空间单元的信息只包括:线段所处直线的参数以及共线点的个数，而无法确定该线段的
起始点的位置。
在图3一9(c)中，a、b、c、d四个峰值点分别对应了图像中矩形的四条边，这四个峰值点满足下面的关系:
l)它们是成对出现的:第一对是b和d，设他们对应的边的倾斜角度为；
第二对是a和c，设他们对应的边的倾斜角度是;
2)两对峰值点在“轴上间隔90。，即;
3)因为矩形的对边的长度相等，则同一对中的两个峰值的累加值是相同的，即。，为参数单元中累加值，代表边的长度;
4)同一峰值对中两点间在轴上的距离值等于矩形的边长，即，
。
我们可以在参数空间中寻找符合上述4个关系的峰值点，从而检测图像中的矩形轮廓。

(a)无噪声图像 (b)加噪后图像

(c)图(a)经Hough变换后参数空间 (d)图(b)经Hough变换后的参数空间

（e）图(a)的Hough变换检测结果 (f)图(b)的Hough变换检测结果
图3一9Hough变换检测直线
图3一10(a)是一副含有单个圆轮廓的合成图像，其中轮廓的边缘厚度为一个像素，(b)是(a)经Hough变换后在参数空间中的累加值图，在变换的过程中，圆的半径是已知的，此时参数空间的大小与图像空间相同，峰值点所处的位置即为图像中圆的圆心位置。图(c)中加入5%的椒盐噪声，并且圆轮廓边缘出现了间断，图(d)图(c)经Hough变换后的参数空间中累加单元的示意图，受噪声的干扰，非峰值点的区域不如图(b)平坦。

改进的Hough变换直线检测方法
Hough变换作为图像目标检测的有效方法，具有很强的抗干扰能力。如果检测的曲线上有小的扰动或是间断，或者图像中存在背景噪声，Hough变换算都能够准确地检测出目标曲线。因此，该方法在图像处理中得到了越来越广泛应用。但Hough变换将图像中的每一个边缘点映射为参数空间中相应的曲线，算量非常大，且需要预存的参数空间，浪费大量的存储资源。特别对于直线的Hough变换检测，由于图像空间和参数空间的离散化以及受到噪声的影响，容易引起数空间中峰值的扩散，甚至会出现伪峰值，给检测带来了困难，限制了它在很多方面的应用。
4.1基于直线连接度量的Hough变换
4.1.1传统Hough变换的局限
Duda提出的Hough变换检测直线的极坐标映射关系可以表示为:
（4.1）
其中表示直线与图像空间中原点的距离，表示直线法线与x轴的夹角。

图4一1特征点（x，y）力映射为参数空间的一条曲线
曲线上的每一点确定穿过（x，y）的直线
可以看出，x一y平面上的一点映射到。平面上是一条正弦曲线。参数空间的离散化单元为，给定图像空间中特征点（x，y），遍历中的离散值计算得到，然后把表示的累加单元的值加1。这一方法隐含了假设通过(x，y)点的直线的角度是在上等概率分布的，如图4一1所示，(a)中的实线表示由参数空间中的值得到的候选直线。可以看出，此时对0的离散个数决定了可能通过点（x，y）的直线条数，这与现实生活中只有有限条直线相交于同一点是矛盾的。
传统Hough变换依据图像的全局统计特性检测直线，它对符合条件的所有参
数单元等值投票累加，容易检测出虚假直线。实际上，如果图像中一点在一条直
线上，则在该点的周围也将有其他点在这条直线上。图4一2表示图像空间中的四个特征点AB、C、D，其中A是待分析的参考点，我们发现，通过参考点A的直线只有两条AB或ACD，因此经Hough变换后，把符合条件的所有上的离散参数单元都等值投票累加是不合理的。由于B点距A点的距离较C、D点小，在图像空间中AB作为经过A点直线的可能性比ACD要大，但传统HT依据图像的全局统计特性检测得到的是本来不应在一条直线上的三点A、C、D所连接成的直线，对于C、D两点，传统HT无法区分它们是图像点还是噪声点。

图4一2A，B是图像点，C，D是噪声点

(a)原图 (b)图(a)经Hough变换后的参数空间
图4一3图像噪声引起的伪峰值示意图
图4一3(a)是一副大小为ldx!百的图像，其中含有一条线段和5个孤立的噪声点，图(b)为图(a)经Hough变换后参数空间累加单元的累加值图，其中Q所指峰值点代表图像中的直线段，而由于受到噪声的干扰，在Q峰值点的附近出现了一个伪峰值点P。同时，在二值累加方式下，由于各投票点的贡献值相同，噪声的存在容易使参数空间出现峰值扩散现象，这对参数空间中的峰值检测是十分不利的。为了保证提取有效的峰值作为直线参数的准确估计，应当对投票点的贡献有所区分，对代表通过该特征点的可能直线的参数单元给与较大的投票值，从而突出局部峰值。

我们应用本文算法(MHT)分别检测合成图像和实际图像中的线段特征，图像的大小都是256x256。在变换的过程中，我们假设参数单元的匹配模板中只含有一条线段特征。实验所用计算机配置为CPU:Pentiuml.SG，内存:256MB。在算法的起始时刻，我们令，乃，，。图4一13(a)是一幅含有噪声的合成图像，图4一13(b)是一所房子的实际图像。

图4一13测试图像
图4一14是由测试图像得到的实验结果，由图4一14可以看出，本文算法具有
很好的鲁棒性，能够准确地定位图像中直线的起点和终点位置，且不受线段中间
断的影响。对图4一13(b)经过Canny算子提取的边缘图像应用传统Hough变换
(eHT)检测线段方法和MHT得到的结果如图4一14(c)，(d)所示，受Canny
算子中阐值和算法步骤(3)中所选取闭值的影响，造成一些边缘点的丢失，MHT
共检测得到25条线段。在CHT中，和的采样均是1，通过分析峰值点处蝶形
单元结构来确定线段的端点坐标。但图像空间中相距很近的两条直线的峰值点蝶
形单元容易相互影响，从而造成误检，如图4一14(c)右下角的三条线段。

图4一14测试图像的实验结果
表4.1是对这两种算法检测到的直线条数，运算时间以及所需参数单元个数
的比较。由表4.1可以看出，MHT在节约计算时间上并不具有很大的优势，但在计
算的过程中只需要固定个数的参数单元。
表1两种算法的性能比较

该算法通过寻找各个参数单元在图像中的匹配模板来获得投票值，从而将满
足单元匹配条件的特征点聚类到同一参数点。它可以准确定位线段的端点，避免
了在内存中预先存储Hough变换的所有参数单元，能够保持与传统算法同样的精
确度，节约大量的存储空间。由于该算法是对各个参数单元进行单独处理，因此
可以采用并行处理的方法来提高算法的运算速度。
第五章总结与展望
边缘作为图像的一个基本特征，为人们描述和识别目标以及解释图像提供了
一个重要的特征参数，同时它还经常被应用于计算机视觉和模式识别等较高层次
的处理中。受滤波过程的影响，图像的边缘容易被模糊。本文介绍了几种经典的
图像滤波方法和边缘检测算子，双边滤波是近年来提出的一种比较新颖的滤波算
法，文中对双边滤波方法做了改进，使其能够平滑混合噪声，并将迭代的双边滤
波方法应用于Cajmy边缘检测过程中，得到很好的边缘检测结果。随着计算机视
觉与模式识别技术的发展，对图像的预处理提出了更高的要求，本文的方法虽然
在仿真时都得到了较好的结果，但要求的计算量比经典方法都要大，因此找到这
些方法的快速算法，达到实时性的要求将是一个很有意义的研究内容。
Hough变换自 1962年提出以来有了很大的发展，在信息处理邻域的应用也越
来越广泛。文中对Hough变换检测直线、圆和椭圆的方法做了介绍，并对这些方
法进行了仿真。由于Hough变换的质量对提高图像的识别率非常重要，本文提出
了基于直线连接度量的Hough变换算法—该方法即从全局也从局部定义图像中
的直线，完成对图像中直线的检测，以及参数单元主动搜索图像空间中特征点的
模板匹配Hough变换。这两种方法都是启发式的方法，因此有待于对其进行理论
分析以及算法效率的分析。对于低信噪比的图像，为了解决经典Hough变换方法
运算量大，耗费存储空间大的缺点，众多研究人员提出了许多改进的方法，但由
于参数空间离散化给Hough变换带来的不确定性与不精确性的矛盾，这些方法对
变换质量的提高是有限的，如何在改进Hough变换投票机制的同时解决上述两个
缺点是以后研究的一个重点方向。