将图像分割成更小的图像的算法，减少空白量并指定最大矩形量
我正在寻找一种算法，可以将图像分割成更小的图像，但有一些限制。 一个限制是使用最少量的“空白”，即空像素。另一个是指定将其分割成的最大图像数量。
例如，让我们看一下下图。其中有很多“空白”。我想将此图像分成几个其他图像，这样我就可以减少该图像占用的内存量，并减少该图像所需的“绘制”量。
.=transparent pixel
x=colored pixel
....................
.xxxxxxxxxxx........
...xxxx...xxxxxx....
.............xxxxx..
...............xxx..
...............xxx..
....................
..xxxxxx............
.....xxxxxxxxxxx....
.........xxxxxxxxxx.
....................
假设我希望将图像最多分割为 4 个图像，可能的解决方案如下所示。
....................
.111111111111111....
.111111111111111....
.............22222..
.............22222.
.............22222..
....................
..3333333...........
..33333334444444444.
.........4444444444.
....................
有谁有这方面的算法，或者知道执行此操作的算法的名称？ 我已经寻找了一段时间并找到了一些相关的算法，但是我发现的算法没有考虑空白，例如它们将图像分割成仅覆盖非透明像素的矩形，从而产生大量的矩形。 我正在处理的现实生活数据是 1024*1024 像素的图像，我更愿意将它们减少到最多 16 个部分。诀窍是使用最少的空白提取 16 张图像。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
我会使用与 ravloony，但有一个轻微而重要的修改，使用“裁剪”操作来查找最小/最大列和行并不是完全空的，而是丢弃其余的。
实际上，裁剪操作将获取一个 X*Y 区域作为输入，并输出 4 个整数 - 包含该区域所有已使用像素的最小矩形的坐标。这也可用于检测和丢弃空白区域。
示例
现在将图像分为 NxN 部分（此处使用 N=4）并对每个部分使用裁剪操作：
对于此示例，我们得到 10+10+10+6+4+1+2+8+15+ 10+3=79 像素，而不是 21*11=231，仅为 34.2%。请注意，这恰好与您手工制作的 4 部分分割的数量相同 (30+15+14+20=79)！
结论
当然，会有一些额外的数据来跟踪每个部件的 16 个部件的位置和大小，并且它并不总是给出最佳结果，但我认为这是速度和节省之间的一个很好的折衷，并且该算法很容易编写和维护。
关于附加数据：大小为 1024x1024 的图像并分为 4x4 部分，您可以使用 4 字节值来存储每个矩形，因此附加数据大小仅为 16*4 = 64 字节 - 关于这一点，您也许应该考虑增加 16 个部分的最大值，除非它会严重减慢其他部分（例如绘图）的速度。
最坏的情况
该算法的最坏情况是在边缘处或附近设置了一些像素的部分，如下所示：
我想到了这些问题的几种解决方案：
使用四叉树实现）
完全空的矩形
里面。
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*Yregion 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
Now divide the image into NxN parts (using N=4 here) and use the crop operation on each of the parts:
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:
Several solutions for these come to my mind:
with a quadtree implementation)
completely empty rectangles in the
inside.
我会考虑递归地执行此操作，每次将其分成两半或四份，直到达到您想要的级别（对您来说 2 -> 4^2 = 16）。在底层检查空方块并丢弃它们。
当然，这会给你一个与原始图像的形状成比例的矩形网格，而不是最佳放置的矩形，但它可能会让你走上正确的轨道。
I would look at doing it recursively, each time splitting in half or into four, until you get to the level you want (for you 2 -> 4^2 = 16). At the bottom level check for empty squares and discard them.
Of course this gives you a grid of rectangles proportional to the shape of the original image, rather than optimally placed rectangles, but it might start you off on the right track.
我的直觉告诉我，理想的解决方案类似于背包问题，因此在计算上是不切实际的。您也许可以使用某种启发式方法来生成“足够好”的解决方案。
您可以使用洪水填充算法来选择非透明像素的连接区域。作为第一次切割，这将为每个不相交的颜色区域提供一个矩形。如果您的预算中有更多可用的矩形，您可以尝试以不同的方式切割它们，看看哪种方式可以提供最高的彩色像素“密度”。
My gut says that an ideal solution is akin to the knapsack problem and is thus computationally impractical. You may be able to use some sort of heuristic to generate a "good-enough" solution.
You could use a flood-fill algorithm to select connected regions of non-transparent pixels. As a first cut, that would give you a rectangle for each disjoint area of color. If you have more rectangles available in your budget, you could try cutting them in different ways to see which gives you the highest "density" of colored pixels.
您想要编写运行长度或增量压缩算法。或者您想使用空间归档曲线或空间索引。 sfc 递归地将表面细分为更小的 4 个图块，并将 2 维的复杂性降低到 1 维，从而更容易识别空白。您想要查找 Nick 的希尔伯特曲线四叉树空间索引博客。您想在 phpclasses.org 下载我的 php 类希尔伯特曲线。
You want to write a run-lenght or a delta compression algorithm. Or you want to use a space-filing-curve or a spatial-index. A sfc recursively subdivide the surface into smaller 4 tiles and reduce the complexity of 2 dimension to 1 dimension thus it makes it easier to identify white-space. You want to look for Nick's hilbert-curve quadtree spatial index blog. You want to download my php class hilbert curve at phpclasses.org.
抱歉这么晚发表评论，但我花了一些时间才找到一个“好的”算法。
经过一番研究后，我将寻求以下解决方案。
首先，我使用四叉树并执行 SplitAndMerge。我首先在“空白”上拆分。然后我将所有矩形合并成最大面积的矩形。
之后，我根据面积大小对四叉树进行排序，只保留最大的 x 面积。 （因此本质上保留最大的空白区域）。但我不想要空白，我想要除了空白之外的所有内容，所以我反转四叉树，并再次执行 SplitAndMerge 。然后从图像中提取剩余的矩形，并将它们装箱到最终图像中。
这给了我一些出色的结果，极大地减小了图像尺寸（因为我的图像中有很多空白），并将绘制它们的时间保持在最低限度。
Sorry for the late comment but it took me some time to find a "good" algorithm.
After some research i am going for the following solution.
First i use a Quadtree and do a SplitAndMerge. i Split on "Whitespace" first. Then i am merging all the rectangles together into the largest area rectangles.
After that i sort the quadtree on area size, only keeping the largest x area's. (So essentialy keeping the largest whitespace areas). But i don't want the whitespace, i want everything except the whitespace so i invert the Quadtree, and do a SplitAndMerge Again. Then extracting the remaining rectangles out of the image, and binpacking them in the final image.
This has given me some excellent results, reducing the image size drastically (because my images had a lot of whitespace in it), and keeping the time to draw them to a minimum.