在C#中加速矩阵加法

Question

我想要优化这段代码：

public void PopulatePixelValueMatrices(GenericImage image,int Width, int Height)
{            
        for (int x = 0; x < Width; x++)
        {
            for (int y = 0; y < Height; y++)
            {
                Byte  pixelValue = image.GetPixel(x, y).B;
                this.sumOfPixelValues[x, y] += pixelValue;
                this.sumOfPixelValuesSquared[x, y] += pixelValue * pixelValue;
            }
        }
}

这是用于图像处理的代码，目前我们正在处理大约200张图片。我们优化了使用不安全代码的GetPixel值，而且没有使用image.Width或image.Height属性，因为这些属性会增加运行时成本。

然而，我们的速度仍然很慢。问题在于我们的图像大小为640x480，所以循环的中间部分会被调用大约640x480x200次。

我想问问是否有办法加快速度，或者说服我它已经足够快了。也许通过一些快速矩阵加法的方式可以解决，或者矩阵加法固有的n^2操作没有任何加速的方法？

也许通过不安全代码进行数组访问会加快速度，但我不确定如何去做，以及是否值得时间和精力。可能不值得。

编辑：感谢所有回答。

这是我们正在使用的GetPixel方法：

 public Color GetPixel(int x, int y)
    {
        int offsetFromOrigin = (y * this.stride) + (x * 3);
        unsafe
        {
            return Color.FromArgb(this.imagePtr[offsetFromOrigin + 2], this.imagePtr[offsetFromOrigin + 1], this.imagePtr[offsetFromOrigin]);
        }
    }

- Jean Azzopardi

---

矩阵加法可以通过少于n^2次操作实现。我在大学里读到过，但现在忘记了方法：P .. 尝试在谷歌上搜索一下，这可能会有所帮助.. 谢谢 :) - Mahesh Velaga

@Mahesh：你不能在小于n^2的时间内完成矩阵加法。你是指矩阵乘法吗？它可以在小于n^3的时间内完成吗？ - Henrik

我刚刚注意到你的Y循环在X循环内部。除非图像被转置存储，否则相邻的Y值在内存中通常相隔一个图像跨度。尝试交换X和Y循环。 - Skizz

@Skizz：仅仅交换X和Y的循环会损害这种情况下的数组访问 - 你需要同时改变数组的意义，并且以 [y, x] 的方式进行访问。 - Jon Skeet

@Jean：如果你以一种每次访问都会使缓存失效的方式访问数组，那意味着你的内存总线需要更加努力地工作。 - Jon Skeet

Answer 1

尽管使用了不安全的代码，GetPixel可能是这里的瓶颈。您是否考虑过获取图像中所有像素的方法，而不是每个像素一次调用？例如，Bitmap.LockBits 可能会对您有所帮助...

在我的 netbook 上，一个非常简单的循环迭代 640 * 480 * 200 次只需要大约 100 毫秒 - 因此，如果您发现速度变慢，您应该重新查看循环内部的代码。

您可能想要查看的另一个优化：避免多维数组。它们比单维数组慢得多。

特别地，您可以拥有一个大小为 Width * Height 的单维数组，只需保持一个索引即可。

int index = 0;
for (int x = 0; x < Width; x++)
{
    for (int y = 0; y < Height; y++)
    {
        Byte pixelValue = image.GetPixel(x, y).B;
        this.sumOfPixelValues[index] += pixelValue;
        this.sumOfPixelValuesSquared[index] += pixelValue * pixelValue;
        index++;
    }
}

使用相同的简单测试工具，向2D矩形数组添加写入操作会使循环200 * 640 * 480的总时间增加到约850毫秒；使用1D矩形数组将总时间降至约340毫秒 - 因此它有一定的重要性，而当前每个循环迭代中有两个这样的数组。

- Jon Skeet

---

@Jon Skeet, Chloe：如果您索引数组，则会执行边界检查，而不是使用固定指针扫描它。但是，如果for循环编写为针对正在索引的数组的Length成员进行测试，则在安全代码中也会优化掉边界检查。 - Ben Voigt

不是从2D到1D的转换带来了差异，而是你如何遍历数组。你的一维代码肯定按顺序遍历。为了实现这一点，你已经有效地将数据从行优先排列变成了列优先排列（以前的索引为y * Width + x，现在是x * Height + y）。提高CPU缓存使用的局部性确实是一个真正的优势，但重新交错结果数组并不是做到这一点的正确方法，因为你仍然会错误地访问行优先源数据。将源和目标交错相同，并颠倒循环嵌套即可解决问题。 - Ben Voigt

请注意，我并不是说二维数组和一维数组的速度一样快，只是你遇到的加速有另一个原因。反转循环嵌套并转换为一维数组可能会更快。 - Ben Voigt

@Skizz：在回复之前，我已经测试过了。如果你改变循环顺序，它会减慢速度。OP问题中的代码已经访问了[0, 0]、[0, 1]、[0, 2]等，这是快速的方式。 - Jon Skeet

（请注意，我谈论的是数组寻址而非像素访问。反转数组顺序和迭代顺序可能会有所帮助，但仅仅反转其中一个是不够的。） - Jon Skeet

Answer 2

阅读这篇文章，其中包含一些代码并提到了GetPixel的运行速度缓慢。

链接文字

从文章中可以看到这段代码用于简单地反转位。 这展示了LockBits的用法。

需要注意的是，不安全的代码将不允许您远程运行代码。

public static bool Invert(Bitmap b)
{

BitmapData bmData = b.LockBits(new Rectangle(0, 0, b.Width, b.Height), 
                               ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb); 

int stride = bmData.Stride; 
System.IntPtr Scan0 = bmData.Scan0; 
unsafe 
{ 
    byte * p = (byte *)(void *)Scan0;
    int nOffset = stride - b.Width*3; 
    int nWidth = b.Width * 3;
    for(int y=0;y < b.Height;++y)
    {
        for(int x=0; x < nWidth; ++x )
        {
            p[0] = (byte)(255-p[0]);
            ++p;
        }
        p += nOffset;
    }
}

b.UnlockBits(bmData);

return true;

}

- anirudhgarg

---

不错的发现。我在Java中也使用类似的技巧 - 速度大幅提升！ - Otto Allmendinger

Answer 3

我建议您对此代码进行分析，找出耗时最长的部分。

您可能会发现是下标操作，如果是这样，您可能需要将数据结构从以下形式更改为其他形式：

long sumOfPixelValues[n,m];
long sumOfPixelValuesSquared[n,m];

为了

struct Sums
{
    long sumOfPixelValues;
    long sumOfPixelValuesSquared;
}

Sums sums[n,m];

这将取决于您在对代码进行分析后所发现的情况。

- John Saunders

Answer 4

System.Drawing.Color 是一个结构体，在当前版本的 .NET 中会破坏大部分优化。既然您只关心蓝色成分，那么使用一个仅获取所需数据的方法即可。

public byte GetPixelBlue(int x, int y)
{
    int offsetFromOrigin = (y * this.stride) + (x * 3);
    unsafe
    {
        return this.imagePtr[offsetFromOrigin];
    }
}

现在，交换x和y的迭代顺序：

public void PopulatePixelValueMatrices(GenericImage image,int Width, int Height)
{            
    for (int y = 0; y < Height; y++)
    {
        for (int x = 0; x < Width; x++)
        {
            Byte  pixelValue = image.GetPixelBlue(x, y);
            this.sumOfPixelValues[y, x] += pixelValue;
            this.sumOfPixelValuesSquared[y, x] += pixelValue * pixelValue;
        }
    }
}

现在，您正在按顺序访问扫描线中的所有值，这将更好地利用涉及的三个矩阵（image.imagePtr、sumOfPixelValues和sumOfPixelValuesSquared）的CPU缓存。（感谢Jon注意到当我修复对image.imagePtr的访问时，我破坏了其他两个。现在，输出数组索引已交换以保持最佳状态。）

接下来，摆脱成员引用。另一个线程理论上可能会在中途将sumOfPixelValues设置为另一个数组，这会对优化造成可怕的影响。

public void PopulatePixelValueMatrices(GenericImage image,int Width, int Height)
{          
    uint [,] sums = this.sumOfPixelValues;
    ulong [,] squares = this.sumOfPixelValuesSquared;
    for (int y = 0; y < Height; y++)
    {
        for (int x = 0; x < Width; x++)
        {
            Byte  pixelValue = image.GetPixelBlue(x, y);
            sums[y, x] += pixelValue;
            squares[y, x] += pixelValue * pixelValue;
        }
    }
}

现在编译器可以生成优化的代码来遍历这两个输出数组，内部循环通过步长为3的方式遍历image.imagePtr数组，而不是一直重新计算偏移量。现在为了保险起见，还有一个不安全的版本，进行我认为.NET应该能够执行但可能没有执行的优化：

unsafe public void PopulatePixelValueMatrices(GenericImage image,int Width, int Height)
{          
    byte* scanline = image.imagePtr;
    fixed (uint* sums = &this.sumOfPixelValues[0,0])
    fixed (uint* squared = &this.sumOfPixelValuesSquared[0,0])
    for (int y = 0; y < Height; y++)
    {
        byte* blue = scanline;
        for (int x = 0; x < Width; x++)
        {
            byte pixelValue = *blue;
            *sums += pixelValue;
            *squares += pixelValue * pixelValue;
            blue += 3;
            sums++;
            squares++;
        }
        scanline += image.stride;
    }
}

- Ben Voigt

---

谢谢你的答复。最终，我们采用了LockBits并直接访问图像的原始结构，而不是使用GetPixel或GetPixelBlue等方法。 - Jean Azzopardi

哎呀！squares最好是一个UInt64数组，因为最大值是255255 * 640480 > 2^32。这使它的大小超过了2兆字节，这几乎可以保证随机访问意味着主存储器的命中...交换循环对于获得良好的速度绝对至关重要。 - Ben Voigt

@Jean：从你使用imagePtr的GetPixel版本来看，我以为你已经在使用LockBits了...那么你还从哪里得到了imagePtr呢？ - Ben Voigt

哎呀，方块没有必要是UInt64的，因为不是每个方块里放置了640*480像素，而是200张图片中相同的像素，所以UInt32就可以了。但与缓存相比仍然很大。 - Ben Voigt

@Ben Voigt，我的意思是，我替换了GetPixel()方法，直接在图像上使用Lockbits获取像素，即不使用方法。 - Jean Azzopardi

Answer 5

代码分析是开始的最佳地点。

矩阵加法是高度并行化的操作，可以通过使用多个线程并行化操作来加速。

我建议使用Intels IPP库，该库包含用于此类操作的线程高度优化的API。也许令人惊讶的是，它只需要约100美元，但会给您的项目增加重要的复杂性。

如果您不想麻烦自己进行混合语言编程和IPP，则可以尝试使用centerspace的C# math库。 NMath API包含易于使用、前向缩放的矩阵操作。

保罗

- Paul

---

谢谢，我们最终通过使用EQATEC分析器对代码进行剖析进行了优化，所以您的建议确实非常好。+1 - Jean Azzopardi

Answer 6

图片存储在哪里？如果每个图片都在磁盘上，那么你的处理时间问题可能在于从磁盘中获取它们。你可以检查一下是否存在这个问题，如果是的话，就重写代码以预取图像数据，这样数组处理代码就不必等待数据了...

如果整个应用程序逻辑允许（每个矩阵加法是否独立，还是依赖于前一个矩阵加法的输出？），如果它们是独立的，我会考虑在单独的线程或并行执行它们。

- Charles Bretana

---

实际上，从磁盘获取图像证明非常快。 - Jean Azzopardi

Answer 7

我能想到的唯一可能加速的方法是尝试并行进行一些加法操作，这样对于你的规模来说，可能会比线程开销更有益。

- Yuriy Faktorovich

Answer 8

我不确定是否更快，但你可以写类似这样的内容；

public void PopulatePixelValueMatrices(GenericImage image,int Width, int Height)
{            
        Byte pixelValue;
        for (int x = 0; x < Width; x++)
        {
            for (int y = 0; y < Height; y++)
            {
                pixelValue = image.GetPixel(x, y).B;
                this.sumOfPixelValues[x, y] += pixelValue;
                this.sumOfPixelValuesSquared[x, y] += pixelValue * pixelValue;
            }
        }
}

- lothlarias

Answer 9

这是一个微观优化失败的典型案例。从那个循环中你得不到任何东西。要获得真正的速度优势，你需要从大局出发考虑：

• 在处理图像[n]的同时，你能异步预加载图像[n+1]吗？
• 你能只加载图像的B通道吗？这将减少内存带宽。
• 你能直接加载B值并更新sumOfPixelValues（Squared）数组吗？也就是说，读取文件并更新而不是读取文件、存储、读取、更新？同样，这会减少内存带宽。
• 你能使用一维数组而不是二维数组吗？也许可以创建自己的数组类，以两种方式工作。
• 也许你可以考虑使用Mono和SIMD扩展？
• 你能将图像分块处理并将它们分配给空闲的CPU在多CPU环境中吗？

编辑：

尝试使用专门的图像访问器，这样你就不会浪费内存带宽：

public Color GetBPixel (int x, int y)
{
    int offsetFromOrigin = (y * this.stride) + (x * 3);
    unsafe
    {
        return this.imagePtr [offsetFromOrigin + 1];
    }
}

或者，更好的做法：

public Color GetBPixel (int offset)
{
    unsafe
    {
        return this.imagePtr [offset + 1];
    }
}

并在循环中使用上述代码：

for (int start_offset = 0, y = 0 ; y < Height ; start_offset += stride, ++y)
{
   for (int x = 0, offset = start_offset ; x < Width ; offset += 3, ++x)
   {
      pixel = GetBPixel (offset);
      // do stuff
   }
}

- Skizz

---

我不同意，GetPixel() 因为速度慢而臭名昭著，因此如果可能的话最好避免使用它。 - Ian

@Ian：给出的代码中，参数为“GenericImage image”，据我所知这不是标准的 .net 框架类，因此它可能是一种更高效的图像处理类，也许是第三方库，并且具有良好的 GetPixel 实现。 - Skizz

是的，我们开发了自己的图像库（基本上是在现有的基础上进行改进）。 - Jean Azzopardi

考虑 CPU 缓存效应可能是一种微观优化，但这是非常有效的。所有三个数组（图像数据和两个输出）大小约为 1 兆字节，通过随机访问它们，您将不断地命中 L3 缓存或主内存。通过以正确的顺序迭代，您将使用完全快一个数量级的 L1 缓存。 - Ben Voigt

除了Ben的评论之外，后期的Pentium处理器可以检测到顺序访问的内存并预取数据，从而减少缓存未命中的机会。如果我没记错的话，它可以检测到最多四个数据流。 - Skizz

Answer 10

虽然这只是微小的优化，因此可能不会增加太多，但您可能希望研究在执行时获得零的可能性是多少

Byte  pixelValue = image.GetPixel(x, y).B;

显然，如果pixelValue = 0，则没有必要进行求和，因此您的例程可能会变成

public void PopulatePixelValueMatrices(GenericImage image,int Width, int Height)
  {
  for (int x = 0; x < Width; x++)
    {
    for (int y = 0; y < Height; y++)
      {
       Byte  pixelValue = image.GetPixel(x, y).B;

       if(pixelValue != 0)
         {
         this.sumOfPixelValues[x, y] += pixelValue;
         this.sumOfPixelValuesSquared[x, y] += pixelValue * pixelValue;
         }}}}

然而，问题在于您有多频繁地看到pixelValue=0，以及计算和存储上的节省是否能抵消测试的成本。

- Bob Jarvis - Слава Україні