Doctoral Thesis

Automatic Point-feature Label Placement

Final Thesis 90.24 MB Appendix 463.75 kB Summary of Thesis 90.24 MB

Author of thesis: Ing. Petr Bobák, Ph.D.

Acad. year: 2024/2025

Supervisor: doc. Ing. Martin Čadík, Ph.D.

Reviewers: prof. Dr. Ing. Eduard Gröller, Prof. Ivan Viola

Abstract:

Automatic label placement is a crucial aspect of data visualization, essential for enhancing the clarity and readability of visual representations across various domains such as cartography, medical imaging, and emergency response management. Label, in this context, refers to textual or symbolic annotation that identifies or explains specific point feature within a visualization, such as the name of the city on a map, measurement on a medical scan, or position of AED in a schematic map for emergency response dispatchers. The work covered in this dissertation aims to advance the field by developing novel techniques addressing the inherent challenges associated with internal and external label placement in complex visualizations.   Internal label placement refers to placing labels close to the point features they describe within the boundaries of the visualization. External label placement, on the other hand, involves placing labels outside the main visualization area, connected to the relevant features by lines. 
Our research focuses on three key areas: achieving temporally stable and visually coherent boundary label placements, leveraging machine learning to improve the completeness of internal label placements, and optimizing label positioning by integrating perceptual insights. The dissertation begins with a comprehensive review of existing techniques, identifying significant gaps in handling dynamic environments and maintaining visual coherence. The literature review also highlights that the label placement quality is not entirely and precisely defined, as many cartographic guidelines rely on best practices rather than empirical studies.  Building on these insights, we introduce novel optimization methods for boundary label placement in dynamic panoramic visualizations, minimizing label movement and reducing user cognitive load. Experimental results demonstrate the effectiveness of these approaches in maintaining label stability without compromising readability or clarity.  In the context of internal label placement, we explore the relevance of deep reinforcement learning and propose a novel method that significantly improves label completeness, particularly in dense and complex scenarios.  Furthermore, we introduce a perceptual study that determines user-preferred label positions, challenges conventional placement strategies, and demonstrates the importance of considering user preferences in label placement design. Our supplementary study on users' preferred label density, a topic scarcely explored in existing literature, further confirms that integrating perceptual insights into the label placement process significantly enhances the overall user experience, leading to more intuitive and compelling visualizations. 
While the proposed methods offer substantial improvements over existing techniques, we acknowledge several limitations, including the complexity of implementing the boundary label optimization in real-time scenarios and the computational demands of the reinforcement learning approach. Future research directions include the development of mixed label placement models for 3D visualizations, optimization of computational efficiency, and further exploration of user perception to refine label placement techniques.

Keywords:

Data visualization, automatic label placement, external label placement, internal label placement, machine learning in visualization, deep reinforcement learning, perception, visual coherence, dynamic visualizations, user-centered design, label position optimization

Date of defence

09.12.2024

Result of the defence

Defended (thesis was successfully defended)

znamkaPznamka

Process of defence

The student presented the goals and results that he achieved within his work of the dissertation. The student has competently answered the questions of the committee members and reviewers. The discussion is recorded on the discussion sheets, which are attached to the protocol. Number of discussion sheets: 3 The committee has agreed unanimously that the student has fulfilled the requirements for being awarded the academic title Ph.D. The committee and reviewers recommend awarding the thesis the Dean's prize.

Language of thesis

English

Faculty

Department

Study programme

Computer Science and Engineering (CSE-PHD-4)

Field of study

Computer Science and Engineering (DVI4)

Composition of Committee

prof. Ing. Lukáš Sekanina, Ph.D. (předseda)
prof. Dr. Ing. Eduard Gröller (člen)
doc. RNDr. Barbora Kozlíková, Ph.D. (člen)
prof. Ing. Pavel Slavík, CSc. (člen)
doc. Dr. Ing. Eduard Sojka (člen)

Supervisor’s report
doc. Ing. Martin Čadík, Ph.D.

For full version, please refer to the pdf file.


Ing. Petr Bobák, in his dissertation titled "Automatic Point-feature Label Placement," addresses the issue of automatic label placement which is a central aspect of data visualization. In my opinion, this is a very current and challenging topic in contemporary data visualization research. The topic of automatic label placement was brought to our attention through practical applications of camera pose estimation methods, which we have been working on within the CPhoto@FIT research group since 2009.


I noticed Petr Bobák's diligence and talent during his engineering studies at FIT BUT. Petr joined our CPhoto@FIT research group in the fall of 2017. He began familiarizing himself with the topic of automatic label placement while simultaneously working in the commercial sector. Over time, Petr delved deeply into the issues of mathematical optimization, machine learning, and user experiments. From the beginning of his doctoral studies, Petr was very passionate about research. Nevertheless, as far as I can judge, he managed to balance his research efforts with his professional and personal life very well. Within the CPhoto@FIT research group, Petr was always willing to help his colleagues.


Among Petr Bobák's main research results are new methods for temporally coherent boundary label placement, which were published in the Computers and Graphics journal and presented at the CGI (Computer Graphics International) conference. The most significant result, in my opinion, is a new method for internal label placement, which is one of the first to use machine learning (specifically reinforcement learning) to increase label completeness. This result was published in the prestigious journal IEEE TVCG (Transactions on Visualization and Computer Graphics) and presented at the PacificVis conference.


Working with Petr Bobák has been a pleasure for me, especially due to his professional approach, reliability, and diligence. It has been an honor to observe and contribute to Petr Bobák's development from a fresh engineer to a confident and successful young researcher. Given the above-mentioned facts, I am pleased to recommend Ing. Petr Bobák's work for defense.

File inserted by supervisor Size
Stanovisko školitele [.pdf] 60,10 kB

Reviewer’s report
prof. Dr. Ing. Eduard Gröller

Moreover, the evaluations do more than merely present data; they reveal a range of non-trivial insights that deepen the reader’s understanding of the subject. Overall, the thesis and the student´s achievements until now fully meet the generally accepted requirements for the award of an academic degree (in accordance with Section 47 of Act No. 111/1998 Coll., on higher education institution).
File inserted by the reviewer Size
Posudek oponenta [.pdf] 226,39 kB

Reviewer’s report
Prof. Ivan Viola

Three research works presented in the thesis substantially contribute to visualization.
Additionally, the survey is valuable on its own and is an additional contribution of this dissertation. In all presented research projects, there is always a valid problem to tackle, the technical solution is appropriate and novel, and it is exhaustively compared to the state-of-the-art methods in quantitative performance evaluation and user studies. Ing. Petr Bobák has clearly demonstrated his capacity as an independent researcher. In conclusion, from the position of an external reviewer, I propose to approve the dissertation in its current form and support the candidate in defending his thesis.
File inserted by the reviewer Size
Posudek oponenta [.pdf] 169,50 kB

Responsibility: Mgr. et Mgr. Hana Odstrčilová