Skip to content (access key 's')
Logo of Technion
Logo of CS Department


Pixel Club: Approximation Algorithms for Aligning Points to Lines with Applications to Visual Tracking
event speaker icon
Ibrahim Jubran (Haifa University)
event date icon
Monday, 8.10.2018, 11:00
event location icon
Taub 401
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.
[Back to the index of events]