Matching point sets : our work at SIGGRAPH 2019

LIRIS is again at SIGGRAPH, the leading conference in computer graphics, this time to present work by Nicolas Bonneel and David Coeurjolly on matching point sets. A fast algorithm was developped, using 1-d projections of higher-dimensional point sets, and based on optimal transport theory.

This summer we have presented a new algorithm for matching point sets, with applications in color processing and 3-d point sets registration. This algorithm consists in projecting points on random lines, and then, once the problem has been reduced to one dimension, matching points in 1-d.

When the number of points in both sets is the same, such 1-d matching is trivial: we just need to sort points, and progressively match them from left to right. However, when the number of points is not the same, existing methods are less trivial and much more costly -- typically methods using dynamic programming are used. We have developped an algorithm that is several orders of magnitude faster than such methods. This thus solves a so-called "partial" 1-d optimal transport problem.

We detail this algorithm further in a short article for CNRS: