Algorithme rapide de polar -> cartésien de conversion

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

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

Cela donne un sous-boucle à l'intérieur de l'extérieur for imbriquées en boucle, j'ai donc une complexité de O(N^4). Une image 512x512 utilise toute une minute. Bien sûr, un genre de complexité qui ne peut pas être utilisé, alors je me demandais si quelqu'un sait de toute algorithmes plus rapides pour ce faire?

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

Vous en remercie d'avance.

EDIT: La gamme va de 0 à r_max, pas -r_max à r_max tel qu'il était avant. Je vois qu'il y a eu quelques missunderstandings. J'ai utilisé la normale, inverse, la conversion;


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

Le problème c'est que je dois d'abord convertir les valeurs x et y de x' et y' les valeurs, car 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. Donc, je dois convertir chaque valeur de pixel dans la valeur de la grille, puis de trouver les r et les valeurs de thêta. Quand j'ai trouvé le r et theta les valeurs que j'ai à courir à travers deux vecteurs, la gamme et th_vec, pour trouver le pixel dans l'image d'origine qui correspond à:

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

Cela me donne une complexité de O(n^4), depuis le th_vec et la gamme des vecteurs sont de la même taille que l'image. Donc, si j'ai une matrice carrée de 512x512 éléments, je dois courir à travers 68 719 476 736 éléments, ce qui est une façon lente. Alors je me demandais si il existe un algorithme plus rapide? Je ne peux pas changer les données d'entrée, pour autant que je sais, c'est la seule façon de le faire si vous ne commencez pas par triangulation et d'autres choses, mais cela est coûteux en temps de la mémoire.

Qu'est-ce? Aussi, pourquoi ne pas vous avez soit l'angle de 0 à pi ou une plage de 0 à r_max? 2*pi donne un cercle complet, alors pourquoi auriez-vous besoin d'négatif de la distance?
Est votre grille à coordonnées polaires partitionné de manière uniforme à l'égard des coordonnées polaires?
Si vous trouvez r_0 et th_0 comme certaine valeur à virgule flottante à partir de votre x,y puis vous n'avez qu'à regarder les quatre paires (r,e) dans votre polaire de l'image, c'est à dire les quatre plus proches voisins (r_0,th_0), de sorte que les quatre combinaisons de plancher(r_0),ceil(r_0) et le plancher(th_0),ceil(th_0) où floor() et ceil() produire quelque chose qui est arrondie à votre grille à coordonnées polaires.

OriginalL'auteur martiert | 2009-08-17

10

Comment sur
```
x=r*cos(angle)
y=r*sin(angle)
```
C'est la façon standard de la conversion de polar à Cartésien, et, sauf si vous allez utiliser un certain type de lecture de la table, il n'y a pas vraiment une option plus rapide.

Modifier: 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 à l'aide de 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 sera pas entier, de sorte que vous avez à faire une sorte d'interpolation de l'image I. La façon la plus simple pour ce faire est tout simplement pour arrondir angle et r; cela vous donnera le plus proche voisin de l'interpolation. Si vous avez besoin d'une meilleure qualité, essayez d'autres types sophistiqués de l'interpolation comme bilinéaire ou bicubique interpolation.

Vous devez décrire comment remplir la totalité de l'image, de sorte que la transformation inverse est plus probable utile, sauf si vous êtes à l'aide de quelques petits malins de la méthode d'interpolation.

OriginalL'auteur Martin B

Vous pourriez boucle sur chaque pixel dans le polar de l'image de la carte et ensuite rendre l'arc qui en résulte dans la section cartésiennes dans le plan image:

polar cartésiennes de 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);
    }
}

Beaucoup de dessin bibliothèques ont intégré dans les fonctions de dessin de l'arc de section, mais vous pouvez toujours juste approximatif 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);
}

OriginalL'auteur e.James

3

Si vous ne se soucient pas de lissage, pourquoi ne pas vous venez de calculer les coordonnées polaires pour chaque destination Cartésien pixel de coordonnées et de lire la valeur de la couleur? Voir http://en.wikipedia.org/wiki/Polar_coordinate_system#Converting_between_polar_and_Cartesian_coordinates si vous avez besoin d'aide.

oui - Si vous voulez que l'image finale à pourvoir, il est préférable de faire l'inverse de transformation et d'interpoler dans l'image source.

OriginalL'auteur Jonathan Graehl
1

Si votre grille est partitionné de manière uniforme à l'égard des coordonnées polaires alors votre algorithme peut être réduite à O(N^2) si vous profitez du fait que le point le plus proche de (r, theta) sera l'un des quatre coins de la grille de l'élément dans lequel elle est contenue.

Dans le cas plus général où le réseau électrique est le produit de l'arbitraire des partitions de la r et theta dimensions, qui peut atteindre O (N log N)^2) si vous avez à la recherche de l'emplacement du point dans chaque partition. Toutefois, si les partitions ont été systématiquement construit, vous devriez être en mesure de descendre à O(N^2).

OriginalL'auteur Richard Dunlap
0

La mémoire qui flanche, mais il peut y avoir une version rapide de cet algorithme qui implique la FFT. Une fois, j'ai pris un cours sur l'imagerie médicale et il semble que ce genre de choses arriverait quand untransforming/pixellisation des balayages de CT. Quelques mots clés de la recherche serait la transformée de radon, le filtre backprojection algorithme et la TOMODENSITOMÉTRIE. J'ai regardé ces brièvement sur wikipédia, et rien n'a sauté, mais peut-être un examen plus approfondi serait à son tour quelques pièces d'or.

OriginalL'auteur RAC
0

O(N²log(N)) algorithme:
- Tableau S sera utilisé pour la source la plus proche (polar) coord par cartésien coord.
- S commence rempli avec un "non-initialisées encore" de la valeur. (Python: Aucun, Haskell: Rien, etc.)
- O(N²) - Itérer toutes vos coordonnées polaires.
  - Traduire cartésiennes coord
  - Trouver le plus proche cartésien coord dans votre image de destination. (par arrondissement et d'appliquer des bordures)
  - Remplir la cellule concernée dans S avec cette coordonner
- O(N²log(N)) - Effectuer une modification de l'algorithme de Dijkstra, comme décrit ci-dessous:
  - Le "Graphique" pour notre algorithme de recherche est comme suit:
    
    Toutes les cellules de la S sont des nœuds
    
    Une cellule voisins sont ceux que le Roi du jeu d'échecs peut se déplacer à partir de ce
  - Le "Score" d'une cellule est infini s'il n'est pas initialisé, et de la distance à partir de la nature intacte
    cartésien coord de la polaire coord son pointant vers
  - Lors de la mise à jour d'un voisin de cellule N nous mettre la valeur de la cellule N (mais comme dans Dijkstra, seulement si il fait son meilleur score que son score actuel)
  - Le point de départ est la matrice S initialisé comme décrit ci-dessus
OriginalL'auteur yairchu
0

Si toutes vos images sont 512x512 puis je utiliser une table de recherche que des cartes pondéré ensemble de pixels dans votre polar image de la cartésienne de l'image. C'est beaucoup de travail en amont, mais rend votre calcul final O(n^2). Si un LUT n'est pas une option, alors que j'avais utilisation:
```
x=r*cos(angle)
y=r*sin(angle)
```
Sur chaque pixel dans le polar de l'image de la carte "d'un pixel dans le cartésien de l'image, où le pixel de sortie est la moyenne de tous les pixels d'entrée qui tombent sur elle. Ensuite, appliquer des dilatations répétées jusqu'à ce qu'il n'y a pas non initialisée pixels à gauche. Pour la dilatation vous utilisez un 3x3 élément de structuration et de remplacer uniquement la valeur du pixel de sortie avec la valeur de la centre de pixel si il n'avaient auparavant aucune valeur. Puis, comme une mesure finale, appliquer un filtre gaussien pour l'ensemble de l'image pour lisser les bords durs. C'est la méthode la plus rapide je pense, qui va produire une image qui est agréable à regarder dans un laps de temps raisonnable.

OriginalL'auteur jilles de wit

Vous devez vous connecter pour publier un commentaire.