Erreur sur l’estimation de la transformée de Hough

Filtre de Kalman assisté par transformée de Hough 

Méthodes de pistage pour lidar

À la di Érence des lidars de notre partenaire industriel, les lidars rotatifs possËdent une grande rÉsolution angulaire pouvant amener ‡ une incertitude sur la position de quelques centimËtres seulement. La nouvelle technologie des lidars ‡ État solide est beaucoup plus abordable et ainsi est trËs prometteuse pour Ítre intÉgrÉe aux systËmes de conduite intelligents. Par contre, leur rÉsolution angulaire est pour l’instant beaucoup moins intÉressante : le secteur couvert par un ÉlÉment est entre 3 et 10 pour les lidars sur le marchÉ actuellement. NÉanmoins, ils demeurent prÉcis pour ce qui est de la mesure en distance radiale.
Cette caractÉristique signi e que les dÉtections faites par l’appareil ne peuvent pas Ítre ap-proximÉes comme des coordonnÉes cartÉsiennes : le systËme de mesures est polaire, et ainsi, la covariance sur la mesure angulaire augmente en fonction de la distance. Surtout, le bruit de mesure sur la position radiale des dÉtections est gaussien, alors que celui sur la position angulaire, fortement discrÉtisÉe, est plutÙt uniforme sur le champ de vue d’un ÉlÉment.
RÉcemment, de nombreux travaux s’intÉressent au pistage pour des lidars haute rÉsolution en utilisant conjointement un ltre de Kalman avec un algorithme d’association de dÉtections. Par exemple, dans [2], le pistage ‡ hypothËses multiples [3] est appliquÉ aux donnÉes lidar pour sÉparer des trajectoires de piÉtons. De maniËre similaire, [4] fait une estimation de la position et de la vitesse d’objets observÉs par un lidar en utilisant le principe des hypothËses multiples pour initialiser pour chaque cible plusieurs ltres de Kalman ‡ di Érentes vitesses. Également, [5] estime l’État du lidar, des cibles dynamiques et de l’environnement statique simultanÉment en utilisant un ltre de Kalman et propose un algorithme pour classi er les donnÉes lidar (les associer ‡ une cible statique, ‡ une nouvelle cible dynamique ou ‡ une cible dynamique existante).
L’estimation d’État doit donc prendre en compte la gÉomÉtrie particuliËre de la nouvelle tech-nologie lidar ‡ État solide : en plus d’a ecter l’estimation de la position angulaire, cette con gu-ration faible rÉsolution nuit ‡ la premiËre Étape du pistage qui consiste ‡ associer les dÉtections aux pistes. En e et, les algorithmes d’association, notamment ceux dans [2; 4; 5], utilisent tous les informations extraites au l du temps (au moins la position et vitesse estimÉe des cibles) par des observateurs. Cependant, jusqu’‡ maintenant, la littÉrature concernant le pistage lidar se concentre presque exclusivement sur les lidars rotatifs haute rÉsolution pour lesquels ces informations sont estimÉes avec une grande prÉcision.
Toutefois, un article en particulier se penche sur l’amÉlioration de l’estimation de la position d’un objet passant au travers du champ de vue d’ÉlÉments lidar faible rÉsolution [6]. Ces ÉlÉ-ments possËdent un champ de 2 chacun, sont espacÉs de plusieurs degrÉs entre eux (plusieurs zones non couvertes par le lidar) et sont xes. L’observateur proposÉ tente de rÉduire l’erreur en se ant sur le sens d’arrivÉe de la dÉtection et une estimation de la vitesse angulaire selon le temps passÉ dans le capteur. Il utilise ces donnÉes comme mesures supplÉmentaires dans un ltre de Kalman. Le modËle considËre que la vitesse est constante ; une Étude pour des trajectoires courbes ou avec accÉlÉration non nulle n’a pas ÉtÉ faite pour l’instant.
Dans la prochaine section, les ltres de Kalman (classique, Étendu et non parfumÉ, tous utilisÉs dans ce mÉmoire) sont dÉveloppÉs. La nÉcessitÉ d’une adaptation pour des mesures angulaires discrËtes est abordÉe en s’appuyant sur la relation du ltre avec le bruit gaussien.

Filtre de Kalman

Le ltre de Kalman est un observateur communÉment appliquÉ au pistage de cibles, en deux et trois dimensions, pour de nombreux systËmes de mesures (lidar, radar, camÉras, etc.). Depuis sa proposition par R. E. Kalman dans [7], le ltre de Kalman a continuÉ d’Évoluer dans la littÉrature a n d’Élargir ses limites : systËme non linÉaire, bruits non gaussiens, ajout de contraintes sur les États et plus encore. Il demeure le meilleur estimateur pour un systËme linÉaire avec bruits gaussiens et le meilleur estimateur linÉaire pour un systËme non linÉaire.
Dans cette section, les dÉveloppements pour les systËmes linÉaires ( ltre de Kalman classique) et non linÉaires ( ltres de Kalman Étendu et non parfumÉ) sont abordÉs en particulier. La nÉ-cessitÉ d’avoir un bruit qui est gaussien pour obtenir les performances optimales est Également expliquÉe par deux approches, soit le moindre carrÉ et le maximum a posteriori. D’abord, dans les prochains paragraphes, la notation mathÉmatique relative au ltre de Kalman employÉe dans ce travail est Établie.
L’État d’un systËme xk peut Ítre exprimÉ en fonction de son État prÉcÉdent xk 1, de la commande en entrÉe uk et d’un bruit de procÉdÉ wk. L’indice reprÉsente l’instant : k Étant l’instant actuel et k 1 Étant l’instant prÉcÉdent. L’Équation aux di Érences gÉnÉrale pour cette relation est la suivante :
xk = f(xk 1; uk) + wk ; (2.1)
o˘ f( ) est une fonction qui peut Ítre non linÉaire.
De la mÍme maniËre, les observations yk ‡ l’instant k peuvent Ítre exprimÉes selon l’État du systËme et le bruit de mesure vk.
yk = h(xk) + vk ; (2.2)
o˘ h( ) est une fonction qui peut, encore une fois, Ítre non linÉaire.
Le ltre de Kalman est un observateur stochastique et s’exprime donc ‡ partir de l’Équation gÉnÉrale d’un observateur :
x^k = x^kjk 1 + Kk hyk y^kjk 1 i ; (2.3)
o˘ l’État estimÉ a priori x^kjk 1 et l’observation correspondante y^kjk 1 sont ÉvaluÉes par :
x^kjk 1 = f(x^k 1; uk) ; (2.4)
y^kjk 1 = h(x^kjk 1) : (2.5)
Le terme (yk y^kjk 1) est appelÉ l’innovation. Le ltre de Kalman est habituellement divisÉ en deux Étapes principales : la prÉdiction ou l’estimation a priori et la correction par l’innovation ou estimation a posteriori.
Le gain du ltre permet de mettre plus ou moins d’importance sur la correction par l’innovation par rapport ‡ la prÉdiction. Le gain du ltre de Kalman Kk est par consÉquent fonction de la matrice de covariance de l’erreur a priori ekjk 1 = (xk x^k jk 1) et de la matrice de covariance de l’innovation. Lorsque les bruits de procÉdÉ et de mesure sont gaussiens et que les fonctions f( ) et h( ) sont linÉaires, le ltre de Kalman est l’estimateur optimal.
Puisqu’un systËme est rarement linÉaire, des extensions au ltre de Kalman, telles que le ltre de Kalman Étendu et le ltre de Kalman non parfumÉ, ont ÉtÉ dÉveloppÉes. Que ce soit le ltre de Kalman classique, Étendu ou non parfumÉ, il suppose toujours un bruit gaussien ‡ la fois sur le procÉdÉ et les mesures. La di Érence entre ces trois ltres se situe plutÙt dans la linÉarisation du modËle de transition f( ) et du modËle de l’État vers les observations h( ).

Filtre de Kalman classique

Le ltre de Kalman classique suppose un systËme linÉaire, de telle sorte qu’il peut Ítre reprÉ-sentÉ par les opÉrations matricielles suivantes :
xk = Axk 1 + Buk + wk ; (2.6)
o˘ A est une matrice reprÉsentant la transition de l’État prÉcÉdent ‡ l’État actuel, B est une matrice reprÉsentant la transformation de la commande ‡ l’entrÉe du systËme vers l’État actuel. Le bruit de procÉdÉ wk est supposÉ gaussien et de moyenne nulle. La matrice de covariance de ce bruit, E[wkw|k], de procÉdÉ est nommÉe Q.
La relation entre l’État et l’observation est aussi supposÉe linÉaire et est reprÉsentÉe par la matrice H :
yk = Hxk + vk : (2.7)
Tout comme le bruit de procÉdÉ, le bruit de mesure vk est supposÉ gaussien et de moyenne nulle. Sa matrice de covariance, E[vkv|k], est nommÉe R.
À la section A.1 en annexe, la matrice de covariance de l’erreur a priori ekjk 1 est dÉveloppÉe pour obtenir la relation suivante :
P kjk 1 = AP k 1A| + Q ; (2.8)
o˘ P k 1 est la matrice de covariance de l’erreur de l’estimation a posteriori ‡ instant prÉcÉdent. Cette relation exprime donc la propagation de la matrice de covariance de l’erreur dans le temps.
À la section A.2 en annexe, la matrice de covariance de l’innovation est Également dÉveloppÉe et la relation suivante est obtenue :
Sk = HP kjk 1H| + R : (2.9)
Le calcul du gain de Kalman, soit la matrice Kk, est dÉveloppÉ dans la littÉrature de multiples faÁons. À l’origine, le ltre de Kalman a ÉtÉ dÉveloppÉ en utilisant la projection orthogonale de l’erreur dans l’espace d’Hilbert [7]. Cependant, a n de mettre en Évidence l’implication du bruit gaussien, les prochaines sections expliquent les grandes lignes du dÉveloppement par l’approche du moindre carrÉ, puis par l’approche du maximum a posteriori.
Approche du moindre carrÉ
Le gain de Kalman est souvent dÉveloppÉ dans la littÉrature en passant par la minimisation de l’erreur quadratique moyenne (MSE), par exemple [8]. L’erreur quadratique moyenne est dÉ nie par la variance et le biais de l’estimateur :
MSE = Var(x^) + Biais2(x^) (2.10)
L’estimateur optimal est dÉrivÉ ‡ partir de deux hypothËses de dÉpart.
La premiËre est que, lorsque l’estimateur est optimal, le biais est nul. Par consÉquent, il faut trouver l’estimateur pour lequel la variance de x^ est minimale. Cette estimation optimale
correspond en fait, puisqu’elle est sans biais, ‡ l’espÉrance conditionnelle de l’État sachant les observations obtenues ‡ l’instant actuel et aux instants prÉcÉdents.
x^k = E[xkjy1; y2; ; yk] (2.11)
Dans de nombreux cas, la distribution de cette probabilitÉ conditionnelle a posteriori n’est pas Évidente ‡ calculer. Cependant, lorsqu’‡ la fois le bruit de mesures et le bruit de procÉdÉ sont gaussiens, cette densitÉ de probabilitÉ se rÉsume Également ‡ une densitÉ gaussienne (qui ne possËde qu’un seul mode).
La deuxiËme hypothËse est donc de considÉrer un bruit de nature normal. Le ltre de Kalman se base entiËrement sur cette propriÉtÉ, car une densitÉ de probabilitÉ normale peut Ítre totalement reprÉsentÉe par son espÉrance et sa covariance. La matrice de covariance de l’erreur et le vecteur d’État estimÉ (a posteriori ) sont donc su sants pour reprÉsenter la densitÉ de probabilitÉ de fxkjy1; y2; ykg.
Pour ces raisons, minimiser l’erreur quadratique moyenne sur x^ revient ‡ minimiser la variance
de l’estimation a posteriori. Dans une matrice de covariance, la variance est situÉe sur la diagonale principale. Par consÉquent, il s’agit de minimiser la trace de la matrice de covariance de l’erreur a posteriori :
E[(xk x^k)2] = Tr(E[(xk x^k)(xk x^k)|]) = Tr(E[ekek|]) = Tr(P k) (2.12)
Le vecteur d’erreur, (xk x^k), est renommÉ ek a n de simpli er la notation.
En remplaÁant par l’Équation gÉnÉrale d’un observateur, le vecteur d’erreur ‡ l’instant prÉsent peut Ítre exprimÉ en fonction du vecteur d’erreur a priori :
ek = (I KkH)ekjk 1 Kkvk (2.13) connaissant l’observation d’obtenir l’État estimÉ
La matrice de covariance de l’erreur a posteriori dÉduite de cette expression est donc :
P k = (I KkH)P kjk 1(I KkH)| KkRK|
k (2.14)
La valeur du gain minimisant cette variance correspond ‡ la valeur pour laquelle la dÉrivÉe de la trace est nulle. Cette dÉrivation est faite en annexe ‡ la sous-section A.3. Le gain de Kalman ainsi obtenu est le suivant : Kk = P kjk 1H|Sk 1 (2.15)
En remplaÁant le gain de Kalman dans (2.14), la covariance a posteriori est simpli Ée ‡ : P k = (I KkH)P kjk 1 (2.16)
Une seconde approche permettant d’arriver au mÍme rÉsultat, en raison de la nature gaussienne du bruit, est celle du maximum a posteriori.
Approche du maximum a posteriori
L’estimateur optimal bayÉsien est de trouver x^k qui maximise la probabilitÉ conditionnelle x^k yk et la densitÉ de probabilitÉ des estimations prÉcÉdentes. Autrement dit, l’estimateur optimal est celui du maximum a posteriori. Or, pour des bruits de mesure et de procÉdÉ gaussiens, le maximum a posteriori (MAP) est l’estimation faite par le ltre de Kalman.
La formulation du MAP dÉpend de la fonction de vraisemblance max p(ykjx^k) et de la distri-bution a priori p(x^kjx^k 1) : max p(x^kjyk) = max p(ykjx^k)p(x^kjx^k 1) ; (2.17)
Le dÉveloppement fait ici est semblable ‡ celui dans [9]. Cependant, ce dernier associe le ltre de Kalman au maximum de vraisemblance, malgrÉ la prÉsence de la distribution a priori, et des Étapes importantes du dÉveloppement, notamment l’explication du passage de la fonction de vraisemblance vers la densitÉ a posteriori, sont omises ou non explicites. Le dÉveloppement ici et ‡ la section A.4 en annexe est direct et plus approfondi et se base sur les prochaines a rmations.
Lorsque le bruit est gaussien, la fonction de vraisemblance ainsi que la distribution sont Également gaussiennes :
exp( (yk Hx^k)R 1 (yk Hx^k)|)
kjk 1 est possible.
Le modËle rÉcursif du systËme est considÉrÉ dans la distribution a priori. Comme la multiplica-tion de distributions gaussiennes Équivaut Également une distribution gaussienne, l’expression de la distribution a priori selon P
Une seconde simpli cation importante, gr‚ce ‡ la nature gaussienne de ces distributions, est appliquÉe sur la distribution a posteriori. Il est possible de minimiser le logarithme de la distribution a posteriori, plutÙt que maximiser la distribution elle-mÍme, pour trouver le MAP :
log p(x^kjyk) / (yk Hx^k)R 1(yk Hx^k)| (x^k x^kjk 1)P kj1k 1(x^k x^kjk 1)| : (2.20)
À la section A.4 en annexe, le dÉveloppement pour trouver la valeur de x^k minimisant (2.20) est dÉtaillÉ. Il est alors dÉmontrÉ, en utilisant le lemme de l’inversion matricielle, que la forme obtenue en passant par cette dÉmarche Équivaut ‡ celle trouvÉe par l’approche du moindre carrÉ : 1
x^k = hH|R 1H + P kj1k 1 i hH|R 1yk + P1 kj1k 1x^kjk 1 i
(2.21) = x^kjk 1 + P kjk 1H|(HP kjk 1H| + R) yk Hx^kjk 1 :
Le ltre de Kalman est donc optimal, car il minimise l’erreur quadratique moyenne et maxi-mise la probabilitÉ a posteriori. Ces deux a rmations sont respectÉes et sont Équivalentes en raison de la nature gaussienne du bruit de mesure et de procÉdÉ : la densitÉ de probabilitÉ de l’État a posteriori est une gaussienne Également et possËde donc un seul mode qui est situÉ ‡ l’espÉrance.
Étapes rÉsumÉes de prÉdiction et correction
L’application du ltre de Kalman peut se rÉsumer en deux Étapes : la prÉdiction ‡ partir des États prÉcÉdents (estimation a priori), et la correction en comparant les États aux observations (estimation a posteriori). Les calculs relatifs ‡ ces Étapes sont les suivants :
PrÉdiction
x^kjk 1 = Ax^k 1 + Buk (2.22)
P kjk 1 = AP k 1A| + Q
Correction
Sk = HP kjk 1H| + R
Kk = P kjk 1H|Sk 1 (2.23)
x^k = x^kjk 1 + Kk(yk Hx^kjk 1)
P k = (I KkH)P kjk 1

Table des matières

1 Introduction 
1.1 Détection de cibles
1.2 Système de pistage de cibles
1.3 Problématique et objectifs du projet
1.4 Structure du mémoire
2 Revue de la littérature 
2.1 Méthodes de pistage pour lidar
2.2 Filtre de Kalman
2.3 Estimation d’états pour mesures discrètes
2.4 Transformée de Hough
2.5 Conclusion
3 Transformée de Hough 
3.1 Conversion pour des mesures en coordonnées polaires
3.2 Espace de Hough et matrice des votes
3.3 Minimisation des calculs
3.4 Résultats préliminaires
3.5 Conclusion
4 Filtre de Kalman assisté par transformée de Hough 
4.1 États d’une cible
4.2 Projection des mesures
4.3 Application d’une contrainte relaxée
4.4 Filtre de Kalman étendu assisté par projection des mesures
4.5 Filtre de Kalman classique assisté par projection des mesures
4.6 Filtre de Kalman étendu assisté par contrainte relaxée
4.7 Filtre de Kalman non parfumé assisté par contrainte relaxée
4.8 Zone morte sur l’innovation
4.9 Matrices de covariance du bruit
4.10 Initialisation du ltre de Kalman
4.11 Conclusion
5 Résultats pour cible de taille piéton 
5.1 Paramètres
5.2 Données expérimentales
5.3 Simulations de trajectoires rectilignes
5.4 Conclusion
6 Résultats pour cible de taille voiture 
6.1 Simulations pour trajectoires rectilignes
6.2 Simulations pour trajectoires courbes
6.3 Conclusion
7 Conclusion 
7.1 Travaux futurs
A Dérivation du ltre de Kalman
A.1 Propagation de l’erreur
A.2 Covariance de l’innovation
A.3 Approche du moindre carré
A.4 Approche du maximum a posteriori
B Filtre de Kalman assisté modèle polaire
C Caractérisation de l’erreur sur l’estimation des paramètres de trajectoire
C.1 Erreur sur l’estimation de la transformée de Hough
Bibliographie 

Télécharger le rapport complet