Coarse‐to‐Fine Isometric Shape Correspondence by Tracking Symmetric Flips

We address the symmetric flip problem that is inherent to multi‐resolution isometric shape matching algorithms. To this effect, we extend our previous work which handles the dense isometric correspondence problem in the original 3D Euclidean space via coarse‐to‐fine combinatorial matching. The key idea is based on keeping track of all optimal solutions, which may be more than one due to symmetry especially at coarse levels, throughout denser levels of the shape matching process. We compare the resulting dense correspondence algorithm with state‐of‐the‐art techniques over several 3D shape benchmark datasets. The experiments show that our method, which is fast and scalable, is performance‐wise better than or on a par with the best performant algorithms existing in the literature for isometric (or nearly isometric) shape correspondence. Our key idea of tracking symmetric flips can be considered as a meta‐approach that can be applied to other multi‐resolution shape matching algorithms, as we also demonstrate by experiments.     

Shape Matching via Quotient Spaces

We introduce a novel method for non‐rigid shape matching, designed to address the symmetric ambiguity problem present when matching shapes with intrinsic symmetries. Unlike the majority of existing methods which try to overcome this ambiguity by sampling a set of landmark correspondences, we address this problem directly by performing shape matching in an appropriate quotient space, where the symmetry has been identified and factored out. This allows us to both simplify the shape matching problem by matching between subspaces, and to return multiple solutions with equally good dense correspondences. Remarkably, both symmetry detection and shape matching are done without establishing any landmark correspondences between either points or parts of the shapes. This allows us to avoid an expensive combinatorial search present in most intrinsic symmetry detection and shape matching methods. We compare our technique with state‐of‐the‐art methods and show that superior performance can be achieved both when the symmetry on each shape is known and when it needs to be estimated.     

Continuous Matching via Vector Field Flow

We present a new method for non‐rigid shape matching designed to enforce continuity of the resulting correspondence. Our method is based on the recently proposed functional map representation, which allows efficient manipulation and inference but often fails to provide a continuous point‐to‐point mapping. We address this problem by exploiting the connection between the operator representation of mappings and flows of vector fields. In particular, starting from an arbitrary continuous map between two surfaces we find an optimal flow that makes the final correspondence operator as close as possible to the initial functional map. Our method also helps to address the symmetric ambiguity problem inherent in many intrinsic correspondence methods when matching symmetric shapes. We provide practical and theoretical results showing that our method can be used to obtain an orientation preserving or reversing map starting from a functional map that represents the mixture of the two. We also show how this method can be used to improve the quality of maps produced by existing shape matching methods, and compare the resulting map's continuity with results obtained by other operator‐based techniques.     

Global Correspondence Optimization for Non‐Rigid Registration of Depth Scans

We present a registration algorithm for pairs of deforming and partial range scans that addresses the challenges of non‐rigid registration within a single non‐linear optimization. Our algorithm simultaneously solves for correspondences between points on source and target scans, confidence weights that measure the reliability of each correspondence and identify non‐overlapping areas, and a warping field that brings the source scan into alignment with the target geometry. The optimization maximizes the region of overlap and the spatial coherence of the deformation while minimizing registration error. All optimization parameters are chosen automatically; hand‐tuning is not necessary. Our method is not restricted to part‐in‐whole matching, but addresses the general problem of partial matching, and requires no explicit prior correspondences or feature points. We evaluate the performance and robustness of our method using scan data acquired by a structured light scanner and compare our method with existing non‐rigid registration algorithms.     

基于谱对称的形状配准方法

针对现有三维形状配准方法中存在左右翻转的错误匹配问题,提出了基于内蕴对称特征检测的高效形状配准算法。首先,通过热核与几何约束构建模型的内蕴自对称点对;其次,基于谱嵌入特征空间分析提取模型的内蕴对称平面,并依据模型表面法向量有效识别模型的左右结构属性;然后,根据内蕴对称点对获得模型的一致性谱对称结构描述;最后,引入一致性点漂移算法(CPD),实现基于谱对称的非刚性模型的形状配准,有效避免了模型配准中的左右结构翻转问题。实验进一步论证了这种方法不仅有效提高了模型匹配的效率,而且能有效识别同类模型的结构特征,对于非刚性模型的配准具有较强的鲁棒性。     

Non‐Rigid Puzzles

Shape correspondence is a fundamental problem in computer graphics and vision, with applications in various problems including animation, texture mapping, robotic vision, medical imaging, archaeology and many more. In settings where the shapes are allowed to undergo non‐rigid deformations and only partial views are available, the problem becomes very challenging. To this end, we present a non‐rigid multi‐part shape matching algorithm. We assume to be given a reference shape and its multiple parts undergoing a non‐rigid deformation. Each of these query parts can be additionally contaminated by clutter, may overlap with other parts, and there might be missing parts or redundant ones. Our method simultaneously solves for the segmentation of the reference model, and for a dense correspondence to (subsets of) the parts. Experimental results on synthetic as well as real scans demonstrate the effectiveness of our method in dealing with this challenging matching scenario.     

Partial Shape Matching Using Transformation Parameter Similarity

In this paper, we present a method for non‐rigid, partial shape matching in vector graphics. Given a user‐specified query region in a 2D shape, similar regions are found, even if they are non‐linearly distorted. Furthermore, a non‐linear mapping is established between the query regions and these matches, which allows the automatic transfer of editing operations such as texturing. This is achieved by a two‐step approach. First, pointwise correspondences between the query region and the whole shape are established. The transformation parameters of these correspondences are registered in an appropriate transformation space. For transformations between similar regions, these parameters form surfaces in transformation space, which are extracted in the second step of our method. The extracted regions may be related to the query region by a non‐rigid transform, enabling non‐rigid shape matching.     

一种基于多尺度轮廓点空间关系特征的形状匹配方法

针对使用三角形区域表示描述子对相似形状进行匹配时,对微小形变比较敏感 以及区分剧烈变化的不相似形状时判别能力较弱的问题, 提出一种结合轮廓点空间关系特征的多尺度形状特征描述子.通过分析不同尺度下参考点与其他采样点之间的位置关系, 利用对应角度信息来对形状进行表示, 并在此基础上构造出一种新的形状特征描述子.本文所提特征提取方法能对形状的局部及全局信息更准确地描述, 具有较好的鲁棒性和判别能力.在形状特征匹配阶段, 利用轮廓点集顺序关系已知这一优势, 引入动态规划及形状复杂度分析的方法,分析形状间的匹配结果, 能够得到较好的形状匹配精度.通过对不同形状数据集行仿真实验, 证明本文方法能够有效地实现形状识别和检索.     

Symmetry in scalar field topology

Study of symmetric or repeating patterns in scalar fields is important in scientific data analysis because it gives deep insights into the properties of the underlying phenomenon. Though geometric symmetry has been well studied within areas like shape processing, identifying symmetry in scalar fields has remained largely unexplored due to the high computational cost of the associated algorithms. We propose a computationally efficient algorithm for detecting symmetric patterns in a scalar field distribution by analysing the topology of level sets of the scalar field. Our algorithm computes the contour tree of a given scalar field and identifies subtrees that are similar. We define a robust similarity measure for comparing subtrees of the contour tree and use it to group similar subtrees together. Regions of the domain corresponding to subtrees that belong to a common group are extracted and reported to be symmetric. Identifying symmetry in scalar fields finds applications in visualization, data exploration, and feature detection. We describe two applications in detail: symmetry-aware transfer function design and symmetry-aware isosurface extraction.     

A Condition Number for Non‐Rigid Shape Matching

Despite the large amount of work devoted in recent years to the problem of non‐rigid shape matching, practical methods that can successfully be used for arbitrary pairs of shapes remain elusive. In this paper, we study the hardness of the problem of shape matching, and introduce the notion of the shape condition number, which captures the intuition that some shapes are inherently more difficult to match against than others. In particular, we make a connection between the symmetry of a given shape and the stability of any method used to match it while optimizing a given distortion measure. We analyze two commonly used classes of methods in deformable shape matching, and show that the stability of both types of techniques can be captured by the appropriate notion of a condition number. We also provide a practical way to estimate the shape condition number and show how it can be used to guide the selection of landmark correspondences between shapes. Thus we shed some light on the reasons why general shape matching remains difficult and provide a way to detect and mitigate such difficulties in practice.     

有约束Patch-Match框架下的非刚体匹配算法

目的 非刚性物体进行匹配时,往往需要对图像中存在的非刚性形变目标进行快速精确的配准,进而实现对图像的后续处理和分析,实现快速而准确的非刚体匹配显得尤为重要。针对传统特征点匹配方法在非刚性物体匹配中准确性差的问题,本文提出了一种基于DAISY算子和有约束Patch-Match的非刚体密集匹配算法。方法 首先对参考图像和待匹配图像生成DAISY特征描述子,其次对两幅图像进行超像素分割,形成相互邻接但没有重叠的超像素块结构,并以其为单元,计算初始位置上对应每一个像素的DAISY特征算子聚合代价。然后,采用Patch-Match算法对整幅图像进行传播和变异,在变异过程中,通过图像预处理和分析得到的先验知识对位置标签的变异窗口进行局部空间约束,使得每个像素的位置标签在该空间范围内随机更新,计算新的聚合代价,保留代价较小的位置标签,重复迭代此过程,直到聚合代价不发生变化或者达到最大迭代次数为止。结果 实验选取了标准数据集、10幅分别由TFDS（the trucking fault dynamic image detection system）线阵列相机和框幅式相机采集的包含非刚体的图像进行匹配,均取得了较好的匹配效果,经验证,本文方法的匹配精度为86%,误匹配点的平均匹配误差为5个像素左右,是传统基于SIFT特征光流匹配方法误差的一半,并且本文采用的DAISY算子在特征提取速度上是Dense SIFT（dense scale invariant feature transform）特征提取算法的2~3倍,大大提升了图像匹配的效率。结论 本文提出了一种非刚体密集匹配算法,针对非刚体变化的不确定性采用密集特征点进行最优化搜索匹配。本文算法对包含小范围非刚性变化的图像匹配上具有较好的适应性,且匹配精度高,视觉效果好,鲁棒性强。