法律状态公告日
法律状态信息
法律状态
2019-01-25
授权
授权
2015-12-23
实质审查的生效 IPC(主分类):G06F17/30 申请日:20150202
实质审查的生效
2015-05-27
公开
公开
技术领域
本发明属于遥感影像处理技术领域。
背景技术
经纬度剖分网格模型是按照固定的经线、纬线间隔递归划分的多层次网格，具有简单、快捷、实用优点。传统的经纬度剖分网格模型主要用于粗略表达地球表面的空间位置，一般经度要求不高，网格的划分层次不多。典型的剖分网格模型有NGA的世界地理参考系统（World Geographic Reference System, Georef）和全球区域参考系统(Globe Area Reference System, GARS)等。上述剖分网格模型源于不同的应用背景，基本上以经纬度坐标系统为划分基础，剖分层次一般为3~4层，各个层级都有较完整的编码体系，但是通常难以满足更精确的地理定位。瓦片金字塔模型是目前公认的组织管理海量影像的有效方法。由于构建瓦片金字塔时需要重采样生成低分辨率的上层影像，因此计算量大且耗时长。随着遥感影像数据量的急剧增加，集中处理模式已很难满足当前遥感影像的处理要求。剖分瓦片金字塔是统一管理全球海量影像的有效手段，能够实现同一地理坐标系下海量影像的快速浏览。由于影像数据的投影方式不同，瓦片金字塔模型会有所区别。一般需要根据应用需求，合理确定影像数据的投影格式。
发明内容
本发明的目的是基于MapReduce的并行计算模型，针对遥感影像的特点，快速进行批量遥感影像并行处理的基于MapReduce的静态瓦片金字塔并行构建方法。
本发明的步骤是：
（1）Map瓦片处理阶段：计算由单幅遥感影像 生成的瓦片金字塔的各层瓦片行列范围：
根据GTPM模型、遥感影像的空间大小和经纬度范围，确定输出瓦片的层级范围，其中，为表3.2中最接近分辨率的层级，对每个，计算出瓦片金字塔的各层瓦片在GTPM模型中的行列范围，公式如下：
（3.1）
其中，为向下取整；放大或缩小后的层影像像素大小为：
（3.2）
其中，为向上取整，为的像素宽度和高度；
（2）创建层瓦片任务：
对于涉及到层的每个瓦片影像，计算瓦片在层的像素坐标范围为：
（3.3）
在对进行采样生成时，影像数据贡献的像素范围为：
（3.4）
其中，为左上角像素点经纬度在层上的像素坐标；瓦片上的有效像素（不透明像素区域）范围可计算得到为：
（3.5）
其中，为右下角点经纬度在层上的像素坐标；确定了中和的有效像素区域对应的像素区域；构建了瓦片金字塔第层任务；再将第层瓦片作为输入执行上述步骤，即实现第层的瓦片任务构建，此时；如此循环直至生成第一层瓦片，实现瓦片金字塔任务的创建；
（3）瓦片影像的生成：
瓦片底层Lmax的瓦片影像
，其余层级的瓦片依照双线性内插法采样下一层的四个瓦片生成；
（4）Reduce瓦片合并阶段：
Reduce阶段合并相邻图幅影像之间的重复区域；此阶段，对于含有完整瓦片情况，只取其中一个完整瓦片即可；不完整瓦片进行合并时，只需采用图层叠加原理即可实现；这样就完成了遥感影像各层瓦片的镶嵌合并。
本发明提出改进的基于MapReduce批量遥感影像的静态瓦片金字塔构建算法，实现了批量遥感影像瓦片金字塔的快速并行构建与生成瓦片金字塔大文件的结合，将瓦片金字塔采用两级索引形式的大文件保存在HDFS中，为海量瓦片影像管理的瓦片索引并行入库与HBase瓦片索引表快速检索奠定基础，实现可以即时打开浏览遥感影像。通过本发明瓦片金字塔大文件和HBase瓦片索引表的结构，从而建立全球瓦片影像的快速检索模型。
附图说明
图1是本发明Map阶段流程图；
图2是单个与阵列磁盘的瓦片金字塔构建耗时情况；
图3是Raid5阵列和单个磁盘生成瓦片金字塔的CPU利用率；
图4是不同节点数目下批量瓦片金字塔构建耗时；
图5是Reduce阶段实验结果；
图6是瓦片影像快速检索实验实验一结果图；
图7是瓦片影像快速检索实验实验二结果图；
图8是第三层瓦片行列编码图；
图9是前五阶的Hilbert曲线；其中：(a) 一阶Hilbert曲线；(b) 二阶Hilbert曲线；(c) 三阶Hilbert曲线；(d) 四阶Hilbert曲线；(e) 五阶Hilbert曲线；
图10是基于Hilbert编码的影像金字塔模型。
具体实施方式
本发明全球瓦片金字塔模型（Globe Tile Pyramid Model，GTPM）为双塔四叉树结构，影像数据采用Plate Carree投影。第一层的东西瓦片是两个四叉树的根节点，之后将每个瓦片平均四分，得到下一层瓦片，这样就得到双塔四叉树结构。瓦片大小均设定为256像素×256像素，金字塔顶层为第一层，行列瓦片数为1×2。
第Level级的瓦片行列数与Level关系为：。
第一层以下的瓦片均是上一层父瓦片2×2均分，因此其分辨率是上一层瓦片的一半，各层瓦片数目与空间分辨率如表3.2示。
表3.2 GTPM各层对应分辨率
本发明约定的行列编码的原点位于瓦片各层的左上角点，第三层的瓦片行列编码如图8所示。
通常，为提高瓦片影像数据存储的空间聚集性，需要将空间填充曲线应用到影像金字塔的瓦片存储中。目前，常用的空间填充曲线有行序、Peano曲线、Hilbert曲线等。Hilbert曲线源自经典的Peano曲线簇，是目前已知填充曲线中空间聚集性最好的一种，图9为前五阶Hilbert曲线图。
本发明采用0，1，2，3依次表示Hilbert曲线经过一个2×2基本类型单元的先后次序。第一层的东西半球分别用“1”、“0”编码。将瓦片索引存储到HBase数据库时，每个瓦片都对应一个四进制Hilbert编码字符串（简称Hcode），如“0132”，如图10示为本发明的瓦片金字塔模型。基于Hcode组织瓦片的特点为：
（1）瓦片的Hcode字符长度与其级数相等；
（2）在Hcode上相邻的瓦片，空间位置也一定相邻；空间位置相邻的瓦片，Hcode一般也相邻。如果按照Hcode顺序存储，则可以充分利用Hilbert曲线优良的空间聚集性；
（3）Hcode可以与HBase表的主键RowKey对应，有利于对HBase表快速检索出瓦片索引数据。
遥感影像在Map阶段完成瓦片重采样和切块任务后，会按照Hcode排序，将相邻的瓦片发送到同一个Reduce节点，瓦片集合在Reducer中按Hcode顺序合并成Block瓦片集，从而实现了按照Hilbert编码曲线存储瓦片影像，能够充分利用Hilbert曲线的空间聚集性，检索时可加快批量瓦片的读取速度。
本发明进行构建静态瓦片金字塔的遥感影像均是经过预处理，符合2000国家大地坐标系的Plate Carree投影的正射影像。在静态瓦片金字塔并行构建时，由于相邻图幅影像的重叠率大，所以需要进行合并处理，以消除重复的瓦片影像，降低数据冗余度。本发明将获取的多幅连续的遥感影像合并生成单个影像金字塔文件，在合并的过程中消除重复的影像数据。本发明基于MapReduce的静态瓦片金字塔并行构建算法主要包括Map和Reduce两个阶段。具体的算法流程是：首先，Client将遥感影像存储在HDFS中，然后Client提交瓦片金字塔构建任务，开始并行构建瓦片金字塔。MapReduce依据任务分配策略，向Mapper节点分配遥感影像瓦片金字塔构建任务，实现基于云的并行处理。在Map阶段，每个分配到任务的Mapper节点从HDFS中读取所分配的遥感影像，采用多线程技术并行处理本地的影像，生成对应图幅影像的瓦片金字塔。生成的每一个瓦片都会在MapReduce框架中进行分组，然后被发送到对应的Reducer节点。在Reduce阶段，Reducer节点在完成瓦片合并后，将瓦片按照Hcode顺序，组织成Block瓦片集文件。再将各个Block瓦片集文件的信息上传至HDFS的NameNode，将Block瓦片集文件中的瓦片索引区抽出，合并生成整个遥感区域的瓦片金字塔索引文件。这样就实现了整个遥感区域的瓦片金字塔大文件ImageFile的并行构建。静态瓦片金字塔的瓦片大小一致，均为256像素×256像素。
经过Map阶段和Reduce阶段的处理，多幅遥感影像完成了瓦片的重采样、切割和镶嵌，最终合并生成了批量遥感影像的单个瓦片金字塔大文件，下面将对这个过程进行详细阐述。
Map阶段的主要功能是重采样遥感影像，并切块生成对应图幅影像的瓦片金字塔。输入的Key为包含遥感影像的地理位置和分辨率信息的M，Value为M对应的遥感影像数据。为实现遥感影像本地计算，首先将遥感影像从HDFS中读取到本地，然后对遥感影像进行处理生成瓦片金字塔。对遥感影像进行重采样，使放大或缩小后的影像与最相邻一级的分辨率相等。设重采样的目标分辨率为，对应级别为，则由遥感影像到目标影像的放大比例为：（为遥感影像的分辨率）。根据放大比例和遥感影像的地理位置及分辨率信息进行影像重采样和切块，Map阶段生成瓦片金字塔算法的步骤如图1所示。
（1）Map瓦片处理阶段：计算由单幅遥感影像生成的瓦片金字塔的各层瓦片行列范围：
根据GTPM模型、遥感影像的空间大小和经纬度范围，确定输出瓦片的层级范围，其中，为表3.2中最接近分辨率的层级，对每个，计算出瓦片金字塔的各层瓦片在GTPM模型中的行列范围，公式如下：
（3.1）
其中，为向下取整；放大或缩小后的层影像像素大小为：
（3.2）
其中，为向上取整，为的像素宽度和高度；
（2）创建层瓦片任务：
对于涉及到层的每个瓦片影像，计算瓦片在层的像素坐标范围为：
（3.3）
在对进行采样生成时，影像数据贡献的像素范围为：
（3.4）
其中，为左上角像素点经纬度在层上的像素坐标；瓦片上的有效像素（不透明像素区域）范围可计算得到为：
（3.5）
其中，为右下角点经纬度在层上的像素坐标；确定了中和的有效像素区域对应的像素区域；构建了瓦片金字塔第层任务；再将第层瓦片作为输入执行上述步骤，即实现第层的瓦片任务构建，此时；如此循环直至生成第一层瓦片，实现瓦片金字塔任务的创建；
（3）瓦片影像的生成：
瓦片底层Lmax的瓦片影像
，其余层级的瓦片依照双线性内插法采样下一层的四个瓦片生成；
（4）Reduce瓦片合并阶段：
Reduce阶段合并相邻图幅影像之间的重复区域；此阶段，对于含有完整瓦片情况，只取其中一个完整瓦片即可；不完整瓦片进行合并时，只需采用图层叠加原理即可实现；这样就完成了遥感影像各层瓦片的镶嵌合并。合并之后将节点下的瓦片合并成瓦片金字塔大文件。
把上述瓦片金字塔大文件的瓦片索引抽出写入到HBase瓦片索引表中，Client通过检索HBase索引表、读取Block中的瓦片影像，可实现海量遥感影像的快速检索。
验证：
本发明的实验是建立在计算机集群上进行的，所以其性能高低决定于集群计算机的硬件和软件配置水平。
5.1.1 硬件环境
实验计算集群包括1个控制节点和7计算节点，两种节点的计算机配置如表5.1所示。实验环境中的网络数据交换机均为千兆交换机。
表5.1 集群计算机配置
5.1.2 软件环境及影像数据
软件环境主要包括节点操作系统、虚拟机、Hadoop平台等方面，具体如5.2表所示。为提高遥感影像元数据查询效率，本发明采用MySQL数据库存储瓦片金字塔大文件的元数据信息。Client使用的开发工具有Microsoft Visual Studio 2008、GDAL等。实验影像数据如表5.3示。
表5.2 软件环境
表5.3 试验环境的影像数据情况
5.2 瓦片金字塔快速构建实验
为验证本发明算法的有效性，本发明对静态瓦片金字塔的构建进行了实验。实验采用某遥感卫星拍摄的2.14米分辨率某地区真彩色影像，影像存储格式为GeoTiff。静态瓦片金字塔构建方法实验分为Map阶段实验和Reduce阶段实验，主要验证基于MapReduce的静态瓦片金字塔并行构建算法的计算效率和资源利用能力。
5.2.1 Map阶段实验
在Map阶段，首先由各个Mapper节点将其对应的遥感影像读取写入到本地磁盘，然后由Mapper节点对其进行本地计算，生成对应图幅的瓦片金字塔。由于本发明的Map阶段是在每个Mapper节点，并行独立地构建瓦片金字塔，因此算法效率会受到单个节点下的计算效率和集群下并行构建效率的制约。为测试本发明算法的有效性，需要进行两个方面的实验，一是单个节点下单幅遥感影像的瓦片金字塔构建实验，二是多节点下多幅遥感影像瓦片金字塔并行构建实验。
（1）单节点单幅遥感影像瓦片金字塔构建
实验遥感影像大小1.18GB，空间尺寸40632像素×33301像素，本发明采用多线程技术构建瓦片金字塔，以此验证本发明基于MapReduce的静态瓦片金字塔构建算法多线程的效率和资源利用能力，实验软硬件环境详见上述软硬件环境。
将遥感影像存储在节点计算机上后，然后启动瓦片金字塔构建程序。首先根据遥感影像空间尺寸和地理信息，计算出瓦片金字塔层的瓦片行列范围。然后采用本发明Map阶段瓦片任务构建算法，建立层的瓦片输出任务，使用多线程并行执行瓦片任务，输出层瓦片。最后，将相同基本单元下层的瓦片合并重采样成上一层瓦片，例如将瓦片“05_10230”、“05_10231”、“05_10232”和“05_10233”按照Hilbert曲线位置合并采样成上一层瓦片“04_1023”。
由于基本单元之间相互独立，所以可采用多线程生成上一层瓦片，如此不断循环生成上一层瓦片，直至完成第一层瓦片时停止。在单个3TB机械磁盘和8块3TB机械磁盘Raid5阵列上，分别采用不同线程个数完成上述实验，记录不同线程数下的耗时情况。
图2为使用3TB机械磁盘分别以单个和8块Raid5阵列作为数据存储器，生成遥感影像瓦片金字塔的耗时情况。从图中可看出，随着运算线程数的增加，耗时均呈现下降趋势，但是采用Raid5磁盘阵列的耗时少于单个磁盘的耗时，这主要是由Raid5阵列的I/O大于单个磁盘造成的。单个磁盘情况下，线程数达到7个时，其耗时39.16秒，之后随着线程数增加，耗时没有显著降低，说明单个磁盘情况下的处理能力已达到最大化，由于单个磁盘的磁盘I/O在7个线程下，已经基本达到饱和，之后维持在120MB/S左右。结合图3单个磁盘和Raid5阵列的CPU利用情况，可知单个磁盘在7个线程时的CPU利用率，由于磁盘I/O限制而达到饱和。再加上线程调度等方面的影响，从而导致在7个线程时，生成瓦片金字塔的耗时已达到稳定。之后随着线程数增加，单个磁盘情况下的耗时总体保持稳定，当线程数超过CPU核数16后，线程之间争夺CPU资源，导致耗时反而增加。
从上述实验分析可得，本发明瓦片金字塔算法可以最大化利用计算机资源，快速构建瓦片金字塔。
（2）多节点下多幅遥感影像并行构建瓦片金字塔
将遥感影像读取写入到对应的Mapper节点后，对5幅遥感影像分别采用不同节点个数，利用本发明的改进算法并行构建瓦片金字塔。每个节点均在Raid5磁盘阵列下，采用16个线程并行构建单幅遥感影像的瓦片金字塔。图4为实验中的集群节点数与构建瓦片金字塔总耗时之间的关系。
由实验结果图可知，当节点数小于遥感影像图幅数时，此时节点平均任务量大于1，总耗时较长。当节点数大于等于影像图幅数时，每幅遥感影像由一个节点生成瓦片金字塔，总耗时小，计算较快。因此，采用集群处理生成瓦片金字塔时，在集群节点数大于要处理的遥感影像图幅数情况下，可使运算时间最短。
5.2.2 Reduce阶段实验
在完成对5幅遥感影像构建各自的瓦片金字塔后，将生成的瓦片发送到Reducer按照Hcode顺序将瓦片影像组织成Block瓦片集文件。实验共生成19块Block瓦片集文件，最后的Block大小为38.4MB，共计1190.4MB。本实验在不同Reducer个数（节点数）下，测试Reduce阶段的耗时与Reducer个数之间的关系。测试结果如图5示Reducer个数为1时的耗时为29分22秒（1762秒）。随着节点数增加，耗时迅速降低，当节点数增至7时，耗时仅为150秒。由实验结果可知，在Reduce阶段通过增加Reducer个数可以大幅降低Reduce阶段耗时。因此，在集群环境下能快速完成Reduce阶段的Block瓦片文件集构建。
瓦片影像快速检索实验
为了验证ImageTable在影像检索中的作用，本发明设计了两个实验分别验证ImageTable的检索功能和检索效率。
实验一：分别使用本发明方法与在Windows环境下使用关系数据库SQL Server 2005直接存储实验的瓦片金字塔影像，实验数据如表5.4所示。对两者分别检索同一个区域影像，检索区域的大小为20个瓦片，检索时均一次性读取该区域影像后再返回。实验结果如图6示，横坐标为系统存储的不同影像金字塔文件数目，纵坐标中，纵坐标数据代表直接检索SQL Server 2005数据库和本发明方法的检索耗时。
表5.4 影像金字塔文件个数与数据量
产生这一实验结果原因主要是：ImageTable保存了各个瓦片索引数据，检索到对应瓦片索引，就可以直接读取HDFS中对应的Block瓦片影像文件。对比方法虽然不需要在HDFS中读取瓦片，但是受制于关系数据库SQL Server影像数据管理能力的限制，所以基于Hadoop管理海量遥感影像的ImageTable具有比关系数据库更高的影像检索效率。
实验二：由于本发明方法在读取跨区域的影像集时，需要重新在ImageTable中检索瓦片，以获取下一个区域影像文件的信息，所以这种跨区域检索可能会影响到影像漫游速度（漫游影像实验时的瓦片影像只读取到内存，不进行显示）。实验二将本发明方法与将瓦片影像直接存储在HBase表中的方法（简称直接存储法）进行对比。实验时对不同数目的瓦片进行漫游，分别记录直接存储法与本方法的单个区域和跨区域漫游效果，结果如图7所示。
从中可以看出，随着漫游瓦片数目增加，采用本发明方法的单个区域漫游耗时最少，跨多个区域漫游居中，直接存储法耗时最多。
通过上述实验管理一定规模的影像数据，进一步验证了本发明基于Hadoop管理海量遥感影像关键技术研究的有效性，展现了利用云计算管理海量遥感影像的潜在能力和优势。
本发明针对海量遥感影像管理面临的检索效率不高、共享能力不强、无法实现一体化管理等问题，采用开源云计算平台Hadoop管理海量遥感影像，并对一些关键技术进行了研究，取得的研究成果有如下几个方面：
1. 对Hadoop平台进行了分析和总结，对HDFS的主要特性、体系结构和主要流程进行了详细分析，对并行计算模型MapReduce的结构模型和运行流程进行了详细的介绍，对HBase数据库的体系结构及数据模型进行了总结。
2. 对符合本文Plate Carree投影格式的遥感影像，本发明提出基于等经纬网格划分的全球剖分瓦片金字塔模型，并利用Hilbert曲线建立了全球瓦片影像Hcode编码。在上述瓦片金字塔模型基础上，改进提出一种适用于MapReduce并行计算的静态瓦片金字塔构建算法。该算法可以充分发挥集群威力，实现快速并行处理批量遥感影像，生成瓦片金字塔大文件。对需要即时打开浏览的遥感影像，本发明改进提出动态瓦片金字塔构建算法，实现遥感影像浏览与瓦片金字塔构建无缝结合。
3. 为快速检索海量瓦片影像，改进并提出一种瓦片金字塔大文件与HBase瓦片索引表相结合的海量瓦片影像管理模型。该模型可实现瓦片影像的快速检索和读取，从而达到遥感影像一体化管理与共享的目的。改进了Hcode计算方法，提出基于查表的Hcode快速计算方法，以及Block瓦片集的并行入库方法，提高了Hcode计算和瓦片入库效率。
机译： 基于增量MapReduce的数据流分布式并行处理系统及方法
机译： 基于分布的基于系统的巨大DEM金字塔砖的并行施工方法
机译： 基于数据依赖度的网络开关并行化数据平面静态分析方法及并行化方法
