1
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal1
Bloc 3 : Traitement et analyse
Semaine 11: Filtrage optimal
GEI 756
Processus stochastiques et traitementstatistique de signaux aléatoires
Denis Gingras
Hiver 2013
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal2
Plan du cours
Introduction Filtrage adapté pour la détection Principe d’orthogonalité Filtrage optimal FIR pour l’estimation linéaire Prédiction linéaire Équations de Wiener-Hopf Filtrage optimal IIR pour l’estimation linéaire Filtrage IIR causal Filtrage IIR non-causal Filtrage récursif scalaire (filtrage séquentiel) Prédiction séquentielle (cas linéaire) Filtrage récursif vectoriel (filtre de Kalman) Décomposition de Wold
2
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal3
IntroductionQu’est-ce que le filtrage optimal?
Conception de filtres non pas à l’aide de spécifications fréquentiellesou temporelles comme dans le cas déterministe, mais plutôt enfonction des moments statistiques des signaux d’entrée et de sortie(ou de l’erreur entre les deux).
À quoi ça ressemble?
Ce sont des filtres FIR ouIIR normaux. Dans le casdu filtrage séquentiel(adaptatif), les coefficientsévoluent avec le temps.On peut chercher les An et
Bn qui minimisent e[n]par exemple suivant lafigure.
A quoi ca sert?
Réduction de bruit, prédiction, filtrage inverse, identification, codage,détection, etc.
x n y n e n c n
ˆ 1y n
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal4
IntroductionQuelques notes sur le filtrage optimal
Le filtrage optimal linéaire est basé en grande partie sur le principe d’orthogonalité .
La prédiction linéaire est un cas simple particulier du filtrage optimal
Dans tous les cas on suppose les moments statistiques connus. En pratique il fautles estimer avec des méthodes comme celles expliquées par exemple dans le coursprécédent.
On suppose les signaux et les bruits stationnaires, donc on suppose que lesmoments statistiques sont invariants dans le temps.
Les filtres étudiés ici ne sont pas adaptatifs dans le temps. De plus, ils effectuent lefiltrage en lot (sauf les filtres récursifs à la fin du cours qui sont séquentiels, ex.Kalman). Ils sont optimisés en fonction des moments d’ordre un et deux des signauxet bruits aléatoires. Pour une trajectoire particulière du signal ou du bruit, le filtren’est pas nécessairement « optimal ». Le filtre est « optimal » pour l’ensemble detoutes les trajectoires possibles. Les données utilisées pour construire et optimiser lefiltre ne sont pas les mêmes que celles pour lesquelles le filtre est utilisé.
3
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal5
Filtre adaptéDéfinitionLe filtre adapté (ne pas confondre avec filtrage adaptatif) s’applique dans
le cas de signaux s(n) connu a priori noyé dans du bruit additif. On
l’utilise principalement pour la détection optimale d’un signal bruité à un
certain temps nP lorsque nous connaissons les propriétés statistiques du
bruit additif η(n). Nous allons démarrer avec le cas d’un signal
déterministe. Soit le signal d’origine s(n) non nul pour P valeurs de n0 à
np= n0 +P. ( ) ( ) ( )x n s n n
Si l’on définit les vecteurs suivants,
(0), (1),... ( 1)T
h h h h P 0 0( ), ( 1),... ( )T
Px x n x n x n
0 0( ), ( 1),... ( )T
Ps s n s n s n 0 0( ), ( 1),... ( )T
Pn n n
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal6
Filtre adapté
Durée du signal P
Exemple de signal observé à durée finie
4
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal7
Filtre adapté
Filtre adapté et sa réponse au signalbruité
Signal d’entrée bruité
Décision
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal8
Filtre adaptéLe filtre adapté sera calculé en maximisant le rapport signal sur bruit
(RSB=SNR) au temps np i.e.:
Soit y la réponse du filtre adapté, elle se décompose donc en 2 parties:
1
0
( ) ( ) ( ) ( ) ( )P
T TP P s P b P
k
y n h k x n k h x x h y n y n
et
Où la notation tilda « ~ » indique le renversement du vecteur tel que nousavions vu au début du semestre.
( ) T Ts Py n h s s h ( ) T T
Py n h h
2
2
( )
( )
s P
P
y nRSB SNR
E y n
( ) ( ) ( ) ( ) ( )P P Py n s n h n n h n
5
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal9
Filtre adaptéUtilisant ces définitions vectorielles, le RSB (SNR) devient alors,
*H TRSB h s s h SNR
Où le terme du dénominateur vient de,** * *T HE E R R R
Par ailleurs, afin de trouver de façon unique la solution, on doit fixerle gain. On peut par exemple choisir les coefficients du filtre de tellesorte que la puissance du bruit à la sortie soit normalisée, i.e.
1Hh R h
Le RSB (SNR) devient alors,
*2 * * *
*
( )T T T T H T
s P
T H H H
h s s h h s s h h s s hy nRSB SNR
h R h h R h h R h h R h
Car La matriceest Toeplitz.
Qui sera la contrainte duproblème d’optimisation
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal10
Dans l’équation caractéristique généralisée, , λ correspond
à la valeur propre généralisée.
Filtre adapté
Il s’agit donc de maximiser le RSB avec contrainte. Utilisant unmultiplicateur de Lagrange, nous formons la fonction objectif suivante,
*H TRSB h s s h
Une condition nécessaire pour l’optimisation est,
Ayant la contrainte, si on multiplie chaque côté de l’équation
résultante par hH , on obtient,
Autrement dit, le RSB (SNR) est maximal si λ est maximal.
* 1H T HQ h s s h h R h
*
* *0 T T
hQ s s h R h s s h R h
*H T Hh s s h h R h RSB
* Ts s h R h
6
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal11
Filtre adapté
Le vecteur propre généralisé h, est proportionnel à
En effet, en remplaçant h par ce terme, on obtient,
Puisque le RSB = λ et avec la contrainte , alors,
Dans le cas d’un bruit blanc, nous avons un problème de valeurpropre/vecteur propre classique. Nous obtenons alors,
1 *R s
1 * 1 *1 1ˆadp
MAX MAX
h R s R sRSB
* * 1 * 1 * *T Ts s h R h s s R s R R s s
* 1 * * 1 * 1T T HMAXs s R s s s R s s R s
22 1 2 2 *0 0 0 0
ˆ, , / /MAX MAX adpR I R I RSB s h s s
1Hh R h
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal12
Filtre adapté
Il s’agit donc d’un problème d’optimisation classique, où on veutmaximiser le rapport signal à bruit (SNR) sujet à la contrainte:
La solution du problème d’optimisationnous donne sous forme vectorielle :
2( ) (0) 1
pp n n
E y n R
1Hh R h
1 *
1
ˆadp H
R sh
s R s
NB: On verra plus loin que, dans le cas où le signal est aléatoire, mais
indépendant, il faut travailler avec la matrice de corrélation du signal, Rs ,mais
la solution habituellement n’est pas analytique.
adaptation
7
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal13
Filtre adaptéExemple: Soit un signal transitoire déterministe de la forme,
La constante de normalisation est donnée par,
La réponse impulsionnelle du filtre adapté sera proportionnel au signaltronqué inversé. Nous aurons
0
0( ) ( ), 1n ns n a u n n a
Où u(n) est l’échelon unitaire. Trouvons d’abord le filtre adapté pour un
bruit blanc. Si le signal est considéré comme étant égal à zéro aprèsune longueur finie de P instants, alors puisque,
*0
ˆ /adph s s
1
0
ˆ , 0 1P n
adp
ah n P
s
1/21/2 21
2
0 0 0 20
1
1
PPk
k
as a
a
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal14
Filtre adapté
Le rapport signal sur bruit quant à lui est donné par,
2 2
2 2 20 0
1 1
1
Ps aRSB SNR
a
Signal d’entrée transitoire àdurée finie Filtre adapté résultant
8
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal15
Filtre adapté
Exemple: soit le même signal
À l’aide de la relation I=R-1R, il peut être montré que l’inverse de la
matrice de corrélation correspondante est de la forme,
Considérons maintenant le cas où le bruit est encore additif etstationnaire mais coloré avec la fonction de corrélation donnée par,
20
2( )
1
l lR l
( ) ( ), 1ns n a u n a
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal16
Filtre adapté
Les coefficients du filtre adapté sont donc donnés par,
La réponse impulsionnelle du filtre adapté devient donc de la forme, (iciP=5= nombre de coefficients)
1 *1ˆadp
MAX
h R sSNR
MAX
2 4 3 5
20
1ˆ 1 , 1 3n n nadp
MAX
h n a a a nSNR
4 3
20
1ˆ 0adp
MAX
h a aSNR
20
1ˆ 4 1adp
MAX
h aSNR
9
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal17
Filtre adapté
Pour complètement spécifier le filtre, , il nous reste à trouver la racinecarrée du RSB (SNR).
Pour ce faire, on doit factoriser l’inverse de la matrice de corrélation du bruit qui,heureusement, est de la forme d’une matrice en bande. Ceci donne,
1HSNR s R s
MAX
NB: Factoriser ici veut dire décomposer en un produit de deux matrices
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal18
Filtre adapté
Avec la substitution suivante
Avec cette factorisation, le SNR peut alors s’exprimer par (ici pour le casP=5),
2( 1) 2( 1)2' '
22 20
1 11
1 1
P PT a a
SNR s s aa a
Pour le cas de P quelconque, nous avons la relation générale
2 2' ' 2 4 6 8
20
11 1 / 1
T
SNR s s a a a a a a
MAX
MAX
( ) ( ), 1ns n a u n a
10
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal19
Filtre adapté
La formulation du filtrage adapté peut également être utilisée dans le casoù le signal est aléatoire. Nous devons utiliser dans ce cas sa fonction de
corrélation. On suppose que le signal aléatoire s(n) est indépendant du
bruit additif η(n). Le signal d’origine s(n) est non nul pour P valeurs de
n0 à np= n0 +P. Reprenant la même démarche que pour le cas du signal
déterministe précédent, le rapport signal sur bruit à maximiser devient,
2
2
( )
( )
Hs P s
H
P
E y n h R hSNR
h R hE y n
De façon similaire à la section précédente, la réponse impulsionnelle dufiltre doit satisfaire les équations
, 1HsR h R h h R h
Cas d’un signal aléatoire
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal20
Filtre adapté
Avec la dernière contrainte, le RSB vaut donc,
Si le bruit est blanc,
HMAX MAX sSNR h R h
2 1 20 0,R I R I
2 '0sR h h h Alors,
La réponse impulsionnelle du filtre adapté est donc le vecteur proprecorrespondant à la valeur propre maximale de la matrice de corrélationdu signal, ce à quoi on s’attendait intuitivement.
Lorsque le bruit est coloré: On peut diagonaliser la matrice decorrélation en matrices de vecteurs propres et de valeurs proprescomme suit, *TR E E
Pour « blanchir » le bruit et ramener le problème à celui plus simpledu bruit blanc, nous allons utiliser la transformation de Mahalanobis.
11
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal21
Filtre adapté
Cette transformation permet d’effectuer une diagonalisation unitaire dela matrice de corrélation du bruit de la manière suivante (notez la formede l’inverse),
' 1/2 1/2 *Tx R x E E x
Avec les nouvelles données transformées, la matrice de corrélation dusignal est également modifiée comme suit,
Notez que la transformation est symétrique hermitienne, i.e,
'
1/2 1/2ss
R R R R
*1/2 1/2T
R R
Le filtre adapté, représenté dans ce nouveau système de coordonnéesest donc le vecteur propre correspondant à la valeur propre maximale dela matrice de corrélation transformée du signal.
'
' '
sR h h
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal22
Filtre adapté
La sortie du filtre adapté s’exprime donc par,
' ' ' 1/2( )T T T
Py n h x h R x h x
où la réponse impulsionnelle du filtre est,1/2 'h R h
Interprétation géométriquedu filtre adapté pour unsignal aléatoire noyé dansdu bruit blanc. La réponseimpulsionnelle du filtreadapté correspond auvecteur propre principal lelong de l’axe majeur del’ellipse de la matrice decorrélation du signal
Ellipse de la matricede corrélation dusignal
12
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal23
Filtre adapté
Les deux figures illustrent l’effet « blanchissant » d’une transformationde Mahalanobis sur la matrice de corrélation du bruit. L’ellipse du bruit« blanchi » devient un cercle.
NB: La transformation de Mahalanobis s’utilise également pour le casd’un signal déterministe noyé dans un bruit coloré.
Avant la transformation Après la transformation
La « lessive » de Mahalanobis -:)
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal24
Principe d’orthogonalité
*
1 ... na a1
...
n
x
x
2 2 2ˆeE y y E e
x1
x2
y
y
Le théorème découlant du principe d’orthogonalité est essentiel aux démarchesqui mènent aux solutions des filtres optimaux. Il peut s’illustrer à l’aide du
problème linéaire suivant. Soit les v.a. x1, x2,…, xn centrées constituant des
éléments d’un espace vectoriel (espace d’Hilbert). L’estimé linéaire de la v.a. yen fonction de aura la forme,
On veut minimiser l’EQM (MSE)
Prenons l’exemple tel qu’illustré à la figure où
les x1 , x2 et y sont des vecteurs 2D
NB: Si les observations ne sont pas centrées, on ajoute à l’équation précédente
un terme constant b, i.e., *Ty xb m a m
*ˆ Ty a x
x
13
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal25
Principe d’orthogonalité
Pour n=1
(une seule observation)
Pour n=2
(deux observations)
Pour minimiser , en doit être orthogonal à et par
conséquent aux xn (on remarque que est la projection de y sur le
sous-espace x1...xn). Il s’ensuit que (théorème de projection),
2 2ˆeE y y
yy
* * * *ˆ ˆ0, 1,2,... 0i iE x e E x e i n E ye E y e Et l’erreur minimisée (EQM),
2 * * * * *ˆ ˆ( )MINe E y y e E y e E y e E y e E ye
* cosee e y e y
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal26
Principe d’orthogonalité
L’erreur minimisée (MSE) s’écrit,
* Hxx xyE xy E xx a R a r
2 * * 2 *( )MIN
H Te y xyE ye E y y x a r a
Sous forme matricielle, le théorème de projection devient,
* * *( ) ( ) 0H HE xe E x y a x E x y x a
Le principe d’orthogonalité correspond donc au théorème de projection lorsqueles v.a. correspondant aux observations sont interprétées comme des vecteursdans un espace vectoriel où un produit scalaire est défini (espace d’Hilbert) .
Notez que dans les figures précédentes y est non-coplanaire avec les v.a. x1 et
x2 . Par contre, l’estimé de y , combinaison linéaire des observations est donc
coplanaire avec celles-ci. Dans le d’un modèle linéaire, le principe d’orthogonalitéest une condition suffisante et nécessaire à l’atteinte de la solution optimale
(minimum global).
14
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal27
Filtrage optimal
Communément, un des filtresoptimaux les plus importants enestimation linéaire est le filtre deWiener. Dans sa forme la plusgénérale, il consiste en un signald’entrée, ,
Le but ici est de concevoir un filtre linéaire à temps discret de telle manière que
le signal à sa sortie correspond à l’estimation du signal désiré minimisant
l’erreur quadratique moyenne (MSE ou EQM). Pour ce faire on doit calculer les
coefficients du filtre de façon à ce que l’EQM soit la plus petite possible.
Il existe diverses structures du filtre de Wiener (notamment FIR et IIR).
Filtreoptimal
une réponse « désirée » à la sortie, nommée d(n), et un filtre linéaire de réponse
impulsionnelle h(n). Ce filtre est alimenté à l’entrée par x(n) pour produire un signal
de sortie y(n). La différence entre le signal à la sortie du filtre, y(n) et le signal
désirée (signal cible) , d(n), correspond à l’erreur d’estimation, e(n).
( )bruit n
( )s n
( ) ( ) ( )x n s n n
( )h n
( ) ( ) ( )x n s n n
ˆ( ) ( )y n d n
ˆ( ) ( ) ( )e n d n d n
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal28
Filtrage optimal FIR
Commençons par le cas général du filtrage FIR optimal.
Σ
Filtre( )x n
( )d n ( )e n
ˆ( )d n
Avec cette structure,on peut résoudredivers types deproblèmes:
Nous allons d’abord étudier l’équation de Wiener-Hopf
Problème Signal observé Signal désiré
Filtrage x[n]=s[n]+η[n] d[n]=s[n]
Prédiction x[n]=s[n]+η[n] d[n]=s[n+p]; p > 0
Lissage x[n]=s[n]+η[n] d[n]=s[n-q]; q > 0
Prédiction linéaire x[n]=s[n-1], sansbruit explicite !
d[n]=s[n]
d[n] est le signal désiré
η[n] est un bruit additif
x[n] est le signal observé
est le signal estimé d n
NB: Nombre fini decoefficients
Σ
( )n
( )s n
_
+
ˆe n d n d n
15
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal29
Filtrage Optimal FIR
On veut minimiser l’EQM:
Pour estimer les coefficients du filtre, on veut minimiser l’EQM. En appliquant lethéorème d’orthogonalité, on arrive aux équations de Wiener-Hopf:
Pour x[n] complexe et
h[n,k] variant dans le
temps on a:
Pour x[n] réel et h[n]invariant dans le temps onarrive à:
0,1... 1i P
Avec le théorèmed’orthogonalité
Dans le cas général, l’estimé peut se faire à l’aide d’un filtre variant dansle temps:
*
1* *
0
0
( , ) ( , ) ( , )P
xx dxl
E x n i e n
R n i n l h n n l r n n i
1
2 * *
0
(0) ( ) ( )P
e d dxl
E d n e n R h l r l
1
0
( ) ( ) ( )P
xx dxl
R l i h l r i
NB: Nombre fini decoefficients
1
1 0
ˆ ( , ) ( ) ( , ) ( )n P
k n P l
d n h n k x k h n n l x n l
22 ˆE e n E d n d n
0,1... 1i P
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal30
Filtrage Optimal FIR
P étant le nombre de coefficients, on peut donc écrire sous forme matricielle:
Pour obtenir ces équations sous forme matricielle, regardons à nouveaul’estimé qui peut s’écrire sous la forme générale,
1
1 0
ˆ ( , ) ( ) ( , ) ( )n P
k n P l
d n h n k x k h n n l x n l
ˆ ( )T
d n x n h
Où,
( ) ( ), ( 1),... ( 1) ,
( , ), ( , 1),... ( , 1) ,
( ), ( 1),... ( 1) ,
T
T
T
x n x n x n x n P
h h n n h n n h n n P
h h n h n h n P
vecteur renversé
variant
invariant
En appliquant le principe d’orthogonalité, on obtient,
* * * *( ) ( ) ( ) ( ) ( ) 0TE x n e n E x n d n x n h
16
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal31
Filtrage Optimal FIR
Dans le cas stationnaire, les équations de Wiener Hopf deviennentet on trouve les coefficients du filtre optimal avec
Ce qui donne les équations de Wiener Hopf,
Pour le cas stationnaire, le MSE devient,
* * *,xx dx xx dxR h r R h r
*xx xxR R
xx dxR h r
L’erreur quadratique moyenne minimale (MSE) devient (cas général),
2 * *( ) (0) (0)MIN
T Te d dx d dxn R r h R h r
2 * * *( ) ( , ) ( , )MIN
T Te d dx d dxn E d n e n R n n r h R n n h r
1opt xx dxh R r
* * *( ) ( ) , ( ) ( )Txx dxR E x n x n r E d n x n
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal32
et correspond à la fonction objectif à minimiser. On peut introduire alors le conceptde superficie de l’erreur. On peut montrer que la surface de l’EQM dépend du
vecteur h et peut s’exprimer par,
La fonction objectif présente donc une forme quadratique convexe. Il s’agit d’une
parabole dont le minimum se situe au point stationnaire h = hopt, comme on devait
s’y attendre. La solution est unique pour le cas FIR (pas toujours le cas pour lefiltrage IIR) correspondant au filtre de Wiener. Les contours de l’EQM ayant la
même valeur forment des ellipses.
Filtrage optimal FIR
Puisque, l’erreur quadratique moyenne (EQM-MSE) peut s’exprimer
en termes de la matrice d’autocorrélation Rxx et du vecteur de corrélation croisée
rdx,
2 1 *
min(0) T
opt d dx xx dx MINE e f h R r R r EQM
1opt xx dxh R r
*T
opt opt xx optf h f h h h R h h
ˆe n d n d n
17
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal33
Outre la translation occasionnée par (h - hopt), on peut effectuer une
rotation à l’aide des vecteurs propres de la matrice d’autocorélation.
HxxR E E
Si on définit Z = EH (h - hopt), on peut exprimer l’EQM sous une forme
canonique,
Les nouveaux axes de la représentation sont spécifiés par les vecteurspropres et l’excentricité des ellipses dépendent de la différence entre lesvaleurs propres. Ainsi, dans cette même veine, on peut aussi utiliser latransformation de Mahalanobis pour “blanchir” l’EQM.
Filtrage Optimal FIR
Hoptf h f h Z Z
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal34
Filtrage Optimal FIR
On peut combiner l’équation de Wiener Hopf avec celle de l’erreur MSE(diapo 31) pour former l’équation augmentée de Wierner Hopf,
Ce système permet de trouver simultanément les coefficients du filtre et l’EQM (MSE).
18
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal35
On veut prédire un signal s[n]avec un filtre de 3ème ordre
(P = 3).
1
0
P
x dxl
R l i h l R i
On applique
Nous disposons de:
0sR l (s[n] et η[n] sont non-corrélés)
On trouve Rx[l] et Rdx[l]
0,1... 1i P
On pose les équations WH
On obtient la solution:
Un exemple numérique:
Filtrage Optimal FIR
( ) ( ) ( )x n s n n
ˆ( ) ( ) ( )e n d n d n( ) ( )d n s n
0
1
2
4 1.6 1.28 2.0
1.6 4 1.6 1.6
1.28 1.6 4 1.28
h
h
h
2(0.8)l
sR l 2R l l
0.3824, 0.2, 0.1176opth
dxR l E d n x n l E s n s n l n l
0 2(0.8) l
dx sR l R l
1 2
2 *
0 0
( ) 0 2 2(0.8) 0.7647P
l
e d dxl l
n R h l R l h l
2(0.8)l
d sR l R l
2(0.8) 2
x
l
s
R l E s n n s n l n l
R l R l l
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal36
On veut prédire un signal s[n]cinq échantillions enavance avec un filtre de 3ème
ordre (P=3).
1
0
P
x dxl
R l i h l R i
On applique
Nous disposons de:
0sR l
(s[n] et η[n] sont non-corrélés)
R l l 2 0.8l
sR l
On trouve Rx[l] et Rdx[l]0,1... 1i P On pose les équations WH
On obtient la solution
Un 2e exemple numérique:
Filtrage Optimal FIR
Filtreoptimal
( )bruit n
( )s n
( ) ( ) ( )x n s n n
( )h n
ˆ( ) ( )y n d n
ˆ( ) ( ) ( )e n d n d n( ) ( 5)d n s n
0
1
2
3 1.6 1.28 0.6554
1.6 3 1.6 0.5243
1.28 1.6 3 0.4194
h
h
h
0.1688, 0.0679, 0.0316opth
5dxR l E d n x n l E s n s n l n l
55 0 2(0.8)
l
dx sR l R l
1 2
52 *
0 0
( ) 0 2 2(0.8) 1.84P
l
e d dxl l
n R h l R l h l
2(0.8)l
d sR l R l
2(0.8)
x
l
s
R l E s n n s n l n l
R l R l l
19
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal37
L’extension multi-capteurs du filtre deWiener (MWF) fonctionne sur le mêmeprincipe que sa version à un capteur.(Données à M dimensions).
Le filtrage repose entièrement sur uneanalyse du second moment dessignaux. Encore une fois, le bruit estassumé non-corrélé avec le signal.
En pratique, un délai ∆ est introduit pour permettre la non-causalité desfiltres hi[n].
1h n
2h n
Mh n
e n
1sx n s
ix n
1x n
2x n
Mx n
n ni i
T
E x n x n E x n x nh n
E x n x n
1 ...TT T
Mh n h n h n
Plusieurs capteurs (multi-canal)
Filtrage Optimal FIR
__
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal38
En conclusion:
L’erreur quadratique moyenne présente une forme quadratique convexeavec un minimum défini par les coefficients du filtre optimal de Wiener
hopt.
h - hopt représente la déviation des coefficients d’un filtre p/r aux
coefficients du filtre optimal de Wiener.
Le locus où l’EQM est à valeur égale a la forme d’une ellipse.
Les vecteur propres de la matrice d’autocorrélation constituent les axes
des ellipses et la variation des valeurs propres indique l’excentricité desellipses. Ainsi lorsque les valeurs propres sont identiques, les loci de l’EQMà valeur égale forment des cercles (hyper-sphères).
Filtrage Optimal FIR
20
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal39
Prédiction linéaire
x n
x n
e n
La prédiction linéaire est un cas spécifique du filtrage optimal Wiener FIRgénéral. Regardons plus en détail ce problème général visant à prédire un signalà partir de ses échantillons passés. On suppose le signal observé stationnaire ausens large. Les coefficients du filtre sont donc indépendants de n.
L’estimé linéaire est de la forme, L’erreur est définie par:
*
1
ˆP
kk
x n a x n k
*0
0
ˆ , 1P
kk
e n x n x n a x n k a
NB: Ici les coefficients du filtre FIR sont:*( ) , 0,1,2,...kh k a k P
La boîte en pointillé constitue le filtre de prédiction de l’erreur -« predictive error filter » (PEF)
IMPORTANT
Ici, x[n]=s[n-1], lebruit d’observationn’est pas explicite dansce modèle.
Ici d[n] = s[n]
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal40
Prédiction linéaire
Puisque le principe d’orthogonalité nous donne,
Pour résoudre le problème de prédiction linéaire, on doit trouver les ak qui
minimisent l’EQM,
*( ) ( ) 0, 1,2,...E x n i e n i P
2 22 ˆ( ) ( ) ( )e E e n E x n x n
Et que
*
1
ˆP
kk
x n a x n k
*0
0
ˆ , 1P
kk
e n x n x n a x n k a
Avec,
21
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal41
Prédiction linéaire
En substituant le modèle pour l’estimé linéaire dans la dernière équation nousretrouvons,
D’autre part, l’erreur minimisée devient,
Sous forme matricielle, nous obtenons les équations normales. Cela s’écrit,
*
0 0
( ) ( ) ( ) 0 0, 1, 2,...,P P
k k xk k
E x n i e n E x n i a x n k a R k i i P
2 *
0
( )MIN
P
e k xk
E x n e a R k
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal42
Les ak doivent satisfaire: 0
0, 1...P
k xxk
a R k i i P
i.e, si par exemple P=3,
1
2
3
0 1 2 1
1 0 1 2
2 1 0 3
xx xx xx xx
xx xx xx xx
xx xx xx xx
R R R a R
R R R a R
R R R a R
La matrice est Toeplitz (car Rxx[n]=Rxx[-n]), on peut utiliser l’algorithme récursif
de Levinson-Durbin pour résoudre le système (ex. voir toolbox Matlab).
Les ak ainsi trouvés minimisent 2 *
0
P
e kk
E x n e n E x n a x n k
1 0 1 2 0
2 1 0 1 0
3 2 1 0 0
xx xx xx xx
xx xx xx xx
xx xx xx xx
R R R R
R R R R
R R R R
Prédiction linéaire
0 0
P P
k k xxk k
a E x n x n k a R k
22
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS GEI756 Bloc 3 Semaine 9
Classification linéaire43
Prédiction linéaireExemple:
2l
xR l
On veut calculer les coefficients du filtre de prédiction linéaire du 2e ordre etla variance de l’erreur de prédiction correspondante. Dans ce cas, lescoefficients de corrélation requis sont:
1 1 0.5, 2 2 0.25x x x xR R R R
Les équations normales ont alors la forme:2
1
2
1 0.5 0.25 1
0.5 1 0.5 0
0.25 0.5 1 0
a
a
On obtient les coefficients du filtre avec:1
2
1 0.5 0.5
0.5 1 0.25
a
a
Ce qui nous donne: 0 1 21, 0.5, 0a a a
La variance de l’erreur de prédiction est donnée par,
21 20 1 2 1 1/ 4 0 0.75x x xR a R a R
Puisque c’est un cas réel, alors:
, 0,1, 2k kh a k
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal44
Prédiction linéaireNote sur les e[n]
Si à chaque nouvelle observation n on permet à l’ordre de
prédiction P d’augmenter (on a plus d’information), pour
Ordre P:
Ordre P+1:
Si 0
ˆP
kk
e n x n x n a x n k
alors
1... 0E e n x n P
1 0... 0E e n x n P
0
1 1P
kk
E e n e n a E e n x n k
1 0E e n e n
Interprétation:
Les échantillons du signal d’erreur sont orthogonaux entre eux; ilsreprésentent seulement la nouvelle information du signal x[n] (sesinnovations). L’erreur e[n] est ainsi un bruit blanc et n’a pas demémoire.
23
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal45
Le filtrage de Wiener FIR en général offreune solution optimale dans le sens del’EQM. En prédiction linéaire, on se base surune modélisation du signal observé commeun processus auto-régressif (AR) que nousverrons plus tard.
À partir de cette modélisation on construit lefiltre PEF (filtre de prédiction de l’erreur).
x n x n
On calcule à l’aide des coefficientsde prédiction linéaire du filtrel’estimé du signal d’entrée. 1
( )( )
HA z
Prédiction linéaire
*
1
( ) ( )P
xx k xxk
R i a R i k
*
1
P
kk
x n a x n k
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal46
Prédiction linéaire
Comme e[n] représente les innovations de x[n] (son autocorrélation Ree[l]est nulle sauf pour l=0 ), celui-ci est une version « compressée » de x[n],c-à-d moins les redondances. Sa gamme dynamique devrait donc être plusfaible que celle de x[n].
La prédiction linéare estutilisée pour le codageADPCM (standards ITU-T G.721-723-726 et727):
x n e n
x n
e n
x n
y n
Pour un signalde paroletypique:
600 610 620 630 640 650 660 670 680 690 700
-1500
-1000
-500
0
500
1000
1500
2000
2500
3000 Entrée x[n]
Prédiction xhat
[n]
On peut calculer legain de prédiction,
2
10 210log x
dB
e
G
Ici par exemple,
P=15,GdB=15.6 dB
Exemple: Codage audio ADPCM
24
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal47
Filtrage optimal IIRNous allons maintenant étudier les filtres IIR (Infinite impulse response). Comme
son nom l’indique, la réponse impulsionnelle du filtre a un nombre infini decoefficients. Cependant, pour générer une telle réponse, les filtres IIR requièrentbeaucoup moins de paramètres à estimer que leurs équivalents FIR, ce qui estavantageux. Par contre il faut faire attention aux questions de stabilité.
Filtre de Wiener de type IIR.
Filtrage IIR causalde Wiener
Filtrage IIRnon-causal de Wiener
Filtrage FIR général(eq. Wiener-Hopf)
1
ˆn
k n P
d n h k x n k
ˆk
d n h k x n k
0 0
ˆN M
k kk k
b x n k a d n k
1
0 1
10 1
...
...
NN
mm
b b z b zH z
a a z a z
On cherche h[n]directement
On cherche H(z)
0
ˆk
d n h k x n k
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal48
Filtrage optimal IIR
On cherche une forme analytique du filtre h[l] pour
l=0...∞ . Pour ce faire il faut trouver H(z). L’idée
générale consiste à blanchir le signal.
1. En appliquant le principed’orthogonalité, on peut poser leséquations de Wiener-Hopf pouri=0...∞:
2. À noter que si x[n] est un processus
blanc, la solution h[l] devient triviale:
3. En assumant qu’on peut transformer
x[n] en bruit blanc, on peut trouver
une solution. On peut prouver que, si
on connaît g[n], trouver un filtre
optimal h[n] revient à trouver h’[n] .
* *
0x dx
l
R l i h l R i
0...i
2x oR l l
g[n] h’[n] x n v n d n
h n
??? bruit blanc
2/ 0
0 0dx oR l l
h ll
2' / 0dv vh n R l l
0
ˆk
d n h n k x k
Filtrage Causal de Wiener
Nous allons d’abord considérer le filtrage causal IIR.
NB: La réponse impulsionnelle a unnombre infini de coefficients k 0
25
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal49
Pour transformer x[n] en bruit blanc (i.e., pour trouver g[n] ), nous allons
employer la factorisation spectrale.
On sait que si x[n] est régulier et satisfait la condition de Paley-Wiener, ie:
ln jwxS e dw
Paley-Wiener
alors Sx(z)
peut s’écrire
* *1/x o ca caS z K H z H z
où Hca-1(z) est un filtre blanchissant,
conséquemment, G(z)=Hca-1(z)
Schématiquement, on se rappelle que:
Hca(z)bruit blanc
20o K
phase min.
x n Hca-1(z)
bruit blanc2
0o K
filtre blanchissant
* *1/x o ca caS z K H z H z
Filtrage optimal IIRFiltrage Causal de Wiener
Notez que Hca(z) représente un filtre causal ayant un inverse causal stable Hca-1(z)
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal50
Nous allons d’abord démontrer que si h’(n) est optimal pour l’entréeintermédiaire blanche v(n), alors h(n) est aussi optimal pour l’entrée x(n).
Soit l’erreur,
Selon le principe d’orthogonalité,
Filtrage optimal IIRFiltrage Causal de Wiener
ˆ( ) ( ) ( )e n d n d n
' *( ) ( ) ( ) 0, 0,1,2...opth n E v n i e n i Puisque,
1 1
( ) ( ) ( )
( ) ( ) ( ) ( ) ( )n
k
v n g n x n
x n g n v n g n k v k
En vérifiant la condition d’orthogonalité pour h[n] on a,
* 1 *( ) ( ) ( ) ( ) ( ) 0n
k
E x n i e n g n i k E v k e n
Autrement dit, h[n] ainsi formé est le filtre optimal pour l’entrée x[n].
26
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal51
Trouvons maintenant le filtre pour le bruit blanc v(n). La fonction decorrélation s’écrit,
En appliquant l’équation de Wiener Hopf pour h’(n) on a,
Filtrage optimal IIRFiltrage Causal de Wiener
2( ) ( )v vR l l
Et,
* * *( ) ( ) ( ) ( ) ( ) ( )n
dvk
R l E d n l v n g k E d n l x n k
Évaluons maintenant ,
2 '*
0
( ) ( ) ( )v dvl
l i h l R i
'*
0
( ) ( ) ( )v dvl
R l i h l R i
2'
1( ), 0,1,2,....
( )
0 , 0
dv
v
R n ih n
i
( )dvR n
( ) ( ) ( )n
k
v n g k x n k
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal52
Ou sous forme de la densité spectrale de puissance complexe, on a,
Filtrage optimal IIRFiltrage Causal de Wiener
Nous avons vu que la DSP complexe de x(n) peut être factorisée comme suit,
* *( ) ( ) ( ) ( ) ( )n
dv dx dxk
R l g k R l k g l R l
En choisissant, et , on obtient le filtre optimal
* *1/x o ca caS z K H z H z
* *( ) ( ) (1/ )dv dxS z S z G z
1( ) ( )caG z H z 20v K
'
* * * *0 0
1 ( ) 1 ( )( ) ( )
(1/ ) ( ) (1/ )dx dx
ca ca ca
S z S zH z H z
K H z K H z H z
NB: Le symbole « + » indique que le filtre est calculé par la transformée inversepour seulement n plus grand ou égale à zéro.
Condition de Paley-Wiener
27
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal53
Filtrage optimal IIRFiltrage Causal de Wiener
Lorsque les coefficients du filtre IIR sont trouvés, comme dans le cas dufiltre FIR, on peut calculer l’EQM avec l’équation de la forme,
2 *
0
( ) (0) ( ) ( )MINe d dx
l
n R h l R l
Habituellement, si nous voulons évaluer l’EQM pour le cas d’un filtre IIR,il est plus commode de procéder dans le domaine fréquentiel commesuit. Le principe d’orthogonalité permet d’écrire,
2 * *( ) ( ) ( ) ( ) (0) (0)e de edE d n e n E e n d n R R Or,
** *ˆ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )de d
k
R l E d n l d n d n R l E d n l h k x n k
* *( ) ( ) ( ) ( ) ( ) ( ) ( )de d dx d dxk
R l R l h k R k l R l R l h l
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal54
Filtrage optimal IIRFiltrage Causal de Wiener
La dernière équation nous donne dans le domaine fréquentiel,
2 11(0) ( )
2e de deR S z z dz
j
* *( ) ( ) ( ) (1/ )de d dxS z S z S z H z
Étant donné que Rde(l) est la transformée inverse en z,
Et pour le 2e terme, on a,* *( ) ( ) (1/ ) ( )ed d dxS z S z S z H z
2 11(0) ( )
2e ed edR S z z dz
j
Le contour d’intégration est sur le cercle unitaire qui se trouve dans
la région de convergence (anneau) de Sed(z) ou de Sde(z).
28
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal55
Filtrage optimal IIRFiltrage Causal de Wiener
Exemple numérique: soit le signal habituel avec
Avec les fonctions de corrélations suivantes,
Le bruit et le signal ne sont pas corrélés.
Pour calculer l’équation de WH, on trouve d’abord,
( ) ( )d n s n
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal56
Filtrage optimal IIRFiltrage Causal de Wiener
On calcule ensuite la DSP complexe croisée par la transformée en Z
Et celle de l’entrée
29
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal57
Filtrage optimal IIRFiltrage Causal de Wiener
Par l’expression précédente, on voit que
Puisque tous les processus sont réels, on forme,
On exprime le tout en z-1 et on fait l’expansion par fractions partielles
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal58
Filtrage optimal IIRFiltrage Causal de Wiener
Le 2e terme de l’équation précédente est négligé car il correspond à lapartie non-causale du filtre, (voir factorisation spectrale) nous avonsalors,
Et finalement, la DSP complexe du filtre,
30
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal59
Filtrage optimal IIRFiltrage Causal de Wiener
Calculons maintenant l’EQM pour ce filtre. Nous avons
Puisque tous les processus sont réels,
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal60
Filtrage optimal IIRFiltrage Causal de Wiener
Annulant les termes communs et simplifiant, on obtient,
On peut voir que a seulement un pôle à l’intérieur du cercleunitaire à z=0.8. Évaluant le résidu à ce pôle, nous obtenons alors, ,
1( )deS z z
Pour vérifier le résultat de ce cas particulier, on peut noter que
Et que L’EQM dans le domaine temporel (série géométrique) devient,
31
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal61
En conclusion, on peut résumer l’approche comme suit,
Rappelons:
'H z G z H z
*
* *1/
vd xd
dv dx
dv dx
R l R l g l
R l R l g l
S z S z G z
On cherche:
1caG z H z 2' /dv vh n R l
g[n] h’[n] x n v n d n
'H z G z H z
G z 'H z 2v o oS z K
Et donc finalement:
La notation [H’(z)]+ est nécessaire car h(n) est causal;
[H’(z)]+ correspond donc seulement aux terme causal de
la transformée (i.e. pôles avec |pi|<1, intérieur du cercleunitaire) .
* *
1
1/
dx
o ca ca
S zH z
K H z H z
* *
* *
1 1' / 1/
1/
dxdv o dx
o o ca
S zH z S z K S z G z
K K H z
Filtrage optimal IIR
Filtrage causal de Wiener
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal62
Filtrage optimum IIR
Pour les problèmes où on peut se permettred’avoir une réponse non-causale (traitementen temps différé): nous avons:
On reprend encore une fois les équations de Wiener-Hopf:
ˆk
d n h n k x k
* *x dx
l
R l i h l R i
conjugé x dxl
R i l h l R i
Si on prend les densités spectrales:
x dxR i h i R i
x dxS z H z S z
dx
x
S zH z
S z ... et le problème est résolu!
* *
1
1/
dxcausal
o ca ca
S zH z
K H z H z
Notez:
* *1/
dx dx
non causal
xo ca ca
S z S zH z
S zK H z H z
on enlève lacausalité
Filtrage Non-causal de Wiener
2 *( ) (0) ( ) ( )MINe d dx
l
n R h l R l
NB: Le calcul de l’EQM pour le filtre IIR non-causal est le même quepour le cas causal.
NB: La réponse impulsionnelle a unnombre infini de termes.
32
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal63
Filtrage optimal IIRFiltrage Non-causal de Wiener
Exemple: soit le signal habituel
Avec les fonctions de corrélations suivantes,
Le bruit et le signal ne sont pas corrélés.
Pour calculer l’équation de WH, on trouve d’abord,
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal64
Filtrage optimal IIRFiltrage Non-causal de Wiener
Exemple: Pour trouver l’EQM, on calcule d’abord,
On peut voir que a seulement un pôle à l’intérieur du cercleunitaire à z=0.5. Évaluant le résidu, nous obtenons alors, ,
1( )deS z z
33
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal65
Filtrage optimal IIRFiltrage Non-causal de Wiener
Exemple:
La conclusion est que le filtre non-causal a une meilleure performanceque le filtre causal équivalent. Ceci est intuitivement raisonnablepuisque le nombre de coefficients utilisés est le double.
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal66
Le filtrage récursif se divise en deux catégories: lefiltrage séquentiel pour le cas scalaire (une seuleobservation scalaire par instant n) et le filtrage deKalman pour le cas vectoriel (un vecteur d’observationsà chaque instant n). Le filtrage récursif offre unealternative intéressante au filtrage optimal de Wienerpour les situations en temps réel. Il réduit le délaialgorithmique car il n’est plus nécessaire d’accumulerdes blocs de données pour calculer l’estimé du signaldésiré. Il s’agit d’une approche dynamique, car àchaque nouvelle observation, nous obtenons une miseà jour de l’estimé.
Prédiction
Correction
Filtrage récursif scalaire
x n s n n
Nous avions vu que l’estimateur linéairequi minimise l’EQM est de la forme:
Nous considérons les observations de laforme d’un signal + bruit. Le bruitd’observation est indépendant du signal.
0 1ˆ ( ) (0) (1) ... ( )MSE ns n c x c x c x n
s n
ˆ 1s n
x n
34
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal67
Filtrage récursif scalaire
ˆ ˆ 1n ns n B s n K x n
Dans le cas du filtrage récursif, le critère d’optimisation demeure toujours lemême, i.e., on minimise l’EQM.
L’erreur de l’estimé est définie par, ˆe n s n s n
À partir du principe d’orthogonalité (ici y=s(n) ), la variance de l’erreur
minimale s’écrit,2 2 2 * *
( ) ( ( )) ( ) ( ) ( ) ( ) ( )MINe e n eVar e n n E e n s n E s n e n
Pour développer le filtre récursif, nous allons iciutiliser un modèle différent. Le processus d’entréesera modélisé plutôt par des équations dedifférence du signal (modèle AR- autorégressif)
ayant la forme récursive:
Notez que les coefficients scalaires Bn et Kn changent dynamiquement.
Puisque le signal et le bruit d’observation ne sont pas corrélés,
* * 2( ) ( ) ( ), ( ) ( ) ( ) ( )s sE s n x n l R l E x n x n l R l l
Estimation récursive
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal68
Filtrage récursif scalaire
Pour trouver les coefficients Bn et Kn on utilise le principe d’orthogonalité. La
variance de l’erreur minimale s’écrit alors,
Et,
* 0E e n x n l 0,1,...,l n
2 *ˆ( ) ( ) ( 1) ( ) ( )e n nn E s n B s n K x n n
Pour trouver Kn , regardons le cas l=0: avec x n s n n
On a,
* * 2( ) ( ) ( ) ( ) ( )E x n n E s n n n
* * * *( ) ( ) ( ) ( ) ( ) ( ) ( ) 0E e n s n n E e n s n E e n n
2 * * *ˆ( ) ( ) ( ) ( 1) ( ) ( ) ( )e n nn E s n n B E s n n K E x n n
2 2( ) 0 0 0e n nn B K
35
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal69
Filtrage récursif scalaire
Notez que le « gain de Kalman » Kn est réel et positif
Ce qui nous donne,
*ˆ( ) ( 1) ( ) ( )n nE s n B s n K x n x n l
Pour trouver le coefficient Bn, regardons le cas l >0:
Suivant le principe d’orthogonalité,
* * *( ) ( ) ( ) ( ) ( ) 0E e n x n l E e n s n l n l
* * *ˆ( ) ( ) ( 1) ( ) ( ) ( )n nE s n x n l B E s n x n l K E x n x n l
22 2
2
( )( ) 0 e
e n n
nn K K
( ) ( )sx sR l R l ( 1)sR l ( ) ( ), 0xx sR l R l l
Car, * *ˆ( 1) ( ) ( 1) ( 1) ( ) ( 1)sE s n x n l E s n e n x n l R l
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal70
Filtrage récursif scalaire
Pour le coefficient Bn nous avons donc,
Ceci veut dire que l’estimation optimale de façon récursive est possibleuniquement si la fonction d’autocorrélation du signal est de la forme décritepar l’équation suivante, i.e.,
( ) 1( ) ( 1) 0 , 0
1 ( 1)s nn
s s n
n s
R l KBR l R l B l
K R l
( ) (0) , / 1ls s n n n nR l R a où a B K
Pour le reste de la discussion, nous allons nous limiter à an=a. Rappelons nous
qu’une fonction de corrélation de forme exponentielle peut être générée à partird’un modèle de la forme récursive,
( ) ( 1) ( )s n as n w n
Où w(n) est un bruit générateur différent de η(n) , le bruit d’observation.
Ainsi,2
2 2
2(0) , ( ) , 0
1
lws s s sR R l a l
a
36
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal71
Le but du filtrage récursif est d’estimer un signal à partir d’observations à l’aided’un filtre adaptatif calculé récursivement à chaque échantillon
On observe: x n s n n
ˆ ˆ 1n ns n B s n K x n
Filtre séquentiel scalaireUn seul signal d’entrée
Monocapteur/Unidimensionnel
Filtre de KalmanPlusieurs signaux d’entrée,
Multi-capteurs/vectoriel
Source 1
Source 2
Source 3
Capteur 1
Capteur 2
Capteur 3Bru
itd’o
bserv
atio
n
s xFiltre
Kalm
an
sEstimé 1
Estimé 2
Estimé 3
Matrice demélange
Observations
On veut estimer:
Filtrage récursif
x n H n s n n
H
ˆ ˆ 1n ns n B s n K x n
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal72
Pour simplifier la démarche, nous étudions seulementle filtre séquentiel scalaire en détails. Desdémarches vectorielles similaires mènent à laversion plus générale du filtre de Kalman résuméplus loin. L’approche d’optimisation est similaireau filtre de Wiener.
1. On applique le principe d’orthogonalité
2. Après manipulations et substitutions pour l=0on obtient la première contrainte:
3. Et pour l > 0 on obtient:
* 0E e n x n l
x n s n n
ˆ ˆ 1n ns n B s n K x n
ˆe n s n s n
1 01
ns s
n
BR l R l
K
1 01
ns s
n
BR R
K
2
2 1 01 1
n ns s s
n n
B BR R R
K K
0l
s sR l a R1
n
n
Ba
K
2
2
e
n
nK
Filtrage récursif scalaire
1l
On constate que:
0,1,...,l n
37
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal73
Notre modèle n’est donc valide que pour s[n] satisfaisant 0ls sR l a R
D’après les propriétés de transformation linéaire des fonctions de corrélation, onpeut prouver que:
nh n u n w n
2w wR l l
s n
Si on fait la transformée en Z de ce système:
1s n as n w n Notre modèle est un estimateur optimal
seulement pour cette forme de s[n]
Filtrage récursif scalaire
Le processus w(n) est un bruit blanc. Si l’on définit le terme de prédiction comme
2
20
1
l lws sR l a a R
ˆ ˆ( 1) ( 1)s n n as n et ˆ ˆ ˆ( ) ( 1) ( ) ( 1)ns n s n n K x n s n n
Alors, l’innovation (nouvelle information)= ˆ( ) ( ) ( 1)r n x n s n n
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal74
On peut reprendre l’équation de prédiction pour s n
ˆ ˆ 1
ˆ ˆ1 1
ˆ ˆ ˆ1 1
n n
n n
n
s n B s n K x n
s n a K s n K x n
s n as n K x n as n
où 2
2
en
nK
Le signal à estimer doit être de forme:
x n s n n (1)
(2)
(3) 1s n as n w n
où a s’obtient à partir de 0ls sR l a R
1
2
22 2 2
1 1
1e
e w
na n
Finalement, par le principe d’orthogonalité
2e n E s n e n
on arrive à résoudre pour 2e n (5)
(4)
2
2
2 20
1 /s
e
s
inconnu!
Filtrage récursif scalaire
0
38
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal75
Filtrage récursif scalaire
On peut représenter le modèle d’observation et de filtrage schématiquement:
+ w n
z-1a
s n x n
Modèle d’observation
Kn +
a
z-1
Filtre récursif
+
n
s n
ˆ 1as n
Bruit d’observation
Signal observé
Résidu
PrédictionCorrection
Estimé
Source
1
2
22 2 2
1 1
1e
e w
na n
2
2
e
n
nK
ˆ ˆ ˆ1 1ns n as n K x n as n
Procédure:
r n
-+
ˆ 1as n
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal76
Filtrage récursif scalaire
Prenons par exemple le filtrage d’une constante observée avec du bruit blanc.Nous avons,
1s n as n w n
Le signal générateur satisfait le modèle
où
1
2
22 2 2
1 1
1e
e w
na n
2
2
e
n
nK
20 , 1, 0ws S a
Ensuite, on peut simplifier:
1
2
2 2
1 1
1e
e
nn
À noter: on peut pré-calculer (àl’avance) les Kn (ils ne
dépendent pas de s[n])
2 22, 2s
2 1.9048, 0.9756, 0.6557, 0.4938, ...
0.9524, 0.4878, 0.3279, 0.2469, ...
e
n
n
K
x n S n
Exemple de filtrage séquentiel: Constante + bruit
39
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal77
On peut simuler le filtre Kalman avec Matlab. On génère un signal x[n] qui
satisfait au modèle . La réponse impulsionnelle du filtre deKalman tend à celle du filtre IIR causal optimal de Wiener.
0 50 100 150 200 250 300-3.5
-3
-2.5
-2
-1.5
-1
-0.5
0
0.5
1
1.5
Signal original s[n]
Signal observé x[n]
Signal estimé shat[x]
0 50 100 150 200 250 300-80
-60
-40
-20
0
20
40
60
80
100
Signal original s[n]
Signal observé x[n]
Signal estimé shat[x]
x n S n
21, 4S 25, 2000S
Filtrage récursif scalaire
Exemple – Constante avec bruit
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal78
Filtrage récursif scalaireExemple numérique:
Soit le problème,
( ) ( 1) ( ) 0.8 ( 1) ( )s n as n w n s n w n
Avec,2( ) 2 (0.8) , 0 ( ) 2 ( )
l l
s sR l a l R l l
On veut calculer les paramètres du filtre avec n=0,1,2. On suppose que s(-1)=0.Puisque la fonction de corrélation du signal est exponentielle, le signal peut êtremodélisé par une équation de différence de la forme,
( ) ( ) ( )x n s n n
Où w(n) est le bruit blanc générateur avec comme variance,22 2 2(1 ) 2(1 (0.8) ) 0.72w s a
Les variances de l’erreur pour n=0,1,2 sont,1
2 2(0) (1) 2
2.0 1 11, 0.0895,
1 2.0 / 2.0 2.0 (0.8) (1.0) 0.72e e
1
2(2) 2
1 10.7647
2.0 (0.8) (0.8095) 0.72e
40
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal79
On veut maintenant calculer récursivement les variances de l’erreur pour leprédicteur séquentiel linéaire. Les gains sont:
0
1
2
1/ 2 0.5,
0.8095 / 2 0.4048,
0.7647 / 2 0.3824... .
K
K
K etc
Les variances obtenues pour les 3 premierséchantillons sont:
2 2
(10)
2 2
(21)
2 2
(32)
(0.8) (1.0) 0.72 1.360
(0.8) (0.8095) 0.72 1.238
(0.8) (0.7647) 0.72 1.209
e
e
e
NB: lorsque n→∞, K→constante
Filtrage récursif scalaire
2
2
en
nK
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal80
Prédiction linéaire séquentielle
Nous allons montrer ici la prédiction optimale séquentielle de s(n+1) en fonction
de l’estimé de la valeur présente ŝ(n)
ˆ ˆ( 1 ) ( )s n n as n
Soit l’erreur de prédiction définie par,
ˆ( 1 ) ( 1) ( 1 )e n n s n s n n
On vérifie maintenant le principe d’orthogonalité,
* * * ˆ( ) ( 1 ) ( ) ( ) ( 1) ( )E x n l e n n E x n l a s n w n a s n
* *ˆ( ) ( 1 ) ( ) ( 1) ( 1 )E x n l e n n E x n l s n s n n
* * * *ˆ( ) ( ) ( ) ( ) ( ) 0E x n l s n s n a E x n l e n
41
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal81
Prédiction linéaire séquentielle
La variance de l’erreur de prédiction est donnée par,
2 * * *
( 1 )ˆ( 1) ( 1 ) ( 1) ( 1) ( 1 )
e n nE s n e n n E s n s n s n n
2 * * * * *
( 1 )ˆ( 1) ( ) ( 1) ( )
e n nE s n a s n w n a s n
2 * * *
( 1 )( ) ( 1) ( ) ( 1)
e n nE as n w n a e n w n
2 22 * * 2 2
( 1 )( ) ( ) ( 1) ( 1) ( )e we n n
a E s n e n E w n w n a n
Utilisant la dernière expression et celle de la variance de l’erreur pour le filtrageséquentiel, i,e,
22 22 2
02 22 22 2 2 2 200
( 1) 1 1 1( ) , 0
( )( 1) ( 1)
w ee
ew e w e
a nn n
na n a n
On obtient l’équationde récurrence de
2
( 1 )e n n
2 2 20 ( 1)2 2
( 1 ) 2 20 ( 1)
e n n
we n n
e n n
a
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal82
Prédiction linéaire séquentielle
Réalisation simultanée du filtre et du prédicteur séquentiel (NB: ici α=a).
Réalisation directe de la prédiction linéaire séquentielle récursive (NB: ici α=a).
NB: lorsque n → ∞, K → constante → filtre de Kalman = filtre de Wiener causal
42
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal83
Filtrage récursif vectoriel – Filtre de Kalman
Dans cette section, nous allons étendre les résultats précédents au cas vectoriel à
l’aide du modèle d’état général suivant,
Est appelée la matrice de transition d’état.
( 1) ( 1, ) ( ) ( )s k k k s k w k
( ) ( ) ( ) ( )x k H k s k k
( 1, )k k
Est appelée la matrice d’observation (des mesures).( )H k
( )w k Est le bruit blanc générateur dont la matrice de corrélation estdéfinie par,
*( ),
( ) ( )0
wTR k n k
E w n w kn k
( )k Est le bruit blanc additif de mesure dont la matrice de corrélationest définie par,
*( ),
( ) ( )0
TR k n k
E n kn k
s=étatsx=observations
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal84
Filtrage récursif vectoriel – Filtre de Kalman
Les deux sources de bruit sont non-corrélées. Soit maintenant les matrices de
corrélation des erreurs de prédiction et de filtrage respectivement,
Le filtre de Kalman peut être calculé en suivant les étapes suivantes,
* *ˆ ˆ( 1 ) ( 1) ( 1 ) ( 1) ( 1 )T TepR k k E s k s k k s k s k k
Initialisation:
* *ˆ ˆ( ) ( ) ( ) ( ) ( )T TefR k k E s k s k s k s k
ˆ ˆ(0 0) (0) (0)s s E s *(0 0) (0), (1 0) (1,0) (0) (1,0) (0)T
ef s ep s wR R R R R
43
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal85
Filtrage récursif vectoriel – Filtre de Kalman
Itérations pour n > 0 :1* *( ) ( 1) ( ) ( ) ( 1) ( ) ( )T T
ep epK k R k k H k H k R k k H k R k
*( 1 ) ( 1, ) ( ) ( 1, ) ( )Tep ef wR k k k k R k k k k R k
( ) ( 1) ( ) ( ) ( 1)ef e epR k k R k k K k H k R k k
ˆ ˆ ˆ( ) ( , 1) ( 1) ( ) ( ) ( ) ( , 1) ( 1)s k k k s k K k x k H k k k s k
Est appelée la matrice du gain du filtre de Kalman.( )K k
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal86
Décomposition de Wold
r px n x n x n
Processusrégulier
Processusprédictible
Un processus est dit ‘prédictible’ si sonerreur moindre carrée par prédictionlinéaire est nulle:
1
ˆ 0
kk
e n x n x n
x n a x n i
Schématiquement:G’(z)
Prédiction linéaire
x n
1
' 1l
ii
i
G z g z
e n
0r pE x n x m
Les 2 composantessont orthogonales
De façon générale, la DSP d’un processus peut s’exprimer par 2 composants,
'( ) ( ) 2 ( )xx xx i ii
S S P
Une partie régulière (continue) et une partie singulière (prédictible).Alternativement,
1
ˆk
k
x n a x n i
44
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal87
Décomposition de Wold
On peut ré-écrire G’(z) en le factorisant: 1
' 1L
jwii
i
G z z e
Conclusion: pour que e[n]=0, et que x[n] soit
prédictible, Sxx(z) doit être un ensemble
d’impulsions de Dirac, soit , 1
2L
jwix i c
i
S z P z e
G’(z)
Prédiction linéaire
x n
1
' 1l
ii
i
G z g z
e n
1
2L
jwix i c
i
S z P z e
' 0E z X z G z
Schématiquement:PEF (Prediction Error Filter)
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal88
Décomposition de Wold
On peut prouver que xr[n] est bel et bien régulier (en appliquant le
principe d’orthogonalité).
En conclusion, comme:
r px n x n x n
0r pE x n x m
2x xr xpr xpR l R l R l R l
x xr xpS z S z S z
Où correspond à la partie continue du spectre xrS z
et correspond à la partie discrète (raies) du spectre xpS z
45
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal89
Décomposition de Wold
Soit un signal aléatoire de la forme,
Où A et φ sont des variables aléatoires avec φ uniformément distribué. Le
processus a une DSP qui consiste en 2 impulsions,
Exemple:
( ) cos( )4
nx n A
/4 /40 0( ) 2 ( ) 2 ( )j j j j j
xxS e P e e P e e
Avec P0=E[A2]/2. Le filtre de prédiction est donc de la forme,
' 1 /4 1 /4 ' 1 2
' 1 2
( ) (1 )(1 ) ( ) 1 2cos( )4
( ) 1 2
j jG z z e z e G z z z
G z z z
Puisque les réalisations du processus satisfont l’équation de différence,
( ) 2 ( 1) ( 2) 0x n x n x n alors le processus est prédictible.
UNIVERSITÉ DE
SHERBROOKE28-mars-13D Gingras - UdeS - GEI 756 Bloc 3 Sem 11
Filtrage optimal90
Références
Anderson Brian D.O., Optimal filtering, Prentice Hall, 1979.
Therrien, Charles W., Discrete random signals and statistical signalprocessing, Prentice Hall, 1992.
Candy James , Bayesian and particle filtering signal processing. 2008,