Сопоставление оконной функции с массивом repa с граничным случаем

Проблема

Я ищу функцию в библиотеке repa, которая может уже существовать. Мне нужна функция, которая:

  1. Принимает 2D-массив
  2. Два целых числа, определяющие размер окна
  3. В каждом окне заданного размера над двумерным массивом вычислите новое значение, например. маленькое значение в этом конкретном окне.

Пример

Сопоставление функции min с окном 3x3 поверх:

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

Вернул бы:

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

Обратите внимание, что я использую схему, похожую на BoundClamp  конструктор в Data.Array.Repa.Stencil. Это не свертка трафарета, т. е. трафарет не применяется к каждому элементу двумерного массива. Вместо этого он выполняет функцию в каждом окне массива, при этом элементам вне диапазона на краях присваивается ближайшее значение на краю двумерного массива.

Тип возможного решения

Функция может выглядеть примерно так:

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

Это что-то, что либо уже существует, либо было бы тривиально закодировать?


haskell repa
person Rob Stewart    schedule 12.05.2014    source источник
comment
traverse не позволяет мне указать, что происходит на границах 2D-массива, например. указать BoundClamp. Кроме того, traverse будет означать, что я должен программно построить окно вокруг каждого элемента, чтобы вычислить min. Эта деталь абстрагируется с помощью функции трафарета в repa.   -  person Rob Stewart    schedule 12.05.2014

Ответы (1)


arrow_upward
1
arrow_downward

Я заржавел в своем репа, но верю, что вы можете использовать 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.

person Thomas M. DuBuisson    schedule 12.05.2014