Digital geometry
Encyclopedia
Digital geometry deals with discrete
sets (usually discrete point
sets) considered to be digitized
models
or image
s 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.
Its main application areas are computer graphics
and image analysis
.
Main aspects of study are:
Digital geometry heavily overlaps with discrete geometry
and may be considered as a part thereof.
).
In Rosenfeld-Kak's book, digital connectivity are defined as the relationship among elements in digital space. For example, 4-connectivity and 8-connectivity in 2D. Also see pixel connectivity
. A digital space and its (digital-)connectivity determine a digital topology
.
In digital space, the digitally continuous function (A. Rosenfeld, 1986) and the gradually varied function
(L. Chen, 1989) were proposed, independently.
A digitally continuous function means a function in which the value (an integer) at a digital point is the same or off by at most 1 from its neighbors. In other words, if x and y are two adjacent points in a digital space, |f(x) − f(y)| ≤ 1.
A gradually varied function is a function from a digital space
to 
where 
and 
are real numbers. This function possesses the following property: If x and y are two adjacent points in 
, assume 
, then 
, 
, or 
. So we can see that the gradually varied function is defined to be more general than the digitally continuous function.
An extension theorem related to above functions was mentioned by A. Rosenfeld (1986) and completed by L. Chen (1989). This theorem states: Let
and 
. The necessary and sufficient condition for the existence of the gradually varied extension 
of 
is : for each pair of points 
and 
in 
, assume 
and 
, we have 
, where 
is the (digital) distance between 
and 
.
Discrete space
In topology, a discrete space is a particularly simple example of a topological space or similar structure, one in which the points are "isolated" from each other in a certain sense.- Definitions :Given a set X:...
sets (usually discrete point
Point (geometry)
In geometry, topology and related branches of mathematics a spatial point is a primitive notion upon which other concepts may be defined. In geometry, points are zero-dimensional; i.e., they do not have volume, area, length, or any other higher-dimensional analogue. In branches of mathematics...
sets) considered to be digitized
Digitizing
Digitizing or digitization is the representation of an object, image, sound, document or a signal by a discrete set of its points or samples. The result is called digital representation or, more specifically, a digital image, for the object, and digital form, for the signal...
models
Scale model
A scale model is a physical model, a representation or copy of an object that is larger or smaller than the actual size of the object, which seeks to maintain the relative proportions of the physical size of the original object. Very often the scale model is used as a guide to making the object in...
or image
Image
An image is an artifact, for example a two-dimensional picture, that has a similar appearance to some subject—usually a physical object or a person.-Characteristics:...
s of objects of the 2D or 3D Euclidean space
Euclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
.
Simply put, digitizing is replacing an object by a discrete set of its points. The images we see on the TV screen, the raster
Raster graphics
In computer graphics, a raster graphics image, or bitmap, is a data structure representing a generally rectangular grid of pixels, or points of color, viewable via a monitor, paper, or other display medium...
display of a computer, or in newspapers are in fact digital
Digital
A digital system is a data technology that uses discrete values. By contrast, non-digital systems use a continuous range of values to represent information...
images.
Its main application areas are computer graphics
Computer graphics
Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....
and image analysis
Image analysis
Image analysis is the extraction of meaningful information from images; mainly from digital images by means of digital image processing techniques...
.
Main aspects of study are:
- Constructing digitized representations of objects, with the emphasis on precision and efficiency (either by means of synthesis, see, for example, Bresenham's line algorithmBresenham's line algorithmThe Bresenham line algorithm is an algorithm which determines which points in an n-dimensional raster should be plotted in order to form a close approximation to a straight line between two given points...
or digital disks, or by means of digitization and subsequent processing of digital images). - Study of properties of digital sets; see, for example, Pick's theoremPick's theoremGiven a simple polygon constructed on a grid of equal-distanced points such that all the polygon's vertices are grid points, Pick's theorem provides a simple formula for calculating the area A of this polygon in terms of the number i of lattice points in the interior located in the polygon and the...
, digital convexity, digital straightness, or digital planarity. - Transforming digitized representations of objects, for example (A) into simplified shapes such as (i) skeletons, by repeated removal of simple points such that the digital topologyDigital topologyDigital topology deals with properties and features of two-dimensional or three-dimensional digital imagesthat correspond to topological properties or topological features of objects....
of an image does not change, or (ii) medial axis, by calculating local maxima in a distance transform of the given digitized object representation, or (B) into modified shapes using mathematical morphologyMathematical morphologyMathematical morphology is a theory and technique for the analysis and processing of geometrical structures, based on set theory, lattice theory, topology, and random functions...
. - Reconstructing "real" objects or their properties (area, length, curvature, volume, surface area, and so forth) from digital images.
- Study of digital curves, digital surfaces, and digital manifoldDigital manifoldIn 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.-...
s. - Designing tracking algorithms for digital objects.
- Functions on digital space.
Digital geometry heavily overlaps with discrete geometry
Discrete geometry
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,...
and may be considered as a part thereof.
Digital space
A 2D digital space usually means a 2D grid space that only contains integer points in 2D Euclidean space. A 2D image is a function on a 2D digital space (See image processingImage processing
In electrical engineering and computer science, image processing is any form of signal processing for which the input is an image, such as a photograph or video frame; the output of image processing may be either an image or, a set of characteristics or parameters related to the image...
).
In Rosenfeld-Kak's book, digital connectivity are defined as the relationship among elements in digital space. For example, 4-connectivity and 8-connectivity in 2D. Also see pixel connectivity
Pixel connectivity
In image processing and image recognition, pixel connectivity is the way in which pixels in 2- or 3-dimensional images relate to their neighbors.-4-connected:...
. A digital space and its (digital-)connectivity determine a digital topology
Digital topology
Digital topology deals with properties and features of two-dimensional or three-dimensional digital imagesthat correspond to topological properties or topological features of objects....
.
In digital space, the digitally continuous function (A. Rosenfeld, 1986) and the gradually varied function
Gradually varied surface
In mathematics, a gradually varied surface is a special type of digital surfaces. It is a function from a 2D digital space to an ordered set or a chain....
(L. Chen, 1989) were proposed, independently.
A digitally continuous function means a function in which the value (an integer) at a digital point is the same or off by at most 1 from its neighbors. In other words, if x and y are two adjacent points in a digital space, |f(x) − f(y)| ≤ 1.
A gradually varied function is a function from a digital space
to where and are real numbers. This function possesses the following property: If x and y are two adjacent points in , assume , then , , or . So we can see that the gradually varied function is defined to be more general than the digitally continuous function.An extension theorem related to above functions was mentioned by A. Rosenfeld (1986) and completed by L. Chen (1989). This theorem states: Let
and . The necessary and sufficient condition for the existence of the gradually varied extension of is : for each pair of points and in , assume and , we have , where is the (digital) distance between and .See also
- Computational geometryComputational geometryComputational 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 are also considered to be part of computational...
- Digital topologyDigital topologyDigital topology deals with properties and features of two-dimensional or three-dimensional digital imagesthat correspond to topological properties or topological features of objects....
- Discrete geometryDiscrete geometryDiscrete 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,...
- Combinatorial geometry
- TomographyTomographyTomography refers to imaging by sections or sectioning, through the use of any kind of penetrating wave. A device used in tomography is called a tomograph, while the image produced is a tomogram. The method is used in radiology, archaeology, biology, geophysics, oceanography, materials science,...