基于形状朝向多分辨率分析的三维模型检索方法

摘要

本发明公开了一种基于形状朝向多分辨率分析的三维模型检索方法，采用三维形状的面片朝向主成分分析方法获取朝向采样平面；采样三维形状的朝向分布，生成朝向分布的采样函数；分析采样函数，提取采样函数的多分辨率低频小波系数；通过自适应多分辨率特征距离计算方法计算特征距离。本发明能够提高三维模型检索的精度和速度，可以应用于三维模型复用、模型识别、机器人视觉、虚拟现实等领域。

说明书

技术领域

本发明涉及一种三维模型检索方法。

背景技术

在过去的二十多年来，随着计算机的普及、硬件性能的提升、多媒体录制和拍摄设备的广泛应用，多媒体信息已经在各个领域迅速发展，让整个世界变得非常丰富和多彩。多媒体信息主要包括声音、图像、视频、三维模型。目前互联网上、个人和工业用户硬盘上已经充斥了海量的多媒体信息，造成了信息在各个媒介爆炸增长。如何帮助用户在海量内容中找到所需要的多媒体信息，成为多媒体匹配与检索技术的研究对象。每一件多媒体作品的设计和制作都需要很大努力和很长时间，设计人员可以通过多媒体检索与信息重用获取相似信息，并稍加修改制作新的数据，以此提高工作效率；机器人视觉通过多媒体匹配在机器人存储体中检索物体图像等识别物体；防范、验证、侦破等领域利用多媒体匹配技术来查询指纹库、二维/三维人脸库、三维头颅库等匹配相关信息；工业现场可以根据图像匹配自动判定控制信息、故障类型等；交通领域通过车牌识别等进行自动违章记录、高速路口收费等。然而多媒体内容的匹配与检索没有文本内容匹配与检索那样简单，从一篇文字中提取关键文字信息，和从一幅图像等多媒体中提取能代表该图像的描述信息相比，后者只有具有高级思维的人类才可以完全实现。通过计算机提取多媒体的特征是一件极为复杂的工作，是多媒体匹配与检索的核心技术。

三维数字模型是一种比二维图像内容更为丰富真实、更加符合人类视觉特性、更能清楚地表达一个现实三维物体的多媒体数据类型，它的基础数据是三维数字形状，由形状来实现三维数字模型。近些年来，新型的三维形状获取设备不断更新、三维形状建模研究的进展和MAYA、3DMAX、Pro/E、CATIA等三维建模工具的大力推广使得三维形状的设计变得越来越简单，三维模型已经在多媒体领域、虚拟现实、工业设计和制造CAD/CAM、MRI医学三维图像、生物分子与基因结构、游戏、动画角色、人机交互等方面广泛应用。这些广泛应用使得每天有数以兆计的三维模型产生，同时在互联网技术作用下使迅速传播，存在着对三维模型进行匹配与检索的迫切需求。而且，三维模型匹配与检索技术可以应用在三维模型重用中，由于三维模型需要大量的建模工作，它可以帮助设计人员迅速找到相似模型并在现有模型基础上构造新的模型，节约建模时间。另外，还可以应用在多媒体信息检索、CAD模型匹配、机器人三维视觉、生物分子与医学器官模型匹配、机械模型设计支援、三维对象识别与验证、虚拟现实场景物体匹配、动画与游戏角色设计支援、月球与深空对象探测、故障诊断等领域。对基于内容的三维形状匹配与检索技术进行研究已变得非常重要。

目前，实现高效快速的基于内容的三维模型匹配与检索技术已成为国内外多媒体信息识别与检索领域的一个研究热点。国内外公开的文献中，在T.Funkhouser，P.Min，M.Kazhdan，J.Chen，A.Halderman，D.Dobkin，and D.Jacobs，“A search engine for 3Dmodels，”ACM Transactions on Graphics，Vol.22，No.1，pp.83-105，2003.中提出了采用球面调和函数分析了体素化模型，提取了调和系数来描述三维形状的特征；H.Laga，H.Takahashi，and M.Nakajima，“Spherical wavelet descriptors for content-based 3D modelretrieval，”IEEE International Conference on Shape Modeling and Applications，Matsushima，Japan，pp.15-25，Jun.2006.中提出了采用球面小波系数分析了球面延长函数，并采用小波系数来进行描述三维形状的特征；T.Furuya and R.Ohbuchi，“DenseSampling and Fast Encoding for 3D Model Retrieval Using Bag-of-Visual Features，”ACMInternational Conference on Image and Video Retrieval，Santorini，Greece，pp.1-8，Jul.2009.中提出了深度缓存图的特征向量降维方法。

但上述文献提出的特征提取方法有几点不足：

(1)以上方法通过计算距离来提取形状特征。然而，计算形状表面到质心的距离、或者形状表面到包围盒的深度缓存距离，如果质心或者包围盒发生微小变化，可以造成提取的距离函数发生很大变化，方法的稳定性差；

(2)有些方法的形状标准化过程采用了主成分分析PCA或者连续主成分分析CPCA方法，由于基于PCA和CPCA方法计算出来的主轴稳定性不够高，对于后续的特征提取方法造成影响；

(3)一些方法在特征提取算法的时间复杂度上考虑较少，使得提取特征的时间较长，失去了特征提取精度与特征提取时间的平衡，影响了实时的在线应用。

发明内容

为了克服现有技术稳定性差、提取时间较长和特征区分力低的不足，本发明提供一种基于形状朝向多分辨率分析的三维形状特征提取方法，该方法增加了方法的稳定性，保证预处理对后期的特征提取尽量小的影响，提高了特征提取的速度，增强了特征的区分力。

本发明解决其技术问题所采用的技术方案包括以下步骤：

(1)采用三维形状的面片朝向主成分分析方法获取朝向采样平面：采用三维形状的面片朝向主成分分析方法获取三个朝向的主轴，并根据该三个垂直主轴设置六个形状朝向采样平面，该采样平面在空间上构成封闭，将三维形状封闭在内。该步骤需要计算三维形状各面片朝向的法向量和三维形状的平均法向量，由此构成的法向量协方差矩阵，在该矩阵中，对每一个面片的法向量进行面积大小加权，按大小顺序排序矩阵的特征值和相应的三个特征向量，从而根据确定的三个特征向量作为朝向主轴以计算形状朝向的采样平面。采样平面满足两个条件：(a)每个特征向量确定两个采样平面，该特征向量与两个采样平面垂直，而且这两个采样平面应该分别位于三维模型的两侧，不与三维模型相交，三个特征向量共确定出六个采样平面；(b)六个采样平面将三维模型完全包围在内，由于采样平面将采集三维形状的朝向参数，因此采样平面距离三维模型的远近可以任意设定，这与包围盒的概念不同。

(2)采样三维形状的朝向分布，生成朝向分布的采样函数：通过步骤(1)生成的采样平面按照一定数量级均匀发射采样射线，与三维形状的表面相交，计算采样射线和与之相交的表面法线的内积，将内积值作为形状朝向函数的函数值，采样时采用2的指数倍进行均匀采样，以利于采用快速方法对采样函数进行分析。

(3)分析采样函数，提取采样函数的多分辨率低频小波系数：选择简单高效的小波母函数，由于朝向函数是区域函数，对于区域运算比较擅长的是Daubechies等母函数，通过该母函数的位移和尺度变换，可以构成一组函数基，利用函数基并根据尺度函数和小波函数对朝向函数按照尺度进行分解，对于二维采样函数采用的是先进行行变换、再进行列变换的方法进行降维，获取多个分辨率下的多组低频小波系数，低频小波系数构成多分辨率的特征。

(4)通过自适应多分辨率特征距离计算方法计算特征距离：利用多采样函数的最小Manhattan距离计算两个三维模型之间某分辨率下的特征距离，同时利用对分辨率加权方法计算所有分辨率下两个三维模型的特征距离。所采用的加权方法为自适应加权，利用样本数据库使检索理论中的First Tier参数最大化，以获取最优的多分辨率特征加权系数。通过这种距离衡量方法使特征距离最大化和最优化。

本发明的有益效果是：本发明考虑了三维形状的朝向，而放弃了提取距离特征的传统方式，从而增加了方法的稳定性。针对三维形状特征提取前的预处理阶段进行了认真考虑和论证，发现基于主成分分析PCA和连续主成分分析CPCA的预处理方法对后续的特征提取有一定的影响，因此本发明提出了一种基于形状朝向主成分分析方法来获取形状采样平面，由于形状朝向的主成分相对稳定，与普通主成分分析PCA或者连续主成分分析CPCA的预处理过程相比，对后期特征提取影响较小。在获取原始特征时，本发明提出了形状朝向作为最原始的分析对象，与之前的基于距离原始特征的方法相比，在加强特征提取的鲁棒性的同时，可以在形状朝向很少的采样率下获取大量的特征。它采用了多分辨率小波分析方法对形状朝向函数进行了快速分析，提高了低频特征提取的速度，有利于将方法推向实时在线的应用场合。本发明提出了自适应多分辨率特征距离计算方法，以保证不同分辨率有着不同距离衡量方式，以保证特征距离的最大化和最优化，提高了特征区分力。

下面结合附图和实施实例对本发明进一步说明。

附图说明

图1为本发明所述三维模型检索的系统流程图；

图2为本发明的三维模型特征提取的流程图；

图3为本发明的形状朝向采样方法的说明图；

图4为本发明的形状朝向采样方法的加速方法说明图；

图5为本发明的朝向采样函数的多分辨率系数获取的说明图。

具体实施方式

如图1所示详细的解释了三维模型检索的系统流程图。本发明的该项技术可以实现三维模型网络搜索的系统功能。通过用户在查询接口输入一个三维模型，计划搜索该模型的所有相似模型，检索系统将该模型的检索请求通过网络传送给搜索引擎，搜索引擎做出响应，将检索到符合条件的三维模型传送给用户，并按照相似度高低对三维模型进行排序。具体流程是，在系统接收到客户端用户发送到的三维模型的检索请求，首先经过特征提取算法获取三维模型的特征向量，该特征向量可以唯一的表达一个三维模型而且具有高度辨别力，可以区分出和其他三维模型的区别。特征提取算法分析形状朝向，获取多分辨率特征。系统采用自适应特征比较方法来逐一计算该特征向量与特征数据库的距离，获取与特征数据库相对应的三维模型数据库中的三维模型。三维模型数据库通过离线特征提取计算数据库中每一个模型的特征，并将这些特征存放在特征数据库。因此，特征数据库与三维模型数据库有着一一对应的关系，这项特征提取工作是离线进行的，不占用在线运行的时间。检索系统根据特征比较的结果生成相似度的排序，从而根据相似度由大到小来排序三维模型，排在最前面的代表最相似的三维模型，排序方法可以采用快速排序等成熟的方法。检索系统将排序的模型列表通过网络响应返回给客户端用户，该列表由二维缩略图组成，每一个缩略图都对应着相应的一个三维模型，同时将返回算法的检索时间，用户可以浏览到相似三维模型的二维缩略图，当点击二维缩略图后可以看到三维模型的三维视图，三维视图均可以通过鼠标滑动来观察三维模型的详细立体内容。

如图2所示为本发明的三维模型特征提取的过程。先对三维模型进行面片朝向主成分分析，计算模型的面片法向量的三个垂直的主轴，获取与主轴垂直的六个相应的朝向采样平面。按照某一个分辨率均匀分割每一个朝向采样平面，从每一个朝向采样平面发射朝向采样射线，并生成朝向采样函数，并对该函数进行多分辨率分析获取多分辨率小波系数，最终作为朝向的多分辨率特征。需要注意的是该特征并不是单一特征，而是包含着多个不同分辨率的特征。

结合附图，具体实施步骤以下做详细说明。

一、采用三维形状的面片朝向主成分分析方法获取朝向采样平面。

该步骤采用三维形状的面片朝向主成分分析方法获取三个朝向的主轴，并根据该三个垂直主轴设置六个形状朝向采样平面，该采样平面在空间上构成封闭，将三维形状封闭在内。该步骤需要计算三维形状各面片朝向的法向量和三维形状的平均法向量，由此构成的法向量协方差矩阵，在该矩阵中，对每一个面片的法向量进行面积大小加权，按大小顺序排序矩阵的特征值和相应的三个特征向量，从而根据确定的三个特征向量作为朝向主轴以计算形状朝向的采样平面。计算如下：

假设任意一个三维形状，共有N个面片，任取一个面片T_i，面片面积为f_i，代表面片朝向的法向量为n_i，该法向量经过标准化处理，由法向量构成的协方差矩阵C为：

$>C=\frac{1}{f}\underset{i=1}{\overset{N}{\Sigma }}(n_i-n_0){(n_i-n_0)}^T$>

其中f为三维形状的表面总面积，表达式为：

$>f=\underset{i=1}{\overset{N}{\Sigma }}{f}_i$>

其中n₀是所有面片朝向的平均法向量。

将形状朝向的协方差矩阵进行特征运算，公式如下：

Ce_i＝λ_ie_i

求取特征值如下：

{λ₁，λ₂，λ₃}

和对应的特征向量如下：

{e₁，e₂，e₃}

并根据特征值从大到小的顺序，排列特征向量。

根据确定的三个特征向量计算形状朝向的采样平面，该采样平面满足两个条件：

(a)每个特征向量确定两个采样平面，该特征向量与两个采样平面垂直，而且这两个采样平面应该分别位于三维模型的两侧，不与三维模型相交，三个特征向量共确定出六个采样平面；

(b)六个采样平面将三维模型完全包围在内，由于采样平面将采集三维形状的朝向参数，因此采样平面相距三维模型的远近可以任意设定，这与包围盒的概念不同。

二、采样三维形状的朝向分布，生成朝向分布的采样函数。

通过步骤(1)生成的采样平面按照一定数量级均匀发射采样射线，与三维形状的表面相交，计算采样射线和与之相交的表面法线的内积，将内积值作为形状朝向函数的函数值，采样时采用2的指数倍进行均匀采样，以利于采用快速方法对采样函数进行分析。

获取朝向分布的目的是：朝向分布是三维形状面片集的重要特征，人类可以根据任意一个三维形状的朝向将其区分，朝向具有三维形状特征的代表性。朝向特征具有不随采样距离远近而变化的特点，这与采样距离函数相比具有鲁棒性，例如如果一个三维形状发生轻微变化，那么立体包围盒就要发生变化，随之采集的深度缓存的距离就会变化，然而采样朝向不受远近距离的影响。

如图3，具体方法如下：

(1)将每一个采样平面分割为N×N的小正方体，那么采样分辨率为N，为了进行快速运算和分析方便，N应该为2的任意指数倍，例如N＝64，并且分割要均匀；

(2)从每一个小正方体的中心O发射一条射线V，与三维形状的第一个面片相交；

(3)获取第一个面片的法向量L，并与射线法向量V求向量内积(L，-V)，这里负号存在的原因是将射线方向取反，可以使用右手定则将L旋转至-V。

(4)将向量内积(L，-V)值作为采样值赋予该小正方体中心，所有小正方体均做采样运算。在赋值之前两个向量必须预先标准化。

(5)这样可以得到一个N×N的二维均匀采样函数f(x，y)。

最终二维采样函数的公式如下：

$>f(x,y)=\left(\begin{array}{ccc}{O}_{\mathrm{0,0}}& ···& O_{0,N-1}\\ O_{x,0}& O_{x,y}& O_{x,N-1}\\ O_{N-\mathrm{1,0}}& ···& O_{N-1,N-1}\end{array}\right)$>

由于采样平面共有六个，因此，采样函数也有六个相应的函数组成，如下所示：

f_o(x，y)，...，f_l(x，y)，...，f_s(x，y)，l ∈[0，5]

其中l表示第l个采样平面。

在实际运算中，该发明设计了一种基于候选法的采样加速方法，图4给出了该方法。图中，任取一个三角形面片i，计算出采样平面内6个正方形组成的包围面，该包围面将该三角形最小包围，确定6条可能与之相交的采样射线，图4中两个实心圆和四个圆环表示6条射线的起点。该方法不再考虑其他采样射线，直接从6个采样点发射的射线中，通过计算判定2个真正与三角形面片相交的两条射线，图中所示的实心圆为两条射线的起点。计算相应2个采样点的采样内积值。这种基于候选法的采样加速方法可以大大节省采样时间。

三、分析采样函数，提取采样函数的多分辨率低频小波系数。

该步骤选择简单高效的小波母函数，由于朝向函数是区域函数，对于区域运算比较擅长的是Daubechies等母函数，通过该母函数的位移和尺度变换，可以构成一组函数基，利用函数基并根据尺度函数和小波函数对朝向函数按照尺度进行分解，对于二维采样函数采用的是，先进行行变换、再进行列变换的方法进行降维，获取多个分辨率下的多组低频小波系数，低频小波系数构成多分辨率的特征。

本发明在处理采样函数的特点是，通过小波分解的方式获取低分辨率系数，来表征朝向采样函数具有的低频特征。获取低频特征有多种方法，例如傅里叶分析，首先傅里叶分析不能提供多分辨率模式，为下一步骤的自适应多分辨率特征距离计算不能提供支持；另外还有一个重要原因是，对于二维函数，傅里叶分析的计算复杂度是O(n²lgn)，然而小波分析的计算复杂度是O(n²)，选用傅里叶分析对于整个三维模型特征提取时间上有很大影响。因此本发明采用小波分解方式获取多分辨率低频特征。

如图5，具体步骤如下：

(1)选择简单高效的小波母函数，由于朝向函数是区域函数，对于区域运算比较擅长的是Daubechies等母函数，通过该母函数的位移和尺度变换，可以构成一组函数基；

(2)根据尺度函数和小波函数对朝向函数按照尺度进行分解，一般对于二维函数采用的是，先进行行变换、再进行列变换的方法进行降维。

(3)获取多个分辨率(例如4-5个)下的多组低频小波系数。每组小波系数的维数为2^s×2^s，这里s表示第s个分辨率。当s＝1时收敛成4个点，包含信息量过少，对特征表达有所影响，本发明从s＝2开始算起，最低分辨率的维数应为4×4，如果s＝5，那么高分辨率的维数应为32×32，依次类推。在实际应用中可以取出5组分辨率下的小波低频系数进行分析。

由于存在六个采样平面和对应的六个采样函数，小波分解应该对每一个采样函数进行分别分析。

四、通过自适应多分辨率特征距离计算方法计算特征距离。

该步骤利用多采样函数的最小Manhattan距离计算两个三维模型之间某分辨率下的特征距离，同时利用对分辨率加权方法计算所有分辨率下的两个三维模型的特征距离。所采用的加权方法为自适应加权，利用样本数据库使检索理论中的First Tier参数最大化，以获取最优的多分辨率特征加权系数。通过这种距离衡量方法使特征距离最大化和最优化。

该发明中设计了一种主要针对多分辨率特征的自适应特征距离计算方法，该方法根据不同分辨率下的特征具有不同的区分力，通过自适应加权的方式来提高具有高度区分力的某分辨率特征所占比重，从而提高整个多分辨率特征的距离区分度。

具体计算如下：

(1)采用多采样函数的最小Manhattan距离计算两个三维模型之间的某分辨率下的特征距离。

设在任意一个分辨率k之下，采用多采样函数的最小Manhattan距离计算在该分辨率下两个三维模型之间的距离d_k。其中l表示第l个采样平面函数，在这里共计采用六个采样平面，可以包围成一个封闭的立方体。在具体实施时，也可以采用12个或者24个采样平面组成一个封闭的十二面体或者二十四面体，目的是可以采样所有的形状朝向而不遗漏。在分辨率k下两个三维模型之间的距离为：

d_k＝min{d_k，l}，l∈[0，5]

d_k从所有采样平面函数之间的距离中取最近距离。两个三维模型在分辨率k下任意一个采样平面函数l的距离可以依据如下特征距离计算公式：

d_kl＝||V_1，k，l-V_2，k，l||

其中V_1，k，l表示第一个三维模型在分辨率k下第l个采样平面的小波低频系数，V_2，k，l表示第二个三维模型在分辨率k下第l个采样平面的小波低频系数。小波低频系数可以与人的视觉相近，因此在相似距离量度上采用Manhattan距离。

(2)采用对分辨率加权方法计算两个三维模型的特征距离。

由于不同分辨率下的小波低频系数具有不同的特征区分能力，如何衡量在某一分辨率下的特征区分能力，本发明设计了两种距离计算方法，第一种方法是固定加权方法，对不同分辨率下不同特征采用固定系数w_k加权；第二种方法是自适应加权方法，根据查询内容和分类自动计算加权系数w_k。第一种方法的缺陷是不会针对所有类的检索得出最优的结果。在本发明中采用第二种自适应加权方法对不同分辨率下的小波系数特征进行自适应加权。加权方法计算的距离公式如下：

$>d=\underset{k=1}{\overset{m}{\Sigma }}{w}_k{d}_k$>

(3)采用自适应加权的手段，利用样本数据库使检索理论中的First Tier参数最大化。

下面给出First Tier计算方法。假设在三维模型的样本数据库D中存在一个三维模型m_i，该三维模型归属于类C_j，模型数据库大小即维数为N，类C_j的大小即维数为R，三维模型m_i归属于类C_j，即

m_i∈C_j

在该数据库中查询该模型，并将不包括该对象本身的查询结果按照距离从小到大进行排序，即最相似的模型排在最前面。现在只关心排序在前R-1的模型列表，R为该归属类的维数，R减去1的目的是不统计该对象本身。假设在前R-1的模型列表中有P个模型属于同一类别C_j，相对于该模型m_i来说，

FT_i＝P/(R-1)

其中FT_i表示该模型m_i的First Tier参数值。理想的First Tier值应该为1.0，表现为输入检索对象时，前R-1个(不包括输入对象本身)全部属于同一类别，说明该特征距离具有最完全的区分能力。在小于1.0的情况下，First Tier值越大越好，说明距离区分能力越强。

通过上述方法统计所有模型的First Tier，并针对样本数据库维数N求出平均值。平均First Tier为，

$>\mathrm{FT}=\underset{i=1}{\overset{N}{\Sigma }}{\mathrm{FT}}_i$>

公式中的First Tier参数为在某一个分辨率下的计算结果。

然后计算所有分辨率k下的First Tier值，赋给w_k作为权重，从而为分辨率k下的距离加权。表达如下：

w_k＝FT_k

这种自适应多分辨率特征距离计算方法最终计算的结果可以表达为：

$>d=\underset{k=1}{\overset{m}{\Sigma }}{w}_k{d}_k=\underset{k=1}{\overset{m}{\Sigma }}{\mathrm{FT}}_k{d}_k$>

采用这种自适应加权方法来确定最优的特征距离分布。之后在实际在线检索时，通过计算输入模型与三维模型数据库之间的这种特征距离，可以排序相似的三维数据模型。