Проблемы, связанные с реализацией функции Wave Collapse & rdquo; алгоритм в Python

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

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

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

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

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

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

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

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

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

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

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

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

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

enter image description here [1170]

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

enter image description here

[1193]

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

enter image description here

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

Однако эти схемы:

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

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

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

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

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

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

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

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

49
задан solub 22 July 2019 в 13:07
поделиться