图像中有多少组合k邻居像素？

Question

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

邻居是4连接的，不要缠绕。

Answer 1

一旦获得大小的像素斑点的不同形状的数量（这里是一个引用）然后它归结为两件事：

• 您的图像上有多少种方法可以放置此斑点？
• 其中有多少相同，使得您不会逐渐计数（由于对称）？

得到一个确切的答案是一个巨大的计算工作（你看起来超过10 ^ 30的k= 56的不同形状 - 想象如果k= 10,000），但你可能能够足够好，因为你需要的东西通过拟合k的前50个值。

（注意：维基百科文章中的参考文章负责重复的是它们对A_K的定义。）

Answer 2

似乎你正在努力映射到马尔科夫散步的问题。

如果我理解你的问题，你试图计算如下所示的长度k路径：

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

.

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

我认为你希望路径是自我避免的，这意味着在散步时不应该穿过像素两次（意味着没有循环）。这种条件导致称为锯（自避免行走）的经典问题。

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

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

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

Answer 3

如果你计划迭代所有可能的 polyominos ，我担心你我要等待很长时间。从关于多聚体的维基百科网站，它至少是O（4.0626 ^ n），可能更接近O（8 ^ n）。当n= 14时，计数将超过50亿超过50亿，太大而无法适合int。在时间n= 30时，计数将超过17千万，并且您将无法将其融入其中。如果所有世界各国政府汇集了他们的资源，以32 x 32图标在所有多聚体中播放，他们将无法在太阳超新星之前做到。

现在，这并不意味着你想要做的是难以解决的。几乎所有你在一个多变物上所做的所有作品都是部分地完成了其他人。它可能是一个有趣的任务，使用动态编程制作指数加速。你试图完成什么？