3

我数学很烂，所以我无法弄清楚：图像中有多少 k 个相邻像素的组合？图像中 n * n 个总像素中的 k 个像素的组合，但限制是它们必须是相邻的，对于从 2 到 n * n 的每个 k。我需要一个程序的所有 k 值的总和，该程序必须考虑到它正在推理的集合中的许多元素。

邻居是 4 连接的，不会环绕。

4

3 回答 3

2

一旦你得到大小为 k 的一团像素的不同形状的数量（这里是一个参考），那么它归结为两件事：

  • 您可以在图像上以多少种方式放置此 blob？
  • 其中有多少是相同的，所以你不会重复计算（因为对称）？

获得准确的答案是一项巨大的计算工作（对于 k=56，您正在查看超过 10^30 个不同的形状——想象一下如果 k = 10,000），但您可以通过拟合获得足够好的结果来满足您的需要k 的前 50 个值。

（注意：wikipedia 文章中的参考资料会处理重复的 A_k 定义。）

于 2010-07-08T19:31:02.477 回答
2

您似乎正在研究一个可以映射到马尔可夫步行的问题。

如果我理解您的问题，您正在尝试计算长度为 k 的路径，如下所示：

Start          (end)-> any pixel after visiting k neighbours
*     - - - - -*
|     |
|     |
- - - -

在类似于棋盘的结构中，您只想连接垂直和水平的邻居。

我认为你希望路径是自我避免的，这意味着一个像素不应该在步行中被遍历两次（意味着没有循环）。这种情况导致了一个经典的问题，称为 SAW（自我避免步行）。

好吧，现在坏消息是：问题是开放的！还没有人解决。

你可以在这里找到一个很好的问题介绍，从第 54 页开始（或第 16 页，计数令人困惑，因为页码在文档中重复）。但整篇论文非常有趣且易于阅读。它设法在几张幻灯片中解释了马尔可夫链的数学背景、历史轶事和科学重要性。

希望这有助于......避免这个问题。

于 2010-07-08T21:46:47.157 回答
1

如果您打算遍历所有可能的polyominos，恐怕您会等待很长时间。从关于 polyominos 的维基百科网站来看，它至少会是 O(4.0626^n) 并且可能更接近 O(8^n)。到 n=14 时，计数将超过 50 亿，并且太大而无法放入 int 中。到 n=30 时，计数将超过 17 quintillion，您将无法将其放入 long 中。如果世界各国政府集中他们的资源在一个 32 x 32 的图标中迭代所有多米诺骨牌，他们将无法在太阳变成超新星之前做到这一点。

现在这并不意味着你想做的事情是棘手的。很可能您在一个 polyominal 上所做的几乎所有工作都部分地在其他人身上完成。使用动态编程实现指数级加速可能是一项有趣的任务。你想要完成什么？

于 2010-07-08T21:48:04.983 回答