有效的2d平均过滤器实现，以最小化冗余内存负载？

Question

假设在核上执行某种函数的一般滑动算法，例如均值滤波器(平均滤波器)或图像处理中的绝对差算法之和。当内核滑到下一个位置时，将从内存中读取一些多余的数据，因为新内核所包含的数据将在某种程度上与以前的数据重叠。

让我用一个实际的例子来解释..。假设您希望在内核(窗口)大小为3x3的大型2D矩阵上执行中值滤波。内核的第一个位置(下图红色)将居中于(1,1)，第二个位置(绿色)将居中(1,2)。注意黄色区域是如何重叠的，这些值现在需要从内存中重新加载。

​

我的具体问题是3D平均滤波器，所以重叠更大(3^3-3^2 = 18，3^2-3 =6，对于2D)。

我肯定这是个常见的问题..。有谁知道这样的算法是如何有效地实现的，以消除冗余内存查找，或者利用现代体系结构上CPU缓存的空间和时间局部性(例如双向关联缓存)？

我在3D中的具体问题仅取最近的6个邻居的平均值(而不是对角线的)，并在C中实现如下：

for( i = 0; i <= maxi; i++ ) {
    for( j = 0; j <= maxj; j++ ) {
        for( k = 0; k <= maxk; k++ ) {
            filteredData[ i ][ j ][ k ] = 
            ONE_SIXTH *
            ( 
             data[ i + 1 ][ j     ][ k     ] +
             data[ i - 1 ][ j     ][ k     ] +
             data[ i     ][ j + 1 ][ k     ] +
             data[ i     ][ j - 1 ][ k     ] +
             data[ i     ][ j     ][ k + 1 ] +
             data[ i     ][ j     ][ k - 1 ]
            );
        }
    }
}

Answer 1

你所做的被称为卷积。您可以将多维数据与相同维数的较小内核进行转换。这是一项非常常见的任务，有大量的库可供使用。

快速解(取决于内核大小)是计算频域卷积的一种方法。计算数据和内核的(多维) FFT，乘以它们，然后计算逆FFT。您会发现优化的库就是这样做的，例如。对于Python，有scipy.ndimage.filters.convolve和scipy.signal.fftconvolve。

贴片是一种常用的图像处理技术，用于优化底层内存访问.您可以分配适合CPU缓存的方形块(或立方体)。当你访问邻近的像素时，它们大部分时间都在内存中紧密相连。不过，对整个数组进行循环有点棘手。

为了进一步阅读，我再次推荐论文现代CPU饥饿的原因及能做些什么，它提到了这种内存阻塞技术，并指出了实现它的数字库。

最后，还有一个积分图像，它允许你用非常少量的内存访问任意矩形/长方体的计算平均值。

Answer 2

对于2D均值过滤器的情况，我将保持列总计，然后可以重复使用，这样每次迭代时，您只计算一个新的列总数，然后对列总计进行求和，以得到平均值。例如，3x3的平均数：

for (i = 1; i < M - 1; ++i)
{
    // init first two column sums
    col0 = a[i - 1][0] + a[i][0] + a[i + 1][0];
    col1 = a[i - 1][1] + a[i][1] + a[i + 1][1];
    for (j = 1; j < N - 1; ++j)
    {
        // calc new col sum
        col2 = a[i - 1][j + 1] + a[i][j + 1] + a[i + 1][j + 1];
        // calc new mean
        mean[i][j] = (col0 + col1 + col2) / 9;
        // shuffle col sums
        col0 = col1;
        col1 = col2;
    }
}

这只会导致每点3次负载，而不是幼稚情况下的9次，但仍然不是很理想。

您可以进一步优化这一点，方法是每次迭代处理两行，并为第一行和第一行保持重叠列和。