基于改进蚁群算法的三维点云数据多分辨三维重建

基于改进蚁群算法的三维点云数据多分辨三维重建

随着计算机图形学和三维扫描技术的发展，点模型越来越受到重视。由于点元不仅包含模型的几何信息（如空间坐标、法律向量等）和表面属性（如颜色、光等），而且不需要考虑采样点之间的拓扑关系。因此，三维模型的隐式重建算法利用了点云数据的这些优点，成为工程科学可视化领域的重要方法和研究对象。然而，如果获得的点云数据是噪声，尤其是接近公共点噪声，那么许多重建算法通常无法很好地再现模型的表面特征。在计算机图形学领域,三维模型曲面的表示方法主要有两类:参数曲面和隐式曲面.参数曲面法通过给定的函数f(s,t)将二维参数域映射到三维空间,隐式曲面法则由三维标量场函数f(x,y,z)的零水平集{(x,y,z)|f(x,y,z)=0}{(x,y,z)|f(x,y,z)=0}表示.由于隐式曲面法不仅能准确地描述复杂物体,而且能方便地对重建后的模型执行变形和编辑等操作,所以该方法得到了广泛应用.滑动最小二乘法(movingleastsquare,MLS)和径向基函数法(radialbasisfunction,RBF)[3,4,5,6,7,8,9,10,11]是目前比较流行的三维隐式曲面重建方法.基于径向基函数的隐式重建算法能准确、稳定地解决离散点插值问题,受到了研究者的青睐,已经取得了一些研究成果,如紧支撑的径向基函数法、快速径向基函数法、多尺度径向基函数法和基于RBF的神经网络法.但是,这些算法对噪声比较敏感,尤其是当输入数据携带大量高频噪声和离群点噪声时,它们都不能准确地重建出三维模型.笔者在本文中提出了一种隐式重建算法,以解决带噪声的点云数据的高质量重建问题.该算法首先定义了光滑的概率密度函数,描述某个采样点应是模型表面上点的概率,基于均值漂移算法的滤波算子将各个采样点沿核密度函数的梯度方向移动;其次,将两个经典的方法——径向基函数法和单位分解法,结合起来,完成离散点数据的隐式重建,即去除了噪声和离群点的输入数据先用由误差控制的自适应八叉树划分为小的子域,然后在八叉树的每个叶子单元用基于径向基函数的插值算法来求解局部曲面函数;最后,通过单位分解法(partitionofunity,PoU)对局部形状函数加权求和得到整个模型的全局隐含数.1平均位移算法1.1pir3模型协方差分析法(covarianceanalysis,CA),也称主元分析法(principalcomponentanalysis,PCA),可以计算各采样点处的法向量、曲率等几何信息,也可以定义某个采样点局部邻域的最小二乘拟合平面.给定带噪声的点云数据的集合Ω={pi}i∈[1,L],pi∈R3,该集合中任意采样点pi的协方差矩阵C定义为C=L∑j≠i,j=1(pj-ˉpi)(pj-ˉpi)ΤW1(|pj-pi|sk),(1)C=∑j≠i,j=1L(pj−p¯¯i)(pj−p¯¯i)TW1(|pj−pi|sk),(1)式中:ˉpp¯¯i是点pj的某一k-邻域的重心;W1是单调递减的权函数;sk是自适应的核的大小,其值由空间采样密度而定.考虑特征值和特征向量问题:Cel=λlel,l=0,1,2.(2)因为C是对称的半正定矩阵,所以特征值λl在实数域内取值,所有的特征向量el构成一个正交坐标系,对应于局部邻域的主元.假定λ0≤λ1≤λ2,则穿过ˉpi的最小二乘拟合平面定义为Η(pi)∶(pi-ˉpi)e0=0,且点pi的邻域内的采样点到该平面的距离的二次方和最小.因此,e0可近似为曲面在点pi处的法向量ni,即ni≈e0.换句话说,e1和e2张成了一个过点pi的切平面.1.2采样点正交投影均值漂移是一种有效的迭代统计算法,可使每个采样点漂移到密度函数的局部最大值点.本文中用非参数核密度估计的方法近似定义点云数据的核密度函数d(p).平滑的核密度函数d(p)能较好地反映任意点p是模型曲面S上的采样点的概率.受文献的启发,用p到参考平面H(p)的距离的二次方和定义核密度函数d(p)=L∑i=1di(p)=L∑i=1W2(p-ppro)W3(ppro-ˉpi){1-[(p-ˉpi)nisk2〗2},(3)式中:ppro是某个采样点p在参考平面H(p)上的正交投影;W2和W3是两个单调递减的权函数,分别从空间域和范围域为采样点分布加权,距离参考平面H(p)和重心ˉpi越近的采样点分配到的权值越大,反之亦然,这样可以更好地适应点模型的局部几何特性.权函数可以选用Gaussian或Epanechnikov核.本文中选择Gaussian核函数e-x2/2σ2,其中,x是自变量,σ是核的宽度,x和σ均为实数.用梯度下降法求方程(3)的局部最大值:∇d(p)=L∑i=1∇di(p)≈-2s2kL∑i=1W2(p-ppro)W3(ppro-ˉpi)[(p-ˉpi)⋅ni]⋅ni,(4)于是,均值漂移向量θ(p)=p-L∑i=1W2(p-ppro)W3(ppro-ˉpi)[(p-ˉpi)⋅ni]⋅niL∑i=1W2(p-ppro)W3(ppro-ˉpi).(5)将式(4)和(5)结合,可得到均值漂移的迭代方程:pi,t+1=θ(pi,t),pi,0=pi,(6)其中,t是迭代次数.在本算法中,d(p)满足下列条件:d(p2)-d(p1)＞∇d(p1)(p2-p1),∀p1≥0,∀p2≥0,(7)因此,d(p)是凸函数,且在集合U=pi|d(pi)≥d(pi,1)中存在有限个稳定点,所以序列{pi,t,i=1,2,…,L,t=1,2,…}收敛.均值漂移算法的聚类特性常会使几个离群点收敛为同一个点,并且稀疏地分布于点模型周围.与模型表面上的采样点相比,离群点的空间采样密度较低,利用这一特性并结合合适的阈值就可很容易地剔除离群点噪声.2计算曲线隐藏函数2.1确定局部支撑半径为避免求解稠密的线性系统,提高重建速度,采用文献中介绍的自适应八叉树空间划分方法,将滤波后的点云数据Ω′={pn}n∈[1,N],pn∈R3,N≤L,划分为相互少量覆盖的小的子域.首先为八叉树节点单元定义局部支撑半径Rm=ατm,m∈[1,M],其中,τm是叶子节点的立方体包围盒的主对角线的长度,α是调节系数.设每个叶子节点包含的采样点数介于最小值Nmin和最大值Nmax之间,并取α=0.6,Nmin=20,Nmax=40,得到了满意的实验结果.为控制细分的深度,根据Taubin距离定义局部逼近误差的最大范数:ε=max|pn-cm|＜Rm|f(pn)||∇f(pn)|,(8)其中,cm是节点单元的中心.如果ε大于用户指定的误差阈值ε0,则继续细分,直至ε≤ε0.2.2权系数wn的函数及约束条件给定滤波后的输入点云数据集合Ω′={pn}n∈[1,N],pn∈R3,N≤L,和相应的函数值{vn}n∈[1,N],vn∈R.本算法的主要目的是求解插值函数f(pn):R3→R,使式(9)成立:f(pn)=vn.(9)用基于径向基函数的插值方法求解模型的曲面函数f(p),即f(p)=η(p)+Ν∑n=1wnφ(|p-pn|),(10)式中:η(p)=ζkηk(p),系数ζk∈R,{ηk(p)}k∈[1,Q]是包含所有三变量实值多项式的零空间中的一个基,其最高阶次为β,且Q∈,ηk(p)由径向基函数φ(|p-pn|)确定;wn∈R3是权值;|⋅|表示Euclidean范数.用文献中给出的C2连续且紧支撑的基函数φ(r)=(1-r)4+(4|r|+1)计算曲面函数,其中r=|p-pn|.为保证正交性,权系数wn必须满足下面的自然约束条件:Ν∑n=1wnη1=Ν∑n=1wnη2=⋯=Ν∑n=1wnηQ=0.(11)合并方程(9),(10)和(11)为矩阵形式:[AηηΤ0〗[wζ〗=[v0〗‚(12)式中:A=[φ(|pn-pj|)];η=pj);w=;ζ=;v=;n,j=1,2,…,N,k=1,2,…,Q.求解线性系统(12)可以确定未知参数ζk和wn,从而得到整个模型曲面的形状函数.用LU分解法解线性方程组(12).为避免产生奇异,引入额外的偏移点,在这些点处函数值不等于零.2.3局部函数fmp加权函数的求解单位分解法的主要思想是“分而制之”.设噪声剔除后的点云数据为全局域Ω′={pn}n∈[1,N],用八叉树细分为M个相互少量重叠的小的子域{Ωm}m∈[1,M],M≤N,且Ω′⊆Μ∪m=1Ωm.在每个子域Ωm内,用基于径向基函数的隐式重建法计算出局部曲面的形状函数fm(p),然后用非负且紧支撑的函数{Λm}m∈[1,M]对fm(p)加权求和以得到全局函数f(p).如图1所示,4个局部形状函数f1(p),f2(p),f3(p)和f4(p)被4个对应的混合函数Λ1,Λ2,Λ3和Λ4混合,实线即为所求的全局函数.因此,定义在全局域Ω上的曲面函数方程f(p)是由所有的局部函数fm(p)加权混合而成的,其数学表达式为f(p)=Μ∑m=1fm(p)Λm(p),(13)其中,混合函数Λm(p)在整个定义域上的和等于1,且是由一些光滑函数通过归一化过程得到的:Λm(p)=W4m(p)/Ν∑j=1W4j(p),(14)式中,权函数W4m(p)在每个子域上连续.将权函数定义为W4m(p)=θ。Dm(p),其中:Dm:Rn→是距离函数,并且在Ωm的边界上Dm(p)=1;θ:→是衰减函数;运算符“。”表示函数复合,即θue0c9Dm(p)=θp).3采样点渗出率的创建在VC6.0++环境下实现了本研究的算法.硬件平台:PC机,2.8GHz奔腾4超线程处理器,512MB内存.为了实现重建的隐式曲面的可视化,用纯粹的基于点的绘制算法替代传统重建算法中基于移动立方体(marchingcube)的算法,这样可以有效地避免大量的网格化过程,并充分利用点云数据的优点.表1给出了在误差阈值为10-5下3个噪声模型的算法时间统计,表中:Pinput表示输入的初始采样点个数;Pfilter表示经均值漂移滤波后的采样点个数;Tfilter表示均值漂移滤波的时间开销;Toctree表示八叉树空间划分的时间开销;Trec表示隐式重建的时间开销.为了更好地对自适应核密度函数进行估计,在滤波过程中选择了较大的k-邻域值(k=200),但却导致滤波时间增长,不适于实时系统的重建.然而,从另一方面看,由于均值漂移算法的聚类特性,滤波后的采样点数少于输入数据,这又节省了重建时间,但相对于均值漂移滤波的时间开销来说,这部分时间是非常少的,因为均值漂移的时间远远大于重建的时间.图2比较了文献的算法和本文算法的重建效果.Carr等用多重调和径向基函数重建了光滑的流形曲面,该算法是隐式重建领域的一个非常优秀的研究成果.然而,正如图2(b)所示,由于该算法对噪声比较敏感,尤其是当离群点噪声较大时,重建模型会产生失真.本文算法正好解决了这一问题,取得了高质量的重建结果,如图2(c)所示.为了验证不同的误差阈值对重建模型的光顺程度和正确性的影响,分别比较了点模型StanfordDragon(包含2.11×106个采样点)在误差阈值8.4×10-4和2.1×10-5下的重建效果,如图3所示.较小的误差阈值可再现(甚至强化)模型丰富的细节特征,增大误差阈值则会损失重建模型的细节特征.实验结果表明,本算法还具有多分辨建模的功能.4噪声点云数据的有机隐式重建本文中针对带噪声和离群点的点云数