12

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

问题：

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

计算一个包含所有更改像素的单个可能很大的矩形将是微不足道的，但也是不可取的。我们宁愿有多个、更小、更紧密的矩形，直到指定的最小尺寸（这是一个可以改变的变量）。

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

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

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

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

谢谢！

4

3 回答 3

5

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

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

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

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

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

于 2011-05-08T00:32:58.243 回答
2

研究R-tree和quadtree数据结构。

于 2011-03-25T14:17:43.940 回答
1

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

我用某种伪代码写的..

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

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

    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

}
于 2011-03-23T19:57:35.697 回答