python - 将二维数组中的像素数据旋转 x 度(伪代码或 Python3)

Question

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

对此我没有办法:如何将给定的 Colour-Object-Array 转换为表示相同图像但旋转 x 度(扩展)的另一个数组。新的颜色/像素在哪里着陆，如何计算？如何计算这个数组的新大小？有没有任何易于理解的pdf，我可以通过，理解，如何，fe。 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() - 我已经实现了“画家”算法，这意味着颜色可以是通过调用 merge(bottomColour, topColour) 进行合并，如果一个颜色位于另一个之上，则返回结果颜色。这方面的理论可以在这里找到: Determine RGBA colour received by combining two colours

我们不允许使用 numpy 或任何其他模块或库。没有颜色/像素的地方应该是“无”。

非常感谢!

Answer 1

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

假设围绕(a, b) 旋转并逆时针旋转θ 度:

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

---

简单技术:最近邻

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

乍一看这似乎足够好，但网页重新缩放 + 图像压缩模糊了边缘。放大 View 显示生成的图像具有令人讨厌的锯齿状边缘(锯齿):

---

过滤:双线性近似

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

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

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

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

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

---

还有更高级的技术可用，例如使用傅立叶变换 - 请参阅达特茅斯大学名为 High Quality Alias Free Image Rotation 的论文(可直接从其网站获取)。此外，我们可以使用更高阶的代替双线性插值，例如双三次，这会产生更平滑的结果。