performance - universo - Encontrar el píxel no negro más cercano en una imagen rápida
que hay dentro de un agujero negro (9)
Tengo una imagen 2D al azar y escasamente dispersa con píxeles.
dado un punto en la imagen, necesito encontrar la distancia al píxel más cercano que no está en el color de fondo (negro).
¿Cuál es la forma más rápida de hacer esto?
El único método que podría encontrar es construir un árbol kd para los píxeles. pero realmente me gustaría evitar un preprocesamiento tan caro. también, parece que un árbol kd me da más de lo que necesito. Solo necesito la distancia a algo y no me importa qué es esto.
Busque "Búsqueda de vecinos más cercanos", los primeros dos enlaces en Google deberían ayudarlo.
Si solo está haciendo esto por 1 píxel por imagen, creo que su mejor opción es simplemente una búsqueda lineal, un cuadro de 1 píxel de ancho en el momento hacia el exterior. No puede tomar el primer punto que encuentre, si su cuadro de búsqueda es cuadrado. Tienes que tener cuidado
Me gustaría hacer una tabla de búsqueda simple: para cada píxel, precalcular la distancia al píxel no negro más cercano y almacenar el valor en el mismo desplazamiento que el píxel correspondiente. Por supuesto, de esta manera necesitarás más memoria.
No especificó cómo quiere medir la distancia. Asumiré L1 (rectilíneo) porque es más fácil; posiblemente estas ideas podrían modificarse para L2 (euclidiano).
Si solo hace esto para relativamente pocos píxeles, simplemente busque hacia afuera desde el píxel fuente en espiral hasta que golpee uno que no sea negro.
Si está haciendo esto para muchos / todos ellos, qué tal esto: construya una matriz bidimensional del tamaño de la imagen, donde cada celda almacena la distancia al píxel no negro más cercano (y si es necesario, las coordenadas de ese píxel). ) Haga cuatro barridos de línea: de izquierda a derecha, de derecha a izquierda, de abajo hacia arriba y de arriba a abajo. Considere el barrido de izquierda a derecha; mientras barre, mantenga una columna en 1-D que contenga el último píxel no negro que se ve en cada fila, y marque cada celda en la matriz bidimensional con la distancia y / o las coordenadas de ese píxel. O (n ^ 2).
Alternativamente, un árbol kd es excesivo; podrías usar un quadtree. Solo un poco más difícil de codificar que el barrido de mi línea, un poco más de memoria (pero menos del doble), y posiblemente más rápido.
Sí, la búsqueda de vecinos más cercanos es buena, pero no garantiza que encuentre la más cercana. Mover un píxel cada vez producirá una búsqueda cuadrada: las diagonales estarán más alejadas que la horizontal / vertical. Si esto es importante, querrá verificar: continúe expandiendo hasta que la horizontal absoluta tenga una distancia mayor que el píxel ''encontrado'', y luego calcule las distancias en todos los píxeles no negros que se localizaron.
Como dice Pyro, busca en el perímetro de un cuadrado que sigues moviendo un píxel cada vez desde tu punto original (es decir, aumentando el ancho y el alto en dos píxeles a la vez). Cuando tocas un píxel no negro, calcules la distancia (este es tu primer cálculo caro) y luego sigues buscando hacia afuera hasta que el ancho de tu casilla sea el doble de la distancia al primer punto encontrado (cualquier punto más allá de esto no puede estar más cerca) que su pixel encontrado original). Guarde los puntos que no sean negros que encuentre durante esta parte, y luego calcule cada una de sus distancias para ver si alguno de ellos está más cerca que su punto original.
En un hallazgo ideal, solo tiene que hacer un cálculo de distancia caro.
Actualización : debido a que está calculando distancias de píxel a píxel aquí (en lugar de ubicaciones de coma flotante de precisión arbitraria), puede acelerar este algoritmo de manera sustancial utilizando una tabla de búsqueda precalculada (solo una matriz de altura por anchura) para darle distancia como una función de x y y . Una matriz de 100x100 le cuesta esencialmente 40K de memoria y cubre un cuadrado de 200x200 alrededor del punto original, y le ahorra el costo de hacer un cálculo de distancia costoso (ya sea de Pythagorean o álgebra matricial) para cada pixel coloreado que encuentre. Esta matriz podría incluso precalcularse e incorporarse en su aplicación como un recurso, para ahorrarle el tiempo de cálculo inicial (esto probablemente sea una exageración grave).
Actualización 2 : Además, hay formas de optimizar la búsqueda en el perímetro cuadrado. Su búsqueda debe comenzar en los cuatro puntos que se cruzan con los ejes y mover un píxel cada vez hacia las esquinas (tiene 8 puntos de búsqueda en movimiento, lo que fácilmente podría ocasionar más problemas de los que vale la pena, según los requisitos de su aplicación). Tan pronto como localice un pixel coloreado, no hay necesidad de continuar hacia las esquinas, ya que los puntos restantes están más lejos del origen.
Después del primer píxel encontrado, puede restringir aún más el área de búsqueda adicional requerida al mínimo utilizando la tabla de búsqueda para asegurarse de que cada punto buscado esté más cerca del punto encontrado (comenzando de nuevo en los ejes y deteniéndose cuando se alcanza el límite de distancia) ) Esta segunda optimización probablemente sería demasiado costosa de emplear si tuviera que calcular cada distancia sobre la marcha.
Si el píxel más cercano está dentro del cuadro de 200x200 (o el tamaño que sea que funcione para sus datos), solo buscará dentro de un círculo delimitado por el píxel, haciendo solo búsquedas y <> comparaciones.
Personalmente, ignoraría la sugerencia de MusiGenesis de una tabla de búsqueda.
Calcular la distancia entre los píxeles no es costoso, sobre todo porque en esta prueba inicial no necesita la distancia real, por lo que no es necesario tomar la raíz cuadrada. Puedes trabajar con distancia ^ 2, es decir:
r^2 = dx^2 + dy^2
Además, si va hacia afuera un píxel a la vez, recuerde que:
(n + 1)^2 = n^2 + 2n + 1
o si nx es el valor actual y ox es el valor anterior:
nx^2 = ox^2 + 2ox + 1
= ox^2 + 2(nx - 1) + 1
= ox^2 + 2nx - 1
=> nx^2 += 2nx - 1
Es fácil ver cómo funciona esto:
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...
Por lo tanto, en cada iteración, solo necesita retener algunas variables intermedias así:
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 cálculo con solo cambios de bit, suma y resta :)
Por supuesto, en cualquier CPU moderna decente, calcular r ^ 2 = dx * dx + dy * dy podría ser tan rápido como esto ...
Ok, esto suena interesante. Hice una versión c ++ de una soulution, no sé si esto te ayuda. Creo que funciona lo suficientemente rápido ya que es casi instantáneo en una matriz de 800 * 600. Si tiene alguna pregunta solo pregunte.
Perdón por los errores que he cometido, es un código de 10 minutos ... Esta es una versión iterativa (estaba planeando hacer una recursiva también, pero he cambiado de opinión). El algoritmo podría mejorarse al no agregar ningún punto a la matriz de puntos que está a una distancia mayor del punto de inicio que el min_dist, pero esto implica calcular para cada píxel (a pesar de su color) la distancia desde el punto de inicio.
Espero que ayude
//(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;
}
Estoy seguro de que esto podría hacerse mejor, pero aquí hay un código que busca el perímetro de un cuadrado alrededor del píxel central, examinando el centro primero y moviéndose hacia las esquinas. Si no se encuentra un píxel, el perímetro (radio) se expande hasta que se alcanza el límite del radio o se encuentra un píxel. La primera implementación fue un ciclo haciendo una espiral simple alrededor del punto central, pero como se observó, no se encuentra el píxel más cercano absoluto. La creación de SomeBigObjCStruct dentro del ciclo fue muy lenta: eliminarlo del ciclo lo hizo lo suficientemente bueno y el enfoque en espiral es lo que se usó. Pero aquí está esta implementación de todos modos. Cuidado, se realizaron muy pocas pruebas.
Todo se hace con sumas y restas enteras.
- (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;
}
Puede combinar muchas formas para acelerarlo.
- Una forma de acelerar la búsqueda de píxeles es usar lo que llamo un mapa de búsqueda espacial. Básicamente es un mapa muestreado (digamos de 8x8 píxeles, pero es una compensación) de los píxeles en ese bloque. Los valores pueden ser "sin píxeles establecidos" "píxeles parciales establecidos" "todos los píxeles configurados". De esta forma, una lectura puede decir si un bloque / celda está lleno, parcialmente lleno o vacío.
- escanear una caja / rectángulo alrededor del centro puede no ser ideal porque hay muchos píxeles / celdas que están muy lejos. Utilizo un algoritmo de dibujo circular (Bresenham) para reducir la sobrecarga.
- la lectura de los valores de píxel sin procesar puede ocurrir en lotes horizontales, por ejemplo, un byte (para un tamaño de celda de 8x8 o múltiplos de él), dword o long. Esto debería darte una aceleración seria de nuevo.
- también puede usar múltiples niveles de "mapas de búsqueda espacial", nuevamente es una compensación.
Para el cálculo de la distancia se puede usar la tabla de búsqueda mencionada, pero es un intercambio de ancho de banda (de caché) frente a velocidad de cálculo (no sé cómo funciona en una GPU, por ejemplo).