骯髒的矩形的最佳設置

我在這裏尋找一種算法，獨立於特定的編程語言。骯髒的矩形的最佳設置

問題：

我們有一個2維顯示區域（認爲像素的簡單的緩衝）。週期性地，一些像素被改變。我們需要找到一組包含所有變化像素的一組矩形。

這將是微不足道的，但不受歡迎的，來計算一個單一的，可能的大矩形，封裝所有變化的像素。我們寧願有多個，更小，緊的矩形下降到指定的最小大小（這是一個變量，可以是變化）。

例如，假設整個顯示區域內，在幾個像素的左上角改變，並且在右下角一個幾個像素改變。我們不想計算整個區域的一個單個髒矩形 - 我們需要兩個髒矩形：左上方的小尺寸和右下方的小尺寸。

表現是至關重要的，因此這個問題。

這個問題在所有的時候都會出現，絕對是在視頻編解碼器和遠程桌面壓縮領域，我猜想。就我而言，在圖形圖像操作過程中，這是一個反覆出現的問題，涉及多個用戶同時在共享區域中繪圖。

有沒有人知道已發佈的算法或知道過去使用過的解決方案？

謝謝！

來源

2011-03-23 Clay Fowler

你如何定義「性能」？你有什麼其他限制？你有具體的度量來判斷好的解決方案嗎？ – Karmastan 2011-03-23 20:00:35

由於我要求的是一種獨立於特定語言或平臺的算法，因此很難具體使用度量標準，但我的意思是一種算法，它儘可能少地找到答案，而不是某種例如，對該區域中的每個像素執行多次強力掃描。我會用與測量Bresenham畫線等算法相同的方式來衡量它：它在足夠少的操作中找到了正確的答案，因此很難設想使用更少的操作。 – 2011-03-23 20:25:30

我的想法，有兩個決策選項：

我寫它在某種僞代碼..

基本上你在你的領域的必須遵守滿足最低髒像素的百分比決定第一個選項計數。

對於第二個選項，您可以決定如果展開以包含此像素，此因子或每個區域的髒像素的差異是否變化太大。

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 

}

來源

2011-03-23 19:57:35

查找到R-tree和quadtree數據結構。

來源

2011-03-25 14:17:43 xan

屏幕視頻/遠程桌面編解碼器通常會將屏幕分成多個圖塊，然後僅爲已更改的圖塊傳輸位圖。瓦片圖像通常是ZLIB壓縮的。

有多種方法可以對此進行改進，例如，

給每瓦自己的邊框，覆蓋變化像素在瓷磚（以避免重新傳輸整個瓷磚如果只有幾個像素髮生了變化。）
總理壓縮機與以前的內容瓦（這極大地提高壓縮效率，如果你正在錄製被拖動窗口或精靈在2D遊戲中移動。）

例如的Adobe Flash使用的所有三種技術的組合在其「屏幕視頻2」編解碼器。

如果你不想使用壓縮，包圍盒的組合&是一個很好的折衷。例如。如果在對角處只有兩個變化的像素，那麼只會更新這兩個像素，但是如果您有一個分散變化的區域（例如，在文本編輯器中鍵入），則會將這些變化合併爲幾個較大的矩形，這可能比將其分成數百個小矩形。）

來源

2011-05-08 00:32:58 finnw

骯髒的矩形的最佳設置

回答

相關問題