﻿ 一种多分辨率体绘制中张量分解最佳秩选取算法 An Algorithm for Choosing Optimal Rank in Tensor Approximation of Multi-Resolution Volume Rendering

Computer Science and Application
Vol. 08  No. 11 ( 2018 ), Article ID: 27449 , 10 pages
10.12677/CSA.2018.811183

An Algorithm for Choosing Optimal Rank in Tensor Approximation of Multi-Resolution Volume Rendering

Xiaoyan Nie1*, Cai Lu2

1Department of Electronic Engineering, Chengdu College of University of Electronic Science and Technology of China, Chengdu Sichuan

2School of Information and Communication Engineering, University of Electronic Science and Technology of China, Chengdu Sichuan

Received: Oct. 20th, 2018; accepted: Nov. 1st, 2018; published: Nov. 8th, 2018

ABSTRACT

Multi-resolution volume rendering is an effective method to solve the problem of massive data volume rendering. The comentropy based multi-resolution volume rendering has an obvious limitation when handling data of geophysical field which have a low SNR and complex microstructure characteristics. Tensor approximation can extract the characteristic bases of the data, and gain the data approximation with microstructure characteristics by means of the linear combination of the characteristic bases. We made a research about how to choose the rank in tensor approximation multi-resolution volume rendering. Low rank gained a high compression ratio, but low PSNR. High rank gained an ideal rendering effect, but low compression ratio. In this paper, we presented a method that could find the best rank adaptively for every block. Based on high rank decomposition, we did binary search to find the optimal rank which will exactly meet the error threshold. Meanwhile, data were separated into blocks, different blocks have different ranks. Experimental results show that our method has a higher compression ratio and similar render result in comparison with high rank decomposition and our method has a significant better rendering result and a slightly lower compression ratio.

Keywords:Volume Rendering, Massive Data, Multi-Resolution, Rank Truncation, Tensor Approximation

1电子科技大学成都学院电子工程系，四川 成都

2电子科技大学信息与通信工程学院，四川 成都

1. 引言

Ljung P等 [2] 提出了基于统一划分的多分辨率体绘制技术。在统一划分中，每个分块各自独立地确定自己的分辨率，分块与分块之间互不影响。Ljung等 [3] 提出了基于CIELUV (CIE 1976 (L*, u*, v*) color space)空间的误差准则。并且在分块细节水平选择时，引入了传递函数的信息，以此来优化绘制效果。梁荣华等 [4] 提出了基于信息熵的分块细节水平选择方法，并能够自适应的优化用户设定的阈值，以提高绘制效果。

Boada I [5] 等首先提出了基于八叉树的多分辨率数据表示。用一颗八叉树来表示整个三维数据体。每一个节点代表一个分块。将空间中8个相邻的分块重采样成一个相同大小的分块，即构成了这8个分块的父分块。父分块对应八叉树中，这个8个分块所对应节点的父节点。因此，每个分块的点数相同，但其所代表的空间中的实际大小不同。通过对八叉树的遍历，能够很容易地实现对每个分块的随机访问。八叉树多分辨率的很多研究集中在，如何在硬件的限制下确定每一个节点的误差。砖块与视点的距离，感兴趣的区域和块内部数据的同质性以及近似后的误差 [6] [7] [8] 通常被用来确定一个分块的细节水平。Guthe和Straber [9] 提出了一种对失真误差的保守估计方法。他们将误差定义为最大的RGB误差和最大的不透明度误差的和。Ljung [10] 用简化的1维直方图去近似每个分块和它原始分块的均方误差。

2. 高阶张量近似原理

$A\approx B{×}_{1}{U}^{\left(1\right)}{×}_{2}{U}^{\left(2\right)}{×}_{3}\cdots {×}_{n}{U}^{\left(n\right)}$ (1)

Figure 1. Tucker model tensor decomposition

3. 秩截断技术分析

Figure 2. Rank truncation

$\text{MSE}=\frac{{\sum }_{n=0}^{N}{\left({a}_{n}-{b}_{n}\right)}^{2}}{N}$ (2)

$\text{PSNR}=10×{\mathrm{log}}_{10}\frac{{K}^{2}}{\text{MSE}}$ (3)

Table 1. PSNR and compression ratio

4. 最佳秩选取算法

Figure 3. Binary search for optimal rank

$e=\frac{{‖A-\stackrel{˜}{A}‖}_{F}}{{‖A‖}_{F}}$ (4)

${‖B‖}_{F}=\sqrt{{\sum }_{i=1}^{M}{\sum }_{j=1}^{N}{b}_{ij}^{2}}$ (5)

5. 仿真分析

Table 2. Blocks distribution under different threshold by rank

(a) Te = Tp = 0.1; (b) Te = Tp = 0.2; (c) Te = Tp = 0.3; (d) Te = Tp = 0.4

Figure 4. Optimal rank rendering result under different threshold

Table 3. Comparison between optimal rank and unified rank

(a)Te = Tp = 0.25，最佳秩；(b)统一秩(16, 16, 16)分解；(c)统一秩(8, 8, 8)分解；(d)统一秩(4, 4, 4)分解

Figure 5. Comparison between optimal rank and unified rank

6. 结束语

An Algorithm for Choosing Optimal Rank in Tensor Approximation of Multi-Resolution Volume Rendering[J]. 计算机科学与应用, 2018, 08(11): 1665-1674. https://doi.org/10.12677/CSA.2018.811183

1. 1. Balsa Rodríguez, M., Gobbetti, E., Iglesias Guitián, J.A., et al. (2014) State-of-the-Art in Compressed GPU-Based Direct Volume Rendering. Computer Graphics Forum, 33, 77-100. https://doi.org/10.1111/cgf.12280

2. 2. Hadwiger, M., Ljung, P., Salama, C.R., et al. (2009) Advanced Illumination Techniques for GPU-Based Volume Raycasting. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, New York, 12-53.

3. 3. Ljung, P., Lundstrom, C., Ynnerman, A., et al. (2004) Tansfer Func-tion Based Adaptive Decompression for Volume Rendering of Large Medical Data Sets. Proceedings of the IEEE Symposium on Vol-ume Visualization and Graphics, Los Alamitos, 25-32.

4. 4. 梁荣华, 薛剑锋, 马祥音. 自适应分块细节水平的多分辨率体绘制方法[J]. 计算机辅助设计与图形学学报, 2012, 24(3): 314-322.

5. 5. Boada, I., Navazo, I. and Scopigno, R. (2001) Multi-Resolution Volume Visualization with a Texture-Based Octree. The Visual Computer, 17, 185-197. https://doi.org/10.1007/PL00013406

6. 6. LaMar, E., Hamann, B. and Joy, K.I. (1999) Multiresolution Techniques for Interactive Texture-Based Volume Visualization. Proceedings of the IEEE Visualization, San Francisco, 24-29 October 1999, 355-362. https://doi.org/10.1109/VISUAL.1999.809908

7. 7. Plate, J., Tirtasana, M., Carmona, R., et al. (2002) A Hierarchical Approach for Interactive Roaming through Very Large Volumes. Proceedings of the EUROGRAPHICS/IEEE TCVG Symposium on Visualization, Switzerland, 53-60.

8. 8. Wang, C.L., Gao, J.Z. and Shen, H.-W. (2004) Parallel Multiresolution Volume Rendering of Large Data Sets with Error-Guided Load Balancing. Proceedings of the EURO-GRAPHICS Symposium on Parallel Graphics & Visualization, Switzerland, 23-30.

9. 9. Guthe, S. and Staßer, W. (2004) Advanced Techniques for High-Quality Multi-Resolution Volume Render-ing. Computers & Graphics, 28, 51-58. https://doi.org/10.1016/j.cag.2003.10.018

10. 10. Ljung, P., Lundstrom, C., Ynnerman, A., et al. (2004) Transfer Function Based Adaptive Decompression for Volume Rendering of Large Medical Data Sets. Proceedings of the IEEE Symposium on Volume Visualization and Graphics, Austin, TX, 12 October 2004, 25-32. https://doi.org/10.1109/SVVG.2004.14

11. 11. Kolda, T.G. and Bader, B.W. (2009) Tensor Decompositions and Applications. SIAM Review, 51, 455-500. https://doi.org/10.1137/07070111X

12. 12. Wu, Q., Xia, T., Chen, C., et al. (2008) Hierarchical Tensor Approximation of Multidi-mensional Visual Data. IEEE Transaction on Visualization and Computer Graphics, 14, 186-199. https://doi.org/10.1109/TVCG.2007.70406

13. 13. Suter, S.K., Makhynia, M. and Pajarola, R. (2013) Tamresh-Tensor Approxima-tion Multiresolution Hierarchy for Interactive Volume Visualization. Computer Graphics Forum, 32, 151-160.

14. 14. Ballester-Ripoll, R., Suter, S.K. and Pajarola, R. (2015) Analysis of Tensor Approximation for Compression-Domain Volume Visualization. Computers & Graphics, 47, 34-47. https://doi.org/10.1016/j.cag.2014.10.002

15. 15. Balsa Rodríguez, M., Gobbetti, E., Iglesias Guitián, J.A., et al. (2014) State-of-the-Art in Compressed GPU-Based Direct Volume Rendering. Computer Graphics Forum, 33, 77-100. https://doi.org/10.1111/cgf.12280

16. 16. Piccand, S., Noumeir, R. and Paquette, E. (2008) Region of Interest and Multiresolution for Volume Rendering. IEEE Transactions on Information Technology in Biomedicine, 12, 561-568. https://doi.org/10.1109/TITB.2007.907986

17. 17. Lorensen, W.E. and Cline, H.E. (1987) Marching Cubes: A High-Resolution 3D Surface Construction Algorithm. Computer Graphics, 21, 163-169. https://doi.org/10.1145/37402.37422

18. 18. Grgic, S., Grgic, M. and Mrak, M. (2004) Reliability of Objective Picture Quality Measures. Journal of Electrical Engineering, 55, 3-10.

NOTES

*通讯作者。