Please wait a minute...
Journal of Zhejiang University (Science Edition)  2023, Vol. 50 Issue (6): 681-691    DOI: 10.3785/j.issn.1008-9497.2023.06.003
CCF CAD/CG 2023     
Focus+Context visualization based on optimal mass transportation
Kehua SU1(),Bailüe LIU1,Na LEI2(),Kehan LI1,Xianfeng GU3
1.School of Computer Science,Wuhan University,Wuhan 430072,China
2.International School of Information Science & Engineering,Dalian University of Technology,Dalian 116024,Liaoning Province,China
3.Department of Computer Science,State University of New York at Stony Brook,Stony Brook 11790,New York,USA
Download: HTML( 3 )   PDF(3910KB)
Export: BibTeX | EndNote (RIS)      

Abstract  

In visualization field, Focus+Context techniques have been developed to visualize large, complex models on the display device with limited resolution. In this work, we propose a novel method for Focus+Context visualization based on optimal mass transportation. An optimal mass transportation map deforms a volume to itself, transforms the source measure (volumetric element) to the target measure with the minimal transportation cost. Solving the optimal mass transportation problem is equivalent to a convex optimization, and can be converted to computing power Voronoi diagrams in classical computational geometry. Comparing to existing approaches, the proposed method has solid theoretic foundation, which guarantees the existence, uniqueness and the smoothness of the solution. It allows the user to accurately control the target measure, and select multiple focus regions with irregular shapes. The resulting deformation is globally smooth and flipping free. Experiments with several volume data sets from medical applications and scientific simulations demonstrate the effectiveness and efficiency of our method.



Key wordsradiosity      global illumination      constant time     
Received: 12 June 2023      Published: 30 November 2023
CLC:  TP 391.41  
Corresponding Authors: Na LEI     E-mail: skh@whu.edu.cn;nalei@dlut.edu.cn
Cite this article:

Kehua SU,Bailüe LIU,Na LEI,Kehan LI,Xianfeng GU. Focus+Context visualization based on optimal mass transportation. Journal of Zhejiang University (Science Edition), 2023, 50(6): 681-691.

URL:

https://www.zjujournals.com/sci/EN/Y2023/V50/I6/681


基于最优质量传输的Focus+Context可视化

在分辨率有限的显示设备上,Focus+Context技术可用于大型复杂模型的可视化。提出了一种基于最优质量传输的Focus+Context可视化方法。通过最优质量传输映射,对自身进行体积变形,将源测度(体素)转换为传输成本最小的目标测度;将求解最优质量传输问题等价于凸优化过程,转换为计算几何中经典的幂Voronoi图计算。与现有方法相比,本文方法具有坚实的理论基础,保证了解的存在性、唯一性和平滑性;允许用户精确控制目标测度,选择多个形状不规则的聚焦区域,使产生的变形是全局平滑的,并可自由翻转。用于自医学应用和科学仿真的几项体数据集,证明了所提方法是有效和高效的。


关键词: 辐射度,  全局光照,  常量时间 
Fig.1 The upper envelope h, the convex hull 𝒞h, the power voronoi cell decomposition 𝒱(h), the power Delaunay triangulation 𝒯h and two-dimensional analogies of their relationship
Fig.2 The volumetric aneurism magnified by large scales using the OMT technique
Fig. 3 Measure accurate control for Bonsai model
Fig. 4 The effectiveness of the smoothness of the target measure μ on the smoothness of the deformation
Fig. 5 F+C visualization for NCAT phantom model
Fig. 6 F+C visualization for CT knee model with multiple focus magnification in different views
模型数据来源运行时间/s分辨率
动脉瘤Philips Research,Hamburg,Germany118512×512×512
盆栽Rosttger S,VIS,University of Stuttgart156512×512×512
Philips Research,Hamburg,Germany182256×256×256
NCAT phantomSegars WP,Tsui BMW156512×512×512
CT膝关节Department of Radiology University of Iowa134440×440×440
Table 1 Running time
[1]   WANG Y S, WANG C, LEE T Y, et al. Feature-preserving volume data reduction and Focus+ Context visualization[J]. IEEE Transactions on Visualization and Computer Graphics, 2010, 17(2): 171-181. DOI:10.1109/tvcg.2010.34
doi: 10.1109/tvcg.2010.34
[2]   GU X, LUO F, SUN J, et al. Variational principles for Minkowski type problems, discrete optimal transport, and discrete Monge-Ampere equations[J]. Asian Journal of Mathematics, 2016, 20(2): 383-398. doi:10.4310/ajm.2016.v20.n2.a7
doi: 10.4310/ajm.2016.v20.n2.a7
[3]   SARKAR M, BROWN M H. Graphical fisheye views of graphs[C]// SIGCHI Conference on Human Factors in Computing Systems. Monterey: SIGCHI, 1992: 83-91. DOI:10.1145/142750.142763
doi: 10.1145/142750.142763
[4]   KUMAR V R, EISING C, WITT C, et al. Surround-view fisheye camera perception for automated driving: Overview, survey & challenges[J]. IEEE Transactions on Intelligent Transportation Systems, 2023, 24(4): 3638-3659. DOI:10.1109/tits.2023. 3235057
doi: 10.1109/tits.2023. 3235057
[5]   BIER E A, STONE M C, PIER K, et al. Toolglass and magic lenses: The see-through interface[C]// 20th Annual Conference on Computer Graphics and Interactive Techniques. Anaheim: ACM, 1993: 73-80. DOI:10.1145/166117.166126
doi: 10.1145/166117.166126
[6]   AGLEDAHL S, STEED A. Magnification vision: A novel gaze-directed user interface[C]// 2021 IEEE Conference on Virtual Reality and 3D User Interfaces Abstracts and Workshops (VRW). IEEE: Portugal, 2021: 474-475. DOI:10.1109/vrw52623.2021.00119
doi: 10.1109/vrw52623.2021.00119
[7]   CARPENDALE M S T, COWPERTHWAITE D J, FRACCHIA F D. Distortion viewing techniques for 3-dimensional data[C]// Proceedings of IEEE Symposium on Information Visualization. San Francisco: IEEE, 1996: 46-53. DOI:10.1109/infvis. 1996.559215 .
doi: 10.1109/infvis. 1996.559215
[8]   CARPENDALE M S T, COWPERTHWAITE D J, FRACCHIA F D. Multi-scale viewing[C]// 23th International Conference on Computer Graphics and Interactive Techniques. New Orleans: ACM, 1996: 149. DOI:10.1145/253607.253882
doi: 10.1145/253607.253882
[9]   CARPENDALE M S T, MONTAGNESE C. A framework for unifying presentation space[C]// 14th Annual ACM Symposium on User Interface Software and Technology. Orlando: ACM, 2001: 61-70. DOI:10.1145/502348.502358
doi: 10.1145/502348.502358
[10]   VIOLA I, KANITSAR A, GROLLER M E. Importance-driven volume rendering[C]// IEEE Visualization. Austin: IEEE, 2004: 139-145. DOI:10.1109/visual.2004.48
doi: 10.1109/visual.2004.48
[11]   VIOLA I, FEIXAS M, SBERT M, et al. Importance-driven focus of attention[J]. IEEE Transactions on Visualization and Computer Graphics, 2006, 12(5): 933-940. DOI:10.1109/tvcg.2006.152
doi: 10.1109/tvcg.2006.152
[12]   PIETRIGA E, APPERT C. Sigma lenses: Focus-Context transitions combining space, time and translucence[C]// SIGCHI Conference on Human Factors in Computing Systems. Florence: SIGCHI, 2008: 1343-1352. DOI:10.1145/1357054.1357264
doi: 10.1145/1357054.1357264
[13]   PIETRIGA E, BAU O, APPERT C. Representation-independent in-place magnification with sigma lenses[J]. IEEE Transactions on Visualization and Computer Graphics, 2009, 16(3): 455-467. doi:10.1109/tvcg.2009.98
doi: 10.1109/tvcg.2009.98
[14]   MCGUFFIN M J, TANCAU L, BALAKRISHNAN R. Using deformations for browsing volumetric data[C]// IEEE Visualization. Seattle: IEEE, 2003: 401-408. DOI:10.1109/visual.2003.1250400
doi: 10.1109/visual.2003.1250400
[15]   CORREA C, SILVER D, CHEN M. Illustrative deformation for data exploration[J]. IEEE Transactions on Visualization and Computer Graphics, 2007, 13(6): 1320-1327. DOI:10.1109/tvcg.2007.70565
doi: 10.1109/tvcg.2007.70565
[16]   WANG L, ZHAO Y, MUELLER K, et al. The magic volume lens: An interactive Focus+Context technique for volume rendering[C]// IEEE Visualization. Minneapolis: IEEE, 2005: 367-374. DOI:10.1109/visual.2005.1532818
doi: 10.1109/visual.2005.1532818
[17]   WANG Y S, LEE T Y, TAI C L. Focus+Context visualization with distortion minimization[J]. IEEE Transactions on Visualization and Computer Graphics, 2008, 14(6): 1731-1738. DOI:10.1109/tvcg.2008.132
doi: 10.1109/tvcg.2008.132
[18]   ZHAO X, ZENG W, GU X D, et al. Conformal magnifier: A Focus+ Context technique with local shape preservation[J]. IEEE Transactions on Visualization and Computer Graphics, 2012, 18(11): 1928-1941. doi:10.1109/tvcg.2012.70
doi: 10.1109/tvcg.2012.70
[19]   TAO J, WANG C, SHENE C K, et al. A deformation framework for Focus+Context flow visualization[J]. IEEE Transactions on Visualization and Computer Graphics, 2013, 20(1): 42-55. DOI:10.1109/tvcg.2013.100
doi: 10.1109/tvcg.2013.100
[20]   ZHAO X, SU Z, GU X D, et al. Area-preservation mapping using optimal mass transport[J]. IEEE Transactions on Visualization and Computer Graphics, 2013, 19(12): 2838-2847. DOI:10.1109/tvcg.2013.135
doi: 10.1109/tvcg.2013.135
[21]   BONNOTTE N. From Knothe's rearrangement to Brenier's optimal transport map[J]. SIAM Journal on Mathematical Analysis, 2013, 45(1): 64-87. DOI:10.1137/120874850
doi: 10.1137/120874850
[22]   KANTOROVICH L V. On a problem of Monge[J]. Journal of Mathematical Sciences, 2006, 133(4): 1383-1383. DOI:10.1007/s10958-006-0050-9
doi: 10.1007/s10958-006-0050-9
[23]   BRENIER Y. Polar factorization and monotone rearrangement of vector-valued functions[J]. Communications on Pure and Applied Mathematics, 1991, 44(4): 375-417. DOI:10.1002/cpa. 3160440402
doi: 10.1002/cpa. 3160440402
[24]   ALEXANDROV A D. Convex Polyhedra[M]. Berlin: Springer, 2005. doi:10.1007/b137434
doi: 10.1007/b137434
[25]   AURENHAMMER F. Power diagrams: Properties, algorithms and applications[J]. SIAM Journal on Computing, 1987, 16(1): 78-96. DOI:10.1137/0216006
doi: 10.1137/0216006
[26]   DE BERG M, CHEONG O, VAN KREVELD M J, et al. Computational Geometry (Algorithms and Applications)[M]. Berlin: Springer, 2008. doi:10.1007/978-3-540-77974-2
doi: 10.1007/978-3-540-77974-2
[27]   SI H. TetGen, a Delaunay-based quality tetrahedral mesh generator[J]. ACM Transactions on Mathematical Software, 2015, 41(2): 1-36. DOI:10. 1145/2629697
doi: 10. 1145/2629697
[28]   REUTER M, WOLTER F E, PEINECKE N. Laplace-Beltrami spectra as "Shape-DNA" of surfaces and solids[J]. Computer-Aided Design, 2006, 38(4): 342-366. DOI:10.1016/j.cad.2005. 10.011
doi: 10.1016/j.cad.2005. 10.011
[1] Shengjun LIU,Zi TENG,Haibo WANG,Xinru LIU. Two-dimensional shape intrinsic symmetry detection algorithm based on functional map[J]. Journal of Zhejiang University (Science Edition), 2023, 50(6): 668-680.
[2] Zerun LIU,Yufei YIN,Wenhao XUE,Rui GUO,Lechao CHENG. A review of conditional image generation based on diffusion models[J]. Journal of Zhejiang University (Science Edition), 2023, 50(6): 651-667.
[3] Yuhua FANG,Feng YE. MFDC-Net: A breast cancer pathological image classification algorithm incorporating multi-scale feature fusion and attention mechanism[J]. Journal of Zhejiang University (Science Edition), 2023, 50(4): 455-464.
[4] Ruiqi YU,Yuhua LIU,Xilong SHEN,Ruyu ZHAI,Xiang ZHANG,Zhiguang ZHOU. Representation learning driven multiple graph sampling[J]. Journal of Zhejiang University (Science Edition), 2022, 49(3): 271-279.
[5] Ying ZHONG,Song WANG,Hao WU,Zepeng CHENG,Xuejun LI. SEMMA-Based visual exploration of cyber security event[J]. Journal of Zhejiang University (Science Edition), 2022, 49(2): 131-140.
[6] Jintai ZHU, Jihua YE, Feng GUO, Lu JIANG, Aiwen JIANG. FSAGN:An expression recognition method based on independent selection of video key frames[J]. Journal of Zhejiang University (Science Edition), 2022, 49(2): 141-150.
[7] Qiang ZHU,Chaoyi WANG,Jiqing ZHANG,Baocai YIN,Xiaopeng WEI,Xin YANG. UAV target tracking algorithm based on event camera[J]. Journal of Zhejiang University (Science Edition), 2022, 49(1): 10-18.
[8] Meng YANG,Shu DING,Yuntao MA,Jiayi XIE,Ruifeng DUAN. Dynamic simulation method of wheat rust based on texture feature[J]. Journal of Zhejiang University (Science Edition), 2022, 49(1): 1-9.
[9] FU Rujia, XIAN Chuhua, LI Guiqing, WAN Juanjie, CAO Cheng, YANG Cunyi, GAO Yuefang. Rapid 3D reconstruction of bean plant for accurate phenotype identification[J]. Journal of Zhejiang University (Science Edition), 2021, 48(5): 531-539.
[10] YU Peng, LIU Lan, CAI Yun, HE Yu, ZHANG Songhai. Home fitness monitoring system based on monocular camera[J]. Journal of Zhejiang University (Science Edition), 2021, 48(5): 521-530.
[11] GUI Zhiqiang, YAO Yuyou, ZHANG Gaofeng, XU Benzhu, ZHENG Liping. An efficient computation method of 3D-power diagram[J]. Journal of Zhejiang University (Science Edition), 2021, 48(4): 410-417.
[12] XU Min, WANG Ke, DAI Haoran, LUO Xiaobo, YU Weilun, TAO Yubo, LIN Hai. Visual analysis of cohorts and treatments of breast cancer based on electronic health records[J]. Journal of Zhejiang University (Science Edition), 2021, 48(4): 391-401.
[13] ZOU Beiji, YANG Wenjun, LIU Shu, JIANG Lingzi. A three-stage text recognition framework for natural scene images[J]. Journal of Zhejiang University (Science Edition), 2021, 48(1): 1-8.
[14] CHEN Yuanqiong, ZOU Beiji, ZHANG Meihua, LIAO Wangmin, HUANG Jiaer, ZHU Chengzhang. A review on deep learning interpretability in medical image processing[J]. Journal of Zhejiang University (Science Edition), 2021, 48(1): 18-29.
[15] DENG Huijun. Ranking-supported interactive data classification method and its application[J]. Journal of Zhejiang University (Science Edition), 2021, 48(1): 9-17.