Converting discrete images to partitioning trees

摘要

The discrete space representation of most scientific datasets,ngenerated through instruments or by sampling continuously definednfields, while being simple, is also verbose and structureless. Wenpropose the use of a particular spatial structure, the binary spacenpartitioning tree as a new representation to perform efficient geometricncomputation in discretely defined domains. The ease of performing affinentransformations, set operations between objects, and correctnimplementation of transparency makes the partitioning tree a goodncandidate for probing and analyzing medical reconstructions, in suchnapplications as surgery planning and prostheses design. Thenmultiresolution characteristics of the representation can be exploitednto perform such operations at interactive rates by smooth variation ofnthe amount of geometry. Application to ultrasound data segmentation andnvisualization is proposed. The paper describes methods for constructingnpartitioning trees from a discrete image/volume data set. Discrete spacenoperators developed for edge detection are used to locatendiscontinuities in the image from which lines/planes containing thendiscontinuities are fitted by using either the Hough transform or anhyperplane sort. A multiresolution representation can be generated bynordering the choice of hyperplanes by the magnitude of thendiscontinuities. Various approximations can be obtained by pruning thentree according to an error metric. The segmentation of the image intonedgeless regions can yield significant data compression. A hierarchicalnencoding schema for both lossless and lossy encodings is described