Algorithme pour faire pivoter une image de 90 degrés sur place ? (Pas de mémoire supplémentaire)

Question

Dans une application C intégrée, j'ai une grande image que je voudrais faire pivoter de 90 degrés. Actuellement, j'utilise la méthode simple bien connue algorithme pour le faire. Cependant, cet algorithme m'oblige à faire une autre copie de l'image. J'aimerais éviter d'allouer de la mémoire pour une copie, je préfère faire la rotation sur place. Comme l'image n'est pas carrée, c'est délicat. Quelqu'un connaît-il un algorithme approprié ?

Modifié pour ajouter une clarification, parce que les gens demandent :

Je stocke une image dans le format habituel :

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

J'espère pouvoir déplacer le contenu de la section data autour, puis échangez le width et height variables membres. Ainsi, si je commence avec une image de 9x20 pixels, puis que je la fais pivoter, je me retrouverai avec une image de 20x9 pixels. Cela change le pas de l'image, ce qui complique beaucoup l'algorithme.

Answer 1

Voici une méthode 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 2

C'est peut-être trop vague, et ce n'est pas ce que vous recherchez, mais je vais quand même le poster.

Si vous considérez une image comme un tableau de pixels à deux dimensions, il vous suffit d'inverser l'ordre du tableau supérieur ou du tableau imbriqué, selon que vous souhaitez un retournement horizontal ou vertical

Ainsi, vous pouvez soit boucler à travers chaque colonne de pixels (0->colonnes/2), et les échanger (de sorte que vous n'avez besoin de mémoire temporaire que pour un pixel, et non pour l'ensemble de l'image), soit boucler à travers les rangées pour un retournement horizontal Est-ce que cela a du sens ? Si ce n'est pas le cas, j'élaborerai / écrirai du code

Answer 3

Ceci est similaire à la rotation d'une matrice 2D. Voici mon algorithme ci-dessous qui fait tourner une matrice 2D de 90 degrés. Il fonctionne également pour M X N. Prenez la transposition de la matrice donnée, puis échangez la première colonne avec la dernière, la deuxième colonne avec l'avant-dernière colonne et ainsi de suite. Vous pouvez également utiliser des lignes au lieu de colonnes.

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 4

Voici ma tentative de rotation de 90 degrés de la matrice qui est une solution en 2 étapes en C.
Transposez d'abord la matrice en place, puis échangez les colonnes.

#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;
}