drehen von bitmaps.In code
https://stackoverflow.com/questions/848025
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Gibt es einen schnelleren Weg zu drehen große bitmap um 90 oder 270 Grad, als Sie einfach tun, eine verschachtelte Schleife mit invertierten Koordinaten?
Die bitmaps werden 8 bit / Pixel und in der Regel 2048*2400*8 bit / Pixel
Derzeit kann ich dies tun, indem Sie einfach kopieren, mit dem argument inversion, etwa (pseudo-code:
for x = 0 to 2048-1
for y = 0 to 2048-1
dest[x][y]=src[y][x];
(In Wirklichkeit habe ich es mit Zeiger, für ein bisschen mehr Geschwindigkeit, aber das ist in etwa die gleiche Größenordnung)
GDI ist ziemlich langsam, mit großen Bildern und GPU-load - /store-Zeiten für Texturen (GF7 Karten) sind in der gleichen Größenordnung wie die aktuelle CPU-Zeit.
Irgendwelche Tipps, Hinweise?Ein in-place-Algorithmus wäre sogar besser, aber die Geschwindigkeit ist wichtiger, als in-place.
Ziel ist Delphi, aber es ist mehr eine Algorithmische Frage.SSE(2) Vektorisierung kein problem, es ist ein genügend großes problem für mich, um code in assembler
Folgen Sie bis zu Nils' Antwort
- Bild 2048x2700 -> 2700x2048
- Compiler Turbo Explorer 2006 mit Optimierung auf.
- Windows:Energieschema auf "Immer an".(wichtig!!!!!!!)
- Maschine:Core2 6600 (2,4 GHz)
Zeit mit der alten routine:32ms (Schritt 1)
Zeit mit stepsize 8 :12ms
Zeit mit stepsize 16 :10ms
Zeit mit stepsize 32+ :9ms
Mittlerweile habe ich auch getestet, auf dem ein Athlon 64 X2 (5200+ iirc), und die Geschwindigkeit, bis es war etwas mehr als einen Faktor vier (80 19 ms).
Die Geschwindigkeit-up ist es Wert, danke.Vielleicht, dass in den Sommermonaten werde ich Folter mich mit einem SSE - (2) - version.Allerdings habe ich schon darüber nachgedacht, wie man in Angriff zu nehmen, und ich denke, ich werde das ausführen von SSE2-Register für eine gerade Umsetzung:
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>
So 8x8 benötigt 9 registriert, aber 32-bit-SSE hat nur 8.Wie auch immer, das ist etwas für die Sommermonate :-)
Beachten Sie, dass der Zeiger Sache ist etwas, das ich aus Instinkt, aber es könnte sein, dass es tatsächlich etwas zu, wenn Ihre Dimensionen sind nicht fest kodiert, der compiler kann nicht schalten Sie die mul zu einer Verschiebung.Während muls an sich sind Billig, Sie generieren auch mehr registrieren, Druck, soweit ich weiß.
Der code (validiert durch Subtraktion ergeben sich aus der "naieve" rotate1 Umsetzung):
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;
Update 2 Generika
Ich habe versucht, aktualisieren Sie diesen code, um eine Generika-version in Delphi XE.Ich gescheitert, weil QC 99703 und forum Menschen haben bereits bestätigt, es gibt Sie auch in XE2.Bitte votet für ihn :-)
Update 3 Generika Arbeitet jetzt in XE10
Lösung
Ja, es gibt schnellere Möglichkeiten, dies zu tun.
Ihre einfache Schleife verbringt die meiste Zeit im cache findet.Diese happends, weil Sie Tippen eine Menge von Daten, die an sehr verschiedenen Orten in einer engen Schleife.Noch schlimmer:Ihr memory locations, die genau eine Potenz von zwei, auseinander.Das ist eine Größe, wo sich der cache führt Schlimmste.
Sie verbessern kann dieser rotation Algorithmus, wenn Sie der Verbesserung der Lokalität Ihrer Speicher zugreift.
Ein einfacher Weg, dies zu tun wäre zu drehen, jedes 8x8 pixel block auf seine eigene mit dem gleichen code, den Sie verwendet haben, für Ihre ganze bitmap, und wickeln Sie eine weitere Schleife, teilt die Bild-Drehung in Stücke 8x8 Pixel jeder.
E. g.so etwas wie diese (nicht geprüft, und sorry für die C-code.Meine Delphi-Kenntnisse sind nicht up-to-date):
// 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]
}
}
Es gibt andere Möglichkeiten, wie gut.Nun kann man die Daten in Hilbert-Ordnung oder die Morton-Ordnung.Das wäre theoretisch auch ein bisschen schneller, aber der code wird sehr viel komplexer sein.
Btw - Da Sie erwähnt haben, dass die SSE ist eine option für Sie.Beachten Sie, dass Sie drehen können, ein 8x8-byte-block innerhalb der SSE-Register.Es ist ein bisschen schwierig, um es zu bekommen zu arbeiten, aber ein Blick auf die SSE-matrix transponieren code sollte Ihnen den Einstieg, da es das gleiche.
EDIT:
Gerade überprüft:
Mit einer block-Größe von 8x8 Pixel der code wird ausgeführt, ca.5 mal schneller auf meinem Rechner.Mit einer block-Größe von 16x16 es läuft 10 mal schneller.
Scheint, wie es eine gute Idee, zu Experimentieren mit verschiedenen block-Größen.
Hier ist die (sehr einfachen) test-Programm, das ich verwendet habe:
#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);
}
Andere Tipps
Wenn Sie können verwenden C++, dann möchten Sie vielleicht zu schauen Eigen.
Es ist eine C++ - template-Bibliothek, die verwendet SSE (2 und neuer) und AltiVec instruction sets mit graceful fallback für nicht-vektorisierte code.
Schnell.(Siehe Benchmarks).
Expression templates allow intelligent zu entfernen Provisorien und aktivieren lazy evaluation, wenn das angemessen ist -- Eigen übernimmt dies automatisch und Griffe aliasing auch in den meisten Fällen.
Die explizite Vektorisierung ist für die Geleistete SSE (2 und neuer) und AltiVec instruction sets, mit graceful fallback to non-Vektorisierung.Expression templates allow führen diese Optimierungen Global für die ganze Ausdrücke.
Mit fester Größe Objekte, dynamische Speicherverwaltung vermieden, und die Schleifen sind abgerollt, wenn das Sinn macht.
Für große Matrizen, die Besondere Aufmerksamkeit auf die cache-Freundlichkeit.
Sie könnte in der Lage sein, zu verbessern, indem Sie in der cache-Blöcke ausgerichtet, anstatt durch die Reihen, als in dem moment der Schritt von entweder src dest wird ein miss ( je nachdem, ob delphi ist die Zeile mit der großen oder Spalte-Dur ).
Wenn das Bild nicht quadratisch ist, können Sie nicht in-place.Auch wenn Sie die Arbeit in quadratische Bilder, die Transformation ist nicht förderlich für die in-place-arbeiten.
Wenn Sie wollen, um zu versuchen, Dinge zu tun, ein wenig schneller, können Sie versuchen, Vorteile aus der Reihe Fortschritte zu machen es Arbeit, aber ich denke, das beste, was Sie tun würde, ist zu Lesen 4 Byte zu einem Zeitpunkt in eine lange, von der Quelle und dann schreiben Sie es in vier aufeinander folgenden Zeilen in der Ziel.Das sollte schneiden Sie einige Ihrer overhead, aber ich würde nicht erwarten, dass mehr als 5% verbessert.
