Data structure, architecture and algorithms

Abstract

A study of Linear Octree, for application to 3D biomedical image analysis, is undertaken in this thesis. It is roughly divided into 3 parts: (1) the data structure selection and analysis, (2) the study of an architectural model, based on this data structure particular features, and (3) the derivation of a set of basic algorithms for this scheme. First concentrating on space efficiency, we develop a new neighbor finding technique, which reduces the running time's memory requirement from 4$\sp{n}$ for the best algorithm known up to now, to n, for an 2$\sp{n} \times$ 2$\sp{n} \times$ 2$\sp{n}$ universe. Using this search technique, we then introduce a Connected Component Labeling algorithm. Its principle is to use a hierarchical labeling technique to reduce the label's memory requirement, from the usual $\Theta$($n \times N$) digits (where N is the number of element in the list) to O(N). In order to deliver the computational power required by a real-time manipulation and display of multidimensional biomedical images, we present in the second part a massively parallel octree architecture, based on a new Interconnection Network, the Partitionable Spanning Multibus Hypercube (PSMH). Its goal is, to use one Processing Element per obel (object element), as opposed to one Processing Element per voxel (volume element) of a brute force application. The underlying idea of the PSMH, is to take advantage of the data hierarchical ordering, to reduce the computational cost. As a basic tool, we first derive a routing algorithm, for the case of an object shift. Its running time is of order O(max($n\sp3,m$)), for an $8\sp{n}$ PSMH, where m is the message length in bits. As we deal with obels instead of voxels, we design a compaction algorithm, which meets the requirements. We get a compression ratio of O(2$\sp{n}$). This is followed by a parallel neighbor finding technique, to account for the compaction in the routing operations. The last section introduces a more general routing algorithm, aimed at complex operations, with no clear communication pattern. Its main feature is to be able to adapt efficiently to the PSMH varying structures.