一种基于彩色旋转图像的三维部分形状匹配和检索方法

摘要

本发明涉及一种基于彩色旋转图像的三维部分形状匹配和检索方法，包括步骤：对三维形状表面进行采样，得到一系列基点，在每个基点上计算一种局部形状特征；对所述局部形状特征进行聚类得到聚类中心，保存所述聚类中心构成局部形状特征词典；在所述局部形状特征词典中查找和每个局部形状特征最接近的聚类中心，并将该特征用聚类中心的编号替代；对每个带有聚类中心编号的基点计算旋转图像形状特征，生成彩色旋转图像特征；计算两个彩色旋转图像间的相似性及两个三维形状之间的相似性。该方法解决了传统三维模型检索方法不适用于基于部分形状相似性查找，和对三维形状数据中的噪声和遮挡较为敏感的问题。

权利要求

1.一种三维部分形状匹配和检索方法，其特征在于，所述方法包括以下步骤：S1，对三维数据库中的每个三维形状的表面进行采样，得到一系列基点，并在每个基点上计算任意一种局部形状特征；

S2，对所述局部形状特征进行聚类得到聚类中心，给每个聚类中心设置编号，保存所述聚类中心及其编号，构成局部形状特征词典；

S3，在所述局部形状特征词典中查找和每个局部形状特征最接近的聚类中心，并将该特征用聚类中心的编号替代，记录三维形状各个基点对应的局部形状特征的聚类中心的编号；

S4，按照旋转图像的构造方法，重新对S1中的每个带有聚类中心编号的基点计算旋转图像形状特征，生成彩色旋转图像特征；

S5，依次进行直方图求交、图像扩散，计算两个彩色旋转图像间的相似性及两个三维形状之间的相似性；

其中，

所述彩色旋转图像特征的计算方法包括如下步骤：

S4-1，对于三维形状上的每个基点，将一小平面沿该基点处三维形状的法线为轴旋转，在旋转过程中将三维形状的每个标记颜色的基点投影到该小平面上，形成彩色的二维平面；

S4-2，在对二维平面进行离散化的同时，生成三维直方图(c，i，j)，其中c为聚类中心编号，(i，j)为二维空间的离散坐标；

S4-3，根据小平面上每个彩色点的位置将三维直方图中对应的单元加一；

S4-4，对彩色旋转图像进行规则化，即将三维直方图的全部单元的数字的和归一；

S4-5：记录所述彩色旋转图像中所有出现的聚类中心编号；

S4-6：记录彩色旋转图像每个空间位置(i，j)出现的聚类中心编 号和对应每个编号的颜色；

计算所述步骤S5中两个彩色旋转图像间的相似性的步骤如下：S5-1，将彩色旋转图像之间的相似性分解为各个颜色图层相似性的和：其中I1，I2为两个彩色旋转图像的直方图，c为颜色维度的索引值，I1(c)，I2(c)为I1，I2的第c个颜色图层，表示为两个二维的直方图；

0 0

S5-2，将最高分辨率下的两个图层I1(c)，I2(c)记为I1(c)，I2(c)，进行直方图相交，求出在该分辨率下匹配的数值：S5-3，对每个象素i，j，将匹配的数值从I10(c)，I20(c)的对应单元中减去：I10(c，i，j)←I10(c，i，j)-a0(c，i，j)I20(c，i，j)←I20(c，i，j)-a0(c，i，j)S5-4，采用图像扩散方法，降低两个图层的分辨率：将I10(c)降低一个分辨率的图层记为I11(c)，对图层I10(c)的每个象素(i，j)，它将均匀分配到图层I11(c)中的象素 其中a，b∈0，1，并且[x]为不超过x的最大整数；

S5-5，重复S5-2到S5-4的过程，依次降低图层的分辨率直到形成单个像素为止；

S5-6，在此基础上，定义两个图层之间的相似度为在每层匹配的值，乘以每个图层分辨率下像素边长倒数的加权和：其中，L是从最高分辨率到最低分辨率跨越的层数,计算所述步骤S5中的两个三维形状之间的相似性的步骤如下：S5-7：定义两个彩色旋转图像特征fi，gj之间的基础度量为：d(fi，gj)＝A-SCSI(fi，gj)

其中A为任意大于1的常数；

S5-8，根据上述基础度量，满足下列约束

的两个三维形状之间的最小输运距离为：

其中，eij表示从fi传输到gj特征的量，d(fi，gj)为描述把一个单位的特征从fi传输到gj的代价的基础度量，fi和gj分别是两个彩色旋转图像特征，ui和vj是其对应的权重，F，G分别代表F：{(f1，u1)，(f2，u2)，...(fm，um)}和G：{(g1，v1)，(g2，v2)，...(gn，vn)}。

2.如权利要求1所述的三维部分形状匹配和检索方法，其特征在于，在步骤S1中，所计算的局部形状特征为10000-100000个，对每个三维形状采样的基点个数为100-500。

3.如权利要求1所述的三维部分形状匹配和检索方法，其特征在于，在步骤S2中，所述局部形状特征词典包括编号和对应的局部形状特征的聚类中心，其中每个编号对应一种用于标记其对应的特定形状特征的颜色。

4.如权利要求3所述的三维部分形状匹配和检索方法，其特征在于，利用K-means方法对所述局部形状特征进行聚类。

5.如权利要求1-4中任一项所述的三维部分形状匹配和检索方法，其特征在于，所述聚类中心的个数为500-2000个。

说明书

一种基于彩色旋转图像的三维部分形状匹配和检索方法

技术领域

[0001] 本发明涉及计算机视觉和信息检索领域，具体涉及一种基于彩色旋转图像的三维部分形状匹配和检索方法。

背景技术

[0002] 随着三维场景重建技术和CAD造型技术的快速发展，三维模型在不少领域都得到了大量应用，如计算机动画，计算机辅助制造，计算机仿真药物设计等。在此基础上，三维模型的数量快速增长，并在网上出现了一些可供下载的三维模型数据库。在很多情况下，从三维模型数据库中检索到相关的三维模型，往往可以直接满足用户需要或大大降低设计全新的三维模型的工作量。

[0003] 现有的三维模型检索技术主要基于整体的三维形状特征。例如用一个向量或者矩阵来表示一个三维模型的整体几何特征。在此基础上，可以通过对比两个向量或矩阵，来快速计算出两个三维形状之间的相似性/距离。这样，可以对三维模型数据库中的各个形状，按照它们和用于查询的三维形状之间的相似性/距离进行排序，并将数据库中少量和查询形状最相似的三维模型返回给用户，作为参考。

[0004] 现有方法尽管对查找整体形状接近的三维模型较为有效，然而，大量的三维数据是在充满大量混杂和遮挡的环境中采集的。在这类三维场景中，对特定的三维形状进行匹配和识别仍然是一个具有挑战性的问题。此外，查找和整体形状完全相似的三维模型，在实际应用中往往很难提供有价值的新信息。一个实用的三维形状检索系统，应该能够找到和查询对象具有部分相似性(即部分重合)的三维形状。最后，现有的三维模型检索方法一般不适用与柔性三维形状，如人体和动物的形状可以灵活改变，现有的刚性形状描述子一般不适合描述这类三维形状的相似性。

[0005] 另一方法，三维形状匹配的目的是找到两个相似三维形状之间的对应关系。为此，一个关键的问题是如何评价对应点匹配的可靠性。现有的工作包括大量基于几何特征的局部三维形状描述子和它们的相似性度量。然而，和整体形状特征类似，这类形状描述子同样对混杂信息，遮挡和部分形状缺失较为敏感。因此往往在实际应用中不能获得满意的效果。 [0006] 发明内容

[0007] 本发明的目的是提供一种基于彩色旋转图像的三维部分形状匹配和检索的方法，设计一种新的形状描述子“彩色旋转图像”和针对它的相似性度量，从而解决传统三维模型检索方法不适用于基于部分形状相似性查找，和对三维形状数据中的噪声和遮挡较为敏感的问题。

[0008] 为了达到上述发明目的，本发明提供了一种基于彩色旋转图像的三维部分形状匹配和检索方法，所述方法包括步骤：

[0009] S1，对三维数据库中的每个三维形状表面进行采样，得到一系列基点，并在每个基点上计算一种局部形状特征；

[0010] S2，对所述局部形状特征进行聚类得到聚类中心，保存所述聚类中心构成局部形状特征词典；

[0011] S3，在所述局部形状特征词典中查找和每个局部形状特征最接近的聚类中心，并将该特征用聚类中心的编号替代；

[0012] S4，按照旋转图像的构造方法，重新对S1中的每个带有聚类中心编号的基点计算旋转图像形状特征，生成彩色旋转图像特征；

[0013] S5，依次进行直方图求交、图像扩散，计算两个彩色旋转图像间的相似性及两个三维形状之间的相似性。

[0014] 其中，在步骤S1中，所采集的局部形状特征为10000-100000个，对每个三维形状采样的基点个数为100-500。

[0015] 其中，在步骤S2中，所述局部形状特征词典包括一系列编号和对应的局部形状特征的聚类中心，其中每个编号对应一种用于标记其对应的特定形状特征的颜色。 [0016] 其中，利用K-means方法对所述局部形状特征进行聚类。

[0017] 其中，所述聚类中心的个数为500-2000个。

[0018] 其中，所述步骤S3中还包括步骤：记录三维形状各个基点对应的特征聚类中心的编号，即该基点的颜色编号。

[0019] 其中，所述旋转图像的形状特征的计算方法包括如下步骤：

[0020] S4-1，对于三维形状上的每个基点，将一小平面沿该基点处三维形状的法线为轴旋转，在旋转过程中将三维形状的每个标记颜色的基点投影到该小平面上，形成彩色的二维点云分布；

[0021] S4-2，在对二维平面进行离散化的同时，生成三维直方图(c，i，j)，其中c为编号，(i，j)为二维空间的离散坐标；

[0022] S4-3，根据小平面上每个彩色点的位置在三维直方图中对应的单元加一； [0023] S4-4，对彩色旋转图像进行规则化，即将三维直方图的全部单元的数字的和归一。 [0024] 其中，在所述步骤S4-4之后，还包括步骤

[0025] S4-5，记录所述彩色旋转图像中所有出现的聚类中心编号；和

[0026] S4-6，记录彩色旋转图像每个空间位置(i，j)出现的编号和对应每个编号的数值。

[0027] 其中，计算所述步骤S5中的两个彩色旋转图像间的相似性的步骤如下： [0028] S5-1，将彩色旋转图像之间的相似性分解为各个颜色图层相似性的和：其中I1，I2为两个彩色旋转图像的直方图，c为颜色维度的索
引值，I1(c)，I2(c)为I1，I2的第c个颜色图层，表示为两个二维的直方图；
0 0

[0029] S5-2，将最高分辨率下的两个图层I1(c)，I2(c)记为I1(c)，I2(c)，进行直方图相交，求出在该分辨率下匹配的数值：

[0030]

[0031]0 0

[0032] S5-3，对每个象素i，j，将匹配的数值从I1(c)，I2(c)的对应单元中减去： [0033]

[0034]

[0035] S5-4，采用图像扩散方法，降低两个图层的分辨率：

[0036] 将I10(c)降低一个分辨率的图层记为I11(c)，对图像I10(c)的每个象素(i，j)，它1
将均匀分配到图像I1(c)中的象素 其中a，b∈0，1，并且[x]为不超过x
的最大整数；

[0037] S5-5，重复S5-2到S5-4的过程，依次降低图层的分辨率直到形成单个像素为止； [0038] S5-6，在此基础上，定义两个图层之间的相似度为在每层匹配的值，乘以每个图层分辨率下像素边长倒数的加权和：

[0039]

[0040] 这里，L是从最高分辨率到最低分辨率跨越的层数。

[0041] 其中，计算所述步骤S5中的两个三维形状之间的相似性的步骤如下： [0042] S5-7：定义两个彩色旋转图像fi，gj之间的基础度量为：

[0043] d(fi，gj)＝A-SCS1(fi，gj)

[0044] 其中A为任意大于1的常数；

[0045] S5-8，根据上述基础度量，利用推土机距离的方法，定义两个三维形状之间的距离为在满足下列约束下：

[0046]

[0047] 的最小输运距离：

[0048]

[0049] 其中，eij表示从fi传输到gj特征的量，d(fi，gj)为描述把一个单位的特征从fi传输到gj的代价的基础度量，fi和gj分别是两个彩色旋转图像特征，ui和vj是其对应的权重。

[0050] 本发明所提供的基于彩色旋转图像的三维部分形状匹配和检索方法，解决了传统三维模型检索方法不适用于基于部分形状相似性查找，和对三维形状数据中的噪声和遮挡较为敏感的问题。本发明中生成的彩色旋转图像不仅可以反映基点附近局部形状上的三维点的几何分布，而且反映了这些点自身的形状语义信息。在此基础上提出的相似性度量的计算步骤较好地模拟了层次形状匹配的实际过程，在实际形状检索和匹配中有较好的结果。

[0051] 附图说明

[0052] 图1为本发明的基于彩色旋转图像的三维部分形状匹配和检索方法流程图； [0053] 图2为本发明的彩色旋转图像局部形状特征的计算过程示意图。

[0054] 具体实施方式

[0055] 以下实施例用于说明本发明，但不用来限制本发明的范围。

[0056] 图1为本发明的基于彩色旋转图像的三维部分形状匹配和检索方法流程图。如图1所示，本发明提供了一种基于彩色旋转图像的三维 部分形状匹配和检索方法，所述方法包括步骤：S1，对三维数据库中的每个三维形状表面进行采样，得到一系列基点，并在每个基点上计算一种局部形状特征；S2，对所述局部形状特征进行聚类得到聚类中心，保存所述聚类中心构成局部形状特征词典；S3，在所述局部形状特征词典中查找和每个局部形状特征最接近的聚类中心，并将该特征用聚类中心的编号替代；S4，按照旋转图像的构造方法，重新对S1中的每个带有聚类中心编号的基点计算旋转图像形状特征，生成彩色旋转图像特征；S5，依次进行直方图求交、图像扩散，计算两个彩色旋转图像间的相似性及两个三维形状之间的相似性。

[0057] 其中，在步骤S1中，所采集的局部形状特征为10000-100000个，对每个三维形状采样的基点个数为100-500。其中，在步骤S2中，所述局部形状特征词典包括一系列编号和对应的局部形状特征的聚类中心，其中每个编号对应一种用于标记其对应的特定形状特征的颜色。其中，利用K-means方法对所述局部形状特征进行聚类。其中，所述聚类中心的个数为500-2000个。其中，所述步骤S3中还包括步骤：记录三维形状各个基点对应的特征聚类中心的编号，即该基点的颜色编号。

[0058] 其中，所述旋转图像的形状特征的计算方法包括如下步骤：S4-1，对于三维形状上的每个基点，将一小平面沿该基点处三维形状的法线为轴旋转，在旋转过程中将三维形状的每个标记颜色的基点投影到该小平面上，形成彩色的二维点云分布；S4-2，在对二维平面进行离散化的同时，生成三维直方图(c，i，j)，其中c为编号，(i，j)为二维空间的离散坐标；S4-3，根据小平面上每个彩色点的位置在三维直方图中对应的单元加一；S4-4，对彩色旋转图像进行规则化，即将三维直方图的全部单元的数字的和归一；S4-5，记录所述彩色旋转图像中所有出现的聚类中心编号；和S4-6，记录彩色旋转图像每个空间位置(i，j)出现的编号和对应每个编号的数值。

[0059] 其中，计算所述步骤S5中的两个彩色旋转图像间的相似性的步骤如下：S5-1，将彩色旋转图像之间的相似性分解为各个颜色图层相似性的和：
其中I1，I2为两个彩色旋转图像的直方图，c为颜色维度的索
引值，I1(c)，I2(c)为I1，I2的第c个颜色图层，表示为两个二维的直方图；S5-2，将最高分辨率下的两个图层I1(c)，I2(c)记为I10(c)，I20(c)，进行直方图相交，求出在该分辨率下匹配的数值：

[0060]

[0061]

[0062] S5-3，对每个象素i，j，将匹配的数值从I10(c)，I20(c)的对应单元中减去： [0063]

[0064]0

[0065] S5-4，采用图像扩散方法，降低两个图层的分辨率：将I1(c)降低一个分辨率的1 0 1
图层记为I1(c)，对图像I1(c)的每个象素(i，j)，它将均匀分配到图像I1(c)中的象素 其中a，b∈0，1，并且[x]为不超过x的最大整数；S5-5，重复S5-2到S5-4
的过程，依次降低图层的分辨率直到形成单个像素为止；S5-6，在此基础上，定义两个图层之间的相似度为在每层匹配的值，乘以每个图层分辨率下像素边长倒数的加权和： [0066]

[0067] 这里，L是从最高分辨率到最低分辨率跨越的层数。

[0068] 其中，计算所述步骤S5中的两个三维形状之间的相似性的步骤 如下：S5-7：定义两个彩色旋转图像fi，gj之间的基础度量为：

[0069] d(fi，gj)＝A-SCSI(fi，gj)

[0070] 其中A为任意大于1的常数；

[0071] S5-8，根据上述基础度量，利用推土机距离的方法，定义两个三维形状之间的距离为在满足下列约束下：

[0072]

[0073] 的最小输运距离：

[0074]

[0075] 其中，eij表示从fi传输到gj特征的量，d(fi，gj)为描述把一个单位的特征从fi传输到gj的代价的基础度量，fi和gj分别是两个彩色旋转图像特征，ui和vj是其对应的权重。

[0076] 下面详细介绍本发明中的技术方案。

[0077] 1.彩色旋转图像的计算过程

[0078] 彩色旋转图像通过两个步骤生成。第一阶段的目标是，给三维形状上的每个点赋予代表它周围形状属性的索引值。首先从三维模型数据库中采集大量的三维局部形状特征。这是通过对数据库中的每个模型，在它的表面上采样大量的基点，并在每个基点上运用局部形状描述子抽取特征得到。对于每个模型，使用Monte-Carlo方法在三维形状上均匀采样。然后，我们运用K-Means(或其它)聚类方法，把这些海量的形状特征进行聚类。对于聚类后得到的类中心，可以视为独立的、反复出现的特征模式。由于所有类中心构成了局部特征的“字典”，因此每个聚类中心也常常被称为是“字典”中的一个字，在字典中有它的编号。这个建字典的过程离线完成，之后将生成的“字典”存储起来，以便于将来使用。 [0079] 对于在线的特征提取过程，对作为查询对象的三维形状使用前面提到的Monte-Carlo算法，在三维形状上采样，得到一系列基点。在每个基点位置，运用局部形状描述子提取一个特征，并在字典中查找和该特征距离最近的“字”。将该“字”在“字典”中的编号赋予这个基点，来指示它周围的局部形状。

[0080] 在本文中，“字”在字典的索引被称为“颜色”。因此前面的过程，可以看成是对三维形状上的每个点，根据该点周围的局部形状，给它赋予一个颜色。因此，将所提出的形状描述子称为“彩色的旋转图像”。然而，对于三维形状上的所有稠密采样点都赋予一个颜色，具有较大的计算复杂性。处理这个问题的捷径是这样的：只对形状上的少量采样点(例如500个)进行染色。然后再对形状上每个稠密的采样点，赋予它在这500个点中最近点的颜色。

[0081] 上述为计算彩色旋转图像的第一阶段的过程。在这个阶段，有很多自由度可供灵活选择。首先，局部形状描述子的种类，可以任意选择。例如，可以使用原始的旋转图像方法，对形状上的点进行染色。其次，局部形状描述子的支撑范围的大小可以根据具体问题灵活指定。总得来说，对于噪声较高的三维数据，应对描述子设定较大的支撑范围。相反地，对于存在较多遮挡的三维形状，支撑范围不应设得过大，以避免形状信息的混淆。 [0082] 现在介绍构造彩色旋转图像的第二个步骤。在介绍具体细节之前，首先介绍一下原始的旋转图像形状描述子。如图2中所示，旋转图像表示为一个二维的向量，和传统的图像相似。顾名思义，旋转图像是通过旋转以基点法向为轴的小平面，扫描三维形状上的点生成的。我们在这里介绍更多的技术细节。如图所示，假定B是形状上的某个点，这里做为旋转图像的基点。P是形状上的另一个点，在该旋转图像的支撑范围内。Γ是位于点B处的形状的切平面。由此，位移向量 可以被分解成两部分，位于切平面内的部分 和垂直于 切平面的部分 记 的长度为w， 的长度为h。这样，对旋转图像上对应(w，h)的象素(i，j)投下一票。旋转图像的支撑范围(W，H)保证了只有形状上满足下面约束|h|≤H，|w|≤W的点，才能投影到旋转平面上，否则被忽略掉。换句话说，支撑范围定义了旋转图像对基点周围的局部形状的描述范围。

[0083] 在提出旋转图像的原始文献中，仅仅将网格的顶点，作为形状的采样点，来生成旋转图像。这些点在形状上是不规则分布的，而且可能很稀疏，因此效果往往会受到较大影响。在本方法中，运用蒙特卡洛方法，采集了均匀，稠密的形状采样点，避免了这一问题。 [0084] 对于彩色旋转图像，它和原始旋转图像的关键不同之处在于：形状的采样点已被赋予了颜色(编号)，因此，需要将彩色的点投影到旋转平面上。此外，和二维的旋转图像方法不同，彩色旋转图像由三维直方图进行表示。其每个单元由三个整数值(c，i，j)索引，这里c代表一个特定的颜色。最后，还需对彩色旋转图像进行规则化，即将它的全部单元的数字的和归一。

[0085] 2、彩色旋转图像的空间存储

[0086] 和自然图像只有三个颜色通道不同，彩色旋转图像可能有几百个到几千个颜色通道。在表面上看，人们可能认为彩色旋转图像需要比旋转图像大得多的存储空间，然而事实上并不需要。由于彩色旋转图像是一种稀疏的表示，可以利用这一点来大大减小它的存储空间。实际上，尽管“特征字典”可能有成百上千个“字”，在一个彩色旋转图像中出现的“字”(即颜色)可能并不多。特别地，对于固定的(i，j)，可能只有极少的颜色出现在这个象素位置上。因此，首先在彩色旋转图像文件的开始处，记录在它之中所有出现的颜色编号。然后，对于每个(i，j)位置，只需记录在这个位置出现的少数几个颜色的索引值，和对应每个颜色的数值。在我们的试验中，尽管字典中有1500个字，彩色旋转图像的存储空间仅仅是普通旋转图像的大约3倍。

[0087] 索引结构使得彩色旋转图像的相似性计算更为快捷。在比较两个彩色旋转图像之前，首先对它们之中出现的颜色索引求交，然后只需对这些共同的颜色图层进行比较即可。 [0088] 3、彩色旋转图像的相似性度量

[0089] 下面介绍如何计算两个彩色旋转图像之间的相似性。首先，将三维的彩色旋转图像看成一个二维的图像，在每个象素位置(i，j)都放置了很多不同颜色的点。这样，比较两个彩色旋转图像的任务就转换成了匹配在两个图像平面上分布的两组彩色的点。既然每种颜色代表一种特定类型的局部形状，只有相同颜色的点才能匹配。因此，可以将彩色旋转图像之间的相似度分解为各个颜色层之间相似度的和：

[0090]

[0091] 其中I1，I2为两个三维的彩色旋转图像直方图，c为颜色维度的索引值，I1(c)，I2(c)为I1，I2的第c个颜色图层，表示为两个二维的直方图。

[0092] 现在问题就转换成了计算两个二维直方图之间的相似度。例如，可以用归一化的相关度来计算它们的相似性。但是，这对彩色旋转图像并不十分合适。因为在彩色旋转图像中，每个三维形状上的点都已标记上颜色，而相同颜色的点恰好在同一个像素位置(i，j)匹配的概率往往很小。因此，应允许位于平面上不同像素位置的相同颜色的点匹配。 [0093] 因此，为了描述彩色旋转图像两个图像层之间的相似度，应采用单元交叉匹配的相似性度量。我们给出一个非常高效的，多分辨率的直方图求交方法，来计算两个图层之间0 0
的相似性。将初始的两个图层I1(c)，I2(c)记为I1(c)，I2(c)，因为它们在最高的分辨率。
将这两个二维图层相交，来计算在该层匹配的数值：

[0094]

[0095] 对每个象素(i，j)，将匹配的数值从I10(c)，I20(c)的对应单元中减去： [0096]

[0097]0 0

[0098] 接下来，I1(c)，I2(c)的尺寸均缩小到原来的二分之一，来生成较低分辨率的两幅图像。为了避免直方图里不同的单元对相似性计算贡献不同的问题(即空间偏差)，采1 1 0
用了图像扩散的方法。设在下一个低分辨率的两个图层为I1(c)，I2(c)，对图像I1(c)的每个象素(i，j)，将它扩散到图像I11(c)中的象素 其中a，b∈0，1，并且[x]为不超过x的最大整数。对I20(c)进行类似的操作。

[0099] 不难验证在这种扩散的情况下，任何侧面相邻的两个象素，它们50％的值在下一个分辨率下都会合并。对于对角相邻的象素，它们25％或50％的值会在下一层合并。因此，直接合并直方图单元带来的空间偏差，就大大降低了。

[0100] 最后，定义两个图层I1(c)，I2(c)的相似度为在每层匹配的值，乘以像素边长倒数的加权和：

[0101]

[0102] 这里，L是最低分辨率对应的层数，此时原始的图层已经收缩成一个象素。通过上面的构造，很容易证明相似性度量S具有一个线性的O(n)的计算复杂度，这里n代表图像中象素的个数。这样，所述的相似性度量，在计算时间复杂度的量级上和一般经典的直方图相似性度量是一致的。

[0103] 4、计算三维形状之间的相似性

[0104] 上面已经介绍了彩色旋转图像的构造方法，以及该特征之间相似性度量的计算方法。然而，对于三维模型检索，需要计算两个三维形状之间的相似度。以下将利用推土机距离的方法，将两个彩色旋转图像之间的相似性推广到两个三维形状之上。

[0105] 简单地说，给定两个局部特征的集合F：{(f1，u1)，(f2，u2)，...(fm，um)}和G：{(g1，v1)，(g2，v2)，...(gn，vn)}，推土机距离计算出将一个集合的特征搬运到另一个集合的特征上的最小代价。这里fi和gj分别是两个集合的局部特征，ui和vj是对应的权重。在数学上推土机距离在满足下列的约束下：

[0106]

[0107] 求解了下列优化问题：

[0108]

[0109] 其中，eij表示从fi传输到gj的特征的量，d(fi，gj)为描述把一个单位的特征从fi传输到gj代价的基础度量。因此，上述几个约束反映了输运过程中特征“质量守恒”的自然约束关系。

[0110] 由于彩色旋转图像的基点是在三维形状上均匀采样得到的，因此，所有特征的权重是相同的。定义基础度量d为一个常数减去两个彩色旋转图像之间的相似度： [0111] d(fi，gj)＝A-SCSI(fi，gj)

[0112] 如前面所述，由于彩色旋转图像描述子是归一化的，很容易证明SCSI(fi，gj)≤1。因此只要把常数设为A＞1就足以保证基础度量恒正。更进一步地，很容易证明常数A的值可以在上述条件下自由选定，因为最终计算出来的，两个三维模型之间的距离DEMD(F，G)相差一个常量。

[0113] 以上实施方式仅用于说明本发明，而并非对本发明的限制，有关技术领域的普通技术人员，在不脱离本发明的精神和范围的情况下，还可以做出各种变化，因此所有等同的技术方案也属于本发明的范畴，本发明的专利保护范围应由其权利要求限定。