Applications de la topologie discrète pour la captation de mouvement temps réel et sans marqueurs, Applications of digital topology for real-time markerless motion capture

´UNIVERSITEPARIS-EST
ECOLEDOCTORALEMSTIC
Th`ese pour obtenir le titre de docteur de l’Universit´e Paris-Est
Sp´ecialit´e : Informatique
Soutenue et pr´esent´ee publiquement par
Benjamin RAYNAL
Sous la direction de Michel COUPRIE
Applications de la Topologie Discr`ete pour
la Captation de Mouvement en Temps R´eel
et Sans Marqueurs
7 December 2010
Composition du jury :
Rapporteurs : Edmond BOYER
Luc BRUN
´Examinateurs : K´alma´n PALAGYI
Hideo SAITO
Michel COUPRIE
Vincent NOZICK
tel-00597513, version 1 - tel-00597513, version 1 - To my beloved parents,
who always believed in me.
tel-00597513, version 1 - Title:
Applications of Digital Topology
For Real-Time Markerless Motion Capture
Abstract
This manuscript deals with the problem of markerless motion capture. An approach to this
problem is model-based and is divided into two steps: an initialization step in which the initial
pose is estimated, and a tracking which computes the current pose of the subject using infor-
mation of previous ones. Classically, the initialization step is done manually, forbidding the
possibility to be used online, or requires constraining actions of the subject.
We propose an automatic real-time markerless initialization step, that relies on topological
information provided by skeletonization of a 3D reconstruction of the subject. This topological
information is then represented as a tree, which is matched with another tree used as model
description, in order to identify the different parts of the subject. In order to provide such
a method, we propose some contributions in both digital topology and graph theory research
fields.
As our method requires real-time computation, we first focus on the speed optimization of
skeletonization methods, and on the design of new fast skeletonization schemes providing good
results.
In order to efficiently match the tree representing the topological information with the tree
describing the model, we propose new matching definitions and associated algorithms.
Finally, we study how to improve the robustness of our method by the use of innovative con-
straints in the model.
This manuscript ends by a study of the application of our method on several data sets, demon-
strating its interesting properties: fast computation, robustness, and adaptability to any kind
of subjects.
Keywords
markerless;motion capture;digital topology;thinning; alignment;homeomorphism;
betweenness.
tel-00597513, version 1 - Titre:
Applications de la topologie discr`ete pour
la captation de mouvement en temps r´eel et sans marqueurs.
R´esum´e
Durant cette th`ese, nous nous sommes int´eress´es a` la probl´ematique de la captation de mouve-
ment sans marqueurs. Une approche classique est bas´ee sur l’utilisation d’un mod`ele pr´ed´efini
du sujet, et est divis´ee en deux phases: celle d’initialisation, ou` la pose initiale du sujet est
estim´ee, et celle de suivi, ou` la pose actuelle du sujet est estim´ee a` partir des pr´ec´edentes. Sou-
vent, la phase d’initialisation est faite manuellement, rendant impossible l’utilisation en direct,
ou n´ecessite des actions sp´ecifiques du sujet.
Nous proposons une phase d’initialisation automatique et temps-r´eel, utilisant l’information
topologique extraite par squelettisation d’une reconstruction 3D du sujet. Cette information est
repr´esent´ee sous forme d’arbre (arbre de donn´ees), qui est mis en correspondance avec un arbre
utilis´e comme mod`ele, afin d’identifier les diff´erentes parties du sujet. Pour obtenir une telle
m´ethode, nous apportons des contributions dans les domaines de la topologie discr`ete et de la
th´eorie des graphes.
Comme notre m´ethode requiert le temps r´eel, nous nous int´eressons d’abord `a l’optimisation du
tempsdecalculdesm´ethodesdesquelettisation,ainsiqu’a`l’´elaborationdenouveauxalgorithmes
rapides fournissant de bons r´esultats.
Nous nous int´eressons ensuite `a la d´efinition d’une mise en correspondance efficace entre l’arbre
de donn´ees et celui d´ecrivant le mod`ele.
Enfin, nous am´eliorons la robustesse de notre m´ethode en ajoutant des contraintes novatrices
au mod`ele.
Nous terminons par l’application de notre m´ethode sur diff´erents jeux de donn´ees, d´emontrant
ses propri´et´es: rapidit´e, robustesse et adaptabilit´e a` diff´erents types de sujet.
Mots Cl´es
captation de mouvement sans marqueurs;topologie discr`ete;squelettisation;aligne-
ment; homeomorphisme; interposition.
tel-00597513, version 1 - Acknowledgements
First and foremost, I wish to thank my supervisors: Michel Couprie for his numerous and
precious advices, his patience and all the other things which are too long to enumerate; Vincent
Nozick, especially for his infectious enthusiasm, his support and his friendship, and many other
things.
OverthethreepastyearsIhaveenjoyedworkingintheA3SIteam,inagoodmoodandwithvery
competent researchers. I wish to thank Venceslas, Gilles, Jean, Denis, Yukiko, Hugues, Laurent
and Dror for their good advices and their attention. I specially thank my fellow PhD students,
Franois-senpai,Patrice-senpai,Yohann,John,Fabrice,Anthony, Adrien,Camille,Olena(special
thanks for you, for all the time you spent to read my thesis ;) ) and Nadine for all the time
spend together, for their support and their friendship.
From my point of view, the LIGM is a great lab, thanks to its awesome members, who taught
me almost all I know concerning computer science, from the basics to my actual level. I wish to
specially thanks Marc, Nicolas, Marie-Pierre, Eric, Etienne, Cyril, and Jean-Christophe for this
reason, and Julien, Elsa and Nelly for their friendship.
In a more general way, I would like to thanks my Dad who transmits me his passion for the
computers, my Mom who always encourages me to do what I wanted, my big brother who shows
me the way of the research and my little sister, well, you know... for being my little sister.
Special thanks to Florian and Damien, who believe in me and are my friends since more than
twenty years.
Finally, I would like to thank my fianc´ee Celine, for her patience, her kind, her tenderness, and
her love.
vi
tel-00597513, version 1 - Contents
Abstract iv
Acknowledgements vi
List of Figures xiii
List of Tables xvii
I Introduction 1
1 Global Introduction 3
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Motion Capture Overview 5
2.1 Overview of Motion Captures Systems . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.1 Acquisition Systems Using Markers . . . . . . . . . . . . . . . . . . . . . . 6
2.1.2 Marker Free Optical Acquisition Systems . . . . . . . . . . . . . . . . . . 6
2.2 A priori Model Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.1 Adaptability of the Models . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 On the Use of Multi Camera Systems . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.1 Projection in Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.2 3D Reconstruction of the Subject . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.2.1 Stereo-Correlation . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.2.2 Visual Hulls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Initialization Step of Model-Based Methods . . . . . . . . . . . . . . . . . . . . . 12
3 Motivation 13
3.1 Model Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.1.1 Constraints of Descriptors . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.1.2 Model Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 Initialization Method Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2.1 Extraction of Data Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2.2 Matching Data Tree with Model Tree . . . . . . . . . . . . . . . . . . . . 16
3.2.3 Pipeline and Main Difficulties of Our Method . . . . . . . . . . . . . . . . 17
vii
tel-00597513, version 1 - viii
II Skeletonization Optimizations 19
4 State of the Art of Skeletonization 21
4.1 Thinning Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.1.1 Definitions and Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.1.1.1 Neighborhood . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.1.1.2 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.1.1.3 Connectivity Numbers . . . . . . . . . . . . . . . . . . . . . . . . 24
4.1.2 Simple points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.1.2.1 Simple Points in 2D . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.1.2.2 Simple Points in 3D . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.1.2.3 Simple Points in Higher Dimensions . . . . . . . . . . . . . . . . 26
4.2 Different Kind of Skeletons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26