最优脏矩形集
我在这里寻找一个算法，独立于特定的编程语言。
问题：
我们有一个二维显示区域(比如简单的像素缓冲区).周期性地，一些像素被改变。我们需要找到一组矩形来封装所有改变的像素。 计算一个可能很大的矩形来封装所有变化的像素是微不足道的，但不可取。我们宁愿有多个，更小，更贴合的矩形，直到一个指定的最小尺寸(这是一个可以改变的变量)。 例如，假设在整个显示区域内，左上角的几个像素发生了变化，右下角的几个像素发生了变化。我们不想计算整个区域的单个脏矩形-相反，我们想要两个脏矩形:左上角的一个小的，右下角的一个小的。
性能至关重要，因此出现了这个问题。
这个问题一直出现在视频编解码器和远程桌面压缩领域，我想。在我的例子中，这是一个在图形图像处理过程中反复出现的问题，涉及到多个用户同时绘制在一个共享区域中。
是否有人知道已发表的算法，或知道您在过去使用过的解决方案？
谢谢!
回答 3
Stack Overflow用户
发布于 2011-05-08 00:32:58
屏幕视频/远程桌面编解码器通常将屏幕划分为块，然后仅传输更改后的瓷砖的位图。瓷砖图像通常是ZLIB压缩的.
在这方面有多种改进的方法。
- 给每个瓷砖自己的边界矩形，覆盖该瓷砖中变化的像素(如果只改变了几个像素，就避免重新传输整个瓷砖)。
- 最优压缩器与之前的内容瓷砖(这大大提高压缩效率，如果你是记录一个窗口被拖动或精灵移动在2D游戏中)。
例如，Adobe在其“屏幕视频2”编解码器中使用了所有三种技术的组合。
如果您不想使用压缩，瓷砖和包围框的组合是一个很好的折衷方案。例如，如果你在相对的角上只有两个被改变的像素，只有这两个像素会被更新，但是如果你有一个有零散变化的区域(例如输入一个文本编辑器)，这些变化被组合成几个大的矩形，这可能比把它分解成数百个小矩形更有效。
Stack Overflow用户
发布于 2011-03-25 14:17:43
查看R-树和四叉树数据结构。
Stack Overflow用户
发布于 2011-03-23 19:57:35
我的想法，有两个选择：
我用某种伪码写的..。
基本上，对于第一个选项，您决定一个百分比，您的区域必须遵守，以满足最低脏像素计数。
对于第二个选项，如果扩展到包含这个像素，则决定该因子的差异或每个区域的脏像素是否变化过大。
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
}https://stackoverflow.com/questions/5410672
复制相似问题
腾讯云开发者
