基于CKPCA-HOG和支持向量机的运动目标分类算法

闻帆，屈桢深，闫纪红

(1.哈尔滨工业大学 机电工程学院，黑龙江 哈尔滨 150001;2.哈尔滨工业大学 空间控制与惯性技术研究中心，黑龙江哈尔滨150001)

智能化的视频监控(intelligent video surveillance，IVS)是将图像与事件建立一种映射关系，借助计算机强大的数据处理能力对监控视频的内容进行描述、理解和分析，并能根据分析的结果对视频监控系统进行控制，从而使视频监控系统具有较高层次的智能化水平.其中，运动目标的自动分类是其中不可或缺的一个重要环节.在交通领域中的智能交通控制管理系统中，通过提取车辆目标的特征可计算出交通流参数，依此来设定信号配时［1］.在交叉口碰撞检测中，正确地识别出运动目标并根据其运行轨迹，可以预测是否有碰撞发生［2］.除此之外，目标分类算法还可以实现智能车辆对周边环境中感兴趣目标的检测、分类和存储等功能［3］.

目前，目标分类算法主要分为两类:基于样本或模板的方法和基于形状特征［4］的方法.相对于前者，基于形状的方法在描述同类目标或具有相似运动的目标时很难用统一的模型加以表征，因此在对目标进行精细分类时存在明显的不足.虽然国内外学者提出了诸多分类算法，但是迄今为止，如何对目标进行有效地分类，还是一个尚未得到很好解决的问题.

目前，基于梯度方向直方图［5］的纹理描述符已用于目标分类.文献［6］找到一个解决弥补在某些情况下单个分类器不足问题的方法，就如何将特征与分类器进行组合展开了研究.文献［7］提出了一种基于boosted HOG特征和线性SVM的目标分类算法.在文献［8］中，利用局部梯度最大方法来估计感兴趣区域(ROIs)的位置，然后利用AdaBoost分类器对这些假进行验证.文献［9］为了更加快速地检测行人，将人脸检测中Boosted Cascade算法用在特征选取上，不仅训练时间短、检测速度快，而且检测精度比较高.从各文献实验结果中看出，这些方法在针对行人和车辆目标分类中都取得了很好的效果.

虽然HOG特征能够得到很高的检测率，但是高达几千维的特征向量限制了训练样本的数量，同时增加了在分类过程中的计算时间.由于CKPCA在特征降维中的优越性能，本文将高维的 HOG特征用CKPCA降到低维，缩短了分类器的训练时间并未影响检测精度.然后利用降维后的特征向量训练二叉决策树支持向量机，得到最终的分类器.最后，利用训练好的分类器对视频序列出现的新目标进行分类，并对分类结果进行评价.

1 图像特征描述及CKPCA方法

1.1 图像特征描述

为了对图像进行有效地分析和理解，需要将给定的原始图像用有利于人或机器分析和理解的简单明确的数值、符号或图形表示出来，这些数值、符号或图形称为图像的特征.目标分类是对于未知目标的观测数据，利用一组能够代表目标的合适特征作为输入，得到此目标的类别或者属于不同目标类别的可能性.现阶段，对目标特征表达可以归纳为两方面:全局特征与局部特征.通过检测图像的局部特征，形成易于区分、稳定性好的特征向量，把目标分类问题转化为特征空间中特征向量的聚类问题.由于目标的局部特征易于提取和表示，具有很强的鲁棒性，因此在目标分类领域获得了广泛的应用.

2005年，Dalall提出了基于HOG特征的算法，并成功应用于行人检测.梯度方向直方图描述子(descriptors)的本质思想是图像内的局部对象的外观和形状可以通过梯度强度或边缘方向的分布加以描述.如图1所示，这些描述子的应用可以通过将图像划分成称之为细胞(cell)的小的连通区域，对每个单元内的像素计算梯度方向或边缘方向的直方图，然后对这些直方图加以组合构成最终的描述子.为了提高描述子的性能，计算由若干单元组成的块内所有像素梯度强度值的和，然后利用该值归一化块内所有单元，得到归一化的描述子.

图1 HOG特征算子Fig.1 HOG operator

1.2 CKPCA方法

对于场景中的运动目标，首先提取能够有效描述该目标的特征向量.由于获取的特征向量维数比较高，这样会影响目标分类的运算速度，因此需要通过数据降维的方法得到一个能够有效描述目标特征并且数据维数比较小的特征向量.PCA为特征向量由高维降为低维提供了一个很好的解决方法.通过对从现场采集的目标特征向量进行分析后发现，这些特征向量之间往往是线性不可分的，而PCA又不能解决非线性问题，因此采用CKPCA方法实现上述目标.该方法首先通过核函数将输入非线性空间变换到高维线性空间，然后在高维空间利用主成分分析的方法对特征向量进行数据降维［10］.

设xi∈RP(i=1，2，…，n)为样本点，RP表示输入空间，F表示特征空间.非线性变换φ:RP→F实现两者间的映射，将样本点xi映射为特征空间的样本点φ(xi)，其中i=1，2，…，n.

F空间中样本的协方差矩阵C为

根据Cv=λv计算C的特征值λ和对应的特征向量V∈F{0}.

设C的特征值为0≤λ1≤λ2≤…≤λn，对应的特征向量为v1，v2，…，vn.另外，v1，v2，…，vn可由F空间中的样本φ(xi)张成.记:

考虑等式

将式(1)、(2)代入式(3)，令

得到

式中:K称为核矩阵，是n×n矩阵，nλi是K的特征值，α1，α2，…，αn是对应的特征向量.按一定的标准(前m个特征值占总特征值的比例≥90%)，取前m (m＜n)个特征值和对应的标准化后的特征向量α1，α2，…，αm，其中…，m).

对F空间中样本φ(xj)(j=1，2，…，n)在vr上进行投影:

称gr(xj)为对应φ的第r个非线性主元分量.将所有的投影值形成一个矢量g(x)=(g1(xj)，g2(xj)，…，gm(xj))作为样本的特征值.根据Mercer定理，利用核函数K(xi，xj)=(φ(xi)·φ(xj))代替F空间中的内积运算，式(5)可写为

核函数有很多选择，常用的核函数如下:

1)多项式核函数:

2)Sigmoid核函数:

3)径向基核函数:

式中:d、β0、β1和σ需要事先确定，这些参量可以通过K-Means聚类算法来得到.这里采用径向基核函数，其中σ表示函数的宽度参数，就是距离中心的半径.这个半径等于聚类中心向量和属于该类的样本之间的距离的平均值.

不同的核函数决定了由原始空间到特征空间的不同映射.对于主元分析算法，数据需要在特征空间中心化.这可以由取代K来实现:

式中:Li，j=1/l.

从上面计算可以看到，核矩阵与样本点的个数相关，PCA不能解决非线性问题，KPCA虽能解决，但由于样本点的个数比较大，带来核矩阵的维数比较大，造成计算复杂度增加.为了解决核矩阵的计算复杂性，选择疏散的贪婪矩阵近似(sparse greedy matrix approximation，SGA)［11］的方法缩减样本点个数来达到降低核矩阵的阶数.

1.3 CKPCA-HOG计算过程

CKPCA-HOG计算过程主要由两部分组成:第1部分是特征提取，利用HOG算子获取目标梯度向量;第2部分是特征数据降维，利用CKPCA将HOG高维数据影射到一个线性子空间，在去掉冗余信息的同时保留了主要的特征，而且不影响分类精度.

令I∈Rm×n表示一个具有宽度为m高度为n的图像，I(x，y)表示位于(x，y)处像素的灰度值，其中x=1，2，…，m，y=1，2，…，n.下面给出CKPCA-HOG算子的计算流程:

1)计算图像梯度:首先，图像I经过一个尺寸为wg标准差为σg的高斯滤波器滤除噪声.然后，利用1维的中心点导数离散掩模DX和DY沿x和y方向对图像卷积:

式中:DX=［－1 0 1］，DY=［－1 0 1］T.

根据式(11)和(12)可得到点的梯度幅值|G(x，y)|和方向θ(x，y).

其中，梯度的幅值为

梯度的方向为

为了使CKPCA-HOG对目标的颜色不具有敏感性，根据文献［5］，将式(14)修改如下:

2)创建cell直方图:图像按空间位置均匀的分成sw×sh个相邻的网格，每个网格称为“cell”，在cell内按照设定好的方向量化间隔统计梯度方向直方图，应用梯度的幅值或者梯度幅值的平方或者平方根进行投票.

3)描述符块:为了解释照度或对比度的变化，梯度幅值必须局部归一化.将相邻的cell(2×2)组成一个大块(block)，相邻的block之间相互重叠，意味着每个cell对于最终的描述子的贡献多于一次.HOG描述子是一个由块内所有归一化的cell直方图组成的向量.

4)块归一化:在block内采用二范数(L2)归一化直方图消除光照的影响.一个检测窗口内所有block内的归一化直方图组成图像I最后的特征向量H∈Rnf，nf=ss×sh×sb.

5)计算非线性主元分向量:

①对于给定的数据xk∈Rm(k=1，2，…，N)，利用式(9)计算对应的核矩阵K∈RN×N;

②在特征空间中利用式(10)对数据进行中心化处理.

③解特征方程Nλα=K～α，利用公式αk·αk= 1/λk标准化特征向量αk.

④对正常数据x，通过式(6)计算非线性主元的分向量.

⑤令Γ∈Rnp×nf表示从训练图像HOG描述子获得的前np个主成分，将HOG描述子H投影到由主成分Γ构成的线性子空间:

2 基于二叉决策树SVM分类器

在交叉口，交通目标主要有行人和车辆，而目标分类的目的是将从视频图像序列中检测出来的目标根据某种或者某些特征的组合将它们分类为行人和车辆，然后在此基础上再进一步将车辆分为大型车、中型车和小型车.由于支持向量机仅能够解决两类分类问题，当需要解决实际应用中的确定多类分类问题时，需要构造新的多类分类器.目前，常见的多类分类器主要有以下4种类型:一对多组合、一对一组合、决策有向无环图和全局优化分类.

为了有效地对目标进行区分，如图2所示，在一对多组合类型分类器的基础上设计了基于二叉决策树方案的支持向量机分类器.基于二叉树的多类SVM是先将所有类别分成2个子类，再将子类进一步划分成2个次级子类，如此循环，直到所有的节点都只包含1个独立的类别为止.该方法将原有多类分类问题分解成一系列的2类分类问题，其中2个子类间的分类函数采用SVM，二叉树方法可以避免传统方法的不可分情况，并只需构造k-1个SVM分类器，测试时并不一定需要计算所有的分类器判别函数，从而可以节省测试时间.

图2 二叉决策树SVM分类器Fig.2 Binary decision tree SVM classifier

基于SVM的二叉树多类分类决策算法原理如下［12-13］:

给定一个k类分类问题，学习样本为{(x1，y1)，(x2，y2)，…，(xl，yl)}，xi∈Rn，yi∈{1，2，…，k}，i= 1，2，…，l.

一个二叉树分类结构是一个4元组＜F，P，SVM，SC＞，其中F={f1，f2，…，fk}，是二叉树的终节点的集合，由待识别的k个运动目标类别构成; P={p1，p2，…，pk}，P表示目标分类的优先级，根据各种目标在场景中发生频率的高低来确定.最可能出现的状态优先级为p1，发生可能性最低的状态定为最后一级pk.

SVM={SVMP1，SVMP2，…，SVMPk－1}是由所设计的k－1个SVM组成的二叉树的全部非终止节点集合.对一个k类分类问题，需要构造k－1个SVM.其中第i个SVM决定的目标类别为pi.

SC={SC1，SC2，…，SCk}为属于k个目标类别的全部学习样本集合，其中SCi={(x1，yi)，(x2，yi)，…，(xli，yi)}表示第i类的样本组成，xj∈Rn，yi∈{1，2，…，k}.ΣSCili=l构成全部学习样本.

第i级支持向量SVMPi的训练样本SPi按下述原则确定:

第i个SVM解决以下问题:

如果yi=i，则

如果yj≠i，则

这样可得到k－1个决策函数:

对每一级SVM训练后找出对应该级的支持向量，建立最优分类超平面.由于k－1个SVM是按照优先级由高到低排列的，新模式产生时，只需按照二叉树由高到低进行搜索，就可得出结论.

二叉决策树SVM总体上属于基于SVM的多类策略中的第一大类，相对于“one against all”和“one against one”策略，大大降低了样本的重复训练量.

3 实验及结果分析

为了验证本文提出的目标分类算法的有效性，在台式计算机上进行相关测试.其中，计算机的配置为Intel Pentium IV 2.0 CPU，内存2G，软件在Visual C++6.0下开发完成.测试所用图像主要来自两部分:一部分来自http://cvrr.ucsd.edu/aton/shadow的UIUC数据库，图像分辨率为138×87.另外一部分来自于哈尔滨市区某路口拍摄到的实际视频图像序列，使用CCTV视频监控模拟摄像机，通过图像采集卡完成图像采集，图像分辨率为320×240，本文的分类方法全部在灰度图像上处理.

3.1 CKPCA-HOG描述子性能分析

利用CKPCA-HOG描述子提取目标特征，选用径向基核函数 K(xi，xj)=exp(－|xi－xj|2/σ2.KPCA-HOG描述子中的各个参数为ωg=5，σg=1.2，sw=2，sh=2，sb=8，nf=200，np=20.方向量化间隔为5度，每个特征向量为72维.经过KPCA分析，每个目标由20维的CKPCA-HOG描述子进行描述.

表1给出了基于HOG、PCA-HOG、KPCA-HOG和CKPCA-HOG 4种描述子进行目标分类时的运算时间比较结果.从表中可以看出，HOG特征高达上千维，而PCA-HOG特征和KPCA-HOG和CKPCAHOG特征仅20维.数据维数的降低，意味着计算速度的加快.从运算时间上看，基于HOG特征的目标分类时间最慢，基于PCA-HOG特征的目标分类时间最快，基于CKPCA-HOG的分类时间介于前面两者所花的时间.从表中可以看出，基于CKPCA-HOG方法，大大提高了KPCA计算核矩阵的速度，而且随着数据个数的增多，几乎不影响原来的计算速度.另外，虽然该算法较PCA-HOG算法慢些，但是目标分类精度却提高很多.

表1 运算时间比较Fig.1 Comparison of computation time

3.2 实验目标分类结果

3.2.1 训练阶段

训练阶段为了能使支持向量机能够准确地对目标进行分类，需要输入一些有代表性的包含运动对象的静态图像训练样本对其进行训练.首先收集M幅正样本和Q幅负样本图像作为训练器的训练图像.这里的正样本指的是待检测目标样本，包括行人、小轿车、中型车和大型车等.正样本可以由单个的目标图片或者一系列的事先标记好的图片来创建，也可以从一个预先标记好的图像集合中获取.负样本来自于其它任意的图片，但这些图片不能包含目标特征.通常负样本由背景描述文件来描述.如果样本图像尺寸不同，统一调整成为大小为N×N的图像.然后计算每幅图像的CKPCA-HOG特征，从而获得进行支持向量机分类模型训练所需要的特征向量样本点，并将这些样本点输入到SVM中进行训练，通过优化理论调整分类器的参数，最终获得对象分类的支持向量机分类模型.图3给出了用于训练支持向量机的一组数据，该数据取自UIUC测试图像库.文中共有1050幅测试图像，其中正样本图像为500幅(M=500)，负样本图像为550幅(Q= 550).

图3 SVM训练数据Fig.3 Training data for SVM

本文中，场景中的目标为车辆(小型车、中型车和大型车).因此，训练样本共有C(=3)类，分别计为A1，A2，A3.针对每个分类器SVMi(i=1，2，3)，将训练样本中的第i类样本Ai作为正样本训练，其他所有的样本作为负样本训练.在完成目标特征提取后，将这些特征数据组合成特征向量X.根据每幅图像生成的特征向量xi，以及该图像队应的视频对象yi，组成用于测试的样本点(xi，yi).将由N幅图像组成的样本点集合作为支持向量机的输入，训练第i类分类器SVMi，得到相应的分类平面，用来区分该类与其他类目标.

文中采用的特征有:全局特征中的形状特征，长度、宽度和长宽比，局部特征中的HOG描述符.对于行人和车辆目标的区分，主要采用的特征是:外形尺寸、复杂度、长宽比、紧凑度.首先，根据目标的外形尺寸、复杂度、长宽比和紧凑度将运动目标分为行人和车辆.然后再根据CKPCA-HOG特征描述符将车辆分为小型车、中型车和大型车.

紧凑度:C=4π*Area/Perimeter2，其中Perimeter表示目标边界所有像素个数的总和.

3.2.2 识别阶段

在识别阶段，首先导入训练好的支持向量机分类模型.然后利用特征描述子CKPCA-HOG提取目标的特征向量，并将该特征向量输入到支持向量机中，通过判别公式获得最后的目标分类结果.

下面给出针对UIUC数据库的分类结果.对于待分类的170幅图像，训练好的车辆分类器成功地检测到 156个车辆，漏检 14个，检测率达到了91.7%.图4给出了其中正确识别的结果;图5给出了错误分类和漏检的结果.

图4 正确分类结果Fig.4 Correct classification results

图6给出了城市道路实际场景中目标分类结果.该图像取自哈尔滨市某交叉口监控视频序列.该场景中不但有机动车、非机动车和行人，而且路面上有雪、晃动的摄像头、摇摆的数目以及图像噪声都对目标分类产生不利的影响.首先，利用背景减除算法获得前景运动目标，在完成阴影检测和消除后得到最终的运动目标掩模.从图6给出的分类结果中可以看出，本文提出的算法能够对场景的车辆和行人进行准确的分类.

图5 错误和漏检结果Fig.5 False and leak classification results

图6 实际场景分类结果Fig.6 Classification results of real scenes

4 结束语

文中提出一种鲁棒的目标分类算法.在训练阶段，利用CKPCA-HOG特征描述子得到目标特征向量，然后对二叉决策树SVM进行训练.相对于基于HOG和SVM的目标分类方法相比，本算法在保证识别准确率的同时，系统运行时间在2个方面得到了明显改善:利用CKPCA-HOG特征描述子大大降低了目标特征数据维数;利用二叉决策树SVM在进行多类目标分类的时候节省了测试时间.

本文提出的算法对场景中出现的目标能够很好地区分，下一步将机器学习引入到分类器训练数据提取中，依此来改进分类器性能.由于传统的分类器在训练过程中由人工事先将训练样本定义好类别，这种方法太费时，而且容易导致内在的模糊.此外，由于目标提取不当造成的定义类的错误和分配标签不正确所产生的误差将最终被传播到最终分类，影响目标检测性能.如果在目标分类过程中，系统根据分类结果提取合适的训练样本，这样使系统适应能力更强，从而可以提高分类器的性能.

［1］VEERARAGHAVAN H，MASOUD O，PAPANIKOLO_ POULOS N P.Computer vision algorithms for intersection monitoring［J］.IEEE Trans on Intelligent Transportation Systems，2003，4(2):78-89.

［2］ATEV S，ARUMUGAM H，MASSOUD O，JANARDAN R，PAPANIKOLOPOULOS N.A vision-based approach to collision prediction at traffic intersections［J］.IEEE Trans on Intelligent Transportation Systems，2005，6(4):416-423.

［3］GANDHI T，TRIVEDI M M.Video based surround vehicle detection，classification and logging from moving platforms: issues and approaches［C］//IEEE Intelligent Vehicles Symposium.［s.l.］，2007:1067-1071.

［4］赵秀娟，刘志勇，樊可清.基于支持向量机的车辆自动分类方法［J］.公路交通科技，2003，20(5):108-110.

ZHAO Xiujuan，LIU Zhiyong，FAN Keqing.SVM based method for vehicle automatic-classification［J］.Journal of Highway and Transportation Research and Development，2003，20(5):108-110.

［5］DALA N，TRIGGS B.Histograms of oriented gradients for human detection［C］//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Beijing，2005:886-893.

［6］OLIVEIRA L，NUNES U.On integration of features and classifiers for robust vehicle detection［C］//Proceedings of the 11th International Conference on Intelligent Transportation Systems.Beijing，2008:414-419.

［7］WANG Zhenrui，JIA Yulan，HUANG Hua，TANG Shuming.Pedestrian detection using boosted HOG features［C］//Proceedings of the 11th International Conference on Intelligent Transportation Systems.Beijing，2008:1155-1160.

［8］KHAMMARI A，NASHASHIBI F，ABRAMSON Y，LA_ URGEAU C.Vehicle detection combining gradient analysis and AdaBoost classification［C］//IEEE Conference on Intelligent Transportation Systems.［s.l.］，2005:1084-1089.

［9］朱文佳，戚飞虎.基于Gentle Adaboost的行人检测［J］.中国图象图形学报，2007，12(10):1095-1098.

ZHU Wenjia，QI Feihu.Gentle adaboost based pedestrian detection［J］.Journal of Image and Graphics，2007，12 (10):1095-1098.

［10］王和勇，姚正安，李磊.基于聚类的核主成分分析在特征提取中的应用［J］.计算机科学，2005，32(4): 64-66.

WANG Heyong，YAO Zhengan，LI Lei.The application of feature extraction on using kernel principal component analysis based on clustering［J］.Computer Science，2005，32(4):64-66.

［11］SMOLA A J，SCHOLKOPF B.Sparse greedy matrix approximation for maehine leaming［C］//Proc of ICML＇00，Bochum，Germany，2000:911-918.

［12］韩顺杰，赵丁选.基于SVM的二叉树多类分类算法在工程车辆挡位决策中的应用［J］.中国公路学报，2007，20(5):122-126.

HAN Shunjie，ZHAO Dingxuan.Application to shift decision for construction vehicle based on SVM binary tree multi-class classification algorithm［J］.China Journal of Highway and Transport，2007，20(5):122-126.

［13］马笑潇，黄席樾，柴毅.基于SVM的二叉树多类分类算法及其在故障诊断中的应用［J］.控制与决策，2003，18(3):272-276.

MA Xiaoxiao，HUANG Xiyue，CHAI Yi.2PTMC classification algorithm based on support vector machines and its application to fault diagnosis［J］.Control and Decision，2003，18(3):272-276.