基于Mean+Shift算法的实时运动目标跟踪

基于Mean+Shift算法的实时运动目标跟踪

山西电子技术２００８年第５期

应用实践

基于ＭｅａｎＳｈｉｆｔ算法的实时运动目标跟踪

丁大钢

黄欢

刘辉

罗山

（昆明理工大学信息工程与自动化学院，云南昆明６５００５１）

摘要：Ｍｅａｎｓｈｉｆｔ算法是一种非参数密度估计算法，可以实现实时的最优匹配，为了把Ｍｅａｎｓｈｉｆｔ算法应用到视频图像的运动目标跟踪中去，采用了以颜色直方图建立目标模型的策略，提出了在视频图像中以Ｍｅａｎｓｈｉｆｔ为核

心的目标跟踪算法。实验结果表明，该算法具有很好的鲁棒性、准确度等优点，在运动目标部分遮挡的情况下仍能

实现稳定、实时的跟踪。

关键词：运动目标跟踪；ＭｅａｎＳｈｉｆｔ；颜色直方图；Ｂｈａｔｔａｃｈｍ３９ａ系数中图分类号：ＴＰ３９１．４文献标识码：Ａ

０引言

进一步变形（３）式写成向量的形式：

运动目标的实时跟踪在计算机视觉领域有着非常重要的应用。近年来在目标跟踪领域提出了许多很好的算法，

＾小）＝去喜杨（０宁¨

（４）

式（４）是一般ＭｅａｎＳｈｉｆｔ算法计算无参密度函数估计的常用Ｃｏｍａｎｉｃｉｕ将Ｍｅａｎｓｈｉｆｔ算法引入到了运动目标跟踪领公式。

域ｕ．２ｊ，该算法是以彩色直方图作为特征来实现目标的识别１．２

ＭｅａｎＳｈｉｆｔ向■

与定位的，目标的直方图具有特征稳定，抗部分遮挡和计算量小的特点。并以迭代的方法实现快速搜索，是一种比较理在得到ＭｅａｎＳｈｉｆｔ的密度函数估计式（４），为了得到

Ｍｅａｎ想的目标跟踪方法。然而直方图无法反映任何目标的空间Ｓｈｉｆｔ向量，需要对（４）式求密度梯度估计函数，密度梯

信息，会搜索到和目标直方图相似而与实际情况不符的错误度估计函数恒等于核函数估计的梯度，利用核函数的可微性，得到：

目标。但是在并不复杂的场景中，运动目标非剧烈变化，很短的时间间隔内，目标的颜色分布和结构特征的绝大部分保持相对不变。虽然无法保证每个像素的一一对应，但是目标啾“ｚ）＝Ｖ＾“ｚ）＝南喜（ｚ一枷７（８宁８

２）

（５）

的各个区域间的对应关系还是存在的，因此保留现有的视频令ｇ（ｚ）＝一忌７（ｚ），假设除了有限个点，核函数Ｋ（ｘ）的梯图像信息而不进行动态背景更新是有必要的。本文基于此度对所有ｚ∈［０，ｏ。）均存在。将ｇ（ｚ）作为核函数，核函数

选出候选目标，并通过不断迭代计算ＭｅａｎＳｈｉｆｔ向量，在当Ｇ（ｚ）可以定义为：Ｇ（ｘ）＝ｇ（０ｚ

ＩＩ２），因此将ｇ（ｚ）代入

前帧中得到目标的真实位置，从而达到目标跟踪的目的。

（５）式，可以得到：

１

Ｍｅａｎｓｈｉｆｔ的原理

１．１多维空间下的无参密度估计

瓤“加嘉喜（ｚ一砒（０宁１１２）

给定一组ｒ１个一维空间的数据点的集合８＝

｛≈ｌｆ＿Ｉ．。，它的未知的概率密度函数为ｆ（ｘ），取核函数为＝南ｃ喜ｇｃ擀ｎ６宁｜｜２）］

Ｋ（ｚ），那么在ｚ点处的密度可以按下式计算：

．

１

０１１

（６）

，（ｚ）＝寺∑Ｋ（ｘ—Ｘｉ）

（１）

上式可以理解为：将在每个采样点为中心的局部函数的平均ｌ再叫ｌ丁¨

Ｘ－－Ｘｉ

２一－１ｊ效果作为该采样点概率密度函数的估计值。在计算机视觉中多变量的核函数更适合表达图像的一些特点，因此需要构造多维空间下的无参密度估计，在ｄ维欧式空间Ｘ中，ｚ表ｊ知［喜ｇ（《旦≯６２）］称为在ｚ点处基于核函数Ｇ（ｚ）

示该空间中的一个点，Ｋ０（ｚ）表示该多维空间中的核函数，

类同［１１式，ｄ维欧式空间中点ｚ估计的密度函数为：

＾

ｌ

Ｔｋ

ｆ（ｚ）＝｛２』Ｋｏ（ｚ—Ｘｉ）

（２）

，竹＾，Ｇ（ｚ）＝三ｔ｝——１————万一ｚ

＂ｉ＝ｌ

∑ｇ（１罕∞

ｌ

－

其中：Ｋ二（ｚ）＝ＩＨＩ－童Ｋ（ＩＨＩ一言ｚ），Ｈ表示ｄ×ｄ带宽矩，竹。，Ｇｃｚ，＝群＂１宁１一ｚ

ｃ７，（７）

阵。将此带宽矩阵写成单位阵形式Ｈ＝ｈ２Ｊ，则［２１写成为：

，（工）＝刍∑杨（气产）

一

＇．上…．

（３）

ｒｅ（ｘ）＝｛∑（麓一ｚ）

（８）

收稿日期．＇２００８－０７—１５第一作者丁大拥男２６岁硕士研究生

万方数据

基于Mean+Shift算法的实时运动目标跟踪

第５期丁大硼，等：基于ＭｅａｎＳｈｉｆｔ算法的实时运动目标跟踪

田１Ｍｅａｎ碍ｆｉｆｔ向■、

图１很好的说明了（８）式的意义，中间的实心黑点表示２点，也是（７）式中的核函数ｇ（ｚ）的中心。周围的空白点是样本点ｚ。。箭头表示样本点相对于核函数中心点ｚ的偏穆向量，平均的偏移量会指向样本点最密的方向，也就是梯度方向。因此，ＭｅａｎＳｈｉｆｔ向量％ｃ（ｚ）应该转移到样本点相对点ｚ变化最多（最大）的地方，其方向也就是密度梯度的方向。一般而言，离越近的采样点对估计ｚ周围的统计特性越重要，因此引入了核函数的概念，（７）式中ｇ

¨…０

２

（９Ⅱ

１Ｔ兰０）就是每个采样点的权值，所以（７）式就是在核函

ｎ

ＩＩ

效ｇ（ｚ）加权下豹Ｍｅａｒ－Ｓｈｉｆｔ向量。

１．３

Ｍｅａｎ晶．ｆｃ算法

利用（６）式把ＭｅａｎＳｈｉｆｔ向量重新整理．得到：

ｍ＾Ｇ（ｚ）＝｛＾２要丛生

（９）

‘

，Ｇ（ｚ）

函数的关系，也说明了由棱函数Ｇ（ｚ）可以推导得到№

（９）式说明了ＭｅａｎＳｈｉｆｔ向量与以Ｋ（ｚ）和Ｇ（ｚ）为核

Ｓｈｉｆｔ向量。ＭｅａｎＳｈｉｆｔ算法的基本步骤是，给定一个初始点ｚ．核函数Ｇ（ｚ）及允许误差Ｅ．ＭｅｍｔＳｈｉｆｔ算法循环地执行下面三步，直到条件满足：

１）计算ＭｅａｎＳｈｉｆｔ向量巩．‘扣）；２）把ｍ＾Ｇ扛）赋给ｚ；

３）如果ｌｌ佩．Ｇｈ）一ｚＩＩ＜ｅ，结束循环，否则，继续执行（１）。

２

ＭｅａｎＳｈｉｆｔ在目标跟踪中的应用

对在初始杖图像中目标区域内所有的像素点，计算该区

域内目标特征，我们称之为目标模型的描述。在以后的每帧图像中可能存在目标的候选区域中的计算目标特征称之为候选模型的描述。核函数一般选择Ｅｐａｎｅｃｈｉｋｏｖ函数口Ｊ。利用相似性函数度量初始帧目标模型和当前帧候选模型的相

似性，通过求相似性函数最大得到关于目标的Ｍ哪Ｓｈｉｆｔ向

量，这个向量即是目标从初始位置向正确位置转移的向量，由于Ｍ朗ｎＳｈｉｈ算法是收敛的ｉｚｊ，不断迭代计算Ｍｅａｎｓ｝ｌｉｈ向量．在当前帧中，最终目标会收敛到目标的真实位置，从而达到跟踪的目的。２ｌ目标模型的描述

目标区域的中心为ｚｎ，假设其中有ｎ个像素用

｛蕾｝川。表示，目标特征６捕的个数为ｍ个，则目标特征估

计的概率密度函数为：

乱＝ｃ∑＾删盟≯Ｉ‘）龇６（ｍ）一“】（１０）

由于遮挡或者背景的影响，目标模型中心附近的像素比外面的像素更可靠，ｋ（ｚ）对中心的像素给一个大的权值，而远离中心的像素给一个小 …… 此处隐藏：11902字，全部文档内容请下载后查看。喜欢就下载吧 ……