QOI 图像格式 -- 理论 & 实现

2022-07-17 22:11 作者:nyasyamorina 0人读过 | 我要投稿

QOI (The Quite OK Image Format) 是一种新的无损图像压缩方式, 它在保持压缩率与 PNG 相近的同时 (比 PNG 大 ~35%), 编码速度达到了 PNG 的 20~50 倍, 而解码速度也有 PNG 的 3~4 倍, 并且它极简的编码解码方式也是一个极大的亮点. 可以在 [QOI 的主页](https://qoiformat.org/) 上找到更多信息.

下面就讲述 QOI 的工作原理并使用 Julia 实现 QOI 的编码解码.

QOI 的图像格式

QOI 图像只能储存 24 位 RGB 或 32 位 RGBA 格式的图像, 对于其他颜色格式的图像 (64 位 RGBA 或 HSV 等) 可以先转为合适的格式后再编码储存, 但这种转换并不是无损的.

QOI 图像文件以 `.qoi` 为文件后缀, 文件的数据内分为 3 个部分: 文件头, 数据块和结束比特串. 其中结束串由 7 个 0 和 1 个 1 (共 8 个字节)组成, 并且结束串对图像解码没有影响.

文件头由 14 个字节构成: 第 0~3 字节为 QOI 图像的标识符 "qoif", 解码器由这 4 字节识别是否为 QOI 编码; 第 4~7 字节为图像的宽度, 是一个以大端储存的 uint32; 第 8~11 字节为图像高度, 同样是大端 uint32; 第 12 字节声明图像的颜色通道, 3 表示为 RGB, 4 为 RGBA; 第 13 字节声明图像的颜色空间, 0 表示 sRGB, 1 表示线性 RGB (无论颜色空间, 透明通道 alpha 都是线性的), 但说实话目前来说并没有看到不同的颜色空间有什么不一样的地方. 文件头仅作为对图像大小和格式的声明, 并不会影响数据块的编码.

QOI 的图像编码

在进行编码时, 图像像素排列为行优先的一维数组, 数组索引如下图所示 (图像的左上角索引为 0)

QOI 里对像素编码一共 6 种方式: QOI_OP_RGB, QOI_OP_RGBA, QOI_OP_DIFF, QOI_OP_LUMA, QOI_OP_RUN 和 QOI_OP_INDEX. 图像编码是逐像素进行的, 通过对比当前像素与上一个像素的颜色值选择合适的编码方式. 当处理第一个像素时 (index = 0), 使用 (r = 0, g = 0, b = 0, a = 255) 当作上一个像素的颜色值. 下面来逐个介绍编码方式:

QOI_OP_RGB & QOI_OP_RGBA

这个编码方式是直接将当前像素的颜色值写入文件内, 并不会进行压缩编码. 为了不让颜色值与其他编码产生的数据弄混, 还要在颜色值前放 1 字节的标签: 0xFE (RGB) 或 0xFF (RGBA). 这种编码的压缩率为 133% (RGB) 或 125% (RGBA)

QOI_OP_DIFF

如果当前像素与上一个像素的颜色值差异非常小的时候, 当前像素可以编码为 1 字节. 记 dr, dg, db, da 为当前像素与上一个像素颜色值的差异 (RGBA) (dr = 当前 r - 上一个 r), 当 da = 0, 并且 dr, dg, db 都在 -2~1 内时进行编码 (-2~1 在 +2 后为 0~3, 刚好可以写进 2 比特), 压缩率为 33% (RGB) 或 25% (RGBA)

QOI_OP_LUMA

与 QOI_OP_DIFF 类似, 但这个编码方式允许颜色差异较大, 并且编码后为 2 个字节. 当满足 da = 0, dg 在 -32~31 内, dr-dg 和 db-dg 在 -8~7 内时编码为, (选择 dg 为主要变化的颜色是因为临近像素的色调变化可能会比亮度变化要小, 并且绿色通道对亮度贡献是最大的) 压缩率为 67% (RGB) 或 50% (RGBA)

QOI_OP_RUN

如果当前像素与上一个像素的颜色值完全相等时, 意味着有可能后面接着的像素颜色值也相等, 那么这时候仅需要记录这串相同颜色值的像素的长度即可. 以当前像素开始往后数, 记颜色相同的像素个数为 run, 为了保证编码后只得出 1 字节, run 应该在 1~62 内, 当实际上 run 大于 62 时, 应该进行多次 QOI_OP_RUN 编码. (如果 run 取 63, 64 编码为 0xFE, 0xFF, 这与 QOI_OP_RGB(A) 的标签相同, 会导致解码器错误). 压缩率为 ≤33% (RGB) 或 ≤25% (RGBA)

QOI_OP_INDEX

在 QOI 编码时, 除了两个像素之间的比较外, 还有 1 个长度为 64 的数组 running array, 这个数组的全部元素初始化为 (r = 0, g = 0, b = 0, a = 0). 在历遍像素数组时, 计算上一个像素的颜色值在 running array 里的索引 index_position = (3r + 5g + 7b + 11a) % 64 (RGB 颜色的 a 为 255), 然后在数组上的这个位置写入颜色值. 如果当前像素的颜色值在 running array 上也存在时, 则可以使用相应的索引表示颜色 (索引的计算方式确保在相同颜色的索引也是一样的, 但索引相同不一定颜色相同). 压缩率为 33% (RGB) 或 25% (RGBA)

QOI 图像格式对编码方式的选取并没有强行要求, 就算全部像素都是用 QOI_OP_RGB(A) 编码保存也是可以的, 但这就达不到压缩的目的了. 上面每种编码方式都给出了压缩率, 所以编码时应该尽可能选取压缩率小的编码方式: QOI_OP_RUN ≤ QOI_OP_INDEX = QOI_OP_DIFF < QOI_OP_LUMA < QOI_OP_RGB(A), 尽管 QOI_OP_INDEX 和 QOI_OP_DIFF 有相同的压缩率, 但是前者的计算量稍小于后者, 所以两者都可时, 选择前者会更好.

QOI 的图像解码

解码也就是编码的逆过程: 读取文件头判断是否为 QOI 图像 (头 4 字节应为 "qoif"), 获得图像的宽度, 高度, 颜色通道和颜色空间后, 即可以对数据块进行解码. 解码就是逐字节读取, 判断标签 (字节里的高 2 位), 然后根据标签选择不同的解码方式. (注意, QOI_OP_RGB(A) 与 QOI_OP_RUN 的高 2 位都是 11)

下面就是个人在 Julia 的实现, 对不熟悉 Julia 的人说一下, 里面用到了大量的点语法, 点语法就是逐元素施加相同的操作, 举个例子: floor.([r, g, b] .+ 8) 展开为 [floor(r+8), floor(g+8), floor(b+8)]. 还有 Julia 的索引起始为 1, 而不是大部分语言那样的 0, 如果要指指点点的话, 我们数学人真的是给你们计算机人丢脸了.

另外不得不说的就是, 如果真的很在乎计算速度的话可以出门右转 C/C++, 尽管 Julia 可以做到原生 C/C++ 的速度, 但可能会造成代码篇幅过长, 所以我想说的是, 下面的实现仅确保"足够"简短, 不确保计算速度.

在代码里出现了宏 @inbounds, 这个宏会取消当前代码块里所有的索引边界检查以提升效率, 但这时出现越界的话, 轻则程序闪退, 重则系统崩溃. 所以自己写代码的时候, 除非有足够的信心 (理论上确保或做过足够多的测试), @inbounds 是不推荐写上的.

在开始正片前, 首先引入官方包 ColorTypes 和写几个有用的工具函数

因为 Julia 支持的颜色格式多种多样, 所以这里直接写了一个 _toT4 函数把颜色转为 RGBA 元组. 下面是编码器的大体结构: 判断参数合理, 打开文件, 写入文件头, 主循环和写入结束串:

这里需要注意 Julia 是列优先的, 所以需要 transpose 图像. encoding 部分为:

当写好编码器后, 就可以测试了. 目前来说, qoi 图像还没广泛普及, 众多图片查看器都未适配, 一个挺好的[在线 qoi 查看器](https://floooh.github.io/qoiview/qoiview.html). 在 [QOI 官方 gayhub 页面](https://github.com/phoboslab/qoi) 可以找到更多信息.

下面是相应的解码器主体