A hierarchical data structure for multidimensional digital images

ABSTRACT

A tree data structure for representing multidimensional digital binary images is described. The method is based on recursive subdivision of the d-dimensional space into 2d hyperoctants. An algorithm for constructing the tree of a d-dimensional binary image from the trees of its (d - 1 )-dimensional cross sections is given. The computational advantages of the data structure and the algorithm are demonstrated both theoretically and in application to a three-dimensional reconstruction of a human brain.

REFERENCES

• 1: Altschuler, M.D., Censor, Y., Herman, G.T., Lent, A., Lewitt, R.M., Srihari, S.N., Tuy, H., and Udupa, J.K. Mathematical aspects of image reconstruction from projections. In L.N. Kanal and A. Rosenfeld, (Eds.), Progress in Pattern Recognition, vol. 1, North-Holland, New York, 1981, 323-375.
• 2: Charles M. Eastman, Representations for space planning, Communications of the ACM, v.13 n.4, p.242-250, April 1970 [doi>10.1145/362258.362281]
• 3: Gillespie, R., and Davis, W.A. Tree data structures for graphics and image processing. Prec. Canadian Man-Computer Comm. Soc. Conf., Waterloo, Ont., Canada, 1981, pp. 155-162.
• 4: Gregory Michael Hunter, Efficient computation and data structures for graphics., 1978
• 5: Jackins, C.L., and Tanimoto, S.L. Oct-trees and their use in representing 3D objects. Comput. Graph. Image Prac. 14, (1980), 249-270.
• 6: Kelly, M.D. Edge detection in pictures using planning. In B. Meltzer and D. Michie (Eds.), Machine Intelligence 6 Halsted Press, New York, 1971. 397-409.
• 7: Klinger, A., and Dyer, C.R. Experiments on picture representation using regular decomposition. Comput. Graph. Image Proc. 5 (1976), 68-105.
• 8: Lozano-Perez, T. Automatic planning of manipulator transfer movements. IEEE Trans. Syst., Man, Cybern. SMC-I 1 (1981), 681-698.
• 9: Meagher, D.J.R. Octree encoding. Tech. Rept. TR-IPL-80-111, Dept. Electrical Systems, Rensselaer Polytechnic Inst., Trey, N.Y., 1980.
• 10: William M. Newman , Robert F. Sproull, Principles of interactive computer graphics (2nd ed.), McGraw-Hill, Inc., New York, NY, 1979
• 11: Reddy, D.R., and Rubin, S. Representation of 3D objects. Tech. Rept. TR- CMU-CS-78-113, Dept. Computer Science, Carnegie Mellon Univ., Pittsburgh, Pa., 1978.
• 12: Samet, H. Region representation: Quad trees from binary arrays. Comput. Graph. Image Prec. 13 (1980), 88-93.
• 13: Samet, H. An algorithm for converting rasters to quadtrees. IEEE Trans. Pattern Anal. Mach. Intell. PAMI-3 (1981), 93-95.
• 14: Srihari, S.N. Hierarchical representations for serial section images. Prec. Int. Conf. Pattern Recognition, Miami Beach, Fla., Dec. 1-4, 1980, pp. 1075-1980.
• 15: Sargur N. Srihari, Representation of Three-Dimensional Digital Images, ACM Computing Surveys (CSUR), v.13 n.4, p.399-424, Dec. 1981 [doi>10.1145/356859.356862]
• 16: Tanimoto, S., and Pavlidis, T. A hierarchical data structure for picture processing. Comput. Graph. Image Prec. 4 (1975), 104-119.
• 17: Udupa, J.K., Srihari, S.N., and Herman, G.T. Boundary detection in multidimensions. IEEE Trans. Pattern Anal. Mach. Intell. PAMI-4 (1982) 41-50.
• 18: Yan, M., Hierarchical Respmsantation of Three-dimensional Digital Objects. Ph.D. Diss., Comptr. Sci. Dept., SUNY at Buffalo, Jan. 1983.
• 19: Yau, M., and Srihari, S.N. Recursive generation of hierarchical data structures for multidimensional digital images. Proc. IEEE Comput. Sac. Conf. Pattern Recog. Image Processing, Dallas, Tex., 1981, pp. 44-46.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Representations, data structures, and transforms
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.2 Compression (Coding)
          Subjects: Exact coding**

General Terms:
Algorithms

Keywords:
computed tomography, hyperoctree, multidimensional arrays, octree, quadtree, serial section image processing