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**