S. Chretien, O. Ekin Karasan, E. Oguz, M. Pinar

Inspired from a problem in computer vision we introduce the quantile matching problem on a bipartite graph, the two parts of which represent two point clouds. The goal is to achieve an optimal registration of a point cloud with another point cloud. The problem is posed as the problem of computing a (perfect when possible) matching, which maximizes the $\alpha$-quantile of affinity weights between the nodes of the graph. We prove that the problem is polynomially solvable in bipartite and non-bipartite graphs. Numerical illustrations are given. Implementations of the proposed algorithms in Python are described along with computational results with synthetic as well as real data from a computer vision application.

Keywords: Computer Vision; Point Cloud Registration ; Quantile; Matching; Bipartite Graphs; Graph Algorithms

Scheduled

FC1 Graphs and Networks 3
June 11, 2021  12:15 PM
1 - GB Dantzig