孫立偉，袁昱緯，周俊芳

(1.中國人民解放軍91977部隊，北京 102249；2.中國人民解放軍92999部隊，北京 102400)

0 引言

場景數(shù)據(jù)的調(diào)度策略是實現(xiàn)大規(guī)模場景數(shù)據(jù)的存儲管理[1]、處理[2]、瀏覽顯示[3]和分發(fā)[4]應(yīng)用[5]的基礎(chǔ)，對于數(shù)字地球等[6]應(yīng)用性能也起著決定性的作用。隨著場景數(shù)據(jù)量以幾何級數(shù)增長，數(shù)據(jù)規(guī)模越來越大，給場景數(shù)據(jù)的組織調(diào)度效率帶來了極大的考驗[7]。目前，許多學(xué)者對數(shù)據(jù)調(diào)度算法進行了研究?；粑√岢隽艘环N基于層次金字塔結(jié)構(gòu)和四叉樹索引結(jié)構(gòu)相結(jié)合的數(shù)據(jù)組織調(diào)度方法，僅僅在內(nèi)存中存儲了索引結(jié)構(gòu)，提高了檢索效率，但是數(shù)據(jù)冗余嚴(yán)重[8]。劉恒飛則設(shè)計了一種基于四叉樹索引結(jié)構(gòu)與網(wǎng)格劃分的數(shù)據(jù)調(diào)度方法，減少了數(shù)據(jù)重復(fù)存儲，提高檢索效率[9]。吳穎等人則利用四叉樹分割的思想，實現(xiàn)對大規(guī)模場景數(shù)據(jù)的裁剪，提升場景的繪制效率，減少了內(nèi)存占有率[10]。通過對傳統(tǒng)四叉樹索引技術(shù)[11]應(yīng)用到海量場景數(shù)據(jù)調(diào)度進行研究，可知數(shù)據(jù)調(diào)度的研究主要集中在數(shù)據(jù)存儲、層次劃分以及空間索引等方面，因此本文研究并提出了一種采用Hilbert空間排列碼的大規(guī)模場景數(shù)據(jù)調(diào)度策略，利用空間排序碼的空間聚集特性，將海量高維數(shù)據(jù)向低維空間靠近，同時通過最近鄰算法提高相鄰空間數(shù)據(jù)連續(xù)存儲的概率，優(yōu)化場景數(shù)據(jù)存儲管理，提高數(shù)據(jù)調(diào)度效率。

1 Hilbert空間排列碼

Hilbert曲線[12]于1891年提出，源自Peano曲線簇。采用Hilbert曲線可以建立二維甚至多維空間向一維線性空間的一一映射關(guān)系，這個一維線性空間的映射序列稱為Hilbert空間排列碼。Hilbert空間排列碼具有優(yōu)良的空間聚集性能[13-14]，可以使二維或多維空間中相鄰的元素在轉(zhuǎn)換的一維線性序列中盡量相鄰。

吳明光等[15]將Hilbert曲線引入數(shù)據(jù)集劃分問題，提高數(shù)據(jù)空間分布的均衡性，吳晨等[16]等將Hilbert曲線引入HBase遙感影像檢索中，提高了影像數(shù)據(jù)的檢索效率。楊明遠[17]等將Hilbert曲線引入數(shù)據(jù)庫存儲結(jié)構(gòu)優(yōu)化中，較大幅度地增強了算法的空間范圍查詢效率。

本文考慮在對三維場景數(shù)據(jù)集的管理中，對于瓦片狀分布的空間實體[18-19]，引入Hilbert曲線及Hilbert空間排列碼，利用其空間聚集性能，優(yōu)化場景數(shù)據(jù)管理策略，增加空間中相鄰的場景數(shù)據(jù)在存儲時同樣連續(xù)的概率，使場景數(shù)據(jù)處理時磁盤盡量連續(xù)讀取，提高數(shù)據(jù)調(diào)度的效率。

2 基于Hilbert空間排列碼的數(shù)據(jù)調(diào)度策略

本文采用一種高效的Hilbert空間排列碼最近鄰查詢方法，有效地規(guī)避Hilbert在臨域查詢時計算復(fù)雜的弊端，同時利用Hilbert空間排列碼良好的空間聚集性能，提高數(shù)據(jù)管理時的搜索和調(diào)度效率，具體算法描述如下：

(1)三維場景數(shù)據(jù)集的預(yù)處理

遍歷三維場景所有區(qū)域，將場景劃分為N×N個地形分塊，并構(gòu)建金字塔模型的層次結(jié)構(gòu)；在邏輯層面上，一般采用四叉樹對金字塔模型的層次結(jié)構(gòu)進行組織和管理。

(2)專用數(shù)據(jù)集的Hilbert排列

該金字塔模型的每個層級中，每個地形分塊采用Hilbert空間排列碼的順序編碼，并按照該編碼順序進行存儲和管理。

由地形分塊的格網(wǎng)編碼轉(zhuǎn)化為Hilbert空間排列碼的方法如下：

① 將索引地形分塊格網(wǎng)的行列數(shù)采用二進制位交叉方法轉(zhuǎn)化為對應(yīng)的Morton碼；

② 將Morton碼轉(zhuǎn)化為二進制，以兩位為一個單位，由高位開始，對生成的Morton碼中的10和11互換；

③ 由高位開始，設(shè)為ti，對后續(xù)各位中的10和00進行互換；

④ 將結(jié)果按順序排列，即為Hilbert空間排列碼。按照Hilbert空間排列碼的順序練成曲線如圖1所示，高階的Hilbert空間排列碼可由圖1遞歸產(chǎn)生。

圖1 Hilbert空間排列碼示意

(3)計算視場區(qū)域格網(wǎng)坐標(biāo)范圍

首先將視點F處的經(jīng)緯度換算為格網(wǎng)坐標(biāo)。然后為減少浮點運算，提高數(shù)據(jù)讀取效率，視場區(qū)域內(nèi)的其他格網(wǎng)坐標(biāo)，不再采用經(jīng)緯度進行換算，而采用格網(wǎng)坐標(biāo)累加的方法得到，直至遇到邊緣的角點，如圖2所示。

假設(shè)視點F處的格網(wǎng)坐標(biāo)為(x，y)，圖2中的深灰區(qū)域為視點F處可見的視野范圍，并為其進行分塊，每個分塊大小的邊長為a。視野范圍中右側(cè)矩形區(qū)域左上角格網(wǎng)坐標(biāo)為(x+[V/a]，y+[w/2/a])，右下角格網(wǎng)坐標(biāo)為(w+{V+L}/a，y-{w/2/a})，(其中，[]表示向上取整，{ }表示向下取整)，視野范圍中左側(cè)三角形所在的格網(wǎng)坐標(biāo)則由矩形區(qū)域左上角、左下角和視點區(qū)域坐標(biāo)推出。

圖2 視野區(qū)域格網(wǎng)坐標(biāo)范圍示意

(4)采取基于視點擴散的讀取思路，提取視場范圍內(nèi)的地形分塊數(shù)據(jù)

得到視野區(qū)域所需地形分塊的格網(wǎng)坐標(biāo)后，按照(2)中的方法計算視點F的Hilbert編碼；然后以F點的Hilbert為起點，按照視點方向，進行臨域搜索，搜索范圍限定在(3)得到的格網(wǎng)范圍內(nèi)，將該范圍完全遍歷。

(5)按照Hilbert空間排列碼順序讀取和處理

在上一步的臨域搜索和遍歷的同時，對于每搜索一個分塊格網(wǎng)將其讀取，供處理和顯示使用。讀取時，按照首地址+偏移地址的方式進行，偏移地址=(本影像塊編碼-首影像塊編碼)×每個影像塊所占用的磁盤空間。

采用本算法對空間數(shù)據(jù)進行管理和調(diào)度，使后續(xù)進行的空間數(shù)據(jù)調(diào)度效率得到了很大的提高。例如，按照空間范圍進行查詢時，通過查詢區(qū)域內(nèi)的格網(wǎng)范圍，得到對應(yīng)的Hilbert空間排列碼，以此計算偏移地址進行提取，可以較大地減少重新計算地址的計算量，減少空間索引量，提高數(shù)據(jù)調(diào)度的性能。此外，由于Hilbert空間排列碼優(yōu)秀的線性映射特性，空間數(shù)據(jù)按照該順序存儲后，空間中相鄰的地形分塊在線性存儲上也是盡量相鄰存儲的，從而減少了磁盤的訪問時間，提高了數(shù)據(jù)處理效率。

3 實驗結(jié)果

實驗采用的硬件環(huán)境為Intel Xeon? CPU E3-1271 V3 3.60 GHz，8 GB內(nèi)存，NVIDIA Quadro K2200顯卡，軟件環(huán)境為Windows7，VS2010。實驗素材選取了6組場景數(shù)據(jù)，其大小分別為6.65，20.63，72.10，257.93，889.28，5 602.91 MB，分塊數(shù)量分別為128，512，2 048，8 192，32 768，131 072。

3.1 基于Hilbert空間排列碼的三維場景數(shù)據(jù)集構(gòu)建測試

對6組場景數(shù)據(jù)分別采用將經(jīng)典四叉樹編碼索引算法和本文提出算法構(gòu)建數(shù)據(jù)集，并對比2種方法在構(gòu)建時的耗時。實驗分別記錄經(jīng)典四叉樹編碼索引算法和本文提出算法構(gòu)建數(shù)據(jù)集的時間開銷，每組場景數(shù)據(jù)各測試5次，并計算平均值。經(jīng)過實驗驗證，實驗結(jié)果如表1所示。

表1 構(gòu)建結(jié)構(gòu)耗時的測試結(jié)果

數(shù)據(jù)量大小/MB分塊數(shù)量傳統(tǒng)方法構(gòu)建耗時/s本文方法構(gòu)建耗時/s6.6471280.466 90.468 820.6315122.120 62.294 972.7032 0489.620 910.032 4256.9568 19287.97591.741 9879.38232 768434.125482.0875 620.119131 0722 942.4813 140.316

從實驗結(jié)果可以看出，本文方法與傳統(tǒng)方法在進行三維場景數(shù)據(jù)集構(gòu)建的耗時相當(dāng)。由于四叉樹構(gòu)建的時間復(fù)雜度一般為O(nlogn)，與本文算法的時間復(fù)雜度相當(dāng)，其中，n為層次結(jié)構(gòu)中最底層分塊數(shù)量。本文方法略多的耗時主要發(fā)生在Hilbert排列碼的計算上。

3.2 場景數(shù)據(jù)隨機讀取測試

將6組實驗場景數(shù)據(jù)在金字塔模型的層次結(jié)構(gòu)中進行分級、分塊后，得到層級數(shù)分別為5～10層，實驗時分別采用本文提出方法(Hilbert空間排列碼順序)和四叉樹結(jié)構(gòu)(在各層級中按照先行后列、從左到右的順序)方式進行測試。實驗時，隨機指定行列號，讀取并顯示以該位置為中心的10×10個地形分塊，記錄使用上述方法在索引和讀取上的時間開銷。每組實驗場景分別進行5次測試，并計算平均值，如表2所示。

表2 場景數(shù)據(jù)隨機讀取耗時的測試結(jié)果

層級數(shù)四叉樹qrst編碼索引檢索耗時/msHilbert空間排列碼順序及檢索耗時/ms5830.27425.376991.30561.7471 297.70569.3881 620.76559.5291 893.53610.24102 219.80665.37

由表2中的實驗數(shù)據(jù)可知，本文提出的方法(Hilbert空間排列碼順序)與傳統(tǒng)方法的四叉樹結(jié)構(gòu)(先行后列、從左到右的順序)相比，隨機讀取效率明顯提高。本文算法在數(shù)據(jù)讀取時的時間復(fù)雜度為O(nlogn)，比經(jīng)典四叉樹算法的O(n)略多，其中n為層級數(shù)；但由于本文方法利用了Hilbert空間排列碼的特性，瀏覽三維場景時讀取的場景分塊一般為連續(xù)的，Hilbert空間排列碼在組織數(shù)據(jù)時，空間上相鄰的分塊在磁盤存儲時相鄰的概率較經(jīng)典四叉樹方法大很多，大部分的讀取能夠連續(xù)進行，減少了磁盤尋址時的開銷，縮短影像塊的讀取時間。

4 結(jié)束語

針對三維場景實時性瀏覽中的數(shù)據(jù)調(diào)度問題，本文研究了一種采用Hilbert空間排列碼的三維場景數(shù)據(jù)調(diào)度策略，通過Hilbert空間排列碼生成方法構(gòu)建數(shù)據(jù)集，以提高數(shù)據(jù)管理時的搜索和讀取效率。試驗表明，與基于傳統(tǒng)四叉樹的調(diào)度策略相比，在構(gòu)建時間相當(dāng)?shù)幕A(chǔ)上，本文方法的隨機讀取時間明顯減少，具有更高的場景數(shù)據(jù)調(diào)度效率。