Journal Home > Volume 8 , Issue 1

Stable label movement and smooth label trajectory are critical for effective information understanding. Sudden label changes cannot be avoided by whatever forced directed methods due to the unreliability of resultant force or global optimization methods due to the complex trade-off on the different aspects. To solve this problem, we proposed a hybrid optimization method by taking advantages of the merits of both approaches. We first detect the spatial-temporal intersection regions from whole trajectories of the features, and initialize the layout by optimization in decreasing order by the number of the involved features. The label movements between the spatial-temporal intersection regions are determined by force directed methods. To cope with some features with high speed relative to neighbors, we introduced a force from future, called temporal force, so that the labels of related features can elude ahead of time and retain smooth movements. We also proposed a strategy by optimizing the label layout to predict the trajectories of features so that such global optimization method can be applied to streaming data.


menu
Abstract
Full text
Outline
Electronic supplementary material
About this article

Smoothness preserving layout for dynamic labels by hybrid optimization

Show Author's information Yu He1Guo-Dong Zhao2Song-Hai Zhang1( )
Department of Computer Science and Technology, TsinghuaUniversity, Beijing, China
Department of Computer Science and Technology,Tianjin University of Technology, Tianjin, China

Abstract

Stable label movement and smooth label trajectory are critical for effective information understanding. Sudden label changes cannot be avoided by whatever forced directed methods due to the unreliability of resultant force or global optimization methods due to the complex trade-off on the different aspects. To solve this problem, we proposed a hybrid optimization method by taking advantages of the merits of both approaches. We first detect the spatial-temporal intersection regions from whole trajectories of the features, and initialize the layout by optimization in decreasing order by the number of the involved features. The label movements between the spatial-temporal intersection regions are determined by force directed methods. To cope with some features with high speed relative to neighbors, we introduced a force from future, called temporal force, so that the labels of related features can elude ahead of time and retain smooth movements. We also proposed a strategy by optimizing the label layout to predict the trajectories of features so that such global optimization method can be applied to streaming data.

Keywords: label layout, smoothness preserving, dynamic label, forced based, static optimization, hybrid optimization

References(21)

[1]
Wolff, A.; Strijk, T. The map-labeling bibliography. 1996. Available at http://i11www.ira.uka.de/map-labeling/bibliography.
[2]
Van Garderen, M. Pictures of the past: Visualization and visual analysis in archaeological context. Ph.D. Thesis. Universität Konstanz, 2018.
[3]
Imhof, E. Positioning names on maps. The American Cartographer Vol. 2, No. 2, 128–144, 1975.
[4]
Zoraster, S. Integer programming applied to the map label placement problem. Cartographica: the International Journal for Geographic Information and Geovisualization Vol. 23, No. 3, 16–27, 1986.
[5]
Freeman, H. An expert system for the automatic placement of names on a geographic map. Information Sciences Vol. 45, No. 3, 367–378, 1988.
[6]
Christensen, J.; Marks, J.; Shieber, S. An empirical study of algorithms for point-feature label placement. ACM Transactions on Graphics Vol. 14, No. 3, 203–232, 1995.
[7]
Wagner, F.; Wolff, A. A combinatorial framework for map labeling. In: Graph Drawing. Lecture Notes in Computer Science, Vol. 1547. Whitesides S. H. Ed. Springer Berlin Heidelberg, 316–331, 1998.
DOI
[8]
Meng, Y.; Zhang, H.; Liu, M. C.; Liu, S. X. Clutter-aware label layout. In: Proceedings of the IEEE Pacific Visualization Symposium, 207–214, 2015.
DOI
[9]
Lhuillier, A.; Garderen, M.; Weiskopf, D. Density-based label placement. The Visual Computer Vol. 35, Nos. 6–8, 1041–1052, 2019.
[10]
Bell, B.; Feiner, S.; Höllerer, T. View management for virtual and augmented reality. In: Proceedings of the 14th Annual ACM Symposium on User Interface Software and Technology, 101–110, 2001.
DOI
[11]
Rosten, E.; Reitmayr, G.; Drummond, T. Real-time video annotations for augmented reality. In: Advances in Visual Computing. Lecture Notes in Computer Science, Vol. 3804. Bebis, G.; Boyle, R.; Koracin, D.; Parvin, B. Eds. Springer Berlin Heidelberg, 294–302, 2005.
DOI
[12]
Sirk, C.; Kalkofen, D.; Schmalstieg, D.; Bornik, A. Dynamic label placement for forensic case visualization. In: Proceedings of the EG/VGTC Conference on Visualization, 139–143, 2017.
[13]
Hirsch, S. A. An algorithm for automatic name placement around point data. The American Cartographer Vol. 9, No. 1, 5–17, 1982.
[14]
Pick, S.; Hentschel, B.; Tedjo-Palczynski, I.; Wolter, M.; Kuhlen, T. Automated positioning of annotations in immersive virtual environments. In: Proceedings of the 16th Eurographics Conference on Virtual Environments & Second Joint Virtual Reality, 1–8, 2010.
[15]
Vaaraniemi, M.; Treib, M.; Westermann, R. Temporally coherent real-time labeling of dynamic scenes. In: Proceedings of the 3rd International Conference on Computing for Geospatial Research and Applications, 2012.
DOI
[16]
Tatzgern, M.; Kalkofen, D.; Grasset, R.; Schmalstieg, D. Hedgehog labeling: View management techniques for external labels in 3D space. In: Proceedings of the IEEE Virtual Reality, 27–32, 2014.
DOI
[17]
Stadler, G.; Steiner, T.; Beiglböck, J. A practical map labeling algorithm utilizing morphological image processing and force-directed methods. Cartography and Geographic Information Science Vol. 33, No. 3, 207–215, 2006.
[18]
Krogmann, S. Automatic 2D label placement. 2017. Available at https://www.researchgate.net/publication/ 316043550_Automatic_2D_Label_Placement.
[19]
Ekman, S. Force-based label placement for dynamic data. Master Thesis. Chalmers University of Technology, University of Gothenburg, 2018.
[20]
Vaaraniemi, M.; Treib, M.; Westermann, R. Temporally coherent real-time labeling of dynamic scenes. In: Proceedings of the 3rd International Conference on Computing for Geospatial Research and Applications, 2012.
DOI
[21]
Lu, Y. Z.; Li, Q.; Guo, Y. M. Improved prediction model of modified exponential curve. In: Proceedings of the 3rd International Conference on Intelligent Control and Information Processing, 513–516, 2012.
Video
101320TP-2022-1-149_ESM.mp4
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 17 February 2021
Accepted: 27 March 2021
Published: 27 October 2021
Issue date: March 2022

Copyright

© The Author(s) 2021.

Acknowledgements

The authors would like to thank all reviewers for their thoughtful comments. This work was supported by the National Key Technology R&D Program (Project No. 2017YFB1002604), the National Natural Science Foundation of China (Project Nos. 61772298 and 61832016), Research Grant of Beijing Higher Institution Engineering Research Center, and Tsinghua–Tencent Joint Laboratory for Internet Innovation Technology.

Rights and permissions

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduc-tion in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made.

The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Other papers from this open access journal are available free of charge from http://www.springer.com/journal/41095. To submit a manuscript, please go to https://www. editorialmanager.com/cvmj.

Return