在二维数组上执行有效的局部平均

Question

我有一个尺寸约为 250、250 的二维数组自定义矢量 class。 Vector class 仅存储向量的 x 和 y 浮点分量。我的项目要求我对数组执行平滑函数，以便通过获取数组中每个向量周围 i 索引的局部平均值来创建新数组。我的问题是我当前的解决方案计算速度不够快，想知道是否有更好的计算方法。

我当前解决方案的伪代码如下所示。我在 C# 中实现这个，任何帮助将不胜感激。我的实际解决方案使用一维数组来加速，但我没有在此处包括它。

function smoothVectorArray(Vector[,] myVectorArray, int averagingDistance) {

    newVectorArray = new Vector[250,250];

    for (x = 0; x < 250; x++)
    {
        for (y = 0; y < 250; y++)
        {
            vectorCount = 0;
            vectorXTotal = 0;
            vectorYTotal = 0;

            for (i = -averageDistance; i < averagingDistance+ 1; i++)
            {
                for (j = -averageDistance; j < averagingDistance+ 1; j++)
                {

                    tempX = x + i;
                    tempY = y + j;

                    if (inArrayBounds(tempX, tempY)) {
                        vectorCount++;
                        vectorXTotal += myVectorArray[tempX, tempY].x;
                        vectorYTotal += myVectorArray[tempX, tempY].y;
                    }

                }
            }

            newVectorArray[x, y] = new Vector(vectorXTotal / vectorCount, vectorYTotal / vectorCount);

        }
    }

    return newVectorArray;

}

Answer 1

您肯定会希望利用 CPU 缓存来解决这个问题，听起来您的 1D 数组解决方案考虑到了这一点。尝试安排算法一次处理连续的内存块，而不是在数组中跳跃。对于这一点，您应该使用 Vector 结构而不是 class，或者使用两个浮点数组，一个用于 x 值，一个用于 y 值。通过使用 class，您的数组存储指向堆中不同位置的指针。因此，即使您按顺序遍历数组，当您跳转到 Vector 对象的位置时，您仍然始终缺少缓存。每次缓存未命中都会浪费约 200 cpu 个周期。这将是首先要解决的主要问题。

在那之后，您可以考虑的一些微优化是

在 inArrayBounds 方法上使用内联提示：[MethodImpl(MethodImplOptions.AggressiveInlining)]
使用不安全模式并使用指针算法进行迭代以避免数组边界检查开销

这最后两个想法可能有也可能没有任何重大影响，你应该测试。

Answer 2

你的内循环所做的是计算矩形区域的总和：

for (i = -averageDistance; i < averagingDistance+ 1; i++)
   for (j = -averageDistance; j < averagingDistance+ 1; j++)

您可以在 O(n^2) 中高效地预先计算这些。让我们介绍数组 S[N][N]（在您的例子中 N = 250）。

为了简单起见，我假设只有一个坐标。您可以通过构建 2 个数组轻松地使其适应 (x, y) 对。

S[i, j] - 将是子矩形 (0, 0)-(i, j)

的总和

我们可以高效地构建这个数组：

S[0, 0] = myVectorArray[0, 0]; //rectangle (0, 0)-(0,0) has only one cell (0, 0)
for (int i = 1; i < N; ++i){
  S[0, i] = S[0, i-1] + myVectorArray[0, i];  //rectangle (0, 0)-(0, i) is calculated based on previous rectangle (0,0)-(0,i-1) and new cell (0, i)
  S[i, 0] = S[i - 1, 0] + myVectorArray[i, 0]; //same for (0, 0)-(i, 0)
}

for (int i = 1; i < N; ++i){
  var currentRowSum = myVectorArray[i, 0];
  for (int j = 1; j < N; ++j){
     currentRowSum += myVectorArray[i, j]; //keep track of sum in current row
     S[i, j] = S[i - 1, j] + currentRowSum; //rectangle (0,0)-(i,j) sum constrcuted as //rectanle (0, 0) - (i-1, j) which is current rectagnle without current row which is already calculated + current row sum
  }
 }

一旦我们计算出这个部分和数组，我们就可以在 O(1) 中得到子矩形和。假设我们想要在矩形 (a, b)-(c,d)

中求和

为了得到它，我们从大矩形 (0, 0)-(c, d) 开始，我们需要从中减去 (0, 0)-(a-1, d-1) 和 (0, 0 )-(c-1, b-1) 并添加添加矩形 (0, 0)-(a-1, b-1) 因为它被减去两次。

这样你就可以摆脱你的内循环。

https://en.wikipedia.org/wiki/Summed_area_table

在二维数组上执行有效的局部平均

Performing efficient local average over a 2D array

c#

arrays

performance

2d

average