“An algorithmic approach to controlling search in three-dimensional image data” by Rhodes

  • ©Mìchael L. Rhodes




    An algorithmic approach to controlling search in three-dimensional image data



    In many three-dimensional imaging applications random shaped objects, reconstructed from serial sections, are isolated to display their overall structure in a single view. This paper presents an algorithm to control an ordered search strategy for locating all contours of random shaped objects intersected by a series of cross-section image planes. Classic search techniques in AI problem solving and software for image processing and computer graphics are combined here to aid program initialization and automate the search process thereafter. Using three-dimensional region growing, this method isolates all spatially connected pixels forming a structure’s volume and enters image planes the least number of times to do so. An algorithmic description is given to generalize the process for controlling search in 3-D image data where little core memory is available. Phantom and medical computer tomographic data are used to illustrate the algorithm’s performance.


    1. Chow, C. K., and Kaneka, T., “Boundary Detection of Radiographic Images by a Thresh. Method,” IBM Report RG3203, December 1970.
    2. Ausherman, D. A., Dwyer, S. J., and Lodwick, G. S., “Extraction of Connected Edges from Radiographs,” IEEE Trans. Computers, C-21, 1972, pp. 753-758.
    3. Ballard, D., and Sklansky, J., “Tumor Detection in Radiographs,” Comput. Biomed. Res. 6, 1973, pp. 299-321.
    4. Carton, E., Weszka, J., Mohr, J., Rosenfeld, A., “Some Basic Edge Detection Techniques,” Univ. Maryland Tech. Rep. TR-277, Dec. 1973.
    5. Bullock, B., “The Performance of Edge Operators in Images with Texture,” Hughes Air. Co. Tech. Rep., Malibu, CA., Oct. 1974.
    6. Frei, W., Chen, C. C., “Fast Boundary Detection: A Generalization and a New Algorithm,” IEEE Trans. Comp., Vol. C-26, No. 10 pp. 988-998.
    7. Chien, Y. P., and Fu, K. S., “A Decision Function Method for Boundary Detection,” Comp. Graphics and Image Proc., 3, 1974, pp. 125-140.
    8. Mazziotta, J. C., Huang, H. K., “THREAD (Three dimensional Reconstruction and Display) with Biomed. Applic. in Neuron Ultrastructure and Comp. Tomography,” Proc. Nat’l Comp. Conf. AFIPS 1976, Vol. 45, AFIPS Press, Montvale, N.J., pp. 241-250.
    9. Liu, H. K., “Two-and-Three-Dimensional Boundary Detection,” Comp. Graph. and Image Proc., 6, 1977, pp. 123-134.
    10. Cohen, P., Livingston, R., Sumners, R., Application Programs for Computer Graphics, “Dynamic Viewing of CT Image Data,” 16-mm film, Roch Laboratories Inc., and the Neuroscience Department, Univ. Cal. San Diego, La Jolla, CA., 1978.
    11. Shantz, M. J., McCann, G. D., “Computational Morphology: Three-D Comp. Graph. for Elec. Microscopy,” IEEE Trans. Biom. Eng., Vol. BME-25, No. 1, Jan. 1978, pp. 99-102.
    12. Yakimovsky, Y., Cunningham, R., “On the Problem of Embedding Picture Elements in Regions,” Jet Prop. Lab. Tech. Report No. 33-774, Pasadena, CA., June 1976.
    13. Rhodes, M. L., Glenn, W. V., Klinger, A., “Interactive Volume and Surface Iso. Using Tomogr. Data,” Proc. San Diego Biom. Symp., Feb. 1-3, 1978, pp. 403-411.
    14. Rosenfeld, A., “Connectivity in Digital Pictures,” J. ACM, Vol. 17, No. 1, 1970, pp. 146-160.
    15. Jackson, P. C., Intro. to Artificial Intel., Mason/Charter Pub. Inc., New York, 1974.
    16. Nilsson, N. J., Prob. Solv. Methods in Art. Intel., McGraw-Hill, New York, 1971.
    17. Winston, P. H., Artificial Intelligence, Addison-Wesley, Menlo Park, CA., 1977.
    18. Fuchs, H., Kedem, Z. M., Uselton, S. P., “Optimal Surface Reconstruction from Planar Contours,” Comm. ACM, Vol. 20, No. 10, Oct., 1977, pp. 693-702.
    19. Denning, P. J., “Virtual Memory,” Computing Surveys, Vol. 2, No. 3, Sept. 1970, pp. 153-189.

ACM Digital Library Publication: