| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Recovering the Missing Components in a Large Noisy Low-Rank Matrix: Application to SFM
August 2004 (vol. 26 no. 8)
pp. 1051-1063
Abstract—In computer vision, it is common to require operations on matrices with "missing data,” for example, because of occlusion or tracking failures in the Structure from Motion (SFM) problem. Such a problem can be tackled, allowing the recovery of the missing values, if the matrix should be of low rank (when noise free). The filling in of missing values is known as imputation. Imputation can also be applied in the various subspace techniques for face and shape classification, online "recommender” systems, and a wide variety of other applications. However, iterative imputation can lead to the "recovery” of data that is seriously in error. In this paper, we provide a method to recover the most reliable imputation, in terms of deciding when the inclusion of extra rows or columns, containing significant numbers of missing entries, is likely to lead to poor recovery of the missing parts. Although the proposed approach can be equally applied to a wide range of imputation methods, this paper addresses only the SFM problem. The performance of the proposed method is compared with Jacobs' and Shum's methods for SFM.
[1] 1051 P.M.Q. Aguiar and J.M.F. Moura, Rank 1 Weighted Factorization for 3D Structure Recovery: Algorithms and Performance Analysis IEEE Trans Pattern Analysis and Machine Intelligence, vol. 25, no. 9, pp. 1134-1149, Sept. 2003.[2] M. Brand, Incremental Singular Value Decomposition of Uncertain Data with Missing Values Proc. European Conf. Computer Vision, pp. 707-720, 2002.[3] M. Brand, Fast Online SVD Revisions for Lightweight Recommender Systems Proc. SIAM Third Int'l Conf. Data Mining, 2003.[4] S. Brandt, Closed-Form Solutions for Affine Reconstruction under Missing Data Proc. Statistical Methods for Video Processing Workshop, pp. 109-114, 2002.[5] P. Chen and D. Suter, An Analysis of Linear Subspace Approaches for Computer Vision and Pattern Recognition Technical Report MECSE-6-2003, Monash Univ., Clayton 3800, Australia,http://www.ds.eng.monash.edu.au/techrep/ reports/2003MECSE-6-2003.pdf, 2003.[6] F. DelaTorre and M.J. Black, A Framework for Robust Subspace Learning Int'l J. Computer Vision, vol. 54, pp. 117-142, 2003.[7] A. Fitzgibbon, G. Cross, and A. Zisserman, Automatic 3D Model Construction for Turn-Table Sequences, 3D Structure from Multiple Images of Large-Scale Environments Lecture Notes in Computer Science, vol. 1506, pp. 155-170, 1998.[8] G.H. Golub and C.F.V. Loan, Matrix Computations, second ed. Baltimore: Johns Hopkins Univ. Press, 1989.[9] R.F.C. Guerreiro and P.M.Q. Aguiar, Estimation of Rank Deficient Matrices from Partial Observations: Two-Step Iterative Algorithms Proc. Conf. Energy Minimization Methods in Computer Vision and Pattern Recognition, 2003.[10] C.J. Harris and M. Stephens, A Combined Corner and Edge Detector Proc. Alvey Vision Conf., pp. 147-151, 1988.[11] A. Heyden and F. Kahl, Reconstruction from Affine Cameras Using Closure Constraints Proc. Int'l Conf. Pattern Recognition, pp. 47-50, 1998.[12] M. Irani, Multi-Frame Optical Flow Estimation Using Subspace Constraints Proc. Int'l Conf. Computer Vision, 1999.[13] M. Irani, Multi-Frame Correspondence Estimation Using Subspace Constraints Int'l J. Computer Vision, vol. 48, no. 3, pp. 173-194, 2002.[14] D. Jacobs, "Linear Fitting with Missing Data," Proc. IEEE CVPR, 1997.[15] D. Jacobs, Linear Fitting with Missing Data for Structure-from-Motion Computer Vision and Image Understanding, vol. 82, pp. 57-81, 2001.[16] F. Kahl and A. Heyden, Affine Structure and Motion from Points, Lines, and Conics Int'l J. Computer Vision, vol. 33, no. 3, pp. 163-180, 1999.[17] K. Kanatani, Motion Segmentation by Subspace Separation and Model Selection Proc. Int'l Conf. Computer Vision, pp. 301-306, 2001.[18] D. Martinec and T. Pajdla, Structure from Many Perspective Images with Occlusion Proc. European Conf. Computer Vision, pp. 355-369, 2002.[19] T. Morita and T. Kanade, A Sequential Factorization Method for Recovering Shape and Motion from Image Streams IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 19, no. 8, pp. 858-867, Aug. 1997.[20] C. Poelman and T. Kanade, A Paraperspective Factorization Method for Shape and Motion Recovery IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 19, no. 3, pp. 206-219, Mar. 1997.[21] C. Rother and S. Carlsson, Linear Multi View Reconstruction with Missing Data Proc. European Conf. Computer Vision, 2002.[22] B.M. Sarwar et al., Application of Dimensionality Reduction in Recommender System-A Case Study Proc. ACM WebKDD 2000 Web Mining for E-Commerce Workshop, pp. 309-324, 2000.[23] H. Shum, K. Ikeuchi, and R. Reddy, Principal Component Analysis with Missing Data and Its Applications to Polyhedral Object Modeling IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 9, pp. 854-867, Sept. 1995.[24] P. Sturm and B. Triggs, A Factorization Based Algorithm for Multi-Image Projective Structure and Motion Proc. European Conf. Computer Vision, pp. 709-720, 1996.[25] J.I. Thomas and J. Oliensis, Dealing with Noise in Multiframe Structure from Motion Computer Vision and Image Understanding, vol. 76, no. 2, pp. 109-124, 1999.[26] C. Tomasi and T. Kanade, Shape and Motion from Image Streams under Orthography: A Factorization Method Int'l J. Computer Vision, vol. 9, no. 2, pp. 137-154, 1992.[27] O. Troyanskaya et al., Missing Value Estimation Methods for DNA Microarrays Bioinformatics, vol. 17, pp. 520-525, 2001.[28] J.H. Wilkinson, The Algebraic Eigenvalue Problem. Oxford: Clarendon Press, 1965.
Index Terms:
Imputation, missing-data problem, rank constraint, singular value decomposition, denoising capacity, structure from motion, affine SFM, linear subspace.
Citation:
Pei Chen, David Suter, "Recovering the Missing Components in a Large Noisy Low-Rank Matrix: Application to SFM," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 8, pp. 1051-1063, Aug. 2004, doi:10.1109/TPAMI.2004.52
