基于小波变换的三维模型特征提取技术

基于小波变换的三维模型特征提取技术,学士学位论文答辩,2008年6月,内容提要,本课题的主要工作和创新点本课题研究内容三维模型特征提取方法小波加速计算过程综合实验演示参考文献致谢,1. 本课题的主要工作及创新点,1.1 主要工作分析了光线投射算法的缺陷，提出了基于三维小波变换的光线投射算法。将小波变换引入到体素表示的三维模型中，分别实现了表面体素小波变换和实体体素小波变换。采用了L2和L1两种相似性度量方式进行匹配。实现了进行特征评价的可视化实验平台。,1.2 创新点,本文提出的小波变换特征提取方法，部分解决了文献15存在的球函数定义二义性问题，在一定程度上解决了文献16存在的球函数定义的不稳定性。本文提出的方法与文献15和文献16相比，在查全率、查准率、ST、FT等方面有所提高，算法的复杂度由原来的O(B4)变为O(B3log(B)。,15G. Burel, H. Henocq, Three-dimensional invariants and their application to object recognition, Signal Processing, 1995, 45(1), pp. 1-22.16 D. V. Vranic, An improvement of rotation invariant 3D shape descriptor based on functions on concentric spheres, Proc. Int. Conf. on Image Processing, 2003, volume 3, pp. 757760.,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-dimensional invariants and their application to object recognition,” Signal Processing, 1995, 45(1), pp. 1-22.,3.2 光线投射算法,对于每条向外发射的射线，记录它与三维模型表面的最远交点与模型重心之间的距离，这样就可以离散地给出一个球面函数的定义，采样点定义在切比雪夫节点的位置，因此可以直接利用球面调和变换的方法抽取一组旋转不变量。 缺陷：对于较为复杂的三维模型，每条射线可能与模型表面有多个交点，因此只考虑最远交点也会丢失很多几何信息,3.2 光线投射算法,D. V. Vranic在文献16中提出了改进的光线投射算法：,16 D. V. Vranic, “An improvement of rotation invariant 3D shape descriptor based on functions on concentric spheres,” Proc. Int. Conf. on Image Processing, 2003, volume 3, pp. 757760.,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. 综合实验演示,本系统是在Intel Pentium 4 2.40GHz CPU、256MB内存级别的PC机上设计实现的，具体的软件环境如下：,操作系统：Microsoft Windows XP SP2 开发平台：Microsoft Visual Studio. Net 2003 图形接口：Silicon Graphics OpenGL Library for Windows 计算接口：Matlab 6.5 辅助软件：S2kit，Gnuplot 实验模型库：Princeton Shape Benchmark,5.1 可视化实验平台,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月. vol 16. 882889.3 杨育彬, 林珲, 朱庆. 基于内容的三维模型检索综述.计算机学报.2004年10月.第27卷 第10期1297-1310.4 郑伯川, 彭维等. 3D模型检索技术综述. 计算机辅助设计与图形学学报. Vol.16, No.7, July 2004. pp 873-881.5 Yang Yu Bin. Research and applications on the key techniques of content-based image retrieval Ph. D.dissertation . Department of Computer Science , Nanjing University , Nanjing , 2003 (in Chinese).6 Mallat S. Multiresolution approximations and wavelet orthonormal bases of L2(R).Trans.Amer.Math.Soc,1989,9;6987.7 Mallat S.A theory for multiresolution signal decomposition; The wavelet representation.IEEE Trans on PAMI,1989,7,11(7);764693.8 Chui C.K and Wang J.Z A cardinal spline approach to wavelets.Proc. Amer.Math.Coc.,1991,11(3);785794.9 Wickerhauser M V. Adapted wavelet analysis from theory to software. IEEE Press, The Institute of Electrical and Electronics Engineers,Inc.New York,1994.10 Coifman R. and Wickerhauser M. Entropy based algorithms for best basis selection.IEEE Trans.On IT,1992,38(2);715717.11 Funkhouser T. Min P., Kazhdan M. et al. A search engine for 3d models. ACM Transactions on Graphics , 2003 , 22 (1) : 83105.12 刑玉辉,几种重要的三维模型特征提取方法实现研究. 吉林大学硕士学位论文,2006年6月.13 D.M. Healy, D. Rockmore, P. Kostelec, and S. Moore. FFTs for the 2-sphere -Improvements and variations, Advances in Applied Mathematics, (to appear). Preprint and corresponding software ,SpharmonicKit ,areavailableat. 14 /. FFTW快速傅立叶变换软件包.,6.参考文献,15 G. Burel, H. Henocq, “Three-dimensional invariants and their application to object recognition,”Signal Processing, 1995,45(1),pp.1-22 .16 D. V. Vranic, “An improvement of rotation invariant 3D shape descriptor based on functions on concentric spheres,” Proc. Int. Conf. on Image Proce