c++ - 将 1bit/bw/二进制图像中的像素打包到盒子中

Question

我需要一种算法，从 1 位二维图像(混合 1 和 0 的二维矩阵)返回矩形(每个角的 x，y 坐标)，这些矩形包含等于零的像素，使用最少的盒子。

所以对于像这样的图像

0000000
1111111
1111111
1111110
1111100
0000000

它会返回类似的东西

Rectangle 1 ((0,0),(0,1),(7,0),(7,1))
Rectangle 2 ((6,3),(7,3),(7,4),(6,4))
Rectangle 3 ((5,4),(7,4),(7,6),(5,6))
Rectangle 4 ((0,5),(0,6),(7,6),(7,5))

我觉得这个算法存在，但我无法用谷歌搜索或命名它。

Answer 1

我猜您正在寻找一种图像压缩算法。据我所知，没有保证最小矩形数的算法。

首先想到的是将像素数据作为一维数组并使用游程编码对其进行压缩。图像往往具有相当大的相似颜色像素组，因此这应该可以节省一些数据。

除此之外，您还可以做一些事情来进一步增加信息密度:

• 按照您的建议，从全白且仅存储黑色像素的图像开始
• 如果编码时间不是问题，请对白色和黑色像素都运行编码，然后存储需要较少数据的那个，并使用一位来存储图像应该以黑色背景还是白色背景开始。

有一些算法尝试在二维中执行此操作，但这似乎要复杂得多。这是我在该主题上发现的一种尝试: https://pdfs.semanticscholar.org/d09a/62ea3472352bf7bbe873677cd81f348206cc.pdf