徐 通, 馬 燕, 王玉善, 趙慧君

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)

并行計算在詞袋模型算法中的應(yīng)用

徐 通, 馬 燕*, 王玉善, 趙慧君

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)

傳統(tǒng)詞袋模型已廣泛地應(yīng)用于圖像處理領(lǐng)域,并取得較好效果.但在傳統(tǒng)詞袋模型中,僅考慮了串行計算,使得整個算法流程耗時較長.考慮現(xiàn)有的多核CPU資源,結(jié)合共享存儲并行編程(OpenMP)并行框架,對詞袋模型進(jìn)行并行優(yōu)化,并對其性能進(jìn)行討論.主要考慮對特征提取、特征聚類和圖像直方圖生成三個部分進(jìn)行并行優(yōu)化.通過對Caltech 100數(shù)據(jù)庫進(jìn)行實驗,結(jié)果表明,該方法可以取得接近于CPU核數(shù)的加速比,因此減少了詞袋模型的構(gòu)造和圖像直方圖生成時間,相對于傳統(tǒng)詞袋方法提高了算法的效率.

詞袋模型; 并行計算; 共享存儲并行編程; 圖像分類

0 引 言

圖像分類是計算機(jī)視覺領(lǐng)域的一個基礎(chǔ)問題.它在很多應(yīng)用場景都起著關(guān)鍵性的作用,如圖像分析和視覺監(jiān)控.其中一個重要的方法就是詞袋模型[1].近些年來,詞袋模型在許多常用數(shù)據(jù)集中得到廣泛應(yīng)用,如15-Scenes[2],Caltech 101[3],Caltech 256和ImageNet[4].傳統(tǒng)的視覺詞袋模型一般采用sift描述子,k-means聚類方法以及SVM分類器來實現(xiàn),并且在很多應(yīng)用上都取得了很好的效果.但是傳統(tǒng)詞袋算法僅考慮了串行計算,這使得對于大數(shù)據(jù)量的圖像進(jìn)行特征提取和特征聚類,往往會耗費(fèi)很長的時間,這就限制了詞袋模型的應(yīng)用.針對這些問題,學(xué)者們提出了不少對于詞袋模型的改進(jìn)算法.趙春暉等人[5]提出通過確定感興趣區(qū)域(ROI)從而減少特征描述子的詞袋模型優(yōu)化方法;陳凱等人[6]提出了一種基于單尺度詞袋模型分類方法.

隨著計算機(jī)科學(xué)的發(fā)展,原有的計算機(jī)串行計算也逐步向并行計算[7]發(fā)展,從而提高計算機(jī)的執(zhí)行效率.共享存儲并行編程(OpenMP)是用于共享內(nèi)存并行系統(tǒng)的多核處理程序設(shè)計方案,其實現(xiàn)簡單、可用性強(qiáng),尤其適用于任務(wù)型并行編程.因此,針對傳統(tǒng)詞袋模型串行運(yùn)行時間較長,無法充分利用多核CPU資源的不足,本文作者提出了一種基于OpenMP的并行詞袋模型算法,該算法主要對詞袋模型算法的3個方面:特征提取、特征聚類和圖像直方圖生成進(jìn)行并行優(yōu)化,使得計算負(fù)載分配到多個CPU上進(jìn)行,并在線程調(diào)度上進(jìn)行合理的設(shè)計,從而提高算法的執(zhí)行效率.

1 詞袋模型的基本框架

詞袋模型由于其簡單、有效的優(yōu)點(diǎn)最先在文本處理領(lǐng)域得到廣泛的應(yīng)用,然后被引入到圖像處理領(lǐng)域.其基本原理就是將文本看作無序關(guān)鍵詞的集合表示,通過統(tǒng)計每個關(guān)鍵詞在文本中出現(xiàn)的次數(shù),生成關(guān)鍵詞的向量直方圖來表示文本.在對應(yīng)的圖像分類領(lǐng)域中,詞袋模型的基本步驟包括:特征點(diǎn)的提取,視覺詞典的構(gòu)造,圖像直方圖生成和訓(xùn)練分類器進(jìn)行分類.圖1給出詞袋模型的基本流程.

圖1 詞袋模型流程圖

根據(jù)圖1,可以發(fā)現(xiàn),基于傳統(tǒng)詞袋模型的圖像分類算法僅考慮了串行計算,算法只有在執(zhí)行完上一步操作以后,才能執(zhí)行下一步操作.但對于大數(shù)據(jù)量的圖像來說,比如上萬幅的訓(xùn)練圖像,需要依次對每一幅圖像進(jìn)行特征提取,然后將特征點(diǎn)的集合進(jìn)行聚類得到視覺詞典,接著根據(jù)視覺詞典依次生成每幅圖像的直方圖表示,最后將圖像的直方圖表示放入SVM分類器中進(jìn)行訓(xùn)練.這樣整個算法流程耗時非常長,所消耗時間主要集中在特征提取、特征聚類和圖像直方圖生成3個部分.

2 并行優(yōu)化方案

針對傳統(tǒng)視覺詞袋模型耗時長的缺點(diǎn),結(jié)合現(xiàn)有的多核CPU技術(shù)和OpenMP并行計算框架針對視覺詞袋模型進(jìn)行并行優(yōu)化,以此來提高算法的執(zhí)行效率.考慮到傳統(tǒng)視覺詞袋模型耗時主要集中在特征提取、特征聚類和圖像直方圖生成3個部分,因此,主要對這3個部分進(jìn)行并行優(yōu)化,從而提高算法的執(zhí)行效率.

2.1 特征提取并行優(yōu)化

由于sift特征點(diǎn)可以在一定程度上解決目標(biāo)旋轉(zhuǎn)、縮放和平移、圖像仿射、光照影響、雜物場景等方面的問題,故選取sift特征點(diǎn)作為所需提取的特征.在實驗中通常采用Lowe[8]的建議,在關(guān)鍵點(diǎn)的尺度空間內(nèi),使用128維的描述子向量來表示,也就是說,在每個區(qū)域內(nèi)構(gòu)造4×4的窗口,每個窗口計算出8個方向的梯度信息,得到4×4×8=128維向量特征.這種sift特征描述子不受光照、視角變化等的影響,具有較高的獨(dú)特性.

圖2 特征提取并行優(yōu)化流程圖

特征提取并行優(yōu)化算法的步驟如下所述:首先對整個訓(xùn)練圖像集{I}進(jìn)行分類,圖像數(shù)據(jù)子集合I1到In,共n組(其中n表示圖像的類別數(shù));接著創(chuàng)建線程,記錄每個圖像所屬的圖像類別;然后對圖像進(jìn)行sift特征點(diǎn)提取,分別得到sift特征點(diǎn)集di(i=1,2,…,n);最后將所得到的sift特征點(diǎn)子集合并,即d1∪d2∪…∪dn,生成sift特征點(diǎn)總集合{D}.算法流程圖如圖2所示.

2.2 特征聚類并行優(yōu)化

在對訓(xùn)練圖像進(jìn)行特征點(diǎn)提取以后,得到完整的sift特征點(diǎn)集合{D},接著就是對特征點(diǎn)進(jìn)行聚類,得到聚類中心,即視覺詞典wk(k為視覺詞典的大小即聚類中心個數(shù)).傳統(tǒng)視覺詞袋模型采用k-means算法產(chǎn)生聚類中心.其基本流程是:

1)從特征空間中選擇k個特征點(diǎn)作為初始聚類中心;

2)在第n次迭代中,對任意一個樣本數(shù)據(jù),求其到k個中心的距離,將該樣本歸到距離最短的那個中心所在的類;

3)求均值更新該類的中心值;

4)對于所有的k個聚類中心,如果利用步驟2和3的迭代法更新后,值保持不變,或是滿足設(shè)定的終止條件,則迭代結(jié)束,否則繼續(xù)迭代.

圖3 特征聚類并行優(yōu)化流程圖

特征聚類并行優(yōu)化算法的步驟如下所述:首先確定初始聚類中的個數(shù)k,并從sift特征點(diǎn)集{D}中選取k個特征點(diǎn)wi(i=1,2,…,k);接著創(chuàng)建線程k,并行計算特征點(diǎn)集中剩余點(diǎn)到聚類中心的距離,將剩余點(diǎn)分配到距離最近的類中;然后計算該類中的距離均值;最后判斷是否滿足迭代終止條件,滿足則記錄聚類中心,否則重新選擇聚類中心.算法流程圖如圖3所示.

2.3 圖像直方圖生成并行優(yōu)化

在經(jīng)過上述步驟以后,就得到了詞袋模型的單詞表.利用它構(gòu)建每幅圖像的直方圖表示.并行優(yōu)化的具體步驟為:首先對圖像提取sift特征描述子di(n×128,n表示圖像sift特征點(diǎn)的數(shù)量);然后將單獨(dú)的sift特征點(diǎn)作為特征子集,并行計算它們和視覺詞典k的距離

(1)

其中i表示特征點(diǎn)的標(biāo)識符,k表示視覺單詞的標(biāo)記,mi為分別記錄每個特征點(diǎn)距離最近的視覺單詞的標(biāo)號,最后將所有標(biāo)號進(jìn)行合并,即m1∪m2∪…∪mn,得到圖像的的直方圖表示hi(1,2,…,k).將得到得圖像直方圖向量放入SVM分類器中進(jìn)行訓(xùn)練和測試.算法的具體流程如圖4所示.

圖4 圖像直方圖生成并行優(yōu)化流程圖

2.4 并行調(diào)度策略

在并行計算中,良好的線程調(diào)度策略[9]不僅可以保證CPU之間的負(fù)載平衡,還可以提高資源的利用率和并行效率.在OpenMP并行框架中,提供了4種調(diào)度策略:默認(rèn)策略、Static策略、Dynamic策略和Guided策略.通過實驗得到默認(rèn)的調(diào)度策略在性能上要略差于其他3種調(diào)度策略,而其他3種調(diào)度策略在并行計算上的效果不相上下.

通過對10類共200幅訓(xùn)練圖像并行測試,發(fā)現(xiàn)在4種調(diào)度策略的實際性能中,Dynamic策略是最好的.同時由于各圖像特征描述子數(shù)量的不同,選擇數(shù)據(jù)塊大小為1的Dynamic調(diào)度策略,使得數(shù)據(jù)劃分程度最細(xì),從而減小數(shù)據(jù)量不一致導(dǎo)致的CPU負(fù)載不均問題,減少線程同步等待時間,提高詞袋模型算法的效率.

3 實驗結(jié)果與分析

實驗在Windows系統(tǒng)(Intel(R)Core(TM)i5 CPU 3.20 GHz,內(nèi)存3.47 GB)上使用Visual Studio 2010實現(xiàn).實驗使用了由Li等提供的Callech-101圖像數(shù)據(jù)庫,共含有101個物品圖像類共9 146幅圖像,包含了的從人到動物的多種類別,每類的圖像的數(shù)量從31～800張不等,如圖5所示.Caltech-101數(shù)據(jù)集中的圖像存在較大的類內(nèi)變化,同時受到背景因素的影響,所以它是目前最復(fù)雜、最具挑戰(zhàn)性的圖像分類標(biāo)準(zhǔn)測試集之一.

為了驗證本方法的有效性,在數(shù)據(jù)集Caltech 101上進(jìn)行實驗.為了使實驗具有說服性,從數(shù)據(jù)集上隨機(jī)選擇10類進(jìn)行實驗.這10類圖像類別為:airplanes,anchor,ant,brain,ceiling_fan,chair,cup,elephant,face和rooster.由于對于每幅圖像,sift描述子的數(shù)量各不一樣,基本介于400～1 200之間,因此每次隨機(jī)挑選訓(xùn)練和測試圖像,每類的訓(xùn)練圖像為20張,測試圖像為10張,進(jìn)行10次隨機(jī)試驗,記錄每次的串行和并行時間,最后求取平均試驗時間.實驗中視覺詞典的大小選為200和300.

首先計算在串行下的運(yùn)行時間,接著計算在不同線程數(shù)下的并行優(yōu)化時間,如表1所示.

從表1中,可以發(fā)現(xiàn)通過并行優(yōu)化的詞袋模型算法能大大提高執(zhí)行效率.同時,為了使提高的效率表示更加明顯,引入加速比sp[10]的概念,設(shè)算法的串行執(zhí)行時間為Tk(1),而n個線程的并行執(zhí)行時間為Tk(n),則

圖5 Callech-101圖像數(shù)據(jù)庫

(2)

分別計算3個優(yōu)化部分在不同線程數(shù)和不同聚類個數(shù)下的加速比.

表1 詞袋模型串并行時間對比

當(dāng)線程數(shù)在CPU核數(shù)內(nèi)時,加速比逐漸增加,同時加速比的大小也接近計算機(jī)的核數(shù),但是當(dāng)線程數(shù)超過計算機(jī)的核數(shù)以后,加速比基本就不會變化太大.這是因為CPU的實際核數(shù)為4,當(dāng)線程數(shù)超過4以后,超出的部分將會掛起,等待執(zhí)行.因此,并行優(yōu)化可以通過設(shè)置核數(shù)與CPU核數(shù)相等,從而達(dá)到最好的加速比.這里發(fā)現(xiàn)在特征提取部分,sp的值和核數(shù)差距有點(diǎn)大,這是由于在優(yōu)化并行時,對每類圖像進(jìn)行并行計算,而由于每幅圖的sift描述子各不相同,導(dǎo)致圖像類別之間sift描述子的數(shù)量可能相差較大,從而導(dǎo)致sp的值低于理論值.

4 結(jié) 論

本文作者提出了基于OpenMP并行框架的詞袋模型,對特征提取、特征聚類和圖像特征直方圖3個部分進(jìn)行并行優(yōu)化,從實驗結(jié)果來看,通過并行優(yōu)化可以大大提高算法的執(zhí)行效率,并且能達(dá)到接近于CPU核數(shù)的加速比.對于訓(xùn)練好的詞袋模型進(jìn)行圖像分類時,單幅圖像并行優(yōu)化處理的時間基本在毫秒級,可以達(dá)到可接受的范圍;但是對于大規(guī)模圖像的SVM分類器訓(xùn)練,僅僅是作者所提的并行優(yōu)化方案則需耗費(fèi)較長時間,但如果輔以GPU(Graphics Processing Unit)來對特征提取和特征聚類進(jìn)行并行優(yōu)化,則可以實現(xiàn)時間的大幅度減少,使得詞袋模型構(gòu)造部分的時間達(dá)到可接受范圍.

[1] Mansoori N S,Nejati M,Razzaghi P,et al.Bag of visual words approach for image retrieval using color information [C].IEEE Computer Society Conference on Electrical Engineering (ICEE),Mashhad:IEEE,2013.

[2] Wang C,Huang K.How to use Bag-of-Words model better for image classification [J].Image and Vision Computing,2015,38(C):65-74.

[3] Li F F,Fergus R,Perona P.Learning generative visual models from few training examples:an incremental Bayesian approach tested on 101 object categories [J].Computer Vision and Image Understanding.2007,106(1):59-70.

[4] Gregory G,Alex H,Pietro P.Caltech-256 object category dataset [J].California Institute of Technology,2007,54(7694):1-20.

[5] Zhao C H,Wang Y,Kaneko M.An optimized method for image classification based on bag of words model [J].Journal of electronics and information,2012,34(9):2064-2070.

[6] Chen K,Xiao G Q,Pan Z,et al.Single-scale image classification employing bag of words model [J].Computer application research,2011,28(10):3986-3988．

[7] OpenMP Architecture Review Board.The Open MPAPI specification for parallel programming [EB/OL].[2013-10-01].http://openmp.org/mp-documents/OpenMP-4.0-C.pdf.

[8] Lowe D G.Distinctive image feature from scale-invariant keypoints [J].International Journal of Computer Vision,2004,60(2):91-100.

[9] Luo Q M,Ming Z,Liu G,et al.OpenMp compiler theory and implementation techniques [M].Beijing:Tsinghua University Press,2012.

[10] Chen G L,Sun G Z,Xu Y,et al.Parallel computing research methodology [J].Chinese Journal of Computer,2008,31(9):1493-1502.

(責(zé)任編輯：包震宇)

The application of parallel computing in the bag ofwords model algorithm

Xu Tong, Ma Yan*, Wang Yushan, Zhao Huijun

(College of Information,Mechanical and Electrical Engineering,Shanghai Normal University,Shanghai 200234,China)

Traditional bag of words (BoW) model has been widely used in image classification,and achieves better results.But in the traditional bag of words model only the serial computation is considered,making the whole process takes a long time.In this paper the BoW model is optimized with parallel method combining with OpenMP parallel framework under multi-core CPU resources.Parallel optimization of three parts,including feature extraction,feature clustering and image histogram generation,is performed.The proposed method is executed on the Caltech 100 database.The experimental results show that the proposed method can achieve speedup ratio which is close to the number of CPU cores.Therefore,compared with the traditional BoW model,the time for vocabulary construction and image histogram generation has been reduced,which improves the algorithm efficiency.

bag of words; parallel computing; OpenMP; image classification

2015-10-09

徐 通(1989-),男,碩士研究生,主要從事圖像處理方面的研究.E-mail:xtahch8949@163.com

導(dǎo)師簡介: 馬 燕(1970-),女,教授,主要從事圖像處理方面的研究.E-mail:ma-yan@shnu.edu.cn

TP 391

A

1000-5137(2017)02-0218-06

*通信作者