2025-11-25T03:34:17.382844

INT-DTT+: Low-Complexity Data-Dependent Transforms for Video Coding

Fernández-Menduiña, Pavez, Ortega et al.
Discrete trigonometric transforms (DTTs), such as the DCT-2 and the DST-7, are widely used in video codecs for their balance between coding performance and computational efficiency. In contrast, data-dependent transforms, such as the Karhunen-Loève transform (KLT) and graph-based separable transforms (GBSTs), offer better energy compaction but lack symmetries that can be exploited to reduce computational complexity. This paper bridges this gap by introducing a general framework to design low-complexity data-dependent transforms. Our approach builds on DTT+, a family of GBSTs derived from rank-one updates of the DTT graphs, which can adapt to signal statistics while retaining a structure amenable to fast computation. We first propose a graph learning algorithm for DTT+ that estimates the rank-one updates for rows and column graphs jointly, capturing the statistical properties of the overall block. Then, we exploit the progressive structure of DTT+ to decompose the kernel into a base DTT and a structured Cauchy matrix. By leveraging low-complexity integer DTTs and sparsifying the Cauchy matrix, we construct an integer approximation to DTT+, termed INT-DTT+. This approximation significantly reduces both computational and memory complexities with respect to the separable KLT with minimal performance loss. We validate our approach in the context of mode-dependent transforms for the VVC standard, following a rate-distortion optimized transform (RDOT) design approach. Integrated into the explicit multiple transform selection (MTS) framework of VVC in a rate-distortion optimization setup, INT-DTT+ achieves more than 3% BD-rate savings over the VVC MTS baseline, with complexity comparable to the integer DCT-2 once the base DTT coefficients are available.
academic

INT-DTT+: Low-Complexity Data-Dependent Transforms for Video Coding

基本信息

  • 论文ID: 2511.17867
  • 标题: INT-DTT+: Low-Complexity Data-Dependent Transforms for Video Coding
  • 作者: Samuel Fernández-Menduiña, Eduardo Pavez, Antonio Ortega (University of Southern California), Tsung-Wei Huang, Thuong Nguyen Canh, Guan-Ming Su, Peng Yin (Dolby Laboratories)
  • 分类: eess.IV (Image and Video Processing), cs.IT, math.IT
  • 提交时间: 2025年11月22日
  • 论文链接: https://arxiv.org/abs/2511.17867

摘要

本文针对视频编码中的变换设计问题，提出了一种低复杂度的数据依赖变换框架INT-DTT+。传统离散三角变换（如DCT-2和DST-7）在编码性能和计算效率间取得平衡，但数据依赖变换（如KLT和图基可分离变换GBST）虽能提供更好的能量压缩，却缺乏可利用的对称性来降低计算复杂度。本文基于DTT+（一种通过秩一更新DTT图得到的GBST族）构建框架，首先提出联合估计行列图秩一更新的图学习算法，然后利用DTT+的渐进结构将核分解为基础DTT和结构化Cauchy矩阵。通过利用低复杂度整数DTT和稀疏化Cauchy矩阵，构建了INT-DTT+整数近似。在VVC标准的模式依赖变换场景下验证，INT-DTT+相比VVC MTS基线实现超过3%的BD-rate节省，复杂度与整数DCT-2相当。

研究背景与动机

问题定义

视频编码系统中的变换设计面临"性能-复杂度"困境：

  1. 传统DTT的局限：DCT-2、DST-7等离散三角变换虽有快速算法，但对特定信号统计特性的适应性有限
  2. 数据依赖变换的困境：KLT理论上最优但缺乏快速实现；可分离KLT和GBST虽降低参数量，但仍无对称性可利用来减少计算
  3. 实际应用瓶颈：现有学习变换因缺乏快速算法而鲜少用于实际编解码器

研究重要性

  • 编码效率提升：模式依赖变换（MDT）可利用每种预测模式残差的统计特性提升能量压缩
  • 工业应用需求：VVC等新一代编解码器需要在保持低复杂度的同时提升压缩性能
  • 理论与实践桥梁：需要在理论最优（KLT）和实际可行（DTT）之间找到平衡点

现有方法的局限

  1. sep-KLT：需学习n²个参数，计算复杂度高（O(n²)乘法），无快速算法
  2. GBST：虽约束参数数量提升鲁棒性，但仍缺乏可利用的结构
  3. 直接量化方法：将浮点核直接量化为整数无法降低计算复杂度
  4. 作者前期工作：DTT+的FFT快速算法仅在大块尺寸时优于朴素矩阵乘法，且未解决参数学习问题

核心贡献

本文的主要贡献包括：

  1. 联合图学习算法：提出针对DTT+的图学习方法，通过联合估计行列图的秩一更新参数（αr, βr, αc, βc, ir, ic），捕获整个块的协方差结构
  2. INT-DTT+整数实现框架：
    • 利用DTT+的渐进分解特性（基础DTT + Cauchy矩阵）
    • 基于特征值交错性质设计Cauchy矩阵稀疏化策略
    • 构建低复杂度整数近似，复杂度可比拟整数DCT-2
  3. RDOT设计方法：将DTT+整合到率失真优化变换（RDOT）框架，使学习的变换与VVC现有MTS核互补
  4. 权重聚类策略：提出基于k-means的参数聚类方法，进一步降低存储需求（相比sep-KLT减少66%-94%）
  5. 系统验证：在VVC标准的帧内预测残差场景下，实现3%+ BD-rate节省，复杂度增量仅相当于一次整数DCT-2计算

方法详解

任务定义

输入：预测残差块 xi ∈ R^(n×n)（如VVC帧内预测残差）
输出：变换系数 yi = T^⊤ xi
目标：设计变换矩阵T，使其：

  • 适应信号统计特性（能量压缩性能）
  • 具有低计算复杂度（整数运算，稀疏结构）
  • 低存储需求（参数量少）
  • 可整合到现有编码框架（RDO兼容）

DTT+理论基础

秩一更新图模型

DTT+基于对DTT图Laplacian的秩一更新：

L̃(α, β, i) = βL + αeie_i^⊤,  i ∈ {1,...,n}, α,β ≥ 0

其中：

  • L是基础DTT图的Laplacian（路径图对应DCT-2，带自环路径图对应DST-7）
  • α控制自环权重，β缩放原图边权
  • i指定自环位置

关键理论性质

性质1（渐进分解）：给定 L = Udiag(λ)U^⊤ 和 L̃ = Ũdiag(λ̃)Ũ^⊤，有：

Ũ^⊤ = diag(a)C(λ̃, βλ)diag(z)U^⊤

其中C是Cauchy矩阵：C_ij = 1/(λ̃_i - βλ_j)

意义：可先计算基础DTT系数U^⊤x，再通过Cauchy矩阵转换到DTT+基

性质2（特征值交错）：当α,β > 0时：

βλ_1 ≤ λ̃_1 ≤ βλ_2 ≤ ... ≤ βλ_n ≤ λ̃_n

意义：|λ̃_j - βλ_i|随|i-j|增大而增大，导致Cauchy矩阵系数衰减，可稀疏化

图学习算法

可分离模型

将完整块的Laplacian建模为行列图的Cartesian积：

L_g(φ) = L̃(αr, βr, ir) ⊗ I + I ⊗ L̃(αc, βc, ic)

参数向量：φ = αr, αc, βr, βc, ir, ic

优化目标

最小化负对数似然（等价于最大似然估计）：

φ* = argmin_φ [-log det(L_g(φ)) + tr(L_g(φ)S)]

其中S是样本协方差矩阵

求解策略

  1. 重参数化：使用 α² 和 β² 替代 α 和 β，避免非负约束
  2. 混合优化：
    • 对离散变量(ir, ic)枚举所有n²种组合
    • 对每组(ir, ic)，通过Newton法求解连续变量(αr, αc, βr, βc)
  3. 梯度计算：利用秩一结构高效计算梯度（方程9-12）

RDOT整合（算法1）

1. 初始化：随机划分样本到nt个簇
2. 迭代直到收敛：
   a. 对每簇Ij，求解φ_j*并计算变换Tj
   b. 通过RDO更新簇分配（方程4）
3. 输出：学习的变换集{Tj}

INT-DTT+整数实现

核分解策略

基于渐进性质，将变换核K（对应Cauchy矩阵）分解：

K = K_d + K_o = (I + K_o K_d^(-1))K_d = (I + F)K_d

其中：

  • K_d：对角部分
  • K_o：非对角部分
  • F = K_o K_d^(-1)：归一化非对角项

优势：F比K_o更适合稀疏化（已除以对角项）

量化方案

K_dq = round(p_d K_d)/p_d
F_q = round(p_f F)/p_f

参数选择：

  • p_d = 128（8位精度，标准整数变换精度）
  • p_f = 4（3位精度，更激进的稀疏化）
  • 采用截断限制位深

精细调优

量化后在±1范围内微调核元素，优化三个指标：

  1. 正交性（U^⊤U接近单位阵）
  2. 接近度（与原始核的距离）
  3. 范数（变换的能量保持）

遵循HEVC/VVC整数变换设计准则

前向变换流程（算法2）

输入：图像块xi，整数矩阵K'_dq和F'_q
1. 计算基础DTT系数：yi = U^⊤xi
2. 对角矩阵乘法：zi = K'_dq yi
3. 稀疏矩阵乘法：qi = zi + F'_q zi
输出：INT-DTT+系数qi

复杂度分析：

  • 步骤1：假设已在RDO中计算（无额外开销）
  • 步骤2：n次乘法（对角矩阵）
  • 步骤3：取决于F'_q稀疏度，通常≤n²/2次操作

基础DTT选择策略

根据学习的自环权重选择基础变换：

  • 自环权重 < 0.5：选DCT-2（自环为0）
  • 自环权重 ≥ 0.5：选DST-7（自环为1）

依据Weyl不等式，这保证特征值间隙最大，Cauchy矩阵衰减最快

实验设置

数据集

训练集：

  • CLIC测试集：878×2048到2048×2048像素
  • Kodak数据集：512×768像素

测试集：

  • CLIC验证集：878×2048到2048×2048像素

残差提取：

  • 配置：VVC全帧内编码
  • 块尺寸：8×8, 16×16, 32×32
  • 选择：仅保留RD最优块（量化前）
  • 预测模式：planar、DC、角度模式（共66种）

评价指标

  1. BD-rate：相对VVC MTS基线的码率节省百分比（越低越好）
  2. 算术操作数：乘法和加法次数
  3. 存储需求：核参数占用的比特数
  4. 正交性/接近度/范数：整数核质量指标

对比方法

  1. VVC MTS基线：显式多变换选择（DCT-2, DST-7等组合）
  2. sep-KLT：可分离KLT，每模式学习n²参数
  3. DTT+：浮点精度DTT+（8位量化）
  4. INT-DTT+：本文提出的整数近似

实现细节

训练配置

  • 样本数：每模式500-4000个块（消融实验）
  • RDOT迭代：RD代价下降<1%时停止
  • 优化器：Newton法求解连续参数
  • 率失真权衡：使用ℓ1范数作为码率代理加速

编码配置

  • 量化器：死区量化器
  • 熵编码：CABAC
  • 失真度量：PSNR
  • 变换索引：复用VVC MTS语法信令
  • RDO：穷举搜索所有候选变换

INT-DTT+参数

  • 对角精度：p_d = 128（8位）
  • 非对角精度：p_f = 4（3位）
  • 稀疏化：基于系数幅度阈值
  • 微调范围：±1

实验结果

主要结果

不同训练样本数的性能（表I，8×8块）

样本数sep-KLTDTT+INT-DTT+
500-2.70%-3.06%-3.01%
1000-2.99%-3.08%-3.04%
2000-3.21%-3.12%-3.06%
4000-3.25%-3.13%-3.09%

关键发现：

  • DTT+和INT-DTT+在小样本时更鲁棒（仅2参数 vs. n²参数）
  • INT-DTT+性能损失极小（<0.1%）
  • 所有方法均显著优于VVC MTS基线

不同块尺寸的性能（表II，2000样本）

尺寸sep-KLTDTT+INT-DTT+
8×8-3.21%-3.12%-3.06%
16×16-3.60%-3.64%-3.46%
32×32-3.72%-3.96%-3.75%

关键发现：

  • 大块尺寸增益更显著（更多可学习结构）
  • DTT+在32×32时优于sep-KLT（参数效率优势）
  • INT-DTT+保持竞争力

复杂度分析

算术操作数（图5）

以8×8块为例（DCT-2基线≈200次操作）：

  • INT-DTT+增量：约200次操作（假设基础DTT已计算）
  • 总计：约400次操作（从像素域直接计算）
  • sep-KLT：约4000次操作（64×64矩阵乘法）

复杂度降低：相比sep-KLT降低10倍

存储需求（表IV，8×8块）

核数量34567sep-KLT×1
比特数115215361976238427841024

对比分析：

  • 6个INT-DTT+核 ≈ 2.3个sep-KLT核（存储）
  • 但覆盖66种模式（sep-KLT需66个核）
  • 实际节省：66%-94%（考虑聚类）

消融实验

权重聚类效果（表III，8×8块）

核数量34567
sep-KLT-2.92%-3.01%-3.06%-3.08%-3.12%
DTT+-2.89%-2.96%-3.08%-3.13%-3.14%
INT-DTT+-2.85%-3.02%-3.04%-3.06%-3.08%

关键发现：

  • 6个核即可匹配66个独立核的性能
  • DTT+的权重聚类优于sep-KLT的角度分组
  • 存储-性能权衡灵活可调

学习参数分析（图4）

观察到的模式：

  1. 空间一致性：相邻角度模式参数相似
  2. 方向性：
    • αr在水平预测（模式18）峰值
    • αc在垂直预测（模式50）峰值
  3. 尺寸效应：块增大时自环权重↓，边权重↑
  4. 最优位置：自环总在第一节点（边界像素预测最佳）

案例分析

Cauchy矩阵稀疏化（图3）

以DST-7到planar模式DTT+的转换核为例：

  • (a) 原始核：对角占优，远离对角快速衰减
  • (b) 量化后：p_d=128, p_f=4，保持结构
  • (c) 整数实现：稀疏度约60%，对角附近密集

验证理论：特征值交错性质确实导致预期的衰减模式

RDO场景优势

在编码器RDO过程中：

  1. VVC已计算DCT-2/DST-7系数（候选变换）
  2. INT-DTT+仅需额外计算K'_dq和F'_q操作
  3. 边际成本：≈一次整数DCT-2（vs. 全新sep-KLT计算）

实用价值：在实际编码器中开销可接受

相关工作

数据依赖变换

  1. KLT及变体：
    • Jain (1976)：快速KLT for特定随机过程
    • Effros et al. (2004)：KLT次优性分析
    • Fan et al. (2019)：信号无关可分离KLT
  2. 图基方法：
    • Egilmez et al. (2020)：GBST for视频编码
    • Egilmez et al. (2017)：Laplacian约束下的图学习
    • 本文：专注于秩一更新的特殊结构

视频编码变换

  1. 标准变换：
    • Strang (1999)：DCT理论基础
    • Han et al. (2011)：ADST for预测残差
    • Budagavi et al. (2013)：HEVC核变换设计
    • Zhao et al. (2021)：VVC变换编码
  2. 学习变换：
    • Yeo et al.：低复杂度模式依赖KLT
    • Egilmez et al. (2020)：参数化图基变换
    • Zou et al. (2013)：RDOT设计方法
    • 本文：首次实现实用低复杂度学习变换

快速算法

  1. FFT及变体：
    • Cooley-Tukey (1965)：FFT算法
    • Puschel & Moura (2008)：代数信号处理理论
  2. 结构化矩阵：
    • Cauchy矩阵快速算法
    • 本文前期工作 (2025)：DTT+的FFT复杂度算法
    • 本文：整数实现和稀疏化策略

结论与讨论

主要结论

  1. 理论贡献：建立了从DTT到数据依赖变换的桥梁，保留快速算法可能性
  2. 方法创新：
    • 联合行列图学习捕获块级统计
    • 整数实现利用渐进性和Cauchy结构
    • RDOT设计使学习变换与固定变换互补
  3. 实验验证：
    • 3%+ BD-rate节省（显著改进）
    • 复杂度与整数DCT-2相当（实用）
    • 存储需求降低66%-94%（高效）
  4. 实用价值：首次使数据依赖变换在实际编码器中可行

局限性

  1. 应用范围：
    • 当前仅验证帧内预测残差
    • 未测试帧间预测和其他编码工具
  2. 理论限制：
    • 仅考虑秩一更新（更复杂结构未探索）
    • 基于可分离假设（非可分离KLT理论最优）
  3. 实现约束：
    • 需要基础DTT已计算（RDO场景）
    • 量化精度影响性能-复杂度权衡
  4. 评估局限：
    • 未进行硬件实现和实际运行时测试
    • 仅在VVC框架下验证

未来方向

论文明确提出的方向：

  1. 帧间预测模式：扩展到运动补偿残差
  2. 硬件感知评估：实际运行时和能耗测试
  3. 其他编解码器：AV1、EVC等标准

潜在扩展： 4. 高阶更新：秩二或更高秩更新 5. 非可分离扩展：保持低复杂度的非可分离变换 6. 端到端学习：与神经网络编码器联合优化 7. 感知优化：整合感知质量度量

深度评价

优点

1. 理论创新性（⭐⭐⭐⭐⭐）

  • 优雅的数学框架：秩一更新→渐进分解→Cauchy结构，理论链条完整
  • 可证明性质：特征值交错性质为稀疏化提供理论支撑
  • 统一视角：将DTT和数据依赖变换纳入统一框架

2. 工程实用性（⭐⭐⭐⭐⭐）

  • 复杂度突破：首次使学习变换达到DTT级别复杂度
  • RDO友好：利用已计算的DTT系数，边际成本低
  • 存储高效：参数量少且支持聚类，适合实际部署
  • 标准兼容：无缝整合VVC MTS框架

3. 实验充分性（⭐⭐⭐⭐）

  • 多维度评估：性能、复杂度、存储、鲁棒性
  • 消融实验完整：训练样本数、块尺寸、聚类数
  • 对比全面：sep-KLT、浮点DTT+、整数近似
  • 结果显著：3%+ BD-rate改进在视频编码领域非常可观

4. 写作清晰度（⭐⭐⭐⭐）

  • 结构合理：问题→理论→方法→实验逻辑清晰
  • 图表丰富：图3直观展示稀疏化过程
  • 符号规范：数学表达严谨
  • 可复现性：算法伪代码和参数设置详细

不足

1. 方法局限性

  • 秩一限制：虽简化问题但可能限制表达能力，未探讨更高秩的潜力
  • 可分离假设：理论上非可分离KLT更优，但文中未量化此差距
  • 基础DTT依赖：性能受限于DCT-2/DST-7的近似能力

2. 实验设计缺陷

  • 测试集单一：仅CLIC验证集，未测试其他标准测试序列（如JVET CTC）
  • 缺乏实时性评估：操作数≠实际运行时间，未提供硬件测试
  • 编码器配置：仅全帧内，实际应用多为随机接入配置
  • QP范围：未明确说明测试的量化参数范围

3. 分析深度不足

  • 失败案例：未分析哪些模式/内容DTT+效果不佳
  • 与神经网络对比：未与学习型编码器（如VCM）对比
  • 理论界限：未给出性能上界或复杂度下界分析
  • 泛化性：跨数据集、跨分辨率的泛化能力未充分验证

4. 技术细节缺失

  • 量化策略：p_d和p_f的选择缺乏系统分析（仅经验值）
  • 收敛性：RDOT迭代的收敛性保证未讨论
  • Newton法：求解方程9-12的初始化和收敛条件未说明
  • 编解码器漂移：整数近似的累积误差影响未评估

影响力评估

对领域的贡献（⭐⭐⭐⭐⭐）

  • 开创性：首次实现实用级数据依赖变换，可能改变编码器设计范式
  • 理论价值：秩一更新框架可启发其他信号处理问题
  • 工业潜力：Dolby参与表明工业界关注，有标准化可能

实用价值（⭐⭐⭐⭐）

  • 即时应用：可直接整合现有VVC编码器
  • 性能提升：3% BD-rate在商业应用中有价值
  • 部署可行：复杂度和存储开销可接受
  • 局限：需离线训练，在线适应性有限

可复现性（⭐⭐⭐）

  • 优点：算法描述清晰，参数设置明确
  • 不足：
    • 未开源代码（截至论文发表）
    • VVC参考软件修改细节未公开
    • 训练数据预处理流程不完整

适用场景

最适合的应用

  1. 离线编码系统：内容分发、归档存储（有时间训练）
  2. 模式依赖优化：帧内编码、纹理编码
  3. 资源受限设备：相比sep-KLT更适合移动端
  4. 标准扩展：作为VVC/AV1的可选工具

不适合的场景

  1. 实时编码：离线训练开销大
  2. 极低延迟：INT-DTT+增加编码复杂度
  3. 通用内容：针对特定统计特性优化
  4. 硬件编码器：可能需要专用硬件支持

与相关工作的对比

方法参数量复杂度性能实用性
sep-KLTO(n²)O(n²)基线低
GBSTO(n)O(n²)略优低
DTT+ (浮点)O(1)O(n log n)优中
INT-DTT+O(1)O(n)优高

独特优势：唯一同时满足参数少、复杂度低、性能优的方法

参考文献（精选）

理论基础

  1. Jain (1976): "A fast Karhunen–Loève transform" - KLT快速算法开创性工作
  2. Bunch et al. (1978): "Rank-one modification of symmetric eigenproblem" - 特征值交错性质
  3. Ortega et al. (2018): "Graph signal processing: Overview" - 图信号处理综述

视频编码标准

  1. Bross et al. (2021): "Overview of VVC standard" - VVC标准概述
  2. Zhao et al. (2021): "Transform coding in VVC" - VVC变换编码
  3. Budagavi et al. (2013): "Core transform design in HEVC" - HEVC整数变换设计

相关方法

  1. Egilmez et al. (2020): "Graph-based transforms for video coding" - GBST方法
  2. Zou et al. (2013): "Rate-distortion optimized transforms" - RDOT设计方法
  3. 作者前期工作 (2025): "Fast DCT+: A family of fast transforms" - DTT+快速算法

总结

本文是视频编码变换设计领域的重要进展，成功弥合了理论最优（KLT）与实际可行（DTT）之间的鸿沟。核心创新在于利用秩一更新的特殊结构，将数据适应性与快速算法结合，这是该领域长期追求但未实现的目标。

主要优势包括理论优雅（完整的数学框架）、工程实用（与DCT相当的复杂度）、实验充分（多维度验证），使其成为极具潜力的实用技术。主要局限在于评估的深度和广度仍有提升空间，特别是硬件实现和跨场景泛化能力。

对于视频编码研究者，本文提供了数据依赖变换设计的新范式；对于工业实践者，INT-DTT+是提升编码效率的可部署方案；对于理论工作者，秩一更新框架可启发其他结构化矩阵问题的研究。

推荐指数：9/10 - 强烈推荐给视频编码、图信号处理和数值线性代数领域的研究者。