Filling in a concave polygon represented as a binary matrix

Question

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

how do you decide that these are not positions (3, 0), (4, 0) are not the ones that are supposed to be filled? is it related to path of zeros touching the "border" of the whole matrix? — Kuba Wyrostek, Jul 08 '15 at 11:15
I'm not sure if I understand it correctly, but those two zeros are outside the border of the u-shaped polygon defined by the outermost layer of ones. — John Manak, Jul 08 '15 at 11:25

Imanol Luengo · Accepted Answer · 2015-07-08T11:40:41.890

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]])

score 0 · Answer 2 · edited May 23 '17 at 12:29

0

I do not believe there would exist some generic purpose solution in Python or whatever. This is classic breadth-first graph search. For each 0 either exists a path of adjacent zeros, so that at least one of those zeros is at position (y,x) so that (x = 0 or y = 0 or x = maxx or y = maxy) or this 0 should be changed to 1.

Maybe an answer here will be helpful to you: How to trace the path in a Breadth-First Search?

edited May 23 '17 at 12:29

Community

1
1

answered Jul 08 '15 at 11:34

Kuba Wyrostek

6,163
1
22
40

Thanks! Actually this was my first solution, but I was looking for something like the `binary_fill_holes` function in the other answer. – John Manak Jul 08 '15 at 12:10
Because your first statement contradicts the accepted answer. It does exists a generic solution. Binary hole-filling is a basic operation in image processing. While the answer is not bad (gives some hints of how to do stuff) it has an obvious wrong sentence that a bit of image processing knowledge would have solved. Ultimately the OP asks "is there an easy way on python/numpy" and your answer is "no" which is wrong. – Ander Biguri Jul 09 '15 at 15:22
OK, I get it. However I fill the urge to emphasize that the answer doesn't state a *hard no*. I just said I do not believe there exists (but feel free to carry on searching). While I surely know close to nothing about image processing I saw a possible solution in graph algorithms. I wouldn't personally downvote similiar answer for the sake of overconfident author :) but you are of course free to do so. Thank you for explanation. – Kuba Wyrostek Jul 09 '15 at 15:52

Filling in a concave polygon represented as a binary matrix

2 Answers2