Image auto-cropper

By
Back to image territory, to prove again that the 2D land is awesome. :-)



In this post we're going to talk about image cropping and how to do this generically for any background color, even for backgrounds that have variations of the same color.

# Finding the background color

First, we need an algorithm to detect the background color, then we need to find where the background ends in all four parts of the image.

The background color detection is the simplest part. We can take a pixel from one corner of the image and assume that this is the background color.

To validate or invalidate this assumption, we have to test each edge of the image, pixel by pixel, to see if all pixels are about the same color. A clever way is by sampling pixels in larger steps and spiraling-in slowly until we checked all the pixels from a given row or column.

For example, if we have a row of 100 pixels wide, the steps that we'll take in order to check all the edge pixels, are the following:

10 20 30 40 50 60 70 80 90 100
 9 18 27 36 45 54 63 72 81 99
 8 16 24 32 48 56 64 88 96
 7 14 21 28 35 42 49 77 84 91 98
 6 12 66 78
 5 15 25 55 65 75 85 95
 4 44 52 68 76 92
 3 33 39 51 57 69 87 93
 2 22 26 34 38 46 58 62 74 82 86 94
 1 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

This sequence of steps gives us a good overall performance improvement, because when it first encounters a pixel which doesn't match the assumed background color, it simply stops. However, this optimization is fully optional and is beneficial only for pictures that cannot be cropped, so it will fail faster.

# Comparisons to the background color

The background color can be a variation of a color, not an exact color everywhere, so the validation needs to be flexible enough to allow us cropping such images.

One way of doing this, is the following: compare two RGB hashes color-to-color and return "true" when all the differences are within the allowed tolerance.

Example:

(abs(a["R"] - b["R"]) <= tolerance) &&
(abs(a["G"] - b["G"]) <= tolerance) &&
(abs(a["B"] - b["B"]) <= tolerance)

A good value for tolerance may be anywhere from 5 to 50, or even higher.

# Finding the end of the background

After all the edges passed the test, we are ready to go to the next step, which is the actual cropping.

In this step, we need to find the boundary points to know how much the image can be cropped. This step is very similar with the background identification step, but instead of trying to validate the background color, now we try to do the opposite: find the points where the background ends.

The steps of the algorithm are the following:
  1. check each row from 1 to height, from 1 to width
  2. check each column from 1 to width, from 1 to height
In each step we test both the top and bottom rows, as well as left and right columns. In the first step, we find the (top, bottom) points, while in the second step we find the (left, right) points.


# Example

To illustrate this, please consider the following 26x8 ASCII image.

+--------------------------+
|                          |
|          *               |
|         \|/              |
|        __|__             |
|       /=/~\=\            |
|       \=\~/=/            |
|        \=_=/             |
|                          |
+--------------------------+

In the first step, we check the rows, from top and bottom and remember the y-values where the background ends from both sides.

+--------------------------+
|                          |
|          *               |
|         \|/              |
|        __|__             |
|       /=/~\=\            |
|       \=\~/=/            |
|        \=_=/             |
|                          |
+--------------------------+

The values for top and bottom are (1, 8).

Now, we have to check the left and right columns, starting at the edges, getting closer and closer to each other.

+--------------------------+
|                          |
|          *               |
|         \|/              |
|        __|__             |
|       /=/~\=\            |
|       \=\~/=/            |
|        \=_=/             |
|                          |
+--------------------------+

When the algorithm encounters a pixel only from one side that has a different color than the background color, it will continue to check the pixels only from the other side.

+--------------------------+
|                          |
|          *               |
|         \|/              |
|        __|__             |
|       /=/~\=\            |
|       \=\~/=/            |
|        \=_=/             |
|                          |
+--------------------------+

At this point, we have the value only for the left-side, which is 7. The algorithm continues until it finds a value for the right-side as well.

+--------------------------+
|                          |
|          *               |
|         \|/              |
|        __|__             |
|       /=/~\=\            |
|       \=\~/=/            |
|        \=_=/             |
|                          |
+--------------------------+

Finally, the right value (14) is found. Having all the required points, we can now crop the image.

  • The start point is: (left, top)
  • The end point is: (right, bottom)

In the end, we have the cropped image as expected:

+-------+
|   *   |
|  \|/  |
| __|__ |
|/=/~\=\|
|\=\~/=/|
| \=_=/ |
+-------+

# Conclusion

Being able to crop images automatically, regardless of the background color and without any human interaction, it's pretty cool and it may be useful sometimes as well.

# Implementation

Comments

Post a Comment