八叉树和颜色抖动——生成 gif 图片帧

Table of Contents

gif 图片每帧最多只有 256 色，当把真彩色图片转成 gif 图片的时候，需要压缩颜色数量。为了尽可能还原图片色彩，压缩后的颜色最好是根据原图颜色生成。这就用到了八叉树颜色量化算法^（1）。

八叉树颜色量化

比如，某个像素值是 (123, 234, 111)，其二进制表示如下：

R	0	1	1	1	1	0	1	1
G	1	1	1	0	1	0	1	0
B	0	1	1	0	1	1	1	1
index	2	7	7	4	7	1	7	5

从左往右，可以用 8 个数字表示（index 行），分别表示所在八叉树对应层级中的位置。比如，第一个数 2 表示第一层下标为 2 的位置，第二个数 7 表示上一层位置 2 的子节点中下标为 7 的位置……

依此形成一个树，最后一级为叶子结点。当叶子结点超过最大颜色数（这里是 256，也可以设成其他数值，比如实践中我设成了 254，留两个给背景色和透明色），就需要合并叶子节点。合并原则是：

从倒数第二层开始。因为越下面的层级代表的颜色范围越小，合并后失真越小。
子节点数需要大于等于两个。深度相同，选择子节点数少的那个。
合并后，此节点的颜色值为累积颜色值对所代表像素数量的平均值——此值可以在遍历完所有像素后，取颜色的时候计算。同时，将该节点标记为叶子结点，以后此路径添加颜色时截止到此节点。

所有像素遍历结束后，八叉树就构建完成了，然后再次遍历所有像素，从八叉树上取色。

import { getBits } from './helpers'

/**
 * cotree color quantization
 * https://zhuanlan.zhihu.com/p/220177037
 */
export default class Quantizer {
  constructor () {
    this.tree = new TreeNode()
    this.tree.level = -1
    this.levelNodes = new Array(8).fill(0).map(() => {
      return []
    })
  }

  // max color nums-- a slot for transparant color, a slot for background color
  maxColor = 254

  // color count
  colorCount = 0

  // tree
  tree: TreeNode

  // level nodes
  levelNodes: Array<Array<TreeNode | null>>

  // add color
  addColor (r: number, g: number, b: number) {
    let parentNode = this.tree

    for (let i = 7; i >= 0; i--) {
      const idx = (getBits(r, i, 1) << 2) + (getBits(g, i, 1) << 1) + getBits(b, i, 1)

      let node = parentNode.nodes[idx]

      // create node
      if (!node) {
        parentNode.nodes[idx] = new TreeNode()
        node = parentNode.nodes[idx]
        node.level = 7 - i
        node.parent = parentNode
        parentNode.nodesCount++
        node.idxInLevelNodes = this.levelNodes[node.level].length
        this.levelNodes[node.level].push(node)

        // last level, color count + 1
        if (node.level === 7) {
          this.colorCount++
        }
      }

      node.count++
      node.redSum += r
      node.greenSum += g
      node.blueSum += b

      if (node.isLeaf) {
        break
      }

      if (node.level === 7) {
        node.isLeaf = true
      }

      parentNode = node
    }

    // check max color count
    if (this.colorCount > this.maxColor) {
      this.reduceColor()
    }
  }

  // get color--get transformed color
  getColor (r: number, g: number, b: number): Array<number> {
    let parentNode = this.tree
    const color = [0, 0, 0, 0]
    for (let i = 7; i >= 0; i--) {
      const idx = (getBits(r, i, 1) << 2) + (getBits(g, i, 1) << 1) + getBits(b, i, 1)

      const node = parentNode.nodes[idx]

      if (!node) {
        break
      }

      if (node.isLeaf) {
        color[0] = (node.redSum / node.count) >> 0
        color[1] = (node.greenSum / node.count) >> 0
        color[2] = (node.blueSum / node.count) >> 0
        color[3] = 1
        break
      }

      parentNode = node
    }
    return color
  }

  // reduce color
  private reduceColor () {
    let targetNode = null
    let minCount = Number.MAX_SAFE_INTEGER

    // from bottom to top, there are all leaf nodes in level 7, skip
    for (let i = 6; i >= 0; i--) {
      const nodes = this.levelNodes[i]
      for (let idx = 0, len = nodes.length; idx < len; idx++) {
        if (nodes[idx]) {
          const node = nodes[idx] as TreeNode
          if (!node.isLeaf && node.nodesCount > 1 && node.count < minCount) {
            targetNode = node
            minCount = node.count
          }
        }
      }
      if (targetNode) {
        break
      }
    }

    // delete sub nodes
    if (targetNode) {
      this.deleteSubNodes(targetNode)
    }
  }

  // delete sub nodes
  private deleteSubNodes (targetNode: TreeNode) {
    for (let i = 0, len = targetNode.nodes.length; i < len; i++) {
      const node = targetNode.nodes[i]
      if (node) {
        if (!node.isLeaf) {
          this.deleteSubNodes(node)
        }
        this.levelNodes[node.level][node.idxInLevelNodes] = null
      }
    }

    this.colorCount -= targetNode.nodesCount - 1

    targetNode.nodes = []
    targetNode.nodesCount = 0

    targetNode.isLeaf = true
  }
}

export class TreeNode {
  constructor () {
    this.isLeaf = false
    this.level = 0
    this.count = 0
    this.redSum = 0
    this.greenSum = 0
    this.blueSum = 0
    this.parent = null
    this.nodes = []
    this.nodesCount = 0
    this.idxInLevelNodes = 0
  }
  // is leaf node ?
  isLeaf: boolean
  // level
  level: number
  // color count
  count: number
  // red count
  redSum: number
  // green count
  greenSum: number
  // blue count
  blueSum: number
  // parent node
  parent: TreeNode | null
  // nodes
  nodes: Array<TreeNode>
  // nodes count
  nodesCount: number
  // idx in level nodes
  idxInLevelNodes: number
}

颜色抖动

通过量化的颜色生成 gif 图像的时候会出现颜色分块明显的情况。为了让颜色过渡合理一些，避免过多的细节丢失，就需要颜色抖动（dithering）^（2）。

颜色抖动有多种方式：

随机颜色抖动（Random Dither）
有序颜色抖动（Ordered Dither）
误差扩散（Error Diffusion）

我采用的是误差扩散方法。误差扩散原理就是将量化后的颜色与原来的颜色比对，计算（RGB 各个通道）差值，然后将差值按照一定的比例加到周围像素上。

	*	7/16
3/16	5/16	1/16

误差扩散分配比例

比例可以自行调整，表格中只是一种分配方式。

经过抖动，颜色的数量很可能超过预设的限制，所以扩散之后的颜色并不是最终的结果。为此，我尝试了两种方式：

二次量化。将扩散之后的图像再次量化处理。二次量化之后不再需要颜色抖动。
取量化后颜色表中的近似色。近似色的选择需要计算色差，色差公式^（3）如下：

这两种方式处理的结果……其实差不多。事实上，我选择的图片是否颜色抖动基本没差别。我不确定是处理有问题还是图片选择有问题。

Q&A

Q：为什么八位二进制从左往右代表 1~8 层，而不是反过来？
A：因为左边的数字代表的范围更大。比如 123 这个数字，1 发生变化造成的影响比 2 发生变化造成的影响更大，影响更大的位，我们要放到树的上层。

八叉树颜色量化

颜色抖动

Q&A

参考