Fast algorithm for polar -> cartesian conversion

Question

I have an image on a polar grid. This image should be transformed into a cartesian grid, but the only algorithm I know of is really slow for this. Now I use the cartesian grid, for each point I find the r and theta values, and then I look in two vectors to find the smallest error defined by:

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

This gives a nested for-loop inside of the outer nested for-loop, so I have a complexity of O(N^4). A 512x512 image uses a whole minute to complete. Of course, a complexity like that can not be used, so I'm wondering if anyone know of any faster algorithms to do this?

I have the image, and the two vectors. The X-axis of the image is the angle, while the Y-axis of the image is the length from the center. The angle is always from 0-2pi, and the range goes from 0 to r_max.

Thank you in advance.

EDIT: The range goes from 0 to r_max, not -r_max to r_max as it stood before. I see that there have been some missunderstandings. I have used the normal, inverse, conversion with;

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

The problem is that I have to first convert the x and y values to x' and y' values, since the grid is from -r_max to r_max in the resulting image, but in pixels in the data. So I have a 512x512 image, but r_max can be something like 3.512. So I have to convert each pixel value into the grid value, then find the r and theta values. When I have found the r and theta values I have to run trough two vectors, range and th_vec, to find the pixel in the original image that matches:

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

This gives me a complexity of O(n^4), since the th_vec and range vectors are the same size as the image. So if I have a square matrix of 512x512 elements, I have to run trough 68 719 476 736 elements, which is way slow. So I'm wondering if there is a faster algorithm? I can't change the input data, so as far as I know, this is the only way to do it if you don't start with triangulation and stuff, but this is to expensive in times of memory.

Answer 1

If your grid is uniformly partitioned with respect to the polar coordinates then your algorithm can be reduced to O(N^2) if you take advantage of the fact that the closest point to (r, theta) will be one of the four corners of the grid element in which it is contained.

In the more general case where the grid is the product of arbitrary partitions of the r and theta dimensions, that might grow to O( (N log N)^2) if you have to search for the location of the point in each partition. However, if the partitions were systematically constructed, you should be able to get back down to O(N^2).