如何设计高效算法实现图像同色像素的最少矩形划分

首先明确问题边界：

目标是将图像中颜色一致的像素划分为互不重叠的轴对齐矩形，最终使用的矩形总数越少越好。该问题已经被证明属于NP-Hard类，不存在能在多项式时间内保证得到全局最优解的算法，所有工业界和学界实际使用的方案都是启发式折衷方案，在可接受的耗时下输出质量足够好的结果。

下图是一种可行的划分效果参考：

主流高效启发式方案 #

以下是经过实际场景验证、落地成本低的几种实现方案，按实现难度从低到高排序：

• 最大矩形贪心算法
  这是最容易上手的方案，逻辑非常直白：
  1. 维护未分配像素集合，初始状态为整张图的所有像素
  2. 每次从未分配区域中，找出面积最大的、内部所有像素颜色完全相同的轴对齐矩形
  3. 将该矩形标记为已分配，从未分配集合中移除对应像素
  4. 重复步骤2-3，直到所有像素都被分配完成
     实现时可以用单调栈算法加速最大同色矩形的查找过程，单步查找的时间复杂度和当前待处理区域的像素数线性相关，处理普通分辨率的图像速度极快。缺点是早期选择大矩形后，容易留下大量难以合并的边角碎块，最终矩形数和全局最优解的偏差通常在10%~25%区间。
• 四叉树分裂合并算法
  这是工程中最常用的平衡方案，速度快、结果稳定：
  1. 从整张图开始递归分裂：如果当前块内所有像素颜色一致就停止分裂，否则将块等分为四个子块递归处理，直到所有叶子块都是内部同色的矩形
  2. 分裂完成后做自底向上合并：遍历所有相邻的同色块，只要多个块拼接后仍然是内部全同色的轴对齐矩形，就将其合并为一个大块
  3. 最后做一轮扫描优化，遍历所有相邻块，把能合并为更大同色矩形的块继续合并，直到没有可合并的块为止
     该方案整体时间复杂度和图像总像素数线性相关，速度比纯最大矩形贪心更快，结果质量也更稳定，大多数场景下和最优解的偏差能控制在15%以内，适配绝大多数业务需求。
• 分域生长+局部迭代优化方案
  适合对矩形数量要求更高、可接受更高耗时的场景：
  1. 先按连通性把同色像素拆分为独立的同色连通域，每个连通域单独做矩形划分，避免跨连通域的无效计算
  2. 对每个连通域，从边缘像素开始做区域生长，每次优先选择能让当前矩形边界更规整、剩余区域划分难度最低的方向扩展
  3. 得到初始划分后做迭代优化：随机选取2~3个相邻矩形，把它们覆盖的像素重新做局部最优划分，如果新划分使用的矩形数更少就替换原有结果，重复迭代直到连续多轮没有优化收益为止
     该方案的结果质量更高，多数场景下和最优解的偏差可以压到10%以内，代价是耗时比前两种方案高3~10倍。

补充说明：如果是尺寸极小的图（比如边长小于16像素的图），可以用状态压缩动态规划或者整数线性规划求解全局最优解做效果对照，大尺寸图像目前没有可行的全局最优求解方法。

内容的提问来源于stack exchange，提问作者Droh Gabuh