“The theory, design, implementation and evaluation of a three-dimensional surface detection algorithm” by Artzy, Frieder and Herman

In many three-dimensional imaging applications the three-dimensional scene is represented by a three-dimensional array of volume elements, or voxels for short. A subset Q of the voxels is specified by some property. The objects in the scene are then defined as subsets of Q formed by voxels which are “connected” in some appropriate sense. It is often of interest to detect and display the surface of an object in the scene, specified say by one of the voxels in it. In this paper, the problem of surface detection is translated into a problem of traversal of a directed graph, G. The nodes of G correspond to faces separating voxels in Q from voxels not in Q. It has been proven that connected subgraphs of G correspond to surfaces of connected components of Q (i.e., of objects in the scene). Further properties of the directed graph have been proven, which allow us to keep the number of marked nodes (needed to avoid loops in the graph traversal) to a small fraction of the total number of visited nodes. This boundary detection algorithm has been implemented. We discuss the interaction between the underlying mathematical theory and the design of the working software. We illustrate the software on some clinical studies in which the input is computed tomographic (CT) data and the output is dynamically rotating three-dimensional displays of isolated organs. Even though the medical application leads to very large scale problems, our theory and design allows us to use our method routinely on the minicomputer of a CT scanner.

1. Artzy, E. Display of three-dimensional information in computed tomography. Comm. Grph. and Image Proc. 9, (Feb. 1979), 196-198.
2. Artzy, E. and Herman, G.T., Boundary detection in 3-dimensions with a medical application. Comp. Graph., to appear.
3. Coin, CG., Herman, G.T., Huck-Folliss, A., Jacobson, S., Pernink, M., and Reranen, V. Computed tomography of disc disease. Scientific exhibit at the Radiological Soc. of North Amer., Atlanta, Ga., Nov. 1979.
4. Fuchs, H., Kedem, Z.M., and Uselton, S.P. Optimal surface reconstruction from planar contours. Comm. ACM 20, 10 (Oct. 1977), 693-702. (Also presented at SIGGRAPH’77.)
5. Gordon, R., Herman, G.T. and Johnson, S.A. Image reconstruction from projections. Sci. Amer. 233 (Oct. 1975), 56-68.
6. Greenleaf, J.F., Tu, J.S., and Wood, E. H. Computer generated three-dimensional oscilloscopic images and associated techniques for display and study of the spatial distribution of pulmonary blood flow. IEEE Tran. Nucl. Sci. NS-17, (June 1970), 353-359.
7. Harary, F. Graph Theory. Addison-Wesley Publishing Company, (1972).
8. Herman, G.T. and Liu, H.K. Three-dimensional display of human organs from computed tomograms. Comp. Graph. and Image Processing 9, (Jan. 1979), 1-21.
9. Knuth, D.E. The Art of Computer Programming Volume 1 Fundamental Algorithms. Addison-Wesley Company, Reading, Mass., (1968).
10. Liu, H.K. Two and three dimensional boundary detection. Comp. Graph. and Image Processing 6 (Apr. 1977), 123-134.
11. Rhodes, M.L. An algorithmic approach to controlling search in three-dimensional image data. SIGGRAPH’79 Proceedings, Chicago, Ill. (Aug. 1979), 134-142.
12. Robb, R.A., Ritman, E.L., Greenleaf, J.F., Sturm, R.E., Herman, G.T., Chevalier, P.A., Liu, H.K., and Wood, E.H., Quantitative imaging of dynamic structure and functions of the heart, lungs and circulation by computerized reconstruction and subtraction techniques. Proceedings of the 3rd Annual Conf. on Comp. Grph., Interactive Techniques and Image Processing (SIGGRAPH’76), Philadelphia, Pa. (July 1976), 246-256.
13. Rosenfeld, A. connectivity in digital pictures. J. Assoc, Computing Mach. 17 (Jan. 1970), 146-160.
14. Rosenfeld, A., and Kak, A.C. Digital Picture Processing. Academic Press, New York, N.Y., (1976).
15. Sunguroff, A., and Greenberg, D. Computer generated images for medical application, SIGGRAPH’78 Proceedings, Atlanta, GA. (Aug. 1978), 196-202.