haskell - 在具有边界情况的 repa 数组上映射窗口函数

Question

问题

我正在寻找 repa 库中可能已经存在的函数。我想要一个功能:

1. 接受一个二维数组
2. 指定窗口大小的两个整数
3. 在二维数组上给定大小的每个窗口中，计算一个新值，例如此特定窗口中的小值。

例子

用 3x3 窗口映射 min 函数:

| 1 2 3 4 3  4 5 6 7 2  7 8 9 4 2  5 4 8 1 6  8 5 3 3 2 |

Would return:

| 1 1 2 2 2  1 1 2 2 2  4 4 1 1 1  4 3 1 1 1  4 3 1 1 1 |

Note that I'm using a scheme akin to the BoundClamp  constructor in Data.Array.Repa.Stencil. This isn't a stencil convolution, i.e. it is not applying a stencil to every element of a 2D array. Instead, it is performing a function at each window on the array, with out-of-range elements at the edges being assigned the closest value at the edge of the 2D array.

Type of possible solution

The function might look something like:

mapF
  :: Source r a
  => Boundary a            -- ^ How to handle the boundary of the array.
  -> (Int,Int)             -- ^ window size in the X and Y direction.
  -> (Array r DIM2 a -> b) -- ^ function over window e.g. to return the minimum value.
  -> Array r DIM2 a        -- ^ Array to apply function to.
  -> Array r DIM2 b

这是已经存在的东西，还是编写起来微不足道的东西？

Answer 1

我对我的 repa 生疏了，但相信你可以使用 traverse 并手动检测数组边界。考虑类型:

traverse ::
  (Source r a, Shape sh, Shape sh') =>
  Array r sh a
  -> (sh -> sh') -> ((sh -> a) -> sh' -> b) -> Array D sh' b

该函数采用原始数组、一个生成新形状的函数、一个采用查找函数和索引生成新值的函数，并生成新的(延迟的)数组。

一个简单的解决方案是检查索引的所有邻居，使用 min 和 max 控制边界:

import qualified Data.Array.Repa as R
import           Data.Array.Repa (Z(..), traverse, fromListUnboxed, toList, (:.)(..))
import Prelude
import Data.List.Split

main = do let a = fromListUnboxed (Z :. h :. w) ( [1..6] ++ [2..7] ++ [3..8] ++ [4..9] ++ [5..10] ::  [Int])
              r = traverse a id (\f (Z :. y :. x) -> minimum [f (Z :. yi :. xi) | xi <- idx w x, yi <- idx h y])
          printArray a
          printArray r
  where
    idx b i = map (bound b) [i, i+1, i-1]
    bound b = min (b-1) . max 0
    w = 6 :: Int
    h = 5 :: Int

    printArray = putStrLn . unlines . map show . chunksOf w . toList

反对此解决方案的主要原因是性能(对相同数字进行多次比较，应静态消除许多边界检查)。 OTOH，您的问题只要求一个简单的解决方案，似乎并不过分关注性能。

如果 Repa 内置了更快的解决方案，我也很感兴趣。