c - 最小化冗余内存负载的高效二维均值滤波器实现？

Question

假设一个通用的滑动算法在内核上执行一些函数，例如图像处理中的均值滤波器(average-filter)或绝对差求和算法。当内核滑动到下一个位置时，将会有一些内存的冗余读取，因为新内核所包含的数据会与之前的数据有所重叠。

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

我的具体问题是 3D 均值滤波器，因此重叠更大(3D 为 3^3-3^2 = 18，2D 为 3^2-3 = 6)。

我确定这是一个常见问题...有谁知道如何有效地实现此类算法以消除冗余内存查找，或利用现代架构(例如， 2 路关联缓存)？

我在 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

您所做的称为<​​strong>卷积。您将多维数据与维数相同的较小内核进行卷积。这是一项非常常见的任务，并且有大量的库可用于此任务。

快速解决方案 ( depending on the kernel size ) 是计算频域中的卷积。您计算数据和内核的(多维)FFT，将它们相乘，然后计算逆 FFT。您会发现经过优化的库可以做到这一点，例如。对于 Python 有 scipy.ndimage.filters.convolve和 scipy.signal.fftconvolve .

平铺 是一种常用的图像处理技术，用于优化低级内存访问。您分配适合 CPU 缓存的正方形图 block (或立方体)。当您访问相邻像素时，它们大多数时候会在内存中靠近在一起。不过，遍历整个数组有点棘手。

为了进一步阅读，我推荐论文 Why Modern CPUs Are Starving and What Can Be Done about It ，其中提到了这种内存阻塞技术，并指向实现它的数字库。

最后是 Integral Image，它允许您 calculate the average任意矩形/长方体的内存访问次数非常少。