Abstract: In this article, we propose new parallel algorithms for the construction and 2:1 balance refinement of large linear octrees on distributed memory machines. Such octrees are used in many problems in computational science and engineering, e.g., object representation, image analysis, unstructured meshing, finite elements, adaptive mesh refinement, and N-body simulations. Fixed-size scalability and isogranular analysis of the algorithms using an MPI-based parallel implementation was performed on a variety of input data and demonstrated good scalability for different processor counts (1 to 1024 processors) on the Pittsburgh Supercomputing Center's TCS-1 AlphaServer. The results are consistent for different data distributions. Octrees with over a billion octants were constructed and balanced in less than a minute on 1024 processors. Like other existing algorithms for constructing and balancing octrees, our algorithms have $\mathcal{O}(N\log N)$ work and $\mathcal{O}(N)$ storage complexity. Under reasonable assumptions on the distribution of octants and the work per octant, the parallel time complexity is $\mathcal{O}(\frac{N}{n_p}\log(\frac{N}{n_p})+n_p\log n_p)$, where $N$ is the size of the final linear octree and $n_p$ is the number of processors.
Abstract: We present a new method for the fast and robust computation of information theoretic similarity measures for alignment of multi-modality medical images. The proposed method defines a non-uniform, adaptive sampling scheme for estimating the entropies of the images, which is less vulnerable to local maxima as compared to uniform and random sampling. The sampling is defined using an octree partition of the template image, and is preferable over other proposed methods of non-uniform sampling since it respects the underlying data distribution. It also extends naturally to a multi-resolution registration approach, which is commonly employed in the alignment of medical images. The effectiveness of the proposed method is demonstrated using both simulated MR images obtained from the BrainWeb database and clinical CT and SPECT images.
Abstract: A 4D image registration method is proposed for consistent estimation of cardiac motion from MR image sequences. Under this 4D registration framework, all 3D cardiac images taken at different time-points are registered simultaneously, and motion estimated is enforced to be spatiotemporally smooth, thereby overcoming potential limitations of some methods that typically estimate cardiac deformation sequentially from one frame to another, instead of treating the entire set of images as a 4D volume. To facilitate our image matching process, an attribute vector is designed for each point in the image to include intensity, boundary and geometric moment invariants (GMIs). Hierarchical registration of two image sequences is achieved by using the most distinctive points for initial registration of two sequences and gradually adding less-distinctive points for refinement of registration. Experimental results on real data demonstrate good performance of the proposed method in registering cardiac images and estimating motions from cardiac image sequences.