3.5.2 哈达玛变换（WHT [Walsh-Hadamard Transform]）

Previous3.5.1 整数离散正余弦变换（DST/DCT）Next3.5.3 低频不可分变换（LFNST [Low-Frequency Non-Separable Transform]）

Last updated 9 months ago

除了整数离散正余弦变换（IDST/IDCT）外，在早期的规格中（如 H.264）还会使用一种，被称为 沃尔什-哈达玛变换（WHT [Walsh-Hadamard Transform]） 的离散傅立叶的变换变体算法，来代为进一步的富集频域信息。

在之前的傅立叶变换运用中，我们大都选择三角函数或近似拟合，来作为基底函数进行分解。考虑到傅立叶函数，只从周期性上，对基底函数族和目标函数进行了约束。我们是不是可以选择一种，类似于自然排序线性组合的周期性函数，代替正余弦处理，从而获取更符合数据物理介质存储（媒介传输）状态（0/1 双模态）的变换过程呢？

答案是可以的。虽然，从某种意义上，哈达玛变换相当于取用了只拟合正余弦函数极值的特殊函数。但哈达玛变换（WHT）依旧被认为是此类 非三角函数离散傅立叶变换，简称 非三角函数变换（或非正/余弦变换），的经典代表之一。

考虑周期 $T=2^n$ 分段函数：

\begin{aligned} f(x)= & (-1)^{ \lfloor \tfrac{x}{T} \rfloor } = (-1)^{ \lfloor \tfrac{x}{2^n} \rfloor } \\ \end{aligned}

记周期 $T=2^n =N$ 的原信号函数 $s(t)$ 以 $f(x)$ 函数族构成基底。根据 傅立叶级数 有：

\begin{aligned} s(n) &= \frac{1}{N}\sum_{k = 0}^{N-1} \hat{s}(k) \cdot (-1)^{nk} \\ \hat{s}(k) &= \sum_{n = 0}^{N-1} s(n) \cdot (-1)^{nk} \\ \end{aligned}

这即是 哈达玛变换的基础公式。

不同于 DST/DCT 需要进行泛化后，才能运用到工程之中的情况。哈达玛变换由于 $f(x)$ 本身为偶函数，且始终只有实部的特性，可以直接在原有无扩充的数据集上使用。因此，假设原信号函数 $s(t) = s(n)$ 在 $n \in \mathbb{Z} [0, \ N - 1]$ 的各节点位置，有样本采样 $S \in [S_0, \ S_{N - 1}]$ 。则：

\begin{aligned} WHT:& { \begin{cases} s(n) &= \frac{1}{N}\sum_{k = 0}^{N-1} \hat{s}(k) \cdot (-1)^{nk} = \sqrt{\frac{1}{N}} \cdot \sum_{k = 0}^{N-1} \begin{pmatrix} \sqrt{\frac{1}{N}} \cdot \hat{s}(k) \end{pmatrix} \cdot (-1)^{nk} \\ \hat{s}(k) &= \sum_{n = 0}^{N-1} s(n+\tfrac{1}{2}) \cdot (-1)^{nk} = \sum_{n = 0}^{N-1} s(n) \cdot (-1)^{nk} \end{cases} } \\ \end{aligned}

即：

扩展到二维情况，有：

如此，就可以矩阵表示 WHT 变化为：

其中：

常用的哈达玛变换算子主要有 3 种，分别是：

从上面的推导过程可知，采用哈达玛变换，同样能够将频域中的高低频信息，进行分区汇集。理论上 WHT 也可以代替 IDST/IDCT 来做频域压缩（降低信息熵）前的归类处理。

哈达玛变换的常见应用

考虑到 WHT 是 DST/DCT 的特殊拟合，而基底函数有限。其本身在选取较大的窗口尺寸，且被使用在取值范围差异较大的原信号时，会导致一定程度的误差。工程中除非量化到门电路的粒度，其余大多时间还是用它来求解指定窗口范围，残差信号（Residual Singnal） 经哈达玛变换后 绝对误差和（SATD [Sum of Absolute Transformed Difference]）。

而哈达玛变换后绝对误差和（SATD）取值，即是变换求得的所有元素绝对值之和，有：

以 SATD 来代替传统绝对误差和（SAD [Sum of Absolute Difference]）。利用 WHT 的加和快速运算特征计算残差趋势，协助时空域运动估计和数据量化的压缩处理。

哈达玛变换的常见应用

除此之外，如果我们换一种视角，将经过 IDST/IDCT 处理后的一系列子块所得结果，整合各子块得到的直流系数（DC）为一次输入给哈达玛变换。那么根据傅立叶变换特性，WHT 将对已经分离的低频权重信息，再次进行一次基于基底函数的分离。

这个做法在 H.264 中得到了较为充分的体现。

不过，随着小模型介入了二次变换压缩直流系数矩阵的过程，这套基于哈达玛变换（WHT）的压缩手段，最终还是被压缩比和还原程度更高的，以 低频不可分变换（LFNST）为代表的高频凋零技术，替代了原有的作用。

因为如上的缘故，在现行最新的规格中，以压缩冗余为目的频域数据分离，大都仍然采用整数离散正余弦变换（IDST/IDCT）为主要入口技术。哈达玛变换（WHT）则相对局限的，被使用在 SATD 上。