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

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

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

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

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

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

詞袋模型; 并行計(jì)算; 共享存儲(chǔ)并行編程; 圖像分類

0 引 言

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

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

1 詞袋模型的基本框架

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

圖1 詞袋模型流程圖

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

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

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

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

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

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

特征提取并行優(yōu)化算法的步驟如下所述:首先對(duì)整個(gè)訓(xùn)練圖像集{I}進(jìn)行分類,圖像數(shù)據(jù)子集合I1到In,共n組(其中n表示圖像的類別數(shù));接著創(chuàng)建線程,記錄每個(gè)圖像所屬的圖像類別;然后對(duì)圖像進(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)化

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

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

(2)

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

表1 詞袋模型串并行時(shí)間對(duì)比

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

4 結(jié) 論

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

TP 391

A

1000-5137(2017)02-0218-06

*通信作者