張　翔，王少東，王玉霞

1. 武漢大學(xué)資源與環(huán)境科學(xué)學(xué)院，湖北 武漢 430079； 2. 中國(guó)科學(xué)院軟件研究所計(jì)算機(jī)科學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100190； 3. 北京大學(xué)遙感與地理信息系統(tǒng)研究所，北京100871

?

基于偏移四叉樹(shù)投票的“大尺寸”點(diǎn)狀符號(hào)多尺度無(wú)壓蓋可視化

張翔1，王少東2，王玉霞3

1. 武漢大學(xué)資源與環(huán)境科學(xué)學(xué)院，湖北 武漢 430079； 2. 中國(guó)科學(xué)院軟件研究所計(jì)算機(jī)科學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100190； 3. 北京大學(xué)遙感與地理信息系統(tǒng)研究所，北京100871

Foundation support： The National Natural Science Foundation of China (No. 41301410 )；The National High-tech Research and Development Program of China (863 Program) (No. 2015AA123901)；The Project for National Basic Science Personnel Training Fund(No. J1103409)

為解決Web 2.0環(huán)境下點(diǎn)狀符號(hào)地圖混搭中的制圖問(wèn)題，本文研究并實(shí)現(xiàn)了一種可100%避免壓蓋的“大尺寸”點(diǎn)符號(hào)高效可視化方法。該方法的核心思想是四叉樹(shù)網(wǎng)格單選，采用網(wǎng)格平移對(duì)多次單選結(jié)果投票來(lái)計(jì)算符號(hào)在各縮放級(jí)別的顯著性等級(jí)，可解決符號(hào)在相鄰網(wǎng)格的空間沖突。該過(guò)程不需要顯式探測(cè)沖突，因而處理效率極高。隨著地圖放大，重要性較低的符號(hào)也逐級(jí)顯現(xiàn)，實(shí)現(xiàn)了語(yǔ)義層次的多尺度表達(dá)。針對(duì)符號(hào)和網(wǎng)格大小比率關(guān)系、有效網(wǎng)格平移方案及圖面利用率不足問(wèn)題提出兩種擴(kuò)展：格網(wǎng)增選和多級(jí)符號(hào)疊加。對(duì)方法的可行性進(jìn)行了試驗(yàn)驗(yàn)證，并分析了該方法在用戶查詢條件改變下的穩(wěn)定性和不同數(shù)據(jù)量下的伸縮性(非優(yōu)化實(shí)現(xiàn)可達(dá)到105量級(jí)數(shù)據(jù)的亞秒級(jí)處理)。

空間沖突消解；多尺度可視化；大尺寸符號(hào)；四叉樹(shù)；實(shí)時(shí)Web制圖

Web 2.0環(huán)境下，地圖制圖的服務(wù)對(duì)象正從測(cè)繪相關(guān)行業(yè)轉(zhuǎn)向公眾服務(wù)，空間數(shù)據(jù)采集、地圖制圖技術(shù)、地圖發(fā)布與傳播呈現(xiàn)大眾化、網(wǎng)絡(luò)化和移動(dòng)化的趨勢(shì)。目前，Web瀏覽器、移動(dòng)客戶端出現(xiàn)了大量地圖混搭的應(yīng)用形式：將位置相關(guān)信息(如帶有地理標(biāo)簽的照片、視頻、微博消息等多媒體)以點(diǎn)狀符號(hào)的形式簡(jiǎn)單映射到Web地圖上。近來(lái)出現(xiàn)的基于位置的社交網(wǎng)絡(luò)(LBSN)[1]也通過(guò)地圖混搭對(duì)朋友圈網(wǎng)絡(luò)、微博消息等進(jìn)行時(shí)空可視化[2]。然而，混搭地圖容易出現(xiàn)圖面雜亂、易覽性差等制圖問(wèn)題，極大地削弱了地圖閱讀與信息獲取效率[3]，這在社交網(wǎng)絡(luò)、微博、媒體共享服務(wù)等大數(shù)據(jù)環(huán)境的制圖中顯得尤為突出。

本質(zhì)上，地圖混搭是一種專題地圖。與傳統(tǒng)專題符號(hào)不同，混搭地圖的符號(hào)本身承載豐富信息(如照片、視頻、Logo標(biāo)志等)，符號(hào)尺寸較大，且數(shù)據(jù)體量巨大。本文研究“大尺寸”點(diǎn)狀符號(hào)的實(shí)時(shí)Web制圖，并定義“大尺寸”的內(nèi)涵為“符號(hào)尺寸遠(yuǎn)大于符號(hào)間距”，筆者認(rèn)為這是大數(shù)據(jù)環(huán)境下混搭制圖的一個(gè)重要特征。具體有如下特點(diǎn)：①尺寸敏感性，即制圖算法需要顯式考慮符號(hào)大小，因?yàn)椤按蟪叽纭狈?hào)更容易產(chǎn)生壓蓋沖突；②海量“大尺寸”符號(hào)空間競(jìng)爭(zhēng)導(dǎo)致的高淘汰率(見(jiàn)3.2.3節(jié))；③由于符號(hào)本身是信息認(rèn)知主體，用戶更關(guān)注符號(hào)個(gè)體信息的完整表達(dá)。

在點(diǎn)狀符號(hào)可視化方面，本文主要綜述3類方法：制圖綜合、空間變形和表達(dá)轉(zhuǎn)換。地圖綜合中的相關(guān)問(wèn)題是點(diǎn)群綜合，采用選取、典型化、聚合、位移等綜合算子進(jìn)行點(diǎn)群化簡(jiǎn)。典型化、聚合的結(jié)果無(wú)法表達(dá)個(gè)體信息[3]，因而不太適合本應(yīng)用；位移雖能保證每個(gè)符號(hào)可完整識(shí)別，卻無(wú)法高效處理大數(shù)據(jù)集[3-4]?，F(xiàn)有點(diǎn)群化簡(jiǎn)算法大多為地理相關(guān)科學(xué)服務(wù)，注重保持點(diǎn)群的空間分布規(guī)律，采用復(fù)雜度高的化簡(jiǎn)算法[5-8]，難以擴(kuò)展到大規(guī)模實(shí)時(shí)Web制圖。此外，這些方法將制圖目標(biāo)作為無(wú)大小的點(diǎn)，根據(jù)載負(fù)量規(guī)律[9]減少目標(biāo)數(shù)量，并不保障空間沖突的消解。本文中Web用戶強(qiáng)調(diào)高效處理，關(guān)注個(gè)體信息而非整體態(tài)勢(shì)，且無(wú)壓蓋的大尺寸符號(hào)是無(wú)法保持原始數(shù)據(jù)的分布模式的，空間分布約束不作為本文的制圖目標(biāo)。另一些算法考慮符號(hào)大小，并顯式探測(cè)空間沖突。如有學(xué)者利用數(shù)學(xué)規(guī)劃方法尋找點(diǎn)群在尺度軸上的活躍范圍，可構(gòu)建點(diǎn)群在尺度空間的連續(xù)表達(dá)[10-11]，但優(yōu)化算法的效率使其難以勝任高響應(yīng)制圖任務(wù)。當(dāng)然，可將算法復(fù)雜度高的綜合結(jié)果存儲(chǔ)在層次結(jié)構(gòu)中[12-13]，如Google通過(guò)預(yù)存儲(chǔ)其海量POI點(diǎn)化簡(jiǎn)結(jié)果來(lái)彌補(bǔ)耗時(shí)的優(yōu)化算法[14-15]，不足在于難以靈活應(yīng)對(duì)動(dòng)態(tài)語(yǔ)義查詢和變化更新。在強(qiáng)調(diào)效率的Web和移動(dòng)制圖方面，國(guó)內(nèi)外學(xué)者均采用空間剖分結(jié)構(gòu)來(lái)加快沖突探測(cè)與消解，在小數(shù)據(jù)量下取得不錯(cuò)的結(jié)果[16-18]。

空間變形包括Cartogram、變比例尺表達(dá)[19-20]、放大鏡等。空間變形能降低放大區(qū)域內(nèi)符號(hào)壓蓋的可能性，但無(wú)法控制變形邊界區(qū)域的空間沖突[4]。表達(dá)轉(zhuǎn)換是指通過(guò)空間變換(如核密度分析)將離散點(diǎn)群轉(zhuǎn)換為密度圖或熱圖，能夠揭示點(diǎn)群分布總體態(tài)勢(shì)與密度差異，但卻無(wú)法表達(dá)個(gè)體信息。

綜上，地圖綜合中的選取算子是比較適合本研究的方法，然而針對(duì)海量“大尺寸”空間沖突快速消解、符號(hào)大小可定制，顧及語(yǔ)義重要性的研究并不多。針對(duì)該應(yīng)用特點(diǎn)和新型用戶需求，本文研究了一種高效的“大尺寸”地圖符號(hào)多尺度可視化方法，旨在滿足以下設(shè)計(jì)原則：

(1) 最小化符號(hào)壓蓋：無(wú)壓蓋的符號(hào)有利于用戶探索符號(hào)本身承載的信息內(nèi)容，減少干擾。

(2) 語(yǔ)義層次的多尺度表達(dá)：利用多尺度結(jié)構(gòu)展現(xiàn)語(yǔ)義重要性，滿足重要目標(biāo)在較小尺度優(yōu)先出現(xiàn)，次要目標(biāo)隨尺度變大逐級(jí)累加的原則[12]。

(3) 平移和縮放一致性：當(dāng)前縮放級(jí)別(或窗口范圍)存在的目標(biāo)在窗口放大(或移動(dòng))后須保持，提供圖形上下文信息，不迷失方位[15]。

(4) 提高圖面空間利用率：利用更多的空間來(lái)提高專題信息表達(dá)強(qiáng)度。

1　基于偏移Quadtree的多尺度顯著性評(píng)級(jí)

1.1基本思想：網(wǎng)格單選

對(duì)于海量點(diǎn)符號(hào)的沖突，本文的基本思想是對(duì)空間進(jìn)行劃分，每個(gè)網(wǎng)格單元選取一個(gè)最重要的符號(hào)，簡(jiǎn)稱“網(wǎng)格單選法”。采用分治策略處理效率高，且剖分結(jié)構(gòu)能夠在較大程度上減少符號(hào)的初始?jí)荷w。然而，要滿足上述設(shè)計(jì)原則，仍需解決要素重要性評(píng)估、網(wǎng)格大小、網(wǎng)格定位等問(wèn)題。

1.2空間上下文中的相對(duì)重要性

本文應(yīng)用場(chǎng)景中的點(diǎn)狀符號(hào)都具有語(yǔ)義重要性，比如地點(diǎn)口碑、簽到數(shù)，訪問(wèn)量等。然而，使用這些語(yǔ)義來(lái)選取符號(hào)并不能滿足設(shè)計(jì)原則(1)和(4)。如圖1所示，選取重要性高于75的點(diǎn)符號(hào)，得到的A和C，既沒(méi)有解決空間沖突，也沒(méi)有很好地利用圖面空閑空間。這里采用相對(duì)重要性的概念：相對(duì)重要的目標(biāo)是在空間沖突上下文中重要性最高的目標(biāo)。在圖1中，A和D的相對(duì)重要性較高，因?yàn)镈的周圍沒(méi)有沖突目標(biāo)，其較低的重要性依然能夠從上下文中凸顯出來(lái)。相對(duì)重要性能夠調(diào)和語(yǔ)義和空間關(guān)系。

圖1　空間沖突上下文中的相對(duì)重要性(圖中虛線框代表點(diǎn)符號(hào)的覆蓋區(qū)域)Fig.1　Relative importance made sense in conflicting context (dashed boxes indicate the extents of point symbols)

1.3網(wǎng)格與符號(hào)的大小關(guān)系

網(wǎng)格單選基本思路中并沒(méi)有對(duì)網(wǎng)格大小進(jìn)行約定，不同的情況可能會(huì)導(dǎo)致“單選法”失效或引入不必要的計(jì)算負(fù)荷。本文通過(guò)制定合理網(wǎng)格劃分方案對(duì)單選思路進(jìn)行優(yōu)化，并規(guī)避不必要的空間計(jì)算，以達(dá)到計(jì)算效率最大化。理想的網(wǎng)格單元大小(w)應(yīng)是符號(hào)尺寸(s)的函數(shù)：w=f(s)，當(dāng)網(wǎng)格大小使得落入網(wǎng)格內(nèi)的任意兩個(gè)符號(hào)必然產(chǎn)生壓蓋時(shí)，不需要空間計(jì)算就知道只能從中選出一個(gè)無(wú)壓蓋符號(hào)。據(jù)此非嚴(yán)格估算網(wǎng)格與符號(hào)的大小關(guān)系如下式所述。

(1)

式(1)之外有兩種情況：①網(wǎng)格過(guò)小(小于符號(hào)尺寸)將使相鄰網(wǎng)格選取的符號(hào)必然產(chǎn)生壓蓋(原則(1))，“單選法”失去意義；②網(wǎng)格過(guò)大將降低點(diǎn)符號(hào)的空間利用率(原則(4))。若要提高后者的空間利用率，須計(jì)算N個(gè)點(diǎn)中選M個(gè)無(wú)壓蓋且重要性高的點(diǎn)符號(hào)(N?M，M不固定)的組合優(yōu)化問(wèn)題，計(jì)算復(fù)雜度高。下文對(duì)“單選法”的優(yōu)化能夠避免該計(jì)算過(guò)程。

1.4四叉樹(shù)層次網(wǎng)格劃分與跨網(wǎng)格臨近問(wèn)題

本文采用四叉樹(shù)作為符號(hào)選取的空間剖分方案，可根據(jù)符號(hào)在四叉樹(shù)中的Morton碼判斷他們是否落在第z級(jí)的同一網(wǎng)格。本文使用二進(jìn)制Morton碼對(duì)四叉樹(shù)網(wǎng)格進(jìn)行編碼，每個(gè)層次占2位編碼，第z級(jí)的編碼長(zhǎng)度為2z,z∈{1,2,…,n}。式(2)給出了兩個(gè)點(diǎn)目標(biāo)處于四叉樹(shù)第n層下的Morton碼示例(每一層次的編碼用中括號(hào)分隔)，可以看出M1、M2在第1～4級(jí)都位于同一個(gè)網(wǎng)格，從第5級(jí)開(kāi)始分隔到不同網(wǎng)格。

(2)

通過(guò)四叉樹(shù)實(shí)現(xiàn)基本的網(wǎng)格單選法：①采用遞歸算法對(duì)所有目標(biāo)進(jìn)行一次性編碼(到第z層)，目標(biāo)的Morton碼采用字符數(shù)組存儲(chǔ)在其屬性中，可獲得目標(biāo)在所有縮放級(jí)別所在的網(wǎng)格信息；②對(duì)編碼的前2z位進(jìn)行子串提取并排序分組，查詢特定縮放級(jí)別z下位于同一網(wǎng)格中的目標(biāo)；③對(duì)于同一網(wǎng)格內(nèi)的大量點(diǎn)符號(hào)，選取重要性最高的一個(gè)作為最終結(jié)果(圖6(b))；④當(dāng)?shù)貓D平移縮放時(shí)重復(fù)步驟②—③，可實(shí)時(shí)獲得對(duì)應(yīng)縮放級(jí)別下點(diǎn)符號(hào)的選取結(jié)果。

然而，該簡(jiǎn)單實(shí)現(xiàn)有一個(gè)明顯的缺陷：點(diǎn)符號(hào)的臨近關(guān)系是通過(guò)位于同一網(wǎng)格來(lái)隱含判定，即位于同一網(wǎng)格認(rèn)為臨近(產(chǎn)生符號(hào)壓蓋)，而沒(méi)有考慮跨網(wǎng)格的臨近關(guān)系。換言之，相鄰網(wǎng)格選出的符號(hào)仍然可能產(chǎn)生壓蓋(圖6(b))?，F(xiàn)考查圖2(a)中的3點(diǎn)A、B、C，因?yàn)锽、C兩點(diǎn)被分在了0001網(wǎng)格內(nèi)，若B比C的重要性高，從中選出B，0000網(wǎng)格選出A點(diǎn)，A、B就會(huì)產(chǎn)生的壓蓋。這是由于網(wǎng)格定位的任意性所致，且無(wú)論如何選擇網(wǎng)格起點(diǎn)，單一的網(wǎng)格劃分無(wú)法避免臨近關(guān)系被網(wǎng)格邊界分割。

圖2Fig.2

1.5四叉樹(shù)多次平移與顯著性投票

設(shè)想四叉樹(shù)在不同方向進(jìn)行多次平移，對(duì)每個(gè)網(wǎng)格在多次平移中的入選的重要目標(biāo)進(jìn)行投票，得票高者作為最終的入選結(jié)果。以圖2為例，假設(shè)A、B、C的重要性為90、80、20，則圖2(a)中0000網(wǎng)格中A入選，0001網(wǎng)格中B入選，在網(wǎng)格偏移后(圖2(b))，0001網(wǎng)格中A入選，0100網(wǎng)格中C入選，綜合兩次結(jié)果A獲得兩票，B、C分別獲得一票。若A、B、C的重要性為80、90、20，則A、C獲得一票，B兩票。在多次平移下，得票數(shù)高者表明與它周圍發(fā)生沖突的目標(biāo)相比其重要性更高。合理的平移次數(shù)與方案能把當(dāng)前目標(biāo)與其臨近目標(biāo)納入到相同網(wǎng)格中，并能在多尺度下持續(xù)有效。

1.5.1多尺度結(jié)構(gòu)中的有效平移方案

以橫向平移為例，將圖2中的點(diǎn)向右進(jìn)行平移，當(dāng)偏移量達(dá)到一個(gè)網(wǎng)格寬度w(或其整數(shù)倍)時(shí)，A、B、C3點(diǎn)與網(wǎng)格劃分的相對(duì)關(guān)系復(fù)原，因此有效的平移全部發(fā)生在w個(gè)單位的平移中，其間會(huì)出現(xiàn)B、C分在一個(gè)網(wǎng)格的偏移區(qū)間(圖2a)，也會(huì)出現(xiàn)A、B分在一個(gè)網(wǎng)格的偏移區(qū)間(圖2(b))。由于計(jì)算中必須把平移過(guò)程離散化，不妨考慮將平移分為n個(gè)單元，每次的偏移量為w/n，離散偏移量可表示為{0,w/n,2w/n,…,(n-1)w/n}，因?yàn)閚w/n與0偏移量效果相同，故剔除。

上述偏移僅討論了一個(gè)比例尺下的情況，通常在每個(gè)縮放級(jí)別下都需要進(jìn)行該偏移計(jì)算，重復(fù)計(jì)算將極大降低實(shí)時(shí)處理效率。為了避免在各個(gè)縮放級(jí)別下都要針對(duì)當(dāng)前網(wǎng)格大小進(jìn)行單位為w/n的平移，需要找到一種偏移方案，使得在四叉樹(shù)的上層進(jìn)行的平移在后續(xù)層級(jí)中依然是有效的。

現(xiàn)將n分為奇數(shù)和偶數(shù)情況討論。首先考慮n為偶數(shù)的情況，如圖3(a)所示：n=4，則4次偏移量分別為{0,w/4,w/2,3w/4}。放大一級(jí)后，偏移量長(zhǎng)度變成兩倍：{0,w/2,w,3w/2}，其中有效的偏移只有{0,w/2}兩次平移。如果再放大，偏移量將變?yōu)閣的整數(shù)倍，成了無(wú)效平移。由于每次放大操作都使有效平移次數(shù)減少一半，偶數(shù)偏移次數(shù)無(wú)法在多尺度結(jié)構(gòu)中保持持續(xù)有效。

考慮n為奇數(shù)的情況，如圖3(b)所示：n=3，3次偏移量為{0,w/3,2w/3}。放大一級(jí)后，3次偏移量為{0,2w/3,4w/3}，其中4w/3相當(dāng)于w/3，與放大前的偏移量集合等價(jià)?？梢宰C明，n=3的情況下不論放大多少級(jí)，偏移量集合均等價(jià)于{0,w/3,2w/3}，該性質(zhì)可以推廣至任意奇數(shù)n>1?？紤]到計(jì)算效率，本文選擇最小有效平移次數(shù)(n=3)。

圖3　不同偏移次數(shù)在四叉樹(shù)層次中的有效性(w為00網(wǎng)格的寬度)Fig.3　Effectiveness of offset schemes under even/odd numbers of translation (w: width of the grid with code 00)

同理，橫向平移原理可擴(kuò)展到縱向平移，當(dāng)n=3時(shí)，四叉樹(shù)在二維平面中共有9次平移，平移矩陣由式3表示，其中矩陣元素形如(dx,dy)，w為當(dāng)前網(wǎng)格寬度

(3)

1.5.2離散平移下網(wǎng)格與符號(hào)的大小關(guān)系

式(1)中符號(hào)矩形與網(wǎng)格大小關(guān)系只是一個(gè)初步估計(jì)，考慮到網(wǎng)格平移需進(jìn)行調(diào)整。如果平移是連續(xù)的，所有的臨近目標(biāo)都會(huì)在某個(gè)平移階段落入同一個(gè)網(wǎng)格內(nèi)，但是實(shí)際的離散平移下有一個(gè)例外，下面進(jìn)行論述。

以橫向平移3次為例(圖4(a))，將網(wǎng)格按照平移單元w/3進(jìn)行劃分，則落入每個(gè)帶中的點(diǎn)在一次平移后會(huì)落入下一個(gè)相鄰帶中。觀察邊界情況3、6號(hào)帶(圖4(a)中灰色區(qū)域)，位于這兩個(gè)帶的點(diǎn)在平移中不可能落在同一個(gè)網(wǎng)格。因?yàn)槁湓?、6號(hào)帶中任意兩點(diǎn)的最小距離為2w/3，如果符號(hào)尺寸s=w，還是有可能產(chǎn)生壓蓋沖突，只是該沖突無(wú)法被本文方法探測(cè)到。這一情況適用于任何中間間隔兩帶的帶號(hào)(如圖4(a)中的1、4號(hào)，2、5號(hào))。為了完全解決符號(hào)壓蓋，在3次平移下符號(hào)尺寸必須滿足：s≤2w/3。同理，當(dāng)n=5時(shí)，符號(hào)尺寸須小于4w/5(圖4(b))?？梢宰C明，平移網(wǎng)格下滿足無(wú)壓蓋的符號(hào)尺寸與一維方向平移次數(shù)n(奇數(shù))相關(guān)

(4)

當(dāng)式(4)中的n→∞，離散偏移趨于連續(xù)平移，而最大符號(hào)尺寸也趨近網(wǎng)格寬度w，與式(1)相符。當(dāng)平移次數(shù)n較大時(shí)，符號(hào)與網(wǎng)格的比例相對(duì)較大，這樣能夠提高圖面利用率，但同時(shí)帶來(lái)了較大的計(jì)算負(fù)荷。本文采用符號(hào)的最大尺寸為2w/3。

圖4　平移3次和5次下的邊界情況及精確符號(hào)尺寸上限分析Fig.4　Maximum symbol size relative to the selection grid under 3 and 5 translation

1.5.3顯著性評(píng)級(jí)的計(jì)算流程

本文把一個(gè)目標(biāo)在多次四叉樹(shù)平移中獲得的票數(shù)作為其顯著性評(píng)級(jí)。顯然，在n=3時(shí)，能獲得的最高顯著級(jí)別為9，最終可根據(jù)需求輸出顯著性級(jí)別高于指定閾值的目標(biāo)集合?？傮w計(jì)算流程如下。

輸入：符號(hào)尺寸s；當(dāng)前地圖縮放級(jí)別z；指定輸出目標(biāo)的顯著性級(jí)別SL；查詢窗口Q；

輸出：縮放級(jí)別z對(duì)應(yīng)的選取目標(biāo)集合P。

步驟1：預(yù)處理階段：按式(3)進(jìn)行9次平移，每次平移計(jì)算所有目標(biāo)0-zmax級(jí)的Morton編碼；

步驟2：網(wǎng)格單選與顯著性投票(響應(yīng)地圖操作事件，實(shí)時(shí)計(jì)算)：

(1) 根據(jù)s和z計(jì)算網(wǎng)格單選和顯著性投票所需的四叉樹(shù)網(wǎng)格級(jí)別k；

(2) 空間查詢落入Q中的目標(biāo)候選集C；

(3) 對(duì)9次平移中的每一次：對(duì)每個(gè)c∈C，提取c的Morton碼前2k位子串，進(jìn)行相同網(wǎng)格分組，每組中重要性c.imp最高的目標(biāo)其顯著性級(jí)別c.ds=c.ds+1(投票)；

(4) 對(duì)每個(gè)c∈C，把c加入集合P當(dāng)且僅當(dāng)c.ds≥SL。

計(jì)算過(guò)程中步驟1屬于一次性計(jì)算，在處理完后步驟2是在每次的放大、縮小和窗口移動(dòng)的事件中觸發(fā)，其間不需要重新計(jì)算步驟1即可改變s、SL等參數(shù)，并實(shí)時(shí)獲得結(jié)果；步驟(1)在式(4)后進(jìn)行了解釋；步驟(3)中的顯著性級(jí)別ds在9次平移網(wǎng)格中進(jìn)行累加，最高可獲得9票；步驟(4)選取滿足指定顯著性級(jí)別的目標(biāo)作為z級(jí)上的最終結(jié)果。

2　增大圖面利用率的兩種擴(kuò)展

從試驗(yàn)結(jié)果可以看出，平移四叉樹(shù)投票算法雖然可有效避免壓蓋沖突，但還是造成了一定的圖面空間浪費(fèi)。為提高圖面利用率(原則(4))，本文提出兩種擴(kuò)展方法。

2.1格網(wǎng)增選

步驟如下所示，格網(wǎng)增選為顯著性投票的后續(xù)子過(guò)程，可利用顯著性投票算法記錄的信息，如當(dāng)前窗口Q中的網(wǎng)格，網(wǎng)格中已經(jīng)選取的目標(biāo)等。算法通過(guò)少量的外接矩形沖突計(jì)算，確定是否進(jìn)行增選，增選多少符號(hào)；同時(shí)，算法依照顯著性評(píng)級(jí)的順序?qū)δ繕?biāo)進(jìn)行判斷，以保證增選出的目標(biāo)仍具有較高的顯著性。

輸入：圖面利用率r(缺省值100%)；

輸出：縮放級(jí)別z對(duì)應(yīng)的增選目標(biāo)集合PS。

步驟1：令增補(bǔ)候選集B=C-P；對(duì)B中元素按顯著性排序；

步驟2：對(duì)每個(gè)目標(biāo)b∈B，根據(jù)b的Morton碼獲取它所在格網(wǎng)及其相鄰8個(gè)格網(wǎng)(九宮格)；

步驟3：獲取九宮格中已經(jīng)選取的目標(biāo)，判斷b是否與他們有壓蓋關(guān)系，若無(wú)，則將b加入PS；

步驟4：若點(diǎn)集P+PS的圖面利用率超過(guò)r，或者窗口Q中所有網(wǎng)格已經(jīng)增選完畢，則終止循環(huán)；否則繼續(xù)步2。

2.2多級(jí)符號(hào)疊加

第2種增大圖面利用率的方法是采用多級(jí)尺寸符號(hào)，即在同一個(gè)縮放級(jí)別中采用不同大小，不同顯著性的符號(hào)疊加。不同符號(hào)尺寸按照表1分別計(jì)算顯著性評(píng)級(jí)，并選取評(píng)級(jí)為9的點(diǎn)要素，最后將結(jié)果進(jìn)行疊加。在大符號(hào)空缺的區(qū)域，由小符號(hào)填充。不同尺寸的符號(hào)位于四叉樹(shù)的不同層次上，獲得某一尺寸符號(hào)無(wú)沖突表達(dá)只需計(jì)算相應(yīng)的四叉樹(shù)層次，并截取相應(yīng)長(zhǎng)度的Morton碼，按1.5.3節(jié)中的步驟2進(jìn)行計(jì)算。由于大小不同的符號(hào)處于不同四叉樹(shù)層次，其顯著性不同，該擴(kuò)展方案能夠在增大圖面利用率的同時(shí)提升專題符號(hào)的視覺(jué)層次(見(jiàn)3.4節(jié))。

3　試驗(yàn)分析

3.1原型系統(tǒng)與試驗(yàn)數(shù)據(jù)

本文試驗(yàn)環(huán)境為B/S架構(gòu)，采用Node.js作為后臺(tái)服務(wù)器，并使用MongoDB數(shù)據(jù)庫(kù)存儲(chǔ)數(shù)據(jù)，使用OpenLayers作為客戶端軟件。試驗(yàn)數(shù)據(jù)包括兩部分：①Flickr網(wǎng)站的真實(shí)地理標(biāo)記照片數(shù)據(jù)；②全球范圍內(nèi)的隨機(jī)點(diǎn)數(shù)據(jù)，試驗(yàn)中點(diǎn)符號(hào)的重要性在0～100間隨機(jī)分配。

3.2試驗(yàn)結(jié)果

3.2.1算法執(zhí)行效果

圖5(a)為Flickr網(wǎng)站下載的6000個(gè)照片位置，可見(jiàn)大量符號(hào)聚集壓蓋，符號(hào)尺寸遠(yuǎn)大于點(diǎn)位間距；圖5(b)為2.4節(jié)所述樸素網(wǎng)格單選法的實(shí)現(xiàn)結(jié)果，可見(jiàn)相鄰網(wǎng)格符號(hào)仍會(huì)產(chǎn)生壓蓋；圖5(c)的投票選取的結(jié)果能夠完全避免壓蓋(顯著性級(jí)別SL為9)。

圖5Fig.5

圖6為隨機(jī)生成點(diǎn)數(shù)據(jù)的算法運(yùn)行結(jié)果。圖6(c)中的半透明方框?yàn)楦窬W(wǎng)增選算法增選的符號(hào)，能夠提高顯著性評(píng)級(jí)方法圖面利用率，用戶可指定圖面利用率使增選結(jié)果符合預(yù)期。

圖6　模擬點(diǎn)數(shù)據(jù)Fig.6　Random data points

3.2.2顯著性評(píng)級(jí)對(duì)算法影響

隨著顯著性評(píng)級(jí)參數(shù)SL的降低，更多的符號(hào)得以表達(dá)，但同時(shí)壓蓋沖突逐漸增多(圖7)。在允許部分壓蓋的應(yīng)用環(huán)境下，降低顯著性評(píng)級(jí)不失為一種增加圖面利用率的手段。

圖7　模擬數(shù)據(jù)選取結(jié)果：顯著性評(píng)級(jí)不小于9(a),7(b),5(c),3(d)Fig.7　Results of random data points: significance level ≥9 (a)、7 (b)、5 (c)、3 (d)

3.2.3算法響應(yīng)實(shí)時(shí)變化效果

地圖縮放和平移時(shí)查詢窗口Q和縮放級(jí)別z發(fā)生改變，觸發(fā)顯著性投票(1.5.3節(jié))和格網(wǎng)增選(2.1節(jié))算法運(yùn)行，實(shí)時(shí)獲得新的結(jié)果。隨著地圖放大，更多的符號(hào)顯現(xiàn)出來(lái)，較小比例尺中符號(hào)是較大比例尺符號(hào)的子集(原則(3))，較大比例尺中新顯現(xiàn)的是(上一縮放級(jí))顯著性級(jí)別較低的符號(hào)(圖8(a)—8(c))，這符合“概覽，縮放過(guò)濾，按需細(xì)節(jié)”[17]的信息可視化原則。此外，格網(wǎng)增選在地圖操作中能夠保證符號(hào)無(wú)壓蓋(圖8(d)—8(f))。圖9展示了顯著性投票與增選算法可實(shí)時(shí)響應(yīng)符號(hào)尺寸s變化，符號(hào)無(wú)壓蓋，具有良好的魯棒性；同時(shí)，當(dāng)符號(hào)尺寸大于當(dāng)前選取格網(wǎng)2w/3時(shí)，算法將選用上一級(jí)格網(wǎng)作為選取依據(jù)。試驗(yàn)中選取率在0.5%左右，當(dāng)符號(hào)變大時(shí)選取率更低。

3.3系統(tǒng)效率

分別考察核心算法(1.5.3節(jié))中預(yù)處理(步驟1)和實(shí)時(shí)查詢(步驟2)的運(yùn)行效率，測(cè)試環(huán)境為i5-5250U@1.6 GHz筆記本，內(nèi)存4 GB。對(duì)103、6000(真實(shí)Flickr數(shù)據(jù))、104、105、106數(shù)量級(jí)隨機(jī)分布點(diǎn)的9次平移Quadtree編碼耗時(shí)分別為0.134 s、0.421 s、0.759 s、5.916 s、33.23 s，該預(yù)處理過(guò)程在服務(wù)器端一次性完成。針對(duì)響應(yīng)地圖縮放的實(shí)時(shí)查詢，統(tǒng)計(jì)不同數(shù)據(jù)量從z3(實(shí)際最小縮放級(jí)別)到z18級(jí)的20次試驗(yàn)的耗時(shí)均值(圖10)。除了106量級(jí)在z3的查詢時(shí)間為1500 ms，其他均可達(dá)到亞秒級(jí)的查詢效率(105量級(jí)的最大查詢時(shí)間為148 ms；6000量級(jí)最大查詢時(shí)間為31.95 ms)。

圖9　改變符號(hào)尺寸(格網(wǎng)增選的符號(hào)為空心矩形)：符號(hào)寬度21px (a)，39px (b)，87px (c)Fig.9　Results of varying symbol sizes: symbol width = 21px (a), 39px (b), 87px (c)

Flickr數(shù)據(jù)(6000)在不同縮放級(jí)別的測(cè)試窗口均選擇在目標(biāo)聚集區(qū)符號(hào)最多(圖10柱狀圖)的區(qū)域，其查詢時(shí)間(圖10方形折線圖)可視為當(dāng)前級(jí)別的上限，在非聚集區(qū)的查詢效率更高；同時(shí)可見(jiàn)查詢時(shí)間與檢索出的結(jié)果數(shù)量具有正相關(guān)性。與真實(shí)數(shù)據(jù)不同，隨機(jī)生成點(diǎn)位分布比較平均，在幾次放大后數(shù)據(jù)密度迅速下降，沒(méi)有聚集中心，使得查詢效率快速提高；模擬數(shù)據(jù)在較大縮放級(jí)別下的查詢時(shí)間在2 ms以內(nèi)，為清晰起見(jiàn)，圖10中不予表達(dá)。

圖10　平移四叉樹(shù)顯著性投票算法在不同數(shù)據(jù)量和縮放級(jí)別下的運(yùn)算效率Fig.10　Performance of our approach under different data volumes and zoom levels

原型系統(tǒng)的顯著性投票算法用Javascript實(shí)現(xiàn)，已經(jīng)達(dá)到可觀的運(yùn)行效率，采用效率更高的語(yǔ)言或數(shù)據(jù)庫(kù)技術(shù)可進(jìn)一步提高系統(tǒng)效率。算法中在同一網(wǎng)格選擇重要性最高的要素需要掃描網(wǎng)格中所有數(shù)據(jù)項(xiàng)，通過(guò)對(duì)Morton碼和顯著性屬性添加B-Tree索引將大大加快該過(guò)程。

3.4圖面空間利用率

表1記錄了兩種算法處理不同數(shù)據(jù)量的圖面利用效率，試驗(yàn)中考察的區(qū)域是固定的，而顯著性評(píng)級(jí)為9，符號(hào)大小為45×45。當(dāng)數(shù)據(jù)量超過(guò)1000時(shí)，顯著性評(píng)級(jí)算法的圖面利用率穩(wěn)定在17.4%，因?yàn)樘囟▍^(qū)域內(nèi)符號(hào)數(shù)量是有界的(≤格網(wǎng)數(shù)量)。格網(wǎng)增選可提升圖面利用率，隨著數(shù)據(jù)量增大，格網(wǎng)增選貢獻(xiàn)越大，在105量級(jí)上基本達(dá)到飽和(47.9%)。此外，符號(hào)越大空間浪費(fèi)越大，因而圖面利用率也會(huì)下降(圖10)，具體不再贅述。

表1算法的圖面利用率

Tab.1Map space usage (percentage) under varying data volumes

數(shù)據(jù)量顯著性投票/(%)格網(wǎng)增選/(%)102.52.510014.618.4100017.439.01000017.446.010000017.447.9

此外，本文在多級(jí)符號(hào)疊加試驗(yàn)中選用兩級(jí)符號(hào)疊加，小符號(hào)尺寸為大符號(hào)的1/4，進(jìn)行選取的網(wǎng)格層級(jí)比大符號(hào)層級(jí)深兩級(jí)，兩級(jí)符號(hào)的顯著性評(píng)級(jí)均為9，小符號(hào)在大符號(hào)層級(jí)中的顯著性低于9，在較深層次被選取出來(lái)。圖11展示了真實(shí)數(shù)據(jù)在不同縮放級(jí)別下的結(jié)果，可見(jiàn)多級(jí)符號(hào)疊加可以改善圖面利用率，具有縮放穩(wěn)定性。該可視化方案可突出重要目標(biāo)，弱化次要目標(biāo)，過(guò)濾無(wú)關(guān)目標(biāo)，以視覺(jué)層次原則區(qū)分專題要素的語(yǔ)義重要性。

圖11　對(duì)Flickr數(shù)據(jù)的多級(jí)符號(hào)疊加結(jié)果Fig.11　Increasing map space usage with two-level overlay

值得注意的是，圖面利用率是一個(gè)設(shè)計(jì)問(wèn)題，并不是越大越好。利用率究竟在多少比較合適，點(diǎn)狀符號(hào)大小如何選擇，選擇多少級(jí)符號(hào)疊加，各級(jí)符號(hào)大小關(guān)系如何，都需要視地圖目的用途而定，并需要開(kāi)展用戶試驗(yàn)來(lái)評(píng)價(jià)認(rèn)知效率。

4　結(jié)　論

本文研究了一種可高效處理大量符號(hào)空間沖突的多尺度可視化方法。該方法可確保任意尺度下符號(hào)之間100%無(wú)壓蓋，適用于海量“大尺寸”符號(hào)的地圖混搭。因?yàn)椴恍杩臻g計(jì)算即能完成空間沖突消解，能夠達(dá)到極高的處理效率，在原型系統(tǒng)中的Javascript非優(yōu)化實(shí)現(xiàn)中可達(dá)到105級(jí)別數(shù)據(jù)亞秒級(jí)處理效率。同時(shí)由于實(shí)時(shí)進(jìn)行顯著性投票，本方法可支持動(dòng)態(tài)語(yǔ)義過(guò)濾：在投票前對(duì)數(shù)據(jù)進(jìn)行語(yǔ)義過(guò)濾，首先選取與用戶高度相關(guān)的子集(如食品類)，再對(duì)該子集進(jìn)行重要性投票，可獲得用戶相關(guān)信息的無(wú)沖突表達(dá)。顯著性投票方法能夠體現(xiàn)空間目標(biāo)的重要性關(guān)系，不同顯著等級(jí)的目標(biāo)在地圖縮放層次中漸進(jìn)累加，符合信息可視化與空間數(shù)據(jù)多尺度建模的一般規(guī)律[12,21]，并可進(jìn)一步將結(jié)果存儲(chǔ)于層次結(jié)構(gòu)用于提高效率或漸進(jìn)式傳輸目的。擴(kuò)展方法可提高Web制圖的圖面利用率，其中多級(jí)符號(hào)疊加方法符合視覺(jué)層次理論，在同一尺度區(qū)分專題符號(hào)的語(yǔ)義層次，增加可視化的信息獲取效率。進(jìn)一步的研究將開(kāi)展定量用戶調(diào)查，考查該方法的可用性、易用性，為Web地圖設(shè)計(jì)提供依據(jù)，并在地圖認(rèn)知理論方面開(kāi)展相關(guān)研究。

[1]ROICK O, HEUSER S. Location Based Social Networks: Definition, Current State of the Art and Research Agenda[J]. Transactions in GIS, 2013, 17(5): 763-784.

[2]FIELD K, O’BRIEN J. Cartobiography: Experiments in Using and Organising the Spatial Context of Micro-blogging[J]. Transactions in GIS, 2010, 14(S1): 5-23.

[3]KORPI J, AHONEN-RAINIO P. Clutter Reduction Methods for Point Symbols in Map Mashups[J]. The Cartographic Journal, 2013, 50(3): 257-265.

[4]ELLIS G, DIX A. A Taxonomy of Clutter Reduction for Information Visualisation[J]. IEEE Transactions on Visualization and Computer Graphics, 2007, 13(6): 1216-1223.

[5]艾廷華, 劉耀林. 保持空間分布特征的群點(diǎn)化簡(jiǎn)方法[J]. 測(cè)繪學(xué)報(bào), 2002, 31(2): 175-181.AI Tinghua, LIU Yaolin. A Method of Point Cluster Simplification with Spatial Distribution Properties Preserved[J]. Acta Geodaetica et Cartographica Sinica, 2002, 31(2): 175-181.

[6]蔡永香, 郭慶勝. 基于Kohonen網(wǎng)絡(luò)的點(diǎn)群綜合研究[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2007, 32(7): 626-629.CAI Yongxiang, GUO Qingsheng. Points Group Generalization Based on Konhonen Net[J]. Geomatics and Information Science of Wuhan University, 2007, 32(7): 626-629.

[7]DE BERG M, BOSE P, CHEONG O, et al. On Simplifying Dot Maps[J]. Computational Geometry, 2004, 27(1): 43-62.

[8]鄧紅艷, 武芳, 錢海忠, 等. 基于遺傳算法的點(diǎn)群目標(biāo)選取模型[J]. 中國(guó)圖象圖形學(xué)報(bào), 2003, 8(8): 970-976.

DENG Hongyan, WU Fang, QIAN Haizhong, et al. A Model of Point Cluster Selection Based on Genetic Algorithms[J]. Journal of Image and Graphics, 2003, 8(8): 970-976.

[9]T?PFER F, PILLEWIZER W. The Principles of Selection[J]. The Cartographic Journal, 1966, 3(1): 10-16.

[10]BEEN K, N?LLENBURG M, POON S H, et al. Optimizing Active Ranges for Consistent Dynamic Map Labeling[J]. Computational Geometry, 2010, 43(3): 312-328.

[11]SCHWARTGES N, ALLERKAMP D, HAUNERT J, et al. Optimizing Active Ranges for Point Selection in Dynamic Maps[C]∥Proceedings of the 16th ICA Generalisation Workshop (ICAGW’13). Dresden: Bib Sonomy, 2013.

[12]艾廷華, 成建國(guó).對(duì)空間數(shù)據(jù)多尺度表達(dá)有關(guān)問(wèn)題的思考[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2005, 30(5): 377-382.

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.

[13]VAN OOSTEROM, P. Variable-scale Topological Data Structures Suitable for Progressive Data Transfer: The Gap-face Tree and Gap-edge Forest[J]. Cartography and Geographic Information Science, 2005, 32(4): 331-346.

[14]NUTANONG S, ADELFIO M D, SAMET H. Multiresolution Select-distinct Queries on Large Geographic Point Sets[C]∥Proceedings of the 20th International Conference on Advances in Geographic Information Systems. New York, NY: ACM, 2012: 159-168.

[15]SARMA A D, LEE H, GONZALEZ H, et al. Efficient Spatial Sampling of Large Geographical Tables[C]∥Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. New York, NY: ACM, 2012: 193-204.

[16]BEREUTER P, WEIBEL R. Real-time Generalization of Point Data in Mobile and Web Mapping Using Quadtrees[J]. Cartography and Geographic Information Science, 2013, 40(4): 271-281.

[17]KOVANEN J, SARJAKOSKI L T. Sequential Displacement and Grouping of Point Symbols in a Mobile Context[J]. Journal of Location Based Services, 2013, 7(2): 79-97.

[18]楊敏, 艾廷華, 盧威, 等. 自發(fā)地理信息興趣點(diǎn)數(shù)據(jù)在線綜合與多尺度可視化方法[J]. 測(cè)繪學(xué)報(bào), 2015, 44(2): 228-234. DOI: 10.11947/j.AGCS.2015.20130564.

YANG Min, AI Tinghua, LU Wei, et al. A Real-time Generalization and Multi-scale Visualization Method for POI Data in Volunteered Geographic Information[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(2): 228-234. DOI: 10.11947/j.AGCS.2015.20130564.

[19]HARRIE L, SARJAKOSKI T, LEHTO L. A Mapping Function for Variable-scale Maps in Small-display Cartography[J]. Journal of Geospatial Engineering, 2002, 4(2): 111-123.

[20]HAUNERT J H, SERING L. Drawing Road Networks with Focus Regions[J]. IEEE Transactions on Visualization and Computer Graphics, 2011, 17(12): 2555-2562.

[21]SHNEIDERMAN B. The Eyes Have It: A Task by Data Type Taxonomy for Information Visualizations[C]∥Proceedings of the IEEE Symposium on Visual Languages. Boulder, CO: IEEE, 1996: 336-343.

(責(zé)任編輯：宋啟凡)

修回日期： 2016-06-23

E-mail： xiang.zhang@whu.edu.cn

Clutter-free Visualization of Large Point Symbols at Multiple Scales by Offset Quadtrees

ZHANG Xiang1,WANG Shaodong2,WANG Yuxia3

1. School of Resources and Environmental Sciences, Wuhan University, Wuhan 430079, China；2. Institute of Software Chinese Academy of Sciences, Beijing 100190, China；3.Institute of Remote Sensing and Geographical Information Systems, Peking University, Beijing 100871, China

To address the cartographic problems in map mash-up applications in the Web 2.0 context, this paper studies a clutter-free technique for visualizing large symbols on Web maps. Basically, a quadtree is used to select one symbol in each grid cell at each zoom level. To resolve the symbol overlaps between neighboring quad-grids, multiple offsets are applied to the quadtree and a voting strategy is used to compute the significant level of symbols for their selection at multiple scales. The method is able to resolve spatial conflicts without explicit conflict detection, thus enabling a highly efficient processing. Also the resulting map forms a visual hierarchy of semantic importance. We discuss issues such as the relative importance, symbol-to-grid size ratio, and effective offset schemes, and propose two extensions to make better use of the free space available on the map. Experiments were carried out to validate the technique,which demonstrates its robustness and efficiency (a non-optimal implementation leads to a sub-second processing for datasets of a 105magnitude).

clutter reduction; multi-scale visualization; large symbols; quadtree; real-time Web mapping

ZHANG Xiang(1982—)，male，PhD，associate professor，majors in volunteered geographic information processing and visualization.

10.11947/j.AGCS.2016.20150446.

P208

A

1001-1595(2016)08-0983-09

國(guó)家自然科學(xué)基金(41301410)；國(guó)家863計(jì)劃(2015AA123901)；國(guó)家基礎(chǔ)科學(xué)人才培養(yǎng)基金(J1103409)

2015-08-30

張翔(1982—)，男，博士，副教授，研究方向?yàn)橹驹刚叩乩硇畔⑻幚砼c可視化。

引文格式：張翔，王少東，王玉霞.基于偏移四叉樹(shù)投票的“大尺寸”點(diǎn)狀符號(hào)多尺度無(wú)壓蓋可視化[J].測(cè)繪學(xué)報(bào)，2016,45(8)：983-991.

ZHANG Xiang, WANG Shaodong, WANG Yuxia.Clutter-free Visualization of Large Point Symbols at Multiple Scales by Offset Quadtrees[J]. Acta Geodaetica et Cartographica Sinica,2016,45(8):983-991. DOI:10.11947/j.AGCS.2016.20150446.