key: cord-1017695-9qgzz4er
authors: He, Yu; Zhao, Guo-Dong; Zhang, Song-Hai
title: Smoothness preserving layout for dynamic labels by hybrid optimization
date: 2021-10-27
journal: Comput Vis Media (Beijing)
DOI: 10.1007/s41095-021-0231-y
sha: f08698409474e47a6d710042bd992b65fde27597
doc_id: 1017695
cord_uid: 9qgzz4er

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. [Image: see text] ELECTRONIC SUPPLEMENTARY MATERIAL: Supplementary material is available in the online version of this article at 10.1007/s41095-021-0231-y.

The automated placement of labels on maps and other visualizations is a long-standing goal of information visualization. Human map makers and designers can solve the labeling problem quite well, but an automated approach is often required for large dynamic data sets of visualizations.

Most optimization problems related to label placement are NP-hard, but several heuristics with different objectives and underlying principles have been proposed over the years. In this paper, we focus on the problem of boundary labeling, that is, the labels are placed around the perimeter of the visualization and connected to their corresponding features (e.g., points or image features) with leaders (i.e., lines). A drawback of boundary labeling is that the associations between features and their labels are not immediately apparent nor easy to follow: one has to trace the leader across the visualization to find the corresponding label. In the literature, automated dynamic label placement is often split into two main approaches, each of which has its features and drawbacks: • Global optimization with previous frames. The global optimization originally used into static label layout problem. Several aspects are taken into consideration, including relative position to its features, non-overlapping to other features, and other aesthetic rules, assuring a balanced layout without overlapping after optimization. For dynamic labeling, a common extension is optimization incorporating the label positions in previous frames. This strategy is global optimization only in spatial and NOT in temporal domain, so as to be in a dilemma in optimization occasionally. A more sophisticated approach is optimization in both spatial and temporal domain so that labels can adjust their trajectories ahead of time to remain moving smoothly. However, the problem is quite easy to formulate and quite difficult to optimize for all labels at all frames together. Moreover due to the trade off between temporal coherence and all other aspects in optimization neither cannot guarantee temporal coherence especially in consecutive frames. • Forced directed methods. All labels are moving according to the resultant force caused by all neighboring features and labels. Due to the forces calculated inverse to their relative distances, forced directed methods are inherently retaining smoothness of label movements. However, the resultant force only considers neighboring situations, and may cause interleaving and sudden changes if the labels have not been carefully places initially. In this paper, we propose a novel approach for solving the labeling problem in hybrid optimization. We define joint set as the subset of the features who influence the label layout of others in the set. We extract the joint sets from spatial and temporal domain, and layout relative labels with global optimization in descending order of the complexity of the joint sets. Inbetween two joint sets, the force directed method is applied with initial positions of two joint sets. And thus we achieve the good initial layout on key regions and key frames, and move the labels according to resultant forces to achieve smoothness of the trajectories inbetween. In force directed framework, we also introduce a temporal force that copes with features with high speed relative to neighbors. The temporal force is calculated by the position and speed and added to the resultant forces so that the labels can elude ahead of time and retain smooth movements.

We also proposed a strategy to extend our hybrid framework to streaming data. By prediction of all feature trajectories, we estimate the joint sets in the future, so that the current layout can be optimized globally and our hybrid framework can be applied for the current layout.

Our main contributions are: • A hybrid optimization method for dynamic label layout is proposed by cluster layout propagation to achieve smooth changing results. • A temporal force is introduced to cope with features with high speed relative to neighbors so that the labels can elude ahead of time and retain smooth movements. • The proposed layout method is extended to streaming data by prediction to avoid sudden changes.

Automatic label layout has been an active research area for decades, so a comprehensive review of all related work is beyond the scope of this paper. We focus on highlighting major developments and the works closely related to our approach. We refer the reader to the bibliography by Wolff and Strijk [1] for an extensive list of published heuristics and to the survey by Van Garderen [2] for a detailed literature review.

The labeling problem can be applied to geographical maps, technical maps, or any other kind of diagrams, such as 3D scene, graph, etc. Labels are not necessarily textual labels; they can also be graphical representations of any form. The label can be placed internally or adjacent to its feature sometimes including leaders. Such problem has been studied extensively. It is formulated as an optimization with several guidelines for "good" label placement [3] and non-overlapping constraints, which is known as an NP-Hard problem. Thus many approximations and heuristic approaches are proposed including integer linear programs [4] , expert systems [5] , simulated annealing [6] , and combined optimization [7] . In recent years, Meng et al. [8] introduced a clutter model to prevent visual clutter in the layout. Lhuillier et al. [9] proposed a versatile density-based approach to label placement by applying kernel density estimation to the input features. These approaches presented a well organized layout result in the global scale, and however those optimization approaches did not take dynamic layout into consideration. In this paper, we proposed a hybrid solution taking the both advantages of global optimization [6] on global arrangement and forced based approaches on local smoothing together.

A common extension of the static label layout into dynamic labels is global optimization not only in spatial domain but also in temporal domain. However, the problem is quite easy to formulate and quite difficult to optimize for all labels at all frames together. A reasonable solution is optimization frame by frame with the initial position of labels in previous frame [10] [11] [12] . As the temporal coherence is only one aspect of all constraints, the trade off between temporal coherence and all other aspects in optimization cannot guarantee temporal coherence especially in consecutive frames.

Force-based approach is another branch for label layout. A force-based approach was first presented by Hirsch [13] . He uses a gradient-driven heuristic to label point features. Labels are placed on a circle around their corresponding features. To resolve conflicts, vectors between overlapping labels are computed based on the intersection area. As a single label can collide with multiple other annotations, the sum of all its vectors guides its movement, thus improving the global labeling layout. Attractive forces pull labels to their point feature, while repelling forces push labels away from other features. Thus, step by step, the map layout converges towards a final labeling state through a gradient descent method. As far as we know, the forces are mainly consider the influence within spatial domain. In this paper, we proposed a temporal force which can influence over time, so as to cope with features with high speed relative to neighbors, so that the labels can elude ahead of time and retain smooth movements.

Force-based approaches [14] [15] [16] are inherently preserve local smoothness for dynamic label movements when the forces are defined as smooth function. So that force-based approaches can be directly extended to dynamic label layout with temporal coherence enforcement. However, the resultant force only considers neighboring situations, and may cause interleaving and sudden changes if the labels have not been carefully places initially. To fully use the feature of local smoothness, and cope with the sudden change problem of force-based methods, we incorporated global optimization to achieve good initial place of labels. A hybrid approach is presented by Stadler et al. [17] . They obtain an initial placement with the help of image processing. Then, iterative forces improve the chosen labeling positions.

Our method focuses on high-density and highdynamic data visualization. Taking the point-feature label placement (PFLP) as an example [6] , we solve both the problem of static layout optimization and dynamic movement smoothing of labels by spatiotemporal decoupling. Two key frameworks are performed in our method: global spatiotemporal joint optimization and label motion planning based on force traction.

In the process of this framework, we first locate all joint sets from spatial and temporal as is shown in Fig. 1 (a), and sort them in descending order of the complexity. There are two joint sets {C 1 , C 2 } in this example. Then we perform static label placement on the frame where the joint sets are located, and the position constraints of labels transmit according to the order of the joint sets. Finally, the initial label layout of the first frame and the label position constraint of each joint set are obtained. The entire workflow is illustrated in Fig. 1 .

According to the definition of the PFLP problem in Ref. [6] , one or zero of the candidate positions for placing a label have to be chosen for each feature, such that the value of the objective function of the resulting labeling is minimal. Following the labeling quality rules proposed in Ref. [18] , our optimization objective function is as follows:

which consists three energy terms: overlap between labels and labels and overlap between labels and features E overlap , the relative position of a label to a feature E position , and aesthetics factors E aesthetics .

where N is the number of feature. As is shown in Fig. 2 , O i,j is the area of overlap between label i and label j, and P i,j is the area of overlap between label i and feature j. W label−label and W label−feature are the corresponding weights.

where θ i is the angle of the label in the corresponding feature-centered polar coordinate system as shown in Fig. 3 (a). Δ(θ i ) is to determine which quadrant the label is in. W orient has four values representing the priorities of the different quadrants. r i is the distance between the label and feature, and W distance is the corresponding weight.

where X i is the area of the label out of the axes as shown in Fig. 3 (b), and I i is the number of leader line intersections. W out−of−axes and W intersect are the corresponding weights.

Since PFLP is NP-complete, we adopt the heuristics search to find good solutions in acceptable time. Based on the algorithm evaluation in Ref. [18] , simulated annealing algorithm is applied to solve the objective function. The annealing schedule is chosen according to Ref. [6] . Figure 1 shows an example to illustrate how the label position constraint transmits. Five features (F 1 , F 2 , F 3 , F 4 , F 5 ) and their corresponding motion paths are marked in different colors (red, green, purple, blue, yellow, respectively). There are two joint sets

For the maximum joint set, we use the objective function E static which is proposed in Section 3.1.1 to layout the labels, and then we transmit this layout as position constraint to the next joint set based on the complexity descending order. The objective function is formulated as follows:

where E static is the static label placement energy term, and E constraint is the label position constraint transmitted from last joint set, which is formulated as

where (r, θ) is the coordinate value of the label in the corresponding feature-centered polar coordinate system as is shown in Fig. 3 (a). (r p , θ p ) represents the current joint set, and (r l , θ l ) represents the last joint set. We only calculate the features which occur in both joint sets. In the above-mentioned example in Fig. 1 , only F 2 and F 4 need to calculate this term in the second joint set C 2 . After traversing all joint sets, every feature in joint sets will obtain a position constrain at the first frame. As for features where no path intersection occurs such as F 5 , a specified initial label position will be assigned.

In this framework, we focus on the movement of the labels, and both smoothness and readability are considered. After we obtain the initial layout constraints on key regions and key frames (Section 3.1), the force directed method is adopted to move the labels according to resultant forces to achieve smoothness of the trajectories inbetween [19] . In addition, to further improve readability, we also introduce a temporal force that copes with features with high speed relative to neighbors.

In this paper, we adopt a free annotation type to display label placement [20] . A free label i is positioned by an optional offset from its corresponding feature i as illustrated in Fig. 3(a) . Following the force descriptions in Ref. [19] , we define four basic forces to maintain the smoothness and readability of label movement as is shown in Fig. 4 .

Label-label collision force: To avoid overlap between labels, the first force introduced is repulsive force between labels. Since all labels are rectangles oriented in the same axis, we simplify the calculation of the distance between label i and label j:

where p is the center position of a label and s is the extent of a label. A label-label collision happens when d label−label is less than 0. The formula of labellabel collision force is where D label−collision is maximum distance the force will act; an illustration of this force can be seen in Fig. 4(a) . Label-feature collision force: In this paper, each point feature has a specific size. Hence, repulsive forces between labels and features are also needed to prevent them from collision. Similar to labellabel collision force, the distance between label i and feature j is

where l is the center position of a feature and r is the extent of a feature. The formula of label-feature collision force is as follows:

where D feature−collision is maximum distance the force will act. Feature-label pulling force: To ensure the label stay close to the corresponding feature, a pulling force is needed. As is shown in Fig. 4(b) , this force proportional to the distance, which is formulated as follows:

where D pull is the minimum distance at which the force will be acted. The force acts only if

Friction force: To stabilize the movement of the labels, a friction force is acted to each label which is formulated as

where c friction is the friction coefficient, and V label and V feature are the velocities of labels and features respectively. This force has a dampening effect on the labels except when they are moving in the same direction as their corresponding features.

In allusion to high density and hybrid high dynamics data, two more forces are introduced to enhance the visualization performance.

Space constraint force: To reduce the label movement chaos caused by the intersections of feature motion paths, a space constraint force is acted to plan the movement path of a label as shown in Fig. 5 . The formulation of this force is as follows:

where p is the constraint position of label at upcoming feature joint set which is described in Section 3.1. If there is no new upcoming intersection, the constraint will remain the same as the previous one or the original one.

Time constraint force: The features of hybrid dynamics data have very different velocities. The basic forces mentioned in Section 3.2.1 are unable to deal with the overlap under such a large velocity difference. Therefore, we introduce a time constraint force which is acted from where the features will be in the future. As is shown in Fig. 6 , V j feature is much bigger than V i feature . l j is the relative future position of the feature j, which is calculated as follows:

where δt is the time of the feature movement to the future. The time constraint force is formulated as

After all forces are calculated for all labels, we combine them into one resultant force acting on each label. To weigh the forces against each other, we introduce a constant scaling factor for each force. The summarized force for label i is

We introduce a virtual mass m i for label i. The current acceleration a i is computed by Newton's second law: a i = f i resultant /m i The time interval between successive frames is Δt, and the new velocity v i can be calculated by Euler's integration method:

v

In this paper, we take virtual mass of labels equal to 1.

We make two different implementations to evaluate the performance of our dynamic label layout method on both non-real-time and real-time data. They are both written in Python, and are only based on CPU calculations. Both of them use epidemiological data on COVID-19 in China. However, the first implementation used the data as recorded video, and the second one used the data as real-time video stream. In order to better visualize the epidemic data, we make several improvements to the visual elements. As is shown in Fig. 7 , we extend the point feature to a ring feature to convey more information about the epidemic. We encode the cumulative number of confirmed cases of a province as the outer radius of the feature (red line in Fig. 7) . The red-green ratio of the ring represents the ratio of the cumulative number of deaths to the cumulative number of cures. In addition, with so many provinces to display, the total area of all labels and features will be larger than the screen. We have to selectively hide some features and labels. Thus, we introduce a feature priority evaluation system for choosing which labels to be hidden, and the priority of a feature can be calculated as follows:

where R death is the ratio of death, R cure is the ratio of cure, N confirmed is the cumulative number of confirmed cases, and ω is the corresponding weight which allows the user to control tendency of priority determination. The lower priority labels or features will be hidden when overlapping with higher priority labels, but if features with different priorities are overlapping, the lower priority features do not need to be hidden. Video result demonstrations of the implementations can be found in the Electronic Supplementary Material (ESM).

The first implementation follows the steps described in Section 3. In the first step, we calculate the initial label positions and the position constraints at joint sets. In the second step, the priority of features is calculated to determine whether labels and features need to be hidden or not. In the third step, we calculate the resultant force for each label to guide the movement. As described in Section 3.2.3, there are six forces acting on each label. However, after feature priority is introduced, we hope that the movement of the labels with higher priority is more pronounced, and the lower priority labels will give way to the higher priority labels during movement. When two labels are displayed and label i has a higher priority than label j , the label collision force f i,j label−collision will not be applied to label i . But, the opposite forces f j,i label−collision are still applied to label j . In another case, when label i is displayed and label j is hidden, f i,j label−collision is not applied to label i and the opposite forces f j,i label−collision are still applied to label j .

The second implementation is for real-time video stream. Since we are unable to obtain the full path of the features, our hybrid optimization method needs a small modification. In the first step, we can only use the existing joint sets to calculate the label position constraints. In order to enable the labels to have a preperception to the upcoming joint set, we predict the feature motion based on the existing data by using an exponential curve prediction model [21] . As is shown in Fig. 8 , the entire workflow is slightly modified from which is described in Section 3.1. For the existing part, we apply static optimization following Section 3.1, and the initial label positions and the position constraints of joint set (C 1 {F 1 , F 2 }) can be calculated. For the predicted part, if a new intersection (C 2 {F 1 , F 2 , F 3 }) occurs, the static optimization of this joint set will be constrained by the maximum intersection in the existing data. The next two steps follow the flow of the first implementation, which is converting the label position constraint into force traction to guide the label movement.

We implement the hybrid optimization method on the epidemiological data on COVID-19 in China. Figure 9 shows the visualization results of four different frames of the epidemic data. The ringfeatures represent provinces of China, which are placed based on their new diagnosis (y-axis) and the cumulative confirmed (x-axis). Epidemic data of 34 provinces (some provinces in Fig. 9 are hidden due to low priority) from January 21 to April 10 are included in this experiment. This figure shows effectiveness of our hybrid optimization on static label placement, in which both readability and aesthetics are maintained. The dynamic video visualization result can be found in the ESM, which shows effectiveness of our method on label movement smoothness. To verify and evaluate the effectiveness of our hybrid optimization method on smoothness preserving, we compare the results produced by the force-based label placement method [19] with and without spatiotemporal force constraint. The forcebased label placement method can place labels both with smoothness and readability for dynamic data, and thus choosing this label placement method as a base can reflect the effectiveness of our spatiotemporal force constraint in these two aspects. Here we use the force-based label placement method with the parameters mentioned in Ref. [19] . To compare the performance of methods on high density and hybrid high dynamics data, the comparisons are performed on the epidemic data of China.

As shown in Fig. 10 , we compare the partial layout results on the epidemic data at four different frames. In the video sequence, JiangSu first approaches and intersects HeNan, and then HeNan approaches FuJian. Basic forces without space constraint force are shown in Fig. 10(a) . Due to the absence of initial position constraints and early awareness of upcoming intersection, the motion path of the label appears chaotic and the leads are too long (in order to escape overlapping), which greatly reduces the readability of labels. Oppositely, the path of the label can be planned rationally with space constraint force, and initializing the label position can also effectively improve the label movement and reduce the visual confusion caused by unreasonable paths. Complete video of the comparison experiments can be found in the ESM. Figure 11 shows the comparison results of basic forces with or without the time constraint force. Partial features of epidemic data are displayed in this experiment. As is shown in Fig. 11 , the movement velocity of HeBei is much bigger than other features. In a situation that there is a huge difference in velocity between the features, the basic forces cannot timely adjust the label's motion trajectory to avoid label overlap. It is obviouse that in Fig. 11 (a), with HeBei approaching quickly, the label of HeiLongJiang cannot elude the feature in time, so that the lead line has to be stretched, which seriously affects the readability. However, as shown in Fig. 11(b) , the time constraint force can make the label perceive the approaching feature in advance and adjust the label position in advance, so as to make the label movement more reasonable and smooth. The comparison video also can be found in the ESM. Figure 12 shows the performance comparison of our proposed method on real-time data stream. Two example provinces are FuJian (purple) and GuangXi (Green). The dotted line represents the movement trajectory of the province based on the real data, while the solid line represents the movement trajectory of the province based on the prediction as described in Section 4.2. The deviation of tag trajectory and the result of tag layout show that our method can carry out automatic layout of moving labels on the real-time data stream of real data.

In order to evaluate the performance of our method quantitatively, we compare the results produced by static optimization method [6] , force-based method [19] , and our hybrid optimization method.

The static optimization method can place labels with both rationality and readability, and the force-based label placement method can maintain the smoothness of label movement. Thus we compare these labeling methods to reflect the effectiveness of our hybrid optimization in aforementioned three aspects. The comparisons are performed on epidemiological data on COVID-19 in China.

As shown in Table 1 , we compared the results in the following aspects: the overlap between labels and labels and overlap between labels and features S Overlap , the distance from the label to the corresponding feature S Position , the number of leader line intersections S Aesthetics , and the relative position changes of labels between adjacent frames S Smoothness .

The first three are based on the static label layout quality rules [18] , which mainly evaluates the quality of the label layout in each frame, including rationality and readability. The calculation methods are similar to the calculation of energy terms described in Section 3.1.1 without adjustment weights. The calculation formulas are as follows:

where N is the number of features, and M is the number of frames. As is shown in Fig. 2 , O i,j is the area of overlap between label i and label j, and P i,j is the area of overlap between label i and feature j.

The unit of overlap is pixel 2 .

where r i is the distance between the label and feature as shown in Fig. 3(a) . The unit of distance is pixel.

where I i is the number of leader line intersections. The last item evaluates the smoothness of label movement. We calculate the relative position changes of labels between adjacent frames. In the featurecentered polar coordinate system, the relative position changes include two parts (S θ Smoothness and S r Smoothness ). The calculation formula is as follows:

where θ i is the angle of the label in the corresponding feature-centered polar coordinate system as shown in Fig. 3(a) . The unit is degree.

where r i is the distance between the label and feature, and the unit is pixel.

According to the data in Table 1 , the average overlap area and label-feature distance of static optimization method are less than the other two methods' results. Although as a trade off, the number of lead line intersections increases. The overall quality of label layouts produced by static optimization method is slightly better than those produced by force-based method. However, the static optimization method has a poor performance in the smoothness of label movement, although we add the change of label position between frames as an energy term to the objective function. Compared to static optimization method, the results produced by force-based method are much better in terms of smoothness. However, when dealing with high density and hybrid high dynamics data, the quality of label layouts produced by force-based method with basic forces becomes poor because of lacking good path planning and decoupling of high differential dynamic features. The hybrid optimization method proposed in this paper can effectively solve the confusion of label path caused by dense data intersection, obtain better initial label position through global optimization, and reasonably plan the label path through joint sets decoupling. The quality of label layouts is comparable to that produced by static optimization method. Further more, the introduced time force can effectively solve the problem of label overlap caused by the huge difference of feature speed. In terms of smoothness of label movement, hybrid optimization method is also better than the other two methods.

Three more experiments of real-world data are shown in the ESM. Additional screen shots are found in Appendix B.

We have proposed an effective hybrid optimization method for dynamic label layouts. The hybrid framework consists of global spatiotemporal joint optimization and dynamic label movement planning. In global spatiotemporal joint optimization, the initial label positions and position constraints of joint sets are calculated. In dynamic label movement planning, the position constraints are converted into forces to guide the label motion, and four basic forces and a temporal force are introduced to maintain the smoothness of label movement. Experiments on realworld datasets show that our hybrid optimization dynamic labeling method is able to produce clear and legible label layouts on each frame and smooth label movements in the dynamic process.

Our current hybrid optimization dynamic labeling framework needs to be improved in some respects in the future. First, the parameter settings should be optimized. We aim at designing a adaptive parameter selection method, which can greatly accelerate the process of adjusting parameters. Second, to achieve real-time labeling, we need an efficient computation of forces between labels. The GPU can be used for parallel processing of these tasks [20] .

These two tables presents all parameters for static optimization label layout method and the hybrid optimization dynamic label layout method. 

Below are illustrations of the dynamic datasets labeled with hybrid optimization method. All 

The map-labeling bibliography

Pictures of the past: Visualization and visual analysis in archaeological context

Positioning names on maps

Integer programming applied to the map label placement problem

An expert system for the automatic placement of names on a geographic map

An empirical study of algorithms for point-feature label placement

A combinatorial framework for map labeling

Clutteraware label layout

Density-based label placement

View management for virtual and augmented reality

Real-time video annotations for augmented reality

Dynamic label placement for forensic case visualization

An algorithm for automatic name placement around point data

Automated positioning of annotations in immersive virtual environments

Temporally coherent real-time labeling of dynamic scenes

Hedgehog labeling: View management techniques for external labels in 3D space

A practical map labeling algorithm utilizing morphological image processing and force-directed methods

Automatic 2D label placement

Force-based label placement for dynamic data

Temporally coherent real-time labeling of dynamic scenes

Improved prediction model of modified exponential curve

The authors would like to thank all reviewers for their thoughtful comments. This work was supported by the National Key Technology R&D Program 

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction 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.