一种基于Hilbert曲线的HBase遥感影像检索方法

2014-01-07全吉成袁昱纬赵秀影王宏伟

科技视界 2014年31期

吴晨全吉成袁昱纬赵秀影王宏伟

（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编码组织影像数据可以高效地完成检索任务。