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

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

}