Boundaries in digital spaces

Gabor T. Herman

doi:10.4995/agt.2007.1918

Authors

Gabor T. Herman City University of New York

DOI:

https://doi.org/10.4995/agt.2007.1918

Keywords:

Boundaries, Surfaces, Tracking, Algorithms, Digital topology, Geometry, Digital space

Abstract

Intuitively, a boundary in an N-dimensional digital space is a connected component of the (N âˆ’ 1)-dimensional surface of a connected object. In this paper we make these concepts precise, and show that the boundaries so specified have properties that are intuitively desirable. We provide some efficient algorithms for tracking such boundaries. We illustrate that the algorithms can be used, in particular, for computer graphic display of internal structures (such as the skull and the spine) in the human body based on the output of medical imaging devices (such as CT scanners). In the process some interesting mathematical results are proven regarding “digital Jordan boundaries,” such as a specification of a local condition that guarantees the global condition of “Jordanness.”

Downloads

Download data is not yet available.

Author Biography

Gabor T. Herman, City University of New York

PhD Program in Computer Science

References

E. A. Abbott, Flatland, A Romance of Many Dimensions, Little, Brown and Co., Boston, 1899.

E. Artzy, G. Frieder and G. T. Herman, The theory, design, implementation and evaluation of a three-dimensional surface detection algorithm, Comput. Graph. Image Proc. 15 (1981), 1–24. http://dx.doi.org/10.1016/0146-664X(81)90103-9

L.-S. Chen, G. T. Herman, R. A. Reynolds and J. K. Udupa, Surface shading in the cuberille environment, IEEE Comput. Graph. Appl. 5(12)(1985), 33–43. (Erratum appeared in 6(2) (1986), 6749).

A. V. Evako, Topological properties of closed digital spaces: One method of constructing digital models of closed continuous surfaces by using covers, Comput. Vision Image Underst. 102 (2006), 134–144. http://dx.doi.org/10.1016/j.cviu.2003.11.003

S. Fourey, T. Y. Kong and G. T. Herman, Generic axiomatized digital surface-structures, Disc. Appl. Math. 139 (2004), 65–93. http://dx.doi.org/10.1016/j.dam.2003.03.001

G. Frieder, G. T. Herman, C. Meyer and J. K. Udupa, Large software problems for small computers: An example from medical imaging, IEEE Software 2(5) (1985), 37–47. http://dx.doi.org/10.1109/MS.1985.231757

E. Gardu-o, G. T. Hermana and H. Katz, Boundary tracking in 3-D binary images to produce rhombic faces for a dodecahedral model, IEEE Trans. Med. Imag. 17 (1998), 1097–1100. http://dx.doi.org/10.1109/42.746729

D. Gordon and J. K. Udupa, Fast surface tracking in three-dimensional binary images, Comput. Vision Graph. Image Proc. 45 (1989), 196–241. http://dx.doi.org/10.1016/0734-189X(89)90132-1

G. T. Herman, A survey of 3D medical imaging technologies, IEEE Eng. Med. Biol. Mag. 9(4)(1990), 15–17. http://dx.doi.org/10.1109/51.105212

G. T. Herman, 3D display: A survey from theory to applications, Comput. Med. Imag. Graph. 17 (1993), 231–242. http://dx.doi.org/10.1016/0895-6111(93)90012-C

G. T. Herman, Oriented surfaces in digital spaces, CVGIP: Graph. Models Image Proc. 55 (1993), 381–396. http://dx.doi.org/10.1006/cgip.1993.1029

G. T. Herman, Finitary 1-simply connected digital spaces, Graph. Models Image Proc. 60 (1998), 46–56. http://dx.doi.org/10.1006/gmip.1997.0456

G. T. Herman, Geometry of Digital Spaces. Birkhäuser, Boston, MA, 1998.

G. T. Herman and D. F. Robinson, Digital boundary tracking, Pattern Anal. Appl. 1 (1998), 2–17. http://dx.doi.org/10.1007/BF01238022

G. T. Herman and D. Webster, A topological proof of a surface tracking algorithm, Comput. Vision Graph. Image Proc. 23 (1983), 162–177. http://dx.doi.org/10.1016/0734-189X(83)90110-X

T. Y. Kong, Topological adjacency relations on ZN, Theor. Comput. Sci. 283 (2002), 3–28. http://dx.doi.org/10.1016/S0304-3975(01)00050-0

T. Y. Kong, The Khalimsky topologies are precisely those simply connected topologies on ZN whose connected sets include all 2n-connected sets but no (3 (n) âˆ’ 1)-disconnected sets, Theor. Comput. Sci. 305 (2003), 221–235. http://dx.doi.org/10.1016/S0304-3975(02)00710-7

T. Y. Kong and J. K. Udupa, A justification of a fast surface tracking algorithm, CVGIP: Graph. Models Image Proc. 54 (1992), 507–515. http://dx.doi.org/10.1016/1049-9652(92)90063-4

R. Kopperman, On storage of topological information, Disc. Appl. Math. 147 (2005), 287–300. http://dx.doi.org/10.1016/j.dam.2004.09.016

R. Kopperman, P. R. Meyer and R. G. Wilson, A Jordan surface theorem for three dimensional digital spaces, Disc. Comput. Geom. 6 (1991), 155–161. http://dx.doi.org/10.1007/BF02574681

J.-O. Lachaud and A. Montevert, Continuous analogs of digital boundaries: A topological approach to iso-surfaces, Graph. Models 62 (2000), 129–164. http://dx.doi.org/10.1006/gmod.2000.0522

W. Lorensen and H. Cline, Marching cubes: A high-resolution 3D surface construction algorithm, Comput. Graph. 21(4) (1987), 163–169. http://dx.doi.org/10.1145/37402.37422

J. R. Munkres, Topology: A First Course, Prentice-Hall, Englewood Cliffs, NJ, 1975.

A. Ralston, E. D. Reilly and D. Hemmendinger, Encyclopedia of Computer Science, Nature Publishing Group, London, 4th edition, 2000. 25 J. K. Udupa and G. T. Herman, 3D Imaging in Medicine, CRC Press, Boca Raton, FL, 2nd edition, 2000.