1 简介
ViBe（Visual Background Extractor）[1] 是一种前景分割（foreground segmentation）算法。 在ViBe中，前景被定义为视频中运动的物体，背景被定义为视频中静止不动的物体。例如，在高速公路上，运动的车是前景，路面、天空、草地是背景。但假如一辆车停在应急车道上，处于静止状态，那么它就应当被视为背景。需要注意的是，所谓运动与不运动，是相对而言的。例如流动的白云，随风摇摆的草地，虽然它们是运动的，但它们应当被视为背景。
这类前景分割（或者可以称为背景减除（background substraction）、运动检测（motion detection））算法在安防领域有许多应用。例如，通过对仓库监控视频的运动检测，我们可以快速从长时间的视频中找到潜在的有人出入的时间片段。前景检测算法还可以作为许多复杂任务的预处理任务，例如行人计数、交通监测等等。
前景分割的一般思路是背景建模：通过比较当前帧与所建立的背景模型，判断出一块区域是属于前景还是背景。
前景分割任务的常见问题：
- 鬼影：当一个静止物体发生运动时，不仅这个物体表面像素发生变化，它身后的背景区域的像素也发生变化。前者属于前景，但后者应该视为背景，是应当减除的。
- 背景变化的问题：视频时间跨度长时，由于光照环境、天气、季节变换的影响，背景会发生改变。
- 背景的运动：如前所述，草地、云朵等背景不是完全静止的，这给运动检测带来困难。
2 ViBe算法
ViBe的基本假设是：“一个已经在某个位置出现过的背景像素，很有可能再次出现在那附近”。例如，如果某个像素对应于绿色的草坪，那么尽管受风的影响，导致草业摇摆，但同样的颜色很有可能再次出现在那附近（当然，对于没有区分颜色能力的黑白视频，也有同样的结论）。
2.1 分类依据
在这个假设条件下，ViBe将前景分割问题定义为”给定邻域像素的状态，判断当前新像素转态属于前景还是背景的二分类问题”。根据先前的假设，假如一个像素之前在邻域出现过，那么这个像素很有可能是背景。反之，如果在邻域内找不到相似像素，那么这里可能检测到一个以较快速度运动的物体。
ViBe为每一个像素建立背景模型，背景模型定义为前一时刻邻域内的\(N\)个背景像素：
\[ \mathcal{M}(x) = \left\{ v_1, v_2, \dots, v_N\right\} \]
对于当前像素值\(v(x)\)，分类依据是\(\#\{S_R(v(x))\cap \mathcal M(x) \} \geq \#_{min}\)，其中，\(\#\)表示集合中的元素个数，\(S_R(v(x))\)表示颜色空间中，以\(v(x)\)为中心，以\(R\)为半径的一个球体。公式的意思是说，如果邻域中有不少于\(\#_{min}\)的像素，其到当前像素的距离小于阈值，那么这个像素是背景；反之则是前景。
2.2 背景模型初始化
初始化时，ViBe取第一帧图像，随机取邻域内的\(N\)个像素用于填充背景模型\(\mathcal M(x)\)。这里的随机采样是有放回的随机抽取，所以一个像素可以被选取多次。
ViBe的初始化策略基于一个合理的假设，即邻域内的像素服从于相似的分布。
但是，这样的初始化策略有一个问题，即如果第一帧中存在运动物体，那么其像素会污染背景模型。好在ViBe有较强的自适应能力。随著时间流逝，得益于更新策略的设计，它的背景模型会趋于合理。
2.3 背景模型的更新策略
在ViBe之前，常见的背景模型的更新策略是，用当前的某个像素替换掉背景模型中最老的那个像素。这种做法有一定合理性，但它也有可能导致有用的老像素被剔除。
除了剔除新旧像素的优先顺序问题外，另一个问题是，是否要用前景像素来更新背景模型。显而易见，如果要使模型具有自适应学习能力，那么前景像素应当参与到背景模型的更新中来。
所以，ViBe的更新策略是保守的。即，ViBe中，不仅被分类为背景的像素参与背景模型的更新，分类为前景的像素一样有机会参与背景模型更新。
如果一个像素被分类为背景，它会被用来随机替换掉背景模型中的一个元素：与以往一些”先入先出”的顺序替换方法不同，这里的替换是完全随机的。为了进一步减低运算代价和延长背景模型中每个元素的寿命，可以降低替换背景模型的频率。这个技巧在ViBe中被称为时间亚采样（time subsampling）。ViBe用一个固定概率随机地决定是否进行替换，这被称作随机亚采样（random subsampling）。
反之，如果一个像素被分类为前景，它也有机会参与背景模型的更新。ViBe采用一种叫做detection support map的数据结构来统计一个像素被检测为前景的次数。如果计数达到阈值，那么虽然当前像素属于前景，它也会被加入到背景模型中。’
在ViBe中，每个像素不仅负责自己的背景模型的更新，还会将自身的信息扩散到其邻域的背景模型中去。每次更新当前像素的背景模型，都要从邻域中随机选择另一个点，用同样的像素去更新这个点的背景模型。
3 调参经验
在原始论文中，由于视频分辨率比较小，故而将邻域定义为\(3\times 3\)内的4邻域或8邻域。然而，今天许多监控视频都达到高分辨率，那么这样的小邻域就不够用了。有时需要改为\(11\times 11\)或者\(21\times 21\)才行。当然，对原始视频作降采样也是一个办法。
邻域一旦调大，那相应的参数、算法也应当适当调整。比如，在用当前点更新邻域内的背景模型时，可以一次多更新几个点。detection support map的计数阈值应当减小。
4 并行化
ViBe的效率很高。但如果要实时处理高分辨率视频，并且使用较大的邻域定义，那么就要并行化算法才行。通过并行化使得不同像素上的操作分配给不同线程执行，能加快处理速度。原论文[1]没有介绍并行化的方法。这里仅提供个人的几点思考。
ViBe的并行化的困难主要体现在更新邻像素的背景模型时容易出现的访问冲突。为了简便，不妨假设每一个像素位置都由单独的线程来负责。假如像素甲要更新像素乙的背景模型，同时像素乙自己又要更新自身的背景模型，那么就发生冲突。为了避免冲突，可以考虑以下几种方案：
严格限制和检查各个线程的读写权限和操作顺序。例如，限制每个线程一定只能修改当前线程所负责的背景模型。同时，读取其它线程的状态，必须是在这些线程的写入操作都完成时才能进行。从这个思路考虑，难免需要修改大量算法逻辑。
通过线程分组来避免读写冲突。设窗口大小为W，我们知道，读写冲突仅发生在两个并行处理的像素的落在同一个\(W\times W\)的窗口内时。因此，不妨按窗口大小，将像素分成若干组，使得不同组内的像素绝对不在同一个邻域内。组之间的背景模型并行更新，而组内的背景模型串行更新。在背景模型更新操作的步骤后设立一个同步点来同步各个线程的进度。这样一来，就不会有并行处理的待处理像素落在同一个窗口内而导致冲突的事情了。
