Skip to main content
Log in

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

References

  1. Aguiar, P.M.Q., Stosic, M., Xavier, J.: On singular values of partially prescribed matrices. Linear Algebra Appl. 429, 2136–2145 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  2. 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)

    Google Scholar 

  3. 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

  4. Akhter, I., Sheikh, Y., Khan, S., Kanade, T.: Nonrigid structure from motion in trajectory space. In: Neural Information Processing Systems, 2008

  5. Broersen, P., Waele, S., Bos, R.: Application of autoregressive spectral analysis to missing data problems. IEEE Trans. Instrum. Meas. 53, 981–986 (2004)

    Article  Google Scholar 

  6. 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)

    Chapter  Google Scholar 

  7. Candes, E.J., Recht, B.: Exact low-rank matrix completion via convex optimization. In: Forty-Sixth Annual Allerton Conference, pp. 806–812 (2008)

    Chapter  Google Scholar 

  8. 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)

    Article  Google Scholar 

  9. Costeira, J.P., Kanade, T.: A multibody factorization method for independently moving objects. Int. J. Comput. Vis. (IJCV) (3):159–179, 1998

  10. Farid, H., Kosecká, J.: Estimating planar surface orientation using bispectral analysis. IEEE Trans. Image Process. 16, 2154–2160 (2007)

    Article  MathSciNet  Google Scholar 

  11. Golub, G.H., Van Loan, C.F. (eds.): Matrix Computations. The Johns Hopkins University Press, Baltimore (1989)

    MATH  Google Scholar 

  12. 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)

    Chapter  Google Scholar 

  13. Haldar, J.P., Hernando, D.: Rank-constrained solutions to linear matrix equations using powerfactorization. IEEE Signal Process. Lett. 16, 584–587 (2009)

    Article  Google Scholar 

  14. Han, M., Kanade, T.: Reconstruction of a scene with multiple linearly moving objects. Int. J. Comput. Vis. (IJCV) 53, 285–300 (2000)

    Google Scholar 

  15. Hartley, R., Schaffalitzky, F.: Powerfactorization: 3D reconstruction with missing or uncertain data. In: Australian-Japan Advanced Workshop on Computer Vision, 2003

  16. Hayakawa, H.: Photometric stereo under a light source with arbitrary motion. Opt. Soc. Am. 11, 3079–3089 (1994)

    Article  Google Scholar 

  17. Irani, M.: Multi-frame optical flow estimation using subspace constraints. In: ICCV, vol. 1, pp. 626–633 (1999)

    Google Scholar 

  18. Jacobs, D.W.: Linear fitting with missing data for structure-from-motion. Comput. Vis. Image Underst. (CVIU) 1, 57–81 (2001)

    Article  Google Scholar 

  19. 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)

    Chapter  Google Scholar 

  20. 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)

    Article  Google Scholar 

  21. Kanatani, K.: Statistical optimization and geometric inference in computer vision. Philos. Trans., Math. Phys. Eng. Sci. 356, 1303–1320 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  22. Kanatani, K.: Motion segmentation by subspace separation and model selection. In: IEEE Computer Vision and Pattern Recognition (CVPR), vol. 2, pp. 586–591 (2001)

    Google Scholar 

  23. Ma, Y., Soatto, J., Kosecká, J., Sastry, S.: An Invitation to 3D Vision: From Images to Geometric Models. Springer, New York (2004)

    Google Scholar 

  24. 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)

    Article  Google Scholar 

  25. 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)

    Article  Google Scholar 

  26. Poelman, C.J., Kanade, T.: A paraperspective factorization method for shape and motion recovery. IEEE Trans. Pattern Anal. Mach. Intell. 19, 206–218 (1997)

    Article  Google Scholar 

  27. 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)

    Google Scholar 

  28. 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)

    Google Scholar 

  29. Tomasi, C., Kanade, T.: Shape and motion from image streams under orthography: a factorization method. Int. J. Comput. Vis. 9(2), 137–154 (1992)

    Article  Google Scholar 

  30. 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

  31. 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)

    Article  Google Scholar 

  32. 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)

    Google Scholar 

  33. 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)

    Article  MathSciNet  Google Scholar 

  34. Vidal, R., Tron, R., Hartley, R.: Multiframe motion segmentation with missing data using powerfactorization and GPCA. Int. J. Comput. Vis. 78, 85–105 (2008)

    Article  Google Scholar 

  35. Wiberg, T.: Computation of principal components when data is missing. In: Second Symposium of Computational Statistics, pp. 229–326 (1976)

    Google Scholar 

  36. 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)

    Google Scholar 

  37. 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)

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Carme Julià.

Rights and permissions

Reprints 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

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10851-010-0229-z

Keywords

Navigation