張睿萍, 馬宗梅

(中原工學(xué)院 計(jì)算機(jī)系, 鄭州 450007)

在圖像自動組織管理系統(tǒng)中, 圖像分類是一項(xiàng)關(guān)鍵技術(shù)[1-3]. 圖像分類的基本思想： 先用計(jì)算機(jī)根據(jù)圖像內(nèi)容對圖像信息進(jìn)行理解, 然后將圖像分為不同的類別, 幫助用戶更快地找到所需的圖像[4-5]. 圖像分類主要分為兩種類型： 基于場景識別的圖像分類和基于目標(biāo)識別的圖像分類. 基于場景識別的圖像分類方法根據(jù)圖像語義內(nèi)容將圖像劃分為多個(gè)類別; 基于目標(biāo)識別的圖像分類方法是對一幅圖像中的不同目標(biāo)進(jìn)行識別, 包括前景和背景區(qū), 前景即為目標(biāo). 目前圖像分類主要針對于場景識別, 因此本文主要考慮基于場景識別的圖像分類方法[6-7]. 最初的圖像分類主要依賴文本特征, 即圖像分類的關(guān)鍵字, 然后采用人工方式根據(jù)關(guān)鍵字對圖像進(jìn)行標(biāo)注和識別, 由于每個(gè)人對圖像的理解不同, 因此對同一對象, 不同人得到圖像的分類結(jié)果差別較大, 并且隨著圖像規(guī)模越來越大, 人工標(biāo)注方式工作量大, 圖像的分類效率低, 已經(jīng)不能滿足圖像處理的要求[8]. 基于內(nèi)容的圖像分類方法不需進(jìn)行人工標(biāo)注, 克服了人工標(biāo)注圖像分類方法的主觀和盲目性, 直接根據(jù)圖像信息進(jìn)行圖像分類, 該圖像信息主要指圖像的特征, 如顏色、 形狀、 灰度特征、 仿射特征等, 通過這些特征對圖像內(nèi)容進(jìn)行描述, 并根據(jù)圖像特征和圖像類別之間的關(guān)聯(lián), 采用機(jī)器學(xué)習(xí)算法建立圖像分類器[9-10]. 傳統(tǒng)基于內(nèi)容的圖像分類方法主要采用全局特征和機(jī)器學(xué)習(xí)算法進(jìn)行圖像分類, 如小波變換提取圖像空間域特征, 將其作為神經(jīng)網(wǎng)絡(luò)的輸入向量, 建立圖像的分類器, 由于全局特征對光照變化、 遮擋等敏感, 魯棒性差, 因此對一些復(fù)雜的圖像, 難以得到理想的圖像分類結(jié)果[11-12]. 全局特征還存在特征維數(shù)高的缺陷, 易出現(xiàn)“過擬合”的圖像分類結(jié)果, 使圖像分類錯(cuò)誤率較高. 為了克服全局特征的缺陷, 文獻(xiàn)[13]提出了基于局部特征的圖像分類方法, 相對于全局特征, 局部特征可更好地刻畫特征的細(xì)節(jié)信息, 局部特征對光照變化、 遮擋等圖像具有較強(qiáng)的魯棒性, 已成為當(dāng)前圖像分類中的主要研究方向. 由于圖像處理技術(shù)的不斷成熟, 圖像數(shù)量不斷呈指數(shù)形式增長, 傳統(tǒng)單機(jī)圖像分類模式已無法滿足圖像分類的實(shí)時(shí)性要求, 因此如何對大數(shù)據(jù)圖像進(jìn)行快速、 準(zhǔn)確地分類面臨巨大的挑戰(zhàn)[14].

云計(jì)算是一種新興的數(shù)據(jù)處理模式, 具有分布式和并行處理能力, 可將分散、 大量不同地點(diǎn)的硬件和軟件資源組織在一起, 形成一個(gè)龐大的資源池, 用戶通過申請服務(wù)方式利用資源池中的資源, 加快任務(wù)完成的速度. 為了解決大數(shù)據(jù)圖像分類耗時(shí)長、 實(shí)時(shí)性差等問題, 本文提出一種基于Hadoop平臺的大數(shù)據(jù)圖像分類機(jī)制. 首先提取圖像分類的有效特征, 然后采用Map函數(shù)和Reduce函數(shù)得到圖像分類結(jié)果, 最后仿真模擬測試本文分類機(jī)制的優(yōu)越性.

1 Hadoop平臺

圖1 Hadoop平臺的基本架構(gòu)Fig.1 Basic architecture of Hadoop platform

Hadoop平臺是云計(jì)算中的一種分布式處理系統(tǒng), 具有強(qiáng)大的容錯(cuò)能力和計(jì)算能力, 易擴(kuò)展, 對數(shù)據(jù)的處理和分析結(jié)果可靠, 適合于大數(shù)據(jù)的開發(fā)和處理. Hadoop平臺的基本架構(gòu)如圖1所示, 主要包括核心組件、 分布式文件系統(tǒng)、 Map/Reduce編程模型、 文件存儲數(shù)據(jù)庫等. 核心組件主要用于對文件的遠(yuǎn)程處理和調(diào)度, 分布式文件系統(tǒng)簡稱為HDFS, 主要負(fù)責(zé)對數(shù)據(jù)的讀取和寫入, 包括名稱節(jié)點(diǎn)(Name Node)、 數(shù)據(jù)節(jié)點(diǎn)(Data Node)、 客戶(Client), 其中名稱節(jié)點(diǎn)的任務(wù)主要包括存儲和管理文件信息； 對文件系統(tǒng)目錄之間的映射關(guān)系進(jìn)行維護(hù)； 對用戶任務(wù)進(jìn)行分析, 并為其分配相應(yīng)的數(shù)據(jù)節(jié)點(diǎn)； 對文件任務(wù)進(jìn)行管理和控制, 一個(gè)分布式文件系統(tǒng)只有一個(gè)名稱節(jié)點(diǎn). 數(shù)據(jù)節(jié)點(diǎn)屬于工作節(jié)點(diǎn), 一個(gè)分布式文件系統(tǒng)有多個(gè)數(shù)據(jù)節(jié)點(diǎn), 主要完成名稱節(jié)點(diǎn)和任務(wù)之間的通信, 根據(jù)通信協(xié)議和客戶端進(jìn)行通信. 客戶的功能是分布式文件系統(tǒng)和用戶之間的關(guān)聯(lián), 當(dāng)用戶要進(jìn)行數(shù)據(jù)讀取操作時(shí), 則為該用戶建立一個(gè)數(shù)據(jù)傳輸?shù)耐ǖ? Map/Reduce是進(jìn)行大數(shù)據(jù)處理的模塊, 文件存儲數(shù)據(jù)庫主要用于處理規(guī)模數(shù)據(jù), 容錯(cuò)能力強(qiáng), 可靠性高, 主要包括Job Tracker負(fù)責(zé)為任務(wù)服務(wù)器分配相應(yīng)任務(wù), 并劃分相應(yīng)的計(jì)算資源； Task Tracker負(fù)責(zé)任務(wù)的執(zhí)行； Job負(fù)責(zé)上傳用戶提供的任務(wù)； Task為最小的任務(wù)單元； Speculative_Task主要負(fù)責(zé)備份任務(wù).

Map/Reduce編程模型的工作原理如圖2所示, 步驟如下：

1) 將文件傳輸給Map/Reduce模型, 根據(jù)節(jié)點(diǎn)數(shù)、 文件大小及用戶要求, 將文件劃分成多個(gè)數(shù)據(jù)片(Split), 每個(gè)數(shù)據(jù)片與一個(gè)Map對應(yīng), Map數(shù)據(jù)不能太大, 因此數(shù)據(jù)片的合理設(shè)置十分重要；

2) 根據(jù)key/value的格式, Map對數(shù)據(jù)進(jìn)行讀入, 并將數(shù)據(jù)存儲在本地節(jié)點(diǎn)上, 采用編寫的代碼對任務(wù)進(jìn)行執(zhí)行操作;

3) 對Map的輸出數(shù)據(jù)進(jìn)行排序、 復(fù)制、 合并等操作, 實(shí)現(xiàn)數(shù)據(jù)的初步整合, 可對數(shù)據(jù)進(jìn)行壓縮和簡化, 節(jié)約數(shù)據(jù)的存儲空間;

4) 將初步整合的結(jié)果發(fā)送給Reduce( )函數(shù)進(jìn)行處理, 對數(shù)據(jù)進(jìn)行再一次合并;

5) 將Reduce( )函數(shù)處理結(jié)果發(fā)送到分布式文件系統(tǒng)中.

圖2 Map/Reduce編程模型的工作原理Fig.2 Working principle of Map/Reduce programming model

2 Hadoop平臺的大數(shù)據(jù)圖像分類機(jī)制設(shè)計(jì)

2.1 圖像的預(yù)處理

由于受光照、 設(shè)備、 外界環(huán)境等因素的干擾, 采集的圖像會產(chǎn)生一定失真, 因此需對原始圖像進(jìn)行預(yù)處理, 以提高圖像分類的效果. 首先, 用平滑卷積濾波器對原始圖像進(jìn)行去噪處理, 消除圖像中的噪聲, 計(jì)算公式為

(1)

其中：f(x,y)表示原始圖像的像素點(diǎn);h( )表示平滑卷積濾波器;k,j表示濾波的尺度和大小;m×n表示圖像的總像素. 其次, 采用如下仿射變換對平滑卷積濾波器的圖像進(jìn)行校正:

(2)

其中aij表示變換系數(shù). 然后用最小二乘(LS)算法對圖像輸入和輸出點(diǎn)之間的映射關(guān)系進(jìn)行擬合：

(3)

最后根據(jù)如下仿射變換參數(shù)的求解公式進(jìn)行去噪后圖像校正：

2.2 提取圖像特征

尺度不變特征轉(zhuǎn)換(SIFT)算法是一種尺度空間變換處理算法, 可對圖像的位置、 尺度和旋轉(zhuǎn)等局部特征進(jìn)行提取, 因此本文選擇SIFT算法提取圖像分類的特征, 步驟如下：

1) 對圖像進(jìn)行尺度變換, 產(chǎn)生不同尺度的空間序列, 對一幅圖像f(x,y), 采用高斯卷積核函數(shù)G(x,y,σ)進(jìn)行卷積操作, 得到尺度空間為

L(x,y,σ)=G(x,y,σ)*f(x,y),

(6)

其中: *表示卷積;G(x,y,σ)定義為

(7)

式中σ表示尺度空間因子. 對高斯卷積操作后的圖像進(jìn)行降采樣操作, 可得到圖像的金字塔分層結(jié)構(gòu)：

D(x,y,σ)=(G(x,y,kσ)-G(x,y,σ))*f(x,y)=L(x,y,kσ)-L(x,y,σ).

(8)

從圖像金字塔分層結(jié)構(gòu)中提取圖像的候選特征點(diǎn), 通過對三維二次函數(shù)進(jìn)行擬合, 估計(jì)關(guān)鍵點(diǎn)的位置和尺度, 可去掉部分無用特征點(diǎn), 即

(9)

圖像的候選特征點(diǎn)檢測結(jié)果如圖3所示. 根據(jù)特征點(diǎn)的鄰域像素梯度分布為其分配一個(gè)方向, 則特征點(diǎn)的梯度大小和方向分別為

(10)

(11)

根據(jù)梯度方向直方圖得到主梯度方向如圖4所示. 每個(gè)特征點(diǎn)的位置、 尺度和方向均可確定, 從而完成了圖像關(guān)鍵特征點(diǎn)的檢測.

圖3 空間特征點(diǎn)的檢測Fig.3 Detection of spatial feature points

圖4 主梯度方向Fig.4 Direction of main gradient

2) 將坐標(biāo)軸旋轉(zhuǎn)作為關(guān)鍵點(diǎn)的方向, 每個(gè)特征點(diǎn)能產(chǎn)生128維的特征向量, 該特征向量對光照變化、 尺度變化、 幾何旋轉(zhuǎn)具有較強(qiáng)的魯棒性. 由于每個(gè)特征向量為128維, 圖像特征點(diǎn)較多時(shí), 特征存儲空間較大, 對圖像分類實(shí)時(shí)性產(chǎn)生不利影響, 因此采用主成分分析算法對特征進(jìn)行融合和處理.

2.3 圖像分類器的構(gòu)建

支持向量機(jī)的基本思想是找到一個(gè)可將兩類樣本分開的分類線, 對一個(gè)高維空間, 最優(yōu)分類線即為最優(yōu)分類面. 設(shè)樣本集為(xi,yi),i=1,2,…,n,x∈d, y∈{+1,-1}表示分類標(biāo)簽, 則最優(yōu)分類面為

wT·x+b=0.

(12)

使兩種樣本分類間隔最大的分類面為

yi(wT·xi+b)≥1, i=1,2,…,n.

(13)

將式(11)作為分類的約束條件, 對

(14)

的極小值進(jìn)行求解. 當(dāng)樣本為線性不可分時(shí), 在式(11)的分類約束條件中引入松馳項(xiàng)ξi≥0, 則有

yi(wT·xi+b)≥1-ξi.

(15)

在支持向量機(jī)的分類過程中, 很難發(fā)現(xiàn)樣本錯(cuò)分現(xiàn)象, 因此引入錯(cuò)誤懲罰因子C, 將式(15)變?yōu)?/p>

(16)

引入Lagrange乘子ai得到式(16)的對偶形式為

(18)

其中K(xi·x)表示核函數(shù). 根據(jù)式(18)建立圖像的分類器, 對待分類的圖像進(jìn)行識別和分類.

2.4 Hadoop平臺的大數(shù)據(jù)圖像分類步驟

1) Client向Hadoop平臺的Job Tracker提交一個(gè)圖像分類任務(wù), Job Tracker將圖像特征數(shù)據(jù)復(fù)制到本地的分布式文件處理系統(tǒng)中;

2) 對圖像分類的任務(wù)進(jìn)行初始化, 將任務(wù)放入任務(wù)隊(duì)列中, Job Tracker根據(jù)不同節(jié)點(diǎn)的處理能力將任務(wù)分配到相應(yīng)的節(jié)點(diǎn)上, 即Task Tracker上;

圖5 基于Hadoop平臺的大數(shù)據(jù)圖像分類流程Fig.5 Flow chart of large data image classification based on Hadoop platform

3) 各Task Tracker根據(jù)分配的任務(wù), 采用支持向量機(jī)擬合待分類圖像特征與圖像特征庫之間的關(guān)系, 得到圖像相應(yīng)的類別;

4) 將圖像相應(yīng)的類別作為key/value, 保存到本地文件磁盤中;

5) 如果圖像分類中間結(jié)果的key/value相同, 則對其進(jìn)行合并, 將合并的結(jié)果交給Reduce進(jìn)行處理, 得到圖像分類的結(jié)果, 并將結(jié)果寫入到分布式文件處理系統(tǒng)中；

6) Job Tracker將任務(wù)狀態(tài)進(jìn)行清空處理, 用戶從分布式文件處理系統(tǒng)中得到圖像分類的結(jié)果.

基于Hadoop平臺的大數(shù)據(jù)圖像分類流程如圖5所示.

3 圖像分類的實(shí)驗(yàn)結(jié)果與分析

3.1 搭建Hadoop平臺

Hadoop平臺包括1個(gè)主服務(wù)器(Master)和5個(gè)從服務(wù)器(Slave), 其中主服務(wù)器負(fù)責(zé)對所有資源的管理和分配, 從服務(wù)器主要實(shí)現(xiàn)數(shù)據(jù)節(jié)點(diǎn)和Task Tracker功能, 其配置列于表1. 采用VC++6.0作為開發(fā)工具實(shí)現(xiàn)大數(shù)據(jù)圖像分類算法.

3.2 Map和Reduce的性能測試

選擇1 500幅圖像作為測試對象, 提取它們的SIFT特征作為分類器的輸入向量, 并采用主成分分析對特征向量進(jìn)行降維, 不同數(shù)量的Map和Reduce條件下, 圖像的分類時(shí)間列于表2. 由表2可見：

1) 當(dāng)Reduce的數(shù)量固定不變時(shí), 隨著Map數(shù)量的不斷增加, Map的任務(wù)執(zhí)行時(shí)間不斷減少, Reduce的任務(wù)執(zhí)行時(shí)間略有下降, 但下降的幅度沒有Map大, 但當(dāng)Map的數(shù)量增加到一定程度時(shí), Reduce的任務(wù)完成時(shí)間卻略有增加, 這主要是因?yàn)殡S著Map數(shù)量的增加, 中間數(shù)據(jù)產(chǎn)生的規(guī)模不斷增加, 導(dǎo)致Reduce的任務(wù)完成時(shí)間延長；

2) 當(dāng)Map的數(shù)量和Reduce的數(shù)量分為16和8時(shí), 任務(wù)的總執(zhí)行時(shí)間最短, 因此選擇該數(shù)值進(jìn)行圖像分類測試.

表1 Hadoop平臺的配置

表2 不同數(shù)量Map和Reduce的圖像分類時(shí)間

3.3 與傳統(tǒng)單機(jī)平臺的圖像分類性能對比

當(dāng)測試圖像數(shù)量從2 000增加到10 000時(shí), 傳統(tǒng)單機(jī)平臺、 單節(jié)點(diǎn)的Hadoop平臺、 6個(gè)節(jié)點(diǎn)的Hadoop平臺的圖像分類任務(wù)執(zhí)行時(shí)間如圖6所示. 由圖6可見：

圖6 不同節(jié)點(diǎn)數(shù)的圖像分類時(shí)間對比Fig.6 Comparison of image classification time with different number of nodes

1) 當(dāng)圖像數(shù)量不斷增加時(shí), 傳統(tǒng)單機(jī)平臺的圖像分類時(shí)間不斷延長, 幾乎呈線性增加趨勢, 這是因?yàn)殡S著圖像數(shù)量的增加, 單機(jī)內(nèi)存駐留的數(shù)據(jù)量過大, 無法滿足大數(shù)據(jù)圖像分類的時(shí)間要求；

2) 單節(jié)點(diǎn)的Hadoop平臺圖像分類時(shí)間與傳統(tǒng)單機(jī)平臺的圖像分類時(shí)間差不多, 略有下降, 這是因?yàn)閱喂?jié)點(diǎn)的Hadoop平臺要進(jìn)行任務(wù)的初始化、 任務(wù)的細(xì)分、 分類結(jié)果的傳輸?shù)炔僮? 這些均會延長Hadoop平臺的運(yùn)行時(shí)間, 導(dǎo)致圖像分類的整體時(shí)間延長;

3) 6個(gè)節(jié)點(diǎn)的Hadoop平臺圖像分類任務(wù)所需時(shí)間明顯短于傳統(tǒng)單機(jī)平臺, 圖像分類的分類速度得到大幅度提升, 這主要是通過不同節(jié)點(diǎn)之間的協(xié)作完成大數(shù)據(jù)圖像分類的任務(wù), 縮短了圖像的分類時(shí)間.

綜上所述, 本文針對傳統(tǒng)單機(jī)平臺存在圖像分類時(shí)間長、 速度慢而無法滿足大數(shù)據(jù)圖像分類要求的缺陷, 提出一種基于Hadoop平臺的大數(shù)據(jù)圖像分類機(jī)制, 將大數(shù)據(jù)圖像分類任務(wù)拆分為Map和Reduce任務(wù), 通過多個(gè)節(jié)點(diǎn)協(xié)同完成大數(shù)據(jù)圖像分類任務(wù), 大幅度提升了圖像分類的速度, 尤其當(dāng)圖像數(shù)據(jù)規(guī)模較大時(shí), 圖像分類效率的優(yōu)勢更明顯.