Abstract
A novel technique for missing data matrix rank estimation is presented. It is focused on matrices of trajectories, where every element of the matrix corresponds to an image coordinate from a feature point of a rigid moving object at a given frame; missing data are represented as empty entries. The objective of the proposed approach is to estimate the rank of a missing data matrix in order to fill in empty entries with some matrix completion method, without using or assuming neither the number of objects contained in the scene nor the kind of their motion. The key point of the proposed technique consists in studying the frequency behaviour of the individual trajectories, which are seen as 1D signals. The main assumption is that due to the rigidity of the moving objects, the frequency content of the trajectories will be similar after filling in their missing entries. The proposed rank estimation approach can be used in different computer vision problems, where the rank of a missing data matrix needs to be estimated. Experimental results with synthetic and real data are provided in order to empirically show the good performance of the proposed approach.
References
Aguiar, P.M.Q., Stosic, M., Xavier, J.: On singular values of partially prescribed matrices. Linear Algebra Appl. 429, 2136–2145 (2008)
Aguiar, P.M.Q., Xavier, J., Stosic, M.: Globally optimal solution to exploit rigidity when recovering structure from motion under occlusions. In: IEEE International Conference on Image Processing (ICIP), pp. 197–200 (2008)
Aguiar, P.M.Q., Xavier, J., Stosic, M.: Spectrally optimal factorization of incomplete matrices. In: IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2008
Akhter, I., Sheikh, Y., Khan, S., Kanade, T.: Nonrigid structure from motion in trajectory space. In: Neural Information Processing Systems, 2008
Broersen, P., Waele, S., Bos, R.: Application of autoregressive spectral analysis to missing data problems. IEEE Trans. Instrum. Meas. 53, 981–986 (2004)
Buchanan, A., Fitzgibbon, A.W.: Damped Newton algorithms for matrix factorization with missing data. In: IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), vol. 2, pp. 316–322 (2005)
Candes, E.J., Recht, B.: Exact low-rank matrix completion via convex optimization. In: Forty-Sixth Annual Allerton Conference, pp. 806–812 (2008)
Chen, P., Suter, D.: Recovering the missing components in a large noisy low-rank matrix: application to SFM. IEEE Trans. Pattern Anal. Mach. Intell. 26, 1051–1063 (2004)
Costeira, J.P., Kanade, T.: A multibody factorization method for independently moving objects. Int. J. Comput. Vis. (IJCV) (3):159–179, 1998
Farid, H., Kosecká, J.: Estimating planar surface orientation using bispectral analysis. IEEE Trans. Image Process. 16, 2154–2160 (2007)
Golub, G.H., Van Loan, C.F. (eds.): Matrix Computations. The Johns Hopkins University Press, Baltimore (1989)
Guerreiro, R.F.C., Aguiar, P.M.Q.: Estimation of rank deficient matrices from partial observations: two-step iterative algorithms. In: Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR), pp. 450–466 (2003)
Haldar, J.P., Hernando, D.: Rank-constrained solutions to linear matrix equations using powerfactorization. IEEE Signal Process. Lett. 16, 584–587 (2009)
Han, M., Kanade, T.: Reconstruction of a scene with multiple linearly moving objects. Int. J. Comput. Vis. (IJCV) 53, 285–300 (2000)
Hartley, R., Schaffalitzky, F.: Powerfactorization: 3D reconstruction with missing or uncertain data. In: Australian-Japan Advanced Workshop on Computer Vision, 2003
Hayakawa, H.: Photometric stereo under a light source with arbitrary motion. Opt. Soc. Am. 11, 3079–3089 (1994)
Irani, M.: Multi-frame optical flow estimation using subspace constraints. In: ICCV, vol. 1, pp. 626–633 (1999)
Jacobs, D.W.: Linear fitting with missing data for structure-from-motion. Comput. Vis. Image Underst. (CVIU) 1, 57–81 (2001)
Jia, H., Fortuna, J., Martinez, A.: Perturbation estimation of the subspaces for structure from motion with noisy and missing data. In: Third International Symposium on 3D Data Processing, Visualization, and Transmission, pp. 1101–1007 (2006)
Julià, C., Sappa, A.D., Lumbreras, F., Serrat, J., López, A.: Rank estimation in 3d multibody motion segmentation. Electron. Lett. 44, 279–280 (2008)
Kanatani, K.: Statistical optimization and geometric inference in computer vision. Philos. Trans., Math. Phys. Eng. Sci. 356, 1303–1320 (1998)
Kanatani, K.: Motion segmentation by subspace separation and model selection. In: IEEE Computer Vision and Pattern Recognition (CVPR), vol. 2, pp. 586–591 (2001)
Ma, Y., Soatto, J., Kosecká, J., Sastry, S.: An Invitation to 3D Vision: From Images to Geometric Models. Springer, New York (2004)
Myrtveit, I., Stensrud, E., Olsson, U.: Analyzing data sets with missing data: an empirical evaluation of imputation methods and likelihood-based methods. IEEE Trans. Softw. Eng. 27, 999–1013 (2001)
Okatani, T., Deguchi, K.: On the Wiberg algorithm for matrix factorization in the presence of missing components. Int. J. Comput. Vis. 72, 329–337 (2007)
Poelman, C.J., Kanade, T.: A paraperspective factorization method for shape and motion recovery. IEEE Trans. Pattern Anal. Mach. Intell. 19, 206–218 (1997)
Sarwar, M.S., Karypis, G., Konstan, J.A., Riedl, J.T.: Application of dimensionality reduction in recommender system—a case study. In: E-Commerce Workshop, pp. 309–324 (2000)
Thrun, S.: Affine structure from sound. In: Weiss, Y., Schölkopf, B., Platt, J. (eds.) Advances in Neural Information Processing Systems, vol. 18, pp. 1353–1360. MIT Press, Cambridge (2006)
Tomasi, C., Kanade, T.: Shape and motion from image streams under orthography: a factorization method. Int. J. Comput. Vis. 9(2), 137–154 (1992)
Tron, R., Vidal, R.: A benchmark for the comparison of 3D motion segmentation algorithms. In: IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), 2007
Troyanskaya, O., Cantor, M., Sherlock, G., Brown, P., Hastie, T., Tibshirani, R., Botstein, D., Altman, R.B.: Missing value estimation methods for DNA microarrays. Bioinformatics 17, 1–6 (2001)
Vidal, R., Hartley, R.: Motion segmentation with missing data using powerfactorization and GPCA. In: IEEE Computer Vision and Pattern Recognition (CVPR), vol. 2, pp. 310–316 (2004)
Vidal, R., Ma, Y.: A unified algebraic approach to 2-D and 3-D motion segmentation and estimation. J. Math. Imaging Vis. 25, 403–421 (2006)
Vidal, R., Tron, R., Hartley, R.: Multiframe motion segmentation with missing data using powerfactorization and GPCA. Int. J. Comput. Vis. 78, 85–105 (2008)
Wiberg, T.: Computation of principal components when data is missing. In: Second Symposium of Computational Statistics, pp. 229–326 (1976)
Yan, J., Pollefeys, M.: A general framework for motion segmentation: independent, articulated, rigid, non-rigid, degenerate and non-degenerate. In: European Conference on Computer Vision (ECCV), pp. 94–106 (2006)
Zelnik-Manor, L., Irani, M.: Degeneracies, dependencies and their implications in multi-body and multi-sequence factorization. In: IEEE Computer Vision and Pattern Recognition (CVPR), vol. 2, pp. 287–293 (2003)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Julià, C., Sappa, A.D., Lumbreras, F. et al. Rank Estimation in Missing Data Matrix Problems. J Math Imaging Vis 39, 140–160 (2011). https://doi.org/10.1007/s10851-010-0229-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10851-010-0229-z