10

有关图像压缩的文章通常侧重于在给定固定压缩比的情况下生成最佳图像质量 (PSNR)。我很好奇在给定最大允许的每像素误差的情况下获得最佳压缩比。我的直觉是贪婪地删除转换后的数据中的最小系数，跟踪我造成的错误，直到在不超过最大错误的情况下无法再删除。但我找不到任何文件来证实这一点。谁能指出我关于这个问题的参考？

编辑

让我提供更多细节。我正在尝试压缩来自 3D 扫描仪的深度图像，而不是常规图像。颜色不是一个因素。深度图像往往具有大的平滑块，但准确的不连续性很重要。一些像素将是空的 - 超出扫描仪的范围或低置信水平 - 并且不需要压缩。

在此处输入图像描述

该算法需要快速运行——最好像 Microsoft Kinect 那样以 30 fps 的速度运行，或者至少在 100 毫秒范围内的某个地方。该算法将包含在我分发的库中。我更喜欢最小化依赖关系，因此我可以在相当少量的代码中实现自己的压缩方案是更可取的。

4

7 回答 7

1

“贪婪地删除最小的系数”让我想起了 SVD 压缩，您使用与前 k 个最大特征值相关的数据来近似数据。其余较小的特征值不包含重要信息，可以丢弃。
大 k -> 高质量，低压缩
小 k -> 低质量，高压缩

（免责声明：我不知道我在说什么，但它可能会有所帮助）

编辑：
这是 SVD 压缩的更好说明

于 2013-01-26T22:48:46.153 回答
1

如果您提出的问题，我不知道有任何参考资料。

但是，我能想到的一个方向是使用优化技术来选择最佳系数。在这方面可以使用遗传算法、爬山、模拟歼灭等技术。

鉴于我在遗传算法方面有经验，我可以建议以下过程。如果您不了解遗传算法，我建议您阅读有关遗传算法的 wiki 页面。

你的问题可以被认为是选择了一个系数子集，它给出了最小的重建误差。假设有 N 个系数。很容易确定有 2^N 个子集。每个子集可以用 N 个二进制数上的字符串表示。例如，对于 N=5，字符串 11101 表示所选子集包含除 coeff4 之外的所有 coeff。使用遗传算法，可以找到最佳的钻头。目标函数可以选择为重建信号和原始信号之间的绝对误差。但是，我知道当所有的系数都被取走时，你可能会得到一个零错误。

为了解决这个问题，您可以选择使用适当的函数来调制目标函数，该函数不鼓励目标函数值接近零，并且是阈值后的单调递增函数。像 | 这样的函数 日志（\epsion + f）| 可能就足够了。

如果你觉得我的建议很有趣，请告诉我。我有一个遗传算法的实现。但它是根据我的需要量身定制的，你可能无法适应这个问题。我愿意与您一起解决这个问题，因为这个问题似乎很有趣。

请让我知道。

于 2013-02-05T11:07:54.770 回答
1

我认为您非常接近解决方案，但是我认为您应该注意一个问题。因为不同的小波系数对应不同尺度（和位移）的函数，所以消除特定系数引入的误差不仅取决于它的值，还取决于它的位置（尤其是尺度），所以系数的权重应该是类似于w(c) = amp(c) * F(scale, shift)其中 amp(c) 是系数的幅度，而 F 是取决于压缩数据的函数。当您确定将问题简化为背包问题的权重时，可以通过多种方式解决（例如重新排序系数并消除最小的系数，直到您在受相应函数影响的像素上获得阈值误差）。困难的部分是确定F(scale,shift). 您可以通过以下方式进行操作。如果您正在压缩的数据相对稳定（例如监控视频），您可以将 F 估计为接收到不可接受的错误的中间概率，以消除具有给定比例的分量并从小波分解中偏移。因此，您可以对历史数据执行 SVD（或 PCA）分解，并将“F(scale, shift)”计算为具有给定比例的组件的标量积的加权（权重等于特征值）总和，并转移到 F(scale,shift) = summ eValue(i) * (w(scale,shift) * eVector(i))eValue 所在的特征向量是对应于特征向量的特征值 - eVector(i)，w(scale,shift) 是具有给定比例和位移的小波函数。

于 2013-02-05T11:37:19.430 回答
1

迭代地评估不同的系数集不会帮助您实现在生成帧时尽快压缩帧的目标，也不会帮助您保持较低的复杂性。

深度图与强度图的不同之处在于可以帮助您的多种方式。

  1. 游程编码可以非常有效地处理大面积的“无数据”。
  2. 减去固定噪声后，强度图像中的测量误差在整个图像中是恒定的，但来自 Kinect 和立体视觉系统的深度图的误差会随着深度的反函数而增加。如果这些是您的目标扫描仪，那么您可以使用有损压缩来获得更接近的像素 - 因为您的有损函数引入的误差与传感器误差无关，所以在您的有损函数的误差大于传感器误差之前，总误差不会增加.
  3. 微软的一个团队在一个非常低损失的算法上取得了很大的成功，该算法严重依赖运行长度编码（请参阅此处的论文），以更好的压缩和卓越的性能击败了 JPEG 2000；然而，他们的部分成功似乎源于他们的传感器产生的相对粗糙的深度图。如果您的目标是 Kinect，您可能会发现很难改进他们的方法。
于 2013-02-06T16:05:28.570 回答
1

我认为您正在寻找类似JPEG-LS算法的东西，它试图限制最大数量的像素错误。尽管它主要是为压缩自然或医学图像而设计的，而不是为深度图像（更平滑）而设计的。

  • 术语“近无损压缩”是指一种有损算法，其中每个重建图像样本与对应的原始图像样本的差异不超过预先指定的值，即（通常很小的）“损失”。无损压缩对应loss=0。链接到原始参考
于 2013-02-07T08:56:47.603 回答
1

此答案无法满足您对参考的要求，但作为评论发布太长了。

首先，计算机生成图像的深度缓冲区压缩可能适用于您的情况。通常这种压缩是在硬件级别使用透明接口完成的，因此它通常被设计为简单快速。鉴于此，搜索深度缓冲区压缩可能是值得的。

对于基于变换的压缩器（DCT、小波等），您将遇到的主要问题之一是没有简单的方法来找到满足您的硬最大误差标准的紧凑系数。（你最终遇到的问题看起来很像线性规划。小波可以在它们的大多数基向量中具有局部行为，这可能会有所帮助，但它仍然相当不方便。）为了达到你想要的精度，你可能需要添加另一个细化步骤，但这也会增加更多的计算时间和复杂性，并且会引入另一层不完美的熵编码，从而导致压缩效率的损失。

你想要的更像是无损压缩而不是有损压缩。在这种情况下，一种方法是简单地丢弃错误阈值以下的位：如果您的最大允许错误为 X 并且您的深度表示为整数，则将您的深度整数除以 X，然后应用无损压缩。

您面临的另一个问题是深度的表示——根据您的情况，它可能是浮点数、整数、可能在投影坐标系中，甚至更奇怪。

鉴于这些限制，我推荐像 BTPC这样的方案，因为它允许更容易适应的类小波方案，其中错误更清晰地定位，更容易理解和解释。此外，BTPC 对多种类型的图像表现出很强的抵抗力，并且能够以低保真度损失处理连续渐变和锐利边缘——这正是您正在寻找的那种特征。

由于 BTPC 是预测性的，因此深度格式的存储方式并不重要——您只需修改预测器以将坐标系和数字类型（整数与浮点数）考虑在内。

由于 BTPC 不做太多的数学运算，它也可以在通用 CPU 上运行得非常快，尽管它可能不像您希望的那样容易矢量化。（听起来你可能正在做低级优化游戏编程，所以这对你来说可能是一个认真的考虑。）

如果您正在寻找更容易实现的东西，我建议您使用带有Golomb-Rice编码器的“过滤器”类型的方法（类似于PNG ）。您可以编码到“足够好”的程度，而不是完美地编码增量以结束无损压缩。与量化然后无损编码风格的压缩器相比，这样做的好处是您可以潜在地保持更多的连续性。

于 2013-02-12T15:25:25.460 回答
0

我会尝试预处理图像，然后使用通用方法（例如 PNG）进行压缩。

PNG的预处理（首先阅读此）

for y in 1..height
  for x in 1..width
    if(abs(A[y][x-1] - A[y][x]) < threshold)
       A[y][x] = A[y][x-1]
    elsif (abs(A[y-1][x] - A[y][x]) < threshold)
       A[y][x] = A[y-1][x]
于 2013-02-09T23:01:06.690 回答