有没有更快的方法来旋转一个大的位图90或270度,而不是简单地做一个嵌套的循环与倒置坐标?
位图是8bpp,通常是2048 * 2400 * 8bpp
目前我通过简单地使用参数反转进行复制,粗略地(伪代码:
for x = 0 to 2048-1
for y = 0 to 2048-1
dest[x][y]=src[y][x];
(实际上我用指针来做,速度更快一些,但大致相同)
大图像的GDI速度非常慢,纹理(GF7卡)的GPU加载/存储时间与当前CPU时间相同。
任何提示,指针?原地算法甚至会更好,但速度比原地更重要。
它更多是一个算法问题。SSE(2)矢量化没有问题,对我来说,在汇编程序中对它进行编码是一个足够大的问题
时间与旧例程:32毫秒(步骤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变成一个转变。虽然现在的廉价商品价格便宜,但它们也会产生更多的注册压力。
代码(通过从“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;
我试图将此代码更新为Delphi XE中的泛型版本。我因QC 99703而失败,论坛的人已经证实它也存在于XE2中。
现在可以在XE10中使用
发布于 2018-03-15 13:59:13
是的,有更快的方法来做到这一点。
简单循环大部分时间都用在缓存未命中。发生这种情况是因为您在紧密的环路中在非常不同的地方触摸了大量数据。更糟的是:你的内存位置恰恰是两个分开的力量。这是缓存表现最差的大小。
如果改善内存访问的局部性,则可以改进此旋转算法。
一个简单的方法是使用与整个位图相同的代码自行旋转每个8x8像素块,然后包装另一个循环,将图像旋转分割为8x8像素的块。
例如像这样的东西(没有检查,并且对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]
}
}
还有其他方法。你可以用Hilbert-Order或Morton-Order来处理数据。这在理论上会更快一些,但代码会更复杂。
顺便说一句 - 既然你提到SSE是你的选择。请注意,您可以旋转SSE寄存器内的8x8字节块。让它工作起来有点棘手,但看看SSE矩阵转置代码应该让你开始,因为它是一回事。
使用8x8像素的块大小代码运行约。我的机器快了5倍。对于16x16的块大小,其运行速度提高了10倍。
似乎尝试不同的块大小是个好主意。
这是我用过的(非常简单的)测试程序:
#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);
}
发布于 2018-03-15 15:22:07
如果你可以使用C ++,那么你可能想看看Eigen。
它是一个C ++模板库,它使用SSE(2及更高版本)和AltiVec指令集,优雅地回退到非矢量化代码。
快速。(见基准)。 表达式模板允许智能地删除临时对象并启用惰性评估(如果适当的话) - Eigen自动处理并在大多数情况下也处理别名。 对SSE(2及更高版本)和AltiVec指令集执行显式矢量化,并优雅地回退到非矢量化代码。表达式模板允许为整个表达式全局执行这些优化。 对于固定大小的对象,可以避免动态内存分配,并且在有意义时展开循环。 对于大型矩阵,需要特别注意缓存友好性。
https://stackoverflow.com/questions/-100007631
复制相似问题