Computed tomography is a very useful technic which allow non-invasive diagnosis in many applications for example is used with success in industry and medicine. However, manual analysis of the interesting structures can be tedious and extremely time consuming, or even impossible due its complexity. Therefore in this thesis we study and develop discrete geometry and topology algorithms suitable for use in many practical applications, especially, in the problem of automatic quantitative analysis of the human airway trees based on computed tomography images. In the first part, we define basic notions used in discrete topology and geometry then we showed that several class of discrete methods like skeletonisation algorithms, medial axes, tunnels closing algorithms and tangent estimators, are widely used in several different practical application. The second part consist of a proposition and theory of a new methods for solving particular problems. We introduced two new medial axis filtering method. The hierarchical scale medial axis which is based on previously proposed scale axis transform, however, is free of drawbacks introduced in the previously proposed method and the discrete adaptive medial axis where the filtering parameter is dynamically adapted to the local size of the object. In this part we also introduced an efficient and parameter less new tangent estimators along three-dimensional discrete curves, called 3D maximal segment tangent direction. Finally, we showed that discrete geometry and topology algorithms can be useful in the problem of quantitative analysis of the human airway trees based on computed tomography images. According to proposed in the literature design of such system we applied discrete topology and geometry algorithms to solve particular problems at each step of the quantitative analysis process. First, we propose a robust method for segmenting airway tree from CT datasets. The method is based on the tunnel closing algorithm and is used as a tool to repair, damaged by acquisition errors, CT images. We also proposed an algorithm for creation of an artificial model of the bronchial tree and we used such model to validate algorithms presented in this work. Then, we compare the quality of different algorithms using set of experiments conducted on computer phantoms and real CT dataset. We show that recently proposed methods which works in cubical complex framework, together with methods introduced in this work can overcome problems reported in the literature and can be a good basis for the further implementation of the system for automatic quantification of bronchial tree properties
Authors
- Bibliographic Reference
- Michal Postolski. Discrete topology and geometry algorithms for quantitative human airway trees analysis based on computed tomography images. Other. Université Paris-Est, 2013. English. ⟨NNT : 2013PEST1094⟩. ⟨pastel-00977514⟩
- HAL Collection
- ['PASTEL - ParisTech', 'ParisTech', 'Ecole des Ponts ParisTech', 'CNRS - Centre national de la recherche scientifique', 'Université de Marne la Vallée', 'Algorithms, architectures, image analysis and computer graphics', "Laboratoire d'informatique Gaspard-Monge", 'STAR - Dépôt national des thèses électroniques', "CV des membres de l'Université de Marne-la-vallée", 'CV des membres du LIGM', 'ESIEE Paris', 'Université Gustave Eiffel', 'Université Paris-Est Marne-la-Vallée', 'TEST3-HALCNRS']
- HAL Identifier
- 977514
- Institution
- ['Université Paris-Est Marne-la-Vallée', 'École des Ponts ParisTech', 'ESIEE Paris', 'Fédération de Recherche Bézout']
- Laboratory
- Laboratoire d'Informatique Gaspard-Monge
- Published in
- France
Table of Contents
- List of Figures 14
- List of Tables 22
- List of Algorithms 23
- Nomenclature 24
- 1 Introduction 26
- 1.1 Background 26
- 1.2 Aims and Objectives 27
- 1.3 Contributions and Contents 27
- 1.4 Main Thesis of This Work 28
- I State of The Art 30
- 2 Basic Notions 31
- 2.1 The Digital Topology Framework 31
- 2.1.1 Discrete objects 31
- 2.1.2 Euclidean distance and distance transform 31
- 2.1.3 Adjacency relations and neighborhood of a point 32
- 2.1.4 Discrete binary image 33
- 2.1.5 Connected components, cavities, holes and tunnels 34
- 2.1.6 Euclidean balls 35
- 2.1.7 Simple points in 2D 36
- 2.2 The Cubical Complex Framework 36
- 2.2.1 Elements in cubical complex framework 37
- 2.2.2 Cells and cubical complex sets 38
- 2.2.3 Facets in complexes 38
- 2.3 From Binary Images to Cubical Complex 38
- 3 Simplification of Binary Shapes 40
- 3.1 Skeleton Characteristics 43
- 3.2 Skeletonization Methodologies 46
- 3.3 Thinning in The Digital Topology Framework 48
- 3.3.1 Sequential thinning algorithms 49
- 3.3.2 Fully parallel thinning algorithms 51
- 3.3.3 Directional thinning algorithms 53
- 3.3.4 Subfield thinning algorithms 54
- 3.4 Thinning in The Cubical Complex Framework 55
- 3.4.1 Critical kernels based thinning 55
- 3.4.2 Collapse based thinning 56
- 4 Preserving Visual Aspects of a Binary Shape 57
- 4.1 Medial Axis 57
- 4.2 Medial Axis Filtering 59
- 4.2.1 Filtering based on medial ball size 60
- 4.2.2 Filtering based on ball covering 60
- 4.2.3 -medial axis 61
- 4.2.4 Filtering based on the bisector angle 64
- 4.2.5 Scale axis 65
- 4.3 Euclidean Opening Function 66
- 5 Visual and Topological Correction of Binary Shapes 68
- 5.1 The Tunnel Closing Algorithm 70
- 5.1.1 Topological hull 71
- 5.1.2 Topological hull directed by the distance transform 71
- 5.1.3 -closing algorithm 72
- 5.2 Properties and Limitations of the Tunnel Closing Algorithm 74
- 5.3 Application of The Tunnel Closing Algorithm 76
- 6 Extracting Geometrical Properties of Binary Shapes 79
- 6.1 Discrete Curves 82
- 6.2 Continuous Tangent Estimators 83
- 6.3 Discrete Tangent Estimators 85
- 6.3.1 Local discrete tangent estimators 85
- 6.3.2 Local adaptive discrete tangent estimators 87
- 6.3.3 2D -maximal segment tangent direction 89
- II Theory and Algorithms 92
- 7 Medial Axis Filtering with Features at Different Scales 93
- 7.1 Discrete Adaptive Medial Axis 93
- 7.2 Discrete Scale Axis 98
- 7.3 Hierarchical Scale Medial Axis 99
- 7.3.1 The s-scale filtered Euclidean medial axis 99
- 7.3.2 Algorithm for computing the hierarchical scale medial axis 102
- 7.4 Comparison of Medial Axis Filtering Methods 106
- 7.4.1 The reconstruction error 107
- 7.4.2 The size of medial axis 109
- 7.4.3 The border dissimilarity 112
- 7.4.4 The complexity of the skeleton 115
- 7.4.5 The multiscale representations 117
- 7.4.6 Discussions 118
- 7.5 Conclusions 120
- 8 Tangent Estimator Along 3D Discrete Curve 122
- 8.1 3D Discrete Line Segment 122
- 8.2 3D Tangential Cover Construction 123
- 8.2.1 Complexity evaluation 123
- 8.3 Three-dimensional -MSTD Estimator 124
- 8.4 Experiments on Parametric Curves 126
- 8.4.1 Multigrid convergence 126
- 8.4.2 Results and discussion 126
- III Verification and Application 136
- 9 Quantitative Analysis of The Human Airway Trees 137
- 9.1 Introduction 137
- 9.2 System Design 139
- 9.2.1 Airway tree identification 139
- 9.2.2 Airway tree simplification 141
- 9.2.3 Generation of the formal tree structure 143
- 9.2.4 Quantitative analysis 145
- 10 Three dimensional model of The Human Airway Trees 147
- 10.1 Basic Model of Bronchial Trees 148
- 10.2 Extended Algorithm of Bronchial Tree Modeling 152
- 10.2.1 Geometric deformations of surface model 152
- 10.2.2 Transformations of the surface model to volumetric model 153
- 10.2.3 Distortions introduced to in a volumetric model of bronchial tree 153
- 11 Robust Segmentation of The Human Airway Trees 156
- 11.1 Airway Tree Segmentation Based on Tunnel Closing 156
- 11.1.1 Histogram analysis and preliminary wall extraction 156
- 11.1.2 3D tunnel closing in airway walls 158
- 11.1.3 Merging and final segmentation 158
- 11.2 Segmentation Algorithms Comparison 159
- 12 Robust 3D Skeletonisation of Pulmonary Airway Tree Structures 164
- 12.1 Skeleton Centricity 165
- 12.2 Robustness to Noise 167
- 12.3 Discussion 168
- 13 Accurate Cross Sections Generation of The Human Airways Trees 175
- 13.1 Methodology of Tangent Estimators Comparison 175
- 13.2 Results and Discussion 177
- 14 Conclusions 181
- 14.1 Contribution of this thesis 182
- Bibliography 184