8

我有一个极坐标网格上的图像。该图像应转换为笛卡尔网格，但我所知道的唯一算法对此非常慢。现在我使用笛卡尔网格，对于每个点我找到 r 和 theta 值，然后我查看两个向量以找到由以下定义的最小误差：

min{(th_vec - theta)^2 + (范围 - 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{(范围 - r)^2 + (th_vec - theta)^2}

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

4

7 回答 7

10

怎么样

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

这是从极坐标转换为笛卡尔坐标的标准方法，除非您要使用某种表格查找，否则实际上没有更快的选择。

编辑： wrang wrang 有一个好点。如果您尝试将极坐标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；这将为您提供最近邻插值。如果您需要更好的质量，请尝试更复杂的插值类型，例如双线性或双三次插值。

于 2009-08-17T18:40:30.073 回答
5

您可以遍历极坐标图像映射中的每个像素，然后在笛卡尔图像平面中渲染生成的弧形部分：

极坐标到笛卡尔转换 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);
}
于 2009-08-17T19:22:42.673 回答
3

如果您不关心平滑，为什么不只计算每个目标笛卡尔像素坐标的极坐标并读取颜色值？如果您需要帮助，请参阅http://en.wikipedia.org/wiki/Polar_coordinate_system#Converting_between_polar_and_Cartesian_coordinates。

于 2009-08-17T18:45:48.800 回答
1

如果您的网格相对于极坐标是均匀分区的，那么如果您利用离 (r, theta) 最近的点将是四个角之一的事实，那么您的算法可以减少到 O(N^2)包含它的网格元素。

在更一般的情况下，网格是 r 和 theta 维度的任意分区的乘积，如果您必须在每个分区中搜索点的位置，则可能会增长到 O( (N log N)^2)。但是，如果分区是系统构建的，您应该能够回到 O(N^2)。

于 2009-08-17T19:19:09.920 回答
0

内存失败，但该算法可能有一个涉及 FFT 的快速版本。曾几何时，我上了一门医学成像课程，似乎在取消转换/光栅化 CT 扫描时会出现这种东西。一些要搜索的关键字是氡变换、过滤的反投影算法和 CT 扫描。我在 wikipedia 上简单地查看了这些内容，但没有发现任何问题，但也许更彻底的审查会发现一些黄金。

于 2009-08-17T20:07:09.730 回答
0

O(N 2 log(N)) 算法：

  • 数组 S 将用于每个笛卡尔坐标的最近源（极坐标）坐标。
  • S 以“尚未初始化”的值开始填充。（Python：无，Haskell：无，等等）
  • O(N 2 ) - 迭代所有的极坐标。
    • 转换为笛卡尔坐标
    • 在您的目标图像中找到最近的笛卡尔坐标。（通过四舍五入和应用边框）
    • 用这个坐标填入S中的相关单元格
  • O(N 2 log(N)) - 执行修改后的 Dijkstra 算法，如下所述：
    • 我们的搜索算法的“图表”如下：
      • S的所有单元格都是节点
      • 一个细胞的邻居是国际象棋中的国王可以从它移动到的那些
    • 如果未初始化，则单元格的“分数”是无限的，并且与极坐标的未触及笛卡尔坐标的距离指向它
    • 当更新单元格 N 的邻居时，我们将单元格 N 的值放入其中（但就像在 Dijkstra 中一样，只有当它的得分高于当前得分时）
    • 起点是如上所述初始化的数组 S
于 2009-08-18T21:40:29.957 回答
0

如果您所有的图像都是 512x512，那么我会使用一个查找表，将极坐标图像中的一组加权像素映射到笛卡尔图像。这是很多前期工作，但最终计算结果为 O(n^2)。如果LUT不是一个选项，那么我会使用：

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

在极坐标图像中的每个像素上将其映射到笛卡尔图像中的“一个”像素，其中输出像素是落在其上的所有输入像素的平均值。然后应用重复的膨胀，直到没有未初始化的像素。对于膨胀，您使用 3x3 结构元素，并且如果之前没有值，则仅将输出像素的值替换为中心像素的值。然后，作为最终措施，对整个图像应用高斯滤波器以平滑硬边缘。这是我能想到的最快的方法，它会在合理的时间内产生令人愉悦的图像。

于 2009-08-19T11:43:11.347 回答