A method to compute motion models in real time from point-to-line correspon
dences using linear programming is presented. Point-to-line correspondences
are the most reliable measurements for image motion given the aperture eff
ect. and it is shown how they can approximate other motion measurements as
well. An error measure for image alignment using the L-1 metric and based o
n point-to-line correspondences achieves results which are more robust than
those for the commonly used L-2 metric. The L-1 error measure is minimized
using linear programming. While estimators based on L-1 are not robust in
the breakdown point sense, experiments show that the proposed method is rob
ust enough to allow accurate motion recovery over hundreds of consecutive f
rames. The L-1 solution is compared to standard M-estimators and Least Medi
an of Squares (LMedS) and it is shown that the L-1 metric provides a reason
able and efficient compromise for various scenarios. The entire computation
is performed in real-time on a PC without special hardware. (C) 2000 Acade
mic Press.