孟德欣，王民權(quán)，胡國偉

（寧波職業(yè)技術(shù)學(xué)院 a.電子信息學(xué)院；b.海天機(jī)電學(xué)院，浙江 寧波315800）

基于顏色特征聚類的路徑標(biāo)線檢測算法

孟德欣a，王民權(quán)b，胡國偉a

（寧波職業(yè)技術(shù)學(xué)院 a.電子信息學(xué)院；b.海天機(jī)電學(xué)院，浙江 寧波315800）

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

視覺導(dǎo)航；標(biāo)線檢測；最近鄰函數(shù)法；顏色特征；聚類

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

1 概述

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

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

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

2 近鄰函數(shù)法的聚類模型

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

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

圖1 類內(nèi)條狀或線狀分布

考慮到路徑圖像中標(biāo)線為條狀分布，本文采用近鄰函數(shù)法對標(biāo)線特征點(diǎn)進(jìn)行聚類，引入類內(nèi)、類間損失函數(shù)作為評價依據(jù)，構(gòu)造聚類準(zhǔn)則函數(shù)，最后選出聚類結(jié)果中包含特征點(diǎn)最多的類設(shè)為目標(biāo)類。

定義1 近鄰函數(shù)

在圖像矩陣中，考慮像素點(diǎn)樣本χi，計(jì)算χi與其他各樣本間的近鄰函數(shù)值，表示為：

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

定義2 類內(nèi)連接損失

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

定義3 類間連接損失

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

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

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

記wP類的類內(nèi)最大近鄰函數(shù)值：

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

其中，當(dāng) βPq＞γPmaχ，βPq＞γkmaχ，表示類間近鄰函數(shù)值大于類內(nèi)最大近鄰函數(shù)值，說明聚類結(jié)果是合理，其他情況則需進(jìn)行調(diào)整。

定義4 聚類準(zhǔn)則函數(shù)

在計(jì)算出類間損失函數(shù) χPq的基礎(chǔ)上，類間總損失函數(shù)定義如下：

聚類的目標(biāo)是使各 βPq盡可能大，γPmaχ盡可能小，則構(gòu)造聚類準(zhǔn)則函數(shù)如下：

每次對2個類合并，這樣聚類準(zhǔn)則函數(shù)的值每次都要增加，若是函數(shù)值的增加在每一次合并時都是最小的，則得到的分類結(jié)果為最優(yōu)。否則，則需重復(fù)此過程。

3 標(biāo)線檢測算法

在采集路徑圖像過程中，由于受到環(huán)境噪聲的干擾等原因造成噪聲產(chǎn)生，圖像信息會有所丟失。故在標(biāo)線檢測算法先對圖像預(yù)處理，包括去噪、設(shè)置適當(dāng)?shù)拈撝到㈩伾∈杈仃囘@樣可以減少算法處理時間，利用隔行檢測疑似標(biāo)線的顏色特征點(diǎn)，接著利用近鄰函數(shù)法對特征點(diǎn)聚類，選取特征點(diǎn)最多的類別為目標(biāo)類，即為標(biāo)線，同時給出控制指令，下達(dá)給運(yùn)動控制模塊。

標(biāo)線檢測算法的執(zhí)行過程如下：

（1）圖像預(yù)處理

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

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

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

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

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

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

（2）隔行檢測顏色特征點(diǎn)

在對圖像預(yù)處理后，通過設(shè)置閾值對圖像水平方面進(jìn)行隔行掃描，檢測標(biāo)線的顏色特征點(diǎn)?？紤]到標(biāo)線連續(xù)顏色無跳躍的實(shí)際情況，隔行掃描的處理算法是合理的，能夠有效節(jié)省算法執(zhí)行時間。經(jīng)實(shí)驗(yàn)得出，行間距設(shè)置為40行 ～60行之間比較合適。在掃描過程中，顏色特征點(diǎn)檢測需設(shè)置閾值來進(jìn)行判斷，算法中根據(jù)標(biāo)線的寬度等先驗(yàn)知識預(yù)先設(shè)置了標(biāo)線顏色、寬度等信息的閾值，在隔行掃描過程中只有滿足大于顏色、寬度閾值的一些像素點(diǎn)才被確認(rèn)為特征點(diǎn)并存儲起來。

（3）對疑似顏色特征點(diǎn)進(jìn)行聚類

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

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

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

在初始聚類中，計(jì)算 βPq，γPmaχ，γkmaχ，如 βPq小于或等于γPmaχ或γkmaχ，則合并wP和wk，將以上過程迭代執(zhí)行，最終使得準(zhǔn)則函數(shù) JL穩(wěn)定到最小值，聚類過程結(jié)束。

（4）選取特征點(diǎn)最多的聚類為目標(biāo)類

聚類過程所產(chǎn)生的包含特征點(diǎn)最多的目標(biāo)類即標(biāo)線，然后輸出標(biāo)線信息，再由運(yùn)動控制模塊計(jì)算出轉(zhuǎn)向角、速度等控制參數(shù)，進(jìn)而控制智能車的移動［13］。

4 實(shí)驗(yàn)結(jié)果與分析

在仿真實(shí)驗(yàn)中，智能車由電源模塊、信息獲取和處理模塊、導(dǎo)航控制與運(yùn)動模塊等組成，智能車的路徑圖像獲取通過數(shù)碼攝像頭來采集，并以文件形式保存在計(jì)算機(jī)中，通過VC++軟件平臺對此圖像文件進(jìn)行處理和分析，最后通過標(biāo)線檢測算法實(shí)現(xiàn)標(biāo)線信息的檢測。對于工作環(huán)境中有多個疑似標(biāo)線的復(fù)雜情況，本文算法能夠?qū)崟r、準(zhǔn)確地檢測并檢測出疑似標(biāo)線特征，識別出特征點(diǎn)最多的目標(biāo)類，即標(biāo)線。

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

圖2 標(biāo)線

圖3 標(biāo)線的特征點(diǎn)

實(shí)驗(yàn)中設(shè)置引導(dǎo)線的紅色閾值為185，停止位標(biāo)線的藍(lán)色閾值為165，標(biāo)線最大寬度閾值為100，標(biāo)線最小寬度閾值為30。算法對引導(dǎo)線的特征點(diǎn)計(jì)算結(jié)果如圖4所示。

圖4 結(jié)果輸出

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

表1 疑似標(biāo)線檢測結(jié)果

可見本文算法可以快速檢測標(biāo)線，滿足視覺導(dǎo)航智能車對實(shí)時性的要求。實(shí)驗(yàn)結(jié)果說明本文算法可行有效。

5 結(jié)束語

針對彩色路徑圖像中的標(biāo)線檢測算法，本文采用近鄰函數(shù)法對顏色特征點(diǎn)進(jìn)行聚類分析，構(gòu)造基于類內(nèi)類間距離的準(zhǔn)則函數(shù)，找出特征點(diǎn)最多的目標(biāo)類即引導(dǎo)標(biāo)線，然后按標(biāo)線結(jié)構(gòu)將其連通，并輸出運(yùn)動控制模塊。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)顏色空間轉(zhuǎn)換以及基于霍夫變換的邊緣檢測算法相比，該算法的實(shí)時性較好，對于視覺導(dǎo)航的智能車有一定的應(yīng)用價值。

［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，F(xiàn)ascioli 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］ 徐 超，沈曉蓉，羅宇鋒，等.視覺導(dǎo)航特征點(diǎn)匹配及誤匹配剔除算法［J］.計(jì)算機(jī)仿真，2010，27（4）：236-239.

［10］ 朱錚濤，張 宏.基于特征點(diǎn)的形狀匹配技術(shù)及其算法實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010，31（5）：1096-1099.

［11］ 孫即祥.現(xiàn)代模式識別［M］.長沙：國防科技大學(xué)出版社，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ī)器人導(dǎo)航問題研究［J］.計(jì)算機(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

孟德欣，王民權(quán)，胡國偉.基于顏色特征聚類的路徑標(biāo)線檢測算法［J］.計(jì)算機(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年自然科學(xué)基金資助項(xiàng)目“基于動態(tài)輻射的跟蹤式光伏板聚光量增益的研究”（2014A 610075）。

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

2014-10-28

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