基于PCA-SIFT特征與貝葉斯決策的圖像分類算法

涂秋潔　王　晅

(陜西師范大學物理學與信息技術學院　陜西 西安 710119)

?

基于PCA-SIFT特征與貝葉斯決策的圖像分類算法

涂秋潔王晅

(陜西師范大學物理學與信息技術學院陜西 西安 710119)

摘要針對現有的基于SIFT特征的圖像分類算法具有較大的儲存空間需求及對圖像背景較為敏感的問題，提出一種基于PCA-SIFT特征和貝葉斯決策的圖像分類算法。該算法首先應用主成分分析將SIFT特征從128維降為36維，在訓練過程中，對訓練樣本圖像的PCA-SIFT進行區域匹配。基于匹配率選擇目標圖像中的穩定PCA-SIFT以提高算法對背景圖像干擾的魯棒性，然后應用最大似然估計估計概率分布參數，最后，應用貝葉斯決策理論實現圖像分類。仿真實驗表明，該算法與現有的SIFT圖像分類算法相比分類精度高，而且具有最小的儲存空間需求與較高的計算效率。

關鍵詞PCASIFT聚類貝葉斯決策圖像分類

0引言

對幾何變換如平移、旋轉與尺度變換的不變圖像目標描述對圖像分析、目標識別與分類等具有非常重要的意義[1]，現有的不變特征描述主要分為全局、局部與基于目標輪廓的特征表示三類[2]。全局特征只適合于剛性對象的識別與分類，而且對圖像剪切、遮擋、光照改變與視角改變較為敏感。基于目標輪廓的特征，如張量尺度、曲率尺度、內距[3]與多尺度距[4]等僅具有部分幾何變換不變性，而且對圖像剪切、遮擋、光照改變與視角改變較為敏感，另外，其性能嚴重依賴于邊緣檢測與圖像分割的結果。

基于圖像局部特征的不變描述方法，如GLOH[5],Harris-Affine[6],SIFT[7],SURF[8]等對圖像的剪切、遮擋、尺度、位置、方向、光照及輕微的視角改變具有很好的穩定性，而且突破了剛性對象的限制。在這些方法中，SIFT已被證實具有最好的描述性能[9]，被廣泛應用在圖像區域匹配、目標檢測與圖像檢索中。但是，由于圖像局部特征的固有特性，不太適合圖像識別與分類問題。首先，對于一幅圖像，通常會檢測到成百上千個關鍵點，每個關鍵點需要128維的向量表示，這需要較大的儲存空間保存圖像的類別模式特征。其次，兩幅圖像的特征點匹配的計算復雜度為128×N2，N為單幅圖像的關鍵點數量，這使得基于局部特征的圖像分類很難滿足實際應用的計算效率要求。最后，由于圖像區域匹配與分類的目標與要求不同，所以分類精度也達不到實際應用的要求。

最近，出現了許多研究工作將SIFT從圖像區域匹配推廣到圖像分類問題中，較早的SIFT圖像分類算法是基于圖像區域匹配的算法[10,11]，這些算法首先將待識別圖像與已知類別的訓練樣本圖像進行區域匹配，然后基于區域匹配數量實現模式分類。該類算法具有較高的儲存空間要求與計算復雜度，另外，只考慮區域匹配數量很難獲得高的分類精度。隨后出現了基于編碼或聚類的SIFT圖像分類算法[12-16]，該類算法的主要創意來源于文本數據挖掘的BoW(bag-of-words)概念，將圖像所提取的關鍵點特征當作視覺詞匯，然后，基于圖像中出現的視覺詞匯的頻次或編碼結果作為特征實現分類[12-14]. 但是，BOW模型直接應用于SIFT特征沒有考慮局部特征點的空間位置，所以基于此產生的頻次或編碼特征缺失了圖像的空間組織信息。針對此問題，Lazebnik等提出了SPM算法[15]， 該算法將圖像在不同尺度上劃分為多個細段，計算每個細段內的BOW的直方圖，然后，鏈接所有直方圖形成圖像的最終表示。SPM算法雖然部分考慮了圖像的空間組織信息，獲得了較好的分類精度，但其特征具有很高的維數，這嚴重制約了分類過程的計算效率，特別是使用非線性分類器時，其計算復雜度呈指數增長。為了降低SPM的計算復雜度，文獻[16]在SPM的基礎上應用非線性編碼技術將特征轉化為近似線性可分問題，然后應用線性分類器實現分類，獲得了較好的分類效果。最新的此方面的研究[17-19]主要集中在將稀疏編碼或機器學習應用到BOW或SPM模型中，從而降低圖像的特征向量維數或提升其表示能力，以提升分類過程的計算效率與分類精度。如Yang等[17]應用稀疏編碼代替SPM中的向量量化，提出了稀疏SPM(ScSPM)算法，Wang[18]將稀疏編碼過程轉化為局部約束下的優化問題，提出了LLC算法。Zhang等[19]將低階分解與拉普拉斯群稀疏編碼應用于BOF模型中，實現了圖像分類等。

現有的基于SIFT的圖像分類算法雖然對圖像的剪切、遮擋、尺度、位置、方向、光照及輕微的視角改變具有很好的穩定性，但是，其儲存需求與計算效率并不能滿足實際應用的要求，另外，SIFT描述字已經被證實在圖像區域匹配和目標檢測中具有非常好的性能，基于編碼的方法并沒有充分利用SIFT的這一優良特性，所以其分類精度也達不到令人滿意的效果。針對此問題，本文提出了一種基于SIFT區域匹配與貝葉斯決策的圖像分類算法，為了有效地降低算法的特征維數，使用主成分分析(PCA)將SIFT特征從128維降為36維。在訓練過程中，將屬于同類的樣本圖像的PCA-SIFT進行互配，根據匹配率選擇該類圖像較為穩定的PCA-SIFT特征應用最大似然估計估計其均值向量與協方差矩陣，然后基于貝葉斯決策理論進行分類。仿真實驗表明，該算法具有較高的分類精度，而且由于其在分類過程中只涉及簡單的數值計算，具有較高的計算效率。

1SIFT算法與PCA-SIFT簡介

1.1SIFT算法

經典SIFT算法[7]分為多尺度空間極值點檢測、關鍵點篩選、關鍵點方向校正與描述字生成四個子過程。在多尺度空間極值點檢測過程中，首先將待檢測圖像I(x,y)與相鄰尺度的高斯差分函數進行卷積形成多尺度空間表示，即：

G(x,y,σ)=(G(x,y,kσ)-G(x,y,σ))*I(x,y)

(1)

其中，* 表示沿x與y方向的卷積，高斯函數G(x,y,σ)定義為：

L(x,y,σ)=G(x,y,σ)*I(x,y)

(2)

然后，檢測多尺度空間中的極值點作為候選關鍵點，檢測規則為該點是某一尺度空間相鄰8個像素及其上、下相鄰尺度空間中同位置的18個像素的極值點。在這些候選關鍵點中，會存在對局部噪聲干擾較為敏感的不穩定的關鍵點。針對這一問題，SIFT算法引入Hessian矩陣對候選關鍵點進行進一步篩選，候選關鍵點的Hessian矩陣定義為：

(3)

其中：

(4)

(5)

(6)

其中，D(x,y,σ)為該關鍵點所在的尺度空間，不穩定的關鍵點的主方向響應會遠遠大于其垂直方向，如果α表示Hessian矩陣主方向所對應的特征值，β為其垂直方向所對應的特征值，則有：

α+β=Tr(H)=Dxx+Dyy

(7)

(8)

改寫可得：

(9)

其中，γ=α/β，因此，候選關鍵點的篩選規則為：

(10)

其中，T為篩選閾值。通過上述兩個過程，在圖像I(x,y)的多尺度空間可以檢測若干穩定的關鍵點，為了獲得旋轉不變性，還要對關鍵點進行方向校正，其基本原理是在確定該關鍵點的SIFT描述字時，將坐標軸旋轉到該關鍵點的主方向。關鍵點的主方向通過計算該關鍵點鄰域梯度分布直方圖的峰值，然后再進行二次函數的擬合來確定。在統計鄰域梯度分布直方圖時，對梯度幅值進行方差為尺度因子σ1.5倍的高斯函數進行加權。

在關鍵點描述字生成過程中，首先以關鍵點為中心，旋轉其鄰域使得坐標軸x與該關鍵點的主方向重合，并且根據其尺度因子σ進行相應的尺度變換，然后計算其16×16鄰域像素點的梯度幅值與方向，將16×16鄰域劃分為16個4×4的子塊，計算每個子塊8方向的梯度直方圖，將16個子塊的梯度直方圖的值按從左到右，從上到下的次序排列起來(見圖1所示)，然后進行歸一化，形成該關鍵點128維的SIFT描述字。

圖1　SIFT描述字計算過程圖示

1.2PCA-SIFT 算法

直接利用SIFT算法提取的特征進行后續的圖像處理，無論是從算法的計算復雜度，還是從算法的性能來看，都是不可取的。所以需要對128維SIFT特征進行降維。利用主成分分析的方法對SIFT算法進行改進，具體實現過程如下。

確定樣本圖像I(x,y)的關鍵點 ( 假設為n個)，針對每個關鍵點提取SIFT特征，共128維，將其組成特征矩陣X=(x1,x2,…,xn)，維數為n×128。

計算特征向量的均值：

(11)

計算特征向量的協方差矩陣：

(12)

求取協方差矩陣的特征值和特征向量。由于Cx是實對稱的，故可以找到128個正交的特征向量，設特征值λi對應的特征向量為ei，將特征值從大到小排列。

將最大的k個特征值對應的特征向量ek組成變換矩陣A，A的維數為128×k，k的取值大小決定最終特征向量的維數。

Ke等的工作[22]表明，當k選擇36時，PCA-SIFT具有最佳的區域匹配和表示能力，而且在他們的實驗中，PCA-SIFT區域匹配和表示能力好于原SIFT特征。本文選擇k=36，變換矩陣A生成過程采用與文獻[22]相似的方法，即選擇一組與識別問題無關而且差異較大的圖像，抽取20 000多個SIFT特征根據上述方法進行PCA降維，獲得128×36維的變換矩A，將此變換矩陣保存起來，應用下式進行降維：

y=Ax

(13)

其中，x為原SIFT特征，y為對應的36維的PCA-SIFT。

2本文算法

本文算法的實現過程如圖2所示。

圖2　基于PCA-SIFT與貝葉斯決策的圖像分類算法實現流程圖

2.1訓練過程

本文算法首先應用式(10)對所提取到的SIFT特征進行降維。在訓練過程中，對同類訓練樣本圖像所提取到的PCA-SIFT特征進行互配，計算每個PCA-SIFT的互配率，具體作法如下，首先在同一類別的訓練樣本圖像中隨機選擇一幅訓練樣本圖像fw(x,y)，將其與同類的其它訓練樣本圖像基于PCA-SIFT進行區域匹配，對于圖像fw(x,y)中的某一PCA-SIFT特征ywi，其互配率s(ywi)定義為：

(14)

其中，Nw為訓練集中w類樣本圖像總數，nwi為與特征ywi區域匹配成功的該類訓練樣本圖像總數。互配率s(ywi)反映了特征ywi在該類圖像中的穩定程度，如果s(ywi)趨近于1，說明對應特征ywi在該類圖像中為目標圖像的穩定關鍵點，在分類過程中應重點考慮，如果s(ywi)趨近于0，則特征ywi為該類圖像中背景圖像或其它干擾所形成的關鍵點，在分類過程中可能會干擾分類結果。基于此，我們根據互配率s(ywi)的大小對特征ywi進行進一步篩選，如果s(ywi)>T，則特征ywi在該類圖像中為目標圖像的穩定關鍵點保留，否則，即舍去。其中T為閾值，根據具體分類問題基于實驗確定。

對于同一目標圖像的穩定關鍵點特征ywi，在不同的訓練樣本圖像和測試圖像中，其值由于噪聲或成像設備等因素會發生一定漂移，假定其變化符合多維正太分布，有：

(15)

其中，μwi與∑wi為關鍵點特征ywi概率公布的均值向量與協方差矩陣，可以在訓練過程中基于最大似然估計進行估算[23]，有：

(16)

(17)

其中，ywij為特征ywi在同類的第j幅訓練樣本圖像對應的區域匹配特征。由于PCA降維使得特征ywi的各分量不相關，基于正太分布假設，理論上∑wi應為對角矩陣，在實驗中，我們發現，∑wi雖然不是對角矩陣，但其非對角原素值遠小于對角原素，我們只保留∑wi矩陣的對角原素，其它原素為零作為協方差矩陣的近似估計。將w類所有穩定特征對應的μwi、∑wi與互配率s(ywi)作為該類別的模式特征。

2.2基于貝葉斯決策的圖像分類

給定未知樣本圖像f(x,y)，提取其所有SIFT特征，應用式(10)獲得其對應的PCA-SIFT特征yl，1≤l≤N。考慮到這些特征中一部分特征屬于背景圖像，與分類的目標圖像無關，在分類過程中應舍去，則，樣本圖像f(x,y)的類概率：

(18)

(19)

(20)

其中，Nw為w類的圖像穩定的PCI-SIFT特征總數，根據貝葉斯公式，給定未知樣本f(x,y)，其屬于類別w的后驗概率為：

(21)

則未知樣本f(x,y)應分類到后驗概率p(w/f(x,y))最大的對應類別中，由于概率函數的非負性，上述分類規則等價于求p(f(x,y)/w)p(w)的最大值。假定在分類過程中，各個訓練類別的先驗概率類p(w)相同，則上述規則等價于計算p(f(x,y)/w)的最大值，將式(20)代入式(18)，有：

(22)

為了簡化計算，對式(22)兩邊取對數，有：

(23)

去掉上式中不影響比較結果的常數項因子，則取上式的最大值等價于計算下式的最小值：

(24)

則，分類規則為：

(25)

考慮到在訓練過程中，互配率s(ywi)較大的特征在該類圖像中為目標圖像的穩定關鍵點，在分類過程中應重點考，因此，式(25)的分類規則最后修正為：

(26)

2.3方法儲存需求與計算效率分析

表1　儲存需求與計算效率比較

3實驗結果與分析

實驗采用文獻中常用的兩個標準數據庫Caltech-101[24]、15-Scene[15]進行了仿真測試，并與基于SIFT最新的、有代表性的圖像分類方法如SPM[15]、ScSPM[17]、LLC[18]、拉普拉斯群稀疏編碼[19]、自適應分塊機器學習[20]與空域金字塔稀疏編碼方法[21]進行了性能比較。

實驗115-Scene數據庫包含了15類圖像，包括床、郊區、工業園區、廚房、臥室、海岸、森林、高速路等一共4485幅圖像。對每一類選取30幅圖像作為訓練圖像，其它圖像作為測試圖像。實驗結果見表2所示。如表2所示，各種改進的SPM算法較原SPM算法分類精度有不同程度的提高，基于機器學習的改進方法分類精度高于基于稀疏編碼的改進算法，我們的方法較現有的方法具有最好的分類精度。

表2　對15-Scene標準數據庫的分類精度

實驗2Caltech-101 數據庫包含了101類共9144幅圖像(包含有動物，花，人臉等)。每一類圖像有31～800幅方向、光照、大小不同的樣本圖像。對每一類圖像選取30幅圖像作為訓練樣本，其他圖像作為測試樣本。應用我們的方法與上述方法進行分類，結果見表3所示。由表3可以看出，上述方法該數據庫的分類精度較實驗1都有不同程度的下降，主要原因是Caltech-101 數據庫的樣本圖像方向、光照、大小明顯不同，尤其是其分類的目標圖像都具有不同的背景，而我們的方法通過訓練過程中的互配率對圖像的特征點進行了篩選，在分類過程中，互配率大的特征點對分類結果貢獻在。這在一定程度上降低了圖像背景中的特征點對分類過程的干擾，所以我們方法較現有方法具有最好的分類精度，而且在兩個數據庫上的分類精度下降最小。

表3　對Caltech-101 標準數據庫的分類精度

4結語

本文提出了基于PCASIFT特征和貝葉斯決策的圖像分類方法，PCASIFT特征不僅有效地繼承了SIFT特征在平移、旋轉、尺度變換和光照改變下的魯棒性，而且解決了SIFT特征維度較高的問題，大大降低了計算的復雜度。實驗結果表明，本文的方法比現有算法分類精度高，而且對背景圖像的干擾具有較高的魯棒性。

參考文獻

[1]WangX,XiaoB,MaJF,etal.ScalingandrotationinvariantanalysisapproachtoobjectrecognitionbasedonRadonandFourier-Mellintransforms[J].PatternRecognition,2007(40):3503-3508.

[2]XiaoB,MaJF,WangX.ImageanalysisbyBessel-Fouriermoments[J].PatternRecognition,2010(43):2620-2629.

[3]LingH,JacobsDW.Shapeclassificationusingtheinnerdistance[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,2007,29(2):286-299.

[4]HuR,JiaW,LingH,etal.MultiscaleDistanceMatrixforFastPlantLeafRecognition[J].IEEETrans.ImageProcessing,2012,21(11):4667-4172.

[5]MikolajczykK,SchmidC.Aperformanceevaluationoflocaldescriptors[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,2005(27):1615-1630.

[6]MikolajczykK,SchmidC.Scale&affineinvariantinterestpointdetectors[J].InternationalJournalofComputerVision,2004(60):63-86.

[7]LoweDG.Distinctiveimagefeaturesfromscale-invariantkeypoints[J].InternationalJournalofComputerVision,2003,60(2):91-11.

[8]BayH,EssA,TuytelaarsT,etal.Speeded-uprobustfeatures(SURF)[J].ComputerVisionandImageUnderstanding,2008,110(3):346-359.

[9]TuytelaarsT,MikolajczykK.Localinvariantfeaturedetectors:Asurvey[J].FoundationsandTrendsinComputerGraphicsandVision,2007,3(3):177-280.

[10]BadrinathGS,PhalguniGupta.PalmprintVerificationusingSIFTfeatures[J].ImageProcessingTheory,ToolsandApplications,2008(20):1-8.

[11]LeqingZhu,SanyuanZhang,RuiXing,etal.UsingSIFTandPROSACtoIdentifyPalmprints[C]//Proceedingsofthe2008InternationalConferenceonImageProcessing,ComputerVision,&PatternRecognition,2008:136-141.

[12]XuY,HuangSB,JiH,etal.Scale-spacetexturedescriptiononSIFT-liketextons[J].ComputerVisionandImageUnderstanding,2012(116):999-1013.

[13]HeY,KavukcuogluK,WangY,etal.UnsupervisedFeatureLearningbyDeepSparseCoding[J].arXivpreprintarXiv,2013:1312.5783.

[14]JiangZ,LinZ,DavisLS.LearningadiscriminativedictionaryforsparsecodingvialabelconsistentK-SVD[C]//ComputerVisionandPatternRecognition(CVPR),2011IEEEConferenceon.IEEE,2011:1697-1704.

[15]LazebnikS,SchmidC,PonceJ.Beyondbagsoffeatures:Spatialpyramidmatchingforrecognizingnaturalscenecategories[C]//ComputerVisionandPatternRecognition,2006IEEEComputerSocietyConferenceon.IEEE,2006,2:2169-2178.

[16]ZhouX,CuiN,LiZ,etal.Hierarchicalgaussianizationforimageclassification[C]//ComputerVision,2009IEEE12thInternationalConferenceon.IEEE,2009:1971-1977.

[17]YangJ,YuK,GongY,etal.Linearspatialpyramidmatchingusingsparsecodingforimageclassification[C]//ComputerVisionandPatternRecognition,2009.CVPR2009.IEEEConferenceon.IEEE,2009:1794-1801.

[18]WangJ,YangJ,YuK,etal.Locality-constrainedlinearcodingforimageclassification[C]//ComputerVisionandPatternRecognition(CVPR),2010IEEEConferenceon.IEEE,2010:3360-3367.

[19]ZhangL,MaC.Low-rankdecompositionandLaplaciangroupsparsecodingforimageclassification[J].Neurocomputing,2014(135):339-347.

[20]LiuB,LiuJ,LuH.Adaptivespatialpartitionlearningforimageclassification[J].Neurocomputing,2014(142):282-290.

[21]ZhangC,WangS,HuangQ,etal.Imageclassificationusingspatialpyramidrobustsparsecoding[J].PatternRecognitionLetters,2013,34(9):1046-1052.

[22]KeY,SukthankarR.PCA-SIFT:Amoredistinctiverepresentationforlocalimagedescriptors[C]//ComputerVisionandPatternRecognition,2004.CVPR2004.Proceedingsofthe2004IEEEComputerSocietyConferenceon.IEEE,2004:506-513.

[23] 王晅,馬建峰.數字圖像分析與模式識別[M].北京:科學出版社,2009.

[24]FeifeiL,FergusR,PeronaP.Learninggenerativevisualmodelsfromfewtrainingexamples:anincrementalBayesianapproachtestedon101objectcategories[C]//IEEECVPRWorkshoponGenerative-ModelBasedVision,2004.

IMAGE CLASSIFICATION ALGORITHM BASED ON PCA-SIFT FEATURESANDBAYESIANDECISION

Tu QiujieWang Xuan

(School of Physics and Information Technology,Shaanxi Normal University,Xi’an 710119,Shaanxi,China)

AbstractIn order to cope with the problems that existing SIFT-based image classification algorithms require a large amount of storage space and are sensitive to image backgrounds, this paper presents a novel image classification algorithm which is based on PCA-SIFT features and Bayesian decision. The algorithm first applies the principal component analysis (PCA) to reduce the dimensionality of SIFT from 128 to 36, in training process, it makes regional matching on PCA-SIFT descriptors of the training sample images. In order to improve its robustness on background image interference, we selected the stable PCA-SIFT descriptors in object images based on their matching rates, and then used the maximum likelihood estimation to estimate the probability distribution parameters. Finally we used Bayesian decision theory to implement the image classification. Simulation experiment showed that this algorithm has higher classification accuracy compared with existing SIFT-based image classification methods. It also has minimum storage space requirement and higher computation efficiency.

KeywordsPCA-SIFTClusteringBayesian decisionImage classification

收稿日期：2014-12-30。涂秋潔，碩士生，主研領域：數字圖像處理，模式識別。王晅，教授。

中圖分類號TP3

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.06.052