基于改进K均值的运动目标检测算法研究

柯尊海 刘 勇 徐义春 雷帮军

（三峡大学 智能视觉与图像信息研究所，湖北 宜昌 443002）

前景提取是计算机视觉应用的重要环节，是目标跟踪、目标识别、场景分析与理解等高级处理的基础，在行人检测与跟踪、智能交通、社会安防等领域得到了高度的重视.如何针对当前的场景建立一个尽可能完善的背景模型，并进行前景信息的提取是计算机视觉领域的研究热点和难点.

近年来，国内外大量学者对其进行了深入的研究，并取得了大量的成果.目前，背景建模算法已有十几种，如Kim等提出的Codebook背景建模算法，许雪梅等在Kim的基础上提出了局部更新的分层码本目标检测算法［1－2］，P.KadewTraKuPong等人提出的高斯混合模型背景建模算法，黄鑫娟等在其基础上提出了自适应混合高斯背景模型的运动目标检测方法［3－5］等，背景建模算法的综述性论文也频频见刊［6－8］.除此以外，新的背景建模算法也不断地被提出，如Hanzi Wang和David Suter提出的SACON算法［9］、Olivier Barnich和 Marc Van Droogenbroeck提出的 VIBE算法［10］以及Lucia Maddalena和 Al－fredo Petrosino提出的SOBS自组织背景建模方法［11］等.K均值聚类算法是一种基于样本间某种距离或相似性来定义的一种间接聚类方法，由于实际场景是动态变化（如摇曳的树叶等），能够很好地用K均值聚类来分析，因此K均值聚类算法在目标检测中的研究引起了一些学者的注意.杨会锋，曹洁等人提出了一种基于改进K－均值聚类的背景建模方法，通过比较任意样本与像素位置处子类中心的距离，对各个像素的观察值进行聚类.经过一段时间的学习，样本数最多的就构成了背景模型，但是对于背景模型的更新没有进一步的深入研究［12］.查成东等人也提出了一种基于改进K－均值聚类算法的背景提取方法，并且对每个像素用3个动态的元组进行建模，实现原始背景的提取.但是该算法固定了K＝3，而且只是针对单通道灰度视频序列进行建模，不能很好地对实际场景进行建模［13］.张运楚等人提出了一种基于C－均值聚类的视觉监控背景图像构建算法，选择样本点数量最大的类别的均值作为背景模型.该算法不能对动态场景进行处理，并且采用了一种在线更新的形式，内存消耗比较大［14］.Charoenpong T等人提出了一种采用混合高斯模型和K均值的自适应背景建模方法，将捕获的帧转换为单通道的灰度图像，并进行累加，通过K均值方法来确定高斯分布的聚类数目，然后将平滑聚类结果中最大的类作为背景模型.该算法只能处理单运动目标的场景，并且不能适应场景的动态变化［15］.

综上所述，尽管目前前景提取的算法有很多，并且对于某些特定的场合能取得比较好的结果，但是在一些实际应用中，这些算法却不尽人意，因此有必要进一步对其进行研究.本文在文献［14］的基础上，采用其K均值背景图像构建算法的思路，又进行了一些补充.主要补充的内容有：

4）本文的运动目标提取算法，可以根据阴影的特点，实现阴影、背景、前景的分离，使算法具有很大的通用性.

1 算 法

算法在HSV颜色空间，通过K均值聚类算法对视频流的前N帧每个像素样本进行聚类学习，K均值聚类的结果用来表示对应像素的背景模型.然后输入的视频流与背景模型进行比较，进行背景、可能前景和阴影的分离处理，引入TOM方法来消除鬼影现象，算法采用了一种选择性的背景更新策略来进行背景更新.

1.1 K均值聚类算法介绍

K均值聚类算法是一种基于样本间某种距离或相似性度量来定义的一种间接聚类方法，其基本思想是通过迭代寻找K个聚类的一种划分方案，使用这K个聚类的均值来代表相应各类样本时所得的总体误差最小［16］.

令y是待分类的数据样本集，Ni是第i类聚类Γi中样本的数目，mi是这些样本的均值，即

把Γi中的各样本y与均值mi间的误差平方和对所有类相加作为判别准则：

通过迭代，不断地调整样本的归属类使Je极小，Je极小的聚类Γ1，Γ2，…，Γk即待分类样本集y的最优划分.

K均值算法的步骤为：

1）初始划分k个聚类，Γi，i＝1，2，…，k，根据式（1）和式（2）计算mi（i＝1，…，k）和Je；

2）任取一个样本y，设y⊂Γi；

3）若Ni＝1，则转2），否则继续；

4）计算ρj

5）考察ρj中的最小者ρk，若ρk＜ρj，∀j，则把y从Γi移到Γk中；

6）重新计算mi（i＝1，…，k）和Je；

7）若连续N次迭代Je不改变（变化很小），则停止；否则转2）.

1.2 改进K均值背景建模

设｛f0，…，ft，…｝表示视频序列的帧，Xt＝（，）表示t时刻图像帧ft中的像素（x，y）的 HSV彩色向量，Kt表示在0～t之间像素（x，y）出现的灰度的类别数量，表示t时刻像素（x，y）灰度值的第k个类别中样本数量，表示像素（x，y）在时刻t第k个聚类的灰度均值.

文中采用了K均值聚类的思想，对文献［14］的建模算法做了些修改，修改后的K均值背景建模算法描述如下：

1）初始化t＝0，令C0＝1＝1＝X0；

2）在时刻t，将图像帧ft中的每一个像素Xt＝（）根据灰度值大小对其进行分类.对于第k（k≤Kt－1）类别，分类准则如下：

那么对第k个聚类，对相关变量做如下更新：

如果不满足式（5），即该像素不属于任何已有的类别，那么则将其归为一个新的类别：

3）对于每一个像素进行像素值与聚类处理后，选择聚类类别的均值向量为该像素的背景模型，即

从式（9）可以看出，修改后的K均值聚类算法建立的背景模型是一种混合模型，对于比较稳定的场景中的像素位置，在聚类的时候将形成一个稳定的类别，该类别的均值就为该像素的背景模型；而对于具有动态变化的场景，则可能形成多个聚类类别，将聚类形成的多类别的多个均值作为该像素的背景模型，这样建立起来的背景模型相对于文献［14］具有更强的环境适应性，可以较好地适应动态场景的变化.

1.3 像素分类

对于每一个新来的像素，其可能为背景、前景、阴影或者其他成分.根据HSV颜色空间的特点，本文引入色度差和亮度差的表达形式：

这里τ≥ξ，这样就能在背景建模阶段，将背景像素尽可能地聚类在合理的类别中，ξ越小，聚类的类别数愈少，反之越多.

按照高光和阴影的颜色表现原理，如果当前像素与背景像素的色度变化比较多，则认为有目标进入，判为前景像素；当色度变化不大，而亮度比背景要低得多时，则判为阴影像素；当像素变化不大，而亮度比背景要大很多时，则判为高光像素.根据以上描述，则有如下像素所属类别判断准则：

其中，M（i）表示掩膜图像，F、B、S、H 分别表示前景、背景、阴影和高光，τt，τv1，τv2是表示当前像素与对应背景模型中的色度和亮度相似度.如果只关心前景，则上式可以简化为

1.4 背景更新

本文采用一种全新选择性机制来进行背景模型的更新，对于判为背景像素的点，按式（13）进行背景更新：

1.5 鬼影消除

鬼影也称为虚背景，它的产生有两种情况，一种情况是背景物体的移出，即背景中停止的物体，运动移出了背景区域，导致在检测时出现永久不动的前景；另一种情况是运动物体的移入，即运动的目标进入检测区域后，停止在场景中，导致检测时出现虚假前景.本文引入文献中介绍的TOM（Time Out Map）方法来消除鬼影的影响，TOMt（pt）表示t时刻像素pt的TOM值，其表示如下：

其中Bt（pt）＝1表示为前景，如果 TOMt（pt）大于某一阈值，则将该像素判为鬼影，采用背景更新机制将其融入到背景模型中.

2 实验与分析

实验是在Intel Quad CPU Q9500硬件平台、以及Visual C＋＋6.0结合opencv1.0库下进行的.在本文提出的算法中主要有两个参数ξ和τ，分别表示学习时像素间色度差的度量和前景检测时色度差的度量，不同的场景的取值有一定的差异.在本文通过多次试验得出ξ＝24.0，τ＝32.0可以取得较好的检测结果，另外，算法学习帧数N＝300.

1）实验1：该视频序列是公路上对行驶汽车进行监控的一段视频runningcar.avi，该视频序列伴随有光照的变换，并且视频序列的一开始就有汽车在行驶.实验结果如图1所示.

2）实验2：该实验是在一栋教学楼大门前采集的一段视频buildingperson.avi，视频序列伴随有光照的变化以及轻微的阴影，且视频在一开始就有大量的行人来来往往.

图3 视频源帧

图4 检测的前景

通过实验1和实验2可以看到，本文提出的算法能够较精确地提取出运动目标的信息，并且对光照的变化具有一定的鲁棒性.另外，这两个实验都是在一开始有运动目标的场景中进行的，视频能够较好地对初始有运动目标的场景进行处理，消除由于场景中运动目标的移入移出形成的虚背景.

3 结 论

本文分析了背景建模的相关技术，并针对其中的不足，提出了基于改进K均值运动目标检测算法.该算法引入修正的K均值聚类算法对视频序列进行学习并建立背景模型，并提出了一种像素相关的选择性背景更新机制.经过多个实验验证，表明该算法是有效的，并能够较为准确地提取出运动目标的信息，对光照具有较强的鲁棒性，并且能够较好地处理由于目标在场景中移入移出形成的虚背景.但算法也存在一些不足，针对黑色或白色的运动目标可能会出现漏检的现象，将在后续工作中进行深入研究.

［1］ Kim K，Chalidabhongse T H，Hardwood D，et al.Real－time Foreground－background Segmentation Using Codebook model［J］.Real－Time Imaging，2005，11（3）：172－185.

［2］ 许雪梅，墨 芹，倪 兰，等.基于局部更新的分层码本目标检测算法［J］.计算机应用，2011，31（12）：3399－3402.

［3］ P.Kadew Tra Ku Pong，R.Bowden.An Improved A－daptive Background Mixture Model for Real－time Tracking with Shadow Detection［C］.2001proc.2nd European Workshop on Advanced Video－Based Surveillance Systems，2001：149－158.

［4］ 黄鑫娟，周洁敏，刘伯扬.自适应混合高斯背景模型的运动目标检测方法［J］.计算机应用，2010，30（1）：71－74.

［5］ 谢勤岚，李圆双，喻 该.基于高速球形摄像机的运动目标检测与实时跟踪系统［J］.中南民族大学学报：自然科学版，2010，29（2）：82－83，112.

［6］ Brutzer S，Hoferlin B，Heidemann G.Evaluation of Background Subtraction Techniques for Video Surveillance［C］.2011IEEE conference on Computer vision and pattern recognition，2011：1937－1944.

［7］ Benezeth Y，Jodoin PM，Emile B，et al.Review and E－valuation of Commonly－implemented Background Subtraction Algorithm－ms［C］.19th International Conference on Pattern Recognition，2008：1－4.

［8］ Juan C，SanMiguel，Jose＇M，et al.On the Evaluation of Background Subtraction Algorithms Without Groundtruth［C］.2010Seventh IEEE International Conference on Advanced Video and Signal Based Surveillance，2010：180－187.

［9］ Hanzi Wang，David Suter.Background Subtraction Based on a Robust Consensus Method［C］.Proceedings of the 18th International Conference on Pattern Recognition，2006：223－236.

［10］Olivier Barnich，Marc Van Droogenbroeck.VIBE：A Powerful Random Technique to Estimate the Background in Video Sequences［C］.International Conference on Acoustics，Speech and Signal Processing，2009：945－948.

［11］Lucia Maddalena，Alfredo Petrosino.A Self－organizing Approach to Background Subtraction for Visual Surveillance Applications［J］.IEEE Transactions on Image Processing，2008，17（7）：1168－1177.

［12］杨会锋，曹 洁，帅立国.基于改进K－均值聚类算法的背景建模方法［J］.电子测量与仪器学报，2010，24（12）：1114－1118.

［13］查成东，王长松，巩宪锋，等.基于改进K－均值聚类算法的背景提取方法［J］.计算机工程与设计，2007，28（21）：5141－5143.

［14］张运楚，梁自泽，李 恩，等.基于C－均值聚类的视频监控背景图像构建算法［J］.计算机工程与应用，2006：45－47.

［15］Charoenpong T，Supasuteekul A，Nuthong C.Adaptive Background Modeling from an Image Sequence by Using K－Means Clustering［C］.2010International Conference on ECTI－COM，2010：880－883.

［16］张学工.模式识别［M］.3版.北京：清华大学出版社，2010，192：195.