基于字典學習與稀疏表示的非結構化道路分割方法

肖 良，戴 斌，吳 濤，方宇強

(國防科技大學機電工程與自動化學院，長沙410072)

道路分割是自主車 (Autonomous Land Vehicle，ALV)的關鍵技術之一。根據(jù)所處道路環(huán)境的不同，又可分為結構化道路和非結構化道路。結構化道路是指存在明顯的道路標志(如車道線等)的道路，如高速公路。結構化道路的檢測可以通過提取道路標志或道路邊界的方式完成，目前已能較好地解決這一問題。而在復雜非結構化道路(如越野環(huán)境，鄉(xiāng)村道路等)環(huán)境下，路面狀況復雜多變，且不存在明顯的路邊，使得這一問題難度大大增加。解決復雜非結構化環(huán)境下道路檢測問題常用的傳感器有激光雷達、立體視覺和單目視覺等。基于激光雷達和立體視覺的道路檢測主要通過分析三維場景，得到道路區(qū)域，或者說是可通行區(qū)域。這種方法在路邊存在明顯凸起或者凹陷障礙時較為有效，但在復雜非結構化環(huán)境下，可能存在路邊在高度上沒有明顯差別，但卻不可通行的情況(如沼澤地等)，這種情況上述方法很難得到有效解決，且激光雷達設備價格昂貴，不利于控制機器人的成本。而基于單目視覺的道路檢測既有設備簡單且信息量充裕等優(yōu)點而被廣泛應用。

基于單目視覺的道路分割需要根據(jù)采集到的單目圖像實時地分割出道路區(qū)域或者得到道路邊界線以實現(xiàn)視覺導航?；趩文恳曈X的道路分割主要有基于道路模型和基于圖像局部特征兩種?；诘缆纺Ｐ偷姆椒ㄊ紫燃僭O一個道路模型，然后根據(jù)圖像中的邊沿、線段等特征匹配最優(yōu)的模型參數(shù)，消失點［1］檢測也常用于該類算法中，但在復雜的非結構化環(huán)境下，由于道路起伏較大，形狀復雜多變等原因?qū)е逻@類方法效果欠佳?；趫D像局部特征的方法包括聚類、閾值分割、區(qū)域生長等，這種方法通常利用道路與非道路圖像的亮度、顏色或局部紋理等特征進行分類。這種方法對道路的形狀不敏感，但其缺點是極易受光照、陰影、水坑的影響。為更好的解決復雜非結構化道路分割問題，許多研究工作開始引入學習的方法。AdaBoost［2］，SVM及NN［3］等被用來尋找最優(yōu)分類器，大大提高了算法的適應性，但是學習的引入使特征的選擇與訓練樣本選取至關重要。

本文提出了一種新穎的基于字典學習與稀疏表示的道路分割算法，該算法以圖像小片作為處理單元，取小片的所有像素的RGB分量的級聯(lián)作為其特征，通過人工選擇一些典型的路面圖像作為訓練樣本，學習得到初始字典，再根據(jù)車輛前方的一小塊圖像通過在線字典學習對字典進行實時更新，并通過對測試圖像的每個局部圖像小片求解在該字典上的稀疏編碼問題，最終通過在實時字典上的重構誤差判斷該小片是否為道路。該算法通過字典學習與稀疏編碼對圖像小片進行分類，具有良好的自適應性和魯棒性，較好地解決了復雜環(huán)境下非結構化道路分割問題。

1 相關工作

基于稀疏表示的分類器(SRC)最早由Wright等［4］提出，并在人臉識別和圖像分類等領域成功應用［4－7］。文獻［8］中提出了紋理的稀疏模型，該模型利用局部紋理小片可以在一組自適應冗余字典上稀疏表示的假設，利用局部紋理小片在不同紋理字典上的重構精度進行分類獲得了較好的效果。文獻［9］中提出了一種基于稀疏表示的異常事件檢測算法，利用事件在字典上的可重構性進行異常檢測。

基于稀疏表示的分類算法［8］一般包括字典學習和稀疏表示(稀疏編碼)兩部分。相對小波分析中的預定義基，稀疏表示中的字典通過訓練樣本學習得到，且可以是超完備(over－completed)的，這大大提高了自適應性。與矢量量化(vector quantization，VQ)對比，稀疏表示中的系數(shù)求解僅需滿足稀疏性約束，而VQ的系數(shù)則必須為(0，0，…1，0，…，0，0)的形式，所以稀疏表示可以看作是VQ的泛化與推廣，這使得表示精度大大提高，從而提高了利用表示誤差進行分類的分類精度。

1.1 稀疏表示

設信號x∈Rm，信號的稀疏表示就是將信號表示為在字典D=［d1d2…dp］(其中d1，d2，…，dp稱為字典中的原子)上的稀疏線性組合，即線性組合系數(shù)的非零項較少。信號稀疏表示問題通過求解如下優(yōu)化問題實現(xiàn):

式中:‖·‖0為向量的零范數(shù)，即向量中非零元個數(shù)，即‖α‖0=|{k|αk≠0}|(|·|表示集合的勢);T為稀疏度約束。

上述優(yōu)化問題是一個NP問題，目前求解該問題主要有兩種思路:一是通過貪婪算法求解近似最優(yōu)解，如OMP［10］算法等;二是通過用1范數(shù)代替式(1)中的零范數(shù)將其轉(zhuǎn)化為凸優(yōu)化問題求解［11］。

1.2 字典學習

考慮由n個訓練樣本組成的訓練集X=［x1，x2，…，xn］∈Rm×n，字典學習就是需要得到由一組原子構成的字典D使得所有的訓練樣本都能在該字典上稀疏表示，字典學習可以形式化為如下優(yōu)化問題:

式中:集合D={D∈Rm×p|?j∈［1，p］，‖dj≤1}，A=［α1，α2，…，αn］;‖·‖F(xiàn)表示矩陣Frobenius范數(shù)。

上述優(yōu)化問題對于(D，A)不是凸的，但是當D和A中一個固定時，相對另一個卻是凸的，所以求解該問題一般使用交替優(yōu)化的方法，即先在D固定的情況下對A進行優(yōu)化，然后在A固定的情況下對D進行優(yōu)化，不斷交替地對D和A進行優(yōu)化直至收斂［12，13］。

固定D求解A可以分解為n個如式(1)所示的稀疏編碼問題。固定A求解D的字典更新有多種方法，MOD［14］算 法中采用式 D = XA(AAT)－1更新字典。K－SVD［15］算法每次更新D中的一列，同時更新A中相應行中的非零項，且這一過程可以通過奇異值分解(SVD)求解。文獻［13］提出將問題轉(zhuǎn)化為拉格朗日對偶形式后再利用牛頓法或共軛梯度法求解。文獻［12］還提出了一種在線字典學習算法(ONDL)，采用隨機梯度下降的方法求解，該算法的優(yōu)點是效率大大提高，且支持增量式字典學習。

本文從文獻［8－9］中受到啟發(fā)，希望將SRC應用于道路分割問題，但是在道路分割問題中，非路面圖像千變?nèi)f化，難以采用統(tǒng)一的稀疏模型進行描述。所以本文采用了文獻［9］中的單分類框架，僅建立路面圖像的稀疏模型，即路面圖像小片的一組稀疏表示字典，然后通過求解測試圖像小片在該字典上的稀疏表示誤差將其分類為路面或非路面。

2 本文方法

本文提出的基于字典學習與稀疏表示的道路分割算法以圖像小片(patch)為處理單元(文中采用的小片大小為8×8像素)，將圖像小片所有像素的各顏色通道值作為特征向量(共8×8×3= 192維)，該特征完整地描述了圖像小片的所有信息，綜合了小區(qū)域內(nèi)所有像素的顏色特征及其鄰接關系。此外小片還可以采用有重疊和無重疊兩種模式。由于在復雜環(huán)境下非結構化道路分割中，正負樣本不對等，非道路圖像千變?nèi)f化，其局部小片可能遍布整個特征空間，導致其樣本無從選起，或者難以得到具有代表性的樣本。解決此類問題一般采用基于單類樣本的學習算法，將其當作單分類問題(one－class classification)，或稱為異常檢測問題。本文即采用類似單分類的思想處理復雜環(huán)境下道路分割問題。

該算法首先采用人工選取的典型道路圖像作為訓練樣本，訓練道路圖像的稀疏表示字典D0。為了提高字典的適應性，在運行階段需要對字典進行不斷更新，考慮到自主車總是保持在路上這一先驗知識，我們采用車輛前方的一小塊區(qū)域作為實時監(jiān)督信號通過增量學習的方式更新字典，在此基礎上，針對測試圖像的每個小片，求解其在實時字典D上的稀疏編碼問題，利用稀疏表示的誤差實現(xiàn)對其是否為道路的分類。在此基礎上，經(jīng)過簡單的后處理，就可以得到路面區(qū)域和平滑的道路邊界。該算法框架如圖1所示。

圖1 本文提出的道路分割算法框架Fig.1 Framework of the proposed road segm entation algorithm

2.1 初始字典學習

在算法的離線階段，選取大量的典型路面圖像作為訓練樣本訓練初始字典，由于這個階段是離線完成，所以可以根據(jù)可能出現(xiàn)的典型場景(包括不同的天氣、光照情況，路面出現(xiàn)水漬、陰影等情況)選取大量路面圖像樣本充分訓練得到盡量完善的字典。把訓練樣本打包成8×8像素的小片后，經(jīng)過歸一化處理，求解式(2)所示優(yōu)化問題，即得到初始字典D0(見圖2)?？紤]到字典需要實時更新，本文中字典學習采用文獻［12］中的在線字典學習算法。

圖2 初始字典學習示意圖Fig.2 Illustration of Initial dictionary learning

2.2 字典實時更新

由于天氣、光照條件的影響，即使在同一路段也會表現(xiàn)得大為迥異，所以固定不變的字典難以滿足場景復雜多變的要求。而又由于基于單目視覺的道路分割無法通過其他傳感器獲得監(jiān)督信號，所以為實現(xiàn)字典的實時更新，本文做出如下假設:

假設1 ALV始終處于可行駛的路面上，即車輛正前方的一小塊區(qū)域總是為道路。

由于自主車總是保持在路上，所以在該區(qū)域面積(180×120像素，如圖3中矩形框所示)較小的情況下，假設1是合理的。在此假設的基礎上，我們選取這一小塊圖像中的局部圖像小片作為訓練樣本，在初始字典學習或上一時刻得到的字典和模型的基礎上利用在線字典學習算法［12］實時地更新字典，提高字典的適應性。

圖3 車輛前方假設的道路區(qū)域Fig.3 Assumed road area

2.3 基于稀疏重構誤差的小片分類

得到了實時字典后，就可以對當前的測試圖像進行分割，即對當前圖像的每個小片進行分類，與SRC［4］類似，分類依據(jù)為稀疏表示的重構誤差，即根據(jù)路面圖像小片可以在當前字典上精確稀疏重構而非路面圖像小片在該字典上的稀疏重構誤差較大進行分類。首先對測試圖像的每個圖像小片x(經(jīng)歸一化處理)，求解如下稀疏表示問題:

考慮到道路分割的實時性要求，本文中采用速度較快的OMP算法求解上述稀疏表示問題。

然后根據(jù)稀疏表示系數(shù)計算該小片的稀疏表示誤差:

再根據(jù)稀疏表示誤差對小片x進行分類:

式中:errTh為重構誤差閾值。

圖4直觀地展示了上述處理過程，對采集的原始圖像(見圖4(a))的每個小片(無重疊模式)求解式(3)中的稀疏表示問題，并計算稀疏表示誤差得到如圖4(b)所示的誤差圖，再根據(jù)式(5)對每個小片進行分類，分類結果如圖4(c)所示。

圖4 基于稀疏重構誤差的小片分類示意圖Fig.4 Illustration of reconstruction errors of spare representation based patches classification

2.4 后處理

后處理階段通過上述得到的分類結果進行形態(tài)學濾波、填充后得到大致的路面區(qū)域，再通過對道路區(qū)域邊界線進行曲線擬合得到平滑的道路邊界線。圖5為分類結果后處理得到的道路區(qū)域與道路邊界線。圖5(c)為分類結果經(jīng)過簡單處理并通過三次曲線擬合得到的道路邊界線。

圖5 分類結果后處理得到的道路區(qū)域與道路邊界線Fig.5 Road area and boundaries got after post-processing

3 實驗結果

為了驗證算法的有效性，對采集的大量圖像利用上述算法進行測試，原始圖像為640×480像素的RGB彩色圖像。算法中初始字典學習過程為離線完成，在線測試階段需要車輛前方的一小塊區(qū)域作為監(jiān)督信號通過增量式學習更新字典，以及在此基礎上對每個小片求解稀疏編碼問題，由于字典更新過程中輸入的樣本數(shù)較少且可以通過控制迭代次數(shù)控制耗時，所以算法的時間消耗主要來源于對每個測試小片求解稀疏編碼問題，也因此算法的效率與小片數(shù)量和字典大小息息相關。實驗中采用8×8像素小片，無重疊小片模式中小片移動步長為8，有重疊小片模式中小片移動步長為4。在CPU雙核2.6G，內(nèi)存2GB的PC機上測試，不同參數(shù)設置下計算測試圖像小片稀疏編碼的時間消耗如表1所示。

綜合考慮分類效果與實時性要求，本文中采用無重疊小片模式，字典大小為256。在這種設置條件下，測試了大量圖像，圖6給出了一些代表性圖像的處理結果。圖6中第一列為原始圖像，第二列為對每個小片的分類結果，第三列為經(jīng)過濾波填充等后處理后用三次曲線擬合路邊得到的路面分割結果和道路邊界線。結果表明，本文中的算法對不同路面紋理具有自適應性，對天氣、光照造成的水坑、陰影、過曝等具有較好的魯棒性。

表1 不同參數(shù)設置下測試圖像小片稀疏編碼時間消耗Table 1 Time consum ing of testing image patches under various setting

圖6 典型道路分割結果示例Fig.6 Exam ples of typical experiments results

4 結束語

非結構化道路分割是ALV視覺導航中的難點問題，本文將字典學習與稀疏表示應用于非結構化道路分割，提出了一種新穎的道路分割算法。該算法以局部圖像小片為處理單元，通過學習路面圖像小片的一組字典并根據(jù)車輛前方一個小區(qū)域內(nèi)的道路圖像進行在線學習以實現(xiàn)字典的實時更新，再利用測試圖像小片在該實時字典上的稀疏重構誤差進行分類。大量測試圖像實驗結果表明，該算法能夠較好地應對非結構化路面的多變性，以及較好地克服天氣、光照等帶來的影響。但是，該算法目前對整幅圖像采用的是同一尺度，且小片特征為原始像素，維數(shù)較高，導致算法的效率較低，下一步工作中將考慮對圖像采用多尺度分析，以及尋求描述能力強且維數(shù)相對較低的特征以進一步提高算法實時性和魯棒性。

［1］Hui Kong，Jean－Yves Audibert，Jean Ponce.General road detection from a single image［J］.IEEE Trans on Image Processing，2010，9(18):2211－2220.

［2］Alon Y，F(xiàn)erencz A，Shashua A.Off－road path following using region classification and geometric projection constraints［C］//CVPR，2006.

［3］Patrick Conrad，Mike Foedisch.Performace evaluation of color based road detection using neural nets and support vector machines［C］//Proc.Applied Imagery Patt. Recog.Workshop，2003.

［4］Wright J，Yang A Y，Ganesh A，et al.Robust face recognition via sparse representation［J］.IEEE TPAMI，2009，31(2):210－227.

［5］Meng Yang，Lei Zhang，Jian Yang，et al.Robust sparse coding for face recognition［C］//Proc.CVPR.Providence，RI，2011:625－632.

［6］Yang J，Yu K，Gong Y，et al.Linear spatial pyramid matching using sparse coding for image classification［C］//CVPR，2009.

［7］Chen－Kuo Chiang，Chih－Hsueh Duan，Shang－Hong Lai，et al.Learning component－level sparse representation using histogram information for image classification［C］//ICCV，2011.

［8］Gabriel Peyre.Sparsemodeling of textures［J］.Journal of Mathematical Imaging and Vision，2009，34(1):17－31.

［9］Bin Zhao，Li Fei－fei，Eric P Xing.Online detection of unusual events in videos via dynamic sparse coding［C］//CVPR，2011.

［10］Tropp JA.Greed is good:Algorithmic results for sparse approximation［J］.IEEE Trans.Inform.Theory，2004，50(10):2231－2242.

［11］Allen Y Yang，Sastry S S.Fast l1－minimization algorithms and an application in robust face recognition:a review［C］//ICIP，2010.

［12］Julien Mairal，F(xiàn)rancis Bach，Jean Ponce，et al.Online dictionary learning for sparse coding［C］//ICML，2009.

［13］Honglak Lee，Alexis Battle，Rajat Raina，et al.Efcient sparse coding algorithms［C］//Advances Neural Info. Proc.Sys，2006.

［14］Engan K，Aase SO，Hakon－Husoy JH.Method of optimal directions for frame design［C］//Int.Conf. Acoust.，Speech，Signal Process，1999:2443－2446.

［15］Michal Aharon，Michael Elad，Alfred Bruckstein.KSVD:An algorithm for designing overcomplete dictionaries for sparse representation［J］.IEEE Trans on Signal Processing，2006，54:4311－4322.