Discrete Geometry for Computer Imagery: 14th IAPR International Conference, DGCI 2008, Lyon, France, April 16-18, 2008, Proceedings (Lecture Notes in Computer Science, 4992)

Annotation This book constitutes the refereed proceedings of the 14th IAPR TC-18 International Conference on Discrete Geometry for Computer Imagery, DGCI 2008, held in Lyon, France, in April 2008. The 23 revised full papers and 22 revised poster papers presented together with 3 invited papers were carefully reviewed and selected from 76 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, discrete modelling and visualization, as well as discrete and combinatorial tools for image segmentation and analysis Cover......Page p0001.djvu Lecture Notes in Computer Science 4992......Page p0002.djvu Discrete Geometry for Computer Imagery......Page p0003.djvu Preface......Page p0005.djvu Organization......Page p0006.djvu Table of Contents......Page p0008.djvu Introduction......Page p0013.djvu References......Page p0015.djvu Introduction......Page p0016.djvu Consequences of Shannon's Sampling Theorem......Page p0017.djvu Geometric Sampling Theorems......Page p0021.djvu Error Analysis of Segmentation Methods......Page p0025.djvu Conclusions......Page p0030.djvu Weak Rational Computing for Digital Geometry......Page p0032.djvu Introduction......Page p0033.djvu Theoretical Framework......Page p0034.djvu Origin of the Reveillès Discrete Analytical Line......Page p0035.djvu Bases of Nonstandard Analysis on N and Z......Page p0036.djvu The System A......Page p0038.djvu Constructive Mathematics, Proofs and Programs......Page p0039.djvu A Discrete Nonstandard Constructive Model of R......Page p0040.djvu Conclusion......Page p0043.djvu Generation and Recognition of Digital PlanesUsing Multi-dimensional Continued Fractions......Page p0045.djvu Stepped Planes and Dual Maps......Page p0046.djvu Brun Expansions of Real Vectors......Page p0049.djvu Generation of Stepped Planes......Page p0050.djvu Brun Expansions of Stepped Planes......Page p0051.djvu Brun Expansions of Binary Functions......Page p0053.djvu Recognition of Stepped Planes......Page p0054.djvu Introduction......Page p0057.djvu Frequencies of the (m,n)-cubes......Page p0058.djvu Application to Local Estimators......Page p0063.djvu Conclusion......Page p0067.djvu Introduction......Page p0069.djvu Preliminaries......Page p0070.djvu Combinatorics on Words......Page p0071.djvu Christoffel Words......Page p0072.djvu Digital Convexity......Page p0073.djvu Algorithm to Check Word Convexity......Page p0076.djvu The Final Algorithm......Page p0077.djvu Concluding Remarks......Page p0078.djvu Introduction......Page p0081.djvu Mathematical Preliminaries......Page p0082.djvu Matrix Ring over the Kronecker Product and Matrix Addition ......Page p0085.djvu Averages in the Neighbourhood......Page p0086.djvu Operations in Z3......Page p0087.djvu Discrete Gaussian Kernel......Page p0090.djvu Conclusions ......Page p0091.djvu Digitally Continuous Multivalued Functions......Page p0093.djvu Digital Spaces......Page p0095.djvu Continuous Multivalued Functions......Page p0096.djvu Continuous Multivalued Functions and Simple Points......Page p0098.djvu Multivalued Digital Retractions......Page p0102.djvu Digital Version of Hahn-Mazurkiewicz Theorem......Page p0103.djvu About This Paper......Page p0105.djvu Earlier Developments......Page p0106.djvu Earlier Results by Uscka-Wehlou (2007) huw......Page p0107.djvu Main Result......Page p0109.djvu Slopes with Periodic CF Expansions......Page p0113.djvu Slopes with Non-periodic CF Expansions......Page p0114.djvu Conclusion......Page p0115.djvu New Characterizations of Simple Points,Minimal Non-simple Sets and P-Simple Pointsin 2D, 3D and 4D Discrete Spaces......Page p0117.djvu Cubical Complexes......Page p0118.djvu Collapse and Simple Sets......Page p0120.djvu Confluences......Page p0122.djvu New Characterization of Simple Cells......Page p0123.djvu Critical Kernels......Page p0124.djvu Minimal Non-simple Sets......Page p0125.djvu Conclusion......Page p0127.djvu Introduction......Page p0129.djvu Background Notions......Page p0130.djvu Morse Functions......Page p0131.djvu Morse and Morse-Smale Complexes......Page p0132.djvu Cancellations in Morse-Smale and Morse Complexes......Page p0133.djvu Quasi-Morse Complexes......Page p0136.djvu Dual Representation of Morse Complexes......Page p0137.djvu Concluding Remarks......Page p0139.djvu Introduction......Page p0141.djvu Neighbourhoods in Toric Spaces......Page p0143.djvu Loops in Toric Spaces......Page p0144.djvu Fundamental Group......Page p0145.djvu Algorithm for Detecting Wrapped Subsets of Tn......Page p0146.djvu Wrapping Vector of a Loop......Page p0148.djvu Equivalence between Homotopy Classes and Wrapping Vector......Page p0149.djvu Proof of Alg. 1......Page p0150.djvu Annex......Page p0151.djvu Introduction......Page p0153.djvu Generalized Maps......Page p0154.djvu Removal and Contraction Operations......Page p0156.djvu Dimension 1: 0-insertion......Page p0157.djvu Dimension 2......Page p0158.djvu Dimension n......Page p0159.djvu Expansion......Page p0161.djvu Generalisation......Page p0162.djvu Conclusion and Perspectives......Page p0163.djvu Introduction......Page p0165.djvu Conformal Structure......Page p0166.djvu De Rham Cohomology......Page p0169.djvu Hodge Star......Page p0171.djvu The Real Case......Page p0173.djvu Non Real Conformal Structure......Page p0174.djvu Conclusions and Acknowledgments......Page p0175.djvu Introduction......Page p0177.djvu Cubical Complexes......Page p0179.djvu Topology Preserving Operations......Page p0181.djvu Minimal Simple Pairs in F3......Page p0182.djvu Some Properties of Minimal Simple Pairs......Page p0184.djvu Conclusion......Page p0186.djvu Appendix: Simple Equivalence and MSPs......Page p0188.djvu Determining Whether a Simplicial 3-ComplexCollapses to a 1-Complex Is NP-Complete......Page p0189.djvu Collapsing......Page p0190.djvu The 2D Case......Page p0194.djvu The 3D Collapsing Problem......Page p0195.djvu Conclusion......Page p0199.djvu Introduction......Page p0201.djvu Chamfer Distances......Page p0202.djvu Geometry of the Chamfer Ball......Page p0203.djvu Chamfer Medial Axis......Page p0204.djvu General H-Polytopes ziegler2001......Page p0205.djvu Chamfer H-Polytopes......Page p0206.djvu LUT Mask......Page p0209.djvu Conclusion and Future Works......Page p0211.djvu Introduction......Page p0213.djvu Basic Notions and Previous Results......Page p0214.djvu Metricity of the Distance Functions......Page p0216.djvu The fcc Grid......Page p0217.djvu The bcc Grid......Page p0218.djvu Metricity......Page p0219.djvu Algorithm to Find a Minimal Cost-Path between Two Points......Page p0220.djvu Conclusions......Page p0223.djvu Introduction......Page p0225.djvu Recall ECC......Page p0226.djvu Properties of Eccentric Points......Page p0227.djvu Recall Discrete Circles......Page p0228.djvu Shape Bounded Single Source Distance Transform......Page p0229.djvu Progressive Refinement Eccentricity Transform......Page p0230.djvu New Algorithm (ECC08)......Page p0231.djvu Experimental Results......Page p0232.djvu Conclusion......Page p0235.djvu Introduction......Page p0237.djvu Statistical Template Matching......Page p0239.djvu STM under Geometric Transformations......Page p0240.djvu Adaptive Subpixel STM......Page p0242.djvu Experiments......Page p0244.djvu References......Page p0248.djvu Introduction......Page p0250.djvu A Simple Approach Based on the Complete Voronoi Diagram Implementation......Page p0251.djvu A d-Dimensional Algorithm for I-DT......Page p0254.djvu Experiments......Page p0257.djvu Conclusion and Future Works......Page p0260.djvu Introduction......Page p0262.djvu Definition......Page p0263.djvu General Properties......Page p0264.djvu Self-similarity......Page p0265.djvu Constructive Results on Sturmian Words......Page p0266.djvu Grid Configurations from Rotation Words......Page p0268.djvu Application to C/4......Page p0269.djvu Perspectives......Page p0271.djvu Introduction......Page p0274.djvu Skeleton Definition......Page p0275.djvu Simplified Skeletons......Page p0276.djvu Computing Simplified Skeletons......Page p0277.djvu Computing the Y-network......Page p0279.djvu Y-network Decomposition......Page p0280.djvu Skeleton Segmentation......Page p0281.djvu Results and Discussion......Page p0283.djvu Conclusion......Page p0285.djvu Introduction......Page p0287.djvu Width- Discrete Patches......Page p0288.djvu Width- Normal......Page p0290.djvu Width- Patch Area......Page p0292.djvu Patch Outline......Page p0293.djvu Concave and Convex Parts......Page p0294.djvu Conclusion......Page p0297.djvu Introduction......Page p0299.djvu Adjacency Relations between Surfels an Surfels Neighborhoods......Page p0300.djvu On-Surface Convolution......Page p0301.djvu The Averaging Filter......Page p0302.djvu Surface Normal Estimation......Page p0303.djvu Comparison with Papier's Averaging Process......Page p0304.djvu Experiments......Page p0305.djvu Second Derivatives Operators......Page p0307.djvu Experiment......Page p0308.djvu Conclusion......Page p0309.djvu Introduction......Page p0311.djvu Continuous and Discrete Moments of Inertia......Page p0312.djvu Properties of Roundest Discrete Sets......Page p0313.djvu Roundest Discrete Sets Are Strongly Convex......Page p0314.djvu Roundest Discrete Sets Are Discrete Quasi-Discs......Page p0315.djvu Generation of Roundest Discrete Sets According to Size......Page p0316.djvu Concluding Remarks......Page p0318.djvu Introduction......Page p0322.djvu Digital Plane Recognition Problems......Page p0323.djvu The Preimage Polyotope......Page p0324.djvu The Vertices of preimage+(S) and preimage -(S)......Page p0325.djvu The Vertices of preimage0(S) : Chords and Visibility Cone......Page p0326.djvu The Faces of the Preimage......Page p0328.djvu From a Starting Point to a Starting Facet......Page p0329.djvu Gift-Wrapping on the Chords Set SS......Page p0330.djvu Complexity Analysis......Page p0331.djvu Conclusion......Page p0332.djvu Introduction......Page p0334.djvu Preimages of a Digital Plane Patch......Page p0335.djvu Linear LGP Generation by Arithmetic Planes......Page p0336.djvu Feasible Normal Vectors and Discrete Gaussian Spheres......Page p0338.djvu Feasible Normal Vectors of Each LGP......Page p0339.djvu Discrete Gaussian Spheres......Page p0341.djvu Unified Discrete Gaussian Images......Page p0342.djvu Algorithm......Page p0343.djvu Experimental Results......Page p0344.djvu Conclusion......Page p0345.djvu Introduction......Page p0346.djvu Tangential Cover and Tangent Space......Page p0349.djvu Curvature Computation by Optimization......Page p0350.djvu Tangential Cover of Noisy Digital Contours......Page p0352.djvu Experimental Validation......Page p0354.djvu Conclusion......Page p0356.djvu Introduction......Page p0358.djvu Definitions and Notations......Page p0359.djvu Introduction......Page p0360.djvu Subgradient Computation......Page p0361.djvu Studying the Solution Space......Page p0362.djvu Sketching the Method......Page p0363.djvu Improving Valid Cuts......Page p0366.djvu Experimental Results......Page p0367.djvu Conclusion......Page p0368.djvu Introduction......Page p0370.djvu -Thick Segments......Page p0371.djvu Tangential Cover for Closed Discrete Curves......Page p0372.djvu Isothetic Thickness Computation......Page p0374.djvu Convex Hull Maintenance......Page p0375.djvu Putting All Together......Page p0376.djvu Thick Digital Curves......Page p0378.djvu Conclusion......Page p0380.djvu Introduction......Page p0382.djvu Principle......Page p0383.djvu Convergence......Page p0385.djvu Higher Order Derivatives......Page p0386.djvu Derivatives Estimation for Parametrized Curves......Page p0387.djvu Pixel Length Parametrization......Page p0388.djvu Experimental Results......Page p0389.djvu Conclusion......Page p0391.djvu Introduction......Page p0392.djvu Method......Page p0394.djvu Results......Page p0398.djvu Conclusion......Page p0402.djvu Introduction and Notations......Page p0404.djvu Principle of the Reduction......Page p0405.djvu Going Back and Forth from Instance I to Instance I'......Page p0407.djvu From a Solution of I to a Solution of I'......Page p0408.djvu From a Solution of I Back to a Solution of I'......Page p0409.djvu Conclusion......Page p0412.djvu Introduction......Page p0413.djvu The Mojette Transform (MT)......Page p0414.djvu The Finite Radon Transform (FRT)......Page p0415.djvu Ghosts in the FRT......Page p0416.djvu The Mojette Ghost-Recovery Algorithm (MGR)......Page p0417.djvu Results......Page p0420.djvu Further Work......Page p0421.djvu Conclusion......Page p0423.djvu Introduction......Page p0425.djvu Definitions and Properties......Page p0426.djvu Reconstructing a hv-Convex Matrix Respecting One Projection hv-Convex(V)......Page p0427.djvu Reconstructing a Nearly h-Convex Matrix Respecting the Horizontal Projection h-Convex(H,w) ......Page p0428.djvu Heuristic......Page p0430.djvu hv-Convex Images......Page p0431.djvu Conclusion......Page p0433.djvu Introduction......Page p0435.djvu Constrained Connectivity Relations......Page p0436.djvu Alpha,Omega)-Connectivity......Page p0437.djvu Representative Value......Page p0438.djvu Partition Filtering......Page p0439.djvu Filtering Procedures......Page p0440.djvu Experiments......Page p0441.djvu Concluding Remarks and Perspectives......Page p0442.djvu On Watershed Cuts and Thinnings......Page p0446.djvu Basic Notions for Edge Weighted Graphs......Page p0447.djvu Extensions and Graph Cuts......Page p0448.djvu Watersheds......Page p0449.djvu Minimum Spanning Forests and Watershed Optimality......Page p0450.djvu Border Thinnings and Watersheds......Page p0451.djvu Linear-Time Algorithm for Border Cut......Page p0452.djvu Introduction......Page p0458.djvu Preliminaries......Page p0459.djvu Connectivity Measure......Page p0462.djvu Connected Components......Page p0463.djvu Tree Representation......Page p0464.djvu Connected Filters......Page p0466.djvu Illustrative Example......Page p0467.djvu Conclusion......Page p0468.djvu Introduction......Page p0470.djvu Basic Morphological Directional Transformations......Page p0471.djvu Line-Segment and Orientation Functions......Page p0472.djvu Non-parametric Algorithm to Build the Line-Segment and Orientation Functions and the Limits of the Approach......Page p0474.djvu The Limits of the Approach......Page p0476.djvu Image Segmentation Using Directional Morphology and the Watershed Transformation......Page p0477.djvu Conclusion......Page p0480.djvu Introduction......Page p0482.djvu Digitizing an Image into Pixels......Page p0483.djvu Discrete Epipolar Line......Page p0484.djvu Identifying the Boundaries Using the Fundamental Matrix......Page p0485.djvu Corresponding Pixels in Two Views and a Third View......Page p0486.djvu Identifying the Corresponding Region......Page p0487.djvu Experiments......Page p0489.djvu Concluding Remarks......Page p0492.djvu Introduction......Page p0494.djvu Related Work......Page p0495.djvu Our Model......Page p0496.djvu Runoff......Page p0497.djvu Algorithm......Page p0498.djvu Equilibrating Flow Calculation......Page p0499.djvu Transport......Page p0501.djvu Visual Result of Soil Fragments Transport......Page p0502.djvu Conclusion and Future Work......Page p0504.djvu Introduction......Page p0507.djvu Function Classes......Page p0508.djvu Shaped Operators......Page p0511.djvu The Optimal Operator......Page p0512.djvu Optimal Operator Selection......Page p0513.djvu How to Select Function Class and Window Size?......Page p0514.djvu Evaluation......Page p0515.djvu Computation of the Difference Operator......Page p0516.djvu Concluding Remarks......Page p0518.djvu Introduction......Page p0519.djvu Combinatorial Map......Page p0520.djvu 3D Images and Intervoxel Elements......Page p0521.djvu Topological Map......Page p0522.djvu Operation of Segmentation......Page p0523.djvu Criterion Used in the Segmentation Process......Page p0524.djvu Algorithm......Page p0525.djvu Results and Analysis......Page p0527.djvu Conclusion......Page p0529.djvu Introduction......Page p0531.djvu Discrete Geodesic Time......Page p0533.djvu Adaptive Neighbourhoods......Page p0534.djvu Similarity Measures and Filtering Kernels......Page p0535.djvu Application to Multispectral Image Smoothing......Page p0536.djvu Conclusion......Page p0538.djvu Introduction......Page p0541.djvu Related Work......Page p0542.djvu Weak Surface Measurements......Page p0543.djvu Improving the Crease Detection......Page p0545.djvu Weighted Linear Approximation......Page p0547.djvu Dewarping and Output......Page p0548.djvu Results......Page p0549.djvu Conclusion and Further Work......Page p0551.djvu Introduction......Page p0553.djvu Requirements for a Segmentation Environment......Page p0555.djvu The Model......Page p0556.djvu Updating and Feature Extraction Functions......Page p0559.djvu An Example of Segmentation Algorithm......Page p0561.djvu Conclusion......Page p0563.djvu Author Index......Page p0565.djvu