Вращающиеся растровые изображения. В коде
Есть ли более быстрый способ поворота большого растрового изображения на 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) в той же величине, что и текущее время процессора.
Любые советы, указатели? Алгоритм на месте был бы даже лучше, но скорость важнее, чем быть на месте.
Цель - Delphi, но это скорее алгоритмический вопрос. SSE (2) векторизация не проблема, для меня достаточно большая проблема, чтобы закодировать ее в ассемблере
Следуйте за ответом Нилса
- Изображение 2048x2700 → 2700x2048
- Компилятор Turbo Explorer 2006 с оптимизацией.
- Windows: схема питания установлена на "Always on". (<Б > важно!!!!)
- Машина: Core2 6600 (2,4 ГГц)
время со старой рутиной: 32 мс (шаг 1)
время с шагом 8: 12ms
время с шагом 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. Во всяком случае, это что-то для летних месяцев: -)
Обратите внимание, что вещь-указатель - это то, что я делаю из инстинкта, но это может быть что-то для нее, если ваши измерения не жестко закодированы, компилятор не может превратить мул в сдвиг. В то время как muls an sich дешево в наши дни, они также генерируют большее давление afaik.
Код (подтвержденный вычитанием результата из реализации "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:[email protected][rowpitchsource*i]; // ( 0,i)
ps2:[email protected][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:[email protected][rowpitchsource*i]; // ( 0,i)
ps2:[email protected][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:[email protected][rowpitchsource*i]; // ( 0,i)
ps2:[email protected][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:[email protected][rowpitchsource*i]; // ( 0,i)
ps2:[email protected][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
Я попытался обновить этот код до версии generics в Delphi XE. Я потерпел неудачу из-за QC 99703, и люди форума уже подтвердили, что он также существует в XE2. Пожалуйста, проголосуйте за него:-)
Обновление 3 Generics
Работает сейчас в XE10
Ответы
Ответ 1
Да, есть более быстрые способы сделать это.
Ваш простой цикл тратит большую часть времени на пропуски в кеше. Это происходит потому, что вы касаетесь большого количества данных в самых разных местах в узком цикле. Еще хуже: ваши места в памяти точно разделены на две части. Это размер, в котором кеш работает хуже.
Вы можете улучшить этот алгоритм вращения, если вы улучшите локальность доступа к памяти.
Простым способом сделать это было бы повернуть каждый блок размером 8 × 8 на свой собственный, используя тот же код, который вы использовали для всего вашего растрового изображения, и обернуть еще один цикл, который разбивает поворот изображения на куски размером 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. Это было бы теоретически даже немного быстрее, но код будет намного сложнее.
Btw - Поскольку вы упомянули, что SSE является для вас вариантом. Обратите внимание, что вы можете повернуть блок 8x8 байтов в SSE-регистры. Это немного сложно, чтобы заставить его работать, но, глядя на код транспонирования матрицы SSE, вы должны начать с него, как с тем же.
EDIT:
Только что отмечен:
С размером блока 8x8 пикселей код пробегает ca. 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);
}
Ответ 2
Если вы можете использовать С++, вы можете посмотреть Eigen.
Это библиотека шаблонов С++, которая использует команды SSE (2 и более поздние) и AltiVec с грациозным откатом для не-векторизованного кода.
Fast. (См. Контрольный показатель).
Шаблоны выражений позволяют разумно удалять временные файлы и давать ленивую оценку, когда это уместно - Eigen позаботится об этом автоматически и в большинстве случаев обрабатывает aliasing.
Явная векторизация выполняется для наборов инструкций SSE (2 и более поздних) и AltiVec с грациозным откатом от не-векторизованного кода. Шаблоны выражений позволяют выполнять эти оптимизации глобально для целых выражений.
При использовании объектов фиксированного размера исключается распределение динамической памяти, а циклы разворачиваются, когда это имеет смысл.
Для больших матриц особое внимание уделяется кэш-совместимости.
Ответ 3
Возможно, вы сможете улучшить его, скопировав в блоках с выравниванием по керам, а не по строкам, так как на данный момент шаг либо src dest будет пропущен (в зависимости от того, является ли delphi основной строкой или столбцом).
Ответ 4
Если изображение не квадратное, вы не можете сделать это на месте. Даже если вы работаете с квадратными изображениями, преобразование не способствует работе на месте.
Если вы хотите попытаться сделать что-то немного быстрее, вы можете попытаться воспользоваться преимуществами ряда строк, чтобы заставить его работать, но я думаю, что лучше всего вы будете читать 4 байта за один раз в течение длительного времени источник, а затем записать его в четыре последовательные строки в dest. Это должно сократить некоторые из ваших накладных расходов, но я не ожидал бы улучшения более чем на 5%.
