让我们编写视频编解码器 - 第 3 部分：静止图像

在本系列的前几部分中，我们了解了离散余弦变换，从它的数学定义到它在实际示例中的实现。此外，我们还看到了 DCT 在频域中表示数据的能力如何实现有损数据压缩。

现在，我们正在迈出下一步。我们最终将画出一条线，将我们一直在讨论的这些抽象数字数组与它们可以表示的实际图像联系起来。

到本文结束时，我们将重新发现大约 80% 的实际 JPEG 图像压缩过程。

矩阵

在上一篇文章中，我们介绍了 2D-DCT。现在，让我们看一下该公式的稍微调整后的版本：

变量u和v表示 DCT 编码二维数组中值的水平和垂直偏移量。如果x == 0 ，则函数α(x)等于1/sqrt(2)否则等于1 。最后， x和y表示像素在源图像中的位置。

这可能看起来并不明显，但相同的计算可以表示为以下形式的矩阵乘法：

在这个公式中， DCT是 DCT 矩阵， T表示矩阵转置， IMG是源图像。

请记住，此操作的复杂性与源图像的大小成正比。为了管理任何大小的图像并减少工作量，我们将计算限制为 8×8 像素的图像块。

虽然真实图像往往具有更高的分辨率，但我们可以将它们视为由许多独立的 8x8 块组成。

以下是我们如何计算产生所需效果的 DCT 矩阵：

 var dctMatrix: [Float] = Array(repeating: 0.0, count: 8 * 8) for i in 0 ..< 8 { for j in 0 ..< 8 { let a: Float if i == 0 { a = sqrt(1.0 / 8.0) } else { a = sqrt(2.0 / 8.0) } dctMatrix[j * 8 + i] = a * cos((2.0 * Float(j) + 1) * Float(i) * Float.pi / (2.0 * 8)) } }

dctMatrix的值为：

 0.35 0.49 0.46 0.42 0.35 0.28 0.19 0.10 0.35 0.42 0.19 -0.10 -0.35 -0.49 -0.46 -0.28 0.35 0.28 -0.19 -0.49 -0.35 0.10 0.46 0.42 0.35 0.10 -0.46 -0.28 0.35 0.42 -0.19 -0.49 0.35 -0.10 -0.46 0.28 0.35 -0.42 -0.19 0.49 0.35 -0.28 -0.19 0.49 -0.35 -0.10 0.46 -0.42 0.35 -0.42 0.19 0.10 -0.35 0.49 -0.46 0.28 0.35 -0.49 0.46 -0.42 0.35 -0.28 0.19 -0.10

如您所见，它只是一个数字数组。每次应用变换时都不需要重新计算矩阵值，因此我们可以在代码中将它们保存在常量数组中。

此代码执行 8x8 矩阵乘法：

 func matrixMul8x8(m1: [Float], m2: [Float], result: inout [Float]) { for i in 0 ..< 8 { for j in 0 ..< 8 { var acc: Float = 0.0 for k in 0 ..< 8 { acc += m1[i * 8 + k] * m2[k * 8 + j] } result[i * 8 + j] = acc } } }

我们计算 8x8 DCT 如下：

 func dct(_ block: [Float]) -> [Float] { var tmpBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) var resultBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) matrixMul8x8(m1: dctMatrixT, m2: block, result: &tmpBlock) matrixMul8x8(m1: tmpBlock, m2: dctMatrix, result: &resultBlock) return resultBlock }

可以简单地通过交换常规和转置 DCT 矩阵来获得逆 DCT：

 func idct(_ block: [Float]) -> [Float] { var tmpBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) var resultBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) matrixMul8x8(m1: dctMatrix, m2: block, result: &tmpBlock) matrixMul8x8(m1: tmpBlock, m2: dctMatrixT, result: &resultBlock) return resultBlock }

大局观

现在，我们已准备好将我们的知识应用到真实图像中。让我们来处理这个：

想象一下，我们有代码将此图像加载为数字数组，其中每个数字代表相应位置像素的亮度：

 func loadImage(width: Int, height: Int) -> [Float] { ... }

假设图像是 256x256 像素，以下值将对应于左上角：

 -2.00 3.00 -7.00 -6.00 -3.00 -5.00 -13.00 -9.00 -2.00 4.00 -7.00 -6.00 -3.00 -5.00 -13.00 -9.00 -3.00 -1.00 -8.00 -7.00 -6.00 -8.00 -14.00 -12.00 -7.00 -13.00 -9.00 -15.00 -15.00 -12.00 -23.00 -22.00 -18.00 -17.00 -11.00 -15.00 -11.00 -14.00 -20.00 -20.00 -21.00 -19.00 -20.00 -20.00 -18.00 -17.00 -19.00 -19.00 -16.00 -17.00 -20.00 -19.00 -17.00 -21.00 -24.00 -21.00 -19.00 -18.00 -20.00 -22.00 -19.00 -25.00 -20.00 -22.00

为了数学上的方便，我们不将像素亮度表示为0.0到255.0之间的数字，而是减去128.0 。换句话说，我们将值集中在0.0而不是128.0附近。

然后，我们将dct函数应用于图像的每个 8x8 块：

 let values: [Float] = loadImage() // convert RGB to -128.0 ... 128.0 var destinationValues: [Float] = Array(repeating: 0.0, count: values.count) for j in 0 ..< height / 8 { for i in 0 ..< width / 8 { let block = extractBlock(values: values, width: width, x: i * 8, y: j * 8) let resultBlock: [Float] = dct(block) storeBlock(values: &destinationValues, width: width, block: resultBlock, x: i * 8, y: j * 8) } } storeImage(destinationValues) // convert back to RGB

结果是这张图片：

尽管它几乎无法识别为照片，但某些图案（如帽子）仍然可见。有趣的是，有很多黑色像素。事实上，大多数像素都是黑色的。让我们放大其中一个 8x8 块：

这个 8x8 块说明了频域表示的全部内容。非零值倾向于聚集在块的左上角。当我们向右下角移动时，出现大值的可能性会显着降低。

这表明左上角的值对图像更重要。

我们可以通过编写一个“压缩”函数来证明这一点，该函数通过将右下角的一些值设置为0.0来消除它们：

 func compress(_ block: [Float], level: Int) -> [Float] { var resultBlock: [Float] = block for y in 0 ..< 8 { for x in 0 ..< 8 { if x >= 8 - level || y >= 8 - level { resultBlock[y * 8 + x] = 0.0 } } } return resultBlock }

调整我们的处理循环后：

 for j in 0 ..< height / 8 { for i in 0 ..< width / 8 { var block = extractBlock(values: values, width: width, x: i * 8, y: j * 8) block = dct(block) block = compress(block, level: 3) block = idct(block) storeBlock(values: &destinationValues, width: width, block: block, x: i * 8, y: j * 8) } }

我们得到这个图像：

花点时间考虑一下发生了什么。我们已经为每个图像块消除了 64 个值中的 39 个，并且仍然生成了与原始图像非常相似的图像。这是 60% 的压缩率，仅通过乘以矩阵并确定性地丢弃数据即可实现！

当我们丢弃 86% 的 DCT 系数时，会发生这种情况：

量化

将 DCT 系数存储为浮点数会非常浪费，通常需要 4 个字节的存储空间。相反，我们应该将它们四舍五入到最接近的整数。对于 8x8 的块，每个值都可以用一个 2 字节的整数表示。

让我们重新审视我们之前检查过的块。它的（四舍五入的）数值表示是：

 209 -296 -49 43 -38 22 -6 1 39 24 -37 11 -4 -3 2 6 -15 16 -17 0 13 -4 0 5 16 4 2 4 -6 4 -3 -5 -11 4 -1 3 1 -3 6 3 6 -2 2 4 -2 -2 -4 -1 -6 1 0 1 -1 0 3 -1 0 0 0 0 -1 -1 -2 1

正如我们之前在视觉上确认的那样，较大的值更有可能出现在靠近左上角的位置。但是，并非每个块都遵循这种模式。这是我们图像中的另一个块：

此块不遵守 DCT 值的共同分布。如果我们继续盲目地丢弃右下角的值，图像的某些部分可能会显示更多的压缩伪影。为了避免这种情况，我们需要决定哪些块比其他块需要更多的数据。

一个简单而优雅的解决方案利用了我们之前发现的集群属性。这叫做“量化”。我们将 DCT 值除以不同的系数。为了方便起见，我们将使用一个包含每个 DCT 系数值的表：

 16.50 11.50 10.50 16.50 24.50 40.50 51.50 61.50 12.50 12.50 14.50 19.50 26.50 58.50 60.50 55.50 14.50 13.50 16.50 24.50 40.50 57.50 69.50 56.50 14.50 17.50 22.50 29.50 51.50 87.50 80.50 62.50 18.50 22.50 37.50 56.50 68.50 109.50 103.50 77.50 24.50 35.50 55.50 64.50 81.50 104.50 113.50 92.50 49.50 64.50 78.50 87.50 103.50 121.50 120.50 101.50 72.50 92.50 95.50 98.50 112.50 100.50 103.50 99.50

更重要的位置对应于较低的除数，反之亦然。我们通过将量化数据乘以表中的系数来执行反量化步骤。

这些函数分别执行量化和反量化步骤：

 func quantize(_ block: [Int], table: [Float]) -> [Int] { var result: [Int] = Array(repeating: 0, count: block.count) for i in 0 ..< block.count { result[i] = Int(round(Float(block[i]) / table[i])) } return result } func dequantize(_ block: [Int], table: [Float]) -> [Float] { var result: [Float] = Array(repeating: 0, count: block.count) for i in 0 ..< block.count { result[i] = Float(block[i]) * table[i] } return result }

让我们将量化和反量化合并到我们的代码中：

 block = dct(block) var iblock = rounded(block) iblock = quantize(iblock, table: testTable) block = dequantize(iblock, table: testTable) block = idct(block)

这是第一个块在量化时的样子：

 13 -26 -5 3 -2 1 0 0 3 2 -3 1 0 0 0 0 -1 1 -1 0 0 0 0 0 1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

这是第二块：

 -5 18 -10 0 1 1 1 0 0 3 1 -2 0 1 0 0 -4 0 1 0 1 1 0 0 -1 0 0 -2 0 0 0 0 0 1 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

您会注意到第二个块中有更多非零值。因此，量化步骤允许我们存储更多有用的数据并丢弃其余数据。

结论和下一步是什么？

从基础数学，我们已经找到了对真实图像进行编码和解码的方法。我们直观地看到 DCT 如何将任意数据转换为一组频率，以及某些频率如何比其他频率更重要。

在熟悉了基本压缩之后，我们引入了量化的概念，进一步降低了存储需求。

在下一部分中，我们将转向 RGB 图像并探索进一步压缩结果数据的方法。

本文的代码可以在https://github.com/petertechstories/image-dct找到