6

我正在寻找一种算法，可以将图像分割成更小的图像，但有一些限制。一个限制是使用最少的“空白”，意思是空像素。另一种是指定最大数量的图像来分割它。

例如，让我们看看下面的图像。里面有很多“空白”。我想把这些图像分成几个其他的图像，这样我就可以减少这个图像占用的内存量，也可以减少这个图像需要的“绘图”量。

.=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 个图像。

4

5 回答 5

2

我会使用与ravloony相同的算法相同的算法，但进行了轻微而重要的修改，使用“裁剪”操作查找不完全为空的最小/最大列和行并丢弃其余部分。

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

例子

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

现在将图像分成 NxN 部分（这里使用 N=4）并对每个部分使用裁剪操作：

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

对于这个例子，我们得到 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 个部分，除非它会严重减慢绘图等其他部分的速度。

最坏的情况

该算法的最坏情况是部分像素位于或靠近边缘集，如下所示：

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

我想到了几个解决方案：

  • 再次分割区域（以四叉树实现结束）
  • 使用一些额外的步骤来检测内部完全空的矩形。
  • 稍微翻译一下定义部分的网格
于 2011-05-13T16:17:01.853 回答
0

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.

于 2011-05-23T20:49:11.187 回答
0

您想编写运行长度或增量压缩算法。或者您想使用空间归档曲线或空间索引。sfc 递归地将表面细分为更小的 4 个图块，并将 2 维的复杂性降低到 1 维，从而更容易识别空白。您想查找 Nick 的希尔伯特曲线四叉树空间索引博客。你想在 phpclasses.org 下载我的 php 类希尔伯特曲线。

于 2011-05-13T13:23:03.167 回答
0

我的直觉说，理想的解决方案类似于背包问题，因此在计算上是不切实际的。您也许可以使用某种启发式方法来生成“足够好”的解决方案。

您可以使用洪水填充算法来选择非透明像素的连接区域。作为第一次切割，这将为每个不相交的颜色区域提供一个矩形。如果您的预算中有更多可用的矩形，您可以尝试以不同的方式切割它们，看看哪个颜色像素的“密度”最高。

于 2011-05-13T16:34:47.030 回答
0

我会考虑递归地做，每次分成两半或四，直到你达到你想要的水平（对你来说 2 -> 4^2 = 16）。在底层检查空方块并丢弃它们。当然，这会为您提供与原始图像形状成比例的矩形网格，而不是最佳放置的矩形，但它可能会让您走上正确的轨道。

于 2011-05-13T13:58:28.020 回答