本站小編為你精心準備了有效圖像塊描述子分析參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

《軟件學報》2015年第十一期

1圖像特征表示方法概述

設計圖像的特征表示是計算機視覺中一項非常基本的研究內容,圖像的分類、檢索、標注等工作都是以提取圖像特征為初始步驟,好的特征表示可以在相關圖像分析中取得更佳的效果.因此,圖像特征的設計與構造,直接影響算法的性能.而如何定義一個好的圖像特征卻是非常困難的:一方面,設計的圖像特征對于同一類別下圖像之間的變化(比如尺度、光照變化、對象位置變化等)要有足夠的魯棒性;另一方面,設計的圖像特征要具備足夠的判別性來處理不同類別間圖像的變化.近年來,研究者提出了大量的底層特征用于各種圖像分析任務,其中最具有代表性的是基于梯度朝向直方圖的SIFT(scale-invariantfeaturetransform)[1]和HOG(histogramoforientedgradient)[2].盡管這類特征取得了一定意義的成功,但研究者發現,這類單一的底層特征并不足以在某些應用上達到更好的效果,因此提出了一類中間層的圖像特征表示方法.其中,BoW(bagofwords)[3]是這類圖像特征表示方法的典型代表,該方法在場景分類中獲得了較好的性能.BoW算法生成圖像特征表示分為3個過程:圖像底層特征的獲取、學習過完備字典和計算圖像的碼字直方圖表示.然而,BoW方式并沒有考慮特征向量在圖像空間上的位置關系,使得其特征描述能力并沒有達到最大化.為了彌補這一缺陷,空間金字塔匹配(spatialpyramidmatching,簡稱SPM)[4]方法通過在一幅圖像的不同層次上計算碼字直方圖,形成了一個BoW多層特征,將BoW模型與圖像空間進行合理融合.然而,由于SPM方法利用直方圖交核函數來度量兩幅圖像間的相似度,導致無法產生低維度的圖像特征表示,而且需要完整計算訓練集圖像間相似度的Gram矩陣,因此,其算法復雜度為O(n2)(其中,n為訓練集中圖像的個數).為了解決這一問題,有效匹配核算法(efficientmatchkernel,簡稱EMK)[5]在碼字間相似性的基礎上構造了一個低維特征映射空間,整個圖像的特征可以表示為碼字映射在這個低維特征空間后的平均,且可以采用線性SVM方法訓練分類器,在圖像分類應用中獲得了非常不錯的效果.然而,有效匹配核算法仍然依賴于人為定義的圖像局部特征(如SIFT或HOG),只不過是通過計算有限維空間的局部線性特征表示來推出整體圖像的線性特征.

Bo等人擴展了有效匹配核算法并提出了核描述子(kerneldescriptor,簡稱KD)[6]方法.這種方法只需定義任意兩個局部圖像塊之間的相似性,且該相似性函數滿足核函數定義.由于每個核函數都隱性定義了一個映射,它將圖像塊映射為再生核希爾伯特空間(reproducingkernelHilbertspace,簡稱RKHS)中一個非常高維的向量,這樣,核函數可以表示為RKHS中兩個高維向量的內積,通過核主成分分析(kernelprincipalcomponentanalysis,簡稱KPCA)[7]算法,可以由核函數推出圖像塊特征的有限維線性表示.這種低維空間中的表示就稱為核描述子,并且采用EMK算法將其推廣到整個圖像的特征表示.盡管核描述子方法的設計思想較為新穎,但仍然存在計算復雜度過高這一缺陷,限制了其在大規模圖像數據庫上的應用.事實上,在KPCA方法的離線階段,所有聯合基向量對之間的相似性都需要計算,這是非常耗時的.更重要的是:在線階段計算一個新圖像塊的特征映射時,該圖像塊與所有聯合基向量之間的相似性也是需要計算的,而這實際上是不需要的.Xie等人[8]通過使用不完整Cholesky分解替代KPCA算法,成功地解決了這個問題,并且通過迭代,應用不完整Cholesky分解算法表示整個圖像特征[9].但文獻[8,9]中,通過不完整Cholesky分解得到的標志聯合基向量并沒有對應實際的圖像塊,因此,其產生的特征判別能力并沒有最大化地得到利用.

Wang等人提出了有監督的核描述子方法[10],該方法利用訓練集中的圖像類標來輔助設計底層圖像塊特征.盡管他們利用該特征取得了不錯的分類效果,但這個算法運行過程中需要大量有類標的圖像,并且對象優化函數求解過程復雜,時間復雜度過高.除了上述生成圖像底層特征表示的方法以外,另外一類構成圖像特征的方法基于深度學習理論.2006年,Hinton等人[11,12]提出了用于深度信任網絡(deepbeliefnetwork,簡稱DBN)的無監督學習算法,DBN的多層結構,使得它能夠學習得到層次化的特征表示,實現自動特征抽象,文獻[12]將DBN模型成功用于手寫數字識別應用上.Bengio等人在文獻[13]中提出了基于自編碼器(auto-encoder)[14]的深度學習網絡,在手寫數字識別圖像數據庫上得到了類似的實驗結果.另外,文獻[1517]提出了一系列基于稀疏編碼的深層學習網絡,在圖像應用中取得了一定的成功.LeCun等人用誤差梯度設計并訓練卷積神經網絡(convolutionalneuralnetwork,簡稱CNN),其在圖像分類,特別是手寫體字符識別應用中得到優越的性能.在此基礎上,Krizhevsky等人[21]將CNN模型應用到分類大規模ImageNet圖像數據庫,更加充分地顯示了深度學習模型的表達能力.盡管在深度學習模型下獲得的圖像特征有很強的判別表示能力,但其要求計算機硬件條件較高,單機環境下很難實現.除此之外,更加詳細地介紹圖像特征描述子領域的綜述可以參考文獻[23].本文在大數據時代背景下,為了能夠快速得到圖像塊的線性特征表示,提出了有效圖像塊描述子(efficientpatch-leveldescriptor,簡稱EPLd)方法.該方法在不完整Cholesky分解基礎上,可以自動地進行圖像塊篩選,對于求解新圖像塊的線性特征表示,只需計算它和一小部分基圖像塊的相似性就足夠了.有了圖像塊的特征表示之后,一幅圖像就對應著一個圖像塊特征的集合,該集合可以看作是特征空間中基于某個分布的樣本集,這樣,兩幅圖像之間的差異可以看作兩個分布的距離.本文采用基于高維概率分布的MMD距離[24]進行估算,進而計算兩幅圖像間的相似性.本文首先介紹核描述子方法,然后給出有效圖像塊描述子算法的具體實現過程以及如何利用MMD距離計算兩幅圖像的相似性,并在幾個著名的圖像分類數據庫上進行實驗,最后給出工作的結論和展望.

2核描述子方法簡介

核描述子方法是對圖像像素點屬性(梯度/形狀/顏色+位置)基礎上生成的聯合基向量應用KPCA方法,從而計算新圖像塊的有限維特征表示.為了方便敘述,本文采用像素點的梯度屬性來介紹核描述子方法.通過公式(2)可以看到,核描述子方法的主要缺陷有以下3點:(1)算法計算復雜度高,因為需要對dodp維的聯合基向量形成的Gram矩陣計算特征值分解,如果聯合基向量的維度過高或者個數過多,KPCA算法甚至無法實施;(2)對聯合基向量進行KPCA獲得的tij并不是稀疏的,這也就意味著在計算新圖像塊的特征表示時,需要和所有的聯合基向量進行在線計算,所以算法需要存儲全部的聯合基向量;(3)算法無法進行特征選擇,即,并不知道聯合基向量中哪些樣本最具代表性.

3有效圖像塊描述子算法

針對核描述子方法的3點不足之處,文獻[8]解決了其主要缺陷的第一、第二兩點,但是文獻[8]在本質上仍然使用聯合基向量,所以沒有明確地進行特征選擇,即,找出哪些圖像塊是最具代表性的,使得其特征表示能力并沒有達到最大化.為了更加完善地解決核描述子方法的缺陷,本文提出了一種新的圖像塊特征表示方法,稱為有效圖像塊描述子.該方法基于對圖像塊相似度矩陣執行不完整Cholesky分解。總體上來說,有效圖像塊描述子算法由兩部分構成:1)首先從訓練圖像集中均勻抽取足夠的圖像塊,然后在這些圖像塊形成的Gram矩陣上執行不完整Cholesky分解算法.如果設定N代表圖像塊的個數,M代表分解后矩陣的秩,通常情況下,M<<N.這樣做的好處有兩點:首先,在分解過程中只需要按需計算O(MN)個Gram矩陣元素的值;其次,對Gram矩陣執行Cholesky分解的時間復雜度為O(M2N),遠遠低于KPCA算法的O(N3).2)經過第1步分解步驟之后,選擇出了M個最具代表性的基圖像塊,新圖像塊的特征表示僅僅通過O(M)次計算就可以得到.算法的具體步驟將在以下部分詳細介紹.

3.1Gram矩陣的低秩近似半正定的Gram矩陣K可以分解為GGT,所以不完整Cholesky分解的目標就是找到一個矩陣G,其大小為NM,使得TGG在M足夠小的情況下近似K.在執行不完整Cholesky分解算法的過程中,選擇出M個最具代表性的基圖像塊,利用所有圖像塊和這M個基圖像塊之間的相似性,可以近似恢復Gram矩陣K.這里,M的值是可以通過算法在線確定的,由算法中提前給定的近似精度參數來控制.關于不完整Cholesky分解的詳細執行過程可以參考文獻[26],其中,作為輸入參數的Gram矩陣K實際上是按需計算的,即,算法執行過程中需要用到哪兩個訓練圖像塊間的相似度,就按照公式(1)計算得到.算法執行后,就得到了一些具有代表性的基圖像塊,用向量P保存基圖像塊的索引序號,同時得到了矩陣G,使得.TGGK

3.2構造圖像塊特征映射算法一旦獲得了NM的矩陣G,新圖像塊的特征(有效圖像塊描述子)就可以由G構造.其中,新圖像塊特征維度大小由M確定,每一維度i的值可由新圖像塊與P(i)所指示的基圖像塊間相似性K(newpatch,P(i))恢復得到。通過算法1可以看到:選擇出的M個最具代表性的基圖像塊可以看成是一系列局部圖像塊的非線性濾波器,將每個新圖像塊和這些基圖像塊進行相似性度量的過程,也可看成是對這個新圖像塊進行特征提取的過程.另外,針對圖像塊相似度矩陣執行不完整Cholesky分解往往可以保證獲得精度非常高的低秩近似,且分解過程中只與某些訓練樣本(圖像塊)有關.也就是說,利用這些訓練樣本就可以很好地近似恢復相似度矩陣,所以訓練集中的圖像塊具有不同程度的重要性.因此,我們稱重要性最高的前M個圖像塊為“最具代表性”的基圖像塊.為了更加形象地展示這些重要的基圖像塊,我們在Scene-15圖像庫上提取了最重要的前16個基圖像塊,如圖1所示(每個圖像塊由其像素點的梯度幅值來表示).可以看到,每個圖像塊都包含了豐富的邊緣和紋理信息.本文提出的有效圖像塊描述子算法不只繼承了文獻[8]的有效性,而且很好地解決了核描述子算法中的第3點缺陷,最大限度地發揮了圖像塊特征的判別能力.

4利用MMD距離計算圖像間的相似性

基于算法1,每一個圖像塊都可以用有效圖像塊描述子來表示.一幅圖像通過稠密采樣確定很多關鍵點,每一個關鍵點都對應著一個局部的圖像塊,因此,一幅圖像就對應著一個局部特征的集合.假定圖像I1包含m個圖像塊,則其特征集合可以表示為Fp(patchp1,patchp2,…,patchpm),圖像I2包含n個圖像塊,其特征集合表示為Fq(patchq1,patchq2,…,patchqn).Fp可以看作特征空間中來自分布p的一個樣本集,同樣,Fq也可以看作是來自分布q的樣本集.這樣,圖像I1與I2之間的差異性就可以由p和q兩個分布的距離表示.當然,這兩個概率分布之間的距離只能通過這兩個樣本集進行估算.為此,本文采用基于高維概率分布的MaximumMeanDiscrepancy(MMD)距離[24]進行估算.MMD距離可以看作是將兩個概率分布,通過非線性核函數映射到再生核希爾伯特空間(RKHS)后均值的距離.對于上述分布p和q的MMD距離估計可由公式(3)計算。單純地利用公式(3),并沒有考慮局部特征在整幅圖像上的空間分布信息.為了解決這個問題,本文首先采用空間金字塔方法將整幅圖像進行逐層劃分;然后,在兩幅圖像每個層次對應的小圖像上計算它們之間的MMD距離;最終,將所有層次的MMD距離按照其對應層次的權重進行匯總求和,然后度量兩幅圖像I1與I2之間的差異性.

5實驗

本文使用像素點的梯度、形狀和顏色屬性分別構造基于梯度的有效圖像塊描述子(EPLd-G)、基于形狀的有效圖像塊描述子(EPLd-S)和基于顏色的有效圖像塊描述子(EPLd-C).為了測試有效圖像塊描述子算法的性能,分別在3個著名的圖像分類數據庫(Scene-15,Caltech-101[28]和UIUC-8[29])上做了實驗.在接下來的實驗中,計算3個不同類型的有效圖像塊描述子都是首先將圖像按照固定比率縮放到不超過300300像素點;特別地,在計算EPLd-G和EPLd-S時,將縮放后的圖像中的像素點的灰度值標準化為[0,1]范圍.圖像塊通過每隔8個像素點的稠密采樣方式從訓練集圖像中進行抽取,大小為1616像素點.EPLd-All是將EPLd-G,EPLd-S和EPLd-C這3個描述子串接起來形成的.訓練線性SVM分類器使用LIBLINEAR[30],其中,圖像間的相似性利用MMD距離來定義.在計算MMD時,將圖像按照11,22和33分為3個層次來匯總求和,尺度參數在不同的數據庫上利用交叉驗證方法確定.所有的實驗均重復10次,每次的訓練集和測試集都隨機抽取確定,將10次分類準確率的平均值和方差記錄下來.實驗中的其他參數從公平比較的角度考慮,與文獻[6,8]設置相同.

5.1Scene-15Scene-15場景數據庫包含4485張圖片,這些圖片分屬15個類別,有室內場景和室外場景,每一個類別包含200張~400張圖片不等.按照慣例,從每個類別中隨機抽取100張圖片作為訓練,剩余圖片作為測試.在算法中設置Pivots的個數為200,即,利用不完整Cholesky分解選出200個最具代表性的基圖像塊來構造維度為200的有效圖像塊描述子.實驗結果列在表1中(其中,KD代表核描述子方法[6],EKD代表有效核描述子方法[8],EPLd代表本文提出的有效圖像塊描述子方法),EPLd方法獲得在這個數據庫上的最佳分類準確率(87.0%).另外,EPLd方法在所有4種不同情況(梯度、形狀、顏色和上述3種屬性的匯總)下的性能均超過了文獻[6,8].在實驗中,除了測試分類準確率來體現EPLd的判別能力,還通過不同維度下測試分類準確率來體現EPLd的有效性.我們發現,在特征維度只有50維的情況下也獲得了接近最優分類準確率的性能,這充分體現出EPLd算法的有效性和健壯性.事實上,通過表2可以看到:特征維度從50維增加到300維,分類準確率并沒有得到明顯的提升.造成這一現象的原因是,不完整Cholesky分解容易獲得高質量的低秩近似.表2中的數據表明:即使是50維的低秩近似也足以體現Gram矩陣中的關鍵信息,而這些關鍵信息直接決定了分類的性能.在后面的實驗中,從算法效率的角度考慮都使用了100維的特征表示.

5.2Caltech-101Caltech-101圖像數據庫包含9144張圖片.這9144張圖片隸屬于101個對象類別外加一個背景類別,每個類別中的圖片在31張~800張不等.表3中,將EPLd與其他有代表性的描述子算法進行了對比.同樣根據慣例,每個類別隨機挑出30張圖片進行訓練,從剩余圖片中挑選不超過50張進行測試.可以看到:EPLd算法達到了最佳的分類準確率(77.1%),甚至在僅僅使用梯度屬性的情況下(EPLd-G)也達到了非常不錯的分類效果(73.7%).

5.3UIUC-8UIUC-8圖像數據庫包含1579張圖片,這1579張圖片隸屬于8個運動類別,每個類別下包含圖片137張~250張不等.按照慣例,隨機從每個類別中抽取70張圖片進行訓練,從剩余圖片中挑選60張進行測試.分類準確率結果列于表4中.通過表4可以看到,EPLd-All非常接近最佳分類準確率(87.2%vs.87.23%).在實驗部分的最后,本文對比了構造3種不同描述子(EPLdvs.KDvs.EKD)的計算效率.其中,最耗時的是形狀特征,一幅標準圖像(最大300300分辨率,圖像塊大小為1616像素點,圖像塊間隔8個像素點)上的EPLd-S與EKD-S描述子在Matlab環境下計算需要耗時2s,而KD-S需要耗時2.5s.對于梯度特征,EPLd-G與EKD-G描述子耗時0.9s,KD-G耗時1s.以上對比結果列在表5中.表5中的對比結果是在生成100維特征情況下得到的,如果提高特征的維度,EPLd與EKD的計算效率提升相對于KD會表現得更加明顯.另外一點需要指出的是:EPLd與EKD的計算耗時雖然基本相同,但EPLd描述子的特征判別能力相對于EKD描述子要強很多,這一點通過在3個圖像數據庫上的實驗對比結果可以得到印證.所以,綜合考慮,EPLd描述子無論在計算效率還是在判別能力上都要優于EKD和KD描述子.

6結束語

本文提出了有效圖像塊描述子算法.該算法的主要思想是:通過不完整Cholesky分解對圖像塊的相似性進行逆向學習,選出具有代表性的基圖像塊.這些基圖像塊可以看成是一系列的非線性濾波器,將每個新圖像塊和這些基圖像塊進行相似性度量的過程,就是對這個新圖像塊進行特征提取的過程.另外,本文還設計了更為優秀的基于局部特征的整體圖像相似性度量,也就是利用MMD距離計算兩幅圖像之間的相似性,該相似性度量方式不僅能夠反映局部圖像特征之間的相似性,而且能夠有效地利用特征的空間分布信息,從而最大限度地提高整體圖像相似性度量的精確度和敏感度.實驗結果顯示:EPLd方法相對于KD方法和其他一些代表性的方法,在3個著名圖像分類數據庫上都獲得了非常不錯的性能.

作者：謝博鋆 朱杰 于劍 單位：交通數據分析與挖掘北京市重點實驗室 河北省機器學習與計算智能重點實驗室 中央司法警官學院 信息管理系