MPEG-4 二值形状编码

1990 年代中期，MPEG 正在制定下一代视频编码标准——MPEG-4 Visual。与 MPEG-1/2 将整幅矩形帧作为编码单元不同，MPEG-4 的核心愿景是基于对象的编码（Object-Based Coding）：一段视频被分解为若干 Video Object (VO)，每个 VO 在每一帧形成一个 Video Object Plane (VOP)，包含三类独立信息——纹理、运动和形状 #Ostermann-1997。

这一设计的目标是革命性的：解码端可以操作和合成视频中的对象——点击、拖拽、替换背景、分层渲染。为了支持这些功能，MPEG-4 需要一种高效的方法来编码任意形状的二值轮廓——即标记每个像素"属于对象"还是"不属于对象"的信息。

1995 年 11 月，MPEG 收到了 12 份形状编码提案 #Ostermann-1997。此后半年内，更多方法被提出——有些基于已有提案的改进，有些则是全新的设计。在竞争性评估环境中，多个算法的编码效率提升了 50% 以上。到 1997 年 4 月的 Bristol MPEG 会议时，竞争阶段结束，五种方法被保留为最终候选。

本文作者 Jörn Ostermann（AT&T Labs - Research）是 MPEG-4 形状编码标准化的核心推动者。他在 PCS 1997 上发表了这篇论文，系统回顾了五种方法的技术细节、评估过程和最终选择 CAE 的决策依据 #Ostermann-1997。虽然论文只有短短三页，但它记录了视频编码史上一个重要里程碑——第一个支持形状编码的国际标准的诞生过程。

要理解形状编码的设计空间，我们需要先明确 MPEG-4 的 VOP 数据模型。论文指出，MPEG-4 区分了三种类型的 Video Object #Ostermann-1997：

形状编码的基本约束

论文明确了一个关键设计前提：形状编码器可以共享运动信息与纹理编码器 #Ostermann-1997。也就是说，形状的运动矢量不需要独立编码——它可以作为纹理运动矢量的增量来传输。这一约束使得形状编码可以复用视频编码器的运动估计框架，大幅降低额外开销。

另一个隐含约束是：形状编码必须支持无损、主观无损和有损三种模式 #Ostermann-1997。有损模式下，编码器可以通过下采样来降低码率——将 16×16 的宏块下采样为 8×8 或 4×4，编码后再上采样恢复。这种Conversion Ratio (CR) 机制是有损形状编码的核心率控手段。

论文将五种候选方法归为三大类别 #Ostermann-1997：

graph TB
  subgraph "MPEG-4 二值形状编码方法分类"
      A[Binary Shape Coding] --> B[Bitmap-Based
直接编码像素位图]
      A --> C[Contour-Based
编码对象轮廓]
      A --> D[Implicit
隐含在纹理中]
      B --> B1[MMR
Modified Modified READ]
      B --> B2[CAE
Context-based Arithmetic Encoding]
      C --> C1[Vertex-Based
多边形逼近]
      C --> C2[Baseline-Based
基线距离编码]
      D --> D1[Chroma-Keying
色度键控]
  end

3.1 Vertex-Based：多边形逼近与迭代顶点插入

Vertex-based 方法属于轮廓编码——它不直接编码像素位图，而是编码对象的外轮廓。具体做法是用多边形逼近（polygon approximation）来近似轮廓：对于有损编码，用直线段连接一组顶点形成多边形；对于无损编码，多边形退化为链码（chain code） #Ostermann-1997。

顶点选择采用迭代插入策略：

1. 找到形状的最长轴，用两个端点作为初始多边形
2. 对每条多边形边，检查近似误差是否在容差 \(d_{max}^*\) 范围内
3. 如果超出容差，在最大误差点插入新顶点
4. 重复检查所有边，直到全部满足容差约束

图 1：迭代多边形逼近。白色区域为原始形状，三角形为当前多边形近似。箭头指向的边界处距离超过阈值 \(d_{max}^*\)，将在该点插入新顶点。（来自论文 Figure 1）

形式化地，多边形近似 \(\hat{S}\) 与原始形状 \(S\) 之间的最大距离定义为：

当 \(d_{max} > d_{max}^*\)（给定阈值）时，在最大误差点插入新顶点。Vertex-based 方法有一个独特优势：可以通过设定 \(d_{max}^*\) 来直接控制最大形状近似误差，且顶点的位置允许对局部误差进行精细调节 #Ostermann-1997。对于时域预测，每个顶点可以分配一个运动矢量，并支持顶点的删除和添加以适应形状的时域变化。

但 Vertex-based 的编码效率高度依赖编码器实现——"选择合适顶点的艺术"是这种方法性能差异的主要来源 #Ostermann-1997。

3.2 Baseline-Based：基线投影与转折点编码

Baseline-based 方法同样编码轮廓，但采用不同的参数化方式。它将形状放入二维坐标系中，使得形状在 x 轴上的投影最长——这条 x 轴称为基线（baseline） #Ostermann-1997。

编码时，轮廓被逆时针采样。相邻采样点的 x 坐标通常单调递增或递减——方向发生变化的点称为转折点（turning points）。编码流程为：

1. 首先传输所有转折点的地址
2. 在相邻转折点之间，沿 x 轴周期性采样
3. 对每个采样点的 y 坐标（到基线的距离）做差分编码，使用固定算术编码器

时域预测采用全局运动补偿 #Ostermann-1997。Baseline-based 方法在 intra 模式下提供了最好的主观质量，但编码效率在 inter 模式下不如 Vertex-based #Ostermann-1997。

3.3 MMR：来自传真标准的二维游程编码

Modified Modified Reed (MMR) 是一种基于宏块的位图编码器 #Ostermann-1997。与前面两种轮廓方法不同，MMR 直接编码二值位图，使用的是传真 G3 标准中的 MMR 码——这是一种二维游程编码，利用相邻行的相关性来提高压缩效率。

MMR 的率控机制通过下采样实现：形状宏块（16×16）可以被下采样为 8×8（CR=2）或 4×4（CR=4）。编码器尝试用最高的 CR 来编码，只要形状近似误差在容许范围内。解码器解码后根据 CR 上采样恢复到原始分辨率 #Ostermann-1997。

对于时域预测，当前宏块的形状从前一帧通过运动补偿来预测。运动矢量在二值形状信号上做全搜索估计，并编码为纹理运动矢量的增量 #Ostermann-1997。

3.4 CAE：上下文自适应算术编码（MPEG-4 最终选定）

CAE (Context-based Arithmetic Encoding) 与 MMR 的区别仅在于形状信息的编码方式——时域预测、率控和上/下采样机制完全相同 #Ostermann-1997。CAE 的核心创新是将二值形状视为一个马尔可夫信源（Markov source），用上下文模板定义状态，再用算术编码器编码状态转移。

Intra 模式：10-pel 上下文模板

在帧内模式下，CAE 使用一个由 10 个像素组成的上下文模板来预测当前像素的形状值 #Ostermann-1997。这些像素来自当前像素的因果邻域（已经编码的像素），包括上方和左方的像素。模板可以跨越宏块边界——向上延伸最多 2 个像素，向左也延伸最多 2 个像素。

图 2：CAE 上下文模板。左图为 Intra 模式（10 个 x 标记的已编码像素定义当前像素 o 的状态），右图为 Inter 模式（Previous Frame + Current Frame 的上下文组合）。（来自论文 Figure 2）

10 个上下文像素的每一种组合对应一个状态（state），共有 \(2^{10} = 1024\) 个可能的状态。对每个状态，算术编码器维护一个概率估计 \(P(x=1 | \text{state})\)，并根据实际编码的像素值更新这个概率。形式化地，当前像素 \(x_t\) 的编码概率取决于上下文 \(c_t\)：

其中 \(p_1, \ldots, p_{10}\) 是模板中 10 个已编码像素的值，\(f\) 是算术编码器的概率模型。这种将形状建模为马尔可夫信源的方法，使得 CAE 能够自适应地学习形状的局部统计规律——边界区域和内部区域的概率分布截然不同，上下文模板让编码器自动区分这两种情况。

Inter 模式：9-pel 上下文模板

在帧间模式下，CAE 使用 9 个像素的上下文模板 #Ostermann-1997。其中 5 个像素来自运动补偿后的前一帧形状，4 个像素来自当前帧的运动补偿预测误差。这意味着 Inter 模式的上下文不仅利用了空间相关性（通过预测误差的邻域），还利用了时间相关性（通过运动补偿后的参考形状）。

运动矢量的估计方式与 MMR 相同：在二值形状信号上做全搜索，编码为纹理运动矢量的增量 #Ostermann-1997。

3.5 Chroma-Keying：色度键控的隐式编码

Chroma-Keying 的灵感来自影视行业的蓝幕/绿幕技术 #Ostermann-1997。对象在拍摄时被放置在单色背景上，背景颜色必须位于对象纹理色空间之外（通常使用高饱和度颜色）。整幅图像（含背景）用常规编码器（MPEG-4 视频的全帧模式）编码，同时传输 chroma-key（背景颜色）。

解码端解码图像后，根据色度判断：颜色接近 chroma-key 的像素被认为是透明（对象外），其余像素属于对象 #Ostermann-1997。这种方法的关键特点是形状信息隐含在纹理中——通常由子采样的色度信号携带。

Chroma-Keying 的优势是计算和算法复杂度极低，尤其是当形状边界宏块的位置已知时，形状提取只需在这些少量宏块上进行。但缺点也很明显：不支持无损编码（纹理量化会导致形状误差），且无法在不解码整帧的情况下提取对象形状 #Ostermann-1997。

评估过程首先在轮廓编码器中选出最优方案，再在位图编码器中选出最优方案，最后在两者之间做最终抉择 #Ostermann-1997。Chroma-Keying 因复杂形状的拓扑不稳定被排除——但对于 head-and-shoulders 等简单对象，它在主观质量上表现出色，仅有轻微的边缘色溢 #Ostermann-1997。

轮廓路线：Vertex 胜出 Baseline

在轮廓编码器中，Vertex-based 在 inter 模式的编码效率和计算复杂度上均优于 Baseline-based #Ostermann-1997。但值得注意的是，Baseline-based 在 intra 模式下提供了最好的主观质量 #Ostermann-1997。另一个实际因素是：Baseline-based 只有一份独立实现，而其他所有方法都有两份独立实现——这在标准化评估中是一个可靠性隐患。

位图路线：CAE 胜出 MMR

在位图编码器中，CAE 在 intra 和 inter 的无损与有损编码中均优于 MMR #Ostermann-1997。唯一例外是大误差场景——当形状近似误差很大时，MMR 比 CAE 略有优势 #Ostermann-1997。

最终对决：CAE vs Vertex-Based

论文 Table 1 给出了 CAE 与 Vertex-based 在 1997 年 4 月 Bristol MPEG 会议上的对比快照 #Ostermann-1997。以下是从论文原文提取的对比数据：

从数据中我们可以看到：两种方法各有优势——Vertex-based 在 intra 无损场景下节省 7.8% 码率，而 CAE 在 inter 无损场景下节省 20.5%。主观比较中，Vertex-based 略有优势，因为轮廓编码能提供平滑的形状边界（尤其是直线段），而位图编码在低码率下产生块状边界 #Ostermann-1997。

然而，最终选择 CAE 的决定性因素是硬件实现复杂度 #Ostermann-1997：

这个决策揭示了一个重要的工程原则：在标准化过程中，硬件友好性往往比纯粹的编码效率更重要。CAE 虽然在 intra 场景不如 Vertex-based，但它的块基结构与视频编码器的宏块结构天然对齐，硬件实现成本低、延迟小。

1997 年 4 月 Bristol 会议后，竞争阶段结束，MPEG-4 形状编码工作组开始集中改进已选定的 CAE 编码器 #Ostermann-1997。在 1997 年 4 月到 7 月之间，最重要的改进是开发了形状自适应上采样滤波器（Shape Adaptive Upsampling Filter）。

问题：下采样导致的块状边界

如前所述，CAE 的率控机制允许将 16×16 的形状宏块下采样为 8×8（CR=2）或 4×4（CR=4）后再编码。解码端需要将下采样后的形状上采样恢复到原始分辨率。简单的上采样（如最近邻或双线性插值）会产生块状形状表示——这是位图编码相比轮廓编码的主要视觉劣势 #Ostermann-1997。

解决方案：自适应平滑滤波

新的上采样滤波器能够在恢复形状时提供平滑的边界，从而抵消位图编码相比轮廓编码的视觉劣势 #Ostermann-1997。这一滤波主要在intra 模式下应用，因此它改善的是有损 intra 形状的主观质量。

一个关键约束是：由于纹理编码依赖于编码后的形状，编解码端必须使用相同的上采样滤波器 #Ostermann-1997。这确保了编码端的形状决策与解码端的形状重建一致，避免纹理-形状不匹配导致的编码误差。

MPEG-4 形状编码的历史定位

MPEG-4 是第一个覆盖形状编码的国际标准 #Ostermann-1997。论文在结论中明确指出：考虑到形状编码是图像处理中一个相对新颖的领域，需要更多研究才能完全理解其各个方面。MPEG-4 将作为基线，新的形状编码技术需要与它竞争 #Ostermann-1997。标准于 1998 年 11 月最终确定 #Ostermann-1997。

为何未被广泛采用？

尽管 MPEG-4 形状编码在技术上是一个里程碑，但它在实际应用中并未被广泛采用。主要原因包括：

CAE 思想的传承

虽然 MPEG-4 的对象编码范式未被后续标准继承，但 CAE 的核心思想——上下文自适应算术编码——却以另一种形式延续。H.264/AVC 引入了 CABAC (Context-Adaptive Binary Arithmetic Coding) 作为熵编码器，其设计直接继承了 CAE 的"上下文模板 + 算术编码"范式，只是应用对象从形状比特流扩展到了所有语法元素。

形状编码的当代复兴

形状编码并非真正消亡——它在新的技术背景下以新形态复活：

• V-PCC Occupancy Map：MPEG 的点云压缩标准中，occupancy map 本质上是一张二值形状图，用链码编码取代 HEVC #Ostermann-1997
• 语义图压缩：CC-SMC 和 ECC 将链码扩展到语义分割图的压缩，在二值图压缩中展现持续生命力
• 分割辅助编码：SAIP (Seg-VVC) 利用编解码端同步推理的分割 mask 辅助帧间预测——从"传输轮廓"进化到"推理轮廓"
• 语义条件传输：DiSCo 和 MMSD 将轮廓/边缘图作为极低码率的语义条件信号传输，用生成模型在解码端重建

第一课：标准化中的工程权衡

MPEG-4 形状编码的标准化过程是一个经典的工程决策案例。CAE 并非在所有场景下都最优——它在 intra 无损场景下比 Vertex-based 高 7.8% 码率。但它被选中的原因是硬件友好性：规则内存访问、片上解码、低延迟。这告诉我们：在标准化中，"最优"不等于"效率最高"，而是在效率、复杂度、可实现性之间找到最佳平衡。

第二课：分割是形状编码的瓶颈

MPEG-4 形状编码的商业失败，根本原因不在编码技术本身，而在于前端分割。1990 年代没有可靠的视频对象分割工具。今天，SAM (Segment Anything Model) 等基础模型的出现在根本上改变了这一局面——自动分割的质量已经可以达到实用水平。这意味着 MPEG-4 的"对象编码"愿景在 25 年后终于有了技术基础。

第三课：上下文建模的有效性

CAE 将二值形状建模为 10 状态的马尔可夫信源，用上下文模板捕获局部空间相关性。这一思想被 CABAC 继承并发展为现代视频编码的标配熵编码器。从 CAE 的 10-pel 模板到 CABAC 的概率更新机制，我们看到上下文自适应建模是视频编码中经久不衰的有效范式——无论是 1997 年的二值形状，还是 2020 年代的神经视频编码，上下文建模都是压缩效率的核心来源。