×

An adversarial optimization approach to efficient outlier removal. (English) Zbl 1365.68428

Summary: This paper proposes a novel adversarial optimization approach to efficient outlier removal in computer vision. We characterize the outlier removal problem as a game that involves two players of conflicting interests, namely, model optimizer and outliers. Such an adversarial view not only brings new insights into some existing methods, but also gives rise to a general optimization framework that provably unifies them. Under the proposed framework, we develop a new outlier removal approach that is able to offer a much needed control over the trade-off between reliability and speed, which is usually not available in previous methods. Underlying the proposed approach is a mixed-integer minmax (convex-concave) problem formulation. Although a minmax problem is generally not amenable to efficient optimization, we show that for some commonly used vision objective functions, an equivalent Linear Program reformulation exists. This significantly simplifies the optimization. We demonstrate our method on two representative multiview geometry problems. Experiments on real image data illustrate superior practical performance of our method over recent techniques.

MSC:

68T45 Machine vision and scene understanding
90C11 Mixed integer programming

Software:

SIFT; SeDuMi
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Fischler, M.A., Bolles, R.C.: Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 24(6), 381-395 (1981) · doi:10.1145/358669.358692
[2] Alizadeh, F., Goldfarb, D.: Second-order cone programming. Math. Program. 95(1), 3-51 (2003) · Zbl 1153.90522 · doi:10.1007/s10107-002-0339-5
[3] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004) · Zbl 1058.90049 · doi:10.1017/CBO9780511804441
[4] Enqvist, O.; Josephson, K.; Kahl, F., Optimal correspondences from pairwise constraints (2009)
[5] Enqvist, O., Olsson, C., Kahl, F.: Stable structure from motion using rotational consistency. Tech. rep., Lund University (2011)
[6] Govindu, V., Robustness in motion averaging (2006)
[7] Hartley, R.; Kahl, F., Optimal algorithms in multiview geometry (2007)
[8] Hartley, R.; Schaffalitzky, F., L∞ minimization in geometric reconstruction problems (2004)
[9] Hartley, R., Zisserman, A.: Multiple View Geometry in Computer Vision. Cambridge University Press, Cambridge (2003) · Zbl 0956.68149
[10] Huber, P.J.: Robust estimation of a location parameter. Ann. Math. Stat. 35(1), 73-101 (1964) · Zbl 0136.39805 · doi:10.1214/aoms/1177703732
[11] Kahl, F., Hartley, R.: Multiple-view geometry under the L∞-norm. IEEE Trans. Pattern Anal. Mach. Intell. 30(9), 1603-1617 (2008) · doi:10.1109/TPAMI.2007.70824
[12] Ke, Q.; Kanade, T., Quasiconvex optimization for robust geometric reconstruction (2005)
[13] Lee, K., Meer, P., Park, R.: Robust adaptive segmentation of range images. IEEE Trans. Pattern Anal. Mach. Intell. 20(2), 200-205 (1998) · doi:10.1109/34.659940
[14] Li, H., A practical algorithm for L∞ triangulation with outliers (2007)
[15] Li, H., Consensus set maximization with guaranteed global optimality for robust geometry estimation (2009)
[16] Lobo, M., Vandenberghe, L., Boyd, S., Lebret, H.: Applications of second-order cone programming. Linear Algebra Appl. 284(1-3), 193-228 (1998) · Zbl 0946.90050 · doi:10.1016/S0024-3795(98)10032-0
[17] Lowe, D.: Distinctive image features from scale-invariant keypoints. Int. J. Comput. Vis. 60(2), 91-110 (2004) · doi:10.1023/B:VISI.0000029664.99615.94
[18] Monteiro, R., Adler, I.: Interior path following primal-dual algorithms. Part I: Linear programming. Math. Program. 44(1), 27-41 (1989) · Zbl 0676.90038 · doi:10.1007/BF01587075
[19] Nguyen, T., Welsch, R.: Outlier detection and least trimmed squares approximation using semi-definite programming. Comput. Stat. Data Anal. 54(12), 3212-3226 (2010) · Zbl 1284.62430 · doi:10.1016/j.csda.2009.09.037
[20] Nistér, D.: An efficient solution to the five-point relative pose problem. IEEE Trans. Pattern Anal. Mach. Intell. 26(6), 756-770 (2004) · doi:10.1109/TPAMI.2004.17
[21] Nistér, D.: Preemptive RANSAC for live structure and motion estimation. Mach. Vis. Appl. 16(5), 321-329 (2005) · doi:10.1007/s00138-005-0006-y
[22] Olsson, C.; Enqvist, O., Stable structure from motion for unordered image collections (2011)
[23] Olsson, C.; Eriksson, A.; Hartley, R., Outlier removal using duality (2010)
[24] Rockafellar, R.: Convex Analysis. Princeton University Press, Princeton (1997) · Zbl 0932.90001
[25] Rousseeuw, P., Van Driessen, K.: Computing LTS regression for large data sets. Data Min. Knowl. Discov. 12(1), 29-45 (2006) · doi:10.1007/s10618-005-0024-4
[26] Rousseeuw, P.J., Leroy, A.M.: Robust Regression and Outlier Detection. Wiley, New York (1987) · Zbl 0711.62030 · doi:10.1002/0471725382
[27] Russell, S., Norvig, P.: Artificial Intelligence: A Modern Approach, 2nd edn. Prentice Hall, New York (2003) · Zbl 0835.68093
[28] Seo, Y.; Lee, H.; Lee, S., Outlier removal by convex optimization for L-infinity approaches, 203-214 (2009) · doi:10.1007/978-3-540-92957-4_18
[29] Sim, K.; Hartley, R., Removing outliers using the L∞ norm (2006)
[30] Triggs, B.; McLauchlan, P.; Hartley, R.; Fitzgibbon, A., Bundle adjustment—a modern synthesis, 153-177 (2000) · doi:10.1007/3-540-44480-7
[31] Yu, J.; Eriksson, A.; Chin, T. J.; Suter, D., An adversarial optimization approach to efficient outlier removal (2011) · Zbl 1365.68428
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.