performance - 画像内の最も近い黒以外のピクセルをすばやく見つける

Question

私は2D画像をランダムにそしてまばらにピクセルで散らばっています。
画像上の点を指定して、背景色（黒）にない最も近いピクセルまでの距離を見つける必要があります。
これを行うための最速の方法は何ですか？

私が思いつくことができる唯一の方法は、ピクセルのkdツリーを構築することです。しかし、私は本当にそのような高価な前処理を避けたいと思います。また、kd-treeは私に必要以上のものを与えてくれるようです。私は何かまでの距離が必要なだけで、これが何であるかは気にしません。

Answer 1

個人的には、ルックアップ テーブルに関する MusiGenesis の提案は無視します。

ピクセル間の距離の計算は、特にこの最初のテストでは実際の距離を必要としないため、平方根を取る必要がないため、費用はかかりません。距離^ 2で作業できます。つまり、次のようになります。

r^2 = dx^2 + dy^2

また、一度に 1 ピクセルずつ外側に移動する場合は、次のことを覚えておいてください。

(n + 1)^2 = n^2 + 2n + 1

またはnxが現在の値でoxが前の値の場合:

    nx^2  = ox^2 + 2ox + 1
          = ox^2 + 2(nx - 1) + 1
          = ox^2 + 2nx - 1
=>  nx^2 += 2nx - 1 

これがどのように機能するかは簡単にわかります。

1^2 =  0 + 2*1 - 1 =  1
2^2 =  1 + 2*2 - 1 =  4
3^2 =  4 + 2*3 - 1 =  9
4^2 =  9 + 2*4 - 1 = 16
5^2 = 16 + 2*5 - 1 = 25
etc...

したがって、各反復では、次のようにいくつかの中間変数のみを保持する必要があります。

int dx2 = 0, dy2, r2;
for (dx = 1; dx < w; ++dx) {  // ignoring bounds checks
   dx2 += (dx << 1) - 1;
   dy2 = 0;
   for (dy = 1; dy < h; ++dy) {
       dy2 += (dy << 1) - 1;
       r2 = dx2 + dy2;
       // do tests here
   }
}

多田！ビットシフト、加算、減算のみのr^2計算:)

もちろん、まともな最新の CPU では、r^2 = dx*dx + dy*dy を計算すると、これと同じくらい高速になる可能性があります...

Answer 2

Pyro が言うように、元の点から一度に 1 ピクセルずつ移動し続ける正方形の周囲を検索します (つまり、一度に 2 ピクセルずつ幅と高さを増やします)。黒以外のピクセルにヒットすると、距離を計算し (これが最初のコストのかかる計算です)、ボックスの幅が最初に見つかったポイントまでの距離の 2 倍になるまで、外側に向かって検索を続けます (これを超えるポイントは近くにある可能性はありません)。元に見つかったピクセルよりも）。この部分で見つけた非黒点を保存し、それぞれの距離を計算して、元の点よりも近い点があるかどうかを確認します。

理想的な発見では、高価な距離計算を 1 回行うだけで済みます。

更新: ここではピクセル間の距離を計算しているため (任意精度の浮動小数点の位置ではなく)、事前に計算されたルックアップ テーブル (高さ×幅の配列) を使用して、このアルゴリズムを大幅に高速化できます。xとyの関数として距離を与えます。100x100 の配列は、基本的に 40K のメモリを消費し、元の点の周りに 200x200 の正方形をカバーし、見つけたすべての色付きピクセルに対して高価な距離計算 (ピタゴラスまたは行列代数) を実行するコストを節約します。この配列は、事前に計算してリソースとしてアプリに埋め込むこともでき、最初の計算時間を節約できます (これはおそらく深刻なやり過ぎです)。

更新 2 : また、正方形の周囲の検索を最適化する方法があります。検索は、軸と交差する 4 つのポイントから開始し、一度に 1 ピクセルずつ角に向かって移動する必要があります (8 つの移動検索ポイントがあるため、アプリケーションの要件によっては、これが必要以上に困難になる可能性があります)。色付きのピクセルを見つけたら、残りのポイントはすべて原点から遠く離れているため、コーナーに向かって続行する必要はありません。

最初に検出されたピクセルの後、ルックアップ テーブルを使用して、検索された各ポイントが検出されたポイントよりも近くなるようにすることで、必要な追加の検索領域を最小限に制限することができます (再び軸から開始し、距離制限に達したときに停止します)。 ）。この 2 番目の最適化は、それぞれの距離をその場で計算しなければならない場合、採用するにはコストがかかりすぎるでしょう。

最も近いピクセルが 200x200 ボックス (またはデータに適したサイズ) 内にある場合、ピクセルで囲まれた円内のみを検索し、ルックアップと比較のみを行います。

Answer 3

距離の測定方法を指定していません。簡単なので、L1（直線）と仮定します。おそらく、これらのアイデアはL2（ユークリッド）用に変更される可能性があります。

比較的少数のピクセルに対してのみこれを実行している場合は、黒以外のピクセルに到達するまで、スパイラルでソースピクセルから外側に向かって検索します。

それらの多く/すべてに対してこれを行う場合は、これはどうでしょうか。各セルが最も近い非黒ピクセルまでの距離（および必要に応じてそのピクセルの座標）を格納する、画像のサイズの2D配列を作成します。 ）。左から右、右から左、下から上、上から下の4つのラインスイープを実行します。左から右へのスイープを考えてみましょう。スイープするときは、各行に表示される最後の黒以外のピクセルを含む1次元の列を保持し、そのピクセルまでの距離や座標で2次元配列の各セルにマークを付けます。O（n ^ 2）。

あるいは、kdツリーはやり過ぎです。四分木を使用できます。私のラインスイープよりもコーディングが少し難しく、メモリが少し多く（ただし2倍未満）、おそらくより高速です。

Answer 4

わかりました、これは面白そうですね。私はソウルリューションの C++ バージョンを作成しましたが、これが役立つかどうかはわかりません。800*600 マトリックスではほぼ瞬時に動作するため、十分に高速に動作すると思います。ご不明な点がございましたら、お気軽にお問い合わせください。

10 分のコードなので、間違っていたらすみません。アルゴリズムは、開始点からの距離が min_dist よりも長い点を points 配列に追加しないことで改善できますが、これには、ピクセルごとに (色にもかかわらず) 開始点からの距離を計算することが含まれます。

それが役立つことを願っています

//(c++ version)
#include<iostream>
#include<cmath>
#include<ctime>
using namespace std;
//ITERATIVE VERSION

//picture witdh&height
#define width 800
#define height 600
//indexex
int i,j;

//initial point coordinates
int x,y;
//variables to work with the array
int p,u;
//minimum dist
double min_dist=2000000000;
//array for memorising the points added
struct point{
  int x;
  int y;
} points[width*height];
double dist;
bool viz[width][height];
// direction vectors, used for adding adjacent points in the "points" array.
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
int k,nX,nY;
//we will generate an image with white&black pixels (0&1)
bool image[width-1][height-1];
int main(){
    srand(time(0));
    //generate the random pic
    for(i=1;i<=width-1;i++)
        for(j=1;j<=height-1;j++)
            if(rand()%10001<=9999) //9999/10000 chances of generating a black pixel
            image[i][j]=0;
            else image[i][j]=1;
    //random coordinates for starting x&y
    x=rand()%width;
    y=rand()%height;
    p=1;u=1;
    points[1].x=x;
    points[1].y=y;
    while(p<=u){
        for(k=0;k<=7;k++){
          nX=points[p].x+dx[k];
          nY=points[p].y+dy[k];
          //nX&nY are the coordinates for the next point
          //if we haven't added the point yet
          //also check if the point is valid
          if(nX>0&&nY>0&&nX<width&&nY<height)
          if(viz[nX][nY] == 0 ){
              //mark it as added
              viz[nX][nY]=1;
              //add it in the array
              u++;
              points[u].x=nX;
              points[u].y=nY;
              //if it's not black
              if(image[nX][nY]!=0){
              //calculate the distance
              dist=(x-nX)*(x-nX) + (y-nY)*(y-nY);
              dist=sqrt(dist);
              //if the dist is shorter than the minimum, we save it
              if(dist<min_dist)
                  min_dist=dist;
                  //you could save the coordinates of the point that has
                  //the minimum distance too, like sX=nX;, sY=nY;
              }
            }
        }
        p++;
}
    cout<<"Minimum dist:"<<min_dist<<"\n";
return 0;
}

Answer 5

「最近傍検索」で検索してください。Google の最初の 2 つのリンクが役に立ちます。

画像ごとに 1 ピクセルのみでこれを行っている場合、最善の策は、1 ピクセル幅のボックスを外側に向けて線形検索することだと思います。検索ボックスが正方形の場合、最初に見つけたポイントを取ることはできません。あなたは注意する必要があります

Answer 6

はい、最近傍検索は適切ですが、「最も近い」検索を保証するものではありません。毎回 1 ピクセル外側に移動すると、正方形の検索が生成されます。対角線は水平/垂直よりも遠くなります。これが重要な場合は、確認する必要があります。絶対水平方向の距離が「見つかった」ピクセルよりも大きくなるまで拡大を続けてから、配置されたすべての黒以外のピクセルの距離を計算します。

Answer 7

これはもっとうまくできると確信していますが、中心ピクセルの周りの正方形の周囲を検索し、最初に中心を調べて角に向かって移動するコードを次に示します。ピクセルが見つからない場合、半径の制限に達するかピクセルが見つかるまで、周囲 (半径) が拡張されます。最初の実装は、中心点の周りに単純ならせんを実行するループでしたが、前述のように、絶対的に最も近いピクセルが見つかりません。ループ内での SomeBigObjCStruct の作成は非常に時間がかかりました。ループから削除することで十分になり、スパイラル アプローチが使用されるようになりました。しかし、とにかくこの実装があります-注意してください、テストはほとんどまたはまったく行われていません.

それはすべて整数の足し算と引き算で行われます。

- (SomeBigObjCStruct *)nearestWalkablePoint:(SomeBigObjCStruct)point {    

typedef struct _testPoint { // using the IYMapPoint object here is very slow
    int x;
    int y;
} testPoint;

// see if the point supplied is walkable
testPoint centre;
centre.x = point.x;
centre.y = point.y;

NSMutableData *map = [self getWalkingMapDataForLevelId:point.levelId];

// check point for walkable (case radius = 0)
if(testThePoint(centre.x, centre.y, map) != 0) // bullseye
    return point;

// radius is the distance from the location of point. A square is checked on each iteration, radius units from point.
// The point with y=0 or x=0 distance is checked first, i.e. the centre of the side of the square. A cursor variable
// is used to move along the side of the square looking for a walkable point. This proceeds until a walkable point
// is found or the side is exhausted. Sides are checked until radius is exhausted at which point the search fails.
int radius = 1;

BOOL leftWithinMap = YES, rightWithinMap = YES, upWithinMap = YES, downWithinMap = YES;

testPoint leftCentre, upCentre, rightCentre, downCentre;
testPoint leftUp, leftDown, rightUp, rightDown;
testPoint upLeft, upRight, downLeft, downRight;

leftCentre = rightCentre = upCentre = downCentre = centre;

int foundX = -1;
int foundY = -1;

while(radius < 1000) {

    // radius increases. move centres outward
    if(leftWithinMap == YES) {

        leftCentre.x -= 1; // move left

        if(leftCentre.x < 0) {

            leftWithinMap = NO;
        }
    }

    if(rightWithinMap == YES) {

        rightCentre.x += 1; // move right

        if(!(rightCentre.x < kIYMapWidth)) {

            rightWithinMap = NO;
        }
    }

    if(upWithinMap == YES) {

        upCentre.y -= 1; // move up

        if(upCentre.y < 0) {

            upWithinMap = NO;
        }
    }

    if(downWithinMap == YES) {

        downCentre.y += 1; // move down

        if(!(downCentre.y < kIYMapHeight)) {

            downWithinMap = NO;
        }
    }

    // set up cursor values for checking along the sides of the square
    leftUp = leftDown = leftCentre;
    leftUp.y -= 1;
    leftDown.y += 1;
    rightUp = rightDown = rightCentre;
    rightUp.y -= 1;
    rightDown.y += 1;
    upRight = upLeft = upCentre;
    upRight.x += 1;
    upLeft.x -= 1;
    downRight = downLeft = downCentre;
    downRight.x += 1;
    downLeft.x -= 1;

    // check centres
    if(testThePoint(leftCentre.x, leftCentre.y, map) != 0) {

        foundX = leftCentre.x;
        foundY = leftCentre.y;
        break;
    }
    if(testThePoint(rightCentre.x, rightCentre.y, map) != 0) {

        foundX = rightCentre.x;
        foundY = rightCentre.y;
        break;
    }
    if(testThePoint(upCentre.x, upCentre.y, map) != 0) {

        foundX = upCentre.x;
        foundY = upCentre.y;
        break;
    }
    if(testThePoint(downCentre.x, downCentre.y, map) != 0) {

        foundX = downCentre.x;
        foundY = downCentre.y;
        break;
    }

    int i;

    for(i = 0; i < radius; i++) {

        if(leftWithinMap == YES) {
            // LEFT Side - stop short of top/bottom rows because up/down horizontal cursors check that line
            // if cursor position is within map
            if(i < radius - 1) {

                if(leftUp.y > 0) {
                    // check it
                    if(testThePoint(leftUp.x, leftUp.y, map) != 0) {
                        foundX = leftUp.x;
                        foundY = leftUp.y;
                        break;
                    }
                    leftUp.y -= 1; // moving up
                }
                if(leftDown.y < kIYMapHeight) {
                    // check it
                    if(testThePoint(leftDown.x, leftDown.y, map) != 0) {
                        foundX = leftDown.x;
                        foundY = leftDown.y;
                        break;
                    }
                    leftDown.y += 1; // moving down
                }
            }
        }

        if(rightWithinMap == YES) {
            // RIGHT Side
            if(i < radius - 1) {

                if(rightUp.y > 0) {

                    if(testThePoint(rightUp.x, rightUp.y, map) != 0) {
                        foundX = rightUp.x;
                        foundY = rightUp.y;
                        break;
                    }
                    rightUp.y -= 1; // moving up
                }
                if(rightDown.y < kIYMapHeight) {

                    if(testThePoint(rightDown.x, rightDown.y, map) != 0) {
                        foundX = rightDown.x;
                        foundY = rightDown.y;
                        break;
                    }
                    rightDown.y += 1; // moving down
                }
            }
        }

        if(upWithinMap == YES) {
            // UP Side
            if(upRight.x < kIYMapWidth) {

                if(testThePoint(upRight.x, upRight.y, map) != 0) {
                    foundX = upRight.x;
                    foundY = upRight.y;
                    break;
                }
                upRight.x += 1; // moving right
            }
            if(upLeft.x > 0) {

                if(testThePoint(upLeft.x, upLeft.y, map) != 0) {
                    foundX = upLeft.x;
                    foundY = upLeft.y;
                    break;
                }
                upLeft.y -= 1; // moving left
            }
        }

        if(downWithinMap == YES) {
            // DOWN Side
            if(downRight.x < kIYMapWidth) {

                if(testThePoint(downRight.x, downRight.y, map) != 0) {
                    foundX = downRight.x;
                    foundY = downRight.y;
                    break;
                }
                downRight.x += 1; // moving right
            }
            if(downLeft.x > 0) {

                if(testThePoint(upLeft.x, upLeft.y, map) != 0) {
                    foundX = downLeft.x;
                    foundY = downLeft.y;
                    break;
                }
                downLeft.y -= 1; // moving left
            }
        }
    }

    if(foundX != -1 && foundY != -1) {
        break;
    }

    radius++;
}

// build the return object
if(foundX != -1 && foundY != -1) {

    SomeBigObjCStruct *foundPoint = [SomeBigObjCStruct mapPointWithX:foundX Y:foundY levelId:point.levelId];
    foundPoint.z = [self zWithLevelId:point.levelId];
    return foundPoint;
}
return nil;

}

Answer 8

さまざまな方法を組み合わせて高速化できます。

• ピクセル ルックアップを高速化する方法は、私が空間ルックアップ マップと呼んでいるものを使用することです。これは基本的に、そのブロック内のピクセルのダウンサンプリングされたマップ (たとえば 8x8 ピクセルですが、トレードオフ) です。値は、「ピクセル セットなし」、「部分ピクセル セット」、「すべてのピクセル セット」のいずれかです。このようにして、1 回の読み取りで、ブロック/セルがいっぱいか、部分的にいっぱいか、空かを判断できます。
• 中心の周りのボックス/長方形をスキャンすることは、遠くにある多くのピクセル/セルがあるため、理想的ではない場合があります。オーバーヘッドを削減するために、円描画アルゴリズム (Bresenham) を使用します。
• 生のピクセル値の読み取りは、水平方向のバッチで発生する可能性があります。たとえば、1 バイト (セル サイズが 8x8 またはその倍数の場合)、dword、または long です。これにより、再び深刻なスピードアップが得られるはずです。
• 複数レベルの「空間ルックアップ マップ」を使用することもできますが、これもトレードオフです。

距離の計算には、前述のルックアップ テーブルを使用できますが、(キャッシュ) 帯域幅と計算速度のトレードオフです (たとえば、GPU でどのように実行されるかはわかりません)。

Answer 9

私は単純なルックアップ テーブルを作成します。すべてのピクセルについて、最も近い黒以外のピクセルまでの距離を事前に計算し、対応するピクセルと同じオフセットに値を格納します。もちろん、この方法ではより多くのメモリが必要になります。