基于PCA-SVM准则改进区域生长的非结构化道路识别

王新晴，孟凡杰，吕高旺，任国亭

(解放军理工大学 野战工程学院，南京 210007)

基于PCA-SVM准则改进区域生长的非结构化道路识别

王新晴，孟凡杰*，吕高旺，任国亭

(解放军理工大学 野战工程学院，南京 210007)

(*通信作者电子邮箱793306433@qq.com)

针对智能车辆在非结构化道路识别中需要采用众多的特征参数，增加了特征融合识别难度与计算复杂度，并且部分背景与道路区域存在相似性会产生道路识别的误分、误判的问题，提出了一种基于主成分分析的支持向量机(PCA-SVM)准则改进区域生长的非结构化道路识别算法。首先，对非结构化道路颜色、纹理等复杂特征信息进行提取，采用PCA对提取的特征信息进行降维;然后,利用降维后的主元特征对SVM进行训练后作为复杂道路单元格的分类器。利用道路位置、起始单元格等先验知识以及道路边界单元格统计特征改进区域生长方法，在单元格生长时利用分类器判别，排除误判区域。实际道路检测结果表明，所提算法具有较好的鲁棒性，能够有效识别非结构化路面区域。对比结果表明，所提算法在保证准确率的同时，将10余维复杂特征信息压缩为3维主元特征，相比传统算法可缩短计算时间一半以上。针对背景与道路相似区域造成的传统算法10%左右的误判问题，所提算法能够有效排除。在野外环境下基于视觉的局部路径规划与导航方面，所提算法为缩短识别时间、排除背景干扰提供了可行途径。

支持向量机；主成分分析；区域生长；非结构化道路识别；智能车辆

0 引言

近年来，随着无人驾驶系统需求的增长，基于机器视觉的道路识别技术成为研究的热点[1-5]。在道路识别中，一般将道路分为结构化道路和非结构化道路，目前结构化道路识别技术相对成熟。在军事上，各类陆地装备多在条件恶劣环境下工作;在民用方面，农用机械等工况多为野外，因此野外条件下的非结构化道路识别在军用和民用方面，均具有重要意义。

非结构化道路具有道路与环境变量复杂、影响因素多的特性，室外环境下非结构化道路的检测与障碍物识别是一个十分复杂的问题，多特征融合识别成为趋势，例如：文献[6-10]中，利用二维熵和轮廓等特征组合对非结构化道路进行检测；文献[11-14]中，利用机器学习的方式对非结构化道路进行检测。针对复杂的特征向量运算量大的问题，特征压缩和分块计算势在必行，如：文献[15-17]利用主成分分析(Principal Component Analysis, PCA)对复杂特征向量进行压缩；文献[18-19]中，算法均采用分块计算。针对非结构化道路背景与道路存在相似区域的影响，目前行业内使用基于模板与区域生长等具有先验知识的算法，例如文献[20-22]利用区域生长进行图像分割。

区域生长以“种子点”向外延伸的生长方式，可有效避免识别区域外的干扰，但针对非结构化道路，传统区域生长算法随机性大、“种子点”难确定、识别后边界模糊。鉴于上述问题，文本研究并提出了一种基于主成分分析的支持向量机(Support Vector Machine based on Principal Component Analysis, PCA-SVM)准则改进区域生长的非结构化道路识别算法，对道路以单元格的方式进行复杂特征提取后，采用PCA对道路特征降维，利用主元特征训练SVM，改进原有区域生长算法并以PCA-SVM为生长准则对非结构化道路进行识别。所提算法更符合人眼识别道路“由近及远”的特点，能够更有效地识别非结构化道路，排除环境中与路面特征相似区域的干扰。

1 PCA-SVM算法

1.1 PCA基本理论

PCA是一种基于Karhunen-loeve变换原理的统计分析方法，其目的是将原数据投影为一个新空间的较少变量，用该空间变量表示原来的数据,以达到数据降维的目的。令x表示为空间中m维随机向量，ω表示为m维单位向量，x在其上的投影为y,则y可表示为x与ω的内积：

其中ω满足约束条件：

主成分分析的目的就是要找到权值向量ω，使表达式E(y2)值最大化，E(y2)可表达为：

E(y2)=E[(ωTx)2]=ωTE[xxT]ω=ωTCxω

由线性代数理论可知，为了使E(y2)值最大化，ω应满足：

Cxωj=λjωj；j=1,2,…

即ω是矩阵Cx的最大特征值对应的特征向量。

1.2 二分类SVM

SVM是一种机器学习方法，其基础是Vapnik创建的统计学习理论(StatisticalLearningTheory,SLT)。针对非结构化道路，可简化为二分类问题，SVM以训练误差最优化为约束条件，通过置信范围最小化进行分类。训练样本集如下：

式中：yi为降维后的数据样本向量；zi为样本标签，zi=1和zi=-1分别代表两类数据样本；P为降维后的数据样本空间。在利用SVM进行分类时，绝大多数问题都是非线性的，这时需要采用满足Mercer条件的核函数K(y,yi)将输入向量映射到高维特征空间中，变成线性可分的数据向量。常用的核函数有：线性核函数(Liner Kernel)、多项式核函数(Polynomial Kernel)、径向基核函数(Radical Basis Function, RBF)、Sigmoid核函数，其表达式分别为：

K(y,yi)LINEAR=yyi

K(y,yi)POLY=(yyi+1)d

K(y,yi)RBF=exp(-‖y-yi‖2/(2σ2))

K(y,yi)Sigmoid=tanh(k(yyi)+θ)

投影后，转化为线性可分问题，采用最优分类函数对训练样本进行分类，最优分类函数表达式为：

f(x)=sgn(ω′·x+b)

则两类样本间距离为D=2|ω′xi+b|/‖ω‖，若取间隔ε=|ω′xi+b|=1，则当满足式(1)时，有最大样本距离D，即所得最优分类平面。

min ‖ω′‖2/2

(1)

s.t.yi(ω′xi+b)-1≥0,∀i

1.3PCA-SVM分类识别方法

基于PCA-SVM的分类识别方法主要包含两个过程，即训练过程和测试(使用)过程。为提高算法效率，无论是训练或测试过程，对图像集皆采用分块的方式进行单元识别。首先对图像单元格进行特征抽取，包括颜色、纹理等10余种，特征集X可表示为：

X=[x1,x2,…,xn]

其中：x1,x2,…,xn为m维列向量，代表不同图像单元的特征值,则特征集X的大小为m×n。对特征集X进行主元分析后，得到的主元特征矩阵Y可表示为：

Y=[y1,y2,…,yl]=ωTX

其中：y1,y2,…,yl为m维列向量，代表不同图像单元的主元特征值。主元特征集Y的大小为m×l(l≪n),利用主元特征向量构造训练样本集：

其中：Z为标签值列向量，zi=1和zi=-1分别代表两类数据样本。PCA-SVM分类器训练、测试过程如图1所示。

图1 PCA-SVM训练与测试流程

2 单元格特征提取与压缩

图像特征的提取和选择是影响后续处理与分析的关键因素,其主要包括颜色、纹理、形状等。在进行特征提取前，对图像进行大小归一化预处理，处理后图像大小为640×480。非结构化道路没有规则的形状，因此形状特征不适合区分非结构化路面与环境信息。颜色、纹理是非结构化路面区别于环境的主要特征。在PCA-SVM训练过程，道路样本选取在车辆正前方，环境样本选取随机环境区域，样本单元格选取如图2所示。

在颜色特征提取方面，选择了符合人的视觉感知的HSV模型。HSV模型通过对颜色的色度(Hue)、饱和度(Saturation)和亮度(Value)进行描述，与人类视觉接近。HSV模型通过亮度分量V和色度分量H分开表示的方式，能够有效避免因光照不均匀而带来图像彩色不均匀的影响。

图2 样本选取

在纹理特征提取方面，利用灰度共生矩阵(GrayLevelCo-occurrenceMatrix,GLCM)得到图像关于排列规则和局部模式的特征，Haralick等[23]根据GLCM定义了14个可以用于纹理分析的特征参数。对单元格进行上述特征参数和粗糙度、对比度提取后利用PCA降维，在保证贡献率为0.97时，取得前三项主元y1、y2、y3。部分路面与环境区域主元特征值如表1所示，其中：标签值“1”为路面区域，“-1”为环境区域。

表1 部分路面主元特征

3 PCA-SVM准则区域生长

区域生长的基本思想是将具有相似性质的像素集合起来构成区域[18]。传统区域生长首先对每个需要分割的区域找到一个种子像素作为生长的起点，根据事先确定的生长或相似准则将种子周围邻域中与种子像素有相同或相似性质的像素，合并到种子像素所在的区域中，将这些新像素当作新的种子像素循环上面的过程，直到再没有满足条件的像素[17]。常采用的生长准则有：灰度差准则、灰度分布统计准则、区域形状准则。 这种生长方式种子点选取对结果影响大，且采用单一准则鲁棒性差。

针对上述问题，本文提出一种改进区域生长算法。首先定义区域生长单元：即区域生长过程中，每次生长和识别的最小单元。如图3所示，区域生长单元应满足如下条件：

1)每个区域生长单元可沿8个方向向邻域内生长，不能生长至已生长区域，如图3(a)。

2)每个单元在满足生长准则时，成为下一种子单元，当判定为不满足生长准则时，判定为终止单元(即结束单元)如图3(b)。

图3 改进的区域生长单元及传递过程

3.1 初始种子单元选定

根据汽车最小半径理论可知，车辆在行驶过程中，在通道宽度内，存在恒定视野区域。根据“车在路上”这一先决位置信息，可以确定车前以车宽为其中一边、另外两边边长为D*的等腰三角形区域内为机器视觉道路特征选取最佳区域。如图4阴影区域，其中D*满足:

式中：d为前悬尺寸；l为轴距；r为汽车环形内半径；b为汽车宽度；r1为汽车最小转弯半径；n为前轮距。

图4 汽车最小半径示意图

在最佳区域内，选取一个32×32大小集合，作为初始种子单元，可保证初始种子单元位于路面区域，避免随机选取造成的误差。

3.2PCA-SVM准则区域生长过程

以PCA-SVM作为区域生长过程的生长准则，针对某一道路模型，融合PCA-SVM准则具体生长流程为：

1)在最佳区域内，随机选取一个32×32大小集合，作为初始种子单元；

2)以种子单元(str)为中心，在不重复条件下取同等大小的邻域单元(32×32)；

3)将邻域单元进行特征提取并PCA降维后，送入预训练的SVM分类器进行分类；

4)若邻域单元为“道路类”，则以该单元为种子单元(str)，返回到步骤2)，若邻域单元为“环境类”，则该单元为终止单元(stp)；

5)继续扫描直到不能发现种子单元有可生长邻域，则结束整个生长过程。

初始种子生长单元个数为1，在步骤4)中，后续种子单元与终止单元个数不一定为1，这样可保证快速弥漫至最大区域，提高算法效率。选取线性核函数，生长过程如图5所示。

图5 生长过程示意图

4 道路实验与分析

本文算法完整流程为：获得图像集后，对图像进行分块预处理，构建训练集，对训练集样本进行特征提取，将提取的特征进行PCA降维后输入参数优化好的SVM进行训练，构造PCA-SVM分类器；由改进区域生长确定邻域单元位置，以邻域单元作为测试样本，对测试样本进行同等参数的特征提取后，输入PCA-SVM分类器中，根据识别结果判定该位置是否为“道路”类，将多个单元识别后放回原位置，直至生长完毕后，将输出的道路区域与环境区域重组，输出识别结果。

实验采用IntelCorei5CPU@ 2.53GHzCPU、4GB内存、Windows7(32位)操作系统为开发环境，通过Flycapture车载单目成像设备，对野外非结构化和半非结构化等复杂道路在行车过程中进行640×480大小图像帧采集，自建非结构化道路数据库进行实验，数据库包含非结构化路段300余种, 能够包含绝大部分路面和环境种类信息。

本文实验主要包含两组对比实验: 1)传统基于像素值区域生长算法与PCA-SVM准则改进区域生长识别效果对比;2)单独基于PCA-SVM算法与PCA-SVM准则改进区域生长识别效果对比。部分实验结果对比如图6所示。

图6 典型非结构化道路实验对比结果

4.1 算法识别效果对比

通过构造样本训练，实验利用PCA-SVM分类器采用线性核函数，准确率为98.3%。针对图6所示半结构化道路2个示例，3种识别算法均能有效识别出非结构化路面区域，但基于PCA-SVM和改进算法识别的道路区域更加完整，边界更明显；针对图6复杂的非结构化道路4个示例，传统区域生长造成较大的错误识别区域，PCA-SVM算法能够完整识别路面区域，但存在较多的误判区域，误判区域的形成，并不是分类器准确率问题，而是由于环境中存在与路面相近的区域。本文算法针对非结构化道路有较好的识别效果，有效避免了误判区域。

4.2 算法误判率和耗时对比实验

本文给出误判率定义: 实验图片中, 识别出非结构化路面之外区域面积占非结构化路面区域的比例。误判率μ的计算式为:

μ=(S总-S路)/S路

式中：S总代表算法识别出区域总面积；S路代表非结构化路面区域面积。 表2为不同算法识别正确率、误判率和耗时对比结果。

表2 不同算法性能对比

由表2可知，传统算法、PCA-SVM算法和本文算法在识别正确率方面, 单独使用PCA-SVM的算法和本文算法明显高于传统算法；在算法识别时间上，采用单元识别的机器学习的算法在识别时间上远远少于基于像素值的传统识别算法，本文算法在识别时间上稍长于单独使用PCA-SVM算法；但在误判率方面, 本文算法相比于传统基于像素值算法和单独使用PCA-SVM算法能够有效减少非结构化路面区域外的误判识别结果。实验验证了本文改进算法能够有效识别非结构化道路，在减少误判率方面有明显改进。

5 结语

针对非结构化道路特征多、融合识别困难、环境与路面存在相似区域容易造成误判区域等问题，提出了基于PCA-SVM准则的改进区域生长算法，实现了复杂多维特征的主元特征提取以及基于主元特征提取后的SVM单元融合识别方法，以PCA-SVM分类器作为改进区域生长准则，排除了复杂非结构化道路环境内相似区域的影响，有效识别了非结构化道路路面区域。

对比实验结果表明，本文方法相比于传统算法在识别正确率、减少误判和减少耗时上有明显优势，基于单元格分类器基础上的改进区域生长算法能够排除误判区域,但对于环境更为复杂的情况，该算法还需要进一步的改进。非结构化道路识别是一个极为复杂的问题，后续还需要对其中某些技术难题进行更深入的研究。

)

[1]HILLELAB,LERNERR,LEVID,etal.Recentprogressinroadandlanedetection:asurvey[J].MachineVisionandApplications, 2014, 25(3): 727-745.

[2] 高华,刘济林.车辆视频导航中道路检测方法研究进展[J].传感器与微系统,2012,31(1):1-3,6.(GAOH,LIUJL.Researchprogressonroaddetectionmethodinvideonavigationforvehicle[J].TransducerandMicrosystemTechnologies, 2012, 31(1): 1-3, 6.)

[3] 龚建伟,叶春兰,姜岩,等.多层感知器自监督在线学习非结构化道路识别[J].北京理工大学学报,2014,34(3):261-266.(GONGJW,YECL,JIANGY,etal.Unstructuredroadrecognitionusingself-supervisedmultilayerperceptrononlinelearningalgorithm[J].TransactionsofBeijingInstituteofTechnology, 2014, 34(3): 261-266)

[4] 王晓彬,马戎,付维平.基于支持向量机的非结构化道路检测[J].科学技术与工程,2011,11(36):9106-9109.(WANGXB,MAR,FUWP.Unstructuredroaddetectionbasedonsupportvectormachine[J].ScienceTechnologyandEngineering, 2011, 11(36): 9106-9109.)

[5] 李青,郑南宁，马琳，等.基于主元神经网络的非结构化道路跟踪[J].机器人,2005,27(3):247-251.(LIQ,ZHENGNN,MAL,etal.Trackingofunstructuredroadbasedonprincipalcomponentanalysisneuralnetworks[J].Robot, 2005, 27(3): 247-251.)

[6] 郭秋梅,黄玉清.基于二维熵和轮廓特征的非结构化道路检测[J].计算机应用,2013,33(7):2005-2008.(GUOQM,HUANGYQ.Unstructuredroaddetectionbasedontwo-dimensionalentropyandcontourfeatures[J].JournalofComputerApplications, 2013, 33(7): 2005-2008.)

[7]MCCALLJC,TRIVEDIMM.Video-basedlaneestimationandtrackingfordriverassistance:survey,system,andevaluation[J].IEEETransactionsonIntelligentTransportationSystems, 2006, 7(1): 20-37.

[8] 王科,黄智,钟志华.基于多特征融合的道路理解方法[J].中国公路学报,2013,26(4):176-183.(WANGK,HUANGZ,ZHONGZH.Multi-featurefusionbasedlaneunderstandingalgorithm[J].ChinaJournalofHighwayandTransport, 2013, 26(4): 176-183.)

[9]WANGYF,DOHNOUNN,ACHIMA.Anovelsystemforrobustlanedetectionandtracking[J].SignalProcessing, 2012, 92(2): 319-344.

[10]BAIL,WANGY.Roadtrackingusingpartialfilterswithpartitionsamplingandauxiliaryvariables[J].ComputerVisionandImageUnderstanding, 2011, 115(10): 1463-1471.

[11] 高国琴,李明.基于K-means算法的温室移动机器人导航路径识别[J].农业工程学报,2014,30(7):25-33.(GAOGQ,LIM.NavigatingpathrecognitionforgreenhousemobilerobotbasedonK-meansalgorithm[J].TransactionsoftheChineseSocietyofAgriculturalEngineering, 2014, 30(7): 25-33.)

[12]MALDONADO-BASCONS,LAFUENTE-ARROYOS,GIL-JIMENEZP,etal.Road-signdetectionandrecognitionbasedonsupportvectormachines[J].IEEETransactionsonIntelligentTransportationSystems, 2007, 8(2):264-278.

[13]KUMARASWYR,PRABHULV,SUCHITHRAK,etal.SVMbasedclassificationoftrafficsignsforreal-timeembeddedplatform[C]//ProceedingsoftheFirstInternationalConferenceonAdvancesinComputingandCommunications,CCIS193.Berlin:Springer, 2011: 339-348.

[14] 杨力,刘济林.基于非监督特征学习的分叉道路检测算法[J].浙江大学学报(工学版),2014,48(9):1558-1563.(YANGL,LIUJL.Roaddetectionalgorithmforcrossroadbasedonunsupervisedfeaturelearning[J].JournalofZhejiangUniversity(EngineeringScience), 2014, 48(9): 1558-1563.)

[15] 朱志洁,张宏伟,韩军,等.基于PCA-BP神经网络的煤与瓦斯突出预测研究[J].中国安全科学学报,2013,23(4):45-50.(ZHUZJ,ZHANGHW,HANJ,etal.PredictionofcoalandgasoutburstbasedonPCA-BPneuralnetwork[J].ChinaSafetyScienceJournal, 2013, 23(4): 45-50.)

[16] 刘双印,徐龙琴,李振波,等.基于PCA-MCAFA-LSSVM的养殖水质pH值预测模型[J].农业机械学报,2014,45(5):239-246.(LIUSY,XULQ,LIZB,etal.ForecastingmodelforpHvalueofaquaculturewaterqualitybasedonPCA-MCAFA-LSSVM[J].TransactionsoftheChineseSocietyofAgriculturalMachinery, 2014, 45(5): 239-246.)

[17] 王丽荣,王建蕾.基于主成分分析的唇部轮廓建模[J].光学精密工程,2012,20(12):2768-2772.(WANGLR,WANGJL.LipcontourmodelingbasedonPCA[J].OpticsandPrecisionEngineering, 2012, 20(12): 2768-2772.)

[18] 操小文,薄华.基于卷积神经网络的手势识别研究[J].微型机与应用,2016,35(9):55-57.(CAOXW,BOH.StudyongesturerecognitionbasedonCNN[J].Microcomputer&ItsApplications, 2016, 35(9): 55-57.)

[19] 崔巍,杨健,常合友.基于多通道卷积神经网络的非结构化道路路表分析[J].计算机应用与软件,2016,33(1):159-162.(CUIW,YANGJ,CHANGHY.Analyzingterrainofunstructuredroadbasedonmulti-channelconvolutionneuralnetwork[J].ComputerApplicationsandSoftware, 2016, 33(1): 159-162.)

[20] 倪鼎,马洪兵.基于区域生长的多源遥感图像配准[J].自动化学报,2014,40(6):1058-1067.(NID,MAHB.Automaticregistrationofmulti-sourceremotesensingimagesbasedonregiongrowing[J].ActaAutomaticaSinica, 2014, 40(6): 1058-1067.)

[21] 杨家红,刘杰,钟坚成,等.结合分水岭与自动种子区域生长的彩色图像分割算法[J].中国图象图形学报,2010,15(1):63-68.(YANGJH,LIUJ,ZHONGJC,etal.Acolorimagesegmentationalgorithmbyintegratingwatershedwithautomaticseededregiongrowing[J].JournalofImageandGraphics, 2010, 15(1): 63-68.)

[22] 余洁,余峰,张晶,等.结合区域生长与道路基元的高分辨率遥感影像道路提取[J].武汉大学学报(信息科学版), 2013,38(7): 761-765.(YUJ,YUF,ZHANGJ,etal.Highresolutionremotesensingimageroadextractioncombiningregiongrowingandroad-unit[J].GeomanticandInformationScienceofWuhanUniversity, 2013, 38(7): 761-765.)

[23]HARALICKRM,SHANMUGAMK,DINSTEINI.Texturalfeaturesforimageclassification[J].IEEETransactionsonSystems,ManandCybernetics, 1973, 3(6): 610-621.

ThisworkispartiallysupportedbytheNationalKeyResearchandDevelopmentProgram(2016YFC0802900),theNationalNaturalScienceFoundationofChina(61671470).

WANG Xinqing, born in 1963, Ph. D., professor. His research interest include machinery and electronics, fault diagnosis, computer image and vision, artificial neural network.

MENG Fanjie, born in 1992, M. S. candidate. His research interests include computer image and vision, artificial neural network.

LYU Gaowang, born in 1991, M. S. candidate. His research interests include computer image and vision, artificial neural network.

REN Guoting, born in 1993, M. S. candidate. His research interests include artificial neural network, multi-line laser radar application.

Unstructured road detection based on improved region growing with PCA-SVM rule

WANG Xinqing, MENG Fanjie*, LYU Gaowang, REN Guoting

(CollegeofFieldEngineering,PLAUniversityofScienceandTechnology,NanjingJiangsu210007,China)

Intelligent vehicles need to use many characteristic parameters in unstructured road detection, which makes the feature fusion recognition difficult and computation complex, and the similarity of some road area and background may produce the mistake distinguishment and judgement of road identification. In order to solve the problems, an unstructured road detection method based on improved region growing with Principal Component Analysis-Support Vector Machine (PCA-SVM) rule was proposed. Firstly, the complex characteristic parameters such as color and texture of unstructured road were extracted, and then the PCA was used to reduce the dimension of the extracted characteristic information. The SVM trained with the primary characteristics reduced by PCA was used to be the classifier of the complex road cells. The priori knowledge such as the location of road, the initial cell and the characteristics of road boundary cells were used to improve the region growing method, and the classifier was used to decide the way of growing in cell growth for eliminating miscalculation area. The test results of actual roads show that, the proposed method has good adaptability and robustness, and can identify the unstructured road area effectively. The comparison results show that, compared with the traditional algorithm, the proposed method can shorten the calculation time by more than half through cutting characteristics from ten dimensions to three dimensions in ensuring the accuracy at the same time. The proposed method can also eliminate the 10% of miscalculation areas made by some similar areas of road and background for the traditional algorithm. The proposed method can provide a feasible way to shorten the recognition time and eliminate background interference in local path planning and navigation based on vision in the wild environment.

Support Vector Machine (SVM); Principal Component Analysis (PCA); region growing; unstructured road detection; intelligent vehicle

2016- 11- 02;

2016- 12- 21。

国家重点研发计划项目(2016YFC0802900)；国家自然科学基金资助项目(61671470)。

王新晴(1963—)，男，江苏泰州人，教授，博士，主要研究方向：机械电子、故障诊断、计算机图像和视觉、人工神经网络；孟凡杰(1992—)，男，辽宁辽阳人，硕士研究生，主要研究方向：计算机图像和视觉、人工神经网络； 吕高旺(1991—)，男，江苏徐州人，硕士研究生，主要研究方向：计算机图像和视觉、人工神经网络； 任国亭(1993—)，男，内蒙古乌兰察布人，硕士研究生，主要研究方向：人工神经网络、多线激光雷达应用。

1001- 9081(2017)06- 1782- 05

10.11772/j.issn.1001- 9081.2017.06.1782

TP391.4

A