如何重新排列图像像素以使颜色变化平滑？

Question

我有一个 RGB 颜色的 2D 数组，所以基本上是一个 3D 形状数组 (Nrow x Ncol x 3)。最初，该阵列实际上是随机的，颜色全部混合在一起。我正在尝试重新排列颜色，以便它们从一种颜色平滑地变化到另一种颜色，尽管我不关心某些颜色在哪里。基本上，我希望右侧图像的颜色尽可能“平滑”。但我不确定最有效的方法......

目前，我随机选择 2 个单元格，切换它们，并比较初始数组和结果数组的“颜色平滑度”。如果新数组比原始数组“更平滑”，则保留更改。如果不是，则恢复更改。我的“颜色平滑度”指标大致如下：对于每个 RGB 通道，取水平和垂直方向像素之间的差异并将这些差异相加。像素之间的巨大差异表明不同的颜色彼此相邻。图中的数字是“平滑度”的值。

这对于小尺寸来说效果还不错（<100) number of pixels, but still requires many thousands of iterations and still isn't perfect. For example, in the attached image the new array (on the right) 确实看起来更平滑，但我觉得还可以更好。有很多黄色和红色像素可以彼此更接近。

那么有什么方法可以找到这个问题的严格理想解呢？是排序问题吗？某种离散优化问题？还有别的事吗？我正在使用 Python 工作，任何帮助将不胜感激。谢谢！

Answer 1

我们首先定义一个

smoothness

的概念。在这里，我将其定义为图像中每个像素的一些

score

的平均值，其中我将分数定义为该像素的 R、G 和 B 值与其每个像素的平方差之和的平均值。 （最多）八个相邻像素。显然，

smoothness

和

score

都可以适应。

天真地解决这个问题（即通过强力搜索）显然是一种无望的努力，因为对于高度

h

和宽度

w

的图像，存在

(h*w)!

排列。因此，某种在每一步都会增加平滑度（或者至少不会降低平滑度）的贪婪算法似乎是可行的方法。

本质上，我探索了两种技术，其中一种与您已经使用的相同（即对于多个步骤，选择两个随机像素并交换它们（如果交换提高了平滑度），请参阅

smoothen_randomly

，它使用

greedy_swap 

），另一个是一种预处理步骤，即对像素进行排序。

函数

preorder

对每一行进行排序，使其像素的

R

值排序，然后对每一列进行排序，使其像素的

G

值排序，然后对每条对角线进行排序，使其

B

值排序，可指定

n

次。我的想法是，这将使主要平滑算法不太容易对相似像素有多个（而不是只有一个）簇，即允许它更快地收敛。

为了演示，我对 20 x 20 像素的随机 RGB 图像进行了采样，然后针对一系列预排序步骤（0、1、2 和 5）和一系列交换步骤（0、500、5000 和 50000）中的每个组合进行采样绘制了结果图像。 IE。原图在左上角，第一行显示仅应用预排序且不进行随机交换的效果，第一列显示仅应用随机交换而不进行预排序的效果。每张图像顶部的数字对应于其平滑度（或者更确切地说，其“不平滑度”，即分数越低越好）。

import numpy as np
import matplotlib.pyplot as plt
from numpy.random import randint


def random_img(lb, ub):
    """ generates a random RGB image """
    h = randint(lb, ub)
    w = randint(lb, ub)
    img = randint(low=0, high=255, size=(h, w, 3))
    return img


def score(img, ij, p):
    """ mean squared distance of a pixel to its neighboring pixels """
    i, j = ij
    h, w = img.shape[:2]
    s = []
    for x in (-1, 0, 1):
        for y in (-1, 0, 1):
            if (x, y) != (0, 0) and 0 <= i + x < h and 0 <= j + y < w:
                s.append(np.power(p - img[i+x][j+y], 2).sum())
    return np.mean(s)


def smoothness(img):
    """ mean score across all pixels """
    h, w = img.shape[:2]
    scores = []
    for i in range(h):
        for j in range(w):
            scores.append(score(img, (i, j), img[i, j]))
    return int(np.sqrt(np.mean(scores)))


def preorder(img, n):
    """ order R values along the vertical, G values along the horizontal and B values along the diagonal """
    img2 = np.copy(img)
    h, w = img.shape[:2]
    for k in range(n):
        img2 = np.array([sorted(arr, key=lambda x: x[0]) for arr in img2])
        img2 = np.array([sorted(arr, key=lambda x: x[1]) for arr in img2.T]).T
        a = [(i, 0) for i in range(h-1, -1, -1)]
        b = [(0, j) for j in range(1, w, 1)]
        for (i, j) in a + b:
            rng = range(min(h-i, w-j))
            arr = [np.copy(img2[i + x, j + x]) for x in rng]
            for rgb, ofs in zip(sorted(arr, key=lambda x: x[2]), rng):
                img2[i+ofs, j+ofs] = rgb
    return img2


def greedy_swap(img, ij1, ij2):
    """ swap two pixels iff the swap increases the smoothness """
    i1, j1 = ij1
    i2, j2 = ij2
    a = img[i1][j1].copy()
    b = img[i2][j2].copy()
    s1 = score(img, ij1, a)
    s2 = score(img, ij2, b)
    s1_2 = score(img, ij1, b)
    s2_2 = score(img, ij2, a)
    if s1_2 + s2_2 < s1 + s2:
        img[i1, j1] = b
        img[i2, j2] = a


def smoothen_randomly(img, n):
    """ swap two random pixels if swap improves score, for n steps """
    img2 = np.copy(img)
    h, w = img.shape[:2]
    for k in range(n):
        i1 = randint(low=0, high=h)
        j1 = randint(low=0, high=w)
        i2 = randint(low=0, high=h)
        j2 = randint(low=0, high=w)
        greedy_swap(img2, (i1, j1), (i2, j2))
    return img2


img = random_img(20, 21)
n_preorders = [0, 1, 2, 4]
n_swaps = [0, 500, 5000, 50000]

figure, axes = plt.subplots(len(n_swaps), len(n_preorders), figsize=(10, 10))
for ax, x in zip(axes[:,0], n_swaps):
    ax.set_ylabel(f'{x}', fontsize=12)
for i, x1 in enumerate(n_preorders):
    for j, x2 in enumerate(n_swaps):
        img2 = smoothen_randomly(preorder(img, x1), x2)
        axes[j, i].imshow(img2)
        axes[j, i].set_xticks([])
        axes[j, i].set_yticks([])
        prefix = f'{x1}\n' if j == 0 else ''
        axes[j, i].set_title(prefix + f'{smoothness(img2)}')
plt.show()

有许多途径可以进一步探索，从而提高性能，例如

• 使用分数函数（例如，如果使用非平方差会怎样）
• 在考虑交换时研究像素选择方法（例如确定性而不是随机）
• 考虑不同的方法，例如聚类（我预计将像素簇映射到二维网格上会有些困难）。