Проблемы с реализацией алгоритма «Функция коллапса волны» в Python

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

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

Что такое алгоритм Функция коллапса волны?

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

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

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

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

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

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

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

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

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

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

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

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

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

В начале все логические значения установлены на 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-х желтых лепестков)
• столкнуться со слишком большим количеством противоречивых состояний (серые ячейки, отмеченные как «ПРОДОЛЖЕНИЕ»)

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

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

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

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

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

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

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