一种重叠容忍的标签放置方法

摘要: 本发明属于计算机图形学与可视化,特别是涉及一种重叠容忍的标签放置方法。背景技术:1、在可视化技术领域中,标签放置是指为图像或地图上的图形对象分配标签,并确定标签...
一种重叠容忍的标签放置方法

本发明属于计算机图形学与可视化,特别是涉及一种重叠容忍的标签放置方法。

背景技术:

1、在可视化技术领域中,标签放置是指为图像或地图上的图形对象分配标签,并确定标签文本在该图形对象周边最优位置的过程,其目的是帮助用户快速定位、识别并理解这些图形对象。目前,最常用的传统方法是基于严格无重叠约束的标签放置优化算法。该类算法首先定义标签候选位置模型,然后采用模拟退火、贪心算法等优化策略,搜索满足零重叠条件的标签位置组合。然而,传统方法所依赖的“完全无重叠”约束在高密度或空间受限场景下面临严重局限:由于可用空间不足,大量标签无法被放置,导致显著的信息丢失。

2、因此,需要一种能够在保证标签可识别性的前提下容忍一定程度重叠的标签放置方法,以提升高密度场景下的标签放置数量与空间利用率。

技术实现思路

1、本发明的目的在于提供一种重叠容忍的标签放置方法,解决现有技术中严格无重叠约束导致高密度或空间受限场景下标签放置数量不足、信息丢失严重的问题,实现扩大求解空间、提升标签放置数量与空间利用率,并在保证标签可识别性的前提下容忍部分重叠。

2、本发明所采用的技术方案是,一种重叠容忍的标签放置方法,包括以下步骤:

3、步骤s1:针对可容忍重叠的标注场景,进行标签可辨识性建模、标签可识别性建模,构建目标函数与约束条件;

4、步骤s2:计算所有标签的尺寸信息并建立空间索引;

5、步骤s3:基于网格密度的计算策略进行标注顺序计算;

6、步骤s4:采用贪心标注策略,按步骤s3的标注顺序依次处理点要素,对每个点要素的候选位置按优先级依次进行有效性检验,若候选位置有效则完成标签放置并更新空间索引,否则尝试下一个候选位置;若该点要素的所有候选位置均无效,则跳过该点要素;

7、步骤s5:在所有点要素完成遍历与标注处理后,输出每个点要素所选标签的放置位置,将不满足可辨识性与可识别性约束的标签记为未放置,最终生成满足可辨识性与可识别性要求的点要素标签放置方案。

8、进一步地,所述步骤s1具体包括:

9、采用固定位置模型,即8候选位置模型作为候选位置模型约束,并依据标签与点要素之间的无重叠约束构建基础几何约束;

10、基于两项准则进行形式化描述:准则1为:一个单词只有在其所有字母均可被准确识别时,才能被准确识别;准则2为:某个字母的遮挡比例不超过某一阈值时,该字母仍可被准确识别;引入字母级与标签级的可识别性度量,采用对每个字母分别进行的轴对齐包围盒近似;定义标签级可识别性函数作为硬性约束;

11、在满足候选位置约束和无重叠约束的前提下,建立以最大化可识别标签数量为优化目标的目标函数,并通过将满足字母级识别阈值的标签重叠纳入求解空间,形成双层约束机制。

12、进一步地,步骤s2中,所述计算所有标签的尺寸信息具体包括:

13、定义标签的总宽度为所有字母宽度之和、整体垂直覆盖区间为所有字母垂直区间的最小包围区间,、的公式分别为:

14、

15、其中,为标签中字母的索引变量;为标签的字母数量;为字母的宽度;为字母的垂直坐标区间;

16、字母的坐标位置形式化表示为:

17、

18、其中,为标签文本基线起点坐标;为字母索引变量;为字母的宽度;、分别为字母的上伸部高度、下伸部深度;为字母相对位置坐标。

19、进一步地,步骤s2中,所述建立空间索引具体包括:

20、采用两个镜像的空间哈希表,分别为点要素和已放置的标签建立空间索引;索引构建过程包括哈希函数选择与将点要素插入哈希表:

21、以全局最大标签宽度与最大标签高度分别作为空间网格的单元格尺寸;对于任意标注的中心二维笛卡尔坐标,通过哈希函数将其映射至对应的网格索引,映射过程定义为:

22、

23、其中,表示将二维笛卡尔坐标映射至离散网格索引的函数;符号表示向下取整;

24、在索引初始化阶段,仅针对待标注点要素执行插入操作:给定点要素的中心坐标及其预设的影响半径,先计算该点要素对应的矩形边界框坐标,再基于该矩形四个顶点的坐标,分别计算其在哈希网格中的所属网格索引,将该对象的坐标表示写入所有涉及的网格单元中;

25、其中,针对各网格单元内的哈希冲突,采用分离链接法进行处理:将共享同一个网格键的对象存储在同一个哈希桶中,该链表采用集合数据结构进行实例化;插入操作时,会先检索该集合中是否已包含当前对象的唯一标识符,若已包含则不再执行插入操作,若未包含则执行追加操作。

26、进一步地,所述步骤s3具体包括:

27、在完成空间索引构建后,依据要素等级及标注规则筛选生成当前视图范围内的待标注点候选集,并以该候选集为输入,采用局部网格密度排序策略确定点要素的标注优先级:首先,根据当前地图视图范围构建局部网格,统计每个网格单元内候选点要素的数量作为网格单元密度值;随后,基于密度值降序排列网格单元,密度相同的按网格编号或预设遍历顺序稳定排序;最后,对同一网格单元内的候选点要素,优先按重要性等级、显示等级或其他优先级属性降序排列,优先级相同的保持其在原始数据集中的相对顺序。

28、进一步地,步骤s4中,所述候选位置有效性检验具体包括:

29、对于待标注点要素的每个候选位置,按8位置模型的候选位置优先级依次进行有效性检验;引入两个镜像空间哈希表,两者的网格划分方式和哈希映射规则相同,分别用于存储已放置标签、点要素的轴对齐包围盒及其索引;其中,均以轴对齐包围盒作为空间索引与粗过滤的基本单元,哈希表以网格单元地址为键,以对应网格内对象索引列表为值;

30、所述有效性检验包括:查询潜在重叠对象、执行重叠检测、判定重叠是否可接受。

31、进一步地,所述查询潜在重叠对象阶段具体包括:对于待放置标签的整体轴对齐包围盒,利用哈希函数计算其所属网格单元地址,在两个镜像哈希表中查询潜在冲突的点要素与已放置标签;

32、所述执行重叠检测阶段包括:获取候选标签中所有字母的轴对齐包围盒,并分别与潜在冲突的点要素及已放置标签进行字母级重叠检测;

33、所述判定重叠是否可接受阶段包括:在完成重叠检测后,依据字母级可识别性准则进行判定;判定结果分为三种情况:第一,未检测到任何重叠,则该标签候选位置判定为有效;第二,待放置标签的任一字母轴对齐包围盒与任一点要素轴对齐包围盒发生重叠,则该候选位置被判定为无效;第三,待放置标签的字母轴对齐包围盒与其他已放置标签的字母轴对齐包围盒发生重叠,则需进一步执行重叠阈值检测;若所有参与重叠的字母的遮挡面积均不超过其对应阈值,则通过该候选位置的有效性检验;否则,判定该候选位置无效。

34、进一步地,所述执行重叠检测采用由粗到细的两阶段策略:

35、所述粗阶段策略具体包括:在标签整体的轴对齐包围盒层面进行快速筛查:检测候选标签的整体轴对齐包围盒与潜在冲突对象的轴对齐包围盒是否重叠,以剔除不可能发生真实重叠的对象;采用投影法进行轴对齐包围盒重叠判定:当且仅当两个包围盒在轴方向的投影区间相交且在轴方向的投影区间相交时,二者发生重叠;对应的重叠区域仍为轴对齐矩形;

36、所述细阶段策略具体包括:在粗阶段筛选结果的基础上,进一步检查对象之间的潜在重叠关系;对于待放置标签中每一个通过粗筛的字母轴对齐包围盒,采用投影法与通过粗筛的其他标签字母轴对齐包围盒及点要素轴对齐包围盒进行两两重叠判定。

37、进一步地,针对重叠阈值检测的高复杂度,采用与重叠检测相一致的粗、细两阶段策略;给定待放置标签中的字母,先计算该字母与其他字母轴对齐包围盒的重叠区域总面积;若不超过该字母面积与重叠阈值的乘积,则判定字母可识别;否则,用线段树平面扫描算法精确计算重叠区域的并集面积;

38、当多个字母轴对齐包围盒相互重叠时,需要分别对所有参与重叠的字母轴对齐包围盒执行阈值检测;当且仅当每个字母轴对齐包围盒的遮挡面积均不超过其对应阈值时,才能判定该重叠关系可接受;

39、针对重叠阈值检测遮挡的相互性,需要将重叠阈值检测流程扩展到与字母发生重叠的其他字母轴对齐包围盒:对每个相关字母,先进行粗阶段快速判定,若粗判结果超过阈值再精确计算并集面积,并与对应阈值比较。

40、进一步地,步骤s4中,所述标签放置与索引更新具体包括:

41、在标注过程中,候选位置在以下两种情况下被判定为有效:第一,该标签与任何现有点要素或已放置标签均不发生重叠;第二,该标签仅与其他已放置标签发生重叠,但所有发生重叠的标签仍满足标签可识别性要求;

42、基于贪心标注策略,已放置标签的位置确定后不再移动;当待放置标签与已放置标签发生重叠时,只需验证已放置标签的可识别性是否仍被满足;若已放置标签不符合可识别性要求,则判定该候选位置无效;在具体标注过程中,若候选位置有效,则选取该位置完成标注,并将该标签的整体轴对齐包围盒插入至标签空间哈希表中;若该点要素的所有候选位置均无效,则跳过该点要素。

43、本发明的有益效果是:

44、1.本发明采用字母级几何信息的初始化处理,将标签可识别性判据从传统的完全无重叠约束重构为基于字母级遮挡阈值的容忍模型,实现了在保证可读性的前提下对部分重叠的容忍,扩大了标签放置优化问题的求解空间。

45、2.本发明基于视觉单词识别机制建立了标签可识别性模型,并以“最大化放置可识别标签数量”为目标采用贪心标注策略,能够在不同规模数据集上稳定提升标签放置数量与标注完整性,保证了算法的可扩展性。

46、3.本发明通过设计镜像空间哈希表与线段树相结合的空间索引结构,实现了邻域内潜在重叠对象的快速查询与重叠比例的精确计算,大幅降低了候选位置有效性检测的时间复杂度,提升了整体标注效率。

47、4.本发明引入基于局部网格密度的标注顺序排序策略,优先为高密度区域的点要素保留充足的可行空间,有效缓解了传统方法在高密度场景下因顺序不当导致的标签信息损失问题。