基于軟加權(quán)映射的局部聚類向量表示方法

劉 琦，梁 鵬， 周毅書(shū)， 張海濤， 周劍雄

(1.中國(guó)移動(dòng)南方基地，廣東 廣州 510640; 2. 廣東技術(shù)師范學(xué)院 計(jì)算機(jī)科學(xué)學(xué)院，廣東 廣州 510665)

基于軟加權(quán)映射的局部聚類向量表示方法

劉 琦1，梁 鵬2， 周毅書(shū)1， 張海濤1， 周劍雄1

(1.中國(guó)移動(dòng)南方基地，廣東 廣州 510640; 2. 廣東技術(shù)師范學(xué)院 計(jì)算機(jī)科學(xué)學(xué)院，廣東 廣州 510665)

基于特征碼本的圖像分類方法依賴于需要特征向量與聚類中心之間的映射，然而硬加權(quán)映射方法導(dǎo)致了相似的特征向量被映射為不同的聚類中心，從而降低了分類的查全率。為此提出一種基于軟加權(quán)映射的局部聚類向量表示方法。該方法首先用k均值算法將特征向量聚類為k個(gè)聚類中心，采用最近鄰算法尋找最接近的s個(gè)聚類中心，通過(guò)特征向量與聚類中心之間的相似度和鄰近程度構(gòu)建軟加權(quán)映射的局部聚類向量，然后統(tǒng)計(jì)特征直方圖，最后用主成分分析減少特征直方圖維度。實(shí)驗(yàn)結(jié)果分析表明，相比較硬加權(quán)映射方法，文中方法提高了約5%的分類準(zhǔn)確率。

軟加權(quán)映射; 圖像分類; 特征碼本; 主成分分析

0 引言

復(fù)雜紛亂的背景、局部遮擋和幾何變化給目標(biāo)圖像分類帶來(lái)了應(yīng)用上的困難，因此詞包模型分類方法得到了廣泛的應(yīng)用。如圖1所示，詞包模型是基于特征聚類得到的，即對(duì)特征向量進(jìn)行聚類量化得到多個(gè)聚類中心，所有的聚類中心組成一個(gè)特征碼本，特征向量與聚類中心之間的映射稱為特征量化。

圖1 詞包模型表示示意圖

特征向量可以選擇角點(diǎn)或者SIFT特征、SURF特征等，近期這方面的工作可參見(jiàn)文獻(xiàn)[1-3]等。然而，詞包模型在量化過(guò)程中丟失了目標(biāo)物體的空間結(jié)構(gòu)信息，僅僅使用了特征的視覺(jué)信息。這使得一些視覺(jué)上類似但是分布完全不同的物體難以分類，因此加入空間信息成為了另一個(gè)研究的熱點(diǎn)。Svetlana Lazebnik等提出了空間金字塔Spatial pyramid模型[4]，其將圖像分成多個(gè)同樣大小的網(wǎng)格，對(duì)每個(gè)網(wǎng)格內(nèi)的局部特征分別進(jìn)行頻率直方圖統(tǒng)計(jì)，再將直方圖按照網(wǎng)格順序連接起來(lái)形成具有空間分布信息的直方圖。在此基礎(chǔ)上，出現(xiàn)了一系列類似的變化方法[5-9]。其中局部聚類向量表示[10](Vector Local Aggregating Descriptors, VLAD)通過(guò)比較同一個(gè)聚類中心內(nèi)所有的特征向量方向以加入空間信息，既降低了特征碼本量化的精度，又降低了計(jì)算復(fù)雜度。然而上述方法的特征映射過(guò)程均采用硬加權(quán)映射方法，即一個(gè)特征向量只映射到最近鄰的聚類中心。近期研究發(fā)現(xiàn)[11,12]，這些方法的查全率難以提升，這是因?yàn)橛布訖?quán)映射方法在量化特征碼本過(guò)程中存在誤差，從而導(dǎo)致特征映射時(shí)無(wú)法映射到準(zhǔn)確的聚類中心。如圖2所示的硬加權(quán)映射聚類結(jié)果表明，對(duì)于5個(gè)聚類中心，點(diǎn)1，2，3，4, 5表示特征向量，按照硬加權(quán)特征映射方法，即使點(diǎn)3，4空間距離十分相近，在特征匹配階段，點(diǎn)3和點(diǎn)4仍然被認(rèn)為是完全不同的特征，這就給后續(xù)的分類帶來(lái)了匹配上的誤差。

圖2 硬加權(quán)映射的聚類結(jié)果

這樣的硬加權(quán)映射結(jié)果將導(dǎo)致特征點(diǎn)3和特征點(diǎn)4被量化為兩種不同的特征，從而在分類過(guò)程中容易產(chǎn)生混淆，降低了分類的查全率。

軟加權(quán)映射方法可以有效地增加特征的魯棒性，模糊C聚類和模糊k均值是兩種軟加權(quán)映射方法。Li等采用模糊C均值聚類提高了聚類的準(zhǔn)確率[13]。Khang等用分層模糊C均值聚類提高了彩色圖像分割精度。然而模糊聚類使得特征維度變長(zhǎng)，特征直方圖更加稀疏，從而在一定程度降低了分類準(zhǔn)確率[14]。

為了解決硬加權(quán)映射帶來(lái)的問(wèn)題，文中提出一種基于軟加權(quán)的局部聚類向量表示方法，既保留了軟加權(quán)映射的魯棒性，又減少了特征維度。該方法通過(guò)特征向量與聚類中心之間的相似度和鄰近程度實(shí)現(xiàn)軟加權(quán)映射，實(shí)驗(yàn)結(jié)果表明了方法的有效性。

1 基于軟加權(quán)的局部聚類向量表示

特征碼本的構(gòu)建是詞包模型中必不可少的一個(gè)環(huán)節(jié)，通過(guò)特征碼本實(shí)現(xiàn)了特征向量與特征單詞之間的映射，極大地減少了特征向量的維數(shù)。然而，特征碼本的量化精度也成為了檢索方法準(zhǔn)確率的瓶頸，為了盡可能提高特征之間的可區(qū)分性，需要提高量化的精度；而要提高檢索系統(tǒng)的泛化能力，則要降低量化的精度，因此需要在兩者之間尋找一個(gè)平衡。此外，傳統(tǒng)的特征碼本構(gòu)建方法通常采用k均值方法，為了保證量化精度，通常將特征碼本維數(shù)n取為很大的值，該方法的計(jì)算復(fù)雜度為O(n2)，計(jì)算效率很低。為了降低算法復(fù)雜度，提出了近似聚類方法(KD-tree和hierarchical kmeans)，但又無(wú)法保證聚類的精度。

為了解決上述問(wèn)題，文獻(xiàn)[10]提出了一種VLAD局部聚類向量表示方法，該方法既可以降低特征碼本量化的精度以實(shí)現(xiàn)降低計(jì)算復(fù)雜度，又加入了特征之間的空間關(guān)系以保證檢索的準(zhǔn)確率，VLAD構(gòu)建過(guò)程如圖3所示。

VLAD采用的是硬加權(quán)特征映射方法，即一個(gè)特征向量映射到與其距離最近的聚類中心。給定M個(gè)特征向量Φ=[r1,r2,…,rM]，聚類為N個(gè)聚類中心的特征碼本W(wǎng)=[w1,w2,…,wN]，則特征向量rj與聚類中心wi的映射表示如公式(1)所示，d(rj,wi)表示特征向量rj和聚類中心wi的直方圖距離。

(1)

圖3 VLAD方法構(gòu)建過(guò)程

特征直方圖H(wi)則由特征向量rj映射到聚類中心wi的頻次n(rj,wi)和聚類中心wi在圖像I中出現(xiàn)的頻次n(wi,I)計(jì)算得到，如公式(2)所示：

(2)

然而，兩個(gè)極其相似的特征向量如果被映射給兩個(gè)不同的聚類中心，則將被認(rèn)為是完全不同的特征。

據(jù)文本檢索的研究表明，單詞存在多義性，即一個(gè)單詞在不同的情況下有不同的含義。而硬加權(quán)特征映射方法則減少了特征單詞多義性帶來(lái)的泛化能力。為此，本文提出一種基于軟加權(quán)的局部聚類向量表示方法。

采用一個(gè)距離向量V來(lái)取代傳統(tǒng)的單個(gè)特征向量映射，距離向量V=[v1,v2,…,vs]表示為該特征向量與多個(gè)聚類中心之間的距離表示，s表示最近鄰居聚類中心的個(gè)數(shù)。則VLAD中特征向量rj與聚類中心wi之間的映射關(guān)系n(rj,wi)如公式(3)所示：

(3)

(4)

使用軟加權(quán)映射后，增大了特征直方圖的維度(從J維變?yōu)镴×s維)，然而經(jīng)過(guò)對(duì)特征直方圖進(jìn)行統(tǒng)計(jì)分析后發(fā)現(xiàn)，特征向量維度增加導(dǎo)致直方圖大部分值為0，特征直方圖很稀疏，這給后續(xù)的分類帶來(lái)不必要的數(shù)據(jù)冗余。為此，采用主成分分析(PCA)對(duì)特征直方圖進(jìn)行降維，提取出數(shù)據(jù)中最重要的部分。降維步驟如下：

(1)將所有的特征直方圖組成一個(gè)矩陣A∈RJ*s×d，d表示特征直方圖的個(gè)數(shù)；

(2)計(jì)算矩陣A的均值和協(xié)方差矩陣；

(3)根據(jù)協(xié)方差矩陣計(jì)算出特征值和特征向量，將特征值按從大到小的順序排列，選擇特征值較大的特征向量組成主成分矩陣；

(4)將主成分矩陣與矩陣A相乘，得到降維后的特征直方圖。

2 實(shí)驗(yàn)及討論

為了驗(yàn)證本文提出的基于軟加權(quán)的局部聚類向量表示方法的有效性，將該方法用于目標(biāo)分類。實(shí)驗(yàn)數(shù)據(jù)集采用著名的Scene15數(shù)據(jù)集，Scene15數(shù)據(jù)集有15種類別的場(chǎng)景圖像，平均每個(gè)類別約有300張圖像，示例圖像如圖4所示。

圖4 Scene15部分示例圖像

本次實(shí)驗(yàn)的局部特征提取方法采用的是SIFT局部特征，聚類方法采用k均值聚類，分類器使用的是libsvm工具箱。實(shí)驗(yàn)的分類策略是每個(gè)類型抽取前100張圖像用作訓(xùn)練，剩余的圖像作為測(cè)試集。SVM分類器的分類參數(shù)采用交叉驗(yàn)證法獲取，分類參數(shù)為c=5，g=0.5，核函數(shù)采用RBF徑向基核函數(shù)，分類策略采用二分類法，即每個(gè)類別的分類器由多個(gè)二分類器組成，該分類器的分類結(jié)果由二分類器的投票結(jié)果決定，得票最多的分類器類型即是測(cè)試圖像的類型。采用的分類評(píng)價(jià)準(zhǔn)則為平均準(zhǔn)確率(mean Average Precision, mAP)

2.1 不同參數(shù)下的軟加權(quán)對(duì)聚類精度的影響

首先檢驗(yàn)文中方法在不同參數(shù)下對(duì)分類準(zhǔn)確率的影響，改變參數(shù)σ和s，獲取不同參數(shù)下Scene15數(shù)據(jù)庫(kù)分類實(shí)驗(yàn)的mAP值，結(jié)果如表1所示。當(dāng)s>3后，平均準(zhǔn)確率有所降低，這是因?yàn)檫^(guò)多的聚類中心映射反而導(dǎo)致特征匹配準(zhǔn)確率的下降。因此后續(xù)的實(shí)驗(yàn)采用參數(shù)s=3，σ2=5 000。

圖5是本文方法與硬加權(quán)映射方法在不同大小的特征碼本下的mAP曲線圖。從圖中可以看出，本文方法相比較硬加權(quán)映射方法，mAP提高了約5%。隨著特征碼本不斷增大，兩種方法的mAP提高均有限，此時(shí)增加特征碼本不僅對(duì)分類準(zhǔn)確率沒(méi)有提升，反而增加了特征匹配的錯(cuò)誤率，因此選擇合適大小的特征碼本可以減少算法的計(jì)算復(fù)雜度。

表1 不同參數(shù)的實(shí)驗(yàn)對(duì)比結(jié)果

圖5 不同大小特征碼本的mAP曲線

2.2 方法對(duì)比實(shí)驗(yàn)

為了更好地體現(xiàn)文中方法的性能，將文中方法與VLAD+硬加權(quán)映射方法進(jìn)行對(duì)比，實(shí)驗(yàn)對(duì)比的結(jié)果如圖6所示。

圖6 不同圖像數(shù)據(jù)庫(kù)大小的mAP曲線

從上圖的實(shí)驗(yàn)數(shù)據(jù)可以得出，隨著圖像數(shù)據(jù)庫(kù)數(shù)量的不斷增加，兩種方法的mAP值均明顯下降，也說(shuō)明了無(wú)論是哪種方法，在大數(shù)據(jù)量的圖像分類中其作用都相當(dāng)有限。相比較硬加權(quán)映射方法，本文方法通過(guò)軟加權(quán)映射，能更有效地提高特征匹配的魯棒性和分類準(zhǔn)確性。

3 結(jié)論

本文提出了一種基于軟加權(quán)映射的局部聚類向量表示方法，首先用k均值算法將特征向量聚類為k個(gè)聚類中心，采用最近鄰算法尋找最接近的s個(gè)聚類中心，通過(guò)特征向量與聚類中心之間的相似度和鄰近程度構(gòu)建軟加權(quán)映射的局部聚類向量，然后統(tǒng)計(jì)特征直方圖，最后通過(guò)主成分分析減少特征直方圖維度。基于Scene15數(shù)據(jù)庫(kù)的圖像分類實(shí)驗(yàn)表明，文中提出的基于軟加權(quán)映射的局部聚類向量表示方法與硬加權(quán)映射方法表示相比較，可以提高分類準(zhǔn)確率。但文中方法仍存在不足之處，例如特征碼本構(gòu)建的準(zhǔn)確率是本文方法的瓶頸，如何更加快速、準(zhǔn)確地量化特征向量，是今后工作的重點(diǎn)。

[1] GRAUMAN K，DARRELL T. Pyramid match kernels: Discriminative classification with sets of image features[C]. Proceedings of the IEEE International Conference on Computer Vision, 2005:1458-1465.

[2] 王林灝, 宋臻毓. 基于SURF特征的人臉識(shí)別方法研究[J]. 微型機(jī)與應(yīng)用, 2014, 33(7):31-34.

[3] 李倩影,陳鍛生,吳揚(yáng)揚(yáng). 基于圖像距離匹配的人臉卡通化技術(shù)[J]. 微型機(jī)與應(yīng)用, 2014, 33(10):44-46.

[4] LAZEBNIK S. Semi-local and global models for texture, object and scene recognition[D]. University of Illinois at Urbana Champaign, 2006.

[5] KIM G, FALOUTSOS C, HEBERT M. Unsupervised modeling and recognition of object categories with combination of visual contents and geometric similarity links[C]. In ACM International Conference on Multimedia Information Retrieval (ACM MIR), 2008: 419-426.

[6] LEORDEANU M, HEBERT M. A spectral technique for correspondence problems using pairwise constraints[C]. In ICCV, 2005: 1482-1489.

[7] LEORDEANU M, HEBERT M, SUKTHANKAR R. Beyond local appearance: Category recognition from pairwise interactions of simple features[C]. In CVPR, 2007:1-8.

[8] 劉揚(yáng)聞, 霍宏, 方濤. 詞包模型中視覺(jué)單詞歧義性分析[J]. 計(jì)算機(jī)工程, 2011, 37(19):204-209.

[9] Tian Qi, Hua Gang, Huang Qingming, et al. Generating descriptive visual words and visual phrases for large-scale image applications[J]. IEEE Transactions on Image Processing, 2011, 20(9): 2664-2667.

[10] JEGOU H, DOUZE M, SCHMID C, et al. Aggregating local descriptors into a compact image representation[C]. IEEE Conference on Computer Vision Pattern Recognition, 2010: 3304-3311.

[11] KANUNGO G K, SINGH N, DASH J, et al. Mammogram image segmentation using hybridization of fuzzy clustering and optimization algorithms[C]. Processing in Intelligent Computing, Communication and Devices Advances in Intelligent Systems and Computing, 2015: 403-413.

[12] PHILBIN J, CHUM O, ISARD M, et al. Object retrieval with large vocabularies and fast spatial matching[C]. In Proc. CVPR, 2007:1-8.

[13] LI M J, NG M K, CHEUNG Y M, et al. Agglomerative fuzzy K-means clustering algorithm with selection of number of clusters[J]. IEEE Transactions on Knowledge and Data Engineering, 2008, 20(11): 1519-1534.

[14] KHANG S T, NOR A M I. Color image segmentation using histogram thresholding-fuzzy C-means hybrid approach[J]. Pattern Recognition, 2011, 44(1): 1-15.

Vector of locally aggregated descriptor based on soft assignment approach

Liu Qi1, Liang Peng2, Zhou Yishu1, Zhang Haitao1, Zhou Jianxiong1

(1. China Mobile South Base, Guangzhou 510640;2. School of Computer Science, Guangdong Polytechnic Normal University, Guangzhou 510665, China)

The traditional bag-of-words image classification approaches are based on feature vectors mapping to clustering centers by hard assignment, which will cause vision similarly features vectors being mapped to different clustering centers. In this case, we propose a novel vector of locally aggregated descriptor based on soft assignment approach. Firstly, we associate local features withsnearby cluster centers instead of its single nearest neighbor cluster depending on the distance between the features and the cell centers by usingk-means clustering algorithm. Then, we construct vector of locally aggregated descriptors by computing distances and similarity between feature vectors and clustering centers. Finally, we use PCA algorithm to reduce the dimension of feature histogram. The experimental results show that the proposed method can improve 5% accuracy rate.

soft assignment; image classification; feature dictionary; PCA

廣東省自然科學(xué)基金博士啟動(dòng)項(xiàng)目(2015A030310340)；廣東省高等學(xué)校科技創(chuàng)新項(xiàng)目(2013KJCX0117)

TP391

A

1674-7720(2016)01-0038-04

劉琦，梁鵬， 周毅書(shū)，等.基于軟加權(quán)映射的局部聚類向量表示方法[J].微型機(jī)與應(yīng)用，2016，35(1)：38-41.

2015-09-14)

劉琦(1984-)，男，碩士，主要研究方向：大數(shù)據(jù)應(yīng)用、云計(jì)算、圖像處理。

梁鵬(1981-)，通信作者，男，博士研究生，講師，主要研究方向：圖像處理、模式識(shí)別，E-mail：cs_phoenix_liang@163.com。

周毅書(shū)(1981-)，男，碩士，主要研究方向：大數(shù)據(jù)應(yīng)用、云計(jì)算、圖像處理。