Come faccio a fare la convoluzione in F #?

Question

Vorrei convolve un segnale discreto con un filtro discreto. Il segnale e il filtro sono sequenze di float in F #.

L'unico modo in cui riesco a capire come farlo è con due loop nidificati e un array mutabile per memorizzare il risultato, ma non sembra molto funzionale.

Ecco come lo farei in modo non funzionale:

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

Prova questa funzione:

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

Probabilmente non è la migliore soluzione funzionale, ma dovrebbe fare il suo lavoro. Dubito che esista una soluzione puramente funzionale che corrisponderà a quella imperativa per la velocità.

Spero che sia d'aiuto.

Nota: la funzione non è attualmente testata (sebbene sia stata confermata la compilazione). Fammi sapere se non fa proprio quello che dovrebbe. Inoltre, osserva che le variabili i e j non si riferiscono alle stesse cose del tuo post originale.

Answer 2

Non conosco F #, ma posterò un po 'di Haskell e spero che sia abbastanza vicino da usare. (Ho solo VS 2005 e una versione antica di F #, quindi penso che sarebbe più confuso pubblicare qualcosa che funzioni sulla mia macchina)

Vorrei iniziare pubblicando un'implementazione Python del tuo pseudocodice per assicurarmi di ottenere la risposta giusta:

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

Ora convolve ([1,1,1], [1,2,3]) fornisce [3, 5, 6, 3, 1] . Se questo è sbagliato, per favore dimmelo.

La prima cosa che possiamo fare è trasformare il loop interno in uno zipWith; stiamo essenzialmente aggiungendo una serie di righe in un modo speciale, nell'esempio sopra: [[3,2,1], [3,2,1], [3,2,1]] . Per generare ogni riga, comprimeremo ogni i nel segnale con il filtro invertito:

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

(Nota: secondo un rapido google, zipWith è map2 in F #. Potrebbe essere necessario utilizzare una comprensione dell'elenco anziché repeat ) Ora:

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

Per ottenere questo per tutti i i , dobbiamo mappare il segnale:

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

Buona. Ora abbiamo solo bisogno di un modo per combinare correttamente le righe. Possiamo farlo notando che la combinazione sta aggiungendo la nuova riga all'array esistente, ad eccezione del primo elemento, che è bloccato in primo piano. Ad esempio:

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

Quindi dobbiamo solo scrivere del codice che faccia questo nel caso generale:

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

Ora che abbiamo un modo per generare tutte le righe e un modo per combinare una nuova riga con un array esistente, tutto ciò che dobbiamo fare è incollare i due insieme con una piega:

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

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

Quindi questa è una versione funzionale. Penso che sia ragionevolmente chiaro, purché tu comprenda foldr e zipWith . Ma è almeno finché la versione imperativa e come altri commentatori hanno detto, probabilmente meno efficiente in F #. Ecco il tutto in un unico posto.

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)

Modifica:

Come promesso, ecco una versione F #. Questo è stato scritto usando una versione seriamente antica (1.9.2.9) su VS2005, quindi fai attenzione. Inoltre non sono riuscito a trovare splitAt nella libreria standard, ma poi non conosco bene F #.

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

In effetti, generalmente si desidera evitare loop (semplici, nidificati, qualunque cosa) e qualsiasi cosa mutabile nella programmazione funzionale.

Sembra esserci una soluzione molto semplice in F # (e probabilmente quasi ogni altro linguaggio funzionale):

let convolution = Seq.zip seq1 seq2

La funzione zip combina semplicemente le due sequenze in una delle coppie che contengono l'elemento da seq1 e l'elemento da seq2 . Come nota, esistono anche funzioni zip simili per i moduli List e Array , nonché varianti per combinare tre liste in triple ( zip3 ). Se desideri che Tom ore comprenda generalmente (o "convoluta") elenchi in un elenco di n-tuple, dovrai scrivere la tua funzione, ma è piuttosto semplice.

(Ho seguito questa descrizione di convoluzione tra l'altro - dimmi se vuoi dire qualcos'altro.)

Answer 4

In linea di principio, dovrebbe essere possibile utilizzare la Trasformata di Fourier (veloce) o la Trasformazione di coseno (discreta) correlata per calcolare la convoluzione di due funzioni in modo ragionevolmente efficiente. Si calcola la FFT per entrambe le funzioni, le si moltiplica e si applica la FFT inversa sul risultato.

background matematico

Questa è la teoria. In pratica, probabilmente è meglio trovare una libreria matematica che la implementa per te.