16
\$\begingroup\$

Objective: Crop the image so only the number stays in the image

Problem: Slow Performance

I have code that crops an image. The image pixels are 0 or 255. There are no values between.

The background is 0 (black) and the letter/number is between 0 (not-inclusive) - 255 (white).

This code is being used to crop a Mnist Digit of the Mnist Dataset.

white-on-black handwritten digits

Image Source

The code does it, however, it does with 2 fors and it takes a long time! How can I optimize it?

def crop_image(data_to_crop):
    cropped_data = []

    for z in xrange(data_to_crop.shape[0]):

        img = data_to_crop[z]
        img = img.reshape(data_to_crop.shape[0], data_to_crop.shape[1])

        rx = -1
        upy = -1

        lx = -1
        by = -1

        for x in xrange(data_to_crop.shape[0]):
            for y in xrange(data_to_crop.shape[1]):

                px = img[x, y]

                if px > 0:

                    if rx == -1 or x > rx:
                        rx = x

                    if lx == -1 or x < lx:
                        lx = x

                    if upy == -1 or y > upy:
                        upy = y

                    if by == -1 or y < by:
                        by = y

        img = img[lx:rx, by:upy]

        cropped_data.append(img)

    return cropped_data
\$\endgroup\$
  • \$\begingroup\$ You have tagged this question as opencv, but it isn't clear that there is any use of OpenCV in your code. Can you clarify? \$\endgroup\$ – 200_success Jun 24 '16 at 1:36
  • \$\begingroup\$ I normally use cv2 to resize it afterwards. I can use Cv2 methods if theres a quick way on it! Maybe i tagged with the wrong reasons.. But yes, i do use opencv and cv2 for python. \$\endgroup\$ – KenobiShan Jun 24 '16 at 1:39
  • \$\begingroup\$ Generally, as I can see in your data, what you want to remove is much less than what you need to keep. So I'd suggest not to scan the whole image to detect all non-black pixels, but rather scan all four edges line by line, to detect black stripes to be removed – and break the scan as soon as a non-black pixel is found. Note that those stripes overlap at corners, you may want to avoid scanning those overlap areas twice. However, it is still a very ineffective scanning pixel by pixel... \$\endgroup\$ – CiaPan Jun 24 '16 at 9:50
18
\$\begingroup\$

Vectorization with NumPy

When read with cv2.imread or skimage.io.imread or scipy.misc.imread, you would already have the image data as a NumPy array. Now, NumPy supports various vectorization capabilities, which we can use to speed up things quite a bit.

I. Crop to remove all black rows and columns across entire image

To solve our case, one method would be to look for rows and columns that have at least one pixel along rows and columns that is greater than some lower limit or threshold as a pixel value. So, if you are sure that the black areas are absolutely zeros, you can set that threshold as 0. Thus, if img represents the image data, you would have correspondingly two boolean arrays : (img>tol).any(1) and (img>tol).any(0).

Next up, you can use these boolean arrays to index into the image data for extraction of valid bounding box using broadcasted indexing with np._ix -

np.ix_((img>tol).any(1),(img>tol).any(0))

Finally, we index into image data with it for the final extracted data, which is the required bounding box data.

To sum up, the final implementation would be -

def crop_image(img,tol=0):
    # img is 2D image data
    # tol  is tolerance
    mask = img>tol
    return img[np.ix_(mask.any(1),mask.any(0))]

Sample results

1] With tolerance = 0 :

enter image description here

2] With tolerance = 80 (tighter) :

enter image description here

II. Crop while keeping the inner all black rows or columns

To crop the image while keeping the inner all black rows or columns, the implementation would be close to the previous method. The basic idea here would be getting the start, stop indices along rows and columns that decide the bounding box. We will start off with the same mask of ANY match along rows and columns as used in the previous one. Then, argmax would be useful to get start and stop indices of those matches along rows and cols. We will use these indices to slice the 2D input array, which is the desired cropped image output. The implementation would look something like this -

def crop_image_only_outside(img,tol=0):
    # img is 2D image data
    # tol  is tolerance
    mask = img>tol
    m,n = img.shape
    mask0,mask1 = mask.any(0),mask.any(1)
    col_start,col_end = mask0.argmax(),n-mask0[::-1].argmax()-1
    row_start,row_end = mask1.argmax(),m-mask1[::-1].argmax()-1
    return img[row_start:row_end,col_start:col_end]

Sample run -

Input :

enter image description here

Output :

enter image description here


Benchmarking

Since we are talking about performance in this Q&A, let's test out how this method works in comparison to others.

@Gareth Rees's solution is another vectorized one that finds all indices and then slices the input array. Finding all indices could become costly. We will try to time and see how much would that affect the performance. we will use the sample data used in the earlier section -

# @Gareth Rees's solution
def crop_with_argwhere(image):
    # Mask of non-black pixels (assuming image has a single channel).
    mask = image > 0

    # Coordinates of non-black pixels.
    coords = np.argwhere(mask)

    # Bounding box of non-black pixels.
    x0, y0 = coords.min(axis=0)
    x1, y1 = coords.max(axis=0) + 1   # slices are exclusive at the top

    # Get the contents of the bounding box.
    cropped = image[x0:x1, y0:y1]
    return cropped

Timings -

# Import the "4" digit image from previous section
In [50]: from skimage import io
    ...: im = io.imread('https://i.stack.imgur.com/tmdiH.png')

# @Gareth Rees's solution
In [51]: %timeit crop_with_argwhere(im)
1000 loops, best of 3: 1.4 ms per loop

In [52]: %timeit crop_image_only_outside(im,tol=0)
10000 loops, best of 3: 81.8 µs per loop

The memory efficiency with crop_image_only_outside is noticeable on performance.


Extend to generic 2D or 3D image data cases

Assuming we are looking to check for ALL matches across all channels along the last dimension/axis, the extension would be simply performing numpy.all reduction along the last axis. Hence, we would have generic solutions to handle both 2D and 3D image data cases like so -

def crop_image(img,tol=0):
    # img is 2D or 3D image data
    # tol  is tolerance
    mask = img>tol
    if img.ndim==3:
        mask = mask.all(2)
    mask0,mask1 = mask.any(0),mask.any(1)
    return img[np.ix_(mask0,mask1)]

def crop_image_only_outside(img,tol=0):
    # img is 2D or 3D image data
    # tol  is tolerance
    mask = img>tol
    if img.ndim==3:
        mask = mask.all(2)
    m,n = mask.shape
    mask0,mask1 = mask.any(0),mask.any(1)
    col_start,col_end = mask0.argmax(),n-mask0[::-1].argmax()-1
    row_start,row_end = mask1.argmax(),m-mask1[::-1].argmax()-1
    return img[row_start:row_end,col_start:col_end]
\$\endgroup\$
  • 1
    \$\begingroup\$ How does this work if the non-black part of the image is disconnected? For example, what if there are some rows (or columns) in the middle of the image that are completely black? The OP would like those parts of the image to be included in the crop, but the code in this answer will exclude them. \$\endgroup\$ – Gareth Rees Jun 24 '16 at 10:53
  • \$\begingroup\$ @ScientistGirl Glad to hear that! Just curious to what kind of speedups you might be getting with the proposed code, if you could compile for few test cases? Thanks! :) \$\endgroup\$ – Divakar Jun 24 '16 at 19:12
19
\$\begingroup\$

As you've discovered, looping over individual pixels in Python is very slow. You need to organize your computation so that it uses a series of NumPy (or SciPy, or Scikit-Image, or OpenCV) operations on the whole image.

In this case, you could use numpy.argwhere to find the bounding box of the non-black regions:

# Mask of non-black pixels (assuming image has a single channel).
mask = image > 0

# Coordinates of non-black pixels.
coords = np.argwhere(mask)

# Bounding box of non-black pixels.
x0, y0 = coords.min(axis=0)
x1, y1 = coords.max(axis=0) + 1   # slices are exclusive at the top

# Get the contents of the bounding box.
cropped = image[x0:x1, y0:y1]

(Note that this relies on there being some non-black pixels; if the whole image is black, then coords will be empty and you'll have to find something else to do in that case.)

\$\endgroup\$
  • \$\begingroup\$ That's a very efficient way of doing this. But as we should refer to the image coordinate, I guess x0 in the code should be y0, the same convention applies to x1, y0 and y1. \$\endgroup\$ – Kulbear May 7 '18 at 7:22
  • \$\begingroup\$ @Kulbear: That's right: if the image is stored in row-major order (as it usually is in NumPy) then it would make sense to swap the names x and y. \$\endgroup\$ – Gareth Rees May 7 '18 at 9:05
  • \$\begingroup\$ It would be nice if you could provide some code for images with more than one channel :) \$\endgroup\$ – maniac Jul 31 '18 at 19:47
  • \$\begingroup\$ @maniac: That might make a good question for Stack Overflow. \$\endgroup\$ – Gareth Rees Jul 31 '18 at 20:43
  • 1
    \$\begingroup\$ I believe this is a better implementation of crop, than the one in accepted answer. This version crops only external area of the image, and does not touch 'empty' areas inside the border of peripheral pixels. For example the version above crops image of this: ' ( x ) ' into this '(x)'. \$\endgroup\$ – krafter Sep 7 '18 at 9:06

protected by Jamal Jul 20 at 3:23

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.