最近听说一种图像格式比较流行，想起我曾经是做图像压缩的emmmm，就来研究一下。
QOI（Quite OK Image Format），很好的图像格式（git链接），能快速地无损压缩图像。原理也非常简单，没有各种变换，直接空域处理，而无损压缩，自然也不能量化，好家伙，比JPEG不知简单到哪里去了。说明文档呢，只有一页，代码300余行，确实是图像压缩界的一股清流。
一、编码格式解析
首先，文件头的定义如下：
struct qoi_header_t {
char magic[4]; // magic bytes "qoif"
uint32_t width; // image width in pixels (BE)
uint32_t height; // image height in pixels (BE)
uint8_t channels; // 3 = RGB, 4 = RGBA
uint8_t colorspace; // 0 = sRGB with linear alpha, 1 = all channels linear
};
文件头就是告诉电脑这是个什么文件，怎么解析。QOI的文件头14byte，4byte名字，4byte宽和高，2byte通道和颜色空间信息。这里面真正和编解码有关的只有宽和高（时间2021.12.22，后续可能有逻辑改动，下同）channels和colorspace虽然encode时写进去了，但decode时没用上。
定义完文件头，下面就是正式编码了。整体而言，QOI是按行从上往下，每行从左往右进行编码，不分通道，每个像素RGB(或RGBA)一起编码。对于每一个像素，按照不同的像素值，有四种编码策略：
1.前一像素的重复
2.一个出现过的像素的index
3.和前一个像素的残差
4.直接编码RGB(或RGBA)
注意这四种策略是有序的，优先尝试第一种，如果不行再尝试第二种，以此类推。显然最差的是第四种，相当于没有压缩，所以前面三种策略设计得要巧妙，尽量避免第四种情况。
【1】前一像素的重复
前面出现过的元素，自然就不用再编码了，这种情况一般出现在背景上，当前像素和前一像素的像素值完全相同（第一个像素的“前一像素”定义为R=B=G=0,A=255）。这时候就只需要编码标记位和对应的重复次数就行了。不过有一个限制，最多重复62次（后面解释原因）。如果一个像素3byte，重复n次，此时压缩率3n/1最大。
【2】一个出现过的像素的index
编码过程中，始终维护一个64个元素大小的数组，表示出现过的像素的哈希值，哈希的公式是：
index = (r * 3 + g * 5 + b * 7 + a * 11) % 64
每有一个像素的RGB值，就用这公式算一下，把它存到数组的index位置。如果这地方已经有值了，再看两个像素相不相同（可能出现RGB不一样但index相同的情况），如果相同，编码标记位和index。如果不相同，就覆盖，用后面3、4策略。此时压缩率3/1。
【3】和前一个像素的残差
残差就更好理解了，图像压缩领域的经典方法。QOI里的残差分为大小两种，给了不同的标记位。如果当前像素和前一像素的RGB差值均为-2到1（为啥不是-1到2？虽说差不多），就用小残差。小残差只有1byte，所以去掉标记位2bit后，RGB三个通道的残差各剩2bit，所以只能存4个值，而且最小值-2记为b00，最大值1记为b11。如果残差大一些，G的残差为-32到31，R和B的残差与G残差的差为-8到7，那么可以用大残差存储，只有2byte。如果残差更大，那不好意思，存不下了，只能用策略4。当然，两种残差都是在A不变的前提下，如果A不一样，只能用策略4。此时小残差压缩率3/1，大残差压缩率3/2。
【4】直接编码RGB(或RGBA)
以上策略都不行，干脆不压缩了，该是多少就是多少了。此时除了编码原有的RGB3byte，还需多编码1byte标记位，压缩率3/4（反向压缩）。
标记位说明
上面说了那么多标记位，到底是个啥？其实就是编解码器共同约定好的一套符号，有点像什么数据交换协议，都按照这个标准进行。QOI定义的标记位如下：
#define QOI_OP_INDEX 0x00 /* 00xxxxxx */
#define QOI_OP_DIFF 0x40 /* 01xxxxxx */
#define QOI_OP_LUMA 0x80 /* 10xxxxxx */
#define QOI_OP_RUN 0xc0 /* 11xxxxxx */
#define QOI_OP_RGB 0xfe /* 11111110 */
#define QOI_OP_RGBA 0xff /* 11111111 */
编码器是把一个个像素转成二进制码存起来，解码器是读这些0101的数据，恢复图像。所以按照约定，解码器先解出4byte，如果是“qoif”，不就说明这是QOI的码流嘛，再往后解码宽高啥的。除了文件头的14byte，后面也一样。先解出1byte标记位，如果前2bit是00，就说明是index类（对应上面策略2），后面的6bit就是index喽；要是01呢，说明是小残差，等等。但注意如果是10，说明是大残差，需要再读取1byte才能解码出当前像素的RGB值。所以如果前面是11，最后2bit就不能是10或11了，否则解码的时候不知道是这个像素重复多次呢（策略1）还是直接解码出RGB呢（策略4）。这也就解释了为什么重复最多62次，因为63和64已经被其他标记位占据了，这里只能空出来。
最后，QOI的结束码是0x01，不也和index类重复了吗。其实这里没关系了，因为只要宽×高的所有像素没有被填满，所有的0x01都被当成index类且index=1。所有像素解码完后，0x01当成啥都无所谓了，因为也没有位置放新的像素了。
二、性能和压缩率分析
性能首先不谈了，无空间转换无量化无熵编码，快得飞起。压缩率按作者做的实验确实比PNG高一些，但不知道压缩细节纹理比较丰富的图像如何。根据上面的分析，如果RGB都不压缩情况会非常糟糕，但平均而言还是可以得到一个不错的压缩率。
以上是本人对QOI的一些初步分析，如有错误请指出，如果codec有变化本文也会更新。
