Algoritmo rápido para polar -> conversión cartesiana

Question

Tengo una imagen en una cuadrícula polar. Esta imagen debe transformarse en una cuadrícula cartesiana, pero el único algoritmo que conozco es realmente lento para esto. Ahora utilizo la grilla cartesiana, para cada punto encuentro los valores r y theta, y luego miro en dos vectores para encontrar el error más pequeño definido por:

min {(th_vec - theta)^2 + (rango - r)^2}

Esto proporciona un bucle forzado anidado dentro del bucle for externo anidado, por lo que tengo una complejidad de O (N^4). Una imagen de 512x512 usa un minuto completo para completarse. Por supuesto, una complejidad como esa no se puede usar, entonces me pregunto si alguien sabe de algún algoritmo más rápido para hacer esto.

Tengo la imagen y los dos vectores. El eje X de la imagen es el ángulo, mientras que el eje Y de la imagen es la longitud desde el centro. El ángulo siempre es de 0-2pi, y el rango va de 0 a r_max.

Gracias de antemano.

EDITAR: El rango va de 0 a r_max, no -r_max a r_max como estaba antes. Veo que ha habido algunos malentendidos. He usado la conversión normal, inversa, con;

 

r=sqrt(x^2 + y^2); 
theta=atan2(y,x); 
 

El problema es que tengo para convertir primero los valores de x y valores de y a x 'y y', ya que la rejilla es de -r_max a R_max en la imagen resultante, pero en píxeles en los datos. Así que tengo una imagen de 512x512, pero r_max puede ser algo así como 3.512. Así que tengo que convertir cada valor de píxel en el valor de la grilla, luego hallar los valores r y theta. Cuando he encontrado los valores r y theta, tengo que ejecutar dos vectores, rango y th_vec, para encontrar el píxel en la imagen original que coincide con:

min {(rango - r)^2 + (th_vec - theta)^2}

Esto me da una complejidad de O (n^4), ya que th_vec y los vectores de rango son del mismo tamaño que la imagen. Entonces, si tengo una matriz cuadrada de 512x512 elementos, tengo que ejecutar a través de 68 719 476 736 elementos, que es muy lento. Entonces, me pregunto si hay un algoritmo más rápido. No puedo cambiar los datos de entrada, así que, hasta donde yo sé, esta es la única forma de hacerlo si no comienzas con la triangulación y esas cosas, pero es caro en tiempos de memoria.

Answer 1

¿Qué tal

x=r*cos(angle) 
y=r*sin(angle) 

Ésta es la manera estándar de conversión desde zonas polares a cartesianas, ya menos que usted va a utilizar algún tipo de búsqueda en la tabla, no es realmente una opción más rápida.

Editar: wrang wrang tiene un buen punto. Si usted está tratando de transformar una imagen en coordenadas polares I(angle, r) a una imagen en coordenadas cartesianas I_new(x, y), que está definitivamente mejor usar la transformación inversa, de la siguiente manera:

for x=1,...,width 
    for y=1,...,height 
     angle=atan2(y, x) 
     r=sqrt(x^2+y^2) 
     I_new(x, y)=I(angle, r) 
    end 
end 

se

Como regla general, no angle y r ser entero, por lo que debe hacer algún tipo de interpolación en la imagen I. La forma más sencilla de hacerlo es simplemente redondeando angle y r; esto le dará nearest-neighbour interpolation. Si necesita una mejor calidad, pruebe con tipos de interpolación más sofisticados, como bilinear o bicubic interpolación.

Answer 2

Si no le importa el suavizado, ¿por qué no calcula la coordenada polar para cada coordenada de píxel cartesiano de destino y lee el valor del color? Consulte http://en.wikipedia.org/wiki/Polar_coordinate_system#Converting_between_polar_and_Cartesian_coordinates si necesita ayuda para hacerlo.

Answer 3

Si su grilla está uniformemente dividida con respecto a las coordenadas polares, entonces su algoritmo puede reducirse a O (N^2) si aprovecha el hecho de que el punto más cercano a (r, theta) será uno de las cuatro esquinas del elemento de la rejilla en el que está contenido.

En el caso más general donde la cuadrícula es el producto de particiones arbitrarias de las dimensiones r y theta, eso podría crecer a O ((N log N)^2) si tiene que buscar la ubicación del punto en cada partición Sin embargo, si las particiones se construyeron sistemáticamente, debería poder regresar a O (N^2).

Answer 4

Se podría bucle sobre cada píxel en el mapa de imagen polar y luego hacer que la sección de arco resultante en el plano de la imagen cartesiana:

polar to cartesian conversion http://img24.imageshack.us/img24/4635/polartocartesian.png

const float dR = 2*r_max/polar_image_height; 
const float dA = 2*pi/polar_image_width; 

float angle; 
float radius; 
for (int polar_x = 0; polar_x < polar_image_width; polar_x++) 
{ 
    for (int polar_y = 0; polar_y < polar_image_height; polar_y++) 
    { 
     angle = polar_x * dA; 
     radius = polar_y * dR - r_max; 
     DrawArcSection(radius, radius+dR, angle, angle+dA); 
    } 
} 

Muchas bibliotecas de dibujo han incorporado funciones de dibujo esa sección de arco, pero siempre puedes aproximarla con un simple polígono:

void DrawArcSection(float minRadius, float maxRadius, 
        float minAngle, float maxAngle) 
{ 
    point P1 = MakePoint(minRadius * cos(minAngle) + image_width/2, 
         minRadius * sin(minAngle) + image_height/2); 
    point P2 = MakePoint(minRadius * cos(maxAngle) + image_width/2, 
         minRadius * sin(maxAngle) + image_height/2); 
    point P3 = MakePoint(maxRadius * cos(minAngle) + image_width/2, 
         maxRadius * sin(minAngle) + image_height/2); 
    point P3 = MakePoint(maxRadius * cos(maxAngle) + image_width/2, 
         maxRadius * sin(maxAngle) + image_height/2); 

    DrawPolygon(P1, P2, P3, P4); 
} 

Answer 5

La memoria falla, pero puede haber una versión rápida de este algoritmo que involucra la FFT. Érase una vez que tomé una clase sobre imágenes médicas y parece que este tipo de cosas surgieron cuando las tomografías computarizadas no se transformaron/rasterizaron. Algunas palabras clave para buscar serían la transformación del radón, el algoritmo de retroproyección filtrado y las tomografías computarizadas. Lo busqué brevemente en wikipedia y no saltó nada, pero tal vez una revisión más exhaustiva arrojaría algo de oro.

Answer 6

O (N log (N)) algoritmo:

• matriz S se utiliza para la fuente más cercana coord (polar) por coord cartesiano.
• S comienza lleno con un valor "no inicializado todavía". (Python: None, Haskell: Nothing, etc.)
• O (N) - Iterar todas las coordenadas polares.
  • Traducir al coord cartesiano
  • Encuentra más cercano coord cartesiano su imagen de destino en.(Redondeando y las fronteras que aplican)
  • relleno en la celda correspondiente en S con esta coordenada
• O (N log (N)) - Realizar un algoritmo de Dijkstra modificado como se describe a continuación:
  • el "Gráfico" para nuestro algoritmo de búsqueda es el siguiente:
    • Todas las células de S son nodos
    • los vecinos de una célula son aquellos que el rey en el ajedrez se puede mover a
    de ella
  • El "Score" de una célula es infinito si no se ha inicializado, y distancia de la virgen coord cartesiano de la coord su polar que apunta a
  • Al actualizar una vecina de la celda N nos poner el valor de la celda N en el mismo (pero como en Dijkstra, sólo si hace su puntuación mejor que su puntuación actual)
  • el punto de partida es la matriz S inicializa como se describe anteriormente

Answer 7

Si todo tu las imágenes son 512x512 y luego usaría una tabla de búsqueda que mapea un conjunto de píxeles pesados ​​en su imagen polar a la imagen cartesiana. Esto es mucho trabajo por adelantado pero hace su cálculo final O (n^2). Si una LUT no es una opción y que haría uso:

x=r*cos(angle) 
y=r*sin(angle) 

En cada píxel de la imagen polar para asignarlo a "un" pixel en la imagen cartesiana, donde el píxel de salida es el promedio de todas las entradas píxeles que caen sobre él. Luego aplique dilataciones repetidas hasta que no queden píxeles sin inicializar. Para la dilatación, utiliza un elemento estructurador de 3x3 y solo reemplaza el valor del píxel de salida con el valor del píxel central si anteriormente no tenía ningún valor. Luego, como medida final, aplique un filtro gaussiano a toda la imagen para suavizar los bordes duros. Este es el método más rápido que puedo pensar que producirá una imagen agradable de mirar en un tiempo razonable.