JPEG - 构思与实践/变换和量化

余弦变换

使用 YCbCr 色彩表示方法，我们可以说图片是由三张图片组成的，其中第一张比另外两张更重要。这三张图片被称为图片的分量：Y 分量，Cb 分量和 Cr 分量。但是我们可以继续这个过程，获得更多重要的和更不重要的元素。假设我们有一张灰度图片，那么我们可以想象从一张只有一色的图片开始，即图片中所有颜色平均值的颜色，然后通过添加引入越来越多的变化，直到最后得到完整的图片。然后可能结果是，我们可以忽略最后的一些操作，因为我们无法区分新的添加部分。然而，颜色函数的扩展（我们心中所想）在由重要性越来越小的项组成的一系列项中，只对二次图片有效。因此，我们的图片必须分成正方形。这些正方形必须相当小，因为计算次数随正方形边长的四次方增长，这意味着如果将小正方形增大一倍，计算次数将增大四倍。另一方面，如果小正方形太小，则程序的效果会减弱。小正方形的最佳边长似乎是 8-12 像素。在 JPEG 中，图片被分成 8x8 的正方形，但在这里我们将看到如果我们让正方形的边长与 8 不同会发生什么：我们已经安排了程序，以便我们可以选择 2、3、...、24 中的任意一个数字作为边长 s。

因此，我们对图片进行规则的 sxs 正方形划分。在 JPEG 中，这是从左上角开始，从左到右逐行，从上到下进行，就像我们阅读文本一样。然而，在我们的理论演示程序中，我们将以另一种方式遍历图片，即从左到右逐列，以锯齿形上下移动，这样正方形始终有一条公共边。我们将假设图片的宽度和高度可以被 s 整除，或者更确切地说：我们只使用图片中位于最大区域（从左上角开始）内的部分，该区域可以被规则地分成 sxs 的正方形。我们用来扩展正方形内颜色函数的方法是离散余弦变换 (DCT)，定义如下。

我们假设我们有一个边长为 N 的二次图片（灰度），并且我们假设 N 很大，以便我们可以谈论“真实”的图片。这张图片是一个 NxN 的颜色值矩阵（字节）：f(i, j), i, j = 0, 1, ..., N-1（记住 (0, 0) 对应于左上角，因此纵坐标 j 向下测量）。我们想用纯双振荡的形式表达 f(i, j)，例如 f_{u, v}(i, j) = c(i, u) ∙ c(j, v), u, v = 0, ..., N-1，其中函数 c(i, u) 由下式给出

c(i,u)=\cos {\frac {(2i+1)u\pi }{2N}}

请注意，f_{0, 0}(i, j) 是常数 1，函数 f_{u, v}(i, j) 的振荡幅度越大，u 或 v 越大。因此，我们想将 f(i, j) 表达为 N² 个项的双重求和

f(i,j)=\sum _{u=0}^{N-1}\sum _{v=0}^{N-1}h(u,v)\cdot c(i,u)\cdot c(j,v)

其中 h(u, v) 是（实数）系数。第一个项（u = 0 和 v = 0）是一个常数函数，是 N² 个数字 f(i, j) 的平均值。后面的项（作为 i 和 j 的函数）的振荡越来越大，如果我们省略最后的一些项，我们就会得到一个没有最高频率的 f(i, j) 近似值。

我们可以用以下方法找到 f(i, j) 的这个级数表达式中的系数 h(u, v)。设 NxN 矩阵（实数）g(u, v)（u, v = 0, 1, ..., N-1）定义为

g(u,v)={\frac {2\lambda (u)\lambda (v)}{N}}\sum _{i=0}^{N-1}\sum _{j=0}^{N-1}c(i,u)\cdot c(j,v)\cdot f(i,j)

其中 λ(u) 在 u ≠ 0 时为 1，在 u = 0 时为 1/√2。矩阵 g(u, v) 被称为矩阵 f(i, j) 的（正向）离散余弦变换 (DCT 或 FDCT)。请注意，g(0, 0) 是颜色值的平均值的 N 倍。有一个公式，从 NxN 矩阵 g(u, v) 中，可以将我们带回原始的 NxN 矩阵 f(i, j)，并且它具有类似的外观

f(i, j) = (2/N)∑_{u, v = 0, ..., N-1}λ(u)λ(v) ∙ c(i, u) ∙ c(j, v) ∙ g(u, v)

f(i,j)={\frac {N}{2}}\sum _{u=0}^{N-1}\sum _{v=0}^{N-1}\lambda (u)\cdot \lambda (v)\cdot c(i,u)\cdot c(j,v)\cdot g(u,v)

由于这个公式具有 f(i, j) 级数展开的所需形式，因此我们看到展开是可能的，并且系数 h(u, v) 由 h(u, v) = (2λ(u)λ(v)/N) g(u, v) 给出。这个从 g(u, v) 中获得 f(i, j) 的公式被称为逆离散余弦变换 (IDCT)。

如果我们假设这个公式是正确的，那么这两个公式是彼此的逆公式，其中 α 和 β 是奇数整数

{\frac {1}{2}}\sum _{u=0}^{N-1}\cos {\frac {\alpha u\pi }{2N}}{\frac {\beta u\pi }{2N}}=0\;\;for\;\alpha \neq \beta \;and\;{\frac {N}{2}}for\;\alpha =\beta

现在让我们设定 N = 280，例如，这样我们考虑一个 280x280 像素的（灰度）图像。我们转换颜色值 f(i, j)（它们是字节），并且从转换后的值 g(u, v)（四舍五入到可以为负的整数）中，我们构建一个图像，现在是彩色的，因为数字变化很大，因此不能用字节来衡量。新图像（也是 280x280 像素）可能看起来像左侧的图像

余弦变换后的图像
重建后的图像

在变换之后，“颜色”值（在这个例子中）从大约 -6000 到 24000 不等，并且颜色化是通过一个小技巧来实现的：我们从这些值中减去了最小值，使其变为非负值，乘以 (max - min)/65535 并四舍五入，得到从 0 到 65535 = 256² - 1 的整数。这个区间内的整数可以写成 a + 256xb 的形式，其中 a 和 b 是字节，并且我们可以将它们与 RGB 三元组 (0, b, a) 关联，例如（最小值和最大值必须在重建图像的程序中引入，但这可以通过将它们写入 BMP 文件头中的某些空闲条目来完成）。上面的右侧图像是重建后的图像。

如果在重建过程中，我们删除 u > N/2 或 v > N/2 的项，这样我们只利用四分之一的项，我们会得到一张几乎和原始图像一样的图像 - 只是一点模糊

所有项
四分之一的项

但是，在 JPEG 过程中，项实际上并没有被删除：系数被近似值所取代，其中高频系数的近似值比低频系数的近似值偏离原始系数更多。就是这样量化过程执行的。

现在对于被分成 sxs 方块的（彩色）图像。在余弦变换之后，我们每个 sxs 方块和每个分量（彩色图像）都有 s² 个数字。从这些数字中，我们可以重建图像，而且正是这些数字我们要在压缩后写入文件。但是，如果我们没有量化就这样做（也就是说，没有以某种方式使数字在数值上更小），那么余弦变换将一无所获。除了下面要解释的量化之外，我们还可以做另一件事，它可以使一些值变小，并且效果很好：我们可以用每个变换值的第一项（平均值 g(0, 0)）与其前面相同类型的第一项（即，对于同一分量的先前方块）的差异来替换。矩阵 g(u, v) （u, v = 0, ..., s-1）的第一项 g(0, 0) 称为 *DC* 项，而其他 s²-1 项，g(u, v)，u > 0 或 v > 0，称为 *AC* 项。因此，我们用每个 DC 项（对于给定的 sxs 方块和分量）与其前一个 sxs 方块（以及同一个分量）的 DC 项的偏差来替换它。

量化

如果没有量化过程，唯一的信息丢失来源将是四舍五入实数以获得整数。由于平均数 (g(u, v) 对于接近 0 的 u 或 v) 相当大，因此这些误差并不显著：如果我们现在制作文件（即，使用余弦变换，但没有量化），并应用压缩过程（它是无损的），那么我们可以从文件中重建的图像将几乎无法与原始图像区分，但它仍然会占用太多空间。正是量化过程缩小了尺寸并引入了偏差。通过量化，我们理解的是，将 f(i, j) 在纯双重振荡中的展开系数，即来自余弦变换的数字 g(u, v)，通过除以取决于 (u, v) 的数字 q(u, v) 然后四舍五入到整数来使其更小。当从文件中绘制图像时，我们会乘以我们除以的数字。例如，如果 g(u, v) = 135.6 除以 q(u, v) = 36，结果被四舍五入，我们得到 4，当我们用 36 乘以 4 时，我们得到 144。然后我们引入了可能无关紧要的误差，因为它们不是颜色值中的误差，而是在余弦变换后的数字中的误差，并且主要项，即对于接近 0 的 u 和 v 的 g(u, v)，被比不太重要的项，即对于不接近 0 的 u 或 v 的 g(u, v)，小得多的数字 q(u, v) 量化。此外，由于 Y 分量的数字比来自 Cb 和 Cr 分量的数字更重要，因此这些数字的余弦变换后的数字可以被更大的数字 q(u, v) 量化。

JPEG 过程中使用的 Y 分量和两个颜色分量的 8x8 矩阵 q(u, v) (u, v = 0, ..., 7) 是根据实验选择的。因此，有几种这样的表格。精心选择的数字意味着我们可以压缩更多，而不会损坏图像，但我们总是会遇到图像的一部分有令人不安的缺陷，这迫使我们选择更小的量化值。通常情况下，一个 *质量因子* qf 会被引入到制作文件的程序中，以便可以调整量化数字。例如，我们可以安排这种依赖关系，以便最佳质量 - qf = 100 - 意味着没有量化（所有量化数字都被设置为 1），而 qf = 75 意味着使用给定的量化表 q(u, v)。量化表 q(u, v) 和质量因子 qf 在从文件中绘制图像时再次应用。当然，质量因子必须出现在文件头中，而表格只需要出现在生成文件和绘制图像的程序中。

在我们的程序中，我们必须有针对不同的小方块边长（从 2 到 24）的量化表，因此我们必须用数学方法构建这些表 - 尽可能简单。我们首先选择 qf = 75 的 q(u, v) 值，然后找到一个公式，以便所有这些值在 qf = 100 时都变为 1。根据 *第二部分* 中显示的表格，对于 qf = 75，我们为边长 s 以及 Y 分量和颜色分量分别选择以下值

q(u, v) = (s/8)∙12∙(1 + 4∙√(u² + v²)/ s)

q(u, v) = (s/8)∙20∙(1 + 5∙√(u² + v²)/ s)

我们安排程序，以便我们可以对 Y 分量和颜色分量使用不同的质量因子。我们根据 qf 调整数字 q(u, v)，方法如下

q(u, v)^{√(100 - qf)/5}

下面的左侧图像（对于边长 s = 8）没有量化 (qf = 100)，文件占原始 BMP 文件的 60%。在右侧图像中，qf = 70，文件现在只占原始文件的 6%

qf = 100
qf = 75

当我们将量化表的矩阵和余弦变换后的量化数字的矩阵放入文件时，我们必须以某种方式将这些数字线性排列。我们这样做的方法是，最重要的是（对于接近 0 的 u 和 v）排在最前面，即通过应用这种之字形原理

之字形原理

如果 s 是正方形的边长，那么对应于点 (i, j) (i, j = 0, 1, ..., s-1) 的之字形值 m (= 1, 2, ..., s²) 可以用这个程序计算

k = i + j
if k < s then
	begin
		l = (k * (k + 1)) div 2
		if k mod 2 = 0 then
			m = l + i + 1
		else
			m = l + j + 1
	end
if k = s then
	m = (s - 2) * (s - 2) + i
if k > s then
	begin
		k = 2 * s - 1 - k
		l = s * s - (k * (k + 1)) div 2
		if k mod 2 = 0 then
			m = l + (s - i)
		else
			m = l + (s - j)
	end