Digital geometry
Encyclopedia
Digital geometry deals with discrete
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 algorithm
    Bresenham's line algorithm
    The 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 theorem
    Pick's theorem
    Given 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 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....

     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 morphology
    Mathematical morphology
    Mathematical 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 manifold
    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 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 processing
Image 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 geometry
    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 are also considered to be part of computational...

  • 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....

  • 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,...

  • Combinatorial geometry
  • Tomography
    Tomography
    Tomography 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,...


External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK