Encontrar el píxel no negro más cercano en una imagen rápidamente
https://stackoverflow.com/questions/307445
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
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 se me ocurre es construir un árbol kd para los píxeles. pero realmente me gustaría evitar un preprocesamiento tan costoso. Además, 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 este algo.
Solución
Como dice Pyro, busque el perímetro de un cuadrado que sigue moviendo un píxel a la vez desde su punto original (es decir, aumentando el ancho y la altura en dos píxeles a la vez). Cuando golpeas un píxel que no es negro, calculas la distancia (este es tu primer cálculo costoso) y luego continúas buscando hacia afuera hasta que el ancho de tu caja sea el doble de la distancia al primer punto encontrado (cualquier punto más allá de este no puede estar más cerca) que tu píxel encontrado original). Guarde los puntos no 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 costoso.
Actualización : Debido a que aquí está calculando distancias de píxel a píxel (en lugar de ubicaciones de punto flotante de precisión arbitraria), puede acelerar este algoritmo sustancialmente utilizando una tabla de búsqueda precalculada ( solo un conjunto de alto por ancho) para darle distancia en 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 álgebra de Pitágoras o matriz) por cada píxel coloreado que encuentre. Esta matriz podría incluso precalcularse e integrarse en su aplicación como un recurso, para ahorrarle el tiempo de cálculo inicial (esto es probablemente 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 moverse un píxel a la vez hacia las esquinas (tiene 8 puntos de búsqueda en movimiento, lo que podría hacer que esto sea más problemático de lo que vale, dependiendo de los requisitos de su aplicación). Tan pronto como localice un píxel de color, no es necesario 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 que el punto encontrado (nuevamente comenzando en los ejes y deteniéndose cuando la distancia se alcanza el límite). 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 200x200 (o cualquier tamaño que funcione para sus datos), solo buscará dentro de un círculo delimitado por el píxel, haciendo solo búsquedas y < > comparaciones.
Otros consejos
Personalmente, ignoraría la sugerencia de MusiGenesis de una tabla de búsqueda.
Calcular la distancia entre píxeles no es costoso, particularmente en cuanto a esta prueba inicial, no necesita la distancia real, por lo que no es necesario sacar la raíz cuadrada. Puede trabajar con la 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...
Entonces, en cada iteración, por lo tanto, solo necesita conservar algunas variables intermedias:
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 bits, sumas y restas :)
Por supuesto, en cualquier CPU moderna decente, calcular r ^ 2 = dx * dx + dy * dy podría ser tan rápido como esto ...
No especificó cómo desea medir la distancia. Asumiré L1 (rectilíneo) porque es más fácil; posiblemente estas ideas podrían modificarse para L2 (Euclidiana).
Si solo está haciendo esto por relativamente pocos píxeles, simplemente busque hacia afuera desde el píxel de origen en espiral hasta que encuentre uno que no sea negro.
Si está haciendo esto para muchos / todos ellos, ¿qué tal esto ?: Construya una matriz 2D del tamaño de la imagen, donde cada celda almacene la distancia al píxel no negro más cercano (y si es necesario, las coordenadas de ese píxel). Realice cuatro barridos de línea: de izquierda a derecha, de derecha a izquierda, de abajo hacia arriba y de arriba hacia abajo. Considere el barrido de izquierda a derecha; Mientras barre, mantenga una columna 1-D que contenga el último píxel no negro visto en cada fila, y marque cada celda en la matriz 2-D con la distancia y / o coordenadas de ese píxel. O (n ^ 2).
Alternativamente, un árbol k-d es excesivo; podrías usar un quadtree. Solo un poco más difícil de codificar que mi barrido de línea, un poco más de memoria (pero menos del doble), y posiblemente más rápido.
Buscar " Búsqueda de vecino más cercano " ;, 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 solo una búsqueda lineal, un cuadro de 1 píxel de ancho en el exterior. No puede tomar el primer punto que encuentre, si su cuadro de búsqueda es cuadrado. Tienes que tener cuidado
Sí, la búsqueda de vecino más cercano es buena, pero no garantiza que encontrará el 'más cercano'. 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á verificarlo: continúe expandiéndose 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 ubicaron.
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 desde el punto inicial que min_dist, pero esto implica calcular para cada píxel (a pesar de su color) la distancia desde el punto inicial.
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 primero el centro 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 bucle que hacía una espiral simple alrededor del punto central pero, como se señaló, no encuentra el píxel más cercano absoluto. La creación de SomeBigObjCStruct dentro del bucle fue muy lenta: eliminarla del bucle lo hizo lo suficientemente bueno y el enfoque en espiral es lo que se usó. Pero aquí está esta implementación de todos modos: tenga cuidado, se realizan pocas o ninguna prueba.
Todo se hace con suma y resta de enteros.
- (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 de acelerarlo.
- Una forma de acelerar la búsqueda de píxeles es usar lo que yo llamo un mapa de búsqueda espacial. Básicamente es un mapa de muestreo reducido (digamos de 8x8 píxeles, pero es una compensación) de los píxeles en ese bloque. Los valores pueden ser & Quot; ningún conjunto de píxeles & Quot; " píxeles parciales establecidos " " todos los píxeles establecidos " ;. De esta manera, una lectura puede determinar si un bloque / celda está lleno, parcialmente lleno o vacío.
- escanear un cuadro / 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 formato puede ocurrir en lotes horizontales, por ejemplo, un byte (para un tamaño de celda de 8x8 o múltiplos), dword o long. Esto debería darle una aceleración seria nuevamente.
- 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 ancho de banda (caché) frente a una compensación de velocidad de cálculo (no sé cómo funciona en una GPU, por ejemplo).
Haría una tabla de búsqueda simple: para cada píxel, precalcule la distancia al píxel no negro más cercano y almacene el valor en el mismo desplazamiento que el píxel correspondiente. Por supuesto, de esta manera necesitarás más memoria.
