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 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:
 Constructing digitized representations of objects, with the emphasis on precision and efficiency (either by means of synthesis, see, for example, Bresenham's line algorithm 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, 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 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.
 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 manifolds.
 Designing tracking algorithms for digital objects.
 Functions on digital space.
Digital geometry heavily overlaps with discrete geometry and may be considered as a part thereof.
Contents
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).
In RosenfeldKak's book, digital connectivity are defined as the relationship among elements in digital space. For example, 4connectivity and 8connectivity 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 A_{i} are real numbers. This function possesses the following property: If x and y are two adjacent points in Σ, assume f(x) = A_{i}, then f(y) = A_{i}, f(x) = A_{i + 1}, or A_{i − 1}. 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 F of f is : for each pair of points x and y in D, assume f(x) = A_{i} and f(y) = A_{j}, we have , where d(x,y) is the (digital) distance between x and y.
See also
 Computational geometry
 Digital topology
 Discrete geometry
 Combinatorial geometry
 Tomography
References
 A Rosenfeld, `Continuous' functions on digital pictures, Pattern Recognition Letters, v.4 n.3, p. 177184, 1986.
 L. Chen, The necessary and sufficient condition and the efficient algorithms for gradually varied fill, Chinese Sci. Bull. 35 (10), pp 870–873, 1990.
Further reading
 Rosenfeld, Azriel (1969). Picture Processing by Computer. Academic Press. ISBN ???.
 Rosenfeld, Azriel (1976). Digital picture analysis. Berlin: SpringerVerlag. ISBN 0387075798.
 Rosenfeld, Azriel; Kak, Avinash C. (1982). Digital picture processing. Boston: Academic Press. ISBN 0125973012.
 Rosenfeld, Azriel (1979). Picture Languages. Academic Press. ISBN 0125973403.
 Chassery, J., and A. Montanvert. (1991). Geometrie discrete en analyze d’images. Hermes. ISBN 2866012712.
 Kong, T.Y., and A. Rosenfeld (editors) (1996). Topological Algorithms for Digital Image Processing. Elsevier. ISBN 0444897542.
 Voss, K. (1993). Discrete Images, Objects, and Functions in Zn. Springer. ISBN 0387559434.
 Herman, G.T. (1998). Geometry of Digital Spaces. Birkhauser. ISBN 0817638970.
 MarchandMaillet, S., and Y. M. Sharaiha (2000). Binary Digital Image Processing. Academic Press. ISBN 0124705057.
 Soille, P. (2003). Morphological Image Analysis: Principles and Applications. Springer. ISBN 3540429883.
 Chen, L. (2004). Discrete Surfaces and Manifolds: A Theory of DigitalDiscrete Geometry and Topology. SP Computing. ISBN 0975512218.
 Rosenfeld, Azriel; Klette, Reinhard (2004). Digital Geometry: Geometric Methods for Digital Image Analysis (The Morgan Kaufmann Series in Computer Graphics). San Diego: Morgan Kaufmann. ISBN 1558608613. http://www.mi.auckland.ac.nz/index.php?option=com_content&view=article&id=49&Itemid=49.
External links
Categories:
Wikimedia Foundation. 2010.
Look at other dictionaries:
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. Concepts and results of… … Wikipedia
Geometry processing — Geometry processing, or mesh processing, is a fast growing area of research that uses concepts from applied mathematics, computer science and engineering to design efficient algorithms for the acquisition, reconstruction, analysis, manipulation,… … Wikipedia
Digital image — A digital image is a numeric representation (normally binary) of a two dimensional image. Depending on whether or not the image resolution is fixed, it may be of vector or raster type. Without qualifications, the term digital image usually refers … Wikipedia
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… … Wikipedia
Digital Morse theory — In mathematics, digital Morse theory [1] is a digital adaptation of continuum Morse theory for scalar volume data. The main utility of a digital Morse theory is that it serves to provide a theoretical basis for isosurfaces, and perpendicular… … Wikipedia
Digital differential analyzer (graphics algorithm) — This article is about a graphics algorithm. For the digital implementation of a Differential Analyzer, see Digital Differential Analyzer. In computer graphics, a hardware or software implementation of a digital differential analyzer (DDA) is used … Wikipedia
Digital versus film photography — has been a topic of debate since the invention of digital cameras towards the end of the 20th Century. Both digital and film photography have advantages and drawbacks.[1][2] 21st century photography is dominated by digital operation, but the… … Wikipedia
Digital prototyping — gives conceptual design, engineering, manufacturing, and sales and marketing departments the ability to virtually explore a complete product before it’s built. Industrial designers, manufacturers, and engineers use Digital Prototyping to design,… … Wikipedia
Digital holography — is the technology of acquiring and processing holographic measurement data, typically via a CCD camera or a similar device. In particular, this includes the numerical reconstruction of object data from the recorded measurement data, in… … Wikipedia
Digital waveguide synthesis — is the synthesis of audio using a digital waveguide. Digital waveguides are efficient computational models for physical media through which acoustic waves propagate. For this reason, digital waveguides constitute a major part of most modern… … Wikipedia