高效的2d均值滤波器实现,最大限度地减少冗余内存负载

Question

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

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

meanfilter http://luka.s3.amazonaws.com/meanfilter.png

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

我确信这是一个常见的问题......有没有人知道如何有效地实现这样的算法来消除冗余内存查找,或者利用现代架构上CPU缓存的空间和时间局部性(例如2-way)关联缓存)？

我在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 缓存的方形块（或立方体）。当您访问相邻像素时，大多数时候它们在内存中会靠近在一起。不过，循环整个数组有点棘手。

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

最后还有积分图像，它允许您仅通过极少量的内存访问来计算任意矩形/长方体的平均值。