谱流形小波及其在三维几何处理中的应用

('谱流形小波及其在三维几何处理中的应用胡玲;汪政;郭啸【摘要】当处理三角网格(可微的二维流形)时,谱图小波采用的图拉普拉斯矩阵不能充分利用模型内蕴的几何信息.为此,将图拉普拉斯矩阵替换为包含模型几何描述的拉普拉斯贝尔特米算子矩阵,在此基础上建立三角网格上的谱流形小波.并将谱流行小波应用于多种几何处理,包括模型的多分辨表示、去噪等.【期刊名称】《湖南师范大学自然科学学报》【年(卷),期】2018(041)004【总页数】8页(P77-84)【关键词】拉普拉斯-贝尔特米算子;谱流形小波;几何处理;二维流形;三角网格【作者】胡玲;汪政;郭啸【作者单位】中南大学数学与统计学院,中国长沙410083;湖南第一师范学院数学与计算科学学院,中国长沙410205;湖南第一师范学院信息科学与工程学院,中国长沙410205;长沙师范学院初等教育系,中国长沙410000【正文语种】中文【中图分类】TP391.41目前小波分析广泛应用于信号处理、数据压缩及模式识别等多个领域并取得了巨大的成功.经典小波分析实现了规则欧式空间信号(函数)的时间(空间)域与频率域的自适应局部化分析.然而,很多科学问题需要处理的信号并非只定义在规则的欧式空间内，它们有时来自于具有更复杂拓扑结构的非规则空间,例如用图(Graph)表示的区域交通网状况信息等网状数据,描述流形上各点某一特征的信号;三维模型表面各点处的几何坐标、曲率等.对于此类信号,经典小波分析已不再适合直接使用.为此，近年来许多工作尝试将小波分析推广至非规则空间,希望在这些空间内同样实现信号的小波分解与重构,挖掘信号内蕴特征,为高维大数据提供紧的表达式等.文献[1-3]尝试在光滑、可微的流形上创建小波.特别地,Hammond等[4]利用图拉普拉斯矩阵以及图傅里叶变换等谱图理论提出了谱图小波(SGW),类比小波在频率里的性质,Hammond成功定义了小波母函数在图域上的伸缩和平移.SGW具有许多与经典小波相似的性质.目前,该小波已被广泛应用于多个领域[5-6].利用SGWT分析大脑皮层厚度信号辅助诊断Alzheimer病患.在三维几何处理领域，SGW用于实现三维模型的分片、校正以及稀疏表示等[7-8].文献[9-11]应用SGW进行模型的检索和分类、模型部分的匹配等非刚性模型的形状分析.实际应用中,利用三角网格表示的三维曲面虽拓扑结构与图无异,但该三角网格除了边和顶点之外，还富含丰富的几何信息.SGW的创建基于图拉普拉斯算子,仅利用到图的节点和边的权重信息.这意味着若仅利用图拉普拉斯创建小波，将严重丢失模型内蕴的几何信息.为此，本文将利用流形上拉普拉斯-贝尔特米算子(LBO)的谱性质，基于SGW的框架构建连续和离散的谱流形小波(SMW).离散谱图小波本质可以视为将图拉普拉斯矩阵置换为拉普拉斯-贝尔特米算子的矩阵,相比前者,后者充分利用了三角网格的几何信息，矩阵元素里蕴含网格角度、顶点面积等信息.因此,利用谱流形小波进行信号分析，将会包含模型内蕴的几何信息,不易受网格质量影响,这一特征在很多几何处理任务中非常重要.谱流形小波实现对定义在流形域上的信号的分解与重构,在此基础上,类似于经典小波的应用,本文将应用谱流形小波进行经典的几何处理.1谱流形小波1.1拉普拉斯贝尔特米算子假设三维模型X为根植于R3空间的紧连续二维流形,定义在该流形上平方可积函数空间表示为其中dx为黎曼度量下的面积微元.拉普拉斯贝尔特米算子定义为ΔXf(x)=-divX(▽Xf(x)),其中▽Xf和divXf分别为函数f(x)∈L2(X)内蕴的梯度和散度.拉普拉斯贝尔特米算子的特征分解为方程ΔXφk(x)=λkφk(x).由于该算子具有半正定性，其特征值均为正实数，0=λ0≤λ1≤….相应的特征函数φ0,φ1,…在标准内积下构成函数空间L2(X)的一组标准正交基，即利用拉普拉斯-贝尔特米算子特征值和特征向量表示的量称之为谱分析,这是因为该算子的特征系统具有类似于调和分析的特征.拉普拉斯算子的特征函数是经典傅里叶基在非欧氏空间里的推广,任意函数f∈L2(x)可以表示为其中特征值{λk}k≥1等价于频率,相当于傅里叶系数,属于第一个特征值λ0=0的特征函数为常值函数，可以视为函数f(x)的DC成份.特别地，f(x)=δa(x),其中点a∈X，其傅里叶系数为1.2谱流形小波和尺度函数经典小波变换在经典信号处理中，小波为满足容许性条件的母函数ψ(x)通过伸缩平移之后生成的一族基函数,即位移为a,尺度为s的小波基表示为任给信号f,与ψs,a(x)的内积称为小波变换系数，即谱流形小波对于封闭的可微流形曲面X以及点x,a∈X,没有直观自然的方式定义函数的伸缩和平移变化.为了克服该问题,文献[4]中类比经典小波在频率域里的滤波特性,利用谱图理论定义同时具有图域与频率域局部性的小波.在本文中，我们将利用流形的频率和傅里叶基，即拉普拉斯-贝尔特米算子的特征系统,基于SGW的框架,构建谱流形小波.现给定小波生成核函数g:R+→R+,其作用类似于带通滤波器将其沿着频率轴拉伸,当从低频逐渐移动至高频处时,所生成的谱流形小波在空间域里的局部性随之逐渐增强.与经典小波类似,谱流形小波可视为相应脉冲函数的滤波结果.根据式(2),尺度s，位移为a∈X的谱流形小波为对任意f(x)∈L2(X),小波系数Wf(s,a)为f(x)与小波函数ψs,a(x)的内积,即Wf(s,a)=〈f,ψs,a〉X.利用{φk}的正交性,进一步可得为了分析信号的低频部分,需要定义低通滤波器,即另一个实值函数h:R+→R+,满足条件h(0)>0和h(x)→0当x→∞.类似于经典小波变换,可通过低通滤波器h(x)定义位于点a处的尺度函数f(x)相应的尺度系数为根据流形傅里叶变换的意义,Wf(s,·)可以视为函数f(x)经过各带通或低通滤波之后流形(空间域)上的结果.此外,若小波生成核函数g满足容许性条件以及零均值条件g(0)=0,则原始函数f(x)可以通过小波基和小波系数重构谱流形小波生成核函数和尺度核函数通过设计小波生成核函数为带通滤波器,小波在频率域具有局部性.文献[4]证明了若核函数g在0附近足够正则化，则有ψs,a(x)/‖ψs,a(x)‖→0,s→0.事实上,当选取不同的小波生成核函数,所得的谱流形小波具有不同的性质.例如类似于Meyer小波的核函数，将生成保能量的帕斯维尔(Parseval)框架.因此,可根据应用灵活的选择小波核函数.在谱图小波工具箱(SGW_TOOLBOX)中提供了多种小波核函数,本文选择3次样条函数,即图1尺度函数生成核函数与小波生成核函数Fig.1Thekernelfunctionsgeneratedbyscalefunctionandwavelet谱流形小波的尺度生成核函数并不需要与小波生成核函数匹配，其作用只是分析小波函数未能分析的低频信息.故尺度函数可选为其中γ的选取使h(0)与g(x)的最大值相同.3次样条小波生成核函数与尺度函数如图1所示.从左至右6条曲线分别为尺度函数生成核函数h(x),尺度s逐渐减小的5个小波生成核函数g(x)(3次样条函数).2离散谱流形小波2.1离散拉普拉斯贝尔特米算子及其特征系统实际应用中，三维模型X的离散表示为三角网格X={V,E,F},其中V为网格顶点集,(i,j)表示连接顶点i和顶点j的边.记第i个网格顶点的一环邻域集为N(i)={j∈V(i,j)∈E}.定义在网格X上的信号f=(f(i)),其中f(i),i=1,2,…,N为信号在网格第i个顶点处的采样值.图2Voronoi单元面积以及角αij,βijFig.2Voronoicellareaandtheangleαij,βij与βij分别为边(i,j)所对着的两个角,如图2所示.拉普拉斯-贝尔特米算子在三角网格X上的离散计算有许多方法[12-15]，其中使用最为普遍的方法为文献[12]中的方法,具体形式为其中ai为顶点xi的Voronoi单元面积，权重令面积矩阵A=diag(ai),权重矩阵M=(mij)，其中据此，离散拉普拉斯-贝尔特米算子可以表示为N×N拉普拉斯矩阵L=A-1M.(7)事实上,在拉普拉斯矩阵L中,若令边(i,j)的权重ωij=1,j∈N(i),且各顶点处的面积ai均相等时，此时L称为二值型图拉普拉斯矩阵或连接型拉普拉斯矩阵,该矩阵仅仅反映顶点间的连接关系.从中可以看出，只有当网格分布非常均匀时，二值型图拉普拉矩阵才会高度逼近拉普拉斯贝尔特米矩阵.拉普拉斯贝尔特米算子的特征值和离散特征函数等价于拉普拉斯矩阵L的特征值与特征向量.一般情况下,虽然L不具有对称性,但M和A均具有对称性,且A为正定矩阵,特征系统Lv=λv的求解可转换为广义特征值问题[16]Mv=λAv,(8)但需注意的是,此时特征向量的正交性是关于A内积的,即2.2离散谱流形小波设为拉普拉斯矩阵L的特征系统.由式(1)可知信号f的流形傅里叶变换系数为事实上，由于信号f的能量主要集中在低频部分,实际中并不需要求解出全部的特征值与特征向量,选择前K个特征向量,即，利用即可高度逼近原始信号,此特性保证了在具有较多顶点的三角网格上构建谱流形小波的效率.特别地,位于第i个顶点的脉冲函数δi傅里叶系数为故由式(3)可得尺度为sl,位于三角网格X第i个顶点处的离散小波为由式(5)得相应的位于第i个顶点的尺度函数为进一步由式(4)和(6)可以获得离散小波系数和尺度系数为方便计算，将上述结果写成矩阵形式.令N×K矩阵Φ=(φ1,φ2,…,φK),N维向量首先将傅里叶变换写成矩阵形式，重构得令N×1维向量对角矩阵Λ=diag(λ1,λ2,…,λK)，则有离散小波尺度sj由拉普拉斯矩阵L的特征值上界λmax以及尺度总数J确定.最小和最大尺度分别为s1=x2/λmin和sJ=x1/λmax,其中λmin=λmax/k,k>0.余下的尺度sJ≤sl≤s1等对数分布.参数k由用户给定，其值确定了谱的下界，当k增大时，小波的支撑域也随之增加.在图3中展示了位于模型同一点处的尺度函数和不同尺度的谱流形小波函数,J=7,显然，随着尺度值的变小,谱流形小波在空间域局部性逐渐增加,即具备自适应分析高频信息的能力.图3同一点处的尺度函数与不同尺度的谱流型小波Fig.3Thescalefunctionandthespectralmanifoldwaveletswithvariousscalesatonepoint.(a)Thescalefunction;(b)ThespectralmanifoldwaveletwithscaleS1;(c)ThespectralmanifoldwaveletwithscaleS2;(d)ThespectralmanifoldwaveletwithscaleS32.3快速谱流形小波分解和重构当需要处理顶点个数非常多的三角网格时,拉普拉斯矩阵特征值分解十分耗时,若直接采用式(7)和(8)计算小波系数,无法满足实际应用需要.此外,在很多应用中,除了需要分析信号之外，还需要对小波系数进行一定的处理，利用处理后的小波系数重构新的信号.文献[4]提出了快速求解谱图小波系数和重构的方法,其核心思想是利用切比雪夫多项式逼近尺度核函数核和小波生成核函数,将信号滤波过程表示成拉普拉斯矩阵的多项式与信号的乘积,避免了特征值分解过程,只需要计算矩阵与向量的代数运算即可.重构则是利用共轭梯度算法以及多项式逼近，求出小波系数与给定小波系数满足L2范数最小的信号.在此快速算法的基础上,谱流形小波亦可建立快速分解与重构的方法，只需要将输入信号和输出乘以顶点面积权重即可.现总结谱流形小波分解算法如下:(带号为快速算法计算步骤,不需要特征值分解).谱流形小波算法(快速算法):输入：给定信号f∈RN；输出：矩阵Step1给定参数k和M,以及尺度总数J；Step2利用式(7)计算拉普拉斯矩阵L=A-1W；Step3求解广义特征值分解Wv=λAv，求得特征向量矩阵Φ=(φ1,φ2,…,φK)以及对角矩阵Λ=diag(λ1,λ2,…,λK)；(Step3计算L的最大特征值λmax)；Step4给定小波生成核函数g；Step5按照式(10-11)计算以及(Step5采用文献[4]中的多项式逼近近似方法快速计算Wf).3实验与结果实验使用MatlabR2017a软件，在具有Intel(R)CoreTMi7-4790,CPU3.60GHz和16.0GBRAM的PC机上进行.3.1与SGW的比较在图4中,我们分别在具有规则三角网格与不规则三角网格的立方体上建立谱图小波和谱流形小波.图4第一行立方体网格分布均匀,在立方体尖角处分别建立这两种小波,结果显示谱流形小波具有明显的对称性,每个面上的支撑域十分规则.而谱图小波支撑域边缘模糊,不具有对称性.第二行的立方体在每个面上的网格密度差异较大,同样在立方体尖点处建立这两种小波,可以看到谱图小波形状比第一种情况发生了很大变化,相比之下,谱流型小波只在密度特别大的那一侧发生了轻微的变形.这说明,谱流型小波能更有效地捕捉模型的内蕴几何性质,不易受网格质量的影响.图4规则网格化和非规则网格化模型上的谱图小波和谱流形小波Fig.4Thespectralgraphwaveletsandspectralmanifoldwaveletsontheregularandirregularmeshes,respectively.(a)Theoriginalmodels;(b)Thespectralgraphwavelets;(c)Thespectralmanifoldwavelets3.2三维模型多分辨表示与经典小波相似,利用谱流形小波可实现信号的多分辨表示.设为信号f的逼近,参数J′=1,2,…,J,随着其值的增大，的逼近精度逐渐提高.在图5中,将各顶点的-x,-y,-z坐标分别作为输入信号,即3个N×1向量x=(xi),y=(yi),z=(zi)，参数J′选取不同值，利用式(12)多分辨表示模型.显然,J′越大,模型细节越丰富.3.3去噪利用信号的多分辨表示，可实现对噪声模型的光顺.因为噪声一般属于高频信息,这些信息包含在l值较大的小波系数里.故一种简单的去噪方法是在重构模型时适当去掉坐标函数的高频小波系数.在图6中展示了利用文献[17-20]和本文谱流形小波去噪的结果,结果显示本文方法在去掉模型噪声的同时依然保持了模型的主要特征.4结论利用谱图理论,谱图小波将经典小波这一强有力的信号分析工具推广到非规则拓扑空间-图域,然而在三角网格上建立谱图小波时仅仅利用了网格顶点之间的连接信息,几何信息丢失严重.为此,本文利用拉普拉斯-贝尔特米算子的特征系统,在谱图小波的基础上构建了谱流形小波.相比谱图小波,谱流形小波更能反映模型的内蕴几何特征,且不易受模型网格化质量的影响.此外,本文利用谱流形小波实现了模型去噪、多分辨表示等几何处理,方法简单,且计算效率高.然而,与经典小波不同的是,谱流形小波并非正交小波,存在较大冗余度,如何在流形上构建正交的小波基,将是以后的研究方向之一.此外,本文中的应用仅是对模型顶点处的坐标信号进行处理,事实上任何定义在三角网格上的信号,如模型的曲率,颜色等信号都可以利用谱流形小波进行分析,应用领域可涉及细节迁移、模型压缩、模型形状分析等多个领域,这也是谱流形小波未来的研究方向.图5模型多分辨表示Fig.5Themulti-resolutionrepresentationsofthemodels.(a)Theoriginalmodels；(b)ThereconstructionresultswithJ′=1;(c)J′=2;(d)J′=3and(e)J′=5图6模型去噪结果比较Fig.6Thecomparisonofthedenoisingresults.(a)Theoriginalmodelswithnoise;(b)Theresultsof[17];(c)Theresultsof[18];(d)Theresultsof[19];(e)Theresultsof[20];(f)Ourresults参考文献：【相关文献】[1]BREMERJC,COIFMANRR,MAGGIONIM,etal.Diffusionwaveletpackets[J].ApplComputHarmonicAnal,2006,21(1):95-112.[2]GELLERD,MAYELIA.Continuouswaveletsoncompactmanifolds[J].MathZeits,2009,262(4):895-927.[3]ANTOINEJP,ROSCAD,VANDERGHEYNSTP.Wavelettransformonmanifolds:oldandnewapproaches[J].ApplComputHarmonicAnal,2010,28(2):189-202.[4]HAMMONDDK,VANDERGHEYNSTP,GRIBONVALR.Waveletsongraphsviaspectralgraphtheory[J].ApplComputHarmonicAnal,2011,30(2):129-150.[5]KIMWH,PACHAURID,HATTC,etal.Waveletbasedmulti-scaleshapefeaturesonarbitrarysurfacesforcorticalthicknessdiscrimination[J].AdvNeuralInformProcSyst,2012,2012:1241-1249.[6]LEONARDIN,VANDVD.WaveletframesongraphsdefinedbyfMRIfunctionalconnectivity[C]//IEEEInternationalSymposiumonBiomedicalImaging:FromNanoToMacroIEEE,Chicago,30Matrth-April,2011:2136-2139.[7]KIMWH,CHUNGMK,SINGHV.Multi-resolutionShapeAnalysisviaNon-EuclideanWavelets:ApplicationstoMeshSegmentationandSurfaceAlignmentProblems[C]//ComputerVisionandPatternRecognitionIEEE,2013:2139-2146.[8]ZHONGM,QINH.Sparseapproximationof3Dshapesviaspectralgraphwavelets[J].VisualComput,2014,30(6-8):751-761.[9]MASOUMIM,HAMZAAB.Spectralshapeclassification:adeeplearningapproach[J].JVisualCommunImageRepresen,2017,43:198-211.[10]LIC,BENHAMZAA.Amultiresolutiondescriptorfordeformable3Dshaperetrieval[J].VisualComput,2013,29(6-8):513-524.[11]LIN,WANGS,ZHONGM,etal.Generalizedlocal-to-globalshapefeaturedetectionbasedongraphwavelets[J].IEEETransVisualComputGraph,2016,22(9):2094-2106.[12]MEYERM,DESBRUNM,SCHRDERP,etal.Discretedifferential-geometryoperatorsfortriangulated2-manifolds[J].MathVisual,2003,3(8-9):35-57.[13]XUG.ConvergentDiscreteLaplace-Beltramioperatorsovertriangularsurfaces[C]//GeometricModelingandProcessing,2004,Proceedings,Beijing,2004:195-204.[14]BELKINM,WANGY,WANGY.Discretelaplaceoperatoronmeshedsurfaces[C]//Twenty-FourthSymposiumonComputationalGeometry,CollegePark,MD,USA.,2008:278-287.[15]VALLETB,LÉVYB.Spectralgeometryprocessingwithmanifoldharmonics[J].ComputGraphForum,2010,27(2):251-260.[16]ZHANGH,VANKAICKO,DYERR.Spectralmeshprocessing[C]//InternationalConferenceonComputerGraphicsandInteractiveTechniques,SIGGRAPHASIA2009,Yokohama,Japan,December16-19,2009,CoursesProceedings,2009:1865-1894.[17]SHACHARF,IDDOD,DANIELC.Bilateralmeshdenoising[J].ACMTransGraph,2003,22(3):950-953.[18]SUNX,ROSINPL,MARTINRR,LANGBEINFC.Fastandeffectivefeature-preservingmeshdenoising[J].IEEETransVisualComputGraph,2007,13(5):925-938.[19]ZHENGY,FUH,OSCARK,TAIC.Bilateralnormalfilteringformeshdenoising[J].IEEETransVisualComputGraph,2011,17(10):1521-1530.[20]LEIH,SCOTTS.MeshdenoisingviaL0minimization[J].ACMTransGraph,2013,32(4):1-8.',)