Digital Topology, by Yung Kong

Topology Atlas Document # zaaa-58.htm | Production Editor: R. Flagg

Topology Atlas Invited Contributions, vol. 1, issue 3 (1996), 37-38.

Digital Topology
by

Yung Kong

(City University of New York, Queens College, Flushing, NY 11367, U.S.A.)

In image processing and computer graphics, an object in the plane or 3-space is often approximated digitally by a set of pixels ("picture elements'') or voxels ("volume elements''). Digital topology studies properties of the set of pixels or voxels that correspond to topological properties of the original object. The subject was first studied by Azriel Rosenfeld in the late 1960's and early 70's [Ros70, Ros73]. Its concepts and results are important in specifying and justifying some image processing algorithms (including algorithms for object counting, thinning, shrinking, and boundary extraction). Sets of pixels or voxels have usually been represented by graph-based structures or cubical complexes, but an interesting alternative approach uses locally finite topological spaces instead [KKM, Kov]. Ref. [surv] is an introduction to digital topology (written mainly for non-mathematicians) that surveys the subject through the mid-1980's and includes a bibliography of almost 140 references. The special issues [TA,JMIV] contain papers on more recent developments.

References

[KKM] E. Khalimsky, R. D. Kopperman and P. R. Meyer, Computer graphics and connected topologies on finite ordered sets, Topology and its Applications, Vol. 36, 1990, pp.1--17.

[TA] T. Y. Kong, R. D. Kopperman and P. R. Meyer, guest editors, Topology and its Applications, Vol. 46, No. 3, 1992: Special Issue on Digital Topology.

[surv] T. Y. Kong and A. Rosenfeld, Digital topology: introduction and survey, Computer Vision, Graphics and Image Processing, Vol. 48, 1989, pp. 357--393.

[JMIV] T. Y. Kong and A. Rosenfeld, guest editors, Journal of Mathematical Imaging and Vision, Vol. 6, Nos. 2--3: Special Issue on Topology and Geometry in Computer Vision. In press, to be published in 1996.

[Kov] V. A. Kovalevsky, Finite topology as applied to image analysis, Computer Vision, Graphics and Image Processing, Vol. 46, 1989, pp. 141--161.

[Ros70] A. Rosenfeld, Connectivity in digital pictures, Journal of the ACM, Vol. 17, 1970, pp. 146--160.

[Ros73] A. Rosenfeld, Arcs and curves in digital pictures, Journal of the ACM, Vol. 20, 1973, pp. 81--87.

Received by the editors: December 27, 1995.