極座標 - >笛卡爾轉換的快速算法

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值時，我必須跑兩個向量，範圍和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) 

這是極性轉換成直角的標準方式，除非你要使用某種類型的查找表的，有沒有真正更快的選擇。

編輯：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;這會給你nearest-neighbour interpolation。如果您需要更好的質量，請嘗試使用更復雜的插值類型，例如bilinear或bicubic插值。

Answer 2

如果您不關心平滑，爲什麼不計算每個目標笛卡爾座標的極座標並讀取顏色值？如果您需要幫助，請參閱http://en.wikipedia.org/wiki/Polar_coordinate_system#Converting_between_polar_and_Cartesian_coordinates。

Answer 3

如果您的網格相對於極座標統一分區，那麼如果利用最接近（r，theta）點將是下列之一的事實，則可以將算法簡化爲O（N^2）包含它的網格元素的四個角落。

在更一般情況下，如果必須搜索點的位置，網格是r和θ維的任意分區的乘積，那麼可能會增長到O（（N log N）^ 2）在每個分區中。但是，如果系統地構建分區，則應該能夠回到O（N^2）。

Answer 4

你可以循環遍歷極地圖像地圖中的每個像素，然後呈現在笛卡爾圖像平面得到的弧段：

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

許多繪圖庫有內置的繪圖功能該弧段，但總是可以用一個簡單的多邊形來逼近它：

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

內存失敗，但可能存在該算法的快速版本涉及FFT。曾幾何時，我參加了一次醫學成像課程，看起來這種東西在未轉換/光柵化CT掃描時彈出。一些要搜索的關鍵字是氡變換，濾波反投影算法和CT掃描。我在維基百科上簡單地查看了這些，並沒有跳出來，但也許更徹底的審查會出現一些黃金。

Answer 6

O（N 2 ^日誌（N））的算法：

• 數組S將用於每笛卡爾座標最接近的源（極性）座標。
• S開始時填入了「尚未初始化的」值。 （Python：None，Haskell：Nothing等）
• O（N ） - 重複所有極座標。
  • 翻譯成直角座標
  • 查找目的地形象最接近笛卡爾座標。（通過舍入和應用邊框）
  • 填寫S中與此有關的單元座標
• O（N 日誌（N）） - ，如下所述，執行修改的Dijkstra算法：
  • 的「圖」爲我們的搜索算法如下：
    • S的所有單元節點
    • 小區的鄰居是那些國王國際象棋可以移動到從它
  • 的細胞的「分數」是無限的，如果沒有初始化它，距離極座標指向它的不變 笛卡爾座標到
  • 當更新小區的鄰居N送來我們把從單元N的值在它的（但像在迪傑斯特拉，僅當它是其得分比其當前的得分）
  • 的起點是所述陣列S上方

Answer 7

如果如所描述的初始化所有的圖像是512x512，然後我會使用查找表，將您的極圖像中的一組加權像素映射到笛卡爾圖像。這是很多前期工作，但會使您的最終計算O（n^2）。如果LUT不是一個選項，然後我會使用：

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

上的每個像素的極座標圖像中繪製它的笛卡爾圖像，其中輸出像素爲所有輸入的平均值「」像素落在它上面的像素。然後應用重複的擴張直到沒有未初始化的像素。對於膨脹，您可以使用3x3結構元素，並且如果先前沒有值，則只將輸出像素的值替換爲中心像素的值。然後，作爲最後的措施，對整個圖像應用高斯濾鏡以平滑硬邊緣。這是我能想到的最快速的方法，可以在合理的時間內生成令人愉快的圖像。