突出几何特征在局部匹配和相似性测定中的应用研究论文.doc

突出几何特征在局部匹配和相似性测定中的应用研究ran gal and daniel cohen-or特拉维夫大学 这篇文章介绍了一个关于用三角网格模型表示的表面的局部匹配方法，我们的方法针对的是那些数字上和拓扑上不一致，但是大致相同的表面区域。我们介绍新的局部表面描述可以有效地表示表面的局部区域的几何形状，描述方法被独立地定义为基本三角，并且形成一个兼容的允许表面通过不同三角匹配的表示。为了应对大网格的局部匹配的结合复杂度，我们介绍关于突出几何特征的概念并且提出一个方法去构建他们。一个突出几何特征是不平滑局部形状的复合高级特征。我们展示了一些相关的突出几何特征能够很好地描述了表面给各种各样的相似性应用。匹配突出几何特征是基于建立旋转不变量特征的索引并且一个通过几何哈希散列加速的投票系统。我们用一些应用来证明我们方法的有效率性，如同计算自相似性，校准，子部分的相似性。分类和主题描述：i.3.5计算机图形：计算几何和对象建模通用术语：算法附加关键词和短语：部分匹配，形状检索，突出特点，相似性，几何变换1引言 在诸多需要用到大量几何应用的领域中，比如计算机视觉、机器人科学、分子生物学等，匹配是一项基础性的工作。近来，由于3d建模技术广阔的应用前景，关于3d图形检索技术的研究已经愈演愈烈。现在，研究方向主要集中在全局匹配上，即在所有的模型间计算并测定相似性。局部匹配是一项匹配整体的一个元件或一定范围的工作。 被匹配的部分没有预定义，因此可以是任何一个更大形状的一部分，匹配的方向和规模都没有限制。为了测量相似性，局部匹配需要提前搜索并预定义匹配元件，因此在操作中比整体匹配更困难。在这篇文章中，我们将主要关注以三角网络法为代表的表面局部匹配技术。 一般来说，定义一个关于人对于相似性觉知的测量标准还是很困难的。即使有现成的相似度测量方法，在众多具有不同表象的形状里匹配到目标也是一件有挑战的事情。更何况在通往使局部匹配具备足够可操作性的道路上有很多巨大的错综复杂的障碍要跨越。例如，图1中的4朵荷花是佛像的一部分。匹配这些佛像需要搜索超过1m个关于佛像的三角模型。我们注意到这些莲花都是残缺不均匀的，而且处于不同的方位，它们的程度也是事先不知道的。为了解决这个问题，我们通过图形的表面特征定义一个稀疏本地表面描述器群组.这些描述器代表了局部范围内的图形表面特征，这些本地的与潜在的三角测量模型独立定义，如此便建立了一个可通过潜在的不同的三角测量模型测量不同范围间相似性的兼容的表示。由于描述器的数量明显比之前少很多，因而大大减少了表面特征表述的组合复杂性。通过合理的设置描述器，能使这些描述器的描述能力十分的高效。然而，为了高效的实现对面积大，复杂程度高的表面进行局部匹配，这些描述器的数量依然显得庞大因而我们定义突出的几何特征这个概念以用来建立高水平的复合描述器。 突出的几何特征简而言之就是突出特征，由一簇描述表面重要范围的描述器组成。这些突出特征很好的定义了表面的典型特性，为图形的元件之间进行非整体的相似性测量打下了基础。突出特征匹配能够适应很多棘手的应用，比如在简单的一个或几个表面找到相似的部分。仍旧以荷花的图形为例，在图1中，四朵荷花通过自相似性匹配被找到，也就是重要元件和其他元件在相同表面进行匹配。在本篇论文中，我们主要做如下研究：局部匹配：通过三角网络法解决局部匹配的问题，这种方法扩展了3d模型整体匹配的结果。本地表面描述器：介绍一种新型的本地表面描述器，该描述器能够更有效的编码表面的模块儿。它们与底层的三角独立，形成了一个稀疏兼容的允许不同表面匹配的表现。突出几何特征：我们介绍突出几何特征的概念并给出一种构建它们的方法。突出几何特征是一种高度复合的特征，这些特征定义了本地局部图形。我们把每个突出特征用若干转动和尺度不变的指数表征，以加快匹配和相似度测定。应用：介绍一些以局部匹配为主的几何应用。在一些多变庞大且复杂的网络中论证我们的方法的高效性。2背景图形相似和匹配的问题已经在很多领域被广泛研究，诸如计算机视觉，机器人科学，分子生物学等。其中大部分都只是关注2d图形的匹配问题。几何学的方法被引入以后，3d模型匹配似乎更简单，而且还没有类似光照和反射的外部阻塞和破坏效应。 在计算机图像领域，发展3d图形匹配主要是为了图形检索。在网页搜索引擎技术的支撑下，基于几何属性而不是文本的3d模型图形匹配的新方法得到了快速发展。然而有阻塞的局部匹配的方法虽然在2d图形匹配领域占据了至关重要的地位，但还没有在3d图形匹配领域得到足够的关注。大部分技术都注重基于所有几何图形检索相似模型。换句话说也就是相似性是基于3d模型整体的特性，比如相同的时间变量，傅里叶描述器，柱状图和图形分布情况，谐波为主表征。这些方法都依赖于全局相似变换（旋转+均匀缩放）首次对准和标准化模型的能力，这种全局相似变换把模型标准化并在原始模型和标准化之后的模型之间建立对应关系。这种全局对准的方法不能区分数据间的不同，很容易引起局部特征的没有对准。因而是一种不合适的全局相似测量。这启示了kazhdan通过控制异向性的作用来抵消上述方法的未对准的影响。这方面来讲，我们介绍的局部匹配技术可以用来对准两个几乎没有全局相似性的模型。过局部匹配的方法，我们可以明确地匹配符合的突出特征，从局部匹配中建立全局对准.基于图形的方法依赖于3d模型的拓扑结构是图形的一个重要的形态特征。拓扑结构通常表示为有关系的数据结构，如图：基于图形的表示法促进了具有相似拓扑结构的元件间的局部匹配。在funckhouse中，作者为3d模型匹配提供了一种基于两个图形之间描述器群组的距离平方和的方案。这种方法允许不同权重的局部使用原始的模型描述器群组，因而可使局部整体的匹配方案成立。这些方案都依赖于所有的模型按照使匹配局部在3d空间中相互更加靠近的方式排列的假设。局部代替整体的匹配方式可以归类到基于id转换的局部匹配。一般的局部匹配都致力于在任何刚性运动转换下实现局部匹配，有时候甚至在大规模转换下也能有很好的效果。 同样也可以考虑一种更加广泛的转换方式比如仿射或透视等。 在这篇文章中我们发展了一种支持刚性转换和统一缩放的局部图形匹配方法，被称作相似变换。我们的方法不在全局上对齐图形，从而否定了匹配的实现可能，例如把有一个巨大底座的雕像的手转换到没有底座的雕像的手。局部匹配是从扫描仪中得到深度图像的3d实体识别和登记的基础性模块儿。在这种应用场景中，检索依赖于视图和分辨率。通常这些技术基于匹配局部描述器群组，比如旋转图形和图形背景。不同于这些局部描述器群组，我们研究的表面描述器群组能很好的被构建，用来高效的尽可能大的表示网格区域，具有不受规模限制和适应性强的特点。我们将在第9章节进一步阐述这些方法。图像空间中的“有趣”点和突出特征的抽取已经得到广泛研究。有趣表面特征或者叫突出特征的定义使我们工作的中心。正如我们下面将要阐述的，我们对有趣部分的定义着重基于表面曲率。shum认识到了用表面曲率方法去匹配3d图形的重要性。2 显著的几何特性 人类感知以及识别和解释形状的能力是一个广泛研究的课题。确实，它不只是一项任务，而是许多项（任务的集合）：颜色、阴影、形状、运动、纹理和环境因素在过程中一般都将被用到，与文化背景和个人关联不大。在计算机图形和建模中的核心问题就是理解“形状”的概念。为了实现目标，我们使用dryden和mardia1998作的关于形状的正式定义：把位置、规模和旋转效应（欧几里得变换）从物体中滤出后，剩下的就是物体的全部几何信息。 有一个共识就是根据部分来代表整个形状可能有助于用人类的视角来认识过程hebb 1949。在二维空间，它可以用于处理闭塞问题，在三维空间，它可以用于处理非刚性体。一个关键的问题是：哪些部分（需要处理）？在我们的研究中，我们定义，由通用计算规则的方式，一个物品的突出部分，即压缩了足够多特征的部分，将被用于第一级搜索中hoffman and singh 1997。关于物体的“部分显著性”，我们目标是用一小部分特征来捕捉物体的形状。其显著性，在某种程度上，是用有效性作为指标来决定。 我们的方法是建立在hoffman和singh1997提出的视觉部分显著性理论之上的。根据他们的理论，一个部件的显著性是它尺寸的函数，相对于整个物体，与其突出的程度和边界的强度有关。在这项工作中，我们的目标是开发能应用于网格的方法的定量定义。重点就是对“边界强度”的计算。我们的方法是使用曲率值的函数。我们建议，一个物体的显著性部分取决于（至少）两个因素：它相对于整个物体的大小以及曲率变化和强度的数量。在第五部分我们将描述确定显著性几何特征的计算方法。3.概述 给定一个三维表格，我们分析它的几何特性并确定用部分形状描述的网格稀疏表示。然后我们从网格中提取有趣并显著的几何特征。这些特征被索引并存储在可被有效地用于查询部分匹配模式的数据库。匹配子部分需要转换成一个共同的坐标系。一个很自然的实现方式是存储所有模型在由每个顶点以及其邻域确定的所有可能坐标系中。然后，对于给定的查询，我们将测试由查询的顶点所确定的所有可能的方位和定标。这种方法会导致测试中“组合爆炸”，这远远超出了我们的计算能力，尤其是（计算）那些含有上千个或更多顶点的模型。为了克服这些组合障碍，我们提出了三种方法：用一组形状的稀疏描述符表示给定的网孔。每个描述符表示具有良好的二次拟合的局部区域。确定一小套显著性的几何特征并索引它们。显著的特征表示一个给定的形状的令人关注的部分。预先计算几何哈希表，使得在旋转和缩放变换下能够快速地部分匹配。在四至六节，我们提出以下的方法分析模型的表面；定义局部的形状描述符；定义显著性特征并存储索引的矢量；使用索引和集合散列法查询部分匹配的模型数据库。然后在第七节我们将讨论我们方法的性能问题。在第八节在我们展示了一些基于我们的部分匹配算法的应用程序和结果。在第九节，我们将说明几何散列法和基于直方图方法之间的关系，然后在第十节我们得出结论，并讨论未来的工作。在我们继续之前，我们参考图3，它充分说明了部分匹配的精髓之处。该图显示了模型（a）和（b）三部分的匹配。值得注意的是，这两个模型只有一小部分实际匹配。这个例子强调了一个事实，即部分匹配多于给定模型的子部分的匹配，并且该匹配部分预先并不确定。3.局部的表面描述符 一个局部的表面描述符是一个点p，它在表面上或者是在p点附近的与其相关联的二次斑点的近似表面上。关键点是，只要每个描述符有效地代表它周围的局部表面区域，那么一小部分的描述符就可以表示形状。这种表示适用于几何形状。平滑区域由相对较少数量的描述符所表示，因为每一个二次曲面斑点可以在局部近似于一个大的区域。高频的不平滑的区域需要相对大量的描述符。注意图5（b）中在鹰嘴附近和在光滑区域的局部形状描述符的密度。作为一种分析局部表面的手段，我们将曲率值与每个描述符相关联。接下来，我们通过描述二次曲面拟合方案和算法来构造一组有效的描述符。图片3 部分匹配。老鹰模型（b）的三个部分通过高度变形叠加在一个结构上应用于图（a）中。这三个副本有不同的尺度和方向。通过应用部分匹配（c）-（e），老鹰的这三个部分与整个老鹰模型相匹配。请注意，每一对匹配之间只有部分重叠。该匹配是通过在一个共同的坐标系中对三组局部形状描述符的变换实现的。用小黄球来说明局部的形状描述符。4.1 二次拟合和曲率估计 使用douros和buxton2002提出的方法，表面通过可分析的二次曲面斑点很好地由每个顶点近似表示。对于每个二次曲面斑点，选择可以代表的点然后计算分析斑点的在该点的微分属性。对于可表示为f（x，y，z）= 0的隐函数的表面，我们使用一个有九个系数的二次方程。这种表面的拟合容易用公式表示为用于解决特征值问题的最小二乘法。这使得该方法可以工作在3d模型的任何类型的点云上，而不管底层表面的取向。需要注意的是这样的表示并不需要单独指出任何坐标轴。对于网格的每个顶点v，我们挑选适合的隐式表面，并且其投影在隐式表面上被表示为v。在v上的曲率张量和曲率倒数由在v上计算分析（的数据）来估计 ohtake et al. 2004。为了增加鲁棒性，我们测量了各顶点附近的尺寸，并选择具有平均曲率的二次方程。尽管有更快的技术来估计离散曲率 alliez et al. 2003; rusinkiewicz 2004，但由于这些曲率计算是离线的，我们实现了一般更强大的一个二次曲面拟合技术。图4展示了局部二次曲面匹配和所估计的曲率图。4.2 简洁的表示 为了产生一组相当小的，但有效的局部表面描述符，我们定义一个局部表面斑点，并将其与表示该斑点的描述符相关联。我们采用区域发展的技术来反复定义局部斑点。我们根据绝对高斯曲率排列对网格顶点进行降序排序，并为每个顶点，在它的附近近似为最大可能的“二次曲面斑点”。所有包括在所述局部斑块中的顶点，之后将从排序列表中删除，并且继续迭代过程以定义下一个斑点。我们的方法是贪婪的，即在每一个步骤中，我们限定所选顶点附近满足预定的错误阈值的最大可能的区域。所有本文中示出的例子，我们使用的模型边界框的对角线长度为10-4。我们测量拟合点到装配表面距离的平方代数之和的二次曲面拟合的质量。代数距离比欧几里德距离更容易评估，虽然它不太可靠，但它是测量质量的有效措施。 一旦斑点被确定，我们选取它的质量中心作为代表点，并与横跨斑点的最高曲率相关联。图5显示的章鱼模型的触手的结果。回想一下，局部表面描述符的主要目标之一是细分表示一个独立的给定模型。因此，我们随机（不一定一致地）在表面取样osada et al. 2001; elad et al. 2001, 并使用这些随机样本进行二次曲面拟合。以图6作为用于计算两个不同的细分曲率的一个例子。可以看出，尽管有不同的细分，曲率地图和局部表面描述符的分布是相似的。图片4 二次曲面拟合示例。红色的点是由主轴（蓝色）确定的网格上的样点。这个网格是由高斯曲率着色的。图片5 章鱼触手吸盘示例。（a）原始细分和加粗的二次曲面斑点。（b）黄色点表示局部表面描述符。需要注意的是它们的密度与表面形状相适应。图6：曲率地图上计算有不同的镶嵌相同的模型。蓝色是低曲率和红色的高。5.计算机的显著几何特性 严格意义上，一个突出的几何特征的图像具有一个非平凡形状的表面的区域。我们归类一组描述相符的几何特性得到有趣发现，它们具有相对于其它具有高曲率的几何特征，并具有高方差曲率值。显著几何特征是一个自由参数h的函数，它由球体边界的显着特征的半径限定。 对于每个描述符，我们从最大当前显着等级逐步添加描述符并围绕它产生一个描述符集群，当添加描述符不足时该过程停止。我们允许集群之间某种程度上重叠的所有的描述符执行此过程（在我们的实验中允许高达20的重叠）。描述符的显着性等级集合f包含d f，具有以下四个方面功能:df区（d）中，其中，area（d）是补丁具有d相关联的球体尺寸区域df curv（d）中，在那里curv（d）是与d相关联的曲率n（f）的数目的最小（s）或最大（多个）曲率集群中var（f）的集群中曲率变化。显著度s级可以定义为这四个方面的线性组合。然而，经验上我们发现以下表达式更有效： 第一项area（d）curv（d）3通过结合其相对大小和曲率表示该区域的显着性。curv（d）可以是高斯曲率或最大曲率分量，图7展示出了从泰国雕像的妇女的2曲率图，无显著差异。需要注意的是当零高斯曲率大面积cad模型时，一个最大的曲率是一个更好的选择。第二项n（f）var（f）表示对簇的兴趣程度，并添加到集群的显着性，如图8所示。我们对w1和w2使用0.5的权重。显著部分的定义相对于启发式并不是完全相关联，因为我们对特定部分不感兴趣，而是在产生了一些特征的模型以及显着特征（参见图9）。应当强调的是，采用的常量公式（1）无需手动调整，本文中使用的所有示例和实验使用相同的表达。换句话说，我们定义一个显著的几何特征作为该模型的一个区域，该区域相比该模型的其他部分更加显著而有趣。顶端分级簇定义了给定形状的显著几何特征。显著几何特征的一些结果示于图9，其中我们只提取最显着的特征，无论是那些等级在排名前10，或那些符合规定的阈值。图7：曲率分析了来自泰国的雕像三女。这些图像是利用高斯曲率（左）与最大曲率（右）。这些微小的差别表明，显着特征的定义是不敏感的分析。图8：左侧图像显示了由曲率着色的局部表面描述符。在右边的图像中，显著性等级是可视化的规模，从蓝色到红色显示。补丁是根据其中显著特征的显著级着色的。图9：显著几何特征（橙色）是通过分析表面自动定义的。单个部分为红色。6索引和几何散列 模型的显着特征在一个旋转和尺寸不变的数据库进行定义，离线提取以及存储。各显著特征都与一个矢量索引（签名）相关联并插入到一个几何哈希表。指数的矢量被用作几何签名并且允许快速访问到有具有相似形状的部分。为了更加有效，我们使用旋转和尺寸不变几何签名。然而只有签名不足以完全识别而且不会提供符合他们的实际转换。通过采用几何散列拉姆丹和欧胜1988最匹配的形状改造被确定。 在我们的实现中，我们使用了四个术语来定义的显著级，如表达由方程1中，作为相似性不变矢量索引。请注意，其他阐述指数，如归矩也同样可以用来适用。然而在执行索引时我们加强了对显著特征效率的要求。我们利用几何散列来加速模型数据库中的部分匹配的检索。简单地说，几何哈希是加速刚体变换和部分匹配的机制，是一个统一的尺度。该方法利用投票计划的方式选取一大组转换中的最佳变换。这些方法量化变换空间成六维表。鉴于两个对象，a和b，对于a中的三个元与b中的三个元转换，其转换过程是经过计算并将其中表决过程保存。得票最多条目进行对齐改造。为了避免穷举搜索所有的转换，几何散列编码离线提取所有候选转换在一个大的哈希表中，这样一来给定尺寸的查询模型| q |时，都需要查询哈希表，不管多少模型被编码在哈希表中。这些经过预先计算的哈希表省却了在每个模型三个元的搜索过程。 我们的实现方式是用显著几何特征和其表面描述为研究对象定义在散列表中的三个元和表决点。哈希表中包含数据库中的所有模型的所有显著几何特征。通常情况下，每一个显着的特点包括20-30个局部表面描述符。我们从一个小邻域（最多两个环）中取三个元定义候补变换，这样一来对准测试通常数所需的只是| q |，而不是。通过结合索引和几何散列，我们成功地找到与查询和存储之间相匹配的在散列表中的显着特征。该指数是用来快速拒绝在投票阶段的显著特点。匹配给定的两个显着特征的转型是关于各种匹配和相似性应用程序，如下所述。表1：统计数据的一些大，小型号7时间和存储的注意事项 提出的方法使执行大部分的工作所必需的脱机部分匹配模式允许快速查询时间。表i作为例子示出了预处理的一步我们所需的时间和存储空间。在其核心，部分匹配问题需要大量的计算进行搜索和比较。我们使用了更加耗时的表面分析来创建一个稀疏和自适应的描述符。为了我们的指数构造显著的几何特征，我们使用几何散列。索引几何散列的主要优点是，它允许一个尺度独立机制这在我们的应用程序中是非常重要的。对于简单的情况下，如果是不需要的规模，可以考虑实施其他用于索引的显著几何特征，如旋图像和形状内容的方法johnson and hebert 1999; huber et al. 2004.。 某些应用程序或方案可能需要一个更有效的预处理步骤。正如我们上面提到的，有快速方法去估计离散曲率和二次系数petitjean 2002; alliez et al. 2003; rusinkiewicz 2004。这些方法可以加快对规则模型的离散曲率估计，但是对于不规则镶嵌模型不太可靠。 此外，关于如何提高几何散列的效率，无论在时间和空间上的要求还有很多的工作要做。8应用和结果 部分匹配，在一般情况下，可以作为各种几何应用的基本工具。特别是，需要进行众多表面处理时。我们在这里论述我们已经尝试过的三个应用程序：自相似性，形状排列，和分部检索。8.1 自相似性 图10 图11 图10显示了自相似性搜索的结果。通过定义表面的一个显著特征来分析表面。方法是自动辨认有大量相似情况的表面的显著特征。在图中,章鱼的触手上的吸盘模型被识别（更仔细的特征参加图5）。注意到吸盘有相对较大的各种尺寸。图1是另一个自相似性应用的结果,通过这个我们了解到佛像模型上四个莲花的存在方式。表1展示了查询章鱼和佛像两个大模型和另两个小模型的统计数据。在上面的例子中,我们发现是对所有特征的复制进行旋转和统一的尺度转换。该算法首先将表面的相似特征分类排序，然后为每一个具有最大相似等级的相似特征进行部分匹配。图11显示了自相似分析在斯坦福三维扫描存储库中泰国雕塑的大型模型上的部分应用。这个模型中,如图12所示, 图12包含10米的多边形,这超出了我们的系统的能力。在我们的实验中,我们只处理它的部分:如图7所示的三个女人,如图12所示的三个大象。雕像有一个粗略的三相对称,但因为他们并不完美的副本，这三个部分的手工制作的雕像并不匹配。我们应用我们的自相似分析并且对于每一个匹配发展出一个更大的区域来形成兼容部分。只要符合一定的误差，该区域就能得到发展。这三相对称性分析结果如图11所示。8.2形状对齐 大多数全局匹配方法首先确定刚体变换和统一的规模,尽可能使两个模型一起,测量他们之间的距离。这通常是通过一个主成分分析(pca)应用于整个模型。当图形在一个细微的地方有差异，这样一个全局分析就容易出错。图2显示了一男一女之间的对齐模型。算例表明，虽然两个模型在几何形态和构成明显的差异，但通过他们的突出几何特征的部分匹配，是可能使它们在匹配的地方对齐的。在图13所示的另一个例子中， 图13 图14相同的模型表现出两种不同的姿势。后者的例子强调全局pca对齐未能正确地对齐,而部分匹配尽可能正确地对齐。我们的对准是基于大多数能够满足主要特征转换的方案提出的。 我们的对齐算法首先搜索每一个模型的主要特征对之间的匹配。然后对于每一个这样的匹配，相关的转换获得一个评级来反映成功对齐的数量。最成功的转换被选出并用来使两个给定的模型尽可能的相近。被选择的转换定义两个模型之间的对应关系。一旦这种对应关系被定义，相应的特征可以在最小二乘意义上更加接近。8.3 部分形状检索 应用局部形状检索允许部分和查询不同的较大的形状来检索。对于局部形状检索的框架概述如图14所示。 图15图15显示了一个检索人手的例子。这样的一个机制对有效建模来说是至关重要的，因为它发现旋转和统一的尺度转换下的相似形状可以作为更大的不同形状的一部分，例如图16中的植物所示。 图16检索的模型不一定要全局相似（例如，植物有高有矮），但需要足够的局部相似。如图16所示，它并不是最好的匹配，而是前5个和前72个匹配中的一些样本。 图17 从图3和图17可以发现有趣的结果，即它们不能通过全局匹配技术来实现。在图17显示的情况下，被检索的图形的现实意义和查询对象是不同的，尽管如此，子部分在几何上是和查询对象相同的。 为了评估我的部分匹配方法的性能，我们的报告对精密召回的实验进行了普林斯顿形状基准（psb）模型数据库。我们只使用分类包括类如人手，人脚，人脸，动物的四肢等自然模型。表二显示了根据以下内容作出的评估结论的总结：最近邻：属于相同等级查询的最贴切匹配的百分比；第一层与第二层：查询的类出现在top k匹配模型的比例，其中k取决于查询类的大小；措施：对检索结果的固定数量的精度和召回的混合测量。在判别方法的更多细节，参见shilane等人2004。 我们的实验是在p4-3.0 ghz 2 gb的内存下进行的。我们用“显著等级”（方程（1）为指标。然而，应该强调的是，在psb数据库最模型有一个粗略的三角（见，例如，图15（a）。在这种情况下，显著性等级过于粗糙，并且和相似的粗略图形有相当大的差别。为了避免这种情况,对于粗糙的模型,我们直接使用几何哈希表中的局部表面描述符。尽管如此，我们的精密召回分数相对于全局匹配实现典型的结果相当不错。应该指出的是，大部分的成功取决于类的定义。例如，人类的双手是良好定义的，而其他类，如动物的肢体或人的面孔，很难界定。图10 自相似性。在章鱼的触手吸盘模型具有相似的形状。注意，它们的大小各不相同的模型。图11大象的对称性分析（左上）。在三头大象类似区域检测和上色。图12斯坦福的3d扫描库中泰国雕像。模型包含10m多边形，具有粗糙的三相对称性。图13基于全局主成分分析（pca）模型对齐（右）和部分匹配（左）。图14形状检索的框架概述。给定一个数据库模型（a）；我们分析了每个图形的几何特性，并定义一个局部形状描述符啮合特性的稀疏表示（b）；然后我们从每个模型提取有趣的和显着的几何特征（c）；这些特征被编入索引并存储在模型数据库，可以有效地查询部分匹配（d）；上述步骤离线执行。当给定一个在线查询模型（e）；我们以同样的方式分析它，确定表面局部描述符（f）和突出的几何特征（g）；对每个显著几何特征，我们查询模型数据库来找到一系列匹配特征（h）。使用这些匹配我们返回具有更多匹配特征的模型。图15两个例子（b）和（c）的粗糙人手成功匹配（一），和两个假阳性匹配（d）和（e）。图16一种植物模型相似性查询的检索结果。图17部分匹配。潜艇（橙色）相匹配的两部分（左）和城堡的四塔（右）。表ii普林斯顿形状基准数据库和精度召回措施实验总结9.基于柱状图的描述符 局部匹配在从全距扫描仪生成的深度图像或者点云图中识别与记录3d物体（johnson and hebert 1999; huber and hebert 2003; frome et al. 2004）里扮演着一个重要的角色。在这些应用中，查询图像通常是依赖于视图和分辨率（视觉相关和分辨率相关）的，而且数据经常嘈杂而不完整。 用纯局部描述方法处理局部匹配，像是表面曲率，在噪音存在的时候是相对不稳定的。因此，稳定的点描述需要依靠局部附近的支持。举例说明，旋转图片johnson and hebert 1999和形状常数frome et al. 2004是有名的量化的对一个给出的点的局部附近的表示。 这些描述符作为输入的点云p和基准点p，并且通过p点周围小范围的其他点的分布捕捉p点局部的图像形状。支持的区域被离散为容器，我们还可以定义一个柱状图用来统计每个容器中包含的点的数量。这些柱状图可以被直接用来当作局部描述或者之后通过额外的转变增强，比如球面谐波表示。 图18第十八张图 通过计算得到的相同形状不同比例的星星模型的旋转图像。这张图显示了在这个位置的四个人们感觉形状相同但是比例不同的旋转星星图片。从中可以看出，即使旋转图像在相同比例计算形状时是相似的（左图），它们在不同比例相同形状是不同的（右图）。 图19第十九张图 这个l2距离表示的是计算出来的在正常大小的旋转图像和其他比例时之间同一点的距离。这个曲线图表示了旋转图像特征对比例大小的敏感度。 这些局部描述可以成为我们局部表面描述的替代物，然而这些描述并不是尺度不变的而且它们对几何学并不适用，这点我们会稍后解释。 基于柱状图的描述johnson and hebert 1999; huber and hebert 2003; frome et al.2004 不是尺度不变的。举例来说，在图18中，我们提到指定位置中的四个人们感觉形状相同但是比例不同的旋转星星图片。从中可以看出，即使旋转图像在相同比例计算形状时是相似的（左图），它们在不同比例相同形状是不同的（右图），旋转图像对比例的敏感度已经在图19中显示出来了。运用某些比例标准化并不适用，因为匹配的例子并没有先验性。第二十张图星星模型中总共包含18个3种不同比例的星星。中等比例的星星被用来当作疑问。使用旋转模型和我们理论的结果在b和c图中分别显示。这个例子表明了我们的方法是与比例无关的。第二十一张图 这个图像显示了描述数量和正确匹配数量之间的平衡。从中可以看出，我们的方法仅仅需要为数不多的描述就能成功地找到所有的局部匹配。 在我们的方法中，我们用几何哈希散列去匹配突出特征，这个方法本质上是一个尺度无关的方法，如同可以在图3和20中可以看到的一样。为了说明旋转图片描述和我们描述之间的不同，我们在不同场景中使用旋转图片描述。我们分发一些旋转图片在表面上，而且对每个旋转图片描述我们都计算了它的最佳匹配而不仅仅是一个匹配。然后我们通过计算在相应描述中得到最多匹