Terrarum::异世界丨居正博客
source link: https://blog.skyju.cc/post/find-the-most-similar-image-with-palette-colors/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
寻找主题配色最相近的两张图片
这个问题实际上也就是寻找配色最相近的两张图片，或者计算两张图片配色上的相似度。需要与之区分的是“寻找相似图像”，前者单论配色，与主题色的相似度及出现的范围大小有关；而后者则把图像中的具体细节，如物体形状、颜色各自出现的位置等因素也考虑在内，更加严格。
Feb 03, 2022 By 居正
一般来说，一副稍微用点心的标准文章题图由至少由几个部分组成：背景图、前置元素及文字（例如本文的题图）。
最近想到一个点子，用与文章背景题图配色相似的动漫角色作为一个前置元素附上，可能可以给题图增加一点生气。
这个问题实际上也就是寻找配色最相近的两张图片，或者计算两张图片配色上的相似度。需要与之区分的是“寻找相似图像”，前者单论配色，与主题色的相似度及出现的范围大小有关；而后者则把图像中的具体细节，如物体形状、颜色各自出现的位置等因素也考虑在内，更加严格。实际上经过调研，寻找相似图像已经有许多成熟的算法，包括aHash、dHash、pHash等。但不适用于这次的需求。
首先从某个TG频道下载一定数量的动漫图像作为原材料，共560张，依次编号。
接下来应该从这些图像中提取主题配色。常见的主题色提取算法有中位切分法、八叉树算法等（ 参考）。由于有现成的Go类库实现了中位切分法，于是直接使用（地址）。
生成每张图片对应的主题色：
实际上最开始是生成2^3=6中主题色，但后期测试发现主题色太多效果反而不好，于是改为2^2=4种。主题色表现在Go代码中则是对应一组color.Color的切片。我将一张图片对应的一组主题色成为一份palette。
接下来需要将目标图片的palette与每张动漫图片对比。每个color即是由RGB三个指标构成的三维向量，感觉很麻烦。从调研了解到可以将三个指标转换成Hue（色调），然后对比Hue就行。
计算Hue的公式是从Stack Overflow上直接找的。
func Hue(color color.RGBA) float64 {
r := float64(color.R) / 255
g := float64(color.G) / 255
b := float64(color.B) / 255
rgb := []float64{r, g, b}
sort.Float64s(rgb)
min := rgb[0]
max := rgb[2]
if max == min {
return 0
}
hue := 0.0
if r >= g && r >= b {
hue = (g - b) / (max - min)
} else if g >= r && g >= b {
hue = 2.0 + (b-r)/(max-min)
} else {
hue = 4.0 + (r-g)/(max-min)
}
hue = hue * 60
if hue < 0 {
hue += 360
}
hue /= 360
return hue
}
注：Go代码中的颜色为RGBA，A即Alpha通道，代表透明度，在本文所述的需求中可以直接舍弃。
可以从palette得到一个Hue的数组。在比较两个图像的palette时，把数组的长度作为向量的维数计算向量的距离。
计算向量距离有几种不同的方法，如欧几里得距离（下图L2）、曼哈顿距离（下图L1）等。实际上由于需要的是相对图像相似度，这几种计算方法对精度基本上没有影响。
用Go标准库的切片排序对图像进行对比和排序。
sort.Slice(girls, func(i, j int) bool {
first := GetPaletteDistance(girls[i], targetPalette)
second := GetPaletteDistance(girls[j], targetPalette)
return first < second
})
尝试之后发现效果非常差，基本上没法用。
调研了解到由于人眼对于颜色其他因素，如亮度的感知实际上比色调更明显，于是由RGB算出亮度也加入到palette的距离计算中。
func Brightness(color color.RGBA) float64 {
return 0.299*float64(color.R)/255 + 0.587*float64(color.G)/255 + 0.114*float64(color.B)/255
}
注：计算亮度其实有多种公式，这里选择的这种是将人类感知力（human perception）考虑在内的一种调整后的公式。
所以现在的代码看起来是这样的：
type Palette struct {
Colors []color.Color `json:"-"`
Hues []float64 `json:"hues,omitempty"`
Brightness []float64 `json:"brightness,omitempty"`
ID int `json:"id,omitempty"`
}
hueDist := 0.0
for i := 0; i < len(p1.Hues); i++ {
hueDist += math.Abs(p1.Hues[i] - p2.Hues[i])
}
brightnessDist := 0.0
for i := 0; i < len(p1.Brightness); i++ {
brightnessDist += math.Abs(p1.Brightness[i] - p2.Brightness[i])
}
return hueDist*0.7 + brightnessDist*0.3
亮度和色调的权重也经过一定调整，但效果时好时坏。
我有想过会不会是因为不同位置色块对不上的问题。因为palette是一个不同颜色的数组，先后有位置区别。可能A图片在下标0的颜色和B图片下标2的颜色非常相近，但这样对比只会讲A图片下标0与B图片下标0的颜色对比，A图片下标2的与B图片下标2的颜色对比，导致完美错过。
所以之后试了几种方法，比如把颜色不论顺序两两比对、取把两张图片最相似的两个颜色的距离（或赋予较大的权重）等，效果都不太理想。猜测可能是因为很多图片都具有某种共同的颜色，如深灰色至黑色，这样的颜色在每张图片中都有，也被palette作为一个主题色呈现，但实际上在图片中占的权重并不多，只是背景的一小部分，并不能作为主题色。而那种比较鲜明的，尤其是动漫角色身体上的颜色才能色是主题色。
但如果要将动漫角色去掉背景抠出来的话就不是我这种简单程序能解决的问题了，关键是我完全不会AI…
再次调研找到一种解决方案，是直接取图片的直方图，然后用一些算法对比。
Go里面用这个类库可以生成图像的直方图数据。
两张主题色基本全是蓝色的图像直方图分别是这样：
每张直方图有256个bin，每个bin的大小代表对应bin的高度。但直接一一对应计算距离显然是不行，因为比如看两种图中蓝色线的位置根本不一样，不在一个bin里。
调研发现有Earth Mover's Distance、Chi-squared distance等方法可以用，但搜了半天基本上只有思路和paper和公式没有代码实现，又全是英文的，我太菜了实在不会用就放弃了。
不过在调研中偶然了解到除了RGB以外的颜色表示方式，如YUV、CIELAB之类的。
这些方式，比如YUV颜色空间，是比较贴合人类视觉的，把亮度之类的因素也纳入考虑。实际上这样的数据表示方式才会比较适合直接套用向量距离计算。比如CIELAB：
三个基本坐标表示颜色的亮度（L*, L* = 0生成黑色而L* = 100指示白色），它在红色／品红色和绿色之间的位置（**a***负值指示绿色而正值指示品红）和它在黄色和蓝色之间的位置（**b***负值指示蓝色而正值指示黄色）。
那么就把之前的计算色调的亮度的代码统统扔掉，改成用把RGB转成LAB空间的方法：
func RGB2CIELAB(inputColors []uint8) []float64 {
RGB := []float64{0, 0, 0}
for ix, value := range inputColors {
v := float64(value) / 255
if v > 0.04045 {
v = math.Pow((v+0.055)/1.055, 2.4)
} else {
v = v / 12.92
}
RGB[ix] = v * 100.0
}
XYZ := []float64{0, 0, 0}
X := RGB[0]*0.4124 + RGB[1]*0.3576 + RGB[2]*0.1805
Y := RGB[0]*0.2126 + RGB[1]*0.7152 + RGB[2]*0.0722
Z := RGB[0]*0.0193 + RGB[1]*0.1192 + RGB[2]*0.9504
XYZ[0] = X
XYZ[1] = Y
XYZ[2] = Z
XYZ[0] = XYZ[0] / 95.047
XYZ[1] = XYZ[1] / 100.0
XYZ[2] = XYZ[2] / 108.883
for ix, value := range XYZ {
if value > 0.008856 {
value = math.Pow(value, 0.3333333333333333)
} else {
value = (7.787 * value) + (16.0 / 116)
}
XYZ[ix] = value
}
Lab := []float64{0, 0, 0}
L := (116.0 * XYZ[1]) - 16
a := 500.0 * (XYZ[0] - XYZ[1])
b := 200.0 * (XYZ[1] - XYZ[2])
Lab[0] = L
Lab[1] = a
Lab[2] = b
return Lab
}
代码抄的是GitHub Gist上某个用Python写的代码。
然后直接计算palette对应色块的曼哈顿距离：
type Palette struct {
Colors []color.Color `json:"-"`
LAB [][]float64
ID int `json:"id,omitempty"`
}
manhattanDist := 0.0
for i := 0; i < len(p1.LAB); i++ {
manhattanDist += math.Abs(p1.LAB[i][0]-p2.LAB[i][0]) + math.Abs(p1.LAB[i][1]-p2.LAB[i][1]) + math.Abs(p1.LAB[i][2]-p2.LAB[i][2])
}
return manhattanDist
发现效果比之前好多了，强差人意吧。有一些时候还是会出现莫名其妙配色对不上的图像，或者明明用肉眼感觉匹配度比较高的图像没有入选。但果然还是直接转成用现成的标准化的色彩空间比较好，自己调色调和亮度的权重太难了。
在Stack Overflow上又看到了另一种思路（链接），不需要提取palette，直接把图片缩放成很小，比如4x4的像素。然后把每个像素作为一个三维向量计算距离。据说效果可能也不错。不过由于图像缩放算法很多，也需要多尝试选到一种最合适的才行。
又尝试了下两两对比的方法：
for i := 0; i < len(p1.LAB); i++ {
for j := 0; j < len(p1.LAB); j++ {
manhattanDist += math.Abs(p1.LAB[i][0]-p2.LAB[j][0]) + math.Abs(p1.LAB[i][1]-p2.LAB[j][1]) + math.Abs(p1.LAB[i][2]-p2.LAB[j][2])
}
}
个人感觉准确度会比直接比对高一点点，考虑到palette反正也只有4种颜色，虽然是多了一层循环但对比4次和对比16次相差也不大，于是就选用这种方法吧。
Licensed under CC BY-NC-SA 4.0
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK