近年来,随着无人驾驶系统需求的增长,基于机器视觉的道路识别技术成为研究的热点[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与ω的内积:
$ \mathit{\boldsymbol{y}}{\rm{ = [}}\mathit{\boldsymbol{\omega }}{\rm{, }}\mathit{\boldsymbol{x}}{\rm{] = }}\sum\limits_{{\mathop{\rm i}\nolimits} {\rm{ = 1}}}^n {{\mathit{\boldsymbol{\omega }}_i}} {\mathit{\boldsymbol{x}}_{\rm{i}}}{\rm{ = }}{\mathit{\boldsymbol{\omega }}^{\rm{T}}}\mathit{\boldsymbol{x}} $ |
其中ω满足约束条件:
$ \left\| \mathit{\boldsymbol{\omega }} \right\| = \sqrt {\mathit{\boldsymbol{\omega }}{\mathit{\boldsymbol{\omega }}^{\rm{T}}}} = 1 $ |
主成分分析的目的就是要找到权值向量ω,使表达式E(y2)值最大化,E(y2)可表达为:
$ E\left( {{\mathit{\boldsymbol{y}}^2}} \right) = E\left[{{{\left( {{\mathit{\boldsymbol{\omega }}^{\rm{T}}}\mathit{\boldsymbol{x}}} \right)}^2}} \right] = {\mathit{\boldsymbol{\omega }}^{\rm{T}}}E\left[{\mathit{\boldsymbol{x}}{\mathit{\boldsymbol{x}}^{\rm{T}}}} \right]\mathit{\boldsymbol{\omega }} = {\mathit{\boldsymbol{\omega }}^{\rm{T}}}{\mathit{\boldsymbol{C}}_\mathit{\boldsymbol{x}}}\mathit{\boldsymbol{\omega }} $ |
由线性代数理论可知,为了使E(y2)值最大化,ω应满足:
Cxωj=λjωj;j=1, 2, …
即ω是矩阵Cx的最大特征值对应的特征向量。
1.2 二分类SVMSVM是一种机器学习方法,其基础是Vapnik创建的统计学习理论(Statistical Learning Theory, SLT)。针对非结构化道路,可简化为二分类问题,SVM以训练误差最优化为约束条件,通过置信范围最小化进行分类。训练样本集如下:
$ \mathit{\boldsymbol{S}} = \left\{ {\left( {{\mathit{\boldsymbol{y}}_i}, {z_i}} \right)|{\mathit{\boldsymbol{y}}_i} \in \mathit{\boldsymbol{P}}, {z_i} \in \left\{ {-1, 1} \right\}} \right\}_{i = 1}^s $ |
式中:yi为降维后的数据样本向量;zi为样本标签,zi=1和zi=-1分别代表两类数据样本;P为降维后的数据样本空间。在利用SVM进行分类时,绝大多数问题都是非线性的,这时需要采用满足Mercer条件的核函数K(y, yi)将输入向量映射到高维特征空间中,变成线性可分的数据向量。常用的核函数有:线性核函数(Liner Kernel)、多项式核函数(Polynomial Kernel)、径向基核函数(Radical Basis Function, RBF)、Sigmoid核函数,其表达式分别为:
$ \begin{array}{l} K{\left( {\mathit{\boldsymbol{y}}, {\mathit{\boldsymbol{y}}_i}} \right)_{{\rm{LINEAR}}}} = \mathit{\boldsymbol{y}}{\mathit{\boldsymbol{y}}_i}\\ K{\left( {\mathit{\boldsymbol{y}}, {\mathit{\boldsymbol{y}}_i}} \right)_{{\rm{POLY}}}} = {\left( {\mathit{\boldsymbol{y}}{\mathit{\boldsymbol{y}}_i} + 1} \right)^d}\\ K{\left( {\mathit{\boldsymbol{y}}, {\mathit{\boldsymbol{y}}_i}} \right)_{{\rm{RBF}}}} = {\rm{exp}}\left( {-{{\left\| {\mathit{\boldsymbol{y}}-{\mathit{\boldsymbol{y}}_i}} \right\|}^1}/\left( {2{\sigma ^2}} \right)} \right)\\ K{\left( {\mathit{\boldsymbol{y}}, {\mathit{\boldsymbol{y}}_i}} \right)_{{\rm{Singmoid}}}} = {\rm{tanh}}\left( {k\left( {\mathit{\boldsymbol{y}}{\mathit{\boldsymbol{y}}_i}} \right) + \theta } \right) \end{array} $ |
投影后,转化为线性可分问题,采用最优分类函数对训练样本进行分类,最优分类函数表达式为:
f(x)=sgn(ω′·x+b)
则两类样本间距离为D=2|ω′xi+b|/‖ω‖,若取间隔ε=|ω′xi+b|=1,则当满足式(1) 时,有最大样本距离D,即所得最优分类平面。
$ \begin{array}{l} \;\;\;\;\;{\rm{min}}{\left\| {\mathit{\boldsymbol{\omega }}'} \right\|^2}/2\\ {\rm{s}}{\rm{.t}}{\rm{.}}\;\;\;\;{\mathit{\boldsymbol{y}}_i}\left( {\mathit{\boldsymbol{\omega }}'{\mathit{\boldsymbol{x}}_i} + b} \right)-1 \ge 0, {\forall _i} \end{array} $ | (1) |
基于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), 利用主元特征向量构造训练样本集:
$ \mathit{\boldsymbol{S}} = \left\{ {\mathit{\boldsymbol{Y}}, \mathit{\boldsymbol{Z}}} \right\} = \left\{ {\left( {{\mathit{\boldsymbol{y}}_i}, {z_i}} \right)|{\mathit{\boldsymbol{y}}_i} \in \mathit{\boldsymbol{P}}, {z_i} \in \left\{ {-1, 1} \right\}} \right\}_{i = 1}^l $ |
其中:Z为标签值列向量,zi=1和zi=-1分别代表两类数据样本。PCA-SVM分类器训练、测试过程如图 1所示。
图像特征的提取和选择是影响后续处理与分析的关键因素, 其主要包括颜色、纹理、形状等。在进行特征提取前,对图像进行大小归一化预处理,处理后图像大小为640×480。非结构化道路没有规则的形状,因此形状特征不适合区分非结构化路面与环境信息。颜色、纹理是非结构化路面区别于环境的主要特征。在PCA-SVM训练过程,道路样本选取在车辆正前方,环境样本选取随机环境区域,样本单元格选取如图 2所示。
在颜色特征提取方面,选择了符合人的视觉感知的HSV模型。HSV模型通过对颜色的色度(Hue)、饱和度(Saturation)和亮度(Value)进行描述,与人类视觉接近。HSV模型通过亮度分量V和色度分量H分开表示的方式,能够有效避免因光照不均匀而带来图像彩色不均匀的影响。
在纹理特征提取方面,利用灰度共生矩阵(Gray Level Co-occurrence Matrix, GLCM)得到图像关于排列规则和局部模式的特征,Haralick等[23]根据GLCM定义了14个可以用于纹理分析的特征参数。对单元格进行上述特征参数和粗糙度、对比度提取后利用PCA降维,在保证贡献率为0.97时,取得前三项主元y1、y2、y3。部分路面与环境区域主元特征值如表 1所示,其中:标签值“1”为路面区域,“-1”为环境区域。
区域生长的基本思想是将具有相似性质的像素集合起来构成区域[18]。传统区域生长首先对每个需要分割的区域找到一个种子像素作为生长的起点,根据事先确定的生长或相似准则将种子周围邻域中与种子像素有相同或相似性质的像素,合并到种子像素所在的区域中,将这些新像素当作新的种子像素循环上面的过程,直到再没有满足条件的像素[17]。常采用的生长准则有:灰度差准则、灰度分布统计准则、区域形状准则。这种生长方式种子点选取对结果影响大,且采用单一准则鲁棒性差。
针对上述问题,本文提出一种改进区域生长算法。首先定义区域生长单元:即区域生长过程中,每次生长和识别的最小单元。如图 3所示,区域生长单元应满足如下条件:
1) 每个区域生长单元可沿8个方向向邻域内生长,不能生长至已生长区域,如图 3(a)。
2) 每个单元在满足生长准则时,成为下一种子单元,当判定为不满足生长准则时,判定为终止单元(即结束单元)如图 3(b)。
3.1 初始种子单元选定根据汽车最小半径理论可知,车辆在行驶过程中,在通道宽度内,存在恒定视野区域。根据“车在路上”这一先决位置信息,可以确定车前以车宽为其中一边、另外两边边长为D*的等腰三角形区域内为机器视觉道路特征选取最佳区域。如图 4阴影区域,其中D*满足:
$ {D^*} = \left( {\sqrt {{{(l + d)}^2} + {{(r + b)}^2}}-\sqrt {{r_1}^2 + {l^2}} + \left( {b + n} \right)/2} \right)/2 $ |
式中:d为前悬尺寸;l为轴距;r为汽车环形内半径;b为汽车宽度;r1为汽车最小转弯半径;n为前轮距。
在最佳区域内,选取一个32×32大小集合,作为初始种子单元,可保证初始种子单元位于路面区域,避免随机选取造成的误差。
3.2 PCA-SVM准则区域生长过程以PCA-SVM作为区域生长过程的生长准则,针对某一道路模型,融合PCA-SVM准则具体生长流程为:
1) 在最佳区域内,随机选取一个32×32大小集合,作为初始种子单元;
2) 以种子单元(str)为中心,在不重复条件下取同等大小的邻域单元(32×32);
3) 将邻域单元进行特征提取并PCA降维后,送入预训练的SVM分类器进行分类;
4) 若邻域单元为“道路类”,则以该单元为种子单元(str),返回到步骤2),若邻域单元为“环境类”,则该单元为终止单元(stp);
5) 继续扫描直到不能发现种子单元有可生长邻域,则结束整个生长过程。
初始种子生长单元个数为1,在步骤4) 中,后续种子单元与终止单元个数不一定为1,这样可保证快速弥漫至最大区域,提高算法效率。选取线性核函数,生长过程如图 5所示。
本文算法完整流程为:获得图像集后,对图像进行分块预处理,构建训练集,对训练集样本进行特征提取,将提取的特征进行PCA降维后输入参数优化好的SVM进行训练,构造PCA-SVM分类器;由改进区域生长确定邻域单元位置,以邻域单元作为测试样本,对测试样本进行同等参数的特征提取后,输入PCA-SVM分类器中,根据识别结果判定该位置是否为“道路”类,将多个单元识别后放回原位置,直至生长完毕后,将输出的道路区域与环境区域重组,输出识别结果。
实验采用Intel Core i5 CPU @ 2.53 GHz CPU、4 GB内存、Windows 7(32位)操作系统为开发环境,通过Flycapture车载单目成像设备,对野外非结构化和半非结构化等复杂道路在行车过程中进行640×480大小图像帧采集,自建非结构化道路数据库进行实验,数据库包含非结构化路段300余种, 能够包含绝大部分路面和环境种类信息。
本文实验主要包含两组对比实验: 1) 传统基于像素值区域生长算法与PCA-SVM准则改进区域生长识别效果对比; 2) 单独基于PCA-SVM算法与PCA-SVM准则改进区域生长识别效果对比。部分实验结果对比如图 6所示。
通过构造样本训练,实验利用PCA-SVM分类器采用线性核函数,准确率为98.3%。针对图 6所示半结构化道路2个示例,3种识别算法均能有效识别出非结构化路面区域,但基于PCA-SVM和改进算法识别的道路区域更加完整,边界更明显;针对图 6复杂的非结构化道路4个示例,传统区域生长造成较大的错误识别区域,PCA-SVM算法能够完整识别路面区域,但存在较多的误判区域,误判区域的形成,并不是分类器准确率问题,而是由于环境中存在与路面相近的区域。本文算法针对非结构化道路有较好的识别效果,有效避免了误判区域。
4.2 算法误判率和耗时对比实验本文给出误判率定义:实验图片中, 识别出非结构化路面之外区域面积占非结构化路面区域的比例。误判率μ的计算式为:
μ=(S总-S路)/S路
式中:S总代表算法识别出区域总面积;S路代表非结构化路面区域面积。表 2为不同算法识别正确率、误判率和耗时对比结果。
由表 2可知,传统算法、PCA-SVM算法和本文算法在识别正确率方面, 单独使用PCA-SVM的算法和本文算法明显高于传统算法;在算法识别时间上,采用单元识别的机器学习的算法在识别时间上远远少于基于像素值的传统识别算法,本文算法在识别时间上稍长于单独使用PCA-SVM算法;但在误判率方面, 本文算法相比于传统基于像素值算法和单独使用PCA-SVM算法能够有效减少非结构化路面区域外的误判识别结果。实验验证了本文改进算法能够有效识别非结构化道路,在减少误判率方面有明显改进。
5 结语针对非结构化道路特征多、融合识别困难、环境与路面存在相似区域容易造成误判区域等问题,提出了基于PCA-SVM准则的改进区域生长算法,实现了复杂多维特征的主元特征提取以及基于主元特征提取后的SVM单元融合识别方法,以PCA-SVM分类器作为改进区域生长准则,排除了复杂非结构化道路环境内相似区域的影响,有效识别了非结构化道路路面区域。
对比实验结果表明,本文方法相比于传统算法在识别正确率、减少误判和减少耗时上有明显优势,基于单元格分类器基础上的改进区域生长算法能够排除误判区域, 但对于环境更为复杂的情况,该算法还需要进一步的改进。非结构化道路识别是一个极为复杂的问题,后续还需要对其中某些技术难题进行更深入的研究。
[1] | HILLEL A B, LERNER R, LEVI D, et al. Recent progress in road and lane detection:a survey[J]. Machine Vision and Applications, 2014, 25(3): 727-745. doi: 10.1007/s00138-011-0404-2 |
[2] | 高华, 刘济林. 车辆视频导航中道路检测方法研究进展[J]. 传感器与微系统, 2012, 31(1): 1-3, 6. ( GAO H, LIU J L. Research progress on road detection method in video navigation for vehicle[J]. Transducer and Microsystem Technologies, 2012, 31(1): 1-3, 6. ) |
[3] | 龚建伟, 叶春兰, 姜岩, 等. 多层感知器自监督在线学习非结构化道路识别[J]. 北京理工大学学报, 2014, 34(3): 261-266. ( GONG J W, YE C L, JIANG Y, et al. Unstructured road recognition using self-supervised multilayer perceptron online learning algorithm[J]. Transactions of Beijing Institute of Technology, 2014, 34(3): 261-266. ) |
[4] | 王晓彬, 马戎, 付维平. 基于支持向量机的非结构化道路检测[J]. 科学技术与工程, 2011, 11(36): 9106-9109. ( WANG X B, MA R, FU W P. Unstructured road detection based on support vector machine[J]. Science Technology and Engineering, 2011, 11(36): 9106-9109. doi: 10.3969/j.issn.1671-1815.2011.36.039 ) |
[5] | 李青, 郑南宁, 马琳, 等. 基于主元神经网络的非结构化道路跟踪[J]. 机器人, 2005, 27(3): 247-251. ( LI Q, ZHENG N N, MA L, et al. Tracking of unstructured road based on principal component analysis neural networks[J]. Robot, 2005, 27(3): 247-251. ) |
[6] | 郭秋梅, 黄玉清. 基于二维熵和轮廓特征的非结构化道路检测[J]. 计算机应用, 2013, 33(7): 2005-2008. ( GUO Q M, HUANG Y Q. Unstructured road detection based on two-dimensional entropy and contour features[J]. Journal of Computer Applications, 2013, 33(7): 2005-2008. ) |
[7] | MCCALL J C, TRIVEDI M M. Video-based lane estimation and tracking for driver assistance:survey, system, and evaluation[J]. IEEE Transactions on Intelligent Transportation Systems, 2006, 7(1): 20-37. doi: 10.1109/TITS.2006.869595 |
[8] | 王科, 黄智, 钟志华. 基于多特征融合的道路理解方法[J]. 中国公路学报, 2013, 26(4): 176-183. ( WANG K, HUANG Z, ZHONG Z H. Multi-feature fusion based lane understanding algorithm[J]. China Journal of Highway and Transport, 2013, 26(4): 176-183. ) |
[9] | WANG Y F, DOHNOUN N, ACHIM A. A novel system for robust lane detection and tracking[J]. Signal Processing, 2012, 92(2): 319-344. doi: 10.1016/j.sigpro.2011.07.019 |
[10] | BAI L, WANG Y. Road tracking using partial filters with partition sampling and auxiliary variables[J]. Computer Vision and Image Understanding, 2011, 115(10): 1463-1471. doi: 10.1016/j.cviu.2011.06.005 |
[11] | 高国琴, 李明. 基于K-means算法的温室移动机器人导航路径识别[J]. 农业工程学报, 2014, 30(7): 25-33. ( GAO G Q, LI M. Navigating path recognition for greenhouse mobile robot based on K-means algorithm[J]. Transactions of the Chinese Society of Agricultural Engineering, 2014, 30(7): 25-33. ) |
[12] | MALDONADO-BASCON S, LAFUENTE-ARROYO S, GIL-JIMENEZ P, et al. Road-sign detection and recognition based on support vector machines[J]. IEEE Transactions on Intelligent Transportation Systems, 2007, 8(2): 264-278. doi: 10.1109/TITS.2007.895311 |
[13] | KUMARASWY R, PRABHU L V, SUCHITHRA K, et al. SVM based classification of traffic signs for real-time embedded platform[C]//Proceedings of the First International Conference on Advances in Computing and Communications, CCIS 193. Berlin:Springer, 2011:339-348. |
[14] | 杨力, 刘济林. 基于非监督特征学习的分叉道路检测算法[J]. 浙江大学学报(工学版), 2014, 48(9): 1558-1563. ( YANG L, LIU J L. Road detection algorithm for crossroad based on unsupervised feature learning[J]. Journal of Zhejiang University (Engineering Science), 2014, 48(9): 1558-1563. ) |
[15] | 朱志洁, 张宏伟, 韩军, 等. 基于PCA-BP神经网络的煤与瓦斯突出预测研究[J]. 中国安全科学学报, 2013, 23(4): 45-50. ( ZHU Z J, ZHANG H W, HAN J, et al. Prediction of coal and gas outburst based on PCA-BP neural network[J]. China Safety Science Journal, 2013, 23(4): 45-50. ) |
[16] | 刘双印, 徐龙琴, 李振波, 等. 基于PCA-MCAFA-LSSVM的养殖水质pH值预测模型[J]. 农业机械学报, 2014, 45(5): 239-246. ( LIU S Y, XU L Q, LI Z B, et al. Forecasting model for pH value of aquaculture water quality based on PCA-MCAFA-LSSVM[J]. Transactions of the Chinese Society of Agricultural Machinery, 2014, 45(5): 239-246. doi: 10.6041/j.issn.1000-1298.2014.05.037 ) |
[17] | 王丽荣, 王建蕾. 基于主成分分析的唇部轮廓建模[J]. 光学精密工程, 2012, 20(12): 2768-2772. ( WANG L R, WANG J L. Lip contour modeling based on PCA[J]. Optics and Precision Engineering, 2012, 20(12): 2768-2772. ) |
[18] | 操小文, 薄华. 基于卷积神经网络的手势识别研究[J]. 微型机与应用, 2016, 35(9): 55-57. ( CAO X W, BO H. Study on gesture recognition based on CNN[J]. Microcomputer & Its Applications, 2016, 35(9): 55-57. ) |
[19] | 崔巍, 杨健, 常合友. 基于多通道卷积神经网络的非结构化道路路表分析[J]. 计算机应用与软件, 2016, 33(1): 159-162. ( CUI W, YANG J, CHANG H Y. Analyzing terrain of unstructured road based on multi-channel convolution neural network[J]. Computer Applications and Software, 2016, 33(1): 159-162. ) |
[20] | 倪鼎, 马洪兵. 基于区域生长的多源遥感图像配准[J]. 自动化学报, 2014, 40(6): 1058-1067. ( NI D, MA H B. Automatic registration of multi-source remote sensing images based on region growing[J]. Acta Automatica Sinica, 2014, 40(6): 1058-1067. ) |
[21] | 杨家红, 刘杰, 钟坚成, 等. 结合分水岭与自动种子区域生长的彩色图像分割算法[J]. 中国图象图形学报, 2010, 15(1): 63-68. ( YANG J H, LIU J, ZHONG J C, et al. A color image segmentation algorithm by integrating watershed with automatic seeded region growing[J]. Journal of Image and Graphics, 2010, 15(1): 63-68. doi: 10.11834/jig.20100111 ) |
[22] | 余洁, 余峰, 张晶, 等. 结合区域生长与道路基元的高分辨率遥感影像道路提取[J]. 武汉大学学报(信息科学版), 2013, 38(7): 761-765. ( YU J, YU F, ZHANG J, et al. High resolution remote sensing image road extraction combining region growing and road-unit[J]. Geomantic and Information Science of Wuhan University, 2013, 38(7): 761-765. ) |
[23] | HARALICK R M, SHANMUGAM K, DINSTEIN I. Textural features for image classification[J]. IEEE Transactions on Systems, Man and Cybernetics, 1973, 3(6): 610-621. |