基于像素的模式识别的数据结构
Data structure for pixel based pattern recognition
我有一个基于约束构造随机图像的应用程序。随机选择不同颜色的像素并将其放置在满足所有约束的网格中。例如（简化），可能有一个约束说明如果蓝色或绿色像素位于 (0,-1)，而红色像素位于 (-1,-1) 和 (-1, 0)，则放置禁止使用白色像素。这些坐标是来自当前放置位置（即它的邻域）的向量。
现在我将约束存储在一个数组中并循环遍历它们，检查每个约束是否适用。我必须为放置在网格中的每个像素执行此操作。因此，随着更多约束的添加，性能会受到影响。此外，两个约束可能会发生冲突，但检查起来并不容易。
我在想图形类型的数据结构（树？）可能是一种存储所有约束的方法，这样我就可以从像素邻域中快速确定哪些（如果有）约束适用。但鉴于单个坐标可以包含多种颜色，以及如何将一组 coordinate/colors 与一组禁止的像素颜色联系起来，我不太清楚如何使这种结构起作用。有什么想法吗？
对于这个问题，你可以使用不同类型的树。
这似乎是一个被广泛研究的话题，答案可能比正常的 SO 答案要长得多。参考下一个链接：
没用过模式匹配，但想到的是：
以通常的图形 ds 为例，其中顶点将是您的向量，边缘将是连接它们的禁止颜色。
在这里，您可以将所有顶点相互连接起来，更理想的方法是采用某个方向来填充 ds，当您要遍历像素数组时，您应该使用相同的起点和方向。
从您的示例中，如果您从 (0,-1) 开始顺时针方向移动，它将类似于： (0,-1) --blue-- (-1, -1), (0,-1) --green- - (-1, -1), (-1, -1) --red -- (-1, 0), (-1, 0) --red--(-1, 1), (-1, 1) --white--(0, 1), (-1, 1) --white-- (1, 1), (-1, 1) --white-- (1, 0)
现在用DFS搜索颜色检查（会是边）
在我看来，一个方便的选择是 kd 树。通过将约束存储在 kd 树中，您可以访问适用于最近邻类型查询的约束。
我建议您看一下可能适用于您的问题的 kd-tree 书Algorithms in a Nutshell. You can find an easy implementation。
但是，请记住，如果约束在您的场景中分布不均匀，则生成的树可能不平衡。在这种情况下，您应该找到更好的约束表示，否则算法的实际复杂度将更接近最差值 O(n)，而不是平均（和最佳）值 O(log n).
您可以使用图形切割来解决这个问题。它甚至会处理提到的冲突。这基本上就是它的工作原理：它尝试根据您希望最小化的成本函数分配标签。对于您的情况，成本函数可能类似于：
E(x)=infinite ; if constraint is violated
and 0 ; otherwise
Graph cut 将分配最小化此成本函数的标签。另外，它非常快速和高效并且收敛到最小值。查看以下两个参考资料：
第二个 link 提供了图形切割的现成代码，您可以在其中使用您自己的成本函数，该函数将被最小化（并且可以根据您的情况取决于邻居值）。
我有一个基于约束构造随机图像的应用程序。随机选择不同颜色的像素并将其放置在满足所有约束的网格中。例如（简化），可能有一个约束说明如果蓝色或绿色像素位于 (0,-1)，而红色像素位于 (-1,-1) 和 (-1, 0)，则放置禁止使用白色像素。这些坐标是来自当前放置位置（即它的邻域）的向量。
现在我将约束存储在一个数组中并循环遍历它们，检查每个约束是否适用。我必须为放置在网格中的每个像素执行此操作。因此，随着更多约束的添加，性能会受到影响。此外，两个约束可能会发生冲突，但检查起来并不容易。
我在想图形类型的数据结构（树？）可能是一种存储所有约束的方法，这样我就可以从像素邻域中快速确定哪些（如果有）约束适用。但鉴于单个坐标可以包含多种颜色，以及如何将一组 coordinate/colors 与一组禁止的像素颜色联系起来，我不太清楚如何使这种结构起作用。有什么想法吗？
对于这个问题，你可以使用不同类型的树。
这似乎是一个被广泛研究的话题，答案可能比正常的 SO 答案要长得多。参考下一个链接：
没用过模式匹配，但想到的是：
以通常的图形 ds 为例，其中顶点将是您的向量，边缘将是连接它们的禁止颜色。 在这里，您可以将所有顶点相互连接起来，更理想的方法是采用某个方向来填充 ds，当您要遍历像素数组时，您应该使用相同的起点和方向。 从您的示例中，如果您从 (0,-1) 开始顺时针方向移动，它将类似于： (0,-1) --blue-- (-1, -1), (0,-1) --green- - (-1, -1), (-1, -1) --red -- (-1, 0), (-1, 0) --red--(-1, 1), (-1, 1) --white--(0, 1), (-1, 1) --white-- (1, 1), (-1, 1) --white-- (1, 0)
现在用DFS搜索颜色检查（会是边）
在我看来，一个方便的选择是 kd 树。通过将约束存储在 kd 树中，您可以访问适用于最近邻类型查询的约束。
我建议您看一下可能适用于您的问题的 kd-tree 书Algorithms in a Nutshell. You can find an easy implementation。
但是，请记住，如果约束在您的场景中分布不均匀，则生成的树可能不平衡。在这种情况下，您应该找到更好的约束表示，否则算法的实际复杂度将更接近最差值 O(n)，而不是平均（和最佳）值 O(log n).
您可以使用图形切割来解决这个问题。它甚至会处理提到的冲突。这基本上就是它的工作原理：它尝试根据您希望最小化的成本函数分配标签。对于您的情况，成本函数可能类似于：
E(x)=infinite ; if constraint is violated
and 0 ; otherwise
Graph cut 将分配最小化此成本函数的标签。另外，它非常快速和高效并且收敛到最小值。查看以下两个参考资料：
第二个 link 提供了图形切割的现成代码，您可以在其中使用您自己的成本函数，该函数将被最小化（并且可以根据您的情况取决于邻居值）。