Digital Geometry Algorithms: Theoretical Foundations and Applications to Computational Imaging

Cover
Digital Geometry Algorithms
	Preface
	Contents
	Contributors
Chapter 1: Digital Geometry in Image-Based Metrology
	1.1 Introduction
	1.2 The Digitization Model and the Metrology Tasks
	1.3 Self Similarity of Digital Lines
	1.4 Digital Straight Segments: Their Characterization and Recognition
	1.5 Digital Disks, Convex and Star-Shaped Objects
	1.6 Shape Designs for Good Metrology
	1.7 The Importance of Being Gray
	1.8 Some Further Open Questions
	1.9 Concluding Remarks
	References
Chapter 2: Provably Robust Simplification of Component Trees of Multidimensional Images
	2.1 Introduction
	2.2 Foreground Component Tree Structures (FCTSs)
	2.3 The (lambda, k)-Simplification of a kappa-FCTS, Essential Isomorphism, and the Main Theorem
	2.4 Pruning by Removing Branches of Length <=lambda
		2.4.1 Specification of Simplification Step 2
		2.4.2 An Easily Visualized Characterization of the Output of Simplification Step 2
		2.4.3 Linear-Time Implementation of Simplification Step 2
	2.5 Elimination of Internal Edges of Length <=lambda from Fcrit
		2.5.1 Specification of Simplification Step 3
		2.5.2 Implementation of Simplification Step 3
	2.6 Demonstration of Potential Biological Applicability
	2.7 Possibilities for Future Work
		2.7.1 How Can Our Simplification Method and Theorem 1 Be Adapted to Contour Trees?
		2.7.2 Does the Bottleneck Stability Theorem Have an Analog for FCTSs That Implies Theorem 1?
		2.7.3 Can Images Be Simplified Using Variants of Our Method?
	2.8 Conclusion
	Appendix A:  Some Properties of Simplification Steps 2 and 3, and a Proof of the Correctness of Algorithm 1
		A.1 Properties of Simplification Step 2
		A.2 Properties of Simplification Step 3
		A.3 Justification of Algorithm 1
	Appendix B:  A Constructive Proof of Theorem 1
		B.1 Step 1 of the Proof of the Fundamental Lemma
		B.2 Some Useful Observations
		B.3 Step 2 of the Proof of the Fundamental Lemma
		B.4 Step 3 of the Proof of the Fundamental Lemma
	Appendix C:  Justification of Assertions L, M, N, and O in Step 3 of the Proof of the Fundamental Lemma
		C.1 Proof of Assertion L
		C.2 Proof of Assertion M
		C.3 Proof of Assertion N
		C.4 Proof of Assertion O
	References
Chapter 3: Discrete Topological Transformations for Image Processing
	3.1 Introduction
	3.2 Topological Transformations of Binary Images
		3.2.1 Neighborhoods, Connectedness
		3.2.2 Connectivity Numbers
		3.2.3 Topological Classification of Object Points
		3.2.4 Topology-Preserving Transformations
		3.2.5 Transformations Guided by a Priority Function
		3.2.6 Lambda-Medial Axis
		3.2.7 Other Applications of Guided Thinning
		3.2.8 Hole Closing
	3.3 Topological Transformations for Grayscale Images
		3.3.1 Cross-Section Topology
		3.3.2 Local Characterizations and Topological Classification of Points
		3.3.3 Topological Filtering
		3.3.4 Topological Segmentation
		3.3.5 Crest Restoration Based on Topology
	3.4 Parallel Thinning
		3.4.1 Cubical Complexes
		3.4.2 Collapse and Simple Facets
		3.4.3 Critical Kernels
		3.4.4 Crucial Cliques and Faces
		3.4.5 Parallel Thinning Algorithms
	3.5 Perspectives
	3.6 Conclusion
	References
Chapter 4: Modeling and Manipulating Cell Complexes in Two, Three and Higher Dimensions
	4.1 Introduction
	4.2 Background Notions
	4.3 Data Structures for Cell Complexes: An Overview
	4.4 Dimension-Independent Data Structures
	4.5 Data Structures for Two-Dimensional Cell Complexes
		4.5.1 Representing Manifold 2-Complexes
		4.5.2 Representing Non-manifold 2-Complexes
	4.6 Data Structures for Three-Dimensional Cell Complexes
	4.7 Manipulation Operators on Cell Complexes: An Overview
		4.7.1 Collapse Operators on Simplicial Complexes
		4.7.2 Stellar Operators
		4.7.3 Handle Operators
	4.8 Euler Operators on Cell Complexes: An Overview
		4.8.1 Euler-Poincaré Formula for Cell Complexes
		4.8.2 Euler-Poincaré Formula for General Complexes
		4.8.3 Classification of Euler Operators
		4.8.4 MEV, MEF and MEKR Operators
	4.9 Euler Operators on Manifolds
		4.9.1 Euler Operators on Manifold 2-Complexes Bounding a Solid (Boundary Representations)
		4.9.2 Splice Operator
	4.10 Euler Operators on Non-manifolds
		4.10.1 Euler Operators for 2-Complexes
		4.10.2 Euler Operators on 3-Complexes
	4.11 Discussion
	References
Chapter 5: Binarization of Gray-Level Images Based on Skeleton Region Growing
	5.1 Introduction
	5.2 Skeleton Strength Map (SSM)
		5.2.1 Computation of the Skeleton Strength Map
		5.2.2 Comparison Between SSM and Distance Transform
	5.3 Skeletonization of Binary Images
		5.3.1 Local Maxima Detection
		5.3.2 Local Maxima Connection
	5.4 Skeletonization of Gray-Scale Images
		5.4.1 Noise Smoothing of Boundaries
		5.4.2 Computation of SSM from Gray-Scale Images
		5.4.3 Robustness Under Boundary Noise and Deformation
		5.4.4 Results on Gray-Scale Images
	5.5 Binarization of Gray-Level Images Based on Their Skeletons
		5.5.1 Seeds Selection
		5.5.2 Classifying Skeleton Segments into Foreground and Background
		5.5.3 Dynamic Threshold Computation
		5.5.4 Region Growing Algorithm
	5.6 Experimental Results and Analysis
	5.7 Future Work and Open Problems
	References
Chapter 6: Topology Preserving Parallel 3D Thinning Algorithms
	6.1 Introduction
	6.2 Topology Preserving Parallel Reduction Operations
	6.3 Variations on Parallel 3D Thinning Algorithms
		6.3.1 Fully Parallel Algorithms
		6.3.2 Subiteration-Based Algorithms
		6.3.3 Subfield-Based Algorithms
	6.4 Implementation
	6.5 Results
	6.6 Possible Future Works and Open Problems
	6.7 Concluding Remarks
	References
Chapter 7: Separable Distance Transformation and Its Applications
	7.1 Introduction
	7.2 Distance Transformation and Discrete Medial Axis Extraction
		7.2.1 Distances
		7.2.2 Distance Transformation
		7.2.3 Reverse Distance Transformation
		7.2.4 Medial Axis Extraction
		7.2.5 Voronoi Diagrams and Power Diagrams
			7.2.5.1 E2DT and Voronoi Diagram
			7.2.5.2 REDT and Power Diagram
	7.3 Extensions and Generalizations
		7.3.1 Irregular Grids
			7.3.1.1 E2DT Computation on I-Grids
		7.3.2 Toric Domains
	7.4 High Performance Computation
		7.4.1 Parallel Computation
		7.4.2 Out-of-Core Approaches
	7.5 Discussion and Open Problems
	References
Chapter 8: Separability and Tight Enclosure of Point Sets
	8.1 Introduction
	8.2 Separation Maps and Parameter Domains
		8.2.1 Affine Function Spaces
		8.2.2 Separation by Sign Maps
		8.2.3 Domains of Functions
		8.2.4 Minimal Separations
	8.3 Lattice Structure of a Domain
		8.3.1 Leaning Points and Surfaces
		8.3.2 Lifting Map
		8.3.3 Separation Extensions
	8.4 Enclosure and Separation with Elemental Subsets
		8.4.1 Tight Enclosure and Separation
		8.4.2 Elemental Subsets
		8.4.3 Tight Enclosure of Large Set
		8.4.4 Tight Separation of Sets
	8.5 Classification of Domains
		8.5.1 Simplices
		8.5.2 More Complex Domains
	8.6 Concluding Remarks and Open Problems
	References
Chapter 9: Digital Straightness, Circularity, and Their Applications to Image Analysis
	9.1 Introduction
	9.2 Digital Straightness
		9.2.1 Properties of Digital Straightness
		9.2.2 Approximate Straightness
		9.2.3 Extraction of ADSS
		9.2.4 Algorithm Extract-ADSS
	9.3 Digital Circularity
		9.3.1 Existing Works
		9.3.2 Down the Top Run
			9.3.2.1 Nesting the Radii
			9.3.2.2 The Algorithm DCT
		9.3.3 General Case
			9.3.3.1 The Algorithm DCG
	9.4 Polygonal Approximation
		9.4.1 Approximation Criterion
			9.4.1.1 Cumulative Error (Criterion C)
			9.4.1.2 Maximum Error (Criterion Cmax)
		9.4.2 Algorithm for Polygonal Approximation
		9.4.3 Quality of Approximation
		9.4.4 Experimental Results
	9.5 Circular Arc Segmentation
		9.5.1 Finding the Intersection Points
		9.5.2 Storing the Curve Segments
		9.5.3 Deviations of Chord Property
		9.5.4 Verifying the Circularity
		9.5.5 Combining the Arcs
		9.5.6 Finalizing the Centers and Radii
		9.5.7 Some Results
	9.6 Future Work and Open Problems
	9.7 Conclusion
	References
Chapter 10: Shape Analysis with Geometric Primitives
	10.1 Introduction
	10.2 The Tangential Cover
		10.2.1 Shapes as Digital Curves
		10.2.2 Digital Straight Segments
		10.2.3 The Tangential Cover
	10.3 Generic Shape Representation
		10.3.1 Shapes as Connected Components
		10.3.2 alpha-Path on Connected Components
			10.3.2.1 Decomposition into Branches
			10.3.2.2 Ordering the Branches
	10.4 Geometric Primitives
		10.4.1 Blurred Straight Segments
		10.4.2 Digital Circular Arcs and Annulus
	10.5 The Predicate Cover
	10.6 Multi-primitives Analysis
		10.6.1 alpha-Blurred Straight Segments Versus alpha\'-Thick Digital Arcs
		10.6.2 Building the Complete Tree
			10.6.2.1 The Choice of the Starting Point
		10.6.3 A Partial Tree
			10.6.3.1 Our Criterion
		10.6.4 Experimental Results
	10.7 Future Work and Open Problems
	References
Chapter 11: Shape from Silhouettes in Discrete Space
	11.1 Introduction
	11.2 Shape Reconstruction
		11.2.1 Silhouettes and Support Hyperplanes
		11.2.2 Reconstruction of Non-convex Objects
	11.3 Mathematical Preliminaries
		11.3.1 Connectivity of Pixels and Voxels
		11.3.2 Discrete Linear Objects
			11.3.2.1 Discrete Planar Lines
			11.3.2.2 Discrete Spatial Lines
			11.3.2.3 Discrete Planes
		11.3.3 Discrete Polygons and Polyhedra
	11.4 Shape Reconstruction in Discrete Space
		11.4.1 Reconstruction of Space and Object
		11.4.2 Convex Hull and Visual Hull in Discrete Space
		11.4.3 Proof of Theorem 16
			11.4.3.1 Two-Dimensional Case
			11.4.3.2 Three-Dimensional Case
		11.4.4 Non-convex Case
	11.5 Examples
	11.6 Discussion
		11.6.1 Reconstruction of Spatial String
		11.6.2 Shape Carving
		11.6.3 Approximation of the Hybrid Model
		11.6.4 Open Problems
	11.7 Conclusions
	References
Chapter 12: Combinatorial Maps for 2D and 3D Image Segmentation
	12.1 Introduction
	12.2 Topological Maps
		12.2.1 Combinatorial Maps
		12.2.2 Removal Operations
		12.2.3 Images, Regions and Inter-elements
		12.2.4 Topological Maps
	12.3 Image Segmentation Algorithm
		12.3.1 The Global Merging Algorithm
		12.3.2 The Segmentation Algorithm
		12.3.3 Different Criteria of Segmentation
			12.3.3.1 Range of Gray Levels
			12.3.3.2 Gradient on (n-1)-Cells
			12.3.3.3 External and Internal Contrasts
			12.3.3.4 Size of Regions
	12.4 Betti Numbers and Topological Criteria
		12.4.1 Betti Numbers
		12.4.2 Computation Algorithms Using Topological Maps
			12.4.2.1 Computation of Betti Numbers in 2D Image Partition
			12.4.2.2 Computation of Betti Numbers in 3D Image Partition
			12.4.2.3 Computation of the Second Betti Number in 3D Image Partition
		12.4.3 Incremental Computation Algorithms
			12.4.3.1 Incremental Computation of the Number of Cavities
			12.4.3.2 Incremental Computation of the Number of Tunnels in 3D
		12.4.4 Implementation of Topological Criteria in the Segmentation
	12.5 Experimental Results
		12.5.1 Generic Criteria
		12.5.2 Constraint on Betti Numbers
	12.6 Open Problems and Discussion
	References
Chapter 13: Multigrid Convergence of Discrete Geometric Estimators
	13.1 Introduction
	13.2 Global Estimators
		13.2.1 Multigrid Convergence for Global Estimators
		13.2.2 Area and Moments
		13.2.3 Perimeter and Length Estimators
		13.2.4 Summary
	13.3 Local Estimators
		13.3.1 Multigrid Convergence for Local Estimators
		13.3.2 Methodology for Experimental Evaluation
	13.4 Tangent
		13.4.1 Tangent Estimators
		13.4.2 Experimental Evaluation
	13.5 Curvature
		13.5.1 Curvature Estimators
		13.5.2 Experimental Evaluation
	13.6 Implementation
	13.7 Related Problems and Perspectives
		13.7.1 Geometric Estimators Along Damaged or Noisy Contours
		13.7.2 Geometric Estimators in 3D and nD
		13.7.3 Current Bottlenecks and Open Problems
	References
Index