Share Email Print

Proceedings Paper

Grid-independent necessary criteria for shape-preserving digitization
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

The question, which shapes can be digitized without any change in the fundamental geometric and topological properties is of great importance for the reliability of image analysis algorithms, but is nevertheless unanswered for a lot of digitization schemes. While r-regularity is a sufficient criterion for shapes to be reconstructed correctly by using any regular or irregular sampling grid of certain density, necessary criteria are up to now unknown. The author proves such a necessary criterion: If you choose some sampling grid and you want a shape to be digitized correctly with any alignment of this grid, then the shape has to be a bordered 2D-manifold, i.e. its boundary has to have no junctions. This implies that any correct digitization is an extended well-composed set and thus the well known problems of defining connectivity in 2D are always due to wrong sampling or improper original shapes. This is of great importance, since extended well-composed sets have many nice topological properties, for example the Jordan curve theorem holds and the Euler characteristic is locally computable. Moreover the author proves a second necessary criterion: In case of a correct digitization with a grid of a certain density, shapes are not allowed to have corners with an angle smaller than 60 degrees. In case of common square grids the smallest possible angle is even 90 degrees. If some shape has some corner with a too small angle, the shape can not be digitized topologically correctly with every alignment of some sampling grid, if this grid exceeds a certain density. Thus the intuitive assumption that a finer grid would lead to a better digitization (in a topological sense) is simply wrong.

Paper Details

Date Published: 17 January 2005
PDF: 8 pages
Proc. SPIE 5675, Vision Geometry XIII, (17 January 2005); doi: 10.1117/12.585775
Show Author Affiliations
Peer Constantin David Stelldinger, Univ. Hamburg (Germany)

Published in SPIE Proceedings Vol. 5675:
Vision Geometry XIII
Longin Jan Latecki; David M. Mount; Angela Y. Wu, Editor(s)

© SPIE. Terms of Use
Back to Top