在二维数组中旋转像素数据x度(PseudoCode或Python3)

Question

对于一个学校项目，我们的信息学老师希望我们重新发明车轮。我们给出了一个数组，表示图像的像素，包含在另一个脚本中定义的颜色对象。它们代表一个由4个整数组成的集合，红色、绿色、蓝色和阿尔法值的值为0到255。现在，我们必须对这个数组进行图像处理的标准操作。我们被明确告知，要借鉴互联网和问题站点的堆栈溢出.

对此，我没有方法:如何将给定的彩色对象数组转换为另一个表示相同图像的数组，但旋转x度(并进行扩展)。新颜色/像素在哪里，如何计算？如何计算这个数组的新大小？有没有什么简单易懂的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] ]

编辑:要访问colour-Value，有getred()、getgreen()、getblue()和gettuple()方法--我已经实现了“画师”-algorithm，这意味着颜色可以通过调用merge(bottomColour，topColour)来合并，这会返回结果颜色，如果其中一个放在另一个上面。这方面的理论发现在这里：Determine RGBA colour received by combining two colours

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

提前非常感谢！

Answer 1

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

假设绕(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
    }
}

放大-结果：

​

​

比天真的近邻法好得多！

强迫症警报！

出于好奇，我实现了前面提到的完整的“各向异性”方法。花费的时间比它应该长，而且不完全有效(使用萨瑟兰-霍奇曼裁剪来计算旋转像素区域和每个网格像素之间的交集区域)。计算时间通过屋顶--大约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));
        }
    }

有更先进的技术可用，例如使用傅立叶变换-见达特茅斯大学的论文名为高质量的别名自由图像旋转(直接从他们的网站)。另外，我们可以使用更高的阶，例如双三次，而不是双线性插值，这样可以得到更平滑的结果。

Answer 2

至于位置，试着进行背向变换。让每个结果像素正方形用它的中心点来表示。对于每一个这样的点，让我们找出哪里属于源点。找到，什么像素方属于那个源点-瞧-你有源方和源集的颜色。

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

不要忘记计算正弦曲线和余弦一次，并将它们用于每一点的计算。