delphi - 如何在代码中有效地旋转位图

Question

是否有比简单地使用反转坐标进行嵌套循环更快的方法将大位图旋转 90 或 270 度？

位图为 8bpp，通常为 2048x2400x8bpp

目前，我通过简单地通过参数反转进行复制来实现此目的，大致如下(伪代码:

for x = 0 to 2048-1
  for y = 0 to 2048-1
    dest[x][y]=src[y][x];

(实际上，我用指针来实现，速度更快，但幅度大致相同)

GDI 对于大图像来说相当慢，并且纹理(GF7 卡)的 GPU 加载/存储时间与当前 CPU 时间相同。

有什么提示、指点吗？就地算法甚至会更好，但速度比就地更重要。

目标是Delphi，但它更多的是一个算法问题。 SSE(2) 向量化没问题，这对我来说是一个足够大的问题，需要用汇编程序对其进行编码

<小时/>

跟进尼尔斯的回答

• 图片 2048x2700 -> 2700x2048
• 已启用优化的编译器 Turbo Explorer 2006。
• Windows:电源方案设置为“始终开启”。 (重要!!!)
• 机器:Core2 6600 (2.4 GHz)

旧例程的时间:32ms(步骤 1)

步长为 8 的时间:12ms

步长为 16 的时间:10ms

步长为 32+ 的时间:9ms

同时，我还在 Athlon 64 X2 (5200+ iirc) 上进行了测试，速度提升略高于四倍(80 至 19 毫秒)。

加速是非常值得的，谢谢。也许在夏天我会用 SSE(2) 版本来折磨自己。不过我已经考虑过如何解决这个问题，并且我想我会用完 SSE2 寄存器来直接实现:

for n:=0 to 7 do
  begin
    load r0, <source+n*rowsize> 
    shift byte from r0 into r1
    shift byte from r0 into r2
    ..
    shift byte from r0 into r8
  end; 
store r1, <target>   
store r2, <target+1*<rowsize>
..
store r8, <target+7*<rowsize>   

所以 8x8 需要 9 个寄存器，但 32 位 SSE 只有 8 个。无论如何，这是夏季的事情:-)

请注意，指针的事情是我出于本能所做的事情，但它可能实际上有一些东西，如果你的维度没有硬编码，编译器无法将 mul 转换为移位。虽然现在 muls an sich 很便宜，但它们也会产生更大的套准压力。

代码(通过从“naieve”rotate1 实现中减去结果进行验证):

const stepsize = 32;
procedure rotatealign(Source: tbw8image; Target:tbw8image);

var stepsx,stepsy,restx,resty : Integer;
   RowPitchSource, RowPitchTarget : Integer;
   pSource, pTarget,ps1,ps2 : pchar;
   x,y,i,j: integer;
   rpstep : integer;
begin
  RowPitchSource := source.RowPitch;          // bytes to jump to next line. Can be negative (includes alignment)
  RowPitchTarget := target.RowPitch;        rpstep:=RowPitchTarget*stepsize;
  stepsx:=source.ImageWidth div stepsize;
  stepsy:=source.ImageHeight div stepsize;
  // check if mod 16=0 here for both dimensions, if so -> SSE2.
  for y := 0 to stepsy - 1 do
    begin
      psource:=source.GetImagePointer(0,y*stepsize);    // gets pointer to pixel x,y
      ptarget:=Target.GetImagePointer(target.imagewidth-(y+1)*stepsize,0);
      for x := 0 to stepsx - 1 do
        begin
          for i := 0 to stepsize - 1 do
            begin
              ps1:=@psource[rowpitchsource*i];   // ( 0,i)
              ps2:=@ptarget[stepsize-1-i];       //  (maxx-i,0);
              for j := 0 to stepsize - 1 do
               begin
                 ps2[0]:=ps1[j];
                 inc(ps2,RowPitchTarget);
               end;
            end;
          inc(psource,stepsize);
          inc(ptarget,rpstep);
        end;
    end;
  // 3 more areas to do, with dimensions
  // - stepsy*stepsize * restx        // right most column of restx width
  // - stepsx*stepsize * resty        // bottom row with resty height
  // - restx*resty                    // bottom-right rectangle.
  restx:=source.ImageWidth mod stepsize;   // typically zero because width is 
                                          // typically 1024 or 2048
  resty:=source.Imageheight mod stepsize;
  if restx>0 then
    begin
      // one loop less, since we know this fits in one line of  "blocks"
      psource:=source.GetImagePointer(source.ImageWidth-restx,0);    // gets pointer to pixel x,y
      ptarget:=Target.GetImagePointer(Target.imagewidth-stepsize,Target.imageheight-restx);
      for y := 0 to stepsy - 1 do
        begin
          for i := 0 to stepsize - 1 do
            begin
              ps1:=@psource[rowpitchsource*i];   // ( 0,i)
              ps2:=@ptarget[stepsize-1-i];       //  (maxx-i,0);
              for j := 0 to restx - 1 do
               begin
                 ps2[0]:=ps1[j];
                 inc(ps2,RowPitchTarget);
               end;
            end;
         inc(psource,stepsize*RowPitchSource);
         dec(ptarget,stepsize);
       end;
    end;
  if resty>0 then
    begin
      // one loop less, since we know this fits in one line of  "blocks"
      psource:=source.GetImagePointer(0,source.ImageHeight-resty);    // gets pointer to pixel x,y
      ptarget:=Target.GetImagePointer(0,0);
      for x := 0 to stepsx - 1 do
        begin
          for i := 0 to resty- 1 do
            begin
              ps1:=@psource[rowpitchsource*i];   // ( 0,i)
              ps2:=@ptarget[resty-1-i];       //  (maxx-i,0);
              for j := 0 to stepsize - 1 do
               begin
                 ps2[0]:=ps1[j];
                 inc(ps2,RowPitchTarget);
               end;
            end;
         inc(psource,stepsize);
         inc(ptarget,rpstep);
       end;
    end;
 if (resty>0) and (restx>0) then
    begin
      // another loop less, since only one block
      psource:=source.GetImagePointer(source.ImageWidth-restx,source.ImageHeight-resty);    // gets pointer to pixel x,y
      ptarget:=Target.GetImagePointer(0,target.ImageHeight-restx);
      for i := 0 to resty- 1 do
        begin
          ps1:=@psource[rowpitchsource*i];   // ( 0,i)
          ps2:=@ptarget[resty-1-i];       //  (maxx-i,0);
          for j := 0 to restx - 1 do
            begin
              ps2[0]:=ps1[j];
              inc(ps2,RowPitchTarget);
            end;
       end;
    end;
end;

更新 2 个泛型

我尝试将此代码更新为 Delphi XE 中的泛型版本。我因为QC 99703失败了，论坛的人已经确认它也存在于XE2中。请投票:-)

更新 3 个泛型现在可以在 XE10 中使用

更新4

2017 年，我为 8x8 cubes of 8bpp images only 的汇编版本做了一些工作。及相关SO question关于彼得·科德斯慷慨地帮助我解决洗牌瓶颈的问题。这段代码仍然错失了机会，并且仍然需要另一个循环级别来将多个 8x8 block 迭代聚合成伪更大的迭代，例如 64x64。现在又是整行，这是浪费。

Answer 1

是的，有更快的方法可以做到这一点。

您的简单循环大部分时间都花在缓存未命中上。发生这种情况是因为您在紧密循环中的不同位置接触了大量数据。更糟糕的是:你的内存位置相距正好是2的幂。这是缓存性能最差的大小。

如果您改进内存访问的局部性，则可以改进此轮换算法。

一种简单的方法是使用与整个位图相同的代码自行旋转每个 8x8 像素 block ，并包装另一个循环，将图像旋转分成每个 8x8 像素的 block 。

例如像这样的东西(未检查，对 C 代码感到抱歉。我的 Delphi 技能不是最新的):

 // this is the outer-loop that breaks your image rotation
 // into chunks of 8x8 pixels each:
 for (int block_x = 0; block_x < 2048; block_x+=8)
 {
    for (int block_y = 0; blocky_y < 2048; block_y+=8)
    { 
       // this is the inner-loop that processes a block
       // of 8x8 pixels.
       for (int x= 0; x<8; x++)
         for (int y=0; y<8; y++)
            dest[x+block_x][y+block_y] = src[y+block_y][x+block_x]
    }
 } 

还有其他方法。您可以按希尔伯特阶或莫顿阶处理数据。理论上这会更快一点，但代码会复杂得多。

顺便说一句 - 既然您提到 SSE 是您的一个选择。请注意，您可以在 SSE 寄存器内旋转 8x8 字节 block 。要让它工作有点棘手，但是查看 SSE 矩阵转置代码应该可以帮助您入门，因为它们是同一件事。

<小时/>

编辑:

刚刚检查:

对于 8x8 像素的 block 大小，代码运行大约。在我的机器上速度快了 5 倍。 block 大小为 16x16 时，运行速度提高了 10 倍。

尝试不同的 block 大小似乎是个好主意。

这是我使用过的(非常简单的)测试程序:

#include <stdio.h>
#include <windows.h>

char temp1[2048*2048];
char temp2[2048*2048];

void rotate1 (void)
{
  int x,y;
  for (y=0; y<2048; y++)
  for (x=0; x<2048; x++)
    temp2[2048*y+x] = temp1[2048*x+y];
}

void rotate2 (void)
{
  int x,y;
  int bx, by;

  for (by=0; by<2048; by+=8)
  for (bx=0; bx<2048; bx+=8)
  for (y=0; y<8; y++)
  for (x=0; x<8; x++)
    temp2[2048*(y+by)+x+bx] = temp1[2048*(x+bx)+y+by];
}

void rotate3 (void)
{
  int x,y;
  int bx, by;

  for (by=0; by<2048; by+=16)
  for (bx=0; bx<2048; bx+=16)
  for (y=0; y<16; y++)
  for (x=0; x<16; x++)
    temp2[2048*(y+by)+x+bx] = temp1[2048*(x+bx)+y+by];
}


int main (int argc, char **args)
{
  int i, t1;

  t1 = GetTickCount();
  for (i=0; i<20; i++) rotate1();
  printf ("%d\n", GetTickCount()-t1);

  t1 = GetTickCount();
  for (i=0; i<20; i++) rotate2();
  printf ("%d\n", GetTickCount()-t1);

  t1 = GetTickCount();
  for (i=0; i<20; i++) rotate3();
  printf ("%d\n", GetTickCount()-t1);

}