Оптимальный набор грязных прямоугольников

Question

Я ищу здесь алгоритм, независимый от конкретного языка программирования.

Проблема:

У нас есть двумерная область отображения (подумайте простой буфер пикселей). Периодически некоторые из пикселей изменилось. Нам нужно найти набор прямоугольники, которые инкапсулируют все изменились пиксели.

Это было бы тривиально, но нежелательно, вычислить один, потенциально большой прямоугольник, который заключает в себе все изменились пиксели. Мы бы предпочли несколько, меньше, облегающие прямоугольники до указанного минимума размер (это переменная, которая может быть изменено).

Например, предположим, что в пределах вся область отображения, несколько пикселей в верхний левый угол изменился и несколько пикселей в правом нижнем углу изменилось. Мы не хотим вычислять один грязный прямоугольник всего площадь - вместо этого мы хотим два грязных прямоугольники: маленький в верхнем левый и маленький в нижнем правый.

Производительность имеет решающее значение, поэтому этот вопрос.

Эта проблема возникает постоянно, я полагаю, определенно в видеокодеках и областях сжатия удаленных рабочих столов. В моем случае это повторяющаяся проблема во время манипуляций с графическим изображением, когда несколько пользователей одновременно рисуют в общей области.

Кто-нибудь знает об опубликованных алгоритмах для этого или знает о решении, которое вы использовали в прошлом?

Спасибо!

Answer 1

Экранные видео / кодеки удаленного рабочего стола обычно делят экран на фрагменты, а затем передают растровые изображения только для измененных фрагментов.Изображения мозаичного изображения обычно затем сжимаются ZLIB.

Существуют различные способы улучшить это, например:

• Придайте каждой плитке собственный ограничивающий прямоугольник, покрывая измененные пиксели в этой плитке(чтобы избежать повторной передачи всей плитки, если изменилось только несколько пикселей.)
• Заполните компрессор предыдущим содержимым плитки (это значительно повышает эффективность сжатия, если вы записываете перетаскиваемое окно или спрайтыперемещение в 2D-игре.)

Например, Adobe Flash использует комбинацию всех трех приемов в своем кодеке «Screen Video 2».

Если вы не хотите использоватьсжатие, комбинация плиток и ограничительных рамок - хороший компромисс.Например, если у вас есть только два измененных пикселя в противоположных углах, будут обновлены только эти два пикселя, но если у вас есть область с разбросанными изменениями (например, ввод в текстовом редакторе), изменения объединяются в несколько больших прямоугольников, что, вероятно, более эффективночем разбить его на сотни маленьких прямоугольников.)

Answer 2

Просмотр R-дерева и квадродерева структур данных.

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

}