通过将相似的像素分组为矩形来划分图像

Question

考虑这样的图像：

通过按颜色将像素分组到不同的矩形中，可以实现不同的配置，例如：

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

关于如何设计能够解决这个问题的有效算法有什么想法吗？

编辑：我认为最好的答案是@dshin 的答案，因为他们证明这个问题是一个 NP-HARD 问题，所以可能没有任何有效的解决方案能够保证最佳结果。其他答案提供了合理的妥协以获得可接受的解决方案，但这并不总是最佳的。

Answer 1

每个连接的彩色区域都是一个可以独立考虑的直线多边形，因此您的问题相当于解决直线多边形的最小覆盖矩形。这是一个经过充分研究的问题，在某些领域（例如VLSI）中找到了应用。

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

非凸情况是NP 困难的（参考），因此可能不存在有效的最优解。但有几种算法可以产生良好的经验结果。这份 1990 年的出版物描述了三种不同的算法，每种算法都保证最多使用最佳解决方案两倍的矩形。这篇 2016 年出版物描述了一种使用常见IP + LP 松弛技术的算法，尽管缺乏理论保证，但该算法显然在现实生活中的问题实例中产生了更好的结果。不幸的是，这两种出版物都是付费墙，我无法找到描述算法的免费资源。

如果您只是在寻找合理的东西，并且您的问题实例本质上不是病态的，那么其他答案中描述的算法可能就足够了。