一种三维模型特征提取与压缩算法

刘作军

(淮阴工学院计算机工程学院,江苏淮安 223003)

0 引 言

近些年来,随着图像技术、三维图形建模技术以及三维数据获取技术的发展,出现了越来越多的三维模型.三维的模型包含的数据量远远多于二维图形,其设计费时费力.同时,网络技术的发展也使研究者的思路发生了巨大变化,以前设计模型时考虑的是如何构造三维模型,现在则是考虑如何去寻找现有的三维模型资源,以及如何利用现有的三维模型构建新的三维模型,这种基于模型的设计使得产品设计变得更加容易和快捷[1].因此,如何迅速检索到所需要的三维模型成为继文本、图像、音频和视频检索之后的又一个热门研究领域[2,3].

对于三维模型检索,特征提取是整个检索系统最主要和关键的问题.通常,对特征提取有两个基本要求:一个是提取的特征要足够区分各个三维模型,保证较高的性能;二是特征信息量不能太大,否则检索速度会很低.这两个要求是相互制约的,效率和速度很难同时满足,这也是三维模型检索一直以来难以解决的问题[4].基于此,本文提出一种三维模型特征提取和压缩算法,该算法能同时确保三维模型检索的性能和速度.

1 预处理

通常,三维模型所包含的信息自由度很高,其空间位置、尺寸和方位等信息都具有不确定性.用户在进行模型检索的时候,提供的模型的坐标系很有可能与数据库中的模型坐标系不一致,例如,示例模型和数据库中的模型在坐标系中的位置不同,或尺寸不一致,或对于坐标系旋转的角度不同.如果不做处理直接比较则很可能是相同的模型却被检索系统视为不同的模型而影响检索的准确性[5,6],因此,在提取特征前需要对三维模型做预处理.

1.1 预处理思路

要实现三维模型的检索,首先要把模型进行参数化处理,而参数化的三维模型必然要用到很多变量参数来表示.变量太多,会增加分析问题的难度与复杂性,增加计算的工作量,从而使检索的速度大大下降.并且多个变量之间又有一定的相关关系.因此,在各个变量之间相关关系研究的基础上,尽量用较少的新变量代替原来较多的变量,并使这些较少的新变量尽可能多地保留原来较多的变量所反映的信息.这样做既节省存储和后续计算处理的开销,同时,还能保证计算的速率与检索的性能.本文采用主元分析方法实现该功能,主元分析是把原来多个变量转化为少数几个综合指标的一种统计分析方法,从数学角度看是一种降维处理技术.

1.2 预处理步骤

假设 p个因变量,y1,y2,…,yp,构成线性方程组(见式1),每个方程分别由自变量 x1,x2,…,xm,构成,m是自变量的个数,小于 p,xi是均值为“0”,标准差为“1”的标准变量.

方程组(1)也可以表示成矩阵的形式,

在这个数学模型中,X为因子变量,A为载荷矩阵.根据矩阵方程组计算的协方差矩阵S为,

式中,D为e的协方差矩阵.由于 X是标准化的,所以协方差矩阵就是相关系数矩阵R,

αij的绝对值越大,则组合向量zi与原向量xi的关系越强.通过坐标变换方法把原来的p个相关变量yi做线性变换,可转换成不相关的变量zi,

这里,z1是 y1,y2,…,yp所有线性组合中方差最大的,其综合原有变量 y1,y2,y3,…,yp的能力最强,是第一主成分,z2,z3的方差依此递减,分别是第二～～和第三等主成分.我们首先设R=AA′,同时求出R的p个特征值λk以及对应的特征向量βk=(βk1,βk2, βk3,…,βkp)′,k=1,2,3,…,p.

可惜他跳下来还没有摔死，那时候建筑工地的脚手架还是竹子搭的，他掉到五楼的时候，被一根过长的竹竿挡了一下，竹竿弹了一弹，他的身体像个沙袋一样也向上弹了弹，才又重新落到了地上。他没有死，乌红的血从脑袋里汩汩流了出来，他还没有死，他还在说话，他想说什么？可惜没人听得清，他吸进呼出的都是血泡，他像一条缺水的鱼一样，翕动着嘴巴。白色的脑浆流出来了，他还没有死……虽然他说的最后一句话，别人听清了，爸爸说：救救我，我还不想死，我还想活……

由式(6)可以计算出载荷矩阵的解,

由于分析的目的是减少变量个数,因此,在计算载荷矩阵时,一般不选取所有特征值,而只选取前m个特征值和对应的特征向量,得到具有 m个公共变量的载荷矩阵,

经主元分析变换,三维模型顶点分布最广泛的方向处于第一主轴上,是第一主成分,顶点分布次广泛的方向处于第二主轴上,是第二主成分,依此类推,得到第三主成分.这样就使模型分布最广泛的方向都分布在X,Y,Z三个坐标轴上.该方法使模型在平移、旋转和比例上都实现了归一化,由于提取的是模型的主要成分,从而提高了模型处理的计算速度.

2 特征提取与向量压缩

特征提取与压缩是三维模型检索算法最重要和最关键的部分,其直接关系到检索的性能与速度[7-10].

2.1 透视投影

预处理后的三维模型的重心调整到三维坐标系的原点,模型顶点分布最广泛的3个方向分别调整到三维坐标系的3个主坐标轴方向,同时实现了模型的尺寸归一化、坐标比例归一化和旋转归一化,预处理调整后的效果如图1(a)所示.

为了获取三维模型的特征,我们首先把模型从几个方向透视投影,使观察点看到的信息量尽可能大而又不丢失模型表面的信息,同时在姿态调整的基础上用一个正四面体包围该模型(见图1(b)).正四面体和三维坐标系的3个坐标轴有6个交点,分别是 K、L、M、K′、L′、M′,其中,K、L、M是正四面体与3个坐标轴正向的交点,K′、L′、M′是正四面体和3个坐标轴负向的交点.把这6个交点作为透视投影的视点,则6个视点都取自于模型信息量分布最广泛的方向.投影后图像上每个点的属性值是与该图像平面垂直方向上的点与观测点的最近距离,即图像上点(a,b)的属性值是f(a,b),

图1 透视投影变换示意图

其中,A是点(a,b)到垂直于平面的方向上模型表面点的最短距离,B是点到图像中心的距离,这样得到的图像是一幅N×N大小的距离图像,投影点属性包含了投影点和三维模型的空间距离信息.由此,经过6个视点方向的透视投影得到6幅距离图像,实现了模型从三维空间到二维空间的转换.

2.2 特征提取

因为本文的透视投影是把模型三角片的顶点进行投影得到的点集,所以我们采用离散的傅立叶变换提取模型特征.但直接进行傅立叶变换,时间复杂度是O(M2N2),这样计算量会相对比较大.为了降低计算的时间复杂度以提高计算的速度,我们把傅立叶变换转化为两次一维傅立叶变换,降维后的傅立叶变换为,

经过傅立叶变换后,再进一步把透视投影图像转换成6幅M×N大小的频域能量分布图像,从而在频域提取模型的向量特征,同时,参考文献[11]取图像的1/8低频区域,6幅图像生成的特征向量的维数是6×(64/8)×(64/8)=384,得到的特征向量形式如下,

其中,vixy表示第i幅图像频率变量分别为x、y时的能量值.

2.3 向量压缩

目前,提取特征向量的方法存在两大问题:一是低频采样必然会丢失大量的信息,检索的性能会降低;二是生成的向量特征维数依然很高,检索速度也会降低[11].因此,我们考虑把每一幅图像在频域直接提取高维向量,然后把高维向量进行有效压缩,每一幅图像的高维向量压缩成一维,同时确保一维向量具有最大的可区分度.具体的方法是把高维向量投影到一条直线上.我们利用 Fisher判别准则方法[12]寻找这样一条直线,使得在这条直线上特征向量投影的区分度最好.

取一个样本集合 X,包含 N个d维样本向量, x1,x2,…,xN,其中,N1个是满意模型类的样本,记为 X1,N2个是不满意模型样本,记为 X2.若对 xn的分量做线性组合,可以得到标量 yn,

这样就得到N个一维样本yn组成的集合,并可分为两个子集 X1和 X2.从几何上看,如果 ‖w‖=1,则每个yn就是相对应的xn到方向为w的直线上的投影.实际上,w的绝对值无关紧要,重要的是w的方向,其方向不同,将使样本投影后的可分离程度不同,从而直接影响识别效果.

利用Fisher判别准则降维方法可以得到w＊,

w＊就是使Fisher准则函数取极大值时的解,也就是高维空间X到一维空间Y的最好投影方向.有了投影方向w＊就可以把高维样本xn映射成一维向量yn.

每一幅图像的特征向量映射成一维向量,每一个三维模型的6幅图像特征向量组合成一个三维模型的6维特征向量(v0,v1,v2,v3,v4,v5),这样就可保证信息不缺失,既确保了系统检索的性能又能确保系统检索的速度. i

3 实验验证

为了测试本文提出的算法的性能,我们将获取的特征向量送入神经网络实现模型的检索.实验时,我们从数据库中选择3类模型对算法进行测试,这3类模型分别是桌子模型、兔子模型、灯具模型.我们选择这3类模型是因为数据库中这类模型数量都比较大、种类比较多、相近和相似模型多,可以很好地测试算法的性能.

3.1 实验结果

下面仅仅给出用桌子模型进行测试的实验结果(见图2),其他模型检索结果与此类似.

图2展示了检索给出的示例模型和检索的实验结果,结果按相似度高低排序.通过检索结果可以看出检索的性能.

图2 模型检索结果

表1给出了实验中算法运行所需要的时间,通过时间分析可以看出系统检索的速度.

表2 模型检索时间

3.2 实验分析

从图2的检索结果和表1的检索速度可以看出,本算法在具有较高检索性能的同时还具有较低的时间复杂度,解决了检索性能和检索速度的矛盾,实现了三维模型的高速检索.也就是说,本文所提出的提取模型高维向量特征的方法保证了检索性能,同时进一步把特征压缩后提高了检索的速度,且对性能的影响不是很大.实验结果表明该算法取得了较好的效果.

[1]Lu Hanqing,K ong Weixin,Liao Ming,et al.A Review of Content-Based Parsing and Retrieving for Image and Video[J].Acta Automatic Silica,2009,21(1):56-69.

[2]Yang Yubin.Research and Applications on Key Techniques of Content-Based Image Retrieval[D].Nanjing:Nanjing University, 2008:77-83.

[3]Funkhouser T,Min P,Kazhdan M.Search Engine for3D Models [J].ACM Transactions on Graphics,2003,22(1):83-105.

[4]Neal J,Shapiro G.Symbolic Representation for3D Object Feature Detection[C]//Proceeding of International Conference Pattern Recognition.Barcelona:IEEE Press,2007:1221-1224.

[5]潘 翔,张三元,张 引,等.一种基于拓扑连接图的三维模型检索方法[J].计算机学报,2008,27(9):1250-1257.

[6]潘 红,吴 飞,庄越挺.基于深度加权法向映射的三维模型检索[J].计算机辅助设计与图形学报,2007,17(2): 247-252.

[7]刘 一.基于内容的三维模型比较与检索算法研究[D].北京:北京大学,2008.

[8]崔 晨.三维模型检索中关键技术的研究[J].计算机辅助设计与图形学报,2009,10(21):48-53.

[9]章志勇.三维模型几何相似性比较的研究[D].杭州:浙江大学,2009.

[10]Zhang C,Chen T.Efficient Feature Extraction for2D/3D Objects in Mesh Representation[C]//Proceeding of IEEE International Conference on Image Processing.Greece:IEEE Press, 2009:935-938.

[11]贺 巍,覃 征,周 婧.一种基于视点距离的三维模型特征提取算法[J].小型微型计算机系统,2009,8(32):33 -39.

[12]边肇祺,张学工.模式识别[M].北京:清华大学出版社, 2007:31-43.