c - voltea - Algoritmo para girar una imagen 90 grados en su lugar?(Sin memoria extra)

voltear fotos espejo iphone

Question

En una aplicación C incrustada, tengo una imagen grande que me gustaría rotar 90 grados. Actualmente uso el conocido algorithm simple para hacer esto. Sin embargo, este algoritmo me obliga a hacer otra copia de la imagen. Me gustaría evitar asignar memoria para una copia, prefiero rotarla en el lugar. Como la imagen no es cuadrada, esto es complicado. ¿Alguien sabe de un algoritmo adecuado?

Editado para agregar aclaraciones, porque la gente pregunta:

Guardo una imagen en el formato habitual:

// Images are 16 bpp
struct Image {
int width;
int height;
uint16_t * data;
};
uint16_t getPixel(Image *img, int x, int y)
{
return img->data[y * img->width + x];
}

Espero mover el contenido de la matriz de data , luego cambiar las variables de miembros de width y height . Entonces, si comienzo con una imagen de 9x20 píxeles, gírela, terminaré con una imagen de 20x9 píxeles. Esto cambia el paso de la imagen, lo que complica mucho el algoritmo.

Answer 1

Aquí está mi intento de rotación de matriz de 90 grados que es una solución de 2 pasos en C.
Primero transpone la matriz en su lugar y luego intercambia los cols.

#define ROWS 5
#define COLS 5
void print_matrix_b(int B[][COLS], int rows, int cols)
{
for (int i = 0; i <= rows; i++) {
for (int j = 0; j <=cols; j++) {
printf("%d ", B[i][j]);
}
printf("/n");
}
}
void swap_columns(int B[][COLS], int l, int r, int rows)
{
int tmp;
for (int i = 0; i <= rows; i++) {
tmp = B[i][l];
B[i][l] = B[i][r];
B[i][r] = tmp;
}
}
void matrix_2d_rotation(int B[][COLS], int rows, int cols)
{
int tmp;
// Transpose the matrix first
for (int i = 0; i <= rows; i++) {
for (int j = i; j <=cols; j++) {
tmp = B[i][j];
B[i][j] = B[j][i];
B[j][i] = tmp;
}
}
// Swap the first and last col and continue until
// the middle.
for (int i = 0; i < (cols / 2); i++)
swap_columns(B, i, cols - i, rows);
}
int _tmain(int argc, _TCHAR* argv[])
{
int B[ROWS][COLS] = {
{1, 2, 3, 4, 5},
{6, 7, 8, 9, 10},
{11, 12, 13, 14, 15},
{16, 17, 18, 19, 20},
{21, 22, 23, 24, 25}
};
matrix_2d_rotation(B, ROWS - 1, COLS - 1);
print_matrix_b(B, ROWS - 1, COLS -1);
return 0;
}

Answer 2

Aquí hay un método simple en Java,

 public static void rotateMatrix(int[][] a) {
int m =0;
for(int i=0; i<a.length; ++i) {
for(int j=m; j<a[0].length; ++j) {
int tmp = a[i][j];
a[i][j] = a[j][i];
a[j][i] = tmp;
}
m++;
}
for(int i=0; i<a.length; ++i) {
int end = a.length-1;
for(int j=0; j<a[0].length; j++) {
if(j>=end)
break;
int tmp = a[i][j];
a[i][j] = a[i][end];
a[i][end] = tmp;
end--;
}
}
}

Answer 3

Este problema me llevó bastante tiempo, pero si tienes el enfoque correcto, es muy simple.

Tenga en cuenta que esto solo funciona para una matriz cuadrada . Un rectángulo requerirá que uses el otro algoritmo (transponer y voltear). Si desea hacerlo en su lugar, es posible que necesite cambiar el tamaño temporalmente de la matriz.

Simplificando el problema

Considere la siguiente matriz:

 1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Gire 90 grados y observe solo las esquinas (números 1, 4, 16 y 13). Si tiene problemas visualizándolo, ayúdese con una nota post-it.

Ahora, consideremos el siguiente:

1 - - 2
- - - -
- - - -
4 - - 3

Gírelo 90 grados, y observe cómo los números se rotan de forma circular: 2 se convierte en 1, 3 se convierte en 2, 4 se convierte en 3, 1 se convierte en 4.

Esquinas giratorias

Para rotar esquinas, es necesario definir todas las esquinas en términos de la primera esquina:

• La primera esquina sería (i, j)
• La segunda esquina sería (SIZE - j, i)
• La tercera esquina sería (SIZE - i, SIZE - j)
• La cuarta esquina sería (j, SIZE - i)

Tenga en cuenta que las matrices están basadas en 0, por lo tanto, SIZE también tendrá que estar basado en 0. (es decir, tendrá que restar 1).

Ahora que entendiste la idea de girar esquinas, expandiremos la idea de "girar esquinas" a "cuadrantes giratorios". El mismo principio es válido.

Código

Deberá asegurarse de que no se sobrescriba ningún número. Lo que significa que tendrá que girar 4 números a la vez simultáneamente.

#include <algorithm>
#include <numeric>
#include <vector>
using std::iota;
using std::swap;
using std::vector;
// Rotates 4 numbers.
// e.g: 1, 2, 3, 4 becomes 4, 1, 2, 3
// int& means numbers are passed by reference, not copy.
void rotate4(int &a, int &b, int &c, int &d)
{
swap(a, b);
swap(b, c);
swap(c, d);
}
void rotateMatrix(vector<vector<int>>& m) {
int n = m.size();
// NOTE: i and j from 0 to n/2 is a quadrant
for (int i = 0; i < n/2; i++) {
// NOTE : here + 1 is added to make it work when n is odd
for (int j = 0; j < (n + 1)/2; j++) {
int r_i = (n - 1) - i;
int r_j = (n - 1) - j;
rotate4(
m [i] [j],
m [r_j] [i],
m [r_i] [r_j],
m [j] [r_i]
);
}
}
}
void fillMatrix(vector<vector<int>>& m) {
int offset = 0;
for (auto &i : m) {
iota(i.begin(), i.end(), offset);
offset += i.size();
}
}
// Usage:
const int size = 8;
vector<vector<int>> matrix (size, vector<int>(size));
fillMatrix(matrix);
rotateMatrix(matrix);

Impresión

Para imprimir la matriz, puede usar:

#include <algorithm>
#include <iostream>
#include <iterator>
using std::copy;
using std::cout;
using std::ostream;
using std::ostream_iterator;
using std::vector;
ostream& operator<<(ostream& os, vector<vector<int>>& m) {
for (auto const &i : m) {
copy(i.begin(), i.end(), ostream_iterator<int>(os, " "));
os << "/n";
}
return os;
}
// Usage
cout << matrix;

Answer 4

Esto es similar a la rotación de la matriz 2D. Aquí está mi algoritmo a continuación, que rota la matriz 2D 90 grados. También funciona para MX N. Tome la transposición de la matriz dada y luego cambie la primera columna con la última, la 2.ª columna con la 2.ª última columna y así sucesivamente. También puede hacer filas en lugar de columnas.

import java.io.*;
import java.util.*;
public class MatrixRotationTest
{
public static void main(String arg[])throws Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter the matrix rows:");
int r = Integer.parseInt(br.readLine());
System.out.println("Enter the matrix columns:");
int c = Integer.parseInt(br.readLine());
int[][] matrix = new int[r*c][r*c];
for(int i=0;i<r;i++)
{
System.out.println("Enter row "+(i+1));
for(int j=0;j<c;j++)
{
matrix[i][j] = Integer.parseInt(br.readLine());
}
}
matrix = reverseMatrixColumns(transformMatrix(matrix),r,c);
System.out.println("Rotated Matrix");
for(int i=0;i<c;i++)
{
for(int j=0;j<r;j++)
{
System.out.print(matrix[i][j]+" ");
}
System.out.println();
}
}
//Transform the given matrix
public static int[][] transformMatrix(int[][] matrix)throws Exception
{
for(int i=0;i<matrix.length;i++)
{
for(int j=i;j<matrix[0].length;j++)
{
int temp = matrix[i][j];
matrix[i][j] = matrix [j][i];
matrix[j][i] = temp;
}
}
}
//Swap columns
public static int[][] reverseMatrixColumns(int[][] matrix,int r,int c)
{
int i=0,j=r-1;
while(i!=r/2)
{
for(int l=0;l<c;l++)
{
int temp = matrix[l][i];
matrix[l][i] = matrix[l][j];
matrix[l][j] = temp;
}
i++;
j--;
}
return matrix;
}
}

Answer 5

Esto podría ayudar: transposición de matriz en el lugar .

(También es posible que tenga que hacer un reflejo después de la transposición, como lo menciona rlbond).

Answer 6

Esto podría ser demasiado vago, y no ser lo que estás buscando, pero voy a publicar de todos modos.

Si considera que una imagen es una matriz en 2D de píxeles, solo necesita invertir el orden de la matriz anidada o de nivel superior, según si desea voltear horizontal o verticalmente.

Entonces, recorrerá cada columna de píxeles (0-> columnas / 2), y las intercambiará (para que solo necesite memoria temporal para 1 píxel, no para toda la imagen), o recorra las filas para voltear horizontalmente ... ¿Eso hace ¿sentido? Elaborará / escribirá código si no ...

Answer 7

No estoy seguro de qué procesamiento va a hacer después de la rotación, pero puede dejarlo en blanco y usar otra función para leer el píxel girado de la memoria original.

uint16_t getPixel90(Image *img, int x, int y)
{
return img->data[(img->height - x) * img->width + y];
}

Donde los parámetros de entrada xey han cambiado la dimensión desde el original

Answer 8

Si lees la imagen de la memoria en "el orden incorrecto", es esencialmente lo mismo que rotarla. Esto puede o no ser adecuado para lo que sea que estés haciendo, pero aquí va:

image[y][x] /* assuming this is the original orientation */
image[x][original_width - y] /* rotated 90 degrees ccw */
image[original_height - x][y] /* 90 degrees cw */
image[original_height - y][original_width - x] /* 180 degrees */

Answer 9

la respuesta real: no, no se puede sin asignar memoria.

o tiene que usar recursión, que fallará con imágenes grandes.

Sin embargo, hay métodos que requieren menos memoria que la propia imagen

por ejemplo, puede tomar el punto A (x de 0 a ancho, y de 0 a alto), calcular su nueva ubicación, B, copiar B a su nueva ubicación (C) antes de reemplazarlo por A, etc.

pero, ese método requeriría hacer un seguimiento de qué bytes ya se han movido. (utilizando un mapa de bits de un bit por píxel en la imagen girada)

vea el artículo de la wikipedia, demuestra claramente que esto no se puede hacer para las imágenes no cuadradas: aquí está el enlace nuevamente: http://en.wikipedia.org/wiki/In-place_matrix_transposition