In einer eingebetteten C-App habe ich ein großes Bild, das ich um 90 Grad drehen möchte. Aktuell verwende ich das altbekannte simple Algorithmus um dies zu tun. Dieser Algorithmus erfordert jedoch, dass ich eine weitere Kopie des Bildes anfertige. Ich möchte vermeiden, Speicher für eine Kopie zuzuweisen, ich würde es lieber an Ort und Stelle rotieren. Da das Bild nicht quadratisch ist, ist dies schwierig. Kennt jemand einen geeigneten Algorithmus?

Bearbeitet, um eine Klarstellung hinzuzufügen, weil die Leute fragen:

Ich speichere ein Bild im üblichen Format:

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

Ich hoffe, den Inhalt der zu verschieben data Array herum, dann tauschen Sie über die width und height Mitgliedsvariablen. Wenn ich also mit einem 9×20-Pixel-Bild beginne und es dann drehe, erhalte ich am Ende ein 20×9-Pixel-Bild. Dadurch ändert sich der Schritt des Bildes, was den Algorithmus sehr verkompliziert.

Das könnte helfen: In-Place-Matrixtransposition.

(Möglicherweise müssen Sie nach der Transposition auch etwas spiegeln, wie rlbond erwähnt).

Wenn Sie das Bild aus dem Speicher in “der falschen Reihenfolge” lesen, ist es im Wesentlichen dasselbe wie es zu drehen. Dies kann für das, was Sie tun, geeignet sein oder auch nicht, aber hier ist Folgendes:

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 */

Sie sind sich nicht sicher, welche Verarbeitung Sie nach der Drehung durchführen werden, aber Sie können es in Ruhe lassen und eine andere Funktion verwenden, um gedrehte Pixel aus dem ursprünglichen Speicher zu lesen.

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

Wobei die Eingabeparameter x und y die Dimension vom Original vertauscht haben

Dieses Problem hat mich einige Zeit gekostet, aber wenn Sie den richtigen Ansatz haben, ist es sehr einfach.

Beachten Sie, dass dies nur für eine quadratische Matrix funktioniert. Bei einem Rechteck müssen Sie den anderen Algorithmus verwenden (Transponieren und Spiegeln). Wenn Sie dies an Ort und Stelle tun möchten, müssen Sie möglicherweise die Größe des Arrays vorübergehend ändern.

Vereinfachung des Problems

Betrachten Sie die folgende Matrix:

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

Drehen Sie um 90 Grad und schauen Sie nur auf die Ecken (Nummern 1, 4, 16 und 13). Wenn Sie Probleme haben, es zu visualisieren, helfen Sie sich mit einem Post-it-Zettel.

Betrachten wir nun das Folgende:

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

Drehen Sie es um 90 Grad und beobachten Sie, wie die Zahlen kreisförmig gedreht werden: 2 wird 1, 3 wird 2, 4 wird 3, 1 wird 4.

Drehende Ecken

Um Ecken zu drehen, müssen alle Ecken in Bezug auf die erste Ecke definiert werden:

• 1. Ecke wäre (i, j)
• 2. Ecke wäre (SIZE - j, i)
• 3. Ecke wäre (SIZE - i, SIZE - j)
• 4. Ecke wäre (j, SIZE - i)

Beachten Sie, dass Arrays daher 0-basiert sind SIZE muss ebenfalls 0-basiert sein. (das heißt, Sie müssen 1 subtrahieren).

Nachdem Sie nun die Idee der rotierenden Ecken verstanden haben, erweitern wir die Idee der “rotierenden Ecken” auf “rotierende Quadranten”. Es gilt das gleiche Prinzip.

Code

Sie müssen sicherstellen, dass keine Nummer überschrieben wird. Das heißt, Sie müssen 4 Zahlen gleichzeitig drehen.

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

Drucken

Zum Drucken der Matrix können Sie verwenden:

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

Das ist vielleicht zu vage und nicht das, wonach Sie suchen, aber ich werde trotzdem posten.

Wenn Sie ein Bild als 2D-Array von Pixeln betrachten, müssen Sie nur die Reihenfolge des obersten oder des verschachtelten Arrays umkehren, je nachdem, ob Sie horizontal oder vertikal spiegeln möchten.

Sie würden also entweder jede Pixelspalte durchlaufen (0 -> Spalten / 2) und sie austauschen (Sie benötigen also nur einen temporären Speicher für 1 Pixel, nicht das gesamte Bild) oder Zeilen zum horizontalen Spiegeln durchlaufen Sinn? Wird Code ausarbeiten / schreiben, wenn nicht ..

Die eigentliche Antwort: Nein, das geht nicht, ohne etwas Speicher zuzuweisen.

oder Sie müssen Rekursion verwenden, was bei großen Bildern fehlschlägt.

Es gibt jedoch Methoden, die weniger Speicher benötigen als das Bild selbst

Sie könnten beispielsweise Punkt A (x von 0 bis Breite, y von 0 bis Höhe) nehmen, seine neue Position berechnen, B, B an seine neue Position (C) kopieren, bevor Sie ihn durch A ersetzen, usw.

aber diese Methode würde erfordern, zu verfolgen, welche Bytes bereits verschoben wurden. (unter Verwendung einer Bitmap von einem Bit pro Pixel im gedrehten Bild)

Siehe den Wikipedia-Artikel. Er zeigt deutlich, dass dies für nicht quadratische Bilder nicht möglich ist: Hier ist noch einmal der Link: http://en.wikipedia.org/wiki/In-place_matrix_transposition

Hier ist eine einfache Methode in 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--;
        }
    }
}