将图像旋转90度的算法？(没有额外的记忆)

Question

在嵌入式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像素的图像.这改变了图像的步幅,这使算法复杂化很多.

Answer 1

这可能有所帮助:就地矩阵转置.

(你可能还需要在换位后做一些镜像,正如rlbond提到的那样).

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

Answer 3

不确定在旋转后你将做什么处理,但你可以不管它并使用另一个函数从原始内存中读取旋转像素.

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

输入参数x和y已从原始交换尺寸

Answer 4

这个问题花了我相当长的时间，但如果你有正确的方法，它会非常简单。

请注意，这仅适用于方阵。矩形将要求您使用其他算法（转置和翻转）。如果您想就地执行此操作，可能需要您暂时调整数组的大小。

简化问题

考虑以下矩阵：

 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 开始的，因此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;