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

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

Проблема:

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

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

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

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

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

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

Спасибо!

Ответ 1

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

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

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

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

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

Ответ 2

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

Ответ 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

}