快速算法极 - ＆GT;笛卡尔转换 [英] Fast algorithm for polar -> cartesian conversion

问题描述

我有一个极坐标网格的图像。此图像应被转换成笛卡尔网格，但唯一的算法，我所知道的就是这个很慢。现在我用的是笛​​卡尔网格，每个点我觉得r和θ值，然后我看在两个向量来寻找定义的最小误差：

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:

分{（th_vec - THETA）^ 2 +（范围 - R）^ 2}

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

这给出了一个嵌套的循环嵌套的循环外里面，所以我有一个复杂性为O（N ^ 4）。 512×512的图像采用了整整一分钟即可完成。当然，这样的复杂性不能用，所以我不知道是否有人知道任何更快的算法来做到这一点？

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?

我有图像，并且两个向量。图像的X轴是角度，而图像的Y轴是从中心的长度。的角度始终从0-2pi，和范围从0到r_max

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.

感谢你在前进。

编辑：范围从0至r_max，不-r_max至r_max像以前站立。我看到有一些missunderstandings。我用正常的，相反，转换带;

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

的问题是，我必须首先将x和y值与x'和y'的值，由于网格是从-r_max在所得图像r_max，但在数据像素。所以，我有一个512×512的图像，但r_max可以像3.512。所以我要每个像素值转换成网格值，然后找到r和θ值。当我发现了R和θ值我要运行低谷两个向量，范围和th_vec，找到相匹配的原始图像的像素：

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:

分{（范围 - R）^ 2 +（th_vec - THETA）^ 2}

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

此给我一个复杂性为O（N ^ 4）中，由于th_vec和范围的载体，是大小相同的图像。所以，如果我有512×512的元素方阵，我要运行槽68 719 476 736元，这是远远慢。所以，我想知道是否有更快的算法？我不能改变输入数据，所以据我所知，这是要做到这一点，如果你不开始与三角和东西的唯一方法，但这是昂贵的存储时间。

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.

推荐答案

如何

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

这是从极性转换成直角的标准方法，除非你要使用某种类型的表查询，有没有真正更快的选择。

This is the standard way of converting from polar to Cartesian, and unless you're going to use some kind of table lookup, there's not really a faster option.

修改：wrang wrang好点。如果你想变换的图像在极坐标 I（角，R）来在直角坐标系的图像 I_new（X，Y），你绝对最好使用逆变换，如下：

Edit: wrang wrang has a good point. If you're trying to transform an image in polar coordinates I(angle, r) to an image in Cartesian coordinates I_new(x, y), you are definitely better off using the inverse transformation, as follows:

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

作为一个规则，角度和研究不会是整数，所以你必须做一些插值图像中的我。要做到这一点，最简单的方法就是圆角度和研究;这会给你最近邻插值。如果你需要更好的质量，尽量插值更复杂的类型，如双线性或的双三次插值。

As a rule, angle and r will not be integer, so you have to do some kind of interpolation in the image I. The easiest way to do this is simply to round angle and r; this will give you nearest-neighbour interpolation. If you need better quality, try more sophisticated types of interpolation such as bilinear or bicubic interpolation.

这篇关于快速算法极 - ＆GT;笛卡尔转换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！