c - transpuesta - Transponer una matriz 2D

multiplicacion de matrices

Question

¿Cómo transpone eficientemente una matriz? ¿Hay bibliotecas para esto o qué algoritmo usarías?

P.ej:

short src[W*H] = {
{1,2,3},
{4,5,6}
};
short dest[W*H];
rotate_90_clockwise(dest,src,W,H); //<-- magic in here, no need for in-place
//dest is now:
{
{4, 1},
{5, 2},
{6, 3}
};

(En mi caso específico, su matriz src es datos de imágenes en bruto, y el destino es un framebuffer, y estoy incrustado en ARM en una cadena de herramientas que no admite el ensamblaje)

Answer 1

Hay bibliotecas para esto, en algunos casos. Y, notablemente, hay trucos que puede jugar con datos vectorizados (por ejemplo, cuatro elementos de 32 bits en un vector de 128 bits, pero esto también se aplica a cuatro bytes de 8 bits en un registro de 32 bits) para ir más rápido que el individuo acceso a los elementos.

Para una transposición, la idea estándar es que utilice instrucciones "shuffle", que le permiten crear un nuevo vector de datos a partir de dos vectores existentes, en cualquier orden. Usted trabaja con bloques 4x4 de la matriz de entrada. Entonces, comenzando, tienes:

v0 = 1 2 3 4
v1 = 5 6 7 8
v2 = 9 A B C
v3 = D E F 0

Luego, aplique instrucciones de mezcla a los primeros dos vectores (entrelazando sus elementos impares, A0B0 C0D0 -> ABCD, e intercalando sus elementos pares, 0A0B 0C0D -> ABCD), y a los dos últimos, para crear un nuevo conjunto de vectores con cada bloque 2x2 transpuesto:

1 5 3 7
2 6 4 8
9 D B F
A E C 0

Finalmente, aplica instrucciones de mezcla al par impar y al par par (combinando sus primeros pares de elementos, AB00 CD00 -> ABCD, y sus últimos pares, 00AB 00CD -> ABCD), para obtener:

1 5 9 D
2 6 A E
3 7 B F
4 8 C 0

Y allí, ¡16 elementos transpuestos en ocho instrucciones!

Ahora, para bytes de 8 bits en registros de 32 bits, ARM no tiene exactamente instrucciones de mezcla, pero puede sintetizar lo que necesita con turnos y una instrucción SEL (seleccionar), y el segundo conjunto de combinaciones que puede hacer en una instrucción con las instrucciones PKHBT (paquete media palabra inferior superior) y PKHTB (paquete media palabra superior inferior).

Finalmente, si está usando un procesador ARM grande con vectores de NEON, puede hacer algo como esto con vectores de 16 elementos en bloques de 16x16.

Answer 2

Solo una copia simple para temp y copy-back, transposición sobre la marcha, utilizando el puntero-paso para evitar el multiplicar en el cálculo de la dirección, y el ciclo interno desenrollado:

char temp[W*H];
char* ptemp = temp;
memcpy(temp, array, sizeof(char)*W*H);
for (i = 0; i < H; i++){
char* parray = &array[i];
for (j = 0; j+8 <= W; j += 8, ptemp += 8){
*parray = ptemp[0]; parray += H;
*parray = ptemp[1]; parray += H;
*parray = ptemp[2]; parray += H;
*parray = ptemp[3]; parray += H;
*parray = ptemp[4]; parray += H;
*parray = ptemp[5]; parray += H;
*parray = ptemp[6]; parray += H;
*parray = ptemp[7]; parray += H;
}
for (; j < W; j++, parray += H){
*parray = *ptemp++;
}
}

No sé cómo evitar el problema de la ubicación del caché debido a la naturaleza del problema.

Answer 3

Una solución muy simple que funciona en O (1) es guardar un booleano adicional para la matriz, indicando si está ''transpuesta'' o no. Luego, el acceso a la matriz se realizará de acuerdo con este booleano (fila / col o col / row).

Por supuesto, impedirá la utilización de su caché.

Por lo tanto, si tiene muchas operaciones de transposición y pocas "travesías completas" (que, por cierto, también podrían reordenarse de acuerdo con el valor del booleano), esta es su mejor opción.

Answer 4

Wikipedia tiene un artículo completo sobre la transposición de matrices in situ. Para las matrices no cuadradas, es un problema no trivial, bastante interesante (si se usa menos de O (N x M) memoria, eso es). El artículo tiene enlaces a bastantes documentos con algoritmos, así como algunos códigos fuente.

Sin embargo, ten cuidado, como dije en un comentario a tu pregunta, tu demostración no es de una transposición estándar, para la cual se escribirán todos los algoritmos.

(Una función de transposición estándar dará este resultado para sus datos de ejemplo :)

{
{1, 4},
{2, 5},
{3, 6}
};

Si solo hace esto para mostrar una imagen en una pantalla, es mejor que solo haga la transposición mientras copia la imagen en el búfer posterior, en lugar de transponerla en el lugar y luego hacer blitting.

Answer 5

• Si la matriz es cuadrada o si no está buscando una transposición en el lugar, es realmente fácil:

Básicamente itera en líneas e intercambia cada elemento con elementos de columna coincidentes. Obtiene el elemento correspondiente intercambiando índices de fila y columna. Cuando haya tratado todas las columnas, la transposición habrá finalizado. También puede ir al revés e iterar en columnas.

Si desea aumentar el rendimiento, puede copiar una línea completa en una matriz temporal y la columna de coincidencia completa en otra, luego cópiela de nuevo. Debería ser un poco más rápido (incluso si esta estrategia implica una asignación de variable más) si utiliza una memoria para transferencias que involucran elementos más internos.

• Si la matriz no es cuadrada (como en su ejemplo) es realmente complicado hacerlo en el lugar. Como la transposición no cambia las necesidades de memoria, todavía parece posible hacerlo en el lugar, pero si lo hace descuidadamente terminará sobrescribiendo elementos de otra línea o columna.

Si la memoria no es un cuello de botella recomiendo usar una matriz temporal. Es realmente más fácil y probablemente sea más rápido de todos modos.

• El mejor método es no transponer en absoluto, sino simplemente establecer una bandera en algún lugar indicando si accede a los datos fila primero o columna primero. En la mayoría de los casos, los algoritmos que necesitan transposición se pueden reescribir para acceder a una matriz no transpuesta como si fuera. Para lograr esto solo tienes que volver a escribir algunas operaciones básicas como productos de matriz para aceptar matrices con una orientación u otra.

Pero en algunos casos, entiendo que esto no será posible, normalmente si se están preparando datos para acceder a algún hardware o biblioteca existente.

Answer 6

La solución más eficiente aquí es rotar los datos mientras se copian desde la RAM al framebuffer. Girar la fuente en la RAM y luego copiar el resultado al framebuffer será, en el mejor de los casos, la mitad de la velocidad de la versión de copiar y girar. Entonces, la pregunta es, ¿es más eficiente leer de forma secuencial y escribir aleatoriamente o leer al azar y escribir secuencialmente? En código, esta sería la elección entre:

// read sequential
src = { image data }
dest = framebuffer
for (y = 0 ; y < H ; ++y)
{
for (x = 0 ; x < W ; ++x)
{
pixel = *src++
dest [y,x] = pixel
}
}

o:

// write sequential
src = { image data }
dest = framebuffer
for (x = 0 ; x < W ; ++x)
{
for (y = 0 ; y < H ; ++y)
{
pixel = src [x,y]
*dest++ = pixel
}
}

La respuesta a esto solo puede determinarse perfilando el código.

Ahora bien, puede ser que tenga una GPU, en cuyo caso podría hacer rotaciones y será mucho más eficiente dejar que la GPU haga la rotación al ajustar la imagen a la pantalla.