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

Cela pourrait aider : Transposition de la matrice en place .

(Il se peut que vous deviez aussi faire un peu de miroir après la transposition, comme le mentionne rlbond).

Answer 2

Si vous lisez l'image de la mémoire dans le "mauvais ordre", cela revient essentiellement à la faire tourner. Cela peut ou non convenir à ce que vous faites, mais voilà :

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 3

Je ne suis pas sûr du traitement que vous ferez après la rotation, mais vous pouvez le laisser seul et utiliser une autre fonction pour lire le pixel tourné depuis la mémoire d'origine.

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

Où les paramètres d'entrée x et y ont une dimension permutée par rapport à l'original.

Answer 4

Ce problème m'a pris pas mal de temps mais si vous avez la bonne approche, c'est très simple.

Notez que cela ne fonctionne que pour une matrice carrée . Pour un rectangle, vous devrez utiliser l'autre algorithme (transposition et retournement). Si vous voulez le faire sur place, vous devrez peut-être redimensionner temporairement le tableau.

Simplifier le problème

Considérons la matrice suivante :

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

Faites une rotation de 90 degrés et regardez uniquement les coins (numéros 1, 4, 16 et 13). Si vous avez du mal à le visualiser, aidez-vous d'un post-it.

Considérons maintenant la suivante :

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

Faites-la pivoter de 90 degrés et remarquez comment les chiffres sont tournés de manière circulaire : 2 devient 1, 3 devient 2, 4 devient 3, 1 devient 4.

Coins tournants

Pour faire pivoter les coins, il est nécessaire de définir tous les coins en fonction du premier coin :

• Le premier coin serait (i, j)
• Le deuxième coin serait (SIZE - j, i)
• Le troisième coin serait (SIZE - i, SIZE - j)
• Le quatrième angle serait (j, SIZE - i)

Notez que les tableaux sont basés sur 0, donc SIZE devra également être basé sur 0. (c'est-à-dire que vous devrez soustraire 1).

Maintenant que vous avez compris l'idée des coins tournants, nous allons étendre l'idée des "coins tournants" aux "quadrants tournants". Le même principe s'applique.

Code

Vous devrez vous assurer qu'aucun numéro n'est écrasé. Autrement dit, vous devrez faire tourner 4 numéros à la fois simultanément.

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

Impression

Pour imprimer la matrice, vous pouvez utiliser :

#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 5

La vraie réponse : non, vous ne pouvez pas sans allouer de la mémoire.

ou vous devez utiliser la récursion, ce qui échouera avec les grandes images.

Il existe cependant des méthodes qui nécessitent moins de mémoire que l'image elle-même.

Par exemple, vous pourriez prendre le point A (x de 0 à la largeur, y de 0 à la hauteur), calculer son nouvel emplacement, B, copier B à son nouvel emplacement (C) avant de le remplacer par A, etc.

mais cette méthode nécessiterait de garder la trace des octets qui ont déjà été déplacés. (en utilisant un bitmap d'un bit par pixel dans l'image tournée)

voir l'article de wikipedia, il démontre clairement que cela ne peut pas être fait pour des images non carrées : voici à nouveau le lien : http://en.wikipedia.org/wiki/In-place_matrix_transposition