有效的二維平均過濾器實現，可以最大限度地減少冗餘內存負載？

假設一個在內核上執行一些函數的通用滑動算法，如平均濾波器（平均濾波器）或圖像處理中算法的絕對差值總和。當內核滑到下一個位置時，將會有一些來自內存的冗餘讀取，因爲新內核包含的數據將與前一個內容重疊。有效的二維平均過濾器實現，可以最大限度地減少冗餘內存負載？

讓我用一個實際的例子來解釋...假設您想對內核（窗口）大小爲3x3的大型2D矩陣執行中值濾波。內核的第一個位置（下圖中的紅色）將以（1,1）爲中心，第二個位置（綠色）將以（1,2）爲中心。注意黃色區域是如何重疊的，現在這些值需要從內存中重新加載。

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

我的具體問題是3D意味着過濾所以重疊更大（3^3-3^2 = 18，用於3D比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 ] 
      ); 
     } 
    } 
}

來源

2011-05-07 lms

+1有一個清晰明確的問題 – schnaader 2011-05-07 20:13:25

對於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作爲幼稚的情況下，但仍不太理想。

您可以通過處理每次迭代的兩行和維護重疊列總和的行i和i進一步優化本+ 1

來源

2011-05-07 20:29:53

做這些算法沒有「最佳實踐」嗎？我原以爲這是教科書的情況。 – lms 2011-05-08 11:51:14

可能不是 - 大多數過濾器不具備平均過濾器的冗餘性，加載/存儲與算術操作的相對成本與可用寄存器的數量與高速緩存的大小等有關，這意味着「最佳」方法可能會有點體系結構依賴性。 – 2011-05-08 14:11:35

就我個人而言，我遇到過很多這個問題。例如使用Jacobi方法求解拉普拉斯方程，使用絕對差之和或平方差之和進行計算機視覺模板匹配。基本上任何對內核執行某種減少的算法都需要這樣做。對我來說，這似乎不是「教科書」的東西。無論如何感謝您的代碼！ – lms 2011-05-10 14:59:18

你在做什麼叫做卷積。您將多維數據與具有相同維數的較小內核進行卷積。這是一個非常普遍的任務，並且有很多庫。

快速解決方案（depending on the kernel size）是計算頻域卷積。您計算數據和內核的（多維）FFT，將它們相乘，然後計算逆FFT。你會發現庫優化來做到這一點，例如。對於Python，有scipy.ndimage.filters.convolve和scipy.signal.fftconvolve。

平鋪是一種常見的圖像處理技術來優化低級別的內存訪問。您分配適合CPU緩存的正方形瓷磚（或立方體）。當你訪問鄰近的像素時，它們大部分時間都會在內存中靠近。儘管如此，循環遍歷整個數組有點棘手。

爲了進一步閱讀，我推薦文章Why Modern CPUs Are Starving and What Can Be Done about It，它提到了這種內存阻塞技術，並指出了實現它的數值庫。

最後是積分圖像，它允許你calculate the average一個任意的矩形/立方體只有很少的內存訪問。

來源

2011-05-13 08:26:07 maxy

有效的二維平均過濾器實現，可以最大限度地減少冗餘內存負載？

回答

相關問題