Digital topology

From Wikipedia, the free encyclopedia

Digital topology deals with properties and features of two-dimensional (2D) or three-dimensional (3D) digital images that correspond to topological properties (e.g., connectedness) or topological features (e.g., boundaries) of objects.

Concepts and results of digital topology are used to specify and justify important (low-level) image analysis algorithms, including algorithms for thinning, border or surface tracing, counting of components or tunnels, or region-filling.

Digital topology was first studied in the late 1960's by the computer image analysis researcher Azriel Rosenfeld (1931-2004), whose publications on the subject played a major role in establishing and developing the field. The term digital topology was itself invented by Rosenfeld, who used it in a 1973 publication for the first time.

A basic (early) result in digital topology says that 2D binary images require the alternative use of 4- or 8-adjacency (for "object" or "non-object" pixels) to ensure the basic topological duality of separation and connectedness. This alternative use corresponds to open or closed sets in the 2D grid cell topology, and the result generalizes to 3D: the alternative use of 6- or 26-adjacency corresponds to open or closed sets in the 3D grid cell topology. Grid cell topology also applies to multilevel (e.g., color) 2D or 3D images, for example based on a total order of possible image values and applying a `maximum-label rule' (see book by Klette and Rosenfeld, 2004).

See also: digital geometry, computational geometry, computational topology, topology, and discrete mathematics.

[edit] Books

• Kong, T.Y., and A. Rosenfeld (editors) (1996). Topological Algorithms for Digital Image Processing. Elsevier. ISBN 0-444-89754-2.

• Voss, K. (1993). Discrete Images, Objects, and Functions in Zn. Springer. ISBN 0-387-55943-4.

• Chen, L. (2004). Discrete Surfaces and Manifolds: A Theory of Digital-Discrete Geometry and Topology. SP Computing. ISBN 0-9755122-1-8.

• Klette, R., and A. Rosenfeld (2004). Digital Geometry. Morgan Kaufmann. ISBN 1-55860-861-3.