65.9K
CodeProject 正在变化。 阅读更多。
Home

一个简单而功能强大的 C# 调色板量化器

Smart K8
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.97/5 (103投票s)

2010年3月18日

CPOL

21分钟阅读

viewsIcon

375494

downloadIcon

13076

基于人类感知的调色板量化器

介绍 

本文介绍了一种调色板量化器，它对初学者来说简单易懂，但对日常使用来说足够强大。从2.0版开始，它包含了优化版本，以及其他常用量化器的实现供您使用。从4.0版开始，它还包含了不同的颜色匹配算法，以提高实际可用性。在5.0版中，增加了抖动和并行处理支持（详见更新日志）。

SimplePaletteQuantizerVS2008

背景

我一直在寻找一个好的颜色量化算法，我的第一站当然是Code Project。我找到了很多量化器，但它们都非常相似。它们都基于八叉树，并且都以不准确的方式减少调色板。我需要一些更像瑞士军刀的量化器，即使对于1位色深也能合理地减少调色板。它必须足够快，足够精确，并且结果至少要高于平均水平。所以我设计了一种基于HSL颜色模型的算法，它更像人眼一样处理图像。

Using the Code

本文的代码非常简单，易于理解。它由一个接口IColorQuantizer组成，该接口提供基本的量化器功能。还有一个实现类PaletteQuantizer，本文主要介绍它。

颜色量化解释

它是一个尝试将给定图像中的颜色数量减少到一定有限数量（由外部因素给定），同时保持图像视觉本质不变的过程。它通常用于满足某些设备的显示能力，以减小图像的原始大小。此外，某些图像格式仅支持最多256种颜色（例如GIF格式）。源图像中的颜色数量通常远高于允许的数量，因此算法必须仔细丢弃颜色。

接口 SimplePaletteQuantizer/New.png

我尽量保持它的简单性，同时允许集成其他实现。例如Code Project上那些基于八叉树的算法。因为在我看来，一个好的API是第一步。这里去掉了注释，所以所有方法都可以在下面更详细地描述。但乍一看，我想您应该已经知道接下来会发生什么了。

public interface IColorQuantizer
{
    Boolean AllowParallel { get; } // introduced in version 5.0
    void Prepare(ImageBuffer image); // introduced in version 4.0 - changed in version 5.0
    void AddColor(Color color, Int32 x, Int32 y); // changed in version 5.0
    List<Color> GetPalette(Int32 colorCount);
    Int32 GetPaletteIndex(Color color, Int32 x, Int32 y); // changed in version 5.0
    Int32 GetColorCount();
    void Finish(); // introduced in version 5.0
    void Clear(); // deprecated in version 4.0
}

更详细的说明

那么，我们逐一介绍；不耽搁。AddColor() 方法用于向量化器提供图像像素颜色。之后，这些颜色将根据需要被丢弃并保持在调色板范围内。基本思想是，您通常会遍历一个或多个图像的所有像素（如果您想在它们之间共享该调色板）。所有这些颜色都提供给量化器，量化器根据实现将创建各种结构和其他装置，以便随时生成特定大小的调色板。此方法是主要方法，将大量使用。因此，它应该尽可能快。

另一个重要的方法是GetPalette()，它通常是主要的技术诀窍。有许多算法可用，但基本上都是从n维数据（RGB颜色模型的情况是立方体）中提取代表性点。理想情况下，量化器中（即源图像中）的颜色数量小于或等于我们想要的数量。但通常情况并非如此。因此，我们不能拥有所有真彩色，而是被迫只拥有限定的一组颜色。此方法正是这样做的。它选择一组颜色，并希望最终这些颜色能最接近地代表图像。

当我们收集完颜色并确定调色板后，是时候将所有像素从真彩色（RGB或ARGB）转换为我们调色板中的索引了。由于此方法也用于每个像素，因此它也必须尽可能快。通常，所有“肮脏的”技巧都用在这里。基本上，每个像素都有一个任意颜色（RGB最多2^24种颜色，或ARGB最多2^32种颜色），而您在此方法中的任务是，在您仅仅（最多256种颜色）的调色板中找到该颜色，并返回其索引。这很困难，但绝非不可能。

最后两个方法，GetColorCount() 和 Clear() 相比之下只是美化。GetColorCount 顾名思义，检索当前量化器中存储的唯一颜色数量。它通常用于向用户展示您将颜色数量减少了多少，但图像看起来仍然一样……嗯，几乎一样。Clear() 方法用作维护方法，以清除所有那些宝贵的颜色。新的 Prepare() 方法执行旧 Clear() 方法的功能，但它也提供了事先处理图像的机会（从版本 4.0 开始）。然后，量化器就可以进行下一轮处理了，处理下一张图像。

在 5.0 版本中，添加了 Finish() 方法，基本上是为了重新引入旧的 Clear() 方法（但怯懦地给了它一个不同的名字，使其看起来像一个完全不同的方法）。它用于在处理结束后进行清理，因为当多个量化器同时使用时，会占用大量内存。此外，还增加了 AllowParallel 属性，以确定量化器是否支持并行处理。同样值得注意的是，ImageBuffer 类进行了重构，以清理和优化像素处理。

我的方法

既然我们知道了游戏中有什么方法，我将不再像我实现它们那样逐一描述。我将尝试将这三个阶段中发生的事情汇总成一个元注释-要点-代码。

第一阶段 - 哈希表作弊

记住，这个阶段对应于将所有像素的颜色数据读入我们的智能结构。我的智能结构是一个哈希表。一个简单的`Dictionary<Int32, Int32>`，其中键是32位颜色值（如ARGB四元组），值是图像数据中存在这种颜色的像素数量。这个存在计数器在这里的作用并不大，所以我称之为作弊，因为一个`Boolean`在这里几乎可以做同样的工作。但最终，我发现它有一些用途……所以就是这样。MBC（元-要点-代码）

  • 扫描源图像的所有像素。
  • 如果哈希表中存在颜色，则将像素存在值增加1。
  • 如果不存在，则添加并设置像素存在值为1。

到目前为止一切顺利，但最奇怪的还在后面。

第二阶段 - 颜色研磨机

我们现在已经统计了所有像素。那么，让屠杀开始吧。这里我指的是GetPalette()方法。

  • （通过您选择的固定种子）随机化颜色的顺序，统计学站在我们这边。
  • 如果量化器中的颜色少于或等于请求的颜色，我们就完成了。我们只取所有这些颜色。这是理想情况。
  • 否则，创建三个列表。一个按色调明确过滤，另一个按饱和度过滤，最后一个按亮度过滤。请记住，这些必须是浮点表示。
  • 确定其中哪个元素最多。扫描图像的细节在该区域中。我们的候选者就在这个区域。

在继续之前，让我稍微解释一下。如果唯一色相列表最大，那很可能是一张包含许多颜色的图像，因此重要的是捕捉所有这些丰富多彩的细节。如果是亮度，那么图像上可能有一些颜色较少但阴影较深的对象。至于饱和度，细节主要在彩色阴影中。所以我们正在稍微适应眼睛所看到的东西。既然我们已经减少了大部分颜色，让我们开始稍微完善我们的选择。继续。

  • 如果颜色仍然多于我们需要的数量，则继续；否则，我们就完成了。
  • 现在，在剩余的方面之间进行一场类似的“死斗”。例如，如果色调是主要的方面，那么我们再次按亮度和饱和度过滤我们的颜色。
  • 再次选择颜色更多的那一个。
  • 如果获胜者的颜色少于我们需要的数量，则忽略它并冲向最后一轮。
  • 否则，选择这些颜色。
  • 作为最后手段，尝试通过最后一个方面过滤颜色（如果我们在第一层选择了色调，在第二层选择了亮度，那么就是饱和度）。
  • 同样，如果这会导致颜色少于请求的数量，则忽略它。
  • 否则，传递它。

此时，我们应该已经将颜色数量减少到我们需要的程度，但如果仍然有太多颜色，我们只需

  • 按像素计数存在（哈希中的值）对剩余颜色进行排序。
  • 然后只取我们请求的顶部 (n) 种颜色。这样，我们就得到了我们需要的确切数量。
  • 这是我们代表性颜色的结果集。所以将它们传出函数。

第三阶段 - 几乎欧几里得

如果您遵循了这里的所有步骤，您现在应该拥有一个具有相当好的颜色表示的调色板。现在所需要做的就是将目标图像上的所有颜色更改为我们调色板中的索引。您可以使用任何您想要的算法，但我只是使用了古老的欧几里得距离（没有平方根，以加快速度）。

  • 对于源中的每个像素，获取其颜色。
  • 调用GetPaletteIndex()方法。
  • 如果缓存包含此颜色（我们之前已经请求过），则返回缓存的索引。
  • 否则，用欧几里得距离查找，并将索引存储在缓存中。（Dictionary<Color, Byte>）
  • 将结果索引存储在目标图像中。

一图胜千言

我鼓起勇气将所有这些都放到了下面的图中，所以请随意查看，并请多多包涵。我的一些朋友告诉我，它实际上比纯粹的要点更令人困惑。但努力已经付出了，也许你们中的一些人会更喜欢这种方式。所以不多说了，这个怪物来了。

A truly monstrous diagram.

独特选择量化器（即本文描述的颜色量化器）

我将其仅作为与其他算法的比较，我试图保持客观。

Pros
  • 非常好的图像质量（尤其是照片）
  • 支持所有颜色计数
Cons
  • 内存消耗
  • 较慢
     （在4.0版中 - 可以通过局部敏感哈希或八叉树搜索颜色缓存进行改进）
     （在5.0版中 - 通过并行处理和其他优化进一步改进）

竞争者……市面上的替代方案 SimplePaletteQuantizer/New.png

正如 Som Shekhar 所指出的，列出并简要描述一些其他潜在的 IColorQuantizer 实现。所以，我履行承诺。

均匀量化（2.0版已包含）

这种算法是现存最古老的算法之一。它是一种朴素的方法。每个颜色分量轴（红、绿和蓝）被分成几个固定段（如255种颜色中8-8-4或252种颜色中6-6-7）。每个找到的颜色都放入相应的段槽中。添加所有颜色后，计算每个槽的平均颜色。这些就是调色板的颜色。

Pros
  • 非常快
  • 文件非常小
  • 内存占用低
Cons
  • 图像质量差
  • 仅还原为256色

流行度算法（2.0版已包含）

与均匀量化类似，并且肯定属于同一家族的，是一种所谓的流行度算法。我最初的目标是编写类似这样的东西，但后来它演变成更好的东西（我希望如此）。一个RGB立方体也被分成4x4x4的小区域（每种颜色分量256/4 = 64个，因此有262,144个小立方体）。颜色也被放置到相应的区域中，并且还计算像素存在。所有颜色到位后，选择像素存在最高的N个区域，计算平均颜色。这给我们N种调色板颜色。

Pros
  • 文件非常小
  • 内存占用低
  • 支持所有颜色计数
Cons
  • 图像质量非常差
    高度着色的图像

中值切割（2.0版已包含）

中值切割采取了一种不同的方法，本质上更具几何性。首先它将所有像素放入RGB空间中，然后找到包含所有像素的最小盒子（最坏的情况是整个立方体，但这很不寻常）。然后迭代过程开始。选择最长的轴（R、G或B），并沿该轴对点进行排序。然后计算中值，并用一个平面在该点切割盒子。这样我们就得到了两个较小的盒子。我们再次递归地对它们应用此操作，直到我们得到N个盒子，它们的包含颜色再次取平均值以给出调色板条目。

Pros
  • 可接受的图像质量
  • 支持所有颜色计数
Cons
  • 内存消耗
  • 较慢
     （在4.0版中 - 可以通过局部敏感哈希或八叉树搜索颜色缓存进行改进）
     （在5.0版中 - 通过并行处理和其他优化进一步改进）

八叉树算法（2.0版已包含）

网上有大量关于此方法的文章，因为它是目前最常用的算法。这里仅引用Code Project上的一篇（CQuantizer）。基本上，一个立方体被迭代地分成多个立方体（再次）。但这一次，它是沿所有轴同时进行的（维基百科上的八叉树）。所以只创建盒子来覆盖插入的像素。一旦所有颜色都被计算在内，分支（那些包含至少一个叶子的分支）将从最深层开始被减少，因为在那里颜色通常彼此更近。通过计算其所有叶子的平均值来减少一个分支，消除它们从而自身成为一个叶子。当我们拥有的叶子数量低于或等于我们想要的颜色数量时，我们停止减少，并解析所有叶子以获取我们的调色板颜色。因此，减少是一个破坏性过程，八叉树只能使用一次。此外，最多可以一次减少8个叶子，最坏的情况下调色板中只剩下248种颜色（这并不太理想）。

Pros
  • 非常快
  • 良好的图像质量
Cons
  • 内存消耗
  • 仅支持256种颜色
     （在4.0版中 - 添加了对任何颜色数量的支持）

空间颜色量化

我对这种方法了解不多，因为它相对较新，我也不太想尝试。我只知道它以某种方式将量化与抖动结合在一起，同时对于16种或更少的颜色来说非常出色。它不适用于256种颜色等高颜色计数。请自行在SColorQ上查看。这些是我针对较低比特率测试的图像。它非常令人印象深刻。我显然无法在4bpp及更低的位深下与那里的抖动竞争。

Pros
  • 图像质量极好
Cons
  • 非常慢
  • 仅在每个调色板2-16种颜色时有效
  • 不适用于照片（和平滑图像）

吴氏颜色量化器（4.0版已包含）

另一个几何量化器是吴晓林（Xiaolin Wu）的吴氏颜色量化器。此算法速度较慢，但提供了其他算法无法企及的极佳图片质量。它是一种聚类算法，通过切割RGB空间来找到所需数量的立方体。切割参数是体积方差。正如作者所说：“通过包含-排除技巧辅助，对RGB空间进行贪婪正交二分，以最小化方差。”如果您认为质量比速度更重要，我推荐此算法。

Pros
  • 图像质量极好
  • 支持所有颜色计数
Cons
  • Slow
  • 内存消耗

NeuQuant算法（4.0版已包含）

该算法使用Kohonen神经网络来学习图像颜色。神经元然后对应于颜色槽，随着神经网络的训练而优化。您可以在质量和速度之间进行选择。通过对所有像素进行采样，您将获得最大的质量，或者您可以选择较低的质量（采样步长）以执行更快的量化。该算法应用于更高的颜色计数。我已将其限制为仅256种颜色。请随意尝试其他选项。它在视觉丰富的图像（如照片和渲染图像）上表现更好。

Pros
  • 良好的图像质量（尤其是照片） - 取决于质量设置
  • 内存消耗
Cons
  • 较慢 - 取决于质量设置

优化调色板算法（5.0版已包含） SimplePaletteQuantizer/New.png

关于此算法没什么可说的。它基本上是一个智能计算的（但不可更改的）调色板，它覆盖了所有颜色，但实际上没有一种颜色。您将获得平均结果，无需合成调色板（因为一个已经准备好），但结果也会有点平均。

Pros
  • 相当快
  • 几乎不消耗内存
Cons
  • 图像质量非常差
  • 仅支持256种颜色

颜色缓存

自4.0版起，增加了对颜色缓存的支持。您可以通过BaseColorQuantizer.ChangeColorCache()分配这些IColorCache实现。此概念通过引入新接口取代了“我懒惰”的默认欧几里得距离最近颜色搜索。

public interface IColorCache
{
    void Prepare();
    void CachePalette(IEnumerable<Color> palette);
    void GetColorPaletteIndex(Color color, out Int32 paletteIndex);
}

该接口允许您在量化调色板中单独实现最佳颜色搜索。CachePalette()允许您将已经计算好的调色板存储在您的智能结构中。GetColorPaletteIndex()替换了IColorQuantizer的方法（详见）。Prepare()方法只是在第一次（或下一次）传递之前清除所有杂乱。现在有三种实现可用。

欧几里得距离

这是一个标准的三维距离，但为了加快速度，没有开平方根。详见欧几里得距离。下面是三维的一般方程。

SimplePaletteQuantizer/LocalitySensitiveHashing.png

局部敏感哈希

我搜索了互联网，寻找更快的颜色匹配算法。我找到了这个有趣的通用算法最近邻问题，我想知道它是否对我有用。然后我将其改造成一个用于颜色匹配问题的功能版本。所以现在您提供“质量”（实际上是桶的数量）。这个算法可以通过结合更多的参考点（例如与白色和红色的距离）来进一步改进（速度）。然后可以计算交集，以便更精确地猜测最近的颜色，而无需计算昂贵的欧几里得距离。质量范围从1（最佳质量，有额外开销）。不建议使用此值，因为它没有带来任何优势。其他值：8（快/质量95%），16（更快/质量85%），32（非常快/60%），或64（几乎瞬时/30%）。我不会再进一步了。

SimplePaletteQuantizer/LocalitySensitiveHashing.png

八叉树搜索

该技术将八叉树算法中的快速搜索与特定的量化算法调色板相结合，而无需使用八叉树算法。它比欧几里得距离算法快得多，几乎没有质量损失。下面这张粗略的图是微软完整八叉树量化算法粗略图的略微修改版本。调色板中的每种颜色都添加到它所经过的每个树节点的列表中。当搜索特定颜色时。您将找到最远的可用节点，然后对特定节点列表中的所有颜色执行欧几里得距离比较。

SimplePaletteQuantizer/OctreeSearch.png

抖动 SimplePaletteQuantizer/New.png

抖动过程基于这样一个事实：人眼对亮度的变化更敏感。因此，需要减少量化对最终图像亮度平滑度的影响，同时仍试图保持其特征（例如边缘，它们应该是亮度的急剧过渡）。

在 5.0 版中，引入了一个新接口来处理抖动功能。让我们简要了解它包含什么。主要方法是 ProcessPixel，它接受一个源像素，对其颜色执行抖动例程，然后返回一个抖动后的（目标）像素。然后有一个标志属性 IsInplace，此标志决定抖动处理是否仅发生在已处理的像素上。因此，像素可以在量化过程中进行处理（速度快得多）。Prepare() 方法用于在处理前准备抖动器，而 Finish() 用于在处理后进行清理。

public interface IColorDitherer
{
    Boolean IsInplace { get; }
    void Prepare(IColorQuantizer quantizer, Int32 colorCount, ImageBuffer sourceBuffer, ImageBuffer targetBuffer);
    Boolean ProcessPixel(Pixel sourcePixel, Pixel targetPixel);
    void Finish();
}

有许多抖动方法，本文中包含的一些抖动方法简要列表是

有序抖动

这种抖动类型只处理实际像素，而不了解图像中的其他变化（通过抖动其他像素）。这在一定程度上限制了能力，但这种方法仍然能产生我们习惯的图像。

阅读维基百科了解更多信息：有序抖动

Original

拜耳

聚类点
SimplePaletteQuantizer/Original.png SimplePaletteQuantizer/Bayer.png SimplePaletteQuantizer/ClusteredDot.png

误差扩散抖动

此方法处理像素，并将累积误差（差异）分配给其邻居。它取决于像素处理的顺序。

阅读维基百科了解更多信息：误差扩散

Original

弗洛伊德-斯坦伯格

阿特金森

贾维斯-朱迪斯-宁克
SimplePaletteQuantizer/Original.png SimplePaletteQuantizer/FloydSteinberg.png SimplePaletteQuantizer/Atkinson.png SimplePaletteQuantizer/JarvisJudiceNinke.png

截图画廊SimplePaletteQuantizer/New.png

这些只是一些图片，展示了内部工具的新功能，以及一些新的统计数据。
您现在可以从五种颜色量化方法中选择一种来比较算法。您还可以选择将源图像缩减到的位深度。

SimplePaletteQuantizer/SimplePaletteQuantizer1v2.png

左侧还有另一个选择，允许您预览源图像保存为 GIF（特别是为 Roey C）后的样子，以及一些预估大小统计信息，即量化图像保存为 GIF 或 PNG 后的大小。

SimplePaletteQuantizer/SimplePaletteQuantizer2v2.png

在 4.0 版中，增加了一些新选择。首先，现在可以为某些量化器选择要使用的颜色缓存类型。在以前的版本中，只有缓慢的欧几里得距离方法可用。现在您可以从另外两种更快速的方法中选择。

SimplePaletteQuantizer/SimplePaletteQuantizer3v4.png

同样在 4.0 版中，为某些颜色缓存添加了对颜色模型的支持。虽然没有太大区别，但它在那里是为了进一步优化（我很懒）。我添加了支持，然后我注意到它并没有真正产生差异，但我把它留在了那里。

SimplePaletteQuantizer/SimplePaletteQuantizer4v4.png

版本 5.0 带来了对并行处理的支持，它真正利用了多核处理器，并允许发挥全速潜力。

SimplePaletteQuantizer/SimplePaletteQuantizer5v5.png

版本 5.0 还包含抖动支持。这可能会提高颜色缩减质量（但也可能导致质量下降）。

SimplePaletteQuantizer/SimplePaletteQuantizer6v5.png

反馈

一如既往，欢迎在下面的论坛中提出任何问题。我目前正在忙于一些更大的项目，所以很快会发布另一篇文章。这个量化器可能会是其中的一部分，尽管不是必不可少的部分。

相关文章

更改日志

版本 5.0

  • 新增算法：最佳调色板量化器（好吧，有点作弊，但我就是想添加一些新方法）。
  • 所有图形例程都已重写和优化。现在包含直接像素（无论深度如何）访问。
  • 增加了并行处理支持。这会带来速度提升（取决于处理器核心数量）。
  • 由于评论区多次提及抖动方法。现在添加了一些抖动方法。
  • 更快的随机数（感谢colgreen），因为这里速度很重要，随机性没那么重要。
  • 其他通用加速，例如早期调色板检测（少于所需颜色）、避免浮点数、尽可能使用Color（24字节！）。
  • 所有方法的颜色计数检测已修复。

4.0 版本

  • 新增两种算法：吴氏颜色量化器和基于NeuQuant神经网络的量化器
  • 通用优化分析速度提升约2倍于原始速度
  • 像素枚举现在支持内存版本，这在某些情况下应该会带来一些速度提升
  • 一些量化器现在支持可互换的颜色缓存。速度提升约2-3倍（在某些情况下高达5-6倍）
  • 修复了处理索引图像（Image.Palette！）的致命缺陷，这将索引图像的速度提高了100倍
  • 新的颜色缓存概念，以实现比慢速欧几里得最近颜色更快的速度
  • 一些颜色缓存还包括颜色模型选项
  • 该工具现在可以加载和处理所有像素格式（甚至包括索引格式）
  • 该工具现在在打开时显示图像文件名
  • 注意：在我的CPU上，测试图像 3072 x 2304（169220 种颜色）现在需要 3.5 秒（使用 HSL 方法 + 八叉树搜索）
  • 注意：图像 512 x 512（155774 种颜色）需要 0.5 秒。因此它能很好地随大小缩放。基本上从现在开始是 Dictionary (C#) 的速度问题。
  • 注意：不要忘记在 Visual Studio 外部测试，并在发布模式下构建。

版本 3.0

  • 八叉树量化器现在支持所有颜色计数（根据 Matt Perdeck 的要求）
  • 量化图像现在以最佳像素格式存储（自动检测）
  • 现在可以计算NRMSD（归一化均方根偏差）
  • 一些小修复和加速

版本 2.0

  • 各种速度优化（感谢 Andrew Rissing）
  • 包含Alpha混合支持
  • 包含多种量化算法
  • 新增半透明图像支持
  • 添加了预测统计数据（为 Roey C）
  • 现在测量量化过程持续时间
  • 代码注释覆盖率增加
  • 界面略有更改，以支持更多调色板索引（Andrew Rissing）

版本 1.0

  • 初始自发版本发布

历史

  • 2012-07-28：版本 5.0 发布
  • 2011-07-04：添加了颜色缓存部分
  • 2011-07-04：版本 4.0 发布
  • 2011-07-02：版本 3.0 发布
  • 2010-03-26：版本 2.0 发布
  • 2010-03-19：添加了颜色量化解释部分
  • 2010-03-18：添加了竞争者……市面上的替代方案部分
  • 2010-03-18：首次发布文章
© . All rights reserved.