算法的图像分割成更小的图像的空白减少的量，并指定矩形的最大量 [英] Algorithm to split an image into smaller images reducing the amount of whitespace and specifying maximum amount of rectangles

问题描述

我在寻找一种算法，可以分割图像分成更小的图像，有一些限制。 一个制约因素就是用最少的空白的意思是空像素。另一种是，以指定的图像将其分割成的最大量。

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.
....................

假设我想要的图像分割成最多4张图片，一个可能的sollution将如下绘制。

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.
....................

有没有人有一种算法这一点，或知道算法做到这一点的名字？ 我一直在寻找了一段时间，发现了一些相关的算法，但我发现算法不占空白，例如他们图象分成矩形覆盖只有非透明像素，产生了大量的矩形。 现实生活中的数据，我有工作是1024 * 1024像素的图像，我会preFER，以减少他们到最多16个部分。诀窍是使用最少量的空白，提取16个图像。

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.

推荐答案

我会使用相同的算法<一去href="http://stackoverflow.com/questions/5991302/algorithm-to-split-an-image-into-smaller-images-reducing-the-amount-of-whitespace/5993002#5993002">ravloony,但有轻微的和重要的修改，使用裁剪的操作，查找最小/最大列和行并不完全是空的，丢弃其余部分。

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.

在实践中，作物操作会得到一个 X * Y 区域作为输入，将输出4个整数 - 最小矩​​形的坐标，它包含了所有使用的像素该区域。这也可以用于检测和丢弃空的区域。

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.

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

现在将图像划分为N×N个部件（使用N = 4这里），并使用作物操作上每个部分：

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

有关这个例子中，我们得到了21 * 11 = 231这是只有34,2％10 + 10 + 10 + 6 + 4 + 1 + 2 + 8 + 15 + 10 + 3 = 79个像素，而不是。注意，这恰好是相同的量，与您的手工-4-部分分割（30 + 15 + 14 + 20 = 79）！

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)!

当然，会有一些额外的数据跟踪的16件为每个位置和大小，它不会永远是最好的结果，但我认为这是速度快，节约和算法之间有一个很好的平衡容易编写和维护。

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.

关于额外的数据：大小1024×1024和分割图像为4×4的部分会给你用4个字节的值来存储每个矩形的可能性，因此额外的数据的大小将只有16 * 4 = 64个字节 - 关于这一点，或许应该考虑增加16部分最大的，除非它会减慢其他部分，如绘画严重。

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

这篇关于算法的图像分割成更小的图像的空白减少的量，并指定矩形的最大量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！