pythonnumpyconcaveconcave-hull

Filling in a concave polygon represented as a binary matrix

In my task, I represent a concave polygon as a matrix of ones and zeros, where one means that the given point belongs to the polygon. For instance, the following are a simple square and a u-shaped polygon:

0 0 0 0     0 0 0 0 0 0 0
0 1 1 0     0 1 1 0 0 1 1
0 1 1 0     0 1 1 1 1 1 1
0 0 0 0     0 1 1 1 1 1 1

However, sometimes I get an incomplete representation, in which: (1) all boundary points are included, and (2) some internal points are missing. For example, in the following enlarged version of the u-shaped polygon, the elements at positions (1,1), (1,6), (3,1), ..., (3,6)* are "unfilled". The goal is to fill them (i.e., change their value to 1).

1 1 1 0 0 1 1 1
1 0 1 0 0 1 0 1
1 1 1 1 1 1 0 1
1 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1

Do you know if there's an easy way to do this in Python/NumPy?

*(row, column), starting counting from the top left corner

Solution

  • This is a very well known problem in image processing that can be solved using morphological operators.

    With that, you can use scipy's binary_fill_holes to fill the holes in your mask:

    >>> import numpy as np
>>> from scipy.ndimage import binary_fill_holes
>>> data = np.array([[1, 1, 1, 0, 0, 1, 1, 1],
                     [1, 0, 1, 0, 0, 1, 0, 1],
                     [1, 1, 1, 1, 1, 1, 0, 1],
                     [1, 0, 0, 0, 0, 0, 0, 1],
                     [1, 1, 1, 1, 1, 1, 1, 1]])

>>> filled = binary_fill_holes(data).astype(int)
>>> filled
array([[1, 1, 1, 0, 0, 1, 1, 1],
       [1, 1, 1, 0, 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]])