《使用动态模式分解分离视频背景和前景》笔记

论文题目：

Dynamic Mode Decomposition for Real-Time Background/Foreground Separation in Video

作者：J.Grosek and J.Nathan Kutz

谢绝任何不标注出处的转载和百度百家号抄袭

笔记作者：李皮皮

这篇文章也是在介绍动态模式分解（DMD），但是相对于上一篇DMD的笔记

《用于动作侦测的随机低秩动态模式分解》读书笔记（上）

，这一篇个人觉得在理念上更全面一点。文章提到DMD是一个非常快速和轻量级的物体识别方法，我个人深有感触。在我的代码中，不论质量，用我个人的笔记本（thinkpad t460，配置算中等8G+i5），1700张高速公路灰度图像的车辆抓取一般130秒左右就能搞定。

我给DMD的定位是一个基于RPCA理念衍生的机器学习前置作业。目前来看，它本身并不是一个像神经网络等能达到高精度低错的机制，毕竟其起源是流体力学中用于分离气流和物体的手段，个人感觉可能它更能显示一个物体在背景上的动态过程。因为车辆的结构和运行方式还有一些未知原因，这个动态过程被抽离的不是很明显。但是在人的行走方面，就很容易发现有一些显示人类行走轨迹的人影抽离不干净。

文章首先介绍了RPCA（稳健主成分析）。PCA（主成分析）已经是一个降维和可视化常用的手段了。PCA依赖于欧几里得距离（L2 norm）来进行优化，主要是向量的内积/投影。但是在处理冗余数据上，欧氏距离的效果并不是非常好，因为欧氏距离对稀疏outlier极度敏感。因此，就有人使用其他范式进行替代，曼哈顿距离（L1 norm）就是一个替代选项。曼哈顿距离的本质就是绝对值相加，所以它不会给稀疏outlier太多权重。也有理论证明曼哈顿距离近来在许多物理应用上取得了不错的成绩【1】。

RPCA，就是集成了L1和L2两个范式而产生的算法。因此其在处理冗余数据和稀疏数据时能表现的稳健。在处理非线性系统时，RPCA会首先寻找数据中的稀疏结构，同时将其它数据用低秩基底表示。用公式表示如下：

其中，X是一个m*n的矩阵，代表原数据。S是一个m*n的稀疏矩阵，代表数据中改变较为明显的特征，L就是由低秩部分构成的m*n矩阵。从理解上我们就可以看出，X可以代表原图像，L是几乎不动的背景，S表示变化明显的物体/前景。这里RPCA问题就变成了一个主成追踪（principal component pursuit，PCP）问题：

lambda是一个惩罚项，取值非负实数。当lamda趋近于0，则图像就近似于只有背景；当lambda趋近于1，则图像趋近于原图。一般lambda的取值都需要考究一番，常用的公式为：

其中m，n为原矩阵的维度m,n。对于这种PCP问题，可以使用增广拉格朗日乘子法（Augmented Lagrange multiplier, ALM）解决。ALM是专门用于解决这类等式约束问题的算法。在使用RPCA处理的时候，假设有m张照片，每张照片对应的像素为(x,y)，那么我们的数据集就是一个(m,x,y)的矩阵。在进行进一步计算前，需要将这个矩阵转化成（x*y, m）维度的矩阵。每一张图像被压缩成一个m*n长度的长条，这就是一个框架（frame）。在视频问题中，相邻frame上静止的物体及其周围的像素点会变得高度相关，有助于我们通过frame形成低秩结构。

这里就可以看出来这类方法的一个缺陷——如何定义background和foreground并且精准分离。假设在一个地铁站，如果一个人走进镜头，那么无疑地铁站是背景，人是一个物体；可是当这个人长久伫立于镜头前，该如何判断他属于哪一类？这个问题我曾经和我的导师探讨过，他说目前学术界针对DMD方面产生的背景和前景并没有一个绝对的定义，大部分都是约定俗成：这个人一开始就是不属于这个镜头背景的，他站的再久，也有离开的时候，因此他依然是一个物体。但是对于RPCA，这个长久站立的人构成的一批图片在此人及其周围的像素点一定是高度相关的，那么这一部分图片中的人就很可能被误判成背景，造成分离错误。

接下来论文进入了正题，讲述了动态模式分解（DMD）。如上文所述，DMD最原始的作用是在无需完全知晓潜在非线性系统驱动公式的情况下，理解、控制和模拟本质复杂的非线性系统。它的神奇之处就是可以通过运算，让即使非线性的系统也能通过线性关系来表示。目前DMD的应用并不是非常广泛（该文章发表于2014年），还是局限在流体力学层面比较多。DMD中的核心是特征值分解和库普曼算子。使用DMD分离背景的核心则是傅里叶模式。因为核心的计算步骤和《用于动作侦测的随机低秩动态模式分解》读书笔记（中）一样，所以就不再赘述。DMD特别适合做视频分解，因为DMD要求数据必须均匀地在时间区间delta t上分布（傅里叶模式计算公式中要求delta t），在视频拆分成图像中可以得到很好地满足。

在叙述DMD的效果时，主要影响的点有：

（1）通过傅里叶模式划分特征值时threshold的选取

（2）图片数量的选取

（3）图片精度的选取，往往高分辨率的图片能得到更好的结果。因为特征值抓取的好

我在做DMD时，有两个主要问题，一个是分辨率，一个是抓取不干净的问题。高分辨率的图片得到的效果好，但是往往监控录像等是没有那么清晰地，尤其受天气影响。即使录制效果良好，物体移动时路面等也会存在抓取不干净的情况。比如说高速公路的车，因为车在快速移动，所以车下的路面的像素点也在快速改变，容易在后期图片中被识别成动态模式。对于第二个问题，论文说可以采用迭代方式精进。目前我还没有实验过。DMD是一个可以迭代的方法，一层一层过滤，因为每次过滤速度很快，所以对时间的影响还是在可容忍范围内的。

总的来说，这是一个拥有理论基础可行的方法，它在操作的简易性、运行时间、算力需求上表现出了很大的优势。主要问题就是精度和面对恶劣天气或者恶劣拍摄情况时造成的分离不均。

参考文献：

【1】E. Cand`es, J. Romberg, and T. Tao. Robust Uncertainty Principles: Exact Signal Reconstruction From Highly Incomplete Frequency Information. IEEE Transactions on Information Theory, 52(2):489–509, 2006.