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

薛琮琳 郭劍輝 馬玲玲

（南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210094）

1 引言

對(duì)于地形識(shí)別來說，一般可分為結(jié)構(gòu)化環(huán)境或者復(fù)雜非結(jié)構(gòu)化環(huán)境下的地形識(shí)別。結(jié)構(gòu)化環(huán)境主要為高速公路與城市化道路等，一般可通過對(duì)車道標(biāo)識(shí)和邊界等來進(jìn)行識(shí)別，與結(jié)構(gòu)化環(huán)境相比，非結(jié)構(gòu)化環(huán)境下因?yàn)楸尘昂偷缆窙]有明顯的差別而難利用上述的邊界特征進(jìn)行識(shí)別，而且室外非幾何地形存在有很大的潛在危險(xiǎn)性，例如美國(guó)在2005年，2006年研發(fā)的機(jī)遇號(hào)、勇氣號(hào)火星探測(cè)器就因?yàn)橄萑肓怂绍浀纳惩敛荒芤苿?dòng)。所以對(duì)野外環(huán)境下各類地形的識(shí)別研究具有重要意義。

目前對(duì)于野外地形環(huán)境的分類主要分為兩種:一種是被稱作基于本體感受的分類方法（proprioceptive methods），另一種是基于圖像外形特征的分類方法（appearance—based methods）［1］?；诒倔w感受的方法，主要是利用觸覺傳感器獲得機(jī)器人在行駛的時(shí)候與地面相互作用的振動(dòng)信號(hào)來進(jìn)行分類，基于振動(dòng)的優(yōu)點(diǎn)是受光照變化較小，對(duì)被遮擋的目標(biāo)物體也有較好的效果，缺點(diǎn)是需要事先實(shí)驗(yàn)觸覺獲得振動(dòng)與地形的關(guān)系，對(duì)未知地形不適用，對(duì)于危險(xiǎn)地形探測(cè)比較危險(xiǎn)?；诘匦瓮庑蔚奶卣鞯姆诸惙椒ㄊ抢脠D像視覺信息來進(jìn)行地形識(shí)別，圖像包含的信息是最豐富的，相較來說有著巨大的優(yōu)勢(shì)。而基于圖像的視覺分類的好壞，在不同的問題和環(huán)境下圖像特征的選取對(duì)圖像的表現(xiàn)力有著相當(dāng)大的影響。

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

SSPM算法進(jìn)一步加強(qiáng)了圖像的表現(xiàn)能力，但是最后的特征向量有可能會(huì)發(fā)生維數(shù)災(zāi)難，所以需要較快速度的分類器?；诮Y(jié)構(gòu)風(fēng)險(xiǎn)最小化原則的SVM的分類性能已經(jīng)獲得了很好的效果，但是由于求解的是一個(gè)二次規(guī)劃的問題會(huì)導(dǎo)致比較慢。LSTSVM［7］算法是利用PSVM的思想，在TWSVM［6，10］的基礎(chǔ)上提出的。將二次規(guī)劃問題轉(zhuǎn)化為一個(gè)最小正則問題，與SVM相比具有更高的分類精度和計(jì)算速度。

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

2 SSPM算法

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

圖1 空間金字塔的構(gòu)造

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

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

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

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

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

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

3 LSTSVM算法

傳統(tǒng)支持向量機(jī)在分類性能已經(jīng)有很好的表現(xiàn)，多平面向量機(jī)［12～13，15］是為了解 SVM 過高的計(jì)算代價(jià)和異或等問題而提出的。而最小二乘相關(guān)支持向量機(jī)是在孿生支持向量機(jī)的基礎(chǔ)上提出的。因?yàn)榻鹱炙Ｐ偷南蛄烤S數(shù)會(huì)隨著層數(shù)增大，為了更好的分類性能和訓(xùn)練時(shí)間采取比較快速的LSTSVM來進(jìn)行分類。LSTSVM是采用了和PSVM相同的思路來求解兩個(gè)平面，具有較快的分類速度和精度。

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

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

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

目標(biāo)函數(shù)為最小化以下問題:

最小二乘相關(guān)支持向量機(jī)使用松弛變量的二范數(shù)形式代替孿生支持向量機(jī)中的?1范數(shù)形式，這樣使得原本約束條件中的 y≥0可以被省略［9］。將約束條件轉(zhuǎn)換為目標(biāo)函數(shù)，第一個(gè)優(yōu)化問題變?yōu)?/p>

以第一個(gè)平面為例，式（8）對(duì)w和b求偏導(dǎo)可得:

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

4 結(jié)合算法

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

算法具體步驟:

1）對(duì)圖片提取dense SIFT特征；

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

3）利用字典D將每張圖片的SIFT特征對(duì)應(yīng)到相應(yīng)的字典項(xiàng)當(dāng)中；

4）對(duì)圖像進(jìn)行金字塔模型劃分，并提取出高級(jí)語義的特征；

5）利用網(wǎng)格搜索法計(jì)算LSTSVM的最優(yōu)參數(shù)δ；

6）利用最優(yōu)參數(shù)δ與訓(xùn)練集訓(xùn)練分類器LSTSVM；

7）利用訓(xùn)練得到的分類器進(jìn)行算法驗(yàn)證，分析性能。

5 實(shí)驗(yàn)結(jié)果

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

實(shí)驗(yàn)在Matlab R2014a上，每類圖片隨機(jī)選取200幅作為訓(xùn)練數(shù)據(jù)，其余為測(cè)試數(shù)據(jù)。底層特征采取的是4×4網(wǎng)格結(jié)構(gòu)，統(tǒng)計(jì)了8個(gè)方向的梯度sift描述子，每個(gè)樣本可以提取出961個(gè)dense sift特征，實(shí)驗(yàn)結(jié)果如表1～3所示。

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

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

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

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

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

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

表4 時(shí)間比較

6 結(jié)語

本文針對(duì)地形類型分類中，提出了一種結(jié)合了金字塔模型和LSTSVM的地形分類算法。實(shí)驗(yàn)證明，使用的SSPM算法相比于直接使用底層特征提高了分類精度，而且避免了個(gè)別類上分類精度的上的偏差，相比于傳統(tǒng)的SIFT特征識(shí)別有著明顯優(yōu)勢(shì)，總體上提高準(zhǔn)確率，而且標(biāo)準(zhǔn)差減小，結(jié)果比較穩(wěn)定。LSTSVM相比于SVM有更高的分類精度，有效地降低了對(duì)于分類層數(shù)增加帶來的計(jì)算成本，對(duì)于工程實(shí)踐應(yīng)用有著一定意義。綜上，對(duì)于野外非結(jié)構(gòu)環(huán)境下的地形識(shí)別，SSPM算法與LSTSVM相結(jié)合的方法是有著極高的實(shí)踐價(jià)值。