Find an empty space in a binary image that can fit a shape

I have this image
<br>

<br>
I need to find an empty area that can fit this shape
<br>

<br>
so that the end result is something like this
<br>

Here is a simple yet naive solution to this problem. It uses 2D convolution as mentioned by UnquoteQuote.

import random
import numpy as np
import scipy.signal as sig
import matplotlib.pyplot as plt
import cv2

# load images
image = (cv2.imread('image.jpg').mean(axis=2) > 127).astype(np.float32)
shape = (cv2.imread('shape.jpg').mean(axis=2) > 127).astype(np.float32)

# perform 2D convolution
conv = sig.convolve2d(image, shape, mode='valid')
solutions = np.where(conv == 0)

# draw some solutions
plt.figure(figsize=(16, 4))
for i in range(4):
    r = random.randint(0, solutions[0].shape[0] - 1)
    x, y = solutions[0][r], solutions[1][r]

    solution_plot = np.zeros((*image.shape, 3))
    solution_plot[:, :, 0] = image
    solution_plot[x:x + shape.shape[0], y:y + shape.shape[1], 1] = shape

    plt.subplot(1, 4, i + 1)
    plt.imshow(solution_plot)

plt.show()

Example results:

This algorithm finds all possible solutions. If you only need one, you can optimize it so that it gets a random (x, y) point and perform dot product of the shape and a cropped image area [x:x+shape_width, y:y+shape_height] to check if there is a space until you find the right point.

This can be done for example like this:

while True:
    x = random.randint(0, image.shape[0] - shape.shape[0])
    y = random.randint(0, image.shape[1] - shape.shape[1])

    if np.sum(shape*image[x:x + shape.shape[0], y:y + shape.shape[1]]) == 0:
        break

# x, y is the solution

Compared to convolution this one is much faster (but it depends on the number of the solutions):

• convolution: 6.65 s ± 21.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

• random search: 1.31 ms ± 31.2 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)