Óptimo conjunto de rectángulos sucios

Question

Estoy buscando un algoritmo aquí, independientemente del lenguaje de programación específico.

El problema:

Tenemos un área de visualización de 2 dimensiones (piensa búfer sencilla de píxeles). Periódicamente, algunos de los píxeles han cambiado . Necesitamos encontrar un conjunto de rectángulos que encapsulan todos los píxeles cambiados .

Sería trivial, pero indeseable, para calcular una sola, potencialmente grande, rectángulo que encapsula todas píxeles modificados. Preferimos tener múltiple, más pequeño, de ajuste hermético rectángulos abajo a un determinado mínimo (que es una variable que puede ser cambiada ).

Por ejemplo, supongamos que dentro de toda el área de visualización , unos pocos píxeles en la esquina superior izquierda cambiados y un pocos píxeles en la esquina inferior derecha cambiaron. NO queremos calcular un rectángulo sucia único de toda el área ; en su lugar, queremos dos rectángulos sucios : uno pequeño en la parte superior a la izquierda y uno pequeño en la parte inferior derecha.

El rendimiento es fundamental, de ahí esta pregunta.

Este problema surge todo el tiempo, sin duda, en los códecs de vídeo y las zonas de compresión de escritorio remoto, supongo. En mi caso, es un problema recurrente durante las manipulaciones de imágenes gráficas que involucran a múltiples usuarios dibujando simultáneamente en un área compartida.

¿Alguien sabe de algoritmos publicados por esto o sabe de una solución que ha utilizado en el pasado?

Gracias!

Answer 1

Mi idea, con dos opciones de decisión:

Lo escribí en algún tipo de pseudocódigo ..

Básicamente por la primera opción de decidir sobre un porcentaje que su área, debe cumplir para satisfacer píxeles mínimos sucios contar.

Y por la segunda opción, usted decide si la diferencia en este factor o sucios píxeles por unidad de superficie cambia demasiado si expande para incluir este píxel.

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 

} 

Answer 2

Mira en R-tree y quadtree estructuras de datos. códecs

Answer 3

de vídeo de pantalla/escritorio remoto general divide la pantalla en azulejos y luego transmiten los mapas de bits sólo para las baldosas modificados. Las imágenes de mosaico suelen ser comprimidas en ZLIB.

Hay varias maneras de mejorar en este ejemplo,

• Dar a cada baldosa su propio rectángulo delimitador, que cubre los píxeles cambiados en esa baldosa (para evitar la re-transmisión de toda la baldosa si sólo unos pocos píxeles han cambiado.)
• primer compresor con el contenido anterior la baldosa (esto mejora en gran medida la eficiencia de compresión si está grabando una ventana arrastrada o sprites en movimiento en un juego en 2D.)

Por ejemplo Adobe flash utiliza una combinación de las tres técnicas en su "pantalla de vídeo 2" códec .

Si no desea utilizar la compresión, una combinación de recuadros delimitadores & es un buen compromiso. P.ej. si solo tiene dos píxeles cambiados en las esquinas opuestas, solo se actualizarán esos dos píxeles, pero si tiene una región con cambios dispersos (por ejemplo, escribir en un editor de texto) los cambios se combinan en unos pocos rectángulos grandes que es probablemente más eficiente que dividiéndolo en cientos de pequeños rectángulos.)