画像内の最も近い非黒ピクセルを高速に見つける
https://stackoverflow.com/questions/307445
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
2D画像がランダムに散在し、ピクセルがまばらに散らばっています。
画像上の点が与えられた場合、背景色（黒）ではない最も近いピクセルまでの距離を見つける必要があります。
これを行う最速の方法は何ですか？
私が思いつく唯一の方法は、ピクセルのkdツリーを構築することです。しかし、私は本当にそのような高価な前処理を避けたいです。また、kd-treeは必要以上に多くを提供してくれるようです。何かまでの距離が必要なだけで、これが何であるかは気にしません。
解決
パイロが言うように、元のポイントから一度に1ピクセルずつ移動し続ける正方形の周囲を検索します（つまり、一度に2ピクセルずつ幅と高さを増やします）。黒以外のピクセルをヒットすると、距離を計算し（これが最初の高価な計算です）、ボックスの幅が最初に見つかったポイントまでの距離の2倍になるまで外側に向かって検索を続けます（これを超えるポイントは近づかない可能性があります）元の見つかったピクセルよりも）。このパートで見つけた黒い点以外を保存し、それぞれの距離を計算して、元の点よりも近い点があるかどうかを確認します。
理想的な検索では、1つの高価な距離計算のみを行う必要があります。
更新：ここでは（任意の精度の浮動小数点位置ではなく）ピクセル間の距離を計算しているため、事前に計算されたルックアップテーブルを使用して、このアルゴリズムを大幅に高速化できます（ x と y の関数として距離を与えるための高さx幅の配列）。 100x100の配列は、基本的に40Kのメモリを消費し、元のポイントの周囲の200x200の正方形をカバーし、見つかったすべてのカラーピクセルに対して高価な距離計算（ピタゴラスまたは行列代数）を行うコストを節約します。この配列を事前に計算して、リソースとしてアプリに埋め込むこともできます。これにより、最初の計算時間を節約できます（これはおそらく深刻な過剰です）。
更新2 ：また、正方形の境界の検索を最適化する方法があります。検索は、軸と交差する4つのポイントから開始し、一度に1ピクセルずつ角に向かって移動する必要があります（8つの移動検索ポイントがあるため、アプリケーションの要件に応じて、これは価値以上に簡単に問題を引き起こす可能性があります）。色付きピクセルを見つけるとすぐに、残りのポイントはすべて原点から遠いので、角に向かって進む必要はありません。
最初に見つかったピクセルの後、ルックアップテーブルを使用して、検索された各ポイントが見つかったポイントよりも近くなるように、必要な追加の検索領域をさらに制限できます（再び軸から開始し、距離が制限に達しました）。この2番目の最適化は、各距離をオンザフライで計算しなければならない場合、採用するにはおそらく非常に高価になります。
最も近いピクセルが200x200ボックス内にある場合（またはデータに有効なサイズであれば）、ピクセルに囲まれた円内のみを検索し、ルックアップと<！> lt; <！> gt;比較のみを行います。
他のヒント
個人的に、MusiGenesisのルックアップテーブルの提案は無視します。
ピクセル間の距離の計算は 高価ではありません。特に、この最初のテストでは実際の距離は必要ないため、平方根を取る必要はありません。 distance ^ 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計算：）
もちろん、r ^ 2 = dx * dx + dy * dyを計算する最近のCPUでは、これと同じくらい速いかもしれません...
距離の測定方法を指定しませんでした。 L1（直線）は簡単だからです。おそらく、これらのアイデアはL2（ユークリッド）向けに変更できます。
これを比較的少数のピクセルに対してのみ行う場合は、黒以外のピクセルに達するまで、らせん状にソースピクセルから外側に向かって検索します。
それらの多く/すべてに対してこれを行う場合、これについてはどうですか：各セルが最も近い非黒ピクセルまでの距離を格納する2次元配列を構築します（必要に応じて座標そのピクセルの）。左から右、右から左、下から上、上から下の4つのラインスイープを実行します。左から右へのスイープを検討してください。スイープするときに、各行に表示される最後の非黒ピクセルを含む1次元の列を保持し、そのピクセルまでの距離や座標で2次元配列の各セルをマークします。 O（n ^ 2）。
代わりに、k-dツリーは過剰です。クワッドツリーを使用できます。ラインスイープよりもコーディングが少し難しく、メモリが少し（ただし、2倍未満）で、おそらく高速です。
検索<！> quot;最近接検索<！> quot;、Googleの最初の2つのリンクが役立ちます。
これを画像ごとに1ピクセルだけ行う場合、最善の策は、外側に1ピクセル幅のボックスを線形検索することだけだと思います。検索ボックスが正方形の場合、最初に見つけたポイントを取得できません。注意する必要があります
はい、最近傍検索は良好ですが、「最近傍」が見つかることを保証するものではありません。毎回1ピクセルを移動すると、正方形の検索が生成されます-対角線は水平/垂直よりも遠くになります。これが重要な場合は、確認する必要があります-絶対水平方向の距離が「見つかった」ピクセルよりも大きくなるまで拡大を続けてから、配置されたすべての非黒ピクセルの距離を計算します。
わかりました、これは面白いですね。 解決策のC ++バージョンを作成しましたが、これが役立つかどうかはわかりません。 800 * 600マトリックスではほぼ瞬時に処理されるため、十分に高速に動作すると思います。質問がある場合は質問してください。
私が犯した間違いはごめんなさい、それは10分のコードです... これは反復バージョンです（再帰バージョンも計画していましたが、気が変わりました）。 アルゴリズムは、min_distよりも開始点からの距離が大きいポイント配列にポイントを追加しないことで改善できますが、これには各ピクセル（色にもかかわらず）の開始点からの距離の計算が含まれます。
役立つこと
//(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;
}
これはもっと良い方法だと思いますが、ここでは最初に中心を調べて角に向かって移動し、中心ピクセルの周りの正方形の周囲を検索するコードがあります。ピクセルが見つからない場合、半径制限に達するかピクセルが見つかるまで、境界線（半径）が拡張されます。最初の実装は、中心点を中心に単純なスパイラルを実行するループでしたが、指摘したように、絶対的な最も近いピクセルは見つかりません。 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;
}
多くの方法を組み合わせて高速化できます。
- ピクセル検索を高速化する方法は、空間検索マップと呼ばれるものを使用することです。基本的には、そのブロック内のピクセルのダウンサンプリングされたマップ（たとえば、8x8ピクセルですが、トレードオフ）です。値は<！> quot; no pixel set <！> quot;にできます。 <！> quot;部分的なピクセルセット<！> quot; <！> quot;すべてのピクセルセット<！> quot;。この方法で、ブロック/セルがいっぱいか、部分的にいっぱいか、空かを読み取ることができます。
- 遠くに離れた場所に多くのピクセル/セルがあるので、中心の周りのボックス/長方形をスキャンすることは理想的ではないかもしれません。オーバーヘッドを減らすために、円描画アルゴリズム（Bresenham）を使用します。
- 未加工ピクセル値の読み取りは、バイト（8x8のセルサイズまたはその倍数）、dwordまたはlongなどの水平バッチで発生する可能性があります。これにより、大幅に高速化されるはずです。
- 複数レベルの<！> quot; spatial lookup maps <！> quot;を使用することもできますが、これもトレードオフです。
距離の計算には、前述のルックアップテーブルを使用できますが、その（キャッシュ）帯域幅と計算速度のトレードオフがあります（たとえば、GPUでの実行方法はわかりません）。
単純なルックアップテーブルを作成します。すべてのピクセルについて、最も近い非黒ピクセルまでの距離を事前計算し、対応するピクセルと同じオフセットに値を保存します。もちろん、この方法ではより多くのメモリが必要になります。
