图像的差异/补丁

Question

我正在写一个项目，需要通过网络传输一组相似的图像。为了加快速度，我考虑采用大多数电影编解码器使用的方法，即拥有关键帧，然后只发送更改部分。

现在，我手头有一组 BufferedImage ，所以类比于文本文件，我基本上只想对它们进行差异化处理并发送补丁。但是我之前从未真正处理过图像，所以如果这样做的话，效果可能不太好。

那么，实现这样的功能的最佳方式是什么？还是已经有好的实现方式了？

我猜存储图像到字节数组中并进行二进制差异处理可能不会非常有效。

编辑：我需要流式传输这些图像。 编辑2：这不是关于具体实现的细节，而是：最有效的算法思路是什么？例如只处理5个像素块，如果像素变化很小，肉眼看不出来就忽略掉（我可以接受一些质量损失）。

- lawl0r

---

也许你可以让现有的压缩算法为你完成工作，将图像打包成一个大图像（并以任何常见格式压缩它），或者打包成zip（或类似）存档。 - tjollans

我们在谈论什么类型的流式传输？ - Leonard Brünings

@Damokles 好的，到我知道发生了什么变化时，我已经发送了关键帧。 - lawl0r

有很多相同颜色的小块，大约1000x1000像素缩小，至少1秒比3秒更好，这对于100kbps的上行速度来说真的很困难。 - lawl0r

你已经尝试过什么了吗？ - Jesse Webb

Answer 1

一种简单的方法是对两个图像执行异或操作，这将显示相同的像素（将为零）和已更改的像素（非零）。

如果您不关心几乎无法察觉的差异，可以使用“减法”混合，然后右移以丢弃一到两个位的差异。

然后，您可以计算出边界（可能是一个简单的矩形），并仅传输增量。增量可能包含很多零或最多几个右侧位有差异的字节，即它具有低的“熵”，这意味着使用当代压缩算法理论上应高度可压缩。

在接收端，反向过程同样简单。给定增量和边界框，解压缩增量，然后将其应用于先前/现有图像的受影响区域（XOR、左移再加）。

对于一种更为复杂的无损方法，请查看动画GIF/PNG如何制作动画以及用于计算/编码帧间增量信息的算法。例如，请参见What's the best way to make an animated GIF using an algorithm?。

对于更加复杂的方法，当处理真实世界的图像并且你愿意采用有损压缩的方法时——你已经暗示了它。例如，看看视频编解码器如何对帧进行编码/传输MPEG Video Encoding。

不言而喻，因为在编码/解码过程的复杂性和传输数据大小的减少之间存在权衡，在某些时候你将不得不决定计算上的额外开销是否值得节省传输成本。

- Alistair A. Israel

Answer 2

您可以使用getRGB（int x，int y）迭代缓冲图像的所有像素。

for (int x = 0; x < img.getWidth(); ++x)
{
    for (int y = 0; y < img.getHeight(); ++y)
    {
        int oldARGB = oldImg.getRGB(x, y);
        int newARGB = img.getRGB(x, y);
        if (oldARGB != newARGB)
        {
            // handle the diffrence
        }
    }

}

- Martijn Courteaux

---

处理差异是我认为最有趣的部分。您需要能够以高效的方式传输差异。 - Leonard Brünings

感谢您的回答，但我的问题更多关注于一个好的算法应该是什么样子的。我的意思是我可以接受一定的质量损失。所以如果alpha值只改变了一个，我就不需要更新像素。最好的方法是像操作5x5像素块之类的东西吗？是的，处理这种差异是我真正关心的。 - lawl0r

你可以创建一个新的BufferedImage（delta），最初所有像素都是100％透明的（或其他固定值），并将所有更改的像素复制到该图像中。将其作为PNG发送，并在接收端循环遍历所有像素，将不透明像素复制过去。 - tjollans

如果alpha值变化了一个单位，我就不需要更新像素。你可以通过在服务器端保留客户端所看到的图像的副本，并且只包含改变的像素（例如jollybox的方法），如果参考和实际的RGB差异超过某个阈值，那么这种方式可能是相当有效的。 - Kevin K

Answer 3

我有一个想法，实际上这非常简单。逐个比较像素。

如果像素相等，则保存为RGBA（0，0，0，0）。 然后将差异存储为PNG。

这是演示结果。 差异非常小。

stackoverflow说您需要至少10个声望才能发布图像。所以我只能在这里发布图像地址。

http://oi61.tinypic.com/2vs5ifl.jpg

- codeskyblue

Answer 4

根据您想要投入的工作量，我建议一个相当简单的解决方案，将这些图像保存为位图，然后让7z对其进行压缩。然后发送存档文件。

- Leonard Brünings

---

是的，不幸的是这不是我要找的，我真的需要进行“diff”比较，因为它需要快速完成。 - lawl0r

Answer 5

如果你不介意一些质量下降，并且希望在带宽方面有一个真正高效的解决方案，而又不需要太多手动工作，你也可以使用真正的电影编解码器对图像进行编码。特别是如果你有一个GPU来卸载计算，这种方法在计算方面也非常高效。

- mschwaig

Answer 6

你的时间最好花在开发应用程序上，如果有问题再评估性能改进。我猜整个过程都是YAGNI。

为了加快速度，我考虑做...

这不是一个要求，只是一个“如果...那该多酷啊”的想法。随着今天的网络速度，即使传输几百兆字节也可以在不到一分钟内完成。

- Jesse Webb

---

我有2 MBps的上行速度。如果糟糕的互联网需要这么复杂的代码，也许简单的解决方案是购买更好的互联网套餐？如果我的回答不符合您的期望，我很抱歉，我只是想提供一个不同的观点。 - Jesse Webb