Discrete Geometry for Computer Imagery: 20th IAPR International Conference, DGCI 2017, Vienna, Austria, September 19 – 21, 2017, Proceedings (Lecture Notes in Computer Science, 10502)

This book constitutes the thoroughly refereed proceedings of the 20th IAPR International Conference on Discrete Geometry for Computer Imagery, DGCI 2017, held in Vienna, Austria, in September 2017. The 28 revised full papers presented together with 3 invited talks were carefully selected from 36 submissions. The papers are organized in topical sections on geometric transforms; discrete tomography; discrete modeling and visualization; morphological analysis; discrete shape representation, recognition and analysis; discrete and combinatorial topology; discrete models and tools; models for discrete geometry. Preface......Page 6 Organization......Page 7 Contents......Page 9 Invited Talks......Page 12 2 Freeform Skins from Planar Panels and Associated Support Structures......Page 13 3 Structures in Static Equilibrium......Page 16 4 On Fairness, the Importance of Regularizers and Structures Beyond Discrete Differential Geometry......Page 17 References......Page 18 1 Introduction......Page 19 2 A Brief History......Page 20 3 Connectivity Theory......Page 22 4 Algorithms......Page 23 5 Conclusions and Perspectives......Page 24 References......Page 25 1 Introduction and Context of the Artistic Work......Page 29 2.1 Digital Surface of Revolution with Hand-Drawn Generatrix and Curve of Revolution......Page 31 2.2 Swept Tubular Surfaces......Page 34 2.3 Unfolding Voxel Surfaces......Page 35 2.4 State of the Art......Page 36 2.5 Our Unfolding Problem......Page 37 2.6 Results......Page 38 References......Page 39 Geometric Transforms......Page 41 1 Introduction......Page 42 2.2 Digitized Rigid Motions......Page 43 3.1 Neighborhood Motion Maps......Page 45 3.2 Remainder Range Partitioning......Page 46 3.3 Generating Neighborhood Motion Maps for r = 1......Page 47 4 Eisenstein Rational Rotations......Page 48 5.1 Non-injective Frames of the Remainder Range......Page 50 5.2 Non-injective Digitized Rigid Motions in Square and Hexagonal Grids......Page 51 6 Conclusion......Page 52 References......Page 54 1 Introduction......Page 55 3 Using 1D FRT Projections to Build 2D Arrays......Page 57 4 Affine Transforms Preserve Correlations......Page 58 5.1 Array Construction......Page 59 5.2 Building Array Families......Page 62 6 Results......Page 63 7 Conclusions and Further Work......Page 64 References......Page 65 1 Introduction......Page 66 2.1 Metricity......Page 68 3 The Minimum Barrier Distance in Zn......Page 69 4 Convergence Properties......Page 70 5.1 Distance Transform Computation of Discretization I, "0362......Page 71 6 The Minimum Barrier Distance in Image Processing Applications......Page 72 6.1 Example Applications of Different Versions of the Minimum Barrier Distance......Page 73 References......Page 76 1 Introduction......Page 78 2.2 Digitization of Objects and Topology Preservation......Page 80 3 Digital Convexity......Page 81 3.1 Definitions......Page 82 3.3 Verification and Recognition Algorithms......Page 83 4.1 Rational Rigid Motions of a Digital Half-Plane......Page 84 4.2 Rigid Motions of H-convex Digital Objects......Page 85 5.2 Digital Object Rigid Motions Using Concavity Tree......Page 87 References......Page 89 1 Introduction......Page 91 2 Description of Trihexagonal Tiling (6, 3, 6, 3)......Page 92 3 Definition of Weighted Distances......Page 93 4.1 Case 2 and 2......Page 94 4.2 Case 2......Page 95 4.4 Case 2......Page 96 4.5 Case 2......Page 97 5 Properties of Distances......Page 101 References......Page 102 1 Introduction......Page 103 2 The Triangular Grid......Page 104 4 Integer Hull and Chvátal Cuts......Page 106 5 Linear Programming Model......Page 107 6 Construction of Chvátal Cuts......Page 109 7 Facet-Defining Inequalities......Page 112 References......Page 114 Discrete Tomography......Page 116 1 Introduction......Page 117 2 Inverse Problems and Tomography......Page 118 3 Overview of ODL and ASTRA......Page 119 4 Discrete Algebraic Reconstruction......Page 120 5 ODL Implementation of TVR-DART......Page 121 5.1 Abstract Formulation......Page 122 5.3 Defining the Objective Functional......Page 123 5.5 Implementing the Huber Norm and Soft Segmentation Operator......Page 124 5.7 Reconstructions......Page 126 References......Page 128 1 Introduction......Page 130 2 Level-Set Methods......Page 132 2.1 Approximation to Heaviside Function......Page 134 3 Joint Reconstruction Algorithm......Page 136 4 Numerical Experiments......Page 137 4.2 Full-View Test......Page 138 4.3 Limited-Angle Test......Page 139 5 Conclusions and Discussion......Page 140 References......Page 141 1 Introduction......Page 143 2.1 Ghosts and Tomography......Page 144 2.2 Constructing N-Ghosts......Page 145 2.3 Reconstruction from Projections......Page 146 2.4 Minimal Ghosts......Page 147 3 Maximal Ghosts......Page 148 3.2 Constructing Maximal N-Ghosts......Page 149 3.3 Binary Maximal Ghosts......Page 152 5 Summary......Page 153 References......Page 154 1 Introduction......Page 155 2 Definitions and Known Results......Page 157 2.1 The Notion of Switching Components......Page 158 3 A New Class of Switching Components......Page 160 3.1 Composing Hexagonal Switching Components Along a Diagonal Direction......Page 162 3.2 General Construction of the Switching Components......Page 164 References......Page 165 1 Objectives of the Study......Page 167 2.1 The Mojette Transform......Page 168 2.2 The Lattices......Page 170 2.3 Projections and Haros-Farey Sequences......Page 172 3.1 Methodology of Comparison......Page 173 3.2 Comparison Criteria......Page 174 4 Experimental Results......Page 175 References......Page 177 1 Introduction......Page 179 2 Related Work......Page 180 3 Directional Enlacement Model......Page 181 4.1 Definition......Page 182 4.2 Fuzzy Evaluation......Page 183 5 Experimental Results......Page 184 5.1 Surrounding......Page 185 5.2 Global Enlacement......Page 188 6 Conclusion......Page 189 References......Page 190 Discrete Modelling and Visualization......Page 191 1 Introduction......Page 192 2.1 Spectral Clustering......Page 193 2.2 Gamma Convergence......Page 194 3 Gamma Limit of Ratio - Cut......Page 195 4.1 How the Algorithm Works?......Page 197 4.2 Relation to MST-clustering......Page 198 4.3 Relation to Spectral Clustering......Page 200 5 Conclusion and Future Work......Page 201 References......Page 202 1 Introduction......Page 204 2 Preliminaries......Page 205 3 Variational Formulation......Page 207 3.2 Normal Vector Alignment Term......Page 208 3.3 Fairness Term......Page 209 4 Energy Minimization......Page 210 5 Experiments......Page 211 A Details on Operator R......Page 215 References......Page 216 Morphological Analysis......Page 217 1 Introduction......Page 218 2.2 Simple Points......Page 219 4 Computing Homotopic Openings......Page 220 4.1 Random Propagation......Page 221 4.2 Propagation by Layers......Page 223 4.3 More Than Simple Points......Page 225 References......Page 228 1 Introduction......Page 230 2.1 Digital Topology and DWCness......Page 231 2.2 Axiomatic Digital Topology and AWCness......Page 232 3.1 Complements About Antagonism in Z n......Page 234 3.3 Infimum of Two Faces in Hn......Page 235 3.4 Some Additional Background Concerning n-surfaces......Page 238 4 Properties Specific to the Proof......Page 239 6 Conclusion......Page 241 References......Page 242 Discrete Shape Representation, Recognition and Analysis......Page 243 1 Introduction......Page 244 2.1 Preliminaries and Classical Discretizations on Triangular Meshes......Page 246 2.2 Desired Properties of a Discrete Laplacian......Page 248 3 New Laplace-Beltrami Operator on Digital Surfaces......Page 249 4.1 Experimental Convergence......Page 251 4.2 Shape Approximation Using Eigenvectors Decomposition......Page 252 4.3 Heat Diffusion......Page 254 References......Page 255 1 Introduction......Page 257 2 Brief Review of Incremental Approach......Page 259 2.1 Representing a Feasible Region Using Its Vertices......Page 260 3 Efficient Update of Vertices of Feasible Region......Page 261 4 Algorithm......Page 263 5 Experiments......Page 265 A Appendix: Proof of Lemma1......Page 267 References......Page 268 1 Introduction......Page 270 2 New Q-convexity Measure......Page 271 2.1 Background......Page 272 2.2 The Generalized Shape Descriptor......Page 274 3 The GS Matrix......Page 275 4 Computation of......Page 277 5 Experiments......Page 278 References......Page 280 1 Introduction......Page 282 2 Decidability for Planar Sets and Pyramids......Page 284 2.1 Polytope's Expansion in Higher Dimensions......Page 285 2.2 Proof of Decidability for Planar Sets......Page 286 3 Decidability for Marquees......Page 287 3.1 Decidability for Prisms......Page 288 3.2 Strategy for General Marquees......Page 289 3.3 Perspectives......Page 292 References......Page 293 1 Introduction......Page 294 2 Multi-scale Noise Detection......Page 296 3 Irregular Isothetic Cyclic Representation......Page 297 4 Recognition of Straight Segments and Circular Arcs......Page 300 5 Experimental Results......Page 301 References......Page 304 Discrete and Combinatorial Topology......Page 307 1 Introduction......Page 308 1.2 Overview of the Paper......Page 309 2.1 Describing Local Topology with LBPs......Page 310 3 Distance Profiles......Page 311 3.1 Local Extrema Along a Distance Profile......Page 312 3.2 Persistence Defined on the Distance Profile......Page 313 4 Experiments......Page 315 References......Page 318 1 Introduction......Page 320 2 Vectorizing Images from Level Set Contours......Page 321 3 Overview of Polygonalization Methods......Page 325 3.2 DLL Based Polygonalization [18, 19]......Page 326 3.4 Visual Curvature Based Polygon Representation......Page 327 5 Conclusion and Perspectives......Page 328 References......Page 330 Discrete Models and Tools......Page 333 1 Introduction......Page 334 2 The Boolean Map Distance in Rn......Page 335 2.1 Equivalence Between BMD and......Page 337 3 The Discrete Boolean Map Distance......Page 338 3.1 Equivalence Between the Discrete and......Page 339 4 Computing Distance Transforms for the Discrete BMD......Page 340 4.3 Dijkstra's Algorithm......Page 341 4.4 Empirical Comparison of Running Time......Page 342 5 Extension to Multi-channel Images......Page 343 6 Conclusion......Page 344 References......Page 345 1 Introduction......Page 346 2 Space Filling Digital Sphere......Page 348 2.1 Properties of Naive Sphere......Page 349 2.2 Characterization of Space Filling Digital Sphere......Page 350 3 Frontier Propagation......Page 352 3.1 Spherical Propagation......Page 353 4 Test Result......Page 354 5 Concluding Note......Page 356 References......Page 357 Models for Discrete Geometry......Page 359 1 Introduction......Page 360 2 Background......Page 361 3.1 Bounding up by Counting the Crossed Tiles......Page 362 3.2 Bounding up by Counting the Intersections......Page 363 3.3 The Convex Case......Page 367 4 Conclusion......Page 368 A Convex Sets......Page 369 B.2 Building Toric Partitions in One-to-one Correspondence with the Power Set of the Toggling Boundary......Page 370 References......Page 371 1 Introduction......Page 372 2 Preliminaries......Page 373 2.1 Indexing Map......Page 375 3 Matching Algorithm......Page 376 3.1 Correctness......Page 378 3.2 Filtration Preserving Reductions......Page 379 4.1 Examples on Synthetic Data......Page 380 4.2 Examples on Real Data......Page 381 4.3 Discussion......Page 382 References......Page 383 1 Introduction......Page 385 2.1 Definition......Page 387 2.2 Properties......Page 390 3 Extensions......Page 391 3.2 Primitives with One Focal Point and a Directrix......Page 392 4 Conclusion and Perspectives......Page 393 References......Page 395 Author Index......Page 396