matrix - 二维照片的线性变换

Question

前言:我不确定是将其归类为数学问题还是编程问题，而且我是线性代数的菜鸟，出于业余爱好而这样做。非常感谢任何帮助。

假设我有一些任意的编程语言，它没有任何既定的机制来对位图图像(或任意 x、y 值的任意集合)执行线性转换。假设我想执行一些任意的旋转、缩放和平移。

现在我将遍历每个 x,y，获取像素颜色，并对它执行变换，四舍五入到最近的新 x,y 以将我的像素颜色值复制到，然后生成最终图像。它适用于我预先计算的简单旋转，但需要几秒钟才能在 i5 上的 TransformImage 方法中进行计算，所以我想知道什么是更快的方法？

这是我目前在 C# 中测试的方法:

        Color[,] BackupOriginal = OriginalColorData.Clone() as Color[,];
        float angle = 25.0f;
        float angleRadians = (float)(angle * (Math.PI / 180f));
        float cosAngle = (float)Math.Cos(angleRadians);
        float sinAngle = (float)Math.Sin(angleRadians);
        BackupOriginal = LinearTransformation.TransformImage(BackupOriginal, new float[2, 2] {
            {cosAngle,-1f * sinAngle},
            {sinAngle,cosAngle}
        });

...

    public static Color[,] TransformImage(Color[,] originalImage, float[,] transformationMatrix)
    {
        if (transformationMatrix.GetUpperBound(1) < 1 || transformationMatrix.GetUpperBound(0) < 1) return null;

        int width = originalImage.GetUpperBound(1) + 1;
        int height = originalImage.GetUpperBound(0) + 1;
        Color[,] newImage = new Color[height, width];
        for (int y=0;y<height;y++)
        {
            for (int x=0;x<width;x++)
            {
                Color currentPixel = originalImage[y, x];
                int newX = (int)Math.Round((x * transformationMatrix[0, 0]) + (y * transformationMatrix[0, 1]));
                int newY = (int)Math.Round((x * transformationMatrix[1, 0]) + (y * transformationMatrix[1, 1]));
                if (IsValidPixel(newX, newY, width, height))
                    newImage[newY, newX] = currentPixel;
            }
        }
        return newImage;
    }

Answer 1

基本上，这是一个您不想自己用任意语言实现的操作。您需要考虑几个问题:

1. 所有边界检查都会产生一些费用。 C# 将检查所有数组索引的限制，您也一样。对于每个像素。如果幸运的话，JIT 编译器会排除其中的一部分，但它仍然很昂贵。二维数组比更常见的一维情况更昂贵，特别是在 C# 中，Why are multi-dimensional arrays in .NET slower than normal arrays?
2. float 和整数之间的来回转换成本很高。您正在将 int 转换为 float 四次，并将 float 转换为 int 两次。每像素。

我们可以在这里停下来，只考虑您现在对每个像素执行的操作数，而不是琐碎的分配。

然而，更重要的是:

1. 内存力不统一。你想在一些连续的 block 中读取和写入它。您现在正在以完美的顺序阅读，但根据变换，您正在到处书写。这很难针对“任意转换”进行优化，但一般的想法是尝试做适合您的缓存层次结构的小块。由于变换是线性的，因此一个空间中的任何小图 block 都会非常粗略地最终出现在另一个空间中的类似位置。
2. 现代 CPU 非常擅长矢量运算。通过适当的逻辑，可以一次复制 32 字节的 block (8 个 32 位像素)，计算新像素位置也是如此。

然后，您会遇到如何处理别名的问题。没有简单的方法可以保证 newImage 中的每个像素都映射到 originalImage 中的一个且仅一个像素。您最终可能会多次写入同一个像素(您可能真的想混合结果)，并且某些像素可能最终为空。

那么，在一个相当短的代码片段中可以完成什么？不要太多。如果您正在寻找性能，我至少会尝试摆脱 Math.Round(只需在进行粗略舍入之前添加 .5)，并且理想情况下完全避免 float 。一种选择是存储一个整数乘数，然后将结果(>>> 运算符)移回相同的范围，即将 cosAngle 存储为 cosAngle * 65536 并将 newX 移动 16。根据之前的评论，甚至可能将转换矩阵存储为四个单独的浮点值可能比那里的二维数组更可取。我希望 JIT 编译器能够处理这种情况。

但是，归根结底，它并没有什么魔力。高性能实现往往更长，并且也倾向于用其他语言编写。相同逻辑的 C 或 C++ 实现可以稍微加快速度，但您仍然必须特别处理内存带宽问题，其中对完整源图像的顺序循环会给您带来目标中不利的内存访问模式角度。您可以自己测试一下，0 度的角度是否明显快于 0.4 度？

C 实现的大部分加速将来自积极调整的优化编译器，以便为计算密集型循环生成简洁的代码，而实践中的 .NET 环境更多地关注业务线应用程序。

我不认为这里使用 Color 类型是个问题，因为 .NET 结构往往很快，但如果你想评估性能，我可能会尝试使用只是一个简单的 int 或 float 灰度值数组，以了解 OO 抽象是否以某种方式妨碍了适当的优化。