在图像中找到最少数量的矩形

Question

我有矩形随机放置的二进制图像，我想获得这些矩形的位置和大小。如果可能，我想要精确重新创建图像所需的最少矩形数量。

左边是我的原始图像，右边是我申请后得到的图像scipys.find_objects() （就像这个问题的建议）。

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

如果矩形相距很远，这可以正常工作，但是如果它们重叠并构建更复杂的结构，则该算法只会给我最大的边界框（对图像进行上采样没有区别）。我有一种感觉，应该已经存在执行此操作的scipyoropencv方法。我很高兴知道是否有人对如何解决这个问题有想法，或者甚至更了解现有的解决方案。

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

这是生成示例图像的代码（以及更复杂的示例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])

Answer 1

这里有一些可以帮助您入门的东西：na\xc3\xafve 算法，它会遍历您的图像并创建尽可能大的矩形。现在，它仅标记矩形，但不报告回坐标或计数。这是为了单独可视化算法。

\n\n

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

\n\n

from PIL import Image\n\ndef fill_rect (pixels,xp,yp,w,h):\n    for y in range(h):\n        for x in range(w):\n            pixels[xp+x,yp+y] = (255,0,0,255)\n    for y in range(h):\n        pixels[xp,yp+y] = (255,192,0,255)\n        pixels[xp+w-1,yp+y] = (255,192,0,255)\n    for x in range(w):\n        pixels[xp+x,yp] = (255,192,0,255)\n        pixels[xp+x,yp+h-1] = (255,192,0,255)\n\ndef find_rect (pixels,x,y,maxx,maxy):\n    # assume we\'re at the top left\n    # get max horizontal span\n    width = 0\n    height = 1\n    while x+width < maxx and pixels[x+width,y] == (0,0,0,255):\n        width += 1\n    # now walk down, adjusting max width\n    while y+height < maxy:\n        for w in range(x,x+width,1):\n            if pixels[x,y+height] != (0,0,0,255):\n                break\n        if pixels[x,y+height] != (0,0,0,255):\n            break\n        height += 1\n    # fill rectangle\n    fill_rect (pixels,x,y,width,height)\n\nimage = Image.open(\'A.png\')\npixels = image.load()\nwidth, height = image.size\n\nprint (width,height)\n\nfor y in range(16,height-15,1):\n    for x in range(16,width-15,1):\n        if pixels[x,y] == (0,0,0,255):\n            find_rect (pixels,x,y,width,height)\n\nimage.show()\n

\n\n

从输出来看

\n\n

\n\n

您可以观察到检测算法可以得到改进，例如，“明显的”左上角的两个矩形被分成了 3 个。类似地，中心较大的结构也包含比绝对需要多的一个矩形。

\n\n

可能的改进是调整find_rect例程以找到最适合的\xc2\xb9，或者存储坐标并使用数学（超出我的知识）来查找可以连接哪些矩形。

\n\n\n\n

\xc2\xb9 对此的进一步想法。目前，所有找到的矩形都会立即填充“找到的”颜色。您可以尝试检测明显的多个矩形，然后在标记第一个矩形后，要检查的其他矩形可能是黑色或红色。我想说的是，你需要尝试不同的扫描顺序（从上到下或反向、从左到右或反向）才能真正找到任意组合中所需的最小矩形数量。

\n