突出几何特征在局部匹配和相似性测定中的应用研究论文.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和Mardia[1998]作的关于形状的正式定义：把位置、规模和旋转效应（欧几里得变换）从物体中滤出后，剩下的就是物体的全部几何信息 有一个共识就是根据部分来代表整个形状可能有助于用人类的视角来认识过程[Hebb 1949]。

在二维空间，它可以用于处理闭塞问题，在三维空间，它可以用于处理非刚性体一个关键的问题是：哪些部分（需要处理）？在我们的研究中，我们定义，由通用计算规则的方式，一个物品的突出部分，即压缩了足够多特征的部分，将被用于第一级搜索中[Hoffman and Singh 1997]关于物体的“部分显著性”，我们目标是用一小部分特征来捕捉物体的形状其显著性，在某种程度上，是用有效性作为指标来决定 我们的方法是建立在Hoffman和Singh[1997]提出的视觉部分显著性理论之上的根据他们的理论，一个部件的显著性是它尺寸的函数，相对于整个物体，与其突出的程度和边界的强度有关在这项工作中，我们的目标是开发能应用于网格的方法的定量定义重点就是对“边界强度”的计算我们的方法是使用曲率值的函数我们建议，一个物体的显著性部分取决于（至少）两个因素：它相对于整个物体的大小以及曲率变化和强度的数量在第五部分我们将描述确定显著性几何特征的计算方法3.概述 给定一个三维表格，我们分析它的几何特性并确定用部分形状描述的网格稀疏表示然后我们从网格中提取有趣并显著的几何特征这些特征被索引并存储在可被有效地用于查询部分匹配模式的数据库。

匹配子部分需要转换成一个共同的坐标系一个很自然的实现方式是存储所有模型在由每个顶点以及其邻域确定的所有可能坐标系中然后，对于给定的查询，我们将测试由查询的顶点所确定的所有可能的方位和定标这种方法会导致测试中“组合爆炸”，这远远超出了我们的计算能力，尤其是（计算）那些含有上千个或更多顶点的模型为了克服这些组合障碍，我们提出了三种方法：——用一组形状的稀疏描述符表示给定的网孔每个描述符表示具有良好的二次拟合的局部区域——确定一小套显著性的几何特征并索引它们显著的特征表示一个给定的形状的令人关注的部分——预先计算几何哈希表，使得在旋转和缩放变换下能够快速地部分匹配在四至六节，我们提出以下的方法——分析模型的表面；——定义局部的形状描述符；——定义显著性特征并存储索引的矢量；——使用索引和集合散列法查询部分匹配的模型数据库然后在第七节我们将讨论我们方法的性能问题在第八节在我们展示了一些基于我们的部分匹配算法的应用程序和结果在第九节，我们将说明几何散列法和基于直方图方法之间的关系，然后在第十节我们得出结论，并讨论未来的工作在我们继续之前，我们参考图3，它充分说明了部分匹配的精髓之处该图显示了模型（a）和（b）三部分的匹配。

值得注意的是，这两个模型只有一小部分实际匹配这个例子强调了一个事实，即部分匹配多于给定模型的子部分的匹配，并且该匹配部分预先并不确定3.局部的表面描述符 一个局部的表面描述符是一个点P，它在表面上或者是在P点附近的与其相关联的二次斑点的近似表面上关键点是，只要每个描述符有效地代表它周围的局部表面区域，那么一小部分的描述符就可以表示形状这种表示适用于几何形状平滑区域由相对较少数量的描述符所表示，因为每一个二次曲面斑点可以在局部近似于一个大的区域高频的不平滑的区域需要相对大量的描述符注意图5（b）中在鹰嘴附近和在光滑区域的局部形状描述符的密度作为一种分析局部表面的手段，我们将曲率值与每个描述符相关联接下来，我们通过描述二次曲面拟合方案和算法来构造一组有效的描述符图片3 部分匹配老鹰模型（b）的三个部分通过高度变形叠加在一个结构上应用于图（a）中这三个副本有不同的尺度和方向通过应用部分匹配（c）-（e），老鹰的这三个部分与整个老鹰模型相匹配请注意，每一对匹配之间只有部分重叠该匹配是通过在一个共同的坐标系中对三组局部形状描述符的变换实现的用小黄球来说明局部的形状描述符4.1 二次拟合和曲率估计 使用Douros和Buxton[2002]提出的方法，表面通过可分析的二次曲面斑点很好地由每个顶点近似表示。

对于每个二次曲面斑点，选择可以代表的点然后计算分析斑点的在该点的微分属性对于可表示为F（X，Y，Z）= 0的隐函数的表面，我。