地標分層多粒度路徑導(dǎo)引描述方法

李 霖，毛 凱，譚永濱

武漢大學(xué) 資源與環(huán)境科學(xué)學(xué)院，湖北 武漢 430079

1 引 言

路徑導(dǎo)引是導(dǎo)航與位置服務(wù)領(lǐng)域重要研究內(nèi)容，是人類活動和日常生活的一個基本組成部分。路徑導(dǎo)引是一個空間認知過程，也是建立在空間認知基礎(chǔ)之上的空間關(guān)系推理過程。文獻［1］將路徑導(dǎo)引過程分為3個認知階段，依次是當前環(huán)境認知、最優(yōu)路徑選擇和概念轉(zhuǎn)換結(jié)果（語言或圖像）輸出。路徑導(dǎo)引描述通常由一系列連續(xù)的連接點（junction）組成。連接點被定義為一個二元組〈description，instruction〉，其中description是對空間位置的描述（如前方100m、環(huán)島第3出口等），instruction表示在該空間位置采取的行動（如右轉(zhuǎn)、轉(zhuǎn)出等）［2］。依次轉(zhuǎn)彎 （turn－by－turn）路徑導(dǎo)引方式就是對路徑計算結(jié)果中的每一個連接點依次輸出，而對于一條復(fù)雜的路徑結(jié)果，輸出全部的路徑導(dǎo)引描述會非常冗長復(fù)雜，增加人在尋路過程中的認知負荷和記憶負荷。文獻［3］對區(qū)域環(huán)境的熟悉程度不同提出了4種尋路模式：熟知者、半熟知者、探索者、輔助尋路，討論了尋路決策與地標之間的關(guān)系。地理信息的語言文字描述，在一定程度上對地理，概念的理解總存在一定語言上的模糊性［4］，對熟悉周邊環(huán)境的本地人而言，基于地標的描述方式更加符合人們的認知習(xí)慣，地標作為位置信息的載體，對于安撫情感和保證尋路決策的正確性有很大作用［5］?；诘貥说穆窂綄?dǎo)引描述成為當前導(dǎo)航技術(shù)領(lǐng)域研究熱點之一。

基于地標的路徑導(dǎo)引描述的關(guān)鍵在于研究基于導(dǎo)航語義的地標參考空間位置描述方法。文獻［6］認為定性位置（qualitative location，QL）是目標對象與其他特征的相對參照位置，正是通過未知特征與已知特征之間的空間關(guān)系來描述或者獲得關(guān)于目標對象的空間位置。文獻［7］提出一種基于地標的定性參考（landmark based qualitative reference，LBQR）系統(tǒng)，通過將Voronoi圖與地標相結(jié)合，實現(xiàn)定性空間的位置描述，但該方法的應(yīng)用依賴一個假定：各地標顯著度是等價的，這與實際情況有一定差距。文獻［8］對LBQR進行了改進，考慮到地標顯著度對定性空間范圍的影響，提出加權(quán)Voronoi圖與地標的空間位置描述，但該方法僅以校區(qū)為范圍在單一的尺度下進行研究，并未考慮知識是有粒度的［9］，對空間現(xiàn)象的認知表現(xiàn)為從總體到局部、從概略到細微、從重要到次要的層次順序［10］，并且不同的任務(wù)對數(shù)據(jù)尺度的要求不同［11－12］，多粒度的描述方法則能更好地處理路徑表達的不確定性。總體上，上述研究局限于空間中各自孤立、離散的位置的描述，而并未考慮在駕駛導(dǎo)航環(huán)境下，位置描述有序性的特點?；诖?，本文試圖針對不同尺度的地標認知空間完成基于導(dǎo)航語義的多粒度的形式化建模，設(shè)計更符合人們認知習(xí)慣的路徑導(dǎo)引描述方法。

2 多粒度路徑導(dǎo)引描述

2.1 候選地標數(shù)據(jù)集

文獻［5］從景觀的角度提出構(gòu)成城市的5個基本要素：道路、邊界、區(qū)域、節(jié)點、標志物。文獻［23］將地標定義為環(huán)境中唯一的或者與鄰近相比具備顯著性的特征體。文獻［13］根據(jù)功能性將地標分為兩類：定向地標和定位地標。定向地標具有相當?shù)闹?，主要?yīng)用于空間知識的表達和共享，承擔(dān)定向的作用，其不一定分布于規(guī)劃的路徑附近；定位地標主要應(yīng)用于尋路過程中的位置指引或反饋，承擔(dān)定位的作用，通常沿著規(guī)劃的路徑周邊分布。文獻［14］根據(jù)對人們尋路決策的影響將地標分為決策地標、潛在決策地標和沿途地標3類。在導(dǎo)航語義下，獨立于尋路者之外的地理參考元素都可能因為視覺外觀、位置分布或功能特征而作為獲選地標，如道路及其附屬設(shè)施同樣具備定位或定向功能，亦可作為候選地標對象，又如交叉口、立交橋等在路徑導(dǎo)引過程中影響到?jīng)Q策結(jié)果。

綜上考慮本文候選地標數(shù)據(jù)集構(gòu)建步驟如下：① 選擇導(dǎo)航數(shù)據(jù)庫中的POI數(shù)據(jù)集和道路附屬物為數(shù)據(jù)源；② 對路徑規(guī)劃的結(jié)果進行分析，確定路徑規(guī)劃的節(jié)點和主要形點，并以此作為輸入，對數(shù)據(jù)源進行緩沖區(qū)分析；③ 將分析的結(jié)果即作為候選地標數(shù)據(jù)集。

2.2 導(dǎo)航地標顯著度

文獻［15］以建筑物為研究對象，從視覺、語義和結(jié)構(gòu)3個方面研究對地標的顯著度影響。文獻［24］在此基礎(chǔ)上進行了改進，引入了可視性參數(shù)，認為對于特定路徑上下文來說，如果地標無法或難以通視（如遮擋情形），那么顯著度也勢必受到影響。導(dǎo)航地標顯著度（Sf）可由以下公式計算

式中，ωv，ωs，ωt＞0且Σω＝1；Sv表示視覺特征；Ss表示語義特征；St表示結(jié)構(gòu)特征，Sa表示通視程度；ωv、ωs、ωt分別表示視覺、語義、結(jié)構(gòu)的權(quán)重系數(shù)。

視覺特征Sv定義為大小、形狀、顏色等外部特征的度量，主要反映視覺上與周圍環(huán)境的差異程度。在駕駛導(dǎo)航環(huán)境下，視覺特征對于使用者來說更為重要，因此也是本文研究的重點。本文中視覺特征值是通過模擬駕駛試驗獲取，該試驗是建立在兩點假設(shè)基礎(chǔ)上：① 視覺特征的地標在視域范圍內(nèi)是可見的；② 地標的視覺特征值與其在視域范圍內(nèi)出現(xiàn)頻次相關(guān)，可認為出現(xiàn)頻率越高視覺特征值越大，反之亦然。建立視覺特征值Sv與地標出現(xiàn)頻次f（x）函數(shù)關(guān)系如下式

式中，xmin、xmax分別為樣本中地標出現(xiàn)頻次的最小值與最大值。

結(jié)構(gòu)特征St定義為空間布局等效用特征的度量，主要反映個體對整體貢獻的差異程度。對于車載導(dǎo)航而言，地標的結(jié)構(gòu)特征主要表現(xiàn)為定向作用，距離道路越近的地標結(jié)構(gòu)特征越高，反之，距離道路越遠結(jié)構(gòu)特征越低。為了計算的方便，本文建立結(jié)構(gòu)特征值St與地標到道路中心線投影距離dprj的映射關(guān)系，如下表所示。

表1 投影距離dprj與結(jié)構(gòu)特征值St映射Tab.1 Mapping of dprjand St

語義特征Ss定義為文化、歷史、特色等內(nèi)部特征的度量，主要反映屬性上與周圍環(huán)境的差異程度。但是在導(dǎo)航過程中，由于使用者在短時間內(nèi)中難以迅速判別地標的語義特征，因此語義特征對導(dǎo)航地標顯著度的影響在這里本文不作進一步討論。

基于上述分析，導(dǎo)航地標顯著度的計算公式為

式中，ωv，ωt＞0且Σω＝1。

2.3 多層加權(quán)Voronoi圖

從理論角度來講，多粒度分析提倡通過不同的分辨率或尺度，對地理數(shù)據(jù)中出現(xiàn)的知識進行認知以及探索。在日常生活實踐中，人們的空間認知和空間行為大多與尺度相關(guān)的。有研究表明，地標作為空間認知過程中的重要參照物，也往往表現(xiàn)為分層的空間認知結(jié)構(gòu)［10，16］。文獻［17］根據(jù)影響范圍的不同，將地標分為局部地標和全局地標，并提出了視域空間的概念，本文借鑒這種思想，并進一步細化將城市地標由大到小劃分為5個級別：城市級、區(qū)域級、街區(qū)級、街道級、視域級，具體描述如表2所示。

表2 城市地標分級Tab.2 Levels of city landmarks

另一方面，地標對城市空間的影響符合空間相互作用理論，即地標對周圍空間的影響力與地標的顯著度成正比。本文將地標顯著度定義為權(quán)重，引入加權(quán) Voronoi（weighted Voronoi，WV）來解決這一問題。位于加權(quán)Voronoi圖多邊形中的每個點到該多邊形地標點的距離與該點到相鄰多邊形地標點的距離之比小于兩地標點的權(quán)重之比（如圖1所示）［18］。

圖1 常規(guī)Voronoi圖與加權(quán)Voronoi圖Fig.1 Voronoi and WV

綜合以上因素可知多層加權(quán)Voronoi圖是建立分層地標參考系的基礎(chǔ)之上，故本文采用多層加權(quán)Voronoi圖實現(xiàn)空間剖分，具體實現(xiàn)方法如下：

（1）按照文獻［19］中提出的迭代法，對候選地標數(shù)據(jù)集L進行分層處理，可得到每一層地標集合記作Li，i∈N。

加權(quán)Voronoi圖的算法實現(xiàn)有柵格法和矢量法，出于模型表達及計算效率等因素考慮本文采用矢量法［20］構(gòu)造加權(quán)Voronoi圖。

2.4 基于分層地標的路徑導(dǎo)引描述

路徑計算的結(jié)果通常是以首尾相接、連續(xù)的弧段來描述，記作

為了描述的方便，將Rs稱作弧段路徑。對于第i層，將加權(quán)Voronoi圖Vi與弧段路徑Rs求交，根據(jù)公式（4）即可得到第i層地標路徑

式中，T（）表示以地標為中心的泰森多邊形。

考察公式（5）的幾何意義，對于中每一個地標，與其鄰近地標li（li?）相比，與弧段路徑Rs距離最近，這一結(jié)果符合認知習(xí)慣，即在顯著度相似的條件下，距離人越近的地標越容易被關(guān)注。在建立分層地標參考系之后，本文以簡化的方式生成多粒度路徑導(dǎo)引描述，即在對應(yīng)層級下將集合中的地標順序輸出，形如

在實際應(yīng)用中，在獲得各層級地標路徑之后，通過進一步定性和定量的空間方位計算，可轉(zhuǎn)換為更容易接受的多尺度自然語言描述［21］，因為不是本文討論重點，這里不作進一步展開。歸納起來，算法描述如下

圖2 算法流程圖Fig.2 The flow of the algorithm

3 試驗設(shè)計及結(jié)果

城市街景是以影像的方式對城市道路及其周邊環(huán)境的真實記錄與再現(xiàn)，包含了傳統(tǒng)地圖所不能表現(xiàn)的空間語義，代表著地球?qū)嶋H的物理狀況，是帶有與人們生活環(huán)境相關(guān)的社會、經(jīng)濟和人文知識的 地 球 全 息 圖 （knowledge based GIS）［22］。本文在武漢公益地圖網(wǎng)站（2010年3月更新）上進行模擬駕駛試驗，以間隔15～20m的步距進行地標采樣，記錄每個全景影像采樣點視距內(nèi)可辨識的地標對象，累計采集可視POI 717個。從公信度較高的谷歌地圖數(shù)據(jù)源（2011年更新）上采集地標及POI共計1442個，以此作為試驗樣本數(shù)據(jù)。

試驗選取了武漢市洪山區(qū)珞瑜路魯巷至武漢天河機場路段，橫跨武昌、漢陽、漢口三鎮(zhèn)，全長約43.5km。通過試驗計算得出 “中南大酒店”、“黃鶴樓”、“武漢長江大橋”等地標從街景上可辨認次數(shù)均超過20次，視覺特征值Sv均大于0.8，也就是說在視覺特征更為明顯，其中，“卓刀泉立交橋”、“武漢長江大橋”、“江漢橋”等地標由于其附著于道路上，相較于“黃鶴樓”、“群光廣場”、“中國電信湖北公司”等地標距離道路更近，與道路的結(jié)構(gòu)關(guān)系更顯著，結(jié)構(gòu)特征值St均為1。將導(dǎo)航地標的視覺特征值Sv和結(jié)構(gòu)特征值St代入公式（3）計算顯著度Sf。

接著試驗按照上文所述步驟，分別以地標的經(jīng)緯度和顯著度作為加權(quán)Voronoi圖的發(fā)生點的坐標和權(quán)重構(gòu)造多層加權(quán)Voronoi圖，計算結(jié)果如圖3所示。其中圖3（a）表示大尺度下加權(quán)Voronoi圖，沿途經(jīng)過卓刀泉立交橋、黃鶴樓、武漢長江大橋等城市級地標；圖3（b）和圖3（c）分別表示區(qū)域級和街區(qū)級中等尺度下計算結(jié)果，為了方便對比表示，圖3（c）是圖3（b）的局部放大；圖3（d）表示街道級小尺度下計算結(jié)果，與圖3（c）相比可以看到街道級地標個數(shù)明顯增多，剖分圖形更加細化。

最后試驗將導(dǎo)航規(guī)劃的路徑與各級加權(quán)Voronoi圖空間求交，以得到相交的加權(quán)泰森多邊形，相交加權(quán)泰森多邊形的發(fā)生點即是所求的結(jié)果地標。如此逐級計算進而得到各級路徑導(dǎo)引地標集合。再根據(jù)實際應(yīng)用需要，將集合中的地標按照行進方向順序輸出，即可生成由小到大不同粒度的路徑導(dǎo)引描述信息。

以楚天盧酒店到群光廣場路段為例，大尺度描述為“楚天盧酒店（經(jīng)過）卓刀泉立交橋（到達）群光廣場”，通過“卓刀泉立交橋”（Sf：0.631 1）這一地標的引入，形成路徑導(dǎo)引的整體態(tài)勢；在小尺度下，補充表達了“魯廣人行天橋”（Sf：0.438 8）、“武體人行天橋”（Sf：0.563 1）、“卓刀泉立交橋”（Sf：0.631 1）、“測繪科技大廈”（Sf：0.565）、“君宜王朝大飯店”（Sf：0.594 2）等地標，路徑導(dǎo)引信息得到進一步細化。在長距離（如從“魯巷廣場”至“天河機場”）路徑導(dǎo)引的描述亦可采用此方法。試驗表明，導(dǎo)航地標顯著度一定程度上決定了導(dǎo)航語義下地標多尺度分布特征，而多粒度的描述方式符合從粗到細的空間認知規(guī)律，能夠滿足不同詳細程度信息的應(yīng)用需求。大尺度的導(dǎo)航地標序列能夠以簡潔的方式快速表達導(dǎo)航路徑概況，中小尺度能夠表達更為詳細的途經(jīng)信息，使得尋路過程更為明確。

圖3 試驗區(qū)分級加權(quán)Voronoi圖Fig.3 Hierarchy weighted－Voronoi maps in experimental area

經(jīng)過實地行走測試，試驗結(jié)果中單個地標在視域范圍內(nèi)可辨認度、持續(xù)性以及各地標之間承接的連貫性等方面與實地行走體驗基本一致。為了對試驗結(jié)果進行進一步驗證，隨機調(diào)查了6位武漢本地出租車司機，其中武昌出租車（鄂A XL1＊8、鄂A XP1＊9、鄂A XX0＊2）司機3位，漢口出租車（鄂A XR0＊9、鄂A XH5＊5、鄂A XL9＊9）司機3位。調(diào)查問題“請問魯巷廣場到天河機場會經(jīng)過哪些地方”、“還能再詳細一點么”。在6位司機的答復(fù)中 “卓刀泉立交橋”、“中南大酒店”、“黃鶴樓”、“武漢長江大橋”、“江漢橋”、“青年路”、“天河機場”等地標出現(xiàn)率均超過83.3%；“湖濱花園酒店”、“廣埠屯電腦城”、“街道口”、“大東門”、“古琴臺”、“武勝路家樂?！?、“長江大酒店”、“金盾大酒店”、“航空路”、“省電信”、“機場路立交”出現(xiàn)率在50%～83.3%之間；其余地標出現(xiàn)率均低于50%。除個別地標因本地俗稱或個人偏好引起差異外（如有兩位司機認為“古琴臺”和“江漢橋”在方位表達上是一致的，“廣埠屯電腦城”比“君宜王朝大飯店”在方位表達上更符合本地習(xí)慣），調(diào)查結(jié)果與試驗結(jié)果基本一致。

4 結(jié) 論

基于分層地標的多粒度路徑導(dǎo)引描述方法，對導(dǎo)航語義下不同尺度的地標認知空間進行劃分，通過將地標顯著度與多層加權(quán)Voronoi圖的空間剖分相結(jié)合，實現(xiàn)多粒度的路徑導(dǎo)引描述。該方法可以根據(jù)周邊環(huán)境、溝通對象和實際場景提供不同粒度的、符合人們認知習(xí)慣的描述結(jié)果，能有效地增強導(dǎo)航尋路知識的傳遞和共享能力，對于導(dǎo)航與位置服務(wù)應(yīng)用具有實際意義。本文主要研究對象是基于點狀地標的計算和建模，線狀和面狀地標可在此基礎(chǔ)上進一步擴展。此外，地標的語義特征、方位朝向等其他因素對地標顯著度評價的影響還有待進一步的研究。

［1］ DANIEL M P，DENIS M.Spatial Descriptions as Navigational Aids：A Cognitive Analysis of Route Directions［J］.Kognitionswissenschaft，1998，7（1）：45－52.

［2］ TVERSKY B，LEE P.Pictorial and Verbal Tools for Conveying Routes in Spatial Information Theory：Cognitive and Computational Foundations of Geographic Information Science［M］.Berlin：Springer Verlag，1999：51－64.

［3］ XIA J C，ARROWSMITH C，JACKSON M，et al.The Wayfinding Process Relationships between Decision－making and Landmark Utility［J］.Tourism Management，2008，29（3）：445－457.

［4］ LI Lin，ZHU Haihong，WANG Hong，et al.Semantic Analyses of the Fundamental Geographic Information Based on Formal Ontology：Exemplifying Hydrological Category［J］.Acta Geodaetica et Cartographical Sinica，2008，37（2）：230－235.（李霖，朱海紅，王紅，等.基于形式本體的基礎(chǔ)地理信息語義分析［J］.測繪學(xué)報，2008，37（2）：230－235.）

［5］ KEVIN L.The Image of the City［M］.Beijing：Huaxia Publishing House，2003：150－151.（凱文·林奇.城市意象［M］.北京：華夏出版社，2003：150－151.）

［6］ YAO X，THILL J C.Spatial Queries with Qualitative Locations in Spatial Information Systems［J］.Computers，Environment and Urban Systems，2006，30（4）：485－502.

［7］ WANG X，LIU Y，GAO Z，et al.Landmark－based Qualitative Reference System［C］∥25th IEEE International Geoscience and Remote Sensing Symposium （IGARSS 2005）.Seoul：IEEE，2005：932－935.

［8］ GONG Yongxi，LIU Yu，WU Lun，et al.Locality Description Based on Multiplicatively Weighted Voronoi Diagram and Landmarks［J］.Geography and Geoinformation Science，2010，26（4）：21－26.（龔詠喜，劉瑜，鄔倫，等.基于帶權(quán)Voronoi圖與地標的空間位置描［J］.地理與地理信息科學(xué)，2010，26（4）：21－26.）

［9］ DENG Min，LI Zhilin，CHENG Tao，et al.Rough－set Representation of GIS Data Uncertainties with Multiple Granularities［J］.Acta Geodaetica et Cartographica Sinica，2006，35（2）：64－70.（鄧敏，李志林，程濤，等.多粒度的GIS數(shù)據(jù)不確定性粗集表達［J］.測繪學(xué)報，2006，35（2）：64－70.）

［10］ AI Tinghua，CHENG Jianguo.Key Issues of Multi－scale Representation of Spatial Data［J］.Geomatics and Information Science of Wuhan University，2005，30（5）：377－382.（艾廷華，成建國.對空間數(shù)據(jù)多尺度表達有關(guān)問題的思考［J］.武漢大學(xué)學(xué)報：信息科學(xué)版，2005，30（5）：377－382.）

［11］ TIMPF S，VOLTA G S，POLLOCK D W，et al.A Conceptual Model of Wayfinding Using Multiple Levels of Abstraction［J］.Lecture Notes in Computer Science，1992，639：348－367.

［12］ ZHENG Nianbo，LU Feng，LI Qingquan.Dynamic Multi－scale Road Network Data Model for Navigation［J］.Acta Geodaetica et Cartographica Sinica，2010，39（8）：428－434.（鄭年波，陸鋒，李清泉.面向?qū)Ш降膭討B(tài)多尺度路網(wǎng)數(shù)據(jù)模型［J］.測繪學(xué)報，2010，39（8）：428－434.）

［13］ PRESSON C C，MONTELLO D R.Points of Reference in Spatial Cognition：Stalking the Elusive Landmark［J］.British Journal of Developmental Psychology，1988，6：378－381.

［14］ LOVELACE K L，HEGARTY M，MONTELLO D R.Elements of Good Route Directions in Familiar and Unfamiliar Environments.in Spatial Information Theory：Cognitive and Computational Foundations of Geographic Information Science［M］.Berlin：Springer Verlag，1999：65－82.

［15］ SORROWS M E，HIRDE S C.The Nature of Landmarks for Real and Electronic Spaces.in Spatial Information Theory：Cognitive and Computational Foundations of Geographic Information Science［M］.Berlin：Springer Verlag，1999：37－50.

［16］ TOMKO M，WINTER S，CLARAMUNT C.Experiential Hierarchies of Streets［J］.Computers，Environment and Urban Systems，2008，32（1）：41－52.

［17］ MONTELLO D R.Scale and Multiple Psychologies of Space［M］∥Spatial Information Theory：A Theoretical Basis for GIS.Berlin：Springer Verlag，2009：312－321.

［18］ LI Shengquan，HU Peng，YAN Weiyang.Delimitation of Central Cities Influenced Regions Based on Weighted－Voronoi Diagram ［J］.Engineering Journal of Wuhan University，2004，37（1）：94－97.（李圣權(quán)，胡鵬，閆衛(wèi)陽.基于加權(quán)Voronoi圖的城市影響范圍劃分［J］.武漢大學(xué)學(xué)報：工學(xué)版，2004，37（1）：94－97.）

［19］ WINTER S，TOMKO M，ELIAS B，et al.Landmark Hierarchies in Context［J］.Environment and Planning B：Planning and Design，2008，35（3）：381－398.

［20］ GAHEGAN M，LEE I.Data Structures and Algorithms to Support Interactive Spatial Analysis Using Dynamic Voronoi Diagrams［J］.Computers，Environment and Urban Systems，2000，24（6）：509－537.

［21］ YING Shen，LI Lin，GAO Yurong，et al.Natural Language Description of Multi－scale Spatial Orientation in LBS［J］.Geomatics World，2008（1）：28－33.（應(yīng)申，李霖，高玉榮，等.LBS中多尺度空間方位的自然語言描述［J］.地理信息世界，2008（1）：28－33.）

［22］ LI Deren，HU Qingwu.Digital Measurable Image Based Geo－spatial Information Service［J］.Geomatics and Information Science of Wuhan University，2007，32（5）：377－380.（李德仁，胡慶武.基于可量測實景影像的空間信息服務(wù)［J］.武漢大學(xué)學(xué)報：信息科學(xué)版，2007，32（5）：377－380.）

［23］ SIEGEL A W，WHITE S H.The Development of Spatial Representations of Large－scale Environments ［J］.Advances in Child Development and Behavior，1975（10）：9－55.

［24］ KLIPPEL A，WINTER S.Structural Salience of Landmarks for Route Directions［C］∥Proceedings of International Conference on Spatial Informational Theory.Elliottville：COSIT，2005：347－362.