前语

最近要搞图画处理服务，其间一个是要完成图片紧缩功能。以前前端开发的时分只要运用canvas现成的API处理下就能完成，后端或许也有现成的API但我并不知道。仔细想想，我从来没有具体了解过图片紧缩原理，那刚好趁这次去调研学习下，所以有了这篇文章来记录。老样子，如有不对的当地，DDDD（带带弟弟）。

咱们先把图片上传到后端，看看后端接收了什么样的参数。这儿后端我用的是Node.js（Nest），图片我以PNG图片为例。

接口和参数打印如下：

@Post('/compression')
@UseInterceptors(FileInterceptor('file'))
async imageCompression(@UploadedFile() file: Express.Multer.File) {
  return {
    file
  }
}

要进行紧缩，咱们就需求拿到图画数据。能够看到，仅有能藏匿图画数据的便是这串buffer。那这串buffer描绘了什么，就需求先澄清什么是PNG。

PNG

这儿是PNG的WIKI地址。

阅览之后，我了解到PNG是由一个8 byte的文件头加上多个的块（chunk）组成。示意图如下:

其间：

文件头是由一个被称为magic number的组成。值为 89 50 4e 47 0d 0a 1a 0a（16进制）。它标记了这串数据是PNG格局。

块分为两种，一种叫要害块（Critical chunks），一种叫辅佐块（Ancillary chunks）。要害块是必不可少的，没有要害块，解码器将不能正确辨认并展示图片。辅佐块是可选的，部分软件在处理图片之后就有或许带着辅佐块。每个块都是四部分组成：4 byte 描绘这个块的内容有多长，4 byte 描绘这个块的类型是什么，n byte 描绘块的内容（n 便是前面4 byte 值的巨细，也便是说，一个块最大长度为28*4），4 byte CRC校验查看块的数据，标记着一个块的完毕。其间，块类型的4 byte 的值为4个acsii码，第一个字母大写表明是要害块，小写表明是辅佐块；第二个字母大写表明是公有，小写表明是私有；第三个字母有必要是大写，用于PNG后续的扩展；第四个字母表明该块不辨认时，能否安全仿制，大写表明未修改要害块时才干安全仿制，小写表明都能安全仿制。PNG官方提供很多界说的块类型，这儿只需求知道要害块的类型即可，分别是IHDR，PLTE，IDAT，IEND。

IHDR

PNG要求第一个块有必要是IHDR。IHDR的块内容是固定的13 byte，包含了图片的以下信息：

宽度 width (4 byte) & 高度 height (4 byte)

位深 bit depth (1 byte，值为1，2，4，8或许16) & 颜色类型 color type (1 byte，值为0，2，3，4或许6)

紧缩办法 compression method (1 byte，值为0) & 过滤办法 filter method (1 byte，值为0)

交错办法 interlace method (1 byte，值为0或许1)

宽度和高度很容易了解，剩余的几个如同都很陌生，接下来我将进行阐明。

在阐明位深之前，咱们先来看颜色类型，颜色类型有5种值：

• 0 表明灰度（grayscale）它只要一个通道（channel），当作rgb的话，能够了解它的三色通道值是持平的，所以不需求剩余两个通道表明。

• 2 表明真实颜色（rgb）它有三个通道，分别是R（赤色），G（绿色），B（蓝色）。

• 3 表明颜色索引（indexed）它也只要一个通道，表明颜色的索引值。该类型往往配备一组颜色列表，具体的颜色是依据索引值和颜色列表查询得到的。

• 4 表明灰度和alpha 它有两个通道，除了灰度的通道外，多了一个alpha通道，能够控制透明度。

• 6 表明真实颜色和alpha 它有四个通道。

之所以要提到通道，是由于它和这儿的位深有关。位深的值就界说了每个通道所占的位数（bit）。位深跟颜色类型组合，就能知道图片的颜色格局类型和每个像素所占的内存巨细。PNG官方支持的组合如下表：

过滤和紧缩是由于PNG中存储的不是图画的原始数据，而是处理后的数据，这也是为什么PNG图片所占内存较小的原因。PNG运用了两步进行了图片数据的紧缩转化。

第一步，过滤。过滤的意图是为了让原始图片数据经过该规矩后，能进行更大的紧缩比。举个例子，假如有一张突变图片，从左往右，颜色顺次为[#000000, #000001, #000002, …, #ffffff]，那么咱们就能够约好一条规矩，右边的像素总是和它前一个左面的像素进行比较，那么处理完的数据就变成了[1, 1, 1, …, 1]，这样是不是就能进行更好的紧缩。PNG现在只要一种过滤办法，便是依据相邻像素作为猜测值，用当时像素减去猜测值。过滤的类型一共有五种，（现在我还不知道这个类型值在哪里存储，有或许在IDAT里，找到了再来删除这条括号里的已确定该类型值储存在IDAT数据中）如下表所示：

Type byte	Filter name	Predicted value
0	None	不做任何处理
1	Sub	左边相邻像素
2	Up	上方相邻像素
3	Average	Math.floor((左边相邻像素 + 上方相邻像素) / 2)
4	Paeth	取(左边相邻像素 + 上方相邻像素 – 左上方像素)最接近的值

第二步，紧缩。PNG也只要一种紧缩算法，运用的是DEFLATE算法。这儿不细说，具体看下面的章节。

交错办法，有两种值。0表明不处理，1表明运用Adam7 算法进行处理。我没有去具体了解该算法，简略来说，当值为0时，图片需求一切数据都加载完毕时，图片才会显示。而值为1时，Adam7会把图片划分多个区域，每个区域逐级加载，显示作用会有所优化，但通常会下降紧缩功率。加载过程能够看下面这张gif图。

PLTE

PLTE的块内容为一组颜色列表，当颜色类型为颜色索引时需求装备。值得注意的是，颜色列表中的颜色一定是每个通道8bit，每个像素24bit的真实颜色列表。列表的长度，能够比位深约好的少，但不能多。比方位深是2，那么22，最多4种颜色，列表长度能够为3，但不能为5。

IDAT

IDAT的块内容是图片原始数据经过PNG紧缩转化后的数据，它或许有多个重复的块，但有必要是连续的，而且只要当上一个块填充溢时，才会有下一个块。

IEND

IEND的块内容为0 byte，它表明图片的完毕。

阅览到这儿，咱们把上面的接口改造一下，解析这串buffer。

@Post('/compression')
@UseInterceptors(FileInterceptor('file'))
async imageCompression(@UploadedFile() file: Express.Multer.File) {
  const buffer = file.buffer;
  const result = {
    header: buffer.subarray(0, 8).toString('hex'),
    chunks: [],
    size: file.size,
  };
  let pointer = 8;
  while (pointer < buffer.length) {
    let chunk = {};
    const length = parseInt(buffer.subarray(pointer, pointer + 4).toString('hex'), 16);
    const chunkType = buffer.subarray(pointer + 4, pointer + 8).toString('ascii');
    const crc = buffer.subarray(pointer + length, pointer + length + 4).toString('hex');
    chunk = {
      ...chunk,
      length,
      chunkType,
      crc,
    };
    switch (chunkType) {
      case 'IHDR':
        const width = parseInt(buffer.subarray(pointer + 8, pointer + 12).toString('hex'), 16);
        const height = parseInt(buffer.subarray(pointer + 12, pointer + 16).toString('hex'), 16);
        const bitDepth = parseInt(
          buffer.subarray(pointer + 16, pointer + 17).toString('hex'),
          16,
        );
        const colorType = parseInt(
          buffer.subarray(pointer + 17, pointer + 18).toString('hex'),
          16,
        );
        const compressionMethod = parseInt(
          buffer.subarray(pointer + 18, pointer + 19).toString('hex'),
          16,
        );
        const filterMethod = parseInt(
          buffer.subarray(pointer + 19, pointer + 20).toString('hex'),
          16,
        );
        const interlaceMethod = parseInt(
          buffer.subarray(pointer + 20, pointer + 21).toString('hex'),
          16,
        );
        chunk = {
          ...chunk,
          width,
          height,
          bitDepth,
          colorType,
          compressionMethod,
          filterMethod,
          interlaceMethod,
        };
        break;
      case 'PLTE':
        const colorList = [];
        const colorListStr = buffer.subarray(pointer + 8, pointer + 8 + length).toString('hex');
        for (let i = 0; i < colorListStr.length; i += 6) {
          colorList.push(colorListStr.slice(i, i + 6));
        }
        chunk = {
          ...chunk,
          colorList,
        };
        break;
      default:
        break;
    }
    result.chunks.push(chunk);
    pointer = pointer + 4 + 4 + length + 4;
  }
  return result;
}

这儿我测试用的图没有PLTE，刚好我去TinyPNG紧缩我那张测试图之后进行上传，发现有PLTE块，能够看一下，成果如下图。

经过比对这两张图，紧缩图片的办法咱们也能窥视一二。

PNG的紧缩

前面说过，PNG运用的是一种叫DEFLATE的无损紧缩算法，它是Huffman Coding跟LZ77的结合。除了PNG，咱们经常运用的紧缩文件，.zip，.gzip也是运用的这种算法（7zip算法有更高的紧缩比，也能够了解下）。要了解DEFLATE，咱们首先要了解Huffman Coding和LZ77。

Huffman Coding

哈夫曼编码忘记在大学的哪门课触摸过了，它是一种依据字符呈现频率，用最少的字符替换呈现频率最高的字符，终究下降平均字符长度的算法。

举个例子，有字符串”ABCBCABABADA”，假如依照正常空间存储，所占内存巨细为12 * 8bit = 96bit，现对它进行哈夫曼编码。

1.核算每个字符呈现的频率，得到A 5次 B 4次 C 2次 D 1次

2.对字符依照频率从小到大排序，将得到一个行列D1，C2，B4，A5

3.按次序构造哈夫曼树，先构造一个空节点，最小频率的字符分给该节点的左边，倒数第二频率的字符分给右侧，然后将频率相加的值赋值给该节点。接着用赋值后节点的值和倒数第三频率的字符进行比较，较小的值总是分配在左边，较大的值总是分配在右侧，顺次类推，直到行列完毕，最后把最大频率和前面的一切值相加赋值给根节点，得到一棵完好的哈夫曼树。

4.对每条途径进行赋值，左边途径赋值为0，右侧途径赋值为1。从根节点到叶子节点，进行遍历，遍历的成果便是该字符编码后的二进制表明，得到：A（0）B（11）C（101）D（100）。

完好的哈夫曼树如下（疏忽箭头，没找到连线- -！）：

紧缩后的字符串，所占内存巨细为5 * 1bit + 4 * 2bit + 2 * 3bit + 1 * 3bit = 22bit。当然在实践传输过程中，还需求把编码表的信息（原始字符和呈现频率）带上。因而终究占比巨细为 4 * 8bit + 4 * 3bit（频率最大值为5，3bit能够表明）+ 22bit = 66bit（抱负状态），小于原有的96bit。

LZ77

LZ77算法仍是第一次知道，查了一下是一种依据字典和滑动窗的无所紧缩算法。（题外话：由于Lempel和Ziv在1977年提出的算法，所以叫LZ77，哈哈哈）

咱们仍是以上面这个字符串”ABCBCABABADA”为例，现假设有一个4 byte的动态窗口和一个2byte的预读缓冲区，然后对它进行LZ77算法紧缩，过程次序从上往下，示意图如下：

总结下来，便是预读缓冲区在动态窗口中找到最长相同项，然后用长度较短的标记来替代这个相同项，然后完成紧缩。从上图也能够看出，紧缩比跟动态窗口的巨细，预读缓冲区的巨细和被紧缩数据的重复度有关。

DEFLATE

DEFLATE【RFC 1951】是先运用LZ77编码，对编码后的成果在进行哈夫曼编码。咱们这儿不去讨论具体的完成办法，直接运用其引荐库Zlib，刚好Node.js内置了对Zlib的支持。接下来咱们继续改造上面那个接口，如下：

import * as zlib from 'zlib';
@Post('/compression')
@UseInterceptors(FileInterceptor('file'))
async imageCompression(@UploadedFile() file: Express.Multer.File) {
  const buffer = file.buffer;
  const result = {
    header: buffer.subarray(0, 8).toString('hex'),
    chunks: [],
    size: file.size,
  };
  // 由于或许有多个IDAT的块 需求个数组缓存最后拼接起来
  const fileChunkDatas = [];
  let pointer = 8;
  while (pointer < buffer.length) {
    let chunk = {};
    const length = parseInt(buffer.subarray(pointer, pointer + 4).toString('hex'), 16);
    const chunkType = buffer.subarray(pointer + 4, pointer + 8).toString('ascii');
    const crc = buffer.subarray(pointer + length, pointer + length + 4).toString('hex');
    chunk = {
      ...chunk,
      length,
      chunkType,
      crc,
    };
    switch (chunkType) {
      case 'IHDR':
        const width = parseInt(buffer.subarray(pointer + 8, pointer + 12).toString('hex'), 16);
        const height = parseInt(buffer.subarray(pointer + 12, pointer + 16).toString('hex'), 16);
        const bitDepth = parseInt(
          buffer.subarray(pointer + 16, pointer + 17).toString('hex'),
          16,
        );
        const colorType = parseInt(
          buffer.subarray(pointer + 17, pointer + 18).toString('hex'),
          16,
        );
        const compressionMethod = parseInt(
          buffer.subarray(pointer + 18, pointer + 19).toString('hex'),
          16,
        );
        const filterMethod = parseInt(
          buffer.subarray(pointer + 19, pointer + 20).toString('hex'),
          16,
        );
        const interlaceMethod = parseInt(
          buffer.subarray(pointer + 20, pointer + 21).toString('hex'),
          16,
        );
        chunk = {
          ...chunk,
          width,
          height,
          bitDepth,
          colorType,
          compressionMethod,
          filterMethod,
          interlaceMethod,
        };
        break;
      case 'PLTE':
        const colorList = [];
        const colorListStr = buffer.subarray(pointer + 8, pointer + 8 + length).toString('hex');
        for (let i = 0; i < colorListStr.length; i += 6) {
          colorList.push(colorListStr.slice(i, i + 6));
        }
        chunk = {
          ...chunk,
          colorList,
        };
        break;
      case 'IDAT':
        fileChunkDatas.push(buffer.subarray(pointer + 8, pointer + 8 + length));
        break;
      default:
        break;
    }
    result.chunks.push(chunk);
    pointer = pointer + 4 + 4 + length + 4;
  }
  const originFileData = zlib.unzipSync(Buffer.concat(fileChunkDatas));
  // 这儿原图片数据太长了 我就只打印了长度
  return {
    ...result,
    originFileData: originFileData.length,
  };
}

终究打印的成果，咱们需求注意红框的那几个部分。能够看到上图，位深和颜色类型决定了每个像素由4 byte组成，然后由于过滤办法的存在，会在每行的第一个字节进行标记。因而该图的原始数据所占巨细为：707 * 475 * 4 byte + 475 * 1 byte = 1343775 byte。正好是咱们打印的成果。

咱们也能够试试之前TinyPNG紧缩后的图，如下：

能够看到位深为8，索引颜色类型的图每像素占1 byte。核算得到：707 * 475 * 1 byte + 475 * 1 byte = 336300 byte。成果也正确。

总结

现在再看如何进行图片紧缩，你或许很容易得到下面几个定论：

1.减少不必要的辅佐块信息，由于辅佐块对PNG图片而言并不是有必要的。

2.减少IDAT的块数，由于每多一个IDAT的块，就剩余了12 byte。

3.下降每个像素所占的内存巨细，比方当时是4通道8位深的图片，能够核算整个图片色域，得到色阶表，设置索引颜色类型，下降通道然后下降每个像素的内存巨细。

4.等等….

至于JPEG，WEBP等等格局图片，有机会再看。溜了溜了~（仍是运用现成的库处理紧缩吧）。

好久没写文章，写完才发现语雀不能免费共享，发在这儿吧。