Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Density-based label placement

  • Original Article
  • Published:
The Visual Computer Aims and scope Submit manuscript

Abstract

We introduce a versatile density-based approach to label placement that aims to put labels in uncluttered areas of an underlying 2D visualization. Our novel, image-space algorithm constructs a density map by applying kernel density estimation to the input features, i.e., the locations of the points to be labeled. In order to find a suitable position for a label where it does not overlap any features or other labels, we move it following the gradient descent of this density map. This guides labels toward nearby areas of low feature density, resulting in a layout where labels are spread around feature-dense areas. The gradient descent trajectory can be used to draw curved leaders that connect the point features to their labels. Additionally, our approach supports prioritized label placement, user-defined label-to-label and label-to-feature margins, obstacle-constrained labeling, and arbitrarily shaped labels. The proposed method is conceptually simple and can easily be implemented using OpenCV and image-processing libraries.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Abramowitz, M., Stegun, I.A., et al.: Handbook of Mathematical Functions: with Formulas, Graphs, and Mathematical Tables, vol. 55. Dover Publications, New York (1972)

    MATH  Google Scholar 

  2. Bekos, M.A., Kaufmann, M., Papadopoulos, D., Symvonis, A.: Combining traditional map labeling with boundary labeling. In: SOFSEM 2011: Theory and Practice of Computer Science, pp. 111–122. Springer, Berlin (2011)

  3. Bekos, M.A., Kaufmann, M., Symvonis, A., Wolff, A.: Boundary labeling: models and efficient algorithms for rectangular maps. Comput. Geom. 36(3), 215–236 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  4. Benkert, M., Haverkort, H.J., Kroll, M., Nöllenburg, M.: Algorithms for multi-criteria boundary labeling. J. Graph Algorithms Appl. 13(3), 289–317 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bradski, G., Kaehler, A.: Learning OpenCV: Computer Vision with the OpenCV Library. O’Reilly Media, Newton (2008)

    Google Scholar 

  6. Christensen, J., Marks, J., Shieber, S.: An empirical study of algorithms for point-feature label placement. ACM Trans. Graph. 14(3), 203–232 (1995)

    Article  Google Scholar 

  7. Dwyer, T., Marriott, K., Stuckey, P.J.: Fast node overlap removal. In: Proceedings of 13th International Symposium on Graph Drawing (GD’05), pp. 153–164. Springer, Berlin (2006)

  8. Epanechnikov, V.A.: Non-parametric estimation of a multivariate probability density. Theory Prob. Appl. 14(1), 153–158 (1969)

    Article  MathSciNet  Google Scholar 

  9. Ersoy, O., Hurter, C., Paulovich, F., Cantareiro, G., Telea, A.: Skeleton-based edge bundling for graph visualization. IEEE Trans. Vis. Comput. Graph. 17(12), 2364–2373 (2011)

    Article  Google Scholar 

  10. Fekete, J.D., Plaisant, C.: Excentric labeling: Dynamic neighbourhood labeling for data visualization. In: Proceedings of SIGCHI Conference on Human Factors in Computing Systems (CHI ’99), pp. 512–519 (1999)

  11. Formann, M., Wagner, F.: A packing problem with applications to lettering of maps. In: Proceedings of 7th Annual Symposium on Computational Geometry (SoCG’91), pp. 281–288 (1991)

  12. Freeman, H.: An expert system for the automatic placement of names on a geographic map. Inf. Sci. 45(3), 367–378 (1988)

    Article  Google Scholar 

  13. Frigo, M., Johnson, S.G.: FFTW: An adaptive software architecture for the FFT. In: Proceedings of 1998 IEEE International Conference on Acoustics, Speech, and Signal Processing, vol. 3, pp. 1381–1384 (1998)

  14. Gansner, E.R., Hu, Y.: Efficient node overlap removal using a proximity stress model. In: Tollis, I.G., Patrignani, M. (eds.) Proceedings of 16th International Symposium on Graph Drawing (GD’08), pp. 206–217. Springer, Berlin (2009)

  15. Gonzalez, R.C.: Digital Image Processing. Prentice Hall, Englewood Cliffs (2016)

    Google Scholar 

  16. Hurter, C., Ersoy, O., Telea, A.: Graph bundling by kernel density estimation. Comput. Graph. Forum 31, 865–874 (2012)

    Article  Google Scholar 

  17. Iturriaga, C., Lubiw, A.: Elastic labels around the perimeter of a map. J. Algorithms 47(1), 14–39 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  18. Jones, M.C., Marron, J.S., Sheather, S.J.: A brief survey of bandwidth selection for density estimation. J. Am. Stat. Assoc. 91(433), 401–407 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  19. Kallenbach, R.L., Bishop-Hurley, G.J.: Dairy grazing: growth of pasture plants, vol. M182. University of Missouri Extensions, Columbia (2012)

    Google Scholar 

  20. Kaufmann, M.: On map labeling with leaders. In: Albers, S., Alt, H., Näher, S. (eds.) Efficient Algorithms: Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday, pp. 290–304. Springer, Berlin (2009)

    Chapter  Google Scholar 

  21. Kindermann, P., Niedermann, B., Rutter, I., Schaefer, M., Schulz, A., Wolff, A.: Multi-sided boundary labeling. Algorithmica 76(1), 225–258 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  22. Kouřil, D., Čmolík, L., Kozlíková, B., Wu, H., Johnson, G., Goodsell, D.S., Olson, A., Gröller, M.E., Viola, I.: Labels on levels: labeling of multi-scale multi-instance and crowded 3D biological environments. IEEE Trans. Vis. Comput. Graph. 25(1), 977–986 (2019)

    Article  Google Scholar 

  23. Lampe, O.D., Hauser, H.: Interactive visualization of streaming data with kernel density estimation. In: Proceedings of 2011 IEEE Pacific Visualization Symposium (PacificVis), pp. 171–178 (2011)

  24. Lhuillier, A.: Bundling: a clutter reduction technique and its application to Alzheimer study. Ph.D. thesis, Université Paul Sabatier-Toulouse III (2017)

  25. Lhuillier, A., Hurter, C., Telea, A.: FFTEB: edge bundling of huge graphs by the fast Fourier transform. In: Proceedings of 2017 IEEE Pacific Visualization Symposium (PacificVis), pp. 190–199 (2017)

  26. Löffler, M., Nöllenburg, M., Staals, F.: Mixed map labeling. In: Paschos, V.T., Widmayer, P. (eds.) Algorithms and Complexity, pp. 339–351 (2015)

  27. Luboschik, M., Schumann, H., Cords, H.: Particle-based labeling: fast point-feature labeling without obscuring other visual features. IEEE Trans. Vis. Comput. Graph. 14(6), 1237–1244 (2008)

    Article  Google Scholar 

  28. Meng, Y., Zhang, H., Liu, M., Liu, S.: Clutter-aware label layout. In: Proceedings of 2015 IEEE Pacific Visualization Symposium (PacificVis), pp. 207–214 (2015)

  29. Misue, K., Eades, P., Lai, W., Sugiyama, K.: Layout adjustment and the mental map. J. Vis. Lang. Comput. 6(2), 183–210 (1995)

    Article  Google Scholar 

  30. Oeltze-Jafra, S., Preim, B.: Survey of labeling techniques in medical visualizations. In: Proceedings of 4th Eurographics Workshop Visual Computing Biology Medicine (VCBM’14), pp. 199–208 (2014)

  31. Podlozhnyuk, V.: FFT-Based 2D Convolution. NVIDIA white paper (2007)

  32. Sheather, S.J., Jones, M.C.: A reliable data-based bandwidth selection method for kernel density estimation. J. R. Stat. Soc. Ser. B (Methodol.) 53(3), 683–690 (1991)

    MathSciNet  MATH  Google Scholar 

  33. Silverman, B.W.: Density Estimation for Statistics and Data Analysis. Chapman and Hall, London (1986)

    Book  MATH  Google Scholar 

  34. Telea, A., van Wijk, J.J.: An augmented fast marching method for computing skeletons and centerlines. In: Proceedings of 2002 Symposium on Data Visualisation, pp. 251–258 (2002)

  35. van Liere, R., de Leeuw, W.: GraphSplatting: visualizing graphs as continuous fields. IEEE Trans. Vis. Comput. Graph. 9(2), 206–212 (2003)

    Article  Google Scholar 

  36. van der Zwan, M., Codreanu, V., Telea, A.: CUBu: universal real-time bundling for large graphs. IEEE Trans. Vis. Comput. Graph. 22(12), 2550–2563 (2016)

    Article  Google Scholar 

  37. van Garderen, M.: Automated map labelling. In: Pictures of the past—visualization and visual analysis in archaeological context, chap. 6, pp. 155–174. Doctoral dissertation, University of Konstanz (2018)

  38. Wagner, F., Wolff, A.: A combinatorial framework for map labeling. In: Proceedings of 6th International Symposium on Graph Drawing (GD’98), pp. 316–331 (1998)

  39. Wolff, A., Strijk, T.: The map-labeling bibliography. i11www.ira.uka.de/map-labeling/bibliography/ (2009)

  40. Zinsmaier, M., Brandes, U., Deussen, O., Strobelt, H.: Interactive level-of-detail rendering of large graphs. IEEE Trans. Vis. Comput. Graph. 18(12), 2486–2495 (2012)

    Article  Google Scholar 

  41. Zoraster, S.: Integer programming applied to the map label placement problem. Cartograph. Int. J. Geograp. Inf. Geovis. 23(3), 16–27 (1986)

    Google Scholar 

Download references

Acknowledgements

MvG was funded by the European Research Council (ERC) under the European Union’s Seventh Framework Programme (FP7/2007-2013) / ERC Grant agreement No. 319209 (project NEXUS 1492).

Author information

Authors and Affiliations

  1. University of Stuttgart, Stuttgart, Germany

    Antoine Lhuillier & Daniel Weiskopf

  2. University of Konstanz, Konstanz, Germany

    Mereke van Garderen

Authors
  1. Antoine Lhuillier
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mereke van Garderen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Daniel Weiskopf
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mereke van Garderen.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lhuillier, A., van Garderen, M. & Weiskopf, D. Density-based label placement. Vis Comput 35, 1041–1052 (2019). https://doi.org/10.1007/s00371-019-01686-7

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00371-019-01686-7

Keywords

Search

Navigation