Abstracts of Publications

The discrete space representation of most scientific datasets (pixels, voxels, etc), generated through instruments or by sampling continuously defined fields, while being simple, is also verbose and structureless. We propose the use of a particular spatial structure, the binary space partitioning tree, or, simply, partitioning tree, as a new representation to perform efficient geometric computation in discretely defined domains. The ease of performing affine transformations, set operations between objects and correct implementation of transparency (exploiting the visibility ordering inherent to the representation) makes the partitioning tree a good candidate for probing and analyzing medical reconstructions, in such applications as surgery planning and prostheses design. The multi-resolution characteristics of the representation can be exploited to perform such operations at interactive rates by smooth variation of the amount of geometry. Application to ultrasound data segmentation and visualization is proposed.

The paper describes methods for constructing partitioning trees from a discrete image/volume data set. Discrete space operators developed for edge detection are used to locate discontinuities in the image, from which lines/planes containing the discontinuites are fitted by using either the Hough transform or a hyperplane sort. A multi-resolution representation can be generated by ordering the choice of hyperplanes by the magnitude of the discontinuities. Various approximations can be obtained by pruning the tree according to an error metric. The segmentation of the image into edgeless regions can yield significant data compression. A hierarchical encoding schema for both lossless and lossy encodings is described.

Tools for the system-level investigation of nervous system function are few: electroencephalography (EEG), functional brain imaging techniques, and large scale simulation. Of these, simulation has had the least impact on our understanding. This is unfortunate, as simulation has much to offer: (1) simulation can be a powerful tool for synthesizing experimental data into a coherent system whose dynamic behavior can be examined, (2) the creation of a simulation is the setting out of a theory, and more theories of the brain function are needed, (3) simulation can show us how system level behavior emerges from lower level (cellular, synaptic and anatomical) properties which are incorporated therein, (4) it can combine the temporal resolution of EEG techniques with the spatial resolution of functional brain imaging, and (5) computing power and software tools are readily available. In this article, we describe the construction and application of a simulation environment that uses visualization as the interface to control and analyze the behavior of spinal reflex circuits. This use of visualization as a primary output for simulation is somewhat unusual, and we find it very powerful. The environment facilitates rapid experimentation (simulation with immediate visual feedback on the impact of a change in input, followed by statistical analysis). Because the visualization provides rapid feedback on the impact of an experimental change, sometimes further experimentation can begin without a complete statistical analysis. The tool thus considerably speeds the development cycle of new experiments, as well as providing the usual benefits of data visualization.

The ability of ultrasound scanners to image anatomical structures in real time have led to their use in two important applications of medicine, (1) for monitoring the unborn baby (fetal ultrasound), and, (2) coronary treatment of blockages in blood vessels (intravascular ultrasound). The generated images (in the form of a continuous video) are typically noisy, containing numerous artifacts, making it difficult to isolate and measure features of interest. We explore the use of two algorithms, region growing and a variant of split/merge algorithm for segmenting sequences of fetal ultrasound images. We describe an interactive system that can rapidly process and segment an arbitrary number of features. The system exploits frame to frame coherence for accelerating the segmentation process, while at the same time combining the strengths of these algorithms for accurate and robust detection of features.

Ray tracing is an important and popular rendering technique in computer graphics for synthesizing photorealistic images. However, ray tracing, if not carefully done, can be a computationally expensive technique. A great deal of research has focused on discovering efficient ways to perform ray tracing. An important approach to controlling the computational expense has been the use of geometric search structures to prevent needless ray-object intersection calculations.

Search structures in current use take advantage of scene characteristics in a variety of ways to enhance ray tracing performance. Constraints in their construction can cause inefficiencies and consequent degradation in performance. Performance comparisons between search structures using timing benchmarks have shown that no single existing search structure performs best on all scene models. A knowledge of search structure performance prior to rendering is therefore important to selecting a search structure for a given scene. A thorough understanding of the ways in which search structures succeed in enhancing performance on various types of scenes can also be expected to lead to improvements in existing techniques.

We present new results in adapting search structures to scene characteristics for improving the performance of ray tracing. A cost model is developed for evaluating search structures currently being used in ray tracing. The model has been successfully used to terminate search structure construction, thus making it unnecessary to set termination parameters in advance. The model has also been used with limited success to compare the performance of different search structures for a given scene.

A detailed experimental study of some of the important properties of search structures has been performed. This has resulted in a new adaptive search structure that is based on {\em k-d} trees, a multi-dimensional binary search structure which outperforms existing methods. Its high performance is primarily due to the fact that it combines the advantages of such structures based on space partitioning and those based on bounding volumes. The greater flexibility of this search structure allows it to terminate automatically at a point where further subdivision would result in no additional benefits.