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

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

5 голосов
/ 13 февраля 2020

У меня есть двоичные изображения, в которых прямоугольники размещены случайным образом, и я хочу получить положения и размеры этих прямоугольников. Если возможно, я хочу, чтобы минимальное количество прямоугольников, необходимых для точного воссоздания изображения .

Слева - мое исходное изображение, а справа - изображение, которое я получаю после применения scipys.find_objects() (например, рекомендуется для этот вопрос ).

rectangles rectangles

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])

1 Ответ

1 голос
/ 14 февраля 2020

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

Ему не нужны никакие внешние библиотеки, кроме 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()

Из вывода

found rectangles are marked in orange

вы можете Заметим, что алгоритм обнаружения можно улучшить, так как, например, «очевидные» два верхних левых прямоугольника разбиты на 3. Аналогично, более крупная структура в центре также содержит на один прямоугольник больше, чем абсолютно необходимо.

Возможные улучшения: либо настроить подпрограмму find_rect для определения наилучшего соответствия¹, либо сохранить координаты и использовать математику (за пределами моего кена), чтобы найти прямоугольники, которые можно объединить.

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

...