基于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

朱瑩芳，江蘇信息職業技術學院物聯網工程學院教師。