寻找图像中最少的矩形数量

Question

我有一些二进制图像，其中矩形随机放置在图像中，我想要获取这些矩形的位置和大小。如果可能的话，我希望使用最少的矩形数目来完全重建该图像。 左侧是我的原始图像，右侧是应用scipys.find_objects()后获得的图像（如this question所建议的）。

import scipy

# image = scipy.ndimage.zoom(image, 9, order=0)
labels, n = scipy.ndimage.measurements.label(image, np.ones((3, 3)))
bboxes = scipy.ndimage.measurements.find_objects(labels)

img_new = np.zeros_like(image)
for bb in bboxes:
    img_new[bb[0], bb[1]] = 1

如果矩形相距很远，这个方法就可以正常工作，但如果它们重叠并构建更复杂的结构，这个算法只会给我最大的边界框（放大图像没有任何区别）。我有一种感觉，应该已经存在一个scipy或opencv方法来解决这个问题。 如果有人有想法如何解决这个问题，或者甚至更好的已经知道现有的解决方案，请告诉我，我将不胜感激。

结果是我想要在图像中得到矩形的列表（即左下角：右上角）。条件是，当我重新绘制这些填充的矩形时，我希望获得与之前完全相同的图像。如果可能，矩形的数量应该尽量少。

以下是生成示例图像的代码（以及更复杂的示例original vs scipy）

import numpy as np 

def random_rectangle_image(grid_size, n_obstacles, rectangle_limits):
    n_dim = 2
    rect_pos = np.random.randint(low=0, high=grid_size-rectangle_limits[0]+1,
                                 size=(n_obstacles, n_dim))
    rect_size = np.random.randint(low=rectangle_limits[0],
                                  high=rectangle_limits[1]+1,
                                  size=(n_obstacles, n_dim))

    # Crop rectangle size if it goes over the boundaries of the world
    diff = rect_pos + rect_size
    ex = np.where(diff > grid_size, True, False)
    rect_size[ex] -= (diff - grid_size)[ex].astype(int)

    img = np.zeros((grid_size,)*n_dim, dtype=bool)
    for i in range(n_obstacles):
        p_i = np.array(rect_pos[i])
        ps_i = p_i + np.array(rect_size[i])
        img[tuple(map(slice, p_i, ps_i))] = True
    return img

img = random_rectangle_image(grid_size=64, n_obstacles=30, 
                             rectangle_limits=[4, 10])

- scleronomic

---

"编写这个应该不太难。" 在中心左侧的重叠集合中，右侧图形中有多少个矩形？至少2个，但根据计数方式也可能是3个或4个。 - Jongware

好的，在接收到关于那个措辞的多次评论后，我希望能找到一个现有的算法，并想就此咨询。如果没有现成的算法，我很愿意自己动手解决。我的意思并不是：一定有人比我蠢（或聪明）到可以替我完成这项工作... - scleronomic

所以基本上你要求的是找到图像中每个直角多边形的最小矩形分区。我认为这是一个众所周知的问题，如果你在谷歌上搜索，会找到很多算法。但我不认为有一个简单的解决方案。 - Andreas K.

你可以尝试使用OpenCV的Blob检测方法，并针对这个特定的图像调整其参数。在应用Blob检测器之前，还要考虑对图像进行预处理，如腐蚀和膨胀操作，以便更容易地检测矩形。 - Guilherme Marques

我想到你可能在过度思考这个问题。一个天真的算法也许同样有效：找到矩形的左上角，扫描其边界，从图像中删除。重复此步骤。这种方法会导致比实际绘制的矩形更多的矩形（对于重叠的矩形），但应该是十分可靠的。 - Jongware

Answer 1

以下是需要翻译的内容：

这里有一些让你开始的东西：一个天真的算法，它遍历您的图像并创建尽可能大的矩形。目前，它仅标记矩形，但不报告坐标或计数。这是为了单独可视化算法。

除了PIL之外，它不需要任何外部库来加载和访问左侧图像（保存为PNG时）。我假设周围有15个像素的边框可以忽略。

from PIL import Image

def fill_rect (pixels,xp,yp,w,h):
    for y in range(h):
        for x in range(w):
            pixels[xp+x,yp+y] = (255,0,0,255)
    for y in range(h):
        pixels[xp,yp+y] = (255,192,0,255)
        pixels[xp+w-1,yp+y] = (255,192,0,255)
    for x in range(w):
        pixels[xp+x,yp] = (255,192,0,255)
        pixels[xp+x,yp+h-1] = (255,192,0,255)

def find_rect (pixels,x,y,maxx,maxy):
    # assume we're at the top left
    # get max horizontal span
    width = 0
    height = 1
    while x+width < maxx and pixels[x+width,y] == (0,0,0,255):
        width += 1
    # now walk down, adjusting max width
    while y+height < maxy:
        for w in range(x,x+width,1):
            if pixels[x,y+height] != (0,0,0,255):
                break
        if pixels[x,y+height] != (0,0,0,255):
            break
        height += 1
    # fill rectangle
    fill_rect (pixels,x,y,width,height)

image = Image.open('A.png')
pixels = image.load()
width, height = image.size

print (width,height)

for y in range(16,height-15,1):
    for x in range(16,width-15,1):
        if pixels[x,y] == (0,0,0,255):
            find_rect (pixels,x,y,width,height)

image.show()

从输出中

你可以观察到检测算法可以得到改进，例如，“显然”的左上角两个矩形被分成了3个。同样，中间的较大结构也比绝对需要的多一个矩形。

可能的改进方法是调整find_rect例程以找到最佳适配¹，或存储坐标并使用数学（超出我的能力范围）来查找哪些矩形可以合并。

---

关于这个问题，还有一个进一步的想法。目前，所有找到的矩形都会立即填充上“找到”的颜色。您可以尝试检测明显的多个矩形，然后，在标记第一个矩形后，其他需要检查的矩形可能为黑色或红色。我会随口说一下，您需要尝试不同的扫描顺序（从上到下或反向，从左到右或反向），以实际找到任何组合中所需的最小矩形数量。

- Jongware