空間數(shù)據(jù)快速索引技術(shù)研究

楊燦

摘要

隨著空間數(shù)據(jù)在多個領(lǐng)域和行業(yè)的廣泛使用，各行各業(yè)對空間數(shù)據(jù)的共享和服務(wù)效率提出了更高要求，而傳統(tǒng)的瓦片瀏覽技術(shù)制約了數(shù)據(jù)共享服務(wù)的效率提升。本文通過對空間數(shù)據(jù)索引技術(shù)研究，提出了空間特征關(guān)鍵信息提取與顯示的數(shù)據(jù)索引技術(shù)，研究數(shù)據(jù)顯示與顯示范圍之間的關(guān)系，精確控制顯示范圍內(nèi)數(shù)據(jù)查詢、顯示的數(shù)據(jù)量，達(dá)到了的數(shù)攏快速篩選與獲取。

【關(guān)鍵詞】空間數(shù)據(jù) 索引 空間特征

1 前言

隨著空間數(shù)據(jù)在多個領(lǐng)域和行業(yè)的廣泛使用，各行各業(yè)對空間數(shù)據(jù)的共享需求逐年遞增，數(shù)據(jù)現(xiàn)勢性和服務(wù)效率要求也越來越高。如何有效提升數(shù)據(jù)的應(yīng)用效率，提供實(shí)時穩(wěn)定的數(shù)據(jù)共享接口服務(wù)，是迫切需要解決的問題。目前瓦片技術(shù)是空間數(shù)據(jù)在線瀏覽的主流技術(shù)，其網(wǎng)絡(luò)傳輸效率高，數(shù)據(jù)瀏覽速度快。但與此同時瓦片的應(yīng)用也帶來了一定的弊端，主要存在以下不足：

（1）瓦片數(shù)據(jù)存儲空間大;

（2）瓦片數(shù)據(jù)不能實(shí)時分析編輯;

（3）數(shù)據(jù)現(xiàn)勢性與瓦片更新滯后性有矛盾，數(shù)據(jù)更新受制于瓦片更新。

因此，通過研究空間數(shù)據(jù)快速顯示技術(shù)，突破瓦片數(shù)據(jù)瀏覽的傳統(tǒng)技術(shù)瓶頸，實(shí)現(xiàn)無需裁剪瓦片的模式下空間數(shù)據(jù)的實(shí)時快速檢索將十分有意義。

2 國內(nèi)外研究現(xiàn)狀

空間數(shù)據(jù)庫的檢索經(jīng)過多年研究涌現(xiàn)了大量的數(shù)據(jù)索引方法。主流的索引方法有B樹索引、R樹索引、網(wǎng)格索引、四叉樹、KD樹及其變形樹等。

2.1 B樹索引

B樹，即二叉搜索樹，其工作原理為：基于根節(jié)點(diǎn)的關(guān)鍵信息查找與匹配。一般而言需要搜索的信息與節(jié)點(diǎn)關(guān)鍵信息有偏差，通過關(guān)鍵信息對比，進(jìn)入左節(jié)點(diǎn)或者右節(jié)點(diǎn)匹配，通過二分法查找可以快速查詢結(jié)果。實(shí)際中使用B樹都是在B樹的基礎(chǔ)上加上平衡算法，是一種平衡多路查找樹，其原理是把數(shù)據(jù)劃分為樹狀層次索引，每個節(jié)點(diǎn)占一個存儲塊。

2.2 R樹索引

R樹索引作為一種重要的空間數(shù)據(jù)索引結(jié)構(gòu)，目前己成為許多空間索引方法的基礎(chǔ)，不少前沿的空間索引都使用R樹或者對R樹改良。其原理是以參考地理空間位置邊框搜索方法，對聚合程度高的節(jié)點(diǎn)進(jìn)行矩形邊框滑動檢索。樹結(jié)構(gòu)中，將聚合程度高的節(jié)點(diǎn)作為上層邊框矩形，并賦予節(jié)點(diǎn)對象。通過矩形搜索，可以選擇性地忽略無效節(jié)點(diǎn)，由于空間數(shù)據(jù)的特有幾何特征，有利于R樹索引的高效檢索。但是由于采用遍歷算法進(jìn)行節(jié)點(diǎn)查詢，通常這種查詢會因為空間數(shù)據(jù)幾何重疊的因素而導(dǎo)致效率受到制約，因此通常采用R+樹索引和R*樹索引。

2.3 網(wǎng)格索引

網(wǎng)格索引作為一種常用的空間數(shù)據(jù)索引，其原理是將空間實(shí)體數(shù)據(jù)的范圍劃分成一系列的空間單元格，每個單元格都存儲了關(guān)鍵的地理對象屬性值。對每個單元格采用行列標(biāo)簽進(jìn)行位置標(biāo)注與記錄。當(dāng)用戶進(jìn)行空間查詢時，通過查詢行列編號確定網(wǎng)格位置，通過關(guān)鍵地理屬性值匹配地理單位。但是，由于空間數(shù)據(jù)種類繁多，通常要素復(fù)雜時，會產(chǎn)生索引的冗余，容易導(dǎo)致記錄信息的重復(fù)和冗余量增大，查詢效率低下。

2.4 四又樹索引

四叉樹索引借鑒了網(wǎng)格索引的方式，通過對地理空間進(jìn)行網(wǎng)格單位劃分。相比與網(wǎng)格索引，四叉樹索引主要是對地理空間進(jìn)行四分劃定，然后利用遞歸的思想，對每一個劃定區(qū)域繼續(xù)四分劃定，直到節(jié)點(diǎn)關(guān)聯(lián)單元少于4個為止。由于幾何特征的復(fù)雜性以及單元聚合，采用最小邊框矩形進(jìn)行空間過濾，不斷進(jìn)行幾何運(yùn)算，達(dá)到檢索符合條件的地理單元。但是，與網(wǎng)格索引類似也容易產(chǎn)生索引冗余。

2.5 KD樹索引

KD樹是基于二叉樹索引的的一種多維數(shù)據(jù)的結(jié)構(gòu)，是多維空間中的一種二分檢索樹，常存儲和組織空間中的點(diǎn)數(shù)據(jù)集合。而KDB樹兼有KD樹和B樹的特性，以B樹的方式進(jìn)行插入和刪除。對于簡單的地理要素，如點(diǎn)要素，具有較好的檢索效率。但是，對于空間線、面要素等區(qū)域范圍的檢索略顯不足。

3 空間數(shù)據(jù)快速索引技術(shù)

綜合應(yīng)用現(xiàn)有空間數(shù)據(jù)索引技術(shù)，通過對數(shù)據(jù)空間特性的分析研究，研究數(shù)據(jù)顯示與顯示范圍之間的關(guān)系，精確控制顯示范圍內(nèi)數(shù)據(jù)查詢、顯示的數(shù)據(jù)量，可以達(dá)到快速的數(shù)據(jù)篩選與獲取。

3.1 快速索引原理

在數(shù)據(jù)顯示時，可視區(qū)域通常小于實(shí)際數(shù)據(jù)的整個范圍，且可視區(qū)域內(nèi)的數(shù)據(jù)在不同分辨率下要表達(dá)的清晰度和完整度也有所差異，如在復(fù)位狀態(tài)下要顯示的數(shù)據(jù)通常需要表達(dá)出數(shù)據(jù)完整的區(qū)域范圍，但數(shù)據(jù)的清晰度不需太高，而在放大狀態(tài)下的數(shù)據(jù)的清晰度要求提高，區(qū)域范圍卻在縮小。通過對空間范圍進(jìn)行網(wǎng)格劃分成塊，采用行列標(biāo)識編號，如圖1所示。

空間范圍內(nèi)某一點(diǎn)（x，y）所在數(shù)據(jù)標(biāo)識公式為：

式中：ID_XY為空間單元數(shù)據(jù)標(biāo)識號，X為列方向坐標(biāo)，y為行方向坐標(biāo)，Data Width為空間區(qū)域?qū)挾龋珺lock Width，Block Height分別為數(shù)據(jù)單元的寬度和高度，[]為數(shù)值向下取整，日為數(shù)值向上取整。

3.2 空間特征提取

對空間數(shù)據(jù)庫進(jìn)行圖元級別的空間特征提取，據(jù)此建立特征字段，并創(chuàng)建相應(yīng)的索引，實(shí)現(xiàn)對圖元的動態(tài)篩選和快速訪問。對于具有矢量空間特征的數(shù)據(jù)而言，提取與表達(dá)數(shù)據(jù)關(guān)鍵特征是該類數(shù)據(jù)檢索查詢的重點(diǎn)內(nèi)容，而遙感影像數(shù)據(jù)則是利用其RGB顏色特征與空間分布要素信息結(jié)合，因此可以利用影像柵格單元增加空間分布信息。矢量空間數(shù)據(jù)的特征碼是數(shù)據(jù)的最基本的特征，它包含了方位、位置、拓?fù)涞刃畔ⅰＳ跋駭?shù)據(jù)的位置、色彩與輪廓也為識別目標(biāo)數(shù)據(jù)提供了特征信息，因此這些特征信息的提取則成為研究的關(guān)鍵。具體操作過程為：設(shè)定一個n×n的矩陣過濾器，通過過濾器平移滑過數(shù)據(jù)的各個行列像素，將過濾器中心像素與它的8個相鄰像素色差進(jìn)行對比，通過數(shù)值比對，可以確定中心像素是否處于邊緣或者是平滑像素，不同的比對結(jié)果需要建立不同的直方圖進(jìn)行分析。

3.3 數(shù)據(jù)庫存儲過程建立

在數(shù)據(jù)庫端建立數(shù)據(jù)索引、及其數(shù)據(jù)庫存儲過程，通過預(yù)先編輯好存儲函數(shù)以及相應(yīng)的參數(shù)調(diào)用方法，無需每次執(zhí)行查詢時遍歷整個數(shù)據(jù)集。通過建立存儲過程，可以只需要對索引進(jìn)行訪問，通過輸入?yún)?shù)設(shè)置，可以得到不同區(qū)域范圍的空間要素，或者選取特定的顯示范圍，這樣則提高了海量數(shù)據(jù)的查詢、檢索、渲染的效率?；跀?shù)據(jù)庫存儲過程，利用索引在數(shù)據(jù)庫端同時建立了圖元空間特征與幾何圖元之間的動態(tài)更新計算機(jī)制，實(shí)現(xiàn)圖元空間和屬性更新后的對應(yīng)空間特征刷新。

3.4 索引維護(hù)

對空間特征進(jìn)行智能自動多級維護(hù)，保證索引與圖元以及空間特征的一致性。整個數(shù)據(jù)顯示過程分主要由幾個對象類實(shí)現(xiàn)：

3.4.1 數(shù)據(jù)讀取

通過輸入空間區(qū)域劃分單元的邊框矩形的標(biāo)識值與范圍Width、Height值，實(shí)現(xiàn)獲取標(biāo)識的矩形區(qū)域邊框。對于影像數(shù)據(jù)，還需要輸入金字塔的層標(biāo)識碼，可以獲取該層級的影像信息。

3.4.2 數(shù)據(jù)與顯示緩存

把獲取的矩形區(qū)域內(nèi)的數(shù)據(jù)單元數(shù)據(jù)存儲到內(nèi)存，利用Map容器裝載緩存單位。對于影像數(shù)據(jù)，利用MFC框架中的CBitmap對象;實(shí)現(xiàn)影像數(shù)據(jù)位圖數(shù)據(jù)尺寸與顯示緩存尺寸匹配。

3.4.3 數(shù)據(jù)調(diào)閱顯示

通過前面兩個對象類獲取的空間數(shù)據(jù)或者影像數(shù)據(jù)，調(diào)用MFC框架中的Cscrollview對象，實(shí)現(xiàn)整個數(shù)據(jù)的調(diào)閱與顯示。通過幾個對象類的實(shí)現(xiàn)，可以保證整個數(shù)據(jù)從裝載到顯示過程中的流暢與穩(wěn)定。

4 試驗與結(jié)論

通過在開發(fā)的“XXX空間數(shù)據(jù)顯示原型系統(tǒng)”過程中，運(yùn)用數(shù)據(jù)快速索引技術(shù)，有效提升了數(shù)據(jù)的檢索效率。試驗機(jī)器CPU為P43.04GHz、內(nèi)存為16GB，試驗數(shù)據(jù)為分辨率為0.2m遙感數(shù)據(jù)，尺寸為5120×5120的3個波段，數(shù)據(jù)量接近3TB，格式為TIFF。測試的可視窗口大小為1366×768像素。從打開文件到顯示全景圖共耗時799ms;對數(shù)據(jù)進(jìn)行視圖瀏覽循環(huán)操作，每次系統(tǒng)響應(yīng)耗時均在2s之內(nèi)，保證了數(shù)據(jù)瀏覽的穩(wěn)定與流暢。在測試過程中，系統(tǒng)本身消耗的內(nèi)存始終保持在130MB以內(nèi)。通過實(shí)驗，該方法易于實(shí)現(xiàn)、冗余數(shù)據(jù)少以及對機(jī)器硬件資源消耗少等優(yōu)勢，較好地提升了地理空間數(shù)據(jù)的檢索與顯示效率，在實(shí)時業(yè)務(wù)分析與數(shù)據(jù)調(diào)閱過程中，可以穩(wěn)定地進(jìn)行快速查詢與結(jié)果展示。

參考文獻(xiàn)

[1]程昌秀.矢量數(shù)據(jù)多尺度空間索引方法的研究[J].武漢大學(xué)學(xué)報.信息科學(xué)版，2009（05）.

[2]鄭坤，朱良峰等.GIS空間索引技術(shù)研究[J].地理與地理信息科學(xué)，2016（07）.

[3]程偉，王波等.海量圖像數(shù)據(jù)快速顯示方法及實(shí)現(xiàn)[J].地理與地理信息科學(xué)，2011（01）.

[4]史婷婷等.一種新的圖像空間特征提取方法[J].計算機(jī)工程，2012（02）.