基于Kmeans算法的二步迭代道路檢測算法

史迪瑋 毛劍琳

摘要：為增強現(xiàn)有基于機器視覺的自動導引車AGV對非結(jié)構(gòu)化路面的適應能力，提出一種基于Kmeans聚類分析算法的二步迭代道路檢測算法。算法實現(xiàn)了自動選擇路面樣本區(qū)域與自主動態(tài)添加路面樣本，克服了基于其它機器學習算法的道路識別方法需要人工收集大量路面樣本進行訓練的缺陷。實驗仿真結(jié)果顯示，該方法能有效降低光照、陰影、車道線等對道路識別的影響，能夠適應含有多種不同障礙物的道路場合。

關(guān)鍵詞：非結(jié)構(gòu)化路面;路面檢測;聚類分析;二步迭代;機器視覺

DOIDOI：10.11907/rjdk.181137

中圖分類號：TP312

文獻標識碼：A文章編號文章編號：16727800（2018）009011005

英文標題Twostep Iterative Road Detection Algorithm Based on Kmeans Algorithm

--副標題

英文作者SHI Diwei，MAO Jianlin

英文作者單位（Faculty of Information Engineering and Automation，Kunming University of Science and Technology， Kunming 650500， China）

英文摘要Abstract：This paper proposes a twostep iterative road detection algorithm based on Kmeans clustering analysis algorithmto enhance the adaptability of current automated guided vehicles （AGV） based on machine vision to unstructured pavement.Thisalgorithm implements the automatic selection of pavement sample areas and autonomous dynamic addition of pavement samples.However other road recognition methods based onmachine learning algorithmsneed to manually collect a large number of pavement samples for training，this algorithm has overcome the defects.The simulation results show that this method can effectively reduce the influence of illumination，shadow and lane line on road recognition，and it can adapt to roadsituation with many different obstacles.

英文關(guān)鍵詞Key Words：unstructured pavement;pavement detection;cluster analysis;twostep iterative;machine vision

0引言

道路識別技術(shù)是指利用計算機對采集的路面圖像進行分析處理，從而區(qū)分畫面中的道路區(qū)域與非道路背景及障礙物的技術(shù)[1]。道路識別技術(shù)是自動導引車輛（AGV，Automated Guided Vehicles）視覺導引的關(guān)鍵技術(shù)[2]，隨著人工智能技術(shù)在導航控制、輔助駕駛、物流運輸領(lǐng)域的廣泛應用，該技術(shù)已成為相關(guān)領(lǐng)域的研究重點[34]。

道路識別技術(shù)的難點在于對非結(jié)構(gòu)化道路路面的識別[5]，非結(jié)構(gòu)化道路路面是指沒有相對清晰的車道線和明確的道路邊界，且道路形狀多樣、周圍環(huán)境復雜的道路路面[6]。此類路面一般沒有相對明顯的標志線與明確的道路邊界線，且易受到光照與天氣變化、環(huán)境陰影及路面縫隙等因素影響[7]。鐘鵬飛[8]提出先提取非結(jié)構(gòu)化道路的路面邊緣點，然后基于 Hough檢測道路邊緣直線線段，并對邊緣點進行優(yōu)化，最后基于最小二乘法理論，對道路圖像中的左右邊緣點和兩側(cè)邊緣線進行擬合，得到道路左右邊緣直線，進而確定路面區(qū)域。然而，單純的基于檢測并擬合道路邊緣直線的方法無法很好地適用于路況復雜的路型：當路面上有車道線且較為明顯，或是有較清晰的光影邊界線時，根據(jù)某些算法，容易將此類車道線或光影邊界線誤識別為道路的某一側(cè)邊緣;對于多叉路路口，普通算法無法對道路的具體岔路模式進行識別。為改善并解決相關(guān)缺陷，王海、蔡英鳳、賈允毅等[12]提出一種基于深度卷積神經(jīng)網(wǎng)絡（DCNN）與自編碼器的場景自適應道路分割算法，并在 KITTI數(shù)據(jù)集上進行測試，結(jié)果表明，該算法相較于現(xiàn)有的非場景自適應道路分割算法，其對相關(guān)路面分割的準確率提升了約4.5%;李春陽[10]圍繞基于視覺信息的道路區(qū)域檢測方法，將深度學習（Deep Learning）技術(shù)應用于道路場景的路面特征提取環(huán)節(jié)，并引入人工魚群算法對監(jiān)督學習框架進行參數(shù)優(yōu)化，以實現(xiàn)對道路區(qū)域的檢測。根據(jù)多個由連續(xù)幀組成數(shù)據(jù)集上的檢驗結(jié)果顯示，該算法的通用性和魯棒性良好，能夠適應多種復雜場景，并得到令人滿意的結(jié)果。然而，現(xiàn)有大量基于機器學習理論的道路識別方法為了適應不同路面環(huán)境，需要人工收集海量路面圖片樣本數(shù)據(jù)并制作訓練集，再利用人工神經(jīng)網(wǎng)絡等技術(shù)進行多次訓練[11]，從而嚴重降低了道路檢測技術(shù)的普適性。

只有完整提取當前道路路面的具體形狀，才能進一步判別出當前道路的實際類型（如直路、彎道、叉路等），再根據(jù)道路路面的具體模式對智能移動設(shè)備進行局部定位，并與全局路徑和全局地圖相結(jié)合，從而提出合理的局部路徑規(guī)劃。因此，完整提取當前所處道路路面的具體形狀是首要研究方向。本文提出的基于Kmeans聚類分析[12]的兩步迭代道路檢測算法能針對路面樣本進行主動選擇，基于視覺的自動導引車可依靠自身的軟件和硬件設(shè)備，自主添加道路圖像作為動態(tài)樣本，且能自動選擇適合的樣本區(qū)域。該算法可降低光影、障礙物、車道線等負面環(huán)境因素對道路識別準確性的影響，能夠適應多種道路條件，減少運行過程中的人工需求，并縮短機器學習過程中的訓練時間。

1二步迭代道路檢測算法

重復進行某種反饋過程的活動稱為迭代，為了逼近所需目標或結(jié)果，通常需要進行多次迭代。算法中每一次對某個過程的完全重復，稱為一次“迭代”，而每一次迭代結(jié)束得到結(jié)果量之后，會作為下一次迭代開始的初始量，再對一系列運算過程進行重復執(zhí)行[13]。該過程每一次得到的結(jié)果，都是對前一次所得結(jié)果進行相同運算后得到的。迭代思想是利用計算機解決問題的一種基本思想[14]。

根據(jù)實際應用需要，設(shè)計一種基于兩步迭代思想的道路路面檢測算法。通過實時連續(xù)不間斷地采集行駛方向前方路面圖像，根據(jù)相鄰兩張圖像中路面區(qū)域的近似程度，判斷前方道路的連續(xù)性與可通行程度。算法默認初始位置為完全可通行區(qū)域，每次基于兩張連續(xù)且相鄰的圖像進行迭代，首先在前一張圖片Pn中選擇安全可行的路面區(qū)域Sn作為樣本區(qū)域，然后利用聚類算法提取道路樣本區(qū)域聚類特征，再將區(qū)域Sn移植到后一張圖片Pn+1中，以選取相同路面區(qū)域作為第二次聚類樣本，提取出后一張圖片道路樣本區(qū)域的聚類特征后，對前后兩組聚類特征的相似性作比較，以判斷當前道路是否為可通行路面。

2算法關(guān)鍵技術(shù)步驟

2.1樣本區(qū)域自動選擇

實時連續(xù)不間斷地采集行駛方向前方路面圖像，根據(jù)算法流程，先選取任意圖像Pn對圖像進行預處理，再轉(zhuǎn)換為單通道灰度圖像，選用 Canny算子提取道路圖像中的邊緣信息。在道路圖像背景部分中，道路邊緣界線一般表現(xiàn)為大量方向呈隨機分布的短線段，且在道路實際邊界附近，短線段分布密度明顯高于道路路面部分。通常情況下，在路面的實際真實邊界附近，邊緣線分布密度最高，且道路邊界內(nèi)側(cè)和外側(cè)存在較大的邊緣線密度差。檢測圖像中道路主體部分（直線部分）的左右兩條近似邊界，利用霍夫變換（Hough Transform）方法擬合并提取道路邊界直線。完成路面主體部分（主要指直線部分）兩側(cè)近似直線邊界的提取后，在樣本區(qū)域的左右兩側(cè)邊界上各選擇一邊界中點an、bn，獲得兩點坐標an（xn，1，yn，1）、bn（xn，2，yn，2），并確定左右直線邊界交點及其坐標cn（xn，3，yn，3）。根據(jù)3點坐標即可確定擬合出的近似道路邊界ln，1、ln，2。左右直線分別記為ln，1、ln，2，邊界內(nèi)部區(qū)域即為樣本區(qū)域，記為Sn，1，樣本區(qū)域內(nèi)部像素點（空間）將作為算法后續(xù)步驟的輸入，用于提取當前路面的具體顏色特征和紋理特征。隨后以圖像Pn的樣本區(qū)域Sn，1為樣本空間，對其中的像素點進行聚類分析。

2.2樣本區(qū)域移植

在確定了左右直線邊界的交點及其坐標cn后，根據(jù)3點坐標在圖像Pn+1中找出對應的3個點an+1（xn+1，1，yn+1，1）、bn+1（xn+1，2，yn+1，2）和cn+1（xn+1，3，yn+1，3）。以an+1、cn+1兩點確定出擬合的近似道路左側(cè)邊界ln+1，1，以bn+1、cn+1兩點確定出擬合的近似道路邊界ln+1，2。左右直線邊界內(nèi)部區(qū)域即為樣本區(qū)域，記為Sn+1，1，樣本區(qū)域內(nèi)部像素點（空間）將作為算法后續(xù)步驟的輸入，用于表征當前道路路面的實際顏色特征和紋理特征，至此即完成基于圖像Pn對于圖像Pn+1的樣本區(qū)域移植。

2.3聚類中心提取

K-means（K均值）聚類算法屬于基于數(shù)據(jù)劃分思想的無監(jiān)督聚類算法。樣本區(qū)域Sn，1中的每個像素點作為輸入樣本集，隨機設(shè)置K個聚類中心，再設(shè)置最大迭代次數(shù)max_iter，以標準K-means算法進行聚類，采用K-means++算法[15]初始化聚類中心，得到K個聚類中心（Centroids，記為Cn，1、Cn，2...Cn，k）及相應的樣本類別標記（Labels，記為Ln，1、Ln，2...Ln，k）。標準K-means算法步驟如下：

步驟1：從樣本集合中隨機選擇K個樣本數(shù)據(jù)作為聚類中心（隨機產(chǎn)生），每個聚類中心代表一個樣本類別。

步驟2：計算樣本集合中所有數(shù)據(jù)樣本與每個聚類中心的歐氏距離，將數(shù)據(jù)樣本加入與其歐氏距離最短的聚類中心簇中（記錄其數(shù)據(jù)樣本編號），即對數(shù)據(jù)樣本進行歸類。

步驟3：重新計算現(xiàn)在每個簇的聚類中心，更新樣本類別的聚類中心，判斷新聚類中心是否與原聚類中心相等。若相等，則迭代結(jié)束;若不相等，則回到步驟2繼續(xù)迭代，直至迭代總次數(shù)到達算法預設(shè)的最大迭代次數(shù)。

根據(jù)標準K-means算法，初始所有聚類中心均采用隨機采樣的方式，這意味著不能確保得到預期的聚類結(jié)果。為了優(yōu)化并獲得更好的聚類結(jié)果，則需要多次隨機初始化所有聚類中心，將得到的多組結(jié)果進行相互對比及選擇，但該方法會嚴重降低算法運行速度。最簡單且有效的改進方法是由David Arthur提出的K-means++算法，該算法可以更有效地產(chǎn)生初始聚類中心，確保初始化的K-means聚類后可以得到O（logk）的近似解。根據(jù)該算法思想，首先隨機地初始化一個聚類中心C={C1}，然后通過迭代方式計算出最大概率值：

x*=argxmaxd（x，C）∑j=1，...，nd（xj，C）

加入下一個聚類中心：

C←C∪{x*}

直到選擇K個中心。

K-means++算法復雜度為O（knd），與之前方法相比，不但沒有過多地增加計算負擔，同時能確保算法更顯著地近似于理論最優(yōu)解。

對于均值聚類分析算法，一般需要預先人工設(shè)定聚類類別數(shù)量。根據(jù)實際實驗結(jié)果，適當?shù)卦黾訕颖绢悇e數(shù)量，能在一定程度上提高算法最終檢測效果。然而，當聚類中心的初始設(shè)定數(shù)量過大時，單純地提升樣本類別數(shù)量將不再對識別效果帶來顯著改善，反而會影響道路識別的有效性。為了兼顧算法的實時性，并保證其實際檢測效果，將聚類中心的數(shù)量設(shè)定為5。不同聚類中心表征相應路面不同的紋理、顏色、光照強度、車道線及障礙物等路面特征。5個聚類中心（Centroids，記為Cn，1、Cn，2、Cn，3、Cn，4、Cn，5）及相應的樣本類別標記（Labels，記為Ln，1、Ln，2、Ln，3、Ln，4、Ln，5），代表樣本區(qū)域Sn，1中5種不同路面特征。提取經(jīng)過聚類分析得到的聚類中心Cn，1、Cn，2、Cn，3、Cn，4、Cn，5的具體參數(shù)，并使其與相應的樣本類別標記一一對應，構(gòu)建聚類中心特征值矩陣Mn。

以樣本區(qū)域Sn+1，2中的每個像素點作為輸入樣本集，經(jīng)過前文所述聚類分析計算步驟后，即得到與之對應的5個聚類中心（Centroids，記為Cn+1，1、Cn+1，2、Cn+1，3、Cn+1，4、Cn+1，5）及相應的樣本類別標記（Labels，記為Ln+1，1、Ln+1，2、Ln+1，3、Ln+1，4、Ln+1，5），代表樣本區(qū)域Sn+1，2的5種不同路面特征。同樣提取經(jīng)過聚類分析得到聚類中心Cn+1，1、Cn+1，2、Cn+1，3、Cn+1，4、Cn+1，5的具體參數(shù)，并使其與相應樣本類別標記一一對應，構(gòu)建聚類中心特征值矩陣Mn+1。

2.4相似度判斷

將由圖像Pn中提取出的聚類中心Cn，1、Cn，2、Cn，3、Cn，4、Cn，5和由圖像Pn+1提取出的聚類中心Cn+1，1、Cn+1，2、Cn+1，3、Cn+1，4、Cn+1，5進行對比，若數(shù)組Cn+1與Cn相比有相似的單個數(shù)據(jù)，則判定該數(shù)據(jù)代表的樣本類別為路面。例如假設(shè)圖像Pn顯示的路面為完全可通行路面區(qū)域，若Cn+1，2、Cn+1，3、Cn+1，4、Cn+1，5與Cn，2、Cn，3、Cn，4、Cn，5相似度較高，Cn+1，1與Cn，1有明顯差異，則判定在圖像Pn+1中，將Cn+1，2、Cn+1，3、Cn+1，4、Cn+1，5對應的樣本類別標記為路面，Cn+1，1對應的樣本類別標記為非路面特征。

然后以圖片Pn+1作為基準對圖片Pn進行處理，得到樣本區(qū)域Sn+2，1與相應的聚類中心及樣本類別標記;再以圖片Pn+2作為對象，在圖像預處理后以樣本區(qū)域Sn+2，1為準，進行樣本區(qū)域移植，對移植后樣本區(qū)域中的樣本進行聚類分析，得到聚類中心及樣本類別標記，進行聚類中心特征值的相似度判斷;不斷迭代循環(huán)上述處理和運算步驟，即可完成對當前路徑的道路檢測。若檢測不到任何可通行路面區(qū)域，則算法中斷，自動跳出至結(jié)束。

3仿真結(jié)果與分析

3.1仿真平臺及數(shù)據(jù)集

本文計算機仿真工作在Windows 7 （x64）操作系統(tǒng)下完成，開發(fā)平臺為Matlab R2016a。

采用西安交通大學人工智能與機器人研究所（IAIR）的道路—車輛數(shù)據(jù)集（Road-Vehicle Dataset ，RVD）作為圖像數(shù)據(jù)來源。RVD數(shù)據(jù)集中包含了豐富的道路場景圖像數(shù)據(jù)，涵蓋了有著不同車道數(shù)量的城區(qū)道路與高速道路。同時，數(shù)據(jù)集涵蓋了多種天氣狀況。

3.2仿真結(jié)果

利用前文所述道路—車輛數(shù)據(jù)集（RVD）中的Curve_Lane（曲線車道）數(shù)據(jù)集，對本文提出的算法進行驗證。該數(shù)據(jù)子集中含有數(shù)千張連續(xù)拍攝的道路圖像數(shù)據(jù)，所指示的道路交通情形大體分為障礙物不影響正常行駛和障礙物影響正常行駛兩種狀態(tài)。其中障礙物不影響正常行駛有前方無障礙物和僅側(cè)方有障礙物兩種情形，前方有障礙物的情況即為障礙物影響正常行駛。在連續(xù)拍攝的n張圖片中，選取含有3種不同障礙物分布情況的圖片數(shù)據(jù)，對算法的準確性及有效性作出說明。

根據(jù)圖4、圖5兩組聚類結(jié)果的散點圖及聚類中心分布可以看出，兩幅圖片的聚類中心點C（x，y）均大多分布在區(qū)間S=[127≤x≤130，128≤y≤134]中。與原始數(shù)據(jù)圖2、圖3的實際路況作對比后可知，該分布區(qū)間S所涵蓋的聚類中心點，即為可正常通行的路面區(qū)域?qū)臉颖究臻g分布區(qū)間。即若某聚類中心點在區(qū)間S內(nèi)，則該聚類中心點對應的實際路面特征可判定為路面區(qū)域。

選取數(shù)據(jù)集中某時刻有側(cè)方并行車輛的圖片，代表僅側(cè)方有障礙物，且障礙物不影響向前正常行駛的情形，如圖6所示;選取數(shù)據(jù)集中某時刻行駛方向前方有較近距離車輛的圖片，代表前方有障礙物，且障礙物影響正常行駛的情形，如圖7所示。

根據(jù)圖8聚類結(jié)果散點圖及聚類中心分布可以看出，基于圖6的聚類中心點C6（x，y）均分布在區(qū)間S6=[128≤x≤129，128≤y≤134]中。與之前判定的可正常通行路面區(qū)域?qū)臉颖究臻g分布區(qū)間S進行對比可得，S6∈S，得到S6涵蓋的聚類中心點即為可正常通行路面區(qū)域?qū)臉颖究臻g分布區(qū)間，即圖6所表征的道路路況為可正常通行道路。

根據(jù)圖9的聚類結(jié)果散點圖及聚類中心分布可以看出，基于圖7的聚類中心點C7（x，y）有一部分的確分布在區(qū)間S=[127≤x≤130，128≤y≤134]中，有3點C7，3（131，132）、C7，4（131，135）、C7，5（134，137）超出了區(qū)間分布。根據(jù)算法設(shè)定，判定此3點對應的像素特征點集合為存在障礙物，剩余兩點C7，1（128，128）、C7，2（129，133）在區(qū)間S中，判定為路面區(qū)域。與實際路況圖像圖7進行對比，C7，3、C7，4、C7，53點對應的物體為道路正前方距離較近的一輛黑色小型汽車與路面上的淺色減速帶，其判斷的是否有障礙物情況與路面實際障礙物情況吻合，成功驗證了算法的準確性和有效性。

4結(jié)語

針對智能車視覺導引中的道路檢測問題，提出一種基于Kmeans算法的AGV二步迭代道路檢測算法。以間隔一定周期拍攝的連續(xù)道路圖像為數(shù)據(jù)輸入，與傳統(tǒng)利用拍攝實時視頻作為數(shù)據(jù)輸入的方式相比，大大減少了數(shù)據(jù)存取及傳輸量，節(jié)約了設(shè)備硬件資源;在傳統(tǒng)根據(jù)道路邊界進行路徑檢測的基礎(chǔ)上，加入基于Kmeans聚類中值算法的無監(jiān)督機器學習技術(shù)，既可以實現(xiàn)路面樣本的動態(tài)添加與判斷，又避免了針對大量路面樣本的提前訓練工作;將傳統(tǒng)的道路形態(tài)學檢測與針對像素點的特征聚類及分析判定技術(shù)相結(jié)合，大大增強了對正常路面及非路面的識別能力，提高了檢測速度，降低了道路檢測技術(shù)對硬件設(shè)備的要求，增強了實用性。

未來的研究方向為：①繼續(xù)針對多個連續(xù)圖像，對其相關(guān)性進行發(fā)掘，以提高路面識別速度與檢測效果;②改進現(xiàn)有聚類中心提取方法，實現(xiàn)自適應確定聚類中心個數(shù)，進一步減少人工操作;③設(shè)計完善的連續(xù)采樣機制和特征學習方法，增強算法對具體障礙物的判別能力。

參考文獻參考文獻：

[1]潘奎剛.智能車輛基于視覺的可通行區(qū)域檢測方法[D].南京：南京理工大學，2017.

[2]張舒原.視覺導引AGV及其在制造業(yè)廠內(nèi)的應用[J].物流技術(shù)與應用，2016，21（3）：114117.

[3]婁會東.視覺導引的物料搬運AGV關(guān)鍵技術(shù)研究[D].廣州：華南理工大學，2015.

[4]周曉杰.AGV系統(tǒng)及引導方式發(fā)展趨勢綜述[J].南方農(nóng)機，2017，48（4）：80.

[5]武歷穎，余強.一種快速準確非結(jié)構(gòu)化道路檢測方法研究[J].計算機仿真，2016，33（9）：174178.

[6]劉富，袁雨桐，李洋.基于紋理特征的非結(jié)構(gòu)化道路分割算法[J].計算機應用，2015（2）：271273.

[7]李迎春，付興建，薛琴.基于RGB熵的非結(jié)構(gòu)化道路分割方法[J].計算機工程與設(shè)計，2017，38（6）：15701574.

[8]鐘鵬飛.基于機器視覺的非結(jié)構(gòu)化道路識別與障礙物檢測研究[D].廣州：華南農(nóng)業(yè)大學，2016.

[9]王海，蔡英鳳，賈允毅，等.基于深度卷積神經(jīng)網(wǎng)絡的場景自適應道路分割算法[J].電子與信息學報，2017，39（2）：263269.

[10]李春陽.基于機器學習的道路區(qū)域識別方法研究[D].杭州：浙江大學，2016.

[11]DAHL J V，KOCH K C，KLEINHANS E，et al.Convolutional networks and applications in vision[C].IEEE International Symposium on Circuits &Systems ，2011 ，14 （5）：253256.

[12]郝運河，張浩峰，於敏杰，等.基于Kmeans特征的復雜環(huán)境下道路識別算法[J].計算機應用研究，2016，33（2）：602606.

[13]孫明軒.迭代學習控制[M].北京：國防工業(yè)出版社，1999.

[14]李仁俊，韓正之.迭代學習控制綜述[J].控制與決策，2005，20（9）：961966.

[15]ARTHUR D，VASSILVITSKII S.Kmeans++：the advantages of careful seeding[C].Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms，2007：10271035.

責任編輯（責任編輯：黃?。?/p>