基于霍夫变换的二值边缘图拟合直线的研究

基于霍夫变换的二值边缘图拟合直线的研究

1拟合直线拟合在项目中，通常需要线性调整，如实验数据分析、统计数据分析、数据处理中的二值边缘方案，合成连续的直线，并在3d系统中获得三维物体图像的方案。直线拟合在计算数学中有多种方法,最常用的是平方逼近,即最小二乘法。最小二乘法的定义是∑i=1N[yi−φ(xi)]2=min∑i=1Ν[yi-φ(xi)]2=min(1)其中(xi,yi)为已知数据点;φ(x)为拟合函数,直线拟合时为一次多项式。显然,最小二乘法考虑的是已知数据点到拟合函数(直线拟合时为直线)的距离平方和为最小。这里存在两个问题,一是已知数据点集中若存在干扰点或噪声时,拟合函数并不通过最多的数据点,拟合误差较大;二是已知数据点集趋向于分布在多条直线附近时,需事先对已知数据进行分离预处理,否则拟合结果没有意义。对数据点集进行分离预处理是一项既难又费时的工作,有时甚至不可能。霍夫变换(HoughTransform)是模式识别领域中对二值图像进行直线检测的有效方法,它检测已知点的共线性,是一种全局性的检测方法。当已知数据点集中存在干扰点和噪声时,它可以很好地抑制干扰和噪声,同时它还可以将已知数据点集拟合成多条直线。但是,霍夫变换的精度却不容易控制,当实际问题对拟合直线的精度要求较高时,则不能用霍夫变换。霍夫变换的输出是共线点直线方程的参数,当需要得到线段时,还需进一步处理。本文将霍夫变换与最小二乘法相结合,研究对实验数据和图像处理中的边缘图进行直线拟合的方法。首先,用霍夫变换剔除数据点集中的干扰点和噪声,并将分布在不同直线附近的点分离出来;然后,用最小二乘法拟合各直线。该方法既解决了直接使用最小二乘法拟合直线时存在的两个问题;同时也解决了直接使用霍夫变换时,拟合直线精度不高和直线段有效区间不容易控制的问题。2霍夫变换原理和实现方法2.1直线检测的化方式1962年,P.V.C.Hough根据数学对偶性原理提出了检测图像直线的方法,此后,该方法被不断地研究和发展,主要应用于模式识别领域中对二值图像进行直线检测。其原理如图1所示,在标准参数化方式下,平面直角坐标系中的直线l表达为ρ=xcosϑ+ysinϑ,ρ≥0,0≤ϑ<2π(2)其中,ρ为l相对于原点的距离,ϑ为ρ与x轴的夹角。根据式(2),直线l上不同的点在参数空间中被变换为一族相交于p点的正弦曲线。显然,若能确定参数空间中的p点(局部最大值),就实现了直线检测。由上述霍夫变换原理可知,霍夫变换具有如下性质:(1)直角坐标系中的一个点映射到参数空间中为一条曲线;(2)参数空间中的一个点对应直角坐标系中的一条直线;(3)直角坐标系中的共点线映射到参数空间中为一条曲线;(4)直角坐标系中的共线点映射到参数空间中后为一个交于同一点的曲线族。2.2霍夫变换m工程中的实验数据和图像处理中的二值边缘图,通常都是离散数据,因此,根据霍夫变换性质,可按下列步骤实现霍夫变换。(1)将参数空间量化成m×n(m为ϑ的等份数,n为ρ的等份数)个单元,并设置累加器矩阵Qm×n;(2)给参数空间中的每个单元分配一个累加器Q(i,j),并把累加器的初始值置为零;(3)取出直角坐标系中的点(xi,yi)(i=1,2,3…s,s为直角坐标系中的已知点数)代入式(2),并以量化后的ϑ值计算出ρ;(4)在参数空间中,找到ϑ和ρ所对应的单元,并将该单元的累加器加1,即Q(i,j)=Q(i,j)+1;(5)当直角坐标系中的点都经过(3)、(4)两步遍历后,检验参数空间中每个累加器的值,累加器值最大的单元所对应的ϑ和ρ即为直角坐标系中直线方程式(2)的参数。由上述霍夫变换过程可知,如果参数空间中的ϑ和ρ量化过粗,则参数空间中的凝聚效果较差,找不出直线的准确参数ϑ和ρ;反之,ϑ和ρ量化过细,那么计算量将增大。另外,当直角坐标系中的点分布在R条直线附近时,可在第5步检测累加器时,取出累加器中前R个值最大的单元所对应的ϑk和ρk(k=1,2,…,R),以ϑk和ρk(k=1,2,…,R)为直角坐标系中直线方程式(2)的参数,即可同时实现多条直线的拟合。3拟合直线的参数假设采集到的数据集为M=(xi,yi)T,(i=1,2,…,s,s为数据集中的数据点数),M中的数据点分布在R条直线附近,根据实验目的要求给定误差阈值为dk。(1)霍夫变换。将式(2)改写成ρk=xicosϑk+yisinϑk(k=1,2,…,s;k=1,2,…,R)(3)根据式(3),对M作霍夫变换,可得拟合直线的参数(ϑk,ρk)。(2)找出拟合直线(ϑk,ρk)附近的点集M*k。将式(3)表示的法线式直线方程改写成斜截式yi=akxi+bk(4)其中ak=−cosϑksinϑk,bk=−ρksinϑkak=-cosϑksinϑk,bk=-ρksinϑk计算M中的点到由式(4)确定的直线的距离dki=|akxi+bk−yi|1+a2k√,(xi,yi)∈M,(i,=1,2,⋯,s,k=1,2,⋯,R)dki=|akxi+bk-yi|1+ak2,(xi,yi)∈Μ,(i,=1,2,⋯,s,k=1,2,⋯,R)(5)如果dki<dk(6)则(xi,yi)⇒M*k(xkj,ykj),(j=1,2,…s*,s*≤s)(7)M*k为符合误差阈值要求的第k条霍夫变换直线附近的点集。(3)以点集M*k为拟合数据,分别拟合各直线,可得直线方程式(4)的参数(a*k,b*k。以((xkj)min,ykj)∈M*k和((xkj)max,ykj)∈M*k为端点,可确定各直线段的区间,即ykj=a*kxkj+b*k,(xkj)min≤xkj≤(xkj)max(8)4实验4.1霍夫变换拟合直线已知某实验中得到的实验数据如表1所示。(1)首先对数据进行预处理,检查它们是否分布于一条直线附近。如图2(a)所示,实验数据分布在一条直线附近。(2)将实验数据直接作最小二乘法拟合,得直线的斜率a直=0.6142,截距b直=13.8112,拟合结果如图2(b)所示。(3)将实验数据作霍夫变换。霍夫变换时,参数空间的量化值为:0≤ϑ<360,0≤ρ<1000,形成360×1000个单元,累加器最大值为11,输出参数为ϑ=120°,ρ=13。将直线方程式(2)写成斜截式,代入ϑ=120°,ρ=13,得直线的斜率a霍=0.5774,截距b霍=15.0111。拟合结果如图2(c)所示。(4)利用第3步霍夫变换结果,设误差阈值d=5,剔除干扰点2后,用最小二乘法拟合,得直线的斜率a=0.5650,截距b=15.4886。拟合结果如图2(d)所示。霍夫变换拟合的直线与最小二乘法拟合的直线斜率和截距不同,这是因为,霍夫变换考虑的是拟合直线通过最多的数据点,而最小二乘法考虑的是所有数据点距离拟合直线的平方和最小。显然,当数据集中存在干扰点或噪声时,直接采用最小二乘法拟合,其拟合结果误差较大。此时,应先采用霍夫变换剔除干扰点或噪声,然后采用最小二乘法拟合。若实验结果需要拟合的直线通过最多数据点时,可采用霍夫变换进行直线拟合。3.2直线拟合的数值结果已知某次实验所得数据如表2所示。当对实验数据进行预处理后,发现其分布在两条直线附近,如图3(a)所示。根据实验目的的要求,采用两种直线拟合方法。(1)直接采用霍夫变换进行直线拟合。霍夫变换时,参数空间的量化值为:0≤ϑ<360,0≤ρ<1000,形成360×1000个单元,累加器最大值分别为13和12。L1的拟合参数ϑ1=60°,ρ1=63.7,L2的拟合参数ϑ2=125°,ρ2=2.5拟合结果如图3(b)所示。(2)首先采用霍夫变换找出分布在拟合直线附近的点,然后采用最小二乘法拟合。在寻找拟合直线附近的点时,取误差阈值d=6。图3(c)为L2的拟合结果,图3(d)为L1的拟合结果。4.3维生物图像中的部分照片生成在模式识别、计算机视觉和CAD系统中,经常需要获得三维物体图像的线图,以便后续处理。图4所示是L型多面体的综合图像及其各棱线的编号,图像大小为360×400像素。(1)图像预处理加入1%的模拟噪声后,采用图5所示的3×3模板算子,得到如图6(a)所示的二值边缘图。(2)参数空间的量化值为:0≤ϑ<360,0≤ρ<800。检测到的棱线结果如图6(b)所示,各棱线的参数如表3所示,其中ϑ和ρ为棱线的法线式参数,a和b为棱线的斜截式参数。(3)通过霍夫变换来确定闭合线周围的点根据式(5),取误差阈值dk=4(像素),检测到的棱线周围点如图6(c)所示。(4)最小二乘法调整根据第3步检测到的棱线周围点,采用最小二乘法拟合。拟合结