时间戳

首页 > 解决方案 > 将 1bit/bw/binary 图像中的像素打包到框中

c++ - 将 1bit/bw/binary 图像中的像素打包到框中

问题描述

我需要一种算法，它从 1 位 2D 图像（混合 1 和 0 的 2D 矩阵）返回矩形（每个角的 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))

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

标签： c++algorithm

解决方案

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

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

除此之外，您还可以做一些事情来进一步提高信息密度：

  • 就像你建议的那样，从一个完全白色的图像开始，只存储黑色像素
  • 如果编码时间不是问题，请在白色和黑色像素上运行编码，然后存储需要较少数据的那个，并使用一位来存储图像应该以黑色还是白色背景开始。

有一些算法试图在二维中做到这一点，但这似乎要复杂得多。这是我在该主题上发现的一次尝试： https ://pdfs.semanticscholar.org/d09a/62ea3472352bf7bbe873677cd81f348206cc.pdf

推荐阅读