一種基于Hilbert曲線的HBase遙感影像檢索方法

吳 晨 全吉成 袁昱緯 趙秀影 王宏偉

（1.中國人民解放軍空軍航空大學航空航天情報系，吉林 長春 130022；2.中國人民解放軍海軍航空工程學院電子信息工程系，山東 煙臺 264001）

0 引言

遙感影像信息豐富且形象直觀，在地理測繪、資源環(huán)境監(jiān)測、軍事偵察與戰(zhàn)場感知等方面具有重要應用。隨著對地觀測技術的快速發(fā)展，人類每天接收及處理產(chǎn)生的遙感影像數(shù)據(jù)量正在以幾何級數(shù)增加，加上之前積累的影像，獲取的遙感影像已達到海量的級別。而管理海量遙感影像的能力卻沒有跟上影像增長的步伐，導致“影像數(shù)據(jù)越多，可用的影像越少”[1]。

在這種情況下，傳統(tǒng)的集中式存儲已無法滿足海量遙感影像的管理要求。隨著云計算的興起，由于云計算本身就具有“無限的計算能力和存儲能力”[2]，其自然成為當前海量遙感影像存儲管理的首選方案。云計算并不是新發(fā)明的技術，而是眾多已有技術的綜合集成。Hadoop[3]是Apache軟件基金會的開源云計算系統(tǒng)。Hadoop的三個關鍵部分HDFS（Hadoop Distributed File System）、MapReduce、HBase[4]， 分 別 是Google云計算的GFS、MapReduce、Bigtable的開源實現(xiàn)。其中，HBase是建立在HDFS上的可隨機讀寫、面向列存儲、支持海量數(shù)據(jù)快速檢索的分布式數(shù)據(jù)庫。本文將Hilbert曲線應用到影像金字塔模型中，提出一種基于HBase的高效管理海量遙感影像方法，實現(xiàn)了海量遙感影的快速檢索。

1 HBase體系結構

HBase是Apache軟件基金會下的一款開源分布式數(shù)據(jù)庫軟件。HBase建立在HDFS之上，適用于對海量數(shù)據(jù)進行隨機快速讀寫。HBase構建在廉價計算機上，具有高可靠性、高穩(wěn)定性、可伸縮及面向列族存儲的優(yōu)點。

HBase在其結構和應用特點上不同于傳統(tǒng)關系型數(shù)據(jù)庫。HBase為了更好的可伸縮性和靈活性削弱了其他方面的優(yōu)勢，從而使得HBase具有獨特的數(shù)據(jù)模型。這也導致了其在表的設計方面與傳統(tǒng)關系型數(shù)據(jù)庫有很大區(qū)別。

HBase系統(tǒng)架構：

HBase的底層是Hadoop，其具體負責文件的可靠存儲與管理。HBase的主要組成部件有：

1）HBaseMaster

HBaseMaster負責分配HRegion給 HRegionServer，同時監(jiān)控HRegionServer的運行情況。

2）HRegionServer

HRegionServer負責處理HBaseClient的讀寫請求，同時與HBaseMaster聯(lián)系，以獲取服務所需的HRegion并報告HBaseMaster自身的運行狀況。

3）HBaseClient

HBaseClient負責尋找存儲了所要檢索數(shù)據(jù)的HRegionServer，其中HBaseClient會首先找到存儲RootRegion的位置。

4）HFile

HFile是HBase實現(xiàn)Bigtable快速檢索和存儲功能的基本單元，主要負責列族數(shù)據(jù)的存儲。

2 基于Hilbert曲線的影像金字塔模型

影像金字塔是目前公認的管理海量遙感影像的數(shù)據(jù)模型[9]。影像金字塔的分層分塊策略使客戶端可以快速獲取所需顯示的影像。本文的影像金字塔采用Plate Carree投影[9]。Plate Carree投影是一種可描述全球地理范圍的投影。在Plate Carree投影中，設層級為level(level≥

通常，為提高瓦片影像數(shù)據(jù)管理的空間聚集性，需要將空間填充曲線應用到影像金字塔模型中。目前，常用的空間填充曲線有行序、Peano曲線、Hilbert曲線等，如圖所示。Hilbert曲線源自經(jīng)典的Peano曲線簇，是目前已知編碼曲線中空間聚集性最好的一種。

本文采用0,1,2,3依次表示Hilbert曲線經(jīng)過一個2×2基本類型單元的次序。第一層的東西半球分別用 “1”、“0”編碼。將瓦片存儲到HBase數(shù)據(jù)庫時，每個瓦片都對應一個Hilbert編碼（簡稱Hcode），如“0323”?；贖code組織瓦片的特點為：

①瓦片的Hcode字符長度與其級數(shù)相等；

②在Hcode上相鄰的瓦片，空間位置也相鄰；空間位置相鄰的瓦片，Hcode一般也相鄰。

經(jīng)典的Hilbert編碼算法的時間復雜度為O（n2）。由于檢索時都需要將層級和瓦片位置轉換為Hcode，所以要盡量簡化Hilbert編碼算法。曹忠升[10]等提出了一種基于分劃思想的Hilbert曲線快速編碼算法，可將時間復雜度由O（n2）降低為O（n log n）。本文對該方法進行了相應的改進，提出基于查表的Hilbert快速編碼。

經(jīng)過觀察，Hilbert曲線具有很強的遺傳性，且每一層都由四種基本曲線類型組合而成。

規(guī)定1：設當前層的基本曲線單元為子單元 （2×2的特定位置網(wǎng)格），其曲線類型為子類型，則父單元為子單元對應上一級的基本單元，父類型為父單元的基本曲線類型。

規(guī)定2：基本單元的坐標示意圖如圖示，坐標原點位于基本單元的左上角點，將坐標x和y按二進制位計算得到象限號GroupID=x×21+y×20。除基本單元外，其他二維坐標也以左上角點為坐標原點。

父類型和子單元所處的象限號對應唯一的子類型和編碼。如此，按層級由上到下依次循環(huán)查表可得到所需的瓦片Hcode。

由Hcode反解到行列號，與正解相似。根據(jù)父類型和編碼可唯一確定子單元對應所在父單元的象限號和子類型。如此，按層級由上到下依次循環(huán)查反解表可得到象限號字符串GroupStr。

3 實驗驗證

基于Hilbert編碼索引的實驗數(shù)據(jù)表明，1-4級瀏覽時間高于行列編碼索引。這主要由于Hilbert編碼計算時間高于行列編碼，且在1-4級Hilbert的空間聚集性優(yōu)勢體現(xiàn)不明顯。4級以后隨著級別增加，Hilbert空間聚集性優(yōu)勢越來越明顯超過行列編碼的計算優(yōu)勢。整體上看，在HBase中采用Hilbert編碼組織影像數(shù)據(jù)可以高效地完成檢索任務。

4 結語

本文利用HBase分布式數(shù)據(jù)庫的列存儲模型特點，將Hilbert曲線應用到影像金字塔中，提出了一種基于查表的Hilbert快速編碼算法，通過實驗驗證了所提方法的有效性和實用性。下一步將研究如何提高HBase的存儲效率和基于MapReduce的影像進一步處理。

［1］李飛.影像數(shù)據(jù)庫管理系統(tǒng)關鍵技術研究[D].北京：中國科學院研究生院，2008：18-20.

［2］呂雪峰，程承旗，龔健雅，等.海量遙感數(shù)據(jù)存儲管理技術綜述[J].中國科學，41（21）：1561-1579.

［3］陸嘉恒.Hadoop 實戰(zhàn)[M].北京:機械工業(yè)出版社,2011：260-261.

［4］L.George.HBase:The Definitive Guide[M].2011：5-6.