改进mean shift算法在目标跟踪中的研究

周春云，丁伟，房伟，谢林柏

（1.国家高性能计算中心扬州分中心，万方电子技术有限责任公司，扬州 225006；2.扬州大学；3.江南大学）

改进mean shift算法在目标跟踪中的研究

周春云1，丁伟2，房伟3，谢林柏3

（1.国家高性能计算中心扬州分中心，万方电子技术有限责任公司，扬州 225006；2.扬州大学；3.江南大学）

提出了一种融合纹理和颜色模型的改进mean-shift算法，可以克服传统目标跟踪方法中目标特征单一的缺点。在传统mean-shift算法的框架下，通过融合目标信息的颜色模型和Contourlet变换后的纹理模型，从多角度建立匹配特征，并在嵌入式平台上实现本文提出的算法。实验结果显示，跟踪效果得到明显的改善。

目标跟踪；mean-shift算法；Contourlet变换；嵌入式系统

引 言

随着科学技术的快速发展，计算机视觉的应用范围越来越广，深深地影响人类的生产和生活。目标检测与跟踪是计算机视觉的重要研究课题，其涉及到图像处理、人工智能以及模式识别等诸多领域。在无人驾驶、国防安全、智能视频监控、基于视频的人机交互等领域都有广泛的应用，因此研究此课题很有意义。

视频对象检测与跟踪技术［1］是计算机视觉中一个非常关键的技术，与之有联系的应用主要有：智能视频监控、基于视频的人机交互、智能机器人、医疗诊断中的应用。此外，目标跟踪在视觉控制［2］、国防安全［3］、农业自动化［4］、视觉重构［5］等领域均有应用。目标跟踪，即在一段视频图像中的每一帧图像中找到感兴趣的目标所处的位置。一个好的视频跟踪算法一般要满足两个基本要求：实时性强和鲁棒性强。

mean-shift概念最早是由Fukunaga［6］等提出，基于Lindeberg提出的尺度空间理论［7］。Collins提出了一种改进的mean-shift算法，弥补了在运动目标跟踪中核函数带宽不能实时变化的缺陷［8］。Zhao等简化Correlogram直方图，同时考虑了目标的三维信息，结合mean-shift算法对运动目标进行跟踪［9］。Birchfield等提出一种空间直方图模型，该模型不仅考虑运动目标的颜色信息，同时考虑各个像素之间的空间位置关系。

基于传统mean-shift算法，本文在融合目标信息的颜色模型和Contourlet变换后的纹理模型基础上，从多角度建立匹配特征，最终在特定的嵌入式平台上实现了该算法。实验结果显示，本文所提出的算法能够在嵌入式平台实现，而且在视频图像的目标跟踪中，与单一特征空间的目标模型相比，本算法具有更好的鲁棒性及有效性。

1 颜色直方图的mean shift跟踪算法

1.1 目标参考模型

式中：k（·）是核函数；δ（·）是KroneckerΔ函数δ（·）；b）是指示函数，指示像素点所在直方图段数。定义如下所示：

1.2 候选目标模型

同上，归一化常数ch如下所示：

1.3 基于相似性函数的测度

目标候选模型和目标参考模型之间的相似程度可以通过相似函数来描述，两个模型的概率分布在理想情况下是相同的。通常使用Bhattacharyya系数作为相似性度量函数，用来描述候选模型和目标模型之间的相似程度，定义如下所示：

式中，ρ值为0～1，ρ值越大，表示目标模型和候选区域越相似。

1.4 位置更新

当目标模型确定后，候选区域在当前帧内移动时，令其中心为y，则得到不同的Bhattacharyya系数ρ（y），跟踪目标的位置就在ρ（y）极大值处。令初始中心位置为y0，通过泰勒展开，ρ（y）可近似为：

其中：

式（7）中只有第二项含有y，根据均值平移理论可知，只要核函数k（·）是单调的并且函数的曲线是凸的，令g（·）=-k（·），则根据均值平移理论，该概率密度估计的极值点可以从y0处递归得到，计算得到新的目标位置y1为：

2 改进mean-shift算法

2.1 Contourlet变换

Contourlet分解变换是通过两个步骤实现的：方向滤波器组（Directional filter bank，DFB）滤波和拉普拉斯金字塔（Laplacian pyramid，LP）分解。将方向滤波器和金字塔分解结合起来，就实现了Coutourlet变换，单独使用其中任何一步都不能很好地对图像进行描述。金字塔分解不具有方向性，对高频部分不能很好地分解；而方向滤波器对高频部分能很好地分解，但对低频部分不行。二者的结合可以很好地描述图像。

图像经过拉普拉斯塔形滤波器（LP）产生一个低通图像以及原图与低通逼近图之间的差值，也就是得到了该层分解后的低频子带和高频子带。方向滤波器组再对高频子带进行分解，则高频子带可被分解为2i个方向子带（i为任意正整数）。对低频子带重复上述过程，实现了对图像的多分辨率多方向分解。

2.2 纹理模型

在基于Contourlet变换的算法中，一般用子带能量的均方差和平均值来表示分解后子带的纹理。为了降低计算复杂度，本文采用子带能量的平均值来提取各子带纹理特征，即：

式中，M和N分别为各子带系数的行列数，ai，j为Contourlet变换后各子带的系数，C为归一化因子，即满足下式：

式中，Nsb表示子带的个数。

进行2级Contourlet分解得到的13个子带分别用公式（11）对其进行纹理信息提取，得到建模区域的Contourlet变换后的纹理模型：

2.3 信息融合的mean-shift算法

求得颜色特征空间和小波纹理特征空间的目标模型后，对这两个模型加权融合得到联合特征空间的目标模型。

3 目标跟踪算法实现

3.1 嵌入式系统

随着智能手机、平板电脑、MP3等数码产品的广泛使用，嵌入式系统从工业控制领域的应用渗透到人类的生产生活中，从仪表仪器、制造工业到移动通信以及数码产品各个应用领域，研究嵌入式系统有广泛的应用意义。本节交叉编译基于颜色模型的mean-shift目标跟踪算法和本文改进的mean-shift算法，把编译成功后的二进制码传输到开发板上，比较算法的优缺点，同时为以后做基于嵌入式的视频图像检测与跟踪系统做铺垫。

本文使用的是由飞思卡尔开发的i.MX53Quick Start Board工程嵌入式平台，基于MCIMX535DVV1B，可以支持Linux/Android/WinCE等操作系统，采用Cortex -A8架构，可应用于多种嵌入式设计领域。平台的参数如表1所列。

表1 硬件参数配置

3.2 环境搭建

本文嵌入式的开发采用宿主机-目标机的形式。宿主机里装有Windows XP和Linux双操作系统，通过串口、USB、以太网口与开发板相连。串口用来输出调式信息，通过USB烧写Bootloader、根文件系统，网口用来传输文件和挂载。开发环境硬件连接示意图如图1所示。

图1 硬件环境示意图

3.3 目标跟踪算法实现

本节主要用C++语言编写基于颜色直方图的mean -shift跟踪算法和本文提出的算法，然后用交叉编译工具链编译成开发平台可执行的二进制代码。

本文提出的算法的伪代码：

① 手动选取第一帧的跟踪区域。

② 分别建立目标区域纹理和颜色模型，然后建立目标区域的信息融合模型，如下所示：

③ 分别建立候选区域纹理和颜色模型，然后建立候选区域的信息融合模型，如下所示：

④ 迭代计算候选区域新位置。

⑤如果相似性函数递增，则继续执行下面的流程。否则，更新值，更新后的值变为新位置和旧位置的中点，跳转到步骤②，继续执行。

⑥ 如果新位置和旧位置的差的绝对值小于阀值，则收敛到最优点，即找到目标的质心。否则，更新值取新位置，跳转到步骤②，继续执行。

⑦收敛到最优点。

4 实验结果与分析

本文的实验环境是基于Cortex-A8、主频1GHz的嵌入式开发平台，平台上运行的系统是嵌入式Linux系统。实验所处理的视频是分辨率为128×96的彩色图像序列，是由斯坦福大学的实验室提供的，专门用于检测人脸跟踪算法的好坏。本实验视频共有50帧，含有人脸旋转、人脸不可见的情况。跟踪效果图如图2和图3所示。

图2 基于颜色模型的mean-shift跟踪效果图

图3 基于本文算法跟踪效果图

图2是基于颜色模型的mean-shift跟踪效果图，从图中可以看出，人脸姿态的变化引起视频跟踪结果的不准确，当人脸不可见时，跟踪目标丢失。图3是基于本文算法的结果截图，从图中可以看出，跟踪效果明显得到改善，始终可以很好地跟踪目标，这得益于加入的纹理模型。

由表2可以看出，本文提出的算法耗时稍微高于基于颜色模型的mean-shift的耗时，但是满足实时要求。

表2 两种跟踪算法的耗时比较

［1］侯志强，韩崇昭.视觉跟踪技术综述［J］.自动化学报，2006，32（4）：603-617.

［2］Marchand N，Chaumette F.Task sequencing for high-level sensor-based control［J］.IEEE Trans on Robotics，2007，23（1）：60-72.

［3］Yang Yunpu.Research on the model and ambiguity property of a GSM passive radar signal［J］.Electronics Transactions，2005，33（6）：1048-1052.

［4］Lenain R，Thuilot B，Cariou C，et al.Model Predictive Control of Vehicle in presence of sliding Application to farm vehicles path tracking［C］//IEEE International Conference on Robotics and Automation，2005（4）：897-902.

［5］Kyriakoulis N，Gasteratos A.Color-based monocular visuoinertial 3-D pose estimation of A Volant robot［J］. IEEE Trans Instrum Meas，2010，59（10）：2706-2715.

［6］Fukunaga K，Hostetler L D.The estimation of the gradient of a density function，with applications in pattern recognition ［J］.IEEE Transactions on Information Theory，1975，21（1）：32-87.

［7］Lindeber T.Feature detection with automatic scale selection.International Journal of Computer Vision，1998，30（2）：194-203.

［8］Collins R T.Mean Shift blob tracking through scale space ［J］.IEEE Conf.on Computer Vision and Pattern Recongnition，2003（5）：234-240.

［9］Zhao Q，Tao H，Object tracking using color correlogram［C］// IEEE Workshop on Visual Surveillance and Performance Evaluation of Tracking and Surveillance，2005（3）：263-270.

周春云（工程师），主要研究方向为嵌入式系统与并行体系结构；丁伟、房伟（工程师），主要研究方向为嵌入式系统；谢林柏（教授），主要研究方向为计算机控制系统。

9在程序设计时，要慎用长型。当不得已使用长型选择因子时，如果选择因数（case值）不是很多，选取if-thenlese的语句效果会更好。

许多参考文献都在讨论嵌入式软件设计的运行效率［4-8］。单片机程序的一个重要设计目标是对硬件的控制，因此，用汇编语言设计程序可以取得较好的效果，但汇编语言程序较难掌握，对于较为抽象的算法，用汇编语言更难，并且其可读性和可维护性较差，因此，用混合编程方法是一个好办法。另外一个途径就是，利用C语言先行设计，然后根据Keil编译的结果进行修改，也可以得到非常满意的效果。

参考文献

［1］牛洪涛.优化C51程序的方法.微计算机应用，1998（7）：237 -240.

［2］周敬利，卓越，余胜生.MCS51程序空间扩展原理及编译器优化.计算机工程，2003（5）：183-185.

［3］侯济恭，余坚.C语言开关语句的自动翻译［J］.华侨大学学报：自然科学版，1995（1）：105-110.

［4］张开便.C语言与汇编混合编程机理探析与应用［J］.电脑开发与应用，2010，23（4）：28-30.

［5］杨加国.单片机C语言与汇编语言混合编程［J］.成都大学学报：自然科学版，2008（9）：208-211.

［6］张志科，王振喜.基于Keil51汇编与C语言混合编程方法研究［J］.计算机与现代化，2010（10）：43-46.

［7］韩彩霞.单片机C语言编程中几种常见问题解析［J］.软件导刊，2013（7）：47-49.

［8］阮海蓉.Keil C51中变量的使用［J］.单片机与嵌入式系统应用，2011（5）：67-69.

（责任编辑：薛士然 收稿日期：2015-01-08）

Research on Target Tracking Based on lmproved mean-shift Algorithm

Zhou Chunyun1，Ding Wei2，Fang Wei3，Xie Linbo3
（1.National High Performance Computing Center at Yangzhou，Wanfang Electronic Technology Co.，Ltd.，Yangzhou 225006，China；2.Yangzhou University；3.Jiangnan University）

The improved mean-shift algorithm based on texture and color model is proposed，which can overcome the disadvantage of single target feature in the traditional target tracking.In the framework of traditional mean-shift algorithm，the system establishes the matching feature from multiple perspectives，by fusing color model and texture model obtained from Contourlet transform.The proposed algorithm has been realized on an embedded platform.The experimental results show that the tracking effect is improved.

target tracking；mean-shift algorithm；Contourlet transform；embedded system

TP273

A

��薛士然

2015-01-13）