2次元配列の矩形領域内で最大値を見つけるための速い方法

Question

2次元配列の奥行き値があり、与えられた矩形領域内で最大値を見つけるための高速な方法が必要です。多くの四角形が与えられた深度バッファに対してテストされるので、合理的な前処理ステップが受け入れられます。

単純なアプローチは、矩形内の各ピクセルを走査して、幅が必要な最大*高さの繰り返しを追跡することです。

各親ノードがその子ノードの最大値を含む深度バッファのクォードツリーを最初に作成することによって、複雑度をおよそ幅+高さの繰り返しに減らすことができます。この方法は良いですが、それがもっと速くできるかどうかを知りたいのですが。

リニア時間前処理hereを使用して一定時間内の最大値ではなく、平均値を見つける方法の例を挙げました。

最大値を見つけるための同様の手法を知っている人はいますか？

Answer 1

はいは、例えば8ビットの深さ（0〜255）のために、しかし、わずかな色深度のための平均のトリックを一般化することができます。 k色（または異なる奥行値）があるとします。

参考のため、積分画像Viola/Jones CVPR 2001による矩形の平均計算については、2.1項を参照してください。

私の一般化されたアルゴリズムは、色/深さの値がどのくらいの頻度で発生するかを、次元kのベクトルの積分を事前に計算することです。。このベクトルから、トリックと同じ違いを取って平均を計算することができます。これにより、矩形領域内の最大値だけでなく、一定時間内にその矩形内のヒストグラムのベクトルが得られます。もちろん、ヒストグラムでは、最大（または最小、または他の分位数）を抽出することができます。当然の

時間とメモリの要件は、色の数と一緒に成長、私は複雑性クラスが事前計算のためのルックアップのためのO（K）とO（k個の*幅*高さ）だと思います。

（私の考えは、以前に使用されている場合、私は興味がある。）

Answer 2

パッド2の乗に出て、配列、ゼロを追加することによって。次に、それをスタックにピラミッド化し、毎回各次元で2倍に縮小します。各レベルで、各要素の値は、ピラミッド内の次に大きい配列の4つの対応する要素の最大値に等しくなります。これは、ミップマップのように、パディングされた配列サイズの上に追加の1/3の記憶スペースを必要とします。

与えられた配列レベルの単一の要素をとり、クエリ領域がそれによってカバーされる境界をカバーするかどうかを調べる再帰関数を作成します。そうでない場合は、クエリ領域と重なる次の最大配列の各領域をチェックし、それぞれの再帰的に計算された最大値を返します。

擬似コード：

int getMax(Rect query_rect, int level, int level_x, int level_y) 
{ 
     int level_factor = 1 << level; 
     // compute the area covered by this array element: 
     Rect level_rect(level_x * level_factor, level_y * level_factor, 
      (level_x + 1) * level_factor, (level_y + 1) * level_factor); 

     // if the regions don't overlap then ignore: 
     if(!query_rect.intersects(level_rect)) 
      return -1; 

     // query rect entirely contains this region, return precomputed max: 
     if(query_rect.contains(level_rect)) 
      return pyramid[level][level_x][level_y]; 

     if(level == 0) 
      return -1; // ran out of levels 

     int max = getMax(query_rect, level - 1, level_x * 2, level_y * 2); 
     max = maxValue(max, getMax(query_rect, level - 1, (level_x * 2) + 1, level_y * 2); 
     max = maxValue(max, getMax(query_rect, level - 1, level_x * 2, (level_y * 2) + 1); 
     max = maxValue(max, getMax(query_rect, level - 1, (level_x * 2) + 1, (level_y * 2) + 1); 

     return max; 
} 

最初にトップレベル（ピラミッドで絶頂の1x1のアレイ）でそれを呼び出す：

int max = getMax(query_rect, 10, 0, 0); 

以下、クエリ矩形の最小サイズがありますそれはすべての要素を反復するだけで安くなるでしょう。これを非正方配列でも使えるように変更することができます。再帰するときは、各レベルの配列サイズに対していくつかの追加テストが必要になります。