第15章 视频专题：光流、时空正则与低秩-稀疏张量分解

1. 开篇：从 2D 到 3D 的维度诅咒与祝福

视频处理不仅仅是“处理很多张图片”。引入时间维度 $t$ 后，我们面临双重局面：

  • 维度的诅咒（Curse）：数据量爆炸。一段 1080p 的 1 分钟视频包含约 $10^9$ 个像素点，优化问题的规模从百万级跃升至十亿级，对内存和算力提出严峻挑战。
  • 维度的祝福（Blessing）：时间冗余。相邻帧之间包含极强的信息重叠。单帧中丢失的信息（被遮挡、被噪声淹没），往往可以从邻近帧中找回。

本章将聚焦于三个核心数学问题，它们分别代表了视频处理的三种世界观：

  1. 微观运动（光流）：像素去哪了？（基于 PDE 和变分）
  2. 时空复原（Video Restoration）：如何利用时间连续性压制噪声？（基于时空正则化）
  3. 全局结构（RPCA/Tensor）：如何分离变与不变？（基于低秩稀疏分解）

2. 变分光流（Variational Optical Flow）

光流是计算机视觉中“运动”的代名词。它是一个二维向量场 $\mathbf{u}(x,y,t) = (u, v)$，描述了像素从当前帧到下一帧的瞬时速度。

2.1 核心假设：亮度恒常与其线性化

一切始于亮度恒常假设（Brightness Constancy Assumption, BCA）：

场景中同一点的物理亮度，在短时间内随物体运动保持不变。

$$ I(x+u, y+v, t+1) = I(x, y, t) $$ 这是一个高度非线性的方程（$u, v$ 在 $I$ 的自变量里）。为了能用凸优化求解，我们必须对其进行泰勒级数一阶展开（线性化）： $$ I(x, y, t) + \frac{\partial I}{\partial x} u + \frac{\partial I}{\partial y} v + \frac{\partial I}{\partial t} \Delta t \approx I(x, y, t) $$ 整理得到著名的光流约束方程（Optical Flow Constraint Equation, OFCE）： $$ I_x u + I_y v + I_t = 0 $$ 直觉理解： 这个方程定义了 $(u, v)$ 必须落在一条直线上。

  • 如果图像在该点没有纹理（$I_x \approx 0, I_y \approx 0$），则方程变为 $0=0$，无法求出 $u, v$（什么都看不出在动）。
  • 如果图像是边缘（$I_x$ 大，$I_y$ 小），只能求出垂直于边缘的速度分量。 这就是著名的孔径问题（Aperture Problem）。为了得到唯一解，必须引入正则项。

2.2 经典模型：Horn-Schunck (HS) —— 扩散的艺术

Horn 和 Schunck (1981) 提出了全局平滑假设：相邻像素的运动速度应该变化缓慢。

能量泛函： $$ E(u, v) = \int_{\Omega} \underbrace{(I_x u + I_y v + I_t)^2}_{\text{数据项：亮度误差}} + \lambda \underbrace{(|\nabla u|^2 + |\nabla v|^2)}_{\text{正则项：速度平滑}} d\Omega $$ 欧拉-拉格朗日方程（解析性质）： 对 $E$ 求变分并令其为 0，得到的方程包含拉普拉斯算子 $\Delta u$ 和 $\Delta v$。这在物理上对应于热扩散过程。

  • 物理意义：光流信息从图像中梯度大的地方（有纹理、角点）产生，并通过正则项（扩散项）向平坦区域传播。
  • 缺陷：由于使用 $L_2$ 范数平方作为平滑项，它不允许流场发生突变。这导致运动物体的轮廓会被“模糊”化，背景可能会被前景物体“拖拽”。

2.3 现代基石：TV-L1 光流

为了允许运动不连续性（例如：人的轮廓运动很快，背景不动，轮廓处速度场应该有阶跃），并处理光照变化或遮挡（由于这些情况违反亮度恒常假设，会产生巨大的数据项残差），TV-L1 模型成为了标准配置。 $$ \min_{\mathbf{u}} \int_{\Omega} \underbrace{|I(\mathbf{x}+\mathbf{u}) - I(\mathbf{x})|}_{\text{L1 数据项}} + \lambda \underbrace{|\nabla \mathbf{u}|_1}_{\text{TV 正则项}} d\mathbf{x} $$ 为什么是双重 L1？

  1. 数据项 L1：鲁棒统计。当出现遮挡或高光时，$I(x+u) - I(x)$ 很大。$L_2$ 数据项会为了拟合这个错误值而扭曲整个流场；$L_1$ 数据项则倾向于把这个点视为“离群值”（Outlier），允许其残差很大而不影响估计。
  2. 正则项 TV ($L_1$ on gradient)：允许流场 $\mathbf{u}$ 存在跳变（Edges in the flow field）。

ASCII 示意：L2 vs TV 流场剖面

真实运动场 (物体移动，背景静止)
Velocity
  ^
  |      ___________

  |      ___________
  |     |           |
  |_____|           |_____

        <--Object-->      Pixel Position

Horn-Schunck (L2 Regularization) -> 过度平滑
  ^
  |        _-----
  |      /       \
  |____/           \____  (边界模糊)

TV-L1 (Total Variation) -> 保持锐利边缘
  ^
  |      ___________

  |      ___________
  |     |           |
  |_____|           |_____ (边界清晰)

2.4 关键工程技术：Coarse-to-Fine 金字塔

初学者实现光流往往失败，因为线性化假设只在位移很小（<1像素）时成立。如果物体移动了 10 个像素，泰勒展开完全失效。

解决方案：多尺度金字塔（Pyramidal Scheme）

  1. 下采样：建立图像金字塔（Level 0 到 Level K）。Level K 的图像非常小，原本 10 像素的位移在这里可能只有 0.1 像素。
  2. 求解与传播：
    • 在最顶层求解光流（满足小位移假设）。
    • 将求得的光流上采样放大，作为下一层的初始猜测。
    • Warping (卷绕)：利用初始猜测 $u_0$，将 Image 2 向 Image 1 对齐。
    • 在下一层计算残余光流（Residual Flow），修正 $u_0$。
  3. 循环：直到最底层（原分辨率）。
ASCII 示意：金字塔流程

Level 2 (极小图)  [Solve] -> du2
                      | (Upsample & Scale)
                      v
Level 1 (中等图)  [Warp I2 by u_prev] -> [Solve Residual] -> u1 = u_prev + du1
                      | (Upsample & Scale)
                      v
Level 0 (原图)    [Warp I2 by u_prev] -> [Solve Residual] -> u0 = u_prev + du0

3. 视频复原：时空正则化的进化

3.1 3D 全变分 (Spatiotemporal TV)

将视频看作 $x-y-t$ 的立方体。去噪模型自然地扩展为： $$ \min_{U} \frac{1}{2}|U - F|_2^2 + \lambda_{s} |\nabla_{xy} U|_1 + \lambda_{t} |\nabla_{t} U|_1 $$

  • $\nabla_{xy} U$: 空间 TV，去除每帧内的噪声。
  • $\nabla_{t} U = |U_{x,y,t} - U_{x,y,t-1}|$: 时间 TV，强迫对应像素在时间轴上保持数值接近。

局限性：这种模型假设场景是静止的。 如果物体运动，像素 $(x,y)$ 在 $t$ 时刻是物体，在 $t+1$ 时刻变成了背景。强行让 $U_{x,y,t} \approx U_{x,y,t-1}$ 会导致严重的运动拖影（Ghosting）——这就像老式液晶屏的残影。

3.2 运动补偿时空正则 (Motion Compensated Regularization)

为了消除拖影，正则化必须“顺着”运动轨迹进行。我们引入光流 $\mathbf{v} = (u,v)$。

定义沿轨迹的时间导数（输运导数）： $$ D_t U(x, y, t) = U(x+u, y+v, t+1) - U(x, y, t) $$ 改进模型： $$ \min_{U} \frac{1}{2}|U - F|_2^2 + \lambda_{s} |\nabla_{xy} U|_1 + \lambda_{t} |D_t U|_1 $$

  • 直觉：这相当于在视频立方体中，沿着“光流纤维”进行平滑，而不是沿着垂直的时间轴平滑。
  • 挑战：这是一个鸡生蛋、蛋生鸡的问题。去噪需要准确的光流，算光流又需要无噪的图像。
  • 策略：通常采用联合优化（Joint Optimization），交替迭代更新图像 $U$ 和光流 $\mathbf{v}$。

4. 低秩与稀疏分解：从背景建模到张量补全

4.1 矩阵 RPCA 与背景分离

在监控视频中，我们可以利用数据的结构冗余。 将 $N$ 帧图像拉成 $N$ 个列向量，组成矩阵 $X \in \mathbb{R}^{d \times N}$。

  • 背景 (Low Rank)：墙壁、地面是不变的，每一列都高度线性相关。对应矩阵 $L$ 秩极低。
  • 前景 (Sparse)：行人、车辆是移动且稀疏的（相对于整图像素较少）。对应矩阵 $S$ 是稀疏的。
  • 噪声 (Gaussian)：摄像机热噪声，对应残差 $E$。

模型： $$ \min_{L, S} |L|_* + \lambda |S|_1 \quad \text{s.t.} \quad |X - L - S|_F \le \sigma $$

  • $|L|_*$：核范数（奇异值之和），是秩函数的凸松弛。
  • $|S|_1$：$L_1$ 范数，诱导稀疏性。
  • 求解：通常使用 ADMM 或 IALM (Inexact Augmented Lagrange Multiplier) 算法，涉及 SVD 阈值化（针对 $L$）和软阈值化（针对 $S$）。

4.2 张量 RPCA (Tensor RPCA) —— 保留空间结构

矩阵化（Vectorization）有一个致命弱点：它破坏了图像的 2D 空间结构。像素 $(0,0)$ 和 $(0,1)$ 在矩阵列中是相邻的，但 $(0,0)$ 和 $(1,0)$ 可能相隔很远。

张量方法将数据保持为 $\mathcal{X} \in \mathbb{R}^{H \times W \times N}$。

张量奇异值分解 (t-SVD)： Kilmer 等人提出了一种基于张量乘积 (t-product) 的代数框架。其核心思想是利用 FFT 将卷积运算转化为频域的逐点乘法。

张量核范数 (TNN) 的直觉：

  1. 对张量 $\mathcal{X}$ 沿时间轴做 FFT，得到 $\bar{\mathcal{X}}$。
  2. $\bar{\mathcal{X}}$ 的每一个切片（Frontal Slice）是一个复数矩阵。
  3. TNN 近似等于所有这些频域切片的核范数之和。
  4. 物理含义：通过限制 TNN，我们实际上是在约束视频在频域上的低秩性，这比直接矩阵化更能捕捉时空纹理的规律性（例如水面波纹的周期性运动）。

应用： Tensor RPCA 在去除由于摄像机抖动引起的背景微动、去除雨雪（具有时空重复模式）方面，效果显著优于矩阵 RPCA。

5. 本章小结

  • 光流是基础：它是视频处理中连接像素的纽带。
    • HS 模型：L2 正则，简单快速但边缘模糊，像热扩散。
    • TV-L1 模型：L1 正则，保留运动边缘，抗光照干扰，是现代标准。
    • 金字塔策略：必不可少的工程实现，解决大位移线性化失效问题。
  • 去噪需顺势而为：单纯的 3D 平滑会破坏运动信息。运动补偿（Motion Compensation） 将正则化方向对准物体运动轨迹，是高质量视频复原的关键。
  • 分解即理解：
    • RPCA 利用 $X=L+S$ 将视频分解为静止背景（低秩）和运动前景（稀疏）。
    • 张量方法 通过 t-SVD 在保留空间结构的同时利用全局相关性，适合处理更复杂的动态背景。

6. 练习题

基础题

  1. 光流方程推导：如果不使用泰勒展开，直接令 $I(x+u, y+v, t+1) - I(x, y, t) = 0$，请说明为什么这个方程在数值上极难直接求解？（提示：关于 $u,v$ 的凸性）。
  2. 正则项权重：在 TV-L1 光流中，如果正则化参数 $\lambda \to 0$，求解结果会变成什么样？如果 $\lambda \to \infty$ 呢？
  3. 计算复杂度：假设视频大小为 $H \times W \times T$。矩阵 RPCA 需要对 $HW \times T$ 的矩阵做 SVD。张量 RPCA (t-SVD) 需要做 $T$ 次 $H \times W$ 的 SVD（以及 FFT）。哪种在 $T$ 很大时更耗时？（假设 $HW \gg T$）。

挑战题

  1. 色彩恒常性：推导 RGB 彩色图像的光流约束方程组。这个方程组在什么情况下依然无法唯一确定 $(u,v)$？（即讨论彩色图像下的孔径问题）。
  2. 遮挡与前向/后向光流：
    • 物体移动导致背景被遮挡。此时 $t \to t+1$ 的光流是有定义的，但 $t+1 \to t$ 的光流在被遮挡区域无定义（无源）。
    • 设计一种利用 前向光流 (Forward Flow) 和 后向光流 (Backward Flow) 的一致性（Consistency Check）来自动检测遮挡区域的方法。
  3. RPCA 的抖动敏感性：如果摄像机有轻微抖动，导致背景整体平移了 1-2 个像素。矩阵 RPCA 的 $L$ 分量还能保持低秩吗？为什么？这种情况下 $S$ 会包含什么？
点击查看答案提示
  1. 直接求解难点：$I(x+u, ...)$ 是关于 $u,v$ 的高度非凸函数。图像 $I$ 可能有无数个局部极小值（纹理）。直接优化会陷入局部最优，无法找到真实的运动位移。线性化将其变成了凸的二次/L1问题。
  2. 参数极限：$\lambda \to 0$ 时，只考虑数据项，这是病态的（孔径问题），流场会充满噪声，且在平坦区域不可控。$\lambda \to \infty$ 时，流场变为全局常数（通常为0），完全平滑。
  3. 复杂度：矩阵 RPCA 的 SVD 复杂度约为 $O(\min(HW, T)^2 \cdot \max(HW, T))$。如果 $HW \gg T$，约为 $O(T^2 HW)$。张量 RPCA 主要是 FFT $O(HWT \log T)$ 和 $T$ 次 SVD $O(T \cdot H W^2)$（假设 $H \approx W$）。通常张量方法因分解为小矩阵 SVD，在大尺寸图像上可能更快，但对 $T$ 敏感。
  4. 彩色孔径：方程组为 $[R_x u + R_y v + R_t = 0; G_x u + ... = 0; B_x u + ... = 0]$。如果 $R, G, B$ 梯度的方向是平行的（例如黑白边缘，RGB 梯度共线），矩阵秩仍为1，依然存在孔径问题。
  5. 遮挡检测：计算 $u_{fwd}(x, t)$ 和 $u_{bwd}(x+u_{fwd}, t+1)$。理论上 $u_{fwd} + u_{bwd} \approx 0$。如果两者之和远大于 0，说明该点在下一帧找不到对应或已被遮挡。
  6. 抖动敏感性：不能保持低秩。矩阵秩对列的对齐非常敏感。即使是 1 像素的错位，也会导致本来相同的列变得线性无关，导致秩急剧增加。$S$ 会包含大量的“边缘残差”（看起来像物体轮廓的线条），因为那是对齐误差最大的地方。

7. 常见陷阱与错误 (Gotchas)

7.1 "Warping" 带来的数值噩梦

在金字塔实现中，你需要根据当前 $u$ 对图像进行 Warping（重采样）。

  • 陷阱：直接使用最近邻插值（Nearest Neighbor）。这会导致目标函数不连续，优化器（如梯度下降或对偶方法）无法收敛，因为梯度处处为0或无穷大。
  • 正解：必须使用双线性（Bilinear）或双三次（Bicubic）插值。更重要的是，在计算光流的数据项梯度时，要包含 Warp 操作的线性化项。

7.2 导数的离散化

  • 陷阱：计算 $I_t$ 时简单的用 I[:,:,1] - I[:,:,0]，计算 $I_x$ 时用 I[:,1:] - I[:,:-1]。这两者在空间位置上没有对齐（中心偏了 0.5 像素）。
  • 正解：使用中心差分或类似 Sobel 的算子，并确保 $I_x, I_y$ 和 $I_t$ 是在同一个时空位置采样的（通常取两帧的平均位置）。不一致的导数计算会导致显著的系统性误差（Bias）。

7.3 RPCA 的内存溢出

  • 初学者常试图一次性将 1 小时的视频读入内存做 RPCA。
  • 现实：1小时 1080p 视频解压后可能有几百 GB。SVD 更是 $O(N^3)$ 消耗。
  • 策略：必须使用在线算法（Online RPCA/Stochastic RPCA），或者将视频分块（Temporal Batching），例如每 200 帧做一次处理。

7.4 颜色通道处理

  • 光流通常在灰度图上计算。
  • 陷阱：直接对 RGB 三通道分别算光流，然后取平均。
  • 后果：三个通道的噪声和孔径问题表现不同，导致结果不一致。
  • 建议：使用多通道数据项联合优化 $\sum_{c} |I_c(x+u) - I_c(x)|$，共享同一个运动场 $u$。