最好的一组脏矩形

Question

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

问题:

我们有一个二维显示区域(想象简单的像素缓冲区).定期地,一些像素被改变.我们需要找到一组封装所有更改像素的矩形.

计算一个封装所有已更改像素的单个可能很大的矩形将是微不足道的,但这是不可取的.我们宁愿将多个较小的,紧密拟合的矩形缩小到指定的最小尺寸(这是一个可以更改的变量).

例如,假设在整个显示区域内,左上角的几个像素发生了变化,右下角的几个像素发生了变化.我们不想计算整个区域的单个脏矩形 - 我们想要两个脏矩形:左上角的小矩形和右下角的小矩形.

性能至关重要,因此这个问题.

我认为,这个问题一直存在,绝对是在视频编解码器和远程桌面压缩区域.就我而言,在图形图像处理过程中,这是一个反复出现的问题,涉及多个用户同时在共享区域绘图.

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

谢谢!

Answer 1

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

有各种方法可以对此进行改进,例如

• 为每个图块赋予自己的边界矩形,覆盖该图块中已更改的像素(以避免重新传输整个图块(如果只有几个像素已更改).)
• 使用磁贴的先前内容填充压缩器(如果您正在记录被拖动的窗口或在2D游戏中移动的精灵,这将极大地提高压缩效率.)

例如,Adobe Flash在其"屏幕视频2"编解码器中使用了所有这三种技术的组合.

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

Answer 2

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

我用某种伪代码写了它..

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

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

    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

}