Algoritmo per ruotare un’immagine di 90 gradi in posizione? (Nessuna memoria extra)

In un’applicazione C incorporata, ho un’immagine grande che vorrei ruotare di 90 gradi. Attualmente uso il noto algoritmo semplice per farlo. Tuttavia, questo algoritmo mi richiede di fare un’altra copia dell’immagine. Vorrei evitare di allocare memoria per una copia, preferirei ruotarlo sul posto. Poiché l’immagine non è quadrata, è difficile. Qualcuno sa di un algoritmo adatto?

Modificato per aggiungere chiarimenti, perché le persone chiedono:

Conservo un’immagine nel solito formato:

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

Spero di spostare il contenuto dell’array di data , quindi scambiare le variabili membro di width e height . Quindi se inizio con un’immagine di 9×20 pixel, quindi ruotala, finirò con un’immagine di 20×9 pixel. Questo cambia il passo dell’immagine, che complica molto l’algoritmo.

Questo potrebbe aiutare: trasposizione della matrice sul posto .

(Potrebbe anche essere necessario fare del mirroring dopo la trasposizione, come menziona rlbond).

Se leggi l’immagine dalla memoria in “l’ordine sbagliato”, è essenzialmente la stessa di rotazione. Questo può o non può essere adatto per qualsiasi cosa tu stia facendo, ma qui 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 */ 

Non sai quale elaborazione farai dopo la rotazione, ma puoi lasciarla da sola e usare un’altra funzione per leggere i pixel ruotati dalla memoria originale.

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

Dove i parametri di input x e y hanno invertito la dimensione dall’originale

la vera risposta: no, non puoi, senza allocare un po ‘di memoria.

oppure devi usare la ricorsione, che fallirà con immagini di grandi dimensioni.

tuttavia ci sono metodi che richiedono meno memoria dell’immagine stessa

per esempio, puoi prendere il punto A (x da 0 a larghezza, y da 0 a altezza), calcolare la sua nuova posizione, B, copiare B nella sua nuova posizione (C) prima di sostituirlo con A, ecc.

ma, quel metodo richiederebbe di tenere traccia di quali byte sono già stati spostati. (usando una bitmap di un bit per pixel nell’immagine ruotata)

guarda l’articolo di wikipedia, dimostra chiaramente che questo non può essere fatto per le immagini non quadrate: ecco di nuovo il collegamento: http://en.wikipedia.org/wiki/In-place_matrix_transposition

Questo potrebbe essere troppo vago, e non essere quello che stai cercando, ma inserirò comunque.

Se consideri un’immagine come una matrice di pixel 2d, devi solo invertire l’ordine della matrice di livello superiore o nidificata, a seconda che tu voglia lanciare orizzontalmente o verticalmente ..

In questo modo puoi eseguire il ciclo di ogni colonna di pixel (0-> colonne / 2) e scambiarli (quindi hai bisogno solo di memoria temporanea per 1 pixel, non dell’intera immagine) o di scorrere le righe per sfogliare orizzontalmente. senso? Elaborare / scrivere codice se non ..

Ecco un metodo semplice in Java,

  public static void rotateMatrix(int[][] a) { int m =0; for(int i=0; i=end) break; int tmp = a[i][j]; a[i][j] = a[i][end]; a[i][end] = tmp; end--; } } } 

Questo problema mi ha richiesto un po ‘di tempo ma se hai il giusto approccio è molto semplice.

Nota questo funziona solo per una matrice quadrata . Un rettangolo richiederà l’utilizzo dell’altro algoritmo (trasporre e capovolgere). Se si desidera eseguirlo, potrebbe essere necessario ridimensionare temporaneamente l’array.

Semplificare il problema

Considera la seguente matrice:

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

Ruota di 90 gradi e osserva solo gli angoli (numeri 1, 4, 16 e 13). Se hai problemi a visualizzarlo, prenditi una nota post-it.

Ora, consideriamo il seguente:

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

Ruota di 90 gradi e nota come i numeri vengono ruotati in modo circolare: 2 diventa 1, 3 diventa 2, 4 diventa 3, 1 diventa 4.

Angoli rotanti

Per ruotare gli angoli, è necessario definire tutti gli angoli in base alla prima curva:

  • Il primo angolo sarebbe (i, j)
  • Il secondo angolo sarebbe (SIZE - j, i)
  • Il terzo angolo sarebbe (SIZE - i, SIZE - j)
  • Il quarto angolo sarebbe (j, SIZE - i)

Si noti che gli array sono basati su 0, pertanto SIZE dovrà essere anch’esso basato su 0. (nel senso, sarà necessario sottrarre 1).

Ora che hai capito l’idea di ruotare gli angoli, estenderemo l’idea di “angoli rotanti” a “quadranti rotanti”. Lo stesso principio vale.

Codice

È necessario assicurarsi che nessun numero venga sovrascritto. Significato, dovrai ruotare simultaneamente 4 numeri alla volta.

 #include  #include  #include  using std::iota; using std::swap; using std::vector; // Rotates 4 numbers. // eg: 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>& 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>& m) { int offset = 0; for (auto &i : m) { iota(i.begin(), i.end(), offset); offset += i.size(); } } // Usage: const int size = 8; vector> matrix (size, vector(size)); fillMatrix(matrix); rotateMatrix(matrix); 

Stampa

Per stampare la matrice puoi usare:

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

Questo è simile alla rotazione della matrice 2D. Ecco il mio algoritmo sotto il quale ruota la matrice 2D di 90 gradi. Funziona anche per MX N. Prendi la trasposizione della matrice data e poi scambia la 1a colonna con l’ultima, 2a colonna con la 2a ultima colonna e così via. Puoi anche fare con le righe anziché le colonne.

 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 

Ecco il mio tentativo di rotazione matrice a 90 gradi che è una soluzione a 2 passaggi in C.
Prima trasporre la matrice in posizione e quindi scambiare i 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; }