最大类间方差法(Otsu法)

此方法的目的是把一幅图像，通过一个阈值T的方法，分割成前景和背景两部分。通过选定阈值T，是图像的前景部分和背景部分的差别最大。

其中，前景和背景的差别的衡量标准为如下表达式：g=wf*(uf-u)^2+wb*(ub-u)^2=wf*wb*(uf-ub)^2，其中wf和wb分别为前景和背景所占的比例，uf和ub为前景和背景的平均灰度。Otsu方法，就是寻找一个阈值T，把图像分割前前后景两部分，使前面的公式中g取得最大值。

计算阈值T的算法如下：首先统计一下图像的直方图，或者这里可以在做一下直方图平滑，然后设置T=0到最大值，逐次搜索每个值，得到一个最大的g的阈值T。

类间方差法对噪声和目标大小十分敏感，它仅对类间反差为单峰的图像产生较好的分割效果。当目标与背景的大小比例悬殊时，类间方差准则函数可能呈现双峰或者多峰，此时类间方差法效果就不太适用了。

读“W4: Real-Time Surveillance of People and Their Activites”

本文是PAMI 2000年的文章，解决的问题是实时的监控视频的多人的检测、跟踪以及检测他们的行为，所谓W4就是：where, when, what and who。本文是对于静止的单目的灰度摄像机或者红外摄像机获得的数据进行处理。W4结合形状分析和跟踪来定位人和人的各个部分(包括头，手，脚，躯干)。本文说能够处理320x240达到25 fps (400MHz dual-Pentium II PC)。

本文涉及到背景差分、跟踪和行为检测等多个方面，我这里只是关注背景差分部分。背景模型在整体上来说是一个在训练阶段建立起来的统计模型，每个像素用三个值表示：最小值m(x), 最大值n(x), 连续帧的之间的最大差分值d(x)。

1. 学习初始化背景模型

这个使用两个阶段来排除学习阶段的中场景中的运动像素。第一个阶段是使用针对像素的中值滤波器，在时间上对一段数秒的视频进行滤波来区分运动和静止像素。第二个阶段是利用第一阶段得到的静止像素点建立初始化背景模型，具体操作如下:设V为连续的N个图像的集合，delta(x)和lamda(x)分别表示像素点x的标准差和中值，其中m(x)=min{Vz(x)}, n(x)=max{Vz(x)}, d(x)=max{|Vz(x)-Vz-1(x)|},其中|Vz(x)-lamda(x)| < 2*delta(x), 这样Vz(x)就是表示是静止的像素点。

2. 更新背景模型参数 

W4是基于灰度值的背景模型，光照的变化会明显影响检测，另外长期静止的前景可能会造成误检。本文使用两种背景更新方法：

基于像素的更新：周期的更新背景模型来适应光照的变化；
基于对象的跟新：更新背景来适应场景的物理改变，例如，场景中出现或者移除物体，车辆停靠等。

W4使用如下的方法来更新背景：在跟踪过程中，W4动态建立change map来决定使用何种更新方式，其中change map含有如下三个主要的元素：

• detection support map (gS): 代表在前N帧内被分类为背景的次数, 若x是背景像素gS(x,t)=gS(x, t-1)+1;
• motion support map (mS): 代表当前像素是运动像素的次数，判断一个像素是否为运动像素点方法是：连续三帧之差，都大于2*delta;
• change history map (hS): 代表自从上次被分类为前景的消耗的时间，如果是前景，则hS(x, t)=255, 否则hS(x, t)=hS(x, t-1)-255/N。

W4使用gS来决定背景哪些部分使用基于像素的更新，ms、gS和hS来决定哪些部分使用基于对象的更新。当背景模型被根性后这个change map就被重置为0。在跟踪的过程中，背景模型对前景像素和背景像素分别进行运算，背景模型的更新策略如下：

1. 若gS(x)>K*N，则使用基于像素的背景更新策略，设置为[mb(x), nb(x), db(x)]，即背景点;
2. 若gS(x)<K*N且mS(x)<r*N，则使用基于对象目标的更新，设置为[mf(x), nf(x), df(x)]，即前景点;
3. 如果上面都不符合，就保持原样。

3. 前景检测

首先，每个像素使用如下的方法来把每个像素点分类成前景或者背景：若当前像素点It(x)，满足|It(x)-m(x)|<k*du或者|It(x)-n(x)|<k*du，则判定为背景，其中du为整个图像的d(x)的中值。

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，这样的速度可观的，有机会要实现一下本算法。

读“Real-time Background Subtraction in C++”

这篇文章的作者Haotian Wu, Yifan Yu，在Boston大学的技术报告，忘记这篇文章是在哪里下来的了，不知道是否出自什么会议，或者是一个学习总结类型的文章，不过附有源代码，所以认真看了一下。

本文的重点是想实现实时的背景差分，在算法的效率方面的讨论比较多，这不是我所关注的地方，但是他在这篇文章中提到的背景差分模型还是值得借鉴的。

1  单高斯模型 
对每个像素点建立一个高斯模型，是最简单的背景差分模型，此算法的效率很高，运行速度非常快，但是差分效果不太好。

2 Kernel Density Estimation 核密度估计
此方法的核心使用使用统计的方法，估计最近n帧的图像中的像素值，来确定当前像素点是否是前景。

把最近的n帧或者按照一定规律取n帧存入缓存（Buffer）中作为核 (未完成)