将图像分割成矩形区域，通过将相似的像素分组。

Question

考虑这样一张图片：

使用颜色将像素分组为不同的矩形，可以得到不同的配置，例如：

目标是找到一个最佳的配置，即具有最小可能数量的矩形（矩形的大小并不重要）。

有没有关于如何设计能够解决此问题的高效算法的想法呢？

编辑： 我认为@dshin的答案是最好的，因为他们证明了这个问题是NP-HARD问题，因此可能没有任何有效的解决方案能够保证最优结果。其他答案提供了合理的折衷方案，但那并不总是最优的。

- Droh Gabuh

---

欢迎来到SO！你目前尝试了什么？请分享一下。另外，你是否从https://dev59.com/vW025IYBdhLWcg3wl3Am中得到任何想法？ - Jeru Luke

@JeruLuke 你好，谢谢！目前我正在使用“基于行”的方法，即使用Nx1大小的矩形，这种方法很容易实现，但在矩形数量方面并不总是最优化的... - Droh Gabuh

问题看起来很熟悉。你删除了上一个吗？如果我没记错，它被关闭了，因为是重复的 - 这可能是一个“NP”问题。如果你有一个大问题，但仍然想快速解决，那么它需要近似算法。这是计算机科学或数学/几何学的问题，编程不是这里的问题。你应该尝试在其他堆栈交换网站上提问，比如https://cs.stackexchange.com/或https://math.stackexchange.com/。 - Christoph Rackwitz

@ChristophRackwitz 对不起，这是我第一次在SO上发帖，我真的发了一个错误的问题吗？我在这里看到很多类似的问题（我也可以在这里的“相关”部分看到它们），你能告诉我为什么你认为我的问题不同（并且是错误的）吗？ - Droh Gabuh

我认为这没问题。下面有一个有趣的答案可以帮助你找到解决方案，这也是目标所在。我建议其他堆栈交换，因为专门解决你的问题的专家可能不会在这里出现。 - Christoph Rackwitz

Answer 1

每个相连的彩色区域都是一个直角多边形，可以独立考虑，因此你的问题就是解决直角多边形的最小矩形覆盖问题。这是一个经过深入研究的问题，在一些领域中有应用，比如VLSI。

对于凸直角多边形，有一种算法可以在多项式时间内找到最优解，该算法在这篇1984年论文中有描述。

非凸情况是NP-hard的（参见NP-hard reference），因此可能不存在有效的最优解。但有几种算法可以产生良好的实证结果。这篇1990年的publication描述了三种单独的算法，每种算法保证使用的矩形至多是最优解的两倍。这篇2016年的publication描述了一种使用常见IP + LP松弛技术的算法，该算法在实际问题中似乎产生更好的结果，尽管缺乏理论保证。不幸的是，这两个出版物都需要付费购买，而我没有找到免费资源来描述这些算法。

如果您只是在寻找一些合理的东西，并且您的问题实例不具有病态特性，那么其他答案中描述的算法可能已经足够好了。

- dshin

---

非常有趣的文献，我一定会深入研究，谢谢！ - Droh Gabuh

Answer 2

我没有证据，但我认为采用贪心算法应该可以解决这个问题：

1. 从左上角开始（或其他角落）
2. 向右扩展1像素，只要颜色匹配
3. 向下扩展1像素，只要该行中的所有颜色都匹配
4. 逐行和逐列查找下一个像素，该像素尚未成为正方形的一部分（也许在第二个数组中跟踪已访问的像素），然后重复步骤2和3。

你可以切换行和列，向上和向左移动，或者以其他方式结束并得到不同的配置，但是我在脑海中玩过后，我认为矩形的数量应该始终相同。

- MrJ

---

我不相信这种方法总是使用最少的矩形。考虑一个2x100的网格，其中除了右上角、右下角和左下角紧挨着右下角的单元之外，所有单元格都是白色的。最优方法使用四个矩形。而您的方法将使用比此更多的矩形。 - templatetypedef

@MrJ 是的，这是真的。但是如果我只考虑最大行宽度，然后再担心高度，你可能会遇到一个仅有Nx1行的情况，因为下一行的最后一个像素颜色不同...更好的解决方案是取一个N-1 x M的行，然后再担心那个最后一个像素。 - Droh Gabuh

@MrJ，实际上意图是减少矩形的数量，而不是让它们变得漂亮。鉴于此，我将进一步尝试您的想法，以找到证明矩形数量仍将保持最优的证据。谢谢您的提示！ - Droh Gabuh

我找到了另一个简单的例子，证明这不是最优解：想象一下一个颜色反转的“T”形状，通过从左上角开始，该算法产生了3个矩形，但最优解应该是2个。 - Droh Gabuh

我没有完全理解@ChristophRackwitz的例子，因为没有图片，但我同意反向T形确实代表了一个反例。我认为你可以改进这个算法（例如，如果右侧一列的所有像素颜色都不同，则停止向下扩展），以捕捉T形情况，但最终我同意这些都是近似解 :) - MrJ

Answer 3

这里的想法基于以下链接：链接1和链接2。

在这两种情况下，都计算了给定多边形/形状内最大可能的矩形。有关详细信息，请查看上述链接。

我们可以将上述思想扩展到手头的问题中。

步骤：

1. 按颜色（比如红色）过滤图像 2. 找到红色区域内最大可能的矩形。找到后进行遮罩处理。 3. 重复操作以找到下一个最大的矩形，直到覆盖了红色部分的所有区域。 4. 对每个唯一颜色重复以上操作。

概览：

- Jeru Luke

---

“寻找可能的最大矩形”不是一个库函数。你应该详细说明这一步，因为它是唯一的非平凡步骤。 - Christoph Rackwitz

@ChristophRackwitz 我已经提供了链接，不想重复。这里我只是想展示如何使用那个想法。 - Jeru Luke

@JeruLuke 这是一个有趣的想法，我会尝试一下。我猜我需要找到一个好的方法来找到最大的矩形，因为你提供的链接似乎比这里需要的要复杂得多（它们还考虑了不存在的对角线）。 - Droh Gabuh

@JeruLuke 在处理这个问题时，我发现这个过程并不能保证矩形数量方面的最优解。比如一个红色的“T”形，如果垂直部分比水平部分更长，那么它将被认为是最大的矩形，将水平部分对半切开... 这意味着会生成3个矩形，但最优解应该是2个。 - Droh Gabuh