一种三维模型表征方法、检索方法及检索系统

摘要

本发明提供一种三维模型表征方法、检索方法及检索系统，该表征方法包括利用云计算，MapReduce的集群计算能力，根据三维模型的体素之间的热量传递快速计算每个内部体素的热核特征值。该表征方法还包括选择热核特征值小于预定阈值的内部体素作为骨架体素；骨架体素、骨架体素的热核特征值以及骨架体素之间的热量传递构成该三维模型的热核骨架特征描述符。本发明适用于检索非刚性三维模型并且能够高效地提取三维模型的特征。

说明书

技术领域

本发明涉及信息检索及可视化技术领域，尤其涉及一种三维模型表征 方法、检索方法及检索系统。

背景技术

早在上个世纪90年代，三维模型就已作为一种有效的表现形式广泛 应用于工业设计、三维动画、历史文物保护等多种领域。随着三维模型数 据库规模的逐渐扩大，对三维模型检索的需求也愈加急迫，高精度高效率 的三维模型检索已经成为当前研究的一个热点。通常，三维模型检索采用 三维模型特征提取算法，提取出三维模型的形状特征描述符，通过比较三 维模型间的形状特征描述符来检索出形状相似的三维模型。在计算机动 画、虚拟现实、三维游戏等领域的实践应用中，三维模型，尤其是具备铰 链、关节等结构、变化性较强的三维模型，易受到刚性变换（rigid or iso  metric transformations），从而发生形变，这类三维模型被定义为非刚性三 维模型，参见图1。现有的大部分三维模型特征提取技术都不适用于非刚 性三维模型，这是因为当前特征提取算法大多基于三维模型的点集信息和 视图信息，而点集信息和视图信息均不能承受刚性变换。当三维模型发生 形变后，其点集和视图信息都将发生改变，导致在刚性变换前后所提取出 的特征存在很大差异，形状特征描述符相去甚远，不能保证非刚性模型检 索的准确性。因此，针对非刚性三维模型检索的研究意义重大。

现有的非刚性三维模型检索技术包括一种基于热核特征的非刚性三 维模型检索技术，该方法通过使用热核特征提取算法（Heat Kernel Signa  ture，简称HKS）来提取三维模型的热核特征。热核特征提取算法源自于 热核（Heat Kernel）——热扩散（heat diffusion）的基本解。热核具备很 多优质特性：能够通过多尺度的方式将模型几何特征组织起来、极具稳定 性，并且热核特征能够承受刚性变换。因此，将热核作为三维模型的特征 可用于检索非刚性三维模型。

然而，现有的热核特征提取算法在表示三维模型的结构特征时具有一 定的局限性。现有技术中都是在点集的基础上运用热核特征提取算法，所 得到的热核特征仅限于体现三维模型的表面信息，而对于那些具有孔、洞 等结构的三维模型来说，则很难体现其内部特征。此外，由于热核需要计 算三维模型的拉普拉斯-贝特拉密算子，其计算量大且复杂度高，而现有的 单机环境通常限制了计算速度，使得热核特征提取算法实施起来效率较 低。

发明内容

为解决上述问题，根据本发明的一个实施例，提供一种三维模型表征 方法，该方法包括：

步骤1）、根据三维模型的体素之间的热量传递计算每个内部体素的热核 特征值；

步骤2）、选择热核特征值小于预定阈值的内部体素作为骨架体素；由骨 架体素、骨架体素的热核特征值以及骨架体素之间的热量传递构成该三维 模型的热核骨架特征描述符。

在一个实施例中，所述三维模型表征方法还包括：

步骤0）、将三维模型体素化，得到该三维模型的内部体素。

在一个实施例中，在步骤1）中，使用MapReduce计算每个内部体素的 热核特征值。

在进一步的实施例中，步骤1）包括：

步骤11）、在Map阶段，并行地计算在一定时间内三维模型的每个体素 传递至该三维模型所有体素的热量；

步骤12）、对Map的输出进行排序并将结果输入Reduce；以及

步骤13）、在Reduce阶段，将每个内部体素从其他体素传递得到的热量 汇总，得到内部体素的热核特征值。

根据本发明的一个实施例，还提供一种三维模型检索方法，包括：

步骤A）、根据权利要求1-4中任何一个所述的三维模型表征方法得到待 检索三维模型的热核骨架特征描述符；

步骤B）、基于所述待检索三维模型的热核骨架特征描述符，将所述待 检索三维模型与数据库中的每个三维模型的热核骨架特征描述符进行匹配， 检索出与所述待检索三维模型相似的三维模型。

在一个实施例中，在步骤B）中，将待检索三维模型与数据库中的一个 三维模型进行匹配包括：

步骤a）、根据骨架体素分别构建所述待检索三维模型和该数据库中的三 维模型的骨架图G₁和G₂；

步骤b）、根据骨架体素的热核特征值以及骨架体素之间的热量传递构 建骨架图G₁和G₂的关联图H_v，检测关联图H_v的最大团得到骨架图G₁和G₂的 最大公共子图；

步骤c）、根据下式计算所匹配的两个三维模型的相似性：

L＝N_m/max(N₁,N₂)

其中，N_m表示骨架图G₁和G₂的最大公共子图的节点个数，N₁和N₂分 别表示骨架图G₁和G₂的节点个数。

在一个实施例中，在步骤b）中，构建关联图H_v包括：

步骤i）、对于骨架图G₁中每个节点遍历骨架图G₂中的每个节点，组成 节点对，如果组成节点对的两个节点的热核特征值之差的绝对值小于阈值 δ1，则将该节点对加入关联图H_v作为其节点；

步骤ii）、对于关联图H_v中的每两个节点u_H＝(u₁,u₂)和v_H＝(v₁,v₂)，如果 骨架图G₁中的边e₁＝(u₁,v₁)与骨架图G₂中的边e₂＝(u₂,v₂)的属性值之差的绝对 值小于阈值δ2，则构造一条连通边e_H＝<u_H,v_H>加入关联图H_v；如果骨架图 G₁中的节点u₁和v₁、骨架图G₂中的节点u₂和v₂各不相邻，则构造一条非连 通边e_H＝<u_H,v_H>加入关联图H_v；其中，边的属性值是两个端点间在一定时 间内传递的热量值。

在一个实施例中，步骤a）包括：

步骤a1）、将骨架体素分为节点体素、一般体素和终端体素；其中，节 点体素至少有三个邻接体素，一般体素有两个邻接体素，终端体素有一个邻 接体素；

步骤a2）、寻找靠近三维模型重心的节点体素作为种子节点；

步骤a3）、从该种子节点开始连接与其直接相连的节点体素，且依次向 外连接直到没有节点体素为止，并且将终端体素作为各连接分支的结束点； 其中直接相连指两个节点体素之间包含一般体素且不包含节点体素和终端 体素。

在一个实施例中，步骤B）之前还包括：根据权利要求1-4中任何一个 所述的三维模型表征方法得到数据库中每个三维模型的热核骨架特征描述 符。

在一个实施例中，所述三维模型检索方法还包括：构建三维模型索引数 据库，该三维模型索引数据库包括数据库中每个三维模型的热核骨架特征描 述符与该三维模型的存储位置之间的对应关系。

根据本发明的一个实施例，还提供一种模型表征设备，该设备包括：

用于根据三维模型的体素之间的热量传递计算每个内部体素的热核特 征值的装置；以及用于选择热核特征值小于预定阈值的内部体素作为骨架体 素的装置；其中，由骨架体素、骨架体素的热核特征值以及骨架体素之间 的热量传递构成该三维模型的热核骨架特征描述符。

在一个实施例中，所述模型表征设备还包括：

数据预处理装置，用于将三维模型体素化，得到该三维模型的内部体素。

根据本发明的一个实施例，还提供一种三维模型检索系统，包括：

上述模型表征设备，用于得到待检索三维模型的热核骨架特征描述符； 以及模型匹配设备，基于所述待检索三维模型的热核骨架特征描述符，将所 述待检索三维模型与数据库中的每个三维模型的热核骨架特征描述符进行 匹配，检索出与所述待检索三维模型相似的三维模型。

在一个实施例中，所述系统还包括：

索引设备，用于构建三维模型索引数据库，该三维模型索引数据库包括 数据库中每个三维模型的热核骨架特征描述符与该三维模型的存储位置之 间的对应关系。

本发明将针对连续点集的热核计算扩展到三维模型的体素，得到每个 内部体素的热核特征值，再根据该热核特征值选取三维模型的骨架体素， 将骨架特征与热核特征结合起来，作为三维模型的热核骨架特征描述符来 表征三维模型，进而进行三维模型的检索。此外，加入了云计算技术和M  apReduce的应用，利用云的计算能力解决复杂的特征提取算法在计算速度 方面的限制，从而可以达到如下的有益效果：

本发明所提取的三维模型特征既满足刚性形变的不变性，又具有骨架 的拓扑特性，能够体现有孔、洞等结构的三维模型的内部特征，并且拥有 普遍性，适用于检索任意三维模型。此外，本发明能够高效地提取三维模 型的特征。

附图说明

图1是根据本发明一个实施例的非刚性三维模型的示意图；

图2是根据本发明一个实施例的三维模型表征方法的流程图；

图3是根据本发明一个实施例的三角面片体素化的示意图；

图4是根据本发明一个实施例的用MapReduce实现HKS算法的流程 图；

图5是根据本发明一个实施例的三维模型检索方法的流程图；

图6是根据本发明一个实施例的构建三维模型的热核骨架特征描述索 引的流程图；以及

图7a-7c是根据本发明一个实施例的关联图构造示意图，其中图7a是 骨架图G1，图7b是骨架图G2，图7c是关联图。

具体实施方式

下面结合附图和具体实施方式对本发明加以说明。应当理解，此处所 描述的具体实施例仅用以解释本发明，并不用于限定本发明。

根据本发明的一个实施例，提供一种三维模型表征方法。参考图2且 简要概括，该方法包括：三维模型的预处理以及提取三维模型的热核骨架 特征描述符。

步骤一、三维模型的预处理

概括而言，预处理过程可以包括：解析所获取的三维模型文件，并且 将该三维模型的原始数据体素化，得到该三维模型的体素结构。

对获取到的三维模型文件进行解析，从而获得由三角面片组成的三维 模型，其数据由顶点集和面片集构成，接着进行体素化处理。体素化是指 在保证精度的前提下，将由三角面片或者其他边界表示的几何模型转化为 由离散的体素集合表示的过程。如本领域技术人员所公知的，体素是指分 布在正交网格中的单位立方体。在三维离散空间中，体素有三种邻接关系： 26-邻接、18-邻接和6-邻接。如果两个体素之间存在一个公共顶点、或者 一条公共边，或者一个公共面，则称这两个体素是26-邻接的；如果两个 体素之间存在一条公共边或者一个公共面，则称这两个体素是18-邻接的； 如果两个体素之间仅存在一个公共面，则称这两个体素是6-邻接的。

在三维欧几里德空间中，任意一点都存在唯一的一个体素与之对应， 即通过坐标变换可找到三维空间中的点所对应的体素。可以根据公式（1） 对三维模型中的点p(x,y,z)进行体素化，公式（2）给出了点p(x,y,z)所对应 的体素编号：

$\left(\begin{array}{c}{\mathrm{vox}}_i=\mathrm{floor}((x-{\min }_x)/w)\\ {\mathrm{vox}}_j=\mathrm{floor}((y-{\min }_y)/w)\\ {\mathrm{vox}}_k=\mathrm{floor}((z-{\min }_z)/w)\end{array}\right)---\left(1\right)$

index＝vox_k×R_x×R_y+vox_j×R_x+vox_i  （2）

其中，(min_x,min_y,min_z)为三维模型最小点的坐标，w为体素宽度，即 一个立方体体素的边长，R_x×R_y×R_z为体素模型的分辨率，floor是一个向下 取整函数，(vox_i,vox_j,vox_k)为点p(x,y,z)所对应的体素坐标。

在一个实施例中，可采用快速体素化算法对三维模型进行表面体素 化。快速体素化是将任意大小的三角面片细划为一系列边长均小于体素宽 度的极小子三角面片，其划分点所对应的体素就是该三角面片的体素化结 果，如此，可快速找出三维模型某一表面的三角面片所对应的体素。以图 3所示的三角面片abc为例，快速体素化算法的步骤如下：

（1）、计算△abc的三条边的长度，进行比较得到最大值l_max；

（2）、用最大边长l_max除以体素宽度w，并向上取整，由此得到边的划 分系数n；

（3）、将△abc的ab、ac边分别划分n等分，得到等分点b_i及c_i，其 中i=0,1,…,n，通过这样的划分可以保证ab、ac边所得到的子线段长度均 小于体素宽度w；

（4）、接着依次连接对应的b_i及c_i得到线段b_ic_i，并将b_ic_i划分为i等分， 各等分点为每个子三角形的顶点，即体素化的对象。最后，只需将各等分 点进行体素化即可得到该三角面片abc的体素化结果。

按照以上步骤（1）-（4）遍历三维模型的所有三角面片即可得到该三 维模型所对应的表面体素。

在得到表面体素之后，可通过flooding算法来得到三维模型的内部体 素，从而完成三维模型的预处理过程。flooding算法类似于种子填充算法， 分为向前和向后两步完成。在一个实施例中，初始化时，将所有体素的标 志位flag均设置为1，在经过表面体素化后，使表面体素的标志位设置为 0，体素(0,0,0)和(R_x-1,R_y-1,R_z-1)为外部体素。在向前行进时，设vox(0,0,0)的 标志位flag=-1。从体素vox(1,0,0)开始，搜索每一体素的26邻域，在其 26邻域中只要有体素的标志位flag=-1，则设置该体素的标志位为-1；在 向后行进时，设vox(R_x-1,R_y-1,R_z-1)的标志位flag=-1，从 vox(R_x-2,R_y-1,R_z-1)开始，搜索每一体素的26邻域，同样的，在其26邻 域中只要有体素的标志位flag=-1，则设置该体素的标志位为-1。flooding 算法操作完成后，所有外部体素的标志位flag=-1，表面体素的标志位 flag=0，而内部体素的标志位flag=1，从而得到标志位为1的内部体素。 表面体素和内部体素（下文统称体素）是计算三维模型的热核骨架特征描 述符的输入数据。

步骤二、提取三维模型的热核骨架特征描述符

本发明在所得到的体素的基础上，提供一种基于热核的骨架提取算法 来获得三维模型的热核骨架特征描述符。该算法包括计算内部体素的热核 特征值，并且筛选出骨架体素，从而得到热核骨架特征描述符。在一个实 施例中，还可以采用MapReduce技术来计算热核特征。基于热核的骨架提 取算法所获得的三维模型特征具有刚性不变性，适用于非刚性模型。

首先，将针对点的热核特征计算扩展到针对体素的热核特征计算。

根据现有技术可知，在某一形状M内的热扩散方程可表示为：

$\mathrm{\Delta Mu}(x,t)=-\frac{\partial u(x,t)}{\partial t}---\left(3\right)$

其中，ΔM是形状M的拉普拉斯-贝特拉密（Laplace-Beltrami）算子， u(x,t)表示在时间为t时，x位置的热量值，x表示M形状上的任意位置。 则当时间t极小时有：

$\underset{t\to 0}{\lim }u(x,t)=f\left(x\right)---\left(4\right)$

其中，f是形状M上给定的初始热分布，f(x)就是x位置的初始热量 值。

对于形状M上给定的初始热分布f来说，H_t(f)表示在时间为t时形状 M上的热分布情况，H_t被定义为热能算子（heat operator）。而ΔM和H_t都 可以表示为M的实值函数，H_t满足H_t＝e^-tΔM。其中，若用λ表示ΔM的特征 值，则e^-λt是H_t相应特征函数的特征值。则对于任意形状M有：

u(x,t)＝H_tf(x)＝∫_Mk_t(x,y)f(y)dy                       （5）

其中，k_t(x,y)是满足公式（3）的最小函数，且称之为热核（Heat Kernel）。 即对于x处给定的初始热量，经过时间段t，由x传递至y处的热量总和。 对于给定的形状M，热核有以下特征分解：

$k_t(x,y)=\underset{i=0}{\overset{\infty }{\Sigma }}{e}^{-{\lambda }_{i}t}{\phi }_i\left(x\right){\phi }_i\left(y\right)---\left(6\right)$

其中，λ_i和φ_i分别对应拉普拉斯-贝特拉密算子的第i个特征值和特征 函数。由于拉普拉斯-贝特拉密算子本身具备的对于刚性形变的不变性，因 此热核能够表示三维模型的固有几何信息，而不随刚性形变而变化，能够 承受住三维模型的刚性变换。

由于热核是一种点的特征描述符，因此在较小的时间段t内，k_t(x,·)主 要由x的邻接点来决定。换言之，在较小的时间段t内，k_t(x,·)可表示为x附 近的局部特征信息，但k_t(x,·)的计算量仍然很大。因此，在进一步的实施例 中，为降低计算量，可将热核特征定义为：

HKS(x,t)＝k_t(x,x)   （7）

则有：

$k_t(x,x)=\underset{i=0}{\overset{\infty }{\Sigma }}{e}^{-{\lambda }_{i}t}{\phi }_i{\left(x\right)}^2---\left(8\right)$

如果将热核特征应用于体素上，则在极小的t时间段内，热核特征可 以表示该体素内的局部特征。此时x即表示三维模型的体素，由此，将基 于点的热核特征扩展到了体素中，通过体素的热核特征值的计算，可获得 每个体素的几何内部信息。

由于对于三维模型的体素结构，计算每个内部体素的热核特征值需要 较大计算量。在一个实施例中，可运用MapReduce技术来快速计算每个体 素的热核特征值，利用集群并行计算的能力提升计算速度，从而大大降低 了计算量与计算时间。如图4所示，利用MapReduce技术将输入的体素数 据集划分成一个个独立的体素数据块，由Map以完全并行的方式处理它 们，Map阶段通过公式（6）计算三维模型中当前体素对所有体素的热量 传递k_t(x,y)。MapReduc框架会对Map的输出先进行排序，然后把结果输 入给Reduce。通常作业的输入和输出都会被存储在文件系统中， MapReduce框架和分布式文件系统是运行在一组相同的节点上的，也就是 说，计算节点和存储节点通常在一起。这种配置允许MapReduce框架在那 些已经存好数据的节点上高效地调度任务，达到快速计算的效果。接下来， 在Reduce阶段对每个体素的热量统计汇总（从其他体素热扩散得到的热 量相加），得到体素的热核特征值，即得到内部体素的热核特征值。

在得到每个内部体素在一定时间段t内热扩散后的热核特征值（或称 热核值）之后，根据计算得到的热核特征值筛选出三维模型的骨架体素。

由于每个体素所设置的初始热量值相同，若某一体素与更多体素具有 相关性，那么该体素所具备的热量值应该较小。这是因为热核表示的是热 扩散方程的一种基本解，若某一体素与更多体素相关联，那么该体素的热 核具备的热量在确定的时间段t内，应比其他体素扩散的更快，也就是说， t时间段后，该体素具备的热量较小。骨架体素较普通体素来说，与周围 体素的关联性较大，因此选取热核特征值较小的内部体素作为骨架体素。 从而通过对内部体素的进一步筛选，得到三维模型的骨架体素。

筛选出骨架体素后，即获得三维模型的热核骨架特征描述符。该热核 骨架特征描述符能够体现三维模型的骨架体素以及骨架体素的热核特征 （包括热核特征值以及与其他体素在一段时间内的热量传递情况）。这里 所提取出的热核骨架特征描述符具备热核特征，能够很好地承受刚性变 换，并且具有稳定等特性，不易受到噪声的影响。骨架体素本身又能体现 三维模型的拓扑结构，能够同时反映三维模型的拓扑与形状特征，并减少 原始模型的冗余信息。因此所提取出的热核骨架特征描述符具有更加丰 富、稳定的特征信息，为三维模型检索，尤其是非刚性三维模型检索奠定 了良好基础。

根据本发明的一个实施例，还提供一种适用于上述三维模型表征方法 的三维模型检索方法。参考图5且简要概括，该方法包括：提取用户提交 的待检索三维模型的热核骨架特征描述符；基于该热核骨架特征描述符， 将用户提交的三维模型与三维模型数据库中的三维模型进行匹配，从该数 据库中得到与用户提交的三维模型相似度大的三维模型。其中，在匹配三 维模型之前，还需要对三维模型数据库中的三维模型进行处理，即提取出 该数据库中每个三维模型的热核骨架特征描述符，用于与用户提交的待检 索三维模型进行匹配。

第一步、提取用户提交的待检索三维模型的热核骨架特征描述符，以 及三维模型数据库中的三维模型的热核骨架特征描述符。

可采用上文描述的三维模型表征方法来提取三维模型的热核骨架特 征描述符。其中，对于三维模型数据库中存储的三维模型，在提取前可以 首先将该数据库中的三维模型存储到Hadoop集群的文件系统HDFS上， 使得其三维模型能够得到合理有效的管理。对于用户提交的待检索三维模 型来说，在进行提取前还要判断用户所提交的文件是否符合格式要求。如 果提交格式符合要求，则对该三维模型进行处理；否则，对用户返回提示 出错信息，要求重新上传三维模型或者取消操作。以PSB（Princeton Shape  Benchmark）datasets、McGill3D Shape Datasets、SHREC'10datasets等数 据库为例，这些数据库的三维模型文件主要为.off文件格式。对于这类数 据库，用户提交的待检索三维模型也应符合.off文件格式。

在一个实施例中，对于三维模型数据库中的三维模型来说，在提取了 热核骨架特征描述符之后，还可以构建三维模型的热核骨架特征描述符索 引，形成三维模型索引数据库。例如，可在Hadoop集群上构建三维模型 索引数据库。参考图6，该构建过程包括：

在提取出每个三维模型的热核骨架之后，将三维模型的骨架文件存储 在HDFS文件系统中，并将其作为作业的输入，在Map中对其进行特征向 量的提取，输出该三维模型在HDFS中的存储位置URL的MD5值作为 key，以及该三维模型的特征向量组成的字符串作为value（即三维模型热 核骨架特征描述符）。由此得到热核骨架特征描述符与索引号之间的对应 关系（key，value），最终经Reduce输出三维模型数据库的索引文件，构 成三维模型索引数据库，便于接下来的三维模型特征匹配。

第二步、将用户提交的待检索三维模型与数据库中的每一个三维模型 进行匹配，最终检索出相似的三维模型。

在一个实施例中，可首先搜索三维模型索引数据库，将待检索三维模 型的热核骨架特征描述符与索引数据库中的热核骨架特征描述符进行匹 配，从而得到相似的三维模型的key，接着可使用该key找到该相似三维 模型在HDFS中的存储位置。

在一个实施例中，匹配三维模型可以包括以下步骤：

步骤1、首先将三维模型的骨架转换为骨架树或骨架图的形式

通过每个骨架体素的连通骨架体素（例如，与该骨架体素26-邻接的 骨架体素）个数，可以将骨架体素分为节点体素、一般体素和终端体素三 种。其中，节点体素的邻接连通体素至少有三个；一般体素则有两个邻接 体素；而终端体素只有一个邻接体素；其中，如果两个骨架体素之间仅含 有一般体素则称这两个骨架体素是直接相连的。通过对体素邻接情况的筛 选，可迅速获得节点体素和终端体素。找到一个靠近三维模型重心的节点 体素作为种子节点，由该节点开始向周围扩散，连接与其直接相连的节点 体素，由此依次向外连接，直到没有节点体素为止，并且将终端体素作为 各连接分支最后的结束点，最终构建出骨架树或骨架图。

步骤2、采用近似求解基于边的最大公共子图（maximum edge induced  subgraph）的方法，来实现热核骨架特征描述符的匹配，返回三维模型之 间的相似度。

基于边的最大公共子图算法可分为以下2个步骤：

（1）、根据两个匹配模型的骨架图构建一个特定的关联图H_v。对于骨 架图G₁中的任意一个节点v_i∈V₁(1≤i≤n)，遍历骨架图G₂中的每一个节点 u_j∈V₂(1≤j≤m)，组成顶点对(v_i,u_j)，若v_i与u_j具有相同的属性值（即热核值）， 则将(v_i,u_j)加入H_v的点集V_H作为一个节点。如上文所述，点的属性值即点 在一定时间内具有的热核值，换言之，就是在一定时间内该体素点与三维 模型全部体素之间热扩散后，从其他体素热扩散得到的热量总值其中，x表示当前体素，y_i表示三维模型的体素。由于在提取骨架体素之 前的Reduce阶段已经计算得到每个内部体素的热核值（热核特征值），该 热核值是与其他体素相关联之后得到的体现其几何特征的热信息，能够表 示该点的属性。在本步骤中，如果两点热核值之差的绝对值小于一个极小 阈值δ1，则这两个点具有相同的热核值，具有相同的属性值。这说明两个 点在两个三维模型中与其他体素之间的关联性相同，所体现的几何结构相 同。

任取H_v中的两个节点u_H＝(u₁,u₂)和v_H＝(v₁,v₂)，若u₁≠v₁，u₂≠v₂且图G₁中 的边e₁＝(u₁,v₁)与图G₂中的边e₂＝(u₂,v₂)具有相同的属性值，即两个端点之间 在一定时间内传递的热量值；或者图G₁中的节点u₁和v₁，图G₂中的节点u₂和 v₂各不相邻，则构造一条边e_H＝<u_H,v_H>，加入到关联图H_v的边集E_H中并作 为它的一条边。将上述两种情况下构造的边分别称为连通边和非连通边， 由此得到两个骨架图的关联图。该边的属性值即两个端点间在一定时间t 内传递的热量值k_t(u₁,v₁)和k_t(u₂,v₂)，即边的热量值。两端点之间的热量传递 可表示这两个端点基于热的关联性。由于端点u₁和u₂、v₁和v₂属性值（即 热核值）相同，因此，如果k_t(u₁,v₁)和k_t(u₂,v₂)值也相同，那么表示两端点间 （即边）的热值特征相同。在本步骤中，如果两条边的热量值之差的绝对 值小于一个极小阈值δ2，则这两条边具有相同热量值，具有相同属性值， 说明边的端点间基于热的关联性相同。

图7(a)-7(c)给出了构造关联图的一个示例，图中的圆、正方形和三角 形节点分别表示属性不同的顶点，图7(a)和图7(b)分别表示骨架图G₁和G₂。 图7(c)为两个骨架图的关联图H_v，H_v由顶点N_aB、N_aA、N_bD、N_bE、N_cC和N_cE组成，顶点之间的连通边用实线表示，非连通边用虚线表示。在图7(c)中， 三角形内的顶点集合称为H_v的最大团，即骨架图G₁和G₂的最大公共子图。

（2）、通过检测关联图的最大团来实现最大公共子图的检测。在一个 实施例中，采用Bron和Kerbosch提出的最大团检测算法检测出两个骨架 图的所有最大公共子图。将查找出的最大公共子图对应于两个模型上相似 的特征或局部结构，用所有最大公共子图的节点个数与两个骨架图的节点 个数较大者之比，来描述两个模型的相似性大小。为规范描述，将相似结 构的尺度记为：

L＝N_m/max(N₁,N₂)    （9）

其中，N_m表示所有最大公共子图节点的个数，N₁和N₂分别表示两个 骨架图的节点个数。L越大表示两个模型之间的相似性越大，它们所包含 的相似特征或局部结构就越多。

在将待检索三维模型与三维模型数据库中所有的三维模型进行匹配 后，可得到与用户提交的三维模型相似度最大的模型。

根据本发明的一个实施例，还提供一种三维模型检索系统。包括模型 表征设备、索引设备、模型匹配设备以及三维模型数据库。在一个实施例 中，可采用基于Hadoop集群的HDFS来存储三维模型数据库中的三维模 型。

其中，模型表征设备包括数据预处理装置和特征提取装置。数据预处 理装置用于对Hadoop集群的文件系统HDFS上存储的三维模型及用户提 交的待查询三维模型，获取并处理其模型文件，解析数据文本并将其体素 化，得到三维模型的体素结构。特征提取装置用于针对体素化后的三维模 型体素数据，利用MapReduce技术快速提取三维模型的热核骨架特征描述 符。其中，根据三维模型的体素在一段时间内的热量传递计算每个内部体素 的热核特征值，选择热核特征值小于预定阈值的内部体素作为骨架体素。

索引设备用于在Hadoop集群上构建三维模型索引数据库，其将三维 模型数据库中的每个三维模型热核骨架特征描述符与索引号一一对应。

模型匹配设备用于进行HDFS上存储的三维模型与用户提交的待检索 三维模型之间的热核骨架特征描述符的相似性匹配。计算用户提交模型与 三维模型数据库中的模型的相似度，并且返回给用户具有相似结构特征的 三维模型。

应该注意到并理解，在不脱离后附的权利要求所要求的本发明的精神 和范围的情况下，能够对上述详细描述的本发明做出各种修改和改进。因 此，要求保护的技术方案的范围不受所给出的任何特定示范教导的限制。