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

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

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

0 引 言

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

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

1 橢圓-雙曲線度量

在數(shù)學(xué)史上,當(dāng)歐氏幾何學(xué)的平行公理被質(zhì)疑時,兩種非歐幾何學(xué)誕生,即橢圓型幾何和雙曲線型幾何[18]。

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

?x,y∈Rn

(1)

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

(2)

式中,i為虛數(shù)單位,如果矩陣Ω是不定的,令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上的度量,橢圓型度量與雙曲線型度量共同構(gòu)成橢圓-雙曲線度量。其中,(En,ρE)叫做橢圓型幾何;(Hn,ρH)叫做雙曲型幾何;1/k是橢圓幾何空間的曲率;-1/k是雙曲幾何空間的曲率?？梢詫E圓-雙曲線度量表示為

(5)

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

2 橢圓-雙曲線馬氏度量

數(shù)據(jù)的統(tǒng)計特性在一定程度上反映了樣本數(shù)據(jù)的幾何結(jié)構(gòu),因此可以由樣本數(shù)據(jù)的均值和協(xié)方差矩陣計算初始橢圓-雙曲線度量矩陣。對于給定的樣本矩陣

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

令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協(xié)方差矩陣的逆矩陣,即G=cov(xi,xj)-1。

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

(11)

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

3 橢圓-雙曲線馬氏度量學(xué)習(xí)

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

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

dEH(xi,xj)=

(12)

因此,橢圓-雙曲線馬氏度量在EH-LMNN學(xué)習(xí)準(zhǔn)則下的最優(yōu)化問題可表示為

(13)

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

M0=LTL

(14)

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

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

(15)

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

將式(15)考慮進(jìn)目標(biāo)函數(shù)中,其表達(dá)式為

(16)

因此最優(yōu)化問題可以通過梯度下降法迭代解決,即對式(16)進(jìn)行求導(dǎo),記矩陣L在第t次迭代時為Lt,目標(biāo)函數(shù)的梯度函數(shù)在度量矩陣第t次迭代時的計算式為

(17)

式(17)中的兩部分的導(dǎo)數(shù)分別為

(18)

(19)

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

學(xué)習(xí)算法如下:

輸入訓(xùn)練樣本及其標(biāo)簽

步驟1首先根據(jù)樣本的統(tǒng)計特性計算樣本的均值和協(xié)方差矩陣;

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

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

步驟4計算第t次目標(biāo)函數(shù)的值Ψ(Lt);

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

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

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

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

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

輸出最優(yōu)橢圓-雙曲線馬氏度量矩陣M。

4 圖像分類算法及其實驗結(jié)果

4.1 圖像分類算法流程

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

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

4.2 實驗結(jié)果

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

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

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

表1 不同算法的AUC值比較

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

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

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

表3 在VIPeR數(shù)據(jù)集行人對的匹配率對比

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

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

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

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

5 結(jié) 論

針對圖像分類中的度量學(xué)習(xí)問題,提出一種基于橢圓-雙曲線馬氏度量學(xué)習(xí)的圖像分類算法。該算法結(jié)合數(shù)據(jù)點的統(tǒng)計特性定義了橢圓-雙曲線馬氏度量,建立了橢圓-雙曲線馬氏度量學(xué)習(xí)算法,通過度量圖像特征間的距離實現(xiàn)了圖像分類。實驗驗證基于橢圓-雙曲線馬氏度量學(xué)習(xí)圖像分類性能優(yōu)于傳統(tǒng)的馬氏度量學(xué)習(xí)算法。

[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ìn)展綜述[J]. 系統(tǒng)工程與電子技術(shù), 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] 陳善學(xué), 屈龍瑤, 胡燦. 基于空間約束加權(quán)條件稀疏表示高光譜圖像分類[J]. 系統(tǒng)工程與電子技術(shù), 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] 楊柳, 于劍, 景麗萍.一種自適應(yīng)的大間隔近鄰分類算法[J]. 計算機(jī)研究與發(fā)展, 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.