THÈSE En vue de l'obtention du

THÈSE
En vue de l'obtention du
DOCTORAT DE L’UNIVERSITÉ DE TOULOUSE
Délivré par l'Institut National Polytechnique de Toulouse
Discipline ou spécialité : Informatique
Présentée et soutenue par Pascaline PARISOT
Le 23 janvier 2009
Titre :
Suivi d'objets dans des séquences d'images de scènes déformables
----
De l'importance des points d'intérêt et du maillage 2D
JURY
Michel DHOME (DR – président du jury) LASMEA Clermont-Ferrand
Stéphane PATEUX (IR) France Télécom R&D Rennes
Peter STURM (DR) INRIA Grenoble
Marie-Odile BERGER (CR) INRIA Lorraine
Alain AYACHE (PR) IRIT
Bernard THIESSE (MdC) IRIT
Géraldine MORIN (MdC – invitée) IRIT
Vincent CHARVILLAT (MdC – invité) IRIT
Ecole doctorale : Mathématiques-Informatique-Télécommunications de Toulouse
Unité de recherche : Institut de Recherche en Informatique de Toulouse
Directeur(s) de Thèse : Alain AYACHE
Rapporteurs : Michel DHOME, Stéphane PATEUX, Peter STURMTitre :
Suivi d’objets dans des séquences d’images de scènes déformables : de l’importance des points d’in-
térêt et du maillage 2D
Résumé :
Nous abordons le suivi d’objets dans des séquences d’images de scènes déformables selon deux
axes de recherche. Il s’agit de déterminer les transformations d’un objet, d’une image à l’autre, lorsque
celui-ci s’est éventuellement déformé ou déplacé et lorsque le point de vue de la caméra a éventuel-
lement été modifié (déplacement, zoom...). Pour cela, nous nous sommes inspirés de l’algorithme de
Jurie et Dhome qui permet de suivre un objet plan indéformable. D’une part, nous en améliorons les
performances. D’autre part, nous le généralisons au cas d’objets déformables.
Le premier axe de recherche consiste à améliorer les performances de l’algorithme de Jurie et
Dhome en termes de précision et robustesse. Le suivi s’appuie sur un ensemble de points d’intérêt,
dont dépendent fortement les performances. Ces points d’intérêt sont issus d’une sélection des points
obtenus par des détecteurs reconnus, à savoir SIFT, KLT, SUSAN, HARRIS et MORAVEC. Nous
avons étudié et mis en œuvre, sur différentes classes d’images, des heuristiques de sélection fondées
sur des approches statistique et algébrique. Nous montrons :
– qu’il n’existe pas de détecteur universel,
– que l’approche statistique est à privilégier dans tous les cas.
Le second axe de recherche est une proposition d’un nouvel algorithme de suivi s’appuyant sur le
maillage 2D des images de la séquence. Cet algorithme généralise celui de Jurie et Dhome aux scènes
déformables. Il repose sur :
– des transformations élémentaires (nodales) du maillage, directes et inverses, que nous avons carac-
térisées tant d’un point de vue géométrique qu’analytique,
– l’utilisation des coordonnées barycentriques généralisées pour approcher la composition de deux
transformations d’un maillage.
Cet algorithme donne des résultats similaires à celui d’appariement hexagonal de Nakaya et Hara-
shima tout en étant plus rapide.
Mots Clés :
suivi, apprentissage, points d’intérêt, maillage 2D, objets déformables, séquence d’imagesTitle :
Objects tracking in video of non rigid scenes : importance of interest points and 2D mesh
Abstract :
We deal with object tracking in videos of non-rigid scenes with two main purposes. We aim at
determining the transformations of an object, from one frame to the next, when it may be distorted or
moved and when the camera focus may change (movement, zoom...). To do this, we were inspired by
the Jurie and Dhome algorithm, which enables the tracking of plane rigid objects. On the one hand,
we improve its performance. On the other hand, we generalize it to non-rigid objects.
The first goal consists in improving the performance of the Jurie and Dhome algorithm, in terms of
accuracy and robustness. The tracking is based on a set of interest points, which has a great effect on
the algorithm’s performance. These interest points come from a selection among the points extracted
with some common detectors: SIFT, KLT, SUSAN, HARRIS, and MORAVEC. With various pictures
classes, we have studied and implemented some selection heuristics based on statistical or algebraic
approaches. We show that:
• there is no universal detector,
• the statistical approach is the best in all cases.
The second goal is a proposal of a new tracking algorithm based on a 2D mesh of the video frames.
This algorithm generalizes the Jurie and Dhome one for non-rigid scenes. It is based on :
• elementary (nodal), direct or inverse, mesh transformations that we geometrically and analyti-
cally characterize,
• generalized barycentric coordinates to approximate the composition of two mesh transforma-
tions.
This algorithm gives similar results to the hexagonal matching algorithm of Nakaya and Harashima
while being faster.
Keywords :
tracking, learning, interest points, 2D mesh, non rigid objects, videoMÉMOIRE
de
Pascaline PARISOT
intitulé
Suivi d’objets dans des séquences d’images
de scènes déformables
–
De l’importance des points d’intérêt et du maillage 2D
Composition du jury :
Rapporteurs : Michel DHOME
Stéphane PATEUX
Peter STURM
Examinateur : Marie-Odile BERGER
Responsables : Alain AYACHE
Vincent CHARVILLAT
Géraldine MORIN
Bernard THIESSEÀ Maman,Remerciements
Il est de coutume d’avoir une page de remerciements dans tout mémoire que l’on
écrit... mais qui vais-je donc pouvoir remercier ? Après réflexion, j’ai trouvé quelques per-
sonnes qu’il me tenait à cœur de remercier plus particulièrement...
Je tiens tout d’abord à remercier Monsieur Alain Ayache, professeur à l’ENSEEIHT,
pour m’avoir donné la possibilité d’effectuer une thèse au sein de son équipe.
Mes remerciements vont également aux membres de mon jury Madame Marie-Odile
Berger et Messieurs Michel Dhome, Stéphane Pateux et Peter Sturm pour m’avoir fait l’hon-
neur d’évaluer mes travaux de recherche. Merci à ces trois derniers pour leurs remarques,
en tant que rapporteurs, sur ce mémoire.
Mes sincères remerciements à mes responsables Géraldine Morin, Vincent Charvil-
lat et Bernard Thiesse pour m’avoir guidée dans cette recherche, pour les discussions que
nous avons eues ensemble. Plus particulièrement merci à Bernard pour la rédaction de ce
mémoire, pour sa tenacité, pour son perfectionnisme... Merci à vous trois pour tout ce que
j’ai acquis en vous côtoyant.
Merci à mes relecteurs pour le travail de longue haleine qu’ils ont effectué : Céline,
Philippe, Noële, Sandrine et Sébastien.
Je tiens également à remercier mes co-bureaux successifs pour m’avoir supportée...
dur, dur... Christophe, Pascal, Bernard, le Viok (heu... Stéphane) et Benoît.
Merci aussi à tous les doctorants ou stagiaires avec qui j’ai parcouru un bout de che-
min et passé de très bons moments : Matthijs, Ariel, Vincent, Christophe, Bertrand, Aurélie,
Cezar, Jean-Charles, Stéphane (et le pingouin volant), Sébastien, Sandrine (et les coin-coin
lumineux), Nassima, Victoria, Benoît, Jérôme, Dorin... Merci pour leur sympathie, leur dis-
ponibilité, leurs plaisanteries.
Merci à tous les membres de l’équipe VORTEX pour m’avoir très bien accueillie
pendant ma thèse : Jano et sa constante bonne humeur, Romulus et ses pots improvisés,
Pierre, Jean-Pierre, Philippe...
Un grand merci à toutes les personnes que j’ai côtoyées durant mes enseignements
et qui ont été confrontées à mes innombrables questions. Merci pour votre patience et vos
réponses. Un remerciement tout particulier à Xavier C. pour sa rigueur, sa clarté d’explica-
tions et les échanges fort enrichissants que j’ai eus avec lui. Merci. Merci à Marc, Xavier C.,
Vincent, Géraldine, Bernard, Pascal, François, Ronan, Marcel, Christiane, Pierre, Daniel,
Aurélie, Sandrine, Nassima... pour m’avoir fait confiance et m’avoir permis d’enseigner
aussi bien l’informatique que les mathématiques appliquées.
Sans oublier tous les collègues du laboratoire, voisins de bureau pendant un temps,
animateurs de discussion, tous sympathiques : Xavier T., Emmanuel, André-Luc, Julien,
Jérôme, Béatrice, Gérard, Michel...
Une pensée aussi pour le personnel du secrétariat et du support technique que j’ai
eu le plaisir d’embêter pendant cette thèse pour leur sympathie et leur patience : Annie,
ixAnne-Marie, Violette, Josiane, Sylvie E., Sabyne, Sylvie A., Marie-Blandine, Jean-Claude,
Stéphane.
Je voudrais aussi remercier des personnes qui restent souvent dans l’ombre et qui
font qu’auj