The fastest way to exclude surrounding zeros from an array representing an image?

Question

I have a 2D array containing grayscale image created from .png as follows:

import cv2

img = cv2.imread("./images/test.png")
img = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

What I would like to do is to extract a subarray containing only the rectangle containing the data - ignoring all zeros surrounding the picture.

For example, if input is:

  0   0   0   0   0   0   0   0
  0   0   0   0   0   0   0   0
  0   0 175   0   0   0  71   0
  0   0   0  12   8  54   0   0
  0   0   0   0 255   0   0   0
  0   0   0   2   0   0   0   0
  0   0   0   0   0   0   0   0
  0   0   0   0   0   0   0   0

then output should be:

175   0   0   0  71
  0  12   8  54   0
  0   0 255   0   0
  0   2   0   0   0

I could iterate over the rows in forward direction to find the first nonzero row and then iterate over the rows backwards to find the last nonzero row remembering indices - and then repeat the same for the columns and then extract a subarray using that data but I am sure there are more appropriate ways of doing the same or there even might be a NumPy function designed for such a purpose.

If I were to choose between shortest code vs fastest execution I'd be more interested in fastest ~~code~~ execution.

EDIT:
I did not include the best example because there could be zero rows/columns in the middle as here:

Input:

  0   0   0   0   0   0   0   0
  0   0   0   0   0   0   0   0
  0   0 175   0   0   0  71   0
  0   0   0  12   8  54   0   0
  0   0   0   0 255   0   0   0
  0   0   0   0   0   0   0   0
  0   0   0   2   0   0   0   0
  0   0   0   0   0   0   0   0

Output:

175   0   0   0  71
  0  12   8  54   0
  0   0 255   0   0
  0   0   0   0   0
  0   2   0   0   0

`If I were to choose between shortest code vs fastest execution I'd be more interested in fastest code.` By the `fastest code` you mean the fastest execution, right? — dROOOze, Mar 25 '18 at 05:56
You can do this without iterating, by first masking `>0` and then asking for min and max mask indices on each axis, and then slicing on that. I don't think it would be significantly faster or more readable at that point, but… might be worth trying. — abarnert, Mar 25 '18 at 06:08
@abarnet: Why wouldn't you write down the answer so I could accept it? Seems as droooze did write a correct answer but then he removed it :-/ — Chupo_cro, Mar 25 '18 at 06:30
@Chupo_cro sorry, I wanted to change something to make it more general. — dROOOze, Mar 25 '18 at 06:30
@droooze: No need to sorry :-) I saw your answer for the moment and it seemed to me it was correct. I'll wait until you write it again. — Chupo_cro, Mar 25 '18 at 06:34
I have even your first anser because I made a screenshot :-) It is grayed because you already deleted the answer but it is still readable. It was my mistake because I did not make the best example data, I'll add the example with the zeros in the middle. — Chupo_cro, Mar 25 '18 at 06:40

dROOOze · Answer 1 · 2018-03-25T12:49:04.037

Note, not an OpenCV solution - this will work for n-dimensional NumPy or SciPy arrays in general.

(Based on Divakar's answer, extended to n dimensions)

def crop_new(arr):

    mask = arr != 0
    n = mask.ndim
    dims = range(n)
    slices = [None]*n

    for i in dims:
        mask_i = mask.any(tuple(dims[:i] + dims[i+1:]))
        slices[i] = (mask_i.argmax(), len(mask_i) - mask_i[::-1].argmax())

    return arr[[slice(*s) for s in slices]]

Speed tests:

In [42]: np.random.seed(0)

In [43]: a = np.zeros((30, 30, 30, 20),dtype=np.uint8)

In [44]: a[2:-2, 2:-2, 2:-2, 2:-2] = np.random.randint(0,255,(26,26,26,16),dtype
=np.uint8)

In [45]: timeit crop(a) # Old solution
1 loop, best of 3: 181 ms per loop

In [46]: timeit crop_fast(a) # modified fireant's solution for n-dimensions
100 loops, best of 3: 5 ms per loop

In [48]: timeit crop_new(a) # modified Divakar's solution for n-dimensions
100 loops, best of 3: 1.91 ms per loop

Old solution

You can use np.nonzero to get the indices of the array. The bounding box of this array are then contained entirely in the maximum and minimum values of the indices.

def _get_slice_bbox(arr):
    nonzero = np.nonzero(arr)
    return [(min(a), max(a)+1) for a in nonzero]

def crop(arr):
    slice_bbox = _get_slice_bbox(arr)
    return arr[[slice(*a) for a in slice_bbox]]

E.g.

>>> img = np.array([[  0,   0,   0,   0,   0,   0,   0,   0],
                    [  0,   0,   0,   0,   0,   0,   0,   0],
                    [  0,   0, 175,   0,   0,   0,  71,   0],
                    [  0,   0,   0,  12,   8,  54,   0,   0],
                    [  0,   0,   0,   0, 255,   0,   0,   0],
                    [  0,   0,   0,   2,   0,   0,   0,   0],
                    [  0,   0,   0,   0,   0,   0,   0,   0],
                    [  0,   0,   0,   0,   0,   0,   0,   0]],  dtype='uint8')
>>> print crop(img)
[[175   0   0   0  71]
 [  0  12   8  54   0]
 [  0   0 255   0   0]
 [  0   2   0   0   0]]

Note, if you want to extend this to support colour images, you'll have to figure out the position of the colour channel then slice appropriately. As of now this solution doesn't fully support colour images. — dROOOze, Mar 25 '18 at 06:45
This is exactly what I need, thank you! In fact, I could use even 1-bit per pixel image. — Chupo_cro, Mar 25 '18 at 06:49
I've updated my answer with a simpler function using opencv methods, that's probably as fast or faster than numpy based method. — fireant, Mar 25 '18 at 20:48

Divakar · Answer 2 · 2018-03-25T10:36:34.643

We could use argmax to get the start, stop row and column indices, as discussed in some detail in this post. We also intend to work with boolean arrays/masks for efficient processing. Thus, using these tools/ideas, we would have one vectorized solution, like so -

def remove_black_border(a): 
    # Mask of non-zeros
    mask = a!=0 # Use a >tolerance for a tolerance defining black border

    # Mask of non-zero rows and columns
    mask_row = mask.any(1)
    mask_col = mask.any(0)

    # First, last indices among the non-zero rows
    sr0,sr1 = mask_row.argmax(), len(mask_row) - mask_row[::-1].argmax()

    # First, last indices among the non-zero columns
    sc0,sc1 = mask_col.argmax(), len(mask_col) - mask_col[::-1].argmax()

    # Finally slice along the rows & cols with the start and stop indices to get 
    # cropped image. Slicing helps for an efficient operation.
    return a[sr0:sr1, sc0:sc1]

Sample run -

In [56]: a # Input image array
Out[56]: 
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, 175,   0,   0,   0,  71],
       [  0,   0,   0,   0,  12,   8,  54,   0],
       [  0,   0,   0,   0,   0, 255,   0,   0],
       [  0,   0,   0,   0,   0,   0,   0,   0],
       [  0,   0,   0,   0,   2,   0,   0,   0],
       [  0,   0,   0,   0,   0,   0,   0,   0],
       [  0,   0,   0,   0,   0,   0,   0,   0]])

In [57]: out = remove_black_border(a)

In [58]: out
Out[58]: 
array([[175,   0,   0,   0,  71],
       [  0,  12,   8,  54,   0],
       [  0,   0, 255,   0,   0],
       [  0,   0,   0,   0,   0],
       [  0,   2,   0,   0,   0]])

Memory efficiency :

The output is a view into the input array, so no extra memory or copying is needed, which is helping on memory efficiency. Let's verify the view part -

In [59]: np.shares_memory(a, out)
Out[59]: True

Timings with all proposed approaches on bigger image

In [105]: # Setup for 1000x1000 2D image and 100 offsetted boundaries all across
     ...: np.random.seed(0)
     ...: a = np.zeros((1000,1000),dtype=np.uint8)
     ...: a[100:-100,100:-100] = np.random.randint(0,255,(800,800),dtype=np.uint8)

In [106]: %timeit crop_fast(a) # @fireant's soln
     ...: %timeit crop(a)      # @droooze's soln
     ...: %timeit remove_black_border(a) # from this post
100 loops, best of 3: 4.58 ms per loop
10 loops, best of 3: 127 ms per loop
10000 loops, best of 3: 155 µs per loop

Thanks for pointing out a much faster method. I added a new solution to handle n-dimensions based on your method, which should be able to handle image stacks. — dROOOze, Mar 25 '18 at 12:30
When I saw the answers for the last time fireant's answer was the fastest and I just wanted to mark it as a solution but now it seems as your solution is the fastest and drooze updated his answer with the solution basen on your answer. Now I am not anymore sure which answer to mark as a solution :-/ Furthermore, I only now realized that my program could benefit if there is `an information about the coordinates of the extracted subarray`. I am not sure whether to post a new question with the added requirement (extract a subarray `and return its coordinates inside the original array`) or not :-/ — Chupo_cro, Mar 25 '18 at 19:04
@Chupo_cro I guess post a new question detailing on - `an information about the coordinates of the extracted subarray` part. — Divakar, Mar 25 '18 at 20:19

fireant · Accepted Answer · 2018-03-28T04:49:53.077

5

Update This simpler method using opencv functions actually faster, and probably faster than the other methods presented in the other answers here.

def crop_fastest(arr):
    return cv2.boundingRect(cv2.findNonZero(arr))

This return the x, y, width, and the height of bounding box. On my desktop pc for my old code 1000 loops, best of 3: 562 µs per loop while for this new code 10000 loops, best of 3: 179 µs per loop.

Yet Another Update

As Chupo_cro pointed out simply calling cv2.boundingRect(arr) returns the same result, and that seems to be due to the code in this function that does the conversion internally.

Previous answer

Probably there are faster methods for this. This simpler function is slightly faster.

from scipy import ndimage
def crop_fast(arr):
    slice_x, slice_y = ndimage.find_objects(arr>0)[0]
    return arr[slice_x, slice_y]

To compare the speeds of droooze's code and this one,

arr = np.zeros(shape=(50000,6), dtype=np.uint8)
arr[2] = [9,8,0,0,1,1]
arr[1] = [0,3,0,0,1,1]

Then %timeit crop(arr) returns 1000 loops, best of 3: 1.62 ms per loop and %timeit crop_fast(arr) returns 1000 loops, best of 3: 979 µs per loop on my laptop. That is, crop_fast() takes about 60% of time by crop().

edited Mar 28 '18 at 04:49

answered Mar 25 '18 at 07:08

fireant

14,080
4
39
48

When I saw the answers for the last time your answer was the fastest and I just wanted to mark it as a solution but now it seems as Divakar's solution is the fastest and drooze updated his answer with the solution basen on Divakar's answer. Now I am not anymore sure which answer to mark as a solution :-/ – Chupo_cro Mar 25 '18 at 18:55
1

@Chupo_cro I updated my answer, probably this is the fastest code, you can try on your own data and see if that's the case. – fireant Mar 25 '18 at 20:47
I tried using just `cv2.boundingRect(arr)` instead of `cv2.boundingRect(cv2.findNonZero(arr))` and that gives correct results as well - how is that possible? `findNonZero(arr)` returns `list of coordinates` of non-zero pixels and replacing that with just `arr` gives the same result :-O `cv2.boundingRect()` expects a point set but everything works even if the array is passed instead of set of the points. – Chupo_cro Mar 28 '18 at 00:20
@Chupo_cro you're right, I just checked and that was surprising to me. I tried to quickly dig in the code and see why that's the case. It seems [this function](https://github.com/opencv/opencv/blob/ff190b1ef4bdf42af7c8d358ca6795bc906a1db4/modules/python/src2/cv2.cpp#L1356) does that conversion. – fireant Mar 28 '18 at 04:47
I just checked with OpenCV `2.4.12` and `cv2.boundingRect(arr)` didn't work meaning automatic conversion was added later. In older versions of OpenCV only `cv2.boundingRect(cv2.findNonZero(arr))` works well. – Chupo_cro Mar 28 '18 at 23:40

The fastest way to exclude surrounding zeros from an array representing an image?

3 Answers3

Linked