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

  • ©Yu-Ting Tsai and Zen-Chung Shih




    K-Clustered Tensor Approximation: A Sparse Multi-Linear Model for Real-Time Rendering



    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

ACM Digital Library Publication:

Overview Page: