简而言之:
我对
Wave Collapse Function
algorithm
什么是
波浪崩塌函数
它是由Maxm GuMin在2016中编写的一种算法,它可以从样本图像生成过程模式。你可以看到它在起作用
here
(二维重叠模型)和
here
(三维平铺模型)。
将算法(二维重叠模型)归结为其本质,避免了
original C# script
(出人意料的长和难读)。这是一个尝试,使一个更短,更清楚和蟒蛇版本的算法。
我在用
Processing
(Python模式),一个用于可视化设计的软件,它使图像操作更容易(没有PIL,没有Matplotlib,…)。主要缺点是我仅限于Python 2.7,无法导入numpy。
与原始版本不同,此实现:
算法
(据我所知)
读取输入位图,存储每个NxN模式并统计其发生次数。
(
可选:
使用旋转和反射来增强图案数据。)
2个/
预先计算并存储模式之间的所有可能的邻接关系。
在下面的示例中,模式207、242、182和125可以与模式246的右侧重叠
3个/
W
对于wave)。这个数组的每个元素都是一个保持状态的数组(
True
属于
False
例如,假设我们计算输入中的326个唯一模式,我们希望输出的维度为20×20(400个单元格)。然后“Wave”数组将包含400个(20x20)数组,每个数组都包含326个boolan值。
一开始,所有的布尔人都被设置为
真的
W = [[True for pattern in xrange(len(patterns))] for cell in xrange(20*20)]
4个/
H
). 这个数组的每个元素都是一个浮点数,它保存输出中相应单元格的“熵”值。
这里的熵是指
Shannon Entropy
真的
例如,要计算单元22的熵,我们看它在波中的对应指数(
W[22]
真的
H[22]
小时
真的
,对于每个单元格。
H = [entropyValue for cell in xrange(20*20)]
核心
5个/
观察:
找到单元格的索引
非零
然后,在波的相应索引处查看仍然有效的模式,并随机选择其中一个,根据模式在输入图像中出现的频率进行加权(加权选择)。
例如,如果
小时
H[22]
真的
西[22]
6个/
我们现在用最小熵将所选模式的索引分配给单元格。也就是说波中相应位置的每一个图案都被设置为
假
除了被选中的那个。
246
在里面
西[22]
真的
假
. 细胞
22
是指定的模式
.
在输出单元22中,将填充图案246的第一种颜色(左上角)。
(本例中为蓝色)
7个/
由于相邻约束,该模式选择会对波中的相邻单元产生影响。与最近折叠的单元格左右、顶部和上方的单元格相对应的布尔数组需要相应地更新。
例如,如果单元格
22个
246个
,然后
W[21]
W[23]
(右),
W[2]
(向上)和
W[42]
(向下)必须修改,以便它们只保持
真的
与模式相邻的模式
246个
.
例如,回顾步骤2的图片,我们可以看到只有模式207、242、182和125可以放置在
模式246。也就是说
西[23]
(牢房右侧
)需要保持207242 182和125模式
真的
并将数组中的所有其他模式设置为
假
. 如果这些模式不再有效(已设置为
假
由于之前的约束),则算法将面对
矛盾
八/
因为单元格已折叠(选择了一个模式,设置为
)其周围的单元格也相应地更新(将非相邻模式设置为
)所有这些细胞的熵都改变了,需要重新计算。(请记住,一个单元的熵与它在波中保持的有效模式数相关。)
H[22] = 0
,因为只有模式
246个
设置为
真的
在
西[22]
)相邻细胞的熵也降低了(与模式不相邻的模式
已设置为
).
现在,算法到达第一次迭代的末尾,将在步骤5(找到具有最小非零熵的单元格)到步骤8(更新熵)之间循环,直到所有单元格都折叠。
你需要
Processing
具有
Python mode
已安装以运行此脚本。
input image
并相应地改变第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页中所述
this
纸张和
this
文章)
这让我觉得
某物
. 要么我错误地实现了这些步骤中的一个,要么我丢失了逻辑中的一个关键元素。
此外,欢迎任何基于提供的脚本(使用或不使用处理)的回答
有用的附加资源:
这个细节
article
斯蒂芬·谢拉特的解释
paper
来自Karth&Smith。
另外,为了便于比较,我建议检查一下这个
Python implementation
注:我尽我所能使这个问题尽可能清楚(用gif和插图进行全面解释,用有用的链接和资源对代码进行完全注释),但如果出于某些原因,你决定投反对票,请留下简短的评论来解释你为什么这么做。
