Materials and Methods

The above unwrapping algorithm has been implemented in C++ for 3D MR images. This program, called PRELUDE (Phase Region Expanding Labeller for Unwrapping Discrete Estimates), is available as part of the FMRIB Software Library (FSL) at www.fmrib.ox.ac.uk/fsl.

In order for the implementation to be fast it is necessary to use data structures that are efficient for this algorithm. We have used the Standard Template Library data structure, map, to store the constraints between pairs of regions. This has the advantage of constant insertion and deletion complexity, plus logarithmic search complexity when using the region numbers as the key. The only step where the map is inefficient is for finding the maximum $\Delta C$ value, which is $O(N_C)$, where $N_C$ is the number of constraints. However, as this is only done at most $N$ times (once per iteration), it is a small penalty to pay for having very efficient insertion, deletion and search operations, since these are used several times (on average) per iteration. Consequently the overall complexity (worst case) is $O( N^2 \log(N_C) + N . N_C)$, since each iteration has a complexity of $O(N_C) + O(N \log(N_C))$, representing the search and updating/deletion operations respectively.