三维几何部分和近似对称检测1.doc

三维几何部分和近似对称检测图1：在雕塑模型的对称性检测。从左至右依次为：原始模型，检测到的局部和近似对称，颜色编码的偏离完美对称的边界框对角线的一小部分。抽象“对称是一个复杂性降低的概念.;寻求它无处不在。” - 阿兰J.玻璃市许多天然和人造物体表现出显着的对称性，或包含重复的子结构。本文提出了一种新的算法，处理几何模型和有效地发现并提取他们的欧式对称的紧凑表示。这些对称性可以只是部分的，近似的，或两者兼而有之。该方法是基于匹配的签名，对简单的局部形状和使用这些比赛中积累的证据在适当的变换空间的对称。聚类阶段中提取潜在的显着对称的对象，其次是检验步骤。统计抽样分析的基础上，我们的成功率，我们的算法提供了理论保障。提取的对称图形表示捕捉重要的高层结构的几何模型，这反过来又使大集的进一步加工业务，包括形状压缩，分割，编辑一致，对称，索引，检索等信息CR分类：I.3.5图形学学报：计算几何形状和对象建模。关键词：几何造型，形态分析，检测对称，形状描述，取样担保。1引言对称是必要的，无处不在的概念，性质，科学和艺术。例如，在几何，在厄兰格的FelixKlein方案的1893起到了推波助澜的超过一个世纪的数学家的兴趣，在某些集体行动的一个重要原则理解几何空间不变性。许多生物，物理或人造结构表现出的对称性作为一个基本的设计原则或作为其功能的一个重要方面。对称无论进化或设计，隐含着一定的经济效益和效率的结构，使人们普遍有吸引力的。对称性也起着重要的作用，在人类视觉感知和美学。可以说很多我们周围的世界的理解的基础上共享或重复结构的认知和认可，是我们的美感汤普森1961。在本文中，我们提出了一种新的方法用于检测有意义的数字化三维形状的对称性。据我们了解一组变换下的不变性对称性 - 在我们的例子中平移，旋转，再屈曲，并均匀缩放，共同发电机的欧氏集团。下图所示的二维图。在这个例子中可以看出，我们是相当明显的对称性或同余可以是近似的，发生在不同的尺度。我们的目标是定义一个算法，该算法提取（部分）对称性在所有尺度上，包括不同程度的近似或不完美的对称性。这允许用户选择的对称性，是最有意义的一个特定的应用程序的子集。例子包括扫描登记和比对，形状匹配，分割和骨架提取，压缩，先进的建模和编辑，形状和数据库检索。为了实现这一目标，我们分开的对称性计算分为两个阶段：在第一阶段，我们计算简单形状描述子在选定的一组点的形状。这些描述符的选择，使他们感兴趣的组行动下是不变的。我们使用这些局部描述符配对点可以映射到彼此下候选人对称操作。我们认为，对每一个这样的沉积质量，或投票，在转变为一个特定的对称空间的兴趣。在这个空间里，对类似的转变，形成集群，提供相应的对称关系的证据。在第二个步骤中，我们使用一个随机的聚类算法，前道，这次大规模的分布显着的模式。由于地图平转换空间不保留样品的空间相干的ENCE或结构上输入的形状，我们是否已经发现一个有意义的对称空间一致性检查所提取的子部分的表面。我们的群集的方法提供所必需的表面对应，因为在转换空间对应于每一个点质量的候选点在空间域中的日期对。因此，只有一小需要考虑的候选样本的检测和提取对称面的修补程序，避免了昂贵的二次空间搜索在整个输入数据集。这种分离为两个阶段，我们的算法的有效性是至关重要的。的基本观察是：给出一个建议的对称关系，以确认是否是这个特定的对称模型中存在，它是简单而有效的，我们只需要申请对称变换和检查模型是否被映射到自身，或子模型的一部分被映射到相应的子部分。然而，所有潜在的映射是过于庞大，做一个彻底的搜索。因此，我们首先积累了统计上的证据，通过我们的集群在变换空间的对称性存在。只有这方面的证据是足够的，如果我们进行空间验证，以检查是否有特定的对称实际上是有效的。因此，复杂的对称提取主要取决于有关本模型中的对称性，而不是模型本身的复杂性，或底层对称组的数量和大小。作为我们的方法的一部分，我们可以提供一种定量测量上的“正确性”，或显着性的对称关系，这使得用户能够控制在所提取的对称性的完善程度。此外，通过指定的大小的局部形状描述符的组，用户可以交易准确性为了计算效率。较少的样本用于检测大型的全球性对称性是足够的，小部分的对称性要求显着密集的采样。我们的算法的最终输出是一个“对称图形”的对象，其中编码的对象的显两者并无统计对称性，每个所描述的一个补丁对和它们之间的相应的变换。对象，其中包含定期重复结构，如窗户或门，建筑模型，我们可以恢复的基础上减少算法的重复图案的对称性。实际上，这导致一个贫乏，更多的信息对称图形，只包含基本的对称发电机和避免编码分别对称，产品已记录的对称性。这种重复模式发现一致的网编辑应用程序可以是有用的。1.1贡献我们提出了一个新的算法为了配对样本点的三维形状与兼容的局部描述符来生成转换空间上的分布，其的峰值捕捉的对象有关对称性。我们将展示如何在这个分布的随机聚类算法检测到潜在的对称候选物，并提供表面修补法提取降低对称图形提取的集群。我们的算法可以应用到不同的外形特征的3D模型。内存要求是最小的，在这个意义上，它的复杂性主要取决于实际存在的对象的数量和程度的对称性，计算输出敏感。此外，我们还提供了理论界限的成功率，我们的算法选择的初始样本数的函数。这些结果表明，该算法是很有效地甚至对于非常大的不适合放在主内存中的模型。1.2相关工作这个问题已被广泛研究的众多领域，包括视觉感知，计算机视觉，机器人技术，计算几何的对称性检测_早期的方法集中在寻找完美的对称性在二维或三维的平面点集 Atallah 1985，Atallah 1985。由于精确对称的限制，限制了使用这些方法对于现实世界的物体，Alt et al.1988提出计算近似的全球三维点集的对称性，但该算法的复杂性，使得大型数据集是不切实际的 Zabrodsky et al. 1995形式化表示作为一个连续的特征对称的近似对称的概念 Sun et al. 1997提出审查的的高斯图像以恢复全球反射对称和旋转对称的关系_Kazhdan和他的同事2002推出了全球再射式对称形状描述的简明编码_后来，他们延续了这项工作，并用它旋转对称的形状检索数据库中匹配Kazhdanet al. 2004.。我们的方法具有一些相似的Hough变换，一个流行的特征提取方法主要用于图像处理。从开始使用边缘检测获得的采样点的一组的方法，该方法重复选择小的子集，这些样品的特征曲线的参数估计。我们的方法相类似，所有这些估计数施放的累积和占多数的基础上的最终特性曲线中提取。最近Hough变换的思想已被loy和Eklundh用于检测图像中的反射对称和旋转对称。Fischler and Bolles 1981提出的随机抽样一致性（RANSAC）是一个强大的含有许多异常点的数据模型拟合算法。在上下文的形状匹配的基本想法是随机选择一组相应的样本在查询和目标形状,应用全局变换诱导这些样本,并评估匹配两个形状之间的误差。如果足够多的转换以这种方式进行,有关对称性可以最终确定。由于匹配误差的评估需要代价高昂空间接近性测试，几何散列法【姆丹】预计算所有可能的路线通过密集采样的空间变换和存储产生的形状分布的一个散列网格。Gal and Cohen-Or 2006 最近提出了一种有效的方法，基于这一理念的形状匹配算法。他们的算法用计算，分组，以形成显着的形状特征局部形状描述。使用经验性显着措施，形状特征，然后使用预先计算的几何哈希表可以有效的部分匹配。虽然共享一些相似之处，我们的方法是根本不同的RANSAC和几何散列法。我们避免了昂贵穷举搜索，通过计算匹配误差的转变后，我们积累足够的证据证明对称性。同时我们的方法需要最小的存储与几何散列,对于复杂的几何形状 哈希表需要高达3.5 G的报告。1.3 概述我们首先给一些直觉_我们的方法在2D例如图3所示，其目的是检测到重新射式对称的蝴蝶。_任何对模型的边界上的点（p，q）的定义相对于平分线_一个独特的反射_通过（P + Q）/ 2与正常方向p - q时。因此，可以理解为这样一对为这specificre射式对称的存在证据。在所有这些对我们可以积累这方面的证据，并提取相关_对称关系。只有对多点认同在相同的反射线，我们有理由相信，相应的对称性是真正的模型中存在。因此，我们可以检测潜在的对称性看变换的空间，其中每个点对应一个specificre反射线的点_集群。然而，正如图中所示，一对单点的证据是唯一可靠的_如果周围的点的局部几何形状被忠实地反映了在反射变换这样的观察能让我们删除一些点集以避免大量的