Reconstruction of Convex Polytope Compositions from 3D Point-clouds

• URL: http://arxiv.org/abs/2105.02956v1
• Date: Tue, 27 Apr 2021 00:14:55 GMT
• Title: Reconstruction of Convex Polytope Compositions from 3D Point-clouds
• Authors: Markus Friedrich and Pierre-Alain Fayolle
• Abstract summary: Reconstructing a composition (union) of convex polytopes that perfectly fits the corresponding input point-cloud is a hard optimization problem. We propose a pipeline that first extracts a set of planes, then partitions the input point-cloud into weakly convex clusters and finally generates a set of convex polytopes as the intersection of fitted planes for each partition. Finding the best-fitting convex polytopes is formulated as a optimization problem over the set of fitted planes and is solved using an Evolutionary Algorithm.
• Score: 3.04585143845864
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Reconstructing a composition (union) of convex polytopes that perfectly fits the corresponding input point-cloud is a hard optimization problem with interesting applications in reverse engineering and rigid body dynamics simulations. We propose a pipeline that first extracts a set of planes, then partitions the input point-cloud into weakly convex clusters and finally generates a set of convex polytopes as the intersection of fitted planes for each partition. Finding the best-fitting convex polytopes is formulated as a combinatorial optimization problem over the set of fitted planes and is solved using an Evolutionary Algorithm. For convex clustering, we employ two different methods and detail their strengths and weaknesses in a thorough evaluation based on multiple input data-sets.

Related papers

• Mathematical Programming Algorithms for Convex Hull Approximation with a Hyperplane Budget [0.0]
  We search for a convex polyhedron with at most K faces, containing all the positive points and no negative point. The problem is known in the literature for pure convex polyhedral approximation. Our interest stems from its possible applications in constraint learning.
  arXiv  Detail & Related papers  (2024-07-24T15:08:52Z)
• Differentiable Convex Polyhedra Optimization from Multi-view Images [29.653374825428614]
  This paper presents a novel approach for the differentiable rendering of convex polyhedra. It addresses the limitations of recent methods that rely on implicit field supervision.
  arXiv  Detail & Related papers  (2024-07-22T14:53:29Z)
• 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)
• PolyGNN: Polyhedron-based Graph Neural Network for 3D Building Reconstruction from Point Clouds [22.18061879431175]
  PolyGNN is a graph neural network for building reconstruction point clouds. It learns to assemble primitives obtained by polyhedral decomposition. We conduct a transferability analysis across cities and on real-world point clouds.
  arXiv  Detail & Related papers  (2023-07-17T16:52:25Z)
• A Combinatorial Perspective on the Optimization of Shallow ReLU Networks [35.329916555349214]
  NP-hard problem of optimizing a shallow ReLU network can be characterized as a search over each training example's activation pattern. We show that it can be naturally modeled via a zonotope with its set is to the set of feasible activation patterns.
  arXiv  Detail & Related papers  (2022-10-01T03:09:02Z)
• A Scalable Combinatorial Solver for Elastic Geometrically Consistent 3D Shape Matching [69.14632473279651]
  We present a scalable algorithm for globally optimizing over the space of geometrically consistent mappings between 3D shapes. We propose a novel primal coupled with a Lagrange dual problem that is several orders of magnitudes faster than previous solvers.
  arXiv  Detail & Related papers  (2022-04-27T09:47:47Z)
• 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)
• Differentiable Convolution Search for Point Cloud Processing [114.66038862207118]
  We propose a novel differential convolution search paradigm on point clouds. It can work in a purely data-driven manner and thus is capable of auto-creating a group of suitable convolutions for geometric shape modeling. We also propose a joint optimization framework for simultaneous search of internal convolution and external architecture, and introduce epsilon-greedy algorithm to alleviate the effect of discretization error.
  arXiv  Detail & Related papers  (2021-08-29T14:42:03Z)
• PU-Flow: a Point Cloud Upsampling Networkwith Normalizing Flows [58.96306192736593]
  We present PU-Flow, which incorporates normalizing flows and feature techniques to produce dense points uniformly distributed on the underlying surface. Specifically, we formulate the upsampling process as point in a latent space, where the weights are adaptively learned from local geometric context. We show that our method outperforms state-of-the-art deep learning-based approaches in terms of reconstruction quality, proximity-to-surface accuracy, and computation efficiency.
  arXiv  Detail & Related papers  (2021-07-13T07:45:48Z)
• 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)
• Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
  We develop a convex analytic approach to analyze finite width two-layer ReLU networks. We show that an optimal solution to the regularized training problem can be characterized as extreme points of a convex set. In higher dimensions, we show that the training problem can be cast as a finite dimensional convex problem with infinitely many constraints.
  arXiv  Detail & Related papers  (2020-02-25T23:05: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.