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. 停止使用浮点，除非您确定您的目标 CPU 在硬件中具有良好的性能。
  2. 确保内存访问是缓存优化的，即聚集在一起。
  3. 尽可能使用最快的数据类型。有时这意味着最小，有时意味着“最原生，需要最少的开销”。
  4. 调查整数运算的有符号/无符号是否在您的平台上有性能成本。
  5. 调查查找表而不是计算是否能给你带来任何好处（但这些可能会破坏缓存，所以要小心）。

当然，还要进行大量的分析和测量。

于 2012-07-06T13:25:11.013 回答
3

内联缓存和查找表

在你的算法中缓存你的计算。

  • 避免重复计算（如(1-y_diff)or (x_ratio * j)）

    遍历算法的所有行，并尝试识别重复模式。将这些提取到局部变量中。并且可能提取到函数，如果它们足够短可以内联，以使事情更具可读性。

  • 使用查找表

    很有可能，如果您可以节省一些内存，您可以为您的 RGB 值实现“存储”，并根据生成它们的输入简单地“获取”它们。也许您不需要存储所有这些，但您可以进行试验，看看是否有一些经常回来。或者，您可以“捏造”您的颜色，从而以更少的值存储更多的查找输入。

    如果您知道输入的边界，则可以计算完整的域空间并找出缓存的意义。例如，如果您不能缓存整个R, G,B值，也许您至少可以预先计算(b>>16)在您的情况下最有可能确定的移位（等等......）。

使用正确的数据类型来提高性能

如果可以避免double和float变量，请使用int. 在大多数架构上，int由于内存模型，将测试更快的计算类型。您仍然可以通过简单地移动单位（即使用1026asint而不是1.026asdouble或float）来获得不错的精度。这个技巧很可能对你来说已经足够了。

于 2012-07-06T13:48:41.393 回答
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 回答
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

我的随机猜测（使用分析器而不是让人们猜测！）：

当输入和输出重叠时，编译器必须生成有效的方法，这意味着它必须生成大量冗余存储和加载。添加restrict到输入和输出参数以删除该安全功能。

您也可以尝试使用a=b;andc=d;而不是再次加载它们。

于 2012-07-06T15:39:57.977 回答