CodeBook

Posted on Edited on In Waline:

对 SLAM 算法中会见到的 CodeBook 进行内容整理，主要是 CSDN 上找到的内容进行修改转载。

CodeBook

1 起源

平均背景的建模方法：

  • 对于每个像素，累积若干帧的像素值，计算平均值和方差，以此来建立背景模型。但每个像素的特征仅有统计量而没有历史起伏，即没有考虑时间序列和噪声。因此建模时不能有运动前景的部分。

如果考虑时间序列，以 nn 帧图像建模，每个像素点会产生 nn 个像素值，分别加权或进一步统计不同像素出现的频次或距离，以此来排除噪声，模拟复杂的背景，但会带来大的内存消耗。

如果对该像素值起伏的范围进行压缩，依据于像素值间的大小距离，即当前观测值与历史值的对比：

  • 如果两个值接近，则归为异类，即同属一个码元（CodeWord）；
  • 如果差别较大，则以当前值新建一个码元。

压缩后可以得到只含有若干个码元的编码本（CodeBook），这个编码本能模拟复杂背景，同时减少了内存消耗。对每个码元的更新频率也进行监督，剔除那些频率低的（动态前景）。

2 CodeBook 的主要参数

CodeBook 算法为当前图像的每一个像素建立一个 CodeBook（CB）结构，每个 CB 又由多个 CodeWord（CW）组成。CB 和 CW 的形式如下：

CB={CW1,CW2,...,CWn,t}CB = \{ CW_1, CW_2, ..., CW_n, t \}

CW={learnHigh[],learnLow[],max[],min[],t_last_update,stale}CW = \{ learnHigh[], learnLow[], max[], min[], t \_ last \_ update, stale \}

nn 为一个 CB 中 CW 的个数，当 nn 太小时，退化为简单背景，当 nn 较大时可以对复杂背景进行建模。CW 在整个算法中主要包括的参数为：

  • maxMod[]：用训练好的背景模型进行前景分割时的调节量，判断点是否小于 max[] + maxMod[]；
  • minMod[]：用训练好的背景模型进行前景分割时的调节量，判断点是否小于 min[] - minMod[]；
  • cbBounds[]：训练背景模型时用到，相当于控制模型的增长速率，更新 learnHigh[] 和 learnLow[]；
  • learnHigh[]：背景的学习上界限，当新像素进来时判断其是否属于该码元；
  • learnLow[]：背景的学习下界限，当新像素进来时判断其是否属于该码元；
  • max[]: 背景学习中不断更新，记录当前码元的最大值，在前景分割时，与 maxMod[] 配合，判断像素是前景还是背景;
  • min[]: 背景学习中不断更新，记录当前码元的最小值，在前景分割时，与 minMod[] 配合，判断像素是前景还是背景;
  • 为了剔除陈旧码元，给每个 CB 和 CW 都加入了若干时间标签，比如 CB 的 t，记录 CB 更新的次数，CW 的 t_last_updata 和 stale，t_last_updata 记录了该 CW 上次更新的时间，stale 记录了 CW 的搁浅时间，stale = t - l_last_updata。

3 算法流程

假设当前训练图像 II 中某一像素为 I(x,y)I(x,y)，该像素的 CB 的更新算法如下：

  1. CB 的访问次数加 1；
  2. 遍历 CB 中的每个 CW，如果存在一个 CW 中的 learnHigh，learnLow 满足 learnLow≤I(x,y)≤learnHighlearnLow \le I(x,y) \le learnHigh，则转 4；
  3. 创建一个新的码字 CWnew 加入到 CB 中，CWnew 的 max 与 min 都赋值为 I(x,y)I(x,y)，$ learnHigh = I(x,y) + cbBounds，，learnLow = I(x,y) - Bounds$，并且转 6；
  4. 更新该码字的 t_last_update，若当前像素值 I(x,y)I(x,y) 大于该码字的 max，则 max=I(x,y)max = I(x,y)，若 I(x,y)I(x,y) 小于该码字的 min，则 min=I(x,y)min = I(x,y)；
  5. 更新该码字的学习上下界，以增加背景模型对于复杂背景的适应能力，具体做法是： 若 learnHigh<I(x,y)+cbBoundslearnHigh < I(x,y) + cbBounds，则 learnHigh 增长 1，若 learnLow>I(x,y)−BoundslearnLow > I(x,y) - Bounds，则 learnLow 减少 1；
  6. 更新 CB 中每个 CW 的 stale。

使用已建立好的CB进行运动目标检测的方法：

  • 记判断前景的范围上下界为 minMod 和 maxMod，对于当前待检测图像上的某一像素 I(x,y)I(x,y)，遍历它对应像素背景模型 CB 中的每一个码字 CW，若存在一个 CW，使得 I(x,y)<max+maxModI(x,y) < max + maxMod 并且 I(x,y)>min−minModI(x,y) > min - minMod，则 I(x,y)I(x,y) 被判断为背景，否则被判断为前景。

实际使用 CodeBook 进行运动检测时，除了要隔一定的时间对 CB 进行更新的同时，需要对 CB 进行时间滤波，目的是去除很少被访问到的 CW，方法是访问每个 CW 的 stale，若 stale 大于一个阈值（通常设置为总更新次数的一半），移除该 CW。

综上，CodeBook 算法检测运动目标的流程如下：

  1. 选择一帧到多帧使用更新算法建立 CodeBook 背景模型；
  2. 按上面所述方法检测前景（运动目标）；
  3. 间隔一定时间使用更新算法更新 CodeBook 模型，并对 CodeBook 进行时间滤波；
  4. 若检测继续，转 2，否则结束。

参考