基于MapReduce的海量图像检索技术研究

朱莹芳

（江苏信息职业技术学院，江苏 无锡 214000）

基于MapReduce的海量图像检索技术研究

朱莹芳

（江苏信息职业技术学院，江苏 无锡 214000）

随着互联网+技术的应用和普及，图像数据在种类和数量上均呈现明显的上升趋势。如何从海量图像集中检索出所需的图像已成为当下亟待解决的问题之一。文中尝试利用Hadoop云平台，并采用MapReduce分布式计算模型来进行海量数字图像检索，最终建立一个分布式的图像检索系统。实验结果表明，无论在海量图像的存储能力还是检索速度上，这种分布式图像检索方式和集中式的图像检索方式相比，有着更明显的优势。

Hadoop；图像检索；MapReduce；分布式

随着现代信息技术的飞速发展，以图像、视频为代表的复杂数据急剧增加，其中图像信息的快速增长尤为突出。所以，如何实现对这些数据的有效管理，如何从海量数据中快速准确地检索出所需的图像，则成为当下的研究热点。基于文本的图像检索作为一种传统的检索方法，并没有对图像本身的内容加以分析和利用，已不能满足发展需求，基于内容的图像检索应运而生。

1.基于内容的图像检索

基于内容的图像检索（Content-Based Image Retrieval，CBIR），其基本思想是：依据图像所包含的颜色、纹理、形状及对象的空间关系等信息，从中提取出图像特征，再进行特征匹配。

进行CBIR的研究需综合认知心理学、数据库、计算机视觉、人工智能、图像处理、机器学习等各门学科的知识。由于CBIR是建立在对图像内容的理解和计算机视觉理论的基础之上的，因此，对图像内容的描述不像基于文本的图像检索那样依赖于用户的手工标注，而是借助于从图像中提取出来的颜色、纹理、形状等视觉特征；同样，对图像的检索也不仅仅是关键字的匹配，而演变为图像特征的相似度匹配。一般而言，可以将CBIR系统看作是介于信息用户和数据库（多媒体）之间的一种信息服务系统。图1给出了一个典型的CBIR系统的基本框架。CBIR系统主要分为图像库建立子系统和图像查询子系统两部分。首先使用特定的图像特征提取算法提取出图像的颜色、纹理、形状等特征，然后把图像的特征连同图像一起存储到图像库中，这样就建立了基于内容的图像库。图像的查询子系统，其主要功能是负责和用户的交互，以及用户提交的待检索图像和库存图像之间的相似度度量，并按一定的相似度度量准则在图像库中进行特征匹配，最后依据相似度顺序将查询结果返回给用户。

2.Hadoop云平台的相关技术

Hadoop是一个由Apache基金会所开发的分布式系统基础架构，它以分布式文件系统HDFS（Hadoop Distributed Filesystem）和MapReduce（Google MapReduce的开源实现）为核心，从而为用户提供了系统底层细节透明的分布式计算和分布式存储的编程环境。

2.1 Hadoop的体系结构

在系统架构中，首先主从式的主节点可以屏蔽底层的复杂结构，其次文件目录的映射非常方便。正因为这两个突出的优点，使得主从式成为云计算系统中非常典型的系统架构模式。同时，为减少单一主节点的负载，有部分主从式架构在分层方向进行了一些改进。Hadoop从上层架构上看是一种典型的主从式结构，主节点负责对整个系统的工作进行管理，并分发数据；子节点负责数据的存储、作业的运行。HDFS为分布式计算存储提供了底层支持。主从式分布式文件存储HDFS和主从式并行数据处理模型MapReduce构成了Hadoop的基本架构模型。

如图2所示，在Hadoop主从结构中，通常会把HDFS的主节点Name Node和Map Reduce中的作业主控程序Job Tracker都运行在Master节点上，而HDFS的数据节点Data Node和Map Reduce的子程序

Task Tracker则通常运行在同一个slave节点上。通过这样的主从式体系结构，巧妙地实现了“计算向数据的迁移”。这种策略在处理海量数据时，可以有效地减少网络中大规模数据移动所导致的开销，只需将相对较小的计算程序分布到各个slave上就能实现分布式计算，节约了网络带宽，也就显著地提高了整个系统的计算效率。

2.2 分布式文件系统HDFS

HDFS体系架构采用master/slave模型。如图3所示，云平台中的节点被分成两类：Name Node和Data Node，为简化系统架构，HDFS集群中只有一个主节点Name Node，而Data Node可有若干个。其中Name Node充当master的角色，主要负责管理HDFS文件系统，同时接受来自客户端的请求；Data Node则主要用来存储数据文件，HDFS把一个文件分割成一个或多个文件块block，这些block存储在一个或多个Data Node上。其中比较典型的部署是：在一台性能相对较好的计算机上运行Name Node，集群中的其他计算机各运行一个Data Node；但若是运行Name Node的计算机的性能足够好，也可以在该台计算机运行一个或者多个Data Node。另一台计算机上运行的Data Node数量则没有严格限制，只要不突破计算机存储能力的可承受范围即可。

2.3 并行计算框架MapReduce

MapReduce是Google提出的一个软件框架，基于它编写的应用程序能够运行于由上千个普通商业机器组成的集群上，并以一种可靠容错的方式实现大规模数据的并行处理。Hadoop的MapReduce即是Google的MapReduce的开源实现。MapReduce模型受函数式编程语言的启发，其基本思想是：将要完成的任务分成Map（映射）和Reduce（归约）两步。首先，Map程序会将大的数据块切分成多个特定大小的不相关数据块；然后Map程序会在多个Data Node的节点上运行进行分布式计算；最后Reduce程序将各个Map程序的计算结果汇总，即可获得最后的输出文件。MapReduce框架的计算流程如图4所示。

2.4 HBase简介

HBase是bigtable的开源实现，是建立在HDFS之上，具备高性能、高可靠性、列存储、可伸缩、实时读写的数据库系统。HBase介于Nosql和RDBMS之间，能且仅能通过主键（row key）和主键的range来检索数据，只支持单行事务 （可通过hive支持来实现多表join等复杂操作）。HBase主要用来存储非结构化和半结构化的松散数据。与Hadoop一样，HBase主要靠横向扩展，通过不断增加廉价的商用服务器来实现计算和存储能力的增加。

3.基于Hadoop的图像检索系统

3.1 基于MapReduce的图像存储

在图像数据量很大时，若把图像放到HDFS中，对图像的读取将费时较多。如前所述，HBase是一个在HDFS上开发、面向列的分布式数据库，若要实时地随机读/写超大规模数据集，HBase将是一个理想的解决方案，在本文中，把库存图像的各特征以及存储路径存储在HBase中。将图像的ID作为HBase表的主键，将图像和图像特征分别作为表的两个列族；图像列族又分为图像原文件和图像缩略图两列；图像特征列族分为颜色特征列、纹理特征列、形状特征列三列。因在HBase中，在同一时间默认仅有一行数据可被锁住，同时又由于行的写入属于原子操作，故我们设计使每个图像的整体信息存储在每一行，以方便读写。

由于图像的特征提取是密集型计算，耗时较长，因此采用MapReduce分布式计算来完成图像库的特征提取是非常必要的。将特征提取出来后，把相应的图像的ID、存储的物理路径、颜色特征、纹理特征、形状特征等并行写入HBase中。图像的分布式存储架构如图5所示，其具体的执行流程如图6所示。

3.2 基于MapReduce的图像检索

本文中采用了多特征综合度量的算法，融合了图像的颜色、纹理、形状三种特征来进行检索。检索时，依据用户设置的检索方式来控制三种特征在检索中所占的权重，本次权重分配方式如表1所示。

表1 各特征权重分配方式

假设图像库中共有N副图像，那么库中图像可以用In（n∈｛1，2，..，N｝）来表示，其相应的颜色、纹理和形状特征可分别用Cn、Tn和Sn表示。用户上传的待检索图像是I0，其图像的颜色、纹理和形状特征分别用C0、T0和S0表示，三个特征的维数分别是L、M、Q。通过计算I0和In的相似度，可得到示例图像和图像库中某副图像的颜色相似度DCn、纹理相似度DTn以及形状相似度DSn，分别表示为：

本文中，图像及其特征都是存储在HBase中的，

当HBase的数据集非常大的时候，扫描搜索整个表都要花费很长时间。为提高效率，本文使用MapReduce计算模型对图像的检索进行并行计算。图像的并行检索架构如图7所示，具体流程如图8所示。在整个Map Reduce任务中，输入的是HBase中的图像表。整个流程主要分为以下几步：（1）在Map阶段，首先从HDFS的分布式缓存中读取示例图像，提取其特征值，与HBase中的图像进行特征比较和相似度匹配。将〈相似度，图像ID〉键值对作为map的输出。（2）对map输出的所有〈相似度，图像ID〉键值对按相似度进行排序和重新划分，再输入到reducer。（3）在Reduce阶段，收集所有〈相似度，图像ID〉键值对，再对这些键值对按相似度排序，把前N（N是用户设置的检索结果数）个键值对写入到HDFS。（4）最后输出与示例图像相似度最高的图像的ID。

4.系统平台搭建以及测试分析

4.1 图像存储的性能测试

实验中的图像主要来源于网上下载，包括一些动物素材和植物素材，其他部分直接从网页抓取的。图片有大有小，有几K的，也有几M的。共收集了图片20000张左右，大小约5.1G。

实验中，分别测试了在不同的图像数量以及使用不同的节点数的情况下，图像存储的所花费的时间。其中采用了100张、500张、1000张、2000张、5000张、10000张共六个图像数量。在节点数量的选择上，分别在1个、2个、3个节点下进行了测试。实验结果如图9所示。

从图中可见，当图像数量低于100时，节点数对存储耗时的影响很小。不过，在100到500之间的某个数量开始，分布式存储的优势就显现了。

随着图像数量的不断增长，三个节点消耗的存储时间相比两个节点所消耗的时间减少得越来越多，两个节点消耗的时间相比一个节点所消耗的时间也减少得越来越多。此外，当图像数量大于500张后，单个节点所消耗的存储时间呈指数级增长；而两个节点和三个节点的分布式存储所消耗的时间则增长得相对较慢。当图像数量大于2000张后，两个节点和三个节点的分布式存储耗时均呈线性增长。在此情况下，Map任务数已多于三个，某些节点在同一时刻会被分配多个Map任务，而一个节点同一个时刻却仅能执行一个Map任务。由此可见，图像越多，增加存储的节点数量就越能提高图像特征提取和存储的效率；反之，若图像较少，则不应使用过多的节点来进行存储。

4.2 图像检索的性能测试

实验中分别测试了HBase总行数不同和所使用的节点数不同的情况下检索的耗时。首先，HBase总行数分别选择 400、800、2500、4000、5000、6000、18000、20000；其次，在节点数量的选择上，分别在1个、2个、3个节点下进行了测试，实验结果如图10所示。

从图中可见，在HBase的总行数小于6000时，节点数越多，检索消耗的时间反而越长，这说明此种情况下由于数据量相对较小，HBase倾向于把数据集中存放于一个节点上。若HBase没有将数据分布式存储，那么使用多个节点来并行计算反而会增加系统开销，从而延长检索时间，因此就出现了图10中所看到的情况。之后，随着数据量的逐渐增加，HBase会把数据分布存储到各个节点上，这样就可以利用MapReduce的并行计算优势了。由此可见，检索超大规模的图像库，适当地增加节点数量，可显著提高检索效率。

［1］Yixin Chert，James Z.Wang Robert Oovetz.Content-based image retrieval by clustering［C］.International Multimedia Conference Proceedings of the fifth ACM SIGMM International Workshop，November 2003:193-200.

［2］Flickner M，Sawhney H，Niblack W.Query by image and video content:The QBIC system［C］.IEEE Computer，1995，28（9）:23-32.

［3］Pentland A.，Rosalind W.，Stanley S.，1996.Photobook:content-based manipulation of image databases.International Journal of Computer Vision，18（3）:233-254.

［4］孙君顶.基于内容的图像检索技术研究［D］.西安电子科技大学，2005.4.

［5］张良将.基于Hadoop云平台的海量数字图像数据挖掘的研究［D］.上海交通大学，2013.1.

［6］杨志文.云计算技术指南：应用、平台与架构［M］.北京：化学工业出版社，2010，10.

［7］Fay Chang，Jeffrey Dean，et al.Bigtable:A Distributed Storage System for Structured Data［C］.7th OSDI，2006，276-290.

TP391.41

B

1671-5136（2016）01-0121-03

2016-03-16

朱莹芳，江苏信息职业技术学院物联网工程学院教师。