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

Fawn

"It should not be too hard to code this."ᶜᶦᵗᵃᵗᶦᵒⁿ ⁿᵉᵉᵈᵉᵈ How many rectangles are in the right hand side figure, in the overlapping set left of the center? At least 2 -- but it can also be 3 or 4, depending on how you are counting. – Towrope

I know that the solution can be ambiguous. That the number of rectangles is minimal is not that important. I just don't want an algorithm that creates a new rectangle at every corner, but rather takes the overlaps into account. – Fawn

So how would the desired image B look like? Can you draw it please? This would make more clear what you want to achieve. – Matted

Image B should look exactly like image A. I want to recreate image A when drawing all the found rectangles. – Fawn

Is there an upper limit on the number of rectangles that can overlap / form a connected component? – Twinned

@PaulBrodersen The maximum number or rectangles in the image is 50. They are placed completely random. So all 50 could overlap in theory. – Fawn

You cannot recreate the exact same image A from B, because image A contains rectilinear polygons, not only simple polygons. So having [lower-left-corner : upper-righ-corner] is not enough. And since you have image A, why you need to recreate it? – Matted

@AndreasK. I don't want to recreate image A from image B. I have image A. I want to get a complete list of rectangles from image A. The condition for this list is, that when I would redraw all the rectangles the result should be exactly equal to image A. The image B I have drawn is just an example where I have tried scipys.find_objects() to get my list of rectangles. – Fawn

What do you mean by list of all rectangles? As I said, you have rectilinear polygons of different shapes, so to spesify each, two points is not enough. – Matted

I know that my figure is composed of (possible overlapping) rectangles. I want a list of all those rectangles. If they are overlapping and form a rectilinear polygon. I want to break it down into simple rectangles. – Fawn

Ok, I think I understand now. But I think it would help if you provided exactly the desired output for a small example-image (e.g. create a 10x10 binary array as your image and write the desired list of rectangles). – Matted

"It should not be too hard to code this" really? – Monobasic

Ok after multiple comments on that phrasing: I hoped that there is an existing algorithm for this and wanted to ask about it. If there is none, I will happily do it myself. It should not sound like: surely there is somebody dumb (and smart) enough to do the work for me... – Fawn

So basically what you are asking for is to find the minimum rectangular partition for each rectilinear polygon in the image. It is a well known problem I think and if you Google it you will find many algorithms for this. But I don't think that there's an easy solution. – Matted

Thank you for the keywords, that helps. Didn't expect to stumble on a whole area of research. Just wanted to draw some rectangles. – Fawn

You could try to use opencv blob detection method and tweak its parameter for this specific image. Also consider preprocessing the image before applying a blob detector, like erosion and dilation operations to make it easier to detect rectangles. – Southwestwardly

It occured to me that you may be overthinking this. A naïve algorithm may work as well: locate top left of a rectangle, scan for its boundaries, remove from image. Repeat. It will lead to more rectangles that there are drawn (for overlapping rects) but it should be foolproof. – Towrope

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.

Towrope