colorthief.js(图像中自动提取出主色调、调色板或者平均颜色)源码解析MMCQ算法
一、colorthief.js介绍
Color Thief 是一个开源的 JavaScript 库，它能够从图像中自动提取出主色调、调色板或者平均颜色
。通过分析图像的像素数据，Color Thief 计算出最具代表性的颜色，并将这些颜色值返回。这个库可以在浏览器和 Node.js 环境中运行，使得动态地获取图片的主要颜色成为可能
核心功能
- getColor：获取图像的主导颜色，返回一个包含三个整数的数组，分别代表红、绿、蓝值
- getPalette：获取图像的颜色调色板，通过聚类相似颜色来构建调色板，返回一个包含多个颜色的数组，每个颜色本身是一个包含三个整数的数组
如何使用
const ColorThief = require('colorthief');
const img = resolve(process.cwd(), 'rainbow.png');
ColorThief.getColor(img)
.then(color => { console.log(color) })
.catch(err => { console.log(err) })
ColorThief.getPalette(img, 5)
.then(palette => { console.log(palette) })
.catch(err => { console.log(err) })
二、什么是真彩色图像，什么是伪彩色图像
真彩色和伪彩色图像是数字图像处理中的两个概念，具体如下
真彩色图像
真彩色图像是指图像中每个像素的颜色都是由三个颜色通道（红、绿、蓝，即RGB）的值直接决定的。在真彩色图像中，每个通道通常用8位（一个字节）来表示，因此每个像素可以用24位位来表示，能够显示的颜色数量达到2^24(1677)万种。这意味着真彩色图像能够非常精确地再现现实世界中的颜色，因为它几乎覆盖了人眼能够感知的所有颜色范围。
总结：
真彩色图像具有如下特点
- 每个像素的颜色由RGB三个通道的值直接决定
- 能够显示的颜色数量非常多，通常达到1677万色
- 图像文件通常较大，因为每个像素需要更多的数据来存储
伪彩色图像
伪彩色图像是指图像中的颜色不是由RGB三个通道的值直接决定的，而是由单一的强度值（灰度）通过颜色映射转换而来。在伪彩色图像中，每个像素通常只有一个强度值，这个值用来从颜色映射表中查找对应的颜色。颜色映射表定义了强度值和颜色之间的对应关系，因此即使是灰度图像，也可以通过颜色映射表显示位彩色。
总结：
伪彩色图像具有如下特点
- 每个像素的颜色由单一的强度通过颜色映射转换而来
- 能够显示的颜色数量受限于颜色映射表的大小
- 图像文件通常较小，因为每个像素只需要较小的数据来存储强度值。
真彩色和伪彩色图像的应用
真彩色图像
- 摄影和图像编辑：数码相机拍摄的照片通常是真彩色图像，能够精确地记录和再现现实世界中的颜色。
- 视频制作和播放：电影、电视节目和在线视频通常使用真彩色图像，以提供丰富的视觉体验。
- 图形设计和广告：设计师在创建广告、海报和其他视觉作品时，使用真彩色图像来确保颜色的准确性和吸引力。
- 艺术和插画：数字艺术家和插画师使用真彩色图像来创作具有丰富色彩和细节的作品。
- 医学成像：某些医学成像技术（如MRI和CT扫描）使用真彩色图像来提供详细的解剖信息。
- 卫星和航拍图像：卫星图像和航拍照片通常以真彩色形式呈现，以便于观察和分析地理特征。
伪彩色图像
- 遥感和地理信息系统（GIS）：卫星图像和航拍照片在GIS中常用伪彩色来增强特定特征的可视化，例如植被、水体和城市区域。
- 医学成像：伪彩色用于增强MRI、CT扫描和其他医学成像技术中的特定结构，使医生能够更容易地区分不同的组织类型。
- 科学可视化：在科学研究中，伪彩色用于表示数据的强度或值，如温度、压力或浓度，这在热成像和流体动力学模拟中尤为常见。
- 计算机视觉和机器学习：在训练机器学习模型时，伪彩色可以用来增强图像特征，帮助算法更好地识别和分类对象。
- 数据可视化：在数据可视化中，伪彩色可以用来表示数值数据的分布，如在热力图中使用颜色渐变来表示数据的密度或强度。
- 低带宽通信：在带宽有限的情况下，如早期的互联网或某些无线通信，伪彩色图像由于数据量较小，可以更快地传输。
三、中值切割量化（MCQ）
中值切割量化（MCQ）是一种颜色量化算法，用于减少图像中的颜色数量，同时尽量保持图像的视觉质量。这种算法特别适用于需要将真彩色图像转换为伪彩色图像的场景，例如在显示设备上或者在颜色深度有限的图形格式中。以下是MCQ算法的详细细节和具体思想：
- 颜色空间和直方图
- 算法首先将图像中的每个像素点转为RGB颜色空间中的点。然后，算法构建一个颜色直方图，统计每个颜色的出现频率。
- 初始化VBox
- 定义一个初始的VBox（体积盒子），它包含了图像中的所有颜色点，这个盒子在缩小的颜色空间中有一个确定的体积
- 选择VBox进行分割
- 选择包含最多颜色的VBox进行分割。这个选择基于颜色的频率，以确保每次分割都能最大化减少颜色数量。
- 确定分割维度
- 确定VBox的最长维度（红、绿或蓝色通道），这将作为分割的依据。
- 寻找中值
- 在选定的维度上，找到颜色值的中位数，这个中值将VBox分割成两个新的VBox。
- 分割VBox
- 根据中值将VBox分割成两个新的VBox，每个新VBox包含原VBox中的一部分颜色。
- 重复分割
- 重复步骤3-6，直到达到所需的颜色数量或所有VBox都不能再被分割。
- 生成调色板
- 每个最终的VBox代表调色板中的一个颜色，通常是该VBox内所有颜色的中值或平均值。
- 映射原始颜色
- 对于图像中的每个像素，找到调色板中最接近的颜色，并用该颜色替换原始颜色。
- 输出结果
- 输出最终的调色板和映射后的图像。
中位数反映的信息
12. 中位数反映了数据集的中心趋势，即一半的数据项小于或等于中位数，另一半的数据项大于或等于中位数。
13. 中位数对异常值（Outliers）和数据的偏斜不敏感，因此在数据分布不均匀或包含极端值时，中位数通常比平均数更能代表数据的中心位置。
14. 中位数可以用来比较不同数据集的中心趋势，即使它们的分布形状不同。
四、改良后的中值切割量化（MMCQ）
MMCQ是一种颜色量化算法，它在传统的中值切割量化（MCQ）的基础上进行了改进，以更有效地减少图像中的颜色数量，同时保持图像的视觉质量。
MMCQ相比于MCQ算法基本思路一致，但是在细微处做了优化。优化点如下
- 两阶段分割策略
- MCQ: 在传统的MCQ中，颜色空间的分割是单一阶段的，直接基于颜色的中值进行分割，直到达到目标颜色数量。
- MMCQ：引入了两阶段的分割策略。第一阶段基于像素数量进行分割，直到达到目标颜色数量的75%左右。第二阶段则考虑像素数量和颜色空间体积的乘积，以更细致地控制颜色的分布和数量，直到达到最终的目标颜色数量。
- 优先队列的使用
- MCQ：在传统的MCQ中，VBox的分割顺序可能是基于简单的迭代，没有明确的优先级
- MMCQ：使用优先队列（如最大堆）来管理VBox，根据VBox的像素数量和体积的乘积来动态选择下一个要分割的VBox。这种方法可以更有效地平衡颜色的分布和数量。
- 颜色空间的量化
- MCQ：在传统的MCQ中，颜色空间的量化可能不是必要的步骤。
- MMCQ：在构建颜色直方图之前，将颜色空间量化到较少的位数（例如，从8位降到5位或6位），以减少计算量和提高算法的效率。
- 颜色替换策略
- MCQ：在传统的MCQ中，颜色替换可能是基于简单的最近邻搜索。
- MMCQ：在颜色替换阶段，MMCQ使用更精确的最近颜色匹配策略，如基于欧几里得距离的最近颜色搜索，以确保每个像素都能被映射到调色板中最接近的颜色。
- 调色板的优化
- MCQ：在传统的MCQ中，调色板的生成是基于简单的中值切割结果。
- MMCQ：MMCQ在生成调色板时，会考虑颜色的分布和数量，以及颜色空间的体积，以生成更优的调色板。
- 算法的鲁棒性
- MCQ：在某些情况下，传统的MCQ可能对颜色分布不均匀的图像处理效果不佳。
- MMCQ：通过两阶段分割和优先队列的使用，MMCQ提高了算法的鲁棒性，使其能够更好地处理各种颜色分布的图像。
MMCQ的算法步骤如下
- 颜色空间转换
- 与MCQ类似，将图像的每个像素从RGB颜色空间映射到一个较低分辨率的颜色空间。
- 构建颜色直方图
- 统计图像中每种量化后颜色的出现频率，构建颜色直方图。
- 创建初始VBox
- 定义一个初始的VBox，包含所有颜色点。
- 使用优先队列
- 使用优先队列（如最大堆）来管理VBox，根据VBox的像素数量和体积的乘积来动态选择下一个要分割的VBox。
- 分割VBox
- 在每个阶段，选择包含最多颜色的VBox进行分割，确定最长维度，并找到该维度上的中值进行分割。
- 两阶段分割策略
- 第一阶段：基于像素数量进行分割，直到达到目标颜色数量的75%左右。
- 第二阶段：基于像素数量和颜色空间体积的乘积进行分割，直到达到最终的目标颜色数量。
- 生成调色板
- 每个最终的VBox代表调色板中的一个颜色，通常是该VBox内所有颜色的平均值。
- 最近颜色匹配
- 对于图像中的每个像素，使用基于欧几里得距离的最近颜色搜索，找到调色板中最接近的颜色进行替换。
- 输出结果
- 输出最终的调色板和映射后的图像。
五、源码分析
getPalette函数
getPalette函数是从图像中提取一个颜色调色板
/**
* 获取图像的颜色调色板。
* @param {HTMLImageElement|Canvas} img - 要提取颜色的图像或画布元素。
* @param {number} [colorCount=10] - 要提取的颜色数量，默认为10。
* @param {number} [quality=10] - 控制颜色量化的质量，影响颜色空间的量化位数，默认为10。
* @returns {Promise<Array>} - 一个承诺（Promise），解析为颜色调色板数组。
*/
function getPalette(img, colorCount = 10, quality = 10) {
// 验证传入的选项，并确保它们是有效的。
const options = validateOptions({ colorCount, quality });
// 加载图像并返回图像数据。
return loadImg(img)
.then(imgData => {
// 计算图像中的像素总数。
const pixelCount = imgData.shape[0] * imgData.shape[1];
// 根据图像数据和质量选项创建像素数组。
const pixelArray = createPixelArray(imgData.data, pixelCount, options.quality);
// 使用像素数组和颜色数量选项进行颜色量化，获取颜色映射。
const cmap = quantize(pixelArray, options.colorCount); // quantize函数内是MMCQ算法的具体实现，也是重点
// 从颜色映射中提取调色板。
const palette = cmap ? cmap.palette() : null;
// 返回调色板数组。
return palette;
});
}
validateOptions 函数校验输入参数是否符合规定。代码如下
function validateOptions(options) {
let { colorCount, quality } = options;
// 验证 colorCount 参数
if (typeof colorCount === 'undefined' || !Number.isInteger(colorCount)) {
colorCount = 10; // 如果 colorCount 未定义或不是整数，则设置默认值为 10
} else if (colorCount === 1) {
// 如果 colorCount 为 1，则抛出错误，因为至少需要两种颜色
throw new Error('`colorCount` should be between 2 and 20. To get one color, call `getColor()` instead of `getPalette()`');
} else {
// 确保 colorCount 在 2 到 20 的范围内
colorCount = Math.max(colorCount, 2);
colorCount = Math.min(colorCount, 20);
}
// 验证 quality 参数
if (typeof quality === 'undefined' || !Number.isInteger(quality) || quality < 1) quality = 10;
// 返回包含验证后的颜色数量和质量的对象
return { colorCount, quality };
}
loadImg 函数是一个用于加载图像并提取像素数据的实用工具
const loadImg = (img) => {
const type = Buffer.isBuffer(img) ? FileType.fromBuffer(img).mime : null; // 1. 确定图像类型
return new Promise((resolve, reject) => { // 2. 返回一个Promise对象
sharp(img) // 3. 使用sharp库处理图像
.toBuffer() // 4. 将图像转换为Buffer
.then(buffer => sharp(buffer).metadata() // 5. 获取图像的元数据
.then(metadata => ({ buffer, format: metadata.format })))
.then(({ buffer, format }) => getPixels(buffer, format)) // 6. 提取像素数据（使用ndarray-pixels库）
.then(resolve) // 7. 成功时解析Promise
.catch(reject); // 8. 失败时拒绝Promise
});
}
createPixelArray 函数的目的是从一个包含像素数据的数组中创建一个新的像素数组
/**
* 从给定的像素数据中创建一个新的像素数组，只包含不完全透明且不是纯白色的像素。
* @param {Uint8Array} pixels - 包含原始像素数据的数组。
* @param {number} pixelCount - 原始像素数据中的像素总数。
* @param {number} quality - 用于确定选取像素间隔的质量参数。
* @returns {Array} 一个新的数组，包含符合条件的像素数据。
*/
function createPixelArray(pixels, pixelCount, quality) {
const pixelArray = []; // 初始化一个空数组来存储符合条件的像素数据
// 遍历原始像素数据，步长为 quality 参数
for (let i = 0, offset, r, g, b, a; i < pixelCount; i += quality) {
offset = i * 4; // 计算当前像素的偏移量，假设每个像素由4个分量（RGBA）组成
// 从原始像素数据中提取当前像素的 RGBA 分量
r = pixels[offset];
g = pixels[offset + 1];
b = pixels[offset + 2];
a = pixels[offset + 3];
// 如果像素的 alpha 分量未定义或大于等于125（即不完全透明）
// 且该像素不是纯白色（即 RGB 分量都大于250）
if ((typeof a === 'undefined' || a >= 125) && !(r > 250 && g > 250 && b > 250))
pixelArray.push([r, g, b]); // 将符合条件的像素的 RGB 分量添加到新数组中
}
return pixelArray; // 返回包含符合条件的像素数据的新数组
}
quantize函数
它是实现MMCQ算法的函数。
首先对输入数据进行判断，对于不符合条件的数据直接报错或者后续逻辑不执行
function quantize(pixels, maxcolors) {
// Add input validation
// 确保maxcolors是整数并在[1,256]
if (!Number.isInteger(maxcolors) || maxcolors < 1 || maxcolors > 256) {
throw new Error("Invalid maximum color count. It must be an integer between 1 and 256.");
}
// short-circuit
if (!pixels.length || maxcolors < 2 || maxcolors > 256) {// 如果 pixels 数组为空，或者 maxcolors 不在2到256的范围内，函数返回 false。
// console.log('wrong number of maxcolors');
return false;
}
// short-circuit
if (!pixels.length || maxcolors < 2 || maxcolors > 256) {
// console.log('wrong number of maxcolors');
return false;
}
...
从 pixels 的数组中提取出唯一颜色
var uniqueColors = []; // 创建一个空数组来存储唯一的颜色
var seenColors = new Set(); // 创建一个Set集合来存储已经见过的颜色的键值，利用Set的独一无二特性来快速检查颜色是否已经存在
for (var i = 0; i < pixels.length; i++) {
var color = pixels[i]; // 获取当前索引下的颜色数组
var colorKey = color.join(',');// 将颜色数组转换为一个字符串，以逗号分隔每个颜色值，作为这个颜色的唯一标识
if (!seenColors.has(colorKey)) {
seenColors.add(colorKey);
uniqueColors.push(color);
}
}
上面代码实现了pixels数组去重逻辑，最终得到一个包含所有唯一颜色的 uniqueColors 数组。这种方法在处理大量颜色数据时效率较高，因为它避免了对数组进行多次线性搜索，而是利用 Set 的常数时间复杂度的查找特性。
如果uniqueColors数组中唯一颜色的数量小于或等于maxColors变量的值，那么代码将直接返回这些颜色
// If the number of unique colors is already less than or equal to maxColors,
// return these colors directly.
if (uniqueColors.length <= maxcolors) {
return new SimpleColorMap(uniqueColors);
}
/**
* SimplePalette class
*/
var SimpleColorMap = /*#__PURE__*/function () {
/**
* @param {Array} pixels - An array of [r, g, b] pixel values
*/
function SimpleColorMap(colors) {
this.colors = colors;
}
/**
* Returns the stored palette (array of pixels)
* @returns {Array} The array of [r, g, b] pixel values
*/
var _proto = SimpleColorMap.prototype; // 将 SimpleColorMap 的原型赋值给变量 _proto，以便在原型上添加方法。
_proto.palette = function palette() {
return this.colors;
};
_proto.map = function map(color) {
return color;
};
return SimpleColorMap;
}();
颜色空间转换和构建颜色直方图(MMCQ)
var histo = getHisto(pixels);
histo.forEach(function () {
});
// 将一个像素的颜色值（r, g, b）转换为一个单一的颜色索引值
function getColorIndex(r, g, b) {
return (r << 2 * sigbits) + (g << sigbits) + b;
}
// histo (1-d array, giving the number of pixels in
// each quantized region of color space), or null on error
function getHisto(pixels) {
var histosize = 1 << 3 * sigbits, // 计算直方图数组的大小。这里使用了位移运算符 <<，它将 1 向左移动 3 * sigbits 位，相当于计算 2^(3 * sigbits)，这里sigbits = 5，所以histosize 将是 2^15 = 32768
histo = new Array(histosize),// 创建一个长度为 histosize 的数组，用于存储直方图数据
index,
rval,
gval,
bval; // 声明变量 index（用于存储颜色索引），以及 rval、gval、bval（分别用于存储像素的红、绿、蓝值）
pixels.forEach(function (pixel) {
rval = pixel[0] >> rshift; // 计算红色分量的值，通过将像素的红色值向右移动 rshift 位。rshift 是一个外部变量，代表向右移动的位数， rshift这里为 8 - sigbits
gval = pixel[1] >> rshift;
bval = pixel[2] >> rshift;
index = getColorIndex(rval, gval, bval);
histo[index] = (histo[index] || 0) + 1; // 在直方图数组中对应索引的位置增加计数
});
return histo;
}
注：pixel[0] >> rshift 这种操作的意图是减少颜色值的位数，从而减少颜色空间的分辨率。这是颜色量化过程中的一个关键步骤，目的是将连续的颜色空间离散化，以便在有限的颜色数量下近似原始图像的颜色。通过减少每个颜色通道的位数，我们可以将颜色空间划分为更少的区域，每个区域代表一组相似的颜色，从而实现颜色的压缩和简化。
创建初始VBox和使用优先队列(MMCQ)
// 3d color space box
function VBox(r1, r2, g1, g2, b1, b2, histo) { // 创建一个 VBox 实例，代表一个三维颜色空间盒子
var vbox = this;
vbox.r1 = r1;
vbox.r2 = r2;
vbox.g1 = g1;
vbox.g2 = g2;
vbox.b1 = b1;
vbox.b2 = b2; // r1, r2, g1, g2, b1, b2 是盒子的边界值
vbox.histo = histo; // histo 是直方图数据，用于计算盒子中的颜色数量
}
VBox.prototype = {
// 计算盒子的体积
volume: function volume(force) {
var vbox = this;
if (!vbox._volume || force) { // 没有计算过体积或者需要强制计算
vbox._volume = (vbox.r2 - vbox.r1 + 1) * (vbox.g2 - vbox.g1 + 1) * (vbox.b2 - vbox.b1 + 1); // 体积公式
}
return vbox._volume;
},
// 计算盒子中的颜色数量
count: function count(force) {
var vbox = this,
histo = vbox.histo;
if (!vbox._count_set || force) { // 如果颜色数量未计算或强制重新计算
var npix = 0,// 计数器
i,
j,
k,
index;
for (i = vbox.r1; i <= vbox.r2; i++) { // 遍历每个颜色通道
for (j = vbox.g1; j <= vbox.g2; j++) {
for (k = vbox.b1; k <= vbox.b2; k++) {
index = getColorIndex(i, j, k); // 获取颜色索引
npix += histo[index] || 0;// 计数
}
}
}
vbox._count = npix;
vbox._count_set = true; // 标记颜色数量已计算
}
return vbox._count;
},
// 创建盒子的副本
copy: function copy() {
var vbox = this;
return new VBox(vbox.r1, vbox.r2, vbox.g1, vbox.g2, vbox.b1, vbox.b2, vbox.histo); // 返回一个新的VBox实例
},
// 计算盒子中颜色的平均值
avg: function avg(force) {
var vbox = this,
histo = vbox.histo;
if (!vbox._avg || force) { // 如果平均值未计算或强制重新计算
var ntot = 0, // 存储盒子内所有颜色的总数量
mult = 1 << 8 - sigbits, // mult 的目的是在计算加权总和时，将颜色值缩放到原始颜色空间的范围内
rsum = 0,
gsum = 0,
bsum = 0, // 颜色分量的总和
hval, // 存储直方图中每个颜色的计数
i,
j,
k,
histoindex;
// 特殊情况：如果盒子代表单一颜色（即 r1 等于 r2，g1 等于 g2，b1 等于 b2），则平均值就是该颜色本身，通过左移 rshift 位来增加颜色值的位数。（为什么要左移？是因为在创建VBox时，传入的r，b，g都是右移rshift过的结果，所以需要复原）
if (vbox.r1 === vbox.r2 && vbox.g1 === vbox.g2 && vbox.b1 === vbox.b2) {
vbox._avg = [vbox.r1 << rshift, vbox.g1 << rshift, vbox.b1 << rshift];// 这里的vbox.r1 << rshift和上面mult = 1 << 8 - sigbits 原理一致
} else {// 一般情况处理
for (i = vbox.r1; i <= vbox.r2; i++) {
for (j = vbox.g1; j <= vbox.g2; j++) {
for (k = vbox.b1; k <= vbox.b2; k++) {
histoindex = getColorIndex(i, j, k);// 根据当前颜色值 (i, j, k) 计算出的直方图索引
hval = histo[histoindex] || 0; // hval 是直方图中该颜色的计数
ntot += hval; // 累加盒子内所有颜色的总数量
rsum += hval * (i + 0.5) * mult; // 累加红色分量的加权总和。
// 这里多加0.5为了更准确地估计颜色通道值的中心位置。
// 这有助于在计算平均值时考虑到颜色通道范围内的每个值。
// 比如：如果一个颜色通道的范围是从 10 到 20，中点是 15，这比简单地取最小值或最大值更能代表该范围内的颜色。
gsum += hval * (j + 0.5) * mult;
bsum += hval * (k + 0.5) * mult;
}
}
}
if (ntot) {
vbox._avg = [~~(rsum / ntot), ~~(gsum / ntot), ~~(bsum / ntot)]; // 计算平均值
} else { // 当盒子为空（即没有颜色）
vbox._avg = [~~(mult * (vbox.r1 + vbox.r2 + 1) / 2), ~~(mult * (vbox.g1 + vbox.g2 + 1) / 2), ~~(mult * (vbox.b1 + vbox.b2 + 1) / 2)];
}
}
}
// ~~ 的功能使其成为 Math.floor 的更好替代方案，虽然它的可读性不太好，但它速度更快且占用的字符更少。
return vbox._avg;
},
// 检查一个像素是否在盒子内
contains: function contains(pixel) {
var vbox = this,
rval = pixel[0] >> rshift;
gval = pixel[1] >> rshift;
bval = pixel[2] >> rshift;
return rval >= vbox.r1 && rval <= vbox.r2 && gval >= vbox.g1 && gval <= vbox.g2 && bval >= vbox.b1 && bval <= vbox.b2; // // 检查像素是否在盒子的边界内
}
};
function vboxFromPixels(pixels, histo) {
// rmin, rmax, gmin, gmax, bmin, bmax 是用来存储最小和最大值的变量
var rmin = 1000000,
rmax = 0,
gmin = 1000000,
gmax = 0,
bmin = 1000000,
bmax = 0,
rval,
gval,
bval;
// find min/max
pixels.forEach(function (pixel) { // 遍历pixels数值，分别找出r、g、b中的最大值和最小值
rval = pixel[0] >> rshift; // 这里的rshift和上面getHisto函数中使用的值一致(8 - sigbits)
gval = pixel[1] >> rshift;
bval = pixel[2] >> rshift;
if (rval < rmin) rmin = rval;else if (rval > rmax) rmax = rval;
if (gval < gmin) gmin = gval;else if (gval > gmax) gmax = gval;
if (bval < bmin) bmin = bval;else if (bval > bmax) bmax = bval;
});
return new VBox(rmin, rmax, gmin, gmax, bmin, bmax, histo); // 返回 VBox 实例，包含所有像素颜色的边界和直方图数据
}
// PQueue 类提供了一个简单的优先队列实现，它允许元素的添加、查看、移除以及获取队列的大小
function PQueue(comparator) {
var contents = [], // 用于存储优先队列中的元素的数组
sorted = false; // 标记数组是否已排序
// 排序函数，用于将数组按照比较函数的规则排序
function sort() {
contents.sort(comparator);
sorted = true;
}
// 返回优先队列的操作方法集合
return {
push: function push(o) {
contents.push(o); // 将元素添加到数组的末尾
sorted = false; // 由于添加了新元素，数组可能需要重新排序
},
peek: function peek(index) {
if (!sorted) sort();// 如果数组未排序，则先进行排序
if (index === undefined) index = contents.length - 1; // 如果未指定索引，则默认查看最后一个元素
return contents[index];
},
// 移除并返回队列中的最后一个元素。
pop: function pop() {
if (!sorted) sort(); // 如果数组未排序，则先进行排序
return contents.pop(); // 移除并返回数组的最后一个元素
},
// 获取队列中的元素数量。
size: function size() {
return contents.length;
},
// 对队列中的每个元素执行一个函数。
map: function map(f) {
return contents.map(f); // 对数组中的每个元素执行函数，并返回结果数组
},
// 用于调试的函数，返回队列的当前状态
debug: function debug() {
if (!sorted) sort();
return contents;
}
};
}
var pv = {
// naturalOrder 函数用于比较两个数字，并返回它们在自然排序顺序下的关系。
naturalOrder: function naturalOrder(a, b) {
return a < b ? -1 : a > b ? 1 : 0; // 如果a小于b，返回-1；如果a大于b，返回1；如果a等于b，返回0
},
// sum 函数用于计算一个数字数组的总和。
sum: function sum(array) {
return array.reduce(function (p, d) {// 使用数组的reduce方法来累加值
return p + d;
}, 0);
},
// max 函数用于找出一个数字数组中的最大值
max: function max(array) {
return Math.max.apply(null, array);
}
};
// get the beginning vbox from the colors
var vbox = vboxFromPixels(pixels, histo), // 创建一个包含所有像素颜色的初始 VBox
pq = new PQueue(function (a, b) { // 初始化优先队列，并指定排序算法
return pv.naturalOrder(a.count(), b.count());
});
pq.push(vbox); // 将初始 VBox 添加到优先队列中
分割VBox和两阶段分割策略(MMCQ)
// 对给定的 VBox 应用中值切割算法进行分割
function medianCutApply(histo, vbox) {
// 如果 VBox 为空，则不进行分割
if (!vbox.count()) return;
var rw = vbox.r2 - vbox.r1 + 1, // R 维度的大小
gw = vbox.g2 - vbox.g1 + 1, // G 维度的大小
bw = vbox.b2 - vbox.b1 + 1, // B 维度的大小
maxw = pv.max([rw, gw, bw]); // 找到最大的维度
// only one pixel, no split
// 如果 VBox 只包含一个像素，则不进行分割
if (vbox.count() == 1) {
return [vbox.copy()];
}
/* 寻找选定轴上的累积和数组。 */
var total = 0, // 总像素数
partialsum = [], // 累积和数组
lookaheadsum = [],
i,
j,
k,
sum,
index;
// 根据最大维度计算累积和
if (maxw == rw) {
for (i = vbox.r1; i <= vbox.r2; i++) {
sum = 0;
for (j = vbox.g1; j <= vbox.g2; j++) {
for (k = vbox.b1; k <= vbox.b2; k++) {
index = getColorIndex(i, j, k);
sum += histo[index] || 0;
}
}
total += sum;
partialsum[i] = total;
}
} else if (maxw == gw) {
for (i = vbox.g1; i <= vbox.g2; i++) {
sum = 0;
for (j = vbox.r1; j <= vbox.r2; j++) {
for (k = vbox.b1; k <= vbox.b2; k++) {
index = getColorIndex(j, i, k);
sum += histo[index] || 0;
}
}
total += sum;
partialsum[i] = total;
}
} else {
/* maxw == bw */
for (i = vbox.b1; i <= vbox.b2; i++) {
sum = 0;
for (j = vbox.r1; j <= vbox.r2; j++) {
for (k = vbox.g1; k <= vbox.g2; k++) {
index = getColorIndex(j, k, i);
sum += histo[index] || 0;
}
}
total += sum;
partialsum[i] = total;
}
}
// 计算lookaheadsum（具体解释看下图）
partialsum.forEach(function (d, i) {
lookaheadsum[i] = total - d;
});
// 执行分割的函数
function doCut(color) {
var dim1 = color + '1', // 维度的起始属性
dim2 = color + '2', // 维度的结束属性
left, // 用于计算切割点的辅助变量
right, // 用于计算切割点的辅助变量
vbox1,// 分割后的新 VBox
vbox2,// 分割后的新 VBox
d2, // 切割点
count2 = 0;// 用于避免 0 计数盒子的辅助变量
// 遍历选定维度上的所有可能切割点
for (i = vbox[dim1]; i <= vbox[dim2]; i++) {
if (partialsum[i] > total / 2) {// 找到中值切割点
vbox1 = vbox.copy(); // 创建第一个新 VBox 的副本
vbox2 = vbox.copy(); // 创建第二个新 VBox 的副本
// 计算切割点两侧的长度
left = i - vbox[dim1]; // 计算左侧距离
right = vbox[dim2] - i; // 计算右侧距离
// 如果 left 小于或等于 right，则切割点 d2 应该在 i 的右侧，距离 i 的一半 right 的位置，但不能超过 vbox[dim2] - 1。
// 如果 left 大于 right，则切割点 d2 应该在 i 的左侧，距离 i 的一半 left 的位置，但不能小于 vbox[dim1]
if (left <= right) d2 = Math.min(vbox[dim2] - 1, ~~(i + right / 2));else d2 = Math.max(vbox[dim1], ~~(i - 1 - left / 2));
// avoid 0-count boxes
// 避免 0 计数的盒子
while (!partialsum[d2]) d2++;
count2 = lookaheadsum[d2];
while (!count2 && partialsum[d2 - 1]) count2 = lookaheadsum[--d2];
// set dimensions
// 设置新 VBox 的维度
vbox1[dim2] = d2;
vbox2[dim1] = vbox1[dim2] + 1;
return [vbox1, vbox2];
}
}
}
// determine the cut planes
// 确定切割平面
return maxw == rw ? doCut('r') : maxw == gw ? doCut('g') : doCut('b');
}
// inner function to do the iteration
function iter(lh, target) {
var ncolors = lh.size(),// 优先队列中 VBox 的数量
niters = 0, // 迭代次数计数器
vbox; // 待分割的 VBox
// 最大迭代次数限制，防止无限循环
while (niters < maxIterations) { // 这里 maxIterations 为 1000
if (ncolors >= target) return; // 如果颜色数量已达到目标，则结束迭代
// 如果像素数量过低会导致死循环。这里通过niters++加判断跳出循环
if (niters++ > maxIterations) {
// console.log("infinite loop; perhaps too few pixels!");
return;
}
// 从优先队列中取出一个 VBox
vbox = lh.pop(); // pop 会修改原数组
// 如果取出的 VBox 没有颜色（count 为 0），则将其放回优先队列
if (!vbox.count()) {
/* just put it back */
lh.push(vbox);
niters++;
continue;
}
// 对取出的 VBox 进行分割
var vboxes = medianCutApply(histo, vbox), // medianCutApply是中值切割量化算法的核心部分，用于将一个 VBox（体积盒子）分割成两个新的 VBox，以便减少图像中的颜色数量。
vbox1 = vboxes[0], // 分割得到的两个新 VBox 中的第一个
vbox2 = vboxes[1]; // 分割得到的两个新 VBox 中的第二个（可能为 null）
// 如果分割失败
if (!vbox1) {
// console.log("vbox1 not defined; shouldn't happen!");
return;
}
lh.push(vbox1); // 将分割得到的第一个新 VBox 放回优先队列
if (vbox2) { // 如果第二个新 VBox 存在，则也将其放回优先队列，并增加颜色数量计数
/* vbox2 can be null */
lh.push(vbox2);
ncolors++;
}
}
}
// first set of colors, sorted by population
iter(pq, fractByPopulations * maxcolors); // fractByPopulations 为 0.75，这是两阶段分割策略中第一阶段75%的限制值
iter它是颜色量化算法中的一个内部迭代函数，用于通过迭代分割 VBox 来减少颜色数量，直到达到目标颜色数量
注：partialsum和lookaheadsum数组含义
两阶段分割策略 第二阶段：基于像素数量和颜色空间体积的乘积进行分割，直到达到最终的目标颜色数量（MMCQ）
var pq2 = new PQueue(function (a, b) {
return pv.naturalOrder(a.count() * a.volume(), b.count() * b.volume());// 优先队列的排序依据是 VBox 中的像素数量与其在颜色空间中的体积的乘积
});
while (pq.size()) { // 将另一个优先队列 pq 中的所有元素转移到新的优先队列 pq2 中。
pq2.push(pq.pop());
}
// next set - generate the median cuts using the (npix * vol) sorting.
iter(pq2, maxcolors);// 第二阶段分割时，限制不再是第一阶段的75%而是全部
上段代码是将优先队列pq中的所有元素按照新的排序规则转移到另一个优先队列pq2中，然后使用pq2中的元素进行中值切割，以生成最终的颜色量化结果。通过这种方式，算法可以优先处理哪些在颜色空间占据较大体积且包含较多像素的VBox，从而优化颜色量化结果。执行步骤和逻辑和第一阶段一致。
生成调色板、最近颜色匹配和输出结果(MMCQ)
// Color map
/**
* CMap (Color Map) constructor
*
* This function initializes a new CMap object, which is used to store and manage
* color information in the quantization process. The CMap uses a priority queue (PQueue)
* to efficiently organize and access color data.
*
* Data Structure:
* - CMap: An object containing a priority queue of VBox objects.
* - VBox (Volume Box): Represents a 3D color space volume. Each VBox contains:
* - Color range information (r1, r2, g1, g2, b1, b2)
* - A histogram of colors within this range
* - Methods for calculating average color, volume, and other properties
*
* The priority queue is sorted based on the product of each VBox's count (number of pixels)
* and volume (size in color space). This sorting helps in selecting the most significant
* color ranges for the quantized palette, balancing between color popularity and diversity.
*
* The CMap structure allows for efficient color quantization by iteratively splitting
* the color space (represented by VBoxes) and selecting the most representative colors.
*/
// CMap 对象，用于存储和管理量化过程中的颜色信息。
function CMap() {
// 初始化一个优先队列，用于存储 VBox 对象
// 优先队列的排序依据是每个 VBox 的像素数量和体积的乘积
this.vboxes = new PQueue(function (a, b) {
return pv.naturalOrder(a.vbox.count() * a.vbox.volume(), b.vbox.count() * b.vbox.volume());
});
}
CMap.prototype = {
// 将一个新的 VBox 添加到优先队列中
push: function push(vbox) {
this.vboxes.push({
vbox: vbox,
color: vbox.avg() // 使用 VBox 的平均颜色作为代表色
});
},
// 获取颜色映射中的调色板
palette: function palette() {
return this.vboxes.map(function (vb) {
return vb.color; // 返回每个 VBox 的代表色
});
},
// 获取优先队列中的 VBox 数量
size: function size() {
return this.vboxes.size();
},
// 将给定的颜色映射到颜色映射中的最近颜色（如果颜色没找到时，使用最近颜色匹配）
map: function map(color) {
var vboxes = this.vboxes;
for (var i = 0; i < vboxes.size(); i++) {
// 如果给定的颜色在某个 VBox 的颜色范围内
if (vboxes.peek(i).vbox.contains(color)) {
return vboxes.peek(i).color; // 返回该 VBox 的代表色
}
}
return this.nearest(color); // 如果没有找到，返回最近的颜色
},
// 找到给定颜色的最近颜色
nearest: function nearest(color) {
var vboxes = this.vboxes,
d1, // 用于存储当前最近的距离
d2, // 用于存储新计算的距离
pColor; // 用于存储当前最近的颜色
for (var i = 0; i < vboxes.size(); i++) {
// 计算给定颜色和 VBox 代表色之间的欧几里得距离
d2 = Math.sqrt(Math.pow(color[0] - vboxes.peek(i).color[0], 2) + Math.pow(color[1] - vboxes.peek(i).color[1], 2) + Math.pow(color[2] - vboxes.peek(i).color[2], 2));
// 如果新计算的距离小于当前最近的距离，或者当前还没有最近的颜色
if (d2 < d1 || d1 === undefined) {
d1 = d2; // 更新最近的距离
pColor = vboxes.peek(i).color; // 更新最近的颜色
}
}
return pColor;
},
// 强制将颜色映射中的最暗和最亮颜色分别设置为黑色和白色
forcebw: function forcebw() {
// XXX: won't work yet
var vboxes = this.vboxes;
vboxes.sort(function (a, b) {
return pv.naturalOrder(pv.sum(a.color), pv.sum(b.color)); // 将 vboxes 按颜色总和排序
});
// force darkest color to black if everything < 5
var lowest = vboxes[0].color;
// 如果最暗的颜色非常暗，则将其设置为黑色
if (lowest[0] < 5 && lowest[1] < 5 && lowest[2] < 5) vboxes[0].color = [0, 0, 0];
// force lightest color to white if everything > 251
var idx = vboxes.length - 1,
highest = vboxes[idx].color;
// 如果最亮的颜色非常亮，则将其设置为白色
if (highest[0] > 251 && highest[1] > 251 && highest[2] > 251) vboxes[idx].color = [255, 255, 255];
}
};
// calculate the actual colors
var cmap = new CMap(); // 创建一个新的颜色映射对象
while (pq2.size()) {
cmap.push(pq2.pop()); // 从 pq2 中弹出（移除）最后一个元素，并将其添加到颜色映射 cmap 中
}
return cmap; // 返回颜色映射对象
欧几里得距离公式
getPalette函数
function getPalette(img, colorCount = 10, quality = 10) {
//....
//....
const cmap = quantize(pixelArray, options.colorCount);
const palette = cmap ? cmap.palette() : null;
return palette;
});
}
最后根据返回的cmap.palette()数组
参考文章
- 8位深度 伪彩色图 为什么能呈现彩色，不应该只能表示灰度吗
- JavaScript 的双位非运算（~~）