0

C++ を使用した画像補間 (バイキュービック法およびバイリニア法) の実装に関する質問があります。私の主な関心事は速度です。問題の私の理解に基づいて、補間プログラムを高速かつ効率的にするために、次の戦略を採用できます。

  1. ストリーミング SIMD 拡張命令 (SSE) を使用した高速画像補間

  2. マルチスレッドまたは GPU による画像解釈

  3. 高速画像補間アルゴリズム

  4. C++ 実装の秘訣

ここで、私は最後の戦略にもっと興味があります。補間用のクラスを設定しました：

     /**
        * This class is used to perform interpretaion for a certain poin in 
        * the image grid.
        */
        class  Sampling
        {
        public:
            //   samples[0] *-------------* samples[1]
            //              --------------
            //              --------------
            //   samples[2] *-------------*samples[3]
            inline void sampling_linear(unsigned char *samples, unsigned char &res)
            {
                unsigned char res_temp[2];
                sampling_linear_1D(samples,res_temp[0]);
                sampling_linear_1D(samples+2,res_temp[1]);
                sampling_linear_1D(res_temp,res);
            }
        private:
            inline void sampling_linear_1D(unsigned char *samples, unsigned char &res)
            {
            }
        }

ここでは、双一次補間の例のみを示します。プログラムを高速に実行するために、インライン関数が採用されています。私の質問は、この実装スキームが効率的かどうかです。さらに、解釈手順中に、異なる補間方法を選択するオプションを使用する場合。次に、2 つの選択肢があります。

  1. 補間方法に応じて、画像全体の補間を実行する関数を呼び出します。
  2. 各出力イメージ ピクセルについて、最初に入力イメージ内の位置を決定し、次に補間方法の設定に従って補間関数を決定します。

最初の方法はプログラム内のコードが増えることを意味しますが、2 番目の方法は非効率につながる可能性があります。では、これら 2 つのスキームのどちらかを選択するにはどうすればよいでしょうか。ありがとう！

4

1 に答える 1

9

ストリーミング SIMD 拡張命令 (SSE) を使用した高速画像補間

あなたのアルゴリズムは FLOP/s バウンドではなくメモリバウンドになると予想されるため、これは望ましい結果をもたらさない可能性があります。

つまり、間違いなく改善されますが、実装コストと比較して有益ではありません。

ところで、最新のコンパイラは自動ベクトル化を実行できます (つまり、SSE およびその他の拡張機能の使用): GCC 4.0 以降、MSVC 2012以降、MSVC 自動ベクトル化ビデオ講義。

マルチスレッドまたは GPU による画像解釈

マルチスレッド バージョンは、利用可能なすべてのメモリ スループットを活用できるため、効果が高いはずです。

データを数回処理する予定がない場合、または GPU で何らかの方法で使用する予定がない場合、GPGPU は望ましい結果をもたらさない可能性があります。はい、結果はより速く生成されます (主にメモリ速度が高いため) が、メイン RAM と GPU の RAM 間の転送が遅いため、この効果は打ち消されます。

たとえば、最新のスループットを概算します。

  1. CPU RAM ~ 20GiB/秒
  2. GPU RAM ~ 150GiB/秒
  3. CPU RAM <-> GPU RAM 間の転送 ~ 3-5 GiB/秒

シングル パス メモリ バウンド アルゴリズムの場合、ほとんどの場合、3 番目の項目によって GPU の使用が非現実的になります (そのようなアルゴリズムの場合)。

プログラムを高速に実行するために、インライン関数が採用されています

クラスメンバー関数はデフォルトで「インライン」です。「インライン」の主な目的は実際には「インライン化」ではなく、関数がヘッダーで定義されている場合にOne Definition Rule違反を防ぐのに役立つことに注意してください。

コンパイラに依存する「forceinline」機能があります。たとえば、MSVC には__forceinlineがあります。または、コンパイラの ifdef'ed BOOST_FORCEINLINE マクロから抽象化されます。

とにかく、別の方法で証明しない限り (たとえば、アセンブラーの助けを借りて)、コンパイラーを信頼してください。最も重要な事実は、コンパイラが関数の定義を確認する必要があるということです。関数がインライン化されていなくても、コンパイラーはインライン化することを決定できます。

私の質問は、この実装スキームが効率的かどうかです。

私が理解しているように、前段階として、サンプルを 2x2 マトリックスに収集します。イメージ内の 2 つの要素の配列に 2 つのポインターを直接渡すか、1 つのポインター + 幅サイズ (2 番目のポインターを自動的に計算するため) を直接渡す方がよいと思います。ただし、これは大きな問題ではありません。おそらく、一時的な 2x2 行列は最適化されて取り除かれます。

本当に重要なのは、イメージをどのようにトラバースするかです。

与えられた x と y について、インデックスは次のように計算されます。

i=width*y+x;

次に、トラバーサル ループは次のようになります。

for(int y=/*...*/)
    for(int x=/*...*/)
    {
        // loop body
    }

別の順序 (最初に x、次に y) を選択すると、キャッシュに適していないため、結果としてパフォーマンスが最大 64 倍低下する可能性があります (ピクセル サイズによって異なります)。あなたの興味のためにそれをチェックするかもしれません。

最初の方法はプログラム内のコードが増えることを意味しますが、2 番目の方法は非効率につながる可能性があります。では、これら 2 つのスキームのどちらかを選択するにはどうすればよいでしょうか。ありがとう！

この場合、コンパイル時のポリモーフィズムを使用して、最初のバージョンのコード量を減らすことができます。たとえば、テンプレートに基づいています。

std::accumulateを見てください。一度記述すれば、さまざまなタイプの反復子、さまざまなバイナリ操作 (関数またはファンクター) で機能し、ポリモーフィズムによる実行時のペナルティを意味することはありません。

アレクサンダー・ステパノフ さんのコメント：

何年もの間、私はより高度な言語 (Ada や Scheme など) で相対的な効率を達成しようとしましたが、失敗しました。単純なアルゴリズムの汎用バージョンでさえ、組み込みのプリミティブと競合できませんでした。しかし、C++ では、最終的に相対的な効率を達成するだけでなく、絶対的な効率という野心的な目標に非常に近づくことができました。これを確認するために、さまざまなアーキテクチャーのさまざまなコンパイラーによって生成されたアセンブリー・コードを調べるのに数え切れないほどの時間を費やしました。

Boost の Generic Image Libraryを確認してください。優れたチュートリアルがあり、作成者によるビデオ プレゼンテーションがあります。

于 2012-10-30T18:17:23.100 に答える