基于像素的模式识别的数据结构

Question

我有一个应用程序,根据约束构造随机图像.随机选择不同颜色的像素并将其放置在满足所有约束的网格中.例如(简化),可能存在一个约束,表示蓝色或绿色像素是(0,-1),红色像素是(-1,-1)和(-1,0),然后放置禁止使用白色像素.这些坐标是来自当前放置位置(即其邻域)的矢量.

现在我将约束存储在一个数组中并循环遍历它们,检查每个约束是否适用.我必须为我放置在网格中的每个像素执行此操作.因此,随着更多约束的增加,性能会受到影响.此外,两个约束可能存在冲突,但要检查它并不容易.

我认为图形类型数据结构(树？)可能是存储所有约束的一种方式,这样我就可以从像素邻域快速确定哪些(如果有的话)约束适用.但是我不知道如何使这样的结构起作用,因为单个坐标可以包含多种颜色,以及如何将一组坐标/颜色与一组禁止的像素颜色联系起来.有任何想法吗？

Answer 1

您可以使用图割来解决这个问题。它甚至会处理提到的冲突。它基本上是这样工作的：它尝试根据您希望最小化的成本函数来分配标签。对于您的情况，成本函数可能类似于：

E(x)=infinite ; if constraint is violated
and  0        ; otherwise

图割将分配最小化此成本函数的标签。另外，它非常快速、高效，并且收敛到最小值。看看下面两个参考资料：

1. 能量最小化的图割
2. 实现图割的代码

第二个链接提供了用于图形切割的现成代码，您可以在其中使用自己的成本函数，该函数将被最小化（并且可以取决于您的情况下的邻居值）。