基变换的三维模型提取技术,包括代码和

基于小波变换的

三维模型特征提取技术学士学位论文答辩答辩人：指导教师：周光有金喜子2008年6月内容提要本课题的主要工作和创新点本课题研究内容三维模型特征提取方法小波加速计算过程综合实验演示参考文献致谢1.本课题的主要工作及创新点1.1主要工作分析了光线投射算法的缺陷，提出了基于三维小波变换的光线投射算法。将小波变换引入到体素表示的三维模型中，分别实现了表面体素小波变换和实体体素小波变换。采用了L2和L1两种相似性度量方式进行匹配。实现了进行特征评价的可视化实验平台。1.2创新点本文提出的小波变换特征提取方法，部分解决了文献[15]存在的球函数定义二义性问题，在一定程度上解决了文献[16]存在的球函数定义的不稳定性。本文提出的方法与文献[15]和文献[16]相比，在查全率、查准率、ST、FT等方面有所提高，算法的复杂度由原来的O(B4)变为O(B3log(B))。[15]G.Burel,H.Henocq,Three-dimensionalinvariantsandtheirapplicationtoobjectrecognition,SignalProcessing,1995,45(1),pp.1-22.[16]D.V.Vranic,Animprovementofrotationinvariant3Dshapedescriptorbasedonfunctionsonconcentricspheres,Proc.Int.Conf.onImageProcessing,2003,volume3,pp.757–760.

2.本课题研究的内容三维模型的表示方法三角网格法和体素法相似性度量方式和评价L2和L1两种基于距离的度量方式Precision-Recall

曲线和FT、ST三维模型的规范化预处理平移不变缩放不变旋转不变三维模型特征提取算法球面调和变换方法光线投射方法小波变换方法（包括三角网格、表面体素和实体体素）综合实验及可视化实验平台3.三维模型特征提取算法3.1

球面调和变换算法3.2光线投射算法3.3小波变换算法3.1球面调和变换算法[12]

将S2Kit从UNIX工作站上向Windows平台上移植，把相应的动态链接库同开发环境结合起来。

[12]刑玉辉,几种重要的三维模型特征提取方法实现研究.吉林大学硕士学位论文,2006年6月.

3.1球面调和变换算法

FST_semi_memo(rdata2，idata2,

rcoeffs，icoeffs,

size， seminaive_naive_table， workspace， 1， cutoff)；

rdata2和idata2两数组用来存储函数输入也就是球面函数在各方向的采样方向的实部和虚部值，对于本文的情况，输入的球面函数采样值均为实数，这样idata2输入为全等于0的数组首地址。rcoeffs和icoeffs两个数组用来存储函数的输出的实部和虚部值，size为截止频率即B，剩下两个参数为系统为了计算而开辟的一块内存间的指针，cutoff默认值为截止频率B

。3.2光线投射算法

G.Burel等在文献[15]中提出了光线投射方法。光线投射算法沿等经度，等纬度方向从模型重心发射出一组射线：

[15]G.Burel,H.Henocq,“Three-dimensionalinvariantsandtheirapplicationtoobjectrecognition,”SignalProcessing,1995,45(1),pp.1-22.3.2光线投射算法

对于每条向外发射的射线，记录它与三维模型表面的最远交点与模型重心之间的距离，这样就可以离散地给出一个球面函数的定义，采样点定义在切比雪夫节点的位置，因此可以直接利用球面调和变换的方法抽取一组旋转不变量。缺陷：对于较为复杂的三维模型，每条射线可能与模型表面有多个交点，因此只考虑最远交点也会丢失很多几何信息

3.2光线投射算法

D.V.Vranic在文献[16]中提出了改进的光线投射算法：[16]D.V.Vranic,“Animprovementofrotationinvariant3Dshapedescriptorbasedonfunctionsonconcentricspheres,”Proc.Int.Conf.onImageProcessing,2003,volume3,pp.757–760.3.2光线投射算法

算法的基本思想：以三维模型的重心为球心的最小包围球剖分成一系列同心球壳，落入每个球壳的射线与模型表面的交点定义一个球坐标方程。一般地，对于每条射线，它与模型表面的多个交点同时落入一个球壳的几率大大降低了，这样就可以尽可能的减少信息的丢失。对应每个球壳的方程的定义：如方向的射线在该球壳内与模型表面无交点，则如有交点，则的值定义为落入该球壳内的最远交点与模型重心的距离。3.2光线投射算法

上面两种方法都没有根本上解决球面函数定义的二义性问题，并且，改进的光线投射算法虽然减轻了出现二义性的几率，但同时带来了新的不稳定性。当引入的同心球面数增大时，三维模型的表面受到噪声因素影响，在不同的球面之间跳跃的几率也同样开始增大，如下图所示。

左图中红色的圆环代表一个球状三维模型的表面，我们可以看到，全部的模型表面均分布在最外层球面内。这样经过球面调和变换后，该模型所有的能量均包含在这层球面内，其它球面对应的能量为零。右图所示带有一个突起噪声的球状三维模型，可以看出，最外层球面内分布的模型表面只占很小一部分，绝大部分模型的表面分布在次外层球面内这样，经过球面调和变换后最外层球面只包含了很小一部分能量，模型的绝大部分能量

3.2光线投射算法

包含在次外层球面内。由于我们用来度量两个三维模型形状差异度的度规是L2范数，即各层球面之间被认为是相对独立的，每个球面只与其它模型对应层数的球面相比较，因此，形状匹配的结果认为这两个模型的形状差异度很大，这显然不符合人的直观感觉。通过上面的分析，本文提出了一种基于小波变换的三维模型特征提取方法。首先利用小波变换来刻画三维模型的特征信息，并以此定义球坐标函数。然后，将这些球函数分解成球面调和变换的序列和，并利用分解的系数构造出一系列旋转不变量，构成该算法抽取的模型几何特征。

3.3小波变换算法

3.3.1小波的分解与重构

首先假设模型被一系列的同心球面包围，最小包围球的半径为M，对于得到的M个切比雪夫采样序列记为：

，定义：：：：：定义两个滤波器算子H和G：

则小波分解算子为：设有M个同心球面构成的三维模型能够被分解成一系列的轮廓球面

和高频

，则小波的分解示意图为：小波的重构与分解类似，只是过程相反。

设表示第层球面的半径，，该球面上的切比雪夫采样点为:

各个分量的小波系数为：

各个分量的尺度系数为：3.3光线投射小波变换算法step1．对模型作平移变换，使其重心与坐标参考系原点重合。step2．对模型作缩放变换，使其最小外包围球的半径为M。step3．沿等经度，等纬度方向从模型重心发射出一组射线:

step4．将模型最小外包围球的半径等分成个小区间,。

对于从模型的重心出发，沿方向向外投射的射线,若该射线在区间内与模型表面无交点,则的值定义为0,否则,的值定义为落入该区间内的最远交点与模型重心的距离。step5.对于所得到的射线的个离散值,进行离散小波变(DWT)(利用上文介绍的小波分解与重构方法):

3.3光线投射小波变换算法

其中,和分别是离散尺度函数和小波函数。step6．令，这样，对于每个切比雪夫采样方向的射线，我们均获得了个值：因此，我们可以定义个离散表示的球面函数：

3.3光线投射小波变换算法step7．对每个球面函数进行球面调和变换，将其分解成频率由低到高的球面调和函数的序列和：

step8．由于球面调和函数相对于旋转其范数不改变,因此对每个球坐标函数,定义L个球面调和函数的L2范数：3.3光线投射小波变换算法step9．组成3D模型的特征向量矩阵,矩阵元素值表示球面调和函数的范数,其中,表示第个球坐标函数,表示第个球面调和函数。表面体素小波变换算法实体体素小波变换算法上面两种算法涉及到三角网格向体素转化的算法、种子填充算法、领域判断、灌水式填充思想等，在本文的研究中文献[12]的作者和AMP实验室提供了大量源代码和参考资料，本人只在此基础上引入小波变换的方法。4小波变换加速计算过程第一步：对方向进行切比雪夫采样，得到采样点序列第二步：Legendre连带多项式的迭代计算[4]：

由

的对称性，对

有第三步：计算1.对积分的离散化。设

[23]崔丽,N维广义拟实数进制小波_小波矩理论及其应用,吉林大学博士学位论文,2002年2月.

则离散化后的结果为：2.对

积分的离散化。由知其离散化后的结果为：3.

对

积分的离散化，最后得到

知其离散化的结果为：第四步：计算特征描述符加速计算的具体体现：第三步的1，可以用一维快速傅立叶变换加速，这样可以使计算量从原来的降低到第三步的2，利用的对称性，可以将算法的计算量减半。。当为偶数时，

当为奇数时，第三步的3，对一维信号

可以用小波分析中的Mallat算法

加以提升。5.综合实验演示

本系统是在IntelPentium42.40GHzCPU、256MB内存级别的PC机上设计实现的，具体的软件环境如下：

操作系统：MicrosoftWindowsXPSP2

开发平台：MicrosoftVisualStudio.Net2003

图形接口：SiliconGraphics’OpenGLLibraryforWindows

计算接口：Matlab6.5

辅助软件：S2kit，Gnuplot

实验模型库：PrincetonShapeBenchmark5.1可视化实验平台显示模块检索实验模块特征提取模块模型文件特征值文件OpenGL接口Gnuplot接口S2kit接口Matlab6.5接口5.2可视化实验平台显示模块显示模块模型显示标准化过程方法可视化

面片显示平移变换旋转变换缩放变换射线法渲染显示体素显示5.3可视化实验平台特征提取读取参数分配存储空间球面调和变换小波变换载入模型创建输出文件并写入文件头取off文件输出特征值结束5.4可视化实验平台检索评价模块5.5

文献[2]的实验结果图5.1固定球面数的射线方法图5.2固定带宽的多层球面射线方法5.5

本文的实验结果图5.3固定球面数的Harr小波变换方法图5.4固定带宽的Harr小波变换方法5.5

本文的实验结果图5.5多种方法的对比图5.6体素表示的Harr小波变换方法5.5

本文的实验结果图5.7表面体素与实体体素的对比图5.8两种相似性度量方法的对比5.5

本文的实验结果图5.9两种度量方式的对比图5.10测试库与训练库的对比6.参考文献

[1]周继来,三维模型检索技术及实现。西北大学博士学位论文,2005年5月.[2]崔晨旸,石教英.三维模型检索中的特征提取技术综述.计算机辅助设计与图形学报.2004年7月.vol16.882~889.[3]杨育彬,林珲,朱庆.基于内容的三维模型检索综述.计算机学报.2004年10月.第27卷第10期．1297-1310.[4]郑伯川,彭维等.3D模型检索技术综述.计算机辅助设计与图形学学报.Vol.16,No.7,July2004.pp873-881.[5]YangYuBin.Researchandapplicationsonthekeytechniquesofcontent-basedimageretrieval[Ph.D.dissertation].DepartmentofComputerScience,NanjingUniversity,Nanjing,2003(inChinese).[6]MallatS.MultiresolutionapproximationsandwaveletorthonormalbasesofL2(R).Trans.Amer.Math.Soc,1989,9;69~87.[7]MallatS.Atheoryformultiresolutionsignalposition;Thewaveletrepresentation.IEEETransonPAMI,1989,7,11(7);764~693.[8]ChuiC.KandWangJ.ZAcardinalsplineapproachtowavelets.Proc.Amer.Math.Coc.,1991,11(3);785~794.[9]WickerhauserMV.Adaptedwaveletanalysisfromtheorytosoftware.IEEEPress,TheInstituteofElectricalandElectronicsEngineers,Inc.NewYork,1994.[10]CoifmanR.andWickerhauserM.Entropybasedalgorithmsforbestbasisselection.IEEETrans.OnIT,1992,38(2);715~717.[11]FunkhouserT.MinP.,KazhdanM.etal..Asearchenginefor3dmodels.ACMTransactionsonGraphics,2003,22(1):83～105.[12]刑玉辉,几种重要的三维模型特征提取方法实现研究.吉林大学硕士学位论文,2006年6月.[13]D.M.Healy,D.Rockmore,P.Kostelec,andS.Moore.FFTsforthe2-sphere-Improvementsandvariations,AdvancesinAppliedMathematics,(toappear).Preprintandcorrespondingsoftware,SpharmonicKit,areavailableat.[14].FFTW快速傅立叶变换软件包.6.参考文献

[15]G..Burel,H.Henocq,“Three-dimensionalinvariantsandtheirapplicationtoobjectrecognition,”SignalProcessing,1995,45(1),pp.1-22.[16]D.V.Vranic,“Animprovementofrotationinvariant3Dshapedes