Подтвердить что ты не робот

Алгоритм для поворота изображения на 90 градусов? (Нет дополнительной памяти)

Во встроенном приложении C у меня есть большое изображение, которое я хотел бы поворачивать на 90 градусов. В настоящее время я использую известный простой алгоритм для этого. Однако этот алгоритм требует от меня сделать еще одну копию изображения. Я бы хотел избежать выделения памяти для копии, я бы скорее поместил ее на место. Поскольку изображение не является квадратным, это сложно. Кто-нибудь знает подходящий алгоритм?

Отредактировано для добавления разъяснений, потому что люди спрашивают:

Я сохраняю изображение в обычном формате:

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

Я надеюсь переместить содержимое массива data, а затем поменять переменные-члены width и height. Поэтому, если я начну с изображения размером 9x20 пикселей, а затем поверните его, я получаю изображение размером 20x9 пикселей. Это изменяет шаг изображения, что усложняет алгоритм.

4b9b3361

ОТВЕТЫ

Ответ 1

Это может помочь: Транзакция на месте.

(Возможно, вам придется сделать некоторое зеркалирование после транспонирования, как упоминает rlbond).

Ответ 2

Если вы читаете изображение из памяти в "неправильном порядке", оно по существу равносильно его вращению. Это может быть или не быть подходящим для того, что вы делаете, но здесь идет:

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

Ответ 3

Не уверен, какую обработку вы будете делать после вращения, но вы можете оставить ее в покое и использовать другую функцию для чтения повернутого пикселя из исходной памяти.

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

Если входной параметр x и y имеет размер подкачки от оригинала

Ответ 4

Это может быть слишком неопределенно, а не быть тем, что вы ищете, но я все равно отправлю.

Если вы считаете, что изображение является 2-мерным массивом пикселей, вам нужно только отменить порядок верхнего или нижнего массива, в зависимости от того, хотите ли вы горизонтальное или вертикальное переключение.

Таким образом, вы либо прокручиваете каждый столбец пикселей (0- > столбцы /2), либо свопите их (так что вам нужна только временная память для 1 пикселя, а не целое изображение) или цикл через строки для горизонтального листания. Имеет ли это смысл? Будет ли разрабатывать/писать код, если нет..

Ответ 5

реальный ответ: no, u не может не выделять некоторую память.

или вы должны использовать рекурсию, которая не удастся с большими изображениями.

однако существуют методы, которые требуют меньше памяти, чем само изображение

Например, вы можете взять точку A (x от 0 до ширины, y от 0 до высоты), рассчитать новое местоположение, B, скопировать B в новое местоположение (C), прежде чем заменять его на A и т.д.

но для этого метода потребуется отслеживать, какие байты уже были перемещены. (используя растровое изображение одного бита на пиксель во вращающемся изображении)

см. статью wikipedia, она наглядно демонстрирует, что это невозможно сделать для неквадратных изображений: вот ссылка снова: http://en.wikipedia.org/wiki/In-place_matrix_transposition

Ответ 6

Вот простой способ в 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--;
        }
    }
}

Ответ 7

Эта проблема заняла у меня довольно много времени, но если у вас есть правильный подход, это очень просто.

Обратите внимание, что это работает только для квадратной матрицы. Прямоугольник потребует от вас использования другого алгоритма (транспонирование и переключение). Если вы хотите сделать это на месте, вам может понадобиться временно изменить размер массива.

Упрощение проблемы

Рассмотрим следующую матрицу:

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

Поверните на 90 градусов и посмотрите только на углы (цифры 1, 4, 16 и 13). Если у вас возникли проблемы с визуализацией, помогите себе с записью после этого.

Теперь рассмотрим следующее:

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

Поверните его на 90 градусов и обратите внимание на то, как цифры вращаются круговым образом: 2 становится 1, 3 становится 2, 4 становится 3, 1 становится 4.

Вращающиеся углы

Чтобы повернуть углы, необходимо определить все углы в терминах первого угла:

  • 1-й угол будет (i, j)
  • Второй угол будет (SIZE - j, i)
  • Третий угол будет (SIZE - i, SIZE - j)
  • Четвертый угол будет (j, SIZE - i)

Обратите внимание, что массивы основаны на 0, поэтому SIZE также должно быть основано на 0. (это означает, что вам нужно будет вычесть 1).

Теперь, когда вы поняли идею вращающихся углов, мы расширим идею "вращающихся углов" до "вращающихся квадрантов". Тот же принцип имеет место.

Код

Вам нужно будет убедиться, что номер не перезаписан. Значит, вам нужно будет одновременно поворачивать 4 числа.

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

Печать

Чтобы напечатать матрицу, которую вы можете использовать:

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

Ответ 8

Это похоже на вращение 2D-матрицы. Вот мой алгоритм, ниже которого вращается 2D-матрица на 90 градусов. Он также работает для M X N. Возьмите транспонирование данной матрицы, а затем замените 1-й столбец последним, 2-м столбцом со вторым последним столбцом и так далее. Вы также можете делать строки вместо столбцов.

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

Ответ 9

Вот моя попытка вращения матрицы на 90 градусов, которая является 2-ступенчатым раствором в C.
Сначала перенесите матрицу на место и затем поменяйте 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;
}