Algorithm to split an image into smaller images reducing the amount of whitespace and specifying maximum amount of rectangles

Question

I am looking for an algorithm which can split an image into smaller images, with some constraints. One constraint is to use the least amount of "whitespace" meaning empty pixels. And the other is to specify a maximum amount of images to split it into.

For example lets look at the below image. There is a lot of "whitespace" in it. I would like to divide this images into a few other images so i can reduce the amount of memory this image occupies, and also to reduce the amount of "drawing" this image will take.

.=transparent pixel
x=colored pixel

....................
.xxxxxxxxxxx........
...xxxx...xxxxxx....
.............xxxxx..
...............xxx..
...............xxx..
....................
..xxxxxx............
.....xxxxxxxxxxx....
.........xxxxxxxxxx.
....................

Let's assume i want the image to be split into a maximum of 4 images, a possible sollution would be as drawn below.

....................
.111111111111111....
.111111111111111....
.............22222..
.............22222.
.............22222..
....................
..3333333...........
..33333334444444444.
.........4444444444.
....................

Does anyone have an algorithm for this, or knows the name of an algorithm which does this? I have been looking for a while and found some related algorithms, but the algorithms i found don't account for the whitespace e.g. they split the image into rectangles covering only the non transparent pixels, resulting in a huge amount of rectangles. The real life data i am working with are images of 1024*1024 pixels and i would prefer to reduce them into a maximum of 16 parts. the trick is to extract the 16 images using the least amount of whitespace.

Answer 1

I'd go with the same algorithm as ravloony, but with a slight and important modification, using a "crop" operation that looks for the minimal/maximal columns and rows that aren't completely empty and discarding the rest.

In practice, the crop operation would get a X*Y region as input and would output 4 integers - the coordinates of the smallest rectangle that contains all the used pixels of the region. This can also be used to detect and discard empty regions.

Example

....................
.xxxxxxxxxxx........     xxxxxxxxxxx.......
...xxxx...xxxxxx....     ..xxxx...xxxxxx...
.............xxxxx..     ............xxxxx.
...............xxx.. =>  ..............xxx. (first crop)
...............xxx..     ..............xxx.
....................     ..................
..xxxxxx............     .xxxxxx...........
.....xxxxxxxxxxx....     ....xxxxxxxxxxx...
.........xxxxxxxxxx.     ........xxxxxxxxxx
....................

Now divide the image into NxN parts (using N=4 here) and use the crop operation on each of the parts:

xxxxx|xxxxx|x....|
..xxx|x...x|xxxxx|
---------------------
     |     |  xxx|xx
     |     |  ..x|xx
---------------------
     |     |    x|xx
     |     |     |
---------------------
 xxxx|xx...|     |
 ...x|xxxxx|xxxxx|
     |...xx|xxxxx|xxx

For this example, we get 10+10+10+6+4+1+2+8+15+10+3=79 pixels instead of 21*11=231 which is only 34,2%. Note that this happens to be the same amount as with your handcrafted 4-part segmentation (30+15+14+20=79)!

Conclusions

Of course there will be some additional data to keep track of the position and size of the 16 parts for each and it won't always give best results, but I think it's a nice compromise between speed and savings and the algorithm is easy to write and maintain.

About the additional data: Images of size 1024x1024 and splitting into 4x4 parts would give you the possibility to use 4 byte values to store each rectangle, so additional data size would be only 16*4 = 64 bytes - regarding this, you should perhaps consider to increase your 16 part maximum unless it will slow down some other part like the drawing heavily.

Worst cases

Worst cases for this algorithm would be parts with some pixels at or near the edges set, like these:

x......x    xxxxxxxx    xx......
........    ........    x.......
........    ........    ........
x......x    ...x....    .......x

Several solutions for these come to my mind:

• Splitting the region again (ending up with a quadtree implementation)
• Using some additional step to detect completely empty rectangles in the inside.
• Translating the grid that defines the parts a bit