Project topics and materials
Get Complete Project Material File(s) Now! »
Initialization Method Overview
Now we have defined the inputs of our method: a visual hull representation of the subject and the a priori model.
Our method consists in extracting a descriptor from the visual hull (called the data descriptor ) which is similar to the one used in the a priori model (called the model descriptor ). The main difference is that the data descriptor has to contain some spatial information, where as that the model descriptor contains informations about the nature of the parts of the model. Finding a matching between the two descriptors results in finding spatial information for each part of the model and by this way, the pose of the subject.
Extraction of Data Tree
First we have to find a way to extract topological and geometrical information from the visual hull, and to represent it by a tree. We solve this problem in two steps: first, we consider the skeleton of the visual hull. The skeleton is an efficient shape descriptor, representing in a compact form the topology and the main geometric features of a shape. It can be obtained by iteratively removing voxels without changing the topology (see Figure 3.2 for an example). Then, we “translate” the skeleton into a tree:
• Each vertex represents a characteristic point of the skeleton: ending point or intersection point.
• Two vertices are linked if the associated points are adjacent to a same curve in the skeleton.
• To each edge is associated a weight, which is the number of voxels in the corresponding curve.
In the case of incomplete model, we have to consider that a branch ended by a point touching the border of acquisition space have an infinite length. See Figure 3.3 for some examples of data tree extractions.
Matching Data Tree with Model Tree
Once we have a tree description of the subject, we have to find a way to match it with the model tree. In the literature, numerous methods are proposed to find a matching between two trees. However, in our case we have to take into consideration several kind of noises in the data tree. Furthermore, in the literature, proposed methods are designed for special kind of trees, usually rooted, oriented, and with information on vertices instead of on edges, as in our case. We have to define a new way to match our data tree with our model tree, corresponding to our constraints.
Different Kind of Skeletons
In this section, we will review the different kinds of results which can be expected from a thinning process. The design and the constraints of the thinning algorithm will obviously depend on the desired result.
Table of contents :
Abstract
Acknowledgements
List of Figures
List of Tables
I Introduction
1 Global Introduction
1.1 Background
1.2 Contribution
2 Motion Capture Overview
2.1 Overview of Motion Captures Systems
2.1.1 Acquisition Systems Using Markers
2.1.2 Marker Free Optical Acquisition Systems
2.2 A priori Model Definitions
2.2.1 Adaptability of the Models
2.3 On the Use of Multi Camera Systems
2.3.1 Projection in Images
2.3.2 3D Reconstruction of the Subject
2.3.2.1 Stereo-Correlation
2.3.2.2 Visual Hulls
2.4 Initialization Step of Model-Based Methods
3 Motivation
3.1 Model Definition
3.1.1 Constraints of Descriptors
3.1.2 Model Description
3.2 Initialization Method Overview
3.2.1 Extraction of Data Tree
3.2.2 Matching Data Tree with Model Tree
3.2.3 Pipeline and Main Difficulties of Our Method
II Skeletonization Optimizations
4 State of the Art of Skeletonization
4.1 Thinning Theory
4.1.1 Definitions and Notations
4.1.1.1 Neighborhood
4.1.1.2 Connectivity
4.1.1.3 Connectivity Numbers
4.1.2 Simple points
4.1.2.1 Simple Points in 2D
4.1.2.2 Simple Points in 3D
4.1.2.3 Simple Points in Higher Dimensions
4.2 Different Kind of Skeletons
4.2.1 Ultimate Skeleton
4.2.2 Curvilinear and Surface Skeletons
4.2.2.1 Extremity Points
4.2.2.2 Isthmus
4.2.2.3 Symmetric versus Asymmetric Skeletons
4.3 Thinning Algorithms
4.3.1 Sequential algorithms
4.3.2 Parallel algorithms
4.3.2.1 Directional Algorithms
4.3.2.2 Subfield-Based Algorithms
4.3.2.3 Fully Parallel Algorithms
5 Faster Implementation of Thinning Schemes
5.1 Classical Optimizations
5.1.1 Restriction of Points to Check
5.1.2 Optimization of Deletion Conditions Tests
5.1.2.1 Usage of Look-Up Tables
5.1.2.2 Usage of Binary Decision Diagrams
5.1.2.3 Look Up Tables versus Binary Decision Diagrams
5.2 Look Up Tables for Critical Kernel Based Algorithms
5.2.1 Critical Kernel Based Algorithms
5.2.2 Reformulation of templates
5.2.2.1 Reformulation of M2
5.2.2.2 Reformulation of M1
5.2.2.3 Reformulation of M0
5.2.3 Look Up Tables for New Masks
5.2.4 Reformulation of the Thinning Schemes
5.2.4.1 Speed up
5.3 Configurations Computation Speed-Up
5.3.0.2 Speed up
5.4 Benchmarks
5.4.1 Methodology
5.4.1.1 Implemented Algorithms
5.4.1.2 Tested Images
5.4.2 Results
5.4.3 Discussion
5.4.3.1 CCSU Speed Gain
5.4.3.2 LUT Speed Gain for Critical Kernel Based Thinning
5.5 Application in Motion Capture Framework
6 Isthmus Based Directional Thinning
6.1 Background
6.1.1 Bertrand and Couprie Isthmus Based Thinning
6.1.2 Pal´agyi and Kuba 6-directional Thinning
6.2 New Method
6.2.1 Design of Deletion Condition Masks
6.2.2 Mask Set Reduction
6.3 Comparative Results
6.4 Other Kinds of Skeletons
6.4.1 Ultimate Skeletons
6.4.2 Surface Skeletons
III Matching to A Priori Model
7 Problematics and Usual Definitions
7.1 Representation of the Shape
7.1.1 Global Descriptors
7.1.1.1 Moments
7.1.2 Features Distribution
7.1.3 Contours
7.1.4 Spatial Maps
7.1.5 Skeleton Based Approaches
7.1.5.1 Shock Graphs
7.1.5.2 Skeleton Graph
7.1.5.3 Skeletal Shape-Measure
7.1.5.4 Skeletal Segments
7.1.5.5 Skeleton Paths
7.1.6 Choice of the Description
7.2 Usual Definitions on Graphs
7.2.1 Undirected graphs definitions
7.2.1.1 Undirected graphs
7.2.1.2 Paths and cycles
7.2.1.3 Trees and forests
7.2.2 Directed graphs definitions
7.2.2.1 Directed graphs
7.2.2.2 Associated undirected graphs
7.2.2.3 Rooted trees and rooted forests
7.2.3 Common definitions
7.2.3.1 Isomorphism
7.2.3.2 Attributed graphs
7.2.3.3 Labeled graphs
7.2.3.4 Weighted graphs
7.3 Data Tree Extraction
7.3.1 Data Tree Specificities
7.3.2 Data Tree Construction Design
7.3.3 From Skeleton to Data Tree
7.3.3.1 Incomplete Model Special Case
7.3.4 Data Tree Noises
7.3.4.1 Ghost limbs and Spurious branches
7.3.4.2 Useless 2-degree vertices
7.3.4.3 Splitted vertices
8 State of the Art of Edit-Based Matching
8.1 Similarity and Matching between Graphs
8.1.1 Graph Matching
8.1.1.1 Association Graph
8.1.1.2 Graph Eigenspace
8.1.2 Similarity Measurement
8.1.3 Methods Providing both Graph Similarity and Matching
8.2 Edit-based Distance Basics
8.2.1 Edit Operations
8.2.2 Cost Function
8.2.3 Tree Edit Distance
8.2.4 Mapping
8.2.5 Complexities notations
8.3 General Edit Distance
8.4 Other Edit Distances
8.4.1 Alignment Distance
8.4.2 Constrained/Isolated Subtree Edit Distance
8.4.3 Less Constrained Edit Distance
8.4.4 1-Degree/Top-Down Edit Distance
8.4.5 2-Degree Edit Distance
8.4.6 Bottom-Up Edit Distance
8.5 Inclusion of Mappings
8.6 Edit Distances with Extended Set of Operations
8.6.1 Edge Merging and Edge Pruning
8.6.2 Cut Operation
8.6.3 Horizontal/Vertical Merge and Split
8.7 Discussion for our Purpose
8.8 Alignment Distance for Weighted Trees
9 Homeomorphic Alignment
9.1 Preliminar Definitions
9.1.1 Merging Operation
9.1.2 Homeomorphism
9.1.3 Merging Kernel
9.2 Homeomorphic Alignment Definition
9.3 Algorithm for rooted trees
9.3.1 Definitions and notations
9.3.2 Reformulations
9.3.3 Algorithm
9.3.4 Complexity
9.4 Algorithm for unrooted trees
9.4.1 Naive algorithm
9.4.1.1 Complexity
9.4.2 Optimized algorithm
9.4.2.1 Adapted order of navigation
9.4.2.2 Final algorithm
9.5 Algorithm for rooted tree with unrooted tree
9.5.1 Algorithm
9.5.1.1 Complexity
9.6 Usage of Cut Operation
9.6.1 Integration of cut operation in our algorithm
9.7 Limitations
10 Asymmetric Homeomorphic Alignment
10.1 Asymmetric Homeomorphis
10.1.1 Definition
10.1.2 Properties
10.1.2.1 Usual definitions on binary relations
10.1.2.2 Properties of asymmetric homeomorphism
10.2 Asymmetric Homeomorphic Alignment
10.3 Algorithm for Rooted Trees
10.3.1 Reformulations
10.3.2 Algorithm
10.3.3 Complexity
10.4 Algorithm for Unrooted Trees and for Rooted Tree with Unrooted Tree
11 Alignments Comparison
11.1 Complexities Comparison
11.2 Accuracy
11.2.1 Protocol
11.2.2 Results
11.2.3 Discussion
11.3 Computation Speed
11.3.1 Protocol
11.3.2 Results
11.3.3 Discussion
11.4 Frequencies in Motion Capture Context
11.4.1 Statistics on data trees
11.4.2 Choice of algorithm
11.4.3 Protocol
11.4.4 Results
11.4.5 Discussion
IV Motion Capture Applications
12 Generic Pose Initialization Step
12.1 Summary of our Method
12.1.1 Use of Asymmetric Homeomorphic Alignment
12.1.2 Pipeline
12.2 Optional Constraints
12.2.1 Coordinate Constraints
12.2.2 Betweenness Constraints
12.2.2.1 Design of Intuitive Betweenness Relation
12.2.2.2 Design of Mathematically Efficient Betweenness Relation
12.2.2.3 Application in our Method
12.3 Complete Method and Model Definition
13 Results and Discussion
13.1 Implementation and Data Sets
13.1.1 Implementation
13.1.2 Used Data Sets
13.2 Results
13.2.1 Speed
13.2.2 Proportion of False Positives
13.2.2.1 Study of Full Human Body Matchings
13.2.2.2 Study of Hand Matchings
13.2.3 Output Pose Samples
13.2.4 Discussion
13.3 Possible Usages of our Method
13.3.1 Combination with Tracking
13.3.1.1 Combination with Model Free Tracking
13.3.1.2 Combination with Model-Based Tracking
13.3.2 Specific Pose Detection and Pose Clustering
13.3.2.1 Specific Pose Detection
13.3.2.2 Pose Clustering
V Conclusion
14 Conclusion
14.1 Contributions
14.2 Future Works
Bibliography
