背景提取算法——帧间差分法、背景差分法、ViBe背景提取算法 #23
Description
背景提取算法——帧间差分法、背景差分法、ViBe背景提取算法
注：本博文中的矩阵与公式不能正确显示，具体可以在本博文其他地址中查阅：
http://blog.csdn.net/ajianyingxiaoqinghan/article/details/72628402
背景提取是在视频图像序列中提取出背景，背景就是场景中静止不动的景物。因为摄像机不动，因此图像中的每个像素点都有一个对应的背景值，在一段时间内，这个背景值是比较固定的。背景提取的目标就是根据视频图像序列，找出图像中每一点的背景值。
背景提取有很多算法。针对静止摄像机的帧间差分法、高斯背景差分法、ViBe背景提取算法以及它的改进算法ViBe+，还有针对运动摄像机的光流法等。
本文针对静止摄像机的背景提取算法进行讲解，主要讲解帧间差分法、背景差分法，以及ViBe背景提取算法。
笔者已经将本文所有源码上传到笔者的GitHub账号上，地址如下：
https://github.com/upcAutoLang/BackgroundSplit-OpenCV
一. 帧间差分法
1. 算法原理
帧间差分法是将视频流中相邻两帧或相隔几帧图像的两幅图像像素值相减，并对相减后的图像进行阈值化来提取图像中的运动区域。
若相减两帧图像的帧数分别为第k帧, 第(k+1)帧，其帧图像分别为$ f_{k}(x, y) , f_{k+1}(x, y)$，差分图像二值化阈值为T，差分图像用D(x, y)表示，则帧间差分法的公式如下：
$$ D(x, y) = \left{\begin{matrix}1, |f_{k+1}(x,y) - f_{k}(x,y)|>T \ 0, others \end{matrix}\right. $$
帧间差分法的优缺点如下：
- 优点：算法简单，不易受环境光线影响
- 缺点：
- 不能用于运动的摄像头中；
- 无法识别静止或运动速度很慢的目标；
- 运动目标表面有大面积灰度值相似区域的情况下，在做差分时图像会出现孔洞；
2. 算法源码
笔者已经将把源码上传到GitHub网站上，地址如下：
https://github.com/upcAutoLang/BackgroundSplit-OpenCV/tree/master/src/FramesDifference
二. 背景差分法
参考网址：
《背景差分法》
《帧间差分法和背景建模法》
1. 算法原理
背景差分法是一种对静止场景进行运动分割的通用方法，它将当前获取的图像帧与背景图像做差分运算，得到目标运动区域的灰度图，对灰度图进行阈值化提取运动区域，而且为避免环境光照变化影响，背景图像根据当前获取图像帧进行更新。
根据前景检测，背景维持和后处理方法，存在几种不同的背景差方法。若设$ I_{t}, B_{t} $分别为当前帧与背景帧图像，T为前景灰度阈值，则其中一种方法流程如下：
- 取前几帧图像的平均值，将其作为初始的背景图像$ B_{t} $；
- 当前帧图像与背景图像作灰度减运算，并取绝对值；公式即为$ |I_{t}(x,y) - B_{t}(x,y)|$；
- 对当前帧的像素(x,y)，若有$ |I_{t}(x,y) - B_{t}(x,y)|>T $，则该像素点为前景点；
- （可选）对前景像素图进行形态学操作（腐蚀、膨胀、开闭操作等）
- 用当前帧图像对背景图像进行更新；
背景差分法的优缺点如下：
- 优点：
- 算法比较简单；
- 一定程度上克服了环境光线的影响；
- 缺点：
- 不能用于运动的摄像头；
- 对背景图像实时更新困难；
2. 算法源码
笔者已经将把源码上传到GitHub网站上，地址如下：
https://github.com/upcAutoLang/BackgroundSplit-OpenCV/tree/master/src/GaussBGDifference
三. ViBe背景提取算法
ViBe - a powerful technique for background detection and subtraction in video sequences
——摘自ViBe算法官网
ViBe是一种像素级视频背景建模或前景检测的算法，效果优于所熟知的几种算法，对硬件内存占用也少。该算法主要不同之处是背景模型的更新策略，随机选择需要替换的像素的样本，随机选择邻域像素进行更新。在无法确定像素变化的模型时，随机的更新策略，在一定程度上可以模拟像素变化的不确定性。
参考地址：
《ViBe算法原理和代码解析 》
《背景建模--Vibe 算法优缺点分析》
《第一次总结报告——Vibe 》
《运动检测（前景检测）之（一）ViBe 》
《VIBE改进算法》
参考论文：
《O. Barnich and M. Van Droogenbroeck. ViBe: a powerful random technique to estimate the background in video sequences.》
《O. Barnich and M. Van Droogenbroeck. ViBe: A universal background subtraction algorithm for video sequences.》
算法官网：
http://www.telecom.ulg.ac.be/research/vibe/
1. 一般背景提取算法存在的问题
前文提到的帧间差分法、背景差分法中存在若干问题如下：
- 对于环境变化的适应并不友好（如光照的变化造成色度的变化）；
- 相机抖动导致画面抖动
- 物体检测中常出现的Ghost区域；
其中值得一提的是Ghost区域：Ghost区域常常出现于帧间差分法，当一个原本静止的物体开始运动时，帧间差分法检测时，可能会将原本该物体覆盖区域错误的检测为运动的，这块被错误检测到的区域被称为Ghost。同样的，原本正在运动的物体变成静止物体时，也会出现Ghost区域。
例如下图，原图像中只有三个正在运动的人，但由于帧间差分法取得的背景图中包含这三个运动的人的某一帧运动状态，后面的一系列帧序列与背景图相减，都会存在背景图中三个人所在的位置，这时候取得的前景会多出三个被检测区域，即Ghost区域。
Ghost区域在检测中，一定要尽快消除。
2. ViBe算法原理
ViBe比较特殊的地方它的思想：它为所有像素点存储了一个样本集，样本集里面保存的采样值是该像素点过去的像素值与其邻居点的像素值。后面每一帧的新像素值和样本集里的样本历史值进行比较，判断是否属于背景点。
下面从几点讲解ViBe算法：
(1) 背景、前景模型
模型中，背景就是静止的，或者移动非常缓慢的物体；前景就是相对于背景的物体，即正在移动的物体。所以背景提取算法也可以看成是一个分类问题，遍历像素点的过程中，来确定一个像素点是属于前景点，还是属于背景点。
在ViBe模型中，背景模型为每个像素点存储了样本集，样本集大小一般为20个点。对于采入的新一帧图像，该帧的某个像素点与该像素点的样本集内采样值比较接近时，就可以判断其是一个背景点。
用公式表示，我们可以认为：
- $ v(x,y) $：像素点(x, y)处的当前像素值；
- $ M(x,y)={ v_{1}(x,y), v_{2}(x,y), ... v_{N}(x,y) } $：像素点(x, y)的背景样本集（样本集大小为N）；
- $ R $：上下取值范围；
将$ v(x,y)
(2) 背景模型初始化
初始化是建立背景模型的过程，一般的检测算法需要一定长度的视频序列学习完成，影响了检测的实时性，而且当视频画面突然变化时，重新学习背景模型需要较长时间。
ViBe算法建立背景模型只需要一帧，即使用单帧视频序列初始化背景模型。将视频的第一帧作为背景模型的同时，算法也将该帧中每一个像素点周围随机取多个像素点，填充该像素点的样本集，这样样本集中就包含了像素点的时空分布信息。
用公式表示，我们可以认为：
- $ M_{0}(x,y) $：初始背景模型中的像素点(x, y)；
- $ NG(x, y) $：像素点(x, y)的邻居点；
- $ v_{0}(x, y)$：初始原图像中像素点(x, y)的像素值；
于是有：
$ M_{0}(x, y) = { v_{0}(y|y \in NG(x,y) } , t = 0$
这种背景模型初始化的优缺点如下：
- 优点：
- 对于噪声的反应比较灵敏；
- 计算量小速度快；
- 不仅减少了背景模型建立的过程，还可以处理背景突然变化的情况，当检测到背景突然变化明显时，只需要舍弃原始的模型，重新利用变化后的首帧图像建立背景模型。
- 缺点：
- 用于作平均的几帧初始图像中可能采用了运动物体的像素，这种条件下初始化样本集，容易引入拖影（Ghost）区域；
初始背景模型建立完毕后，就可以进行前景的检测和背景模型的更新了。
###(3) 前景检测
此时已经建立起了背景模型，便可以已经建立好的背景模型进行前景的检测。
遍历新一帧图像的所有像素点。用公式表示，则有：
- $ v(x, y) $：新一帧的像素点(x, y)；
- $ M(x,y)={ v_{1}(x,y), v_{2}(x,y), ... v_{N}(x,y) } $：像素点(x, y)的背景样本集（样本集大小为N）；
- $ D(x, y) = { d_{1}(x,y), d_{2}(x,y), ... d_{N}(x,y) } $：像素点(x, y)当前值与样本集里所有样本值之差（样本集大小为N）
- 其中，$ d_{i} = v(x, y) - v_{i}(x, y) $；
- $ R $：判断像素点与历史样本值是否相近的阈值；
- $ T $：判断前景点的阈值；
- 统计当前像素点的值与历史样本值之差大于$R$的个数，若个数大于$T$，则判断该点为前景点；
检测前景的流程如下：
- 将某像素点的当前像素值$ v(x,y) $，与该像素点的样本集$M(x,y)$作差值，即得到$D(x,y)$。
- 遍历$D(x,y)$中的元素$d_{i}(x,y)$，比较它与阈值T的大小；并计满足$d_{i}(x,y) > R$的个数为$N_{f}$；
- 若有$N_{f} > T$，则该点为前景点；
检测过程的主要三个参数是：样本集数目N，阈值R，与阈值T。一般设置N = 20, R = 20, T = 2；
(4) 背景模型更新策略
即使已经建立起了背景模型，也应该对背景模型进行不断的更新，这样才能使得背景模型能够适应背景的不断变化（如光照变化，背景物体变更等）。
A. 普通更新策略
对于其他的背景提取算法，背景模型有两种不同的更新策略：
- 保守更新策略：前景点永远不会用来填充模型
- 这样会引起死锁，产生Ghost区域。比如初始化的时候如果一块静止的区域被错误的检测为运动的，那么在这种策略下它永远会被当做运动的物体来对待；
- Blind策略：对死锁不敏感，前景和背景都可以用来更新背景模型；
- 这样的缺点在于，缓慢移动的物体会融入到背景中，无法检测出来；
B. ViBe算法更新策略
ViBe算法中，使用的更新策略是：保守更新策略 + 前景点计数法 + 随机子采样。
- 前景点计数法：对像素点进行统计，如果某个像素点连续N次被检测为前景，则将其更新为背景点；
- 随机子采样：在每一个新的视频帧中都去更新背景模型中的每一个像素点的样本值是没有必要的，当一个像素点被分类为背景点时，它有1/φ的概率去更新背景模型。
这就决定了ViBe算法的更新策略的其他属性：
- 无记忆更新策略：每次确定需要更新像素点的背景模型时，以新的像素值随机取代该像素点样本集的一个样本值；
- 时间取样更新策略：并非每处理一帧数据，都需要更新处理，而是按一定的更新率更新背景模型；
- 当一个像素点被判定为背景时，它有1/φ的概率更新背景模型；
- φ是时间采样因子，一般取值为16；
- 空间邻域更新策略：针对需要更新像素点，在该像素点的邻域中随机选择一个像素点，以新选择的像素点更新被选中的背景模型；
C. ViBe算法具体更新的方法：
- 每个背景点都有1/φ的概率更新该像素点的模型样本值；
- 有1/φ的概率去更新该像素点邻居点的模型样本值；
- 前景点计数达到临界值时，将其变为背景，并有1/ φ的概率去更新自己的模型样本值。
更新邻居的样本值利用了像素值的空间传播特性，背景模型逐渐向外扩散，这也有利于Ghost区域的更快的识别。
在选择要替换的样本集中的样本值时，我们是随机选取一个样本值进行更新。这样就可以保证，样本值的平滑的生命周期的原因是由于是随机的更新，这种情况下一个样本值在时刻t不被更新的概率是(N - 1) / N。假设时间是连续的，那么在极小时间dt过去后，样本值仍然保留的概率是：
也可以写作：
上面的公式表明，样本值在模型中是否被替换，与时间t无关，即更新策略是合适的。
3. ViBe算法优缺点
(1) 优点
Vibe背景建模为运动目标检测研究邻域开拓了新思路，是一种新颖、快速及有效的运动目标检测算法。优点主要有两点：
- 思想简单，易于实现：
- 初始化背景图像时，Vibe算法通常随机选取邻域20个样本，作为每个像素点建立一个基于样本的背景模型，具有初始化速度快、内存消耗少和占用资源少等优点；
- 随后，利用一个二次抽样因子φ，使有限的样本基数能近似表示无限的时间窗口，即在较少样本前提下，保证算法的准确性；
- 最后，并采用一种领域传播机制保证算法的空间一致性。
- 样本衰减最优：
- 有人通过增加样本基数（上至200个）来处理复杂场景，也有人结合两个子模型分别处理快速更新和缓慢更新的情况。其实，选取被替换样本更新背景模型，实质上是样本寿命问题。
- 传统方式采用先进先出的替换策略，而Vibe背景模型中每个样本被选中为替换样本的概率是相等的，与样本存在时间的长短无关，这种策略保证背景模型中的样本寿命呈指数衰减，模型更新达到最佳状态。
- 运算效率高：
- Vibe背景模型是基于少量样本的背景模型；
- Vibe算法优化了背景模型中的相似度匹配算法；
关于运算效率的比较，《背景建模--Vibe 算法优缺点分析》中做了实验：为了得到最佳样本数量N值，分别选取N为5、15、20、25进行了实验对比：结果如图所示：
实验结果表明，N取20、25时，检测结果理想；考虑计算负载，N取20最优。与混合高斯的3-5个高斯模型的计算匹配比较，基于20个样本的背景模型计算具有计算开销低、检测速度快等优点。
Vibe的背景模型相似度匹配函数只与判断像素点与历史样本值是否相近的阈值R，以及判断前景点的阈值T有关（具体见本文三.2.(3)）。背景模型中的样本与待分类像素的欧式距离小于R的个数超过T时，更新背景模型；而找到T个匹配样本时，便立即判断该像素为背景像素点，并停止计算，这样提高了运算效率。
(2) 缺点
ViBe算法自身也存在着局限性。主要有静止目标、阴影前景和运动目标不完整等问题。
A. 静止目标
如下图所示：
图(a)红框中的人在等地铁，从图(a)到图(c)经过498帧，长时间驻留未运动，该人物运动目标逐渐被背景吸收。而在本视频中，将在450帧以上都没有明显位移的运动目标区域定义成为静止目标区域。
这样可以总结产生静止目标问题的原因有两个：
- 运动目标从运动到静止；
- 运动目标运动速度太过缓慢：当ViBe背景模型更新速度过快时，会将静止或缓慢运动目标吸收成为背景的一部分；
B. 阴影前景
如下图所示：
图(b)和图(d)分别是用Vibe算法对人体运动目标(a)和车体运动目标(c)的检测结果。由于光线被人体或车体运动目标所遮挡，投射阴影区的背景被误检为运动目标前景。阴影的存在导致检测出来的运动目标形状不准确，影响后续目标分类、跟踪、识别和分析等其他智能视频处理模块。
产生阴影前景问题的根源是：光线被运动目标前景遮挡，投射阴影区的颜色比背景的颜色暗，即阴影和背景颜色值的距离相差较大，背景差分后被误检为运动目标前景。
C. 运动目标不完整问题
如下图所示：
- 图(a)中的人内部出现空洞；
- 图(b)中的人中间出现断层；
- 图(c)中的人上半身出现边缘残躯；
- 图(d)车体的挡风玻璃出现空洞；
总结图中的结果，可以将运动目标不完整现象大致分为三类：
- 运动目标内部有大量空洞（图a）；
- 运动目标边缘残缺，呈现C字形凹陷（图d）；
- 运动目标中间有断层（图b)；
产生运动目标不完整问题的根源主要有两点：
- ViBe算法自身存在的缺陷；
- 基于统计学原理的Vibe样本模型受限于模型的样本个数，当样本趋于无穷大时才能准确描述场景，这在实际应用中是不可能实现的；
- 场景或运动目标的复杂性和多变性；
- 瞬时的光线突变，背景模型来不及更新；
- 前景与背景颜色相近，将前景误判为背景；
- 噪声干扰，出现孤立噪声点和连通噪声区域；
4. ViBe算法源码
笔者已经将把源码上传到GitHub网站上，地址如下：
https://github.com/upcAutoLang/BackgroundSplit-OpenCV/tree/master/src/ViBe
5. ViBe的改进算法ViBe+
笔者会对ViBe+进行学习研究，随后将博客总结上传，并附带源码。
参考地址：
《ViBe算法原理和代码解析 》
《VIBE改进算法》
参考论文：
《M. Van Droogenbroeck and O. Paquot. Background Subtraction: Experiments and Improvements for ViBe.》