块傅里叶基和JPEG

块傅里叶基，是一种用于表示信号的时间-频率基。这些基的使用有两种主要的理由：其一，基于函数分解的正则性，系数呈递减趋势；其二，可将其解释为卡尔霍宁-洛厄夫 (Karhunen-Loève) 基（或某种近似），用于特定的随机过程建模。

连续时间

傅里叶级数

复指数函数族 $e_n(t)=\exp (i 2 \pi n t)$ （其中 $n \in \mathbb{Z}$ ) 是定义在 $L_2(0,1)$ 上的一个正交基。这使得可以在 $L_2(0,1)$ 空间中定义傅里叶级数:

$F_n=\int_0^1 f e_n^* d t =\int_0^1 f(t) \exp (-i 2 \pi n t) d t$

重建公式 (Reconstruction)：

$f=\sum_{n \in \mathbb{Z}} F_n e_n$

傅里叶级数按 $L_2$ 意义上收敛，即：

$\lim _{N \rightarrow \infty}\left\|f-\sum_{n=-N}^N F_n e_n\right\|_2^2=0$

但这并不保证简单或一致收敛。
分解系数 $F_n$ 的递减速度至少与 $f$ 的 Sobolev意义下的正则性相关。

回顾：如果一个函数 $f$ 属于 Sobolev空间 $H_s$ ，则它属于 $L_2$ ，并且它的导数直到 $s$ 阶都是可定义的。此外，如果 $f$ 的支撑严格包含在 $] 0,1[$ 中，则:

$\sum_{n \in \mathbb{Z}} n^{2 s}\left|F_n\right|^2<\infty$

我们有：$F_n^{(s)}=(-2 i \pi n)^s F_n$，且$f^{(s)} \in L_2(0,1)$。假设$f$的支撑严格包含在$]0,1[$。观察：

$\varepsilon_N=\left\|f-f_N\right\|_2^2=o\left(N^{-2 s}\right)$

块傅里叶基

为了从 $L_2(0,1)$ 上的基扩展到 $L_2(\mathbb{R})$ ，需要在整个实数轴上表示函数。具体方法是将定义在 $[0,1]$ 区间内的函数 $f$ 进行分段扩展：将其分割为多个区间 $[m, m+1]$ 的函数片段，每个片段由函数 $f$ 在 $[0,1]$ 上的行为通过平移实现：

$g = f_{1,[m, m+1]}, \ g\in L_2(\mathbb{R})$

由于函数通常没有理由满足周期性条件，因此系数的递减通常非常缓慢。

余弦基 Bases de cosinus

为了获得令人满意的递减性质，可以使用余弦基。

Neumann-Neumann 余弦基

$c_n(t)=\lambda_n \sqrt{2} \cos (\pi n t), \quad avec \quad \lambda_0=\sqrt{2} , \ \lambda_n=1 \text { si } n>0 \text {. }$

Neumann-Neumann 余弦基满足 Neumann 边界条件，即基函数的导数在边界处为零。这对应于函数的平滑延拓，避免了周期性假设下可能出现的不连续性问题。

由于余弦基在边界处是平滑的，分解的系数$F_n$能以较快速度递减。这种性质弥补了块式傅里叶基在边界处引入不连续性的问题

Neumann-Dirichlet 余弦基

$c_n(t)=\sqrt{2} \cos (\pi(n+1 / 2) t), \quad n \geq 0$

该余弦基在 $[0,1]$ 的两端分别满足不同的边界条件：

在 $t=0$ ，满足 Neumann 边界条件（导数为零）。
在 $t=1$ ，满足 Dirichlet 边界条件（函数值为零）。
这意味着函数在一端光滑，但在另一端具有较强的约束（函数值为零）。

Neumann-Dirichlet 余弦基通常无法恢复快速递减的傅里叶系数，因为它在边界 $t=1$ 的 Dirichlet 条件会引入较大的不连续性。这种不连续性影响了系数的平滑性和递减速度。

有限维度

在本文中，向量的索引从 0 开始。

离散傅里叶变换（Transformée de Fourier discrète，简称 TFD）

向量族 $\left(em\right){m=0, \ldots, N-1}$ 的定义为:

$e_m=(1, \ldots, \exp (i 2 \pi n m / N), \ldots, \exp (i 2 \pi(N-1) m / N)),$

该族在常数因子上是复数域 $\mathbb{C}^N$ 中的一个正交基。
维度为 $N$ 的向量 $\mathbf{x}$ 的离散傅里叶变换（TFD）通过以下基变换给出：

$\begin{gathered} \mathbf{F}_{n m}=\exp (-i 2 \pi n m / N) \\ \mathbf{X}=\mathbf{F} \mathbf{x}, \\ X_m=\sum_{n=0}^{N-1} x_n \exp \left(-i 2 \pi n m / N\right), \\ x_n=\frac{1}{N} \sum_{k=0}^{N-1} X_m \exp (i 2 \pi n m / N) \end{gathered}$

其中$F$有$FF^H = NI$

离散傅里叶变换可以看作一种 Karhunen-Loève 基。对于协方差矩阵是循环矩阵的随机向量，傅里叶基正是其 Karhunen-Loève 基。

DCT-I 和 DCT-III：DCT-I 和 DCT-III 的性质与 DCT-II 和 DCT-IV 相似，但它们的对称性和索引定义不同。例如，DCT-I 的对称点为 $0$ 而非 $-1 / 2$ 。

DCT-II 是最常用的变换类型，广泛用于图像压缩（如 JPEG）和信号处理。

DCT-IV 的应用相对较少，但在某些特定场景下，如需要额外的紧凑性或特定边界条件时，是一种有效的选择。

DCT-II 离散余弦变换-II

DCT-II的基向量为：

$c_{m n}^{\mathrm{II}}=\lambda_m \sqrt{\frac{2}{N}} \cos \left(\frac{m \pi}{N}\left(n+\frac{1}{2}\right)\right)$

其中:

$\lambda_0=\sqrt{2}$ ，此外 $\lambda_m=1$ ；
$N$ 是向量维度；
$m, n$ 分别是基向量和数据的索引。

对于大的 $N$ ，DCT-II 基逐渐接近于平稳过程的 Karhunen-Loève 基。这表明，DCT-II 在统计意义上是最优的，用于分解和表示平稳信号。
类似于 Neumann-Neumann 余弦基，DCT-II 通过改变基，可以有效处理非周期信号，且分解系数 $c_{m n}$ 的递减性质依然良好。

DCT-IV（离散余弦变换-IV）

DCT-IV的基向量为：

$c_{m n}^{\mathrm{IV}}=\sqrt{\frac{2}{N}} \cos \left(\frac{\pi}{N}\left(m+\frac{1}{2}\right)\left(n+\frac{1}{2}\right)\right)$

DCT-IV 通常不会单独使用，而是用于更紧凑地计算 DCT-II，或者用于 Neumann-Dirichlet 基的连续版本。

JPEG编码

JPEG格式是目前最常用的有损图像压缩格式之一。

编码算法分为以下步骤：

基于减少熵的分解信号；
量化；
编码。

每个编码器因这三个步骤的实现选择而有所不同。

为了进行图像编码，添加了一个颜色处理的初始步骤。

颜色处理

描述像素的三个RGB（红、绿、蓝）值被替换为 $Y^{\prime}, C_B, C_R$ (亮度和两个色度值），定义如下：

$\begin{gathered} Y^{\prime}=\left(0.299 \cdot R_D^{\prime}\right)+\left(0.587 \cdot G_D^{\prime}\right)+\left(0.114 \cdot B_D^{\prime}\right) \\ C_B=128-\left(0.168736 \cdot R_D^{\prime}\right)-\left(0.331264 \cdot G_D^{\prime}\right)+\left(0.5 \cdot B_D^{\prime}\right) \\ C_R=128+\left(0.5 \cdot R_D^{\prime}\right)-\left(0.418688 \cdot G_D^{\prime}\right)-\left(0.081312 \cdot B_D^{\prime}\right) \end{gathered}$

逆变换为：

$\begin{gathered} R_D^{\prime}=Y^{\prime}+1.402 \cdot\left(C_R-128\right) \\ G_D^{\prime}=Y^{\prime}-0.344136 \cdot\left(C_B-128\right)-0.714136 \cdot\left(C_R-128\right) \\ B_D^{\prime}=Y^{\prime}+1.772 \cdot\left(C_B-128\right) \end{gathered}$

这里的RGB值经过了非线性校正，因此标记为’。
这种转换可以部分解耦三个通道，并将人眼非常敏感的亮度信息与颜色信息分开。颜色信息随后可以以因子2进行下采样。

信号分解

用于信号分解的最优基是 Karhunen-Loève（卡尔霍宁-洛伊夫）基。然而，它取决于图像模型，并且通常没有允许快速计算的结构。

因此，一般更倾向于使用基于 $8 \times 8$ 块的二维DCT-II（离散余弦变换II）。如上所述，DCT对于平稳过程近似于Karhunen-Loève基，并且可以高效计算。

下面的代码提供了一个例子。

def dct8(img):
    step = 8
    d = np.zeros(img.shape)
    Nx = img.shape[0]//step
    Ny = img.shape[1]//step
    
    for n in range(Nx):
        for m in range(Ny):
            patch = img[step * n : step * (n + 1), step * m : step * (m+ 1)]
            d[step * n : step * (n + 1), step * m : step * (m+ 1)] = fft.dctn(patch, norm='ortho')
            
    return d

def idct8(img):
    step = 8
    d = np.zeros(img.shape)
    Nx = img.shape[0]//step
    Ny = img.shape[1]//step
    
    for n in range(Nx):
        for m in range(Ny):
            patch = img[step * n : step * (n + 1), step * m : step * (m+ 1)]
            d[step * n : step * (n + 1), step * m : step * (m+ 1)] = fft.idctn(patch, norm='ortho')
            
    return d

分解后的熵将有效减少

量化

在JPEG格式中，量化可以根据系数使用不同的权重。这是为了考虑人眼对不同频率的敏感性。

实际上，定义具有权重 $w_n^2$ 的量化误差为:

$d=\sum_{n=1}^N \frac{d_n}{w_n^2},$

这等价于将前面课程中的定理应用于加权系数 $X_n^w=X_n / w_n$ 。
因此，量化步长为 $\Delta_n=w_n \Delta$。
对总误差影响最小的系数被粗略量化。
这些量化步长由编码器根据用户提供的质量目标确定，并存储在文件中。
通常，量化步长随频率增加。每个编码器使用的量化参数不同，因此不同编码器的参数并不具有相同的效果。