Dispersion for the point-feature cartographic label placement problem

The point-feature cartographic label placement problem (PFCLP) is a NP-Hard problem arising in design of maps and other graphic objects. For the sake of a better map legibility it is important to avoid overlaps in the process of labeling. This paper examines the PFCLP in the legibility context and proposes a dispersion approach for the problem. It is considered that when all points must to be labeled and overlaps are inevitable, the map can be more readable if overlapping labels are placed more distant from each other. The PFCLP is modeled as a dispersion problem on two mathematical formulations based on binary integer linear programming. Computational tests have provided good results on several generated instances.     

A greedy randomized adaptive search procedure for the point-feature cartographic label placement

The point-feature cartographic label placement problem (PFCLP) is an NP-hard problem, which appears during the production of maps. The labels must be placed in predefined places avoiding overlaps and considering cartographic preferences. Owing to its high complexity, several heuristics have been presented searching for approximated solutions. This paper proposes a greedy randomized adaptive search procedure (GRASP) for the PFCLP that is based on its associated conflict graph. The computational results show that this metaheuristic is a good strategy for PFCLP, generating better solutions than all those reported in the literature in reasonable computational times.     

Lagrangean relaxation with clusters for point-feature cartographic label placement problems

This paper presents two new mathematical formulations for the point-feature cartographic label placement problem (PFCLP) and a new Lagrangean relaxation with clusters (LagClus) to provide bounds to these formulations. The PFCLP can be represented by a conflict graph and the relaxation divides the graph in small subproblems (clusters) that are easily solved. The edges connecting clusters are relaxed in a Lagrangean way and a subgradient algorithm improves the bounds. The LagClus was successfully applied to a set of instances up to 1000 points providing the best results of those reported in the literature.     

A hybrid data mining heuristic to solve the point‐feature cartographic label placement problem

A clean map visualization requires the fewest possible overlaps and depends on how labels are attached to point features. In this paper, we address the cartographic label placement variant problem whose objective is to label a set of points maximizing the number of conflict‐free points. Thus, we propose a hybrid data mining heuristic to solve the point‐feature cartographic label placement problem based on a clustering search (CS) heuristic, a state‐of‐the‐art method for this problem. Although several works have investigated the combination of data mining and multistart metaheuristics, this is the first time data mining has been used to improve CS and simulated annealing based heuristics. Computational experiments showed that the proposed hybrid heuristic was able to reach better cost solutions than the original strategy, with the same time effort. The proposed heuristic also could find almost all known optimal solutions and improved most of the best results for the set of large instances reported so far in the literature.     

Tabu Search Heuristic for Point-Feature Cartographic Label Placement

The generation of better label placement configurations in maps is a problem that comes up in automated cartographic production. The objective of a good label placement is to display the geographic position of the features with their corresponding label in a clear and harmonious fashion, following accepted cartographic conventions. In this work, we have approached this problem from a combinatorial optimization point of view, and our research consisted of the evaluation of the tabu search (TS) heuristic applied to cartographic label placement. When compared, in real and random test cases, with techniques such as simulated annealing and genetic algorithm (GA), TS has proven to be an efficient choice, with the best performance in quality. We concluded that TS is a recommended method to solve cartographic label placement problem of point features, due to its simplicity, practicality, efficiency and good performance along with its ability to generate quality solutions in acceptable computational time.     

A new mathematical model and a Lagrangean decomposition for the point-feature cartographic label placement problem

This paper proposes a 0-1 integer linear programming model for the point-feature cartographic label placement problem based on labeling of the largest number of free labels. In addition, one non-trivial valid inequality is presented to strengthen this proposed model. Even with the strengthened model, a commercial solver was not able to solve a representative sample of known instances presented in the literature. Thus, we also present a Lagrangean decomposition technique based on graph partitioning. Our added approaches established optimal solutions for practically all the used instances and the results significantly improved the ones presented in recent studies concerning the problem.     

Incremental labeling in closed-2PM model

We consider an incremental optimal label placement in a closed-2PM map containing points each attached with a label. Labels are assumed to be axis-parallel square-shaped and have to be pairwise disjoint with maximum possible length each attached to its corresponding point on one of its horizontal edges. Such a labeling is denoted as optimal labeling. Our goal is to efficiently generate a new optimal labeling for all points after each new point being inserted in the map. Inserting each point may require several labels to flip or all labels to shrink. We present an algorithm that generates each new optimal labeling in O(lgn+k) time where k is the number of required label flips, if there is no need to shrink the label lengths, or in O(n) time when we have to shrink the labels and flip some of them. The algorithm uses O(n) space in both cases. This is a new result on this problem.     

Dynamic map labeling

We address the problem of filtering, selecting and placing labels on a dynamic map, which is characterized by continuous zooming and panning capabilities. This consists of two interrelated issues. The first is to avoid label popping and other artifacts that cause confusion and interrupt navigation, and the second is to label at interactive speed. In most formulations the static map labeling problem is NP-hard, and a fast approximation might have O(n log n) complexity. Even this is too slow during interaction, when the number of labels shown can be several orders of magnitude less than the number in the map. In this paper we introduce a set of desiderata for "consistent" dynamic map labeling, which has qualities desirable for navigation. We develop a new framework for dynamic labeling that achieves the desiderata and allows for fast interactive display by moving all of the selection and placement decisions into the preprocessing phase. This framework is general enough to accommodate a variety of selection and placement algorithms. It does not appear possible to achieve our desiderata using previous frameworks. Prior to this paper, there were no formal models of dynamic maps or of dynamic labels; our paper introduces both. We formulate a general optimization problem for dynamic map labeling and give a solution to a simple version of the problem. The simple version is based on label priorities and a versatile and intuitive class of dynamic label placements we call "invariant point placements". Despite these restrictions, our approach gives a useful and practical solution. Our implementation is incorporated into the G-Vis system which is a full-detail dynamic map of the continental USA. This demo is available through any browser     

Particle-based labeling: Fast point-feature labeling without obscuring other visual features

In many information visualization techniques, labels are an essential part to communicate the visualized data. To preserve the expressiveness of the visual representation, a placed label should neither occlude other labels nor visual representatives (e.g., icons, lines) that communicate crucial information. Optimal, non-overlapping labeling is an NP-hard problem. Thus, only a few approaches achieve a fast non-overlapping labeling in highly interactive scenarios like information visualization. These approaches generally target the point-feature label placement (PFLP) problem, solving only label-label conflicts. This paper presents a new, fast, solid and flexible 2D labeling approach for the PFLP problem that additionally respects other visual elements and the visual extent of labeled features. The results (number of placed labels, processing time) of our particle-based method compare favorably to those of existing techniques. Although the esthetic quality of non-real-time approaches may not be achieved with our method, it complies with practical demands and thus supports the interactive exploration of information spaces. In contrast to the known adjacent techniques, the flexibility of our technique enables labeling of dense point clouds by the use of nonoccluding distant labels. Our approach is independent of the underlying visualization technique, which enables us to demonstrate the application of our labeling method within different information visualization scenarios.     

一种新的电子地图注记算法——格网法

提出一种避免冲突和压盖的电子地图标注框架。通过格网号描述所有注记位置,把点、线、面3种要素的注记有机统一在相同框架下,使已标注的要素和未标注的要素关联起来。该格网地图注记算法简洁高效,具有良好的实时性和标注效果,能满足高质量地图注记的要求。     

地图文本注记问题的遗传算法求解

针对地理信息系统中对图形进行文本注记难,大多数已知工具都产生一定数量的注记重叠并且需要人工调节的问题,采用遗传算法解决注记冲突.综合注记信息与线状图形信息的特征,提出了以重叠注记构造位串编码,采用沿折线随机游走的方式构造变异算子,并考虑两个目标,一个是在注记中避免重叠,另一个是提高注记放置的美术性,采用梯形模糊数实现美学度量.初步测试表明,所提算法在快速文本注记和提高美学度上非常有效.     

有遮挡三维草图的标注完备集

线型标注是三维草图语义描述的基本方法。已有工作大都应用三维实体精确投影图所产生的标号集来标注规整后的草图,没有实现真正意义上的三维草图标注。研究积木世界三维草图的标注问题,提出了一个有遮挡三维草图标注的标号集,并证明了其完备性。该标号集能够直接标注草图而无需对草图进行规整,从而实现了真正意义上的三维草图标注,为三维草图语义描述提供了一种新思路。     

Labeling Points with Weights

Annotating maps, graphs, and diagrams with pieces of text is an important step in information visualization that is usually referred to as label placement. We define nine label-placement models for labeling points with axis-parallel rectangles given a weight for each point. There are two groups: fixed-position models and slider models. We aim to maximize the weight sum of those points that receive a label. We first compare our models by giving bounds for the ratios between the weights of maximum-weight labelings in different models. Then we present algorithms for labeling n points with unit-height rectangles. We show how an O(n\log n)-time factor-2 approximation algorithm and a PTAS for fixed-position models can be extended to handle the weighted case. Our main contribution is the first algorithm for weighted sliding labels. Its approximation factor is (2+\varepsilon), it runs in O(n ²/\varepsilon) time and uses O(n/\varepsilon) space. We show that other than for fixed-position models even the projection to one dimension remains NP-hard. For slider models we also investigate some special cases, namely (a) the number of different point weights is bounded, (b) all labels are unit squares, and (c) the ratio between maximum and minimum label height is bounded.     

Labeling Points with Weights

Annotating maps, graphs, and diagrams with pieces of text is an important step in information visualization that is usually referred to as label placement. We define nine label-placement models for labeling points with axis-parallel rectangles given a weight for each point. There are two groups: fixed-position models and slider models. We aim to maximize the weight sum of those points that receive a label. We first compare our models by giving bounds for the ratios between the weights of maximum-weight labelings in different models. Then we present algorithms for labeling n points with unit-height rectangles. We show how an O(n\log n)-time factor-2 approximation algorithm and a PTAS for fixed-position models can be extended to handle the weighted case. Our main contribution is the first algorithm for weighted sliding labels. Its approximation factor is (2+\varepsilon), it runs in O(n ²/\varepsilon) time and uses O(n/\varepsilon) space. We show that other than for fixed-position models even the projection to one dimension remains NP-hard. For slider models we also investigate some special cases, namely (a) the number of different point weights is bounded, (b) all labels are unit squares, and (c) the ratio between maximum and minimum label height is bounded.     

Optimal point removal in closed-2PM labeling

An optimal labeling where labels are disjoint axis-parallel equal-size squares is called 2PM labeling if the labels have maximum length each attached to its corresponding point on the middle of one of its horizontal edges. In a closed-2PM labeling, no two edges of labels containing points should intersect. Removing one point and its label, makes free room for its adjacent labels and may cause a global label expansion. In this paper, we construct several data structures in the preprocessing stage, so that any point removal event is handled efficiently. We present an algorithm which decides in O(lgn) amortized time whether a label removal leads to label expansion in which case a new optimal labeling for the remaining points is generated in O(n) amortized time.     

含缺失标签的大规模多标签分类算法

在对大规模多标签数据进行人工标注时极易产生标签的缺失。现有算法大多利用被所有实例共享的全局标签相关性来解决该问题,即对不同实例而言,标签之间的相关性是相同的。然而在实际应用中,不同实例的标签相关性并非完全相同,此时采用局部方式获取的标签相关性将更加准确。因此,本文提出一种基于局部标签相关性的解决方法。该方法利用局部标签相关性来恢复缺失标签,利用低秩矩阵分解技术来构造适用于大规模数据的分类器。此外,为了加快模型的训练,该方法将这两个过程融合到一个统一的框架中,并采用迭代优化的方式进行求解。大量实验结果表明,该方法在预测准确度上至少比现有算法高2个百分点,在训练速度上至少提升5个百分点。     

基于自适应稀疏邻域重构的无监督主动学习算法

在很多信息处理任务中,人们容易获得大量的无标签样本,但对样本进行标注是非常费时和费力的。作为机器学习领域中一种重要的学习方法,主动学习通过选择最有信息量的样本进行标注,减少了人工标注的代价。然而,现有的大多数主动学习算法都是基于分类器的监督学习方法,这类算法并不适用于无任何标签信息的样本选择。针对这个问题,借鉴最优实验设计的算法思想,结合自适应稀疏邻域重构理论,提出基于自适应稀疏邻域重构的主动学习算法。该算法可以根据数据集各区域的不同分布自适应地选择邻域规模,同步完成邻域点的搜寻和重构系数的计算,能在无任何标签信息的情况下较好地选择最能代表样本集分布结构的样本。基于人工合成数据集和真实数据集的实验表明,在同等标注代价下,基于自适应稀疏邻域重构的主动学习算法在分类精度和鲁棒性上具有较高的性能。     

一种新的二值图像连通区域准确标记算法

在分析已有区域标记算法的基础上,提出了一种新的二值图像连通区域准确标记算法。顺序扫描和标记二值图像的各个像素点,准确判断标记过程中出现的标记冲突,并建立标记冲突的模型,在算法中增加回溯扫描算法,消除标记冲突引起的标记误差。实验证明该算法可以准确标记出各种形状的连通区域,和已有算法相比扫描重复率低、运行准确、速度快,具有很好的应用前景。     

Real-time map labelling for mobile applications

It is essential to label roads, landmarks, and other important features on maps for mobile applications to help users to understand their location and the environment. This paper aims to examine real-time map labelling methods suitable for the small screen on mobile devices. A slider method with a continuous search space was proposed to sequentially label both line and point features. The method starts with defining a range box for possible locations of the label. Then a search is performed, and the range box is reduced, if there are any cartographic objects that overlap the range box. Finally, the label is placed, at the best possible position in the reduced range box according to normal cartographic preferences, where it does not obscure any cartographic object. We implemented this method in a Java environment using the open source library JTS Topology Suite. A case study showed sound cartographic results of the labelling and acceptable computational efficiency.     

置信度加权在线序列标注算法

序列标注问题是自然语言处理领域的基本问题之一. 序列标注任务是将连续输入的不定长序列, 标注成连续等长的标签序列. 在在线序列标注方法的基本框架下, 针对序列标注任务的特征稀疏特性, 采用置信度加权分类算法思想, 提出了一种新的线性判别式在线序列标注方法---置信度加权在线序列标注算法. 该方法对每个特征权值参数引入一个概率置信度, 取得了优于其他相关算法的性能. 在中文分词, 中文名实体识别以及英文组块分析等问题上, 验证了本文方法的有效性.