Digital topology deals with properties and features of
two-dimensional
In mathematics, a plane is a Euclidean (flat), two-dimensional surface that extends indefinitely. A plane is the two-dimensional analogue of a point (zero dimensions), a line (one dimension) and three-dimensional space. Planes can arise as s ...
(2D) or
three-dimensional
Three-dimensional space (also: 3D space, 3-space or, rarely, tri-dimensional space) is a geometric setting in which three values (called ''parameters'') are required to determine the position of an element (i.e., point). This is the informal ...
(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
In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing h ...
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 s ...
) 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 bar coded tags or as sophi ...
algorithms,
including algorithms for
thinning
Thinning is a term used in agricultural sciences to mean the removal of some plants, or parts of plants, to make room for the growth of others. Selective removal of parts of a plant such as branches, buds, or roots is typically known as pruning.
...
, 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
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 bar coded tags or as sophist ...
researcher
Azriel Rosenfeld
Azriel Rosenfeld (February 19, 1931 – February 22, 2004) was an American Research Professor, a Distinguished University Professor, and Director of the Center for Automation Research at the University of Maryland, College Park, Maryland, where he ...
(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 The grid cell topology is studied in digital topology as part of the theoretical basis for (low-level) algorithms in computer image analysis or computer graphics.
The elements of the ''n''-dimensional grid cell topology (''n'' ≥ 1) are all ''n'' ...
, 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 (russian: Па́вел Серге́евич Алекса́ндров), sometimes romanized ''Paul Alexandroff'' (7 May 1896 – 16 November 1982), was a Soviet mathematician. He wrote about three hundred papers, ma ...
and
Heinz Hopf
Heinz Hopf (19 November 1894 – 3 June 1971) was a German mathematician who worked on the fields of topology and geometry.
Early life and education
Hopf was born in Gräbschen, Germany (now , part of Wrocław, Poland), the son of Elizabeth ( ...
, 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 alon ...
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
In mathematics, an abstract cell complex is an abstract set with Alexandrov topology in which a non-negative integer number called dimension is assigned to each point. The complex is called “abstract” since its points, which are called “cell ...
formerly suggested by
Ernst Steinitz
Ernst Steinitz (13 June 1871 – 29 September 1928) was a German mathematician.
Biography
Steinitz was born in Laurahütte (Siemianowice Śląskie), Silesia, Germany (now in Poland), the son of Sigismund Steinitz, a Jewish coal merchant, and ...
(1908). It is the
Alexandrov topology In topology, an Alexandrov topology is a topology in which the intersection of any family of open sets is open. It is an axiom of topology that the intersection of any ''finite'' family of open sets is open; in Alexandrov topologies the finite rest ...
. 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 piec ...
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
In image processing, pixel connectivity is the way in which pixels in 2-dimensional (or hypervoxels in n-dimensional) images relate to their neighbors.
Formulation
In order to specify a set of connectivities, the dimension N
and the width ...
" (for "object" or "non-object"
pixels
In digital imaging, a pixel (abbreviated px), pel, or picture element is the smallest addressable element in a raster image, or the smallest point in an all points addressable display device.
In most digital display devices, pixels are the sm ...
) 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 The grid cell topology is studied in digital topology as part of the theoretical basis for (low-level) algorithms in computer image analysis or computer graphics.
The elements of the ''n''-dimensional grid cell topology (''n'' ≥ 1) are all ''n'' ...
, 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 The grid cell topology is studied in digital topology as part of the theoretical basis for (low-level) algorithms in computer image analysis or computer graphics.
The elements of the ''n''-dimensional grid cell topology (''n'' ≥ 1) are all ''n'' ...
. 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, 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
In mathematics, a piecewise linear (PL) manifold is a topological manifold together with a piecewise linear structure on it. Such a structure can be defined by means of an atlas, such that one can pass from chart to chart in it by piecewise linear ...
made by
simplicial complexes
In mathematics, a simplicial complex is a set composed of points, line segments, triangles, and their ''n''-dimensional counterparts (see illustration). Simplicial complexes should not be confused with the more abstract notion of a simplicial set ...
. 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 piec ...
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
In the mathematical field of differential geometry, the Gauss–Bonnet theorem (or Gauss–Bonnet formula) is a fundamental formula which links the curvature of a surface to its underlying topology.
In the simplest application, the case of a ...
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 ...
.)
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. The i ...
*
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 geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...
*
Computational topology Algorithmic topology, or computational topology, is a subfield of topology with an overlap with areas of computer science, in particular, computational geometry and computational complexity theory.
A primary concern of algorithmic topology, as its ...
*
Topological data analysis
In applied mathematics, topological based data analysis (TDA) is an approach to the analysis of datasets using techniques from topology. Extraction of information from datasets that are high-dimensional, incomplete and noisy is generally challengin ...
*
Topology
In mathematics, topology (from the Greek language, Greek words , and ) is concerned with the properties of a mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformations, such ...
*
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 ...
References
*
*
*
*
*
*
*
*
Vladimir A. Kovalevsky. (2008).
{{Topology