论文 Generating Playful Palettes from Images 发表于 EG 2019。作者是上一篇论文：Playful Palette: An Interactive Parametric Color Mixer for Artists 的原班人马（讲解在这里：论文回顾：Playful Palette: An Interactive Parametric Color Mixer for Artists）。 上一篇论文提出了一种新的支持颜色光滑混合的调色板，这篇论文主要讲如何从已知图像中抽取出Playful Palette，算是对第一篇论文的一个扩展。一个常见的应用就是从别人的画作中抽取调色板，并“偷”用别人的调色板画画。
先上一张论文的Teaser。左侧是输入图像，中间是通过优化求解抽的Playful Palette，右侧是近似的调色板。下方的下图是图像在RGB空间的点云。二者 的区别是，优化求解的调色板的颜色更接近原始图像的颜色，但计算效率较低。近似解法求解的调色板没有那么精确，但是计算更快，实际中更好用。
一、问题定义
Playful Palette由多个color blob生成，每个圆形的blob定义为：
B
i
=
(
r
i
,
g
i
,
b
i
,
u
i
,
v
i
)
B_i = (r_i,g_i,b_i,u_i,v_i)
Bi?=(ri?,gi?,bi?,ui?,vi?), 分别表示颜色和圆心坐标。为此，由多个color blob定义的调色板可以统一表示为：
x
=
{
r
1
,
g
1
,
b
1
,
u
1
,
v
1
,
r
2
,
g
2
,
b
2
,
u
2
,
v
2
,
.
.
.
}
(1)
x = \{r_1,g_1,b_1,u_1,v_1,r_2,g_2,b_2,u_2,v_2,...\}\tag1
x={r1?,g1?,b1?,u1?,v1?,r2?,g2?,b2?,u2?,v2?,...}(1)
论文将color blob的数目统一设置为
n
=
8
n=8
n=8. 具体如何从color blob得到Playful Palette，可以参见上一篇博客。
本文的主要目标是使得生成的调色板能很好的表示原始图像的颜色，为此，定义了如下的能量函数。
d
(
I
,
I
x
)
=
α
(
1
∣
I
∣
∑
p
∈
I
min
?
q
∈
I
x
∥
p
R
G
B
?
q
R
G
B
∥
2
)
+
(
1
?
α
)
(
1
∣
I
x
∣
∑
q
∈
I
x
min
?
p
∈
I
∥
p
R
G
B
?
q
R
G
B
∥
2
)
(2)
\begin{aligned}d\left(I, I_{\mathbf{x}}\right)=\alpha\left(\frac{1}{|I|} \sum_{p \in I} \min _{q \in I_{\mathbf{x}}}\left\|p_{R G B}-q_{R GB}\right\|^{2}\right) +(1-\alpha)\left(\frac{1}{\left|I_{\mathbf{x}}\right|} \sum_{q \in I_{\mathbf{x}}} \min _{p \in I}\left\|p_{R G B}-q_{R G B}\right\|^{2}\right)\end{aligned}\tag2
d(I,Ix?)=α???∣I∣1?p∈I∑?q∈Ix?min?∥pRGB??qRGB?∥2???+(1?α)???∣Ix?∣1?q∈Ix?∑?p∈Imin?∥pRGB??qRGB?∥2????(2)
其中， I I I表示输入图形， I x I_x Ix?表示由公式（1）生成的Playful Palette， d ( I , I x ) d\left(I, I_{\mathbf{x}}\right) d(I,Ix?) 表示衡量二者的差异。能量函数包括两项：第一项：惩罚输入图像中有而调色板中没有的颜色；第二项：惩罚调色板中有而原始图像中没有的颜色。 α \alpha α平衡二者贡献，本文设为 α = 0.9 \alpha = 0.9 α=0.9, 优化的最好结果使得生成的Playful Palette的颜色输入图像的颜色一一对应。
为此，优化对象就是公式（1）所示的 n n n 个color blob的颜色和位置参数，优化的目标是minimize公式（2）对应的能量函数。
二、优化版本
由于公式（2）所示的能量函数无法直接求导，因此不能使用基于梯度下降的算法最优化。因此，作者使用了一个 derivative-free的方法（这类算法很常见，NLOPT中就有很多类似的优化算法）。
2.1、加速技巧
1）Playful Palette 的绘制范围压缩到
48
×
48
48\times 48
48×48的正方形内部；
2）输入图像进行下采样，首先将整个图像空间均匀划分为
16
×
16
×
16
16 \times 16 \times 16
16×16×16 的bins， 并从这些非空的bin中采样1000个像素点。
2.2、初始化
初始化就是给定color blob的初始颜色和位置，一般的做法就是直接随机初始化。但公式（2）所示的能量函数有一个可能的显著问题是：大量位置的梯度为0。可以这样解释这个现象：比如只有两个color blob并且相隔较远，当我们移动任意一个blob一小段距离时，Playful Palette的颜色空间无任何变化，因为不会有颜色混合，所以大部分区域的梯度不变且为0， 这样很可能落到局部最优而难以找到全局最优解。 比如初始化时各个color blob相聚较远时，基本没有办法通过优化将他们拉回来。
为此，作者聪明的将所有color blob的初始位置都设为 u = 0.5 , v = 0.5 u = 0.5, v=0.5 u=0.5,v=0.5, 如此以来，最优化方法就可以将他们慢慢移动开，最终收敛到一个最优的解。
总体来讲，这个方法较慢，不适合交互式的应用，为此，作者进一步提出了近似算法求解Playful Palette。
三、近似解法
近似解法用到 Self Organizing Maps ，简称SOM，中文称为自组织映射。
自组织映射(Self-organizing map, SOM)通过学习输入空间中的数据，生成一个低维、离散的映射(Map)，从某种程度上也可看成一种降维算法。SOM是一种无监督的人工神经网络。
不同于一般神经网络基于损失函数的反向传递来训练，它运用竞争学习(competitive learning)策略,依靠神经元之间互相竞争逐步优化网络。且使用近邻关系函数(neighborhood function)来维持输入空间的拓扑结构。
运用到本文就是将RGB空间的输入图像映射到二维的调色板平面，并且使得相似的颜色在调色板中位置接近。这个方法首次在另一篇SIGGRAPH 论文中被使用：Data-driven Color Manifolds， 我也学习了这个算法，修改了一份简易的代码：https://github.com/Zhengjun-Du/Color_Manifolds，效果如下：
本文就应用了这个SOM算法来辅助生成color blob，具体而言如下图所示。
- 首先使用SOM将输入图像降维到光滑的二维平面 32 × 32 32 \times 32 32×32；
- 对降维的图像进行 k-Means 聚类；
- 对聚类中心所在的2D坐标进行 Delaunay 三角剖分。（三角剖分的目的是确定color blob的相邻关系，然后进一步移动位置）。
四、实验效果
1）Optimizaiton version 和 approximate version比较
2）公式（2）中不同
α
\alpha
α 对求解的影响
3）跟其他几种算法 Chang et al, Tan et al 的比较, 这两个离散调色板直接代入公式（2）计算能量误差。
总结
- 论文提出了通过能量优化的方法提取给定图像的Playful Palette, 对于电子绘画中临摹别人画风有指导意义；
- 通过SOM算法引入近似解法，效率较高；
- 基于Playful Palette的Recoloring值得研究。