12

ここでは、特定のプログラミング言語に依存しないアルゴリズムを探しています。

問題：

2 次元の表示領域があります (ピクセルの単純なバッファを考えてください)。定期的に、一部のピクセルが変更されます。変更されたすべてのピクセルをカプセル化する長方形のセットを見つける必要があります。

変更されたすべてのピクセルをカプセル化する、潜在的に大きい単一の四角形を計算することは簡単ですが、望ましくありません。むしろ、指定された最小サイズ (変更可能な変数) まで、複数の、より小さく、ぴったりと収まる四角形を使用したいと考えています。

たとえば、表示領域全体で、左上隅の数ピクセルと右下隅の数ピクセルが変化したとします。領域全体の 1 つのダーティな四角形を計算する必要はありません。代わりに、2 つのダーティな四角形が必要です。1 つは左上に、もう 1 つは右下にあります。

パフォーマンスは重要であるため、この質問です。

この問題は、間違いなくビデオコーデックとリモートデスクトップ圧縮領域で常に発生していると思います. 私の場合、共有領域で複数のユーザーが同時に描画するグラフィカルな画像操作中に繰り返し発生する問題です。

これについて公開されているアルゴリズムを知っている人、または過去に使用したソリューションを知っている人はいますか?

ありがとう！

4

3 に答える 3

5

画面ビデオ/リモート デスクトップ コーデックは通常、画面をタイルに分割し、変更されたタイルのみのビットマップを送信します。タイル イメージは通常、ZLIB 圧縮されます。

これを改善するにはさまざまな方法があります。

  • 各タイルに独自の境界四角形を与え、そのタイル内の変更されたピクセルをカバーします (変更されたピクセルが数個だけの場合にタイル全体を再送信するのを避けるため)。
  • タイルの以前の内容でコンプレッサーをプライミングします (2D ゲームでウィンドウのドラッグやスプライトの移動を記録している場合、これにより圧縮効率が大幅に向上します)。

たとえば、Adobe Flash は、「Screen Video 2」コーデックで 3 つの技術すべてを組み合わせて使用​​します。

圧縮を使用したくない場合は、タイルと境界ボックスの組み合わせが適切な妥協点です。たとえば、反対側の角に変更されたピクセルが 2 つだけある場合、それらの 2 つのピクセルのみが更新されますが、変更が散在する領域がある場合 (テキスト エディタで入力するなど)、変更はいくつかの大きな長方形に結合され、おそらくより効率的です。何百もの小さな長方形に分割するよりも。)

于 2011-05-08T00:32:58.243 に答える
2

Rツリーと四分木のデータ構造を調べます。

于 2011-03-25T14:17:43.940 に答える
1

私の考えでは、2 つの決定オプションがあります。

私はある種の擬似コードでそれを書きました..

基本的に、最初のオプションでは、ダーティ ピクセルの最小数を満たすためにエリアが準拠しなければならないパーセンテージを決定します。

2 番目のオプションでは、このピクセルを含めるように拡張した場合に、この係数の差または面積あたりのダーティ ピクセルが大きく変化するかどうかを判断します。

    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-23T19:57:35.697 に答える