EUVIMEDEUVIMED entdecken
Crossref

Multirow Boundary-Labeling Algorithms for Panorama Images

Andreas Gemsa, Jan-Henrik Haunert, Martin Nöllenburg

ACM Transactions on Spatial Algorithms and Systems · 2015

DOI: 10.1145/2794299 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Spatial Algorithms and Systems, 2015. Verfasst von Andreas Gemsa und 2 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 25 Literaturangaben. Gefördert von: KIT.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Boundary labeling deals with placing annotations for objects in an image on the boundary of that image. This problem occurs frequently in situations in which placing labels directly in the image is impossible or produces too much visual clutter. Examples are annotating maps, photos, or technical/medical illustrations. Previous algorithmic results for boundary labeling consider a single layer of labels along some or all sides of a rectangular image. If, however, the number of labels is large or the labels are too long, multiple layers of labels are needed. In this article, we study boundary labeling for panorama images, where n points in a rectangle R are to be annotated by disjoint unit-height rectangular labels placed above R in K different rows (or layers). Each point is connected to its label by a vertical leader that does not intersect any other label. We present polynomial time algorithms based on dynamic programming that either minimize the number of rows to place all n labels or maximize the number (or total weight) of labels that can be placed in K rows for a given integer K . For weighted labels, the problem is shown to be (weakly) NP-hard; in this case, we give a pseudo-polynomial algorithm to maximize the weight of the selected labels. We have implemented our algorithms; the experimental results show that solutions for realistically sized instances are computed instantaneously. We have also investigated two-sided panorama labeling, for which the labels may be placed above or below the panorama image. In this model, all of the aforementioned problems are NP-hard. For solving them, we propose mixed-integer linear program formulations.

Förderung

  • KIT

Zitieren

APA

Gemsa, A., Haunert, J., & Nöllenburg, M. (2015). Multirow Boundary-Labeling Algorithms for Panorama Images. ACM Transactions on Spatial Algorithms and Systems. https://doi.org/10.1145/2794299

Vancouver

Gemsa A, Haunert J, Nöllenburg M. Multirow Boundary-Labeling Algorithms for Panorama Images. ACM Transactions on Spatial Algorithms and Systems. 2015. doi:10.1145/2794299

BibTeX
@article{Gemsa2015,
  author = {Gemsa, Andreas and Haunert, Jan-Henrik and Nöllenburg, Martin},
  title = {Multirow Boundary-Labeling Algorithms for Panorama Images},
  journal = {ACM Transactions on Spatial Algorithms and Systems},
  year = {2015},
  doi = {10.1145/2794299}
}
Kostenlos starten →