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

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

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

0 引言

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

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

1 HBase體系結構

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

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

HBase系統架構：

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

1）HBaseMaster

HBaseMaster負責分配HRegion給 HRegionServer，同時監控HRegionServer的運行情況。

2）HRegionServer

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

3）HBaseClient

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

4）HFile

HFile是HBase實現Bigtable快速檢索和存儲功能的基本單元，主要負責列族數據的存儲。

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗驗證

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

4 結語

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

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

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

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

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