Назначьте палитры плиткам изображения, чтобы они поместились в N палитр по K цветов каждая.

Пишу инструмент для работы с плиточными изображениями. Одна из функций - преобразовать все изображение в набор фрагментов и карту фрагментов, например изображение размером 160x144px будет иметь набор уникальных фрагментов 8x8 и карту идентификаторов фрагментов 20x18.

Следующая цель - поддержка палитр. На некоторых старых платформах, которые использовали мозаичную графику, у вас могло быть 8 палитр по 4 цвета каждая или 16 палитр по 16 в каждой. Я хочу автоматически создать набор палитр, который соответствует пределу N на K, используя как можно меньше палитр; и назначьте эти палитры тайловой карте или предупредите, если это невозможно.

Есть несколько очевидных первых шагов: если в какой-либо отдельной плитке используется более K цветов, это будет невозможно; и как только это будет проверено, любая плитка, цвета которой являются подмножеством другого, может тривиально поделиться своей палитрой. Сложность заключается в обработке частично перекрывающихся палитр. Рассмотрим 17 плиток, каждая из которых имеет 15 уникальных цветов; при достаточном перекрытии они могут поместиться в цветовую палитру 16x16, но это может оказаться невозможным.

Я ожидаю, что здесь сработает решение для динамического программирования. На любом этапе проблемы есть частичное присвоение плиток палитрам; и решение состоит в том, какой из N палитр назначить следующую плитку. (Плитка может даже не иметь общих цветов с оптимальным выбором палитры в то время; рассмотрите 4 плитки, каждая с 4 уникальными цветами, все они могут использовать единую 16-цветовую палитру.)

Эта конкретная проблема уже решена? Есть ли для этого известный алгоритм или просто общие советы по динамическому программированию?


color-palette graphics combinatorics dynamic-programming gameboy
person Remy    schedule 08.10.2019    source источник

Ответы (1)


arrow_upward
0
arrow_downward

SuperFamiconv может делать это для нескольких систем, включая SNES (16 палитр, 8 цветов / палитра). и GBC (8 палитр, 4 цвета / палитра). Он также с открытым исходным кодом, поэтому их алгоритм доступен.

Оказывается, динамическое программирование не является необходимым для "достаточно хорошего" решения для изображений реалистичного размера. (Не уверен, насколько хорошо это подойдет для огромных, но для моих целей это не имеет значения.)

Это перевод их алгоритма на 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
person Remy    schedule 12.10.2019