Fill Bounding Boxes in 2d array

  • A+
Category:Languages

I have a 2D numpy array which looks like

array([[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., 0., 0., 0., 0.],        [0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],        [0., 0., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],        [0., 0., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],        [0., 0., 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., 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., 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., 0., 0., 0., 0., 0., 0., 0., 0., 0.],        [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0.],        [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0.],        [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 0., 0., 0.],        [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0.]]) ` 

I want to create bounding box like masks over the 1s shown above. For example it should look like this

array([[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., 0., 0., 0., 0.],        [0., 0., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],        [0., 0., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],        [0., 0., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 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., 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., 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., 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., 1., 0., 0., 0.],        [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 0., 0., 0.],        [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 0., 0., 0.],        [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 0., 0., 0.]]) 

How can I do it it easily? Also how do I do it if other no.s like 2,3 etc exist but I want to ignore them and the groups are mostly 2.

 


Here's one approach to solve this problem. The general idea behind it is to use an iterative algorithm which takes the 2D convolution of the matrix and a set of filters at each step. It'll be much easier to explain this with an example. Say we have the following ndarray:

a = np.array([[0,0,0,0],               [0,0,0,0],               [1,0,0,0],               [1,1,1,0]]) 

The idea behind this method is to detect cells which have at least two neighbours (at a distance of 1 cell) both orthogal and at an angle of 90° between each other, which have non-zero values in them. By iteratively finding these cells and filling them with ones, we'll obtain the expected output. So for this example, the output after the first iteration will be:

a = np.array([[0,0,0,0],               [0,0,0,0],               [1,1,0,0],               [1,1,1,0]]) 

And on the following iteration:

a = np.array([[0,0,0,0],               [0,0,0,0],               [1,1,1,0],               [1,1,1,0]]) 

So now the question would be, how can these points be detected? We can achieve this using convolve2D, which takes the convolution of two 2-dimensional arrays.

The 2D convolution is essentially taken by shifting a 2D filter through a ndarray and computing at each step the sum of the element-wise multiplication.

So it will be necessary to come up with some filter in order to detect the cells of interest. One approach could be:

array([[0, 1, 0],        [1, 0, 1],        [0, 1, 0]]) 

At first glance this filter sould do the task, given that it will detect the sorrounding neighbours. However, this filter would also take into account samples which are two cells away, so, for instance it would add up the values in the first and last row in the filter, and as mentioned previously we want to find neighbours that have an angle of 90° between each other. So what we could do is apply a sequence of filters contemplating all possibilities of such case:

[0, 1, 0]   [0, 1, 0]   [0, 0, 0]   [0, 0, 0] [0, 0, 1] , [1, 0, 0] , [1, 0, 0] , [0, 0, 1] [0, 0, 0]   [0, 0, 0]   [0, 1, 0]   [0, 1, 0] 

So by applying each of these filters we could detect which cells have at least two neighbours, and fill them with ones.


General Solution

def fill_bounding_boxes(a):     '''     Detects contiguous non-zero values in a 2D array     and fills with ones all missing values in the      minimal rectangular boundaries that enclose all      non-zero entries, or "Minimal Bounding Boxes"     ----     a: np.array        2D array. All values > 0 are considered to define        the bounding boxes     ----            Returns:        2D array with missing values filled       '''     import numpy as np     from scipy.signal import convolve2d     # Copy of the original array so it remains unmodified     x = np.copy(a).clip(0,1)     # Indicator. Set to false when no additional     # changes in x are found     is_diff = True     # Filter to be used for the 2D convolution     # The other filters are obtained by rotating this one     f = np.array([[0,1,0], [0,0,1], [0,0,0]])     # Runs while indicator is True     while is_diff:         x_ = np.copy(x)         # Convolution between x and the filters         # Only values with sums > 1 are kept, as it will mean         # that they had minimum 2 non-zero neighbours         # All filters are applied by rotating the initial filter         x += sum((convolve2d(x, np.rot90(f, i), mode='same') > 1)                   for i in range(4))         # Clip values between 0 and 1         x = x.clip(0,1)         # Set indicator to false if matrix x is unmodified         if (x == x_).all():             is_diff = False     return x 

Examples

Lets have a look at the result with the proposed example:

print(a) array([[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, 0, 0, 0, 0],        [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],        [0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],        [0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],        [0, 0, 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, 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, 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, 0, 0, 0, 0, 0, 0, 0, 0, 0],        [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],        [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]])  fill_bounding_boxes(a) array([[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, 0, 0, 0, 0],        [0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],        [0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],        [0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 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, 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, 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, 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, 1, 0, 0, 0],        [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],        [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],        [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0]]) 

And for this other example:

print(a) array([[0, 0, 0, 0, 1, 0],        [0, 0, 0, 0, 1, 1],        [1, 0, 0, 0, 0, 0],        [1, 1, 1, 0, 0, 0],        [1, 0, 1, 0, 0, 0],        [0, 0, 0, 0, 0, 0],        [0, 0, 1, 0, 0, 0],        [0, 1, 1, 0, 0, 1],        [0, 0, 0, 0, 1, 0]])  fill_bounding_boxes(a) array([[0, 0, 0, 0, 1, 1],        [0, 0, 0, 0, 1, 1],        [1, 1, 1, 0, 0, 0],        [1, 1, 1, 0, 0, 0],        [1, 1, 1, 0, 0, 0],        [0, 0, 0, 0, 0, 0],        [0, 1, 1, 0, 0, 0],        [0, 1, 1, 0, 1, 1],        [0, 0, 0, 0, 1, 1]]) 

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: