图像颜色提取

摘要：所以不妨试试查找二叉树这样的数据结构，二叉树的优势在于每次查找的时间会指数级下降，以此加快程序运行。综合起来看，在一定的样本量区间，还是使用原生的效率更高，这个区间在本文指的是种颜色，当然我还是相信当颜色更多的时候，二叉树还是有它的优势的。

本文github项目：colorful color
我的codepen链接：图像颜色提取
the demo
原创文章，转载请注明

最近想找个小项目练练手，以便熟悉React，于是想到了“图像颜色提取”这个方向，也有的说法是图像主题色提取，颜色量子化，或者是叫由图像生成调色板，原因无他，只是因为漂亮！

“分析”的目的有这么几个：

主要颜色： main color 就是出现频率最高的颜色，这样色颜色在设计中常常是用于背景色，提供沉浸式的体验：

平均颜色： average color 是所有颜色的平均值，和主要颜色一样可以用作背景色；

颜色量子化： 颜色量子化在这里相当于是在提取主题色，结果是图像中一系列主要颜色的集合，这些颜色可以通过统计分析得到，也可以通过聚类算法生成。同时，主要颜色，平均颜色和主题色这几个因子都可以作为图像的特征，特征可以用于图像进一步分析，比如图像识别与检索，压缩等；

颜色可视化： 图像本身就是颜色的容器，这个“容器”也是一种可视化的呈现，我想我们也可以从另一个角度观察颜色——去除图像内容，仅呈现不同颜色的值和他们的权重，比如下面这样星星点点像星空一样可视化方案：

中位切分算法首先把所有像素映射到RGB空间，在这个三维的空间里反复切分出子空间，最后将切分空间的像素求均值作为提取结果。分割区块时都选择所有区块中最大（最长的边长最大，或体积最大，或像素最多）的区块，切割点应位于边方向上，使得分割后两个区块的像素各一半的位置，以上是为中位切分法。流程如下（推荐阅读：《Color Quantization》）：

1.像素映射到RGB空间：

2.区块计算：

3.中位切分：

4.反复切分：

5.计算区块的平均颜色：

这里推荐一个采用中位切分法实现（JavaScript）的颜色量子化项目：Color Thief。

八叉树算法的核心理念是用八叉树来划分颜色空间，然后合并叶节点来逐步聚拢颜色（量子化），八叉树的解释可参考《游戏场景管理的八叉树算法是怎样的？》，关键就是下面这两幅图：

1.建树过程：

2.合并叶节点：

具体的解释可参考文章：《图片主题色提取算法小结》，作者还写了一个颜色量子化的node模块： A theme color extractor module for Node.js

K均值聚类的思想十分简单，可分这几步：

选取初始的K个质心；

按照距离质心的远近对所有样本进行分类；

重新计算质心，判断是否退出条件：

两次质心的距离足够小视为满足退出条件；

不退出则重新回到步骤2；

来看js的实现：

/*
colors: 所有样本
seeds: 初始质心
max_step: 最大迭代次数
*/
kMC(colors, seeds, max_step) {
    let iteration_count = 0;
    while (iteration_count++ < max_step) {
      // divide colors into different categories with duff"s device
      classifyColor(colors, seeds);

      // compute center of category
      let len = colors.length;
      let hsl_count = [];
      let category;
      while (len--) {
        category = colors[len].category;
        // ......
      }
      
      // quit or not
      let flag = hsl_count.every((ele, index) => {
        // ......
      });
      if (flag) {
        break;
      }
    }
    console.log("KMC iteration " + iteration_count);
  }

canvas读取本地图像，做适当缩放；

统计颜色信息：颜色需要做量子化处理（Color Quantization），RGB空间中一共有255的三次方约1600多万种颜色，除以8能降采样到32000多种。RGB值组合为键值，统计每种颜色出现的次数：

let r_key = Math.floor(r / 8) * 1000000;
let g_key = Math.floor(g / 8) * 1000;
let b_key = Math.floor(b / 8);
let key = r_one + g_one + b_one;
if(keys.indexOf(key)<0){
  // 未找到key，则新加入key
}else{
  // 找到则出现次数加1
}

过滤颜色：过滤孤立的颜色（出现次数太少）和过亮过黑的颜色；

K均值聚类：选取出现频率最高的K种颜色所谓初始值，由算法聚类出新的稳定的颜色中心；

计算主要颜色和均值颜色；

这张图的原始分辨率是 1080 x 1800 ，缩放到canvas中分辨率是 216 x 360 （缩放规则是固定最大高度为360，按原始宽高比例缩放）。选择颜色降采样的间隔为 5，一共是提取了 6251 种颜色，过滤掉出现次数小于 4 和过黑过亮的颜色后剩余 2555 种颜色。K均值聚类的K设为 6 ，最终迭代次数是 10 ，耗时 106ms。

codepen的原始例子如下：

census color

这方案执行下来会有一些问题：

K均值种子点的选取对结果的影响较大；

计算聚类中心的时候不光是RGB三个值，还加入了颜色出现次数这个值，所以K比较小时，新的聚类中心可能不会收敛到醒目的点缀颜色上，这和我们的视觉感受是不一致的，但是如果选择K为10，对于上面的图像是能够收敛到红色的。

这部分采用了brain，它应该是简单的BP神经网络。训练数据采用的是图虫网的热门图片。目前带评分的图像数据库比较少，而且评分往往是综合的，掺杂了其它（构图，主题，光影，人物等）因素，难以分离出只与色彩相关的评分，所以我是按照自己的喜好对训练数据进行了评分，所以结果会非常强烈的接近我个人的喜好。
另外神经网络的输入项也是比较关键的，因为它必须要正确反映颜色相关的图像信息，我提取的是：

let info = {
  colorCount: (Math.log10(colorInfo.length)),
  average:0,
  variance: 0,
  top50Count: 0,
  top50Average: 0,
  top50Variance: 0,
  top20Count: 0,
  top20Average: 0,
  top20Variance: 0,
  top10Count: 0,
  top10Average: 0,
  top10Variance: 0,
  top5Count: 0,
  top5Average: 0,
  top5Variance: 0
};

数据分为四类，评分从高到低分别是：100，85，75，65。

之前是采用的RGB空间，三个冷冰冰的数字并不能让我们很好的分辨不同色彩，于是这里我试着转换到HSL空间：色相(H)、饱和度(S)、明度(L)，这三个颜色通道相互之间的叠加能得到各式各样的颜色，这个颜色空间几乎包括了人类视力所能感知的所有颜色，是目前运用最广的颜色系统之一。
RGB和HSL的转换可参考《javascript HEX十六进制与RGB, HSL颜色的相互转换》。

转换到HSL空间对于我们提取颜色的目标有以下好处：

原来的RGB中三个值一样重要，对于HSL我们可以使用不同的参数分别去处理三个通道，比如对于色相可以稠密采样，对于明度和饱和度可以适当稀疏采样；

对于不同颜色的控制更加精细准确，原始的RGB空间中我们很难判断两个不同颜色之间他们的RGB值关系，但是对于HSL我们只要关注色相就可以了（其它两个通道也很有用，只是这里选择忽略它们）；

影响整个算法运行时间的关键步骤是颜色信息的统计，而统计环节中最耗时的是key的检测，存储key的容器长度会越来越长，采用indexOf的方式会越来越耗时，实验证明绝大部分的时间都是耗费在这一步上。所以不妨试试查找二叉树这样的数据结构，二叉树的优势在于每次查找的时间会指数级下降，以此加快程序运行。
但是，我用js实现这种数据结构的结果并不理想，运行时间基本与indexOf一致，甚至大部分时候还会略微多一点。我觉得原因在于：虽然每次查找重复key的时间减少了，但是每次新加入key的步骤变得复杂了，而且indexOf()是 native code ，运行效率应该比我们自己实现的js代码高。综合起来看，在一定的样本量区间，还是使用原生的indexOf效率更高，这个区间在本文指的是 1000~3000 种颜色，当然我还是相信当颜色更多的时候，二叉树还是有它的优势的。我实现的代码如下：

二叉树前序/中序/后序遍历

这是个非常实用的技巧（经过我多次验证），感觉已经离不开它了！

let len = colors.length;
let count = (len / 8) ^ 0;
let start = len % 8;
while (start--) {
  // do something
}
while (count--) {
  // do something  
}

测试结果：jsprof。

对图像进行模糊可以减少色彩的种类，从而加速提取算法，这应该是可行的，但是我还没有加入到项目中，我探索的比较快，效果比较好的模糊算法的实现如下：

canvas blur

最开始只是想熟悉react，结果到后面，项目的重心就完全偏向于算法和动画了。我觉得React对SVG还是比较友好的，各种动画属性都可以放到state中。个人感受SVG动画相对于CSS的优势在于：更加灵活，更加容易完成复杂动画效果，兼容性更好，底层优化更流畅。
canvas动画的优势是比较流畅，SVG动画在移动端还是有很多肉眼可见的掉帧卡顿的，而且SVG会让HTML变得很大很乱，可能让有洁癖的你不舒服。

SVG halo animation

不管什么动画最终都还是归结于：数学，比如：

这个动画的难点在于随机的布局算法，关键在于碰撞的检测与碰撞后的移动，本质依赖于几何和物理中的运动定律：

bubble chart

这个动画的难点在于找到一个神奇的数学公式，虽然我自己也不知道怎么回事，但是变换数学公式，有时候就能实现有规律的动画，而有规律再加上色彩，很大概率就是好的动画：

canvas wave