面向道路网络中图形与组合图形检索的基于不变空间关系与子图匹配的方法

《ISPRS International Journal of Geo-Information》：Invariant Spatial Relation-Based Road Network Graphics Retrieval for GPS Art Gang Li and Zhongliang Fu

　　

摘要：本文提出一种集成不变空间关系（Invariant Spatial Relationships）与子图匹配（Subgraph Matching）的图形检索方法及一种基于贪婪策略的组合图形检索算法，用于在道路网络中自动检索与输入矢量图形形状相似的单一路径及由多个子图形构成的组合路径。该方法将输入图形的转向角与线段长度比作为形状不变约束构建约束图，并将其转化为子图同构匹配问题在道路网络动态图上进行检索；通过引入近似线段（Approximate Line Segments）扩展可匹配边集以提高检出率。针对组合图形，各子图形独立初检后依据方向偏差角δ与相邻子图形中心连线方位角β判断可组合性，采用评分函数筛选并按贪婪策略依次拼接。实验在五个中国城市真实路网及模拟路网数据集上进行，结果表明该方法能在秒级时间内准确检索单一字母数字图形（如"5""E""A"等）及组合图形（如"520""LOVE""1314""I?U"），近似线段的使用显著提升了检索成功率与结果规模，评分排序能有效区分形状相似度高低。该方法为GPS艺术（GPS Art）路线生成与定制化导航路径服务提供了自动化解决方案。

论文解读：面向道路网络中图形与组合图形检索的基于不变空间关系与子图匹配的方法

一、研究背景与意义

传统GPS艺术（GPS Art）路线绘制依赖人工在地图上描摹或借助专用软件手动调整，缺乏自动化从路网中直接提取符合特定图形（如字母、数字、符号及组合文字）行走路径的能力。已有研究中Balduz等无法获取实际路经，Waschk与Krüger等则需人工干预调整方向、位置和尺度。定性空间场景匹配（Qualitative Spatial Scene Matching）虽可用于无地理坐标的空间比对，但既有方法未专门针对路网中形状相似性检索进行系统设计。道路网络缺乏输入图形的地理坐标信息，仅含拓扑与几何属性，因此需借助形状不变量（转向角、相对边长比）来描述输入图形并建立匹配约束。本研究旨在提出一种无需人工干预、可自动从城市道路网络（OpenStreetMap数据）中检索单一图形及组合图形对应行走路径的算法，发表于《ISPRS International Geo-Information》。

二、主要关键技术方法

研究人员以OpenStreetMap路网提取的步行友好道路网络为实验对象（深圳南山、武汉洪山、北京东城、上海闵行、西安长安区，各10km×10km），采用OSMnx工具包构建路网图G(V,E)。关键技术包括：（1）将输入矢量图形抽象为节点序列及其间转向角φ_i与线段长度比θ_i（不变空间关系），构建约束图；（2）将路网中原始边及通过引入容差ε合并共线近似点生成的近似线段（Approximate Line Segments）共同构成动态检索图；（3）将图形检索转化为带角度与长度比约束的子图同构匹配（Subgraph Isomorphism Matching），通过回溯枚举所有满足约束的路径并依欧氏节点距与垂距打分排序；（4）组合图形检索对各子图形分别初检得结果集{Y₁,…,Y_m}，以最小基数集为起始种子，用判断函数Judge(e_A)=1筛选满足方向偏差|δ_b?δ_s|≤σ₁且方位偏差|β_ab?δ_s|≤σ₂的候选，按Score_A=1/(|δ_b?δ_s|/σ₁+|β_ab?δ_s|/σ₂)降序取最优，贪婪拼接直至完成；（5）组合结果综合评分Score_C=N(S_β)+N(S_d)（S_β为相邻子图相对方向均方差，S_d为中心距均方差，N为归一化函数），高分者排列平直、间距均匀。模拟数据集含"3""8""V""N""K""G""A""M"及心形五角星等带断点近似线段模板。

三、研究结果

4.1 实验数据（Experimental Data）

研究人员选取五城市10km×10km区域OSM路网及含字母数字与符号的模拟路网，设定φ=0°、θ=0°、ε=0.01（模拟）与φ=15°、θ=15°、ε=0.3（真实路网）为默认参数。

4.2.1 模拟路网实验结果（Experiment Results in the Simulated Road Network）

对比完整算法、去除近似线段变体及去除长度比变体的检索结果数与真值发现：完整算法检索数与真值完全一致无漏检重检；去近似线段后检索数减少且"A""G""V"、心形、五角星无法检出，证明近似线段提升成功率与检出量；去长度比约束致部分图形（"A""K""N""3""V""G"）检索数虚高并出现短线或严重变形误检，说明长度比约束过滤低相似误检、保障形状保真度。

4.2.2 真实路网实验结果（Experiment Results in the Real Road Network）

放松φ=15°、θ=15°、ε=0.3后各测试实例检索耗时<2s，耗时与总迭代次数正相关而非边数或结果数。参数敏感性实验显示φ与ε越小约束越严检出越少，双零时仅"E"可检，故适度放宽以提升成功率。近似线段消融实验表明启用近似线段后检索结果数量与各长度区间分布均高于禁用情况，且能检出心形，证实其对真实路网检索数量与尺度的提升作用。按评分降序排列结果显示Rank-1结果形状与输入高度吻合，低排名结果出现线段长短不一或转角明显偏离，验证单图形评分有效性。

4.3 组合图形算法实验结果（Graphics Combination Algorithm）

设σ₁=σ₂=60°，成功从真实路网检索"520""1314""I?y(原文I?y)""LOVE"等组合图形。"1314"耗时最长（约1725.6s）因子图形"1"初检结果集过大，"O"为初检最少故耗时最短，证实组合耗时与首子图结果集基数正相关。按组合评分Sort Descending显示高分结果子图形沿参考方向近似直线均布、间距匀称美观，低分结果排布歪斜散乱，验证组合评价公式合理性。

四、讨论与结论总结

研究人员指出该方法通过转向角与长度比不变关系解决输入图形缺地理坐标问题，近似线段动态图扩充匹配边提高检出规模与可达长度（最大约8km），贪婪选最小初检集启动与方向—方位评分降低组合复杂度。相比需人工干预的前人工作实现了全自动无坐标特定形状路径检索，将定性空间场景匹配拓展至GPS Art问题，给出通用无坐标空间场景匹配范式——基于不变空间关系建约束图再转子图匹配。局限性在于同种语义可对应多图形表达致难检索异形同义路径，复杂图形（汉字、生肖）对路网形态要求苛刻难检出，"1314"类因某子图初检爆炸致耗时长。未来拟朝语义驱动（Semantic-driven）弱形状约束检索及子图结果预剪枝提效方向开展。

结论：本文提出的融合不变空间关系与子图匹配的图形检索法及基于贪婪策略的组合图形算法，可有效在道路网络中自动检索与输入图形形状相似的单一及组合路径，为智能终端定制导航与大众GPS Art实践提供技术支持，并为无地理坐标下的空间场景匹配问题提供了通用求解思路。