Find minimal number of rectangles in the image

Question

I have binary images where rectangles are placed randomly and I want to get the positions and sizes of those rectangles. If possible I want the minimal number of rectangles necessary to exactly recreate the image.

On the left is my original image and on the right the image I get after applying scipys.find_objects() (like suggested for 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

This works fine if the rectangles are far apart, but if they overlap and build more complex structures this algorithm just gives me the largest bounding box (upsampling the image made no difference). I have the feeling that there should already exist a scipy or opencv method which does this. I would be glad to know if somebody has an idea on how to tackle this problem or even better knows of an existing solution.

As result I want a list of rectangles (ie. lower-left-corner : upper-righ-corner) in the image. The condition is that when I redraw those filled rectangles I want to get exactly the same image as before. If possible the number of rectangles should be minimal.

Here is the code for generating sample images (and a more complex example 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

Here is something to get you started: a naïve algorithm that walks your image and creates rectangles as large as possible. As it is now, it only marks the rectangles but does not report back coordinates or counts. This is to visualize the algorithm alone.

It does not need any external libraries except for PIL, to load and access the left side image when saved as a PNG. I'm assuming a border of 15 pixels all around can be ignored.

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

From the output

you can observe the detection algorithm can be improved, as, for example, the "obvious" two top left rectangles are split up into 3. Similar, the larger structure in the center also contains one rectangle more than absolutely needed.

Possible improvements are either to adjust the find_rect routine to locate a best fit¹, or store the coordinates and use math (beyond my ken) to find which rectangles may be joined.

---

¹ A further idea on this. Currently all found rectangles are immediately filled with the "found" color. You could try to detect obviously multiple rectangles, and then, after marking the first, the other rectangle(s) to check may then either be black or red. Off the cuff I'd say you'd need to try different scan orders (top-to-bottom or reverse, left-to-right or reverse) to actually find the minimally needed number of rectangles in any combination.