The Taub Faculty of Computer Science Events and Talks

We consider the pose-estimation problem of aligning (rotating and translating) a set of n points to a corresponding set of n lines, both on the plane. The goal is to minimize the sum of distances between the matched point-line pairs over all possible translations, rotations, and matching functions.

These natural problems occur e.g. in localization of GPS data (aligning points to a map), 2D images (object to RGB pixels) or stars (to sky patterns, e.g. by drone), with applications for mobile robots (cars, humanoids), or head-positioning for Virtual/Augmented Reality.

We obtain the first provable constant factor approximation algorithm that runs in polynomial time, or O(n) time if the matching between the points and lines is given.

The solution is based on a new generic optimization technique for minimizing the sum of n non-convex functions that satisfy a property that we call piecewise log-Lipschitz, and a data reduction technique known as core-set that we designed for this problem.

Finally, we present experimental results and a real-time tracking system with potential applications for Augmented/Virtual Reality, including benchmark.

*Based on a joint work with Dr. Dan Feldman.