8

極座標グリッドに画像があります。この画像はデカルト グリッドに変換する必要がありますが、私が知っている唯一のアルゴリズムはこれが非常に遅いです。次に、デカルト グリッドを使用します。各点について、r 値と theta 値を見つけます。次に、2 つのベクトルを調べて、次の式で定義される最小の誤差を見つけます。

min{(th_vec - シータ)^2 + (範囲 - r)^2}

これにより、外側の入れ子になった for ループの内側に入れ子になった for ループができるため、O(N^4) の複雑さがあります。512x512 の画像は、完了するのに丸 1 分かかります。もちろん、そのような複雑さは使用できないので、これを行うためのより高速なアルゴリズムを誰かが知っているかどうか疑問に思っていますか?

画像と 2 つのベクトルがあります。画像の X 軸は角度で、画像の Y 軸は中心からの長さです。角度は常に 0 ～ 2pi で、範囲は 0 ～ r_max です。

前もって感謝します。

編集: 範囲は、以前の -r_max から r_max ではなく、0 から 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 の 2 つのベクトルを実行する必要があります。

min{(範囲 - r)^2 + (th_vec - シータ)^2}

th_vec と範囲ベクトルは画像と同じサイズであるため、これにより O(n^4) の複雑さが得られます。したがって、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）に最も近い点がの四隅の1つになるという事実を利用すれば、アルゴリズムをO（N ^ 2）に減らすことができます。それが含まれているグリッド要素。

グリッドがr次元とシータ次元の任意のパーティションの積であるより一般的なケースでは、各パーティション内のポイントの位置を検索する必要がある場合、O（（N log N）^ 2）に成長する可能性があります。ただし、パーティションが体系的に構築されている場合は、O（N ^ 2）に戻ることができるはずです。

于 2009-08-17T19:19:09.920 に答える
0

すべての画像が512x512の場合、極座標画像の重み付けされたピクセルのセットをデカルト画像にマッピングするルックアップテーブルを使用します。これは前もって多くの作業ですが、最終的な計算はO（n ^ 2）になります。LUTがオプションでない場合は、次を使用します。

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

極座標画像の各ピクセルで、デカルト画像の「a」ピクセルにマッピングします。出力ピクセルは、その上にあるすべての入力ピクセルの平均です。次に、初期化されていないピクセルがなくなるまで、拡張を繰り返し適用します。拡張には、3x3の構造化要素を使用し、出力ピクセルの値を、以前は値がなかった場合にのみ中央のピクセルの値に置き換えます。次に、最終的な対策として、画像全体にガウスフィルターを適用して、ハードエッジを滑らかにします。これは私が考えることができる最速の方法であり、妥当な時間で見やすい画像を生成します。

于 2009-08-19T11:43:11.347 に答える
0

メモリは失敗しますが、FFT を含むこのアルゴリズムの高速バージョンが存在する可能性があります。むかしむかし、私は医用画像処理のクラスを受講しましたが、CT スキャンを非変換/ラスタライズするときに、この種のものがポップアップしたようです。検索するキーワードには、ラドン変換、フィルター逆投影アルゴリズム、CT スキャンなどがあります。私はウィキペディアでこれらを簡単に調べましたが、飛び出したものは何もありませんでしたが、より徹底的なレビューでいくらかの金が得られるかもしれません.

于 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)) - 以下で説明する修正ダイクストラ アルゴリズムを実行します。
    • 検索アルゴリズムの「グラフ」は次のとおりです。
      • S のすべてのセルはノードです
      • セルの隣人は、チェスのキングがセルから移動できるセルです。
    • セルが初期化されていない場合、セルの「スコア」は無限であり、指している極座標の手つかずのデカルト座標からの距離
    • セル N の隣人を更新するとき、セル N からの値を入れます (ただし、ダイクストラと同様に、現在のスコアよりもスコアが良くなる場合のみ)
    • 開始点は、上記のように初期化された配列 S です。
于 2009-08-18T21:40:29.957 に答える