Recherche rapide du pixel non noir le plus proche dans une image
https://stackoverflow.com/questions/307445
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai une image 2D dispersée de manière aléatoire et dispersée avec des pixels.
Étant donné un point sur l'image, je dois trouver la distance au pixel le plus proche qui n'est pas dans la couleur d'arrière-plan (noir).
Quel est le moyen le plus rapide de faire cela?
La seule méthode que je pourrais trouver est de construire un kd-tree pour les pixels. mais je voudrais vraiment éviter un prétraitement aussi coûteux. de plus, il semble qu'un arbre de kd me donne plus que ce dont j'ai besoin. J'ai seulement besoin de la distance à quelque chose et je me fiche de ce que c'est quelque chose.
La solution
Comme le dit Pyro, recherchez dans le périmètre d'un carré que vous déplacez continuellement d'un pixel à l'autre de votre point d'origine (c'est-à-dire en augmentant la largeur et la hauteur de deux pixels à la fois). Lorsque vous frappez un pixel non noir, vous calculez la distance (ceci est votre premier calcul coûteux), puis continuez votre recherche vers l'extérieur jusqu'à ce que la largeur de votre zone soit égale à deux fois la distance du premier point trouvé (aucun point au-delà ne peut être plus proche) que votre pixel trouvé original). Enregistrez tous les points non noirs que vous avez trouvés au cours de cette partie, puis calculez chacune de leurs distances pour voir s’ils sont plus proches que votre point initial.
Dans une recherche idéale, il vous suffit de faire un calcul de distance coûteux.
Mettre à jour : dans la mesure où vous calculez des distances pixel par pixel (au lieu d'emplacements à virgule flottante de précision arbitraire), vous pouvez accélérer cet algorithme de manière substantielle en utilisant une table de recherche précalculée ( juste un tableau hauteur par largeur) pour vous donner la distance en fonction de x et de y . Une matrice 100x100 vous coûte essentiellement 40K de mémoire et couvre un carré de 200x200 autour du point d'origine, tout en vous évitant le coût d'un calcul de distance coûteux (que ce soit une algèbre de Pythagore ou une matrice) pour chaque pixel coloré trouvé. Ce tableau pourrait même être précalculé et intégré dans votre application en tant que ressource, afin de vous faire épargner le temps de calcul initial (il s'agit probablement d'un dépassement important).
Mise à jour 2 : vous pouvez également optimiser la recherche dans le périmètre carré. Votre recherche doit commencer aux quatre points intersectant les axes et se déplacer pixel par pixel vers les angles (vous avez 8 points de recherche en mouvement, ce qui peut facilement compliquer la tâche, selon les besoins de votre application). Dès que vous localisez un pixel coloré, vous n'avez plus besoin de continuer vers les coins, car les points restants sont tous plus éloignés de l'origine.
Après le premier pixel trouvé, vous pouvez limiter davantage la zone de recherche supplémentaire requise en utilisant la table de correspondance pour vous assurer que chaque point recherché est plus proche que le point trouvé (en partant de nouveau des axes et en vous arrêtant lorsque la distance est atteinte). limite est atteinte). Cette deuxième optimisation serait probablement trop coûteuse si vous deviez calculer chaque distance à la volée.
Si le pixel le plus proche se trouve dans la zone 200x200 (ou quelle que soit la taille qui convienne à vos données), vous effectuerez une recherche uniquement dans un cercle délimité par le pixel, en effectuant uniquement des recherches et des comparaisons < >
Autres conseils
Personnellement, j'ignorerais la suggestion de MusiGenesis de créer une table de correspondance.
Le calcul de la distance entre pixels n’est pas coûteux, en particulier parce que pour ce test initial, vous n’avez pas besoin de la distance réelle, il n’est donc pas nécessaire de prendre la racine carrée. Vous pouvez travailler avec la distance ^ 2, c’est-à-dire:
r^2 = dx^2 + dy^2
En outre, si vous vous déplacez un pixel à la fois, rappelez-vous que:
(n + 1)^2 = n^2 + 2n + 1
ou si nx est la valeur actuelle et ox est la valeur précédente:
nx^2 = ox^2 + 2ox + 1
= ox^2 + 2(nx - 1) + 1
= ox^2 + 2nx - 1
=> nx^2 += 2nx - 1
Il est facile de voir comment cela fonctionne:
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...
Ainsi, à chaque itération, vous ne devez donc conserver que quelques variables intermédiaires, par exemple:
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 calcul avec seulement des décalages, des additions et des soustractions de bits:)
Bien sûr, sur tout processeur moderne décent, le calcul de r ^ 2 = dx * dx + dy * dy pourrait être aussi rapide que cela ...
Vous n'avez pas précisé comment vous souhaitez mesurer la distance. Je supposerai L1 (rectiligne) parce que c'est plus facile; éventuellement, ces idées pourraient être modifiées pour L2 (euclidienne).
Si vous ne le faites que pour relativement peu de pixels, recherchez simplement une spirale externe en partant du pixel source jusqu'à ce que vous en rencontriez un non noir.
Si vous faites cela pour beaucoup / tous, dites-vous ceci: Créez un tableau à deux dimensions de la taille de l'image, où chaque cellule stockera la distance au pixel non noir le plus proche (et si nécessaire, les coordonnées de ce pixel). Effectuez quatre balayages de lignes: de gauche à droite, de droite à gauche, de bas en haut et de haut en bas. Considérez le balayage de gauche à droite; pendant que vous balayez, conservez une colonne 1-D contenant le dernier pixel non noir visible dans chaque ligne et marquez chaque cellule du tableau 2D avec la distance et / ou les coordonnées de ce pixel. O (n ^ 2).
Alternativement, un arbre k-d est overkill; vous pourriez utiliser un quadtree. Seulement un peu plus difficile à coder que mon balayage de ligne, un peu plus de mémoire (mais moins de deux fois plus), et peut-être plus rapide.
Recherche & "Recherche du plus proche voisin &"; les deux premiers liens de Google devraient vous aider.
Si vous ne faites cela que pour 1 pixel par image, je pense que votre meilleur pari est simplement une recherche linéaire, une boîte d'une largeur de 1 pixel à la fin du temps. Vous ne pouvez pas prendre le premier point que vous trouvez, si votre champ de recherche est carré. Vous devez faire attention
Oui, la recherche du voisin le plus proche est bonne, mais ne garantit pas que vous trouverez le "plus proche". Si vous déplacez un pixel à chaque fois, une recherche carrée se produit - les diagonales seront plus éloignées que l’horizontale / verticale. Si cela est important, vous devrez vérifier - continuez à développer jusqu'à ce que l'horizontale absolue ait une distance supérieure au pixel "trouvé", puis calculez les distances sur tous les pixels non noirs localisés.
Ok, cela semble intéressant. J'ai créé une version c ++ d'une soulution, je ne sais pas si cela vous aide. Je pense que cela fonctionne assez vite car c'est presque instantané sur une matrice 800 * 600. Si vous avez des questions, n'hésitez pas.
Désolé pour les erreurs que j'ai commises, c'est un code de 10 minutes ... Il s’agit d’une version itérative (j’avais l’intention de créer une version récursive également, mais j’ai changé d’avis). L’algorithme pourrait être amélioré en n’ajoutant aucun point au tableau de points situé à une distance plus grande du point de départ que min_dist, mais cela implique de calculer pour chaque pixel (malgré sa couleur) la distance depuis le point de départ.
L’espoir que cela aide
//(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;
}
Je suis sûr que cela pourrait être mieux fait, mais voici un code qui explore le périmètre d’un carré autour du pixel central, en examinant d’abord le centre et en se dirigeant vers les coins. Si aucun pixel n'est trouvé, le périmètre (rayon) est étendu jusqu'à ce que la limite du rayon soit atteinte ou qu'un pixel soit trouvé. La première implémentation était une boucle faisant une simple spirale autour du point central, mais comme indiqué, elle ne trouve pas le pixel absolu le plus proche. La création de SomeBigObjCStruct à l'intérieur de la boucle a été très lente - son retrait de la boucle l'a rendu suffisamment bon et c'est l'approche en spirale qui a été utilisée. Mais voici de toute façon cette implémentation - méfiez-vous, peu ou pas de tests.
Tout est fait avec addition et soustraction d'entiers.
- (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;
}
Vous pouvez combiner plusieurs méthodes pour l'accélérer.
- Pour accélérer la recherche de pixels, vous pouvez utiliser ce que j'appelle une carte de recherche spatiale. C'est en gros une carte sous-échantillonnée (disons de 8x8 pixels, mais c'est un compromis) des pixels de ce bloc. Les valeurs peuvent être & "Aucun pixel défini &"; " pixels partiels définis " " tous les pixels définis " ;. De cette façon, une lecture permet de savoir si un bloc / une cellule est plein, partiellement plein ou vide.
- numériser un rectangle / une boîte autour du centre peut ne pas être idéal, car de nombreux pixels / cellules sont très éloignés. J'utilise un algorithme de dessin de cercle (Bresenham) pour réduire les frais généraux.
- la lecture des valeurs de pixels brutes peut se faire par lots horizontaux, par exemple un octet (pour une taille de cellule de 8x8 ou un multiple de celui-ci), dword ou long. Cela devrait vous donner à nouveau une accélération sérieuse.
- vous pouvez également utiliser plusieurs niveaux de & "; cartes de recherche spatiale &" ;, encore une fois, un compromis.
Pour le calcul de la distance, la table de consultation mentionnée peut être utilisée, mais son compromis entre la bande passante et la vitesse de calcul (cache) (je ne sais pas comment il fonctionne sur un processeur graphique, par exemple).
Je ferais une simple table de correspondance - pour chaque pixel, calculez à l'avance la distance jusqu'au pixel non noir le plus proche et stockez la valeur dans le même décalage que le pixel correspondant. Bien sûr, de cette façon, vous aurez besoin de plus de mémoire.
