黃 鋼 吳超仲 呂能超▲

（1.武漢理工大學智能交通系統(tǒng)研究中心 武漢430063；2.水路公路交通安全控制與裝備教育部工程研究中心 武漢430063）

0 引 言

道路交通安全已經成為研究熱點，特別是圍繞車路協(xié)同系統(tǒng)［1－3］和智能汽車（intelligent vehicle）開發(fā)的汽車安全駕駛系統(tǒng)更是受到廣泛關注。研究表明［4－6］，在國內外智能交通系統(tǒng)和智能車輛的研究領域中，有很多采用不同算法和手段進行前方路面障礙物探測的研究，如利用單目視覺、雙目視覺、彩色CCD等進行探測。

典型的目標檢測方法如基于圖像的目標檢測能在天氣良好的情況下較好的檢測出目標物，但識別精度受環(huán)境影響很大，容易誤判和漏判，且處理圖像過程繁雜，需花費大量時間檢測與行人無關的區(qū)域，此外圖像信息無法精確識別行人距離。而激光傳感器則具有檢測速度快、目標可靠、能提供距離信息等優(yōu)點。

然而，激光傳感器識別行人等障礙物目標時，掃描的數(shù)據(jù)是一些沒有具體特征的平面點，且雷達數(shù)據(jù)有較多冗余，若不對激光數(shù)據(jù)進行處理，則很難識別出有效的目標物。目前，國內外眾多研究者針對不同研究目的提出了許多改進的DBSCAN算法。如劉軍等［7］人提出了基于 DBSCAN方法的交通事故多發(fā)點（段）的排查方法及其改進思路，并且結合J2EE技術，實現(xiàn)了1個Web環(huán)境下的交通事故數(shù)據(jù)挖掘系統(tǒng)，該方法并未用于目標檢測，且聚類方法較為簡單；馮少榮等［8］人針對“基于密度的帶有噪聲的空間聚類”（DBSCAN）算法存在的不足，提出“分而治之”和高效的并行方法對DBSCAN算法進行改進.通過對數(shù)據(jù)進行劃分，利用“分而治之”思想減少全局變量Eps值的影響，利用并行處理方法和降維技術提高聚類效率，降低DBSCAN算法對內存的較高要求，并采用增量式處理方式解決數(shù)據(jù)對象的增加和刪除對聚類的影響，該改進算法能起到較好的效果改進的聚類算法無論是在聚類質量還是在聚類效率上都得到了比較滿意的結果，但算法較為復雜；又如國外學者Derya Birant等［9］人提出的1種ST-DBSCAN算法，在該算法中，作者提出基于識別核心點、噪聲點、相鄰簇的3種邊緣擴展方法，該算法對比現(xiàn)有基于密度的聚類算法的優(yōu)點是能夠根據(jù)非空間、空間及時間數(shù)據(jù)集下物體的值尋找出不同的簇，但該算法的數(shù)據(jù)源為海洋數(shù)據(jù)，具有一定的特殊性。

筆者根據(jù)采集激光雷達數(shù)據(jù)點的特征，對數(shù)據(jù)精簡處理，加快計算速度和提高激光雷達識別的精確性，從大量數(shù)據(jù)中提取有用信息，通過改進DBSCAN聚類算法進行有效的數(shù)據(jù)精簡、數(shù)據(jù)去噪和障礙物識別，主要用于智能交通路側目標物檢測。

1 基于聚類算法的激光雷達目標物識別

激光雷達數(shù)據(jù)是分布于對象表面的一系列三維點坐標，在形式上呈離散分布，掃描帶中數(shù)據(jù)分布不均勻——不同位置的光斑密度不同，盡管直接獲取點三維坐標是激光雷達最顯著的特點之一，但其數(shù)據(jù)類型并不局限于此。強度信號是另1個有用的信息源，它反映了地表物體對激光信號的響應。由于一些技術上的原因（如缺乏有效的定標手段），還沒有得到多少實際應用?；诩す饫走_點云數(shù)據(jù)的特點，為精確的辨識行人，需對激光雷達數(shù)據(jù)進行有效的聚類。

作為數(shù)據(jù)挖掘領域的1個重要研究方向，聚類分析已經廣泛地應用于模式識別、圖像處理以及數(shù)據(jù)分析等諸多領域。常用的聚類方法有：劃分聚類法、層次聚類法、基于密度的聚類法、基于網絡的聚類法以及基于模型的聚類方法等［10－12］。利用聚類算法，可將具有相同性質的數(shù)據(jù)點歸為同一簇，根據(jù)簇的特點有效地判別目標物的種類。DBSCAN算法是1種具有代表性的基于密度的聚類算法。它能在存有噪聲的空間數(shù)據(jù)中發(fā)現(xiàn)任意形狀的類。

基于密度的聚類算法DBSCAN通過計算數(shù)據(jù)集中每個數(shù)據(jù)點的區(qū)域密度來進行聚類，需設置Eps和MinPts這2個參數(shù)。由DBSCAN算法的定義和引理［8］可知，1個簇就是密度相連的點的最大集合，且可以由其中任意1個核心點唯一確定。

基于上述事實，DBSCAN的算法思想是：從數(shù)據(jù)集中任意選擇1個點p開始，查找數(shù)據(jù)集中所有從p密度可達的點。如果p為核心點，則其Eps鄰域內的所有點與p屬于同1個簇，將這些點作為即候選點，通過不斷查找從候選點的密度可達的點來擴展該簇，直至找到1個完整的簇；如果p不是核心點，即沒有對象從p密度可達，則p被暫時標注為噪聲點。然后，算法對數(shù)據(jù)集中未被處理的點重復上述過程，進行其他簇的擴展。最后數(shù)據(jù)集中不屬于任何簇的點即為噪聲點。

2 基于改進DBSCAN算法的激光雷達數(shù)據(jù)處理

DBSCAN算法在聚類過程中存在以下不足之處。

1）對聚類半徑、聚類鄰域中對象個數(shù)等輸入?yún)?shù)敏感。

2）聚類半徑、聚類鄰域中的對象個數(shù)是全局惟一確定的，對于不同密度分布時，聚類效果較差；

3）當聚類的核心對象確定后，以此核心對象為中心向外擴展，從而導致隨著核心對象不斷增多需要的內存也不斷地增大。

研究所用的是IBEO-LUX 4線激光雷達，結合雷達的應用環(huán)境分析可知其數(shù)據(jù)有如下特點：①數(shù)據(jù)應轉化成直角坐標系下的點，便于聚類分析；②雷達應用環(huán)境決定雷達數(shù)據(jù)聚類時，類的數(shù)目是變化的；③雷達數(shù)據(jù)的密度隨著目標物距離的改變而改變。

筆者結合激光雷達二維數(shù)據(jù)和DBSCAN算法的特點，針對激光雷達應用對DBSCAN算法進行改進。

1）改進搜索速度。原始算法中，核心點的Eps鄰域內所有的點都要重新搜索，而實際上起作用的點是該鄰域內離核心點最遠的數(shù)據(jù)點，這樣必定會浪費較多的搜索時間。筆者提出的改進方法是選取有代表性的點作為擴展點，此時需要解決2個問題：①代表對象應該選多少；②如何選擇代表對象。代表對象太多，算法的效率會很低；如果太少，則代表對象鄰域難以比較完全地覆蓋其他對象的鄰域，從而造成對象“丟失”，影響到聚類質量和效率。不考慮掃描點的高度信息，在激光雷達數(shù)據(jù)點存在的二維平面內，可以選代表對象數(shù)為4［13］。此時以核心點為坐標原點建立1個直角坐標系，尋找該直角坐標系下4條半軸（X軸正負半軸和Y軸正負半軸）附近遠離所選核心點最遠的4個點，以這4個點為代表點向外擴展簇，能極大的縮短搜索時間。

2）改進輸入?yún)?shù)。激光雷達的數(shù)據(jù)密度會隨著掃描的距離變化而變化，距離激光雷達原點越近則數(shù)據(jù)密度越高，越遠則數(shù)據(jù)密度越低。在該情況下，搜索半徑即Eps的值應該隨搜索點與激光雷達的距離而變化，而不是保持某個值不變。因此提出聚類半徑Eps與掃描距離相關的函數(shù)如下。

式中：int（）為取整；α為聚類半徑系數(shù)；（xi，yi）為該數(shù)據(jù)點在以激光雷達點為坐標原點建立的直角坐標系下的坐標；θs為激光雷達的掃描角分辨率；L為聚類區(qū)域步長。改進的DBSCAN算法流程圖見圖1。

圖1 改進的DBSCAN算法流程圖Fig.1 Algorithm flow chart of improved DBSCAN

算法步驟如下。

1）初始化，輸入聚類數(shù)據(jù)。

2）任意選取1個數(shù)據(jù)點xi。

3）如果xi沒有被劃分到某1個簇，判斷其是否為核心點。

4）若為核心點，則擴展以xi為核心對象的簇，開始搜索該數(shù)據(jù)點鄰域，若不是核心點，則跳過該點。

5）搜索xi領域時，需檢測鄰域內與該點距離小于Eps值的點，Eps值大小見式（1）。

6）取出領域內的4個點（取點規(guī)則如前文所述）作為代表點，代表點入棧。

6）若棧非空，則取出棧頂數(shù)據(jù)，跳至步驟4）；若為空，則簇數(shù)增加1。

7）若所有的數(shù)據(jù)點均被處理，則結束；否則，轉步驟2）。

3 實驗結果與論證分析

采用德國IBEO公司提供的LUX4線激光雷達作為主傳感器，正常使用時，該激光雷達安裝在實驗用車的保險杠部位，在激光雷達附近安裝有攝像頭，攝像頭采集的圖像信息作為后驗信息，在VS2008下通過雷達的API接口獲取并采集數(shù)據(jù)，激光雷達與圖像數(shù)據(jù)均加入本地時間，這樣便可找出每1幀激光雷達數(shù)據(jù)點對應的圖像信息。為驗證算法的實用性，在進行實車實驗前，進行了模擬實驗。如圖2所示，將激光雷達固定在某處，攝像頭放置在激光雷達上部，模擬行人站立于白板之前。

圖2 激光雷達原始數(shù)據(jù)對應的實驗行人示意圖Fig.2 The pedestrians in experiment

3.1 簡易實驗環(huán)境下改進DBSCAN算法的精度與搜索速度分析

在Matlab中對激光雷達數(shù)據(jù)進行原始聚類以及利用改進后的算法進行聚類，對比圖像信息分析2種算法的精確度，以及搜索時間。在采集的1 589幀激光雷達數(shù)據(jù)中隨機選取10幀數(shù)據(jù)進行聚類，并從采集的圖像數(shù)據(jù)中找到對應的目標物作為后驗信息，選取有代表性的1幀數(shù)據(jù)為例，對比分析改進前后的聚類效果。激光雷達采集的原始數(shù)據(jù)如圖3所示，所采集的數(shù)據(jù)點為一系列無規(guī)則的點集；改進前的聚類算法效果如圖4所示，原始DBSCAN算法將目標簡單的分為了4類，且把2個行人歸為同一類，說明原始的算法在精度上存在較大誤差，分類結果較粗；改進后的聚類算法效果如圖5所示，改進后的DBSCAN算法將目標分成了包含噪聲在內的7類，且能將2個行人及其后面的白板分成3個不同的簇，且對噪聲的劃分也更為精確。對比圖4、圖5可知，改進后的DBSCAN算法在精確度上有了很大的提高。

圖3 激光雷達原始點Fig.3 The original points of laser rader

圖4 未改進的DBSCAN算法聚類Fig.4 Clustering of DBSCAN before improving

圖5 改進后的DBSCAN算法聚類Fig.5 Clustering of improved DBSCAN

改進前后10幀激光雷達的聚類算法搜索時間見表1。由表1可見，改進后的DBSCAN聚類算法的搜索時間比改進前均有較大幅度提高，提高了50%。

表1 改進前后DBSCAN聚類算法的搜索時間Tab.1 the searching time of unimproved and improvedDBSCAN

3.2 實車實驗下改進DBSCAN算法的精度及搜索速度分析

在實車實驗中，由于道路環(huán)境具有一定的復雜性，行人及噪聲較多，無法同簡易實驗環(huán)境一樣根據(jù)圖像信息檢驗目標物的檢測精度，因而需要對激光雷達數(shù)據(jù)的簇形狀有一定的先驗知識。研究表明［14］，激光雷達數(shù)據(jù)點聚類后，不同的簇形狀可以代表不同的目標物。對于車輛行駛過程中，路面可能出現(xiàn)的目標，筆者在激光層根據(jù)聚類結果的激光軸數(shù)對目標做了如表2的分類。

表2 激光軸數(shù)與點的對應Tab.1 the corresponding of lidar axis and points

根據(jù)表2提供分類信息，結合圖像信息提供后驗檢測，分析目標物的情況。該表亦驗證了簡易實驗環(huán)境下改進DBSCAN算法的精度。由圖5可以明顯看出，激光雷達采集數(shù)據(jù)中應該包含2個行人以及1塊白板，對比分析圖4和圖5可知，未改進的DBSCAN算法（見圖4）把白板和行人都歸到了同一類，而改進后的DBSCAN算法（見圖5）則能很好的辨識2個人以及身后的白板。此外，改進后的算法還能很好的識別墻體（即單軸物體），說明該算法具有良好的檢測精度。

將該算法應用與實車實驗中，實驗場景選在較為復雜的學校主干道上，激光雷達安裝在車輛保險杠部位，攝像頭安裝在激光雷達正上方便于檢驗算法檢測的精度。在選取的10幀激光雷達數(shù)據(jù)中，由圖像信息可以檢驗出，激光雷達視角內共出現(xiàn)了21個行人，5輛汽車，其他不明顯目標物10個，改進后的DBSCAN算法結合表2提供的先驗知識能檢測出17個行人，5輛汽車，行人檢測率為80.95%，而原始的DBSCAN算法只能檢測出13個行人，4輛汽車，行人檢測率為61.90%，由此可以看出，在行人檢測方面，改進的DBSCAN算法能較好的提高檢測精度。

此外，改進的DBSCAN算法能較大的提高搜索速度。表1結果表明，在10幀數(shù)據(jù)中，改進后DBSCAN算法的搜索時間較改進前縮短了44.70%，說明該算法在提高搜索精度的同時也提高了搜索效率。

4 結束語

筆者結合LUX4線激光雷達數(shù)據(jù)特點，使用基于密度聚類的DBSCAN算法對激光雷達數(shù)據(jù)進行聚類，并對原有的DBSCAN算法進行了改進，主要修改了算法中的聚類半徑以及搜索范圍，使用同步圖像數(shù)據(jù)作為后驗信息檢驗激光雷達視角內的目標物，對比分析原始DBSCAN算法以及改進的DBSCAN算法，結果表明，改進后的激光雷達具有以下優(yōu)點。

1）改進后的DBSCAN算法行人檢測率達到了80.95%，極大的提高了DBSCAN算法的檢測精度；

2）改進后DBSCAN算法的搜索時間較改進前縮短44.70%，較好的提高了目標物識別效率。

綜上，筆者提出的改進的DBSCAN算法能較好地提高目標物識別的精度及效率，該算法可應用于交通領域目標物檢測中，為道路交通安全提供有力的保障。在雷達數(shù)據(jù)處理方面，筆者所取的4個點，在一定程度上存在數(shù)據(jù)丟失問題，統(tǒng)計丟失率約為5%，因而，在激光雷達數(shù)據(jù)點代表點的選取上，仍需做更多的研究。

［1］ 陳超，呂植勇，付姍姍，等.國內外車路協(xié)同系統(tǒng)發(fā)展現(xiàn)狀綜述［J］.交通信息與安全，2011，29（1）：102-106.CHEN Chao，LYU Zhiyong，F(xiàn)U Shanshan，et al.Overview of the development in cooperative vehicle-infrastructure system home and abroad［J］.Journal of Transport Information and Safety，2011，29（1）：102-106.（in Chinese）

［2］ 黃羅毅，吳志周，楊曉光，等.基于仿真的IEEE802.11P在車路協(xié)同中的適應性研究［J］.交通信息與安全，2011，29（3）：123-126.HUANG Luoyi，WU Zhizhou，YANG Xiaoguang，et al.Simulation of the adaptability of the IEEE 802.11Pin intellidrive system［J］.Journal of Transport Information and Safety，2011，29（3）：123-126.（in Chinese）

［3］ 樊瑤，褚燕利.基于多傳感器融合的智能車路協(xié)同仿真系統(tǒng)［J］.公路.2014，（10）：189-193.FAN Yao，CHU Yanli.Intelligent cooperative vehicle infrastructure simulation system based on multi-sensor Fusion［J］.Highway，2014，（10）：189-193.（in Chinese）

［4］ 張陽，劉偉銘，吳義虎.面向車載輔助駕駛系統(tǒng)的快速行人檢測方法［J］.公路交通科技.2013.30（11）：131-138.ZHANG Yang，LIU Weiming，WU Yihu.A fast pedestrian detection method for vehicle auxiliary driving system［J］.Journal of Highway and Transportation Research and Development，2013，30（11）：131-138.（in Chinese）

［5］ 嚴新平，黃合來，馬明.美國道路交通安全現(xiàn)狀及研究熱點［J］.交通信息與安全，2009，27（5）：1-9.YAN Xinping，HUANG Helai，MA Ming.Road Safety in the United States：State of the Art and the Practice［J］.Journal of Transport Information and Safety，2009，27（5）：1-9.（in Chinese）

［6］ 嚴新平，張 暉，吳超仲，等.道路交通駕駛行為研究進展及其展望［J］.交通信息與安全，2013，31（1）：45-51.YAN Xinping，ZHANG Hui，WU Chaozhong，et al.Research progress and prospect of road traffic driving behavior［J］.Journal of Transport Information and Safety，2013，31（1）：45-51.（in Chinese）

［7］ 劉軍，艾力，馬曉松.一種改進的DBSCAN聚類算法的研究與應用［J］.交通與計算機，2008，26（3）：60-64.LIU Jun，AI Li，MA Xiaosong.An improved DBSCAN clustering algorithm［J］.Traffic ＆ Computer，2008，26（3）：60-64.（in Chinese）

［8］ 馮少榮，肖文俊.DBSCAN聚類算法的研究與改進［J］.中國礦業(yè)大學學報，2008，27（1）：105-111.FENG Shaorong，XIAO Wenjun.An improved DBSCAN clustering algorithm［J］.Journal of China U-niversity of Mining ＆ Technology，2008，27（1）：105-111.（in Chinese）

［9］ BIRANT D，KUT A.ST-DBSCAN：An algorithm for clustering spatial-temporal data［J］.Data ＆Knowledge Engineering，2007，60：208-221.

［10］ WEN Shun，ZHAO Jieyu，ZHU Shaojun.Hierarchical clustering based on a bayesian harmony measure［J］.PR＆AI，2013，26（12）：1161-1168.

［11］ LU Zhimao，F(xiàn)ENG Jinmei.Novel partitional clustering algorithm for large data processing［J］.Systems Engineering and Electronics，2014，36（5）：1010-1015.

［12］ 黃健斌，康劍梅，齊俊杰，等.一種基于同步動力學模型的層次聚類方法［J］.中國科學：信息科學，2013，43（5）：599-610.HUANG Jianbin，KANG Jianmei，QI Junjie，et al.A hierarchical clustering method based on a dynamic synchronization model［J］.Scientia Sinica：Informationis，2013，43（5）：599-610.（in Chinese）

［13］ 王桂芝，王廣亮.改進的快速DBSCAN算法［J］.計算機應用，2009，29（9）：2505-2508.WANG Guizhi， WANG Guangliang.Improved fast DBSCAN Algorithm［J］.Journal of Computer Applications，2009，29（9）：2505-2508.（in Chinese）

［14］ BAR-SHALOM Y，TSE E.Tracking in a cluttered environment with probabilistic data association［J］.Automatic，1975，11（9）：451-460.