低频不可分变换(LFNST [Low-Frequency Non-Separable Transform]) 是高频凋零技术的代表,通过一个 经过离线训练 所得的不可分变换矩阵,来进一步压缩指定范围内的前一次变换结果 [32] 。我们通常将首次变换称为 一次变换(First Transform) 或 主要变换(Primary Transform)。将以一次变换为输入的第二次变换,称为 二次变换(Secondary Transform)。
低频不可分变换(LFNST),与 H.264 中的哈达玛变换(WHT),都属于作用于二次变换的一种处理技术。其本身复杂的部分,在于如何得到 不可分变换矩阵组(NSMG [Non-Separable Matrix Group])。矩阵组通过特殊的离线小模型计算所得,是一个常量矩阵组。
那么,什么是不可分变换(Non-Separable Transform)?
不可分变换,被用来指代一类,无法分解为独立的行变换与列变换的组合形式表示, 只能 用单一矩阵作统一处理的变换类型。 与之相对的就是可分变换(Separable Transform)。 前文中的离散正弦变换和哈达玛变换,就属于可分变换类型。
可见,对于 可分变换,如果记分离后的行列变化矩阵分别为 $$M|{row}$$ 、 $$M|{col}$$ ,那么始终有:
$$ {\displaystyle \begin{aligned} Out &= M|{row} \cdot In \cdot M|{col} \ \end{aligned} } $$
而对于 不可分变换,则有变换矩阵
低频不可分所使用的矩阵组,就属于后一种。
如果记采用一次变换所得
算法要求,目标算子
$$
{\displaystyle
\begin{aligned}
&X_k =
\begin{bmatrix}
& X_{11} \ , & X_{12} \ , \cdots,\ & X_{1N} \
& X_{21} \ , & X_{22} \ , \cdots,\ & X_{2N} \
& \vdots , & \vdots \ , \cdots,\ & \vdots \
& X_{M1} \ , & X_{M2} \ , \cdots,\ & X_{MN}
\end{bmatrix}{M \times N} \
&X_k\prime =
\begin{bmatrix}
& X{11} \ , & X_{12} \ , \cdots,\ & X_{M1} \ , \cdots,\ & X_{MN}
\end{bmatrix}_{MN \times 1}^{T} \
\end{aligned}
}
$$
将
上式即是 低频不可分变换,被应用在二次变换时的基本公式 了。所得
在说明原理中我们提到,低频不可分变换中,根据前置参数的差异,会从持有矩阵组里选择合适的算子
从 LFNST 原论文中可获知的信息是,针对 不可分二次变换(NSST [Non-Separable Secondary Transform])的变换集,采用的是基于 K均值(K-Means)聚类分析法 的变体算法。因此,基本训练过程属于标准的双步(2-Stages)无监督学习(Unsupervised Learning),存在两个阶段,分别是:初始阶段(Initialization)和 迭代阶段(Iteration) [33] 。当然,数据也需要分为 准备数据(Preparing Data) 和 训练数据(Training Data),两者皆来自未开放的黑盒数据集。
初始阶段中,主要处理准备数据,进行了两个工作:
首先,进行 特征(Feature)的选择(Selection)和提取(Extraction)。为每一个从 编码过程(Encoding Process) 获取的 变换系数块(Transform Coefficient Block) 随机的分配一个取值范围为
其次, 选择聚类算法(Clustering Algorithm Selection) 和 约束条件设计(Constraint Design)。这里采用 K均值算法,通过利用前一步中,标签范围在
那么约束条件是怎么设置的呢?这里采用的是,在单次训练过程后,从 3 个聚类的质心与
随后进入迭代阶段。
迭代阶段中,主要处理训练数据,训练同样也分为两步:
首先,进行 聚类验证(Cluster Validation)。聚类验证的过程就和一般的 K均值算法一致,将分批的训练数据交付到 4 个聚类,分别计率失真优化指数(RDO)。之后,用计算结果,按照设置的约束条件进行处理, 更新聚类标定的数据集。
其次,完成 结果解析(Results Interpretation)。当更新聚类当前数据集后,需要重新计算聚类的质心,方法同初始阶段一致。通过求解协方差矩阵,获取最佳不可分离变换矩阵,替代原聚类的质心。显然,
而下一次迭代是否继续,则根据是否到达模型的 最大迭代次数(该参数未提供经验值,也可根据自身训练情况自行设定),或 RDO 没有进一步降低 来决定。两者命中其一,则停止迭代训练,获取
一般
$$
{\displaystyle
\begin{aligned}
&T_{M \times N} \in
\begin{bmatrix}
& {T_1}|{M \times N} \ , & T_2|{M \times N} \ , & T_3|_{M \times N} \
\end{bmatrix}\
\end{aligned}
}
$$
此时的
若输入前置主变换采用 DCT-2 型,那么二次变换的输入
因此,当还原输出权重矩阵
所以,目前 只将 LFNST 运用在 DCT-2 输入的情况。
至此,在经过多次不同尺寸和模式输入下的模型训练过程后,得到了数个
经过上述的推理,我们可以察觉到即便是取一个较小的尺寸,整个 LFNST 的运算也会呈指数的增加算力消耗。例如输入的
于是,在 VTM5 有关 LFNST 工程实践的 JVET-K0099 提案中,对 LFNST 的主要应用场景,即二次不可分变换(NSST),做了算法上的调整 [34] 。利用复合基,降低计算成本。
假设当前输入尺寸为
NSST 规定,对于
而对于两类变换集,NSST 只需要分离所得的低频权重部分。因此反推算子情况,亦只需要保留所有 MTS 中的算子
取尺寸为
对于
而如果强行构造
所以,此处仍选择取用原
对于
$$ {\displaystyle \begin{aligned} \hat{W}k &= T{4 \times 4}\prime \cdot W_k \ \hat{X}k\prime\prime &= \sum{i=1}^4 ( T_{4 \times 4}\prime \cdot W_{4 \times 4} \cdot X_k \prime )_i\ \end{aligned} } $$
其中,
而 $$\hat{X}{k}\prime\prime$$ 则是输入 $$X_k\prime$$ 关于 $$T{4 \times 4}\prime \cdot W_{4 \times 4}$$ 的变换结果。但一组选定尺寸的 LFNST 变换集,只有 3 个矩阵可作为基底。因此,变换的覆盖范围也是有限的。若将输入
$$
{\displaystyle
\begin{aligned}
&X_k =
\begin{bmatrix}
& X_k|{4 \times 4} \ , & X_k|{4 \times 4} \
& X_k|{4 \times 4} \ , & X_k|{4 \times 4}
\end{bmatrix} =
\begin{bmatrix}
& X_{k1} \ , & X_{k2} \
& X_{k3} \ , & X_{k4}
\end{bmatrix}
\end{aligned}
}
$$
那么原
$$
{\displaystyle
\begin{aligned}
\hat{X}k\prime\prime &=
\begin{bmatrix}
& T_1|{4 \times 4}\prime \ , & T_2|{4 \times 4}\prime \
& T_1|{4 \times 4}\prime \ , & \ [0]{4 \times 4}
\end{bmatrix} \cdot
\begin{bmatrix}
& W{k1} \ , & W_{k2} \
& W_{k3} \ , & W_{k4}
\end{bmatrix} \cdot
\begin{bmatrix}
& X_{k1} \ , & X_{k2} \
& X_{k3} \ , & X_{k4}
\end{bmatrix} \
&= \sum T_{4 \times 4}\prime \cdot
\begin{bmatrix}
& W_{k1} \ , & W_{k2} \
& W_{k3} \ , & [0]{4 \times 4}
\end{bmatrix} \cdot
\begin{bmatrix}
& X{k1} \ , & X_{k2} \
& X_{k3} \ , & [0]_{4 \times 4}
\end{bmatrix} \
\end{aligned}
}
$$
存在
$$
{\displaystyle
\begin{aligned}
{T_{8 \times 8}}^{-1} \cdot \hat{X}k\prime &=
\begin{bmatrix}
& {T_1|{4 \times 4}\prime}^{-1} \ , & {T_2|{4 \times 4}\prime}^{-1} \
& {T_3|{4 \times 4}\prime}^{-1} \ , & \ [0]{4 \times 4}
\end{bmatrix} \cdot {W{4 \times 4}}^{-1} \cdot \hat{X}k\prime\prime + {T{4 \times 4}}^{-1} \cdot \hat{X}{k4}\prime \
&=
\begin{bmatrix}
& {\hat{W}{k1}}^{-1} \ , & {\hat{W}{k2}}^{-1} \
& {\hat{W}{k3}}^{-1} \ , & {T_{4 \times 4}}^{-1}
\end{bmatrix} \cdot \begin{bmatrix}
& \hat{X}k\prime\prime \ , & [0]{4 \times 4} \
& [0]{4 \times 4} \ , & \quad \hat{X}{k4}\prime
\end{bmatrix} \
&= X_k
\end{aligned}
}
$$
即:
$$ {\displaystyle \begin{aligned} \hat{X}k\prime &= \begin{bmatrix} & \hat{X}k\prime\prime \ , & [0]{4 \times 4} \ & [0]{4 \times 4} \ , & \quad \hat{X}{k4}\prime \end{bmatrix} \ T{8 \times 8} &= \begin{bmatrix} & \hat{W}{k1} \ , & \hat{W}{k2} \ & \hat{W}{k3} \ , & T{4 \times 4} \end{bmatrix} = \begin{bmatrix} & T_{4 \times 4}\prime \cdot W_k \ , & T_{4 \times 4}\prime \cdot W_k \ & T_{4 \times 4}\prime \cdot W_k \ , & T_{4 \times 4} \end{bmatrix} \end{aligned} } $$
取用:
那么原
$$ {\displaystyle \begin{aligned} \hat{X}k\prime &= (T{8 \times 8}\prime + T_{4 \times 4}\prime )\cdot X_k \ \end{aligned} } $$
而 $$\hat{X}k\prime$$ 的右上和左下角,皆为 $$[0]{4 \times 4}$$ 值。
最终:
$$ {\displaystyle \begin{aligned} NSST:& \begin{cases} { \begin{aligned} T &= [\ T_{4 \times 4}\prime,\ T_{8 \times 8}\prime \ ] \ \hat{X}k\prime &= (T{8 \times 8}\prime + T_{4 \times 4}\prime )\cdot X_k &, min(M ,\ N) = 8 \ \hat{X}k\prime &= T{4 \times 4}\prime \cdot X_k &, min(M ,\ N) = 4 \end{aligned} } \end{cases} \ \end{aligned} } $$
由
不过,即使 NSST 已经极大的缩减了 LFNST 变换集的大小,并能在参与熵编码后,能更为有效的降低信息熵。但在以 H.265/HEVC 为目标应用时,就需要 35 组 2 类 3 算子的变换集 [34] 。延伸到 H.266/VVC 规格,则会至少需要 67 组 2 类 3 算子变换集。不论是 H.265 还是 H.266 ,都不可能采纳,属于无法工程化的技术。 那么,如何精简基础多变换集呢?
在 VTM5 的有关 JVET-N0193 提案的提交中,H.266/VVC 采用了 缩减低频不可分变换(R-LFNST [Reduced LFNST]),处理此问题 [33] 。因为是针对 LFNST 的 二次不可分变换(NSST)的逼近算法,R-LFNST 也被称为 缩减二次变换(RST [Reduced Secondary Transform]) [35] 。
缩减二次变换对 LFNST 的 NSST 应用所得 基础多变换集(MTS),进行 整体变换集算子数量 和 算子生效范围,两方面的裁剪。其理论根基仍来源自 NSST 。
RST 在生效范围的调整,主要集中于控制 NSST 在工程实现中的有效计算区域。根据 NSST 的基本公式可以发现,实际上对于尺寸大于
如此一来,介于参与 NSST 的输入已不可再分,对于这三个区域外的的其余
所以,原 NSST 公式可调整为:
$$ {\displaystyle \begin{aligned} RST:& \begin{cases} { \begin{aligned} T &= [\ T_{4 \times 4}\prime,\ T_{8 \times 8}\prime \ ] \ \hat{X}k\prime &= T{8 \times 8}\prime \cdot X_k\prime|_{48 \times 1} &, min(M ,\ N) = 8 \ \hat{X}k\prime &= T{4 \times 4}\prime \cdot X_k &, min(M ,\ N) = 4 \end{aligned} } \end{cases} \ \end{aligned} } $$
即,对于
图 3-24 RST 的 8x8 输入理示意图[32]
有
图 3-25 RST 的 8x8 输入 NSST 处理结果示意图(蓝线扫描顺序归零)[35]
之后,叠加至原主变化
经过此番调整后,单次算子计算所需要的算力消耗,较 NSST 相比就非常之小了。
而在 MTS 的算子数量方面,通过整合 K均值聚类机器学习
$$
{\displaystyle
\begin{aligned}
&T_{M \times N} \in
\begin{bmatrix}
& {T_1}|{M \times N} \ , & T_2|{M \times N} \
\end{bmatrix}\
\end{aligned}
}
$$
同时,RST 对需要处理的 H.266 规格下的各类帧内预测模式进行了分类。将原本需要单独生成变换集的平面(Planar)模式、直流(DC)模式、角度(Angle)预测模式进行了拆解。把临近相似方向的角度预测模式进行了分类。之后归类于 4 个主流变换集到如下索引 [32] :
凭借这样的处理,使得原本大于
至此,根据输入尺寸大小、预测模式所处归类、输入率失真优化指数(RDO)这 3 个参数,就能够选定具体的算子进行相关处理了。完成 RST 的工程化。
到这里,信息频域分离和部分冗余处理,就已经完成了。随后再配合传统音视频的量化和熵编码,即可完成对信息剩余存储空间冗余的压缩。此处不再赘言。