改进的Mean Shift算法在前视声呐运动目标跟踪中的应用

崔 杰，胡长青，徐海东，吕银杰

(1.中国科学院声学研究所东海研究站，上海201815；2.中国科学院大学，北京100049；3.嘉兴易声电子科技有限公司，浙江嘉兴314000)

0 引 言

随着海洋资源开发和军事安全的需求，水下安防工作受到越来越多的重视。多波束前视声呐分辨率高，成像速度快，既能在高速的运动状态下快速成像，又能针对高速运动中的目标快速成像[1-2]。多波束前视声呐通常采用宽波束发射，通过同时预成多个接收波束来得到大扇面的方位-距离图像，可以在固定不动时得到同一场景的多帧视频图像[1]。因此多波束前视声呐的出现使得蛙人探测、小型潜器监视等侦察警戒任务得以实现，基于图像序列综合处理的水声视觉智能技术受到国内的极大关注。

目标跟踪的方法是按照目标特征，根据颜色、纹理、形状等特征来进行跟踪。从方法的角度来说，可分为基于滤波理论的跟踪技术、基于Mean Shift的跟踪技术、基于粒子滤波的跟踪方法和基于偏微分方程的跟踪技术等。基于水声图像的目标跟踪技术起步较晚，并且多借鉴光学成像中的跟踪技术。国外的研究比我国起步要早，有相对成熟的解决方案，但由于技术较为敏感，相关的研究报告和技术细节极少公开报道。国内主要有中国科学院、中国船舶重工集团、高校等单位进行相关研究。

Mean Shift是一种基于密度梯度的非参数特征空间分析方法，算法的实时性好且容易集成，在目标跟踪领域有着广泛的应用。Mean Shift算法的跟踪模型为核函数加权颜色直方图，具有对边缘遮挡、目标的旋转、变形及背景运动都不敏感的特点。Mean Shift算法也存在局限性：缺乏必要的模板更新算法；跟踪过程中窗口大小保持不变，当目标的形状或者尺寸发生较大变化时，存在跟踪失败的可能；直方图是一种较弱的目标特征，当背景和目标的直方图分布相近时，算法的跟踪效果欠佳[3-5]。

本文主要研究Mean Shift跟踪算法在声呐图像目标跟踪中的应用，并针对算法跟踪框固定不变的缺点提出了一种更新策略。

1 Mean Shift跟踪算法

Mean Shift算法需要在起始帧通过手动确定搜索窗口来选择运动目标，计算搜索框内的核函数加权颜色直方图来建立目标模型，用同样的方法计算下一帧对应窗口的直方图分布，用巴氏(Bhattacharyya)系数来描述目标与候选目标之间的相似性，以两个分布的相似性最大为原则，使搜索窗口沿密度增大最大的方向移动，通过Mean Shift迭代来得到目标的真实位置[4-5]。以下简要介绍其过程。

1.1 建立初始帧目标模型

给定跟踪窗口T，x0为跟踪窗口T的中心，{xi}i=1⋅n表示窗口内各个像素的坐标，定义函数b：R2→{1,…,m}，使b{xi}对应xi处像素的颜色索引，则跟踪窗口T图像的概率密度函数定义为

其中：u=1,⋅⋅⋅,m对应颜色索引；是Epanechnikov、高斯(Guassian)等核函数；h是核函数的带宽；δ是克罗内克(Kronecherdelta)函数，用于判断xi处的颜色值是否属于特征值；C是归一化系数。

1.2 候选目标模型

对应初始帧目标模型，假设当前帧中候选目标的中心为y，为候选目标中的像素位置，候选目标的模型可以表示为

式中：Ch对应式(1)中的C。

1.3 相似性度量

相似性系数用来度量目标与候选目标之间的相似度，目前在Mean Shift跟踪中使用最为广泛的是Bhattacharyya系数，其定义为

1.4 Mean Shift向量

Bhattacharyya系数的局部最大值点可以视为当前帧中的目标位置。以前一帧的目标中心y作为当前帧的目标中心，然后此处开始找寻最优的匹配目标，在处对式(3)进行泰勒展开，可得：

式(4)中，第一项与y无关，而第二项表示坐标y处的含密度估计，其中每个像素点的权重用wi表示。因此，寻找最优候选目标的问题就转化为寻找概率密度函数局部极值位置的问题，它可以通过Mean Shift迭代的方法完成。令，得到Mean Shift的迭代形式：

其中：g(x)=-k'(x)；y0是第N帧搜索窗口的中心坐标；y1表示寻找到新的搜索窗口的中心坐标。

2 运动目标分割

背景消减法是一种常用的基于图像序列的运动目标检测算法，对智能监控中的目标跟踪识别和行为分析等后续处理十分关键。

背景消减法通过计算当前帧与背景模型的差来实现运动目标的检测，因此背景建模是背景消减法的关键。目前已有的背景建模方法有均值背景模型、中值背景模型和混合高斯模型等，本文依据算法效果和复杂度选择中值背景模型来构建[6-8]。

2.1 中值背景构建

中值背景模型适合背景变化不大的场景，同时也能很好地避免均值背景模型存在的“拖影”现象[7-8]。中值背景模型原理简单，取一段时间内的连续K(K为奇数)帧图像，I1(m,n),⋅⋅⋅,IK(m,n)表示像素点(m,n)的时域序列，I(1)(m,n),⋅⋅⋅,I(K)(m,n)表示像素点(m,n)按从小到大排序的序列，则像素点(m,n)的背景像素为：

2.2 运动目标分割

将每一帧待检测的图像减去背景图像，然后对差分图像进行分割操作。设像素点(m,n)在第k帧的值为Ik(m,n)，背景图像的值为B(m,n)，则差分图像的值表示为

选用合适的阈值对差分图像进行分割即可得到运动目标的二值图像。在这里本文选择最大类间方差(Otsu)算法对差分图像进行分割，该算法是一种高效的图像二值化算法。

对于图像I，前景(即目标)和背景的分割阈值记为T，前景像素点数占整幅图像的比例记为ω0，平均灰度为µ0，背景像素点数占整幅图像的比例记为ω1，平均灰度为µ1，图像的类间方差g为

用遍历法求使得类间方差g最大的阈值T，然后用T对差分图像进行二值化操作：

由式(10)得到的二值化图像即为移动目标的二值图像。

3 本文算法

经典的Mean Shift跟踪算法缺乏有效的目标更新策略，并且无法有效地估计目标的尺度。本文针对以上缺点，结合背景消除算法的运动目标检测算法，提出了跟踪窗口随目标大小实时更新的Mean Shift跟踪算法。

算法的原理是利用Mean Shift迭代来完成帧间目标定位，然后在目标定位的范围内利用图像分割对目标的尺寸和跟踪模板进行更新，以实现跟踪窗口随目标大小和形状的自适应变化[9-10]。具体算法流程如下：

(1) 初始化：选择初始帧图像，人工标记待跟踪的运动目标，计算目标的最小跟踪框，并依据1.1节的方法建立目标模型。

(2) Mean Shift迭代：依据1.2～1.4节的方法，选择当前帧图像进行Mean Shift迭代，计算出当前帧中目标中心和跟踪框位置。

(3) 运动目标分割：根据第2节中的方法，对运动目标进行分割，实现运动目标的二值化。

(4) 匹配：根据步骤(2)中Mean Shift跟踪框标记和(3)中的运动目标，计算被标记目标的最小外接矩形，如果最小外接矩形与跟踪框长度和宽度的误差不超过10%，则对跟踪框进行更新，否则不更新。

(5) 更新：依据步骤(4)中新的跟踪框重新建立目标模型。

(6) 循环：回到步骤(2)，对更新后的目标进行跟踪。

4 实验结果分析

本文实验设备选择Kongsberg 公司生产的M3多波束前视声呐，实验场地为某湖上的双体实验船。声呐置于双体船中部的实验甲板中，水域处于自然环境状态，水体中存在线缆及鱼群等干扰物。本文考虑的主要应用场景为海事设施周围对蛙人、水下机器人的监控和跟踪。声呐处于固定状态，受水域限制，前视声呐的探测距离设置为40 m。

实验选用两个相同尺寸的钢丝铁笼作为目标，分别标记为目标1和目标2，其底部最大直径为45 cm，笼口直径为28 cm，笼口到笼子底部的高度为45 cm。目标在前视声呐视野范围内由细绳牵引、人工拖曳进行上下运动，共采集228帧图像。

本文选用经典Mean Shift算法和本文改进后的算法对两个目标进行跟踪。下面通过跟踪轨迹、目标框选和跟踪误差来对两种算法进行评价。

4.1 跟踪轨迹

在本次试验中，目标先在水中下沉后经人工拖曳上浮，采用经典Mean Shift算法和改进后的算法完成了对目标的追踪。目标的跟踪轨迹如图1所示，其中目标1的跟踪轨迹为红色，目标2的跟踪轨迹为绿色。图1(a)是中值背景下(声呐固定，背景固定，但背景中存在鱼群等运动目标的干扰)x-y平面的目标跟踪轨迹，可以看出目标运动的轨迹基本为沿着y轴方向的上下运动。图1(b)是目标的三维运动轨迹，可以看出目标随时间的帧位置变化。

两种算法的跟踪轨迹效果通过肉眼很难看出明显的差别。在下文中通过跟踪框和跟踪坐标的误差来进行具体的对比。

4.2 跟踪框效果

图1 目标跟踪轨迹Fig.1 Target tracking trajectories

为了验证本文算法对跟踪框更新的效果，本文与经典Mean Shift算法进行对比。图2(a)和图2(b)分别是目标1和目标2的跟踪效果对比图，图中依次展示了第1,31,61,⋅⋅⋅,211帧共8帧图像的目标图像和跟踪框，其中红色跟踪框是经典Mean Shift的跟踪框，绿色跟踪框是改进后算法的跟踪框。

图2 经典和改进Mean Shift算法的跟踪框效果对比Fig.2 Comparison of tracking box effects of classical and improved Men Shift algorithms

如图2(a)所示，目标1在运动过程中大小没有发生明显变化，跟踪框的大小变化不明显，跟踪框的中心为Mean Shift算法迭代的目标位置。在Mean Shift算法迭代过程中，基于Bhattacharyya系数的概率密度函数相似性度量会收敛到局部极值。但该极值可能并不是最优解，因此会出现定位偏差，并且Mean Shift的收敛位置多数情况下并不是目标的中心，因此经典的Mean Shift算法存在定位误差和跟踪框无法准确框选运动目标的问题。改进后的算法能够根据目标的大小和形状对跟踪框的位置和尺寸进行更新，并根据更新后的跟踪框对目标模板进行更新，因此跟踪效果比经典的Mean Shift算法更为准确。

如图2(b)所示，目标2在运动过程中由于角度或姿态问题出现了逐渐变小的情况。经典的Mean Shift算法在该情况下虽然完成了对目标的定位，但是由于固定跟踪框的问题，在目标变小的情况下框选了较多的背景信息，而本文的改进算法可以对目标的大小进行实时更新，跟踪框在目标变小的情况下进行了自适应调整，对目标的描述更为准确。

4.3 跟踪定位误差分析

图3 经典和改进Mean Shift算法的跟踪误差对比Fig.3 Comparison of tracking error between classical and improved Mean Shift algorithms

图3是两种算法跟踪坐标的欧式距离误差，其中参考坐标为每帧图像手动标定目标的最小外接矩形中心。其中图3(a)和图3(b)分别目标1和2的误差，其中红线表示经典Mean Shift跟踪算法的误差，绿线表示由上一帧目标模型更新后Mean Shift跟踪(简称更新后跟踪)算法的误差，蓝线表示目标模型更新后跟踪框(简称跟踪框更新)的误差(因为手动标定目标和自动分割目标存在不可避免的误差)。由于目标1的形状变化较小，目标更新对跟踪结果的影响较小；而目标2在运动过程中后期有较明显的伸缩变化，目标更新后的效果则比较明显。

表1是两种算法在不同方向上的均方根误差(Root Mean Square Error, RMSE)，参考坐标同样是目标分割后的质心。从表中可以看出，在x方向、y方向和欧式距离上，目标更新后跟踪算法的算法误差相比传统的Mean Shift算法有了较大的改进，并且目标模型的更新能较准确地定位目标的真实位置。

表1 跟踪结果的均方根误差Table 1 Root mean square error of tracking results

5 结 论

本文将Mean Shift算法用于多波束前视声呐的运动目标跟踪问题，并对Mean Shift算法提出了一种改进方案。该算法利用Mean Shift实现目标的帧间定位，通过基于图像序列的背景消减法实现运动目标分割，根据分割后目标的位置和大小对Mean Shift跟踪框进行更新，并重新建立目标模型来迭代实现目标的准确跟踪和框选。实验数据表明，改进后的算法跟踪框可随目标的尺寸变化进行更新，对目标的定位和框选更加精准。

本文算法实现了简单背景下跟踪框随目标变化的实时跟踪。可以预见，本文算法在复杂场景下目标受背景干扰较大时的效果可能欠佳。因此，在下一步的工作中需要从鲁棒性的角度出发对算法进行改进。