Microsoft Word doc

Size: px

Start display at page:

Download "Microsoft Word - 100260.doc"

药柿钭
7 years ago
Views:

1 第 33 卷第期电子与信息学报 Vol.33No. 20 年月 Journal of Electronics & Information echnology Jan. 20 一种基于二值粒子群优化和支持向量机的目标检测算法潘泓 * 李晓兵金立左夏良正 ( 东南大学自动化学院南京 20096) 摘要 : 针对复杂场景下目标检测和目标检测中特征选择问题, 该文将二值粒子群优化算法 (BPSO) 用于特征选择, 结合支持向量机 (SVM) 技术提出了一种新颖的基于 BPSO-SVM 特征选择的自动目标检测算法该算法将目标检测转化为目标识别问题, 采用 wrapper 特征选择模型, 以 SVM 为分类器, 通过样本训练分类器, 根据分类结果, 利用 BPSO 算法在特征空间中进行全局搜索, 选择最优特征集进行分类基于 BPSO-SVM 的特征选择方法降低了特征维数, 显著提高了分类器性能实验结果表明, 该文算法不仅有效提高了复杂场景下目标姿态尺度光照变化和局部被遮挡时的检测准确率, 还大大缩短了检测时间关键词 : 目标检测 ; 二值粒子群优化 ; 支持向量机 ; 特征选择中图分类号 :P39.4 文献标识码 : A 文章编号 : (20) DOI: /SP.J A Binary Particle Swarm Optimization and Support Vector Machine-based Algorithm for Object Detection Pan Hong Li Xiao-bing Jin Li-zuo Xia Liang-zheng (School of Automation, Southeast University, Nanjing 20096, China) Abstract: his paper proposes a novel object detection method, namely the BPSO-SVM-based detection algorithm that combines Binary Particle Swarm Optimization (BPSO) and Support Vector Machine (SVM) techniques to cope with feature selection issue for object detection under complex scenarios. In the proposed algorithm, object detection is regarded as a two-class categorization problem and feature subset is selected using a wrapper model, in which the BPSO searches the whole feature space and a SVM classifier serves as an evaluator for the goodness of the feature subset selected by the BPSO. Using the proposed BPSO-SVM-based feature selection scheme, feature dimensionality is reduced and classification performance of the SVM classifier is greatly enhanced. Experimental results show the increase on detection accuracy of the proposed algorithm for object detection in complex backgrounds with pose, scale, illumination variations and partial occlusions as well as the significant improvement on detection speed. Key words: Object detection; Binary Particle Swarm Optimization (BPSO); Support Vector Machine (SVM); Feature selection 引言目标检测是目标识别系统中的核心技术之一, 它利用图像处理算法对复杂场景中的目标进行自动检测, 为后续目标识别算法提供相关信息一个好的目标检测算法既要能提取目标本质特征, 并考虑外部环境变化尺度差异和局部遮挡等方面因素对目标外观的影响, 解决好检测器与特征集之间的配合程度, 准确区分目标和非目标 ; 又要能对特征进行有效选择, 在尽可能短的时间内检测出目标, 提收到, 改回国家自然科学基金 ( , ), 航空科学基金 ( ), 东南大学优秀青年教师教学科研资助计划和国家留学基金资助课题 * 通信作者 : 潘泓 enhpan@seu.edu.cn 高检测器的处理速度目前, 目标检测方法可分为两大类, 即传统的 [,2] 基于知识和图像分割的目标检测及基于统计学习 [3 6] 的目标检测前者先对图像进行预处理, 根据上下文知识和目标的先验信息及特征搜索图像中感兴趣区域 (Region of Interest, ROI), 再用图像分割技术将这些 ROI 提取出来这种方法简单快速, 对 [] [2] 建筑物和桥梁等特定目标取得了较好的检测效果但对目标先验知识的依赖性很强, 缺乏推广性, 在复杂场景下目标姿态变化或被遮挡时, 通常无法准确检测到目标后者利用机器学习技术建立起样本和对应属性之间的正确映射, 根据映射关系判断新样本的属性, 检测图像中是否含有待检测目标基于统计学习的目标检测方法能有效克服传统目标

择, 结合支持向量机 (SVM) 技术提出了一种新颖的基于 BPSO-SVM 特征选择的自动目标检测算法该算法将目标检测转化为目标识别问题, 采用 wrapper 特征选择模型, 以 SVM 为分类器, 通过样本训练分类器, 根据分类结果, 利用 BPSO 算

2 8 电子与信息学报第 33 卷检测方法的缺点, 尤其对因尺度姿态光照变化和局部遮挡等造成的目标外观变化具有较好的鲁棒性, 因此该方法代表了未来目标检测技术的发展趋势, 并在人脸检测 [3,4] [5] [6] 行人检测和车辆检测等应用中得到广泛应用过去研究主要集中在有效特征提取和分类器设计上, 对特性选择关注较少, 而特征选择正是机器学习算法的核心问题多数基于统计学习的目标检测方法直接提取目标的原始特征送入分类器训练并识别由于原始特征中包含大量冗余信息和对分类结果起反作用的不稳定特征, 如果不加筛选直接使用, 不仅大大削弱了分类器的分类性能, 还增加了特征维数, 降低了检测速度因此, 改进方法是从原始特征集合中选出最能够反映目标特性的稳定特征子集训练分类器可见, 特征选择对最终检测结果起着十分重要的作用针对目标检测中的特征选择问题, 本文将其转化成组合优化问题, 利用二值粒子群优化 (Binary Particle Swarm Optimization,BPSO) 技术求解优化问题的能力, 结合支持向量机 (Support Vector Machine, SVM) 的强大分类能力, 提出了一种新颖的基于 BPSO-SVM 自动目标检测算法该算法的创新性在于将 BPSO 的自动寻优能力用于特征选择, 采用 wrapper 特征选择模型, 利用 BPSO 在特征空间中搜索全局最优解, 将 SVM 分类结果作为适应度函数, 检验 BPSO 选择的特征组合的分类性能, 并动态调整特征组合得到最优分类特征集通过对复杂场景下车辆检测结果表明, 本文算法有效提高了检测准确率, 大大加快了检测速度 2 算法描述图给出了本文算法的框架图提取图像关键处 SIF (Scale-Invariant Feature ransform) 描述子作为图像特征, 送入 BPSO-SVM 特征选择模块选取最优分类特征集, 进行目标检测 SVM 分类器采用 5-fold 交叉验证方式进行训练图基于 BPSO-SVM 特征选择的目标检测算法框架图 2. 特征提取 [7] SIF 算子是一种对图像仿射变换光照变化 3 维投影变换具有不变性, 对噪声局部遮挡具有较好鲁棒性的局部特征描述子 SIF 算法通过搜索尺度空间中 DOG 图像的极值点, 排除由噪声引起的极值点和不稳定极值点后, 得到图像中关键点及其位置和尺度信息对每个关键点, 计算其附近邻域内每个点的梯度方向和模值, 统计所有点的梯度方向, 得到方向直方图, 并用模值加权后, 将直方图中最大值对应的方向赋予该关键点, 这样就得到具有仿射不变性的含 28 维特征向量的 SIF 描述子对每个关键点, 我们提取该点 7 7 邻域内每点的 SIF 描述子作为特征描述, 得到原始特征集这样, 每个关键点提取了 49 个 SIF 特征 ( 共 6272 维 ), 若图像中含有 K 个关键点, 则整幅图像的特征维数 =K 6272 可见, 如此高维的特征集合极大地增加了分类器的计算量, 因此有必要对其进行特征选择, 以降低特征维数并选取最优特征组合进行目标检测 2.2 特征选择本文提出的 BPSO-SVM 算法采用 wrapper 特征选择模型, 利用 BPSO 的自动寻优能力在特征空间中进行全局搜索, 得到不同特征组合根据 SVM 分类结果判断这些特征组合的分类性能, 并不断更新选取的特征集, 直至搜索到取得最佳分类结果的特征组合在整个特征选择过程中, 粒子群优化 (Particle Swarm Optimization,PSO) 算法起了十分重要的作用, 与神经网络遗传算法等优化算法相比,PSO 具有所需确定的参数较少, 收敛速度更快等优点与顺序选择算法等常用特征选择方法相比,PSO 不易陷入局部极值, 能得到全局最优解 2.2. 粒子群优化 (PSO) 算法 PSO [8,9] 算法是一种基于群体智能的进化计算技术 PSO 求解优化问题时, 群体中每个粒子的位置代表一个可能的解所有粒子都有自己的位置速度和一个由适应度函数决定的适应值来评价当前解的好坏每个粒子根据自身记忆和群体知识搜索整个解空间, 通过迭代方式寻找并收敛到最优解迭代开始时, 所有粒子的初始位置随机分布在整个解空间中, 迭代过程中, 每个粒子根据自己发现过的最优位置 pbest 和整个群体已找到的最优点 gbest 来更新当前飞行速度和位置随着迭代的进行, 整个群体逐渐向最优解位置逼近若解空间为 D 维, 在第 n 次迭代时, 群体中第 i 个粒子的位置表示为 X n [ n, n 2,, n i = xi xi xid], 速度表示为 V n [ n, n 2,, n i = vi vi vid] 第 i 个粒子对应的自身最优点 pbest 表示为 P = [ p, p,, p ], i i i2 id

中包含大量冗余信息和对分类结果起反作用的不稳定特征, 如果不加筛选直接使用, 不仅大大削弱了分类器的分类性能, 还增加了特征维数, 降低了检测速度因此, 改进方法是从原始特征集合中选出最能够反映目标特性的稳定特征子

3 第期潘泓等 : 一种基于二值粒子群优化和支持向量机的目标检测算法 9 整个群体已找到的最优点 gbest 表示为 P g = [ pg, pg2,, pgd ] 如式 (), 式 (2) 所示, 每次迭代时, 所有粒子通过跟踪两个最优点 P i 和 P g 来更新自己的速度和位置 n n n n v + = wv + c r ( p x ) + c r ( p x ) () id id id id 22 pd id n id id id x = x + v (2) 其中 n 表示迭代次数 ;i.=,2,,p, P 为群体中粒子总数 ;d=,2,,d; w>0 是惯性因子 ;c >0, c 2 >0 分别用来调整 P i 和 P g 对速度影响的权重 r 和 r 2 是区间 [0,] 内的随机数粒子在每一维的飞行速度不能超过算法设定的最大速度 v max 式 () 表明粒子的移动速度由 3 个因素共同确定, 即当前速度, 当前位置和个体最佳位置的偏移量以及当前位置与群体最佳位置的偏移量可见, 粒子就是通过自己和同伴中最好的经验来决定下一步的运动随着迭代进化的不断进行, 粒子群逐渐聚集到最优点处基于 BPSO-SVM 的特征选择如果将整个特征空间看作解空间, 不同特征组合看作解空间中不同位置处的粒子, 粒子中各位置分量取值对应特征组合中各特征分量的状态, 则可利用 PSO 算法进行特征选择由于一种特征组合中单个特征分量的状态只能取两种 : 选中 ( 状态为 ) 和丢弃 ( 状态为 0), 因此,PSO 算法需要从实数空间推广至二值空间, 得到二值粒子群优化算法 (BPSO) [9] 在 BPSO 中, 每个粒子的位置表示为一组二值符号序列, 如第 i 个粒子的位置 x i 可表示为 x i,x i2,x id,x id,(d=,2,, D, x id ={0,}), 其中, 粒子空间维数 D 由原始特征集维数决定 BPSO-SVM 算法中, 某个粒子的位置矢量决定了某种特征子集的组合方式, 而整个群体最优点 P g 确定了系统的最优特征组合适应度函数 F 指导粒子群搜索方向, 特性选择的目的是使用尽可能少的特征得到相同或更优的分类性能, 因此, 适应度函数需要综合考虑分类准确性 (accuracy) 和特征维数 (feature_dim) 本文中所取的适应度函数 F 如式 (3) 所示 F = Accuracy + (3) 2 2 Feature_dim 表给出了基于 BPSO-SVM 算法的特征选择过程首先, 初始化粒子群, 设置粒子个数 P, 粒子的最小和最大飞行速度 V min, V max 随机生成各粒子的初始位置和速度由粒子初始位置, 确定相应特征组合, 送入 SVM 分类器得到识别率, 由式 (4) 计算该粒子适应度函数根据所有粒子的适应度函数, 选出个体最优值 P i 和群体最优值 P g 每次循环时, 确定是否更新 P i 和 P g, 并按式 (4) 更新每个粒子的速度和位置每一轮迭代中选择的特征分量由式 (4) 所示的 S 函数和粒子速度 v id 确定, 当 S(v id ) 大于 [0,] 之间的某个随机数 r 时,x id 被设为, 表示第 i 个特征组合中的第 d 维特征分量被选中进行下一轮迭代 ; 否则,x id 被设为 0, 表示第 i 个特征组合中的第 d 维特征分量在下一轮迭代中被丢弃整个迭代过程一直进行下去, 直到迭代次数达到最大迭代次数 N 或粒子适应值达到阈值 h, 停止迭代这时群体最佳位置 P g 中 p gd =(d =,2,,D) 处所对应的特征组成了最优分类特征集 n n n vid = wvid + c r ( pid xid ) + c22 r ( pgd x ) id if vid ( Vmin, Vmax) then vid = max{min( Vmax, vid ), Vmin} (4) Sv ( id ) = vid + e f ( r < S( vid )), then xid = ; else xid = 0 表基于 BPSO-SVM 算法的特征选择过程初始化粒子位置和速度, 设定粒子数量 P, 最小和最大飞行速度 V min,v max, 最大迭代次数 N, 适应度函数阈值 h, 计算每个粒子适应度函数 F, 初始化 P i 和 P g, 初始化迭代次数 n=0 2 For i = to P If F(x i ) > F(P i ) P i = x i If F(x i ) > F(P g ) P g = x i 3 For i = to P For d = to D 根据式 (4) 更新每个粒子的速度 v id 和位置 x id n = n + 4 For i = to P If (l < N) and (F(x i ) < h) 返回 2 Else 停止迭代, 输出群体最佳位置 P g 和 F(P g ) 3 实验结果和分析本节用提出的基于 BPSO-SVM 特征选择的目标检测算法探测复杂场景下的汽车目标为验证算法的检测性能, 本文比较了不进行特征选择, 直接用原始特征集 ( 表 2 所示的 FULL 一列 ) 进行目标检测使用 PCA 算法顺序前向搜索 (SFS) 算法和 BPSO-SVM 算法分别进行特征选择的目标检测方案还比较了不同特征描述子对检测性能的影响, 实验中用到的特征描述方法包括灰度特征 (INEN) Haar 小波特征 (HAAR) 和 SIF 特征将不同特征选择方法和特征空间组合起来, 一共得到表 2 所列的 2 种不同的特征集

=,2,,p, P 为群体中粒子总数 ;d=,2,,d; w>0 是惯性因子 ;c >0, c 2 >0 分别用来调整 P i 和 P g 对速度影响的权重 r 和 r 2 是区间 [0,] 内的随机数粒子在每一维的飞行速度不能超过算法设定的最大速度 v max 式 () 表明粒子的

4 20 电子与信息学报第 33 卷表 2 实验中用到的 2 种特征集 FULL SFS PCA BPSO-SVM 灰度特征 INEN-FULL INEN-SFS INEN-PCA INEN-BPSO-SVM Haar 小波特征 HAAR-FULL HAAR-SFS HAAR-PCA HAAR-BPSO-SVM SIF 特征 SIF-FULL SIF-SFS SIF-PCA SIF-BPSO-SVM 所有分类器都使用 SVM 分类器, 核函数采用高斯径向基函数 K(x,y) = exp(- β x-y 2 ) 经过多次实验, 我们发现当 β =0.7 时 SVM 分类结果最好实验中,BSPO 算法的参数设置如下 :w=, c =c 2 =2, N=00, h = 0.9, V min = -6, V max = 6 实验中用到的数据来自 UIUC car database [0], 该数据库由一个训练集和两个测试集组成, 训练集包括 550 幅含汽车目标的正样本图像和 500 幅不含汽车的负样本图像, 所有训练集图像大小为两个测试集为 Single-Scale 测试集和 Multi-Scale 测试集, 分别用来测试单一尺度和多尺度下算法的检测性能, 其中 Single-Scale 测试集中目标大小和训练集中目标大小基本相同, 而 Multi-Scale 测试集中汽车大小是训练集中目标大小的 0.8~2 倍所有测试集图像都未在训练集中出现过本文采用 5-fold 交叉验证方式训练分类器, 取 5 次 SVM 分类结果的平均值, 作为分类器的检测准确率对 Single- Scale 测试集, 用大小为的窗口在图像中滑动, 检测每个窗口中关键点, 提取关键点附近邻域的各种特征描述子作为原始特征集, 由不同特征选择算法得到相应的分类特征集, 送入 SVM 分类器判断窗口中是否含有待检目标对 Multi-Scale 测试集, 先对测试图像进行尺度变换, 得到一组不同尺度级图像, 对每个尺度级图像再分别采用上述方法进行目标检测在所有基于 PCA 特征选择的算法中, 取前 50 维特征分量作为最优特征集分别采用 ROC 曲线 PR (Precision-Recall) 曲线和 EER 指标来比较不同特征选择算法和特征描述子的检测性能图 2(a),2(b) 给出了不同特征集在 Single-Scale 测试集上的 ROC 曲线由 ROC 曲线可见, 使用特征选择模块去除冗余不稳定特征后, 检测算法的性能得到了明显提升与不采用特征选择的方法相比, 基于 PCA 基于 SFS 和基于 BPSO-SVM 的特征选择算法的检测准确率分别提高了 8.0%, 2.428% 和 6.649% 此外, 不管使用何种特征描述子, 本文提出的基于 BPSO-SVM 特征选择的目标检测算法都取得了最好的检测结果这是由于 BPSO 在搜索过程中结合了个体经验和群体智能, 因此能很快找到全局最优特征, 而 SFS 采用顺序搜索策略, 容易陷入局部最优解对于 PCA 算法, 它可以得到重构意义上的最优特征集, 但对于分类而言, 重构误差最小的特征组合未必是最优分类特征集在各种特征描述方法中, SIF 描述子始终显示了最好的检测性能, 这也验证了 SIF 描述子对尺度旋转仿射变换的不变性和对噪声光照变化及局部遮挡的鲁棒性图 2(c) 比较了本文算法和其它算法在 Multi-Scale 测试集上的 PR 曲线结果显示, 本文提出的基于 SIF-BPSO-SVM 方法的检测性能较文献 [6] 和文献 [] 提出的算法有较大改进,EER 分别提高了 54% 和 7.6% 表 3 比较了各种算法在两个测试集上的 EER 指标在 Multi-Scale 测试集上, 本文算法 EER 达到 94.96%, 显著高于其它算法在 Single-Scale 测试集上, 本文算法仅次于文献 [2] 结果, 但文献 [2] 算法复杂度太高, 检测时间较长表 3 本文算法与其它算法在两个测试集上的 EER 比较算法 Single-Scale 测试集 Multi-Scale 测试集文献 [6] 77% 40% 文献 [] / 87.8% 文献 [2] 99.94% 90.6% 本文算法 97.54% 94.96% 图 2 采用不同特征集和不同算法在两个测试集上得到的 ROC 曲线和 PR 曲线

7 时 SVM 分类结果最好实验中,BSPO 算法的参数设置如下 :w=, c =c 2 =2, N=00, h = 0.

5 第期潘泓等 : 一种基于二值粒子群优化和支持向量机的目标检测算法 2 图 3 本文算法对部分测试图像的检测结果图 3 给出了部分检测结果不论是目标局部被遮挡尺度变化较大目标与背景灰度相近或是由于光照原因导致目标灰度不均匀, 本文算法均能准确检测到目标位置这表明在实际检测时 BPSO- SVM 算法能有效检测到不同姿态尺度和被遮挡情况下的目标检测时间方面, 在 Pentium-IV.6 GHz CPU 机器上, 本文算法对 Single-Scale 和 Multi- Scale 测试集中一幅图像的平均检测时间分别为 500 ms 和 930 ms, 相比不通过特征选择直接进行目标检测的算法, 检测速度分别提高了 95.77% 和 69.46% 4 结论针对复杂场景下目标检测和目标检测中特征选择问题, 本文提出了一种基于 BPSO-SVM 特征选择的自动目标检测算法该算法将目标检测转化为目标识别问题, 提取目标 SIF 描述子作为特征, 以 SVM 为分类器, 根据分类结果, 利用 BPSO 算法在样本特征空间中进行全局搜索, 动态更新并选择最优分类特征集进行目标检测实验结果表明, 基于 BPSO-SVM 的特征选择方法不仅降低了特征维数, 有效提高了分类器的检测精度, 还显著加快了检测速度与传统目标检测方法相比, 本文提出的目标检测算法较好地解决了目标在姿态尺度光照变化及局部遮挡情况下的检测问题参考文献 [] Akcay G and Aksoy S. Automatic detection of geospatial objects using multiple hierarchical segmentations[j]. IEEE ransaction on Geoscience and Remote Sensing, 2008, 46(7): [2] Chaudhuri D and Samal A. An automatic bridge detection technique for multispectral images[j]. IEEE ransaction on Geoscience and Remote Sensing, 2008, 46(9): [3] Viola P and Jones M J. Robust real-time face detection[j]. International Journal of Computer Vision, 2004, 57(2): [4] Vilaplana V, Marques F, and Salembier P. Binary partition trees for object detection[j]. IEEE ransaction on Image Processing, 2008, 7(): [5] Dalal N and riggs B. Histograms of oriented gradients for human detection[c]. Proc. IEEE International Conference on Computer Vision and Pattern Recognition, San Diego, CA, USA, Jun.20-25, 2005: [6] Agarwal S, Awan A, and Roth D. Learning to detect objects in image via s sparse, part-based representation[j], IEEE ransaction on Pattern Analysis and Machine Intelligence, 2004, 26(): [7] Lowe D G. Distinctive image features from scale-invariant keypoints[j]. International Journal of Computer Vision, 2004, 60(2): 9-0. [8] Kennedy J and Eberhart R C. Particle swarm optimization[c]. Proc. IEEE International Conference on Neutral Networks, Perth, Australia, Nov.27-Dec., 995: [9] Kennedy J and Eberhart R C. A discrete binary version of the particle swarm algorithm[c]. Proceeding of IEEE International Conference on Systems, Man, and Cybernetics, Washington, USA, Oct.2-5, 997: [0] UIUC Car dataset, website: /Data/Car/, [] Fritz M, et al.. Integrating representative and discriminant model for object category detection[c]. Proceeding of IEEE International Conference on Computer Vision, Beijing, China, Jun , 2005, (2): [2] Mutch J and Lowe D G. Object class recognition and localization using sparse features with limited receptive fields [J]. International Journal of Computer Vision, 2008, 80(): 潘泓 : 男,974 年生, 博士, 副教授, 研究领域为模式识别机器学习计算机视觉多媒体信号处理. 李晓兵 : 男,967 年生, 博士生, 研究领域为自动目标识别计算机视觉. 金立左 : 男,972 年生, 博士, 副教授, 研究领域为模式识别目标检测识别及跟踪机器学习计算机视觉多媒体信号处理. 夏良正 : 男,942 年生, 教授, 博士生导师, 研究领域为图像处理计算机视觉数字视频处理自动目标识别.

6 GHz CPU 机器上, 本文算法对 Single-Scale 和 Multi- Scale 测试集中一幅图像的平均检测时间分别为 500 ms 和 930 ms, 相比不通过特征选择直接进行目标检测的算法, 检测速度分别提高了 95.77% 和 69.

untitled

untitled 100084 E-mail: ahz@mail.tsinghua.edu.cn (Look Up Table, LUT) Adaboost 300 Adaboost TP391 Real Time Facial Expression Classification WANG Yubo, AI Haizhou, WU Bo, HUANG Chang Computer Science and Technology