基于MapReduce的海量圖像檢索技術(shù)研究

朱瑩芳

（江蘇信息職業(yè)技術(shù)學(xué)院，江蘇 無錫 214000）

基于MapReduce的海量圖像檢索技術(shù)研究

朱瑩芳

（江蘇信息職業(yè)技術(shù)學(xué)院，江蘇 無錫 214000）

隨著互聯(lián)網(wǎng)+技術(shù)的應(yīng)用和普及，圖像數(shù)據(jù)在種類和數(shù)量上均呈現(xiàn)明顯的上升趨勢(shì)。如何從海量圖像集中檢索出所需的圖像已成為當(dāng)下亟待解決的問題之一。文中嘗試?yán)肏adoop云平臺(tái)，并采用MapReduce分布式計(jì)算模型來進(jìn)行海量數(shù)字圖像檢索，最終建立一個(gè)分布式的圖像檢索系統(tǒng)。實(shí)驗(yàn)結(jié)果表明，無論在海量圖像的存儲(chǔ)能力還是檢索速度上，這種分布式圖像檢索方式和集中式的圖像檢索方式相比，有著更明顯的優(yōu)勢(shì)。

Hadoop；圖像檢索；MapReduce；分布式

隨著現(xiàn)代信息技術(shù)的飛速發(fā)展，以圖像、視頻為代表的復(fù)雜數(shù)據(jù)急劇增加，其中圖像信息的快速增長尤為突出。所以，如何實(shí)現(xiàn)對(duì)這些數(shù)據(jù)的有效管理，如何從海量數(shù)據(jù)中快速準(zhǔn)確地檢索出所需的圖像，則成為當(dāng)下的研究熱點(diǎn)?；谖谋镜膱D像檢索作為一種傳統(tǒng)的檢索方法，并沒有對(duì)圖像本身的內(nèi)容加以分析和利用，已不能滿足發(fā)展需求，基于內(nèi)容的圖像檢索應(yīng)運(yùn)而生。

1.基于內(nèi)容的圖像檢索

基于內(nèi)容的圖像檢索（Content-Based Image Retrieval，CBIR），其基本思想是：依據(jù)圖像所包含的顏色、紋理、形狀及對(duì)象的空間關(guān)系等信息，從中提取出圖像特征，再進(jìn)行特征匹配。

進(jìn)行CBIR的研究需綜合認(rèn)知心理學(xué)、數(shù)據(jù)庫、計(jì)算機(jī)視覺、人工智能、圖像處理、機(jī)器學(xué)習(xí)等各門學(xué)科的知識(shí)。由于CBIR是建立在對(duì)圖像內(nèi)容的理解和計(jì)算機(jī)視覺理論的基礎(chǔ)之上的，因此，對(duì)圖像內(nèi)容的描述不像基于文本的圖像檢索那樣依賴于用戶的手工標(biāo)注，而是借助于從圖像中提取出來的顏色、紋理、形狀等視覺特征；同樣，對(duì)圖像的檢索也不僅僅是關(guān)鍵字的匹配，而演變?yōu)閳D像特征的相似度匹配。一般而言，可以將CBIR系統(tǒng)看作是介于信息用戶和數(shù)據(jù)庫（多媒體）之間的一種信息服務(wù)系統(tǒng)。圖1給出了一個(gè)典型的CBIR系統(tǒng)的基本框架。CBIR系統(tǒng)主要分為圖像庫建立子系統(tǒng)和圖像查詢子系統(tǒng)兩部分。首先使用特定的圖像特征提取算法提取出圖像的顏色、紋理、形狀等特征，然后把圖像的特征連同圖像一起存儲(chǔ)到圖像庫中，這樣就建立了基于內(nèi)容的圖像庫。圖像的查詢子系統(tǒng)，其主要功能是負(fù)責(zé)和用戶的交互，以及用戶提交的待檢索圖像和庫存圖像之間的相似度度量，并按一定的相似度度量準(zhǔn)則在圖像庫中進(jìn)行特征匹配，最后依據(jù)相似度順序?qū)⒉樵兘Y(jié)果返回給用戶。

2.Hadoop云平臺(tái)的相關(guān)技術(shù)

Hadoop是一個(gè)由Apache基金會(huì)所開發(fā)的分布式系統(tǒng)基礎(chǔ)架構(gòu)，它以分布式文件系統(tǒng)HDFS（Hadoop Distributed Filesystem）和MapReduce（Google MapReduce的開源實(shí)現(xiàn)）為核心，從而為用戶提供了系統(tǒng)底層細(xì)節(jié)透明的分布式計(jì)算和分布式存儲(chǔ)的編程環(huán)境。

2.1 Hadoop的體系結(jié)構(gòu)

在系統(tǒng)架構(gòu)中，首先主從式的主節(jié)點(diǎn)可以屏蔽底層的復(fù)雜結(jié)構(gòu)，其次文件目錄的映射非常方便。正因?yàn)檫@兩個(gè)突出的優(yōu)點(diǎn)，使得主從式成為云計(jì)算系統(tǒng)中非常典型的系統(tǒng)架構(gòu)模式。同時(shí)，為減少單一主節(jié)點(diǎn)的負(fù)載，有部分主從式架構(gòu)在分層方向進(jìn)行了一些改進(jìn)。Hadoop從上層架構(gòu)上看是一種典型的主從式結(jié)構(gòu)，主節(jié)點(diǎn)負(fù)責(zé)對(duì)整個(gè)系統(tǒng)的工作進(jìn)行管理，并分發(fā)數(shù)據(jù)；子節(jié)點(diǎn)負(fù)責(zé)數(shù)據(jù)的存儲(chǔ)、作業(yè)的運(yùn)行。HDFS為分布式計(jì)算存儲(chǔ)提供了底層支持。主從式分布式文件存儲(chǔ)HDFS和主從式并行數(shù)據(jù)處理模型MapReduce構(gòu)成了Hadoop的基本架構(gòu)模型。

如圖2所示，在Hadoop主從結(jié)構(gòu)中，通常會(huì)把HDFS的主節(jié)點(diǎn)Name Node和Map Reduce中的作業(yè)主控程序Job Tracker都運(yùn)行在Master節(jié)點(diǎn)上，而HDFS的數(shù)據(jù)節(jié)點(diǎn)Data Node和Map Reduce的子程序

Task Tracker則通常運(yùn)行在同一個(gè)slave節(jié)點(diǎn)上。通過這樣的主從式體系結(jié)構(gòu)，巧妙地實(shí)現(xiàn)了“計(jì)算向數(shù)據(jù)的遷移”。這種策略在處理海量數(shù)據(jù)時(shí)，可以有效地減少網(wǎng)絡(luò)中大規(guī)模數(shù)據(jù)移動(dòng)所導(dǎo)致的開銷，只需將相對(duì)較小的計(jì)算程序分布到各個(gè)slave上就能實(shí)現(xiàn)分布式計(jì)算，節(jié)約了網(wǎng)絡(luò)帶寬，也就顯著地提高了整個(gè)系統(tǒng)的計(jì)算效率。

2.2 分布式文件系統(tǒng)HDFS

HDFS體系架構(gòu)采用master/slave模型。如圖3所示，云平臺(tái)中的節(jié)點(diǎn)被分成兩類：Name Node和Data Node，為簡化系統(tǒng)架構(gòu)，HDFS集群中只有一個(gè)主節(jié)點(diǎn)Name Node，而Data Node可有若干個(gè)。其中Name Node充當(dāng)master的角色，主要負(fù)責(zé)管理HDFS文件系統(tǒng)，同時(shí)接受來自客戶端的請(qǐng)求；Data Node則主要用來存儲(chǔ)數(shù)據(jù)文件，HDFS把一個(gè)文件分割成一個(gè)或多個(gè)文件塊block，這些block存儲(chǔ)在一個(gè)或多個(gè)Data Node上。其中比較典型的部署是：在一臺(tái)性能相對(duì)較好的計(jì)算機(jī)上運(yùn)行Name Node，集群中的其他計(jì)算機(jī)各運(yùn)行一個(gè)Data Node；但若是運(yùn)行Name Node的計(jì)算機(jī)的性能足夠好，也可以在該臺(tái)計(jì)算機(jī)運(yùn)行一個(gè)或者多個(gè)Data Node。另一臺(tái)計(jì)算機(jī)上運(yùn)行的Data Node數(shù)量則沒有嚴(yán)格限制，只要不突破計(jì)算機(jī)存儲(chǔ)能力的可承受范圍即可。

2.3 并行計(jì)算框架MapReduce

MapReduce是Google提出的一個(gè)軟件框架，基于它編寫的應(yīng)用程序能夠運(yùn)行于由上千個(gè)普通商業(yè)機(jī)器組成的集群上，并以一種可靠容錯(cuò)的方式實(shí)現(xiàn)大規(guī)模數(shù)據(jù)的并行處理。Hadoop的MapReduce即是Google的MapReduce的開源實(shí)現(xiàn)。MapReduce模型受函數(shù)式編程語言的啟發(fā)，其基本思想是：將要完成的任務(wù)分成Map（映射）和Reduce（歸約）兩步。首先，Map程序會(huì)將大的數(shù)據(jù)塊切分成多個(gè)特定大小的不相關(guān)數(shù)據(jù)塊；然后Map程序會(huì)在多個(gè)Data Node的節(jié)點(diǎn)上運(yùn)行進(jìn)行分布式計(jì)算；最后Reduce程序?qū)⒏鱾€(gè)Map程序的計(jì)算結(jié)果匯總，即可獲得最后的輸出文件。MapReduce框架的計(jì)算流程如圖4所示。

2.4 HBase簡介

HBase是bigtable的開源實(shí)現(xiàn)，是建立在HDFS之上，具備高性能、高可靠性、列存儲(chǔ)、可伸縮、實(shí)時(shí)讀寫的數(shù)據(jù)庫系統(tǒng)。HBase介于Nosql和RDBMS之間，能且僅能通過主鍵（row key）和主鍵的range來檢索數(shù)據(jù)，只支持單行事務(wù) （可通過hive支持來實(shí)現(xiàn)多表join等復(fù)雜操作）。HBase主要用來存儲(chǔ)非結(jié)構(gòu)化和半結(jié)構(gòu)化的松散數(shù)據(jù)。與Hadoop一樣，HBase主要靠橫向擴(kuò)展，通過不斷增加廉價(jià)的商用服務(wù)器來實(shí)現(xiàn)計(jì)算和存儲(chǔ)能力的增加。

3.基于Hadoop的圖像檢索系統(tǒng)

3.1 基于MapReduce的圖像存儲(chǔ)

在圖像數(shù)據(jù)量很大時(shí)，若把圖像放到HDFS中，對(duì)圖像的讀取將費(fèi)時(shí)較多。如前所述，HBase是一個(gè)在HDFS上開發(fā)、面向列的分布式數(shù)據(jù)庫，若要實(shí)時(shí)地隨機(jī)讀/寫超大規(guī)模數(shù)據(jù)集，HBase將是一個(gè)理想的解決方案，在本文中，把庫存圖像的各特征以及存儲(chǔ)路徑存儲(chǔ)在HBase中。將圖像的ID作為HBase表的主鍵，將圖像和圖像特征分別作為表的兩個(gè)列族；圖像列族又分為圖像原文件和圖像縮略圖兩列；圖像特征列族分為顏色特征列、紋理特征列、形狀特征列三列。因在HBase中，在同一時(shí)間默認(rèn)僅有一行數(shù)據(jù)可被鎖住，同時(shí)又由于行的寫入屬于原子操作，故我們?cè)O(shè)計(jì)使每個(gè)圖像的整體信息存儲(chǔ)在每一行，以方便讀寫。

由于圖像的特征提取是密集型計(jì)算，耗時(shí)較長，因此采用MapReduce分布式計(jì)算來完成圖像庫的特征提取是非常必要的。將特征提取出來后，把相應(yīng)的圖像的ID、存儲(chǔ)的物理路徑、顏色特征、紋理特征、形狀特征等并行寫入HBase中。圖像的分布式存儲(chǔ)架構(gòu)如圖5所示，其具體的執(zhí)行流程如圖6所示。

3.2 基于MapReduce的圖像檢索

本文中采用了多特征綜合度量的算法，融合了圖像的顏色、紋理、形狀三種特征來進(jìn)行檢索。檢索時(shí)，依據(jù)用戶設(shè)置的檢索方式來控制三種特征在檢索中所占的權(quán)重，本次權(quán)重分配方式如表1所示。

表1 各特征權(quán)重分配方式

假設(shè)圖像庫中共有N副圖像，那么庫中圖像可以用In（n∈｛1，2，..，N｝）來表示，其相應(yīng)的顏色、紋理和形狀特征可分別用Cn、Tn和Sn表示。用戶上傳的待檢索圖像是I0，其圖像的顏色、紋理和形狀特征分別用C0、T0和S0表示，三個(gè)特征的維數(shù)分別是L、M、Q。通過計(jì)算I0和In的相似度，可得到示例圖像和圖像庫中某副圖像的顏色相似度DCn、紋理相似度DTn以及形狀相似度DSn，分別表示為：

本文中，圖像及其特征都是存儲(chǔ)在HBase中的，

當(dāng)HBase的數(shù)據(jù)集非常大的時(shí)候，掃描搜索整個(gè)表都要花費(fèi)很長時(shí)間。為提高效率，本文使用MapReduce計(jì)算模型對(duì)圖像的檢索進(jìn)行并行計(jì)算。圖像的并行檢索架構(gòu)如圖7所示，具體流程如圖8所示。在整個(gè)Map Reduce任務(wù)中，輸入的是HBase中的圖像表。整個(gè)流程主要分為以下幾步：（1）在Map階段，首先從HDFS的分布式緩存中讀取示例圖像，提取其特征值，與HBase中的圖像進(jìn)行特征比較和相似度匹配。將〈相似度，圖像ID〉鍵值對(duì)作為map的輸出。（2）對(duì)map輸出的所有〈相似度，圖像ID〉鍵值對(duì)按相似度進(jìn)行排序和重新劃分，再輸入到reducer。（3）在Reduce階段，收集所有〈相似度，圖像ID〉鍵值對(duì)，再對(duì)這些鍵值對(duì)按相似度排序，把前N（N是用戶設(shè)置的檢索結(jié)果數(shù)）個(gè)鍵值對(duì)寫入到HDFS。（4）最后輸出與示例圖像相似度最高的圖像的ID。

4.系統(tǒng)平臺(tái)搭建以及測試分析

4.1 圖像存儲(chǔ)的性能測試

實(shí)驗(yàn)中的圖像主要來源于網(wǎng)上下載，包括一些動(dòng)物素材和植物素材，其他部分直接從網(wǎng)頁抓取的。圖片有大有小，有幾K的，也有幾M的。共收集了圖片20000張左右，大小約5.1G。

實(shí)驗(yàn)中，分別測試了在不同的圖像數(shù)量以及使用不同的節(jié)點(diǎn)數(shù)的情況下，圖像存儲(chǔ)的所花費(fèi)的時(shí)間。其中采用了100張、500張、1000張、2000張、5000張、10000張共六個(gè)圖像數(shù)量。在節(jié)點(diǎn)數(shù)量的選擇上，分別在1個(gè)、2個(gè)、3個(gè)節(jié)點(diǎn)下進(jìn)行了測試。實(shí)驗(yàn)結(jié)果如圖9所示。

從圖中可見，當(dāng)圖像數(shù)量低于100時(shí)，節(jié)點(diǎn)數(shù)對(duì)存儲(chǔ)耗時(shí)的影響很小。不過，在100到500之間的某個(gè)數(shù)量開始，分布式存儲(chǔ)的優(yōu)勢(shì)就顯現(xiàn)了。

隨著圖像數(shù)量的不斷增長，三個(gè)節(jié)點(diǎn)消耗的存儲(chǔ)時(shí)間相比兩個(gè)節(jié)點(diǎn)所消耗的時(shí)間減少得越來越多，兩個(gè)節(jié)點(diǎn)消耗的時(shí)間相比一個(gè)節(jié)點(diǎn)所消耗的時(shí)間也減少得越來越多。此外，當(dāng)圖像數(shù)量大于500張后，單個(gè)節(jié)點(diǎn)所消耗的存儲(chǔ)時(shí)間呈指數(shù)級(jí)增長；而兩個(gè)節(jié)點(diǎn)和三個(gè)節(jié)點(diǎn)的分布式存儲(chǔ)所消耗的時(shí)間則增長得相對(duì)較慢。當(dāng)圖像數(shù)量大于2000張后，兩個(gè)節(jié)點(diǎn)和三個(gè)節(jié)點(diǎn)的分布式存儲(chǔ)耗時(shí)均呈線性增長。在此情況下，Map任務(wù)數(shù)已多于三個(gè)，某些節(jié)點(diǎn)在同一時(shí)刻會(huì)被分配多個(gè)Map任務(wù)，而一個(gè)節(jié)點(diǎn)同一個(gè)時(shí)刻卻僅能執(zhí)行一個(gè)Map任務(wù)。由此可見，圖像越多，增加存儲(chǔ)的節(jié)點(diǎn)數(shù)量就越能提高圖像特征提取和存儲(chǔ)的效率；反之，若圖像較少，則不應(yīng)使用過多的節(jié)點(diǎn)來進(jìn)行存儲(chǔ)。

4.2 圖像檢索的性能測試

實(shí)驗(yàn)中分別測試了HBase總行數(shù)不同和所使用的節(jié)點(diǎn)數(shù)不同的情況下檢索的耗時(shí)。首先，HBase總行數(shù)分別選擇 400、800、2500、4000、5000、6000、18000、20000；其次，在節(jié)點(diǎn)數(shù)量的選擇上，分別在1個(gè)、2個(gè)、3個(gè)節(jié)點(diǎn)下進(jìn)行了測試，實(shí)驗(yàn)結(jié)果如圖10所示。

從圖中可見，在HBase的總行數(shù)小于6000時(shí)，節(jié)點(diǎn)數(shù)越多，檢索消耗的時(shí)間反而越長，這說明此種情況下由于數(shù)據(jù)量相對(duì)較小，HBase傾向于把數(shù)據(jù)集中存放于一個(gè)節(jié)點(diǎn)上。若HBase沒有將數(shù)據(jù)分布式存儲(chǔ)，那么使用多個(gè)節(jié)點(diǎn)來并行計(jì)算反而會(huì)增加系統(tǒng)開銷，從而延長檢索時(shí)間，因此就出現(xiàn)了圖10中所看到的情況。之后，隨著數(shù)據(jù)量的逐漸增加，HBase會(huì)把數(shù)據(jù)分布存儲(chǔ)到各個(gè)節(jié)點(diǎn)上，這樣就可以利用MapReduce的并行計(jì)算優(yōu)勢(shì)了。由此可見，檢索超大規(guī)模的圖像庫，適當(dāng)?shù)卦黾庸?jié)點(diǎn)數(shù)量，可顯著提高檢索效率。

［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］孫君頂.基于內(nèi)容的圖像檢索技術(shù)研究［D］.西安電子科技大學(xué)，2005.4.

［5］張良將.基于Hadoop云平臺(tái)的海量數(shù)字圖像數(shù)據(jù)挖掘的研究［D］.上海交通大學(xué)，2013.1.

［6］楊志文.云計(jì)算技術(shù)指南：應(yīng)用、平臺(tái)與架構(gòu)［M］.北京：化學(xué)工業(yè)出版社，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

朱瑩芳，江蘇信息職業(yè)技術(shù)學(xué)院物聯(lián)網(wǎng)工程學(xué)院教師。