Two efficient algorithms for outlier removal in multi-view geometry using L_∞ norm

L_∞ norm has been recently introduced to multi-view geometry computation to achieve globally optimal computation. It however suffers from a serious sensitivity to outliers. A few remedies have been proposed but with high computational complexity. This paper presents two efficient algorithms to overcome these problems. Our first algorithm is based on a cheap and effective local descent method (as opposed to the conventional but expensive SOCP(Second Order Cone Programming)). The second algorithm further improves the first one by using a Depth-first search heuristics. Both algorithms retain the nice property of global optimality of the L_∞ scheme, while at cost only a small fraction of the original computation. Experiments on both synthetic data and real images have validated the proposed algorithms.