将调色板分配给图像的图块以适应 N 个调色板，每个调色板包含 K 种颜色

Question

我正在编写一个用于处理平铺图像的工具。一个功能是将整个图像转换为 tileset 和 tilemap，例如一张 160x144 像素的图像将包含一组独特的 8x8 图块和一张 20x18 的图块 ID 地图。

下一个目标是支持调色板。在一些使用平铺图形的较旧平台上，您可能有 8 个调色板，每个调色板有 4 种颜色，或者有 16 个调色板，每个调色板有 16 种颜色。我想自动创建一组适合 N×K 限制的调色板，使用尽可能少的调色板；并将这些调色板分配给 tilemap，如果不可能则发出警报。

有一些明显的第一步：如果任何单个图块使用超过 K 种颜色，则不可能；一旦被选中，任何其颜色是另一个子集的图块都可以轻松共享其调色板。困难在于处理部分重叠的调色板。考虑 17 块瓷砖，每块瓷砖有 15 种独特的颜色；如果有足够的重叠，它们可以适合 16x16 调色板，但这可能是不可能的。

我希望动态规划解决方案能在这里发挥作用。在问题的任何阶段，都会将瓷砖部分分配给调色板；并且决定将下一个图块分配给 N 个调色板中的哪一个。（瓷砖可能甚至没有任何与当时最佳调色板选择相同的颜色；考虑 4 个瓷砖，每个瓷砖有 4 种独特的颜色，它们都可以使用一个 16 色调色板。）

这个问题已经解决了吗？是否有已知的算法，或者只是所有动态规划的一般技巧？

Answer 1

SuperFamiconv 能够为一些系统执行此操作，包括 SNES（16 个调色板，8 colors/palette）和 GBC（8 个调色板，4 colors/palette）。它也是开源的，所以他们的算法是可用的。

事实证明，对于给定真实大小的图像的 "good enough" 解决方案，动态规划不是必需的。（不确定它对大的效果如何，但这对我的目的来说并不重要。）

这是他们算法的翻译 Python:

def optimize_palettes(tilepals, N, K):
    """
    Return an optimized palette set for the given tile set.
    tilepals -- A list of sets of unique colors used for each tile of the image
    N -- The maximum number of palettes for one image
    K -- The maximum number of colors for one tile palette
    """
    # Check that each tilepal fits within the color limit
    if any(len(s) > K for s in tilepals):
        raise OverflowError, "A tile has more than %d unique colors" % K
    # Remove duplicate tilepals
    sets = []
    for s in tilepals:
        if s not in sets:
            sets.append(s)
    # Remove tilepals that are proper subsets of other tilepals
    sets = [s for s in sets if not any(c != s and s.issubset(c) for c in sets)]
    # Sort tilepals from most to fewest colors
    sets.sort(key=len, reverse=True)
    # Combine tilepals as long as they fit within the color limit
    opt = []
    for s in sets:
        for cs in opt:
            if len(s | cs) <= K:
                cs.update(s)
                break
        else:
            opt.append(s)
    # Sort tilepals from most to fewest colors
    opt.sort(key=len, reverse=True)
    # Check that the palettes fit within the palette limit
    if len(opt) > N:
        raise OverflowError, "There are more than %d palettes" % N
    return opt

将调色板分配给图像的图块以适应 N 个调色板，每个调色板包含 K 种颜色

Assign palettes to tiles of an image to fit within N palettes of K colors each

graphics

dynamic-programming

combinatorics

color-palette

gameboy