J'ai une image sur une grille polaire. Cette image doit être transformée 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 que je trouve les valeurs R et THeta, puis je regarde deux vecteurs pour trouver la plus petite erreur définie par:
min {(th_vec - theta) ^ 2 + (gamme - R ) ^ 2}
Ceci donne une boucle imbriquée à l'intérieur de la boucle intégrée externe, donc j'ai une complexité de O (n ^ 4). Une image 512x512 utilise une minute complète à compléter. Bien sûr, une complexité comme celle-ci ne peut pas être utilisée, je me demande donc si quelqu'un connaît des algorithmes plus rapides de faire cela?
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 du centre. L'angle est toujours de 0 à 14 ci et la plage va de 0 à R_max.
Merci d'avance.
EDIT: La plage va de 0 à r_max, pas -r_max, non -R_max à r_max comme il se tenait auparavant. Je vois qu'il y a eu quelques missionnaires. J'ai utilisé la conversion normale, inverse, avec; Le problème est que je dois d'abord convertir les valeurs x et y en x "et y", car le 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 en valeur de la grille, puis trouver les valeurs r et thêta. Lorsque j'ai trouvé les valeurs R et THETA, je dois exécuter deux vecteurs, 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), car les vecteurs TH_VEC et Plage ont la même taille que l'image. Donc, si j'ai une matrice carrée d'éléments 512x512, je dois exécuter un creux 68 719 476 736 éléments, qui est bien lent. Donc, je me demande s'il y a un algorithme plus rapide? Je ne peux pas changer les données d'entrée, de même que je sache, c'est la seule façon de le faire si vous ne commencez pas avec la triangulation et des trucs, mais c'est trop cher en période de mémoire. < / p>
7 Réponses :
Que diriez-vous de
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
Vous devez décrire comment remplir l'image entière, la transformation inverse est donc plus probablement utile que si vous utilisez une méthode d'interpolation intelligente.
Si vous ne vous souciez pas du lissage, pourquoi ne pas simplement calculer la coordonnée polaire pour chaque destination de pixels de cartésan de destination et lisez la valeur de couleur? Voir http://fr.wikipedia.org/wiki/polar_coordinate_system#converting_between_polar_and_cartesian_coordinate Si vous Besoin d'aide pour faire ça.
Oui - Si vous souhaitez que l'image finale soit remplie, il est préférable de transformer la transformation inverse et d'interpoler dans l'image source.
Si votre grille est uniformément partitionnée par rapport aux coordonnées polaires, votre algorithme peut être réduit à O (N ^ 2) si vous tirez parti du fait que le point le plus proche de (r, thêta) sera l'un des quatre coins de l'élément de grille dans lequel il est contenu.
Dans l'affaire plus générale où la grille est le produit de cloisons arbitraires des dimensions R et Theta, cela pourrait atteindre 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 revenir à O (n ^ 2).
Vous pouvez boucler sur chaque pixel dans la carte de l'image polaire, puis rendre la section d'arc résultante dans le plan d'image cartésien:
Conversion polaire à cartésien http://img24.imageshack.us/img24/4635/polartocartesian.png Beaucoup de bibliothèques de dessin ont été construits Dans les fonctions de dessin de la section Arc, mais vous pouvez toujours simplement approcher de le faire avec un simple polygone:
La mémoire échoue, mais il pourrait y avoir une version rapide de cet algorithme impliquant la FFT. Une fois une fois, j'ai pris une classe sur l'imagerie médicale et il semble que ce genre de choses apparaisse lorsque des analyses de CT non traçables / rasterisants. Certains mots-clés pour rechercher seraient la transformation de radon, l'algorithme de backprojection filtré et les analyses CT. Je les ai regardés brièvement sur Wikipedia et rien n'a sauté, mais peut-être qu'un examen plus approfondi augmenterait de l'or.
O (n 2 log (n)) algorithme:
Si toutes vos images sont 512x512, j'utilise une table de recherche qui correspond à un ensemble pondéré de pixels dans votre image polaire à l'image cartésienne. Ceci est beaucoup de travail à l'avance mais fait votre calcul final O (n ^ 2). Si une lut n'est pas une option, j'utiliserais: sur chaque pixel dans l'image polaire pour la mapper sur "A" pixel dans l'image cartésienne, où le pixel de sortie est le moyenne de tous les pixels d'entrée qui tombent dessus. Appliquez ensuite des dilatations répétées jusqu'à ce qu'il n'y ait plus de pixels non inticialisés. Pour la dilatation, vous utilisez un élément de structuration 3x3 et ne remplacez que la valeur du pixel de sortie avec la valeur du pixel central s'il n'avait plus aucune valeur. Ensuite, en tant que mesure finale, appliquez un filtre gaussien à l'image entière pour lisser les bords durs. C'est la méthode la plus rapide que je puisse penser qui produira une image agréable à regarder dans une quantité de temps raisonnable.
De quoi s'agit-il? En outre, pourquoi n'avez-vous pas d'angle de 0 à PI ou de 0 à R_max? 2 * PI donne un cercle complet, alors pourquoi auriez-vous besoin d'une distance négative?
Votre grille polaire est-elle uniformément partitionnée par rapport aux coordonnées polaires?
Si vous trouvez R_0 et TH_0 comme une valeur de point flottante de votre X, Y, vous devez alors regarder quatre paires (R, TH) dans votre image polaire, c'est-à-dire les quatre voisins les plus proches de (R_0, TH_0), donc les quatre Combinaisons de plancher (R_0), CEIL (R_0) et plancher (TH_0), CEIL (TH_0) où le sol () et le CEIL () produisent quelque chose qui est arrondi à votre grille polaire.