均值漂移去噪算法的研究
CAD/CAE/CAPP/CAM现代制造工程2008年第11期
均值漂移去噪算法的研究
张树森1,伏利1,肖胜兵2
(1辽宁工程技术大学机械工程学院,阜新123000;2黑龙江科技学院机械工程学院,哈尔滨150027)
摘要:逆向工程中对实体扫描时,由于会受到各种因素的影响,不可避免地在真实数据点中混有噪声点,为后续的曲面重构和曲面拟合等带来困难。提出应用均值漂移算法,在局部邻域内估计采样点的核密度函数并通过均值漂移算法计算它的局部最大值点,核密度函数的局部最大值点确定了点云数据的聚类中心并能准确逼近采样点曲面,将每一个采样点漂移到密度函数的局部最大值点,使点云曲面收敛为一个稳定的三维数字模型。通过实验结果表明能有效剔除噪声点。
关键词:逆向工程;均值漂移;核密度函数
中图分类号:TP391 文献标识码:A 文章编号:1671—3133(2008)11—0041—03
The research on a lgor ith m for m ean sh i ft of no isy po i n t
Zhang Shu2sen1,Fu L i1,Xiao Sheng2bing2
(1I nstitute of Mechanical Engineering,L iaoning Technical University,Fuxin123000,
L iaoning,CHN;2I nstitute of Mechanical Engineering,Heil ongjiang University of
Science&Technol ogy,Haerbin150027,CHN)
Abstract:Scanning the entity must m ix noise point int o the real data point inevitably because of s ome fact ors,which should cause the difficulty of surface reconstructi on and surface fitting.S o mean2shift algorith m is given,kernel functi ons of sa mp le points in l o2 cal regi ons were esti m ated and the l ocal maxi m u m of the kernels was computed by using mean2shift technique.The l ocal maxi m a of the kernel esti m ati on functi on deter m ined cluster centers of point cl oud data,which delivered and accurate app r oxi m ati on of the sa mp led surface.Each sa mp le point was shifted t o the l ocal maxi m u m of the kernel functi on,s o the point2set surface could con2 verge t o a stable3D digital model.Experi m ents show the efficient noise s moothing by mean2shift algorith m.
Key words:Reserve engineering;M ean2shift;Kernel density functi on
随着三维测量设备在测量效率、精度等方面的突破,点云数据在三维实体造型中得到了广泛的应用[1,2]。然而在对实体扫描时,由于实际测量过程中受到各种人为或随机因素的影响,不可避免地在真实数据点中混有不合理的噪声点,为后续建模中网格的重构以及曲面拟合等带来困难。统计结果表明,在测量得到的点云数据中,有011%～5%的噪声点要予以剔除[3]。本文利用文献[4]中的鲁棒滤波算法对点云进行去噪,该算法的主要思想是对带有噪声和离群点的点石数据应用一个核密度估计函数作为点聚类,对每个数据点通过一个局部似然估计值与三维采样曲面上的真实点对应起来,用Mean2shift迭代算法将每一个采样点“漂移”到核密度估计函数的局部最大值点。这样一系列最大似然值点最后迭代出一个逼近原始曲面的准确值,从而实现了点石数据的快速高效光顺去噪。而且算法中的似然估计函数充分考虑了散乱点的法矢方向,因此可以去除不同振幅方向的噪声点和离群点。
1 常用的去噪算法
由于获得的点云性质不同,相对应的光顺去噪算法也不尽相同。对于有序或部分有序点云当中噪声点的处理,通常可以采用的算法有维纳滤波、最小二乘滤波、卡尔曼滤波、标准高斯滤波、平均滤波和中值滤波算法等。但在现实中,点云多数情况下是呈现散乱、无序状的,所以以上的算法对散乱点云处理的意义不大。对于无序点云的噪声点处理也有很多种算法,其中较为经典的算法有拉普拉斯算法、平均曲率流和双边滤波器等[5]。
拉普拉斯光顺方法是通过一致扩散高频几何噪
1
4
现代制造工程2008年第11期
CAD /CAE /CAPP /CAM
声达到光顺目的,虽然算法简单,但是随着迭代次数的增加,网格的体积快速收缩,并容易产生过光顺而使模型的凹凸特征变模糊。平均曲率流关键技术在于离散三维模型的曲率估计,如果曲率估计的偏差较大,很容易在曲率较大的位置出现突变。双边滤波器的弊端在于顶点相邻区域的选择,当邻域过大,处理时则需要大计算量来寻找邻域。当邻域过小,则不能有效地光顺一些稍大的噪声,甚至增强这些噪声。除以上算法外还有很多的算法,这里不做介绍。总之,以上的算法有一定的局限性。本文将介绍一种利用均值漂移
[6]
的去噪方法。
2 均值漂移滤波算法
在迭代过程中,均值漂移使每一个点“漂移”到密度函数的局部极大值点。
假设X 是m 维欧氏空间中的总体,{x i ,1≤i ≤n}是来自总体X 的独立同分布样本集,如果总体的核密度函数f ^(x )为:
f ^(x )=
∑
n
i =1w i k (α‖x i -x ‖2
)
(1)
……………文献[6]提出了如下形式的均值漂移算法:
y i+1=
∑
n
i =1w i k ′
(α‖x i -x ‖2
)x i /∑n i =1
w i
k ′
(α‖x i
-x ‖2
) (2)
…………式中:w i 为x i 的权重,满足
∑w
i
=1,简记为w i ;k
(x )为文献[7]中定义的轮廓函数,即概率密度估计中的窗口函数;k ′
(x )是k (x )的导数;y i +1为密度函数的加权值;x i 为样本;x 为采样点;α>0为标准化常数。
211 非参数核密度估计
非参数方法对先验知识要求最少,它完全依靠训练数据进行估计,而且可以用于任意形状密度函数的估计。基于核函数的密度估计是最常用的非参数估计方法之一。该方法是从窗口函数k (x )出发,对每个样本x i ,用正定矩阵Σi 表示x i 处的窗口形状和相对尺度,即用正定矩阵来刻画总体X 在x i 周围的局部空间结构。通过对点云曲面局部邻域的协方差矩阵进行分析,可以得到该邻域的最小二乘拟合平面,本文中的核密度估计函数由点P 所在邻域{p i }中任意一点x 到该邻域的最小二乘拟合平面的距离的平方所确定。核密度函数f ^i (x )为:
f ^i (x )=
Φi (x -x p )G i (x p -p ){h 2
-[(x -)n p ]2
}(3)
………………………式中:Φi 和G i 均为单调递减的非线性权重函数,分别从两个维度刻画采样点在空间邻域{p i }中的分布情况,本文选择高斯函数e -x 2/2
δ2作权重函数;p 是点p 在最小二乘拟合平面上的垂直投影点;x p 为采样点x 在最小二乘拟合平面上的投影;n p 为最小二乘拟合平面的法向量;h 为核的大小,h >0,它的值由前向查找算法划分的局部邻域来自适应确定,核的形状表示采样点在邻域中的分布状况,核的大小决定样本的空间采样密度,因此,h 可以从整体上调整窗口的形状和大小。
为了定义采样点在整个点云曲面上的密度函数,将所有局部邻域内的核密度函数求和为:
f ^(x )=
∑n
i =1
w
i
f ^i (x )
(4)
………………………式中:f ^i (x )为核密度函数,几乎处处存在导数。w i 表
示x i 的权重,w i ∈[0,1],即x i 发生的先验概率,此处令w i 为扫描置信度。如果扫描仪不提供该参数,则取w i =1。212 均值漂移算法
梯度方向是函数的增长方向,人们可以从核密度函数f ^(x )的梯度出发,推导均值漂移的迭代方程,近似公式为:
f ^(x )=
∑
m
i =1
w i f ^i (x )=-2
∑m
i =1
w i
Φ
i
(x -x p )×
G i (x p -p )[(x -p )n p ]n p
(5)
……………………………………因为权重函数Φi 和G i 变化较慢,所以在求梯度
时假定为常量。由式(5)得到均值漂移向量m j
i 为:
m j
i =
∑m
i =1
w i
Φi
(x -x p )G i (x p -p )[(x -p )n p ]n p
∑m
i =1
w i
Φi
(x -x p
)G i
(x
p
-p )
(6)
…………………………………………自适应步长t 为:
t =1/2
∑m
i =1
w i
Φ
i
(x -x p )G i (x p -p )
(7)…………………………………………由式(6)和式(7)可以得出均值漂移迭代公式:
p j +1i =p j i -m j i
p 0
i =p i
(8)………………………………式中:j 为迭代次数。通过迭代过程,每个采样点都将移动到其在点模型曲面上概率最大的位置,实际上也就是完成了对点模型的降噪处理。在文献[5]中证明了该算法具有良好的收敛性。
2
4
CAD /CAE /CAPP /CAM 现代制造工程2008年第11期
3 实验验证
首先利用黑龙江科技学院自行研发的HRE 型三维扫描仪对人脸模型进行扫描,得到散乱点云数据,然后用本文算法对获得的点云进行数据处理。本算法在VC ++610环境下实现。硬件条件是奔四超线程处理器,218GHz,1G 内存的PC 机
。
图1
未处理的点云及其重构图
图2
拉普拉斯算法处理的点云及其重构图
图3 本文算法处理的点云及其重构图
如图1～图3所示,本文通过对原始点云及其重构图、拉普拉斯算法处理的点云及其重构图、本文算法处理的点云及其重构图进行比较,可以清楚地发
现,通过拉普拉斯算法对点云去噪滤波是很有用的,但由于其算法的局限性,使得脸模型的一些特征被磨平。而本文的算法在去噪滤波的同时也很好地保留
了模型的尖锐特征。
4 结语
本文针对点模型提出了基于均值漂移的鲁棒滤波算法,算法有效地剔除了点模型的离群点噪声和随机噪声,大大提高了数据处理的速度,并且也提高了后续的重构速度,同时较好地保持了模型的尖锐特征。但该算法也存在一些问题,如果每一个点都独立收敛于最大值时,并行是一个难点,这也是笔者下一步研究工作的重点。
参考文献:
[1] 温银放.数据点云预处理及特征角点检测算法研究
[D ].哈尔滨:哈尔滨工程大学,2007:18-21.
[2] Pfister H,Z wickerM ,Van Baar J,et al .Surfels surface
ele ments rendering p ri m itives [C ].Pr oceedings of the AC M SI GGRAPH Conference on Computer Graphics,Ne w O rleans,Louisiana,2000:335-342.
[3] 周利民.自由曲面快速反求技术与应用研究[D ].西安:
西安交通大学,1997.
[4] Press W H,Teukolsky S A,Vetterling W T,et al .The
scientific computing [M ].Ca mbridge:Ca mbridge Uni 2versity Press,1993.
[5] 戴静兰.海量点云预处理算法研究[D ].浙江:浙江
大学,2006,17-20.
[6] Cheng Y Z .M ean shift,mode seeking,and clustering
[J ].I EEE Trans .on Pattern Analysis and Machine I n 2telligence,1995,17(8):790-799.
[7] Lange C,Polthier K .Anis otr op ic s moothing of point sets
[J ].Special Issue of Computer A ided Geometric De 2sign,2005,22(7):680-692.
[8] Comaniciu D,Meer P .Mean shift a r obust app r oach t ow
and feature s pace analysis [J ].I EEE Transacti ons on Pattern Analysis and Machine I ntelligence,2002,24(5):603-619.
[9] 李道军,刘德平,上官建林.逆向工程中测量数据点
的滤波[J ].现代制造工程,2006(3).
作者简介:张树森,辽宁工程技术大学机械工程学院教授,硕士生导
师,中国高校切削与先进制造技术研究会理事、全国制造及其自动化研究会理事、中国煤炭学会机械工程研究会副理事长,主要研究现代切削技术、刀具和先进制造技术。伏利,辽宁工程技术大学机械工程学院硕士研究生。肖胜兵,黑龙江科技学院机械工程学院助教。
作者通讯地址:黑龙江省哈尔滨市松北区黑龙江科技学院机械工
程系(150027)
E 2mail:fulit op@s ohu .com
收稿日期:2008204228
3
4