成晓强：信息量与相似度约束下的网络地图服务缩略图自动生成算法 论文推荐|-测绘学报
《测绘学报》
构建与学术的桥梁 拉近与权威的距离
信息量与相似度约束下的网络地图服务缩略图自动生成算法
成晓强1,杨敏2,3,桂志鹏4,艾廷华3,吴华意5
1. 湖北大学资源环境学院, 湖北 武汉 430062;2. 国土资源部城市土地资源监测与仿真重点实验室, 广东 深圳 518034;3. 武汉大学资源与环境科学学院, 湖北 武汉 430079;4. 武汉大学遥感信息工程学院, 湖北 武汉 430079;5. 武汉大学测绘遥感信息工程国家重点实验室, 湖北 武汉 430079
收稿日期：2017-02-02；修回日期：2017-08-18
基金项目：国家自然科学基金（41501443；41371372）；中国科学院太空应用重点实验室开放基金（LSU-SJLY-2017-02）；国土资源部城市土地资源监测与仿真重点实验室开放基金（KF-2016-02-020）
第一作者简介：成晓强(1985-), 男, 博士, 讲师, 研究方向为地理信息可视化及空间信息服务。E-mail:carto@hubu.edu.cn
摘要：缩略图可显著提高图片和视频等图形图像资源的展现效率，有效改善信息检索过程中的用户体验。地图服务是一种耦合空间和尺度信息的图像资源，其设计创作、检索筛选和存储管理均需要缩略图的支撑。设计精巧的缩略图带给人良好、鲜活的第一印象，帮助用户实现高效的交互与探索；粗糙凌乱的缩略图则让用户产生抵触情绪，打消其继续探索地图服务的主动性。本文借鉴视频关键帧的思路并结合地图表达特点，提出了地图服务关键位置和关键尺度的概念，并设计了相应的量化指标和提取算法，重点解决了缩略图视觉效果不佳、地图信息量不足和自动化程度不高等问题。算法基于信息量识别地图中内容丰富的关键位置，然后利用跨比例尺相似度判断发生显著变化的关键尺度，最后自动筛选出若干张代表地图服务内容的缩略图。试验表明本方法提取的缩略图数量适中、内容丰富、代表性强马彬茵 ，可高度还原地图服务的内容构成和外观样式。
关键词：网络地图服务关键尺度缩略图信息量相似度
An Algorithm Creating Thumbnail for Web Map Services Based on Information Entropy and Trans-scale Similarity
CHENG Xiaoqiang1,YANG Min2,3,GUI Zhipeng4,AI Tinghua3,WU Huayi5
Abstract: Thumbnail can greatly increase the efficiency of browsing pictures, videos and other image resources and improve the user experience prominently. Map service is a kind of graphic resource coupling spatial information and representation scale, its crafting, retrieval and management will not function well without the support of thumbnail. Sophisticated designed thumbnails bring users vivid first impressions and help users make efficient exploration. On the contrast, coarse thumbnail cause negative emotion and discourage users to explore the map service positively. Inspired by video summarization李先皓, key position and key scale of web map service were proposed. Meanwhile, corresponding quantitative measures and an automatic algorithm were drawn up and implemented. With the help of this algorithm, poor visual quality, lack of map information and low automation of current thumbnails was solved successfully. Information entropy was used to determine areas richer in content and tran-scale similarity was calculated to judge at which scale the appearance of the map service has changed drastically, and finally a series of static pictures were extracted which can represent the content of the map service. Experimental results show that this method produced medium-sized, content-rich and well-representative thumbnails which effectively reflect the content and appearance of map service.
Key words:web map servicekey scalethumbnailinformation entropysimilarity
网络地图服务(简称“地图服务”)是互联网时代出现的新型地图组织方式，汪则翰它在基本地图可视化的基础上融入了跨尺度集成、多专题耦合及高度互操作等特色，是空间信息基础设施(spatial data infrastructure，SDI)中一种重要的数据资源。进入大数据时代，地图服务以较低的资源需求、直观的可视化形式以及无缝的跨平台衔接成为最佳的知识表达与展现形式。近年来地图服务的数量和质量均在不断提升[1-3]，科研工作者及普通大众对地图服务的需求也逐渐提高，高效管理大量地图服务并快速匹配用户需求成为SDI必须面临的问题。目前该领域研究可分为两类：①主动收集散落于互联网的地图服务[4-10]，该方向的研究成果已经证明互联网中分布的地图服务数量庞大且价值巨大；②将收集到地图服务纳入SDI中统一管理，并提供应用系统供用户查找、比较并选择地图服务，已有若干科研机构实现了相应的软件系统[11-12]。笔者发现，后者这些系统更多考虑查全率和查准率等技术层面的指标，而较少关注用户体验方面的改善。以筛选地图服务为例，系统会为每个服务提供图文简介，包括一段描述地图功用的文字摘要和一张提供可视预览的缩略图。由于文字摘要很难反映地图的色彩构成、设计风格及美学效果，可直观展现地图内容和外观的缩略图就显得尤为重要。但目前的缩略图普遍存在视觉效果不佳、表现形式单一及信息量偏少等问题，并不能给用户提供有效信息，严重者甚至会误导用户[13]。受此问题的影响，地图服务应用系统的可用性被削弱，用户体验也较差。
设计精巧、制作精良的缩略图能带给用户良好、鲜活的第一印象，并引导用户进行高效的探索与交互；反之，粗糙凌乱的缩略图则让用户产生抵触情绪，打消其继续探索地图服务的主动性。因此，如何为地图服务生成合适的缩略图成为互联网时代地图学研究的新命题。经广泛调研发现，国内外尚未有论文对地图服务缩略图作论述和探讨；在实际应用方面，虽然许多系统已利用缩略图展现地图服务，但采用的方法过于简单，包括自动截取全图范围、手动选取热点区域、随机选取地图瓦片等，效果也并不理想。针对以上问题，本文首先分析了地图服务的内容组织方式和表达特点，并在图像和视频缩略图的启发下，设计了地图服务缩略图的自动生成算法。
1 缩略图的概念及其应用
缩略图是原始图片经压缩或裁切处理后的小尺寸图片。利用缩略图管理图像及视频资源可提高检索效率、优化内容布局、改善用户体验以及增加点击量等[14]。静态图片可采用最邻近插值等算法生成小尺寸的缩略图，也可先提取关键区域后再缩小尺寸[15]。视频缩略图的生成方法相对复杂，包括关键帧提取并根据关键帧的表现力及视觉显著性[16-18]生成最适合反映视频内容的片段或图片欧阳祥山。地图服务是多级比例尺地图的耦合，是多张详略不同的地图图片在相同空间坐标系下的有序组合。对于同一地理范围，表达概略的地图幅面较小，表达详细的地图幅面较大二刈子 。直接以概略地图作为缩略图嗜血魔医 ，可能过于简单且信息量较少(图 1(a))；将详细地图调整尺寸后作为缩略图，结果又会出现较大的模糊与失真(图 1(c))。而且，详略不同的地图包含的要素类型及样式符号均有较大差别，图 1(a)和图 1(b)即属于同一地图服务的不同缩放比例。很显然其中任意一张都无法准确反映地图服务的全貌，图 1(a)可能会误导用户认定该服务为分级专题图，而事实上地图服务在后续缩放比例演变为分类专题图。同时，由于互联网环境下地图综合等尺度变换模型的缺失，地图服务普遍存在地物拥挤、符号冲突等现象[19-20]，如图 1(d)。将以上地图图片用作缩略图均会极大影响用户体验。图 1地图服务缩略图示例Fig. 1Thumbnails of web map service
图选项
从控制维度看，地图服务的内容组织比视频更复杂。视频仅通过一维的时间轴来控制内容播放，而地图服务则至少通过3个维度来控制内容展现，二维的平面位置加一维的缩放比例，部分地图服务还可能包括高度维与时间维。本文借鉴视频关键帧的思想提出了地图服务中“关键位置”和“关键尺度”的概念。关键位置指地图中要素类型丰富、符号分布多样、结构布局合理的区域，应尽可能全面反映地图的内容构成。关键尺度则是由地图的多尺度特征决定的，地图缩放会引起要素出现/消失、地图样式调整以及数据模型改变等多种变化，而且这些变化随机分布于各个缩放比例。有些缩放比例的变化并不明显，而有些缩放比例的变化则十分显著。本文将视觉变化明显、容易引起用户感知差别的缩放比例定义为关键尺度。如何形式化表达并自动发现地图服务的关键位置及关键尺度是本文的核心问题。
2 信息量与相似度约束下的地图服务缩略图生成算法2.1 算法的基本思路
地图服务普遍以地图瓦片的形式进行组织。地图瓦片是服务器端预先渲染的，按照四叉树规则切分的小尺寸地图图片(一般宽和高均为256像素)。对于一个包含n级缩放比例的地图服务，最小的缩放比例L0级仅包含1张覆盖全部地图范围的瓦片；最大的缩放比例Ln-1级则包含4n-1张地图瓦片。地图瓦片的尺寸与缩略图的要求比较接近，而且还可以灵活拼接，适合作为服务的缩略图。在地图瓦片的模式下，可将问题定义为“从瓦片金字塔中选取可代表地图服务内容的瓦片”，并进一步分解为两个子问题：平面位置维的瓦片选取和缩放比例维的瓦片选取。
(1) 平面位置维的瓦片选取只考虑特定的缩放比例，核心问题是如何量化地图瓦片的“代表性”。对于一张静态地图，人们更倾向于关注其中较复杂的部分，如符号分布密集或注记摆放紧凑的区域，因为此类区域可以提供更丰富的信息量。从该思路出发，本文利用地图瓦片的复杂度近似表示其信息量并作为其“代表性”的量化指标。
(2) 缩放比例维的关键问题是找到发生“突变”的瓦片。相邻比例尺的地图瓦片之间既有共同点，也存在不同之处。共同点多，表示比例尺之间变化细微；反之，则意味着比例尺之间变化显著。细微和显著对应着地图尺度空间中的缓变和突变[21-22]，而突变更容易引起用户的注意，也更应该在缩略图中予以体现。本文利用图像相似度来定量评价两个比例尺瓦片之间的相似程度，并据此判定发生显著变化的缩放比例。
算法从L0级开始依次遍历所有缩放比例，每个缩放比例包括两次计算。如图 2所示，首先计算瓦片信息量，获取当前缩放比例下内容最丰富的瓦片T2；然后获取与T2相同地理范围的下一级瓦片Tnext，并计算T2和Tnext的相似度，如果相似度大于阈值，就选取Tnext作为缩略图。Tnext是处理下一个缩放比例的初始瓦片，将其等分为4张瓦片，然后重复上述计算过程。完成所有缩放比例的计算后石久让，缩略图集合生成完毕。图 2算法示意图Fig. 2Algorithm diagram
图选项
2.2 基于地图瓦片信息量的地图服务关键位置确定
地图瓦片的数量随缩放比例变化呈指数增长董沛琪，处理全部瓦片的计算量将相当庞大。算法利用地图信息量来进行第一次过滤。在每个缩放比例下选取信息量最丰富瓦片，并以其地理范围为约束遍历下一级缩放比例。该过程是启发式的，除L0和L1级之外，并不能保证其他级别的种子瓦片具有最大信息量，但能够以较小的计算代价得到不错的命中率。利用信息量粗选后，每一级参与比较的地图瓦片均不超过4个，有效降低了计算量曾根菜津子 。
现有地图信息量的度量方法大多基于矢量目标的统计分析[23-24]，并不适用于地图瓦片(图片)的信息量计算。根据文献[25]的研究，图片压缩比是一项计算简单但十分有效的复杂度指标，可反映地图内容的丰富程度及地图符号的多样性。地图瓦片的内容是规律性的地图符号和文字注记，颜色数量较少、区域边界锐利、色块均质性高，利用某些无损压缩算法即可获得较高的压缩比。因此，本文采用地图瓦片的压缩数据量作为其信息量的表征指标。目前的地图瓦片多为PNG(portable network graphics)格式，原因是PNG格式采用的DEFLATE无损压缩算法非常适合处理图像中的均质区域且具有较高的压缩比，能较好满足地图的压缩需求。图 3中每幅地图均包含4张瓦片，将PNG数据量最大的瓦片(虚线框范围)放大一级后得到下一幅地图。可以看出，PNG数据量在前3个缩放比例中均准确定位了地图中最复杂的区域，较好反映了地图信息的丰富程度。图 3基于PNG数据量定位地图复杂区域Fig. 3Locating complex map area based on PNG's size
图选项
2.3 基于跨比例尺相似度的关键尺度识别
虽然不同缩放比例的地图在内容详略程度和符号样式上有差异，但总体地物布局及分布模式是相似的，这在一定程度上降低了瓦片相似度计算的难度。作为地图符号的重要视觉变量，颜色特征在人类地图感知与认知过程中起到了决定性作用，因此本文从颜色角度分析瓦片的相似性。首先采用色彩直方图来量化表达瓦片的颜色特征，然后使用余弦距离计算瓦片的相似度。本文结合地图的表达特点对直方图作了两点改进。
(1) 改进了颜色量化方法。为了顾及可读性及一览性，地图中包含的符号类型有限，对应的色彩数量也极大低于自然场景图片。然而由于反走样等技术策略的应用，地图符号的边缘像素引入了颜色渐变，间接提高了色彩总量，如图 4(a)中的瓦片共包含8238种颜色。图 4(b)、(c)、(d)是不同的颜色量的量化结果，其中图 4(d)对原图的保真度较高，可见该瓦片只需要16种颜色就可近似表达。如果对两幅瓦片分别量化，得到的颜色集合可能不一致，在后续的直方图距离计算时需要额外考虑颜色本身的相似性，计算复杂度较高。在此先将待比较的两幅瓦片拼合到一起，统一管理二者的颜色空间，然后就可以利用常规量化方法得到显著而且唯一的颜色集合。图 4地图瓦片在不同颜色数量下的效果Fig. 4Map tiles quantified by different color number
图选项
(2) 改进了颜色频率的统计方法。常规方法是统计属于某颜色的像素个数，并不能合理地反映地图内容构成。因为地图符号尤其是线状符号和点状符号通常以少量像素表达重要信息，仅统计像素个数会极大弱化这两类符号的地位。针对该问题，本文首先将地图剖分为若干个连续色块，并用这些色块的周长来计算颜色的出现频率。连续色块的划分标准是相同颜色的像素在四邻域相邻接，周长计算则利用摩尔邻域边界跟踪算法。
本方法中提及的颜色均是在RGB色彩空间下，颜色量化方法采用最小方差法，可以指定保留的颜色数量。基于量化后的颜色集合，分别统计每种颜色在两张瓦片中的出现频率，得到色彩直方图，最后利用余弦距离计算直方图之间的相似程度。图 5中展示了两张瓦片在颜色量为16时的直方图，此时相似度为0.172。颜色量会影响相似度的结果。笔者尝试多次后发现当颜色量多于地图中实际出现的颜色后，相似度逐渐趋于稳定，因此，后文试验设定了一个相对较高的颜色量。另外，专题地图中往往会包含大面积的空白区域或底色填充(如图 5中两张瓦片)祝丹文，这些区域也会被识别为连续色块并具有较大影响力，进而干扰相似度计算。本方法在相似度计算时作了简单调整，将直方图中占比最大的颜色权重置零，忽视其对相似度的影响。图 5地图瓦片及其颜色直方图的对比Fig. 5Two map tiles of different scale and corresponding color histogram
图选项
3 试验与分析
试验选取了4个地图服务对算法进行验证，包括两个公众地图服务(武汉市天地图及湖南省电子地图)和两个专题地图服务(美国医疗设施分布图及堪萨斯州河流等级图)。首先获取4个服务在最小缩放比例L0级的地图瓦片作为初始瓦片，如图 6所示，算法默认将L0级的瓦片加入缩略图集合。图 7中列出了算法自动获取的代表性地图瓦片(共10级)，其中两个公众地图服务最后均定位到了内容丰富的建筑密集区域，逐级探索过程较好地体现了地图服务的内容变化。两个专题地图服务在最大缩放比例下的地图瓦片内容偏少后宫计，但从前面几级缩放比例来看，算法对于关键位置的定位基本准确。图 64个地图服务的初始瓦片(L0)Fig. 6Initial tile of four map service (L0)
图选项
图 7各个缩放比例的代表性地图瓦片及跨比例尺相似度(字体加粗表示正确的缩略图候选，下划线表示算法误判)Fig. 7Map services' representative map tile at each scale and trans-scale similarity (bold font represents correct thumbnail candidates and underline represents misjudgments of the algorithm
图选项
将色彩量化的颜色量设为32，进行相似度计算，每个缩放比例与前一个缩放比例的相似度标在图 7每个地图瓦片的下方琥珀年华 。图 8是各个服务从L1到L10之间相似度的变化曲线，横坐标代表缩放比例，纵坐标代表相似度。横坐标1对应的值表示L1和L0的相似度，2对应的值表示L2和L1的相似度，以此类推。总体来看，两类服务在放大过程中呈现出不同规律：公众地图服务的突变发生在后期，由于街区、建筑物、绿地等要素的引入，地图的内容出现显著变化；专题地图服务的突变则出现在前期，原因是符号冲突的缓解、要素内容的舍弃、表达模型的转换及符号样式的更换等。本文暂以0.1为阈值进行缩略图筛选，相似度大于0.1，即认为发生突变，并将其纳入缩略图集合；反之，不作为缩略图。下文将逐一分析每个服务的相似度曲线并探讨缩略图集合的合理性。图 8地图服务跨比例尺相似度曲线Fig. 8Trans-scale similarity curve of web map services
图选项
(1) 美国医疗设施分布图。该服务中有6个缩放比例的相似度超过0.1，而且均发生在整个放大过程的前半程。L2级中，点目标由聚合变为离散，而且引入颜色区分类别，因此变化较大。L4级中，不仅点目标的数量更多，其颜色信息也更丰富。L5级中，地图符号的形状更加复杂，对地图外观造成了一定影响。L1、L3和L6级的相似度偏高是图面空间变大、符号冲突缓解造成的，但视觉变化并不明显，不适合作为缩略图。该服务缩略图集合为L0、L2、L4和L5，算法出现误判。
(2) 堪萨斯州河流等级图。该服务最明显的突变在L4，由于大量低等级河流的出现，地图呈现出与上个缩放比例完全不一样的外观。另一个相对较弱的突变是L2中的河流标明了注记。该服务缩略图集合为L0、L2和L4，算法结果准确。
(3) 武汉市天地图。该地图服务最显著的变化出现在L7，由于细粒度建筑物的引入，地图的内容构成及外观都与上个缩放比例有较大区别。其余缩放比例的相似度均在0.2以下，总体上变化比较平缓。L4和L9级发生的变化稍大，分别是道路符号变化及大量注记出现造成的，其中L4级的地图背景色还出现微调。该服务缩略图集合为L0、L4、L7和L9，算法结果准确。
(4) 湖南省电子地图。该服务中最显著的变化出现在L1和L7。只包含境界的L0级瓦片过于粗略，因此L1级中交通、水系及注记等要素的同时出现显得较为突兀。L7中不仅引入了植被、居民地等新要素，而且原有水系符号也发生变化，因此L7是本服务中变化最大的缩放比例。另外两个差别较大的缩放比例是L9和L10，L9中街区演变为细粒度的建筑物，L10中低等级道路的符号发生改变，这都影响了地图外观。值得注意的是，L8之前逐渐丰富的地图注记在L9和L10中均消失不见，这种变化不符合常理。L2出现了新的道路及注记，“湖南省”的注记方式也有所改变，但视觉变化并不明显，算法判断有误。该服务缩略图集合为L0、L1、L7、L9和L10。
在具体度量指标上，试验采用PNG数据量近似模拟地图信息量。虽然数据量只能体现统计意义上的复杂度罗超凡，钻石王牌动漫无法确切反映地物类型的多寡和地物要素的布局等信息，但其代表的内容丰富程度足以满足缩略图的要求。从试验结果来看，PNG数据量对地图服务中关键位置的定位基本准确。由于算法采用了启发式搜索策略，在逐级放大过程中可能会偏离关键位置、得到无价值瓦片，甚至会终止遍历算法楼天成 。为避免这种情况，可选取每个缩放比例下信息量最丰富的前t张瓦片(t≥1，本文试验中t=1)，t越大，偏离关键位置的概率越小。基于图片相似度的“关键尺度”识别也具有较高的准确率，算法提取的突变尺度与人类视觉感受基本一致。由于设定了固定阈值，算法将几个视觉变化不显著的缩放比例识别为关键尺度，给最终的缩略图集合造成了冗余。后续研究将结合专家知识进一步改进相似度指标和关键尺度识别方法。经大量试验发现，多尺度地图中容易引起视觉关注的现象包括：①新要素类的引入、要素类的选取及要素表达模型的转换等数字景观模型方面的变化；②符号冲突的缓解、符号样式的变化及注记的增减等数字制图模型方面的变化。在缩略图中表达这些现象将引导用户关注地图服务的多尺度特征，进而作出正确的选择与决策。
4 总结及展望
本文提出了一种地图服务缩略图自动生成算法，首先利用地图信息量和四叉树结构定位地图中内容丰富的区域，然后基于颜色直方图计算跨比例尺相似度并识别发生突变的缩放比例，分别从平面位置维和缩放比例维实现了地图服务的自动化逐级探索和缩略图筛选。试验结果表明，算法自动提取的缩略图数量适中、内容丰富、代表性强，既可准确反映地图服务的内容构成，又能快速体现缩放比例间的变化情况，较好满足了地图服务的预览需求。本文将常规缩略图由单张扩展到多张，并将地图服务的跨尺度变化融入其中，既能保证用户在预览时获取足够的信息量，又可避免因单张缩略图效果不佳或内容偏少引起的误导和误判。
本文设计的算法适用于矢量数据派生的地图，对影像地图、三维地图等考虑不足。同时，缩略图个数取决于相似度阈值，智能化程度不高，后续研究将根据每个地图服务的尺度变化情况设计自适应阈值。下一步工作将结合认知试验在SDI中应用地图服务缩略图，验证其使用效果和用户体验。跨比例尺相似度是本文的核心创新，由此衍生的相似度曲线是一种面向多尺度地图的新型评价模型，有望应用于多尺度地图信息量变化规律等研究农女吉祥。
【引文格式】成晓强，杨敏，桂志鹏，等。信息量与相似度约束下的网络地图服务缩略图自动生成算法[J]. 测绘学报，2017，46(11)：1891-1898. DOI: 10.11947/j.AGCS.2017.20170080
往期精彩回顾
8个地球的科学冷知识颠覆你的世界观！
关于稿件“时间”安排那些事儿~
重磅！新增博士、硕士学位授权点名单出炉，有你的母校吗
适合所有研究生读的好文：阳光温热 科研静好
世界上最有趣最冷门的地图，刷新你的世界观！
组建“自然资源部”的来龙去脉
黄昕：当你动笔，成败已定——来自IEEE评审专家的体会与思考
这个遥感学科的排名比较全，值得分享！
院士论坛| 高俊：图到用时方恨少, 重绘河山待后生——《测绘学报》60年纪念与前瞻
武汉大学老师推出最美赏樱专题地图
学术前沿| 李广云：精密工程测量技术及其发展
SCI收录的中文期刊有哪些？
权威 | 专业|学术| 前沿
微信投稿邮箱 |song_qi_fan@163.com
微信公众号中搜索「测绘学报」，关注我们，长按上图二维码，关注学术前沿动态新勇者莱汀 。
欢迎加入《测绘学报》作者QQ群：297834524
进群请备注：姓名+单位+稿件编号