Abstract
We investigate the problem of finding the correspondence from multiple images, which is a challenging combinatorial problem. In this work, we propose a robust solution by exploiting the priors that the rank of the ordered patterns from a set of linearly correlated images should be lower than that of the disordered patterns, and the errors among the reordered patterns are sparse. This problem is equivalent to find a set of optimal partial permutation matrices for the disordered patterns such that the rearranged patterns can be factorized as a sum of a low rank matrix and a sparse error matrix. A scalable algorithm is proposed to approximate the solution by solving two sub-problems sequentially: minimization of the sum of nuclear norm and l 1 norm for solving relaxed partial permutation matrices, followed by a binary integer programming to project each relaxed partial permutation matrix to the feasible solution. We verify the efficacy and robustness of the proposed method with extensive experiments with both images and videos.
Chapter PDF
Similar content being viewed by others
References
Berg, A.C., Berg, T.L., Malik, J.: Shape matching and object recognition using low distortion correspondences. In: CVPR (2005)
Pollefeys, M., et al.: Detailed real-time urban 3d reconstruction from video. IJCV 78, 143–167 (2008)
Enqvist, O., Josephson, K., Kahl, F.: Optimal correspondences from pairwise constraints. In: ICCV (2009)
Caetano, T.S., Caelli, T., Schuurmans, D., Barone, D.A.C.: Graphical models and point pattern matching. TPAMI 28, 1646–1663 (2006)
Maciel, J., Costeira, J.P.: A global solution to sparse correspondence problems. TPAMI 25, 187–199 (2003)
Kolmogorov, V., Zabih, R.: Computing visual correspondence with occlusion via graph cuts. In: ICCV (2001)
Liu, H., Yan, S.: Common visual pattern discovery via spatially coherent correspondences. In: CVPR (2010)
Torresesani, L., Kolmogorov, V., Rother, C.: Feature Correspondence Via Graph Matching: Models and Global Optimization. In: Forsyth, D., Torr, P., Zisserman, A. (eds.) ECCV 2008, Part II. LNCS, vol. 5303, pp. 596–609. Springer, Heidelberg (2008)
Caetano, T.S., McAuley, J., Cheng, L., Le, Q.V., Smola, A.J.: Learning graph matching. TPAMI 31, 1048–1058 (2009)
Li, H.S., Huang, J.Z., Zhang, S.T., Huang, X.L.: Optimal object matching via convexification and composition. In: ICCV (2011)
Jiang, H., Tian, T.P., Sclaroff, S.: Scale and rotation invariant matching using linearly augmented trees. In: CVPR (2011)
Jiang, H., Drew, M.S., Li, Z.N.: Matching by linear programming and successive convexification. TPAMI 29, 959–975 (2007)
Cho, M., Lee, J., Lee, K.: Feature correspondence and deformable object matching via agglomerative correspondence clustering. In: ICCV (2009)
Barnes, C., Shechtman, E., Goldman, D.B., Finkelstein, A.: The Generalized PatchMatch Correspondence Algorithm. In: Daniilidis, K., Maragos, P., Paragios, N. (eds.) ECCV 2010, Part III. LNCS, vol. 6313, pp. 29–43. Springer, Heidelberg (2010)
Oliveira, R., Costeira, J., Xavier, J.: Optimal point correspondence throught the use of rank constraints. In: CVPR (2005)
Torki, M., Elgammal, A.: One-shot multi-set non-rigid feature-spatial matching. In: CVPR (2010)
Poelman, C.J., Kanade, T.: A paraperspective factorization method for shape and motion recovery. In: ECCV (1994)
Tomasi, C., Kanade, T.: Shape from motion from image streams under orthography: A factorization method. IJCV 9, 137–154 (1992)
Candes, E., Li, X., Ma, Y., Wright, J.: Robust principle component analysis? Journal of ACM 58, 1–37 (2009)
Peng, Y.G., Ganesh, A.: Rasl: Robust alignment by sparse and low-rank decomposition for linearly correlated images. In: CVPR (2010)
Lin, Z.C., Chen, M.M., Ma, Y.: The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices. UIUC technical report UILU-ENG-09-2215 (2009)
Toh, K.C., Yun, S.W.: An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems. Pacific Journal of Optimization, 615–640 (2010)
Boyd, S., Parikh, N., Chu, E., Peleato, B., Ecjstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning 3, 1–22 (2010)
Wolf, L., Hassne, T., Maoz, I.: Face recognition in unconstrained videos with matched background similarity. In: CVPR (2011)
Everingham, M., Sivic, J., Zisserman, A.: “who are you?” - learning person specific classifiers from video. In: BMVC (2006)
Lowe, D.G.: Distinctive image features from scale-invariant keypoints. IJCV 60, 91–110 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zeng, Z., Chan, TH., Jia, K., Xu, D. (2012). Finding Correspondence from Multiple Images via Sparse and Low-Rank Decomposition. In: Fitzgibbon, A., Lazebnik, S., Perona, P., Sato, Y., Schmid, C. (eds) Computer Vision – ECCV 2012. ECCV 2012. Lecture Notes in Computer Science, vol 7576. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33715-4_24
Download citation
DOI: https://doi.org/10.1007/978-3-642-33715-4_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33714-7
Online ISBN: 978-3-642-33715-4
eBook Packages: Computer ScienceComputer Science (R0)