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

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

八叉树颜色量化

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

R01111011
G11101010
B01101111
index27747175

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

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

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

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

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)

颜色抖动有多种方式:

  1. 随机颜色抖动(Random Dither)
  2. 有序颜色抖动(Ordered Dither)
  3. 误差扩散(Error Diffusion)

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

*7/16
3/165/161/16
误差扩散分配比例

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

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

  1. 二次量化。将扩散之后的图像再次量化处理。二次量化之后不再需要颜色抖动。
  2. 取量化后颜色表中的近似色。近似色的选择需要计算色差,色差公式(3)如下:

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

Q&A

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

参考

  1. 八叉树颜色压缩图解以及c++实现
  2. 关于颜色抖动(dithering)
  3. 色差公式汇总