Hay una manera más rápida para girar un gran de mapa de bits por 90 o 270 grados que, simplemente, hacer un bucle anidado con invertida coordenadas?

Los mapas de bits son 8bpp y normalmente 2048*2400*8bpp

Actualmente hago esto simplemente copiando con el argumento de la inversión de, aproximadamente (pseudo código:

for x = 0 to 2048-1
  for y = 0 to 2048-1
    dest[x][y]=src[y][x];

(En realidad yo lo hago con los punteros, por un poco más de velocidad, pero que es aproximadamente la misma magnitud)

GDI es bastante lenta, con imágenes de gran tamaño, y la GPU load/store veces para texturas (GF7 tarjetas) están en el mismo orden de magnitud que el actual tiempo de CPU.

Los consejos, los punteros? Un lugar algoritmo incluso sería mejor, pero la velocidad es más importante que estar en el lugar.

Objetivo es Delphi, pero es más un algoritmo pregunta. ESS(2) vectorización ningún problema, no es un gran problema bastante para mí el código en ensamblador


Seguimiento a Nils’ respuesta

  • Imagen 2048×2700 -> 2700×2048
  • Compilador de Turbo Explorer 2006 con una optimización.
  • Windows: esquema de Poder establecer a «Siempre». (¡importante!!!!)
  • De La Máquina: Core2 6600 (2.4 GHz)

tiempo con la rutina de siempre: 32ms (paso 1)

tiempo con stepsize 8 : 12ms

tiempo con stepsize 16 : 10ms

tiempo con stepsize 32+ : 9ms

Mientras tanto, he probado también en un Athlon 64 X2 (5200+ iirc), y la velocidad hasta hubo un poco más de un factor de cuatro (80 a 19 ms).

La velocidad es bien vale la pena, gracias. Tal vez que durante los meses de verano voy a tortura a mí mismo con un ESS(2) versión. Sin embargo, yo ya había pensado en cómo hacer frente a esa, y creo que voy a correr fuera de SSE2 se registra para una recta aplicación:

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>   

Así 8×8 necesidades 9 los registros, pero de 32 bits ESS solo tiene 8. De todos modos eso es algo para los meses de verano 🙂

Tenga en cuenta que el puntero cosa es algo que hago por instinto, pero podría ser, de hecho, hay algo en ella, si sus dimensiones no están codificados, el compilador no puede girar a la mul en un cambio. Mientras muls an sich son baratos hoy en día, sino que también generan más registrar la presión afaik.

El código (validado por restando el resultado de la «naieve» rotate1 aplicación):

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]psource[rowpitchsource*i];   // ( 0,i)
ps2:[email protected]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:[email protected]psource[rowpitchsource*i];   // ( 0,i)
ps2:[email protected]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:[email protected]psource[rowpitchsource*i];   // ( 0,i)
ps2:[email protected]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:[email protected]psource[rowpitchsource*i];   // ( 0,i)
ps2:[email protected]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;

Actualización 2 Genéricos

Traté de actualizar este código a los genéricos de la versión en Delphi XE. Yo no, porque de control de calidad 99703, y en el foro de personas ya han confirmado que también existe en XE2. Por favor vote por ella 🙂

Actualización 3 de Genéricos
Ahora trabaja en XE10

4 Comentarios

  1. 21

    Sí, hay maneras más rápidas de hacer esto.

    Su simple bucle pasa la mayor parte del tiempo en la cache misses. Este happends porque toca una gran cantidad de datos en lugares muy diferentes en un bucle ajustado. Peor aún: Sus lugares de memoria son exactamente una potencia de dos aparte. Esa es una dimensión en la que la caché realiza peor.

    Puede mejorar este algoritmo de rotación si mejora la localidad de sus accesos a la memoria.

    Una manera sencilla de hacerlo sería a girar cada bloque de 8×8 píxeles en su propia utilizando el mismo código que he usado durante toda su mapa de bits, y una envoltura de otro bucle que se divide la rotación de la imagen en bloques de 8×8 píxeles cada una.

    E. g. algo como esto (no comprobado, y lo siento por la C-código. Mi Delphi habilidades no están actualizados):

     //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]
    }
    } 

    Hay otras maneras también. Usted puede procesar los datos de Hilbert de Orden o de Morton-Orden. Que sería, en teoría, incluso un poco más rápido, pero el código será mucho más complejo.

    Por cierto – Ya que usted ha mencionado que la ESS es una opción para usted. Tenga en cuenta que puede girar un 8×8 de bytes de bloque dentro de la ESS en los registros. Es un poco difícil conseguir trabajo, pero mirando al SSE de la matriz transpuesta de código debe empezar ya que es la misma cosa.


    EDICIÓN:

    Acaba:

    Con un bloque de tamaño de 8×8 píxeles, el código se ejecuta ca. 5 veces más rápido que en mi máquina. Con un bloque de tamaño de 16×16 se ejecuta 10 veces más rápido.

    Parece que es una buena idea experimentar con diferentes bloques de tamaños.

    Aquí es el (muy simple) prueba-programa que he utilizado:

    #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);
    }
    • Ok, gracias. Que suena muy prometedor. A 10 veces la velocidad sería suficiente por ahora, algo que no me gustaría molestar a jugar con ESS para. Al menos no ahora. Había tenido una mala sensación sobre hacerlo en pequeños bloques, y de esta manera se confirma y me proporciona una implementación.
    • La técnica se llama bucle de segmentación por cierto. Ah, y no olvide que usted puede paralelizar la escala. Acaba de empezar dos hilos y dejar que cada uno se la manija de la mitad de la imagen.
    • Naah, ya tienen un núcleo dedicado a cada cámara 😉
    • Por cierto Marco, una Vez que haya implementado, háganoslo saber cuánto de una velocidad de hasta que usted haya tenido. Tengo curiosidad de cómo se realiza en una aplicación en el mundo real.
    • Hecho, he actualizado a la pregunta
    • Otra actualización. Este verano por fin hice el ensamblador. Con pequeños tamaños de imagen es hasta 4 veces más rápido que el looptiling uno, véase también stackoverflow.com/questions/47478010/…

  2. 3

    Si se puede usar C++, entonces usted puede desear mirar en Eigen.

    Es una biblioteca de plantillas C++ que utiliza ESS (2 y posteriores) y conjuntos de instrucciones AltiVec, con elegantes de reserva para no vectorizados código.

    Rápido. (Ver referencia).

    La expresión de plantillas que permiten de forma inteligente eliminar temporales y habilitar la evaluación diferida, cuando sea apropiado-Eigen se encarga de esto de forma automática y maneja aliasing también en la mayoría de los casos.

    Explícito de vectorización se realiza para la ESS (2 y posteriores) y conjuntos de instrucciones AltiVec, con elegantes de reserva para no vectorizados código. La expresión de plantillas que permiten realizar estas optimizaciones a nivel mundial para toda expresiones.

    Con tamaño fijo de objetos, asignación dinámica de memoria es evitado, y los lazos se desenrolla al que hace sentido.

    Para matrices grandes, se presta especial atención a la caché de-amistad.

  3. 0

    Que podría ser capaz de mejorar en la copia en caché-alineados bloques en lugar de por filas, como en el momento de la zancada de src dest va a ser una señorita ( dependiendo de si delphi es la fila de los principales o de la columna principal ).

    • (No es el problema de que uno de los dos lados de la = siempre es no alineados? Yo a pie src linealmente o el horario de verano, pero nunca ambos a la vez)
    • No, puede copiar un bloque y su incorporación dentro de la caché como Nils muestra ( suponiendo que la máquina está en tiene 256 bytes líneas de caché )
    • Ok, lo siento, entonces estaba equivocado, sí Nils respuesta es lo que estaba buscando
  4. 0

    Si la imagen no es cuadrada, no se puede hacer en el lugar. Incluso si usted trabaja en la plaza de las imágenes, la transformación no es propicio para el en el lugar de trabajo.

    Si quieres intentar hacer las cosas un poco más rápido, usted puede tratar de tomar ventaja de la fila pasos para hacer el trabajo, pero creo que lo mejor que podría hacer es leer los 4 bytes en un momento en mucho de la fuente y, a continuación, escribir en cuatro filas consecutivas en el destino. Que debe cortar algunas de sus superiores, pero yo no esperaría más de un 5% de mejora.

    • Correcto, pero tengo varios casos de uso, y podría ser directamente, por ejemplo, mediante la ampliación de la imagen a la ligera por lo que es cuadrada. Es uno de los más leves a pesar de que los escenarios de uso. Como se puede ver a continuación, la aceleración es bastante dramático (300-400%). Pero directamente, el costo sería de velocidad ya que no se puede simplemente intercambiar los bloques, pero tendría que girar a través de 4 x 90 grados, así que decidió no presionarla y tomar la copia por sentado ahora.

Dejar respuesta

Please enter your comment!
Please enter your name here