一种快速的视频跟踪算法

摘要：在摄像头固定的视频监控系统中，本文给出了一种基于最小化随机复杂度的快速有效的视频目标跟踪算法。该算法结合了基于背景减技术和目标相似性建模的优势，不需要调整参数权重。实验结果表明，应用本方法能快速的估计运动目标的位置和矩形轮廓。

关键词：目标跟踪；随机复杂度；视频监控

中图分类号：TP391 文献标识码：A文章编号：1007-9599 (2011) 09-0000-02

A Fast Video Tracking Algorithm

Xie Ge

（Computer School,Wuhan University,Wuhan430072,China）

Abstract:In the video surveillance system with fixed camera,this paper puts forward a quick and effective video target tracking algorithm based on the minimization of stochastic complexity.This algorithm combines the advantages of the minus technology based on the background and modeling of target similarity without need for adjusting the parameter weight.The experimental results show that this method can estimate the location and the rectangular shape of the moving target quickly.

Keywords:Object tracking;Stochastic complexity;Video surveillance

视频序列图像中的目标跟踪是一个非常重要的研究内容，在许多方面应用广泛，特别是在视频监控系统中尤其如此。在这些系统中，实时性和快速性的需求非常高，而且在通常情况下，跟踪目标是变化的和非刚体的，因此，不仅跟踪目标的位置，而且跟踪目标的大小必须被估计。本文提出了一种基于最小化随机复杂度[1]和积分图像[2]的目标跟踪算法，它实现了不需要修改系统参数和设定目标大小的情况下对视频目标的快速跟踪，而仅仅需要在背景和目标灰度级的简单的概率密度函数。考虑到背景的变化情况，我们假设目标的灰度级从前一帧抽取。

设bt（x，y）是像素（x，y）在t时刻的背景像素值。同时，它被认为是一个概率密度为pB（x，y）的静态随机变量，其值仅与像素的坐标有关。像素的概率密度能够通过在线学习的方式获得，设st是t时刻的图像，背景减方法[3]能够检测出像素值st（x，y）是否符合背景的概率密度分布PB（x，y）。块匹配技术接着用来从二值检测图中找出目标位置。尽管这些方法能实现有效的跟踪，但是它们的主要局限性在于目标跟踪过程与检测过程是独立完成的。

其他一些方法[4]试图在图像中找到一些给定的已知的目标，通常情况下，这些算法通过优化时刻t所得到的候选目标特征与目标的期望特征之间的相似度来定位目标的位置。但是这些方法并没有考虑到学习背景概率密度PB（x，y）的代价，而且，如文献[5]所述，目标大小的估计并没有在这些方法中给出。

在本文中，我们主要考虑相机固定情况下的目标跟踪问题，所给出的算法克服了上述方法的局限性。算法分为随机复杂度的计算，最小化随机复杂度，以及结合积分图像的跟踪方法。下面将逐一进行介绍。

一、随机复杂度的计算

设Ω表示t时刻图像st中与候选目标有关的像素集，标识区域Ωc的补集。随机复杂度Δt（Ω）定义为：需要熵编码和给定的候选目标区域编码图像的代码长度。代码的长度由三项组成：

Δt（Ω）=Δtshape+ΔtΩ+ΔtΩc （1）

第一项Δtshap编码目标的形状，第二项ΔtΩ和第三项ΔtΩc分别表示编码目标形状之内像素的灰度值以及编码目标形状之外像素的灰度值。由于相机假设为固定状态，因此直接编码目标形状之外的像素值没有意义，仅仅对于假定具有空间独立性的背景像素概率分布函数的波动有意义。在这种情况下，根据[1]，需要编码的像素值St（x，y）的代码长度可以通过香农信息熵来log PB（x，y）（St（x，y））计算，有

（2）

相比之下，在Ωc内，像素值对目标对象建模是足够的。设PA为目标对象的概率分布函数（设对目标内的所有像素）已在之前的图像中被估计。因此，在Ω内需要对像素值编码的长度为：

（3）

为了减少计算代价，假定概率分布函数PA符合目标均值为mA方差为σA的高斯分布，假定概率分布函数PB符合背景均值为mB方差为σB的高斯分布，下面我们将给出随机复杂度框架，在此框架下，我们可以得到一个较好的结果。等式（2）和（3）能被重写为：

，

（4）

其中，NΩ与NΩc分别为Ω内与Ωc外的像素的数量，fAt（x，y）与fBt（x，y）分别为

，

（5）

为了快速的估计目标的位置与大小，我们把目标的形状建模为矩形，在这种情况下，形状Ω能够通过矩形上对角点的坐标来表示，这样在Ω上的编码长度是独立的。最小化随机复杂度Δt（Ω）相当于最小化ΔtΩ+ΔtΩc，比如，估计Ωt时刻目标的形状就是最小化ΔtΩ+ΔtΩc的形状。

二、最小化随机复杂度

定义：

（6）

等式（4）中的表达式ΔtΩc能改写为：

（7）

得到

（8）

其中N=NΩ+NΩC是整个图像中的像素个数。因为kt与N/2*log2π不依赖于Ω，ΔtΩ+ΔtΩc的计算量主要是在目标形状范围内对函数Ω求和，而函数 的求解通过积分图像可以很容易的得到[2]。的确，在任何矩形表面 对ft（x，y）求和可以通过四个加法运算得到，其中 可以通过积分图像由下式得到：

（9）

因此，最小化随机复杂度函数通过如下步骤得到：先估计目标平移；再通过变形矩形轮廓来改变目标的形状，使得概率复杂度减小。为了减少计算时间，在时刻t的积分图像仅仅在搜索窗里被计算，此搜索窗相当于t-1时刻的目标形状的估计并且加宽20个像素宽度。

三、实验结果与分析

为了验证算法的有效性，对本文算法进行了实验分析。算法由VC++实现，机器为P4双核1G内存的，系统为Windows xp，在实际应用过程中，对于分辨率为640×480像素的图像目标大小和位置的估计能够在5毫秒内完成。我们所采用实验视频抽取其中几个有代表性的帧见图1（第一行），目标区域的矩形形状通过给定的方法获取，跟踪结果仅仅只需图像的亮度信息。目标参数mA与σA在目标出现的时候首先被估计，同时背景参数mB与σB通过对目标出现之前的背景图像求平均获得。为了证明所给随机复杂度标准，我们用基于Bhattacharryya距离的标准方法进行比较（见图1第二行）。从图可以看出，相比基于Bhattacharryya距离的标准方法，所给的基于随机复杂度的方法提高了结果的准确性，而且不需要像前一种方法那样估计目标的位置和大小。即便是仅估计目标的位置，形状保持固定，相比标准方法，目标也能被较好的定位。而且，图1第3行的结果表明，和所给方法相反，标准的背景减算法并不能充分的获得运动目标的完整形状，并且由于雪花的干扰会产生较高的虚警率。

所给方法在另外一段视频上获得的结果（如图2所示）表明，尽管这段序列图像背景纹理较强，并且和目标也极其相似，但是目标在整个视频序列中仍然能被正确的跟踪。

图1第一行由本文方法获取的图像，第二行由基于标准Bhattacharryya距离获取的图像，第三行为背景减方法得到的结果

图2.用本文方法得到的两种户外视频序列场景得到的跟踪结果

四、结论

本文给出了一种基于最小化随机复杂度的快速有效的视频目标跟踪算法，相比传统的目标跟踪算法，在目标位置与大小等跟踪属性方面有了明显的提高。本文由于是在单色背景下对视频进行处理，对于彩色图像，我们可以考虑引入表征颜色的向量信息，以提高目标和背景概率分布函数的精度，从而提高目标跟踪的效果。另外，本文只考虑了单一目标跟踪的情况，但是对多目标的检测与跟踪是视频跟踪技术发展的趋势，这是我们今后的研究目标。

参考文献：

[1]Rissanen J,stochastic complexity in statistical Inquiry,vol.15 of series in computer science(World scientific,1989)

[2]Viola P and Jones M,Robust Real-Time Face Detection,IEEE Conference on Computer Vision and Pattern Recognition,2000,511-516

[3]Stauffer C.and Grimson W.E.L.,Learning Patterns of Activity Using Real-Time Tracking,IEEE Trans.Pattern Anal.Mach.Intell.2000,22:747-757

[4]Isard,M.,Blake,A.1998 CONDENSATION-Conditional density propagation for visual p.Vision 29,5-28.

[5]滕游,董辉,俞立.基于DSP的运动目标检测与跟踪系统设计[J].浙江工业大学学报,2009,6:607-609