Como eu faço convolução em F #?

Question

Gostaria convolve um sinal discreto com um filtro discreto. O sinal e do filtro é sequências de flutuador em F #.

A única maneira que eu posso descobrir como fazer isso é com dois laços for aninhados e uma matriz mutável para armazenar o resultado, mas não se sente muito funcional.

Aqui está como eu faria isso não funcional:

conv = double[len(signal) + len(filter) - 1]
for i = 1 to len(signal)
  for j = 1 to len(filter)
    conv[i + j] = conv[i + j] + signal(i) * filter(len(filter) - j) 

Answer 1

Tente esta função:

let convolute signal filter =
    [|0 .. Array.length signal + Array.length filter - 1|] |> Array.map (fun i ->
        [|0 .. i|] |> Array.sum_by (fun j -> signal.[i] * filter.[Array.length filter - (i - j) - 1]))

Provavelmente não é a solução função mais agradável, mas deve fazer o trabalho. Eu duvido que existe uma solução puramente funcional que irá corresponder a um imperativo para a velocidade no entanto.

Espero que ajude.

Nota: A função é atualmente testado (embora eu tenha confirmado que compila). Deixe-me saber se ele não chega a fazer o que deveria. Além disso, observa-se que as variáveis ??i e j não se referem às mesmas coisas que é o seu post original.

Answer 2

Eu não sei F #, mas eu vou postar algumas Haskell e espero que ele vai estar perto o suficiente para uso. (Eu só tenho VS 2005 e uma versão antiga de F #, então eu acho que seria mais confuso para postar algo que funciona na minha máquina)

Deixe-me começar por postar uma implementação Python do seu pseudocódigo ter certeza que eu estou recebendo a resposta certa:

def convolve(signal, filter):
    conv = [0 for _ in range(len(signal) + len(filter) - 1)]
    for i in range(len(signal)):
        for j in range(len(filter)):
            conv[i + j] += signal[i] * filter[-j-1]
    return conv

Agora convolve([1,1,1], [1,2,3]) dá [3, 5, 6, 3, 1]. Se isso é errado, por favor me diga.

A primeira coisa que podemos fazer é transformar o loop interno em um zipWith; estamos essencialmente a adição de uma série de linhas de uma maneira especial, no exemplo acima: [[3,2,1], [3,2,1], [3,2,1]]. Para gerar cada linha, vamos fechar cada i na signal com o filtro invertida:

makeRow filter i = zipWith (*) (repeat i) (reverse filter)

(Nota: de acordo com um Google rápido, zipWith é map2 em F # Você pode ter que usar uma compreensão de lista em vez de repeat.) Agora:

makeRow [1,2,3] 1
=> [3,2,1]
makeRow [1,2,3] 2
=> [6,4,2]

Para obter este para todos i, precisamos mapear mais de sinal:

map (makeRow filter) signal
=> [[3,2,1], [3,2,1], [3,2,1]]

Boa. Agora só precisamos de uma forma de combinar as linhas corretamente. Podemos fazer isso por perceber que a combinação está adicionando a nova linha para a matriz existente, exceto para o primeiro elemento, que é preso em frente. Por exemplo:

[[3,2,1], [6,4,2]] = 3 : [2 + 6, 1 + 4] ++ [2]
// or in F#
[[3; 2; 1]; [6; 4; 2]] = 3 :: [2 + 6; 1 + 4] @ [2]

Por isso, só precisa escrever algum código que faz isso no caso geral:

combine (front:combinable) rest =
    let (combinable',previous) = splitAt (length combinable) rest in
    front : zipWith (+) combinable combinable' ++ previous

Agora que temos uma maneira de gerar todas as linhas e uma maneira de combinar uma nova linha com uma matriz existente, todos nós temos que fazer é colocar os dois juntos com uma dobra:

convolve signal filter = foldr1 combine (map (makeRow filter) signal)

convolve [1,1,1] [1,2,3]
=> [3,5,6,3,1]

Então, isso é uma versão funcional. Eu acho que é razoavelmente claro, desde que você entenda foldr e zipWith. Mas é pelo menos tão longo como a versão imperativo e como outros comentadores disse, provavelmente menos eficientes em F #. Aqui está a coisa toda em um só lugar.

makeRow filter i = zipWith (*) (repeat i) (reverse filter)
combine (front:combinable) rest =
    front : zipWith (+) combinable combinable' ++ previous
    where (combinable',previous) = splitAt (length combinable) rest
convolve signal filter = foldr1 combine (map (makeRow filter) signal)

Editar:

Como prometido, aqui está uma versão # F. Isto foi escrito usando uma versão seriamente antiga (1.9.2.9) em VS2005, então tome cuidado. Também eu não poderia encontrar splitAt na biblioteca padrão, mas então eu não sei F # tão bem.

open List
let gen value = map (fun _ -> value)
let splitAt n l = 
  let rec splitter n l acc =
    match n,l with
    | 0,_ -> rev acc,l
    | _,[] -> rev acc,[]
    | n,x::xs -> splitter (n - 1) xs (x :: acc)
  splitter n l [] 
let makeRow filter i = map2 ( * ) (gen i filter) (rev filter)
let combine (front::combinable) rest =
  let combinable',previous = splitAt (length combinable) rest
  front :: map2 (+) combinable combinable' @ previous
let convolve signal filter = 
  fold1_right combine (map (makeRow filter) signal)

Answer 3

Na verdade, você geralmente querem laços evitar (plain, aninhado, qualquer que seja) e mutável nada na programação funcional.

Há passa a ser uma solução muito simples na F # (e provavelmente quase todos os outros linguagem funcional):

let convolution = Seq.zip seq1 seq2

A função zip simplesmente combina as duas sequências em um dos pares contendo o elemento de seq1 e o elemento de seq2. Como uma nota, existem também funções de fecho de correr semelhantes, para os módulos List e Array, bem como as variantes para a combinação de três listas em triplos (zip3). Se você quiser minério de tom geralmente zip (ou "convolute") n listas em uma lista de n-tuplas, então você vai precisar para escrever sua própria função, mas é bastante simples.

(eu tenho ido por esta descrição de convolução pelo caminho -. diga-me se você quer dizer outra coisa)

Answer 4

Em princípio, deveria ser possível usar o (Fast) Transformada de Fourier, ou relacionados (discreta) Cosine Transform, para calcular a convolução de duas funções razoavelmente eficiente. Você calcular a FFT para ambas as funções, multiplicá-los e aplicar a FFT inversa no resultado.

fundo matemática

Essa é a teoria. Na prática, você provavelmente melhor seria encontrar uma biblioteca de matemática que implementa-lo para você.