Abstract
Geometric model fitting is a typical chicken-&-egg problem: data points should be clustered based on geometric proximity to models whose unknown parameters must be estimated at the same time. Most existing methods, including generalizations of RANSAC, greedily search for models with most inliers (within a threshold) ignoring overall classification of points. We formulate geometric multi-model fitting as an optimal labeling problem with a global energy function balancing geometric errors and regularity of inlier clusters. Regularization based on spatial coherence (on some near-neighbor graph) and/or label costs is NP hard. Standard combinatorial algorithms with guaranteed approximation bounds (e.g. α-expansion) can minimize such regularization energies over a finite set of labels, but they are not directly applicable to a continuum of labels, e.g. \({\mathcal{R}}^{2}\) in line fitting. Our proposed approach (PEaRL) combines model sampling from data points as in RANSAC with iterative re-estimation of inliers and models’ parameters based on a global regularization functional. This technique efficiently explores the continuum of labels in the context of energy minimization. In practice, PEaRL converges to a good quality local minimum of the energy automatically selecting a small number of models that best explain the whole data set. Our tests demonstrate that our energy-based approach significantly improves the current state of the art in geometric model fitting currently dominated by various greedy generalizations of RANSAC.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Beis, J. S., & Lowe, D. G. (1997). Shape indexing using approximate nearest-neighbour search in high-dimensional spaces. In CVPR (pp. 1000–1006).
Birchfield, S., & Tomasi, C. (1999). Multiway cut for stereo and motion with slanted surfaces. In ICCV.
Bishop, C. M. (2006). Pattern recognition and machine learning. Berlin: Springer.
Boult, T., & Brown, L. G. (1991). Factorization-based segmentation of motions. In IEEE workshop on visual motion.
Boykov, Y., Veksler, O., & Zabih, R. (2001). Fast approximate energy minimization via graph cuts. In PAMI.
Chin, T.-J., Wang, H., & Suter, D. (2009). Robust fitting of multiple structures: the statistical learning approach. In International Conference on Computer Vision (ICCV).
Chin, T.-J., Yu, J., & Suter, D. (2010). Accelerated hypothesis generation for multi-structure robust fitting. In European Conference on Computer Vision (ECCV).
Chum, O., Matas, J., & Kittler, J. (2003). Locally optimized RANSAC. In LNCS: Vol. 2781. Pattern recognition (pp. 236–243).
Comaniciu, D., & Meer, P. (2002). Mean shift: a robust approach toward feature space analysis. In PAMI.
Costeira, J., & Kanade, T. (1995). A multi-body factorization method for motion analysis. In ICCV.
Delong, A., Osokin, A., Isack, H., & Boykov, Y. (2011). Fast approximate energy minization with label costs. International Journal of Computer Vision (accepted). Earlier version is in CVPR 2010. doi:10.1007/s11263-011-0437-z
Faugeras, O., & Luong, Q.-T. (2004). The geometry of multiple images. Cambridge: MIT Press.
Figueiredo, M. A., & Jain, A. K. (2002). Unsupervised learning of finite mixture models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(3), 381–396.
Fischler, M. A., & Bolles, R. C. (1981). Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. In CACM.
Gruber, A., & Weiss, Y. (2006). Incorporating non-motion cues into 3D motion segmentation. In European Conference on Computer Vision (ECCV).
Hartley, R. (1997). In defense of the eight-point algorithm. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(6), 580–593.
Hartley, R., & Zisserman, A. (2003). Multiple view geometry in computer vision. Cambridge: Cambridge University Press.
Isack, H. (2009). Spatially coherent multi-model fitting. MS Thesis, CS Dept., University of Western Ontario, London, Canada.
Leclerc, Y. G. (1989). Constructing simple stable descriptions for image partitioning. International Journal of Computer Vision, 3(1), 73–102.
Li, H. (2007). Two-view motion segmentation from linear programming relaxation. In CVPR.
Lowe, D. G. (2004). Distinctive image features from scale-invariant keypoints. In IJCV.
Ma, Y., Soatto, S., Kosecka, J., & Sastry, S. (2003). An invitation to 3D vision: from images to geometric models. Berlin: Springer.
Muja, M., & Lowe, D. G. (2009). Fast approximate nearest neighbors with automatic algorithm configuration. In VISAPP.
Olsson, C., Enqvist, O., & Kahl, F. (2008). A polynomial-time bound for matching and registration with outliers. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Anchorage, USA.
Rother, C., Kolmogorov, V., & Blake, A. (2004). Grabcut—interactive foreground extraction using iterated graph cuts. In ACM Transactions on Graphics (SIGGRAPH), August 2004.
Schindler, K., & Suter, D. (2006). Two-view multibody structure-and-motion with outliers through model selection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(6), 983–995.
Toldo, R., & Fusiello, A. (2008). Robust multiple structures estimation with J-linkage. In ECCV.
Tomasi, C., & Kanade, T. (1992). Shape and motion from image streams under orthography: a factorization method. In IJCV.
Torr, P., & Zisserman, A. (2000). MLESAC: a new robust estimator with application to estimating image geometry. Journal of Computer Vision and Image Understanding, 78(1), 138–156.
Torr, P. H. S. (1998). Geometric motion segmentation and model selection. Philosophical Transactions of the Royal Society A, 1321–1340.
Torr, P. H. S., & Murray, D. W. (1994). Stochastic motion clustering. In LNCS: Vol. 801. European Conference on Computer Vision (ECCV), Stockholm, Sweden (pp. 328–337).
Tron, R., & Vidal, R. (2007). A benchmark for the comparison of 3-d motion segmentation algorithms. In CVPR.
Vidal, R., Tron, R., & Hartley, R. (2008). Multiframe motion segmentation with missing data using powerfactorization and GPCA. In IJCV.
Vincent, E., & Laganiere, R. (2001). Detecting planar homographies in an image pair. In ISPA, June.
Wills, J., Agarwal, S., & Belongie, S. (2003). What went where. In CVPR03 (pp. 37–44).
Yan, J., & Pollefeys, M. (2006). A general framework for motion segmentation: independent, articulated, rigid, non-rigid, degenerate, and non-degenerate. In European Conference on Computer Vision (ECCV).
Zabih, R., & Kolmogorov, V. (2004). Spatially coherent clustering with graph cuts. In CVPR, June.
Zhu, S. C., & Yuille, A. (1996). Region competition: unifying snakes, region growing, and Bayes/MDL for multiband image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(9), 884–900.
Zrour, R., Kenmochi, Y., Talbot, H., Buzer, L., Hamam, Y., Shimizu, I., & Sugimoto, A. (2011). Optimal consensus set for digital line and plane fitting. International Journal of Imaging Systems and Technology, 21, 45–57.
Zuliani, M., Kenney, C., & Manjunath, B. (2005). The multiransac algorithm and its application to detect planar homographies. In ICIP.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Isack, H., Boykov, Y. Energy-Based Geometric Multi-model Fitting. Int J Comput Vis 97, 123–147 (2012). https://doi.org/10.1007/s11263-011-0474-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11263-011-0474-7