基于聚类的背景建模方法

朱敏

摘要：对图像序列中的运动目标进行实时检测是视频处理领域一项基础性工作，背景减除法是主要的运动目标检测方法，有许多的背景模型用于处理不同的问题。提出了一种基于改进的K均值聚类算法的背景建模方法。实验结果显示该方法在复杂背景环境下具有有效性和鲁棒性，取得了较好的精确度。

关键词：背景减除法；背景建模；K均值聚类

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2015）28-0141-03

Background Modeling Method Based on Clustering

ZHU Min

（Dept. of Management & Information， Nantong Shipping College， Nantong 226010， China）

Abstract：Real-time moving objects detection in image sequences is a fundamental step in the video processing field. A typical method is background subtraction. Many background models have been introduced to deal with different problems. This paper proposes a improved K means clustering based Background modeling method. The experimental results show that the proposed method is efficient and robust for the dynamic environment and achieves good accuracy.

Keywords： background subtraction； Background modeling； K means clustering

分析和理解视频序列是一个热点的研究领域，与此相关的应用很多，如智能视频监控、人机交互的感知接口、医疗图像分析、军事上的导弹制导、雷达视频图像分析等。运动目标检测是这类研究的基础，运动目标检测将运动物体（前景）从静态信息（背景）中分离出来。

常用的运动目标检测方法有背景减除法、帧间差分法、光流法等，其中背景减除法因其原理简单、易于实现、所检测的运动对象完整等特点，是最常用的一种方法。

1 背景减除法

背景减除法的基本思想是先构建一个不包含运动物体的静态背景图像，然后用当前图像与背景图像对应像素点的灰度差值来判断运动目标，如果灰度差值大于设定的阈值，则判定该像素点属于运动目标；如果灰度差值小于设定的阈值，则判定该像素点属于背景。使用背景减除法进行运动目标检测通常包含以下几个步骤：

1）背景建模：背景减除法首先要确定使用何种方式对背景建模，这是背景减除法的关键所在。

2）背景初始化：最简单的背景初始化方法是以视频序列的第一帧作为初始背景。也可以用一段训练视频通过学习得到初始背景。

3）背景更新：背景不是一成不变的，随着时间的变化，背景场景会发生变化，与此相适应，背景图像也应该及时更新。

4）前景检测：前景检测把当前图像与背景图像进行比较，把当前图像中的每个像素划分为前景像素或者是背景像素。

背景减除法的基本思路非常简单，但在实际应用中却面临一系列的问题。比如在动态的环境下，要获取一个没有运动物体的静态背景图像是非常困难的。此外，诸如变化的光照条件、摄像机的抖动、波动的水面、晃动的树木等都对背景图像的建立构成挑战。为解决这些问题，人们提出了各种各样的背景建模方法。

Stauffer与Grimson提出了混合高斯模型[1]对动态背景建模，混合高斯模型使用多个高斯模型来表征图像中的像素点，通过对每个分布的匹配检验，来判断哪个分布最接近背景分布。能较好地适应缓慢变化的动态场景，如渐变的光照，摇动的树木等。但它的计算复杂度较高，无法处理像光照的突变、前景停留或背景移出等情况。Karmann与Brandt建立了基于Kalman滤波[2]的自适应模型，该模型较好地随天气和光线等的改变调整背景。Kyungnam Kim 等人提出了码本算法[3]，通过长时间的采样对每个像素不同值的出现频率进行统计，以此区分背景和前景，同时对于一些动态的环境干扰具有一定的抑制能力，但是其计算开销较大，实现复杂。Butler等人提出了基于K均值聚类的建模算法[4]，利用最小距离准则对每个像素分类，该方法的优点是计算的复杂度比较低，但它对初始聚类中心选取的依赖性很大，容易陷入局部最优解。

本文提出了一种基于改进的K均值聚类算法的背景建模方法，解决由于初始聚类中心选择的随机性而可能导致的局部最优解问题。

2 k均值聚类算法介绍

k均值聚类算法是一种基于样本间某种距离或相似性度量来定义的一种间接聚类方法，其基本思想是：在一个待分类的数据样本集中，随机选择k 个对象， 每个对象代表一个聚类中心。对其余的每一个对象， 按该对象与各个聚类中心之间的距离， 把它分配到与之最相似的聚类中， 使得聚类内部对象之间的相似度最大， 而聚类之间对象的相似度最小， 其中聚类的相似度是关于聚类中对象的均值度量， 可看成聚类的质心或者重心。然后， 计算每个聚类的新中心。重复上述过程， 直到准则函数收敛。

设X 是待分类的数据样本集，第i个聚类Ci有Ni个样本，mi是这些样本的均值，即

那么所有样本与其所属的聚类中心之间的误差平方和为

通过迭代，不断调整样本所归属的聚类使Je极小，使Je极小的聚类C1，C2，…，Ck就是样本集 X的最优划分。

K均值算法的步骤为：

（1）任意选择K个对象作为初始聚类中心；

（2）计算每个对象到各个聚类中心的距离，根据最小距离原则划分对象所归属的聚类；

（3）重新计算各个聚类的均值并将其作为该聚类的中心；

（4）重复（2）、（3）直到各个聚类不再发生变化为止。

3 改进的K均值聚类背景建模方法

对上述传统的K均值聚类算法进行分析，该算法最大的问题在于初始聚类中心的选取是随机的。选择不同的初始聚类中心，得到的最终聚类结果是不同的，导致的后果是容易陷入局部最优解。文献[5]提出一种基于遗传算法的K均值聚类方法，但这种方法只适用于样本数量较小， 类别数不大的情况， 如果数据量大， 类别数多时，计算量大大增加，而且效果也不如K均值聚类算法。

本文所改进的算法思路是，如果在K均值聚类算法初始化时，所选择的初始聚类中心与样本数据集本身的分布相一致，就相对容易得到最优化的聚类结果。

设X 是数据样本集，可以如下方式得到初始的聚类中心。首先计算数据集X中任意两个数据点之间的距离。其次找到其中距离最短的两个数据点，把这两个数据点放到集合Ai中，并把这两个数据点从X中删除。第三步计算Ai中的每一数据点与X中的每一数据点的距离，找到与Ai距离最近的数据点，把它从X中删除，加到Ai中。重复第三步直到Ai中的数据点数目达到一个设定的阈值。然后回到第二步组成另一个数据集。如此重复，直到组成K个数据集。最后分别计算这K个数据集的均值，就是所要找的初始聚类中心。

假设，数据集X中包含n个数据点，我们要将它们分成K个聚类，改进后的算法步骤如下：

（1）令i=1，计算X中任两个数据点间的距离，找到距离最短的两个数据点，把它们放入Ai（1<=i<=k）中，并把它们从X中删除；

（2）在X找到与Ai中数据点最近的点，把它加到Ai中，并从X中删除；

（3）重复（2），直到Ai中的数据点的数量达到一个设定的阈值T；

（4）如果i

（5）对第一个Ai（1<=i<=k）计算其均值，得到每个数据集的中心点，这些点就是我们要找的初始聚类中心；

（6）从步骤（2）开始执行传统K均值聚类算法。

4 实验结果与分析

为验证算法的有效性，我们使用了公共数据库中的几段测试视频进行了测试实验，实验的环境为Intel Core i3 2.4GHz CPU，4G内存，Windows7操作系统。编程环境为VS2010，Opencv2.7。

在背景减除法中，被检测图像每个像素的分类有四种：真阳性（TP），即前景像素被正确分类；假阳性（FP），即背景像素错分类为前景像素；真阴性（TN），即背景像素被正确分类；假阴性（FN），即前景像素被错分类为背景像素。

在前景检测完成后，根据每个像素的分类结果，我们可以用灵敏度，精确度，相似度等对算法进行评估，它们的公式如下：

在实验中我们对本文方法与其他的背景建模方法的效果进行了比较。图1为对公开数据库中Waving trees序列图像第247帧的背景模型和前景检测结果，表1是本文方法与其他两种背景建模方法的比较结果。图2为对公开数据库中Fountain序列图像第440帧的背景模型和前景检测结果，表2是本文方法与其他两种背景建模方法的比较结果。

以上图、表显示，本文的背景建模方法取得了较好的效果，在灵敏度、精确度、相似度等多个指标上都较另两种方法有所提高。在动态的环境下，具有较好的鲁棒性和有效性。

5 结论

本文提出了一种基于聚类的改进的背景建模方法，针对传统K均值聚类算法容易陷入局部最优解等的缺点，提出了改进的算法，在进行K均值聚类算法之前先对数据点进行预处理。实验结果显示本文方法取得了较好的检测效果，对动态、复杂场景下的背景提取和前景检测是有效的。

参考文献：

[1] Stauffer C， Grimson E. Adaptive background mixture models for real-time tracking.IEEE Conference on Computer Vision and Pattern Recognition， CVPR 1999，pages 246–252， 1999.

[2] Kim H， Sakamoto R， Kitahara I， et al. Robust foreground extraction technique using Gaussian family model and multiple thresholds. Asian Conference on Computer Vision， ACCV 2007， pages 758–768， November 2007.

[3] Karmann K， Von Brand A. Moving object recognition using an adaptive background memory. Time-Varying Image Processing and Moving Object Recognition， Elsevier， 1990.

[4] Butler D， Bove D， Shridharan S. Real time adaptive foreground/background segmentation. EURASIP， pages ， 2005：2292-2304.

[5] 王敞，陈增强.基于遗传算法的K-均值聚类分析[J].计算机科学，2003，30（2）：163-164.

[6] Klare B， Sarkar S.Background subtraction in varying illuminations using an ensemble based on an enlarged feature set[C].in IEEE Comput. Soc. Conf. on Comput. Vision and Pattern Recognit. Workshops，2009.