基于蚁群聚类算法的H.264压缩域运动目标分割

基于蚁群聚类算法的H.264/AVC压缩域运动

目标分割

武智霞

（上海师范大学）

摘 要 本文提出一种基于蚁群聚类算法的H.264/AVC压缩域运动目标分割算法。首先，将从H.264压缩码流中提取出的运动矢量场进行时间、空间的归一化和中值滤波后，进行局部相同运动矢量合并，以提高运算效率；然后，利用改进的蚁群聚类算法将具有运动相似性的运动矢量聚类到若干个区域中；最后利用运动矢量方向角直方图和最终的聚类中心识别出运动目标和背景区域。实验结果表明，该算法对视频序列能实现较准确的分割。 关键词 运动目标分割 压缩域 H.264/AVC 蚁群聚类 中国法分类号： 文献表示码

Moving Object Segmentation in H.264 Compressed Domain Using Ant

Colony Algorithm

WU ZHIXIA

Abstract This paper presents a novel approach to segmenting moving objects in the H.264/AVC compressed domain, which based on ant colony clustering algorithm. Firstly, the motion vector (MV) is extracted from the H.264/AVC compressed video, and then merge the MV, who have the same nature. Secondly, an improved ant colony clustering algorithm is used to make the MV field into different motion homogenous regions. Finally, the orientation histogram of the MV field and the final cluster centers are exploited to determine the moving object regions. Experimental results for several video sequences demonstrate the proposed approach can segment moving object effectively. Keywords moving object segmentation; compressed domain; H.264/AVC; ant colony

1 引 言

运动视频目标分割技术是随着数字视频技术的发展而产生的一种新的研究领域。通过对视频流中运动目标的检测及提取，进而达到视频检索、智能视频监控等目的。

随着计算机和通信技术的发展，以高压缩比著

称的各种压缩标准相继出现。压缩域运动目标分割技术也以计算量小，能满足实时性要求，且无需对码流进行完全解码的优势引起了国内外学者的重视，近年来也取得了一些成果，但大部分都是在MPEG压缩域完成的[1-3]。针对新一代视频压缩标准——H.264/AVC，这方面的研究甚少，主要有Zeng等人[4]提出的“基于块的马尔可夫随机场（MRF）

模型”，该方法直接对稀疏运动矢量场进行分割；Sarah De Bruyne[5]等人引入了运动矢量可信度，提出“基于H.264压缩域的运动估计可信度算法”。

本文提出一种改进的“蚁群聚类算法”，能够根据运动目标的运动特征动态产生聚类中心，且迭代次数较少，适应实时性场合，能够获得较好的分割效果。

2 蚁群算法的数学描述

大量研究表明，一群蚂蚁可以很容易的找到食物源，而单个蚂蚁却不能，这是因为蚂蚁在行经过程中会不断的释放一种称为信息素（pheromone）的物质，蚂蚁个体之间就是通过这种物质来进行信息的传递。蚂蚁根据信息素的强度来指导前进的方向，越多的蚂蚁经过同一路径，则该路径上留下的信息素越多，则其它蚂蚁选择该路径的可能性也就越大，这样形成了一种正反馈过程。蚁群算法的数学描述如下：

2.1矢量场特征提取

运动矢量的产生是从压缩效率的角度上考虑的，因此从码流中提取出的运动矢量场不能反应真实的运动信息，并且存在噪声的干扰。事实上在一个运动矢量场中存在着表示背景的矢量、表示运动物体的矢量和表示噪声的矢量，表示背景的运动矢量呈现出大片相同的特点，表示运动物体的矢量呈现局部相似的特点，而表示噪声的矢量则呈现杂乱无章的特点。唯一能反应这三种矢量特征的只有运动矢量的幅值和方向角。这样，每只蚂蚁可定义为一个以运动矢量幅值、方向角为特征的二维向量。

2.2 蚁群算法数学描述

给定一个运动矢量场MV ，其中每个运动矢量

mvi看作一只蚂蚁，选取j个聚类中心Cj作为食物

源。蚂蚁寻找食物的过程就是将不同特征的运动矢量聚到j个类别中去。任意运动矢量mvi到聚类中心Cj的距离dij，采用欧几里得距离计算：

mdijpk(mvikCjk)2 （1）

k1 其中，m为每个运动矢量的维数，p为加权因子，根据运动矢量每个分量对聚类结果的影响程度而定。

设r为聚类半径，用来控制聚类精度；phij为t时刻运动矢量mvi到聚类中心Cj的路径上的信息量，则：

ph1dijrij(t) （20d）

ijr运动矢量mvi选择到聚类中心Cj的路径的概率

pij：

ph(t)ij(t)ijjS

pij(t)phis(t)is

（3）

s0其中，ij为启发式引导函数，体现运动矢量与聚类中心的相似度；、分别为信息量与引导函数对选择路径的影响因子；

Smvs|dijr,s1,2,...,N为可选路径集合。

随着蚂蚁的移动，各路径上的信息量可按下式进行调整：

phij(t1)phij(t)phij (4)

其中，为信息量随时间推移的衰减程度，

phij为本次聚类过程路径信息量的增量，定义为：

Nphijphkij (5)

k1其中，phkij为第k只蚂蚁在本次聚类过程中

留在路径上的信息量。

3 改进的蚁群聚类分割算法

进入核心算法之前对运动矢量场进行时间和空间的归一化，并通过中值滤波，最后得到采样精度为4×4块的均匀的运动矢量场。算法框图如图1所示。

3.1 聚类中心设定

经过预处理的运动矢量场具有局部运动矢量相同的特点，如静止背景中的大片平滑区域和运动完全一致的区域。先将这些区域合并可以减少蚂蚁的数量，从而减少循环的次数，加快聚类过程。

经过预处理运动矢量场还具有局部运动矢量相 似的特点，如在一些非刚性运动物体内部，并非所有运动矢量都具有相似性，可能存在部分区域相似。将这些部分相似区域划分到不同的类别中的同时可以更方便排除一些噪声引起的运动矢量。通过观察可以得出，在H.264运动估计搜索范围内，按照运动矢量的分布的密度可以大致划分出这些部分相似区域。

基于此，将搜索范围[-32，32]映射到平面坐标上以原点为圆心中心，2n（n=1,2,„,16）为半径划分成16个等级区域，如图2所示。统计落入每个等级区域中运动矢量的数量，选出N个峰值作为聚类

运动矢量场 初 始 是 是否有矢量相化 同的相邻块 模 块 合并相邻块并否 计算合并区域所含块的数目 确定聚类中心 计算运动矢量聚蚁 类中心的距离 群 聚 类 模 聚 类 块 是 是否有待分类矢量 否 运 动 类间合并运类内剔除噪目 标动区域 声块 提 取 模 块 输出结果 图1 算法框图

Fig. 1 The block diagram of algorithm

中心Cj，聚类中心的特征向量为该等级区域中运动矢量幅值的均值以及方向角的均值。这样，所选定初始聚类中心为Cj(V;G)。

32 … 6 4 Ⅲ … 2 Ⅱ -32 … -6 -4 -2 0 Ⅰ0 2 4 6 … 32 -2 -4 -6 … -32 图2 搜索范围等级区域划分 Fig. 2

3.2 引导函数

引导函数作为一种先验信息，用来表示运动矢量（蚂蚁）mvi选择聚类中心（食物源）Cj的期望程度。在蚁群算法中蚂蚁是否选择某一聚类中心，不仅取决于路径上的信息量，还需要考虑引导函数的作用。一般定义引导函数为距离的倒数。本文中对引导函数的定义如下：

rijm (6) pk(mvikCjk)21k1 运动矢量与聚类中心的相似度越小，引导函数值越大，选择该聚类中心的概率就越大；聚类半径越大，引导函数值越大，选择该聚类中心的概率也越大。 3.3 聚类步骤

步骤一 初始化，，，r，w，p等参数。 步骤二 根据3.1节的方法动态确定聚类中心

Cj。

步骤三 根据式（1）计算运动矢量mvi到不同

聚类中心Cj之间的距离dij，根据式（2）计算路径

上信息量，若dij计算引导函数ij。

步骤四 聚类开始，根据式（3）计算mvi选择各可选路径的概率pij，若最大概率pij≥w，则mvi属Cj类。否则标记为待聚类运动矢量。

步骤五 根据式（4）和（5）调整路径上的信息量，按下式更新第j类聚类中心：

MCj1Mmvk （7）

k1其中，M为本次循环中划分到以Cj为聚类中心的类中的元素个数。

步骤六 若有待聚类运动矢量，转步骤三，否则，结束循环。 3.4运动目标提取

根据聚类的结果选择面积最大且平均幅值最小的一类作为背景区域。

将运动矢量方向角[0，3.14]量化为10个等级。

统计其它各类的方向角直方图。若任两类的类间距小于c，且运动矢量方向角均呈现均匀分布时为运

动区域。这是因为一般视频序列的运动区域无论在

幅值上还是角度上都集中在1~2个量化等级上。而分布零散的往往是由噪声引起的伪运动区域。

由于在聚类的过程中很有可能把一些噪声引起的运动块错误的分到真实运动类中，而这些噪声引起的运动矢量在方向角上会出现突变的特征，因此类内根据方向角直方图剔除突变块。

4 实验结果及分析

本文所选用的测试序列均为国际标准测试序

列，运动矢量场从经JM8.6版本的H.264编码软件压缩后的码流中提取。H.264编码配置如下：Baseline Profile，IPPP...，每30帧插入一帧参考帧，1个参考帧，运动估计搜索范围为[-32，32]，量化参数为30。

图3所示为测试序列Paris第20帧的分割过程。该序列拍摄质量较好，没有太多的干扰噪声，因此聚类效果很好，（b）中显示出各类的聚类情况，可以看出人物内部运动呈明显的局部相似特点，如左 边人物头部的运动，右边人物手中小球的运动明显有别于其他部位的运动。

图4所示为测试序列hall-monitor第27帧和第144帧的分割结果。该序列受光照因素影响较大，且目标颜色和背景颜色也较为接近，给分割带来一定困难，分割结果显示背景上还存在少许噪声矢量有待进一步改进。

5 结论

本文基于H.264/AVC压缩域提出一种改进的蚁群聚类算法，该算法在对运动矢量场进行局部相同矢量合并后可以依据视频内容动态设置聚类中心，然后经蚁群算法对运动矢量进行聚类，最后根据最后的聚类中心和运动矢量方向角直方图提取出运动目标，取得了较为满意的分割实验结果。

参考文献（References）

1 R. Venketesh Babu, Ｋ. R. Ramakrishnan, et al.Video object segmentation : A compressed domain approach[J]. IEEE Transactions on

Circuits and Systems for Video Technology, 2004, 14(4): 462-474.

2 Roy Wang, Hong-Jiang Zhang, Ya-Qin Zhang, A confidence measure based moving object extraction system built for compressed domain[A]. In: Proceedings of IEEE International Symposium on Circuits and Systems[C], Geneva, Switzerland, 2000: 21-24.

3 Zen H, Hasegawa T, Ozawa S, Moving object detection from MPEG coded picture[A], In: Proceedings of International Conference on Image

(a) 原始帧 (b) 聚类后的结果

(c) 分割掩膜 (d) 最后的分割结果 图 3 Paris序列第20帧的分割过程

Fig.3 The segmentation of the 20tth frame of Paris

(a) 第27帧 (b) 第144帧 (c) 第27帧分割结果 (d) 第144帧分割结果

图 4 hall-monitor序列的分割结果 Fig.4 The segmentation result of hall-monitor

Processing[C], Kobe, Japan, 1999: 25-29.

4 Zeng W, Du j, Gao W, et al. Robust moving object segmentation on

H.264/AVC compressed video using the block-based MRF model[J]. Real-time Imaging, 2005, 11(4): 290-299.

5 Sarah De Bruyne, Chris Poppe, Steven V erstockt, et al. Estimating motion reliability

to improve moving object detection in the H.264/AVC

domain[A]. In: Proceedings of IEEE International Conference on

Multimedia and Expo[C], New York, NY, USA, 2009: 330-333.