1

次のバイリニアサイズ変更アルゴリズムで速度を向上させる方法を誰かが見つけることができますか？これは重要であり、良好な画質を維持するため、速度を向上させる必要があります。低速CPUを搭載したモバイル機器での使用が見込まれます。このアルゴリズムは、主にスケールアップのサイズ変更に使用されます。他のより高速な双線形アルゴリズムもありがたいです。ありがとう

void resize(int* input, int* output, int sourceWidth, int sourceHeight, int targetWidth, int targetHeight) 
{    
    int a, b, c, d, x, y, index;
    float x_ratio = ((float)(sourceWidth - 1)) / targetWidth;
    float y_ratio = ((float)(sourceHeight - 1)) / targetHeight;
    float x_diff, y_diff, blue, red, green ;
    int offset = 0 ;

    for (int i = 0; i < targetHeight; i++) 
    {
        for (int j = 0; j < targetWidth; j++) 
        {
            x = (int)(x_ratio * j) ;
            y = (int)(y_ratio * i) ;
            x_diff = (x_ratio * j) - x ;
            y_diff = (y_ratio * i) - y ;
            index = (y * sourceWidth + x) ;                
            a = input[index] ;
            b = input[index + 1] ;
            c = input[index + sourceWidth] ;
            d = input[index + sourceWidth + 1] ;

            // blue element
            blue = (a&0xff)*(1-x_diff)*(1-y_diff) + (b&0xff)*(x_diff)*(1-y_diff) +
                   (c&0xff)*(y_diff)*(1-x_diff)   + (d&0xff)*(x_diff*y_diff);

            // green element
            green = ((a>>8)&0xff)*(1-x_diff)*(1-y_diff) + ((b>>8)&0xff)*(x_diff)*(1-y_diff) +
                    ((c>>8)&0xff)*(y_diff)*(1-x_diff)   + ((d>>8)&0xff)*(x_diff*y_diff);

            // red element
            red = ((a>>16)&0xff)*(1-x_diff)*(1-y_diff) + ((b>>16)&0xff)*(x_diff)*(1-y_diff) +
                  ((c>>16)&0xff)*(y_diff)*(1-x_diff)   + ((d>>16)&0xff)*(x_diff*y_diff);

            output [offset++] = 
                    0x000000ff | // alpha
                    ((((int)red)   << 24)&0xff0000) |
                    ((((int)green) << 16)&0xff00) |
                    ((((int)blue)  << 8)&0xff00);
        }
    }
}
4

5 に答える 5

3

インラインキャッシュとルックアップテーブル

計算をアルゴリズムにキャッシュします。

  • 重複する計算を避けてください（(1-y_diff)またはのように(x_ratio * j)）

    アルゴリズムのすべての行を調べて、繰り返しのパターンを特定してみてください。これらをローカル変数に抽出します。また、関数がインライン化できるほど短い場合は、関数を抽出して、読みやすくします。

  • ルックアップテーブルを使用する

    ある程度のメモリを節約できれば、RGB値の「ストア」を実装し、それらを生成した入力に基づいて単に「フェッチ」できる可能性が非常に高くなります。すべてを保存する必要はないかもしれませんが、実験して、頻繁に戻ってくるものがあるかどうかを確認することはできます。または、色を「ファッジ」して、ルックアップ入力を増やすために保存する値を少なくすることもできます。

    入力の境界がわかっている場合は、完全なドメインスペースを計算して、キャッシュする意味があるものを理解できます。たとえば、値全体Rをキャッシュできない場合は、少なくとも、ケースで決定論的である可能性が最も高いシフト（など）を事前に計算できます）。GB(b>>16)

パフォーマンスに適切なデータ型を使用する

変数を回避できる場合は、を使用しdoubleてください。ほとんどのアーキテクチャでは、メモリモデルがあるため、計算のテストが高速になります。単位をシフトするだけで、まともな精度を達成できます（つまり、またはの代わりにasを使用します）。このトリックで十分である可能性が非常に高いです。floatintint1026int1.026doublefloat

于 2012-07-06T13:48:41.393 に答える
3

私の頭の上から：

  1. ターゲット CPU のハードウェアにパフォーマンスの良い浮動小数点があることが確実でない限り、浮動小数点の使用をやめてください。
  2. メモリアクセスがキャッシュ最適化されていること、つまりまとめられていることを確認してください。
  3. 可能な限り高速なデータ型を使用してください。これは、最小を意味する場合もあれば、「最もネイティブで、必要なオーバーヘッドが最も少ない」ことを意味する場合もあります。
  4. 整数演算の符号付き/符号なしがプラットフォームでパフォーマンス コストを発生させるかどうかを調査します。
  5. 計算ではなくルックアップ テーブルで何かが得られるかどうかを調べます (ただし、これらはキャッシュを吹き飛ばす可能性があるため、注意してください)。

そしてもちろん、多くのプロファイリングと測定を行います。

于 2012-07-06T13:25:11.013 に答える
0

私のランダムな推測 (人々に推測させるのではなく、プロファイラーを使用してください!):

コンパイラは、入力と出力がオーバーラップするときに機能するものを生成する必要があります。つまり、冗長なストアとロードのロードを生成する必要があります。restrictその安全機能を削除するには、入力パラメータと出力パラメータに追加します。

それらを再度ロードする代わりにa=b;andを使用することもできます。c=d;

于 2012-07-06T15:39:57.977 に答える
0

これが私のバージョンです。いくつかのアイデアを盗みます。私の C-fu はかなり弱いので、いくつかの行は疑似コードですが、修正できます。

void resize(int* input, int* output,
            int sourceWidth, int sourceHeight,
            int targetWidth, int targetHeight
) {
    // Let's create some lookup tables!
    // you can move them into 2-dimensional arrays to
    // group together values used at the same time to help processor cache
    int sx[0..targetWidth ]; // target->source X lookup
    int sy[0..targetHeight]; // target->source Y lookup
    int mx[0..targetWidth ]; // left pixel's multiplier
    int my[0..targetHeight]; // bottom pixel's multiplier

    // we don't have to calc indexes every time, find out when
    bool reloadPixels[0..targetWidth ];
    bool shiftPixels[0..targetWidth ];
    int  shiftReloadPixels[0..targetWidth ]; // can be combined if necessary

    int v; // temporary value
    for (int j = 0; j < targetWidth; j++){
        // (8bit + targetBits + sourceBits) should be < max int
        v = 256 * j * (sourceWidth-1) / (targetWidth-1);

        sx[j] = v / 256;
        mx[j] = v % 256;

        reloadPixels[j] = j ? ( sx[j-1] != sx[j] ? 1 : 0)
                            : 1; // always load first pixel

        // if no reload -> then no shift too
        shiftPixels[j]  = j ? ( sx[j-1]+1 = sx[j] ? 2 : 0)
                            : 0; // nothing to shift at first pixel

        shiftReloadPixels[j] = reloadPixels[i] | shiftPixels[j];
    }

    for (int i = 0; i < targetHeight; i++){
        v = 256 * i * (sourceHeight-1) / (targetHeight-1);
        sy[i] = v / 256;
        my[i] = v % 256;
    }

    int shiftReload;
    int srcIndex;
    int srcRowIndex;
    int offset = 0;
    int lm, rm, tm, bm; // left / right / top / bottom multipliers
    int a, b, c, d;

    for (int i = 0; i < targetHeight; i++){
        srcRowIndex = sy[ i ] * sourceWidth;
        tm = my[i];
        bm = 255 - tm;

        for (int j = 0; j < targetWidth; j++){

            // too much ifs can be too slow, measure.
            // always true for first pixel in a row
            if( shiftReload = shiftReloadPixels[ j ] ){
              srcIndex = srcRowIndex + sx[j];
              if( shiftReload & 2 ){
                a = b;
                c = d;
              }else{
                a = input[ srcIndex                   ];
                c = input[ srcIndex +     sourceWidth ];
              }
              b = input[ srcIndex + 1               ];
              d = input[ srcIndex + 1 + sourceWidth ];
            }

            lm = mx[j];
            rm = 255 - lm;

            // WTF?
            // Input  AA RR GG BB
            // Output RR GG BB AA

            if( j ){
              leftOutput = rightOutput ^ 0xFFFFFF00;
            }else{
              leftOutput =
                // blue element
                  (((  ( (a&0xFF)*tm
                       + (c&0xFF)*bm )*lm
                  ) & 0xFF0000 ) >> 8)

                // green element
                | (((  ( ((a>>8)&0xFF)*tm
                       + ((c>>8)&0xFF)*bm )*lm
                  ) & 0xFF0000 )) // no need to shift

                // red element
                | (((  ( ((a>>16)&0xFF)*tm
                       + ((c>>16)&0xFF)*bm )*lm
                  ) & 0xFF0000 ) << 8 )
              ;
            }

            rightOutput =
              // blue element
                (((  ( (b&0xFF)*tm
                     + (d&0xFF)*bm )*lm
                ) & 0xFF0000 ) >> 8)

              // green element
              | (((  ( ((b>>8)&0xFF)*tm
                     + ((d>>8)&0xFF)*bm )*lm
                ) & 0xFF0000 )) // no need to shift

              // red element
              | (((  ( ((b>>16)&0xFF)*tm
                     + ((d>>16)&0xFF)*bm )*lm
                ) & 0xFF0000 ) << 8 )
            ;

            output[offset++] =
              // alpha
              0x000000ff
              | leftOutput
              | rightOutput
            ;

        }
    }
}
于 2012-07-06T15:26:57.673 に答える
0 
 x = (int)(x_ratio * j) ;
 y = (int)(y_ratio * i) ;
 x_diff = (x_ratio * j) - x ;
 y_diff = (y_ratio * i) - y ;
 index = (y * sourceWidth + x) ;

確かにいくつかの最適化を使用できます。x_ration * j-1以前は数サイクルしか使用していなかったので、ここで本当に必要なのはx+=x_ratio

于 2012-07-06T13:45:25.140 に答える