Kaleem Siddiqi

Medial Representations: Mathematics, Algorithms and Applications - Computational Imaging and Vision Kaleem Siddiqi 2008 edition

Marc Notes: Includes bibliographical references and index. Jacket Description/Back: The last half century has seen the development of many biological or physical theories that have explicitly or implicitly involved medial descriptions of objects and other spatial entities in our world. Simultaneously mathematicians have studied the properties of these skeletal descriptions of shape, and, stimulated by the many areas where medial models are useful, computer scientists and engineers have developed numerous algorithms for computing and using these models. We bring this knowledge and experience together into this book in order to make medial technology more widely understood and used. Edited by Prof. K. Siddiqi and Prof. S. Pizer, renowned experts in the field and authors of five of the chapters, this book consists of an introductory chapter, two chapters on the major mathematical results on medial representations, five chapters on algorithms for extracting medial models from boundary or binary image descriptions of objects, and three chapters on applications in image analysis and other areas of study and design. These chapters have been integrated and combined with a mathematics notation appendix and a detailed glossary, bibliography and index. This book will serve the science and engineering communities using medial models and will provide learning material for students entering this field. Table of Contents: 1. Introduction / Stephen Pizer, Kaleem Siddiqi, Paul Yushkevich -- 1.1. Object Representations -- 1.2. Medial Representations of Objects -- 1.2.1. The Definition of the Medial Locus -- 1.2.2. Structural Geometry of Medial Loci -- 1.2.3. Local Geometry of Medial Loci -- 1.2.4. Medial Atoms and M-Reps -- 1.3. Psychophysical and Neurophysiological Evidence for Medial Loci -- 1.4. Extracting Medial Loci of Objects -- 1.4.1. Distance Transforms, the Hessian, Thinning and Pruning -- 1.4.2. Skeletons via Shocks of Boundary Evolution -- 1.4.3. Greyscale Skeletons -- 1.4.4. Core Tracking -- 1.4.5. Skeletons from Digital Distance Transforms -- 1.4.6. Voronoi Skeletons -- 1.4.7. Skeletonization by Deformable Medial Models -- 1.5. Applications of Medial Loci in Computer Vision -- Part I. Mathematics -- 2. Local Forms and Transitions of the Medial Axis / Peter J. Giblin, Benjamin B. Kimia -- 2.1. Introduction -- 2.2. Definitions -- 2.3. Contact -- 2.4. Local Forms of the Symmetry Set and Medial Axis in 2D -- 2.5. Local Forms of the Medial Axis in 3D -- 2.6. Local Reconstruction from the Symmetry Set or Medial Axis in 2D -- 2.7. Local Reconstruction from the Symmetry Set or Medial Axis in 3D -- 2.8. Symmetry Sets and Medial Axes of Families of Curves -- 2.9. Medial Axes of Families of Surfaces -- 2.10. Consistency Conditions at Branches -- 2.11. Summary -- 3. Geometry and Medial Structure / James Damon -- 3.1. Introduction -- 3.2. Medial Data on Skeletal Structures -- 3.2.1. Blum Medial Axis and General Skeletal Structures -- 3.2.2. Radial Flow Defined for a Skeletal Structure -- 3.2.3. Radial and Edge Shape Operators for 1D and 2D Medial Structures -- 3.2.4. Level Set Structure of a Region and Smoothness of the Boundary -- 3.3. Local and Relative Geometry of the Boundary -- 3.3.1. Intrinsic Differential Geometry of the Boundary -- 3.3.2. Geometric Medial Map -- 3.3.3. Deformations of Skeletal Structures and Boundary Smoothness and Geometry -- 3.4. Global Geometry of a Region and Its Boundary -- 3.4.1. Skeletal and Medial Integrals -- 3.4.2. Global Integrals as Skeletal and Medial Integrals -- 3.4.3. Consequences for Global Geometry -- 3.4.4. Expansion of Integrals in Terms of Moment Integrals -- 3.4.5. Divergence Theorem for Fluxes with Discontinuities Across the Medial Axis -- 3.4.6. Computing the Average Outward Flux for the Grassfire Flow -- 3.5. Global Structure of the Medial Axis -- 3.5.1. Graph Structure for Decomposition into Irreducible Medial Components -- 3.5.2. Graph Structure of a Single Irreducible Medial Component -- 3.5.3. Consequences for the Topology of the Medial Axis and Region -- 3.6. Summary -- Part II. Algorithms -- 4. Skeletons via Shocks of Boundary Evolution / Kaleem Siddiqi, Sylvain Bouix, Jayant Shah -- 4.1. Overview -- 4.2. Optics, Mechanics and Hamilton-Jacobi Skeletons -- 4.2.1. Medial Loci and the Eikonal Equation -- 4.2.2. Hamiltonian Derivation of the Eikonal Equation -- 4.2.3. Divergence, Average Outward Flux and Object Angle -- 4.3. Homotopy Preserving Medial Loci -- 4.3.1. 2D Simple Points -- 4.3.2. 3D Simple Points -- 4.3.3. Average Outward Flux Ordered Thinning -- 4.3.4. The Algorithm and Its Complexity -- 4.3.5. Labeling the Medial Set -- 4.3.6. Examples -- 4.4. An Object Angle Approach -- 4.4.1. Examples -- 4.5. Discussion and Conclusion -- 5. Discrete Skeletons from Distance Transforms in 2D and 3D / Gunilla Borgefors, Ingela Nystrom, Gabriella Sanniti di Baja -- 5.1. Introduction -- 5.2. Definitions and Notions -- 5.3. Distance Transforms -- 5.3.1. 2D Distance Transforms -- 5.3.2. 3D Distance Transforms -- 5.3.3. Euclidean Distance Transforms -- 5.4. Centers of Maximal Disks/Balls -- 5.4.1. Centers of Maximal Disks -- 5.4.2. Centers of Maximal Balls -- 5.4.3. Reduced Set of Centers of Maximal Objects -- 5.4.4. Reverse Distance Transforms -- 5.4.5. Role of Centers of Maximal Objects in Skeletons -- 5.5. Skeletons of 2D Shapes -- 5.5.1. Computing the Nearly-Thin 2D Skeleton -- 5.5.2. Post-Processing, 2D Case -- 5.6. Skeletons of 3D Shapes -- 5.6.1. Computing the Nearly-Thin Surface Skeleton -- 5.6.2. Post-Processing, Surface Skeleton -- 5.6.3. Computing the Nearly-Thin Curve Skeleton -- 5.6.4. Post-Processing, Curve Skeleton -- 5.7. Some Applications and Extensions -- 6. Voronoi Skeletons / Gabor Szekely -- 6.1. The Voronoi Skeleton and Its Extraction in 2D -- 6.1.1. Basics -- 6.1.2. The Boundary Sampling Problem -- 6.1.3. Generation of the Voronoi Diagram -- 6.1.4. From Voronoi Diagrams to Skeletons -- 6.1.5. Topological Organization of the 2D Skeleton -- 6.1.6. The Salience of 2D Skeletal Branches -- 6.1.7. Pruning the 2D Voronoi Skeleton -- 6.1.8. A Hierarchy of Skeleton Branches -- 6.2. The Voronoi Skeleton in 3D -- 6.2.1. 3D Voronoi Diagram Generation -- 6.2.2. Topological Organization of the 3D Voronoi Skeleton -- 6.2.3. The Salience of 3D Skeletal Branches -- 6.2.4. Pruning the 3D Voronoi Skeleton -- 6.2.5. Interactive Generation of Skeletal Hierarchy in 3D -- 6.3. Application Examples -- 6.3.1. Skeletons of Artificial 3D Objects -- 6.3.2. Bone Thickness Characterization Using Skeletonization -- 6.3.3. Analysis of the Cortical Structure of the Brain -- 6.4. Discussion -- 7. Voronoi Methods for 3D Medial Axis Approximation / Nina Amenta, Sunghee Choi -- 7.1. Introduction -- 7.2. Approximating the Medial Axis -- 7.2.1. A Few 2D Results -- 7.2.2. Slivers -- 7.3. Sampling and Approximation -- 7.3.1. Stable Subsets of the Medial Axis -- 7.3.2. [lambda]-Medial Axis and Uniform Sampling -- 7.3.3. [gamma]-Medial Axis and Scale-Invariant Sampling -- 7.4. Medial Axis Algorithms for Input Point Clouds -- 7.4.1. Anti-Crust -- 7.4.2. Thinning Algorithms -- 7.4.3. Power Shape -- 7.5. Medial Axis Algorithms for Input Surfaces -- 7.6. Discussion -- 8. Synthesis, Deformation, and Statistics of 3D Objects via M-Reps / Stephen Pizer, Qiong Han, Sarang Joshi, P. Thomas Fletcher, Paul A. Yushkevich, Andrew Thall -- 8.1. Introduction -- 8.2. M-Reps, Medial Atoms, and Figures -- 8.3. Object-Relative Coordinates -- 8.4. Figures, Subfigures, and Multi-Object Ensembles -- 8.5. Synthesis of Objects and Multi-Object Ensembles by Multiscale Figural Description -- 8.6. M-Reps as Symmetric Spaces -- 8.7. The Statistical View of Objects -- 8.8. Discrete M-Reps -- 8.9. Correspondence of Discrete M-Reps in Families of Training Cases -- 8.10. Continuous M-Reps via Splines or Other Basis Functions -- 8.11. Summary and Conclusion -- Part III. Applications -- 9. Statistical Applications with Deformable M-Reps / Stephen Pizer, Martin Styner, Timothy Terriberry, Robert Broadhurst, Sarang Joshi, Edward Chaney, P. Thomas Fletcher -- 9.1. Introduction and Statistical Formulation -- 9.2. Segmentation by Posterior Optimization of Deformable M-Reps: Overview -- 9.2.1. Segmentation Method: Posterior Optimization for Multiscale Deformation of Figurally Based Models -- 9.2.2. Segmentation Method: User Operation -- 9.3. Training and Measuring Statistical Geometric Typicality -- 9.3.1. M-Rep Model Fitting and Geometric Statistics Formation -- 9.3.2. Measuring Statistical Geometric Typicality -- 9.4. Training and Measuring Statistical Geometry-to-Image Match -- 9.4.1. Transforming Between Figural and Euclidean Coordinates -- 9.4.2. Geometry-to-Image Match via Statistics on Discrete Regional Quantile Functions -- 9.5. Pablo Details and Results -- 9.5.1. The Voxel-Scale Stage of Segmentation -- 9.5.2. Evaluation of Segmentations -- 9.6. Hypothesis Testing for Localized Shape Differences Between Groups -- 9.6.1. Tests in Euclidean Space -- 9.6.2. Tests in Symmetric Spaces -- 9.7. Applications of Hypothesis Testing to Brain Structure Shape Differences in Neuro-Imaging -- 9.7.1. Hippocampus Study in Schizophrenia -- 9.7.2. Lateral Ventricle Study of Healthy and Schizophrenic Twins -- 9.8. Discussion and Future Work -- 9.8.1. Are M-Reps Effective? -- 9.8.2. Other M-Rep Uses and Properties -- 10. 3D Model Retrieval Using Medial Surfaces / Kaleem Siddiqi, Juan Zhang, Diego Macrini, Sven Dickinson, Ali Shokoufandeh -- 10.1. Introduction -- 10.1.1. Graph Edit Distance Approaches -- 10.1.2. Subgraph Isomorphism Approaches -- 10.1.3. Graph Spectral Approaches -- 10.2. 3D Model Retrieval -- 10.3. Medial Surfaces and DAGs -- 10.4. Indexing -- 10.5. Matching -- 10.5.1. Node Similarity -- 10.6. Experimental Results -- 10.6.1. Matching Results -- 10.6.2. Indexing Results -- 10.7. Discussion and Conclusion -- 11. From the Infinitely Large to the Infinitely Small / Frederic F. Leymarie, Benjamin B. Kimia -- 11.1. Introduction -- 11.2. Formation and Description of Galaxies -- 11.3. Geography: Topography, Cartography, Networks -- 11.4. From Urbanism to Architecture and Archaeology -- 11.5. From Garden Layouts to the Genesis of Plants -- 11.6. Visual Arts: Painting, Drawing, Sculpting -- 11.7. Motion Analysis, Body Animation, Robotics -- 11.8. Machining, Metal Forging, Industrial Design, Object Registration -- 11.9. Medicine and Biology -- 11.9.1. Object Segmentation from Images -- 11.9.2. Path Planning and Virtual Endoscopy -- 11.9.3. Morphometry, Branching Tree-like Structures -- 11.9.4. Growth, Form Genesis -- 11.9.5. Deformation and Motion of Cells -- 11.9.6. Recognition: From Tissues to Cellular Material -- 11.10. Crystallography, Chemistry, Molecular Design -- 11.11. Perception and Cognition -- 11.12. Conclusion -- A. Notation -- A.1. Common Notation -- A.2. Chapter 1 -- A.3. Chapter 2 -- A.4. Chapter 3 -- A.5. Chapter 4 -- A.6. Chapter 5 -- A.7. Chapter 6 -- A.8. Chapter 7 -- A.9. Chapter 9 -- A.10. Chapter 10 -- Glossary -- References -- Index. Publisher Marketing: The last half century has seen the development of many biological or physical t- ories that have explicitly or implicitly involved medial descriptions of objects and other spatial entities in our world. Simultaneously mathematicians have studied the properties of these skeletal descriptions of shape, and, stimulated by the many areas where medial models are useful, computer scientists and engineers have developed numerous algorithms for computing and using these models. We bring this kno- edge and experience together into this book in order to make medial technology more widely understood and used. The book consists of an introductory chapter, two chapters on the major mat- matical results on medial representations, ?ve chapters on algorithms for extracting medial models from boundary or binary image descriptions of objects, and three chapters on applications in image analysis and other areas of study and design. We hope that this book will serve the science and engineering communities using medial models and will provide learning material for students entering this ?eld. We are fortunate to have recruited many of the world leaders in medial theory, algorithms, and applications to write chapters in this book. We thank them for their signi?cant effort in preparing their contributions. We have edited these chapters and have combined them with the ?ve chapters that we have written to produce an integrated whole.