“Out-of-core tensor approximation of multi-dimensional matrices of visual data” by Wang, Wu, Shi, Yu and Ahuja

Tensor approximation is necessary to obtain compact multilinear models for multi-dimensional visual datasets. Traditionally, each multi-dimensional data item is represented as a vector. Such a scheme flattens the data and partially destroys the internal structures established throughout the multiple dimensions. In this paper, we retain the original dimensionality of the data items to more effectively exploit existing spatial redundancy and allow more efficient computation. Since the size of visual datasets can easily exceed the memory capacity of a single machine, we also present an out-of-core algorithm for higher-order tensor approximation. The basic idea is to partition a tensor into smaller blocks and perform tensor-related operations blockwise. We have successfully applied our techniques to three graphics-related data-driven models, including 6D bidirectional texture functions, 7D dynamic BTFs and 4D volume simulation sequences. Experimental results indicate that our techniques can not only process out-of-core data, but also achieve higher compression ratios and quality than previous methods.

1. Brand, M. 2002. Incremental singular value decomposition of uncertain data with missing values. In Proc. European Conference on Computer Vision (Vol. 1), 707–720. Google ScholarDigital Library
2. Chen, W.-C., Bouguet, J.-Y., Chu, M., and Grzeszczuk, R. 2002. Light field mapping: Efficient representation and hardware rendering of surface light fields. ACM Transactions on Graphics 21, 3, 447–456. Google ScholarDigital Library
3. Dana, K. J., van Ginneken, B., Nayar, S. K., and Koenderink, J. J. 1999. Reflectance and texture of real world surfaces. ACM Transactions on Graphics 18, 1, 1–34. Google ScholarDigital Library
4. Enright, D., Marschner, S., and Fedkiw, R. 2002. Animation and rendering of complex water surfaces. ACM Transactions on Graphics 21, 3, 736–744. Google ScholarDigital Library
5. Furukawa, R., Kawasaki, H., Ikeuchi, K., and Sakauchi, M. 2002. Appearance based object modeling using texture database: Acquisition, compression, and rendering. In 13th Eurographics Workshop on Rendering, 257–265. Google ScholarDigital Library
6. Gu, X., Gortler, S., and Hoppe, H. 2002. Geometry images. ACM Transactions on Graphics 21, 3, 355–361. Google ScholarDigital Library
7. Han, J., and Perlin, K. 2003. Measuring bidirectional texture reflectance with a kaleidoscope. ACM Transactions on Graphics 22, 3, 741–748. Google ScholarDigital Library
8. James, D., and Fatahalian, K. 2003. Precomputing interactive dynamic deformable scenes. ACM TOG 22, 3, 879–887. Google ScholarDigital Library
9. Koudelka, M., Magda, S., Belhumeur, P., and Kriegman, D. 2003. Acquisition, compression, and synthesis of bidirectional texture functions. In 3rd Intl. Workshop on Texture Analysis and Synthesis, 59–64.Google Scholar
10. Kroonenberg, P., and de Leeuw, J. 1980. Principal component analysis of three-mode data by means of alternating least squares algorithms. Psychometrika 45, 324–1342.Google ScholarCross Ref
11. Lathauwer, L. D., De Moor, B., and Vandewalle, J. 2000. A multilinear singular value decomposition. SIAM J. Matrix Analysis and Applications 21, 4, 1253–1278. Google ScholarDigital Library
12. Lathauwer, L. D., de Moor, B., and Vandewalle, J. 2000. On the best rank-1 and rank-(R1, R2, .., Rn) approximation of higher-order tensors. SIAM J. Matrix Analysis and Applications 21, 4, 1324–1342. Google ScholarDigital Library
13. Leung, T., and Malik, J. 1999. Recognizing surfaces using three dimensional textons. In Intl. Conf. Computer Vision. Google ScholarDigital Library
14. Levoy, M., and Hanrahan, P. 1996. Light field rendering. In Computer Graphics Proceedings, Annual Conference Series, 31–42. Google ScholarDigital Library
15. Liu, X., Yu, Y., and Shum, H.-Y. 2001. Synthesizing bidirectional texture functions for real-world surfaces. In Proceedings of SIGGRAPH, 97–106. Google ScholarDigital Library
16. Liu, X., Hu, Y., Zhang, J., Tong, X., Guo, B., and Shum, H.-Y. 2004. Synthesis and rendering of bidirectional texture functions on arbitrary surfaces. IEEE Trans. Visualization and Computer Graphics 10, 3, 278–289. Google ScholarDigital Library
17. Matusik, W., Pfister, H., Brand, M., and McMillan, L. 2003. A data-driven reflectance model. ACM Transactions on Graphics 22, 3, 759–769. Google ScholarDigital Library
18. Nguyen, K., and Saupe, D. 2001. Rapid high quality compression of volume data for visualization. Compuer Graphics Forum 20, 3, 49–56.Google ScholarCross Ref
19. Nishino, K., Sato, Y., and Ikeuchi, K. 1999. Eigen-texture method: appearance compression based on 3d model. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR’99), 618–624.Google Scholar
20. Rabani, E., and Toledo, S. 2001. Out-of-core svd and qr decompositions. In Proceedings of the 10th SIAM Conference on Parallel Processing for Scientific Computing.Google Scholar
21. Rodler, F. 1999. Wavelet based 3d compression with fast random access for very large volume data. In Proceedings of the 7th Pacific Conference on Computer Graphics and Applications, 108–117. Google ScholarDigital Library
22. Sattler, M., Sarlette, R., and Klein, R. 2003. Efficient and realistic visualization of cloth. In Proc. Eurographics Symposium on Rendering, 167–177. Google ScholarDigital Library
23. Shashua, A., and Levin, A. 2001. Linear image regression and classification using the tensor-rank principle. In IEEE Conf. Computer Vision and Pattern Recognition.Google Scholar
24. Shi, L., and Yu, Y. 2005. Controllable smoke animation with guiding objects. ACM Transactions on Graphics 24, 1, 140–164. Google ScholarDigital Library
25. Tong, X., Zhang, J., Liu, L., Wang, X., Guo, B., and Shum, H.-Y. 2002. Synthesis of bidirectional texture functions on arbitrary surfaces. In SIGGRAPH 2002 Proceedings, 665–672. Google ScholarDigital Library
26. Tucker, L. 1966. Some mathematical notes on three-mode factor analysis. Psychometrika 31, 279–311.Google ScholarCross Ref
27. Vasilescu, M. A. O., and Terzopoulos, D. 2002. Multilinear analysis of image ensembles: Tensorfaces. In European Conference on Computer Vision, 447–460. Google ScholarDigital Library
28. Vasilescu, M., and Terzopoulos, D. 2004. Tensortextures: Multilinear image-based rendering. ACM Transactions on Graphics 23, 3, 334–340. Google ScholarDigital Library
29. Wang, H., and Ahuja, N. 2003. Facial expression decomposition. In Int. Conf. on Computer Vision, 958–965. Google ScholarDigital Library
30. Weyrich, T., Pfister, H., and Gross, M. 2005. Rendering deformable surface reflectance fields. IEEE Trans. Visualization and Computer Graphics 11, 1, 48–58. Google ScholarDigital Library
31. Yang, J., Zhang, D., Frangi, A., and Yang, J. 2004. Two-dimensional pca: A new approach to appearance-based face representation and recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence 26, 1 (January). Google ScholarDigital Library
32. Ye, J. 2004. Generalized low rank approximations of matrices. In International Conference on Machine Learning, ICML’04. Google ScholarDigital Library
33. Yeo, B.-L., and Liu, B. 1995. Volume rendering of dct-based compressed 3d scalar data. IEEE Trans. Visualization and Computer Graphics 1, 1, 29–43. Google ScholarDigital Library
34. Yu, Y., and Chang, J. 2005. Shadow graphs and 3d texture reconstruction. International Journal of Computer Vision 62, 1/2, 35–60. Google ScholarDigital Library