基于橢圓-雙曲線馬氏度量的圖像分類算法

鮑文霞, 閻少梅, 梁 棟, 胡根生

(1. 安徽大學計算機智能與信號處理教育部重點實驗室, 安徽 合肥 230039; 2. 偏振光成像探測技術安徽省重點實驗室, 安徽 合肥 230031)

0 引 言

圖像分類作為圖像理解的基礎,是計算機視覺和模式識別領域中重要且應用廣泛的研究方向之一,如在目標識別[1]、物體檢測[2]以及場景識別與分類[3]等方面都有應用。圖像分類是利用計算機視覺技術,根據目標在圖像信息中所反映出的特征,把不同類別的目標識別、區分開來的圖像處理方法[4-9]。目前大部分的圖像分類方法都依賴于用圖像特征間的距離來度量圖像內容的語義相似度,實現對圖像內容的理解與分類,因此距離度量在圖像分類中扮演了重要的角色,文獻[10]提出了k最近鄰分類方法,通過度量出與測試樣本距離最近的k個訓練樣本,根據它們的類別來決定測試樣本的類別;文獻[11]在此基礎上提出了基于監督的最近鄰分類方法;文獻[12]結合貝葉斯分類器和k最近鄰分類器提出了一種新的基于距離度量的分類方法。這些算法在度量圖像特征間的相似性的時候都采用的是歐氏距離,歐氏距離度量對所有屬性特征同等對待,忽略了屬性特征間的主次關系,沒有突出不同的屬性特征對分類帶來不同的影響,因此會降低分類器的性能[13]。

目前流行的解決方法是用馬氏度量[14]取代歐氏度量,如文獻[15]提出的大間隔最近鄰分類算法,從局部近鄰中學習一個馬氏度量距離從而實現分類。馬氏度量考慮了數據樣本維度分量之間的相關性,即非平等地對待數據樣本的各個維度分量,因而在實際應用中比歐氏度量有更好的分類效果。例如,文獻[16]提出了基于圖像到類距離度量的圖像分類方法,該方法基于最近鄰原則度量圖像間的馬氏距離實現分類;文獻[17]提出基于馬氏距離的高斯概率分布從而實現了信息理論度量學習的分類算法。馬氏度量學習是通過訓練樣本,尋找一種能夠反應樣本空間結構信息或語義信息的線性變換,雖然馬氏度量學習得到的馬氏度量優于歐氏度量,但線性變換局限了馬氏度量的應用范圍。為了進一步拓寬度量學習在圖像分類中的適用范圍同時提高分類的性能,本文提出基于橢圓-雙曲線馬氏度量學習的圖像分類算法。橢圓-雙曲線馬氏度量學習問題就是對于給定訓練樣本數據,尋找一種能夠反應樣本空間結構信息或語義信息的分式線性變換,從而使得橢圓-雙曲線馬氏度量有更好區分性。線性變換是分式線性變換的一種特殊形式,因此基于橢圓-雙曲線馬氏度量學習適用范圍更廣。基于橢圓-雙曲線馬氏度量學習的圖像分類算法首先提取圖像特征,圖像特征由HSV(色調Hue, 飽和度Saturation, 亮度Value)與Lab(L(亮度Lightness), a(色度chromaticity,+a表示紅色,-a表示綠色), b(色度chromaticity,+b表示黃色,-b表示藍色))直方圖描述的顏色特征和局部二值模式(local binary patterns,LBPs)描述的紋理特征構成;然后根據數據統計特性定義橢圓-雙曲線馬氏度量,通過橢圓-雙曲線馬氏度量學習獲取最優的度量矩陣;最后通過度量圖像特征間的距離實現了圖像分類。

1 橢圓-雙曲線度量

在數學史上,當歐氏幾何學的平行公理被質疑時,兩種非歐幾何學誕生,即橢圓型幾何和雙曲線型幾何[18]。

給定一個可逆對稱矩陣Ω∈R(n+1)×(n+1),它誘導出x,y∈Rn的雙線性形式為

?x,y∈Rn

(1)

下面將ω(x,y)用其簡化形式ωxy來表示,其中(xT,1)T表示點x的齊次坐標。根據Ω是正定或者不定,ωxy誘導出兩種度量幾何,即橢圓型度量和雙曲線型度量。如果矩陣Ω是正定的,令En={x∈Rn:ωxx>0},定義ρE:En×En→R+,橢圓型度量為

(2)

式中,i為虛數單位,如果矩陣Ω是不定的,令Hn={x∈Rn:ωxx>0},定義ρE:Hn×Hn→R+,雙曲線型度量為

(3)

在En和Hn上,和ρH(x,y)兩種ρE(x,y)度量均滿足其4個條件,即滿足

(4)

因此,ρE(x,y)和ρH(x,y)是En和Hn上的度量,橢圓型度量與雙曲線型度量共同構成橢圓-雙曲線度量。其中,(En,ρE)叫做橢圓型幾何;(Hn,ρH)叫做雙曲型幾何;1/k是橢圓幾何空間的曲率;-1/k是雙曲幾何空間的曲率。可以將橢圓-雙曲線度量表示為

(5)

根據以上定義可知,橢圓-雙曲線度量依賴于一個對稱矩陣Ω,給定一個對稱矩陣就可以確定一個橢圓-雙曲線度量。

2 橢圓-雙曲線馬氏度量

數據的統計特性在一定程度上反映了樣本數據的幾何結構,因此可以由樣本數據的均值和協方差矩陣計算初始橢圓-雙曲線度量矩陣。對于給定的樣本矩陣

表示第i個樣本,1≤i≤N。令Xj=(xj1,xj2,…,xjN),1≤j≤n,且mj為Xj的均值,那么矩陣樣本X可以表示為X=(X1,X2,…,Xn)T,于是Xi與Xj的協方差為cov(Xi,Xj)=(Xi-mi)(Xj-mj)T/(N-1)。因此,樣本矩陣X的協方差矩陣為

令m=(m1,m2,…,mn)T,則初始橢圓-雙曲線度量矩陣定義為

(6)

(xi-m)Tcov-1(xj-m)±k2,k>0

(7)

(9)

已知,樣本xi和xj間的馬氏距離為

(10)

式中,矩陣G∈Rd×d為樣本xi和xj協方差矩陣的逆矩陣,即G=cov(xi,xj)-1。

因此,從幾何上可以得到橢圓-雙曲線度量與馬氏度量的關系為

(11)

式中,1/k(-1/k)是橢圓(雙曲線)空間的曲率,在k取極限的情況下橢圓-雙曲線度量無限接近馬氏度量,因此將由數據統計特性得到的特殊形式的橢圓-雙曲線度量稱為橢圓-雙曲線馬氏度量。

3 橢圓-雙曲線馬氏度量學習

橢圓-雙曲線馬氏度量學習問題就是對于給定訓練樣本數據,尋找一個最優的橢圓-雙曲線馬氏度量矩陣使得相應的度量在某種學習準則下是最優的。根據傳統的馬氏度量學習常用的大間隔最近鄰(large margin nearest neighbor, LMNN )準則[19],可以得到橢圓-雙曲線馬氏度量學習框架下的LMNN學習準則,簡稱橢圓雙曲線-大間隔最近鄰(elliptic hyperbolic-large margin nearest neighbor，EH-LMNN)準則。

由于xi和xj的橢圓-雙曲線馬氏距離度量為

dEH(xi,xj)=

(12)

因此,橢圓-雙曲線馬氏度量在EH-LMNN學習準則下的最優化問題可表示為

(13)

式中,xj是xi的目標近鄰,記j→i。給定一個二值函數yij∈{0,1}來表示樣本xi與樣本xj的類標簽是否相同,yij=1表示樣本xi和xj類別相同,yij=0表示類別不同。xl為不同標簽的樣本,μ是平衡參數,一般取0.5。ξijl≥0表示標簽不同的數據xl侵入由xi的目標近鄰xj定義的xi的周圍邊界的數目,即ξijl≥1+dEH(xi,xj)-dEH(xi,xl)。

M0=LTL

(14)

通過約束條件和鉸鏈函數將松弛變量ξijl表示為L的函數為

ξijl(L)=[1+dEH(xi,xj)-dEH(xi,xl)]+

(15)

式中,如果z≥0,[z]+=z;否則,[z]+=0。

將式(15)考慮進目標函數中,其表達式為

(16)

因此最優化問題可以通過梯度下降法迭代解決,即對式(16)進行求導,記矩陣L在第t次迭代時為Lt,目標函數的梯度函數在度量矩陣第t次迭代時的計算式為

(17)

式(17)中的兩部分的導數分別為

(18)

(19)

因此通過梯度下降法迭代收斂后獲得最優的變換矩陣L,通過L可以得到橢圓-雙曲線度量學習中的最優橢圓-雙曲線馬氏度量矩陣M=LTL。

學習算法如下:

輸入訓練樣本及其標簽

步驟1首先根據樣本的統計特性計算樣本的均值和協方差矩陣;

步驟2給定步長λ,t=1,由式(6)計算初始度量矩陣M0;

步驟3令Mt=M0,對其進行分解Mt=(Lt)T(Lt);

步驟4計算第t次目標函數的值Ψ(Lt);

步驟5由式(17)～式(19)計算第t次的梯度Γt;

步驟6更新Lt+1=Lt-λ·Γt;

步驟7計算Mt+1=(Lt+1)T(Lt+1);

步驟8計算第t+1次目標函數值Ψ(Lt+1);

步驟9判斷‖Ψ(Lt+1)-Ψ(Lt)‖≤10-10,若不滿足條件，令t=t+1并重復步驟(5)～步驟(9)直至迭代收斂。

輸出最優橢圓-雙曲線馬氏度量矩陣M。

4 圖像分類算法及其實驗結果

4.1 圖像分類算法流程

基于橢圓-雙曲線馬氏度量學習的圖像分類算法提取圖像特征,圖像特征由HSV與Lab直方圖描述的顏色特征和LBPs描述的紋理特征構成,并采用主成分分析(principal component analysis,PCA)方法對圖像特征進行降維;然后,根據第3節的橢圓-雙曲線馬氏度量學習算法獲取最優的橢圓-雙曲線馬氏度量矩陣;最后,采用得到的橢圓-雙曲線馬氏度量矩陣將測試樣本變換到新的特征空間并降低特征各維度間的相關性,并利用其計算出測試樣本與每個類別的距離,將距離最小所對應的類作為測試樣本的類別。算法流程如圖1所示。

圖1 算法流程圖Fig.1 Flow chart of algorithm

4.2 實驗結果

利用基于橢圓-雙曲線馬氏度量的圖像分類算法(因在EH-LMNN準則下學習,所以稱此算法為EH_LMNN算法)進行了大量實驗,下面給出LEAR ToyCars數據集[21]和VIPeR數據集[22]上的實驗結果,實驗中圖像采用同樣的特征表示,即由HSV與Lab直方圖描述的顏色特征和LBPs描述的紋理特征構成。LEAR ToyCars數據集包含了14種不同的玩具車和卡車的256張圖像,圖2列舉了4種不同玩具車的圖像,數據集展示了圖像在姿勢、燈光以及雜亂背景的變化。分別利用本文的EH-LMNN算法、支持向量機(support vector machine，SVM)算法[4]、馬氏度量(mahalanobis metric,MAHAL)算法[14]以及信息理論度量學習(information theoretic metric learning，ITML)算法[17]進行在LEAR ToyCars數據集上進行對比實驗;同時采用3種不同的初始矩陣即單位矩陣(I)、隨機矩陣(R)以及本文的橢圓-雙曲線馬氏度量矩陣(M),利用本文的算法進行分類實驗。圖3給出了實驗結果的接收器操作特性(receiver operator characteristic, ROC)曲線和等錯誤率(equal error rate,EER)值。ROC曲線采用假正率和真正率作為橫縱坐標,其中,假正率(false positive rate，FPR)為分類器錯誤預測為正類的負樣本占所有負樣本的比例,計算公式為FPR=FP/(FP+TN),其中,FP表示負類樣本被預測成正類的數目,TN表示負類樣本被預測成負類的數目;真正率(true positive rate，TPR)為分類器正確預測為正類的正樣本占所有正樣本的比例,計算公式為TPR=TP/(TP+FN),其中,TP表示正類樣本被預測成正類的數目,FN表示正類樣本被預測成負類的數目。理想情況下,TPR應該接近1,且FPR應該接近0;ROC曲線下方的面積越大,則分類器的分類性能越好。EER值是ROC曲線中錯分正負樣本概率相等的點,這個點就是ROC曲線與ROC空間中對角線([0,1]-[1,0]連線)的交點。

圖3 ROC曲線對比Fig.3 ROC curves comparison

表1和表2分別給出了分類的曲線下方面積(area under curve,AUC)值和正確率。AUC表示ROC曲線下方的面積,面積越大表示分類性能越好。正確率就是被預測正確的樣本數除以所有的樣本數,即實際正(負)樣本被預測正確的概率。

表1 不同算法的AUC值比較

表2 不同算法的正確率比較

由圖3、表1及表2實驗結果可知,本文基于橢圓-雙曲線馬氏度量學習的圖像分類算法與其他算法相比取得了更好的圖像分類性能;并且以橢圓-雙曲線馬氏度量矩陣M為初始矩陣的分類算法分類效果最佳。

分別利用本文的EH-LMNN算法、SVM算法[4]、MAHAL算法[14]、ITML算法[17]、KISS度量(KISS metric，KISSME)算法[23]以及跨視角二次判別分析(cross-view quadratic discriminant analysis,XQDA)算法[24]在VIPeR數據集上進行對比實驗(見表3);其中,圖像采用同樣的特征表示,即由HSV與Lab直方圖描述的顏色特征和LBPs描述的紋理特征構成。VIPeR數據集包含了兩個不同相機視角獲得的室外632個行人對。其低分辨率圖像在姿勢、角度上展示出了巨大的變化,同時在高光或者陰影等光照上也有巨大的變化。圖4給出兩個相機獲取的行人圖像，大部分的圖像對行人的拍攝角度都有90°的變化,這使得分類更具挑戰性。實驗將632個行人對隨機分成兩部分,其中316個行人對用于實驗訓練,剩下的用于實驗測試。

表3 在VIPeR數據集行人對的匹配率對比

圖4 VIPeR數據集上的行人對實例Fig.4 Pedestrian pairs example on VIPeR dataset

實驗將EH_LMNN算法、ITML算法、MAHAL算法、KISSME算法以及XQDA算法進行分類性能的對比,圖5給出了實驗結果的累計匹配特征(cumulative matching characteristic,CMC)曲線,CMC曲線表示測試集中所選測試圖與目標圖第n次即成功匹配的概率,其中橫坐標表示匹配的次數,縱坐標表示圖像的匹配概率。為了實驗結果的有效性,取100次實驗的平均值。表3具體給出了在第55次、60次、75次以及90次行人對匹配成功的匹配率。

圖5 CMC曲線對比Fig.5 CMC curves comparison

由圖5和表3的實驗結果可以看出,本文基于橢圓-雙曲線馬氏度量學習的圖像分類算法性能優于馬氏度量學習,具有更好的適用性。

5 結 論

針對圖像分類中的度量學習問題,提出一種基于橢圓-雙曲線馬氏度量學習的圖像分類算法。該算法結合數據點的統計特性定義了橢圓-雙曲線馬氏度量,建立了橢圓-雙曲線馬氏度量學習算法,通過度量圖像特征間的距離實現了圖像分類。實驗驗證基于橢圓-雙曲線馬氏度量學習圖像分類性能優于傳統的馬氏度量學習算法。

[1] LIANG M, HU X. Recurrent convolutional neural network for object recognition[C]∥Proc.of the IEEE Conference on Computer Vision and Pattern Recognition, 2015: 3367-3375.

[2] ACHANTA R, HEMAMI S, ESTRADA F, et al. Frequency-tuned salient region detection[C]∥Proc.of the 22nd IEEE Internet Conference on Computer Vision and Pattern Recognition, 2009: 1597-1604.

[3] 顧廣華,韓晰瑛,陳春霞,等. 圖像場景語義分類研究進展綜述[J]. 系統工程與電子技術, 2016, 38(4): 938-948.

GU G H, HAN X Y, CHEN C X, et al. Survey on semantic scene classification research[J]. Systems Engineering and Electronics, 2016, 38(4): 938-948.

[4] ENGEL C, BAUMGARTNER P, HOLZMANN M, et al. Person re-identification by support vector ranking[C]∥Proc.of the Conference on British Machine Vision, 2010: 1-11.

[5] 陳善學, 屈龍瑤, 胡燦. 基于空間約束加權條件稀疏表示高光譜圖像分類[J]. 系統工程與電子技術, 2016, 38(2): 442-449.

CHEN S X, QU L Y, HU C. Spatial correlation constrained weighted conditional sparse representation for hyperspectral image classification[J]. Systems Engineering and Electronics, 2016, 38(2): 442-449.

[6] SCHMIDHUBER J, MEIER U, CIRESAN D. Multicolumn deep neural networks for image classification[C]∥Proc.of the IEEE Conference on Computer Vision and Pattern Recognition, 2012: 3642-3649.

[7] LU J L, WANG G, DENG W H, et al. Multimanifold deep metric learning for image set classification[C]∥Proc.of the IEEE Conference on Computer Vision and Pattern Recognition, 2015: 1137-1145.

[8] HU J L, LU J W, TAN Y P. Discriminative deep metric learning for face verification in the wild[C]∥Proc.of the IEEE Conference on Computer Vision and Pattern Recognition, 2014: 1875-1882.

[9] LUO Y, LIU T, TAO D, et al. Decomposition-based transfer distance metric learning for image classification[J]. IEEE Trans.on Image Processing, 2014, 23(9): 3789-3801.

[10] COVER T M, HART P E. Nearest neighbor pattern classification[J].IEEE Trans.on Information Theory,1967,13(1):21-27.

[11] WOHLHART P, KOSTINGER M, DONOSER M, et al. Optimizing 1 nearest prototype classifiers[C]∥Proc.of the IEEE Conference on Computer Vision and Pattern Rocognition, 2013: 460-467.

[12] FERDOUSY E Z, ISLAM M, MATIN M A. Combination of Na?ve Bayes classifier and K-nearest neighbor (cNK) in the classification based predictive models[J]. Computer & Information Science, 2013, 6(3): 48-56.

[13] 楊柳, 于劍, 景麗萍.一種自適應的大間隔近鄰分類算法[J]. 計算機研究與發展, 2013, 50(11): 2269-2277.

YANG L, YU J, JING L P. An adaptive large margin nearest neighbor classification algorithm[J]. Journal of Computer Research and Development, 2013, 50(11): 2269-2277.

[14] AHARON B H, TOMER H, NOAM S, et al. Leaning a mahalanobis metric from equivalence constraints[J]. Journal of Machine Learning Research, 2005, 6(6): 937-965.

[15] WEINBERGER K Q, SAUL L K. Fast solvers and efficient implementations for distance metric learning[C]∥Proc.of the 25th Internet Conference on Machine Learning,2008:1160-1167.

[16] WANG Z, HU Y, CHIA L T. Image-to-class distance metric learning for image classification[C]∥Proc.of the European Conference on Computer Vision, 2010: 709-719.

[17] DAVIS J V, KULIS B, JAIN P, et al. Information theoretic metric learning[C]∥Proc.of the 24th Internet Conference on Machine Learning, 2007: 209-216.

[18] RICHTER-GEBERT J. Perspectives on projective geometry: a guided tour through real and complex geometry[M]. USA:Springer, 2011.

[19] NIELSEN F, MUZELLEC B, NOCK R. Classification with mixtures of curved mahalanobis metrics[C]∥Proc.of the IEEE International Conference on Image Processing, 2016: 241-245.

[20] DERENIOWSKI D, KUBALE M. Cholesky factorization of matrices in parallel and ranking of graphs[C]∥Proc.of the 5th International Conference on Parallel Processing and Applied Mathematics, 2003: 985-992.

[21] NOWAK E, JURIE F. Learning visual similarity measures for comparing never seen objects[C]∥Proc.of the IEEE Internet Conference on Computer Vision and Pattern Recognition,2007:1-8.

[22] GRAY D, BRENNAN S, TAO H. Evaluating appearance models for recongnition, reacquisition and tracking[C]∥Proc.of the IEEE Internet Workshop on Performance Evaluation of Tracking and Surveillance, 2007: 2-6.

[23] KOSTINGER M, HIRZER M, WOHLHART P, et al. Large scale metric learning from equivalence constraints[C]∥Proc.of the IEEE Conference on Computer Vision and Pattern Recognition, 2012: 2288-2295.

[24] LIAO S C, HU Y, ZHU X Y, et al. Person re-identification by local maximal occurrence representation and metric learning[C]∥Proc.of the IEEE International Conference on Computer Vision and Pattern Recognition, 2015: 2197-2206.