将图像拆分为较小图像的算法，减少空白量并指定最大矩形数量

Question

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

例如让我们看下图。其中有很多“空白”。我想将这张图片分成几张其他图片，这样我就可以减少这张图片占用的内存量，也可以减少这张图片“绘制”的数量。

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

Answer 1

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

在实践中，裁剪操作将获取一个 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

我想到了几种解决方案:

• 再次拆分区域(结束 使用四叉树实现)
• 使用一些额外的步骤来检测 中完全空的矩形 里面。
• 稍微翻译一下定义部分的网格