python教程—实现“波塌缩函数”的问题算法在Python中-Python实用宝典

python教程—实现“波塌缩函数”的问题算法在Python中

简而言之:我在Python 2.7中实现的Wave Collapse Function算法有缺陷,但我无法确定问题在哪里。我需要帮助来发现我可能遗漏了什么或做错了什么。

<强>简而言之:< /强>

我在Python 2.7中实现的Wave Collapse Function算法有缺陷,但我无法确定问题在哪里。我需要帮助来发现我可能遗漏了什么或做错了什么。

什么是波塌缩函数算法?

它是Maxim Gumin在2016年编写的一个算法,可以从一个样本图像生成过程模式。您可以在操作中看到 (2D重叠模型)和 (3D tile model)。

<强>实现目标:

算法(2D重叠模型)归结为其本质,并避免原始c#脚本(出奇地长且难以阅读)的重复和笨拙。这是一个尝试,使该算法更短,更清晰和python版本。

<强>特性此实现:

我使用的是Processing (Python模式),这是一个视觉设计软件,可以使图像处理更容易(没有PIL,没有Matplotlib,…)主要缺点是我只能使用Python 2.7,不能导入numpy。

与原始版本不同,这个实现:

  • 是否面向对象(在当前状态下),使其更容易理解/更接近伪代码
  • 使用一维数组而不是二维数组吗
  • 是否使用数组切片进行矩阵操作

算法(据我所知)

读取输入位图,存储每个NxN模式并计算它们的发生次数。
(可选:通过旋转和反射增强模式数据。)

例如,当N = 3时:

实现“波塌缩函数”的问题算法在Python中 < / >

2/ /强>预计算和存储模式之间的每一个可能的邻接关系。
在下面的示例中,模式207、242、182和125可以与模式246的右侧重叠

实现“波塌缩函数”的问题算法在Python中 < / >

例如,假设我们在输入中计算了326个惟一的模式,并且希望输出的维数为20×20(400个单元格)。然后“Wave”数组将包含400个(20x20)数组,每个数组包含326个boolan值。

一开始,所有布尔值都设置为True,因为波的任何位置都允许使用任何模式。

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

创建另一个具有输出维数的数组(称为H),该数组的每个元素都是一个浮点数,在输出中持有其对应单元格的“熵”值。

这里的熵指的是Shannon Entropy,是根据波中特定位置有效模式的数量计算出来的。一个细胞的有效模式越多(在波中设置为True),它的熵就越大。

例如,为了计算细胞22的熵,我们观察它在波中的对应指数(W[22]),并计算布尔值为True的数目。这样我们就可以用香农公式计算熵了。然后,该计算的结果将存储在H中相同的索引H[22]

开始时,所有的单元格都具有相同的熵值(H中每个位置的浮点数相同),因为每个单元格的所有模式都设置为True。

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

这四个步骤是介绍性的步骤,它们是激活算法所必需的。现在启动算法core > /strong>:

<强> 5 / < /强>观察:

找到具有<强>最小值 <强>非零熵的单元格的指标(注意在第一次迭代时所有的熵都是相等的,所以我们需要随机选取单元格的指标)。

然后,查看对应的波形索引中仍然有效的模式,并随机选择其中一个模式,根据该模式在输入图像中出现的频率进行加权(加权选择)。

例如,如果H中的最小值在索引22处(H[22]),我们查看在W[22]处设置为True的所有模式,并根据它在输入中出现的次数随机选择一个模式。(记住,在第1步中,我们已经计算了每种模式的出现次数)。这确保模式在输出中出现的分布与在输入中出现的分布类似。

<强> 6 / < /强>崩溃:

现在,我们将所选模式的索引分配给具有最小熵的单元格。这意味着,除了已经选择的模式外,波中相应位置的每个模式都被设置为False。

例如,如果W[22]中的模式246被设置为True并已被选中,那么所有其他模式都被设置为False。单元格22被指定为模式246。
< output cell 22中的strong>将填充模式246的第一种颜色(左上角)。(本例中为蓝色)

<强> 7 / < / >强传播:

由于邻接限制,这种模式选择对波中的相邻单元格有影响。需要相应地更新与左右单元格对应的布尔数组,以及最近折叠的单元格的顶部和上方。

例如,如果单元格22已折叠并分配给模式246,则必须修改W[21](左)、W[23](右)、W[2](上)和W[42](下),以便它们只保留与模式246相邻的模式为真。

例如,回顾步骤2的图片,我们可以看到只有207、242、182和125模式可以放在模式246的right上。这意味着W[23](单元格22的右边)需要保持模式207、242、182和125为真,并将数组中的所有其他模式设置为假。如果这些模式不再有效(由于之前的约束已经设置为False),那么算法将面临矛盾性

<强> 8 / < /强>更新熵

因为一个单元格已经折叠(选择了一个模式,并将其设置为True),而它周围的单元格也相应地更新(将非相邻的模式设置为False),所以所有这些单元格的熵都发生了变化,需要重新计算。(记住,细胞的熵与它在波中的有效模式的数量有关。)

在本例中,22单元的熵现在为0,(H[22] = 0,因为在W[22]处只有模式246被设置为True),其相邻单元的熵已经减小(不与模式246相邻的模式被设置为False)。

到目前为止,该算法到达第一次迭代的末尾,并将循环第5步(找到熵最小不为零的单元)到第8步(更新熵),直到所有单元崩溃。

<强> < /强>我的脚本

您将需要Processing,并安装Python模式来运行此脚本。
它包含大约80行代码(与原始脚本的大约1000行代码相比比较短),这些代码都经过了完整的注释,因此可以快速理解。您还需要下载输入图像,并相应地在第16行更改路径。

< /强> < >强问题

尽管我努力将上面描述的所有步骤都小心地放入代码中,但是这个实现返回的结果非常奇怪和令人失望:

一个20x20输出的例子

实现“波塌缩函数”的问题算法在Python中 < / >

模式分布和邻接约束似乎都遵守(与输入相同数量的蓝色、绿色、黄色和棕色,以及相同的模式:水平地面、绿色茎)。

然而这些模式:

  • 经常断开连接
  • 通常是不完整的(缺少由4片黄色花瓣组成的“头”)
  • 遇到太多的矛盾状态(标记为“CONT”的灰色单元格)

关于最后一点,我应该澄清,矛盾状态是正常的,但是应该很少发生(正如论文和这篇文章)

经过数小时的调试,我确信介绍性步骤(1到5)是正确的(计算和存储模式、邻接和熵计算、数组初始化)。这让我想到,一定是算法的核心部分(步骤6到8)出了问题。要么我不正确地实现了其中一个步骤,要么我丢失了逻辑的一个关键元素。

因此,任何有关此事的帮助将不胜感激!

同样,任何基于提供的脚本的答案(不管是否使用Processing)都是受欢迎的

<强>有用additionnal资源:< /强>

这篇详细的文章 from Stephen Sherratt and This解释性论文 from Karth &史密斯。
另外,为了进行比较,我建议检查另一个Python实现(包含一个非强制的回溯机制)。

注意:我尽我所能让这个问题尽可能清晰(综合解释与gif和插图,充分注释的代码与有用的链接和资源)但是,如果由于某种原因你决定投反对票,请留下你一个简短的评论来解释你为什么这样做。

回答

@mbrig和@Leon提出的繁殖步骤遍历整个细胞堆栈(而不是局限于一组4个直接邻居)的假设是正确的。下面是一个尝试提供进一步的细节,同时回答我自己的问题

该问题发生在第7步,同时传播。原始算法确实更新了一个特定单元的4个直接邻居,但是:

  • 该特定单元格的索引被之前更新的邻居的索引替换。
  • 这个级联过程在每次单元格折叠时触发
  • 最后一个<强>,只要特定细胞的相邻模式在其相邻的1个细胞中可用

换句话说,正如评论中提到的,这是一种递归传播类型,它不仅更新折叠单元格的邻居,而且更新邻居的邻居……只要邻接是可能的。

<强>详细算法< /强>

一旦单元格折叠,它的索引就被放入堆栈中。该堆栈稍后意味着临时存储相邻单元格的索引

只要堆栈中充满索引,传播就会持续:

我们要做的第一件事是pop()堆栈中包含的最后一个索引(目前唯一的索引),并获取它的4个相邻单元格(E, W, N, S)的索引。

在继续之前,我们要确保相邻的单元格还没有折叠(我们不想更新只有一个模式可用的单元格):

然后我们检查所有可以被放置在该位置的模式。例如:如果相邻的单元格位于当前单元格的左边(east side),我们将查看当前单元格中包含的每个模式的左边可以放置的所有模式。

我们还研究了 available在相邻细胞中的模式:

Now we make sure that the neighboring cell really have to be updated. If all its available patterns are already in the list of all the possible patterns —> there’s no need to update it (the algorithm skip this neighbor and goes on to the next) :

However, if it is not a subset of the possible list —> we look at the intersection of the two sets (all the patterns that can be placed at that location and that, "luckily", are available at that same location):

如果它们不相交(模式本可以放在那里,但不可用),这意味着我们遇到了一个“矛盾”。我们必须停止整个WFC算法

相反,如果它们相交——>,我们用改进的模式索引列表更新相邻的单元格:

因为那个相邻的细胞已经更新,所以它的熵也必须更新:

最后,也是最重要的,我们将那个相邻单元格的索引添加到堆栈中,这样它就变成了下一个current单元格(它的邻居将在下一个while循环中更新):

< /强> <强>全部更新脚本

实现“波塌缩函数”的问题算法在Python中 < / >

<强>整体改进< /强>

除了这些修复之外,我还进行了一些较小的代码优化,以加快观察和传播步骤,并缩短加权选择计算。

  • “Wave”现在由Python set 组成,其索引的大小随着单元格的“折叠”而减小(替换了大型固定大小的布尔值列表)。

  • 熵存储在defaultdict中,其键值被逐步删除。

  • 初始熵值被一个随机整数所代替(由于初始时等概率高的不确定性,不需要进行第一次熵计算)

  • 单元格重放一次(避免将它们存储在数组中,并在每一帧重画)

  • 加权选择现在是一行代码(避免了一些不必要的列表理解行)

​Python实用宝典 (pythondict.com)
不只是一个宝典
欢迎关注公众号:Python实用宝典

本文由 Python实用宝典 作者:Python实用宝典 发表,其版权均为 Python实用宝典 所有,文章内容系作者个人观点,不代表 Python实用宝典 对观点赞同或支持。如需转载,请注明文章来源。
1

发表评论