optimization - 最优脏矩形集

Question

我在这里寻找一种算法，独立于特定的编程语言。

问题:

We have a 2-dimensional display area (think simple buffer of pixels). Periodically, some of the pixels are changed. We need to find a set of rectangles that encapsulate all changed pixels.

It would be trivial, but undesirable, to compute a single, potentially large, rectangle that encapsulates all changed pixels. We would rather have multiple, smaller, tight-fitting rectangles down to a specified minimum size (that is a variable which can be changed).

For example, suppose that within the entire display area, a few pixels in the upper left corner changed and a few pixels in the lower right corner changed. We do NOT want to compute a single dirty rectangle of the entire area - we instead want two dirty rectangles: a small one in the upper left and a small one in the lower right.

性能是至关重要的，因此这个问题。

这个问题一直都在出现，我想肯定是在视频编解码器和远程桌面压缩领域。在我的例子中，在涉及多个用户同时在共享区域中绘图的图形图像处理过程中，这是一个反复出现的问题。

有谁知道为此发布的算法或知道您过去使用过的解决方案？

谢谢!

Answer 1

屏幕视频/远程桌面编解码器通常将屏幕划分为图 block ，然后仅传输更改的图 block 的位图。然后通常对平铺图像进行 ZLIB 压缩。

有多种方法可以改进这一点，例如

为每个图 block 提供自己的边界矩形，覆盖该图 block 中更改的像素(以避免在只有几个像素发生更改时重新传输整个图 block 。)

使用磁贴的先前内容填充压缩器(如果您正在记录被拖动的窗口或在 2D 游戏中移动的 Sprite ，这将大大提高压缩效率。)

例如，Adobe Flash 在其“屏幕视频 2”编解码器中使用了所有三种技术的组合。

如果您不想使用压缩，瓦片和边界框的组合是一个很好的折衷方案。例如。如果您在对角只有两个更改的像素，则只有这两个像素会被更新，但是如果您有一个具有分散更改的区域(例如，在文本编辑器中输入)，则更改会组合成几个大矩形，这可能比更有效把它分成数百个小矩形。)