C语言 将图像原地旋转 90 度的算法？（没有额外的内存）
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2968397/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Algorithm to rotate an image 90 degrees in place? (No extra memory)
提问by user9876
In an embedded C app, I have a large image that I'd like to rotate by 90 degrees. Currently I use the well-known simple algorithmto do this. However, this algorithm requires me to make another copy of the image. I'd like to avoid allocating memory for a copy, I'd rather rotate it in-place. Since the image isn't square, this is tricky. Does anyone know of a suitable algorithm?
在嵌入式 C 应用程序中，我有一个想要旋转 90 度的大图像。目前我使用众所周知的简单算法来做到这一点。但是，此算法要求我制作另一个图像副本。我想避免为副本分配内存，我宁愿就地旋转它。由于图像不是方形的，这很棘手。有谁知道合适的算法？
Edited to add clarification, because people are asking:
编辑添加澄清，因为人们问：
I store an image in the usual 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];
}
I'm hoping to move the contents of the dataarray around, then swap over the widthand heightmember variables. So if I start with a 9x20 pixel image, then rotate it, I'll end up with a 20x9 pixel image. This changes the stride of the image, which complicates the algorithm a lot.
我希望移动内容data围绕阵列，然后交换在width和height成员变量。所以如果我从一个 9x20 像素的图像开始，然后旋转它，我最终会得到一个 20x9 像素的图像。这改变了图像的步幅，使算法复杂化了很多。
采纳答案by user9876
This might help: In-place matrix transposition.
这可能有帮助：就地矩阵转置。
(You might also have to do some mirroring after the transposition, as rlbond mentions).
（正如 rlbond 所提到的，您可能还需要在换位后进行一些镜像）。
回答by Matti Virkkunen
If you read the image from memory in "the wrong order", it's essentially the same as rotating it. This may or may not be suitable for whatever you're doing, but here goes:
如果你以“错误的顺序”从内存中读取图像，它本质上与旋转它是一样的。这可能适合也可能不适合您正在做的任何事情，但这里有：
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 */
回答by sjchoi
Not sure what processing you will do after the rotation, but you can leave it alone and use another function to read rotated pixel from the original memory.
不确定旋转后将进行什么处理，但您可以不理会它并使用另一个函数从原始内存中读取旋转像素。
uint16_t getPixel90(Image *img, int x, int y)
{
return img->data[(img->height - x) * img->width + y];
}
Where input parameter x and y has swapped dimension from original
其中输入参数 x 和 y 已从原始尺寸交换
回答by Pizzaiola Gorgonzola
the real answer: no, u can't without allocating some memory.
真正的答案：不，你不能不分配一些内存。
or you have to use recursion, which will fail with large images.
或者您必须使用递归，这将因大图像而失败。
however there are methods that require less memory than the image itself
但是有些方法需要的内存比图像本身少
for example, you could take point A (x from 0 to width, y from 0 to height), calculate it's new location, B, copy B to it's new location (C) before replacing it with A, etc..
例如，您可以取点 A（x 从 0 到宽度，y 从 0 到高度），计算它的新位置 B，将 B 复制到新位置 (C)，然后再将其替换为 A，等等。
but, that method would require to keep track of what bytes have already been moved. (using a bitmap of one bit per pixel in the rotated image)
但是，该方法需要跟踪已经移动了哪些字节。（使用旋转图像中每像素一位的位图）
see the wikipedia article, it clearly demonstrates that this cannot be done for non square images: here is the link again: http://en.wikipedia.org/wiki/In-place_matrix_transposition
请参阅维基百科文章，它清楚地表明对于非方形图像无法做到这一点：这里再次提供链接：http: //en.wikipedia.org/wiki/In-place_matrix_transposition
回答by kakaly
Here is a simple method in java,
这是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--;
}
}
}
回答by arboreal84
This problem took me quite some time but if you have the right approach it is very simple.
这个问题花了我很长时间，但如果你有正确的方法，它很简单。
Note this only works for a square matrix. A rectangle will require you to use the other algorithm (transpose and flip). If you want to do it in place, that may need you to temporarily resize the array.
请注意，这仅适用于方阵。矩形将要求您使用其他算法（转置和翻转）。如果你想就地做，那可能需要你临时调整数组的大小。
Simplifying the problem
简化问题
Consider the following matrix:
考虑以下矩阵：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Rotate 90 degrees, and look only at the corners (numbers 1, 4, 16 and 13). If you have problems visualizing it, help yourself with a post-it note.
旋转 90 度，只看角落（数字 1、4、16 和 13）。如果您在可视化时遇到问题，请使用便利贴来帮助自己。
Now, let's consider the following one:
现在，让我们考虑以下问题：
1 - - 2
- - - -
- - - -
4 - - 3
Rotate it 90 degrees, and notice how the numbers get rotated in a circular manner: 2 becomes 1, 3 becomes 2, 4 becomes 3, 1 becomes 4.
将其旋转 90 度，并注意数字如何以循环方式旋转：2 变为 1，3 变为 2，4 变为 3，1 变为 4。
Rotating corners
旋转角
In order to rotate corners, it is necessary to define all corners in terms of the first corner:
为了旋转角点，需要根据第一个角点定义所有角点：
- 1st corner would be
(i, j) - 2nd corner would be
(SIZE - j, i) - 3rd corner would be
(SIZE - i, SIZE - j) - 4th corner would be
(j, SIZE - i)
- 第一个角落是
(i, j) - 第二个角落将是
(SIZE - j, i) - 第三个角落将是
(SIZE - i, SIZE - j) - 第 4 个角是
(j, SIZE - i)
Note that arrays are 0 based, therefore SIZEwill need to be 0 based as well.(meaning, you will need to subtract 1).
请注意，数组是基于 0 的，因此SIZE也需要基于 0。（意思是，您需要减去 1）。
Now that you understood the idea of rotating corners, we will expand the idea of "rotating corners" to "rotating quadrants". The same principle holds.
现在您了解了旋转角的概念，我们将把“旋转角”的概念扩展为“旋转象限”。同样的原则成立。
Code
代码
You will need to make sure no number if overwritten. Meaning, you will need to rotate 4 numbers at a time simultaneously.
如果被覆盖，您将需要确保没有数字。这意味着，您需要同时旋转 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);
Printing
印刷
To print the matrix you can use:
要打印矩阵，您可以使用：
#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;
回答by Jeriko
This might be too vague, and not be what you're looking for, but I'm gonna post anyway.
这可能太模糊了，不是你要找的，但我还是要发帖。
If you consider an image to be a 2d array of pixels, you only need to reverse the order of either the top-level or nested array, depending on whether you want horizontal or vertical flipping..
如果你认为一个图像是一个二维像素数组，你只需要颠倒顶级或嵌套数组的顺序，这取决于你是想要水平翻转还是垂直翻转。
So you would either loop through each pixel column (0->columns/2), and swap them (so you only need temp memory for 1 pixel, not the whole picture), or loop through rows for horizontal flipping.. Does that make sense? Will elaborate / write code if not..
所以你要么遍历每个像素列（0->columns/2），然后交换它们（所以你只需要 1 个像素的临时内存，而不是整个图片），或者遍历行以进行水平翻转。感觉？如果没有，将详细说明/编写代码。
回答by Akshay
This is similar to rotation of 2D matrix. Here is my algorithm below which rotates 2D matrix by 90 degrees. It also works for M X N. Take the transpose of the given matrix and then swap 1st column with last, 2nd column with 2nd last column and so on. You can also do with rows instead of columns.
这类似于二维矩阵的旋转。下面是我的算法，它将 2D 矩阵旋转 90 度。它也适用于 MX N。取给定矩阵的转置，然后将第一列与最后一列交换，第二列与最后一列交换，依此类推。您还可以使用行而不是列。
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;
}
}
回答by user1596193
Here is my attempt for matrix 90 deg rotation which is a 2 step solution in C.
First transpose the matrix in place and then swap the cols.
这是我对矩阵 90 度旋转的尝试，这是 C 中的 2 步解决方案。
首先将矩阵转置到位，然后交换列。
#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;
}
