Die Suche nach Nähe nicht-schwarze Pixel in einem Bild schnell
https://stackoverflow.com/questions/307445
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe ein 2D-Bild zufällig und dünn mit Pixeln verstreut.
einen Punkt auf dem Bild gegeben, ich brauche den Abstand zum nächsten Pixel zu finden, die nicht in der Hintergrundfarbe (schwarz) ist.
Was ist der schnellste Weg, dies zu tun?
Die einzige Methode, die ich mit baut einen kd-Baum für die Pixel kommen konnte. aber ich würde wirklich wollen, so teuer Vorverarbeitung zu vermeiden. Auch scheint es, dass ein kd-Baum gibt mir mehr als ich brauche. Ich brauche nur die Entfernung zu etwas, und ich kümmere mich nicht um, was dies etwas ist.
Lösung
Als Pyro sagt, suchen den Umfang eines Quadrats, die Sie von Ihrem ursprünglichen Punkt zu einem Zeitpunkt ein Pixel in Bewegung bleiben aus (das heißt die Erhöhung der Breite und Höhe um zwei Pixel zu einem Zeitpunkt). Wenn Sie ein nicht-schwarzes Pixel treffen, berechnen Sie den Abstand (dies ist Ihre erste teuere Berechnung) und dann weiter nach außen suchen, bis die Breite der Box zweimal der Abstand zum ersten gefundenen Punkt (alle Punkte darüber hinaus möglicherweise nicht näher als Ihre ursprünglichen gefunden Pixel). Speichern Sie alle nicht-schwarze Punkte, die Sie in diesem Teil finden, und dann berechnen, die jeweils ihre Abstände zu sehen, ob einer von ihnen näher als die ursprünglichen Punkt.
In einer idealen finden Sie nur eine teure Entfernungsberechnung machen.
Aktualisieren : Weil Sie die Berechnung Pixel-zu-Pixel-Abstände hier (statt beliebiger Genauigkeit Punktstellen floating), können Sie diesen Algorithmus beschleunigen im wesentlichen durch eine vorausberechnete Verweistabelle ( nur ein Höhe-by-Breite-Array) Sie Abstand in Abhängigkeit von x geben und y . Ein 100x100-Array kostet SieFormal im Wesentlichen 40K Speichers und deckt ein 200x200 Quadrat um den ursprünglichen Punkt, und erspart Ihnen die Kosten für eine teure Abstandsberechnung zu tun (ob Pythagoreische oder Matrizenalgebra) für jedes farbiges Pixel Sie. Dieses Array könnte sogar in Ihrer Anwendung als Ressource vorausberechnet und eingebettet werden, können Sie die ursprüngliche Berechnung der Zeit zu ersparen (dies ist wahrscheinlich ernsthafte Overkill).
Update 2 : Auch gibt es Möglichkeiten, die Suche auf den Platz Umfang zu optimieren. Ihre Suche an den vier Punkte beginnen sollte, die die Achsen schneiden und ein Pixel in einer Zeit, zu den Ecken hin bewegen (Sie haben 8 Bewegungssuchpunkte, die leicht diese mehr Mühe machen könnten, als es wert ist, je nach Anwendungsanforderungen). Sobald Sie einen farbigen Pixel lokalisieren, gibt es keine Notwendigkeit, auf den Ecken fortgesetzt werden soll, wie die übrigen Punkte alle weiteren vom Ursprung sind.
Nach dem ersten gefundenen Pixel, können Sie weiterhin den zusätzlichen Suchbereich auf das Minimum unter Verwendung der Verweistabelle erforderlich, um sicherzustellen beschränken, dass jeder gesuchter Punkt näher als der gefundenen Punkt (wieder an den Achsen starten und zu stoppen, wenn der Abstand Grenze erreicht). Diese zweite Optimierung wäre wahrscheinlich viel zu teuer zu verwenden, wenn Sie im laufenden Betrieb jede Entfernung berechnen mußten.
Wenn das nächste Pixel innerhalb der 200x200-Box ist (oder was auch immer Größe arbeitet für Ihre Daten), werden Sie nur innerhalb eines Kreises, der durch das Pixel begrenzt suchen, tun nur Lookups und <> Vergleiche.
Andere Tipps
Ich persönlich würde MusiGenesis' Vorschlag einer Lookup-Tabelle ignorieren.
Die Berechnung der Abstand zwischen den Pixeln ist nicht teuer, zumal für diese erste Test, den Sie den tatsächlichen Abstand nicht brauchen, so gibt es keine Notwendigkeit, die Quadratwurzel zu nehmen. Sie können mit der Entfernung arbeiten ^ 2, das heißt:
r^2 = dx^2 + dy^2
Auch wenn du gehst nach außen ein Pixel in einer Zeit, daran erinnert, dass:
(n + 1)^2 = n^2 + 2n + 1
oder nx ist der aktuelle Wert und ox ist der vorherige Wert:
nx^2 = ox^2 + 2ox + 1
= ox^2 + 2(nx - 1) + 1
= ox^2 + 2nx - 1
=> nx^2 += 2nx - 1
Es ist leicht zu sehen, wie das funktioniert:
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...
in jeder Iteration Also, Sie daher müssen nur behalten einige Zwischenvariablen so:
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
}
}
Tada! r ^ 2 Berechnung mit nur wenig verschiebt, addiert und subtrahiert:)
Natürlich auf jedem anständigen modernen CPU Berechnung r ^ 2 = dx * dx + dy * dy könnte genauso schnell wie das sein ...
Sie haben nicht angeben, wie Sie Abstand messen möchten. Ich werde L1 (geradlinig) übernehmen, weil es einfacher ist; möglicherweise könnte diese Ideen für L2 (euklidischen) geändert werden.
Wenn Sie nur diese für relativ wenige Pixel zu tun, dann suchen Sie einfach nach außen von dem Quellpixel in einer Spirale, bis Sie eine nichtschwarze eines Hit.
Wenn Sie dies tun, für viele / alle von ihnen, wie etwa diese: Erstellen Sie ein 2-D-Array die Größe des Bildes, wobei jede Zelle speichert den Abstand zum nächsten nicht-schwarzen Pixeln (und, falls erforderlich, die Koordinaten dieses Pixels). Habe vier Linie fegt: von links nach rechts, von rechts nach links, von unten nach oben und von oben nach unten. Betrachten wir die von links nach rechts fegen; wie Besen, hält eine 1-D-Säule die letzten nicht-schwarzen Pixel enthält in jeder Zeile zu sehen ist, und jede Zelle mit dem Abstand zu und / oder die Koordinaten des Pixels in der 2-D-Matrix kennzeichnen. O (n ^ 2).
Alternativ kann ein K-D-Baum ist übertrieben; Sie könnten eine Quadtree verwenden. Nur ein wenig schwieriger zu Code als meine Linie fegen, ein wenig mehr Speicher (aber weniger als doppelt so viel) und möglicherweise schneller.
Suche "Nächster Nachbar suchen", zuerst zwei Links in Google sollten Ihnen helfen.
Wenn Sie nur tun dies für 1 Pixel pro Bild, ich denke, die beste Wahl ist nur ein lineare Suche, 1 Pixel Breite Feld zum Zeitpunkt nach außen. Sie können den ersten Punkt nicht nehmen Sie finden, wenn Sie Ihre Suchfeld quadratisch ist. Sie müssen vorsichtig sein,
Ja, die nächste Nachbar-Suche ist gut, aber garantiert nicht, Sie die nächste Ort zu finden. Bewegen eines Pixels aus jeder Zeit wird eine quadratische Such produzieren - die Diagonalen werden weiter entfernt ist als die horizontal / vertikal. Wenn dies wichtig ist, sollten Sie überprüfen, -. Weiter ausbauen, bis die absolute horizontal einen Abstand größer als die ‚gefunden‘ Pixel hat, und dann berechnen Entfernungen auf allen nicht-schwarzen Pixeln, die angeordnet waren
Ok, das klingt interessant. Ich habe eine C ++ Version eines soulution, ich weiß nicht, ob dies Ihnen hilft. Ich denke, es funktioniert schnell genug, wie es auf einer 800 * 600 Matrix fast sofortigen ist. Wenn Sie Fragen haben, fragen Sie einfach.
Sorry für die Fehler, die ich gemacht habe, ist es ein 10min-Code ... Dies ist eine iterative Version (ich war Hobel auch eine rekursive eines auf zu machen, aber ich habe meine Meinung geändert). Der Algorithmus könnte verbessert werden, indem nicht jede Stelle an die Punkte Array hinzuzufügen, die von dem Ausgangspunkt zu einem größeren Abstand ist dann die min_dist, aber dies führt für jeden Bildpunkt die Berechnung der Entfernung von dem Ausgangspunkt (obwohl es Farbe ist).
Ich hoffe, das hilft
//(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;
}
Ich bin sicher, dass dies besser getan werden könnte, aber hier ist einige Code, der den Umfang eines Quadrats um das Mittelpixel sucht, zunächst das zentrale Prüfung und zu den Ecken zu bewegen. Wenn ein Pixel, das den Umfang (Radius) nicht gefunden wird, erweitert wird, bis entweder der Radius Grenze erreicht ist oder ein Pixel gefunden wird. Die erste Implementierung war eine Schleife eine einfache Spirale um den Mittelpunkt zu tun, aber wie bereits erwähnt, der die absolute Nähe Pixel nicht finden. SomeBigObjCStruct Schöpfung innerhalb der Schleife war sehr langsam - Entfernen aus der Schleife es gut genug gemacht und die Spirale Ansatz ist, was verwendet wurde. Aber hier ist diese Implementierung sowieso -. Vorsicht, wenig bis gar keine Tests durchgeführt
Es wird alles getan, was mit Integer-Addition und Subtraktion.
- (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;
}
Sie können viele Möglichkeiten kombinieren sie zu beschleunigen.
- Ein Weg, um die Pixel-Lookup zu beschleunigen zu verwenden ist, was ich eine räumliche Lookup-Karte aufrufen. Es ist im Grunde eine unterabgetasteten Karte (sagen wir von 8x8 Pixel, aber es ist ein Kompromiss) der Pixel in diesem Block. Werte können „keine Pixel set“ „partial Pixel gesetzt“ „alle Pixel eingestellt“ werden. So kann ein Lese kann sagen, ob ein Block / Zelle entweder voll, teilweise voll oder leer ist.
- Scannen eines Box / Rechteck um das Zentrum möglicherweise nicht ideal sein, weil es viele Pixel / Zellen sind, die weit weg weit sind. Ich benutze einen Kreis Zeichnung Algorithmus (Bresenham), um den Overhead zu reduzieren.
- die rohen Pixelwerte Lesen in horizontalen Reihen, zum Beispiel (für eine Zellengröße von 8x8 oder einem Vielfachen davon) ein Byte passieren kann, dword oder lang. Dies sollte Ihnen eine ernsthafte Speedup geben wieder.
- können Sie auch mehrere Ebenen von „spatial-Lookup-Karten“, seine wieder ein Kompromiss.
Für die Entfernung calculatation die genannte Lookup-Tabelle verwendet werden kann, aber es ist eine (Cache) Bandbreite vs Rechengeschwindigkeit tradeoff (ich weiß nicht, wie es auf einer GPU zum Beispiel führt).
Ich würde eine einfache Lookup-Tabelle tun - für jedes Pixel, vorberechnen Entfernung zum nächsten nicht-schwarzen Pixel und speichert den Wert in der gleichen wie die entsprechenden Pixel versetzt. Natürlich, werden Sie auf diese Weise mehr Speicher benötigen.
