0%

JavaScript实现Android Palette颜色提取算法

Android Palette Library 是一个从 Bitmap中 提取图像的主题颜色的工具库。我最近对 Palette 的实现感兴趣,阅读源码理解了它的原理后,我打算用 JavaScript 来实现同样的功能。
example

1. 获取图片的像素数据

通过 canvas 获取图片的像素信息 ImageData, ImageData 中包含图片的宽高和一个Uint8数组,该数组以 RGBA 的形式存储像素数据。

1
2
3
4
5
6
7
8
9
10
let width = this.image.width;
let height = this.image.height;

let canvas = document.createElement('canvas');
canvas.width = width;
canvas.height = height;

let ctx = canvas.getContext("2d");
ctx.drawImage(this.image, 0, 0);
let data = ctx.getImageData(0, 0, width, height).data;

2. 以柱状图的形式统计所有颜色出现的次数

柱状图是一个一维 int 数组,数组 index 对应颜色的 int 值,对应的取值表示该颜色的出现次数。RGB888包含的颜色大约有1600万(255x255x255)种颜色,这里将RGB888颜色空间转成RGB555颜色空间。RGB555包含32768(32x32x32)种颜色,可减少大量的计算量。

1
2
3
4
5
6
7
8
9
let colorCount = 1 << 15;
let histogram = new Int16Array(colorCount);

for (let i = 0; i < data.length; i += 4) {
let r = data[i] >> 3;
let g = data[i + 1] >> 3;
let b = data[i + 2] >> 3;
histogram[r << (10) | g << 5 | b]++;
}

3. 筛选出现次数大于0的颜色

将出现次数大于0的颜色保存在一个数组中,统计不同颜色的数量 distinctColorCount。*shouldIgnoreColor * 方法会忽略掉接近白色、黑色和红色的颜色。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
let distinctColorCount = 0;
for (let color = 0; color < colorCount; color++) {
if (histogram[color] > 0 && ColorCutQuantizer.shouldIgnoreColor(color)) {
histogram[color] = 0;
}

if (histogram[color] > 0) {
distinctColorCount++
}
}

let colors = new Int16Array(distinctColorCount);
let index = 0;
for (let color = 0; color < colorCount; color++) {
if (histogram[color] > 0) {
colors[index++] = color;
}
}

如果 distinctColorCount 小于等于我们需要提取的采样个数 maxColors,那么我们的采样流程结束,直接生成颜色样本。

1
2
3
4
5
6
7
8
9
10
11
12
if (distinctColorCount <= maxColors) {
this.quantizedColors = new Array(distinctColorCount);
for (let i = 0; i < distinctColorCount; i++) {
let color = colors[i];
let r = (color >> 10) & 0x1f;
let g = (color >> 10) & 0x1f;
let b = color & 0x1f;
this.quantizedColors[i] = new Swatch(r, g, b, histogram[color])
}
} else {
this.quantizedColors = ColorCutQuantizer.quantizePixels(histogram, colors, maxColors)
}

4. 通过中位切分算法提取样本

如果我们拥有的颜色数量比需要的样本数量多,利用中位切割算法将颜色数量裁剪到需要的采样数量。

  1. 将所有的颜色放入一个长方体(Vbox
    Vbox

我们对 Vbox 进行初始化,得到该 Vbox 对应的R、G、B的最大和最小值,以及表示的该颜色范围内所有像素的数量的 population

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
fitBox() {
this.minRed = this.minGreen = this.minBlue = Number.MAX_VALUE;
this.maxRed = this.maxGreen = this.maxBlue = 0;
this.population = 0;

for (let i = this.lowerIndex; i <= this.upperIndex; i++) {
let color = this.colors[i];
this.population += this.histogram[color];

let r = quantizedRed(color);
let g = quantizedGreen(color);
let b = quantizedBlue(color);

if (r > this.maxRed) {
this.maxRed = r
}
if (r < this.minRed) {
this.minRed = r
}
if (g > this.maxGreen) {
this.maxGreen = g
}
if (g < this.minGreen) {
this.minGreen = g
}
if (b > this.maxBlue) {
this.maxBlue = b
}
if (b < this.minBlue) {
this.minBlue = b
}
}
};
  1. 将这个 Vbox 放入一个优先级队列(PriorityQueue)中。JavaScript 中没有 PriorityQueue 这样的数据结构,我在 Github 上找到了对应的简单实现 TinyQueue。该队列根据 Vbox 的体积排序:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // 获取Vbox的体积 — 三边长的乘积
    getVolume() {
    return (this.maxRed - this.minRed + 1) * (this.maxGreen - this.minGreen + 1) * (this.maxBlue - this.minBlue + 1);
    };

    ...

    let queue = new TinyQueue();
    queue.compare = function (a, b) {
    return b.getVolume() - a.getVolume();
    };
  2. 将RGB中最长的一边从颜色统计的中位数一切为二,使得到的两个长方体所包含的像素数量相同。中位切割最重要的是找到切割的点,下面是我们找到 Vbox 切割点的方法:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    findSplitPoint() {
    // 获取Vbox最长的边
    let longestDimension = this.getLongestColorDimension();

    // 我们需要根据最长的边对该Vbox中的颜色进行排序,由于当前是颜色RGB空间
    // 如果最长的边是Green则需要把颜色修改为GRB,如果最长边是Blue修改为RGR
    Vbox.modifySignificantOctet(this.colors, longestDimension, this.lowerIndex, this.upperIndex);

    // 对Vbox内的颜色排序
    Vbox.sortRange(this.colors, this.lowerIndex, this.upperIndex);

    Vbox.modifySignificantOctet(this.colors, longestDimension, this.lowerIndex, this.upperIndex);

    let midPoint = this.population / 2;
    let count = 0;
    for (let i = this.lowerIndex; i <= this.upperIndex; i++) {
    count += this.histogram[this.colors[i]];
    if (count >= midPoint) {
    return Math.min(this.upperIndex - 1, i)
    }
    }
    return this.lowerIndex
    };
    将分割出的2个的 Vbox 放入队列中,然后我们再从队列中获取体积最大的一个 Vbox 继续分割,直到 Vbox数量达到我们需要的样本数量。

5. 根据Vbox生成样本Swatch

getAverageColor方法计算Vbox中的所有颜色的平均值,然后生成一个 Swatch。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
getAverageColor() {
let redSum = 0, greenSum = 0, blueSum = 0, totalPopulation = 0;
for (let i = this.lowerIndex; i <= this.upperIndex; i++) {
let color = this.colors[i];
let colorPopulation = this.histogram[color];

totalPopulation += colorPopulation;
redSum += colorPopulation * quantizedRed(color);
greenSum += colorPopulation * quantizedGreen(color);
blueSum += colorPopulation * quantizedBlue(color);
}

let redMean = Math.round(redSum / totalPopulation);
let greenMean = Math.round(greenSum / totalPopulation);
let blueMean = Math.round(blueSum / totalPopulation);

return new Swatch(redMean, greenMean, blueMean, totalPopulation);
};

6. 根据Target对Swatch打分,获得最终的主题颜色值列表

Target 定义了我们对颜色饱和度和亮度的最低值、目标值和计算评分的权重要求,默认定义了6种 Target:

  • Vibrant (有活力的)
  • Vibrant dark(有活力的 暗色)
  • Vibrant light(有活力的 亮色)
  • Muted (柔和的)
  • Muted dark(柔和的 暗色)
  • Muted light(柔和的 亮色)

我们得到的 Swatch 是RGB的颜色值,需要通过转换RGB(RGB转HSL算法)得到对应的HSL颜色值然后打分,HSL即色相(Hue)、饱和度(Saturation)、亮度(Lightness)。

在计算分数之前需要判断该Swatch是否满足评分的要求 — 饱和度和亮度在 Target 的要求范围之内,并且该Swatch 没有被其他Target使用。因此该 Targe 可能t获取不到对应的 Swatch。

1
2
3
4
5
6
7
8
9
shouldBeScoredForTarget(swatch, target) {
let hsl = swatch.getHsl();
let s = hsl[1];
let l = hsl[2];

return s >= target.getMinimumSaturation() && s <= target.getMaximumSaturation()
&& l >= target.getMinimumLightness() && l <= target.getMaximumLightness()
&& !this.usedColors.get(swatch.rgb);
};

我们将饱和度分数、亮度分数、像素 Population 分数三项分数加起来,得到该 Target 评分最高的 Swatch。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
generateScore(swatch, target) {
let saturationScore = 0;
let luminanceScore = 0;
let populationScore = 0;
let maxPopulation = this.dominantSwatch.population;

let hsl = swatch.getHsl();

if (target.getSaturationWeight() > 0) {
saturationScore = target.getSaturationWeight() * (1 - Math.abs(hsl[1] - target.getTargetSaturation()));
}
if (target.getLightnessWeight() > 0) {
luminanceScore = target.getLightnessWeight() * (1 - Math.abs(hsl[2] - target.getTargetLightness()));
}
if (target.getPopulationWeight() > 0) {
populationScore = target.getPopulationWeight() * (swatch.population / maxPopulation);
}

return saturationScore + luminanceScore + populationScore;
};

全部代码已上传到Githubhttps://github.com/wangyiwy/palette-js