Algorithms and parallel architecture for multi-dimensional image representation
Djaffer Ibaroudene · 1991
Techniques for non-invasive visualization of the internal structures of the human organs have undergone a revolution in the last decade. New data acquisition systems based on computed tomography (CT), positron emission tomography (PET), magnetic resonance imaging (MRI), and ultrasound, have allowed physicians to display and analyze 3-D images of human internal organs without resorting to exploratory surgery. The complex data sets, generated by these scanning devices, consist of multivariate quantities, defined by a large number of points over a two or three dimensional grid. The choice of a data structure to represent this vast amount of patient information is very critical to the performance of the medical imaging system. Careful consideration must be given to the trade-offs involving the computation time required by the object display operations and the storage efficiency of the representation format. In this study, we propose an efficient multi-dimensional data structure called a hypertree, which exploits the object's spatial coherence in all dimensions. It is based on the principle of recursive decomposition of the object space into quadrant, octants, or hyperants, depending on the dimensionality of the data set. In fact, the quadtree and the octree are the 2-D and 3-D instances of the hypertree data structure. Procedures for encoding, decoding, and condensing linear octrees are discussed. Algorithms for determining the locational code of a face, edge, and corner adjacent block of a given node are proposed. These algorithms are later generalized to the multi-dimensional spaces of a linear hypertree. The computational complexities of all the neighbor identification procedures, described in this study, are of the order of the number of digits in the locational code of the node for which the neighbor is sought. A new coordinate transformation technique is described in the context of a display algorithm for linear octree encoded objects. All translation and rotation matrix operations involved in the projection of a 3-D object onto a 2-D screen, represented by a linear octree, are performed only on the vertices of the universe cube. The coordinates of individual linear octree nodes are determined by using a formula which computes the coordinates of any vertex of a given linear octree node from the transformed coordinates of the corners of the universe. This formula requires only addition and multiplications by powers of 2. Finally, an object space partitioning technique, that maps a linear octree onto a massively parallel hardware architecture, is proposed. This computer architecture is intended to exploit all the possible parallelism in the display algorithms which are based on the back to front traversal of the linear octree nodes.