이미지를 제자리에서 90도 회전시키는 알고리즘?(추가 메모리 없음)

이미지를 제자리에서 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];
}

저는그내용옮싶습다니기고을▁▁contents의 data주위에 배열한 다음, 스위치를 전환합니다.width그리고.height멤버 변수9x20 픽셀 이미지로 시작해서 회전시키면 20x9 픽셀 이미지로 끝날 것입니다.이로 인해 이미지의 스트라이드가 변경되어 알고리즘이 매우 복잡해집니다.

이것은 도움이 될 수 있습니다: 내부 행렬 전위.

(rlbond가 언급한 바와 같이 전환 후 미러링을 수행해야 할 수도 있습니다.)

메모리에서 "잘못된 순서"로 이미지를 읽는 경우, 이미지를 회전시키는 것과 본질적으로 동일합니다.이것은 여러분이 하고 있는 일에 적합할 수도 있고 그렇지 않을 수도 있지만, 여기에는 다음이 있습니다.

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

회전 후 어떤 처리를 할지는 확실하지 않지만, 그대로 두고 다른 기능을 사용하여 원래 메모리에서 회전된 픽셀을 읽을 수 있습니다.

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

여기서 입력 매개 변수 x와 y가 원래의 치수를 스왑했습니다.

이 문제는 시간이 꽤 걸렸지만 당신이 올바른 접근법을 가지고 있다면 매우 간단합니다.

이것은 정사각형 행렬에만 적용됩니다.직사각형을 사용하려면 다른 알고리즘(트랜스포스 및 플립)을 사용해야 합니다.이 작업을 제자리에서 수행하려면 일시적으로 배열 크기를 조정해야 할 수 있습니다.

문제 단순화

다음 행렬을 생각해 보십시오.

 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가 됩니다.

모서리 회전

코너를 회전하려면 첫 번째 코너를 기준으로 모든 코너를 정의해야 합니다.

• 첫 번째 코너는.(i, j)
• 두 번째 코너는.(SIZE - j, i)
• 세 번째 코너는.(SIZE - i, SIZE - j)
• 네 번째 코너는.(j, SIZE - i)

어레이는 0 기반이므로 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;

이건 너무 모호할 수도 있고, 당신이 찾고 있는 것이 아닐 수도 있지만, 어쨌든 글을 올리겠습니다.

이미지를 픽셀의 2D 배열로 간주하는 경우 수평 반전 또는 수직 반전 여부에 따라 최상위 배열 또는 중첩 배열의 순서만 반대로 하면 됩니다.

따라서 각 픽셀 열(0->열/2)을 루프하여 스왑하거나(전체 그림이 아닌 1픽셀에 대한 임시 메모리만 필요함), 수평 반전을 위해 행을 루프하여 루프합니다.이해 하셨나요?그렇지 않을 경우 코드를 자세히 작성합니다.

진짜 대답: 아니요, 메모리를 할당하지 않고는 할 수 없습니다.

또는 큰 이미지에서 실패하는 재귀를 사용해야 합니다.

그러나 이미지 자체보다 적은 메모리를 필요로 하는 방법이 있습니다.

예를 들어, 점 A(x에서 너비, y에서 높이)를 선택하고, 점 A(x에서 너비, y에서 높이)의 새 위치를 계산하고, B를 A로 바꾸기 전에 새 위치(C)로 복사할 수 있습니다.

그러나 이 방법을 사용하려면 이미 이동된 바이트를 추적해야 합니다.(회전된 영상에서 픽셀당 1비트의 비트맵 사용)

위키백과 기사를 보면, 이것은 정사각형이 아닌 이미지에 대해서는 할 수 없다는 것을 분명히 보여줍니다: 여기 다시 링크가 있습니다: http://en.wikipedia.org/wiki/In-place_matrix_transposition

여기 자바로 된 간단한 방법이 있습니다.

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

이는 2D 매트릭스의 회전과 비슷합니다.아래 알고리즘은 2D 매트릭스를 90도 회전시킵니다.MXN에서도 작동합니다. 주어진 행렬의 전치를 취한 다음 첫 번째 열을 마지막 열로, 두 번째 열을 두 번째 열로 바꿉니다.열 대신 행을 사용할 수도 있습니다.

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

C의 2단계 솔루션인 매트릭스 90도 회전을 시도했습니다.
먼저 매트릭스를 제자리에 전치시킨 다음 콜을 맞춥니다.

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

언급URL : https://stackoverflow.com/questions/2968397/algorithm-to-rotate-an-image-90-degrees-in-place-no-extra-memory