4
4
M
M
e
e
s
s
c
c
o
o
l
l
a
a
m
m
e
e
n
n
t
t
i
i
c
c
o
o
n
n
v
v
o
o
l
l
u
u
t
t
i
i
v
v
i
i
e
e
d
d
e
e
s
s
t
t
r
r
a
a
z
z
i
i
o
o
n
n
e
e
d
d
e
e
l
l
l
l
e
e
s
s
o
o
r
r
g
g
e
e
n
n
t
t
i
i
4.1 Definizione del problema
l problema generale del recupero dei segnali sorgente a partire da un set di segnali “osservati”, come già detto nel capitolo precedente, passa sotto il nome di Blind Source Separation (BSS). Questo problema viene risolto tramite l’implementazione di tecniche che ricercano l’indipendenza statistica delle sorgenti (ICA).
In molti casi di interesse pratico, tuttavia, si presenta un’ulteriore difficoltà e cioè la presenza contemporanea sia di un meccanismo di convoluzione sia di uno di mescolamento lineare. Questo determina il fallimento delle comuni tecniche di BSS e impone un cambiamento di approccio nello stimare il nuovo modello.
Il motivo fisico in base al quale si manifesta tale tipo di “mescolamento convolutivo” ( in letteratura: Convolutive Mixing) è ben conosciuto e varia a seconda della natura fisica dei segnali che si stanno investigando. Ad esempio, nel classico problema del cocktail-party o più in generale per i segnali acustici-vocali raccolti da microfoni, i segnali sorgente non giungono ai microfoni allo stesso tempo. Ciò è dovuto al fatto che generalmente i microfoni sono posti a distanza tra loro e quindi, considerata la velocità finita del suono nell’ aria, si verifica un certo ritardo relativo all’acquisizione della medesima sorgente da parte di diversi
microfoni. Nell’ambiente di registrazione, poi, oltre al rumore ci possono essere fenomeni di eco causati da ostacoli o semplicemente da fenomeni di riverbero dovuti alla presenza di mura figura 4.1.
Fig. 4.1 Processo acustico convolutivo
Anche i segnali fMRI possono essere trattati con questo tipo di approccio. Infatti, sebbene molte analisi siano state fatte considerando che la risposta fMRI sia il risultato di un mescolamento istantaneo, spazio variante, di sorgenti statisticamente indipendenti, la natura convolutiva della risposta emodinamica implica che il segnale fMRI ad un dato istante t0 sia la
somma pesata delle precedenti attivazioni nel medesimo voxel per la durata di alcuni secondi. In aggiunta nelle regioni di frontiera è presumibile l’istaurarsi di fenomeni di convoluzione spaziale tra le risposte di voxel adiacenti [2].
verranno usati equivalentemente temini quali separazione dei segnali convoluti, demixin, equalizzazione, Blind deconvolution.
4.2 Modello a singolo canale (SISO)
Il problema della separazione delle sorgenti convolute (Blind deconvolution) si può formulare nella forma base in cui un certo segnale osservato x(t) è pensato essere generato da un unico segnale sorgente s(t) attraverso un processo convolutivo:
∑
∞ −∞ = − = ⊗ = k ks t k a t s t a t x( ) ( ) ( ) ( ) (4.1)Tale tipo di convoluzione che riguarda una sola sorgente nascosta (tramite l’effetto di un solo canale) è anche conosciuto in letteratura col nome di convoluzione a singolo canale.
Ciò sta a significare che versioni ritardate della sorgente sono mescolate assieme attraverso i coefficienti incogniti ak e il nostro scopo consiste nello
stimare la sorgente s(t) a partire dalla conoscenza del solo segnale misurato
x(t). Avremo quindi un solo segnale utile in uscita e da qui deriva il nome di
sistemi SISO (Single Imput Single Output). In altre parole per raggiungere un buon risultato si deve trovare un filtro deconvolutivo tale che si abbia [8] y(t)=
∑
∞ −∞ = − k kx t k h ( ) (4.2)dove y(t) è la stima della sorgente s(t) e gli hk sono i coefficienti (pesi) del
filtro di deconvoluzione che permettono una stima ottima. La scelta degli opportuni filtri risulta quindi critica e viene sempre fatta basandosi sul fatto che questi ultimi siano stabili e cioè a fase minima. Questa semplice considerazione ci aiuta a capire perché spesso sono usati filtri a risposta impulsiva finita (FIR), i quali non danno mai problemi di instabilità. Infatti data la generica forma della somma di convoluzione
y(n) =
∑
−k
kx n k
h ( ) (4.3)
passando nel dominio della z-trasformata si ha
Y(z) = H(z)X(z) (4.4) dove H(z)X(z) non è altro che il prodotto della z-trasformata, rispettivamente, delle sequenze hk e x(n). In particolare gli hk sono chiamati
risposta impulsiva e
H(z) = Y(z)/X(z) (4.5) è chiamata funzione di trasferimento del filtro.
Ora per i filtri FIR si ha X(z) = 1 perciò la funzione di trasferimento non può in alcun caso avere poli che danno origine ad instabilità.
Per stimare i filtri di deconvoluzione, come in (4.3), spesso l’ipotesi di partenza che si utilizza, consiste nel considerare la sorgente statisticamente indipendente e identicamente distribuita come nel classico problema ICA.
4.3 Tipologie di metodi deconvolutivi a singolo canale
4.3.1
Bussgang
L’algoritmo Bussgang è stato uno dei primi tentativi di deconvoluzione cieca a singolo canale utilizzando filtri a risposta impulsiva finita. Tale algoritmo conduce ad un segnale stimato nella forma
∑
− = − = L L k k t x t w t y k( ) ( ) ) ( * (4.6)Dove 2L+1 è la dimensione del filtro FIR e wk*(t) rappresenta il
complesso coniugato dei pesi. E’ evidente che i coefficienti del filtro sono dipendenti dal tempo in quanto devono essere adattati ricorsivamente usando algoritmi del tipo least-mean-square
) ( ) ( ) ( ) 1 (t w t x t k e* t wk + = k +µ − k =−L,...L (4.7)
dove µ rappresenta la velocità di apprendimento (come già visto nel capitolo 2), mentre la funzione errore e(t)=g(y(t))−y(t) è valutata congiuntamente a una opportuna non linearità g. Ancora va notato che le
condizioni di inizializzazione risultano critiche per la convergenza e solitamente vengono scelte in modo tale che
⎩ ⎨ ⎧ ≠ = = 0 0 0 1 ) 0 ( k per k per wk .
Infine imponendo che
{
y(t)y(t k)} {
E y(t)g(y(t k))}
E − ≈ − (4.8)
si ottiene la struttura (4.6). La (4.8) viene rispettata minimizzando una funzione costo (espressa in funzione del segnale y(t) ) del tipo
[
]
}
⎩⎨ ⎧ − = ( ) 2 ) ( p p p t E y tJ γ [9], dove p è un intero positivo e γp una costante
reale nella forma
{
}
{ }
p p p t s E t s E ) ( ) ( 2 = γ (4.9)Naturalmente γp è scelta in modo tale che il gradiente di Jp(t) sia zero
quando si ottiene una perfetta deconvoluzione e cioè quando y(t)=s(t). Utilizzando la (4.9) in accordo al [9] si può dare la seguente forma alla funzione errore e alla rispettiva nonlinearità:
[
p]
p p t y t y t y t e( )= ( ) ( ) −2γ − ( ) (4.10)[
p]
p p t y t y t y t y t y g( ( ))= ( )+ ( ) ( ) −2γ − ( ) (4.11)Un andamento stocastico che soddisfa la relazione (4.8) è definito processo Bussgang.
4.3.2
Riformulazione secondo l’ICA standard
Un’alternativa, teoricamente pratica e intuitiva, per riformulare il problema della BSS convolutiva a singolo canale consiste nel riformulare il problema secondo gli standard dell’ICA. Vale a dire che, supponendo la sorgente statisticamente indipendente ai vari istanti e nongaussiana si può definire il vettore
[
]
T n t s t s t s t ( ), ( 1),..., ( 1) ~s( )= − − + (4.12)formato da n valori ritardati del segnale sorgente e similmente definire il vettore
[
]
T n t x t x t x( ), ( 1),..., ( 1) ~= − − + x . (4.13)In base a queste definizioni si può riscrivere la (4.1) come
s A
x ~
~ = (4.14) valida per un numero di valori finito dell’indice di sommatoria indicato nella (4.1). La matrice
A
nella (4.14) è formata dai coefficienti ak del filtroconvolutivo.
Poiché
A
da origine ad un mescolamento convolutivo lineare, è evidente che dalla (4.14) si può ricercare il segnale sorgente applicando semplicemente un algoritmo standard dell’ICA come quelli visti nel capitolo 3. Infatti il vettore ~ tx( ) consiste semplicemente di vari campioni dellostesso segnale ritardati nel tempo, perciò, stimata una componente indipendente possiamo essere sicuri di avere recuperato il segnale sorgente
s(t), come sarà chiarito più in dettaglio nel paragrafo dei metodi
deconvolutivi a canale multiplo.
4.4 Modello a canale multiplo (MIMO)
Se siamo in presenza di segnali multipli (sistemi Multiple Input Multiple Output) e il mezzo in cui si ha propagazione, congiuntamente ai sensori di rilevamento, determinano un mixing convolutivo, il modello a cui si fa riferimento è raffigurato in figura 4.1
FIG. 4.1 Sistema deconvolutivo MIMO
mentre analiticamente lo stesso modello può utilmente essere scritto come: ) ( ) ( 1 k t s h t x j p j k ikj i =
∑∑
− = per i = 1,…,p (4.15)Gli hikj sono i coefficienti dei filtri FIR del modello convolutivo e per
semplicità implementativa si assume che la somma di convoluzione è estesa su un numero finito di termini k. Inoltre, così come per il problema ad unico canale, ciò che noi osserviamo sono i segnali mescolati xi(t), mentre
il nostro scopo è quello di “recuperare” le sorgenti si(t) (assunte
indipendenti) e tutti i coefficienti hikj che sono incogniti.
Questa operazione di recupero delle sorgenti è effettuata, come mostrato in figura 4.1, tramite una operazione di deconvoluzione di cui i coefficienti
ikj
w rendono conto.
Per invertire la relazione convolutiva (4.15) viene usato un analogo set di filtri FIR così che si ha:
∑∑
= − = p j k j ikj i t w x t k y 1 ) ( ) ( per i = 1,…,p (4.16)Gli yi(t) sono le stime dei segnali sorgente cercati (valutati agli istanti
discreti t) e i filtri di separazione constano di un numero di coefficienti variabile secondo l’accuratezza e la velocità di convergenza desiderata.
4.5 Tipologie di metodi deconvolutivi a canale multiplo
4.5.1 Riformulazione in accordo allo standard ICA
Così come visto per il single channel, anche per il multichannel blind
modo tale da poter applicare gli algoritmi standard dell’Independent Component Analysis (ICA). Solitamente questo metodo di separazione è ottenuto usando algoritmi a due passi, il primo dei quali consiste nel ridurre il mescolamento convolutivo ad un mescolamento istantaneo (privo di effetto memoria), mentre il secondo passo consiste nella separazione del così ottenuto mescolamento istantaneo tramite un qualsiasi algoritmo di standard ICA [10].
Va subito detto che questo tipo di tecnica ha il grosso vantaggio di essere intuitiva e di far uso di semplici statistiche del secondo ordine ma altresì porta ad operare con una grande mole di dati e conseguentemente costringe a tempi di calcolo molto lunghi.
Considerando p sorgenti, supposte statisticamente indipendenti,
T p n s n s n) ( ( ),..., ( )) ( = 1 S e q osservazioni T q n y n y n) ( ( ),..., ( )) ( = 1 Y l’effetto del
canale convolutivo è messo in evidenza dalla figura 4.2
FIG. 4.2 Modello generale
Il mescolamento convolutivo delle sorgenti viene allora espresso dalla relazione vettoriale di dimensione q×1 al tempo n :
∑
−= M i n i
n) () ( )
( H S
o equivalentemente nel dominio della Z-trasformata: ) ( ) ( ) (z H z S z Y = . (4.18)
La matrice H(i) nella (4.17) è scalare, di dimensione q×p e tiene conto dell’effetto convolutivo del mezzo in modo tale che
∑
= − = = M i i ij z i z h z 0 ) ( )) ( ( ) ( HH risulta la matrice polinomiale di filtri FIR. M è il
grado massimo dei singoli filtri hij(z) (per estensione quindi M è il grado di
) (z
H ), mentre S(n−i) è il vettore p×1 delle sorgenti. H(i) perciò non è altro che il valore scalare della matrice polinomiale H(z) calcolata al tempo discreto i.
Considerando ora N+1 osservazioni di Y(n) (per ipotesi supponiamo che
N>q senza perdere di generalità) e usando la seguente notazione
⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ − = ) ( ) ( ) ( N n n n N Y Y Y e ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ − − = + N M n n n N M ( ) ( ) ( S S S . (4.19)
il modello (4.17) può essre riscritto come:
) ( ) ( ) (n N N M n N =T H S + Y (4.20)
dove TN(H) è la matrice di Sylvester associata a H(z) di dimensione ) 1 ( ) 1 ( + × + + × N p M N
⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ − = H(M) . . . H(1) H(0) 0 . . . . . 0 0 . . . . . . . . 0 . . . 0 H(M) 1) H(M . . . H(1) H(0) 0 0 . . . 0 0 H(M) . . . H(2) H(1) H(0) H TN( )
Senza ulteriormente appesantire la notazione matematica è ora evidente che la separazione delle sorgenti sarà raggiunta stimando SM+N(n). Di
conseguenza la separazione può essere fatta determinando una )
1 ( ) 1
(M +N + p×q N+ matrice inversa G della matrice di Sylvester, che esiste solo se TN(H) ha rango pieno. Il rango di TN(H) è dato dalla
relazione:
(
)
∑
= + + = p i i N p N M Rank 1 ) 1 ( ) (H T (4.21)dove Mi è il grado dell’i-esima colonna di H(z) e quest’ultimo è dato dal
più alto grado dei filtri FIR presenti in quella colonna.
Usando la (4.21) è facile provare che la matrice di Sylvester ha rango pieno e quindi è invertibile se e solo se ogni colonna di H(z) ha il solito grado e N ≥Mp. Se ciò non è verificato è comunque possibile raggiungere il nostro obiettivo utilizzando una diversa parametrizzazione sempre basata sulla trasformazione di Sylvester [12].
Assumendo allora che G sia la matrice inversa di TN(H), si ha che ) 1 ( ) ( = M+N+ N H I
GT (dove in pedice a I è rappresentata la sua dimensione), che implica (vedi Fig. 4.3)
) ( ) (n M N n N = S + GY ) 1 ( ) 1 (n+ = M+N n+ N S GY . (4.22)
Denotando ora con Gi l’i-esimo blocco di righe
I di G ed usando la (4.22)
FIG. 4.3 La matrice diagonale ablocchi GTN(H) nel caso di due sorgenti
si può dimostrare che:
I
i
0 G G G = ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ + − + − + − + − = + + ) 1 ( 0 . . . 0 ) ( ) 1 ( . . . 0 0 . . . . . . . . . . . . . . . . . . . 0 ) ( ) 1 ( 0 . . . 0 ) ( ) 1 ( 0 . . . 0 ) ( ) ..., , ( 1 2 ( 1) n Y n Y n Y n Y n Y n Y n Y n Y N N N N N N N N N M GY
Qui G =(G1,G2,...,GM+N+1) è una matrice p×q(N +1)(M +N+1) e )
Y(
Y = n è una matrice q(N +1)(M +N+1)×(N+M). Si può così definire una funzione costo quadratica
∑
= 1 0 n n n G Y Y G T T n n) ( ) ( (4.23)dalla cui minimizzazione si ricava l’inversa della matrice di Sylvester. Questa inversa, tuttavia, non è la semplice matrice pseudo-inversa diTN(H)
bensì una matrice G (di dimensioni (M +N+1)p×q(N+1)) che soddisfa:
⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ = A A A A H GT 0 . . 0 0 0 . . . 0 . . . . . . . . . . . . . . . . 0 0 . . . 0 ) ( N (4.24)
dove A è una matrice scalare p× p. E’ evidente ora che usando la (4.24) e la (4.20) si può trovare che
⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ − − = ) ( . . . ) ( ) ( N M n n n N AS AS GY (4.25)
cosa che corrisponde ad avere ricondotto il problema ad un semplice mescolamento lineare delle sorgenti tramite la matrice scalare A. Quindi alla fine i segnali sorgente possono essere stimati applicando un algoritmo per la separazione istantanea alle prime p righe della (4.25) e cioè ad AS(n).
Resta da notare che la minimizzazione della (4.23) è il cuore nevralgico di tutto il metodo, in quanto il numero di dati coinvolti è grande (l’algoritmo è di tipo batch) anche in presenza di poche sorgenti. Come da noi provato, infatti, indipendentemente dal criterio usato per la minimizzazione, l’algoritmo converge in tempi non inferiori all’ora e per evitare la convergenza sulla soluzione spuria G = 0 bisogna ulteriormente appesantire i calcoli aggiungendo specifiche costrizioni atte anche a garantire che la matrice
A
risulti invertibile. Una soluzione utile è quella di imporre iterativamente che p T n G I R G1 Y( ) 1 = (4.26) dove{
T}
N N n n E n) ( ) ( ) ( Y Y RY = è la matrice di covarianza di YN(n), Ip è la matrice identica p×p.Se la (4.26) è soddisfatta allora p T T n n G AR A I R G1 Y( ) 1 = S( ) = (4.27) in cui
{
T}
n n E n) ( ) ( ) ( S SRS = è la matrice di covarianza dei segnali sorgente che risulta di rango pieno come conseguenza dell’iporesi sull’indipendenza statistica delle p sorgenti. Quando la (4.27) viene soddisfatta allora la matrice
A
risulta invertibile e la piena separazione delle sorgenti può essere raggiunta.4.5.2
Metodi nel dominio della frequenza
Un altro modo di affrontare il problema della BSS convolutiva consiste nello sfruttare il dominio frequenziale e ricondurre il modello ad un semplice mescolamento istantaneo delle sorgenti. Formalmente, infatti, applicando la trasformata di Fourier ad ambo i membri dell’equazione (4.15) si ottiene:
∑
= = n j i ij i f A f S f X 1 ) ( ) ( ) ( (4.28)dove Si( f) è la trasformata di Fourier delle sorgenti originarie e Aij( f) è la rappresentazione frequenziale del filtro FIR relativo al canale i-esimo e applicato alla sorgente j.
In questa maniera il modello convolutivo espresso dalla (4.28) diventa un mescolamento istantaneo e lineare nel dominio della frequenza, in accordo
alla regola generale che la convoluzione temporale si trasforma in prodotto nel dominio frequenziale. L’unica complicazione da affrontare è che la matrice di mescolamento risulta ora funzione della frequenza mentre nel problema ICA standard è una matrice di costanti. Ai dati così riorganizzati si può applicare un algoritmo di separazione istantanea (quale ad esempio il FastICA presentato nel capitolo 3) ottenendo le componenti indipendenti separate direttamente nel dominio frequenziale. A questo punto applicando semplicemente la trasformata inversa di Fourier a tutte le componenti frequenziali relative a ciascuna componente indipendente si ricostruiscono i segnali sorgenti cercati, nel dominio temporale.
4.5.3 Metodi nel dominio del tempo
Un elegante e sistematico approccio per ottenere la separazione di sorgenti convolute è quello basato sul metodo del gradiente naturale direttamente nel dominio del tempo. In pratica i filtri deconvolutivi sono rappresentati come una sequenza di matrici scalari Wk(t), al tempo discreto
t e al ritardo temporale k. Il risultato della deconvoluzione tramite queste
matrici risulta quindi:
∑
= − = L k k t t k t 0 ) ( ) ( ) ( W x y (4.29)Dove x(t−k) è il vettore n-dimensionale dei dati, mescolati convolutivamente, che sono stati acquisiti. Il vettore y(t), che rappresenta
l’output del sistema e quindi la stima delle sorgenti si(t) (con i = 1,…,m), ha
in generale dimensione m<n.
Questa notazione matriciale permette una derivazione di un algoritmo di separazione per il quale le matrici di deconvoluzione sono ricavate con una regola di apprendimento tale che
) ( )) ( ( ) ( ) (t k t y t L k t k W g W W ∝ − − ∆ (4.29)
Nella (4.29) g è un vettore di nonlinearità (che rappresenta la distribuzione statistica delle sorgenti si da stimare) la cui scelta risulta critica
per la giusta convergenza dell’algoritmo, come vedremo più in dettaglio nel prossimo capitolo.
