基于偏移四叉樹投票的“大尺寸”點狀符號多尺度無壓蓋可視化

張　翔，王少東，王玉霞

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

?

基于偏移四叉樹投票的“大尺寸”點狀符號多尺度無壓蓋可視化

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

1. 武漢大學資源與環(huán)境科學學院，湖北 武漢 430079； 2. 中國科學院軟件研究所計算機科學國家重點實驗室，北京 100190； 3. 北京大學遙感與地理信息系統(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)境下點狀符號地圖混搭中的制圖問題，本文研究并實現(xiàn)了一種可100%避免壓蓋的“大尺寸”點符號高效可視化方法。該方法的核心思想是四叉樹網(wǎng)格單選，采用網(wǎng)格平移對多次單選結(jié)果投票來計算符號在各縮放級別的顯著性等級，可解決符號在相鄰網(wǎng)格的空間沖突。該過程不需要顯式探測沖突，因而處理效率極高。隨著地圖放大，重要性較低的符號也逐級顯現(xiàn)，實現(xiàn)了語義層次的多尺度表達。針對符號和網(wǎng)格大小比率關系、有效網(wǎng)格平移方案及圖面利用率不足問題提出兩種擴展：格網(wǎng)增選和多級符號疊加。對方法的可行性進行了試驗驗證，并分析了該方法在用戶查詢條件改變下的穩(wěn)定性和不同數(shù)據(jù)量下的伸縮性(非優(yōu)化實現(xiàn)可達到105量級數(shù)據(jù)的亞秒級處理)。

空間沖突消解；多尺度可視化；大尺寸符號；四叉樹；實時Web制圖

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

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

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

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

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

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

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

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

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

1　基于偏移Quadtree的多尺度顯著性評級

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

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

1.2空間上下文中的相對重要性

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

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

1.3網(wǎng)格與符號的大小關系

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

(1)

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

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

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

(2)

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

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

圖2Fig.2

1.5四叉樹多次平移與顯著性投票

設想四叉樹在不同方向進行多次平移，對每個網(wǎng)格在多次平移中的入選的重要目標進行投票，得票高者作為最終的入選結(jié)果。以圖2為例，假設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ā)生沖突的目標相比其重要性更高。合理的平移次數(shù)與方案能把當前目標與其臨近目標納入到相同網(wǎng)格中，并能在多尺度下持續(xù)有效。

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

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

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

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

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

圖3　不同偏移次數(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)

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

(3)

1.5.2離散平移下網(wǎng)格與符號的大小關系

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

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

(4)

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

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

1.5.3顯著性評級的計算流程

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

輸入：符號尺寸s；當前地圖縮放級別z；指定輸出目標的顯著性級別SL；查詢窗口Q；

輸出：縮放級別z對應的選取目標集合P。

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

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

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

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

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

(4) 對每個c∈C，把c加入集合P當且僅當c.ds≥SL。

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

2　增大圖面利用率的兩種擴展

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

2.1格網(wǎng)增選

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

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

輸出：縮放級別z對應的增選目標集合PS。

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

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

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

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

2.2多級符號疊加

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

3　試驗分析

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

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

3.2試驗結(jié)果

3.2.1算法執(zhí)行效果

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

圖5Fig.5

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

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

3.2.2顯著性評級對算法影響

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

圖7　模擬數(shù)據(jù)選取結(jié)果：顯著性評級不小于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算法響應實時變化效果

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

3.3系統(tǒng)效率

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

圖9　改變符號尺寸(格網(wǎng)增選的符號為空心矩形)：符號寬度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)在不同縮放級別的測試窗口均選擇在目標聚集區(qū)符號最多(圖10柱狀圖)的區(qū)域，其查詢時間(圖10方形折線圖)可視為當前級別的上限，在非聚集區(qū)的查詢效率更高；同時可見查詢時間與檢索出的結(jié)果數(shù)量具有正相關性。與真實數(shù)據(jù)不同，隨機生成點位分布比較平均，在幾次放大后數(shù)據(jù)密度迅速下降，沒有聚集中心，使得查詢效率快速提高；模擬數(shù)據(jù)在較大縮放級別下的查詢時間在2 ms以內(nèi)，為清晰起見，圖10中不予表達。

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

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

3.4圖面空間利用率

表1記錄了兩種算法處理不同數(shù)據(jù)量的圖面利用效率，試驗中考察的區(qū)域是固定的，而顯著性評級為9，符號大小為45×45。當數(shù)據(jù)量超過1000時，顯著性評級算法的圖面利用率穩(wěn)定在17.4%，因為特定區(qū)域內(nèi)符號數(shù)量是有界的(≤格網(wǎng)數(shù)量)。格網(wǎng)增選可提升圖面利用率，隨著數(shù)據(jù)量增大，格網(wǎng)增選貢獻越大，在105量級上基本達到飽和(47.9%)。此外，符號越大空間浪費越大，因而圖面利用率也會下降(圖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

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

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

值得注意的是，圖面利用率是一個設計問題，并不是越大越好。利用率究竟在多少比較合適，點狀符號大小如何選擇，選擇多少級符號疊加，各級符號大小關系如何，都需要視地圖目的用途而定，并需要開展用戶試驗來評價認知效率。

4　結(jié)　論

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

[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]艾廷華, 劉耀林. 保持空間分布特征的群點化簡方法[J]. 測繪學報, 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)絡的點群綜合研究[J]. 武漢大學學報(信息科學版), 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]鄧紅艷, 武芳, 錢海忠, 等. 基于遺傳算法的點群目標選取模型[J]. 中國圖象圖形學報, 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]艾廷華, 成建國.對空間數(shù)據(jù)多尺度表達有關問題的思考[J]. 武漢大學學報(信息科學版), 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ā)地理信息興趣點數(shù)據(jù)在線綜合與多尺度可視化方法[J]. 測繪學報, 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.

(責任編輯：宋啟凡)

修回日期： 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

國家自然科學基金(41301410)；國家863計劃(2015AA123901)；國家基礎科學人才培養(yǎng)基金(J1103409)

2015-08-30

張翔(1982—)，男，博士，副教授，研究方向為志愿者地理信息處理與可視化。

引文格式：張翔，王少東，王玉霞.基于偏移四叉樹投票的“大尺寸”點狀符號多尺度無壓蓋可視化[J].測繪學報，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.