Discrete Geometry for Computer Imagery
16th IAPR International Conference, DGCI 2011, Nancy, France, April 6-8, 2011, Proceedings
Published on 29. March 2011
XIV, 526 pages
978-3-642-19867-0 (ISBN)
Description
This book constitutes the refereed proceedings of the 16th IAPR International Conference on Discrete Geometry for Computer Imagery, DGCI 2011, held in Nancy, France, in April 2011.
The 20 revised full papers and 20 revised poster papers presented together with 3 invited lectures were carefully reviewed and selected from numerous submissions. The papers are organized in topical sections on models for discrete geometry, discrete and combinatorial topology, geometric transforms, discrete shape representation, recognition and analysis, discrete tomography, morphological analysis, as well as discrete and combinatorial tools for image segmentation and analysis.
The 20 revised full papers and 20 revised poster papers presented together with 3 invited lectures were carefully reviewed and selected from numerous submissions. The papers are organized in topical sections on models for discrete geometry, discrete and combinatorial topology, geometric transforms, discrete shape representation, recognition and analysis, discrete tomography, morphological analysis, as well as discrete and combinatorial tools for image segmentation and analysis.
More details
Other editions
Additional editions
Isabelle Debled-Rennesson | Eric Domenjoud | Bertrand Kerautret
Discrete Geometry for Computer Imagery
16th IAPR International Conference, DGCI 2011, Nancy, France, April 6-8, 2011, Proceedings
Book
03/2011
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- Title
- Preface
- Organization
- Table of Contents
- Invited Speakers
- A Probabilistic Grouping Principle to Go from Pixels to Visual Structures
- Introduction
- Helmholtz Principle
- Gestalt Theory
- A Computational Tool: The Number of False Alarms
- Examples
- Alignments in an Image
- Meaningful Boundaries
- Meaningful Good Continuations
- Similarity of a Scalar Attribute
- Conclusion
- References
- Ball-Based Shape Processing
- Introduction
- Review of Key Concepts and Terminology
- Constant Radius Offsetting, Blending, and Tightening
- Variable Distance Offset Formulations
- Computation of the Offset Distance Field between Two Curves
- Compatibility
- Variable Radius Relative Blending
- Pearling Segmentation
- Shape Morphing and Midarc Averaging
- Conclusion
- References
- Hierarchies and Optima
- Introduction: Optimum Optimorum
- Hierarchies of Partitions
- Reminder
- Cuts in a Hierarchy
- Properties of the Hierarchies of Partitions
- Cuts of Minimum Energy in (E)
- Minimization under Hierarchical Increasingness
- Lattice of the Minimum Cuts
- Minimization with External Partitions
- Examples of Hierarchical Minimizations
- Suprema of Energies
- Additive Energies
- Other Laws of Composition
- Conclusion
- References
- Models for Discrete Geometry
- An Arithmetic and Combinatorial Approach to Three-Dimensional Discrete Lines
- Introduction
- Preliminaries
- Generalized Euclid's Algorithm
- Euclid's Substitutions
- A Zoo of Algorithms
- A Generation Method for Discrete Segments
- A Dual Viewpoint
- Discrete Planes
- Generalized Substitutions
- Dual Pattern
- Exchange of Pieces
- Conclusion
- References
- Smooth 2D Coordinate Systems on Discrete Surfaces
- Discrete Conformal Parameterizations
- Quad Meshes
- Triangular Meshes
- Digital Surfaces
- Boundary Conditions
- Solutions of the System
- Connection to Real Continuous Theory
- Connection to the cotan Conformal Coordinates
- Practical Computation
- Energy Minimization
- Initial Conditions
- Preservation of Lengths and Areas
- Results
- Comparison of the Energies
- Digital Surfaces
- Conclusion and Future Work
- References
- An Improved Riemannian Metric Approximation for Graph Cuts
- Introduction
- Preliminaries
- Cut Metrics
- Euclidean Metric Approximation
- Riemannian Metrics
- Introduction
- State of the Art
- Proposed Method
- Extension to 3D
- Experimental Results
- Discussion
- Conclusion
- References
- Introduction to Digital Level Layers
- About the Words
- Why This Kind of Primitives?
- Theory
- Functional and Algebraic DLL
- Topological Properties
- Morphological Property
- Comparison between DLL and Morphological Surfaces
- Algorithms
- Two Problems of Computational Geometry
- From Affine Strips to DLL Recognition: The Kernel Trick
- Conclusion
- References
- Another Definition for Digital Tangents
- Introduction
- Analytic Characterisation
- Combinatorial Description
- Renormalisation (Desubstitution)
- Last Step
- Example
- Complexity
- Balance
- Algorithm
- Other Classes of Curves
- Continuous Curves
- Ck Curves
- Analytic Curves
- Smooth Curves Defined on an Open Interval
- Smooth Curves with Nowhere Zero Curvature
- Curves Going in All Directions
- Conclusion
- References
- Associating Cell Complexes to Four Dimensional Digital Objects
- Introduction
- Preliminaries
- Constructing the Cell Complex Associated to a Given 4-Dimensional Digital Object
- Establishing the Grid and the Neighboring between the Points
- Cell Complex Obtention
- Conclusions and Results
- Results Obtained for Configurations of 4 Vertices of the Unit Hypercube
- Results Obtained for Configurations of 15 Vertices of the Unit Hypercube
- References
- Metric Bases for Polyhedral Gauges
- Introduction
- Norms and Gauges
- Preliminaries
- Gauges
- Chamfer Norms
- Metrics Bases for Polyhedral Gauges in Infinite Space
- Metric Bases for Gauges in Axes-Parallel Rectangles
- Results and Discussion
- Conclusion
- References
- Discrete and Combinatorial Topology
- Completions and Simplicial Complexes
- Introduction
- Completions
- Basic Definitions for Simplicial Complexes
- Connectedness
- Trees
- Collapse
- The Cup/Cap Completions
- Few Basic Properties
- Completions and Simple Homotopy
- Conclusion
- References
- Hierarchic Euclidean Skeletons in Cubical Complexes
- Cubical Complexes and Collapse
- The Discrete -Medial Axis and the Projection Radius Map
- Guided Collapse and Flow Graph
- Upstream of a Vertex and Its Valuation
- Topological Maps
- Topological Map Induced by an Arbitrary Map
- Computing Hierarchic Skeletons
- Conclusion
- References
- Well-Composed Cell Complexes
- Introduction
- 3D Digital Images and Cubical Complexes
- Well-Composed Cell Complexes
- Conclusion and Future Work
- References
- A Unified Topological Framework for Digital Imaging
- Introduction
- Background Notions
- Posets
- Topological Spaces
- Cubical Complexes
- Digital Topology
- Connectivity: From Zn to Fn
- One-to-One Correspondence between Images on Zn and Fn
- Duality
- Computing Values Directly from Facets
- Regular Images and Regular Open/Closed Sets
- Paths and (Digital) Fundamental Groups
- Background Notions on Paths and Arcs
- Mapping Paths in Zn onto Arcs in Fn
- Fundamental Groups
- Conclusion
- References
- Isthmus-Based 6-Directional Parallel Thinning Algorithms
- Introduction
- Basic Notions of Digital Topology
- Thinning Algorithms
- Background
- Bertrand and Couprie Isthmus Based Thinning
- Palágyi and Kuba 6-Directional Thinning
- New Method
- Design of Deletion Condition Masks
- Mask Set Reduction
- Other Kinds of Skeletons
- Comparative Results
- Conclusion
- References
- Geometric Transforms
- Quasi-Linear Transformations, Numeration Systems and Fractals
- Introduction
- Quasi-Linear Transformations
- Quasi-Linear Transformations and Numeration Systems
- Case of Gaussian Integers
- Case of Algebraic Integers of Order 2
- Quasi-Linear Transformations and Fractals
- Border of Tiles in 2-Dimension
- Fractals of Zn
- Conclusion
- References
- Path-Based Distance with Varying Weights and Neighborhood Sequences
- Introduction
- Preliminaries
- Path-Based Distance with Varying Weights
- Minimal Delay Distance Transform
- Generalized Distance Transform
- Translated NS-Distance Transform
- Symmetric DT from Asymmetric DT
- Conclusion
- References
- Sparse Object Representations by Digital Distance Functions
- Introduction
- Distance Functions
- Weighted ns-Distance and Distance Transforms
- Object Representation by Maximal Path-Points
- Local B*-Maxima
- Reducing the Cardinality of Object Representations
- Examples
- Conclusions and Future Work
- References
- Discrete Shape Representation, Recognition and Analysis
- Efficient Robust Digital Hyperplane Fitting with Bounded Error
- Introduction
- Approximate Line and Plane Fitting
- Discrete, Optimal Formulation
- The Problem of Digital Hyperplane Fitting
- Definition
- Problem Formulation
- Theoretical Observation on Exact Fitting
- Approximation with Bounded Error in Number of Inlier Points
- Approximation with Bounded Error in Digital Hyperplane Width
- Implementation
- Experimental Results
- Conclusion
- References
- Analytical Description of Digital Circles
- Introduction
- Digital Analytical Circle Description
- Recall on Digital Analytical Models
- Andres Circle
- Supercover Circles
- Standard Analytical Circles
- Closed Naïve and Naïve Analytical Circles
- Gauss Type Digitized Circles
- Discussion and Perspectives
- References
- Circular Arc Reconstruction of Digital Contours with Chosen Hausdorff Error
- Introduction
- Recent Curvature Estimators
- Contour Reconstruction with Circle Arcs
- Experiments and Comparisons
- Conclusion
- References
- Recursive Calculation of Relative Convex Hulls
- History and Outline of the Paper
- Basics
- The Relative Convex Hull
- Algorithms for Calculating Relative Convex Hulls
- Theoretical Results
- Recursive Algorithm
- Discussion
- Conclusion
- References
- An Error Bounded Tangent Estimator for Digitized Elliptic Curves
- Introduction
- Proposed Tangent Estimation Method
- The Concept
- Geometric Proof of the Proposed Concept
- Choice of R
- Maximum Error in Tangent Estimation Due to Digitization
- Numerical Results
- Practical Application: Hough Transform Based EllipseDetection Method (Yuen [7])
- Conclusion
- References
- Estimation of the Derivatives of a Digital Function with a Convergent Bounded Error
- Introduction
- Roughness of Order k
- Definition
- Taylor-Lagrange Inequality
- Roughness and Vertical Thickness
- Computation
- Digital Estimation of F(k)(0)
- Parameter
- Definition
- Error Bounding
- Bounding the Difference T(x)-P(x) on a Discrete Neighborhood
- Discrete Norms on Polynomials
- Some Values for k (m,n)
- Synthesis
- State of the Art
- Experiments
- Conclusion
- References
- Properties and Applications of the Simplified Generalized Perpendicular Bisector
- Introduction
- Definition and Properties of the SGBP RSLA20102786,ALSR
- Dual of a SGPB
- Adaptive Pixel SGPB and Noisy Circle Recognition
- Application to Noisy Circle Recognition
- Generalized Reflection Symmetry and Biased Rotation Parameter Estimation
- Bundles and Strips
- Rotation Reconstruction Using the SGPB
- Conclusion
- References
- Delaunay Properties of Digital Straight Segments
- Introduction
- Delaunay Properties of Patterns
- Triangulation of a Pattern
- Main Result
- The Facets of a Pattern Form a Triangulation
- Delaunay Condition for Each Facet
- Applications
- Continued Fraction
- Computation of the Delaunay Triangulation
- Computation of the Voronoi Diagram
- Discussion
- References
- Computing the Characteristics of a SubSegment of a Digital Straight Line in Logarithmic Time
- Introduction
- A Coarsening Algorithm for Computing the Characteristics of a Subsegment Included in a Known DSL
- Overview of the Algorithm
- S Is Included in Two Patterns of D
- S Is Included in One Pattern of D
- Correctness and Computational Complexity
- Conclusion
- References
- A Near-Linear Time Guaranteed Algorithm for Digital Curve Simplification under the Fr\'{e}chet Distance
- Introduction
- Fréchet Distance
- Curve Simplification Problem
- Guaranteed Algorithm Using an Approximated Distance
- Approximating the Fréchet Distance
- Algorithm Outline
- Updating the Approximated Distance Efficiently
- Decision on (i,j)
- Decision on b(i,j)
- Theoretical and Experimental Results
- Complexity and Guarantee Analysis
- Experimental Behaviour
- Future Works
- References
- Distance between Separating Circles and Points
- Introduction
- Elementary Circular Separations and Parameter Domains
- Path-Connected Parameter Sets
- Polyhedral and Polytopal Domains
- Polytopal Domains and Elementary Circular Separations
- Properties of Elementary Circular Separations
- Distances and Geometric Properties
- Time Complexity and Conclusion
- References
- Optimal Consensus Set for Annulus Fitting
- Introduction
- Annulus Fitting
- Annuli and Their Consensus Sets
- Annular Characterizations
- Building an Annulus of Width from Three Points
- Finding the Optimal Fitting Annulus of Width
- Algorithm
- Experiments
- Conclusion and Perspectives
- References
- Discrete Tomography
- Bounds on the Di erence between Reconstructions in Binary Tomography
- Introduction
- Notation and Model
- A Bound on the Difference between All Binary Solutions
- A Bound on the Difference with a Particular Binary Image
- Experiments and Results
- Outlook and Conclusions
- References
- Tiling the Plane with Permutations
- Introduction
- Two Classes of Polyominoes
- Polyominoes That Tile the Plane
- Polyominoes Determined by Permutations
- Convex Permutominoes Tiling the Plane
- Up-Growing Direction: Pseudo-square Parallelogram Permutominoes
- Down-Growing Direction
- Further Work
- References
- Characterization of {-1, 0, +1} Valued Functions in Discrete Tomography under Sets of Four Directions
- Introduction
- Notations and Preliminaries
- Necessary Conditions for Unique Reconstructions
- Sets of Four Directions for Unique Reconstructions
- Conclusion and Perspectives
- References
- Growth of Discrete Projection Ghosts Created by Iteration
- Introduction
- Discrete Projections and the Finite Radon Transform
- Generating Ghosts by Iteration
- Ghost Generation by Row vs. Column Oriented Iteration
- Growth of Iterated Ghosts
- Further Work and Conclusions
- References
- Properties of Minimal Ghosts
- Introduction
- Discrete Projections, Finite Radon and Affine Transforms
- Constructing Ghosts and Minimal Ghosts
- An Overview of Ghosts
- Minimal Ghost Construction
- Systematics of Minimal Ghost Construction
- Properties of Minimal Ghost Images
- Compacted Ghosts and the Construction of Image/Anti-image Data
- 2D Correlations between Minimal Ghost Images
- Conclusions
- References
- Morphological Analysis
- Mathematical Morphology on Hypergraphs: Preliminary Definitions and Results
- Introduction
- Basic Concepts on Hypergraphs Ber89
- Lattice Structures on Hypergraphs
- Mathematical Morphology on Hypergraphs
- Dualities
- Hypergraph Similarity Based on Dilations
- Conclusion
- References
- Some Morphological Operators on Simplicial Complex Spaces
- Introduction
- Lattice of Simplicial Complexes
- Morphological Operators on Simplicial Complex Spaces
- Dimensional Operators
- Conclusion and Future Work
- References
- Selection of Relevant Nodes from Component-Trees in Linear Time
- Introduction
- Component-Tree
- Purpose
- Theoretical Study
- Preliminary Properties
- Main Properties
- Algorithmics
- Application Example: Assisted Segmentation of Drop Caps
- Conclusion
- References
- Discrete and Combinatorial Tools for Image Segmentation and Analysis
- Image Denoising with a Constrained Discrete Total Variation Scale Space
- Introduction
- Some Notations and Definitions
- Differential Inclusion
- A Discrete Total Variation Scale Space Approach
- Relative Order and Bregman Distances
- A Coupled Scale-Space Approach
- Numerical Results
- Conclusion
- References
- Smale-Like Decomposition and Forman Theory for Discrete Scalar Fields
- Introduction
- Morse Theory and Morse Complexes
- Forman Theory
- Related Work
- The Smale-Like Discrete Decomposition
- Extended Discrete Gradient Field
- A Discrete Forman Function for the Extended Gradient Field
- Concluding Remarks
- References
- ACCORD: With Approximate Covering of Convex Orthogonal Decomposition
- Introduction
- Preliminaries
- Storing the Vertices
- Identifying the Sub-polygons of a Concavity
- Rules for Decomposition
- Two Simple, Orthogonal, Consecutive Concavities
- Two Simple, Parallel, Consecutive Concavities
- Compound Concavities
- Demonstration
- Time Complexity
- Results and Conclusion
- References
- Measures for Surface Comparison on Unstructured Grids with Different Density
- Introduction
- Surface Comparison Problem
- Related Work
- Mathematical Problem Statement
- Proposed Measures
- Methods
- Algorithm for Interface Triangles Extraction
- Computational Complexity of the Algorithm
- Experiments
- Conclusions
- References
- Approximate Shortest Paths in Simple Polyhedra
- Introduction and Related Work
- Basics
- ESP Computation
- Time Complexity
- Examples: Three NP-Complete or NP-Hard Problems
- Conclusions
- References
- Author Index
