论文推荐|移动地图制图的句法模型
《测绘学报》
构建与学术的桥梁 拉近与权威的距离
移动地图制图的句法模型
田江鹏, 游雄, 贾奋励
信息工程大学地理空间信息学院, 河南 郑州 450052
收稿日期:2015-10-27; 修回日期:2016-09-06
基金项目:国家863计划(2013AA12A202);国家自然科学基金(41271393;41371382;41671407)
第一作者简介: 田江鹏(1987-), 男, 讲师, 研究方向为地图制图学与地理信息工程。
E-mail:
通信作者: 贾奋励
E-mail:
摘要:采用形式语言的方法,研究了移动地图制图的句法模型。剖析了移动地图制图的过程,将句法模型定位在制图的逻辑演算层面;结合地图表达的层次性和递归性特征,将移动地图制图的句法结构抽象为“制图词汇+句法规则”的最简形式。在制图词汇方面,建立了制图词汇的分类体系,并重点对空间关系谓词系统进行了建模;在句法规则方面,描述了句法操作规则和不同层次的句法单位描述规则。探讨了句法模型的编译流程和关键技术,并通过试验对移动地图制图句法模型的可行性进行了验证。句法模型的本质是一种使用有限规则和词汇动态生成不同地图表达形式的形式语言语法,可作为一种高阶的人机交互制图接口。
关键词: 移动地图 动态制图 句法模型 上下文无关语法 形式语言
The Syntax Model of Mobile Maps Generation
TIAN Jiangpeng, YOU Xiong, JIA Fenli
Abstract: Using the method of formal language (FL), the syntax model of mobile map generation is studied. The syntax model is located in the level of logical calculus of map generation based on the analysis of its process. Combined the hierarchical and recursive characteristics of map representation, the simplest form of syntax structure is abstracted as carto-lexicons and syntax-rules. The classification system of carto-lexicons is established as well as the model of the spatial relation predicate system, and the map operation rules and rules of different levels of syntactic units are discussed. The compilation process and key techniques of the syntax model are discussed, and the feasibility of the model is verified through mobile maps generation experiment. The essence of the model is a kind of formal language grammar, which uses finite rules and lexicons to generate maps automatically, as well as a kind of high-level cartography interface of human-computer interactive.
Key words: mobile maps dynamic cartography syntax model context free grammar formal language
位置服务引起了地图学的巨大变化,移动地图及其制图成为了新的研究热点。移动地图是指在位置服务的背景下,通过移动信息设备实现的基于位置的地图,或是类似的地理信息可视化产品[]。其主要特点可以归纳为:面向用户需求与偏好,运行在具备定位、移动互联网接入功能的移动设备上,实时、动态获取位置和用户需求相关的各种时空地理信息,采用多模式可视化方法进行表达等。对移动地图进行制图,简称移动制图,采取的是动态解析用户需求、动态检索与处理所表达信息、动态设计与实现地图表达的制图技术,属于一种“以图适人、制用同时”[]的地图制作模式。较之传统地图制图,移动制图将地图生成在用户使用的过程中,使得移动制图更加强调制图内容和表达的实时动态特征。
实时动态的要求,使得移动制图需要探索和改进其制图模型和相关技术。形式语言是由公理化表达和数学规则构成的形式化模型,具有描述能力强、易于计算机实现等特点。从地图作为一种人工语言的角度,建立一套能够实现移动地图动态制图的形式模型,统一其语法、语义和语用基础,不失为解决该问题的一种有效方法。在这方面,文献[]从数字地图动态生成的角度,探讨了地图语言的字母表和语法组成(操作、规则和写作机制)。文献[]在空间查询语言的基础上提出了图形表达语言(graphical presentation language, GPL)。文献[]基于XML提出了MapMML语言。文献[]将形式语言的方法扩展到虚拟地理环境的构建中等。作为地图语言的重要研究对象,地图符号的形式化描述、语法系统也是探讨的焦点,例如基于BNF的地图符号描述[],海图符号语言语法规则和制图指令[],专题地图符号自动生成模型[],语义驱动的地图符号动态生成[]等。采用形式语言方法的地图制图研究,虽已取得一定的研究成果,但仍存在句法模型不够系统、实时动态制图技术不够深入等问题,特别是在移动地图制图方面,还有待于进一步加强。
本文针对移动地图的动态制图问题,研究移动地图制图句法模型的构建与编译问题。通过构建一个面向移动地图制图过程的上下文无关地图句法系统,实现利用形式语言指令进行制图,解决移动地图表达的实时动态问题,建立起一种制图需求与制图操作间的自动化处理机制。
1 句法模型的认识1.1 句法模型与形式化
移动地图“以图适人、制用同时”的制图模式,决定了移动制图需兼顾两个方面的内容:一是制图内容的动态计算,二是制图表达的动态叠加,且二者是相互依赖的过程。制图内容和制图表达的可计算,依赖于对人在地图设计和制作过程中的地理信息处理规律的形式化描述:制图内容的形式化,要求构建面向情境的地理要素及其空间关系描述,形成制图系统可识别和使用的语义信息和参数集;制图表达的实时叠加,要求以地理信息的语义分析为基础,通过统一、动态灵活的制图规则系统的设计,组合构造制图实体实现地图动态生成。
形式化的目的,是为计算机设计并提供可供执行的统一语法和语义模型,使之能够按照既定程序执行地图动态制作和生成。制图内容和制图表达的形式化,遵循了5个阶层,即“环境认知→地理概念理解和语义建模→制图逻辑演算→制图系统程序语言→机器指令执行”。这5个阶层是一种相对的高阶至低阶的相互作用关系:越是高阶,人的特点越显著,此时有关图形、语言和认知的思维能力发挥重要作用;越是低阶,计算机的特点越显著,此时机器的快速计算、检索和图形渲染能力发挥主导作用。
句法模型是针对“制图逻辑演算”这一阶层提出的,目的是构建统一的制图语法规则系统。一方面,通过采用一定的语法描述规则来演绎地图制图过程,建立起一种相对于“制图系统程序语言”阶层的高阶形式语言,使得低阶的制图系统能够在该高阶语言的控制下,“动态地”执行制图操作,从而弥补传统制图系统只能按照固化或者部分固化的流程执行制图操作的不足。另一方面,相对于更高阶的环境认知和地理概念分析,句法模型可以通过良好的语法设计,使用形式语言的方式接纳制图内容动态计算的结果,使得计算机更为智能地进行制图。
1.2 句法模型参与的移动制图流程
从制图过程来看,至少包括两个方面:一是根据制图情境确定所需制图要素或数据;二是将这些要素或数据按照一定的制图要求渲染出来。借鉴制图代数模型[]、全息位置地图制图模型[],构建了一个顾及情境约束、制图数据的动态获取与重构、制图表达的动态叠加与渲染,并以制图形式语言衔接的动态制图链,如所示。
制图内容的获取与重构方面:通过地理信息检索、过滤和发现等技术,从泛在互联网络、传感器观测等途径获得数据,形成结构化或半结构化的描述;通过构建地理语义知识库,形成情境约束的制图要素语义分析和理解,并完成地理信息向制图数据的映射转换,转换后的数据采用形式语言的语法规范进行描述。
制图表达的编译与渲染方面:基于句法模型,构建形式语言的编译器,编译器将制图语句编译为制图数据的抽象语法树(abstract syntax tree, AST),作为图形渲染阶段的输入数据;再通过遍历抽象语法树,调用制图引擎的应用程序接口,完成地图的渲染与输出。
2 句法模型的构建2.1 移动地图的结构化
类比语言的结构[],可将移动地图的表达视为由多级制图单位(材料)通过各种组合关系构造而成的层次结构,具有典型的层次性特点。例如,将一幅地图视为篇章,则各个图层可视为段落;空间要素及其位置的表达可视为命题,要素或命题间空间关系的表达可视为语句;符号可看作是构成该语言的词汇。可将其归纳为篇章层、句法层和词法层:篇章层描述不同句法表达集合之间的关系;句法层描述的是空间要素及其相互之间的空间关系,以及它们的表达规则;词法层是地图符号层次,关注符素[-]组合为符号的规则和方法。
确立移动地图构造的层次结构,可抽象不同制图单位及其组织规律。参照文献[]提出的“主语+谓语+地点上下文”的一般结构,“地图符号+定位谓词+地点副词”构成了命题,用以表征地理要素及其空间位置;“命题+空间关系谓词+命题”可以构成一个复合的制图语句,用以表征地理要素之间的空间关系。相应的,还可以归纳出诸如“制图语句+空间关系谓词+制图语句”、“制图语句+空间关系谓词+命题”、“命题+空间关系谓词+制图语句”等形式复杂的从句。通过反复使用(有限的)符号、命题等制图材料,在特定的句法规则控制下,可构成无限的地图表达形式。本文将这一特点归结为递归性特征,它是地图多样化表达能力的来源。
根据层次性和递归性特征,可以将移动地图制图的句法结构抽象为“制图词汇+句法规则”的最简形式。制图词汇是指地图符号、定位谓词、地点副词等描述制图对象、操作和地点上下文的词汇。句法规则是诸如“命题=地图符号+定位谓词+地点副词”这类将制图词汇构造为更高级句法成分的组合规则。
通过3种要素的空间关系的表达为例,对句法结构进行示例说明,其中,制图词汇包括:地图符号:Sgreen(绿地)、Striangle(土堆三角点)、Sroad(道路);制图谓词:Plocate(定位谓词)、Pcontain(包含空间关系)、Pintersect(交叉空间关系);地点副词:Gring、Gsring、Gpoint(使用几何对象形式描述的空间位置)。
句法规则有:制图命题=地图符号+定位谓词+地点副词;制图语句=制图命题+空间关系谓词+制图命题;制图语句=制图语句+空间关系谓词+制图命题。
2.2 句法模型的数学建模
文献[]将自然语言形式模型归纳为4种文法层次:0型、1型、2型和3型文法,且每一种文法都是前一种文法的特例化。2型文法又称上下文无关语法(context free grammar, CFG),其典型的特征在于递归,较为适合描述移动地图的层次性和递归性特征。因此,移动地图制图的句法模型G可定义为以下4元组
式中,VR={r1, r2, …, rn}, (i=1, 2,…, n)是句法生成重写过程中的句法规则集合,n是规则的数量,ri是句法表达的句法规则(syntax-rule),不能处于生成过程的终点;VM={m1, m2, …, mk}, (i=1, 2,…, k)是句法重写过程中使用的制图词汇集合,k是词汇的数量,mi是句法表达的制图词汇(carto-lexicon),例如地图符号、空间关系谓词等,只能处于生成过程的终点,其中,空间关系谓词是构成地图语言和自然语言语法模型的显著区别特征;S是语法形式模型生成的起点,可以取VR集合中不同规则并作为初始规则;R是规则的重写形式,其一般形式为
式中,A∈VR且A≠Ø,即A必须是VR集合中的某一规则;ω是规则的重写结果。以此,示例中的制图对象及其相互关系就可以描述为
R:
(1) sentence→sentc+prid+prop
(2) sentence→prop+prid+prop
(3) prop→synbol+prid+geom
(4) synbol→{Sroad, Striangle, Sgreen}
(5) prid→{Plocate, Pcontain, Pintersect}
(6) geom→{Gpoint, Gstring, Gring}
其中,R的规则(1)-(6)解释了VR中的句法规则的递归形式:规则(1)-(2)解释了制图语句的递归规则,规则(3)解释了制图命题的递归规则,规则(4)-(6)分别解释了符号、谓词和几何对象重写的规则。可以看出,移动地图制图句法模型G,其核心在于制图词汇VM和句法规则R的设定。下文将重点对制图词汇和句法规则进行说明。
2.3 制图词汇(carto-lexicon)
文献[]提出了将点状符号作为名词,符号的颜色等修饰作为形容词、要素与修饰之间以及要素与要素之间的空间关系作为动词,副词反映距离和方向等思想。文献[]认为在句子结构中,词汇不仅参与制图语句的构图,还具有多种不同的功能,例如表示某种空间关系,表达距离和方向,连接制图语句等。综合这些思想,本文将制图词汇概括为以下几种类型(见):
句法成分 | 词汇类型 | 说明与举例 |
主语 | 普通符号 | 各种地理事物、空间形态和过程的符号表达,例如Symbol (11010101)表示三角高程点符号。 |
专题符号 | 专属要素或专题要素的符号表达,例如军队标号、旅游专题符号等。 | |
组合符号(名词词组) | 通过不同的构造、派生方法得到的组合符号,相当于名词词组。例如带有载重标识的桥梁符号。 | |
谓语 | 空间关系谓词 | 空间关系谓词反映了空间主语(要素)和空间谓语之间的关系。 |
时间、地点副词 | 时间描述 | 描述时间的词,如Time (2015/10/10 13:26:01) |
位置描述 | 采用几何对象描述空间位置,如Point (113.5 34.7);LineString (113.5 34.7, 113.6 34.5, …);Polygon (113.5 34.7, 113.6 34.5, …)等。 |
在该分类中,能够描述和处理要素间空间关系的是空间关系谓词。对空间关系的描述,不仅受到物体之间几何关系的影响,也受到地理本体所属类型和语言环境等非空间属性的影响[]。因此,诸如4交模型、9交模型等高度形式化的拓扑关系模型,不完全适合于解决地理问题,还需顾及要素的形状和语义[-]。例如,一条河流可以“流入”另一条河流,道路“横跨”河流,两条道路“相交”等。若从拓扑关系角度,可能存在要素之间的拓扑关系一致,但实际中不可能存在的情况,例如“河流‘流入’道路”。因此,“流入”“横跨”和“相交”这些空间关系词汇,通过几何和语义关系的记录,精确地描述了要素间的空间关系,本文称之为空间关系谓词。
通过对空间特征和空间关系进行语义扩展,可建立空间关系谓词系统。本文将空间特征和空间关系划分为位置、方向、距离和拓扑4个方面,每一个谓词均对应一个谓词函数(如)。
谓词系统分类 | 表征的空间关系 | 标识符示例 | |
空间特征 | 位置 | 位于、定位、… | Locate/Position/... |
方向关系 | 绝对参照系 | 东、南、西、北;角度、… | OriEast/OriSouth/OriWest/OriNorth; OriAngle/... |
内参照系 | 前、后;上、下;内、外;… | OriForward/OriBackward; OriTop/OriDown; OriInner/OriOuter; ... | |
相对参照系 | 前、后、左、右;钟面方向;… | OriFront/OriBack/OriLeft/OriRight; OriClock; ... | |
距离关系 | 定性描述 | 近、远;很近、很远;较近、较远;… | DisCentre/DisMin/DisMax/... |
定量描述 | 距离;… | Distance; ... | |
拓扑关系 | 相离 | 附近;周围;周边;沿着;平行;环绕;… | TpNearBy/TpAround/TpPeriphery/TpAlong/TpParallel/TpSurround/... |
相邻 | 边缘;流入;经过;邻接;相接;… | TpBroder/TpInflow/TpPass/TpAdjoin/TpClose/... | |
相交 | 相交;穿越;横跨;汇入;… | TpIntersect/TpCross/TpTraverse/TpInflow/... | |
包含 | 上;包含;内部;里面;… | TpOn/TpContain/TpInner/TpInside/... |
采用几何对象模型描述和记录空间位置数据,实现对地理实体几何形状的概括和抽象。几何对象可以分为点、线和面3种基本形式。点可以分为单点(Point)或组合点(MultiPoint);线可以重写为折线(LineString)、环(LineRing)以及线段(直线段(Line)、贝塞尔曲线(Bezier)、圆弧(CircularArc)和椭圆弧(EclipseArc));面则可以重写为多边形(Polygon)及其组合(MultiPolygon)。
2.4 句法规则(Syntax-Rule)
与上下文无关语法等价的巴科斯范式(Backus-Naur Form, BNF),描述形式具有简洁清楚、易于阅读、容易理解等特征,常作为计算机语言语法描述的元语言,因此可采用BNF对句法的重写规则A→ω进行描述。定义移动地图制图语言句法的一般规则是
〈制图语句〉::=〈句法操作〉〈句法单位描述〉。
2.4.1 句法操作规则
句法操作是指创建、删除、编辑修改某一句法单位的功能操作。借鉴GPL[, ]的6种绘制方式,并一定程度上顾及人的自然语言表达习惯,制定了以下5种句法操作:创建(Create),创建并绘制一个新的制图对象;删除(Delete),删除一个制图对象并擦除地图绘制;叠加(Overlay),在已有的制图对象上叠加新的制图对象,属追加操作;高亮(Highlight),高亮强调表达某个制图对象,使之视觉凸显;选中(Select),选择某一制图对象,对其进行增量编辑和修改。句法操作规则的BNF描述见。
句法操作规则的BNF形式 |
〈carto_stmt〉∷=〈create_stmt〉|〈delete_stmt〉|〈overlay_stmt〉|〈highlight_stmt〉 |
〈create_stmt〉∷='Create'〈carto_object〉 |
〈delete_stmt〉∷='Delete'〈object_name〉 |
〈overlay_stmt〉∷='Overlay'〈object_name〉〈carto_object〉 |
〈highlight_stmt〉∷='Highlight'〈object_name〉 |
〈select_stmt〉∷='Select'〈object_name〉 |
〈carto_object〉∷=〈map〉|〈layer〉|〈sentence〉|〈geometry〉|〈symbol〉 |
2.4.2 句法单位描述规则
句法单位描述规则主要分为:地图和图层描述规则(篇章层);制图语句描述规则(句法层);制图符号描述规则和几何对象描述规则(词法层),如所示。其中,在制图语句描述规则方面,使用了〈sql_select_stmt〉规则,可兼容SQL的SELECT-FROM-WHERE语法,实现从空间数据库中检索几何和属性数据,增强制图数据的查询和制图效率。
层次 | BNF规则 |
图、图层 | 〈map〉∷='Map'([〈db_link〉, ][〈user_region〉, ]〈map_expr〉) 〈map_expr〉∷=〈map_type〉〈layer_list〉 〈map_type〉∷=〈single_2dmap〉|〈single_3dmap〉|〈overlay_map〉 〈layer_list〉∷=(〈layer〉{, 〈layer〉}) 〈layer〉∷='Layer'(〈sentence〉{, 〈sentence〉}) |
语句、命题 | 〈sentence〉∷='Sentence'(〈sentence_expr〉) 〈sentence_expr〉∷=〈sentence_expr〉〈spatial_pred〉|〈sentence_expr〉|〈proposition〉 〈proposition〉∷=〈symbol〉〈spatial_pred〉〈geometry〉|〈symbol〉〈spatial_pred〉(〈sql_select_stmt〉) |
几何对象 | 〈geometry〉∷=〈puntal〉|〈lineal〉|〈polygonal〉 〈puntal〉∷=〈point〉|〈multi_point〉 〈lineal〉∷=〈line_string〉|〈line_ring〉|〈segment〉 〈segment〉∷=〈bezier〉|〈circular_arc〉|〈eclipse_arc〉|〈line〉 〈polygonal〉∷=〈polygon〉|〈multi_polygon〉 |
符号 | 〈symbol〉∷='Symbol'(〈symbol_name〉|〈symbol_id〉) |
3 编译器构建与制图试验3.1 编译器架构设计
编译器是以移动地图制图的制图语句为输入,通过词法分析、语法分析生成抽象语法树,并调用底层制图系统API实现移动地图动态制图,其总体设计方案和流程可用表示。其中,根据句法规则集VR和制图词汇集VM,构建词法和语法分析的规则文件;编译错误提示与反馈模块则提示编译过程中的错误或警告信息。其中的关键步骤包括:①对所输入的制图语句进行词法分析;②基于词法分析的结果,按照重写规则进行语法分析;③根据语法分析的结果,重建抽象语法树;④遍历抽象语法树,生成地图场景树(MapSceneGraph),渲染至终端屏幕。
采用了较为成熟的Flex和Bison[]作为词法分析和语法分析的工具。按照Flex和Bison的规则编写规范,分别按照制图词汇集、句法规则集提供的标识符和规则,编写Carto-Lexicon.l的词法规则文件和Carto-Rule.y的句法规则文件(注:“.l”为Flex规则文件类型,“.y”为Bison规则文件类型);使用Flex/Bison进行编译,可以得到能在制图系统层面使用的词法分析程序和句法分析程序模块。
3.2 编译生成实例
生成实例采用的数据为某万达广场室内数据,采用几何对象描述并记录几何数据,并用二进制方式存储在sqlite数据库中,以便于使用〈sql_select_stmt〉规则,达到移动端的快速空间数据检索和使用的目的。
3.2.1 单一语句的生成过程和效果
给出了一组制图输入语句。以该广场室内一楼数据表FC_862000010020300001_F1为例,分别构建了建筑物、购物、卫生间、问讯处和电话亭等制图语句,并分别为每一类要素赋予了相应的地图符号。则显示了该语句的制图效果。
试验用制图形式语句 |
CREATE MAP2D'IndoorMap'( |
'layer1'( |
SENTENCE'building'(SYMBOL (102101902) LOCATE ('SELECT*FROM FC_862000010020300001_F1 WHERE style=4')), |
SENTENCE'shopping'(SYMBOL ('fill_shopping') LOCATE ('SELECT*FROM FC_862000010020300001_F1 WHERE style=5')), |
SENTENCE'wshj'(SYMBOL ('mark_wsj') LOCATE ('SELECT*FROM FC_862000010020300001_F1 WHERE style=7')) |
), |
'layer2'( |
SENTENCE'wenxun'(SYMBOL ('mark_wenxun') LOCATE ('SELECT*FROM FC_862000010020300001_F1 WHERE style=5 AND poi_no=105')), |
SENTENCE'telephone'(SYMBOL ('mark_telephone') LOCATE ('SELECT*FROM FC_862000010020300001_F1 WHERE style=5 AND poi_no=106')) |
) |
) |
3.2.2 不同语句动态生成的效果
、给出的是模拟不同制图情境、给定不同的制图语句输入,得到的一组实时地图生成效果。其中,为Android终端上的生成效果,基于二维图形引擎实现的伪三维室内地图表达;则是基于三维地图符号生成的室内三维场景。
从不同语句的生成实例来看,基于移动地图动态制图句法模型构建的编译器,能够实现根据给定的制图语句,通过编译和渲染等过程实时生成相应的地图图形。地图生成的效果,取决于制图语句的构成,包括图层、语句、符号、几何数据的描述等。
4 结论
本文探讨了移动地图动态制图的句法模型,将移动地图的表达形式抽象为“制图词汇+句法规则”的最简形式,使得移动制图过程演变为句法规则控制下的制图词汇的构造过程,体现了“通过有限符号表达无限复杂的真实世界”这一动态制图特征。建立起了一种相对于“制图系统程序语言”的高阶形式语言,使得低阶的制图系统能够在这一高阶语言的控制下,实现了移动地图的动态制图。
计算语言学认为,公理化的形式语言描述使得机器人“仿真”人类的认知行为成为可能[],那么,公理化的制图形式语言则在提高制图系统的智能化水平方面具有较大潜力。移动制图的句法模型及其自动化编译机制,立足于制图逻辑演算阶层,一定程度上将属于人类智力活动的空间认知、地理概念语义推理,与属于计算机的快速计算、检索和图形渲染能力结合了起来。同时,使用形式语言的方式接纳概念和语义层面的处理结果,对于地图空间认知学者寻求能够模拟地图认知机理、表达地理语义计算过程的计算机工具,具有较好的借鉴意义。
进一步的研究将会集中在以下几点:一是移动地图制图形式语言的认知和语义问题,BNF和CGF描述能力很强,但是缺乏语义描述,如何统筹考虑句法模型和语义模型,将是一个具有挑战性的难题;二是句法规则的规范化;从数学模型来看,句法模型的生成能力是否强大、生成效率是否高效等,取决于重写规则制定的合理性与规范化程度,对句法规则进行规范化,建立制图语言语法标准,是进一步深化句法模型需解决的问题;三是移动地图制图的词法模型与篇章模型的系统化研究,结合句法模型,可形成完整的移动地图制图的语法基础。
【引文格式】田江鹏,游雄,贾奋励,等。 移动地图制图的句法模型[J]. 测绘学报,2016,45(11):1352-1360. DOI: 10.11947/j.AGCS.2016.20150544
更多精彩内容:
行业动态|吉林一号视频3星将于明年1月发射 正式命名为林业一号卫星
论文推荐|付仲良:M-Quadtree索引:一种基于改进四叉树编码方法的云存储环境下空间索引方法
论文推荐|孙文彬:历史数据和强化学习相结合的低频轨迹数据匹配算法
权威 | 专业 | 学术 | 前沿
微信投稿邮箱 | song_qi_fan@163.com
微信公众号中搜索「测绘学报」,关注我们,扫描上图二维码,关注学术前沿动态。
欢迎加入《测绘学报》作者QQ群: 297834524
进群请备注:姓名+单位+稿件编号