Найдите минимальное количество прямоугольников на изображении

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

Это прекрасно работает, если прямоугольники находятся далеко друг от друга, но если они перекрываются и создают больше Для сложных структур этот алгоритм просто дает мне самую большую ограничивающую рамку (повышение частоты дискретизации не имеет значения). У меня такое чувство, что уже должен существовать метод scipy или opencv, который делает это. Я был бы рад узнать, если у кого-то есть идея о том, как решить эту проблему, или даже лучше знать о существующем решении.

В результате я хочу получить список прямоугольников (ie. Lower- левый угол: верхний правый угол) на изображении. Условие состоит в том, что, когда я перерисовываю эти заполненные прямоугольники, я хочу получить точно такое же изображение, как и раньше. Если возможно, количество прямоугольников должно быть минимальным.

Вот код для создания образцов изображений (и более сложный пример оригинал против 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

Вот кое-что для начала: наивный алгоритм, который обходит ваше изображение и создает прямоугольники как можно большего размера. Как и сейчас, он только помечает прямоугольники, но не сообщает координаты или значения. Это делается для визуализации только одного алгоритма.

Ему не нужны никакие внешние библиотеки, кроме 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 для определения наилучшего соответствия¹, либо сохранить координаты и использовать математику (за пределами моего кена), чтобы найти прямоугольники, которые можно объединить.

---

further Еще одна идея на этом. В настоящее время все найденные прямоугольники немедленно заполняются цветом «найдено». Вы можете попытаться обнаружить явно несколько прямоугольников, а затем, после маркировки первого, другой прямоугольник (и) для проверки может быть либо черным , либо красным. Если бы не манжета, я бы сказал, что вам нужно попробовать разные порядки сканирования (сверху вниз или назад, слева направо или назад), чтобы на самом деле найти минимально необходимое количество прямоугольников в любой комбинации.