“K-Clustered Tensor Approximation: A Sparse Multi-Linear Model for Real-Time Rendering” by Tsai and Shih

With the increasing demands for photo-realistic image synthesis in real time, we propose a sparse multilinear model, which is named K-Clustered Tensor Approximation (K-CTA), to efficiently analyze and approximate large-scale multidimensional visual datasets, so that both storage space and rendering time are substantially reduced. K-CTA not only extends previous work on Clustered Tensor Approximation (CTA) to exploit inter-cluster coherence, but also allows a compact and sparse representation for high-dimensional datasets with just a few low-order factors and reduced multidimensional cluster core tensors. Thus, K-CTA can be regarded as a sparse extension of CTA and a multilinear generalization of sparse representation. Experimental results demonstrate that K-CTA can accurately approximate spatially varying visual datasets, such as bidirectional texture functions, view-dependent occlusion texture functions, and biscale radiance transfer functions for efficient rendering in real-time applications.

Aharon, M., Elad, M., and Bruckstein, A. M. 2006. K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation. IEEE Trans. Signal Process. 54, 11, 4311–4322. Google ScholarDigital Library
Chen, S. S., Donoho, D. L., and Saunders, M. A. 2001. Atomic decomposition by basis pursuit. SIAM Rev. 43, 1, 129–159. Google ScholarDigital Library
Chen, Y., Tong, X., Wang, J., Lin, S., Guo, B., and Shum, H.-Y. 2004. Shell texture functions. ACM Trans. Graph. 23, 3, 343–353. Google ScholarDigital Library
Cohen-Steiner, D., Alliez, P., and Desbrun, M. 2004. Variational shape approximation. ACM Trans. Graph. 23, 3, 905–914. Google ScholarDigital Library
Dana, K. J., Van Ginneken, B., Nayar, S. K., and Koenderink, J. J. 1999. Reflectance and texture of real-world surfaces. ACM Trans. Graph. 18, 1, 1–34. Google ScholarDigital Library
Danielsson, P.-E. 1980. Euclidean distance mapping. Comput. Graph. Image Process. 14, 227–248.Google ScholarCross Ref
Davis, G. M., Mallat, S. G., and Avellaneda, M. 1997. Adaptive greedy approximations. Constr. Approx. 13, 1, 57–98.Google ScholarCross Ref
De Lathauwer, L., 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 Anal. Appl. 21, 4, 1324–1342. Google ScholarDigital Library
Elad, M., Figueiredo, M. A. T., and Ma, Y. 2010. On the role of sparse and redundant representations in image processing. Proc. IEEE 98, 6, 972–982.Google ScholarCross Ref
Filip, J. and Haindl, M. 2009. Bidirectional texture function modeling: A state of the art survey. IEEE Trans. Pattern Anal. Mach. Intell. 31, 11, 1921–1940. Google ScholarDigital Library
Heidrich, W., Daubert, K., Kautz, J., and Seidel, H.-P. 2000. Illuminating micro geometry based on precomputed visibility. In Proceedings of SIGGRAPH’00 Conference. 455–464. Google ScholarDigital Library
Heidrich, W. and Seidel, H.-P. 1999. Realistic, Hardware-Accelerated Shading and Lighting. In Proceedings of SIGGRAPH ’99 Conference. 171–178. Google ScholarDigital Library
Jolliffe, I. T. 2002. Principal Component Analysis 2nd Ed. Springer.Google Scholar
Kambhatla, N. and Leen, T. K. 1997. Dimension reduction by local principal component analysis. Neural Comput. 9, 7, 1493–1516. Google ScholarDigital Library
Kolda, T. G. and Bader, B. W. 2009. Tensor decompositions and applications. SIAM Rev. 51, 3, 455–500. Google ScholarDigital Library
Koudelka, M. L., Magda, S., Belhumeur, P. N., and Kriegman, D. J. 2003. Acquisition, compression, and synthesis of bidirectional texture functions. In Proceedings of the Texture ’03 Conference. 59–64.Google Scholar
Kreutz-Delgado, K., Murray, J. F., Rao, B. D., Engan, K., Lee, T.-W., and Sejnowski, T. J. 2003. Dictionary learning algorithms for sparse representation. Neural Comput. 15, 2, 349–396. Google ScholarDigital Library
Lawrence, J., Ben-Artzi, A., DeCoro, C., Matusik, W., Pfister, H., Ramamoorthi, R., and Rusinkiewicz, S. 2006. Inverse shade trees for non-parametric material representation and editing. ACM Trans. Graph. 25, 3, 735–745. Google ScholarDigital Library
Lefebvre, S. and Hoppe, H. 2006. Appearance-Space texture synthesis. ACM Trans. Graph. 25, 3, 541–548. Google ScholarDigital Library
Mallat, S. G. and Zhang, Z. 1993. Matching pursuits with time-frequency dictionaries. IEEE Trans. Signal Process. 41, 12, 3397–3415. Google ScholarDigital Library
Matusik, W., Pfister, H., Brand, M., and McMillan, L. 2003. A data-driven reflectance model. ACM Trans. Graph. 22, 3, 759–769. Google ScholarDigital Library
McAllister, D. K., Lastra, A., and Heidrich, W. 2002. Efficient rendering of spatial bi-directional reflectance distribution functions. In Proceedings of Graphics Hardware ’02 Conference. 79–88. Google ScholarDigital Library
Müller, G., Meseth, J., and Klein, R. 2003. Compression and real-time rendering of measured BTFs using local PCA. In Proceedings of the VMV ’03 Conference. 271–279.Google Scholar
Müller, G., Meseth, J., and Klein, R. 2004. Fast environmental lighting for local-PCA encoded BTFs. In Proceedings of the CGI ’04 Conference. 198–205. Google ScholarDigital Library
Nayar, S. K., Belhumeur, P. N., and Boult, T. E. 2004. Lighting sensitive display. ACM Trans. Graph. 23, 4, 963–979. Google ScholarDigital Library
Patanè, G. and Russo, M. F. 2001. The enhanced LBG algorithm. Neural Netw. 14, 9, 1219–1237. Google ScholarDigital Library
Policarpo, F., Oliveira, M. M., and Comba, J. L. D. 2005. Real-Time relief mapping on arbitrary polygonal surfaces. In Proceedings of the I3D’05 Conference. 155–162. Google ScholarDigital Library
Qin, Z., McCool, M. D., and Kaplan, C. S. 2006. Real-Time texture-mapped vector glyphs. In Proceedings of the I3D’06 Conference. 125–132. Google ScholarDigital Library
Rebollo-Neira, L. and Lowe, D. 2002. Optimized orthogonal matching pursuit approach. IEEE Signal Process. Lett. 9, 4, 137–140.Google ScholarCross Ref
Roweis, S. T. and Saul, L. K. 2000. Nonlinear dimensionality reduction by locally linear embedding. Sci. 290, 5500, 2323–2326.Google Scholar
Ruiters, R. and Klein, R. 2009. BTF compression via sparse tensor decomposition. Comput. Graph. Forum 28, 4, 1181–1188. Google ScholarDigital Library
Sattler, M., Sarlette, R., and Klein, R. 2003. Efficient and realistic visualization of cloth. In Proceedings of the EGSR’03 Conference. 167–178. Google ScholarDigital Library
Schölkopf, B., Smola, A. J., and Müller, K.-R. 1998. Nonlinear component analysis as a kernel eigenvalue problem. Neural Comput. 10, 5, 1299–1319. Google ScholarDigital Library
Sloan, P.-P. J., Hall, J., Hart, J. C., and Snyder, J. 2003a. Clustered principal components for precomputed radiance transfer. ACM Trans. Graph. 22, 3, 382–391. Google ScholarDigital Library
Sloan, P.-P. J., Kautz, J., and Snyder, J. 2002. Precomputed radiance transfer for real-time rendering in dynamic, low-frequency lighting environments. ACM Trans. Graph. 21, 3, 527–536. Google ScholarDigital Library
Sloan, P.-P. J., Liu, X., Shum, H.-Y., and Snyder, J. 2003b. Bi-Scale radiance transfer. ACM Trans. Graph. 22, 3, 370–375. Google ScholarDigital Library
Smilde, A., Bro, R., and Geladi, P. 2004. Multi-Way Analysis: Applications in the Chemical Sciences. Wiley Press.Google Scholar
Stanford Computer Graphics Laboratory. 2011. The Stanford 3D scanning repository. http://graphics.stanford.edu/data/3Dscanrep/.Google Scholar
Sun, X., Hou, Q., Ren, Z., Zhou, K., and Guo, B. 2011. Radiance transfer biclustering for real-time all-frequency biscale rendering. IEEE Trans. Vis. Comput. Graph. 17, 1, 64–73. Google ScholarDigital Library
Sun, X., Zhou, K., Chen, Y., Lin, S., Shi, J., and Guo, B. 2007. Interactive relighting with dynamic BRDFs. ACM Trans. Graph. 26, 3. Google ScholarDigital Library
Suykens, F., vom Berge, K., Lagae, A., and Dutré, P. 2003. Interactive rendering with bidirectional texture functions. Comput. Graph. Forum 22, 3, 463–472.Google ScholarCross Ref
Tenenbaum, J. B., De Silva, V., and Langford, J. C. 2000. A global geometric framework for nonlinear dimensionality reduction. Sci. 290, 5500, 2319–2323.Google Scholar
Tsai, Y.-T. 2009. Parametric representations and tensor approximation algorithms for real-time data-driven rendering. Ph.D. thesis, National Chiao Tung University.Google Scholar
Tsai, Y.-T., Fang, K.-L., Lin, W.-C., and Shih, Z.-C. 2011. Modeling bidirectional texture functions with multivariate spherical radial basis functions. IEEE Trans. Pattern Anal. Mach. Intell. 33, 7, 1356–1369. Google ScholarDigital Library
Tsai, Y.-T. and Shih, Z.-C. 2006. All-Frequency precomputed radiance transfer using spherical radial basis functions and clustered tensor approximation. ACM Trans. Graph. 25, 3, 967–976. Google ScholarDigital Library
Vasilescu, M. A. O. and Terzopoulos, D. 2003. Multilinear subspace analysis of image ensembles. In Proceedings of the Computer Vision and Pattern Recognition Conference (CVPR’03). 93–99. Google ScholarDigital Library
Vasilescu, M. A. O. and Terzopoulos, D. 2004. TensorTextures: Multilinear image-based rendering. ACM Trans. Graph. 23, 3, 336–342. Google ScholarDigital Library
Vlasic, D., Brand, M., Pfister, H., and Popović, J. 2005. Face transfer with multilinear models. ACM Trans. Graph. 24, 3, 426–433. Google ScholarDigital Library
Wang, H., Wu, Q., Shi, L., Yu, Y., and Ahuja, N. 2005. Out-of-Core tensor approximation of multi-dimensional matrices of visual data. ACM Trans. Graph. 24, 3, 527–535. Google ScholarDigital Library
Wang, L., Wang, X., Tong, X., Lin, S., Hu, S.-M., Guo, B., and Shum, H.-Y. 2003. View-Dependent displacement mapping. ACM Trans. Graph. 22, 3, 334–339. Google ScholarDigital Library
Wright, J., Ma, Y., Mairal, J., Spairo, G. R., Huang, T. S., and Yan, S. 2010. Sparse representation for computer vision and pattern recognition. Proc. IEEE 98, 6, 1031–1044.Google ScholarCross Ref
Wu, Q., Xia, T., Chen, C., Lin, H.-Y. S., Wang, H., and Yu, Y. 2008. Hierarchical tensor approximation of multi-dimensional visual data. IEEE Trans. Vis. Comput. Graph. 14, 1, 186–199. Google ScholarDigital Library
Xu, K., Jia, Y.-T., Fu, H., Hu, S.-M., and Tai, C.-L. 2008. Spherical piecewise constant basis functions for all-frequency precomputed radiance transfer. IEEE Trans. Vis. Comput. Graph. 14, 2, 454–467. Google ScholarDigital Library