【毕业论文】求解最优的任意宝可梦颜色交换算法

单位 | 索尼互动娱乐Polyphony Digital

研究方向 | 计算机图形学与神经网络

转自｜PaperWeekly

（加个英文标题：A Algorithm for Color Transfer on Pokémon Images

其实原来是要作为毕业论文发表的，但是因为本科只要求毕业研究发表，于是英文的稿子也懒得完善了，就算是给 zhigraph 投稿的首发吧。因为不是什么正式的发表所以想到什么就写什么，当然如果有需要引用的话可以直接引用本文 link（233）。

▲ 本文算法的结果

写在前面

神经网络太牛了，只要有数据集就能完成所有的任务。但是有没有可能有的任务就是没有数据集呢。面对这种任务，传统的 CV、数学建模，迎来了他的魅力时刻。由于整个大学期间都在做（混）神经网络，让笔者觉得很没意思，想着毕业论文（没错这篇 zhigraph 就是名义上的毕业论文了）换一种口味不用神经网络（其实还是用了）来完成一个惊艳的任务吧。

▲ 本文算法的颜色交换结果

省流

简单来说，本文提供了一种通过数学建模的，将任意一个宝可梦的配色应用到另外一个宝可梦上，并且保证配色交换后能有最优的效果（某种数学意义上）的算法。

▲ 本文算法的颜色交换结果

01 动机

比较正式的动机是，Color Transfer [1]，Style Transfer [2]，blablabla。类似的论文太多了，因为是在 zhigraph 发表所以笔者懒得贴引用了。

▲ Color Transfer

原来为了毕业研究发表会，写了一大堆，但是其实最主要的动机是，在研究生成模型的时候，发现无论是 gan，vae，diffusion，还是其他的各种变体，都无法很好地学习纯宝可梦（注意是纯，不带其他先验信息，不是 finetune 的）的 dataset。比如我们搜索一下 Pokemon 的生成 Benchmark，可以看到：

FID 都很低。其中最好的效果如下，也和其他数据集的效果差距太大：

▲ StyleGAN-XL的结果

▲ Projected GAN的结果

自己稍微训练了一下，发现一个可能的原因是宝可梦的变化比较大，但是真实的数据集比较小，只有不到 2k 张（不算 Fakemon），然后能做的 Data Augment 也有限，通常就是 Hue Shift 一下，但是很明显 Hue Shift 之后会带来不太正确的先验，导致训练出来的模型有颜色上的 Bias。外加哪怕带上 Hue Shift 之类的常见 Augment，训练出来的效果也就十分一般。

可以举个例子说明一下为啥 Hue Shift 不行，比如我希望让妙蛙种子变成火系的：

无论是往黄色方向偏移还是往红色方向偏移，Hue Shift 总是怪怪的。究其原因其实是 HSV/HSL 颜色空间下，相同的亮度值，饱和度值，在不同 Hue 下人眼感知到的亮度值和饱和度值是不一致的。当然还有其他解决的办法，比如用新的颜色空间 Oklab，Oklch, JzAzBz（没用过）来进行调整。但是笔者这边没有更多的图的存货，也展示不了，但是实际上效果和 HSV 没什么两样，甚至有时候亮度还会 Overshoot。

但是如果使用本文的算法，你可以得到这样的妙蛙种子：

▲ 本文算法结果：火系妙蛙种子

这个结果应用了火恐龙的配色，按照最优度排序的第一个结果。可以看到本文的算法效果十分惊艳，后面将会有客观数据说明该算法的成功。

▲ 火恐龙的配色原图

02 研究目标

研究目标一：从宝可梦图像中提取调色板（Palette）

研究目标二：将任意提取出来的调色板应用到任意宝可梦中

03 基础知识

为了更好进行后续的说明，这里笔者先解释几个概念。

1. 基于 RGB 的图像表现

通常，图像都由 RGB 三个分量表示：

RGB 的好处是三个分量相互独立，但是通常情况下 RGB 三个分量对人类来说并没有什么（美学上的，数学上的）意义。

2. 基于调色板的图像表现

而基于调色板的图像表现可以表示为：，其中 是调色板颜色， 是该颜色的权重。

使用调色板表示的图像可以看到更具美学/数学（笔者想了很久数学上的意义是什么，可能是什么单连通多连通开路径闭路径上的纯净感）意义上的分割，我们可以通过可视化来感受这一点：

▲ 图像被调色板和权重分为多个有实际意义的分割区域

因为基于调色板的图像表现的优秀图像分割能力，本文的颜色交换也是基于调色板表示的图像进行的。

3. 调色板交换

我们可以看到，基于调色板的表达方式可以很方便地进行颜色替换。

一个颜色替换的例子是：

▲ 交换了红绿色

调色板的交换可以定义为：

其中新的调色板是：

图示：

根据排列组合的知识，我们知道任意的交换办法有很多种。而本文的算法的目标是找到其中最优的一种。也就是求解图中的问号。

04 调色板提取/交换的方法

本文的研究重点并非是调色板的提取，因此直接使用 Blind Color Separation [3]（稍作修改）作为提取办法。但是从 RGB 图像中提取调色版是一个有趣的课题，所以本文也会稍微讲解一下。

Blind Color Separation 的精髓在于求解以下凸问题，如果感兴趣可以去阅读张青老师的原论文：

由于本人学术不精，不会求解二次四次的凸问题，最后是使用了一个二次非负性来约束一个梯度下降求解器来完成相似的效果。除了求解时间慢了四五倍之外，结果是能接受的。由于这个提取办法本文没有什么改进（唯一改进是加入了一个新约束项来保证调色板选取原图像的颜色），因此不再赘述。

但是这个方法，很有趣的，通过以下渐进地增大 来使得原本不可优化的 L0 项 最小化可以被渐进地逼近，真的十分巧妙。

这个算法的出处最早应该是 L0 Gradient Minimization [4]：

这个 L0 其实就是向量中非 0 的 Scalar 的个数，想象 Lp 范数，L0 就是 ，十分有趣，但是笔者的语文不好描述不了他为什么有趣了。

这个问题难就难在求解最小 L0 是 NP hard 的，具体证明俺也不懂。

在笔者阅读论文之前，脑内风暴的时候，是有想过这个方向的，可惜晚生了二十年，又错失一个 siga 的论文机会（好吧一年前发的 sig 也没什么时间发到 zhigraph 了）。

另外也有很多通过调色板提取算法进行换色的算法，他们和本文的最大区别是，本文的换色是任意图像匹配，全自动。而之前的算法大多数都需要人手配对调色板，而可以自动匹配的算法则效果很差（尤其是卡通图像，之后会说明）。

需要说明的是，哪怕人手进行调色板之间的颜色匹配更换，能得到好效果的也是少数。这里简单说明一下几种常见的人手匹配更换（并非两两图像颜色交换）的方法：

1. 基于簇的算法

2. 基于凸包的算法

顺带说一下 Blind Color Separation 是基于 Cluster 的，由于只实现了这个，因此不好评价 Convex hull 的算法，有兴趣的朋友也可以实现一下。

05 本文的算法

我们通过前面的章节知道，给定了两张都用调色板表达的图片，只要把全部调色板两两配对的情况都试一遍，总能找到最好的一种匹配方法。我们人眼可以知道什么配对情况最优，但是计算机并不知道。为此，我们需要为“适合度”找到一个合理的数学定义。

1. 两两图像之间的距离

给定两张图片 ，定义他们的距离方法有很多。

最常用的就是 ，但是这些纯数值方法不包含任何先验信息，会在某些“美学”指标上抓瞎（好吧很民科，很符合本人的精神状态）。

那么很自然地，我们会想到更 Advanced 的办法，比如所有生成模型都在用的perceptual loss，里面的那个 pretrained 的 vgg，带了很多符合人眼特征的先验信息，如果能利用的话，就很好。

因此本文定义一个深度图像距离：

其中 是刚刚提到的预训练过的 vgg 网络，下标 表示其中某一层的特征输出。

我们用这个距离就能更好地表达两张图片的差异。

2. 深度距离的不足

很多时候，同样是 Hue Shift 的图像，深度距离会给出很大的差异。其中的原因可能是，预训练的 VGG 中没有加入太多的“去配色影响的几何不变性”。和平移不变性一样，这个去配色影响的几何不变性对于宝可梦图像来说尤其重要。

3. 理想颜色变换空间

为了去除配色对图像距离影响，本文提出了密集颜色变换空间的概念。

我们知道，对于图像 一个包含全部最优配色的图像的集合可以描述为 。这里可能有点绕，但是笔者也想不到更好的说明方法了。

这里的 代表了一种从图像变换到图像的函数（方法），他可以是 Hue Shift，或者“把白色变成红色”，“将图像反色”等全部可能的“非几何的”图像变化方法之一。这里的 是全部“合理”的“对于人类来说最优的”变化方法的集合，也就是一个颜色变换函数构成的空间，于是 则是先前提到的“包含全部最优配色的图像的集合”的符号。

由于这个 是最优的，最理想的。又知道原图的配色（任天堂给出的原图）一定是合理的。合理的配色变换后的图像的全部合理配色变换图像中一定包含了原图像，因为原图像一定是合理的。用数学语言描述，假如 是合理的 ：

都有 使得

换句话说，如果我们找到两个图像空间的最近距离，通过这个距离我们一定程度上（只能说一定程度）就能求得这两个图像的去配色影响的距离。

到这里，我们成功把图像的距离转换为图像空间的距离，并且这个理想的新的距离是完全的去配色影响的。

但是很明显，这里的 是不可求的。我们需要其他方法来近似这个空间。

4. 密集颜色变换空间

虽然我们无法求得一张图的全部合理的颜色变换，但是我们知道一定某种程度上合理的颜色变换。比如刚刚提到的不尽人意的 Hue Shift，如果你希望，还可以有 Brightness Shift，Saturation Shift，从HSV，HSL，其他各种有意义的颜色空间进行的各种 Shift。为此，这种图像变换空间，本文称为密集颜色变换空间。

本文的实现只采用 HSV 空间中的 Hue，Brighness，Saturation 的 Shift。由这些参数的取值的排列组合，我们可以构造出近似的 ，记作 。

5. 图像空间距离

如果我们把图像在 Pretrained VGG 的 latent space 上的向量看作高维的点，可以应用 Hausdorff Distance 来求这个点集的距离。

最终，我们把“应用了新配色方案的图像的适合度”问题，转换成了“应用了新配色方案的图像”的应用了“密集颜色变换空间”的图像集合 与 原图像 应用了“密集颜色变换空间”的图像集合的相似性。好吧，有点绕。

6. 最优配色

全部可能的配色方案置换的集合记作 ，我们可以通过最小化变换后的图像与原图像的 求得最优变换 ：

至此，全部的计算已经可求。

06 实验结果

1. 从宝可梦图像中提取调色板

▲ 提取调色板结果

可以得出结论：效果不错。

2. 颜色交换结果

笔者的主观评价是：效果不错。

3. 主观性评估

笔者口说无凭，但是又由于该任务十分地具有主观性，因此本文将生成的结果若干个与其他自动颜色交换算法的结果放在一起进行比较，做成了问卷，尽可能随机地邀请了一些人进行评估。

具体评估规则如下，宝可梦画像 25 张，互相交换，交换的结果 600 张中选择 25 张用作问卷调查。其中混入其他三种其他算法，分别是亮度匹配，平均 HueShift，以及 Monge-Kantorovich Linearization。问卷中选项出现的顺序均是随机的。问题的顺序也是打乱的。当然，标签也是完全盲的。

▲ 左边：原图/颜色参考图; 中间：问卷内容；右边：使用的算法

参加问卷调查的人共 68 人，其中：

12 个人有美术背景，并且大家都熟知宝可梦。

统计结果如下：

我们的方法差不多在一半的宝可梦颜色互换图像中取得了最好的成绩。然后是最基础的亮度匹配，平均 HueShift，最后是 Monge-Kantorovich Linearization。

可以得出结论，我们的方法在大多数情况下能求得最符合人审美的宝可梦颜色交换的方案。

参考文献

A Blind Color Separation Model for Faithful Palette-Based Image Recoloring：https://ieeexplore.ieee.org/document/9382104/;jsessionid=414ACAD58BE89D6B85CB45B6563356E3

Video Recoloring via SpatialTemporal Geometric Palettes：https://cragl.cs.gmu.edu/videopalette/Video%20Recoloring%20via%20Spatial-Temporal%20Geometric%20Palettes%20(Zheng-Jun%20Du,%20Kai-Xiang%20Lei,%20Kun%20Xu,%20Jianchao%20Tan,%20Yotam%20Gingold%202021%20SIGGRAPH%20Asia)%20presentation%2017-minutes.pdf

Color Transfer for Images: A Survey：https://dl.acm.org/doi/pdf/10.1145/3635152

Image recoloring based on fast and flexible palette extraction：https://link.springer.com/article/10.1007/s11042-023-15114-5