rotation des bitmaps.Dans du code
https://stackoverflow.com/questions/848025
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Existe-t-il un moyen plus rapide de faire pivoter un grand bitmap de 90 ou 270 degrés que de simplement faire une boucle imbriquée avec des coordonnées inversées ?
Les bitmaps sont de 8 bpp et généralement de 2 048 * 2 400 * 8 bpp
Actuellement, je fais cela en copiant simplement avec inversion d'argument, en gros (pseudo code :
for x = 0 to 2048-1
for y = 0 to 2048-1
dest[x][y]=src[y][x];
(En réalité je le fais avec des pointeurs, pour un peu plus de vitesse, mais c'est à peu près la même ampleur)
GDI est assez lent avec de grandes images, et les temps de chargement/stockage du GPU pour les textures (cartes GF7) sont de la même ampleur que le temps CPU actuel.
Des conseils, des indications ?Un algorithme sur place serait encore meilleur, mais la vitesse est plus importante que le fait d'être sur place.
La cible est Delphi, mais c'est plutôt une question algorithmique.Vectorisation SSE(2) pas de problème, c'est un problème suffisamment gros pour que je le code en assembleur
Suite à la réponse de Nils
- Image 2048x2700 -> 2700x2048
- Compilateur Turbo Explorer 2006 avec optimisation activée.
- Les fenêtres:Schéma d'alimentation défini sur "Toujours activé".(important!!!!)
- Machine:Core2 6600 (2,4 GHz)
du temps avec la vieille routine :32 ms (étape 1)
temps avec pas de 8 :12 ms
temps avec pas de 16 :10 ms
temps avec un pas de 32+ :9 ms
Pendant ce temps, j'ai également testé sur un Athlon 64 X2 (5200+ iirc), et la vitesse y était légèrement supérieure à un facteur quatre (80 à 19 ms).
L'accélération en vaut la peine, merci.Peut-être que pendant les mois d'été je me torturerai avec une version SSE(2).Cependant, j'ai déjà réfléchi à la manière de résoudre ce problème, et je pense que je vais manquer de registres SSE2 pour une implémentation directe :
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>
Ainsi, 8x8 a besoin de 9 registres, mais SSE 32 bits n'en a que 8.Quoi qu'il en soit, c'est quelque chose pour les mois d'été :-)
Notez que le pointeur est quelque chose que je fais par instinct, mais il se peut qu'il y ait en fait quelque chose, si vos dimensions ne sont pas codées en dur, le compilateur ne peut pas transformer le mul en décalage.Bien que les muls an sich soient bon marché de nos jours, ils génèrent également plus de pression sur les registres, autant que je sache.
Le code (validé en soustrayant le résultat de l'implémentation "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;
Mise à jour 2 génériques
J'ai essayé de mettre à jour ce code vers une version générique dans Delphi XE.J'ai échoué à cause de QC 99703, et les gens du forum ont déjà confirmé qu'il existe également dans XE2.Merci de voter pour :-)
Mise à jour 3 génériquesFonctionne maintenant dans XE10
La solution
Oui, il existe des moyens plus rapides de procéder.
Votre simple boucle passe la plupart du temps dans les échecs de cache.Cela se produit parce que vous touchez un grand nombre de données à des endroits très différents dans une boucle étroite.Encore pire:Vos emplacements de mémoire sont exactement espacés d’une puissance de deux.C'est une taille où le cache fonctionne le moins bien.
Vous pouvez améliorer cet algorithme de rotation si vous améliorez la localité de vos accès mémoire.
Un moyen simple de procéder serait de faire pivoter chaque bloc de 8 x 8 pixels seul en utilisant le même code que vous avez utilisé pour l'ensemble de votre bitmap, et d'enrouler une autre boucle qui divise la rotation de l'image en morceaux de 8 x 8 pixels chacun.
Par exemple.quelque chose comme ça (non vérifié, et désolé pour le code C.Mes compétences Delphi ne sont pas à jour) :
// 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]
}
}
Il existe également d'autres moyens.Vous pouvez traiter les données dans Hilbert-Order ou Morton-Order.Ce serait en théorie encore un peu plus rapide, mais le code serait beaucoup plus complexe.
Btw - Puisque vous avez mentionné que SSE est une option pour vous.Notez que vous pouvez faire pivoter un bloc de 8x8 octets dans les registres SSE.C'est un peu délicat de le faire fonctionner, mais regarder le code de transposition de la matrice SSE devrait vous aider à démarrer car c'est la même chose.
MODIFIER:
Je viens de vérifier :
Avec une taille de bloc de 8x8 pixels, le code s'exécute env.5 fois plus rapide sur ma machine.Avec une taille de bloc de 16x16, il fonctionne 10 fois plus vite.
On dirait que c'est une bonne idée d'expérimenter différentes tailles de blocs.
Voici le programme de test (très simple) que j'ai utilisé :
#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);
}
Autres conseils
Si vous pouvez utiliser C++, vous voudrez peut-être regarder Propre.
Il s'agit d'une bibliothèque de modèles C++ qui utilise Jeux d'instructions SSE (2 et versions ultérieures) et AltiVec avec repli gracieux vers du code non vectorisé.
Rapide.(Voir benchmark).
Les modèles d'expression permettent de supprimer intelligemment les temporaires et d'activer une évaluation paresseuse, lorsque cela est approprié - Eigen s'en charge automatiquement et gère également l'alias dans la plupart des cas.
La vectorisation explicite est effectuée pour les jeux d'instructions SSE (2 et versions ultérieures) et AltiVec, avec un repli gracieux vers du code non vectorisé.Les modèles d'expression permettent d'effectuer ces optimisations globalement pour des expressions entières.
Avec les objets de taille fixe, l'allocation dynamique de mémoire est évitée et les boucles sont déroulées lorsque cela a du sens.
Pour les grandes matrices, une attention particulière est accordée à la convivialité du cache.
Toi pourrait pouvoir l'améliorer en copiant dans des blocs alignés sur le cache plutôt que par lignes, car pour le moment, la foulée de l'un ou l'autre src dest sera manquée (selon que Delphi est en ligne majeure ou en colonne majeure).
Si l'image n'est pas carrée, vous ne pouvez pas la faire sur place.Même si vous travaillez sur des images carrées, la transformation n'est pas propice au travail sur place.
Si vous voulez essayer de faire les choses un peu plus vite, vous pouvez essayer de profiter des progrès de ligne pour que cela fonctionne, mais je pense que le mieux que vous feriez est de lire 4 octets à la fois dans un long à partir de la source et puis écrivez-le sur quatre lignes consécutives dans le dest.Cela devrait réduire une partie de vos frais généraux, mais je ne m'attendrais pas à une amélioration de plus de 5 %.
