Algorithm for dividing the image into smaller images, reducing the number of spaces and determining the maximum number of rectangles

Question

I am looking for an algorithm that can split an image into smaller images with some limitations. One limitation is to use the least number of spaces meaning empty pixels. And the other is to specify the maximum number of images to split it into.

For example, consider the image below. There are many “gaps” in it. I would like to divide these images into several other images so that I can reduce the amount of memory that this image occupies, as well as reduce the amount of "drawing" of this image.

.=transparent pixel x=colored pixel .................... .xxxxxxxxxxx........ ...xxxx...xxxxxx.... .............xxxxx.. ...............xxx.. ...............xxx.. .................... ..xxxxxx............ .....xxxxxxxxxxx.... .........xxxxxxxxxx. .................... 

Suppose I want the image to be split into a maximum of 4 images, the possible resolution would be as shown below.

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

Does anyone have an algorithm for this, or knows the name of the algorithm that does this? I searched for a while and found some related algorithms, but the found algorithms do not account for spaces, for example. they split the image into rectangles covering only opaque pixels, which leads to a huge number of rectangles. The real life data I'm working with is images with a resolution of 1024 * 1024 pixels, and I would prefer to reduce them to 16 parts. the trick is to extract 16 images using the least amount of spaces.

Answer 1

I would go with the same algorithm as ravloony , but with a small and important modification, using the "crop" operation, which searches for minimum / maximum columns and rows that are not completely empty and discard the rest.

In practice, the cropping operation will receive the X*Y as input and print 4 integers - the coordinates of the smallest rectangle that contains all the pixels in the region that are used. It can also be used to detect and remove blank areas.

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 part:

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

In 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%. Please note that this will be the same amount as with your 4-segment handmade segmentation (30 + 15 + 14 + 20 = 79)!

conclusions

Of course, there will be some additional data to track the position and size of 16 parts for each, and this will not always give the best results, but I think this is a good compromise between speed and economy, and the algorithm is easy to write and maintain.

About additional data: Images of size 1024x1024 and dividing into 4x4 parts will give you the opportunity to use 4 byte values ​​to store each rectangle, so the additional data size will be only 16 * 4 = 64 bytes - in this regard, you might consider increasing the maximum a maximum of 16 parts, unless it slows down any other part, like drawing to a large extent.

Worst cases

The worst cases for this algorithm would be parts with some pixels on or near set edges, such as:

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

Several solutions for this come to my mind:

• Division of area again (completion with quadrant implementation)
• Use an extra step to detect completely empty rectangles in the inside.
• Translation of a grid that defines parts a little

Answer 2

You want to write a duration compression or delta compression algorithm. Or do you want to use a spatial reference curve or spatial index. Sfc recursively subdivides the surface into 4 smaller tiles and reduces the complexity of 2 measurements to 1 size, thus simplifying the identification of white space. You want to see the Quadrree Nick hilbert-curve spatial index blog. You want to upload my php class hilbert curve to phpclasses.org.

Answer 3

I would look at it recursively, each time breaking in half or four, until you reach the level you need (for you 2 → 4 ^ 2 = 16). At the bottom level, check the empty squares and discard them. Of course, this gives a grid of rectangles proportional to the shape of the original image, rather than optimally positioned rectangles, but this can lead you to the right track.

Answer 4

My gut says that the perfect solution is akin to a knapsack problem and therefore computationally impractical. You can use some kind of heuristic to create a “good enough” solution.

You can use the fill fill algorithm to select connected areas of opaque pixels. As a first cut, this will give you a rectangle for each disjoint region of color. If you have more rectangles available in your budget, you can try to cut them differently to see which gives you the highest “density” of color pixels.

Answer 5

Sorry for the late comment, but it took me a while to find a “good” algorithm.

After some research, I am going to execute the following solution. First I use Quadtree and do SplitAndMerge. I First separate the "Space". Then I merge all the rectangles together into the largest rectangles.

After that, I sort the quadrants by the size of the area, keeping only the largest area x. (Thus, the largest gaps remain). But I do not want spaces, I want everything except spaces, so I invert Quadtree and do SplitAndMerge again. Then extract the remaining rectangles from the image and lay them out in the final image.

This gave me great results, significantly reducing the size of the image (because there were a lot of gaps in my images) and kept the time to minimize them.