基于空間特征的多平面支持向量機地形分類?

薛琮琳 郭劍輝 馬玲玲

（南京理工大學計算機科學與工程學院 南京 210094）

1 引言

對于地形識別來說，一般可分為結構化環境或者復雜非結構化環境下的地形識別。結構化環境主要為高速公路與城市化道路等，一般可通過對車道標識和邊界等來進行識別，與結構化環境相比，非結構化環境下因為背景和道路沒有明顯的差別而難利用上述的邊界特征進行識別，而且室外非幾何地形存在有很大的潛在危險性，例如美國在2005年，2006年研發的機遇號、勇氣號火星探測器就因為陷入了松軟的沙土不能移動。所以對野外環境下各類地形的識別研究具有重要意義。

目前對于野外地形環境的分類主要分為兩種:一種是被稱作基于本體感受的分類方法（proprioceptive methods），另一種是基于圖像外形特征的分類方法（appearance—based methods）［1］。基于本體感受的方法，主要是利用觸覺傳感器獲得機器人在行駛的時候與地面相互作用的振動信號來進行分類，基于振動的優點是受光照變化較小，對被遮擋的目標物體也有較好的效果，缺點是需要事先實驗觸覺獲得振動與地形的關系，對未知地形不適用，對于危險地形探測比較危險。基于地形外形的特征的分類方法是利用圖像視覺信息來進行地形識別，圖像包含的信息是最豐富的，相較來說有著巨大的優勢。而基于圖像的視覺分類的好壞，在不同的問題和環境下圖像特征的選取對圖像的表現力有著相當大的影響。

尺度不變換特征轉換（Scale invariant feature transform，SIFT）［14］是 David Lowe在 1999 年提出的，于2004年時完善總結。SIFT是一種利用局部性特征來表達圖像的，它構建出一系列的空間尺度，在相鄰的尺度空間上尋找出極值點，并提取出其位置、尺度、旋轉不變量。對于目標的旋轉遮擋以及光照等問題，SIFT特征都可以取得比較好的效果。而對于地形識別中紋理比較復雜的情況，需要在SIFT特征的基礎上進一步抽象。詞袋模型BOW（bag of words）［2，5］最初是運用在自然語言處理以及信息檢索等領域，BOW忽略了語義上的關系，而是通過構建詞典，利用詞匯的集合的方式來表達文檔。而在2012年，加利福尼亞州圣塔芭芭拉分校（UCSB）機器人研究所的Filichkin與Byl利用BOW，在圖像的SIFT或者SUFR特征的基礎上生成圖像中層特征，結果表明中層特征有著更大的圖像表達能力。其研究成果也實地應用于美軍軍用機器人——小狗（Little—Dog）。受BOW的啟發與基礎上，出現了基層特征的高層語義特征的提取方法，典型的是空間金字塔模型的匹配（spatial pyramid matching，SPM）算法，在局部特征的基礎上，以不同的粒度來劃分金字塔從底層特征上來抽象出高層語義特征。SPM算法的Spatial代表分別統計每一個子區域的特征，最后把所有塊的特征串聯起來形成新的中層特征。在分塊的方式上，采取的類似于層次金字塔的方式，在每一個維度上以不同的尺度上進行統計特征，這是Pyramid部分，最后的Matching部分則是對特征進行匹配。以SIFT作為底層特征，以SPM來提取高級語義能更好地表達圖像。

SSPM算法進一步加強了圖像的表現能力，但是最后的特征向量有可能會發生維數災難，所以需要較快速度的分類器。基于結構風險最小化原則的SVM的分類性能已經獲得了很好的效果，但是由于求解的是一個二次規劃的問題會導致比較慢。LSTSVM［7］算法是利用PSVM的思想，在TWSVM［6，10］的基礎上提出的。將二次規劃問題轉化為一個最小正則問題，與SVM相比具有更高的分類精度和計算速度。

綜上所述，本文以基于SIFT特征的空間金字塔模型特征提取方法SSPM和相關支持向量多平面支持向量機LSTSVM分類來對地形進行有效的分類。

2 SSPM算法

SPM模型出現的背景是BOW模型被大量地用在了圖像表示中。BOW模型對于圖像的表達有很大的提高，但是丟失了特征的位置信息。SPM模型的主要思想:在獲得圖像的底層特征的基礎上，將圖像在每個維度上劃分不同的尺度，以不同的粒度大小來建立空間金字塔模型。

圖1 空間金字塔的構造

假定有點集X與點集Y處在D維的特征空間。以尺度分別為0，1…L來對特征空間進行劃分，對于每一維上，我們可以劃分為2l個相等的間隔。這樣總的特征空間可以產生M=2dl個特征的特征空間塊bin。對于X與Y中的點x1，y1，如果x1和y1在尺度為l形成的bin中，就稱x1與y1是匹配的。定義HlX()i為點集X在尺度l下在第i個bin中的點數，那尺度l下每一個bin中的匹配數定義為

對于尺度l，X與Y的匹配程度定義為

以尺度來分析，直觀地看粒度大的會包含有更復雜的信息，所以大尺度的權重分配小于小尺度的。第l層的權重定義為

綜上，X與Y的匹配程度可以定義為

利用dense sift特征作為底層特征，利用k-mean算法形成d個聚類作為字典D，按照BOW模型的方法把所有圖片的dense sift特征歸屬到相應類別，利用金字塔模型再次進行特征組合。

字典 D=(d1，d2，…，dn)，圖像 I1，I2，對于字典的每一個碼字di有相應的金字塔模型有kL( )Xi，Yi表示圖像I1，I2在di上的匹配關系。對于整個字典來說，圖像I1，I2的匹配程度定義如下:

3 LSTSVM算法

傳統支持向量機在分類性能已經有很好的表現，多平面向量機［12～13，15］是為了解 SVM 過高的計算代價和異或等問題而提出的。而最小二乘相關支持向量機是在孿生支持向量機的基礎上提出的。因為金字塔模型的向量維數會隨著層數增大，為了更好的分類性能和訓練時間采取比較快速的LSTSVM來進行分類。LSTSVM是采用了和PSVM相同的思路來求解兩個平面，具有較快的分類速度和精度。

假定特征空間為n維，定義為Rn，樣本數量為m=m1+m2，m1為正類樣本數，m2為負類樣本數。設兩個超平行平面分別為

其中，w1，w2是超平面權重向量，e1，e1為全為1的列向量，b1，b2是偏差。

令矩陣 A=m1×n代表正類樣本集，矩陣B=m2×n代表負類樣本集。

目標函數為最小化以下問題:

最小二乘相關支持向量機使用松弛變量的二范數形式代替孿生支持向量機中的?1范數形式，這樣使得原本約束條件中的 y≥0可以被省略［9］。將約束條件轉換為目標函數，第一個優化問題變為

以第一個平面為例，式（8）對w和b求偏導可得:

把 w1，w2，b1和 b2帶入式（5）即可以得到分類平面。

4 結合算法

因為是應用于圖像識別，所以使用dense SIFT為底層特征［8］，經金字塔模型組合抽象得到高層特征，以該特征作為樣本輸入。需要考慮的是組合后的特征維數可能會很大。對于金字塔模型來說，我們假定設置M個碼字的字典和L層金字塔，那最后所得的金字塔特征維數為。相比于SVM來說，LSTSVM可以取得較好的分類效果和時間優勢，采用LSTSVM驗證再對底層特征抽象后的特征對地形的識別率影響。

算法具體步驟:

1）對圖片提取dense SIFT特征；

2）利用k-mean算法將dense SIFT特征聚類，形成字典D；

3）利用字典D將每張圖片的SIFT特征對應到相應的字典項當中；

4）對圖像進行金字塔模型劃分，并提取出高級語義的特征；

5）利用網格搜索法計算LSTSVM的最優參數δ；

6）利用最優參數δ與訓練集訓練分類器LSTSVM；

7）利用訓練得到的分類器進行算法驗證，分析性能。

5 實驗結果

關于地形分類的專用數據庫比較少，實驗數據庫采用的是軍事醫學科學院衛生裝備研究所提供的DSI數據庫，數據庫總共包含有8種不同典型的地形路面:瀝青路面、泥地、草地、瓷磚、碎石、大碎石、沙地和落葉覆蓋。每類有300幅圖像樣本，每個樣本分辨率為256×256，圖片在不同光照和天氣條件下獲取。

實驗在Matlab R2014a上，每類圖片隨機選取200幅作為訓練數據，其余為測試數據。底層特征采取的是4×4網格結構，統計了8個方向的梯度sift描述子，每個樣本可以提取出961個dense sift特征，實驗結果如表1～3所示。

圖2 分別為瀝青路面、泥地、草地、瓷磚、碎石、大碎石、沙地和落葉覆蓋

表1 Sift特征與SVM分類結果 /Acc±Std（%）

表2 16碼字1層金字塔與LSTSVM分類結果 /Acc±Std（%）

表3 16碼字3層金字塔與LSTSVM分類結果 /Acc±Std（%）

實驗結果顯示，直接通過SVM分類時，會出現某些類別分類嚴重錯誤。比如Asphalt和floor（0.5327），Asphalt和 Grass（0.3600），Floor和 Sand（0.3764）和 Wood chips（0.4690）等，其他較低的分類精度有 Asphalt和 Dirt（0.7650），Gravel和 Wood chips（0.7254），說明特征的圖像表達能力有待提高；表2可以看出經過金字塔模型形一層形成的特征與LSTSVM結合的分類，上述出現嚴重分類錯誤的幾類已經得到了極大的改善，而其他類的分類效果也得到了提高，標準差小于表1，說明經過進一步的提高底層特征形成的語義能很好地改善對地形的識別；表3是形成三層金字塔的特征與LSTSVM相結合的結果，可以的看出經過進一步的特征組合再次提高識別率，雖然提升相對較小但是總體識別率都達到了較好的效果，且標準差小于表1和表2，結果穩定。

從表4中可以看出，通過對特征的進行SPM模型化之后，總體識別率得到了提高，而且其中每一類的分類精度都得到了保證，不會出現個別類出現很多偏差的情況。而且可看出使用LSTSVM可以降低訓練時間，對地形識別的工程應用方面有著很大的幫助。

表4 時間比較

6 結語

本文針對地形類型分類中，提出了一種結合了金字塔模型和LSTSVM的地形分類算法。實驗證明，使用的SSPM算法相比于直接使用底層特征提高了分類精度，而且避免了個別類上分類精度的上的偏差，相比于傳統的SIFT特征識別有著明顯優勢，總體上提高準確率，而且標準差減小，結果比較穩定。LSTSVM相比于SVM有更高的分類精度，有效地降低了對于分類層數增加帶來的計算成本，對于工程實踐應用有著一定意義。綜上，對于野外非結構環境下的地形識別，SSPM算法與LSTSVM相結合的方法是有著極高的實踐價值。