Digital topology

Last updated

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.

Contents

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.

History

Digital topology was first studied in the late 1960s by the computer image analysis researcher Azriel Rosenfeld (19312004), 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, appeared in the book of Pavel Alexandrov 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 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. 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 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. The main differences between them are: (1) digital topology mainly studies digital objects that are formed by grid cells,[ clarification needed ] 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 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 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.)

See also

Related Research Articles

<span class="mw-page-title-main">Surface (topology)</span> Two-dimensional manifold

In the part of mathematics referred to as topology, a surface is a two-dimensional manifold. Some surfaces arise as the boundaries of three-dimensional solid figures; for example, the sphere is the boundary of the solid ball. Other surfaces arise as graphs of functions of two variables; see the figure at right. However, surfaces can also be defined abstractly, without reference to any ambient space. For example, the Klein bottle is a surface that cannot be embedded in three-dimensional Euclidean space.

In mathematics, combinatorial topology was an older name for algebraic topology, dating from the time when topological invariants of spaces were regarded as derived from combinatorial decompositions of spaces, such as decomposition into simplicial complexes. After the proof of the simplicial approximation theorem this approach provided rigour.

<span class="mw-page-title-main">Digital geometry</span> Deals with digitized models or images of objects of the 2D or 3D Euclidean space

Digital geometry deals with discrete 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 images we see on the TV screen, the raster display of a computer, or in newspapers are in fact digital images.

<span class="mw-page-title-main">Discrete geometry</span> Branch of geometry that studies combinatorial properties and constructive methods

Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.

<span class="mw-page-title-main">Solid modeling</span> Set of principles for modeling solid geometry

Solid modeling is a consistent set of principles for mathematical and computer modeling of three-dimensional shapes (solids). Solid modeling is distinguished within the broader related areas of geometric modeling and computer graphics, such as 3D modeling, by its emphasis on physical fidelity. Together, the principles of geometric and solid modeling form the foundation of 3D-computer-aided design and in general support the creation, exchange, visualization, animation, interrogation, and annotation of digital models of physical objects.

<span class="mw-page-title-main">Manifold</span> Topological space that locally resembles Euclidean space

In mathematics, a manifold is a topological space that locally resembles Euclidean space near each point. More precisely, an -dimensional manifold, or -manifold for short, is a topological space with the property that each point has a neighborhood that is homeomorphic to an open subset of -dimensional Euclidean space.

In topology, a branch of mathematics, a topological manifold is a topological space that locally resembles real n-dimensional Euclidean space. Topological manifolds are an important class of topological spaces, with applications throughout mathematics. All manifolds are topological manifolds by definition. Other types of manifolds are formed by adding structure to a topological manifold. Every manifold has an "underlying" topological manifold, obtained by simply "forgetting" the added structure. However, not every topological manifold can be endowed with a particular additional structure. For example, the E8 manifold is a topological manifold which cannot be endowed with a differentiable structure.

<span class="mw-page-title-main">Mesh generation</span> Subdivision of space into cells

Mesh generation is the practice of creating a mesh, a subdivision of a continuous geometric space into discrete geometric and topological cells. Often these cells form a simplicial complex. Usually the cells partition the geometric input domain. Mesh cells are used as discrete local approximations of the larger domain. Meshes are created by computer algorithms, often with human guidance through a GUI, depending on the complexity of the domain and the type of mesh desired. A typical goal is to create a mesh that accurately captures the input domain geometry, with high-quality (well-shaped) cells, and without so many cells as to make subsequent calculations intractable. The mesh should also be fine in areas that are important for the subsequent calculations.

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.

<span class="mw-page-title-main">Discrete tomography</span> Reconstruction of binary images from a small number of their projections

Discrete tomography focuses on the problem of reconstruction of binary images from a small number of their projections.

In mathematics, specifically geometry and topology, the classification of manifolds is a basic question, about which much is known, and many open questions remain.

James W. Cannon is an American mathematician working in the areas of low-dimensional topology and geometric group theory. He was an Orson Pratt Professor of Mathematics at Brigham Young University.

A combinatorial map is a combinatorial representation of a graph on an orientable surface. A combinatorial map may also be called a combinatorial embedding, a rotation system, an orientable ribbon graph, a fat graph, or a cyclic graph. More generally, an -dimensional combinatorial map is a combinatorial representation of a graph on an -dimensional orientable manifold.

<span class="mw-page-title-main">Geometric design</span>

Geometrical design (GD) is a branch of computational geometry. It deals with the construction and representation of free-form curves, surfaces, or volumes and is closely related to geometric modeling. Core problems are curve and surface modelling and representation. GD studies especially the construction and manipulation of curves and surfaces given by a set of points using polynomial, rational, piecewise polynomial, or piecewise rational methods. The most important instruments here are parametric curves and parametric surfaces, such as Bézier curves, spline curves and surfaces. An important non-parametric approach is the level-set method.

<span class="mw-page-title-main">Reeb graph</span>

A Reeb graph is a mathematical object reflecting the evolution of the level sets of a real-valued function on a manifold. According to a similar concept was introduced by G.M. Adelson-Velskii and A.S. Kronrod and applied to analysis of Hilbert's thirteenth problem. Proposed by G. Reeb as a tool in Morse theory, Reeb graphs are the natural tool to study multivalued functional relationships between 2D scalar fields , , and arising from the conditions and , because these relationships are single-valued when restricted to a region associated with an individual edge of the Reeb graph. This general principle was first used to study neutral surfaces in oceanography.

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 piecewise linear manifold made by simplicial complexes.

The Alexandrov uniqueness theorem is a rigidity theorem in mathematics, describing three-dimensional convex polyhedra in terms of the distances between points on their surfaces. It implies that convex polyhedra with distinct shapes from each other also have distinct metric spaces of surface distances, and it characterizes the metric spaces that come from the surface distances on polyhedra. It is named after Soviet mathematician Aleksandr Danilovich Aleksandrov, who published it in the 1940s.

Mathematics is a broad subject that is commonly divided in many areas that may be defined by their objects of study, by the used methods, or by both. For example, analytic number theory is a subarea of number theory devoted to the use of methods of analysis for the study of natural numbers.

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 “cells”, are not subsets of a Hausdorff space as is the case in Euclidean and CW complexes. Abstract cell complexes play an important role in image analysis and computer graphics.

<span class="mw-page-title-main">Ideal polyhedron</span> Shape in hyperbolic geometry

In three-dimensional hyperbolic geometry, an ideal polyhedron is a convex polyhedron all of whose vertices are ideal points, points "at infinity" rather than interior to three-dimensional hyperbolic space. It can be defined as the convex hull of a finite set of ideal points. An ideal polyhedron has ideal polygons as its faces, meeting along lines of the hyperbolic space.

References