帧差法和Mean shift算法融合的高速无人机目标跟踪

王宜贤，石德乐，杨　宁

（中国空间技术研究院513所，山东烟台264003）

帧差法和Mean shift算法融合的高速无人机目标跟踪

王宜贤，石德乐，杨宁

（中国空间技术研究院513所，山东烟台264003）

为实时跟踪高速飞行无人机，图像跟踪算法必须满足快速性和准确性要求。文章给出一个融合算法，将帧差法和Mean shift算法的优势结合起来。2个算法平行运行，差帧法实现快速跟踪，Mean shift算法则用于对帧差法结果进行准确度修正。还利用Kalman滤波技术对计算周期内的无人机运动位移进行补偿，进一步提高实时跟踪的准确性，并给出Matlab仿真例子验证本文方法的有效性。

无人机；目标跟踪；帧差法；Mean shift算法；融合算法

1　问题的提出

对处于飞行状态的无人机进行无线充能需要2个环节：首先，利用成像器件捕捉无人机图像序列，通过图像处理技术检测无人机目标并获得目标坐标；其次，将无人机坐标信息传给姿态定位及随动跟踪系统实施充能动作。如何利用图像处理技术获得准确的无人机实时坐标，这是无人机无线充能关键的一环。

在图像处理领域，对动态目标的检测、跟踪一直是一个备受关注的问题［1-8］。基于不同的理论模型，不同的跟踪算法被提出，主流的算法有帧差法、背景差分法、模板匹配法、光流法、Mean shift算法、Camshift算法等［9-15］。这些方法中，不同的算法有各自的优势，准确度高的算法计算周期长，实时性较差，而快速的算法则往往跟踪精度较差。没有一种算法能兼备全部算法的优点。

近年来，为了解决复杂的实际问题，人们开始将不同的图像算法融合起来，通过不同算法的优势组合，获得更好的结果［16-19］。文献［16］将帧差法与Mean shift算法进行融合，利用帧差法检测运动目标，确定初始窗口及设定跟踪模板，然后用Mean shift算法进行目标跟踪。文献［17］将帧差法和光流法融合，使用帧差法对图像进行分割，然后利用光流场算法对运动目标进行检测。文献［18］将帧差法和背景差分法进行融合用于运动目标检测，而文献［19］将帧差法和分水岭算法进行融合。

与跟踪快速无人机的要求相比，文献［16-19］给出的融合算法不能满足快速性的要求，比如，文献［17］中的光流法运算复杂，需要特定的硬件支持。文献［18］给出的算法虽然运算量小，可以实时运算，但是准确性不能满足要求。

为实现高速无人机实时跟踪的目的，本文提出一个将帧差法和Mean shift算法融合的算法。其思路是并行运算帧差法和Mean shift算法，利用帧差法对目标进行快速检测和定位，然后用Mean shift算法对帧差法的结果进行精度修正。为进一步补偿无人机在计算周期内飞行所导致的跟踪计算结果的偏差，将修正的结果看作无人机飞行过程的观测量，建立Kalman滤波方程对无人机位置进行实时预报，从而实现对高速无人机的实时跟踪。

2　帧差法和Mean shift算法的融合

2.1帧差法

帧差法又叫阈值帧间差分法（TIFD），是运动目标检测中使用最多的算法。它的突出特点是算法简单、计算量小、实时性高，在大多数情况下检测效果较好。帧差法基本原理是设定一个阈值，然后将前后两帧图像对应像素点的灰度相减。对应灰度差小于阈值的像素点标记为静止的，对应灰度值差大于等于阈值的像素点标记为运动的。所有标记为运动的像素点可以形成运动目标的轮廓。

以T为阈值，It-1（x）、It（x）分别为相邻2个时刻采集的图像在像素点x处的灰度值，做差分并得到差分图像：

利用矩法计算目标轮廓的质心［20］。令：

质心的计算公式为：

式中，yf被看作是无人机的位置坐标。

2.2Mean shift算法

Mean shift算法用概率密度来描述目标和候选目标的特征，定义两者间的相似系数，度量它们间的匹配程度，算法的目标是寻找候选目标，使其与目标有最大的相似系数。Mean shift算法具有很高的稳定性，它能够适应目标的形状、大小的连续变化，而且抗干扰能力强。为获得准确度高的结果，Mean shift算法需要迭代多次，这使得计算周期变长，影响实时性。

Mean shift算法跟踪算法主要包括3个步骤：目标模型和候选模型的建立、相似性度量、迭代计算。

选定目标区域为包含无人机的一个矩形区域，区域中心选为无人机图像的质心。设该区域内有n个像素点，将图像的灰度空间划分m个不同的区间，分别以1，2，…，m索引，则目标模型被表示为灰度索引u的直方分布密度为：

式（4）中，qu被定义为：

式（5）中：C是归一化参数；k（·）是核函数的轮廓函数；h为带宽；b（xi）表示像素点xi所属区间的索引；x0是待跟踪目标的中心，选为无人机的图像质心；δ是Kronecker delta函数。

候选模型的特征：候选模型由像素点y点确定，它仍被描述为灰度索引u的直方分布密度为：

其中，pu（y）被定义为：

式（7）中：y表示候选目标的位置；其他参数与目标模型相同。

这样，搜寻相似系数的极值问题就是寻求ρ（y）的优化问题。这个搜索y的过程可以通过迭代进行，从上一步y0到下一步y1的迭代公式为：

为保证尽可能获得相似系数的优化值，一般需迭代30次，迭代结束时输出的结果ym即被看作无人机的坐标位置。

2.3算法融合

帧差法虽然计算速度快，但相对于真实目标，这一方法检测到的目标轮廓往往范围较大，算出的质心与真实目标位置会有较大的偏差。Mean shift算法虽然跟踪精度比较好，但需要做大量迭代运算，这样就难以保证实时性。为将帧差法的快速性和Mean shift算法的精度优势结合起来，对2个算法进行融合。方法是同时并行运行2个算法，用Mean shift算法的结果修正帧差法的结果，使修正后的结果尽可能接近Mean shift算法的结果。由于在一个Mean shift算法计算周期内，帧差法会执行多个计算周期，用上一Mean shift算法的结果修正当前Mean shift计算周期内帧差法的所有结果。

假设成像部件采集图像的周期为T，在kT（k=0，1，2，…）时刻采集的无人机图像组成一个图像序列，记为G0，G1，G2，…，Gk，…；帧差法记为Pr，计算周期为 Tr＜T；Mean shift算法记为 Ph，计算周期为Th＜NT。

帧差法Pr对kT时刻采集的图像Gk进行处理，在kT+Tr时刻得到无人机在kT时刻的位置坐标，结果记为这一过程表示为：

Mean shift算法Ph的计算周期看作NT，它只能对kNT时刻采集的图像GkN处理，在kNT+Th时刻计算出无人机在kNT时刻的位置坐标，得到结果记为，这一过程表示为：

在kNT时刻，帧差法和Mean shift算法处理同一幅图像GkN，结果分别为和，其差即为Mean shift算法相对帧差法的改进值。这个差反映2个算法间算法质量的差别，在背景近似不变的条件下，差也近似不变。

因Mean shift算法在（k+1）NT时刻完成，这个差在（k+1）NT 得到，所以以修 正时段内帧差法得到的N个结果，其中Ak+1为修正系数矩阵，即：

Ak+1的选择应使修正后的结果尽可能接近Mean shift算法的结果。在Mean shift算法计算周期内，没有新的Mean shift算法的结果用于接近程度的评价，这种评价只能建立在已有的计算结果上。按如下方式选择 Ak+1：假设在（k-1）NT时刻获得后，用修正［kNT，（k+1）NT-T］时间段内帧差法的计算结果，那么Mean shift算法在（k+1）NT时刻得出结果后，“理想的修正值”应满足，即A应满足：

将上一时段的“理想的系数矩阵A”取做当前时间段的Ak+1，它可表示为：

3　Kalman滤波

在执行图像处理期间，处于飞行状态的无人机会飞行一段距离，这样计算出的坐标不是无人机的实时位置。下面引入Kalman滤波方法消除这种计算时延导致的跟踪误差。首先为高速无人机系统建立Kalman滤波所需的状态方程和观测方程。

在无人机目标跟踪过程中，视频图像采集时间间隔较短，无人机在一个图像采集周期内的运动可看作是匀速地。

定义nT时刻卡尔曼滤波的系统状态为Xn=（xn-1，yn-1，xn，yn）T，（xn-1，yn-1）和（xn，yn）分别为无人机在（n-1）T时刻和nT时刻所在的位置。设为 nT时刻无人机在x轴和y轴方向的运动速度，则有：

则对于n+1时刻的无人机的坐标有：

于是，可以建立无人机的状态转移方程：

式中，Wn为状态转移过程中存在的干扰白噪声。

式中，Vn为观测过程中存在的干扰白噪声。

关于转移方程和观测方程中的干扰白噪声，假定它们满足下面统计特性：

式（19）中：Qk是白噪声Wk的4阶协方差矩阵；Rk是白噪声Vk的2阶协方差阵；δkj是Kronecker函数。

根据建立的状态方程和观测方程，可以执行标准的Kalman滤波步骤。由关于（n-1）T时刻观测值，可以得到当前nT时刻的预报值，这个预报值可以作为无人机的当前时刻的位置，传递给随动系统。

4　仿真实验

根据问题实际背景的要求，成像设备采集的无人机飞行图像的分辨率设为480像素×600像素，图像采集频率为48Hz，周期T≈20.8 ms，无人机坐标定位的误差小于1个像素。为保证对图像跟踪的实时性，要求跟踪算法的处理周期在20 ms以内。

帧差法的平均计算周期约为Tr=13.2 ms＜T，小于图像采集周期，Mean shift算法的平均运算周期约为Th=126.1 ms＜7T。

利用成像设备在真实场景下采集无人机飞行的图像序列，在Matlab环境下对融合算法进行仿真验证，得到的结果在图1给出。图1中的方框表示跟踪波门，它以Kalman预报值为中心。

图1　无人机融合算法跟踪仿真Fig.1 Simulation of UAV tracking with fusion algorithm

5　结语

在高速无人机图像跟踪问题中，跟踪算法需要同时满足快速性和准确性的要求，这2个目标难以用一个现有常规的算法单独实现。

本文给出一个融合算法，即将帧差法和Mean shift算法的优势结合起来。2个算法平行运行，差帧法实现快速跟踪，Mean shift算法用于对帧差法结果的进行精度修正。同时，本文还利用Kalman滤波技术对计算周期内的无人机运动位移进行补偿，进一步提高实时跟踪的准确性。虽然本文提出的融合算法能提高帧差法的准确性，实现对无人机快速和准确跟踪，但也存在不足。当背景出现较强干扰时，帧差法会将干扰源处理成无人机轮廓使计算结果出现偏差，这种计算偏差无法用本文的融合算法修正。

［1］崔家瑞，陈鹏，胡广大.空间站脉冲编码被动式交会对接合作目标三维跟踪［J］.宇航学报，2016，37（1）：102-111. CUI JIARUI，CHEN PENG，HU GUANGDA.Cooperative target 3D tracking for space station pulse coded passive rendezvous and docking［J］.Journal of Astronautics，2016，37（1）：102-111.（in Chinese）

［2］DOU JIANFANG，LI JIANXUN.Robust visual tracking base on adaptively multi-feature fusion and particle filter ［J］.Optik，2014，125：1680-1686.

［3］郑远力，胡志坤.基于滑动扫描框的高速物体的图像实时跟踪算法［J］.计算机科学，2015，42（10）：287-291. ZHENG YUANLI，HU ZHIKUN.Real-time tracking algorithm for fast target based on dynamical scanning boxes ［J］.Computer Science，2015，42（10）：287-291.（in Chinese）

［4］GAO MINGLIANG，SHEN JIN，YIN LIJU.A novel visual tracking method using bat algorithm［J］.Neurocomputing，2016，177：612-619.

［5］胡晋铭，张鲁滨，任瑞，等.飞行试验复杂背景下的图像跟踪技术［J］.海军航空工程学院学报，2010，25（1）：11-14. HU JINMING，ZHANG LUBIN，REN RUI，et al.Video tracking technology for the flight test under complex background［J］.Journal of Naval Aeronautical and Astronautical University，2010，25（1）：11-14.（in Chinese）

［6］GIUSEPPE GUIDO，ALESSANDRO VITALE，FRANK F SACCOMANNO.Vehicle tracking system based on videotaping data［J］.Procedia-Social and Behavioral Sciences，2014，111：1123-1132.

［7］史延科，高晓光.图像目标跟踪及其在UCAV中的应用［J］.飞行力学，2005，23（1）：79-81. SHI YANKE，GAO XIAOGUANG.The image target tracking and its applications in UCAV［J］.Flight Dynamics，2005，23（1）：79-81.（in Chinese）

［8］江山，张锐，韩广良，等.复杂背景灰度图像下的多特征融合运动目标跟踪［J］.中国光学，2016，9（3）：320-328. JIANG SHAN，ZHANG RUI，HAN GUANGLIANG，et al.Moving object tracking based on multi-feature fusion in the complex background gray image［J］.Chinese Optics，2016，9（3）：320-328.（in Chinese）

［9］李超，于飞，康晓军.一种模板匹配的快速实现方法［J］.航天返回与遥感，2016，37（1）：63-70. LI CHAO，YU FEI，KANG XIAOJUN.A fast method of template matching［J］.Spacecraft Recovery&Remote Sensing，2016，37（1）：63-70.（in Chinese）

［10］崔陆月，宁媛，袁浩.运动物体的跟踪检测算法的研究［J］.工业控制计算机，2015，28（8）：88-90. CUI LUYUE，NING YUAN，YUAN HAO.Study of detection algorithm of moving objects［J］.Industrial Control Computer，2015，28（8）：88-90.（in Chinese）

［11］顾幸方，茅耀斌，李秋洁.基于Mean shift的视觉目标跟踪算法综述［J］.计算机科学，2012，39（12）：16-24. GU XINGFANG，MAO YAOBIN，LI QIUJIE.Survey on visual tracking algorithms based on mean shift［J］.Computer Science，2012，39（12）：16-24.（in Chinese）

［12］MUSAB COŞKUN，SENCER ÜNAL.Implementation of tracking of a moving object based on camshift approach with a UAV［J］.Procedia Technology，2016，22：556-561.

［13］邱道尹，张文静，顾波，等.帧差法在运动目标实时跟踪中的应用［J］.华北水利水电学院学报，2009，30（3）：45-46. QIU DAOYIN，ZHANG WENJING，GU BO，et al.Appli-cation of frame difference methods in real-time moving target tracking［J］.Journal of North China Institute of Water Conservancy and Hydroelectric Power，2009，30（3）：45-46.（in Chinese）

［14］刘洪彬，常发亮.权重系数自适应光流法运动目标检测［J］.光学精密工程，2016，24（2）：460-468. LIU HONGBIN，CHANG FALIANG.Moving object detection based on adaptive by optical flow method weight coefficient［J］.Optics and Precision Engineering，2016，24（2）：460-468.（in Chinese）

［15］李培华.一种改进的Mean Shift跟踪算法［J］.自动化学报，2007，33（4）：347-354. LI PEIHUA.An improved mean shift algorithm for object tracking［J］.Acta Automatica Sinica，2007，33（4）：347-354.（in Chinese）

［16］邓文浩，唐立才，张南锋，等.基于改进的帧差法和Mean shift结合的运动目标自动检测与跟踪［J］.现代电子技术，2016，39（4）：108-111. DENG WENHAO，TANG LICAI，ZHANG NANFENG，et al.Moving target automatic detection and tracking based on integration of modified frame difference method and Mean shift algorithm［J］.Modern Electronics Technique，2016，39（4）：108-111.（in Chinese）

［17］李建，蓝金辉，李杰.一种新型快速运动目标检测算法［J］.中南大学学报：自然科学版，2013，44（3）：978-984. LI JIAN，LAN JINHUI，LI JIE.A novel fast moving target detection method［J］.Journal of Central South University：Science and Technology，2013，44（3）：978-984.（in Chinese）

［18］屈晶晶，辛云宏.连续帧间差分与背景差分相融合的运动目标检测方法［J］.光子学报，2014，43（7）：213-220. QU JINGJING，XIN YUNHONG.Combined continuous frame difference with background difference method for moving object detection［J］.Acta Photonica Sinica，2014，43（7）：213-220.（in Chinese）

［19］黄应清，赵哲，闫兴鹏，等.改进帧差与分水岭算法融合的运动目标检测法［J］.激光与红外，2014，44（12）：1369-1373. HUANG YINGQING，ZHAO ZHE，YAN XINGPENG，et al.Moving target detection based on improved frame difference and watershed algorithm［J］.Laser and Infrared，2014，44（12）：1369-1373.（in Chinese）

［20］宋克欧，黄凤岗，兰晓亭.二值图像目标质心快速搜索跟踪算法［J］.模式识别与人工智能，1998，11（2）：161-168. SONG KEOU，HUANG FENGGAN，LAN XIAOTING. A fast algorithm for searching and tracking object centroids in binary images［J］.Pattern Recognition and Artificial Intelligence，1998，11（2）：161-168.（in Chinese）

Fusion Algorithm of Frame Difference and Mean Shift for High-Speed UAVs’Tracking

WANG Yixian，SHI Dele，YANG Ning
（Shandong Institute of Aerospace Electronic Technology，Yantai Shandong 264000，China）

In order to track high-speed UAVs in real time，the visual tracking algorithms need to satisfy the requirements of accuracy and rapidity.In this paper，a fusion algorithm was presented that combined the advantages of two typical algorithms，frame difference and Mean shift.The two algorithms were run simultaneously the frame difference was used for rapid tracking，while Mean shift was used for improving the precision of the tracking of frame difference.To get more precise tracking，the Kalman filter was used to compensate the displacement of UAVs moving during the implement of the tracking algorithm.The effectiveness of fusion algorithm was illustrated by a simulation example in Matlab environment.

UAV；object tracking；frame difference；Mean shift algorithm；fusion algorithm

TN949.2；V249.1

A

1673-1522（2016）04-0437-05

10.7682/j.issn.1673-1522.2016.04.006

2016-05-06；

2016-06-10

国家高技术研究发展计划（863计划）基金资助项目（2012AA120605）

王宜贤（1982-），男，工程师，大学。