基于最优k均值聚类的时空动态背景模型

舒浩浩,陈盛双,李石君

1(武汉理工大学 理学院,武汉 430070) 2(武汉大学 计算机学院,武汉 430072)

1 引 言

运动目标检测是智能视频监控系统对目标进行跟踪的基础,它的主要任务是从视频图像序列中将运动目标从背景中分离出来,如何有效地从视频中检测出运动目标长期以来都是研究的热点.

相较于光流法[1]和帧差法[2],基于背景建模的背景减除法往往在真实视频数据集中表现得更好,它对运动目标检测更加有效,并且适应性更强.背景减除法的主要思想是利用不包含运动目标的视频帧来建立初始背景模型,然后通过计算当前帧和背景模型之间的差异来检测运动目标,并对背景模型进行实时更新.背景模型的好坏决定了背景减除法对运动目标检测效果的好坏.

根据运动目标所在场景和监控器之间的相对关系,背景可以分为静态背景和动态背景.在静态背景中,背景基本上保持不变,不会随时间发生变化,而在动态背景中,背景一直处于动态变化之中,如喷泉、摇动的树叶、翻滚的水面[3].对动态背景进行建模一直以来都是背景减除法的一个挑战,它不同于静态背景,如果用静态背景模型对运动目标进行检测,会造成对动态背景的大量误检,因此,有效地对动态背景进行建模至关重要.

本文提出了基于最优k均值聚类的时空动态背景模型,考虑了同一个像素点在前个视频帧中不同时刻下的相邻像素点的信息,从时域和空域上对背景进行建模,并用最优k值间接反映出动态背景运动的快慢,同时将最优k值用于背景更新,从而使得背景更新更符合真实背景的变化.

2 相关工作

在过去的几十年中,研究者们已经提出了大量的背景模型来检测视频流中的前景运动目标.背景模型可以分为参数模型和非参数模型,参数模型为统计模型,通常假设背景满足某个分布,然后对该分布中的参数进行求解,而非参数模型则是收集背景数据来构建背景模型.

最常用的参数模型是高斯混合模型[4].[5]假设每个像素点的像素值分布由3到5个单高斯模型组成,根据新输入的视频帧对模型中的参数---均值和方差进行实时更新.[6]和[7]随后对高斯混合模型进行了改进,使其具有更好的鲁棒性和更高的效率.

非参数模型则种类较多,一般是利用每个像素的前几帧像素值序列或相邻像素值集合来对背景进行建模.[8]提出了码本算法,将每个像素点的像素值聚类到对应的码本集中,但它只考虑了时间信息,当为动态背景进行建模时,效果并不理想.[9]和[10]便利用空间信息提出了ViBe算法,随机抽取第一个视频帧中每个像素点的相邻像素来建立初始背景模型,ViBe算法对于动态背景有着较好的鲁棒性,其检测效果超过了码本算法和高斯混合模型.为了进一步改善ViBe算法,Hofmann提出了一种自适应方案[11],根据算法之前的决策自动调整决策阈值,随后,孙涵[12]、张磊[13]等针对运动目标检测中的阴影问题对Vibe算法进行了改进.文献[14]则利用纹理特征来对背景进行建模,采用局部二值模式(LBP)来区分纹理特征,根据部分重叠的背景区域构建LBP直方图.文献[15]则将局部特征方法和统计模型结合,提出了一个时空背景模型,该模型可以很好地解决光照和动态背景建模问题.通过采集不同尺度下的的相邻像素的历史像素值,文献[16]提出了多尺度时空背景模型,使得模型能够对动态背景有更好的鲁棒性.而文献[17]对传统的RPCA进行改进,提出了TVRPCA,使得RPCA能用于动态背景建模.文献[18]则基于两个相似的自组织映射提出了AAPSA,对不同的视频均有很高的适应性.

3 轮廓系数

k均值聚类算法根据数据点间的距离,将数据x1,x2,…,xn划分成k个类C1,C2,…,Ck,其聚类结果取决于聚类数k,不同的k值可以得到不同的聚类结果,但是在对数据先验知识不足的情况下,无法确定哪种聚类结果最符合当前数据的分布.

轮廓系数是聚类效果好坏的一种评价方式[21].它结合内聚度和分离度两种因素,可以对相同原始数据上的不同聚类结果进行评价.

定义1.类内内聚度.设xi最终聚类到聚类簇C1,则称xi到C1中其他所有数据点的平均距离a(i)为xi的类内内聚度.

定义2.类间分离度.设xi最终聚类到聚类簇C1,xi到其他某个聚类簇Cm中所有数据点的平均距离为bim,则称b(i)=min{bi2,bi3,…,bik}为xi的类间分离度.

定义3.样本数据的轮廓系数.若xi的类内内聚度为a(i),类间分离度为b(i),则xi的轮廓系数为

(1)

4 基于最优k均值聚类的时空背景模型

复杂场景下的动态背景建模是运动目标检测面临的挑战之一,由于背景的无规则运动,很难找到一种通用的背景模型使其可以对不同的复杂动态背景进行建模.虽然同一个背景像素点在不同的视频帧下的像素值一直在发生变化,但是其与相邻像素点相似这一特性却一直保留,在不受噪声影响的情况下,同一帧中的像素点与其周围部分像素点的像素值比较接近,若建立相邻像素点的像素值分布,则该像素点可以由该分布产生.该像素点的相邻像素点在不同帧下的像素值分布可能不同,不过当背景运动幅度不大时,这些分布的个数是有限的,不会随着时间而一直增加.考虑到相邻像素点的这些性质,本文提出了基于最优k均值聚类的时空背景模型.首先对多帧相邻像素点的像素值进行聚类,并用轮廓系数找到最佳聚类数,从而得到每个像素点的相邻像素点在时域和空域下的总分布个数,然后对每个分布进行估计,得到初始背景模型,最后根据最新视频帧对背景模型进行更新.

4.1 初始背景模型的建立

4.1.1 图像数据的增强

视频帧中的背景主要分为静态背景和动态背景,静态背景不随时间发生变化,其在RGB颜色空间下的像素值基本不变,而动态背景的像素值则随着时间发生改变.由于硬件因素或者周围环境的影响,监控器采集到的视频图像存在一定的噪声,这些噪声在时间域上可能分布不均,会使得静态背景在某相邻两时刻的像素值突然变化较大,造成该时刻对静态背景的误检,而动态背景由于像素值一直在变化,对该类噪声不太敏感.为了增强模型对该类噪声的鲁棒性,本文对每个视频帧中的每个像素都添加同一个高斯噪声,使得静态背景也处于动态变化之中,防止静态背景像素值的突然变化对背景模型带来影响.若像素点xi在第t帧中的RGB空间下的像素值为(Rt(xi),Gt(xi),Bt(xi)),则增强后的像素值为:

It(xi)=(Rt(xi),Gt(xi),Bt(xi))+N(Ο,Σ2)

(2)

其中N(Ο,Σ2)是均值为0,方差为Σ2=σ2I的高斯分布.

为了使像素值能反映更多的信息,本文进一步将RGB空间加强后的像素值映射到HSI空间,使得每个像素点的像素值不仅可以反映出色彩信息,还可以反映出该像素点处的灰度信息,本文之后提及的像素值均为HSI颜色空间下的像素值.

4.1.2 背景像素的选取

对于像素点xi,本文从视频的前N1个视频帧中分别随机选取m个相邻像素点的像素值来组成xi的背景像素值,图1是以xi为中心的一个5×5的区域,本文将以xi为中心的十字形区域包含的像素点P1,P2,…,P8作为xi的相邻像素点,则1≤m≤8,

图1 以xi为中心的5×5区域Fig.1 A 5×5 area centered on xi

若第t帧中选取的背景像素值记为:

(3)

则xi的背景像素集为:

B(xi) =B1(xi)∪…∪BN1(xi)

(4)

每一个像素点最终都能得到一个模为N1×m的像素值集合,该集合包含了该像素点周围像素点的空间信息以及前N1个视频帧的时间信息.

4.1.3 最优k值的确定

为了得到像素点的像素值的分布,本文对每个背景像素集首先采用k均值聚类进行分析.对于给定的k值,最终都能根据公式(5)得到xi的背景像素集的k个聚类中心c1(xi),c2(xi),…,ck(xi),以及对应的k个聚类簇C1,C2,…,Ck,

(c1(xi),…,ck(xi))=

(5)

(6)

其中,ak(I(xi))是像素值I(xi)的第k个聚类结果的类内内聚度,bk(I(xi))是I(xi)的第k个聚类结果的类间分离度.

(7)

不同的像素点最终得到的最优k值也不一定相同,最优k值kb(xi)反映了像素点xi在前N1帧中的像素值分布的个数,其值越大,说明xi越有可能是动态背景像素点,并且该像素点处的背景变化也越快,因此在之后的背景更新时,该处的更新速率也应该越快.

4.1.4 初始背景模型

若k=kb(xi)时,B(xi)的最终聚类结果为Cj(xi)(j=1,…,kb(xi)),假设每个聚类簇的分布都是以聚类中心为球心的球形区域,则越接近球心,属于该分布的概率越大,因此对每一个聚类簇都能建立一个基于距离的概率分布.

对于聚类簇Cj(xi),若其聚类中心为cj(xi),假设该簇中元素到聚类中心的距离服从高斯分布,即像素值I属于聚类簇Cj(xi)的概率为:

(8)

为了得到聚类簇的均值和方差,本文采用极大似然估计的方法对其进行求解,用该聚类簇中的所有元素到聚类中心的距离来对均值和方差进行估计,即求解问题(9)

(9)

最终可以得到

(10)

(11)

对于每一个聚类簇最终都可以得到该簇的一个高斯分布,这些高斯分布相互独立,联合这些高斯分布,最后可以得到初始概率背景模型,即像素值I属于B(xi)的概率为:

(12)

其中wj满足以下方程

(13)

4.2 运动目标的分割

初始概率背景模型能计算出像素值为背景像素的概率,概率越大,说明像素值为背景的可能性越大,而像素值到聚类中心的距离越小,其为背景像素值的可能性也越大,若用F(I(xi))=1表示xi为运动目标像素,则将两者结合得到最终的分割策略为:

(14)

其中T(xi)为概率阈值.当概率大于等于T(xi)或者I(xi)到其中一个聚类中心的距离小于其均值时,xi为背景像素,否则为运动目标像素.

由于在统计学中经常将μ±3.5σ视为正常数据的分布区域,同一分布的大部分数据都聚集在该区域,因此本文根据公式(15)确定阈值T(xi)的值.

(15)

4.3 背景模型的更新

4.3.1 参数更新速率以及更新率

最优k值kb(xi)可以直接反映像素点xi在前N1帧中的像素值分布的个数,其值越大说明xi的变化越频繁,而每个像素点的像素值在前N1帧中的取样个数相同,因此kb(xi)也可以间接反映出像素点xi处背景的变化速率,kb(xi)越大,说明xi处的背景变化越快,则在对背景更新时,该处的更新速率也应该越快.假设参数的更新速率与kb(xi)成正比,则xi处的背景更新速率可以表示为:

α(xi)=α1kb(xi)

(16)

其中α1是基本更新速率,其值的选取将在5.1中进行讨论.

为了提高模型的检测速度,本文采取ViBe算法中的时间取样更新策略,每次只对每帧图像中的部分像素进行更新,而不是所有像素同时更新,当一个像素点被判定为背景时,它有1/rate的概率更新背景模型,即在每个视频帧中背景像素的更新率为1/rate,平均每经过rate帧的时间会对所有像素更新一次.其中rate是时间采样因子,本文中其值取为50.

4.3.2 当前像素的背景模型的更新

(17)

(18)

(19)

4.3.3 相邻像素的背景模型的更新

当I(xi)为背景时,考虑到相邻像素的局部连续性,其值可以用来对相邻像素的背景模型进行更新.本文采取和ViBe算法中空间邻域更新策略类似的方法,从xi的所有相邻像素中随机选取一个像素y,用I(xi)对像素y的参数进行更新:

(20)

(21)

(22)

5 实验与结果分析

为了验证本文提出的背景模型对动态背景建模的有效性,本文在CDnet2014提供的动态背景数据集上进行实验.该数据集包含6个测试视频,分别为boats、canoe、fall、fountain01、fountain02、overpass,这6个视频的描述如表1所示.

本文共采用6个评价指标对实验结果进行评价与比较,这六个指标为Recall、Precision、F-Measure、FPR、FNR、PWC,其计算公式为:

(23)

其中TP为检测出的真实的运动目标像素个数,TN为检测出的真实的背景像素个数,FP为误检的运动目标像素个数,FN为误检的背景像素个数.检测效果越好,Recall、Precision、F-Measure的值越大,而FPR、FNR、PWC的值越小.

表1 数据集中的视频描述Table 1 Video description of data set

本文的实验平台为matlab2016a,实验环境为酷睿i5处理器,其频率为2.6GHz,RAM为8G.

5.1 参数的确定

本文需要确定的参数有(1)高斯噪声中的方差σ2(2)选取的视频帧数N1和相邻像素点个数m(3)基本更新速率α1.

本文在视频canoe上对参数的选取进行研究.首先确定N1和m的取值,令σ和α1保持不变,并令N1从5到25进行变化,m从2到5进行变化,计算每组(N1,m)所对应的F-Measure值,图2反映了σ=2,α1=0.01时,不同的(N1,m)的取值对检测效果的影响,从图2中可以看出F-Measure随N1和m的增加而增加,但增长速度越来越慢,当N1=25时,不同m取值下的F-Measure都很高,并且非常接近,由于最终样本数为N1×m,样本越多,在初始背景建模时耗费的时间也越多,考虑到检测精度和计算速度,本文最终令N1=25,m=2.

图2 σ=2,α1=0.01时,(N1,m)对F-Measure的影响Fig.2 F-Measure with different (N1,m) when σ=2,α1=0.01

接下来确定σ的取值,令α1,N1,m保持不变,σ的取值集合为{0,1,2,3,4,5,6,7,8,9,10},图3反映了N1=25,m=2,α1=0.01时,F-Measure和σ取值的关系,可以从图3中得到F-Measure随σ的增大先增大后减小,这说明适当的添加噪声对于提高检测精度是有效的,同时也说明4.1.1中对图像数据的增强是合理的,当σ=2时,F-Measure取得最大值,因此,本文最终令σ=2.

最后确定α1的取值,令N1=25,m=2,σ=2,并依次令α1等于0.0001,0.0005,0.001,0.005,0.01,0.05,0.1,0.15,0.2,0.25,则α1与F-Measure的关系如图4所示,当α1=0.05时,F-Measure取得最大值,因此,α1的最终取值为0.05.

图3 N1=25,m=2,α1=0.01时,σ值对F-Measure的影响Fig.3 F-Measure with different σ when N1=25,m=2,α1=0.01

5.2 实验结果及其与其他方法的比较

令σ2=4,N1=25,m=2,α1=0.05,利用本文提出的时空背景模型对数据集中的6个视频分别进行检测,对视频boats的第2000帧、canoe的第955帧、fall的第1892帧、fountai01的第1147帧、fountain02的第745帧、overpass的第2462帧的检测效果如图5所示,并将其与码本算法和ViBe算法的检测效果进行了比较.

从图5中可以看出,本文提出的时空背景模型在视频boats、canoe、fall、fountain02、overpass中检测到的运动目标的完整性要高于ViBe算法,对背景的误检率要低于码本算法,但是三种方法对视频fountain01的检测效果均不佳.

图4 N1=25,m=2,σ=2时,α1对F-Measure的影响Fig.4 F-Measure with different α1 when N1=25,m=2,σ=2

本文方法对每个视频中所有待检测帧的量化检测结果如表2所示,从表2中可以看出本文提出的时空背景模型对大部分视频检测得到的Precision值和Recall值都比较大,而Precision反映的是检测到的运动目标的完整程度,Precision越大,完整性越高,Recall值反映的是对背景的误检程度,Recall越大,误检率越低,因此本文方法对boats、canoe、fall、fountain02、overpass的检测结果完整性高、误检率低,这与图5中的结果是一致的.同时,图5中和表2都反映出本文对视频fountain01的检测效果很差,这主要是由fountain01中的喷泉无规则运动幅度太大引起的,而本文只考虑了5×5像素区域内的空间信息,导致模型无法对背景做出及时更新.

图5 检测结果及与其他方法的比较.(a)待检测帧原始图像.(b)待检测帧的真实运动目标图像.(c)ViBe算法的检测结果.(d)码本算法的检测结果.(e)本文方法的检测结果Fig.5 Comparison of the detection results.(a)the original frames to be detected.(b)the ground truth of the original frames.(c)the detection results of ViBe.(d)the detection results of Code Book.(e)the detection results of our method

为了进一步检验本文方法的有效性,本文与ViBe算法[10]、LOBSTER[19]、多尺度时空背景模型[16]、EFIC[20]、TVPRCA[17]、AAPSA[18]进行了量化比较,其中,LOBSTER和多尺度时空背景模型与本文方法比较类似,均为时空背景模型,EFIC是changedetection.net中的一个方法,TVPRCA是改进的PRCA,以实现对动态背景的建模,AAPSA是一个自适应的动态背景模型,每个方法对所有视频检测得到的六个量化指标的均值如表3所示,通过比较,可以得到本文提出的时空背景模型虽然Recall值和Precision值不是最高,但是F-Measure值却超过了其他方法,这说明本文方法在对背景的误检和运动目标的完整性检测的综合方面要优于其他方法,也说明本文提出的方法对于动态背景建模是有效可行的.

表2 本文方法对各视频检测的量化结果Table 2 Quantitative results of each video detection using our method

表3 本文方法与其他方法的量化结果比较Table 3 Comparison of the quantitative results of our method and other methods

6 结 论

本文提出的基于最优k均值聚类的时空背景模型利用最优k值反映出动态背景的真实变化速率,并将其用于背景更新,同时利用像素的时间和空间信息对背景进行建模,当动态背景运动幅度不大时,可以对背景成功进行建模,最终使得检测到的运动目标完整性较高,同时对背景有较低的误检率.不过该模型无法对大幅度运动的喷泉类背景进行很好地建模,在之后的工作会对模型进行改进,使之能适应这类动态背景.