Проблемы с реализацией алгоритма "Wave Collapse Function" в Python

В двух словах:

Моя реализация алгоритма Wave Collapse Function в Python 2.7 несовершенна, но я не могу определить, где находится проблема. Мне нужна помощь, чтобы выяснить, что я могу упустить или делаю неправильно.

Что такое алгоритм Wave Collapse Function?

Это алгоритм, написанный в 2016 году Максимом Гумином, который может генерировать процедурные шаблоны из образца изображения. Вы можете увидеть это в действии здесь (2D-модель перекрытия) и здесь (3D-модель плитки).

Цель этой реализации:

Чтобы свести алгоритм (2D перекрывающаяся модель) к его сути и избежать избыточности и неуклюжести оригинального сценария С# (на удивление длинный и трудный для чтения). Это попытка сделать более короткую, ясную и питонную версию этого алгоритма.

Характеристики этой реализации:

Я использую Processing (режим Python), программное обеспечение для визуального проектирования, которое облегчает манипулирование изображениями (без PIL, без Matplotlib,...). Основными недостатками являются то, что я ограничен Python 2.7 и не могу импортировать numpy.

В отличие от оригинальной версии, эта реализация:

• не является объектно-ориентированным (в его текущем состоянии), что облегчает понимание/приближение к псевдокоду
• использует одномерные массивы вместо двухмерных
• использует нарезку массива для матричной манипуляции

Алгоритм (насколько я понимаю)

1/ Чтение входного растрового изображения, сохранение каждого NxN-паттерна и подсчет их количества. (необязательно: дополнить данные шаблона поворотами и отражениями.)

Например, когда N = 3:

2/ Предварительно вычислять и хранить все возможные отношения смежности между шаблонами. В приведенном ниже примере шаблоны 207, 242, 182 и 125 могут перекрывать правую сторону шаблона 246

3/ Создайте массив с размерами вывода (называемый W для волны). Каждый элемент этого массива является массивом, содержащим состояние (True of False) каждого шаблона.

Например, допустим, что мы подсчитали 326 уникальных шаблонов во входных данных и хотим, чтобы наш выход имел размеры 20 на 20 (400 ячеек). Тогда массив "Wave" будет содержать 400 (20x20) массивов, каждый из которых содержит 326 boolan-значений.

В начале все логические значения установлены в True потому что каждый паттерн разрешен в любой позиции Волны.

W = [[True for pattern in xrange(len(patterns))] for cell in xrange(20*20)]

4/ Создайте еще один массив с размерами вывода (называемый H). Каждый элемент этого массива представляет собой число с плавающей запятой, содержащее значение "энтропии" соответствующей ячейки в выходных данных.

Энтропия здесь относится к энтропии Шеннона и вычисляется на основе количества действительных паттернов в определенном месте в волне. Чем больше у ячейки правильных шаблонов (установлено значение True в волне), тем выше ее энтропия.

Например, чтобы вычислить энтропию ячейки 22, мы смотрим на ее соответствующий индекс в волне (W[22]) и подсчитываем число логических значений, установленных в True. С этим счетом мы можем теперь вычислить энтропию по формуле Шеннона. Результат этого вычисления будет затем сохранен в H с тем же индексом H[22]

В начале все ячейки имеют одинаковое значение энтропии (одинаковое значение с плавающей запятой в каждой позиции в H), поскольку для всех ячеек для каждой ячейки установлено значение True.

H = [entropyValue for cell in xrange(20*20)]

Эти 4 шага являются вводными шагами, они необходимы для инициализации алгоритма. Теперь запускается ядро алгоритма:

5/ Наблюдение:

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

Затем посмотрите на все еще действующие паттерны в соответствующем индексе в волне и выберите один из них случайным образом, взвешенный по частоте, с которой паттерн появляется во входном изображении (взвешенный выбор).

Например, если наименьшее значение в H индексу 22 (H[22]), мы смотрим на все паттерны, установленные на True в W[22] и выбираем один случайным образом в зависимости от того, сколько раз он появляется на входе. (Помните, что на шаге 1 мы подсчитали количество случаев для каждого шаблона). Это гарантирует, что шаблоны появляются с таким же распределением в выходных данных, как и во входных данных.

6/ Свернуть:

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

Например, если для шаблона 246 в W[22] задано значение " True и выбрано, то для всех остальных образцов задано значение " False. Ячейке 22 назначен шаблон 246. В выходной ячейке 22 будет заполнен первый цвет (верхний левый угол) шаблона 246. (синий в этом примере)

7/ Распространение:

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

Например, если ячейка 22 свернута и ей присвоен шаблон 246, то W[21] (слева), W[23] (справа), W[2] (вверх) и W[42] (вниз) должны быть изменены. так что они сохраняют в True те шаблоны, которые соседствуют с шаблоном 246.

Например, оглядываясь на изображение шага 2, мы видим, что только шаблоны 207, 242, 182 и 125 могут быть размещены справа от шаблона 246. Это означает, что W[23] (справа от ячейки 22) необходимо оставьте шаблоны 207, 242, 182 и 125 True и установите все остальные шаблоны в массиве как False. Если эти шаблоны больше не действительны (уже установлены в False из-за предыдущего ограничения), тогда алгоритм сталкивается с противоречием.

8/ Обновление энтропий

Поскольку ячейка была свернута (один выбранный шаблон, установлен на True) и соответствующие окружающие ячейки обновлены соответствующим образом (для несмежных шаблонов установлено значение False), энтропия всех этих ячеек изменилась, и ее необходимо вычислять заново. (Помните, что энтропия ячейки соотносится с количеством действительных паттернов, которые она содержит в волне.)

В этом примере энтропия ячейки 22 теперь равна 0 (H[22] = 0, потому что только значение 246 установлено True при W[22]), а энтропия соседних ячеек уменьшилась (структуры, которые не были соседними для шаблона 246 было установлено значение False).

К настоящему времени алгоритм прибывает в конце первой итерации и будет повторять шаги 5 (найти ячейку с минимальной ненулевой энтропией) до 8 (обновить энтропии), пока все ячейки не будут свернуты.

Мой сценарий

Вам потребуется обработка с режимом Python установлен для запуска этого сценария. Он содержит около 80 строк кода (короткий по сравнению с ~ 1000 строк исходного скрипта), которые полностью аннотированы, чтобы его можно было быстро понять. Вам также необходимо загрузить входное изображение и изменить путь в строке 16 соответственно.

from collections import Counter
from itertools import chain, izip
import math

d = 20  # dimensions of output (array of dxd cells)
N = 3 # dimensions of a pattern (NxN matrix)

Output = [120 for i in xrange(d*d)] # array holding the color value for each cell in the output (at start each cell is grey = 120)

def setup():
    size(800, 800, P2D)
    textSize(11)

    global W, H, A, freqs, patterns, directions, xs, ys, npat

    img = loadImage('Flowers.png') # path to the input image
    iw, ih = img.width, img.height # dimensions of input image
    xs, ys = width//d, height//d # dimensions of cells (squares) in output
    kernel = [[i + n*iw for i in xrange(N)] for n in xrange(N)] # NxN matrix to read every patterns contained in input image
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # (x, y) tuples to access the 4 neighboring cells of a collapsed cell
    all = [] # array list to store all the patterns found in input



    # Stores the different patterns found in input
    for y in xrange(ih):
        for x in xrange(iw):

            ''' The one-liner below (cmat) creates a NxN matrix with (x, y) being its top left corner.
                This matrix will wrap around the edges of the input image.
                The whole snippet reads every NxN part of the input image and store the associated colors.
                Each NxN part is called a 'pattern' (of colors). Each pattern can be rotated or flipped (not mandatory). '''


            cmat = [[img.pixels[((x+n)%iw)+(((a[0]+iw*y)/iw)%ih)*iw] for n in a] for a in kernel]

            # Storing rotated patterns (90°, 180°, 270°, 360°) 
            for r in xrange(4):
                cmat = zip(*cmat[::-1]) # +90° rotation
                all.append(cmat) 

            # Storing reflected patterns (vertical/horizontal flip)
            all.append(cmat[::-1])
            all.append([a[::-1] for a in cmat])




    # Flatten pattern matrices + count occurences 

    ''' Once every pattern has been stored,
        - we flatten them (convert to 1D) for convenience
        - count the number of occurences for each one of them (one pattern can be found multiple times in input)
        - select unique patterns only
        - store them from less common to most common (needed for weighted choice)'''

    all = [tuple(chain.from_iterable(p)) for p in all] # flattern pattern matrices (NxN --> [])
    c = Counter(all)
    freqs = sorted(c.values()) # number of occurences for each unique pattern, in sorted order
    npat = len(freqs) # number of unique patterns
    total = sum(freqs) # sum of frequencies of unique patterns
    patterns = [p[0] for p in c.most_common()[:-npat-1:-1]] # list of unique patterns sorted from less common to most common



    # Computes entropy

    ''' The entropy of a cell is correlated to the number of possible patterns that cell holds.
        The more a cell has valid patterns (set to 'True'), the higher its entropy is.
        At start, every pattern is set to 'True' for each cell. So each cell holds the same high entropy value'''

    ent = math.log(total) - sum(map(lambda x: x * math.log(x), freqs)) / total



    # Initializes the 'wave' (W), entropy (H) and adjacencies (A) array lists

    W = [[True for _ in xrange(npat)] for i in xrange(d*d)] # every pattern is set to 'True' at start, for each cell
    H = [ent for i in xrange(d*d)] # same entropy for each cell at start (every pattern is valid)
    A = [[set() for dir in xrange(len(directions))] for i in xrange(npat)] #see below for explanation




    # Compute patterns compatibilities (check if some patterns are adjacent, if so -> store them based on their location)

    ''' EXAMPLE:
    If pattern index 42 can placed to the right of pattern index 120,
    we will store this adjacency rule as follow:

                     A[120][1].add(42)

    Here '1' stands for 'right' or 'East'/'E'

    0 = left or West/W
    1 = right or East/E
    2 = up or North/N
    3 = down or South/S '''

    # Comparing patterns to each other
    for i1 in xrange(npat):
        for i2 in xrange(npat):
            for dir in (0, 2):
                if compatible(patterns[i1], patterns[i2], dir):
                    A[i1][dir].add(i2)
                    A[i2][dir+1].add(i1)


def compatible(p1, p2, dir):

    '''NOTE: 
    what is refered as 'columns' and 'rows' here below is not really columns and rows 
    since we are dealing with 1D patterns. Remember here N = 3'''

    # If the first two columns of pattern 1 == the last two columns of pattern 2 
    # --> pattern 2 can be placed to the left (0) of pattern 1
    if dir == 0:
        return [n for i, n in enumerate(p1) if i%N!=2] == [n for i, n in enumerate(p2) if i%N!=0]

    # If the first two rows of pattern 1 == the last two rows of pattern 2
    # --> pattern 2 can be placed on top (2) of pattern 1
    if dir == 2:
        return p1[:6] == p2[-6:]



def draw():    # Equivalent of a 'while' loop in Processing (all the code below will be looped over and over until all cells are collapsed)
    global H, W, grid

    ### OBSERVATION
    # Find cell with minimum non-zero entropy (not collapsed yet)

    '''Randomly select 1 cell at the first iteration (when all entropies are equal), 
       otherwise select cell with minimum non-zero entropy'''

    emin = int(random(d*d)) if frameCount <= 1 else H.index(min(H)) 



    # Stoping mechanism

    ''' When 'H' array is full of 'collapsed' cells --> stop iteration '''

    if H[emin] == 'CONT' or H[emin] == 'collapsed': 
        print 'stopped'
        noLoop()
        return



    ### COLLAPSE
    # Weighted choice of a pattern

    ''' Among the patterns available in the selected cell (the one with min entropy), 
        select one pattern randomly, weighted by the frequency that pattern appears in the input image.
        With Python 2.7 no possibility to use random.choice(x, weight) so we have to hard code the weighted choice '''

    lfreqs = [b * freqs[i] for i, b in enumerate(W[emin])] # frequencies of the patterns available in the selected cell
    weights = [float(f) / sum(lfreqs) for f in lfreqs] # normalizing these frequencies
    cumsum = [sum(weights[:i]) for i in xrange(1, len(weights)+1)] # cumulative sums of normalized frequencies
    r = random(1)
    idP = sum([cs < r for cs in cumsum])  # index of selected pattern 

    # Set all patterns to False except for the one that has been chosen   
    W[emin] = [0 if i != idP else 1 for i, b in enumerate(W[emin])]

    # Marking selected cell as 'collapsed' in H (array of entropies)
    H[emin] = 'collapsed' 

    # Storing first color (top left corner) of the selected pattern at the location of the collapsed cell
    Output[emin] = patterns[idP][0]



    ### PROPAGATION
    # For each neighbor (left, right, up, down) of the recently collapsed cell
    for dir, t in enumerate(directions):
        x = (emin%d + t[0])%d
        y = (emin/d + t[1])%d
        idN = x + y * d #index of neighbor

        # If that neighbor hasn't been collapsed yet
        if H[idN] != 'collapsed': 

            # Check indices of all available patterns in that neighboring cell
            available = [i for i, b in enumerate(W[idN]) if b]

            # Among these indices, select indices of patterns that can be adjacent to the collapsed cell at this location
            intersection = A[idP][dir] & set(available) 

            # If the neighboring cell contains indices of patterns that can be adjacent to the collapsed cell
            if intersection:

                # Remove indices of all other patterns that cannot be adjacent to the collapsed cell
                W[idN] = [True if i in list(intersection) else False for i in xrange(npat)]


                ### Update entropy of that neighboring cell accordingly (less patterns = lower entropy)

                # If only 1 pattern available left, no need to compute entropy because entropy is necessarily 0
                if len(intersection) == 1: 
                    H[idN] = '0' # Putting a str at this location in 'H' (array of entropies) so that it doesn't return 0 (float) when looking for minimum entropy (min(H)) at next iteration


                # If more than 1 pattern available left --> compute/update entropy + add noise (to prevent cells to share the same minimum entropy value)
                else:
                    lfreqs = [b * f for b, f in izip(W[idN], freqs) if b] 
                    ent = math.log(sum(lfreqs)) - sum(map(lambda x: x * math.log(x), lfreqs)) / sum(lfreqs)
                    H[idN] = ent + random(.001)


            # If no index of adjacent pattern in the list of pattern indices of the neighboring cell
            # --> mark cell as a 'contradiction'
            else:
                H[idN] = 'CONT'



    # Draw output

    ''' dxd grid of cells (squares) filled with their corresponding color.      
        That color is the first (top-left) color of the pattern assigned to that cell '''

    for i, c in enumerate(Output):
        x, y = i%d, i/d
        fill(c)
        rect(x * xs, y * ys, xs, ys)

        # Displaying corresponding entropy value
        fill(0)
        text(H[i], x * xs + xs/2 - 12, y * ys + ys/2)

проблема

Несмотря на все мои усилия по тщательному включению в код всех шагов, описанных выше, эта реализация дает очень странные и неутешительные результаты:

Пример вывода 20x20

Кажется, что соблюдаются как распределение шаблона, так и ограничения смежности (такое же количество синего, зеленого, желтого и коричневого цветов, как на входе, и такие же типы шаблонов: горизонтальное основание, зеленые стебли).

Однако эти модели:

• часто отключаются
• часто бывают неполными (отсутствие "голов", состоящих из 4-х желтых лепестков)
• слишком много противоречивых состояний (серые клетки, помеченные как "CONT")

В связи с этим последним моментом я должен пояснить, что противоречивые состояния являются нормальными, но должны происходить очень редко (как указано в середине страницы 6 этой статьи и в этой статье)

Часы отладки убедили меня, что вводные шаги (от 1 до 5) верны (подсчет и сохранение шаблонов, вычисления смежности и энтропии, инициализация массивов). Это привело меня к мысли, что что-то не так с основной частью алгоритма (шаги с 6 по 8). Либо я выполняю один из этих шагов неправильно, либо мне не хватает ключевого элемента логики.

Таким образом, любая помощь в этом вопросе будет очень цениться!

Также приветствуется любой ответ, основанный на предоставленном сценарии (с использованием Обработки или нет).

Полезные дополнительные ресурсы:

Это подробная статья от Стивена Шерратта и пояснительная статья от Karth & Smith. Кроме того, для сравнения я бы предложил проверить эту другую реализацию Python (содержит механизм обратного отслеживания, который не является обязательным).

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