留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

顾及均衡性与易读性的放大镜式地图目标选取算法

李佳田 李应芸 李显凯 罗富丽 康顺 林艳

李佳田, 李应芸, 李显凯, 罗富丽, 康顺, 林艳. 顾及均衡性与易读性的放大镜式地图目标选取算法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(9): 1211-1217. doi: 10.13203/j.whugis20140560
引用本文: 李佳田, 李应芸, 李显凯, 罗富丽, 康顺, 林艳. 顾及均衡性与易读性的放大镜式地图目标选取算法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(9): 1211-1217. doi: 10.13203/j.whugis20140560
LI Jiatian, LI Yingyun, LI Xiankai, LUO Fuli, KANG Shun, LIN Yan. Object Selection Algorithm for Magnifier Glass Map Considering Balance and Readability[J]. Geomatics and Information Science of Wuhan University, 2016, 41(9): 1211-1217. doi: 10.13203/j.whugis20140560
Citation: LI Jiatian, LI Yingyun, LI Xiankai, LUO Fuli, KANG Shun, LIN Yan. Object Selection Algorithm for Magnifier Glass Map Considering Balance and Readability[J]. Geomatics and Information Science of Wuhan University, 2016, 41(9): 1211-1217. doi: 10.13203/j.whugis20140560

顾及均衡性与易读性的放大镜式地图目标选取算法

doi: 10.13203/j.whugis20140560
基金项目: 

国家自然科学基金 41561082

国家自然科学基金 41161061

详细信息
    作者简介:

    李佳田博士副教授,主要研究方向为数值最优化方法与机器场景理解。ljtwcx@163.com

  • 中图分类号: P208;P283.1

Object Selection Algorithm for Magnifier Glass Map Considering Balance and Readability

Funds: 

The National Natural Science Foundation of China, Nos 41561082

The National Natural Science Foundation of China, Nos 41161061

More Information
    Author Bio:

    LI Jiatian, associate professor, PhD, specializes in numerical optimization and scene understanding for robot. E-mail: ljtwcx@163.com

图(3)
计量
  • 文章访问数:  917
  • HTML全文浏览量:  58
  • PDF下载量:  343
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-08-18
  • 刊出日期:  2016-09-05

顾及均衡性与易读性的放大镜式地图目标选取算法

doi: 10.13203/j.whugis20140560
    基金项目:

    国家自然科学基金 41561082

    国家自然科学基金 41161061

    作者简介:

    李佳田博士副教授,主要研究方向为数值最优化方法与机器场景理解。ljtwcx@163.com

  • 中图分类号: P208;P283.1

摘要: 针对放大镜式地图的信息失衡问题,以分段比例尺变化函数为投影方法,通过Voronoi k阶邻近关系建立观察目标与其邻近目标之间的联系,顾及目标分布的均衡性与目标形变的易读性,提出了Voronoi k阶邻近支持下的目标分布均衡性控制参数、Voronoi区域面积约束下的目标形变易读性控制参数,给出了两种控制参数的定量计算方法以及用于生成放大镜式地图的目标选取算法。实验结果表明,本文算法能够使得放大镜式地图中出现的目标数量保持稳定,与此同时,在放大镜边缘处变形较大的目标不再被表达,具有一定的实用价值。

English Abstract

李佳田, 李应芸, 李显凯, 罗富丽, 康顺, 林艳. 顾及均衡性与易读性的放大镜式地图目标选取算法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(9): 1211-1217. doi: 10.13203/j.whugis20140560
引用本文: 李佳田, 李应芸, 李显凯, 罗富丽, 康顺, 林艳. 顾及均衡性与易读性的放大镜式地图目标选取算法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(9): 1211-1217. doi: 10.13203/j.whugis20140560
LI Jiatian, LI Yingyun, LI Xiankai, LUO Fuli, KANG Shun, LIN Yan. Object Selection Algorithm for Magnifier Glass Map Considering Balance and Readability[J]. Geomatics and Information Science of Wuhan University, 2016, 41(9): 1211-1217. doi: 10.13203/j.whugis20140560
Citation: LI Jiatian, LI Yingyun, LI Xiankai, LUO Fuli, KANG Shun, LIN Yan. Object Selection Algorithm for Magnifier Glass Map Considering Balance and Readability[J]. Geomatics and Information Science of Wuhan University, 2016, 41(9): 1211-1217. doi: 10.13203/j.whugis20140560
  • 放大镜式地图属于变比例尺地图类型之一,它利用数学手段和投影变形,将地图上的重点内容用较大的比例尺表示出来,从而实现提高地图信息负载量的功能[1],并且比例尺变化近似连续,没有大的突变点,满足地图的连续性表示[2],被认为是一种非常实用的地图表达形式。

    放大镜式地图表达中,地图承载的地物细节与相对位置处于首要地位。因此,国内外学者以地图投影方法为核心,并拓展到可视化与自适应方法研究。文献[3]提出了变比例尺地图的基本概念。文献[4-5]归纳了变比例尺地图投影的6种常规方法,并提出可调放大镜投影方法。文献[6]设计了组合投影方法,扩展常规方法的应用范围。文献[7-9]设计了导航地图的可视化方法,实现“近大远小”效果,即对目标区域采用大比例尺——“凸透镜”放大,其他区域使用小比例尺——“凹透镜”缩小。文献[10]提出了导航地图的自适应多尺度表达,并实现了地图可视相关显示方法。文献[11]验证了放大镜参数(倍数、半径)与放大效果的关系。在移动地图制图研究中,由于移动地图的载体、用户群体以及应用环境相对于桌面电子地图都发生了变化,阅读变得更加困难[12-14]。文献[15]提出了空间目标分布变化导致的信息失衡问题,在移动地图应用中,用户根据当前位置设置一个距离范围来选择并表达其中的空间目标,形成用户视图,由于目标的不均匀分布,使得不同范围中的目标过多或过少,造成用户视图的信息量相差悬殊,即范围的大小无法依靠目标分布和用户需求自动调整。信息失衡问题在放大镜式地图中更加突出,与移动地图不同的是,放大镜式地图所呈现的目标数量随着放大镜与目标距离的远近变化增减更加剧烈,即当放大镜距离目标较近时,观察到的目标很少;反之,当距离变大时,目标数量会显著增多。目标的不均匀分布以及目标数量的剧烈变化导致放大镜式地图所呈现信息的不均衡,进而影响阅读。然而,目前鲜见针对此问题的相关研究工作。

    放大镜式地图是选取目标集并根据数学投影方法进行转换的结果,投影转换中的点目标不会出现形变,线目标通常保持连通关系不易进行部分取舍,而面目标则会受到变比例尺的影响,放大镜中心位置目标被明显放大,边缘位置目标被放大程度相对较小。本文以面目标为例,采用比例尺变化函数为放大镜投影方法,通过Voronoi k阶邻近关系建立观察目标与其邻近目标之间的联系,提出了Voronoi k阶邻近支持下的目标分布均衡性控制参数、Voronoi区域面积约束下的目标形变易读性控制参数,并给出了目标选取算法与实验验证。

    • 物理学中,物体、像与焦距是放大镜三要素。将物体、像至透镜中心的距离分别称为物距u、像距v,则它们与焦距f共同构成关系:

      (1)

      如果将物体置于焦距以内,通过透镜看到的是物体放大的像,这是放大镜的基本成像原理。由于这个像不是实际折射光线的会聚点,而是它们的反向延长线交点,因此,其为虚像,物理光屏不能接收。因此,在实际计算环境中,数学投影方法被用来模拟放大成像过程。

      投影方法主要分为6种类型,本文以比例尺变化函数方法为基础,实现放大镜式地图的函数设计。投影变换的过程描述为:在比例尺发生变化的投影规则f下,原始地图空间S投影转换为目标空间Tf(S)→Tf为一一映射函数。变换描述为:

      (2)

      其中,(x0y0)为放大镜焦点p;(xy)为原始地图空间上任意一点,(xy)∈S;(x′,y′)为(xy)经变换后的目标空间点,(x′,y′)∈Tr为焦距;f(r)为比例尺变化函数。

      式(2)的物理意义是根据目标到焦点的距离r调整比例尺变化函数f(r),距离越大,成像变小;反之,成像则越大。在比例尺变化函数f(r)的作用下,目标bS投影变换到目标b′∈T,相当于bb′在大小或形状上产生变化,进而达到对目标突出表达的效果。

      幂函数y=(1+x2)-1,其在定义域(0,+∞)时为单调递减,且函数值为正值,满足(x→+∞,y→0),符合比例尺变化函数f(r)的要求。因此,本文定义比例尺变化函数为:

      (3)

      式中,α为放大倍数,反映比例尺的变化程度。放大镜式地图的关键是在细节区域内显示观察目标,而在这个区域外显示参考目标,使得读图过程保持连续性。更进一步,以r0为阈值区分细节区域与非细节区域,根据式(3),用分段函数形式描述比例尺变化函数:

      (4)

      由式(4)构成的值空间如图 1所示。

      图  1  比例尺变化函数的值空间

      Figure 1.  Value Space of Variable Scale Function

      设有两点(x1y1)、(x2y2)∈S,根据式(2),它们经投影转换后的坐标(x1y1)、(x2y2)∈T分别为:

      (5)

      化简后,得到xy方向长度比例变化:

      (6)

      由比例尺变化函数f(r)的连续性质,根据式(6),以xy轴为参考,矢量vT可分解为两个部分:

      (7)

      根据式(3),f(r)值域为(0,α),通常α>1,目标转换到空间T可分为三种情况:①xy方向比例变化均≥1;②x方向比例变化≥1,y方向比例变化<1或y方向比例变化≥1,x方向比例变化<1;③xy方向比例变化均<1。

      受放大镜特殊物理性质的影响,当使用放大镜式地图时,会伴随信息失衡。

      1)理想情况下,观察目标应充满细节区域I,使得其细节被放大,与此同时,观察目标的邻近目标会充斥整个非细节区域II。而通常情况下,无法保证非细节区域II存在邻近目标,因此,不能直观而有效地判断观察目标的邻近关系和邻接程度,导致地图的均衡性变差。

      2)当非细节区域II中的邻近目标数量过多时,部分邻近目标会出现上述情况②与③,相对其原始目标,这种邻近目标会严重变形,导致易读性变差,应选择性地将其删除。

    • 目标之间邻近关系的描述是度量关系与拓扑关系的有机结合[16-17],其主要描述方法有:欧氏距离方法、拓扑方法、Voronoi邻近方法。面目标之间主要表现为拓扑相离关系,因此,本文主要讨论欧氏距离邻近与Voronoi邻近两种方法。目标之间的欧氏距离反映在读图过程中是不敏感的,在描述或记忆目标空间位置时,并不是给出其精确的空间坐标位置,而是相对其邻域特征的记录。更加特别地,目标空间T是经过变换后的原始空间形态,其中的欧氏距离会被更进一步地弱化。而邻近目标分布的方向性、数量稳定性是放大镜式地图重点考虑的邻近目标描述特征,相对于欧氏距离邻近,Voronoi邻近在这两个方面具有优势[18]

    • 地图中两个相邻目标在现实地理环境中并不一定相邻,例如道路与其旁边的建筑物,在几何关系上它们并非连接,但可以通过建立Voronoi图辅助判断彼此间是否存在邻近关系[18-19]

      定义1  Voronoi邻近:存在空间目标集合O={o1o2,…,on} ⊂ R2,1<n<∞,对于∀oioj(ij),v(oi)与v(oj)分别为目标oi与oj的Voronoi区域,如果条件v(oi)∩v(oj)=∅成立,则称oioj为Voronoi邻近。

      Voronoi邻近关系具有传递特性,可由多个步骤的Voronoi邻近-Voronoi距离定义,归纳出普遍意义下的Voronoi k阶邻近。

      定义2  Voronoi k阶邻近:存在空间目标集合O={o1o2,…,on} ⊂R2,1 < n < ∞,对于∀oioj(ij),如果目标oi经过最小Voronoi邻近步数k(kN)到达目标oj,则称oioj为Voronoi k阶邻近,记为v(oioj)=k。

      Voronoi邻近是Voronoi k阶邻近的特例,即当k=1时,Voronoi 1阶邻近等价于Voronoi邻近。

      定理1[20]  若目标数n > 3,则在与平面上任意n个目标相对应的Voronoi图中,Voronoi顶点的数目不会超过2n-5,而Voronoi边的数目不会超过3n-6。

      由定义1可知,两目标为Voronoi邻近的条件即是共享Voronoi边,又根据定义1与定义2,空间目标集构成的Voronoi图中,目标oi的Voronoi k阶邻近目标数与目标总数之间呈线性关系,表明目标oi的Voronoi k阶邻近目标数量是线性稳定的。

      定理2  存在空间目标集合O={o1o2,…,on}⊂R2,1 < n < ∞,目标oi(oiO)的Voronoi邻近目标集O′={o1o2,…,om},m > 2,如果目标集O′构成一个包含目标oi的凸壳,则目标集O′至少分布在以目标oi为坐标原点的欧氏平面两个不相邻的象限内。

      定理2可由凸壳与目标oi的拓扑包含关系证明,这个性质表达一个目标的Voronoi邻近目标是围绕这个目标方向均衡分布的。

      设放大镜的放大倍数α1及放大镜物理半径l为已知,根据式(3),观察目标oi(oiO)的最小外接矩形(minimum boundary rectangle,MBR)中心即是焦点p(0,0),设MBR以M表示,其宽度、高度分别为wh,那么,焦点p(0,0)至M的最大距离为:

      (8)

      理想情况是M充满细节区域I,那么r0=dmax(pM)。设放大镜地图中需要出现k阶Voronoi邻近目标,并且邻近目标中距离焦点p(0,0)最大距离为dmax,建立由ST的距离变化条件为:

      (9)

      解不等式,得α2为:

      (10)

      α2为均衡性控制参数,依据式(10)设置α2值,使得在满足观察目标放大α1倍的同时,所指定的Voronoi k阶邻近目标出现在非细节区域II中,保证邻近目标分布均衡。

    • 由定义2可知,Voronoi k阶邻近实质上由拓扑关系与度量关系两部分组成。如果两个目标具有相同的Voronoi边界,则两目标邻近,而目标之间的距离即变成Voronoi距离,通过这种距离,邻近的远近程度则可以进一步量测[20]。因此,由Voronoi k阶邻近可以建立目标之间相对空间位置的邻近程度度量,更进一步,依据目标的Voronoi区域面积,可以建立其形变度量。

      定义3  邻近度:存在空间目标集合O={o1o2,…,on}⊂R2,1 < n < ∞,oi(oiO)为观察目标,oi的Voronoi区域为v(oi),oj(ojO)的Voronoi区域为v(oj),若存在v(oioj)=k,则oj的邻近度为:

      (11)

      定义4  缝隙度:设空间目标集合O={o1o2,…,on}⊂R2,1 < n < ∞,∀ojOoj的面积为a1oj的Voronoi区域面积为a2,则oj的缝隙度为:

      (12)

      综合参数ng,以oi为观察目标,则目标oj相对于观察目标的选取值为:

      (13)

      目标选取值为相对于观察目标的Voronoi k阶邻近距离倒数与其自身缝隙度之和,前项是表达邻近目标重要程度的指标,k值越小,重要性越大,相反,则越小。在重要性小的目标中,通过后项表达其形变程度,即形变越大,目标面积与其Voronoi区域面积越接近,比值越小,相反,则越大。

      定义5  平均选取值:空间目标选取值集合Sv={s1s2,…,sn},1 < n < ∞,则平均选取值为:

      (14)

      根据定理1,观察目标与其Voronoi k阶邻近目标呈线性关系,因k值有限,式(14)可转化为:

      (15)

      因此,平均选取值的范围ζ∈(0,clnk),称ζ为易读性控制参数,其取值影响着目标删除数量。ζ取值越小,变形目标被删除的越少;反之,ζ取值越大,变形目标被删除的越多。

    • 根据上述控制参数,将目标形式化描述为如下结构。

      class feature

      {

         object  o;

         object  v;

      }

      其中,o为目标形状与位置;v为目标的Voronoi区域。目标选取算法过程描述如下。

      已知条件:当前位置(xcyc),放大倍数α1k阶邻近值,平均选取阈值ζ,放大镜半径l,目标集合O={o1o2,…,on}。

      计算结果:放大镜式地图目标集Ok

      1)根据当前位置(xcyc),遍历目标集合O,如果任意目标oi与点(xcyc)相交,则oi为观察目标。

      2)根据oi的最小外接矩形M,计算焦点p坐标p(x0y0)与r0

      3)根据文献[21]中的方法生成目标集合O的Vorono图,并根据定义2,计算O中任意目标Oj相对于Oi的Voronoi邻近阶数。

      4)根据已知的k阶邻近值与目标邻近阶数,在目标集合O中提取oik阶邻近目标集OkO

      5)遍历集合Ok,对于集合中的任意目标ok,计算得出dmax

      6)根据式(10)、已知的α1l值,计算得到均衡控制参数α2

      7)如果α1 / α2>10,那么,删除集合Ok中的ok,转至5)。

      8)根据式(4),遍历并转换集合Ok。①对于集合中任意目标ok,计算其目标面积a1与其Voronoi区域面积a2。②根据式(13),计算目标易读性选取值s,如果sζ,则将ok置入集合Ok

      9)输出集合Ok

      算法中,需要说明的是5)~7)迭代过程。当部分邻近目标距离焦点的距离较大时,根据式(10)计算得到的均衡控制参数α2会较小,虽然k阶邻近目标被置入非细节区域Ⅱ,但会出现邻近目标整体挤压形变较大现象,如果不加以处理,根据易读性控制参数,步骤8)会将多数目标删除。为此,设置α1 /α2m条件,m为经验值,本文取10,即当满足该条件时,说明此时目标ok距离焦点的距离过大,将其删除,并迭代此过程,直到该条件不成立为止。

    • 实验数据为云南省昆明市1∶500地图数据,为昆明市当地坐标系,共计包含面目标3 100个,部分数据如图 2(a)所示。为说明算法中控制参数的作用,首先根据式(3)所定义的比例尺变化函数,做α=20倍放大,效果如图 2(b)所示。因观察目标与其邻近目标存在较大的间隔距离,使得在放大倍数较大的情况下,其邻近目标没有出现在放大镜中,此时目标数量过少,会造成读图过程的不连续。在同样条件下,做式(4)比例尺变化函数,即α1=20,并设置入Voronoi 2阶邻近目标,即k=2,根据式(10)求得α2≤8.73,取邻近目标最大的放大效果,即α2=8.73,并将Voronoi图一并做比例尺变化转换,效果如图 2(c)所示。从图 2中可以看出,二阶邻近目标全布置入放大镜中,相对于图 2(b)观察目标保持状态不变,邻近目标数量增多,会使得读图过程更加连续。但在放大镜边缘处,某些二阶Voronoi邻近目标出现较大形变,相对于原始地图,边缘处邻近目标同时出现相互挤压。此时,变换后共存在33个邻近目标,根据式(15)计算得到,平均选取值ζ∈(0,3.83),取ζ=0.5,删除4个目标,结果如图 2(d)所示。可以看出,所删除目标均是处于放大镜边缘、形变大的目标,删除后更加便于读图。上述过程表明,本文提出的均衡性控制参数α2及易读性控制参数ζ是正确与有效的。沿道路实验数据做50次随机间隔放大操作,参数为k=1、2阶邻近、α2=15倍、ζ=0.5,统计放大镜中的邻近目标数目与邻近目标删除数,如图 3所示。可以看出,邻近目标数目与邻近目标删除数均呈均匀稳定状态。k=1时,邻近目标数均值为10;k=2时,邻近目标数均值为33,单次邻近目标数与均值差异较小。当k=1时,平均删除目标数为2;而在k=2时,平均删除目标数为4。这表明在放大参数相同的情况下,随着置入邻近目标数的增多,形变与挤压增大,易读性变差的目标增多,所删除的邻近目标数有增大趋势。

      图  2  控制参数对比

      Figure 2.  Comparison of Controlling Parameters

      图  3  邻近数标数与删除目标数对比

      Figure 3.  Quantity Comparisons of Adjacency Object and Deleted Object

    • 地图放大、缩小与平移是读图过程的基本操作,优良的软件设计更加需要考虑方便易用,以减少基本操作的次数与切换频率,使读图过程更加连续,放大镜式地图同样也是如此。Voronoi k阶邻近是一种空间度量方法,其可用于在目标不均匀分布条件下构建稳定的目标序列。本文正是以此为基础,提出了顾及目标分布的均衡性控制参数α2与目标形变的易读性控制参数ζ。本文目标选取算法能够有效地克服放大镜式地图读图过程中目标出现过多或过少所造成的信息失衡问题。

参考文献 (21)

目录

    /

    返回文章
    返回