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

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

1 голос
/ 08 октября 2019

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

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

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

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

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

1 Ответ

0 голосов
/ 13 октября 2019

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
...