BGS-KDE算法：读”Non-parametric Model for Background Subtraction“

本文是ECCV 2000年的文章，"Non-parametric Model for Background Subtraction"，作者是Ahmed Elgammal，Rutgers大学副教授（这个大学好似没听过，查了一下排名在150名左右），他的主页在这里，专注于人的行为分析、跟踪等。他这篇文章可以找得到，还有一个在线版在这里。

这篇文章是2000年的，十年前的文章，也是第一个提出使用KDE方法的。所谓KDE方法是指：Kernel Denity Estimation,即使用核函数来估计概率。核心思想就是根据最近N帧图像，建立N个样本作为背景Kernel模型，在检测的时候，使用相应的kernel函数来估计当前像素值出现的概率，如果大于某一个门限，即为背景。

KDE算法是一个General的方法，如果把所有的Kernel函数取为高斯函数，则KDE函数就退化为generalized的混合高斯模型，这里每一个样本就是一个高斯模型。

值得注意的是：整个KDE算法是基于这样的假设，背景是变化很频繁的，不足以用几个高斯模型来表示，但是在很短的时间间隔内，还是符合一定的分布的，也就是本文所谓的local-in-time，例如高斯模型。

1. 基本背景模型

概率密度估计：Density Estimation

KDE方法也是基于像素的，以下描述都是对于每个像素的。设 x1, x2, x3,....xN是像素的最近N个样本，使用这些样本值，来当前像素点的概率密度函数如：

                           Pr(xt)=[K(xt-x1)+K(xt-x2)+ ... +K(xt-xN)]/N  (1) 

其中，K表示Kernel函数，xt表示像素在时刻t的值。如果Pr(xt)<T,这里T是一个全局门限，说明可以概率小，可以判定为前景，反之为背景。

这里，如果K为高斯函数，就很像混合高斯模型了。而且Pr(xt)公式可以使用查找表方法计算，可以极大提高运算速度。相比与混合高斯模型，因为KDE算法只是依赖于最近的N个样本，很容易“forget”以前的状况，所以可以灵活控制其精确度。

核函数宽度估计：Kernel Width Estimation(我把它称为高斯函数的标准差估计) 

      如果使用高斯函数上面的公式1就可以更加具体化，把高斯函数代入公式1，具体公式见原文，公式中有一个关键参数--高斯分布的标准差，此参数反映了当前像素的变化剧烈情况，可以通过如下方式来估计此参数：对每个颜色通道，N个连续的样本，相邻的两个值的差值|xi - x(i+1)|，在这些连续的(xi, x(i+1) )对中，求得中值m。此中值m与标准差有直接对应关系：
                    delta = m/(0.68*1.414)
        è¿™é‡Œä¸ºä»€ä¹ˆä½¿ç”¨è¿™æ ·ä¸­å€¼æ¥ä¼°è®¡æ ‡å‡†å·®å‘¢ï¼Ÿè¿™æ˜¯å› ä¸ºåœ¨N个样本中，连续的两个值 (xi, x(i+1) )很大可能是属于同一个local-in-time的高斯分布。这样的估计是有效的。

2. 抑制误检(False Detection)

本文把误检来源分为两种，一种是噪声，一种是背景的轻微运动，例如树枝晃动、水面等。第一种物件由于是全局散落的，可以通过滤波或者形态学的方法滤除，后一种由于有空间的聚集特性，很难用传统的滤波方法消除。

分析一下第二种误检的来源，就可以知道，虽然在当前像素点的KDE中不能匹配上，因为这个像素点很可能是在领域中移动过来的，所以这里就可以在当前像素点的一个领域中寻找最佳的匹配，还是使用前面的概率估计公式，在领域中寻找最佳的匹配，即概率的最大值。
             Pn(xt)=max{Pr(xt| By)},
其中By表示xt的领域像素点。若Pn(xt)大于某个门限th1，则确定为背景。

通过上述方法，虽然能去掉一些误检，但是，同时会把一些真实的前景给去掉。考虑到真实的前景有这样的有这样的特点，整个被检测出来的前景一定是在从附近的某个地方移动到这里来的，而不是几个像素点。这里定义一个概率Pc，表示整个被检测出来的连续区域是从附近移动过来的概率。定义如下：
            Pc = Pn(xi)的乘积
其中，xi是被检测出来的连续的区域内的像素。对于一个真实的前景目标，整个被检测出来的连续区域，对于上面的公式的计算结果应该是很小的。

所以综合上面的两个方面，如果一个像素点同时满足Pn>th1和Pc>th2，则表示这是一个误检，重新说一下，应该是第二种误检。

3. 背景更新

背景更新的策略有两种：

1. 选择性更新：即只是把新的样本(sample)添加到那些被判定为背景的像素点模型
2. 盲目更新：即把新的样本添加到任何像素点模型

这两个方法各有弊端，例如第一种方法很依赖与判定的结果是不是正确，如果错了，就会一错再错。第二种方法比较盲目，会把静止前景或者运动很慢的前景融入到背景模型中。本文提出了一个结合两个更新策略的方法，使既能很快的适用新的背景改变，又能对前景，又能足够精确的检测出前景，使用两个model来达到这个目的：Short-term mdel 和 Long-term model：

Short-term model: 这是一个最近(very recent)场景N个样本模型，此模型对场景的变化适应很快，而且对前景检测很敏感。使用选择性策略更新背景模型；

Long-term model: 这个模型保存相对稳定的背景模型，而且改变非常的缓慢。这个模型也包含N个样本，但是此N个样本的所取自的时间窗口比short-term model要宽很多。这个模型使用盲目更新策略更新。

这两个模型检测结果的交集，可以消除短期模型的持续错误前景(false positive)，也可消除长期模型结果中的误检。这里也会造成一个问题，就是同时消除了一些正确的前景，例如在短期的模型中检测出来的静止前景。本文的解决方法是，在短期模型中检测出来的前景，如果与前面的合并结果相邻的话，就判定为最后的前景。（这种解决方法，我有待考察，我并不明白为什么这样处理就可以解决此问题）

4. 阴影检测

阴影检测是背景差分中的难点之一，阴影的特点就是颜色相似，而亮度变低。本文使用了色度坐标(Chromaticity Coordinate)来运算，r=R/(R+G+B), g=G/(R+G+B), b=B/(R+G+B)，其中r+g+b=1，所以一个像素的色度坐标就可以表示为(r, g)二元组。这个二元组，只是记录了色度信息，完全丢失了亮度信息，可能会造成很多的漏检。这里就另外引入一个亮度信息s=R+G+B，所以同样用一个三元组<r, g, s>来表示一个像素，这里色度和亮度信息就完全区分开来了。如果满足色度r,g分量相近，而a<st/sb<1的话，就可能判定为阴影。

在本文中，还是使用KDE的方法如下：使用前面的KDE的方法，设A={x1, x2,...,xn}为一像素的样本，xt为当前像素值，在集合A中选取alpha<(xt/xi)<betaçš„xi组成集合B，对B集合中的元素xi使用二维的(r, g)做KDE运算。这里集合B就称为与当前像素“相关的”背景样æœ
¬ï¼Œè¿™æ ·æœ‰åˆ©äºŽæé«˜è¿ç®—效率。

总结：

本文是KDE算法的开山之作，提到的和想努力解决的问题也很多。本文的KDE模型是核心，如第1小节中描述的；误检抑制，通过领域内的方法，抑制背景的小运动误差，如第2小节中的描述；长短期背景模型，企图解决背景更新快慢的问题，如第3小节所示；使用色度加亮度坐标，企图解决阴影的问题，如第4小节所示。这些方法都是值得学习的。本文方法的实时性，文中说是在400MHz的奔腾CPU，处理320x240的图片能达到15-20 fps，这样的速度可观的，有机会要实现一下本算法。