Вращающиеся растровые изображения. В коде
Существует ли более быстрый способ поворота большого растрового изображения на 90 или 270 градусов, чем просто выполнение вложенного цикла с инвертированными координатами?
Растровые изображения имеют размер 8 бит / с и обычно 2048*2400*8 бит / с.
В настоящее время я делаю это, просто копируя с инверсией аргумента, примерно (псевдокод:
for x = 0 to 2048-1
for y = 0 to 2048-1
dest[x][y]=src[y][x];
(На самом деле я делаю это с помощью указателей, для большей скорости, но это примерно такая же величина)
GDI довольно медленно работает с большими изображениями, а время загрузки / сохранения текстур (карты GF7) для GPU совпадает с текущим временем процессора.
Любые советы, указатели? Алгоритм на месте был бы даже лучше, но скорость важнее, чем быть на месте.
Цель - Delphi, но это скорее алгоритмический вопрос. SSE(2) векторизация не проблема, это достаточно большая проблема для меня, чтобы написать код на ассемблере
Продолжайте до ответа Нильса
- Изображение 2048x2700 -> 2700x2048
- Компилятор Turbo Explorer 2006 с оптимизацией на.
- Windows: Схема питания установлена на "Всегда включено". (важно!!!!)
- Машина: Core2 6600 (2,4 ГГц)
время со старой программой: 32 мс (шаг 1)
время с шагом 8: 12 мс
время с шагом 16: 10 мс
время с шагом 32+: 9 мс
Тем временем я также тестировал 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. В любом случае, это что-то для летних месяцев:-)
Обратите внимание, что указатель - это то, что я делаю не по инстинкту, но, возможно, в этом есть что-то, если ваши измерения не жестко запрограммированы, компилятор не может превратить мул в сдвиг. В то время как мульс и сич в наше время дешевы, они также создают больше регистрового давления.
Код (проверяется путем вычитания результата из реализации "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 Generics
Я попытался обновить этот код до универсальной версии в Delphi XE. Я потерпел неудачу из-за QC 99703, и форумчане уже подтвердили, что он также существует в XE2. Пожалуйста, проголосуйте за это:-)
Обновление 3 Generics теперь работает в XE10
4 ответа
Да, есть более быстрые способы сделать это.
Ваш простой цикл проводит большую часть времени в промахах кеша. Это происходит потому, что вы касаетесь большого количества данных в очень разных местах в узком цикле. Еще хуже: ваши места памяти - это как раз две степени. Это размер, где кеш работает хуже всего.
Вы можете улучшить этот алгоритм ротации, если улучшите локальность ваших обращений к памяти.
Простой способ сделать это состоит в том, чтобы повернуть каждый блок 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]
}
}
Есть и другие способы. Вы можете обрабатывать данные в порядке Гильберта или Мортона. Теоретически это будет даже немного быстрее, но код будет намного сложнее.
Кстати, так как вы упомянули, что SSE является вариантом для вас. Обратите внимание, что вы можете вращать 8-байтовый блок в регистрах SSE. Немного сложно заставить его работать, но изучение транспонирования кода SSE должно помочь вам начать, так как это одно и то же.
РЕДАКТИРОВАТЬ:
Только что проверил:
При размере блока 8х8 пикселей код выполняется ок. В 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);
}
Если вы можете использовать C++, вы можете посмотреть на Eigen.
Это библиотека шаблонов C++, которая использует наборы инструкций SSE (2 и более поздние версии) и AltiVec с постепенным отступлением от не векторизованного кода.
Быстро. (См. Эталонный тест).
Шаблоны выражений позволяют разумно удалять временные значения и включать ленивую оценку, когда это уместно - Eigen позаботится об этом автоматически и в большинстве случаев обрабатывает псевдонимы.
Явная векторизация выполняется для наборов команд SSE (2 и более поздних) и AltiVec с постепенным отступлением от не векторизованного кода. Шаблоны выражений позволяют выполнять эти оптимизации глобально для целых выражений.
С объектами фиксированного размера динамическое выделение памяти исключается, и циклы развертываются, когда это имеет смысл.
Для больших матриц особое внимание уделяется кешированию.
Вы можете улучшить его, копируя в выровненные по кэшу блоки, а не по строкам, так как в настоящий момент шаг src dest будет пропущен (в зависимости от того, является ли delphi мажорной строкой или мажорной колонкой).
Если изображение не квадратное, вы не можете сделать на месте. Даже если вы работаете с квадратными изображениями, преобразование не способствует работе на месте.
Если вы хотите попытаться сделать что-то немного быстрее, вы можете попытаться воспользоваться преимуществами последовательных шагов, чтобы заставить его работать, но я думаю, что лучшее, что вы могли бы сделать, это читать по 4 байта за раз из источника и затем запишите это в четыре последовательных ряда в dest. Это должно сократить ваши накладные расходы, но я бы не ожидал улучшения более чем на 5%.