Szybki algorytm dla konwersji biegunowej -> kartezjańskiej

Question

Mam obraz na siatce biegunowej. Obraz ten powinien zostać przekształcony w siatkę kartezjańską, ale jedyny znany mi algorytm jest bardzo powolny. Teraz używam siatki kartezjańskiej, dla każdego punktu znajduję wartości r i theta, a następnie szukam dwóch wektorów, aby znaleźć najmniejszy błąd zdefiniowany przez:

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

Daje to zagnieżdżoną pętlę for wewnątrz zewnętrznej zagnieżdżonej pętli for, więc mam złożoność O (N^4). Obraz 512x512 zajmuje całą minutę. Oczywiście takiej złożoności nie można użyć, więc zastanawiam się, czy ktoś wie o szybszych algorytmach, aby to zrobić?

Mam obraz i dwa wektory. Oś X obrazu jest kątem, a oś Y obrazu jest długością od środka. Kąt jest zawsze w zakresie 0-2pi, a zakres zmienia się od 0 do r_max.

Z góry dziękuję.

EDYCJA: Zakres zmienia się od 0 do r_max, nie-r_max do r_max, tak jak poprzednio. Widzę, że były pewne nieporozumienia. Użyłem zwykłej, odwrotnej konwersji z;

 

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

Problemem jest to, że muszę najpierw przekonwertować wartości X i Y do X „i Y” wartości, ponieważ siatka jest z -r_max do r_max w uzyskanym obrazie, ale w pikselach w danych. Tak więc mam obraz 512x512, ale r_max może być podobny do 3.512. Muszę więc przekonwertować każdą wartość piksela na wartość siatki, a następnie znaleźć wartości r i theta. Po znalezieniu wartości r i theta muszę przejść przez dwa wektory, zakres i th_vec, aby znaleźć piksel w oryginalnym obrazie, który pasuje:

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

Daje mi to złożoność O (n^4), ponieważ wektory th_vec i range są tego samego rozmiaru co obraz. Więc jeśli mam kwadratową matrycę z elementami 512x512, muszę biegać przez 68 719 476 736 elementów, co jest bardzo powolne. Zastanawiam się, czy istnieje szybszy algorytm? Nie mogę zmienić danych wejściowych, więc o ile wiem, jest to jedyny sposób, aby to zrobić, jeśli nie zaczniesz od triangulacji i innych rzeczy, ale jest to drogie w czasach pamięci.

Answer 1

Jak o

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

Jest to standardowy sposób konwersji z polarnego do kartezjański i jeśli masz zamiar użyć jakiegoś tabeli przeglądowej, tam naprawdę nie jest szybsza opcja.

Edytuj: wrang wrang ma dobry punkt. Jeśli starasz się przekształcać obraz we współrzędnych biegunowych I(angle, r) do obrazu we współrzędnych kartezjańskich I_new(x, y), jesteś zdecydowanie lepiej stosując odwrotną transformację, w następujący sposób:

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 

będzie

z reguły nie angle i r być liczbą całkowitą, więc musisz wykonać jakąś interpolację obrazu I. Najprostszym sposobem na zrobienie tego jest po prostu okrążenie angle i r; to da ci nearest-neighbour interpolation. Jeśli potrzebujesz lepszej jakości, wypróbuj bardziej wyrafinowane typy interpolacji, takie jak interpolacja bilinear lub .

Answer 2

Jeśli nie zależy Ci na wygładzaniu, dlaczego nie obliczasz współrzędnej biegunowej dla każdej docelowej współrzędnej kartezjańskiej piksela i nie czytasz wartości koloru? Jeśli potrzebujesz pomocy, zobacz http://en.wikipedia.org/wiki/Polar_coordinate_system#Converting_between_polar_and_Cartesian_coordinates.

Answer 3

Jeśli twoja siatka jest podzielona równomiernie w stosunku do współrzędnych biegunowych, twój algorytm może zostać zredukowany do O (N^2), jeśli wykorzystasz fakt, że najbliższy punkt (r, theta) będzie jednym z cztery rogi elementu siatki, w którym się znajdują.

W bardziej ogólnym przypadku, gdy siatka jest wynikiem arbitralnych partycji wymiarów r i theta, może wzrosnąć do O ((N log N)^2), jeśli trzeba wyszukać położenie punktu w każdej partycji. Jeśli jednak partycje były konstruowane systematycznie, powinieneś być w stanie wrócić do O (N^2).

Answer 4

można pętli nad każdym pikselu w polarnym mapy obrazu, a następnie mogłyby uczynić wynikowy punkt łuku w kartezjańskim obrazu samolotem:

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

Wiele bibliotek ciągnienia mają wbudowane funkcje do rysowania ten odcinek łuku, ale zawsze możesz go po prostu przybliżyć za pomocą prostego wielokąta:

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

Pamięć się nie udaje, ale może wystąpić szybka wersja tego algorytmu, która obejmuje FFT. Pewnego razu wziąłem udział w zajęciach z obrazowania medycznego i wydaje się, że takie rzeczy pojawiały się podczas nietransformowania/rasteryzacji skanów TK. Niektóre wyszukiwane słowa kluczowe to transformacja radonu, filtrowany algorytm odwzorowania wstecznego i skanowanie CT. Przejrzałem je krótko na wikipedii i nic nie wyskoczyło, ale może bardziej gruntowna recenzja przyniesie trochę złota.

Answer 6

O (N log (n)) Algorytm:

• macierzy S zostaną wykorzystane do najbliżej źródła (polarny) coord za kartezjańskim współ.
• S rozpoczyna wypełnianie wartości "nie zainicjowano jeszcze". (Python: Brak, Haskell: Nic, itp.)
• O (N) - Powtórzyć wszystkie współrzędne biegunowe.
  • Przekłada się kartezjańskiej coord
  • Znajdź najbliższy kartezjański coord w swoim docelowym obrazie.(Zaokrąglenie i granic zastosowanie)
  • wypełnienia w odpowiedniej komórce S z tym współrzędnych
• O (N log (N)) - Przeprowadzić zmodyfikowanego algorytmu Dijkstry, jak opisano poniżej:
  • z „Graph” dla naszego algorytmu wyszukiwania jest następujący:
    • Wszystkie komórki S są węzłami
    • sąsiedzi komórce są te króla w szachach może poruszać się od niego
  • „Wynik” komórki jest nieskończona, jeśli nie jest inicjowany, a odległość od nietkniętej kartezjańskiej coord z coord polarnego jego wskazując
  • Podczas aktualizacji sąsiad z celi N mamy umieścić wartość z komórki N, w tym (ale jak w Dijkstra tylko wtedy, gdy to ma swój wynik lepszy niż obecnie wyniku)
  • punktem wyjścia jest tablica S inicjowany jak opisano powyżej

Answer 7

If wszystkie Twoje obrazy mają rozmiar 512x512, a następnie użyję tabeli odnośników, która mapuje ważony zestaw pikseli w obrazie biegunowym na obraz kartezjański. To dużo pracy z góry, ale dokonuje ostatecznych obliczeń O (n^2). Jeśli LUT nie wchodzi w grę wtedy użyję:

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

Na każdego piksela w obrazie polarnego do map to „a” piksel w obrazie kartezjańskiej, gdzie piksel wyjściowy jest średnią wszystkich wejścia piksele, które na nią spadają. Następnie nałóż powtarzające się dylatacje, aż pozostaną niezainicjowane piksele. W przypadku dylatacji używasz elementu strukturalnego 3x3 i zastępujesz wartość piksela wyjściowego wartością środkowego piksela, jeśli poprzednio nie miała ona żadnej wartości. Następnie, jako ostateczny środek, zastosuj filtr Gaussa do całego obrazu, aby wygładzić twarde krawędzie. Jest to najszybsza metoda, jaką mogę sobie wyobrazić, która pozwoli uzyskać obraz, który jest przyjemny do obejrzenia w rozsądnym czasie.