极坐标 - >笛卡尔坐标转换的快速算法

Question

我在极地网格上有一个图像.这个图像应该转换成笛卡尔网格,但我所知道的唯一算法对此来说真的很慢.现在我使用笛卡尔网格,对于每个点我找到r和theta值,然后我查看两个向量以找到由以下定义的最小错误:

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

这给出了外部嵌套for循环内部的嵌套for循环,因此我的复杂度为O(N ^ 4).512x512图像使用整分钟完成.当然,这样的复杂性无法使用,所以我想知道是否有人知道更快的算法来做到这一点？

我有图像和两个向量.图像的X轴是角度,而图像的Y轴是距中心的长度.角度始终为0-2pi,范围从0到r_max.

先感谢您.

编辑:范围从0到r_max,而不是-r_max到之前的r_max.我看到有一些误解.我使用了正常,反向,转换;

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

问题是我必须首先将x和y值转换为x'和y'值,因为网格在结果图像中从-r_max到r_max,但在数据中以像素为单位.所以我有一个512x512的图像,但r_max可能是3.512.所以我必须将每个像素值转换为网格值,然后找到r和theta值.当我找到r和theta值时,我必须运行两个矢量range和th_vec,以找到原始图像中匹配的像素:

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

这给了我O(n ^ 4)的复杂度,因为th_vec和范围向量与图像的大小相同.因此,如果我有一个512x512元素的方阵,我必须运行68 719 476 736元素,这很慢.所以我想知道是否有更快的算法？我不能改变输入数据,所以据我所知,如果你不是从三角测量和东西开始,这是唯一的方法,但这在内存时是昂贵的.

Answer 1

怎么样

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

这是从极地转换为笛卡尔的标准方法,除非你打算使用某种表查找,否则实际上没有更快的选择.

编辑:争吵有一个好点.如果您尝试将极坐标I(angle, r)中的图像转换为笛卡尔坐标系中的图像I_new(x, y),那么您最好使用逆变换,如下所示:

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

通常,angle并且r不会是整数,因此您必须在图像中进行某种插值I.最简单的方法就是圆形angle和r; 这将为您提供最近邻插值.如果您需要更好的质量,请尝试更复杂的插值类型,如双线性或双三次插值.

Answer 2

您可以遍历极坐标图像映射中的每个像素,然后在笛卡尔图像平面中渲染生成的弧段:

极地到笛卡儿的转换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);
    }
}

许多绘图库具有用于绘制弧形截面的内置函数,但您总是可以使用简单的多边形来近似它:

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