Robust, Real-Time Motion and Pose Estimation using Linear Programming

A method to compute motion models in real time from point-to-line correspondences using linear programming is presented. Point-to-line correspondences are the most reliable measurements for image motion given the aperture effect, and it is shown how they can approximate other motion measurements as well. An error measure for image alignment using the L1 metric and based on point-to-line correspondences achieves results which are more robust than those for the commonly used L2 metric. The L1 error measure is minimized using linear programming. While estimators based on L1 are not robust in the breakdown point sense, experiments show that the proposed method is robust enough to allow accurate motion estimation over hundreds of consecutive frames. The L1 solution is compared to standard M-estimators and Least Median of Squares (LMedS) and it is shown that the L1 metric provides a reasonable and efficient compromise for various scenarios. The entire computation is performed in real-time on a PC (Pentium MMX 300Mhz) without special hardware.


"Real-Time Motion Analysis with Linear Programming,"
M. Ben-Ezra, S. Peleg and M. Werman,
Computer Vision and Image Understanding (CVIU), Vol. 78, No. 1, pp. 32-52, Apr 2000. [PDF]

"Model Based Pose Estimator Using Linear-Programming,"
In Proc. European Conference on Computer Vision (ECCV),, I:267-281, June 2000. [PDF]

"Real-Time Motion Analysis with Linear-Programming,"
M. Ben-Ezra, S. Peleg and M. Werman,
In Proc. International Conference on Computer Vision (ICCV), pp. 703-709, September 1999. [PDF]

"A Real-Time Video Stabilizer Based on Linear-Programming,"
M. Ben-Ezra, S. Peleg and M. Werman,
In Frame-Rate workshop. Corfu, Greece Sept 1999. [PDF]

"Efficient Computation of the Most Probable Motion from Fuzzy Correspondences,"
M. Ben-Ezra, S. Peleg and M. Werman,
In IEEE Workshop on Applications of Commuter Vision (WACV), pp. 22-27, Oct 1998. [PDF]


Real-Time video stabilization using linear programming. [QT] [AVI]


"TinyProf - A Two Pages Profiler,"
Very small footprint and effective tag based profiler. [PDF] [ZIP]

"Solvex - L1 Linear Programming Equation Set Solver,"
A simple simplex based L1 solver for linear System of Equations. [PDF] [ZIP]

© (software) The Hebrew University of Jerusalem.

Related Projects