Trovare velocemente il pixel non nero più vicino in un'immagine
https://stackoverflow.com/questions/307445
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho un'immagine 2D casuale e scarsamente sparsa di pixel.
dato un punto sull'immagine, devo trovare la distanza dal pixel più vicino che non è nel colore di sfondo (nero).
Qual è il modo più veloce per farlo?
L'unico metodo che ho potuto escogitare è costruire un kd-tree per i pixel. ma vorrei davvero evitare una pre-elaborazione così costosa. inoltre, sembra che un kd-tree mi dia più di quello di cui ho bisogno. Ho solo bisogno della distanza da qualcosa e non mi interessa cosa sia questo qualcosa.
Soluzione
Come dice Pyro, cerca nel perimetro di un quadrato che continui a spostare fuori di un pixel alla volta dal punto originale (ovvero aumentando la larghezza e l'altezza di due pixel alla volta). Quando si colpisce un pixel non nero, si calcola la distanza (questo è il primo calcolo costoso) e quindi si continua a cercare verso l'esterno fino a quando la larghezza della casella non è doppia rispetto al primo punto trovato (eventuali punti oltre questo non possono essere più vicini rispetto al pixel trovato originale). Salva eventuali punti non neri che trovi durante questa parte, quindi calcola ciascuna delle loro distanze per vedere se qualcuno di essi è più vicino del punto originale.
In una ricerca ideale, devi fare solo un costoso calcolo della distanza.
Aggiorna : poiché qui stai calcolando le distanze pixel-pixel (anziché posizioni arbitrarie in virgola mobile di precisione), puoi velocizzare sostanzialmente questo algoritmo utilizzando una tabella di ricerca precalcolata ( solo un array altezza per larghezza) per darti la distanza in funzione di x e y . Un array 100x100 ti costa essenzialmente 40K di memoria e copre un quadrato di 200x200 attorno al punto originale e ti risparmia il costo di fare un costoso calcolo della distanza (che sia pitagorico o algebra di matrice) per ogni pixel colorato che trovi. Questo array potrebbe anche essere pre-calcolato e incorporato nella tua app come risorsa, per risparmiare il tempo di calcolo iniziale (questo è probabilmente un grave sovraccarico).
Aggiornamento 2 : inoltre, ci sono modi per ottimizzare la ricerca nel perimetro quadrato. La tua ricerca dovrebbe iniziare nei quattro punti che intersecano gli assi e si spostano di un pixel alla volta verso gli angoli (hai 8 punti di ricerca in movimento, che potrebbero facilmente creare più problemi di quanti ne valga la pena, a seconda delle esigenze della tua applicazione). Non appena si individua un pixel colorato, non è necessario continuare verso gli angoli, poiché i punti rimanenti sono tutti più lontani dall'origine.
Dopo il primo pixel trovato, è possibile limitare ulteriormente l'area di ricerca aggiuntiva richiesta al minimo utilizzando la tabella di ricerca per assicurarsi che ciascun punto cercato sia più vicino del punto trovato (iniziando nuovamente dagli assi e arrestandosi quando la distanza limite raggiunto). Questa seconda ottimizzazione sarebbe probabilmente troppo costosa da impiegare se dovessi calcolare ogni distanza al volo.
Se il pixel più vicino si trova all'interno della casella 200x200 (o qualunque dimensione funzioni per i tuoi dati), effettuerai la ricerca solo all'interno di un cerchio delimitato dal pixel, facendo solo ricerche e < > confronti.
Altri suggerimenti
Personalmente, ignorerei il suggerimento di MusiGenesis di una tabella di ricerca.
Il calcolo della distanza tra i pixel è non costoso, in particolare per questo test iniziale non è necessaria la distanza effettiva, quindi non è necessario prendere la radice quadrata. Puoi lavorare con la distanza ^ 2, ovvero:
r^2 = dx^2 + dy^2
Inoltre, se stai andando verso l'esterno di un pixel alla volta, ricorda che:
(n + 1)^2 = n^2 + 2n + 1
o se nx è il valore corrente e ox è il valore precedente:
nx^2 = ox^2 + 2ox + 1
= ox^2 + 2(nx - 1) + 1
= ox^2 + 2nx - 1
=> nx^2 += 2nx - 1
È facile vedere come funziona:
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...
Quindi, in ogni iterazione è quindi necessario conservare solo alcune variabili intermedie:
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! calcolo r ^ 2 con solo bit shift, aggiunge e sottrae :)
Naturalmente, su qualsiasi CPU moderna decente il calcolo di r ^ 2 = dx * dx + dy * dy potrebbe essere altrettanto veloce di così ...
Non hai specificato come vuoi misurare la distanza. Presumo L1 (rettilineo) perché è più facile; forse queste idee potrebbero essere modificate per L2 (Euclide).
Se lo fai solo per relativamente pochi pixel, cerca semplicemente verso l'esterno dal pixel sorgente in una spirale fino a quando non ne colpisci uno non nero.
Se lo stai facendo per molti / tutti, che ne dici di questo: costruisci un array 2-D delle dimensioni dell'immagine, dove ogni cella memorizza la distanza dal pixel non nero più vicino (e, se necessario, le coordinate di quel pixel). Esegui quattro passaggi di linea: da sinistra a destra, da destra a sinistra, dal basso verso l'alto e dall'alto verso il basso. Considera la spazzata da sinistra a destra; durante lo sweep, mantieni una colonna 1-D contenente l'ultimo pixel non nero visto in ogni riga e segna ogni cella nell'array 2-D con la distanza e / o le coordinate di quel pixel. O (n ^ 2).
In alternativa, un albero k-d è eccessivo; potresti usare un quadrifoglio. Solo un po 'più difficile da programmare rispetto alla mia linea di sweep, un po' più di memoria (ma meno del doppio) e forse più veloce.
Cerca " Ricerca vicino più vicino " ;, i primi due link in Google dovrebbero aiutarti.
Se lo fai solo per 1 pixel per immagine, penso che la tua scommessa migliore sia solo una ricerca lineare, una casella di larghezza di 1 pixel alla volta verso l'esterno. Non puoi prendere il primo punto che trovi, se la casella di ricerca è quadrata. Devi stare attento
Sì, la ricerca del vicino più vicino è buona, ma non garantisce che troverai il "più vicino". Lo spostamento di un pixel ogni volta produrrà una ricerca quadrata - le diagonali saranno più lontane rispetto all'orizzontale / verticale. Se questo è importante, ti consigliamo di verificare: continua ad espandersi fino a quando l'orizzontale assoluto ha una distanza maggiore del pixel "trovato", quindi calcola le distanze su tutti i pixel non neri che sono stati individuati.
Ok, sembra interessante. Ho realizzato una versione c ++ di un'anima, non so se questo ti aiuti. Penso che funzioni abbastanza velocemente in quanto è quasi istantaneo su una matrice 800 * 600. Se hai domande, chiedi.
Ci scusiamo per eventuali errori che ho fatto, è un codice di 10 minuti ... Questa è una versione iterativa (avevo intenzione di farne anche una ricorsiva, ma ho cambiato idea). L'algoritmo potrebbe essere migliorato non aggiungendo alcun punto all'array di punti a una distanza maggiore dal punto iniziale rispetto a min_dist, ma ciò comporta il calcolo per ogni pixel (nonostante sia il colore) della distanza dal punto iniziale.
Spero che aiuti
//(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;
}
Sono sicuro che questo potrebbe essere fatto meglio, ma ecco del codice che cerca il perimetro di un quadrato attorno al pixel centrale, esaminando prima il centro e spostandosi verso gli angoli. Se non viene trovato un pixel, il perimetro (raggio) viene espanso fino a quando non viene raggiunto il limite del raggio o viene trovato un pixel. La prima implementazione era un loop che faceva una spirale semplice attorno al punto centrale ma, come notato, non trova il pixel più vicino in assoluto. La creazione di SomeBigObjCStruct all'interno del loop è stata molto lenta: rimuoverlo dal loop lo ha reso abbastanza buono e l'approccio a spirale è quello che è stato utilizzato. Ma ecco comunque questa implementazione: attenzione, poco o nessun test fatto.
È tutto fatto con l'aggiunta e la sottrazione di numeri interi.
- (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;
}
Puoi combinare molti modi per accelerarlo.
- Un modo per accelerare la ricerca di pixel è utilizzare quella che chiamo mappa di ricerca spaziale. È fondamentalmente una mappa sottocampionata (diciamo di 8x8 pixel, ma è un compromesso) dei pixel in quel blocco. I valori possono essere & Quot; nessun pixel impostato & Quot; " pixel parziali impostati " " tutti i pixel impostati " ;. In questo modo una lettura può dire se un blocco / cella è pieno, parzialmente pieno o vuoto.
- scansionare una scatola / rettangolo attorno al centro potrebbe non essere l'ideale perché ci sono molti pixel / celle che sono molto lontani. Uso un algoritmo di disegno circolare (Bresenham) per ridurre il sovraccarico.
- la lettura dei valori di pixel non elaborati può avvenire in batch orizzontali, ad esempio un byte (per una dimensione della cella di 8x8 o multipli di esso), dword o long. Questo dovrebbe darti di nuovo un serio aumento di velocità.
- puoi anche usare più livelli di " mappe di ricerca spaziale " è di nuovo un compromesso.
Per il calcolo della distanza è possibile utilizzare la tabella di ricerca menzionata, ma è un compromesso tra larghezza di banda (cache) e velocità di calcolo (non so come si comporti su una GPU per esempio).
Farei una semplice tabella di ricerca: per ogni pixel, precalcolerei la distanza dal pixel non nero più vicino e memorizzerei il valore nello stesso offset del pixel corrispondente. Naturalmente, in questo modo avrai bisogno di più memoria.
