Floodfill segmented image in numpy/python

Question

I have a numpy array which represents a segmented 2-dimensional matrix from an image. Basically, it's a sparse matrix with a bunch of closed shapes that are the outlines of the segments of the image. What I need to do is colorize the empty pixels within each closed shape with a different color/label in numpy.

I know I could do this with floodfill in PIL but I'm trying not to have to convert the matrix back and forth from numpy to PIL. It would be nice if there was a function in someting like skimage or sklearn that could "auto-label" all the different closed regions of my matrix with a different label for me (it could be a monotonically incrementing integer or a color. I don't care so long as it represents the correct grouping of adjacent pixels within its region).

I've already spent a lot of time trying to implement my own floodfill and at this point I'd just like somehting that could label the image out of the box for me.

Answer 1

I'm assuming that your matrix is binary where non-zero values represent the extracted segments and zero values are values you don't care about. The scikit-image label function from the measure module may be of interest: http://scikit-image.org/docs/dev/api/skimage.measure.html#skimage.measure.label

It essentially performs a connected components analysis and labels all separately closed components together with an integer number. You need to be careful though with regards to how you specify connectivity. There is 4-connectedness and 8-connectedness where the former finds connected regions using only the North, South, East and West directions whereas 8-connectedness uses all 8 directions (North, South, East, West, Northeast, Southeast, Northwest, Southwest). You would use the connectivity option and specify 1 for the 4-connectedness and 2 for the 8-connectedness.

However, the default connectivity would be a full connectivity, so for the case of 2D it would be the 2 option. I suspect for you it would be this way. Any blobs in your matrix that are zero would be labelled as zero. Without further ado, here's a very simple reproducible example:

In [1]: from skimage.measure import label

In [2]: import numpy as np

In [3]: x = np.zeros((8,8))

In [4]: x[0:4,0:4] = 1

In [5]: x[6:8,6:8] = 1

In [6]: x
Out[6]:
array([[ 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.,  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.,  1.,  1.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  1.,  1.]])

In [7]: label(x)
Out[7]:
array([[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, 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, 2, 2],
       [0, 0, 0, 0, 0, 0, 2, 2]], dtype=int64)

We can see that there are two separate islands that I created on the top left and bottom right corner. Once you run the label function, it returns a label matrix identifying regions of pixels that belong to each other. Pixels that have the same ID mean that the belong to the same region.

To show you how the connectivity comes into play, here's another simple example:

In [1]: import numpy as np

In [2]: from skimage.measure import label

In [3]: y = np.array([[0,1,0,0],[1,1,1,0],[0,1,0,1]])

In [4]: y
Out[4]:
array([[0, 1, 0, 0],
       [1, 1, 1, 0],
       [0, 1, 0, 1]])

In [5]: label(y, connectivity=1)
Out[5]:
array([[0, 1, 0, 0],
       [1, 1, 1, 0],
       [0, 1, 0, 2]], dtype=int64)

In [6]: label(y)
Out[6]:
array([[0, 1, 0, 0],
       [1, 1, 1, 0],
       [0, 1, 0, 1]], dtype=int64)

The input has a cross pattern on the top left corner and a separate non-zero value at the bottom right corner. If we use 4-connectivity, the bottom right corner would be classified as a different label but if we use the default connectivity (full), every pixel would be classified as the same label.