运动补偿双链码

在 MPEG-4 二值形状编码，五种方法的较量与 CAE 的胜出">MPEG-4 二值形状编码，五种方法的较量与 CAE 的胜出 里我们看到，1997 年 MPEG-4 形状编码的标准化以 CAE（Context-based Arithmetic Encoding）胜出告终——它在帧间无损场景比 Vertex 低 20.5% 码率，更重要的是块基结构硬件实现无需随机访问外部内存 #Ostermann-1997。CAE 因此进入 MPEG-4 Verification Model 7.0，与 JBIG 标准（ITU-T T.82）同源 #Brady-1997。

但标准化定下的是「工程最优」，而非「码率最优」。CAE 是 block-based 方法——把二值形状当一张二值位图，按宏块 raster scan 逐像素用 10-pel 上下文模板做算术编码 #Brady-1997。块基的代价是：块尺寸转换处会出现视觉上刺眼的 staircase effect（阶梯效应） #Brady-1997，且像素级失真难以精确控制。而 contour-based 阵营——沿对象边界用链码压缩——天然没有阶梯效应、失真定义清晰、还能在「平滑轮廓 + 帧间强相关」的视频上榨出更多时域冗余。问题是：1997 年的 contour 方法在码率上还没赢过 CAE。

本文正是 contour 阵营五年后的一次系统反扑。Lu & Pearlman（时在 Lucent Technologies 与 RPI，由 NSF Grant EEC-981276 资助）在 2002 年 TCSVT 上提出 Motion Compensated Two-link Chain Coding：用 6-connected contour lattice 让轮廓更平滑、用 two-link chain code 让一条码字表示两条链、用 affine 全局运动补偿处理 zoom/rotation——三重创新叠加后，在 MPEG-4 测试序列 Akiyo/Weather 上，intra 与 inter 模式码率在多数配置下低于 CAE（intra 仅一处 QCIF 微输）#Lu-Pearlman-2002。

通讯作者 William A. Pearlman 是图像/视频编码权威、SPIHT（Set Partitioning in Hierarchical Trees）的共同发明人 #Pearlman-Said-1996；一作 Zhitao Lu 是 Pearlman 指导的 RPI 博士（2000 年博士论文做小波编码），本文是其「形状序列编码」副方向的成果 #Lu-Pearlman-2002。论文另有一个会议先发表版本（VCIP 2002, SPIE vol. 4671, pp. 356-362，DBLP key conf/vcip/LuP02）。

要理解 Lu & Pearlman 的三件套为什么这么设计，得先看 2002 年 contour-based 形状编码卡在哪。这个问题的输入是一段二值形状序列 \(\{I_n\}\)——每帧是一张 label image（1=物体像素，0=背景），编码目标是把每帧的物体轮廓压成紧凑比特流，lossless 重建或可控失真 #Lu-Pearlman-2002。

contour 阵营的祖师爷是 Freeman chain code（1961）——用 8 个方向码逐 link 记录轮廓相对位移 #Freeman-1961。它的第一个痛点：方向序列太「毛糙」，熵降不下来。Freeman 链码定义在 image lattice（像素格）上，当物体边界呈对角方向时，轮廓表现为 left, right, left, right… 的锯齿（方向交替），熵编码器面对这种高变动序列效率很低——理论上界 \(\log_2 8 = 3\) bits/link。Eden & Kocher 1985 用 4-connectivity 约束把熵降到 1.27 bits/link #Lu-Pearlman-2002，但还不够。

第二个痛点：帧间运动补偿只会处理平移。Gu & Kunt 1995 给链码加上了「运动补偿 + 分段」框架——用全局/局部平移运动矢量从前帧预测当前帧轮廓，只对「预测失败段」做链码编码 #Gu-Kunt-1995。这个分段范式（global success / local success / motion failure）成为后续 contour 形状编码的标准操作。但它假设轮廓做刚体平移运动——「works well when the motion is translational, but does not work well when the motion is more complex, such as zooming and/or rotation」#Lu-Pearlman-2002。一旦物体 zoom 或旋转，平移模型预测大面积失败，失败段被链码重新编码，码率立刻回升。

Lu & Pearlman 的回答是三件套对两个痛点各打一记：6-connected contour lattice + majority filter + two-link chain code 解决痛点 A（实测 intra 把熵压到 1.19 bits/link 理论下界、0.84-0.95 bits/link 实测 #Lu-Pearlman-2002）；affine 全局运动模型 + corner matching + LMS 鲁棒估计 解决痛点 B（同一合成 zoom/rotation 场景，affine 正确预测 408/514 像素 vs 平移模型仅 129/514 #Lu-Pearlman-2002）。

在进入方法细节前，先把整条编码 pipeline 在脑子里建起来——后面每个模块都是 pipeline 上的一环。

本文的编码端是一个清晰的「轮廓 → 平滑 → 运动预测 → 分段 → 分段编码」pipeline，inter 模式完整跑 6 步，intra 模式跳过运动预测只跑前后两端 #Lu-Pearlman-2002。

graph TB
  A[原始 label image] --> B[1. 轮廓提取
6-connected contour lattice
top/left half-pixel 位置]
  B --> C[2. Majority filter
size-1 结构元, FIFO queue]
  C --> D{Intra/Inter?}
  D -->|Intra| H[6. two-link chain code
+ 12-context 算术编码]
  D -->|Inter| E[3. 全局运动估计
translational 或 affine]
  E --> F[4. 全局运动补偿
→ global success/failure 段]
  F --> G1[5. 失败段局部运动搜索
→ local success/failure 段]
  G1 --> H
  H --> I[比特流]

3.1 6-connected contour lattice：让轮廓先「平滑」

链码的效率，根子上取决于「轮廓有多平滑」。Lu & Pearlman 的第一步创新，是把轮廓定义从 image lattice（像素格）挪到 6-connected contour lattice——一种半像素位置网格 #Lu-Pearlman-2002。

具体说，轮廓点只定义在两类位置上：top position（两个垂直邻接的 image pixel 标签不同时，它们之间的「上边」中点）和 left position（两个水平邻接像素标签不同时的「左边」中点）。vertex position 不用。这样定义的妙处在于：lattice 上的轮廓 link 数与 image lattice 表示完全相同，但因为定义在半像素处，每个 top/left 位置只有 6 个邻居（而非 8 个），构成 6-connected 图。

图 1（论文 Fig.3）：contour lattice 上每个 top/left 位置有 6 个邻居，构成 6-connected 图。

为什么 6-connected 比 8-connected（image lattice）更平滑？看对角方向的边界就懂：image lattice 上的对角轮廓是 left, right, left, right… 锯齿（方向交替），而 contour lattice 上是连续的 diag, diag, diag…（单一方向）。方向序列更平滑 → 熵更低 #Lu-Pearlman-2002。

图 2（论文 Fig.4）：同一段对角边界，image lattice 是锯齿（方向交替），contour lattice 是连续 diag。平滑的方向序列让后续熵编码受益。

额外的好处：contour lattice 还能处理 1-pixel-wide 的细窄物体——这种物体在 image lattice 上根本无法形成闭合轮廓，但在 half-pixel lattice 上可以 #Lu-Pearlman-2002。

3.2 Majority filter：把方向可能性砍到 2-3 种

光有平滑的 lattice 还不够。Lu & Pearlman 在编码前再施加一道 majority filter（size-1 结构元，用 FIFO queue 实现以避免原算法 [15] 的迭代 #Lu-Pearlman-2002）对轮廓做平滑，效果近似 perfect 8-connectivity 约束。这道约束的威力在于：它直接砍掉了大部分「不可能」的 link 后继方向。

图 3（论文 Fig.5）：majority filter 的结构元及其平滑效果。FIFO queue 实现避免了原算法的迭代。

经过 majority filter 后，从一个 last contour point \(p_L\) 出发到 current point \(p_c\) 的 6 个可能方向里（2 个水平 + 4 个对角），真正可能的后继方向被压缩到：

• 当前 link 为 水平/垂直方向时，下一条 link 仅 3 种可能；
• 当前 link 为 对角方向时，下一条 link 仅 2 种可能。

等概率假设下，这套约束把链码的信息熵下界压到：

对比 Freeman 8-direction chain code 的理论上界 \(\log_2 8 = 3\) bits/link，这是数量级的差距 #Lu-Pearlman-2002。推导逻辑链很清楚：6-connected lattice 有 6 方向 → majority filter 消除不可能 link → 水平/垂直当前 link 只剩 3 种下一条方向、对角只剩 2 种 → 等概率下熵降至 1.19 → 再叠加 two-link + 算术编码进一步压到 0.84-0.95 bits/link（实测）。

3.3 Two-link chain code：一条码字表两条链

有了平滑约束打底，核心创新 two-link chain code 才能发力。它的思路直白：既然相邻两条 link 高度相关，那就用一个码字同时表示两条连续 link，以「上一条 link 方向」为上下文 #Lu-Pearlman-2002。

图 4（论文 Fig.8）：two-link chain code——一个码字表示两条相邻 contour link。

码字设计分两类（取决于上一条 link 方向）：

• 上一 link 为 水平/垂直：7 种两 link 组合 → 码字 0-6；
• 上一 link 为 对角：5 种两 link 组合 → 码字 0-4。

再加上 2 条 dashed link：当轮廓段是对角直线时，一个码字可以表示 3 或 4 条 link，进一步降低直线段的比特率。在不接熵编码器的情况下，two-link chain code 的码率已能压到 \(\leq 1.5\) bits/link #Lu-Pearlman-2002。

熵编码用的是 context-based arithmetic encoder，上下文 = 上一条 contour link 的方向，共 12 个 context（6 个始于 top position + 6 个始于 left position #Lu-Pearlman-2002）。每个 codeword 的概率在编码过程中自适应更新——这是 CAE「上下文 + 算术编码」范式在 contour 侧的镜像（CAE 是在像素块上做，本文是在链码符号上做，思想同源、对象不同）。

图 5（论文 Fig.9）：6 个 contour context（起始于 left position）及其链码。配合起始于 top position 的另外 6 个，共 12 个 context。

3.4 Affine 全局运动：从平移到 6 参数仿射

解决痛点 B（运动补偿只认平移）需要更强的全局运动模型。Lu & Pearlman 给出 6 参数 affine 模型 #Lu-Pearlman-2002：

其中 \((x,y)\) 是前帧轮廓点坐标，\((\hat{x},\hat{y})\) 是当前帧预测坐标。\(a_1,a_2,a_4,a_5\) 捕获 zoom/shear/rotation，\(a_3,a_6\) 捕获平移——对比 translational 模型仅 2 参数，affine 能建模复杂全局运动。估计流程分三步（见论文 Fig.12 流程图）：

图 6（论文 Fig.12）：contour 的 affine 运动估计流程：corner detection → corner matching → LMS 参数估计。

再转成 matching score \(S(i,j) = (1+C(i,j))^{-1}\)，归一化得初始匹配概率 \(P(i,j)\)。然后用三个 supporting descriptors（邻接角点几何匹配 \(q_1\)、邻域运动矢量一致性 \(q_2\)、参考角点网络 \(q_3\)）构造 update factor \(Q(i,j)\)，做 relaxation 迭代更新匹配概率 #Lu-Pearlman-2002：

真匹配对的概率被放大、伪匹配对的概率被压缩，收敛后超阈值的对判为 matched。

3.5 双模式切换：10 bits vs 60 bits 的权衡

affine 强归强，但它要传 6 个参数 × 每参数 10 bits = 60 bits 的全局运动头，而 translational 只需 10 bits #Lu-Pearlman-2002。简单运动场景下硬上 affine 是浪费。所以编码器用 1-bit flag在两种模式间自适应切换：先尝试 translational，只有当非平移运动显著、正确预测的轮廓像素数偏低时，才切到 affine #Lu-Pearlman-2002。这是码率与表达力之间的工程权衡。

必须先说清一件事：本文是 2002 年的传统信号处理方法，没有机器学习意义上的训练阶段。所以本节不写训练数据/优化器/学习率（统统不适用），而是按 read-article 的训练配置披露表规范，逐项标注「不适用/未披露」，让读者一眼看到这篇论文缺了什么、哪些是方法本身的参数。

4.1 未披露的关键参数

这张表暴露了本文可复现性的主要缺口。下面这些超参数论文均未给数值，复现需要大量调参 #Lu-Pearlman-2002：

• 运动估计搜索范围（搜索窗口大小）——原文未给；
• motion success segment 最小长度阈值——防止过短 success 段（overhead > chain code cost），但阈值数值未给；
• corner detection 曲率阈值、期望 corner 数——原文只给算法，未给值；
• corner matching 的 M1/M2、匹配概率阈值——原文未给；
• cost 权重 \(w_L, w_\sigma\)——原文未给。

此外，corner detection 依赖外部 TargetJr package #Lu-Pearlman-2002 的 curvature/corner 算法（黑盒），可复现性进一步受影响。chain code 部分（6-connected lattice + two-link + 12-context 算术编码）描述完整、Fig.8-10 给出全部 12 context 的码字图，可高度复现；affine ME 部分因超参数缺失和外部包依赖，复现门槛高得多。

解码是编码的逆过程，但 contour-based 方法的解码端有个 block-based 没有的特点：它要维护一个 Contour Memory，保存前一帧的已解码轮廓，供 inter 模式的运动补偿预测使用 #Lu-Pearlman-2002。

整条比特流的语法（论文 Fig.19 复刻如下）是一个清晰的「头部 + 分段循环」结构：

图 7（论文 Fig.19）：比特流语法——全局运动 flag + 参数 + start point + 分段循环。

解码端的流程因此很直接：先熵解码拿全局运动 flag + 参数 + start point，然后逐段解析（2 bits type 决定重建方式），最后用 Contour Reconstructor 把所有段拼成闭合轮廓，转回 label image #Lu-Pearlman-2002。inter 模式下，运动 success 段只传了 length（+ 运动矢量），直接从前帧 Contour Memory 里平移/仿射复制过来；只有 motion failure 段才走 chain decoding。

图 8（论文 Fig.18）：inter 模式 contour coding 的编码端框图，运动补偿预测 + 分段编码。

这种「success 段只传矢量、failure 段才链码」的策略，正是本文 inter 模式码率能大幅低于 intra 的原因——运动可预测的部分几乎不花 bits，只有真正预测失败的部分才付出 chain code 的代价。实测 Akiyo QCIF 从 intra 的 0.89 bits/link 降到 inter 的 0.35 bits/link，降幅约 61% #Lu-Pearlman-2002。

论文实验在两个 MPEG-4 shape test sequence 上做：Akiyo 与 Weather，QCIF 与 CIF 两种格式，30 fps，序列总长 300 帧 #Lu-Pearlman-2002。基线是 MPEG-4 VM7.0 里的 CAE（intra + inter 主 baseline）和 GPSC（Kim/Bovik/Evans 2000，inter 第二 baseline #Kim-Bovik-Evans-2000）。失真度量用 motion success/failure 段距离定义（段内最大欧氏距离为 0 即成功），本实验配置下为 lossless。

6.1 仿射 vs 平移：谁解决了 zoom/rotation

第一个实验验证 affine 模型的必要性。用 Akiyo frame 0 合成一个 3.2° 旋转的 affine 运动（参数 [0, -0.055, 0, 0.055, 0, 0]），测两种模型能正确预测多少 contour pixel：

这个数字说明一切：平移模型在该旋转场景下失败率约 75%（仅 129/514），affine 模型失败率约 21%（408/514）——3.2 倍的提升 #Lu-Pearlman-2002。这正是引入 affine 的全部理由。（配套的 Table I 验证 affine 参数估计精度：合成测试含两组——translational 运动矢量 (-5,5) 与 affine 旋转 [0,-0.055,0,0.055,0,0]。affine 旋转场景各参数均接近真值；translational 场景用 affine 模型估计时 a6 估计 3.90 vs 真值 5 偏差较大，作者仅称「fairly accurate」。注意该表 OCR 行列有错位，需以原 PDF 为准。）

6.2 Intra 模式：two-link chain 的码率

第二个实验测 intra 模式的链码效率。four 配置（Akiyo/Weather × QCIF/CIF）的 bits/link 全部落到 0.84-0.95，远低于理论熵下界 1.19 之上的 Freeman 码 #Lu-Pearlman-2002：

6.3 vs CAE：intra 模式全面占优（一处例外）

intra 模式与 CAE 正面对比（bits/pixel）。proposed 在多数行码率低于 CAE：

注意 Weather QCIF frame 0 是唯一一处 proposed（0.0574）略高于 CAE（0.05581）的配置 #Lu-Pearlman-2002——所以不能笼统说「全面碾压 CAE」，在 QCIF 这种轮廓占比大、序列小的情况下链码方法偶有翻车。frame 30 行是 Table IV 中唯一有 Baseline-based [7] 对比数据的一行（其余行 baseline 列均 N/A，对比数据稀疏），proposed 在该行同时低于 CAE 与 baseline。

6.4 Inter 模式：码率节省 4.95%-9.64%

inter 模式是本文的重头戏——运动补偿 + 分段策略把码率压到 0.35-0.67 bits/link，比 intra 再降约 22%-61%（Akiyo QCIF 降幅最大，Weather CIF 降幅最小）。与 CAE/GPSC 的对比（bits/frame）：

30 fps 上 proposed 比 CAE 省 15 bits/frame（303→288，约 -4.95%）；10 fps 上比 CAE 省 26 bits/frame（382→356，约 -6.81%）、比 GPSC 省 38 bits/frame（394→356，约 -9.64%）#Lu-Pearlman-2002。10 fps 比 30 fps 节省更多，是因为低帧率下帧间运动更大、affine 运动补偿的优势更明显。

把本文放进 MPEG-4 形状编码的全局图景里，它的位置很清楚：这是 contour-based 阵营对标准化 CAE 的一次码率反扑——用 6-connected lattice + two-link chain + affine 运动补偿三件套，第一次在 MPEG-4 测试集上让链码方法在码率上全面（除一处 QCIF 微输）超越 block-based 的 CAE。

7.1 为什么赢了码率却没进标准

答案和 1997 年 CAE 胜出的逻辑完全一致，只是反过来了：CAE 胜出标准化，靠的不是码率，是硬件友好——块基结构与纹理编码共享 macroblock 流水线、片上解码无需随机访问外部内存 #Ostermann-1997。而本文的 contour-based 方案有三个工程硬伤：

• 与块流水线不对齐：它要独立的轮廓提取/跟踪链路，随机访问与并行性差，无法复用纹理编码的 macroblock 架构；
• 处理延迟高：需整条轮廓 + 前帧轮廓才能编码/解码，不像 CAE 那样 macroblock-by-macroblock 低延迟；
• 复杂度高：corner detection + matching + LMS 估计 + 双模式切换，远比 CAE 的「10-pel 上下文 + 算术编码」复杂。

所以即便码率更低，它也因「与纹理块流水线不对齐、硬件实现成本高」而留在学术圈。这是 contour-based 形状编码方法的典型命运——本站 MoRIC，区域化隐式神经编解码与自适应链码轮廓压缩">MoRIC，区域化隐式神经编解码与自适应链码轮廓压缩 的 MoRIC 也印证了这一点：「shape-based coding 在视频编码界研究了几十年却从未真正落地」。

7.2 方法学上的遗产

抛开标准化命运，本文在方法学上留下了三笔遗产，至今仍在被继承：

• 链码演进的关键一站：从 1961 Freeman 链码 → 本文 2002 的 two-link MC-TLCC（6-connected + 一码两链 + dashed 直线）→ 2025 MoRIC 的 C* 自适应步长链码，本文是这条线上「视频时域 + 连通性约束」的重要分支节点；
• corner matching + LMS 流水线：affine 全局运动估计里的「corner detection + relaxation matching + 鲁棒回归」流水线，至今仍是非刚性轮廓对应问题的标准组件；
• 「上下文 + 算术编码」在 contour 侧的镜像：CAE 在像素块上做 10-pel 上下文算术编码，本文在链码符号上做 12-context 算术编码——同一个思想在不同载体上的两次实现，是 Huf-RLC 与熵编码">Huf-RLC 与熵编码「从 CAE 到 CABAC」脉络在 contour 侧的注脚。

7.3 局限与可复现门槛

作为读者要带走的批判性认识：majority filter 是有损的（intra 严格 lossless 需额外处理 filter 引入的偏差，原文未讨论）；affine 模型无法建模非刚性大形变（如人体关节大幅运动），此时仍需 fallback 到 translational 或纯链码；超参数（corner 阈值、M1/M2、cost 权重）原文未给值，corner detection 依赖外部 TargetJr 包，复现门槛高 #Lu-Pearlman-2002。实验规模也有限——仅 Akiyo + Weather 两序列，缺少高速运动/大形变序列的验证。