将二维数组中的像素数据旋转 x 度（伪代码或 Python3）

Question

对于一个学校项目，我们的信息学老师希望我们重新发明轮子。我们给出了一个数组，表示图像的像素，其中包含在另一个脚本中定义的颜色对象。它们代表一组 4 个整数，红色、绿色、蓝色和 Alpha 值的值为 0 到 255。现在我们必须对该数组进行图像处理的标准操作。我们被明确告知，要使用 Internet 和问题站点（例如堆栈溢出）作为参考。

对此我没有办法：如何将给定的颜色对象数组转换为另一个表示相同图像但旋转 x 度（扩展）的数组。新的 Colours/Pixels 降落在哪里，如何计算？如何计算这个数组的新大小？有没有什么通俗易懂的pdf，我可以通过，理解，如何，f.e。 PIL image.rotate(expand=true) 算法在理论上有效，或者任何人都可以想出一个解释如何做到这一点？我会很感激伪代码或 python 3，因为它是我理解的唯一编程语言。

此类数组的简短示例：

BLUE  = Colour(0  ,0  ,255,255)
BLACK = Colour(0  ,0  ,0  ,255)
WHITE = Colour(255,255,255,255)
Array = [ [BLUE , BLACK, WHITE, BLUE ],
          [BLACK, BLACK, BLUE , WHITE],
          [WHITE, WHITE, BLUE , WHITE] ]

编辑：要访问颜色值，有方法 getred()、getgreen()、getblue() 和 gettuple() - 我已经实现了 "painters"-算法，意味着可以通过调用 merge(bottomColour, topColour) 合并颜色 returns 结果颜色，如果一个颜色放在另一个颜色之上。可以在这里找到理论： Determine RGBA colour received by combining two colours

我们不允许使用 numpy 或任何其他模块或库。没有Colour/Pixel的地方应该是'None'.

非常感谢！

Answer 1

关于摆放位置，尽量做背部改造。让每个结果像素方块由其中心点表示。对于每个这样的点，让我们找到源点所在的位置。找到那个源点属于哪个像素方块 - 瞧 - 你有源方块和源颜色集。

注意，使用直线顺序，从源到结果，如果你想得到没有空洞或重叠的图片，你必须找到结果转换像素的区域。这是非常复杂的。另一方面，反向任务可以快速简单地完成。

不要忘记计算一次正弦和余弦，并在每次点计算时使用它们。

Answer 2

我们需要将旋转图像中的每个坐标映射到原始图像中的相应坐标。

假设旋转 (a, b) 并逆时针旋转 θ 度：

其中 (x, y) 是原始图像，(x', y') 是旋转后的图像。

简单技巧：最近邻

当使用计算出的坐标对像素数据进行采样时，我们可以简单地将它们四舍五入到最接近的整数（即最近的像素）。这给出了以下结果：

乍一看这似乎还不错，但网页重新缩放+图像压缩模糊了边缘。放大视图显示生成的图像具有令人讨厌的锯齿状边缘（混叠）：

过滤：双线性逼近

为了改进这一点，我们需要认识到旋转后的“像素”区域实际上覆盖了原始图像中的多个像素：

然后我们可以计算平均像素颜色作为每个覆盖的原始像素的贡献的总和，这些原始像素由它们的相对面积加权。为了方便起见，我们称其为“各向异性”过滤（不是该术语的确切含义，而是我能想到的最接近的含义）。

然而，这些区域将很难准确计算。所以我们可以通过应用一个近似值来“欺骗”一点，其中旋转的样本区域（红色）与网格线对齐：

这使得面积更容易计算。我们将使用一阶线性平均法——“双线性”过滤。

C# 代码示例：

Transform trn = new Transform(a, cx, cy); // inverse rotation transform to original image space

for (int y = 0; y < h; y++)
{
    for (int x = 0; x < w; x++)
    {
        Vector v = trn.Get((float)x, (float)y);
        int i = (int)Math.Floor(v.x),
            j = (int)Math.Floor(v.y);
        float s = v.x - (float)i,
              t = v.y - (float)j;
                
        RGB c = RGB.Black, u; float z, r = 0.0f;
        if ((u = src.getPixel(i, j)).Valid)
        {
            z = (1 - s) * (1 - t); // area of overlap in top-left covered pixel
            c += u * z; r += z; // add to total color and total area
        }
        if ((u = src.getPixel(i + 1, j)).Valid)
        {
            z = s * (1 - t);
            c += u * z; r += z;
        }
        if ((u = src.getPixel(i, j + 1)).Valid)
        {
            z = (1 - s) * t;
            c += u * z; r += z;
        }
        if ((u = src.getPixel(i + 1, j + 1)).Valid)
        {
            z = s * t;
            c += u * z; r += z;
        }
        
        if (r > 0.0f)
            dst.setPixel(x, y, c * (1.0f / r)); // normalize the sum by total area
    }
}

放大结果：

比朴素的最近邻法好很多！

强迫症警报！

出于好奇，我实现了前面提到的完整的“各向异性”方法。花费的时间比应该的长，而且效率不高（使用 Sutherland-Hodgman 裁剪来计算旋转像素区域和每个网格像素之间的交叉区域）。计算时间达到顶峰 - 大约 7 秒，而双线性方法不到 0.5 秒。最后的结果？根本不值得付出努力！

（L：双线性，R：各向异性）

代码（我的实现很垃圾，懒得看，真的）：

private static Vector[][] clipboxes = new Vector[][] {
    new Vector[] { new Vector(-1f,-1f), new Vector(0f,-1f), new Vector(0f,0f), new Vector(-1f,0f)},
    new Vector[] { new Vector(0f,-1f), new Vector(1f,-1f), new Vector(1f,0f), new Vector(0f,0f)},
    new Vector[] { new Vector(1f,-1f), new Vector(2f,-1f), new Vector(2f,0f), new Vector(1f,0f)},
    new Vector[] { new Vector(-1f,0f), new Vector(0f,0f), new Vector(0f,1f), new Vector(-1f,1f)},
    new Vector[] { new Vector(0f,0f), new Vector(1f,0f), new Vector(1f,1f), new Vector(0f,1f)},
    new Vector[] { new Vector(1f,0f), new Vector(2f,0f), new Vector(2f,1f), new Vector(1f,1f)},
    new Vector[] { new Vector(-1f,1f), new Vector(0f,1f), new Vector(0f,2f), new Vector(-1f,2f)},
    new Vector[] { new Vector(0f,1f), new Vector(1f,1f), new Vector(1f,2f), new Vector(0f,2f)},
    new Vector[] { new Vector(1f,1f), new Vector(2f,1f), new Vector(2f,2f), new Vector(1f,2f)}
};

private static bool inside(Vector a, Vector b, Vector c)
{
    return ((c - b) ^ (a - b)) > 0f;
}

private static Vector intersect(Vector a, Vector b, Vector c, Vector d)
{
    return (((c - d) * (a ^ b)) - ((a - b) * (c ^ d))) * (1.0f / ((a - b) ^ (c - d)));
}

private static float getArea(List<Vector> l)
{
    if (l.Count == 0) 
        return 0f;
    float sum = 0.0f;
    Vector b = l.Last();
    foreach (Vector c in l)
    {
        sum += b ^ c;
        b = c;
    }
    return 0.5f * Math.Abs(sum);
}

private static float getOverlap(Vector[] clip, Vector[] box)
{
    List<Vector> lO = box.ToList();
    Vector lC = clip[clip.Length - 1];
    foreach (Vector C in clip)
    {   
        if (lO.Count == 0)
            return 0.0f;
        List<Vector> lI = lO;
        Vector lB = lI.Last();
        lO = new List<Vector>();
        foreach (Vector B in lI)
        {
            if (inside(B, lC, C))
            {
                if (!inside(lB, lC, C))
                    lO.Add(intersect(lB, B, lC, C));
                lO.Add(B);
            }
            else
            if (inside(lB, lC, C)) 
                lO.Add(intersect(lB, B, lC, C));
            lB = B;
        }
        lC = C;
    }
    return getArea(lO);
}

// image processing code, as before

    Transform trn = new Transform(a, cx, cy);

    for (int y = 0; y < h; y++)
    {
        for (int x = 0; x < w; x++)
        {
            Vector p = trn.Get((float)x, (float)y);
            int i = p.X, j = p.Y;
            Vector d = new Vector(i, j);
            
            List<Vector> r = new List<Vector>();
            r.Add(p - d);
            r.Add(trn.Get((float)(x+1), (float)y) - d);
            r.Add(trn.Get((float)(x+1), (float)(y+1)) - d);
            r.Add(trn.Get((float)x, (float)(y+1)) - d);
            
            RGB c = RGB.Black;
            float t = 0.0f;
            
            for (int l = 0; l < 3; l++)
            {
                for (int m = 0; m < 3; m++)
                {
                    float area = getOverlap(clipboxes[m * 3 + l], r.ToArray());
                    if (area > 0.0f)
                    {
                        RGB s = src.getPixel(i + l - 1, j + m - 1);
                        if (s.Valid)
                        {
                            c += s * area;
                            t += area;
                        }
                    }
                }
            }
            
            if (t > 0.0f)
                dst.setPixel(x, y, c * (1.0f / t));
        }
    }

还有更高级的技术可用，例如使用傅立叶变换 - 请参阅达特茅斯大学名为 高质量别名自由图像旋转 的论文（可直接从其网站获得）。此外，我们可以使用更高阶的代替双线性插值，例如双三次，这会给出更平滑的结果。

将二维数组中的像素数据旋转 x 度（伪代码或 Python3）

Rotate Pixel-Data in a two dimensional array by x degrees (PseudoCode or Python3)

python

language-agnostic

arrays

algorithm

image-processing