Digital topology deals with properties and features of
two-dimensional
A two-dimensional space is a mathematical space with two dimensions, meaning points have two degrees of freedom: their locations can be locally described with two coordinates or they can move in two independent directions. Common two-dimension ...
(2D) or
three-dimensional
In geometry, a three-dimensional space (3D space, 3-space or, rarely, tri-dimensional space) is a mathematical space in which three values (''coordinates'') are required to determine the position (geometry), position of a point (geometry), poi ...
(3D)
digital images
A digital image is an image composed of picture elements, also known as pixels, each with '' finite'', '' discrete quantities'' of numeric representation for its intensity or gray level that is an output from its two-dimensional functions f ...
that correspond to
topological
Topology (from the Greek words , and ) is the branch of mathematics concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, wit ...
properties (e.g.,
connectedness
In mathematics, connectedness is used to refer to various properties meaning, in some sense, "all one piece". When a mathematical object has such a property, we say it is connected; otherwise it is disconnected. When a disconnected object can be ...
) 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
Image analysis or imagery analysis is the extraction of meaningful information from images; mainly from digital images by means of digital image processing techniques. Image analysis tasks can be as simple as reading barcode, bar coded tags or a ...
algorithms,
including algorithms for
thinning, border or surface tracing, counting of components or tunnels, or region-filling.
History
Digital topology was first studied in the late 1960s 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 related work called the
grid cell topology, which could be considered as a link to classic
combinatorial topology In mathematics, combinatorial topology was an older name for algebraic topology, dating from the time when topological invariants of spaces (for example the Betti numbers) were regarded as derived from combinatorial decompositions of spaces, such a ...
, appeared in the book of
Pavel Alexandrov
Pavel Sergeyevich Alexandrov (), sometimes romanized ''Paul Alexandroff'' (7 May 1896 – 16 November 1982), was a Soviet mathematician. He wrote roughly three hundred papers, making important contributions to set theory and topology. In topol ...
and
Heinz Hopf, Topologie I (1935). Rosenfeld ''et al.'' proposed digital connectivity such as 4-connectivity and 8-connectivity in two dimensions as well as 6-connectivity and 26-connectivity in three dimensions. The labeling method for inferring a connected component was studied in the 1970s. Theodosios Pavlidis (1982) suggested the use of graph-theoretic algorithms such as the
depth-first search
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible al ...
method for finding connected components.
Vladimir A. Kovalevsky (1989) extended the Alexandrov–Hopf 2D grid cell topology to three and higher dimensions. He also proposed (2008) a more general axiomatic theory of
locally finite topological spaces and
abstract cell complexes formerly suggested by
Ernst Steinitz (1908). It is the
Alexandrov topology
In general topology, an Alexandrov topology is a topology in which the intersection of an ''arbitrary'' family of open sets is open (while the definition of a topology only requires this for a ''finite'' family). Equivalently, an Alexandrov top ...
. The book from 2008 contains new definitions of topological balls and spheres independent of a metric and numerous applications to digital image analysis.
In the early 1980s,
digital surfaces were studied. David Morgenthaler and Rosenfeld (1981) gave a mathematical definition of surfaces in three-dimensional digital space. This definition contains a total of nine types of digital surfaces. The
digital manifold
In mathematics, a digital manifold is a special kind of combinatorial manifold which is defined in digital space i.e. grid cell space. A combinatorial manifold is a kind of manifold which is a discretization of a manifold. It usually means a pie ...
was studied in the 1990s. A recursive definition of the digital k-manifold was proposed intuitively by Chen and Zhang in 1993.
Many applications were found in image processing and computer vision.
Basic results
A basic (early) result in digital topology says that 2D binary images require the alternative use of 4- or 8-adjacency or "
pixel connectivity" (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 the book by Klette and Rosenfeld, 2004).
Digital topology is highly related to
combinatorial topology In mathematics, combinatorial topology was an older name for algebraic topology, dating from the time when topological invariants of spaces (for example the Betti numbers) were regarded as derived from combinatorial decompositions of spaces, such a ...
. The main differences between them are: (1) digital topology mainly studies digital objects that are formed by grid cells (the cells of integer lattices), rather than more general
cell complexes, and (2) digital topology also deals with non-Jordan manifolds.
A combinatorial manifold is a kind of manifold which is a discretization of a manifold. It usually means a
piecewise linear manifold made by
simplicial complexes. A
digital manifold
In mathematics, a digital manifold is a special kind of combinatorial manifold which is defined in digital space i.e. grid cell space. A combinatorial manifold is a kind of manifold which is a discretization of a manifold. It usually means a pie ...
is a special kind of combinatorial manifold which is defined in digital space i.e. grid cell space.
A digital form of the
Gauss–Bonnet theorem is: Let ''M'' be a closed digital 2D
manifold
In mathematics, a manifold is a topological space that locally resembles Euclidean space near each point. More precisely, an n-dimensional manifold, or ''n-manifold'' for short, is a topological space with the property that each point has a N ...
in direct adjacency (i.e., a (6,26)-surface in 3D).
The formula for genus is
:
,
where
indicates the set of surface-points each of which has ''i'' adjacent points on the surface (Chen and Rong, ICPR 2008).
If ''M'' is simply connected, i.e.,
, then
. (See also
Euler characteristic
In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic (or Euler number, or Euler–Poincaré characteristic) is a topological invariant, a number that describes a topological space's ...
.)
See also
*
Digital geometry
Digital geometry deals with discrete sets (usually discrete point sets) considered to be digitized models or images of objects of the 2D or 3D Euclidean space.
Simply put, ''digitizing'' is replacing an object by a discrete set of its points. ...
*
Combinatorial topology In mathematics, combinatorial topology was an older name for algebraic topology, dating from the time when topological invariants of spaces (for example the Betti numbers) were regarded as derived from combinatorial decompositions of spaces, such a ...
*
Computational geometry
*
Computational topology
*
Topological data analysis
*
Topology
Topology (from the Greek language, Greek words , and ) is the branch of mathematics concerned with the properties of a Mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformat ...
*
Discrete mathematics
Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...
*
Geospatial topology
References
*
*
*
*
*
*
*
*
Vladimir A. Kovalevsky. (2008).
{{Authority control