基于顏色特征聚類的路徑標線檢測算法

孟德欣，王民權，胡國偉

（寧波職業技術學院 a.電子信息學院；b.海天機電學院，浙江 寧波315800）

基于顏色特征聚類的路徑標線檢測算法

孟德欣a，王民權b，胡國偉a

（寧波職業技術學院 a.電子信息學院；b.海天機電學院，浙江 寧波315800）

針對視覺導航中路徑彩色圖像數據量大、維數高，引導標線檢測算法耗時較長的問題，提出一種基于顏色特征聚類的快速標線檢測算法。在分析常見的標線檢測算法特征基礎上，建立彩色圖像的顏色稀疏矩陣，隔行檢測疑似標線的顏色特征點，計算各特征點之間的近鄰系數，利用近鄰函數法對顏色特征點聚類分析，找出特征點最多的目標類作為標線，按路徑結構將特征點連通，并提供路徑導航信息。實驗結果表明，與傳統顏色空間轉換和基于霍夫變換的邊緣檢測算法相比，該算法運算速度較快，能夠滿足實時性要求。

視覺導航；標線檢測；最近鄰函數法；顏色特征；聚類

DO I：10.3969/j.issn.1000-3428.2015.10.044

1 概述

視覺導航的智能車通常采用標線跟蹤導航，通過計算機視覺技術對路徑和障礙物圖像理解并提供自動導引，相比較其他導航法如磁導航、激光導航、毫米波雷達法、GPS導航等，視覺導航法具有高精度、柔性控制、環境適應性和應用成本等方面的優勢，基于視覺導航的智能車應用廣泛［1-3］。

目前，智能車采集的路徑圖像多為彩色圖像，相比于灰度圖像其信息量大，標線檢測和跟蹤的速度對計算機圖像處理提出更高的實時性要求。在運動速度較快的情況下，標線檢測的速度和準確性對后續路徑跟蹤導航效果有很大影響［4］。現有的標線檢測算法為提高實時性常見做法是把采集到的彩色圖像轉換為灰度圖像，然后再檢測標線信息，這種算法由于丟失了色彩信息，目標的分割并不準確，而且灰度圖像對光照不均勻、陰影、水漬等的魯棒性較差［5-6］。

針對路徑彩色圖像數據量大、維數高，標線檢測算法耗時的問題，本文在分析彩色路徑圖像的顏色特征基礎上，采用近鄰函數法聚類模型對疑似標線的特征點進行聚類分析，檢測標線的邊界特征，然后按路徑結構將其連通，從而識別標線的位置和形狀［7-9］，使運動控制模塊根據路徑信息做出相應的移動。

2 近鄰函數法的聚類模型

常見的C-均值法適合于類別數確定及初始聚類中心選定的情況，對于類內球狀分布一般都能夠達到理想的聚類效果，但易受類別數及初始聚類中心的影響，是一種局部最優的聚類算法［10］。

近鄰函數法與C-均值法不同，特別適合于類內條狀或線狀分布的情況，如圖1所示。

圖1 類內條狀或線狀分布

考慮到路徑圖像中標線為條狀分布，本文采用近鄰函數法對標線特征點進行聚類，引入類內、類間損失函數作為評價依據，構造聚類準則函數，最后選出聚類結果中包含特征點最多的類設為目標類。

定義1 近鄰函數

在圖像矩陣中，考慮像素點樣本χi，計算χi與其他各樣本間的近鄰函數值，表示為：

式（1）表示連接損失Lij是樣本χi與χj連接損失最小值，如χi與 χj沒有實際連接，則不存在連接損失L。

定義2 類內連接損失

設樣本集共有c類，表示為 wP（P=1，2，…，c），則總的類內連接損失定義為：

定義3 類間連接損失

設聚類wP和 wq（P，q=1，2，…，c；q≠P），則總的類間連接損失定義為：

其中，類wP和 wq（P，q=1，2，…，c；q≠P）的樣本之間最小近鄰函數值為：

式（4）表示除wP類內樣本外，wq中的某一個樣本與wP中的某一個樣本最近鄰，近鄰函數值為βPq，此時還需要考慮 wP和 wk是否可以合并，如要合并則進行迭代運算。

記wP類的類內最大近鄰函數值：

則wP和wq類的類間損失函數定義如下：

其中，當 βPq＞γPmaχ，βPq＞γkmaχ，表示類間近鄰函數值大于類內最大近鄰函數值，說明聚類結果是合理，其他情況則需進行調整。

定義4 聚類準則函數

在計算出類間損失函數 χPq的基礎上，類間總損失函數定義如下：

聚類的目標是使各 βPq盡可能大，γPmaχ盡可能小，則構造聚類準則函數如下：

每次對2個類合并，這樣聚類準則函數的值每次都要增加，若是函數值的增加在每一次合并時都是最小的，則得到的分類結果為最優。否則，則需重復此過程。

3 標線檢測算法

在采集路徑圖像過程中，由于受到環境噪聲的干擾等原因造成噪聲產生，圖像信息會有所丟失。故在標線檢測算法先對圖像預處理，包括去噪、設置適當的閾值建立顏色稀疏矩陣這樣可以減少算法處理時間，利用隔行檢測疑似標線的顏色特征點，接著利用近鄰函數法對特征點聚類，選取特征點最多的類別為目標類，即為標線，同時給出控制指令，下達給運動控制模塊。

標線檢測算法的執行過程如下：

（1）圖像預處理

包括圖像濾波、增強和顏色空間轉換等。采集圖像由于各種原因會存在噪聲和畸變，需要進行濾波處理和圖像增強，達到改善圖像的目的。均值濾波能有效去除隨機噪聲，但當噪聲比較密集時效果明顯減弱，中值濾波是一種快速抑制圖像噪聲的非線性技術，其原理是把圖像中的一點（χ，y）的值用該點鄰域S內的各點（s，t）的中值代替，鄰域窗口大小通常取一個包含奇數個像素點的窗口，窗口大小為3×3或5×5時，在去噪方面通常具有良好的濾波效果［11］。 中值濾波公式為：

其中，f（χ，y）表示像素點（χ，y）的灰度值；s，t分別表示水平、垂直方向的范圍。中值濾波時使用大小為3×3或5×5的采樣窗口掃描圖像，直到找到符合條件的像素點，然后在采樣窗口中取出奇數個像素點進行排序，并用排序后的中值取代要處理的像素點數據即可。

考慮到人眼對亮度信息的敏感程度較色差信息要高的視覺特點以及標線為紅色、藍色的特征，本文算法將RGB的路徑彩色圖像轉換為YUV顏色空間。在YUV顏色空間中，每一個顏色有一個亮度分量矩陣Y和2個色差分量矩陣U和V。其中，亮度分量矩陣Y把RGB信號的亮度部分疊加到一起，色

差分量矩陣U，V實際上就是藍色差信號和紅色差信號，一定程度上間接的代表了藍色和紅色的強度［11］。該模型將亮度和色調分開，適用于圖像處理中對光照比較敏感的情況。

在YUV顏色空間中，辨識圖像的主要依據來源于亮度分量矩陣Y。YUV顏色空間和RGB顏色空間之間的關系如下式所示［12］：

然后，考慮到標線為紅色、藍色，在YUV顏色空間進行YUV三通道分解，增加其中的紅色、藍色分量矩陣U，V通道的亮度信息。

（2）隔行檢測顏色特征點

在對圖像預處理后，通過設置閾值對圖像水平方面進行隔行掃描，檢測標線的顏色特征點。考慮到標線連續顏色無跳躍的實際情況，隔行掃描的處理算法是合理的，能夠有效節省算法執行時間。經實驗得出，行間距設置為40行 ～60行之間比較合適。在掃描過程中，顏色特征點檢測需設置閾值來進行判斷，算法中根據標線的寬度等先驗知識預先設置了標線顏色、寬度等信息的閾值，在隔行掃描過程中只有滿足大于顏色、寬度閾值的一些像素點才被確認為特征點并存儲起來。

（3）對疑似顏色特征點進行聚類

接下來，對特征點進行聚類分析。對于特征點樣本集｛χ1，χ2，…，χn｝，計算特征點的距離矩陣 D，D表示如下：

其中，d（χi，χj）表示 χi和 χj特征點之間的距離。在距離矩陣D中計算出近鄰系數矩陣M，M為一個稀疏矩陣，其元素為各樣本間的近鄰系數。

接著生成近鄰函數矩陣 L，置主對角線元素Lij=2N，如果χi和χj有連接，則Lij則是連接損失即近鄰函數值，同時對矩陣L進行遍歷，將每個特征點與它的最小近鄰函數值的特征點連接起來，從而形成初始聚類。

在初始聚類中，計算 βPq，γPmaχ，γkmaχ，如 βPq小于或等于γPmaχ或γkmaχ，則合并wP和wk，將以上過程迭代執行，最終使得準則函數 JL穩定到最小值，聚類過程結束。

（4）選取特征點最多的聚類為目標類

聚類過程所產生的包含特征點最多的目標類即標線，然后輸出標線信息，再由運動控制模塊計算出轉向角、速度等控制參數，進而控制智能車的移動［13］。

4 實驗結果與分析

在仿真實驗中，智能車由電源模塊、信息獲取和處理模塊、導航控制與運動模塊等組成，智能車的路徑圖像獲取通過數碼攝像頭來采集，并以文件形式保存在計算機中，通過VC++軟件平臺對此圖像文件進行處理和分析，最后通過標線檢測算法實現標線信息的檢測。對于工作環境中有多個疑似標線的復雜情況，本文算法能夠實時、準確地檢測并檢測出疑似標線特征，識別出特征點最多的目標類，即標線。

實驗中，在測試場地中的引導線為紅色，停止位（或工作位）為藍色。原始采集圖像為RGB彩色圖像，分辨率為320×240像素，采集頻率為30 f/s。圖2中垂直方向中心線為智能車正前方的中心引導線，垂直方向的4條粗標線為引導線，水平方向的1條粗標線為停止位，引導線中已標示出已檢測出的特征點。其中，引導線和停止位的特征點檢測結果如圖3所示。

圖2 標線

圖3 標線的特征點

實驗中設置引導線的紅色閾值為185，停止位標線的藍色閾值為165，標線最大寬度閾值為100，標線最小寬度閾值為30。算法對引導線的特征點計算結果如圖4所示。

圖4 結果輸出

圖4一共有4段引導線，運算時間為28.371 1 ms，算法共檢測出4個聚類。其中，第3類包含特征點最多（10個）被確定為目標類，即真正的引導標線。另外，第4類的特征點數為2，由于少于3個，考慮到標線較長的實際情況，因此忽略不計。檢測結果如表1所示。

表1 疑似標線檢測結果

可見本文算法可以快速檢測標線，滿足視覺導航智能車對實時性的要求。實驗結果說明本文算法可行有效。

5 結束語

針對彩色路徑圖像中的標線檢測算法，本文采用近鄰函數法對顏色特征點進行聚類分析，構造基于類內類間距離的準則函數，找出特征點最多的目標類即引導標線，然后按標線結構將其連通，并輸出運動控制模塊。實驗結果表明，與傳統顏色空間轉換以及基于霍夫變換的邊緣檢測算法相比，該算法的實時性較好，對于視覺導航的智能車有一定的應用價值。

［1］ Yu Qifeng，Shang Yang，Liu Xiaochun，et al.Fullparameter Vision Navigation Based on Scene Matching for Aircrafts［J］.Science China Inform ation Sciences，2014，57（5）：1-10.

［2］ Morioka H，Sangkyu Y，Hasegawa O.Vision-based Mobile Robot’s SLAM and Navigation in Crowded Environments［C］//Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems. Washington D.C.，USA：IEEE Press，2011：3998-4005.

［3］ Yang Ming，Lu Zhengchen，Guo Lindong，et al.Visionbased Environmental Perception and Navigation of Micro-intelligent Vehicles［M］//Sun Fuchun，Li Tianrui，Li Hongbo.Foundations and Applications of Intelligent Systems.Berlin，Germany：Springer，2014：653-665.

［4］ Park C H，K im N H.Precise and Reliable Positioning Based on the Integration of Navigation Satellite System and Vision System［J］.International Journal of Automotive Technology，2014，15（1）：79-87.

［5］ Zang Guoquan，Li Zhanming.Research on Preprocessing of Color Im age for Vision Based Mobile Robot Navigation［J］.Information Technology Journal，2011，10（3）：597-601.

［6］ Bertozzi M，Broggi A，Fascioli A.Vision-based Intelligent Vehicles：State of the A rt and Perspectives［J］. Robotics and Autonomous System，2000，32（1）：1-16.

［7］ Kim Y H，Lee S W，Yang H S，et al.Toward Autonomous Robotic Containment Booms：Visual Servoing for Robust Inter-vehicle Docking of Surface Vehicles［J］. Intelligent Service Robotics，2012，5（1）：1-18.

［8］ Li Ying，Hong Sheng，Huang Jieming，et al.The New Environment Model Building Method of Penetration Mission Based on the Artificial Potencial Field Approach［C］//Proceedings of IEEE International Multidisciplinary Conference on Cognitive Methods in Situation Awareness and Decision Support.Washington D.C.，USA：IEEE Press，2012：121-124.

［9］ 徐 超，沈曉蓉，羅宇鋒，等.視覺導航特征點匹配及誤匹配剔除算法［J］.計算機仿真，2010，27（4）：236-239.

［10］ 朱錚濤，張 宏.基于特征點的形狀匹配技術及其算法實現［J］.計算機工程與設計，2010，31（5）：1096-1099.

［11］ 孫即祥.現代模式識別［M］.長沙：國防科技大學出版社，2002.

［12］ Wei Weiyi，Li Zhanming，Zang Guoquan.Novel Fuzzy Clustering-based Image Segmentation with Simultaneous Uneven Illumination Estimation［J］.Information Technology Journal，2011，10（3）：607-610.

［13］ 吳建民，王民鋼.基于視覺的輪式移動機器人導航問題研究［J］.計算機工程，2014，40（8）：143-146.

編輯 劉 冰

Path Marking Detection Algorithm Based on Color Feature Clustering

MENG Dexina，WANG Minquanb，HU Guoweia
（a.Electronics&Information Institute；b.Haitian M echanical&Electrical Institute，Ningbo Polytechnic，Ningbo 315800，China）

According to the path of color image data volume，high dimension，guide marking detection algorithm and time-consuming problem in visual navigation，a fast marking detection algorithm in path image based on color feature clustering is proposed.Based on the analysis of the common features of marking detection algorithm，it establishes a color sparse matrix on color image，adopts interlacing detection feature point in suspected marking，calculates neighbor coefficient between the each feature point and clusters by using of neighbor function method，finds out the target class with most feature point which is marking，connects the path structure with feature points set，and provides the route navigation information. Experimental results indicate that compared with the conventional color space conversion or edge detection algorithm based on the Hough transform，the speed of this algorithm is fast，and can meet the real-time requirements.

visual navigation；marking detection；nearest neighbors function method；color feature；clustering

孟德欣，王民權，胡國偉.基于顏色特征聚類的路徑標線檢測算法［J］.計算機工程，2015，41（10）：236-239.

英文引用格式：Meng Dexin，Wang Minquan，Hu Guowei.Path Marking Detection Algorithm Based on Color Feature Clustering［J］.Computer Engineering，2015，41（10）：236-239.

1000-3428（2015）10-0236-04

A

TP391.9

寧波市2014年自然科學基金資助項目“基于動態輻射的跟蹤式光伏板聚光量增益的研究”（2014A 610075）。

孟德欣（1976-），男，副教授、碩士，主研方向：圖像處理，模式識別；王民權，教授；胡國偉，博士研究生。

2014-10-28

2014-11-24E-mail：78924661@qq.com