Efficient and Robust Shape Correspondence via Sparsity-Enforced Quadratic Assignment

• URL: http://arxiv.org/abs/2003.08680v2
• Date: Fri, 20 Mar 2020 21:23:38 GMT
• Title: Efficient and Robust Shape Correspondence via Sparsity-Enforced Quadratic Assignment
• Authors: Rui Xiang, Rongjie Lai, Hongkai Zhao
• Abstract summary: We introduce a novel local pairwise descriptor and then develop a simple, effective iterative method to solve the resulting quadratic assignment. Our pairwise descriptor is based on the stiffness and mass iteration matrix of finite element approximation of the Laplace-Beltrami differential operator. We use various experiments to show the efficiency, quality, and versatility of our method on large data sets, patches, and point clouds.
• Score: 16.03666555216332
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we introduce a novel local pairwise descriptor and then develop a simple, effective iterative method to solve the resulting quadratic assignment through sparsity control for shape correspondence between two approximate isometric surfaces. Our pairwise descriptor is based on the stiffness and mass matrix of finite element approximation of the Laplace-Beltrami differential operator, which is local in space, sparse to represent, and extremely easy to compute while containing global information. It allows us to deal with open surfaces, partial matching, and topological perturbations robustly. To solve the resulting quadratic assignment problem efficiently, the two key ideas of our iterative algorithm are: 1) select pairs with good (approximate) correspondence as anchor points, 2) solve a regularized quadratic assignment problem only in the neighborhood of selected anchor points through sparsity control. These two ingredients can improve and increase the number of anchor points quickly while reducing the computation cost in each quadratic assignment iteration significantly. With enough high-quality anchor points, one may use various pointwise global features with reference to these anchor points to further improve the dense shape correspondence. We use various experiments to show the efficiency, quality, and versatility of our method on large data sets, patches, and point clouds (without global meshes).

Related papers

• Variable Substitution and Bilinear Programming for Aligning Partially Overlapping Point Sets [48.1015832267945]
  This research presents a method to meet requirements through the minimization objective function of the RPM algorithm. A branch-and-bound (BnB) algorithm is devised, which solely branches over the parameters, thereby boosting convergence rate. Empirical evaluations demonstrate better robustness of the proposed methodology against non-rigid deformation, positional noise, and outliers, when compared with prevailing state-of-the-art transformations.
  arXiv  Detail & Related papers  (2024-05-14T13:28:57Z)
• Registration of algebraic varieties using Riemannian optimization [0.0]
  We consider the problem of finding a transformation between two point clouds that represent the same object but are expressed in different coordinate systems. Our approach is not based on a point-to-point correspondence, matching every point in the source point cloud to a point in the target point cloud.
  arXiv  Detail & Related papers  (2024-01-16T18:47:38Z)
• Globally solving the Gromov-Wasserstein problem for point clouds in low dimensional Euclidean spaces [5.534626267734822]
  This paper presents a framework for computing the Gromov-Wasserstein problem between two sets of points in low dimensional spaces. It can be used to quantify the similarity between two formations or shapes, a common problem in AI and machine learning.
  arXiv  Detail & Related papers  (2023-07-18T08:20:56Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
  arXiv  Detail & Related papers  (2023-06-21T17:03:22Z)
• Robust Ellipse Fitting Based on Maximum Correntropy Criterion With Variable Center [25.20786549560683]
  We develop an ellipse fitting method that is robust to outliers based on conerenren. The proposed method is shown to have significantly better performance over the existing methods in both simulated data and real images.
  arXiv  Detail & Related papers  (2022-10-24T01:59:22Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• PointFlow: Flowing Semantics Through Points for Aerial Image Segmentation [96.76882806139251]
  We propose a point-wise affinity propagation module based on the Feature Pyramid Network (FPN) framework, named PointFlow. Rather than dense affinity learning, a sparse affinity map is generated upon selected points between the adjacent features. Experimental results on three different aerial segmentation datasets suggest that the proposed method is more effective and efficient than state-of-the-art general semantic segmentation methods.
  arXiv  Detail & Related papers  (2021-03-11T09:42:32Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  In many applications, we need algorithms which can align partially overlapping point sets are invariant to the corresponding corresponding RPM algorithm. We first show that the objective is a cubic bound function. We then utilize the convex envelopes of trilinear and bilinear monomial transformations to derive its lower bound. We next develop a branch-and-bound (BnB) algorithm which only branches over the transformation variables and runs efficiently.
  arXiv  Detail & Related papers  (2021-01-19T04:24:23Z)
• Aligning Partially Overlapping Point Sets: an Inner Approximation Algorithm [80.15123031136564]
  We propose a robust method to align point sets where there is no prior information about the value of the transformation. Our algorithm does not need regularization on transformation, and thus can handle the situation where there is no prior information about the values of the transformations. Experimental results demonstrate the better robustness of the proposed method over state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2020-07-05T15:23:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.