劉 琦，梁 鵬， 周毅書， 張海濤， 周劍雄

(1.中國移動南方基地，廣東 廣州 510640; 2. 廣東技術師范學院 計算機科學學院，廣東 廣州 510665)

基于軟加權映射的局部聚類向量表示方法

劉 琦1，梁 鵬2， 周毅書1， 張海濤1， 周劍雄1

(1.中國移動南方基地，廣東 廣州 510640; 2. 廣東技術師范學院 計算機科學學院，廣東 廣州 510665)

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

軟加權映射; 圖像分類; 特征碼本; 主成分分析

0 引言

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

圖1 詞包模型表示示意圖

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

圖2 硬加權映射的聚類結果

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

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

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

1 基于軟加權的局部聚類向量表示

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

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

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

(1)

圖3 VLAD方法構建過程

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

(2)

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

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

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

(3)

(4)

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

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

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

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

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

2 實驗及討論

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

圖4 Scene15部分示例圖像

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

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

首先檢驗文中方法在不同參數(shù)下對分類準確率的影響，改變參數(shù)σ和s，獲取不同參數(shù)下Scene15數(shù)據(jù)庫分類實驗的mAP值，結果如表1所示。當s>3后，平均準確率有所降低，這是因為過多的聚類中心映射反而導致特征匹配準確率的下降。因此后續(xù)的實驗采用參數(shù)s=3，σ2=5 000。

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

表1 不同參數(shù)的實驗對比結果

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

2.2 方法對比實驗

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

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

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

3 結論

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

[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特征的人臉識別方法研究[J]. 微型機與應用, 2014, 33(7):31-34.

[3] 李倩影,陳鍛生,吳揚揚. 基于圖像距離匹配的人臉卡通化技術[J]. 微型機與應用, 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] 劉揚聞, 霍宏, 方濤. 詞包模型中視覺單詞歧義性分析[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

廣東省自然科學基金博士啟動項目(2015A030310340)；廣東省高等學?？萍紕?chuàng)新項目(2013KJCX0117)

TP391

A

1674-7720(2016)01-0038-04

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

2015-09-14)

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

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

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