Search code examples
numpyndimage

Find the 1s pixels that immediately and completely enclose an area of 0s

Starting with a 2d array of 0s and 1s, I need to identify which 1s form a united fence completely enclosing one or more adjacent 0s. Those 0s are considered adjacent if they touch on their sides or the diagonal. The fence must exist on the neighboring diagonal as well.

This is the 2d array, and what I want are the 1s which indicate the fence, and then everything else should be zero. This is a simple case, in reality the array is a png image, and I want all the fences that may exist in it.

Is ndimage the module needed? Any advice please.

array=
[[1,1,1,1,1,1],  
 [1,1,0,0,1,1],  
 [1,1,0,1,1,1],  
 [1,1,1,1,1,1],  
 [0,0,1,1,0,0]] 

answer=
[[0,1,1,1,1,0],  
 [0,1,0,0,1,0],  
 [0,1,0,1,1,0],  
 [0,1,1,1,0,0],  
 [0,0,0,0,0,0]]
Solution

  • Following the approach suggested by Jerome and Mark:

    1. Pad the matrix with a 1px border of zeros
    2. Flood the matrix and keep just the islands of central 0s
    3. Expand those islands with dilate (after inverting them) to expand the contours -> B
    4. bitwise AND it with A to get back just the contours and remove the initial padding
    from collections import deque as queue
from scipy import ndimage
import numpy as np
from skimage.segmentation import flood_fill

A = np.array([[1,1,1,1,1,1],  
              [1,1,0,0,1,1],  
              [1,1,0,1,1,1],  
              [1,1,1,1,1,1],  
              [0,0,1,1,0,0]])
A = np.pad(A, pad_width=1, mode='constant', constant_values=0)
print("A after padding")
print(A)

A = flood_fill(A, (0, 0), 1)
print("A after flooding")
print(A)

# you can also use cv2.dilate if you want to avoid ndimage
struct2 = ndimage.generate_binary_structure(2, 2)
B = ndimage.binary_dilation(1-A, structure=struct2).astype(A.dtype)
print("B")
print(B)

print("result")
res = B & A
print(res[1:-1, 1:-1]) # remove padding

    Output:

    A after padding
[[0 0 0 0 0 0 0 0]
 [0 1 1 1 1 1 1 0]
 [0 1 1 0 0 1 1 0]
 [0 1 1 0 1 1 1 0]
 [0 1 1 1 1 1 1 0]
 [0 0 0 1 1 0 0 0]
 [0 0 0 0 0 0 0 0]]
A after BFS
[[1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1]
 [1 1 1 0 0 1 1 1]
 [1 1 1 0 1 1 1 1]
 [1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1]]
B
[[0 0 0 0 0 0 0 0]
 [0 0 1 1 1 1 0 0]
 [0 0 1 1 1 1 0 0]
 [0 0 1 1 1 1 0 0]
 [0 0 1 1 1 0 0 0]
 [0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0]]
result
[[0 1 1 1 1 0]
 [0 1 0 0 1 0]
 [0 1 0 1 1 0]
 [0 1 1 1 0 0]
 [0 0 0 0 0 0]]