最优脏矩形集

Question

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

问题：

我们有一个二维显示区域 （想想简单的像素缓冲区）。 周期性地，一些像素 改变了。我们需要找到一组 封装所有的矩形 改变了像素。

这虽然微不足道，但不可取， 计算一个潜在的 大的矩形，封装了所有 改变了像素。我们宁愿有 多个、较小、紧身 矩形缩小到指定的最小值 大小（这是一个变量，可以是 改变）。

例如，假设在 整个显示区域，其中的几个像素 左上角发生变化，并且 右下角有几个像素 改变了。我们不想计算 整个的单个脏矩形 区域 - 我们想要两个脏的 矩形：上面一个小矩形 左边，下面有一个小 对。

性能至关重要，因此提出了这个问题。

我认为这个问题一直都会出现，尤其是在视频编解码器和远程桌面压缩领域。就我而言，这是图形图像操作过程中反复出现的问题，涉及多个用户同时在共享区域中绘图。

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

谢谢！

Answer 1

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

有多种方法可以对此进行改进，例如，

• 为每个图块提供自己的边界矩形，覆盖该图块中已更改的像素（以避免在只有几个像素发生变化时重新传输整个图块。）
• 使用先前的内容填充压缩器（如果您要录制 2D 游戏中拖动的窗口或移动的精灵，这会大大提高压缩效率。）

例如，Adobe Flash 在其“Screen Video 2”编解码器中结合使用了所有三种技术。

如果您不想使用压缩，则可以使用图块和图块的组合。边界框是一个很好的折衷方案。例如，如果您在对角处只有两个更改的像素，则只有这两个像素将被更新，但如果您有一个具有分散更改的区域（例如在文本编辑器中键入），则更改将组合成几个大矩形，这可能更有效而不是将其分成数百个小矩形。）

Answer 2

查看 R-tree 和 四叉树 数据结构。

Answer 3

我的想法有两个决策选项：

我用某种伪代码编写了它。

基本上，对于第一个选项，您决定您的区域必须遵守的百分比，以满足最小脏像素数。

对于第二个选项，您可以决定如果扩展以包含此像素，则此因子或每个区域的脏像素的差异是否会发生太大变化。

    struct DirtyPixelArea
{
    Vec2 topLeft;
    Vec2 size;
    list<Vec2> dirtyPixels;

    void AddPixelToArea();

    int Area();
    int DirtyPixelsArea(); // sums all dirty pixels in area
};

list<DirtyPixelArea>  dirtyPixelsAreaList

void add_dirty_pixel(Vec2 dirtyPixel)
{
    closest_area = find_closest_area_to_pixel(dirtyPixel).copy();

    //option 1 - begin

    closest_area.add_dirty_pixel(dirtyPixel);

    if (closest_area.DirtyPixelsArea() > (closest_area.Area() * 0.25))   // you can experiment on choosing your own dirty pixel factor
    {
        update_area_in_list(closest_area);
    }
    else
    {
        new_area = new DirtyPixelArea();
        new_area.AddPixelToArea(dirtyPixel);
        add_area_in_list(new_area);
    }

    //option 1 - end

    // option 2 - begin
    original_area = find_closest_area_to_pixel(dirtyPixel);
    closest_area.add_dirty_pixel(dirtyPixel)

    original_area_factor = original_area.DirtyPixelsArea() / original_area.Area();
    closest_area_factor = closest_area.DirtyPixelArea() / closest_area.Area();

    if ( closest_area_factor / original_area_factor > 0.5)
    {
        update_area_in_list(closest_area);
    }
    else
    {
        new_area = new DirtyPixelArea();
        new_area.AddPixelToArea(dirtyPixel);
        add_area_in_list(new_area);
    }

    // option 2 - end

}