Vibe 算法
简介
ViBe - a powerful technique for background detection and subtraction in video sequences
ViBe 是一种像素级视频背景建模或前景检测的算法，效果优于所熟知的几种算法，对硬件内存占用也少。ViBe 是一种像素级的背景建模、前景检测算法，该算法主要不同之处是背景模型的更新策略，随机选择需要替换的像素的样本，随机选择邻域像素进行更新。在无法确定像素变化的模型时，随机的更新策略，在一定程度上可以模拟像素变化的不确定性。
背景差方法实现运动物体检测面临的挑战主要有：
- 可直接应用在产品中，软硬件兼容性好；
- 必须适应环境的变化（比如光照的变化造成图像色度的变化）；
- 相机抖动引起画面的抖动（比如手持相机拍照时候的移动)；
- 图像中密集出现的物体（比如树叶或树干等密集出现的物体，要正确的检测出来）；
- 须能够正确的检测出背景物体的改变（比如新停下的车必须及时的归为背景物体，而有静止开始移动的物体也需要及时的检测出来）。
- 物体检测中往往会出现 Ghost 区域，Ghost 区域也就是指当一个原本静止的物体开始运动，背景差检测算法可能会将原来该物体所覆盖的区域错误的检测为运动的，这块区域就成为 Ghost，当然原来运动的物体变为静止的也会引入 Ghost 区域，Ghost 区域在检测中必须被尽快的消除。一个 Ghost 区域的实例如图 1,在图中可以发现相比于原图，检测的结果中错误的多出现了两个人的形状，这就是 Ghost。
ViBe 检测方法
ViBe 是本篇论文中所提出的一个检测方法，相比于其他方法它有很多的不同和优点。具体的思想就是为每个像素点存储了一个样本集，样本集中采样值就是该像素点过去的像素值和其邻居点的像素值，然后将每一个新的像素值和样本集进行比较来判断是否属于背景点。
该模型主要包括三个方面：
- 模型的工作原理；
- 模型的初始化方法；
- 模型的更新策略。
模型的工作原理
背景物体就是指静止的或是非常缓慢的移动的物体，而前景物体就对应移动的物体。所以我们可以把物体检测看成一个分类问题，也就是来确定一个像素点是否属于背景点。在 ViBe 模型中，背景模型为每个背景点存储了一个样本集，然后将每一个新的像素值和样本集进行比较来判断是否属于背景点。可以知道如果一个新的观察值属于背景点那么它应该和样本集中的采样值比较接近。
具体的讲，我们记 V(x)：x 点处的像素值； M(x)={$$V_1$$,$$V_2$$,…$$V_N$$} 为 x 处的背景样本集（样本集大小为 N)；SR(v(x))：以 x 为中心 R 为半径的区域，如果 M(x) [{SR(v(x))∩ {$$v_1$$,$$v_2$$, . . . , $$v_N$$}}] 大于一个给定的阈值 min，那么就认为 x 点属于背景点。
背景模型的初始化
初始化是建立背景模型的过程，一般的检测算法需要一定长度的视频序列学习完成，影响了检测的实时性，而且当视频画面突然变化时，重新学习背景模型需要较长时间。
ViBe 算法主要是利用单帧视频序列初始化背景模型，对于一个像素点，结合相邻像素点拥有相近像素值的空间分布特性，随机的选择它的邻域点的像素值作为它的模型样本值。ViBe 的初始化仅仅通过一帧图像即可完成。ViBe 初始化就是填充像素的样本集的过程但是由于在一帧图像中不可能包含像素点的时空分布信息，我们利用了相近像素点拥有相近的时空分布特性，具体来讲就是：对于一个像素点，随机的选择它的邻居点的像素值作为它的模型样本值。
M0(x)=v0(y|y∈NG(x)),t=0
初始时刻，NG(x) 即为邻居点 。这种初始化方法优点是对于噪声的反应比较灵敏，计算量小速度快，可以很快的进行运动物体的检测，缺点是容易引入 Ghost 区域。
- 优点：不仅减少了背景模型建立的过程，还可以处理背景突然变化的情况，当检测到背景突然变化明显时，只需要舍弃原始的模型，重新利用变化后的首帧图像建立背景模型。
- 缺点：由于可能采用了运动物体的像素初始化样本集，容易引入拖影（Ghost）区域。
前景检测过程
1.背景模型为每个背景点存储一个样本集，然后每个新的像素值和样本集比较判断是否属于背景。
2.计算新像素值和样本集中每个样本值的距离，若距离小于阈值，则近似样本点数目增加。
3.如果近似样本点数目大于阈值，则认为新的像素点为背景。
4.检测过程主要由三个参数决定：样本集数目 N，阈值 min和距离相近判定的阈值 R，一般具体实现，参数设置为 N=20，min=2，R=20。
背景模型的更新策略
- 背景模型的更新就是使得背景模型能够适应背景的不断变化，比如光照的变化，背景物体的变更等等。
- 保守的更新策略：前景点永远不会被用来填充背景模型，会引起死锁，比如初始化的时候如果一块静止的区域被错误的检测为运动的，那么在这种策略下它永远会被当做运动的物体来对待；
- Blind 策略：对死锁不敏感，前景背景都可以来更新背景模型，缺点是缓慢移动的物体会融入背景中无法被检测出来。在本方法中采用的更新策略是保守的更新策略+前景点计数方法。
- 前景点计数：对像素点进行统计，如果某个像素点连续 N 次被检测为前景，则将其更新为背景点。
- 随机的子采样：在每一个新的视频帧中都去更新背景模型中的每一个像素点的样本值是没有必要的，当一个像素点被分类为背景点时，它有 1/ φ的概率去更新背景模型。
具体的更新方法：每一个背景点有1/ φ的概率去更新自己的模型样本值，同时也有1/ φ的概率去更新它的邻居点的模型样本值。更新邻居的样本值利用了像素值的空间传播特性，背景模型逐渐向外扩 散，这也有利于 Ghost 区域的更快的识别。同时当前景点计数达到临界值时将其变为背景，并有1/ φ的概率去更新自己的模型样本值。
在选择要替换的样本集中的样本值时候，我们是随机选取一个样本值进行更新，这样可以保证样本值的平滑的生命周期由于是随机的更新，这样一个样本值在时刻 t 不被更新的概率是 (N-1)/N，假设时间是连续的，那么在 dt 的时间过去后，样本值仍然保留的概率是
P(t,t+dt)=(N−1N)(t+dt)−t
也可以写作:
P(t,t+dt)=e−ln(NN−1)dt
这就表明一个样本值在模型中是否被替换与时间 t 无关 ，随机策略是合适的。
1).无记忆更新策略
每次确定需要更新像素点的背景模型时，以新的像素值随机取代该像素点样本集的一个样本值。
2).时间取样更新策略
并不是每处理一帧数据，都需要更新处理，而是按一定的更新率更新背景模型。当一个像素点被判定为背景时，它有 1/rate 的概率更新背景模型。rate 是时间采样因子，一般取值为 16。
3).空间邻域更新策略
针对需要更新像素点，随机的选择一个该像素点邻域的背景模型，以新的像素点更新被选中的背景模型。
ViBe 的改进
- 不同的距离函数和二值化标准
- 对更新掩膜和输出掩膜的分割进行适当的滤波操作
- 抑制邻域更新
- 检测闪烁的像素点
- 增加更新因子
距离计算方法
以圆椎模型代替原来的几何距离计算方法
以自适应阈值代替原来固定的距离判定阈值,阈值大小与样本集的方差成正比,样本集方差越大,说明背景越复杂,判定阈值应该越大.
0.5×σm∈[20,40]
分离 UpdatingMask 和 SegmentationMask
引入目标整体的概念，弥补基于像素级前景检测的不足。针对 updating mask 和 segmentation mask 采用不同尺寸的形态学处理方法，提高检测准确率。
抑制邻域更新
在 updating mask 里，计算像素点的梯度，根据梯度大小，确定是否需要更新邻域。梯度值越大，说明像素值变化越大，说明该像素值可能为前景，不应该更新。
检测闪烁像素点
引入闪烁程度的概念，当一个像素点的 updating label 与前一帧的 updating label 不一样时，blinking level 增加 15，否则，减少 1，然后根据 blinking level 的大小判断该像素点是否为闪烁点。闪烁像素主要出现在背景复杂的场景，如树叶、水纹等，这些场景会出现像素背景和前景的频繁变化，因而针对这些闪烁应该单独处理，可以作为全部作为背景。
增加更新因子
ViBe 算法中，默认的更新因子是 16，当背景变化很快时，背景模型无法快速的更新，将会导致前景检测的较多的错误。因而，需要根据背景变化快慢程度，调整更新因子的大小，可将更新因子分多个等级，如 rate = 16,rate = 5,rate = 1。
ViBe 实验结果
在实验中，我们和其他的一些检测算法在检测准确率和算法的计算量方面都进行了比较，实验表明我们的方法检测效果明显要好很多，对于光照的变化和相机抖动等的效果都十分稳定，而且计算量非常小，内存占用较少，这就使得该方法能够用于嵌入手持照相机中。一些具体的实验效果和数据如下:
总结
在这片文章中，我们提出了一个新的背静差算法-ViBe，和以前相比它具有三个不同点。首先，我们提出了一个新的分类模型。其次，我们介绍了 ViBe 如何初始化，它只需要一帧图像即可完成初始化，而其他的算法通常需要等待数秒去完成初始化，这对于嵌入照相机中的要求实时性比较高的和一些比较短的视频序列很有帮助。 最后，我们提出了自己的更新策略，相比于其他算法将样本值在模型中保存一个固定的时间，我们采用随机的替换更新样本值，经过证明这样可以保证样本值的一个指数衰减的平滑生命周期，并且可以使得背景模型很好的适应视频场景的变化，从而达到更好的检测效果。
通过一系列实验表明 ViBe 方法相比于其他的一些检测算法具有计算量小、内存占用少、处理速度快、检测效果好、有更快的 Ghost 区域消融速度和应对噪声稳定可靠的特点，并且非常适合嵌入照相机等要求计算量小和内存占用少的情境中。
效果图：
算法的主要优势
- 内存占用少，一个像素需要作一次比较，占用一个字节的内存；
- 无参数法；
- 性能优于混合高斯，参数化方法，SACON 等；
- 像素级算法，视频处理中的预处理关键步骤；
- 背景模型及时初始化；
- 具有较好的抗噪能力。
Code
算法执行效率测试程序，windows 和 Linux 操作系统下的程序和 c/c++文件都可以在作者官网下载，如下：
- Windows and Linux users: a benchmarking program to evaluate the time needed by ViBe on your platform and on your own sequences! Download an archive zip archive 15 MB to evaluate the time needed by ViBe on your platform (Windows or Linux Wine ), and on your own sequences.
- A program for Windows and Linux. Download an archive zip archive 16 MB to use ViBe on Windows (or under Wine in Linux).The program allows you to: (1) save the result for your own images, (2) change the few parameters of ViBe to experiment with, and (3) reproduce our results.
- Linux: link a C/C++ object file to your own code. We provide the object (compiled) code of ViBe for non-commercial applications. Under Linux, download the 32 bits zip file, or the 64 bits zip file. Details on this page .
当然这里也借鉴 zouxy09 大神给出的 Mat 格式的代码（在 VS2010+OpenCV2.4.2 中测试通过）:
ViBe.h
#pragma once
#include <iostream>
#include "opencv2/opencv.hpp"
using namespace cv;
using namespace std;
#define NUM_SAMPLES 20 //每个像素点的样本个数
#define MIN_MATCHES 2 //#min 指数
#define RADIUS 20 //Sqthere 半径
#define SUBSAMPLE_FACTOR 16 //子采样概率
class ViBe_BGS
{
public:
ViBe_BGS(void);
~ViBe_BGS(void);
void init(const Mat _image); //初始化
void processFirstFrame(const Mat _image);
void testAndUpdate(const Mat _image); //更新
Mat getMask(void){return m_mask;};
private:
Mat m_samples[NUM_SAMPLES];
Mat m_foregroundMatchCount;
Mat m_mask;
};
ViBe.cpp
#include <opencv2/opencv.hpp>
#include <iostream>
#include "ViBe.h"
using namespace std;
using namespace cv;
int c_xoff[9] = {-1, 0, 1, -1, 1, -1, 0, 1, 0}; //x 的邻居点
int c_yoff[9] = {-1, 0, 1, -1, 1, -1, 0, 1, 0}; //y 的邻居点
ViBe_BGS::ViBe_BGS(void)
{
}
ViBe_BGS::~ViBe_BGS(void)
{
}
/**************** Assign space and init ***************************/
void ViBe_BGS::init(const Mat _image)
{
for(int i = 0; i < NUM_SAMPLES; i++)
{
m_samples[i] = Mat::zeros(_image.size(), CV_8UC1);
}
m_mask = Mat::zeros(_image.size(),CV_8UC1);
m_foregroundMatchCount = Mat::zeros(_image.size(),CV_8UC1);
}
/**************** Init model from first frame ********************/
void ViBe_BGS::processFirstFrame(const Mat _image)
{
RNG rng;
int row, col;
for(int i = 0; i < _image.rows; i++)
{
for(int j = 0; j < _image.cols; j++)
{
for(int k = 0 ; k < NUM_SAMPLES; k++)
{
// Random pick up NUM_SAMPLES pixel in neighbourhood to construct the model
int random = rng.uniform(0, 9);
row = i + c_yoff[random];
if (row < 0)
row = 0;
if (row >= _image.rows)
row = _image.rows - 1;
col = j + c_xoff[random];
if (col < 0)
col = 0;
if (col >= _image.cols)
col = _image.cols - 1;
m_samples[k].at<uchar>(i, j) = _image.at<uchar>(row, col);
}
}
}
}
/**************** Test a new frame and update model ********************/
void ViBe_BGS::testAndUpdate(const Mat _image)
{
RNG rng;
for(int i = 0; i < _image.rows; i++)
{
for(int j = 0; j < _image.cols; j++)
{
int matches(0), count(0);
float dist;
while(matches < MIN_MATCHES && count < NUM_SAMPLES)
{
dist = abs(m_samples[count].at<uchar>(i, j) - _image.at<uchar>(i, j));
if (dist < RADIUS)
matches++;
count++;
}
if (matches >= MIN_MATCHES)
{
// It is a background pixel
m_foregroundMatchCount.at<uchar>(i, j) = 0;
// Set background pixel to 0
m_mask.at<uchar>(i, j) = 0;
// 如果一个像素是背景点，那么它有 1 / defaultSubsamplingFactor 的概率去更新自己的模型样本值
int random = rng.uniform(0, SUBSAMPLE_FACTOR);
if (random == 0)
{
random = rng.uniform(0, NUM_SAMPLES);
m_samples[random].at<uchar>(i, j) = _image.at<uchar>(i, j);
}
// 同时也有 1 / defaultSubsamplingFactor 的概率去更新它的邻居点的模型样本值
random = rng.uniform(0, SUBSAMPLE_FACTOR);
if (random == 0)
{
int row, col;
random = rng.uniform(0, 9);
row = i + c_yoff[random];
if (row < 0)
row = 0;
if (row >= _image.rows)
row = _image.rows - 1;
random = rng.uniform(0, 9);
col = j + c_xoff[random];
if (col < 0)
col = 0;
if (col >= _image.cols)
col = _image.cols - 1;
random = rng.uniform(0, NUM_SAMPLES);
m_samples[random].at<uchar>(row, col) = _image.at<uchar>(i, j);
}
}
else
{
// It is a foreground pixel
m_foregroundMatchCount.at<uchar>(i, j)++;
// Set background pixel to 255
m_mask.at<uchar>(i, j) = 255;
//如果某个像素点连续 N 次被检测为前景，则认为一块静止区域被误判为运动，将其更新为背景点
if (m_foregroundMatchCount.at<uchar>(i, j) > 50)
{
int random = rng.uniform(0, SUBSAMPLE_FACTOR);
if (random == 0)
{
random = rng.uniform(0, NUM_SAMPLES);
m_samples[random].at<uchar>(i, j) = _image.at<uchar>(i, j);
}
}
}
}
}
}
Main.cpp
#include "opencv2/opencv.hpp"
#include "ViBe.h"
#include <iostream>
#include <cstdio>
using namespace cv;
using namespace std;
int main(int argc, char* argv[])
{
Mat frame, gray, mask;
VideoCapture capture;
capture.open("video.avi");
if (!capture.isOpened())
{
cout<<"No camera or video input!\n"<<endl;
return -1;
}
ViBe_BGS Vibe_Bgs;
int count = 0;
while (1)
{
count++;
capture >> frame;
if (frame.empty())
break;
cvtColor(frame, gray, CV_RGB2GRAY);
if (count == 1)
{
Vibe_Bgs.init(gray);
Vibe_Bgs.processFirstFrame(gray);
cout<<" Training GMM complete!"<<endl;
}
else
{
Vibe_Bgs.testAndUpdate(gray);
mask = Vibe_Bgs.getMask();
morphologyEx(mask, mask, MORPH_OPEN, Mat());
imshow("mask", mask);
}
imshow("input", frame);
if ( cvWaitKey(10) == 'q' )
break;
}
return 0;
}
参考文献
- O. Barnich and M. Van Droogenbroeck . ViBe: A universal background subtraction algorithm for video sequences . In IEEE Transactions on Image Processing, 20(6):1709-1724, June 2011. Also available on the University site in PDF format , and HTML format . This paper contains a very detailed pseudo-code description of the complete algorithm .
- M. Van Droogenbroeck and O. Paquot. Background Subtraction: Experiments and Improvements for ViBe. In Change Detection Workshop (CDW), Providence, Rhode Island, June 2012. Available on the University site in PDF format and HTML format .
- O. Barnich and M. Van Droogenbroeck . ViBe: a powerful random technique to estimate the background in video sequences. In International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2009), pages 945-948, April 2009. Available as a IEEE publication or on the University site .
- Patent description at the “freepatentsonline” web site .
Performance
- An independant evaluation is available in S. Brutzer, B. Hoferlin, and G. Heidemann. Evaluation of background subtraction techniques for video surveillance . In IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), pages 1937-1944, Colorado Spring, USA, June 2011.
- In their conclusions, they claim: “Considering these aspects, Barnich is a strong favorite, since it is simple and almost parameterless.”
湘公网安备 43102202000103号