Discrete Geometry for Computer Imagery: 19th IAPR International Conference, DGCI 2016, Nantes, France, April 18-20, 2016. Proceedings (Lecture Notes in Computer Science Book 9647)

This book constitutes the refereed proceedings of the 19th IAPR International Conference on Discrete Geometry for Computer Imagery, DGCI 2016, held in Nantes, France, in April 2016. The 32 revised full papers presented together with 2 invited talks were carefully selected from 51 submissions. The papers are organized in topical sections on combinatorial tools; discretization; discrete tomography; discrete and combinatorial topology; shape descriptors; models for discrete geometry; circle drawing; morphological analysis; geometric transforms; and discrete shape representation, recognition and analysis. Preface......Page 6 Organization......Page 7 Contents......Page 8 Invited Talks......Page 11 1 Introduction......Page 12 2 Volume and Moments Estimators......Page 16 3 Curvatures with Digital Integral Invariants......Page 18 4 Digital Voronoi Covariance Measure......Page 20 5 Digital Surface Integration......Page 22 References......Page 25 2 Statistical Interpretation of Inverse Problems......Page 27 2.2 Maximum a Posteriori......Page 28 3 Imaging Formulations......Page 29 4.2 The Dual-Constrained Total Variation Model......Page 30 5.1 Proximity Operator......Page 32 6 Results......Page 33 8 Conclusion......Page 34 References......Page 35 Combinatorial Tools......Page 37 1 Introduction......Page 38 2 Preliminaries......Page 39 3.1 Number of Words Describing the Same Ball on the Square Grid......Page 41 4.1 The Triangular Tiling......Page 42 4.2 Generalized Traces Describing Digital Balls......Page 47 4.3 The Number of Linearizations of Generalized Traces......Page 48 References......Page 50 1 Introduction......Page 52 2 Basic Notions and Notation......Page 53 3 Construction Guided by Continued Fractions......Page 54 3.1 General Properties of the Construction......Page 56 4 The Choice of a GCF-Algorithm......Page 57 4.1 Hybrid GCF-Algorithms......Page 58 4.2 Generating a Digital Plane......Page 60 5 Conclusion and Further Work......Page 62 References......Page 63 Discretization......Page 64 1 Introduction......Page 65 2 Notations and Definitions......Page 66 3.1 0n the Cardinal of the Digitization Set Dig(fu)......Page 67 3.2 Translation Along the Y Axis......Page 68 3.3 Translations Along the X Axis......Page 69 3.4 0n the Cardinal of the Set D(f)......Page 73 4 Experiment......Page 74 References......Page 75 1 Introduction......Page 77 2.1 Almost Periodic Patterns: Definitions and First Properties......Page 81 2.2 Differences in Almost Periodic Patterns......Page 82 3.1 A Geometric Viewpoint on the Rate of Injectivity......Page 84 3.2 Diffusion Process......Page 86 3.3 Rate of Injectivity of a Generic Sequence of Isometries......Page 88 A Technical Lemmas......Page 90 B Proof of Theorem 2......Page 94 References......Page 97 Discrete Tomography......Page 99 1 Introduction......Page 100 2 Definitions and Known Results......Page 102 2.1 A Sufficient Condition for a Sequence to be h-Graphic......Page 103 2.2 Translating h-Graphicality into the Discrete Tomography Environment......Page 104 3.1 A Procedure to Reconstruct Near d-Regular, h-Uniform Hypergraphs......Page 105 3.2 Reconstructing an h-Uniform Hypergraph Whose Degree Sequence Satisfies Inequality (1)......Page 106 4 Conclusions and Open Problems......Page 108 References......Page 109 1 Introduction......Page 110 2 Definition and Known Results......Page 112 3 Theoretical Results......Page 115 4 Experimental Results......Page 117 References......Page 120 1 Introduction......Page 122 2.2 Least Squared Error Method......Page 124 2.3 Filtered Back-Projection......Page 125 2.4 Comparison of Different Reconstruction Techniques......Page 128 3.1 Replacing Holes in the Fourier Domain of the Filtered Point Spread Function......Page 129 References......Page 132 Discrete and Combinatorial Topology......Page 134 1 Cubical Complexes......Page 135 2 Collapse......Page 136 3 Critical Kernels......Page 137 4 Symmetric Thinning Scheme......Page 138 5 Asymmetric Thinning Scheme......Page 140 6 Experiments, Discussion and Conclusion......Page 144 References......Page 146 1 Introduction......Page 147 2 Basic Notions and Results......Page 149 3 From P-Simple Points to General-Simple Deletion Rules......Page 151 4 From General-Simple Deletion Rules to P-Simple Points......Page 154 References......Page 156 1 Introduction......Page 158 2.1 Cubical Complexes and Homology......Page 159 2.2 Persistent Homology......Page 161 3.1 Motivation......Page 162 3.2 Definitions......Page 164 4 Results......Page 165 5 Conclusion and Future Work......Page 167 References......Page 168 1 Introduction......Page 170 2 Introduction to LBPs......Page 171 3 Impact of the LBP Radius......Page 172 4.1 LBP Persistence Vectors......Page 174 4.3 Shape Classification......Page 175 5 Experiments......Page 176 5.1 Classification Using Single LBP Persistence......Page 177 5.3 Classification Using a Majority Vote for Combined LBP Persistence......Page 178 5.5 Discussion of the Experiments......Page 179 6 Conclusion and Outlook......Page 180 References......Page 181 Shape Descriptors......Page 182 1 Introduction......Page 183 2.1 Fuzzy Set Theory......Page 184 2.2 Shape Signature......Page 185 3 Shape Signature with Sub-pixel Precision......Page 186 3.2 Algorithm for Shape Signature Estimation......Page 187 4 Evaluation......Page 190 References......Page 194 1 Introduction......Page 196 2 Notations and Algorithm......Page 198 3 Validity and Complexity......Page 199 3.1 Algorithm Invariants......Page 200 3.2 Operation Characterization......Page 201 3.3 Termination......Page 203 4 Lattice Reduction and Delaunay Condition......Page 204 5 Applications to Digital Surfaces......Page 205 6 Conclusion and Perspectives......Page 206 References......Page 207 1 Introduction......Page 208 2 Definitions and Preliminaries......Page 210 3 Finding Shortest Path......Page 211 3.1 Finding Intersection Points......Page 212 3.2 Reduction Rules......Page 214 3.3 Algorithms......Page 216 4 Time Complexity......Page 217 5 Experimental Results and Analysis......Page 218 References......Page 219 1 Introduction......Page 221 2 Preliminaries......Page 222 3 Implementation......Page 224 4 Case Study......Page 225 5 Strongly Q-Convexity......Page 229 6 Conclusion and Discussion......Page 230 References......Page 231 Models for Discrete Geometry......Page 233 1 Introduction......Page 234 2 Construction of Symmetric Interpolation Masks......Page 236 2.1 Rules for Constructing Symmetric Masks to In-fill p:q Lattice Pixels......Page 237 3 Mask Performance for Pixel In-filling......Page 239 4.1 Discrete Rotation Angles......Page 240 4.3 Rotation Algorithms......Page 241 6 Conclusions and Future Work......Page 243 References......Page 244 1 Introduction......Page 245 2 Basic Notions and Notations......Page 246 2.1 Implicit Surface Digitization......Page 247 3.1 Implicit Surface of Revolution Definition......Page 248 3.2 Digital Generatrix......Page 249 3.3 Algorithm......Page 250 3.4 Results......Page 251 3.5 Extensions......Page 252 3.6 Limitations......Page 253 4 Conclusion......Page 254 References......Page 255 1 Introduction......Page 257 1.2 Main Results......Page 258 2.1 Basic Notions and Notations......Page 259 3 Functional Gradation of Coordinate Planes......Page 261 4 Grouping of Quadraginta Octants......Page 264 5 Circle Drawing---An Application......Page 266 6 Concluding Note......Page 267 References......Page 268 1 Introduction......Page 269 2 ECM Representations......Page 270 3 3D Cubical Complexes......Page 271 4 Encoding Specific Polyhedral Complexes Using Binary Images......Page 272 References......Page 281 1 Introduction......Page 283 2 Curvature Tensor Estimation......Page 285 3.1 Linear Octree Representation......Page 286 3.3 Level of Details Criteria and Temporal Updates......Page 287 4.1 Per Vertex Real-Time Computation on GPU......Page 289 5.1 Full Resolution Experiment......Page 291 5.2 Fully Adaptive Evaluation......Page 292 6 Conclusion and Discussion......Page 294 References......Page 295 1 Introduction......Page 296 2 Preliminaries......Page 297 2.1 Elliptic Octants......Page 298 3 Properties of Digital Ellipse......Page 300 4.1 Algorithm Draw-Ellipse-Float......Page 302 4.2 Algorithm Draw-Ellipse-Int......Page 305 5 Concluding Notes......Page 307 References......Page 308 Morphological Analysis......Page 310 1 Introduction......Page 311 2 Background Notions for Morphology on Graphs......Page 313 3 Vertex-Edge and Edge-Vertex Distance Maps......Page 316 4 Parallel Algorithm for Distance Maps on Graphs......Page 317 5 Parallel Partition and Disjoint Union Algorithms......Page 320 References......Page 322 1 Introduction......Page 323 2 Lattice of the Regular Open Sets (Reminder)......Page 324 3.1 Tessellations and R open sets......Page 325 3.2 Structure of the Tessellations......Page 326 3.3 Hierarchies of Tessellations......Page 327 4 Connected Classes and Saliency Function......Page 328 5.2 Khalimsky digital tessellations......Page 329 6.1 Hexagonal Tessellation of Z2......Page 331 References......Page 333 Geometric Transforms......Page 335 1 Introduction......Page 336 2 Periodicity of the Tiles......Page 338 3 Behavior Under Iteration of a Quasi-Linear Transformation......Page 342 4 Conclusion......Page 346 References......Page 347 2 Notation......Page 348 3 Minimal Paths as Minima in the Sum of Distance Transforms......Page 349 4.1 Minimal Paths by Prefiltering the Input Image......Page 351 4.2 Minimal Paths by Prior Knowledge on Prefered Directions......Page 352 4.3 General Metric Tensor Minimal Path-Cost......Page 354 References......Page 355 1 Introduction......Page 358 2.1 Digitized Rigid Motions......Page 359 2.3 Remainder Range Partitioning......Page 360 2.4 Non-surjective and Non-injective Frames......Page 361 3 Globally Bijective Digitized Rigid Motions......Page 363 4 Locally Bijective Digitized Rigid Motions......Page 364 4.1 Forward Algorithm......Page 365 4.2 Backward Algorithm......Page 366 5 Conclusion......Page 369 References......Page 370 1 Introduction......Page 371 2 Description of T(8,8,4)......Page 372 3 Definition of Weighted Distances......Page 373 4.1 Case α ≤ β......Page 374 4.3 Case 2β ≤ α......Page 375 5.1 Case α ≤ β......Page 376 5.2 Case β ≤ α ≤ 2β......Page 378 5.3 Case 2β ≤ α......Page 380 6 Summary and Further Thoughts......Page 381 References......Page 382 1 Introduction......Page 384 2 Preliminaries......Page 385 3 Digital Disks......Page 388 3.1 Case 2α ≤ β and 3α ≤ γ......Page 389 3.2 Case 2α > β and α + β ≤ γ......Page 391 3.3 Case 2α > β and α +γ > 2β but α +β > γ......Page 392 4 Approximation of Euclidean Circles......Page 393 References......Page 395 Discrete Shape Representation, Recognition and Analysis......Page 397 1 Introduction......Page 398 2.1 Imprecise Digital Contour......Page 399 2.2 Family of Tours......Page 400 2.3 Definition of an Imprecise Object: Pixel Labeling......Page 401 3.1 Preliminary Definitions......Page 403 3.2 Toleranced Balls of an Imprecise Digital Object......Page 404 3.3 Distances......Page 405 3.4 Toleranced Balls Growing Process......Page 407 3.5 Compact Representation of the Filtration......Page 408 4 Discussion......Page 409 References......Page 410 1 Introduction......Page 412 2 Problem Statement......Page 413 3 The Shadows and the Jewels......Page 415 3.1 A Partial Order......Page 416 3.2 About the Number of Lattice Jewels......Page 418 4 Algorithm......Page 421 4.1 Conclusion......Page 422 References......Page 423 1 Introduction......Page 424 2 Related Works......Page 425 3 Orthogonal Plane Estimation......Page 427 4 Proposed Method......Page 428 5.1 Synthetic Data......Page 431 5.2 Real Data......Page 433 6 Conclusion and Prospects......Page 434 References......Page 435 1 Introduction......Page 436 2.1 Maximal Blurred Segments......Page 437 2.2 Meaningful Thickness......Page 438 3 Adaptive Tangential Cover......Page 442 4 Application to Dominant Point Detection......Page 444 4.1 Dominant Point Detection Algorithm......Page 445 5 Conclusion and Perspectives......Page 447 References......Page 448 Author Index......Page 449