android palette 提取主色的原理

小灰灰 2021-03-23 13:04 639阅读 0赞

2018年3月26日更新内容： 添加中位切割算法的维基。

导读：

提取图片主色，核心逻辑是遍历图片的像素，对图片中颜色和该颜色的像素个数进行统计，构造采样结果 `List<Swatch>` ，然后提取主色或者其他风格的颜色（就是简单的把 Swatch 对应的色值返回），本文会把重点放在 `List<Swatch>` 的构建上，其中涉及 Palette 的简单源码与分析，以及中位切割算法（Median Cut）在这个过程中的应用。

首先，我们先宏观的了解一下采样（即构造`List<Swatch>`）的核心逻辑，

1.  设定一个采样个数，比如 16 个。
2.  对图片的像素进行统计，得出一个横轴为色值，纵轴为个数的直方图。
3.  如果色值个数 count <= 16，采样结束。
4.  如果色值个数 count > 16，需要对色值进行合并，合并的过程使用了 median cut 算法。

Palette 中的中位切割算法是进行了优化的，不过算法思想是不变的。首先引入一个数据结构 Vbox 来表示待切割的对象。

/** * Represents a tightly fitting box around a color space. */
        private class Vbox {
            // lower and upper index are inclusive
            private int mLowerIndex;
            private int mUpperIndex;
            // Population of colors within this box
            private int mPopulation;
    
            private int mMinRed, mMaxRed;
            private int mMinGreen, mMaxGreen;
            private int mMinBlue, mMaxBlue;
        }

Vbox 只是一个包装类。其中 mLowerIndex 和 mUpperIndex 分别代表这个 Vbox 所关心的 mColors 数组中的对应的索引的上下界。mColors 就是一个普通的数组，代表我们上文统计出来的直方图的数据结构原型。数组索引代表色值，数组值代表这个色值对应的像素的个数。注意 Vbox 中的mMinRed 和 mMaxRed 系列变量。他们代表的所有 Vbox 中包含的色值在 RGB 三个分量上的最大最小值。比如，颜色 x 的 R 分量值为二进制的`00000000`，颜色 y 的 R 分量的值为二进制的`11111111`，那么 `mMinRed = 0x00; mMaxRed = 0xFF;`。 进行中位切割的时候，Vbox 会首先对色值进行一个排序。但是，排序的依据不是简单的色值大小，而是“范围最大的颜色分量”。比如，(mMaxRed - mMinRed) > (mMaxGreen - mMinGreen) > (mMaxBlue - mMinBlue)，那么就是以各个色值的 R 分量的大小进行排序。然后类似于二分法，找到排序结果的中位，进行分割，得到两个新的、小的 Vbox 。 每一个 Vbox，我们在生成最终结果的时候，都会将其中包含的色值取平均数。所以，回到采样算法中，我们最初预想得到 16 个采样值。那么就需要有至少 16个 Vbox。当有多个 Vbox 的时候，如何选择下一个待切割的 Vbox 呢？当然我们可以不假思索的直接 random 取一个，只是得到的采样效果可能不好。所以，android palette 类对取下一个 Vbox 做了优化。这里，还需要引入一个颜色体积的概念。我们把 (mMaxRed - mMinRed) \* (mMaxBlue - mMinBlue) \* (mMaxGreen - mMinGreen) 记为颜色体积，然后每次取下一个 Vbox 的时候，取颜色体积最大的那个。

理论讲完了，下面进行代码分析。

首先是入口函数，这里显然就是 Palette 实例的构建。Palette 实例的构建很简单，就是一个简单的 builder 模式。而，整个算法的核心也就在 `builder.generate()` 之中。

Palette.Builder builder = new Palette.Builder(bitmap);
    Palette palette = builder.generate();

`builder.generate()`中关键逻辑如下：

// Now generate a quantizer from the Bitmap
    final ColorCutQuantizer quantizer = new ColorCutQuantizer(
            getPixelsFromBitmap(bitmap),
            mMaxColors,
            mFilters.isEmpty() ? null : mFilters.toArray(new Filter[mFilters.size()]));
    swatches = quantizer.getQuantizedColors();
    // Now create a Palette instance
    final Palette p = new Palette(swatches, mTargets);
    return p;

这里我们可以看到，`List<Swatch>`的值与 ColorCutQuantizer 息息相关。在 ColorCutQuantizer 的构造函数中，实现了我们上文的逻辑：如果得到的颜色个数 count <= 16，就直接返回，否则进行 midian cut 算法来生成 16 个颜色。

if (distinctColorCount <= maxColors) {
        // The image has fewer colors than the maximum requested, so just return the colors
        mQuantizedColors = new ArrayList<>();
        for (int color : colors) {
            mQuantizedColors.add(new Swatch(approximateToRgb888(color), hist[color]));
        }
    } else {
        // We need use quantization to reduce the number of colors
        mQuantizedColors = quantizePixels(maxColors);
    }

median cut 的算法实现是在 quantizePixels(maxColors) 中了。代码如下所示。

private List<Swatch> quantizePixels(int maxColors) {
        // Create the priority queue which is sorted by volume descending. This means we always
        // split the largest box in the queue
        final PriorityQueue<Vbox> pq = new PriorityQueue<>(maxColors, VBOX_COMPARATOR_VOLUME);
        // To start, offer a box which contains all of the colors
        pq.offer(new Vbox(0, mColors.length - 1));
        // Now go through the boxes, splitting them until we have reached maxColors or there are no
        // more boxes to split
        splitBoxes(pq, maxColors);
        // Finally, return the average colors of the color boxes
        return generateAverageColors(pq);
    }

`quantizePixels()` 函数流程中，使用了优先级队列来存储 Vbox ，其中，第二个参数 `VBOX_COMPARATOR_VOLUME` 是一个 custom comparator ，其中的利用 `Vbox#getVolume()` 方法返回颜色体积，进而进行大小比较。算法运行过程中，先把所有的颜色放到一个初始 Vbox 中，作为优先级队列的第一个元素。然后在循环中不断的对 Vbox 进行切割（其实就是我们说的二分法），切割的时候，需要对 Vbox 的颜色按照跨度最大的那个颜色分量进行排序，直到 Vbox 数量为我们想要的采样数为止。

/** * Comparator which sorts { @link Vbox} instances based on their volume, in descending order */
    private static final Comparator<Vbox> VBOX_COMPARATOR_VOLUME = new Comparator<Vbox>() {
        @Override
        public int compare(Vbox lhs, Vbox rhs) {
            return rhs.getVolume() - lhs.getVolume();
        }
    };
    
    final int getVolume() {
        return (mMaxRed - mMinRed + 1) * (mMaxGreen - mMinGreen + 1) *
                (mMaxBlue - mMinBlue + 1);
    }

至此，整个算法的框架我们已经梳理完成。

补充内容：

**中位切割算法（Median cut）** 是Paul Heckbert于1979年提出来的算法。概念上很简单，却也是最知名、应用最为广泛的减色算法（[Color quantization][]）。常见的影像处理软件如Photoshop、GIMP...等，都使用了这个算法或其变种。

假如你有任意一张图片，想要降低影像中的颜色数目到256色。

1.  将图片内的所有像素加入到同一个区域
2.  对于所有的区域做以下的事：
    
    1.  计算此区域内所有像素的[RGB][]三元素最大值与最小值的差。
    2.  选出相差最大的那个颜色（R或G或B）
    3.  根据那个颜色去排序此区域内所有像素
    4.  分割前一半与后一半的像素到二个不同的区域（这里就是“中位切割”名字的由来）
3.  重复第二步直到你有256个区域
4.  将每个区域内的像素平均起来，于是你就得到了256色

[Color quantization]: https://zh.wikipedia.org/w/index.php?title=Color_quantization&action=edit&redlink=1
[RGB]: https://zh.wikipedia.org/wiki/RGB