Algorithme rapide pour la conversion polaire -> cartésienne

Question

J'ai une image sur une grille polaire. Cette image devrait être transformée en une grille cartésienne, mais le seul algorithme que je connais est vraiment lent pour cela. Maintenant, j'utilise la grille cartésienne, pour chaque point je trouve les valeurs r et thêta, puis je regarde dans deux vecteurs pour trouver la plus petite erreur définie par:

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

Cela donne une boucle for imbriquée à l'intérieur de la boucle for externe imbriquée, donc j'ai une complexité de O (N^4). Une image 512x512 utilise une minute entière à compléter. Bien sûr, une telle complexité ne peut pas être utilisée, alors je me demande si quelqu'un connaît des algorithmes plus rapides pour le faire?

J'ai l'image et les deux vecteurs. L'axe X de l'image est l'angle, tandis que l'axe Y de l'image est la longueur du centre. L'angle est toujours de 0-2pi, et la plage va de 0 à r_max.

Merci d'avance.

EDIT: La plage va de 0 à r_max, pas -r_max à r_max tel qu'il était auparavant. Je vois qu'il y a eu des malentendus. J'ai utilisé la conversion normale, inverse, avec;

 

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

Le problème est que j'ai d'abord convertir les valeurs x et y à x « et y » les valeurs, puisque la grille est de -r_max à r_max dans l'image résultante, mais en pixels dans les données. J'ai donc une image 512x512, mais r_max peut être quelque chose comme 3.512. Je dois donc convertir chaque valeur de pixel dans la valeur de la grille, puis trouver les valeurs r et thêta. Quand j'ai trouvé les valeurs r et thêta, je dois parcourir deux vecteurs, range et th_vec, pour trouver le pixel dans l'image originale qui correspond:

min {(range - r)^2 + (th_vec - theta Cela me donne une complexité de O (n^4), puisque les vecteurs th_vec et range ont la même taille que l'image. Donc, si j'ai une matrice carrée de 512x512 éléments, je dois parcourir 68 719 476 736 éléments, ce qui est très lent. Donc je me demande s'il y a un algorithme plus rapide? Je ne peux pas changer les données d'entrée, donc pour autant que je sache, c'est la seule façon de le faire si vous ne commencez pas avec la triangulation et d'autres choses, mais c'est trop cher en temps de mémoire.

Answer 1

Que diriez-vous

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

C'est le moyen standard de conversion de polaire cartésien, et à moins que vous allez utiliser une sorte de consultation de table, il n'y a pas vraiment une option plus rapide.

Édition: Wrang Wrang a un bon point. Si vous essayez de transformer une image en coordonnées polaires I(angle, r) à une image en coordonnées cartésiennes I_new(x, y), vous êtes certainement mieux d'utiliser la transformation inverse, comme suit:

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 

En règle générale, angle et r ne être entier, donc vous devez faire une sorte d'interpolation dans l'image I. La façon la plus simple de le faire est de simplement arrondir angle et r; cela vous donnera nearest-neighbour interpolation. Si vous avez besoin d'une meilleure qualité, essayez des types d'interpolation plus sophistiqués, tels que l'interpolation bilinear ou bicubic.

Answer 2

Si vous ne vous souciez pas du lissage, pourquoi ne calculez-vous pas simplement la coordonnée polaire pour chaque coordonnée de pixel cartésienne de destination et lisez la valeur de couleur? Voir http://en.wikipedia.org/wiki/Polar_coordinate_system#Converting_between_polar_and_Cartesian_coordinates si vous avez besoin d'aide pour le faire.

Answer 3

Si votre grille est partitionnée uniformément par rapport aux coordonnées polaires, alors votre algorithme peut être réduit à O (N^2) si vous profitez du fait que le point le plus proche de (r, theta) sera l'un des les quatre coins de l'élément de grille dans lequel il est contenu.

Dans le cas plus général où la grille est le produit de partitions arbitraires des dimensions r et thêta, cela pourrait augmenter à O ((N log N)^2) si vous devez rechercher l'emplacement du point dans chaque partition. Cependant, si les partitions étaient systématiquement construites, vous devriez pouvoir redescendre à O (N^2).

Answer 4

Vous boucle pouvez sur chaque pixel dans la carte d'image polaire puis rendre la section arc résultant dans le plan d'image cartésienne:

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); 
    } 
} 

De nombreuses bibliothèques de dessin ont intégré des fonctions de dessin cette section d'arc, mais vous pouvez toujours juste l'approximer avec un simple polygone:

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 mémoire échoue, mais il pourrait y avoir une version rapide de cet algorithme qui implique la FFT. Il était une fois, j'ai pris un cours sur l'imagerie médicale et il semble que ce genre de choses a surgi lors de la numérisation CT/rastérisation sans transformation. Certains mots-clés à rechercher seraient la transformation du radon, l'algorithme de rétroprojection filtrée et les tomodensitogrammes. J'ai regardé cela brièvement sur wikipedia et rien n'a sauté, mais peut-être un examen plus approfondi donnerait de l'or.

Answer 6

O (N log (N)) algorithme:

• matrice S est utilisé pour la source la plus proche (polaire) Coord par cartésiennes Coord.
• S commence rempli avec une valeur "pas encore initialisé". (Python: Aucun, Haskell: Rien, etc.)
• O (N) - Itérer toutes vos coordonnées polaires.
  • Traduire en cartésienne coord
  • Trouver plus proche coord cartésienne dans votre image de destination.(Par l'arrondissement et l'application des frontières)
  • remplissage dans la cellule correspondante dans S avec cette coordonnée
• O (N log (N)) - effectuer un algorithme de Dijkstra modifié comme décrit ci-dessous:
  • le « graphique » pour notre algorithme de recherche est la suivante:
    • Toutes les cellules de S sont des noeuds
    • voisins est une cellule sont ceux du roi dans les échecs peuvent passer à de lui
  • Le « score » d'une cellule est infinie si elle n'est pas initialisé, et la distance de la intacte coord cartésienne du coord polaire son pointage à
  • Lorsque la mise à jour d'un voisin de cellule N nous mettre la valeur de la cellule N en elle (mais comme dans Dijkstra, que si elle rend son score mieux que son score actuel)
  • le point de départ est le tableau S initialisé comme décrit ci-dessus

Answer 7

Si tout votre les images sont 512x512 alors j'utiliserais une table de recherche qui mappe un ensemble pondéré de pixels dans votre image polaire à l'image cartésienne. C'est beaucoup de travail à l'avance mais fait votre calcul final O (n^2). Si une LUT n'est pas une option, puis j'utiliser:

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

Sur chaque pixel de l'image polaire à la carte à pixel « a » dans l'image cartésienne, où le pixel de sortie est la moyenne de toutes les entrées les pixels qui tombent dessus. Appliquez ensuite des dilatations répétées jusqu'à ce qu'il ne reste plus de pixels non initialisés. Pour la dilatation, vous utilisez un élément structurant 3x3 et ne remplacez la valeur du pixel de sortie par la valeur du pixel central que si elle n'avait auparavant aucune valeur. Puis, comme mesure finale, appliquez un filtre gaussien sur toute l'image pour lisser les bords durs. C'est la méthode la plus rapide que je puisse imaginer qui produira une image agréable à regarder dans un laps de temps raisonnable.