改进的AdaBoost-SVM算法用于无人机目标跟踪*

左奎军 李艳军 曹愈远 王宏宇

(南京航空航天大学民航学院 南京 211106)

0 引 言

随着数据挖掘、深度学习等新兴技术的发展，在计算机图像处理方面的研究也有了突飞猛进的进步.其中目标跟踪尤其受到研究人员的关注[1].从传统意义上的目标跟踪到如今使用机器学习、深度学习的方法进行目标跟踪，在这一过程中孕育出了许多经典的目标跟踪算法.一般说来，目标跟踪算法可分为两种：生成式和判别式[2].生成式算法其本质是一类寻优问题它将与目标模板匹配程度最高或重构误差最小的位置作为目标位置的预测.侯跃恩[3]使用主元分析理论来对目标模板进行更新，从而提出了一种Gabor特征稀疏表示目标跟踪算法.为了解决由于外观的快速变化导致目标模板不能快速匹配的问题，Jepson等[4]提出了一种鲁棒性自适应的在线外观模型.为了解决在目标快速运动以及受到遮挡时Mean Shift算法跟踪失败的状况，杨建伟[5]将MeanShift算法和卡尔曼滤波进行结合，从而得到了一种新颖的目标跟踪算法，实现了对目标的有效跟踪.从另一个角度来看，判别式算法也可以当成一种分类问题来处理，通过训练分类器，使之对跟踪目标和背景区域进行有效的区分，从而实现良好的跟踪效果.常用算法有：支持向量机(SVM)[6]、随机森林[7]、AdaBoost算法[8]、稀疏表示算法[9]等.

虽然上述算法在一定程度上解决了目标跟踪上的部分难题，但是将其直接用于无人机视频中的运动目标检测跟踪仍存在一定的局限性[10].这是因为：①大多数的算法是在理想的条件下进行的，如相机静止、目标运动缓慢、背景简单、目标清晰等.但是，在实际情况中无人机与跟踪目标都是会移动的，这在无形中增加了跟踪的难度；②计算量大，难以保证实时性；③检测跟踪小目标比较困难.虽然近几年一些学者针对无人机的目标跟踪算法也进行了大量的研究，但是大多数都是采用传统的算法，而传统算法在面对小目标时，并不能有效的提取特征，因此，国内外部分学者开始研究基于机器学习的目标检测与跟踪算法.林晓林等[11]利用Harris 角点检测与改进的多cell、多block的HOG算法结合SVM对视频帧中的小目标进行检测，提出了基于机器学习的小目标检测与追踪算法DT；Rozantsev等[12]使用了滑动窗口与CNN方法相结合的方法来检测小目标；吕卓纹等[13]将Camshift与AdaBoost算法进行结合，以纹理与颜色作为特征进行提取，在复杂的跟踪背景下取得了较好的跟踪效果.但目前针对应用于无人机目标跟踪上的基于机器学习的目标跟踪算法研究尚少，因此本文就此展开深入研究.

1 目标跟踪的基本框架

目标跟踪的基本框架见图1.

图1 目标跟踪的基本框架

2 HOG特征提取

1) 图像规范化 对γ进行压缩处理，I(x,y)=I(x,y)γ，这里γ取1/2，图像经过规范化后，可以有效降低图像局部阴影和光照变化.

2) 计算图像梯度 图像像素点(x,y)的梯度为

Gx(x,y)=H(x+1,y)-H(x-1,y)

Gy(x,y)=H(x,y+1)-H(x,y-1)

在像素点(x,y)处，水平方向梯度表示为Gx(x,y)；垂直方向梯度表示为Gy(x,y);对应的像素值表示为H(x,y)，从而在像素点(x,y)处对应的梯度幅值以及梯度方向可以表示为

3) 计算梯度方向直方图：将图像分割成多个像素为8×8的Cell单元格，然后以每40°为一个分隔点将Cell的梯度方向分成九个方向块；按照梯度方向对Cell内的像素做加权投影，得到该Cell的梯度直方图.

4) 块内归一化梯度直方图 首先，将多个临近的Cell单元组合成一个(blocks)块，然后将每个block内的所有Cell特征向量串联起来构成HOG特征，最后在每个block内进行归一化操作.

5) 生成HOG特征描述向量 将block之间重叠的HOG特征组合成一个高维向量，得到最终的特征向量.

3 随机投影

由于提取的HOG特征向量维度较大，这就不可避免导致计算量的增加，若要解决这一问题，就必须要对数据做降维处理.由于随机投影方法完全独立于样本数据，因此该方法是一种有效的数据降维手段.接下来给出随机投影的定义.

设初始m维数据矩阵为Xm×n，k×m维随机投影矩阵为R，数据矩阵X在随机投影矩阵R的作用下，被投影到一个低维的子空间k内.将上述高维矩阵投影问题用数学公式为

(1)

(2)

此时，对具有M个p维数据的集合Z，存在空间映射f:Rp→Rq，使得所有的u,v∈Z满足

(1-ε)‖u-v‖2≤‖f(u)-f(v)‖2≤

(1+ε)‖u-v‖2

(3)

Johnson-Lindenstrauss定理利用数学公式的推导对随机投影的计算方法进行了证明，并且这里需要指出，高维数据通过降维最终得到的维度为q的低维数据满足q≥o(lnM/ε2).同时在对高维数据进行降维处理时，投影矩阵的选择在很大程度上决定了数据降维的好坏，经常选取的矩阵有：经典正交矩阵、Achiloptas矩阵、Li’s矩阵.为了减小实验误差，文中使用经典正交矩阵的方法计算出投影矩阵.

4 基于AdaBoost的SVM分类器

4.1 AdaBoost算法

AdaBoost算法是Boosting算法的一种，是Freund等[14-15]根据在线分配算法提出的.该算法具有两个优良特性：①随着迭代次数的增加，训练的错误率是逐渐减小的；②即使对数据进行多次训练也不会出现过拟合的情况[16-17].

4.2 支持向量机

4.2.1支持向量机原理

通俗来讲，支持向量机(SVM)是一种典型的二类分类模型，它要解决的问题是如何在一个n维空间里找到一个n-1维的超平面对数据进行分类.SVM不光对线性问题能进行很好的分类，对非线性问题也能取得较好的分类效果；同时SVM在很大程度上也克服了“维数灾难”和“过学习”等问题[18].

4.2.2核函数

当在低维空间中遇到线性不可分的问题时，可以通过一个映射函数把样本值映射到更高维的空间来求解.这里的映射函数即是核函数.核函数的使用有效的避免了“维数灾难”的发生.常用的核函数有：Sigmoid核函数、字符串核函数、线性核函数和径向基核函数等.由于径向基核函数(RBF)能够把原始数据映射到无穷维并且计算复杂度低，因此选用径向基核函数.

4.3 分类器设计

AdaBoost算法要想达到较好的分类效果，精度和差异性缺一不可[19].为了更好的对HOG特征进行分类，将基于径向基核函数的支持向量机(RBFSVM)作为AdaBoost的分量分类器.在使用上述方法对HOG特征进行分类时，若所有弱分类器σ的取值相同，将会导致如下问题：若σ值过大，则AdaBoost的分类效果不佳；若σ值过小，则可能出现过拟合.综上所述，若要进一步提高弱分类的分类精度，合理选取σ值是关键，这里将训练每个弱分类器的样本集的标准差作为参数σ，从而获得了较高的分类精度.

4.4 跟踪算法的计算流程

提出算法的计算流程，在提取到HOG 特征之后，应用随机投影算法对数据做降维处理，特征向量经过降维后再输入到改进的AdaBoost-SVM分类器中进行训练和分类.分类器以上一帧的目标位置为参考，分别对正负样本进行采样，采样结束后得到的结果作为分类器的训练输入，而分类器的输出则是当前帧的跟踪结果.流程如下.

输入 第t+1帧图像

步骤1对满足Dy={z‖l(z)-lt‖<γ}的图像块进行取样，式中lt为目标在第t帧时的跟踪位置.

步骤2对步骤1中取样图像块的HOG特征进行提取，并对提取到的特征向量用随机投影算法做降维处理.

步骤3将步骤2中获得的低维特征向量组输入到改进的AdaBoost-SVM分类器中进行分类，得到第t+1帧图像的目标位置lt+1.

步骤4根据步骤3中得到的目标位置lt+1对正负样本集进行采样，正样本集满足：D∂={z‖l(z)-lt+1‖}<∂，负样本集满足：Dζ,β={z|ζ<‖l(z)-lt+1‖<β}.

步骤5对步骤4中采样的正负样本集提取HOG特征，并再次用随机投影算法对获得的特征向量做降维处理.

步骤6将步骤5中得到的特征向量组输入到改进的AdaBoost-SVM分类器中进行训练.

输出 跟踪位置lt+1和分类器的更新参数.

5 实验结果与分析

5.1 目标跟踪算法的定性评估

本文的目标跟踪算法在Matlab 2016a软件平台下实现，在配置为Intel i5-2.66 GHz双核CPU、内存为4GB的计算机上运行，速度为平均每秒2帧.使用了四个具有不同跟踪难度的无人机拍摄视频，视频均来自UAV123公开数据库，每个跟踪视频的特点见表1.

表1 图像序列挑战因素分析

图2为文中算法与其他算法在不同图像序列上的跟踪结果.由图2可知，Bike1图像序列面向的主要是姿态变化和严重遮挡的场景，跟踪目标在骑行过程中突然下车，然后快速推着车到了马路的另一边；并且跟踪器面临在骑行过程中具有相似跟踪目标的遮挡(第1 040和第1 231帧)问题，但从最终的跟踪结果来看，本文算法取得了较好的跟踪效果，其他算法都存在不同程度的目标跟踪丢失的情况；Bike2图像序列主要是背景杂乱、小目标的场景，跟踪目标特征点较少，跟踪环境复杂，文中算法前期跟踪良好，最后跟踪效果欠佳，其他算法皆不能实现有效的跟踪.MotorRolling图像序列主要是光照变化、背景模糊的场景，摩托车手移动迅速，并且场景中出现较强光照的干扰，文中算法对其进行了准确的跟踪，MIL跟踪器在一定程度上也对目标进行了有效的跟踪；MountainBike图像序列面向的主要是姿态变化、运动模糊的场景，摩托车手在跨越山谷的过程中运动速度快，并且在空中停留的时间内姿态出现了较大变化，即使是在如此复杂的环境下，文中算法还是对其进行了精确的跟踪.

图2 文中算法与其他算法在不同图像序列上的跟踪结果

5.2 目标跟踪算法的定量评估

位置误差和重叠率是衡量目标跟踪效果的重要指标.位置误差表示跟踪目标框选区域的实际中心与预测中心的欧式距离；假设目标跟踪的框选区域为γt，实际的框选区域为γα，则重叠率公式为S=|γt∩γα|/|γt∪γα|.其中:∩为两区域的交集；∪为两区域的并集；|·|为该区域内的像素数目.根据重叠率高于设定阈值的帧数占总帧数的比例可以绘制出成功率曲线图，统计位置误差低于设定阈值的帧数占总帧数的比例可以绘制出精度曲线图.

图3为文中算法与SCM，ASLA，VTD，CXT，VTS，CSK，TLD，LSK，MIT等10种算法在四个不同图像序列上跟踪效果的综合表现.由图3a)可知，当重叠阈值介于0～0.5时，本文算法相较于其它算法而言，对目标的跟踪成功率是最优的；由图3b)可知，当位置误差阈值介于10～50时，从跟踪的精度来看，本文算法与其他算法相比也同样有着优异的性能表现.总体来说，本文算法无论是在跟踪的成功率上，还是在跟踪的精度上都有着良好的性能表现.

图3 不同算法在图像序列上的综合表现

图4为文中算法与TLD，CXT，OAB，MIL，CSK，RS-V，L1-APG，DFT，ASLA共10个算法在快速运动、背景杂乱、运动模糊、低清晰度四种场景下的跟踪成功率对比图.在图4中每张图的右上角方框中表示的是10种跟踪器在不同场景下的AUC值(成功率曲线下的面积)，可以发现，在快速运动、运动模糊、低清晰度三种不同场景下，文中算法的AUC值分别为0.751,0.652,0.660，均高于其他跟踪器的ACU值，说明本文算法在三种不同场景下跟踪成功率最高，在背景杂乱的场景下，文中算法与ASLA算法的ACU值相差无几，ASLA算法之所以在背景杂乱的环境下表现良好是因为该算法综合稀疏表示与增量子空间学习的优势进行模型的更新，能更好处理跟踪漂移和背景杂乱现象.

图4 四种不同场景下的成功率曲线

5.3 随机投影算法的验证实验

为了进一步验证随机投影方法降维的有效性，本文用随机投影法(random projection,RP)、主成分分析法(PCA)、均值取样法(Down sample)、以及没有经过降维的图像进行实验.实验使用的是剑桥大学人脸数据库，见图5.

图5 ORL数据库人脸图像

该数据库由400张灰度图像组成，这些图像包含了40个人的面部表情、脸部特征等基本信息，而且只保留每个人面部表情差异大的10张图片.实验中将每人的前五张图片组成一个模板集，每人的后五张图片打乱顺序组成一个测试集，观察测试集中的图像与模板集中的图像匹配的成功率，分别对每种算法进行20次实验，取平均值作为最终分类正确的结果，得到的结果见表2.由表2可知，未降维图像的匹配准确率是最高的，但是它的特征维度过高，从而导致处理时间过长；PCA和Downs sample方法虽然处理时间短，但是它们的准确率都不足80%；综上所述，在兼顾准确率和实时性的前提下，本文选择了随机投影方法对高维数据做降维处理.

表2 不同降维方法性能比较

5.4 改进的AdaBoost-SVM分类器性能比较实验

为了更加精确的验证改进算法的分类性能，下面将本文算法与固定核函数的AdaBoost-SVM以及径向基核函数的支持向量机(RBFSVM)进行分类实验对比.实验使用的是Westontoynon liner数据集以及Wine数据集.

各分类器在对Westontoynon liner数据集进行分类时，分别取50，15，200，300，500作为训练样本集的大小，另外在数据集中随机取128个样本作为测试样本集；其中AdaBoost-SVM的核函数参数σ取值为12；每种算法皆做3次实验，取3次实验的平均值作为最终结果，实验结果见图6a).

图6 不同算法对Westontoynon liner数据集和Wine数据集的实验结果

各分类器在对Wine数据集进行分类时，分别取50,80,100,130,150作为训练样本集的大小，另外在数据集中随机抽取79个样本作为测试样本集.其中AdaBoost-SVM的核函数参数σ分别取2，6，12；每种算法做3次测试，取3次实验的平均值作为最终结果，实验结果见图6b).通过对图6两幅图的对比分析可知，AdaBoost-SVM相对于SVM来说，分类精度并没有明显改善，而本文提出的改进的AdaBoost-SVM则明显提高了分类精度.

6 结 论

1) 提出的基于改进的AdaBoost-SVM算法能够有效处理严重遮挡、姿态变化、光照变化、小目标检测、运动模糊、背景杂乱等挑战，实现了无人机目标跟踪的精确性、鲁棒性和稳定性.

2) 解决了HOG特征维数高，训练时间长的缺陷，采用了一种随机映射的数据降维方法，可以在不丢失信息的前提下有效地对数据进行降维，从而极大地减少了在线训练器的计算量，保证了算法的实时性.

3) 采用改进的AdaBoost-SVM算法对提取的图像特征做分类处理，同时为了权衡σ值的取值大小对样本分类的影响，将训练每个弱分类的样本集的标准差作为σ值.通过不同分类器对Westontoynon liner数据集以及Wine数据集的分类比较实验可以看出，本文算法可以在更大程度上提高最终强分类器的分类精度和泛化性.

4) 通过一系列的验证实验可以发现，虽然本文算法在运动模糊、姿态变化、光照变化以及背景杂乱等严重干扰的场景下皆对目标进行了有效跟踪.但从最终的跟踪结果来看，当面对小目标以及严重遮挡时，本文算法的跟踪精度以及成功率并不理想；因此，在以后的工作中，还需要对算法进行优化，进一步提高算法的追踪性能.