Multiway K-Clustered Tensor Approximation: Toward High-Performance Photorealistic Data-Driven Rendering

Abstract

This article presents a generalized sparse multilinear model, namely multiway K-clustered tensor approximation (MK-CTA), for synthesizing photorealistic 3D images from large-scale multidimensional visual datasets. MK-CTA extends previous tensor approximation algorithms, particularly K-clustered tensor approximation (K-CTA) [Tsai and Shih 2012], to partition a multidimensional dataset along more than one dimension into overlapped clusters. On the contrary, K-CTA only sparsely clusters a dataset along just one dimension and often fails to efficiently approximate other unclustered dimensions. By generalizing K-CTA with multiway sparse clustering, MK-CTA can be regarded as a novel sparse tensor-based model that simultaneously exploits the intra- and inter-cluster coherence among different dimensions of an input dataset. Our experiments demonstrate that MK-CTA can accurately and compactly represent various multidimensional datasets with complex and sharp visual features, including bidirectional texture functions (BTFs) [Dana et al. 1999], time-varying light fields (TVLFs) [Bando et al. 2013], and time-varying volume data (TVVD) [Wang et al. 2010], while easily achieving high rendering rates in practical graphics applications.

References

1. Michal Aharon, Michael Elad, and Alfred M. Bruckstein. 2006. K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation. IEEE Trans. Signal Process. 54, 11, 4311--4322.
2. Haim Avron, Andrei Sharf, Chen Greif, and Daniel Cohen-Or. 2010. l₁-sparse reconstruction of sharp point set surfaces. ACM Trans. Graph. 29, 5.
3. Marcos Balsa Rodríguez, Enrico Gobbetti, José Antonio Iglesias Guitián, Maxim Makhinya, Fabio Marton, Renato B. Pajarola, and Susanne K. Suter. 2014. State-of-the-art in compressed GPU-based direct volume rendering. Comput. Graph. Forum 33, 6, 77--100.
4. Yosuke Bando, Henry Holtzman, and Ramesh Raskar. 2013. Near-invariant blur for depth and 2D motion via time-varying light field analysis. ACM Trans. Graph. 32, 2.
5. Arindam Banerjee, Sugato Basu, and Srujana Merugu. 2007. Multiway clustering on relation graphs. In Proceedings of the 7^th SIAM International Conference on Data Mining (SDM'07). 145--156.
6. Ron Bekkerman, Ran El-Yaniv, and Andrew Kachites McCallum. 2005. Multiway distributional clustering via pairwise interactions. In Proceedings of the 22^nd International Conference on Machine Learning (ICML'05). 41--48.
7. Thomas Blumensath and Mike E. Davies. 2007. On the difference between orthogonal matching pursuit and orthogonal least squares. http://eprints.soton.ac.uk/142469/1/BDOMPvsOLS07.pdf.
8. Kristin J. Dana, Bram Van Ginneken, Shree Kumar Nayar, and Jan J. Koenderink. 1999. Reflectance and texture of real-world surfaces. ACM Trans. Graph. 18, 1, 1--34.
9. Geoffrey M. Davis, Stéphane Georges Mallat, and Marco Avellaneda. 1997. Adaptive greedy approximations. Construct. Approx. 13, 1, 57--98.
10. Lieven De Lathauwer, Bart De Moor, and Joos Vandewalle. 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.
11. Paul Ernest Debevec. 1998. Rendering synthetic objects into real scenes: Bridging traditional and image-based graphics with global illumination and high dynamic range photography. In Proceedings of the 25^th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH'98). 189--198.
12. Michael Elad, Mário A. T. Figueiredo, and Yi Ma. 2010. On the role of sparse and redundant representations in image processing. Proc. IEEE 98, 6, 972--982.
13. Klaus Jürgen Engel, Martin Kraus, and Thomas Ertl. 2001. High-quality pre-integrated volume rendering using hardware-accelerated pixel shading. In Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Workshop on Graphics Hardware (HWWS'01). 9--16.
14. Jiří Filip and Michal Haindl. 2009. Bidirectional texture function modeling: A state of the art survey. IEEE Trans. Pattern Anal. Mach. Intell. 31, 11, 1921--1940.
15. Nathaniel Richard Fout and Kwan-Liu Ma. 2007. Transform coding for hardware-accelerated volume rendering. IEEE Trans. Vis. Comput. Graph. 13, 6, 1600--1607.
16. Enrico Gobbetti, José Antonio Iglesias Guitián, and Fabio Marton. 2012. COVRA: A compression-domain output-sensitive volume rendering architecture based on a sparse representation of voxel blocks. Comput. Graph. Forum 31, 3, 1315--1324.
17. Steven J. Gortler, Radek Grzeszczuk, Richard Szeliski, and Michael F. Cohen. 1996. The lumigraph. In Proceedings of the 23^rd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH'96). 43--54.
18. Stefan Guthe and Wolfgang Straßser. 2001. Real-time decompression and visualization of animated volume data. In Proceedings of the Conference on Visualization (VIS'01). 349--356.
19. Milos Hašan, Edgar Velázquez-Armendáriz, Fabio Pellacini, and Kavita Bala. 2008. Tensor clustering for rendering many-light animations. Comput. Graph. Forum 27, 4, 1105--1114.
20. Vlastimil Havran, Jiří Filip, and Karol Myszkowski. 2010. Bidirectional texture function compression based on multi-level vector quantization. Comput. Graph. Forum 29, 1, 175--190.
21. Tamara G. Kolda and Brett W. Bader. 2009. Tensor decompositions and applications. SIAM Rev. 51, 3, 455--500.
22. Melissa Linae Koudelka, Sebastian Magda, Peter Neil Belhumeur, and David Jay Kriegman. 2003. Acquisition, compression, and synthesis of bidirectional texture functions. In Proceedings of the 3^rd International Workshop on Texture Analysis and Synthesis (Texture'03). 59--64.
23. Jens Krüger and Rudiger Westermann. 2003. Acceleration techniques for gpu-based volume rendering. In Proceedings of the IEEE Conference on Visualization (VIS'03). 287--292.
24. Marc Levoy. 2006. Light fields and computational imaging. IEEE Comput. 39, 8, 46--55.
25. Marc Levoy and Pat Hanrahan. 1996. Light field rendering. In Proceedings of the 23^rd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH'96). 31--42.
26. Eric Brian Lum, Kwan-Liu Ma, and John Clyne. 2002. A hardware-assisted scalable solution for interactive volume rendering of time-varying data. IEEE Trans. Vis. Comput. Graph. 8, 3, 286--301.
27. Pieter Peers, Dhruv Mahajan, Bruce Lamond, Abhijeet Ghosh, Wojciech Matusik, Ravi Ramamoorthi, and Paul Ernest Debevec. 2009. Compressive light transport sensing. ACM Trans. Graph. 28, 1.
28. Ravi Ramamoorthi. 2009. Precomputation-based rendering. Foundat. Trends Comput. Graph. Vis. 3, 4, 281--369.
29. Roland Ruiters and Reinhard Klein. 2009. BTF compression via sparse tensor decomposition. Comput. Graph. Forum 28, 4, 1181--1188.
30. Jens Schneider and Rüdiger Westermann. 2003. Compression domain volume rendering. In Proceedings of the IEEE Conference on Visualization (VIS'03). 293--300.
31. Pradeep Sen and Soheil Darabi. 2011. Compressive rendering: A rendering application of compressed sensing. IEEE Trans. Vis. Comput. Graph. 17, 4, 487--499.
32. Amnon Shashua, Ron Zass, and Tamir Hazan. 2006. Multiway clustering using super-symmetric non-negative tensor factorization. In Proceedings of the 9^th European Conference on Computer Vision (ECCV'06). 595--608.
33. Heung-Yeung Shum, Shing-Chow Chan, and Sing Bing Kang. 2007. Image Based Rendering. Springer.
34. Charles Soussen, Rémi Gribonval, Jérôme Idier, and Cédric Herzet. 2013. Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares. IEEE Trans. Inf. Theory 59, 5, 3158--3174.
35. Jean-Luc Starck and Jérôme Bobin. 2010. Astronomical data analysis and sparsity: From wavelets to compressed sensing. Proc. IEEE 98, 6, 1021--1030.
36. Xin Sun, Qiming Hou, Zhong Ren, Kun Zhou, and Baining Guo. 2011. Radiance transfer biclustering for real-time all-frequency bi-scale rendering. IEEE Trans. Vis. Comput. Graph. 17, 1, 64--73.
37. Xin Sun, Kun Zhou, Yanyun Chen, Stephen Lin, Jiaoying Shi, and Baining Guo. 2007. Interactive relighting with dynamic BRDFs. ACM Trans. Graph. 26, 3.
38. Susanne K. Suter, José Antonio Iglesias Guitián, Fabio Marton, Marco Agus, Andreas Elsener, Christoph P. E. Zollikofer, Meenakshisundaram Gopi, Enrico Gobbetti, and Renato B. Pajarola. 2011. Interactive multiscale tensor reconstruction for multiresolution volume visualization. IEEE Trans. Vis. Comput. Graph. 17, 12, 2135--2143.
39. Susanne K. Suter, Maxim Makhynia, and Renato B. Pajarola. 2013. TAM-RESH -tensor approximation multiresolution hierarchy for interactive volume visualization. Comput. Graph. Forum 32, 3, 151--160.
40. Yu-Ting Tsai, Kuei-Li Fang, Wen-Chieh Lin, and Zen-Chung Shih. 2011. Modeling bidirectional texture functions with multivariate spherical radial basis functions. IEEE Trans. Pattern Anal. Mach. Intell. 33, 7, 1356--1369.
41. Yu-Ting Tsai and Zen-Chung Shih. 2006. All-frequency precomputed radiance transfer using spherical radial basis functions and clustered tensor approximation. ACM Trans. Graph. 25, 3, 967--976.
42. Yu-Ting Tsai and Zen-Chung Shih. 2012. K-clustered tensor approximation: A sparse multilinear model for real-time rendering. ACM Trans. Graph. 31, 3.
43. M. Alex O. Vasilescu and Demetri Terzopoulos. 2004. TensorTextures: Multilinear image-based rendering. ACM Trans. Graph. 23, 3, 336--342.
44. Chaoli Wang, Hongfeng Yu, and Kwan-Liu Ma. 2010. Application-driven compression for visualizing large-scale time-varying data. IEEE Comput. Graph. Appl. 30, 1, 59--69.
45. Hongcheng Wang, Qing Wu, Lin Shi, Yizhou Yu, and Narendra Ahuja. 2005. Out-of-core tensor approximation of multidimensional matrices of visual data. ACM Trans. Graph. 24, 3, 527--535.
46. Gordon Wetzstein, Douglas Lanman, Wolfgang Heidrich, and Ramesh Raskar. 2011. Layered 3D: Tomographic image synthesis for attenuation-based light field and high dynamic range displays. ACM Trans. Graph. 30, 4.
47. Gordon Wetzstein, Douglas Lanman, Matthew Hirsch, and Ramesh Raskar. 2012. Tensor displays: Compressive light field synthesis using multi-layer displays with directional backlighting. ACM Trans. Graph. 31, 4
48. John Wright, Yi Ma, Julien Mairal, Guillermo R. Spairo, Thomas S. Huang, and Shuicheng Yan. 2010. Sparse representation for computer vision and pattern recognition. Proc. IEEE 98, 6, 1031--1044.
49. Qing Wu, Tian Xia, Chun Chen, Hsueh-Yi Sean Lin, Hongcheng Wang, and Yizhou Yu. 2008. Hierarchical tensor approximation of multidimensional visual data. IEEE Trans. Vis. Comput. Graph. 14, 1, 186--199.

Index Terms

• Information systems

  • Data management systems

    • Data structures

      • Data layout

        • Data compression