Mert Rory Sabuncu, April 2008

Minimum Spanning Tree based Efficient Image Registration

This page is dedicated to providing source code for a fast rigid-body multi-modal registration algorithm that uses a minimum spanning tree based alignment measure.

Theoretically, the alignment measure is related to an estimate of the joint entropy of the image intensity samples [1]. Notice that, as the alignment improves between two images (of potentially different modalities, i.e., acquired from different sensors), corresponding intensity samples (or, for that matter, any image feature samples) tend to cluster, in other words become statistically more dependent. See for example the figures below. This fact motivates information-theoretic registration approaches, including the famous mutual information based registration [2].

FIGURE 1: A Checkerboard visualization of PET and MR volumes acquired from Patient 17. Initially, the two volumes are not aligned. On the right you see the MST computed on the intensity samples collected from this misaligned image pair. Note how the samples are scattered in the intensity plane. As the alignment improves between the two volumes, these samples will tend to cluster (see the figure below) -- indicating higher statistical dependency, which can be captured using entropic measures. The popular mutual information based alignment algorithm is based on this idea. One other way to measure this clustering is by computing the total edge length of the MST computed on the samples.

FIGURE 2: A Checkerboard visualization of Patient 17's PET and MR volumes after rigid-body alignment based on the MST alignment measure. On the right we show the MST computed on the intensity samples after registration. Notice how clustered the samples are -- which yields a small total edge lenght of the MST.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

The paper will go here.

Here, we will include code that computes the MST of a set of two-dimensional samples.

<Code will go here>

The following is a mex file that is an implementation of a 3d rigid-body registration algorithm.

<Code will go here>

 

 

Using Spanning Graphs For Efficient Image Registration

We provide a detailed analysis of the use of minimal spanning graphs as an alignment measure for registering multi-modal images. This yields an efficient graph theoretic algorithm that, for the first time, jointly estimates both an alignment measure and a viable descent direction with respect to a parameterized class of spatial transformations. We also show how prior information about the inter-image modality relationship from pre-aligned image pairs can be incorporated into the graph-based algorithm. A comparison of the graph theoretic alignment measure is provided with more traditional measures based on plug-in entropy estimators. This highlights previously unrecognized similarities between these two registration methods. Our analysis gives additional insight into the trade-offs the graph-based algorithm is making and how these will manifest themselves in the registration algorithm's performance.

The paper can be found here.

TOOLS - CODE

This section includes code for computing a (Euclidean) Minimum Spanning Tree on 2-dimensional samples. This is mex + matlab code that can be compiled in any environment. All you need is a licensed Matlab installed on your computer (with necessary toolboxes) and mex set up. (type mex -help and mex -setup in Matlab command line)

Note: If your complier complains about C++-style comments (i.e., /* xx */ style), you can remove the -ansi (or equivalent) flag in the compiler options -- that worked for me!

Computing an EMST on two-dimensional samples:

Main Code: computeEMSTofPoints.m

Auxilary Code: computeEMST.c

Example Script: sample_emst_script.m

The following is an example of how the MST-registration algorithm can be used with 3D volumes:

Main Code: rigidRegisterEngine3D_EMST.m

Auxilary Code: volumeRigidRegisterEMSTwStochSampling.c, computeEMST.c, derivativeEMST.c, sort_out_samples.m, sort_out_samples_double.c, renorm.m, volumeRigidWarp.c, plot_mst_2d.m, mst_length.m

Data: Single precision BrainWeb [ www.bic.mni.mcgill.ca/brainweb/ ] volumes in Matlab (t1, t2 and pd-weighted simulated MRI): volumes_single.mat

Example Script: registration_example_script.m

RELATED PUBLICATIONS

[Please cite the following (preferrably all 3, but at least the first one) if you use the above code]:

[1] Using Spanning Graphs For Efficient Image Registration, Mert R. Sabuncu and Peter Ramadge, IEEE Transactions on Image Processing, IEEE Transactions on Image Processing, Vol. 17, No. 5, May 2008.

[2] Graph theoretic image registration using prior examples, Mert R. Sabuncu and Peter J. Ramadge, European Signal Processing Conference 2005, Antalya, Turkey, September 2005.

[3] Gradient based optimization of an EMST registration function, Mert R. Sabuncu and Peter J. Ramadge, IEEE Conference on Acoustics, Speech and Signal Processing, Philadelphia, March 2005.

References

[1] A. Hero, B. Ma, O. Michel, and J. Gorman, Applications of entropic spanning graphs, IEEE Signal Proc. Mag., vol. 19, no. 5, pp. 85-95, 2002.

[2] P. Viola and W. Wells, Alignment by maximization of mutual information, Int. Journal of Computer Vision, vol. 24, no. 2, pp. 137-154, 1997.