Finding some missing points in a numpy array

Interesting problem. Here is a way you can solve this. I have mentioned the complete code first with examples and then an explanation below that. This solution has the following advantages -

1. Works on non-square 2D images
2. No need for knowing the repeating pattern beforehand
3. Can handle square and non-square repeating patterns of any shape
4. Memory efficient and completely (almost) vectorized

NOTE: This approach only works if at least 1 complete, pure repeating pattern exists in the image.

import numpy as np
import matplotlib.pyplot as plt

def find_gaps(x):
    #Identifying the size and shape of the repeating pattern
    xpattern = int(x.shape[0]//np.max(x.sum(axis=0))+2)
    ypattern = int(x.shape[1]//np.max(x.sum(axis=1))+2)
    pattern_shape = (xpattern, ypattern)
    
    #Calculating number of rolling windows that exist with that pattern
    num_xpatterns = x.shape[0]//pattern_shape[0]+1
    num_ypatterns = x.shape[1]//pattern_shape[1]+1
    
    #Calculating the stride and shape that needs to be taken with stride_tricks
    shp = (num_xpatterns, num_ypatterns, xpattern, ypattern)  #(2, 2, 3, 5)
    strd = (x.strides[0]*(xpattern-1), x.strides[1]*(ypattern-1), x.strides[0], x.strides[1])  #(144, 32, 72, 8)
    
    #Generating rolling windows/convolutions over the image to separate the patterns.
    convolve_pattern = np.lib.stride_tricks.as_strided(x, shape=shp, strides=strd)
    
    #Assuming at least 1 untouched pattern exists, finding that pure pattern
    pattern_sums = convolve_pattern.sum(axis=(-1,-2))
    idx = np.unravel_index(np.argmax(pattern_sums), pattern_sums.shape)
    truth_pattern = convolve_pattern[idx]
    
    #Identifying the gaps by subtracting the convolved image with the truth pattern
    gaps = convolve_pattern - truth_pattern[None, None, :, :]
    
    #Setting the gaps as -1 directly into the location of memory of the original image
    for i in np.argwhere(gaps==-1):
        convolve_pattern[tuple(i)]=-1
    
    return(x)

Here is an example with an image with non-square repeating patterns (3,5) and 2 gaps. Here value of -1 represents the gaps or missing 1s but that can be changed to what you want in the function -

#Image with non-square repeating patterns

img = np.array([[1., 0., 0., 0., 1., 0., 0., 0., 0.], #One gap added here
                [0., 0., 1., 0., 0., 0., 1., 0., 0.],
                [1., 0., 0., 0., 1., 0., 0., 0., 1.],
                [0., 0., 1., 0., 0., 0., 0., 0., 0.], #One gap added here
                [1., 0., 0., 0., 1., 0., 0., 0., 1.]])

plt.imshow(img)

plt.imshow(find_gaps(img))

Here is another example where I have added 4 gaps in a larger image with square repeating patterns -

img = np.array([[1., 0., 0., 0., 1., 0., 0., 0., 1., 0., 0., 0., 1., 0., 0., 0., 1.],
                [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
                [0., 0., 1., 0., 0., 0., 1., 0., 0., 0., 1., 0., 0., 0., 0., 0., 0.],  #One gap added here
                [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
                [1., 0., 0., 0., 1., 0., 0., 0., 1., 0., 0., 0., 1., 0., 0., 0., 1.],
                [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
                [0., 0., 1., 0., 0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0.],  #One gap added here
                [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
                [1., 0., 0., 0., 1., 0., 0., 0., 1., 0., 0., 0., 1., 0., 0., 0., 1.],
                [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
                [0., 0., 1., 0., 0., 0., 1., 0., 0., 0., 1., 0., 0., 0., 1., 0., 0.],
                [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
                [1., 0., 0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0.]]) #Two gaps added here

plt.imshow(img)

plt.imshow(find_gaps(img))

Detailed Explanation

Let's assume an image with a non-square (different over axis0 and axis1) repeating pattern. Here the non-square pattern clearly seems to be of the shape (3,5)

x = np.array([[1., 0., 0., 0., 1., 0., 0., 0., 0.],  #<- gap in last entry
              [0., 0., 1., 0., 0., 0., 1., 0., 0.],
              [1., 0., 0., 0., 1., 0., 0., 0., 1.],
              [0., 0., 1., 0., 0., 0., 0., 0., 0.],  #<- gap in 3rd last entry
              [1., 0., 0., 0., 1., 0., 0., 0., 1.]])

The first step would be to find the shape of this untouched/pure pattern that should be repeating in the image. For this, you can calculate the max value of sum over both axes and divide the original shape with that (then add +2) to get (3,5)

xpattern = int(x.shape[0]//np.max(x.sum(axis=0))+2)
ypattern = int(x.shape[1]//np.max(x.sum(axis=1))+2)

pattern_shape = (xpattern, ypattern)

(3,5)

Now that you have the shape of the pattern, you want to perform rolling window operations to separate this shape in the original image. Here, you can see that the image comprises of this pattern repeating 4 times, 2 times over x-axis, and 2 times over y-axis. To calculate how many times the pattern would repeat in the image you can do this -

num_xpatterns = x.shape[0]//pattern_shape[0]+1
num_ypatterns = x.shape[1]//pattern_shape[1]+1

print(num_xpatterns, num_ypatterns)

(2,2)

Now, you have everything to let you build rolling windows using strides to separate the image into blocks of pattern size. The output shape of this array that contains the (3,5) shaped pattern blocks would be (2,2,3,5),i.e, 2 patterns repeat over x-axis and 2 patterns repeat over y-axis.

You can also calculate the strides that need to be taken to achieve this output array by multiplying the number of bytes in each direction with the pattern shape in each direction.

shp = (num_xpatterns, num_ypatterns, xpattern, ypattern)   #(2, 2, 3, 5)
strd = (x.strides[0]*(xpattern-1), x.strides[1]*(ypattern-1), x.strides[0], x.strides[1])   #(144, 32, 72, 8)

convolve_pattern = np.lib.stride_tricks.as_strided(x, shape=shp, strides=strd)
convolve_pattern

array([[[[1., 0., 0., 0., 1.],
         [0., 0., 1., 0., 0.],
         [1., 0., 0., 0., 1.]],

        [[1., 0., 0., 0., 0.],
         [0., 0., 1., 0., 0.],
         [1., 0., 0., 0., 1.]]],


       [[[1., 0., 0., 0., 1.],
         [0., 0., 1., 0., 0.],
         [1., 0., 0., 0., 1.]],

        [[1., 0., 0., 0., 1.],
         [0., 0., 0., 0., 0.],
         [1., 0., 0., 0., 1.]]]])

You have now separated the image into blocks of potential pure and impure patterns of the shape (3,5). Now, all you have to do is find a pure pattern, and compare it to every other pattern in this array of pattern blocks.

This can be done by the simple fact that the pure pattern, will have the largest sum among all other pattern blocks.

pattern_sums = convolve_pattern.sum(axis=(-1,-2))
idx = np.unravel_index(np.argmax(pattern_sums), pattern_sums.shape)

pure_pattern = convolve_pattern[idx]
pure_pattern

array([[1., 0., 0., 0., 1.],
       [0., 0., 1., 0., 0.],
       [1., 0., 0., 0., 1.]])

Subtracting this pure pattern block with every other pattern block using broadcasting, you reveal the positions of the gaps in each pattern block with a -1

gaps = convolve_pattern - pure_pattern[None, None, :, :]
gaps

array([[[[ 0.,  0.,  0.,  0.,  0.],
         [ 0.,  0.,  0.,  0.,  0.],
         [ 0.,  0.,  0.,  0.,  0.]],

        [[ 0.,  0.,  0.,  0., -1.],
         [ 0.,  0.,  0.,  0.,  0.],
         [ 0.,  0.,  0.,  0.,  0.]]],


       [[[ 0.,  0.,  0.,  0.,  0.],
         [ 0.,  0.,  0.,  0.,  0.],
         [ 0.,  0.,  0.,  0.,  0.]],

        [[ 0.,  0.,  0.,  0.,  0.],
         [ 0.,  0., -1.,  0.,  0.],
         [ 0.,  0.,  0.,  0.,  0.]]]])

Finally, (and here comes the power of using the numpy view from the stride_tricks), you can identify the location of the gaps (-1) and simply set them as -1 (or what-ever you like) in the numpy view, thus modifying the original image as well, since the assignment has been made directly to the memory of the original image.

for i in np.argwhere(gaps==-1):
    convolve_pattern[tuple(i)]=-1

print(x)

array([[ 1.,  0.,  0.,  0.,  1.,  0.,  0.,  0., -1.],  #<- Found gap 1!
       [ 0.,  0.,  1.,  0.,  0.,  0.,  1.,  0.,  0.],
       [ 1.,  0.,  0.,  0.,  1.,  0.,  0.,  0.,  1.],
       [ 0.,  0.,  1.,  0.,  0.,  0., -1.,  0.,  0.],  #<- Found gap 2!
       [ 1.,  0.,  0.,  0.,  1.,  0.,  0.,  0.,  1.]])

This is how you can identify gaps in an image with non-square repeating patterns.