4

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]]
Jim
  • 155
  • 1
  • 8
  • 1
    What if `array[0][1] = 0` or if `array[0][3] = 0`? Would it be all 0? – mozway Jan 13 '22 at 22:01
  • @mozway Yes because the 0s can escape. – Jim Jan 13 '22 at 22:18
  • 1
    If you consider the zeroes to be black pixels and the ones to be white pixels, you are looking for a *"morphological edgein"* or the difference between the original and a morphological erosion. https://legacy.imagemagick.org/Usage/morphology/#edgein – Mark Setchell Jan 13 '22 at 22:32
  • 1
    To take into account "escaping" 0s, you could perform a floodfill on the array with an additional ghost area (of size 1) filled with 0s and then perform a morphological EdgeIn. – Jérôme Richard Jan 13 '22 at 23:22
  • If you add a 1-pixel wide border of zeroes to each side and flood-fill all zero pixels with one starting at (0,0) it will flood all *"escape routes"* out of the sudes of the image. The 1-pixel border allows the flood-fill to *"flow"* all around the edges of the image and fill in all the *"escape routes"*. – Mark Setchell Jan 13 '22 at 23:25
  • 2
    @JérômeRichard SNAP! – Mark Setchell Jan 13 '22 at 23:25

1 Answers1

1

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]]
rikyeah
  • 1,896
  • 4
  • 11
  • 21
  • I expect the BFS to be very slow on some big images. Consider using `flood_fill`/`flood` of `skimage.segmentation`. – Jérôme Richard Jan 14 '22 at 00:56
  • Probably not the place to discuss this, but I'm new to Stack Overflow; I understood your improvement and want to correct my answer: should I add another answer or edit the current one? – rikyeah Jan 14 '22 at 01:01
  • 1
    You should edit the current one. Adding new answer is only a good idea if you propose a very different (independent) solution. – Jérôme Richard Jan 14 '22 at 01:12
  • 1
    Thank you. Do not forget to update the imports accordingly ;) . – Jérôme Richard Jan 14 '22 at 13:04