MRI scan

Algorithm's Holy Grail

A number of internationally excellent research centres and industrial companies have used our phase unwrappers. Our clients have included The Christie Hospital, Manchester, UK, EADS Astrium, Germany, a multinational aerospace manufacturer of satellite systems, The European Southern Observatory, Australia, The Helen Wills Neuroscience Institute at the University of California, Berkeley.

Our phase unwrappers have been integrated in the SciPy free open-source mathematical library and The Clinical Research Imaging Centre, The University of Edinburgh, where Eric Barnhill has implemented two algorithms as Java ImageJ Plugins.

There are many medical, military and industrial digital image processing applications which as part of their fundamental operation depend upon the extraction of a phase signal from their input image. Examples of such applications are magnetic resonance imaging (MRI), synthetic aperture radar (SAR), fringe pattern analysis, tomography and spectroscopy. These systems use modern and mature algorithms to extract the phase signal. However the phase is returned in a form that suffers from 2-pi phase jumps due to the use of the mathematical arctangent function, which produces an inherently wrapped output. This wrapped phase is unusable until the phase discontinuities are removed and this is achieved practically by employing a phase unwrapping algorithm.

Phase unwrapping is one of the most active areas of research in digital image processing and has been extensively researched in the last twenty years with more than 500 journal papers having been published, all of which suggest various solutions to this problem. The proposed algorithms produce a variety of differing results and no perfect "correct" solution is guaranteed, even if such a solution exists. Instead, all modern phase unwrapping techniques produce estimations of the "correct" solution. On many occasions, these complex algorithms cannot resolve all the phase wraps in the image and many 2-pi phase jumps still exist in the unwrapped phase map. Problems with 2D unwrapping are not limited to a small subset of challenging images; we are talking here about the majority of real images encountered in many practical applications.

Generally speaking, when these algorithms are executed using digital computers, the more robust unwrappers usually require long processing times. Also, the required processing power increases as the noise corrupting the wrapped phase map increases. On the other hand, the faster phase unwrappers are usually not robust and cannot be used for real applications.

In the General Engineering Research Institute (GERI), a significant amount of research has been carried out in order to develop robust and fast two and three-dimensional phase unwrappers. These algorithms have been published in international journals and conferences. An introduction to the specific algorithms that have been developed by the Institute is included below and the code is made freely available for download for non-commercial applications, subject to certain terms and conditions. If you have a commercial application and are interested in including GERI unwrapping algorithms within your product, then this may be accommodated under license. Phase unwrapping algorithms may also be customised in order to meet your application requirements. Please contact Dr. Francis Lilley if you have a commercial enquiry regarding use of our phase unwrapping algorithms.

The phase unwrapping problem

Why is solving the phase unwrapping problem important and difficult?

Phase unwrapping is the final and most challenging step in the phase extraction process, an image-processing stage that is common to many different systems. The failure or success of this procedure can have a massive effect upon the overall performance of such systems. A typical image may contain thousands of individual phase wraps. Some of these wraps are genuine, whilst others are false and are caused by the presence of noise and sometimes by the phase extraction algorithm itself. The process of differentiating between genuine and false phase wraps is extremely difficult and this adds complexity to the phase unwrapping problem.

A second reason that complicates the phase unwrapping problem is that it is a process that is accumulative in nature. The image is processed sequentially on a pixel-by-pixel basis. If a single genuine phase wrap between two neighbouring pixels is missed due to noise, or a false wrap appears in the phase map, an error occurs in unwrapping both pixels. This kind of error then propagates throughout the rest of the image. In some cases, even though all but one of the wraps in an image may have been unwrapped successfully, it is possible that the resultant image could be completely unusable and hence the operation of the image processing system that utilised the unwrapped image may be degraded substantially. This accumulative nature of the phase unwrapping process imposes very stringent requirements on the algorithms that are designed to perform this task.

In reality, phase unwrapping is considered to be one of the most difficult problems in mathematics and engineering. A huge amount of effort has been devoted by different researchers to solving this problem, which has resulted in the development of a wide variety of proposed solutions. The various algorithms suggested frequently produce different results for the same input data-set, producing what may not be a definitively "correct" solution, but rather a set of solutions which are in some sense optimum or "most likely". Discontinuities in the measured object, the possible violation of Shannon’s Theorem due to under-sampling in real wrapped phase maps, and the variety of forms, shapes and densities of noise that might be found in real wrapped phase maps all contribute to make phase unwrapping an extremely complicated problem. A book has been published recently which clearly explains the difficulties in solving this problem and gives some suggested solutions [1].

Previous efforts to solve the phase unwrapping problem

An enormous number of algorithms have been suggested as solutions to the phase unwrapping problem and they vary widely in their approaches to a solution. The proposed solutions occupy a very wide range of mathematical and engineering theory, thereby making it difficult for any scientists researching the problem to fully understand the wide spectrum of these techniques. The list is of potential approaches is a very long one. Examples of theoretical principles that have been used to solve the phase unwrapping problem include the following: local and global optimisation theory, signal and image processing algorithms such as region growing, number theory, dynamic programming, graph theory, wavelets, the Fourier, Hilbert and cosine transforms, network flow algorithms, Bayesian approaches, probability and estimation theories, statistical approaches, Green’s functions, fractals, cellular automata, heuristic and exhaustive search algorithms, cost functions, minimum spanning tree methods, etc. The amount of research conducted in order to solve this problem reflects its importance. Over 500 journal papers have been published suggesting solutions to the phase unwrapping problem.

In what may possibly be considered to be a last resort to find a solution to the phase unwrapping problem, some researchers proposed the adoption of artificial intelligence methods. Artificial intelligence can be used in systems when the relationship between their input and output cannot be expressed in terms of closed formulae. The early attempts in this area utilized neural networks to try to solve the phase unwrapping problem and GERI also participated in such efforts [2]. The best result reported in the literature indicated that the ability of neural networks to differentiate between genuine and false phase wraps is only 95%. These levels of success, though they superficially seem reasonable, do not meet the stringent requirements for a robust phase unwrapping algorithm. Other artificial intelligence techniques have also been suggested, such as simulated annealing, reversed simulated annealing, mean-field annealing, and fuzzy logic. We have participated in these efforts and have suggested the use of genetic algorithms [3]. The results reported by all of these algorithms show they are still not sufficiently robust enough to be practically viable.

Even now researchers and engineers in the industrial and medical fields still regularly complain about the failure or unacceptable performance of existing phase unwrapping methods. Researchers have even attempted to use a collection of existing phase unwrapping algorithms, in order to benefit from the individual capabilities of each method drawn from a variety of applications [4, 5]. This rather desperate move shows the reliance of researchers on exhaustive computations and approximations, but offers little insight towards finding the cause of failure of the phase unwrapping process. In more elaborate efforts, researchers have developed phase unwrapping algorithms that are intimately tied to specific applications, in order to reduce the probability of their failure and they have partly succeeded in this effort. This has driven some researchers away from dealing with the main problem itself and has instead led them to come up with "partial solutions".

To date no knowledge exists on the general subject of why algorithms for phase unwrapping sometimes fail, even the most robust of the numerous algorithms available [1]. However research carried out within GERI may be taking the first steps to understanding the process of phase unwrapping algorithm failure [6]. The most evident disadvantage of the recent advances in phase unwrapping is a lack of generality, i.e. that any phase unwrapping algorithm cannot be used to unwrap any kind of wrapped phase. Algorithms are typically specific to certain applications, with a possibility of failure and in the case of very complex, noisy or under-sampled wrapped phase images, the unwrapping process may take huge amounts of processing time to achieve what may be described as a somewhat acceptable result. However, the demands upon the phase unwrapping process are becoming more and more stringent, driven by fast technological progress. Such demands are: the use of larger images, real time applications, unwrapping three dimensional video data, the need to unwrap very complex surfaces, medical applications that leave no margin for error (e.g., MRI scans), a drive to increase resolution detail, increased precision required in the resulting phase maps, and a need to minimise any human interaction occurring in the unwrapping process.

Introduction to the phase unwrapping problem

An introduction to the one-dimensional phase unwrapping problem can be downloaded:
Microsoft Word file | PDF file

An introduction to the two-dimensional phase unwrapping problem can be downloaded:
Microsoft Word file | PDF file

References

[1] D. Ghiglia and M. Pritt Two-dimensional phase unwrapping theory, algorithms and software, John Wiley & Sons, 1998.
[2] D. J. Tipper, D. R. Burton, M. J. Lalor, "A neural network approach to the phase unwrapping problem in fringe analysis," Nondestructive Testing and Evaluation, Vol. 12, No. 6, pp. 391-400, 1996.
[3] S. A. Karout, M. A. Gdeisat, D. R. Burton and M. J. Lalor, "Phase Unwrapping Using Hybrid Genetic Algorithms," Applied Optics, Vol. 46, No. 5, pp. 730-743, 2007.
[4] F. Qiangian, P. M. Meaney, and K. D. Paulsen, "The multidimensional phase unwrapping Integral and applications to microwave tomographical image reconstruction," IEEE Transactions on Image Processing, Vol. 15, No. 11, pp. 3311-24, 2006.
[5] C. W. Chen, and H. A. Zekber, "Phase unwrapping for large SAR interferograms: statistical segmentation and generalized network models," IEEE Transactions on Geoscience and Remote Sensing, Vol. 40, No. 8, pp. 1709-1719, 2002.
[6] S. A. Karout, M. A. Gdeisat, D. R. Burton, M. J. Lalor, "Residue Vector, An Approach To Branch-Cut Placement In Phase Unwrapping: Theoretical Study", Applied Optics, doi:10.1364/AO.46.004712, Vol. 46, No. 21, pp 4712-4727, 2007.

Two-dimensional phase unwrapping using hybrid genetic algorithms

Phase unwrapping (PU) is a technique used on wrapped phase images to remove the discontinuities embedded within the phase map. It detects a discontinuity and adds or subtracts an integer offset of 2-pi to successive pixels following that discontinuity. Then it moves on, searching for another discontinuity. Thus, retrieving the continuous form of the phase map.

In this project, a Genetic Algorithm (GA), an artificial intelligence method, is used to detect these discontinuities embedded in the phase map and eliminating the factor of noise which stands against a perfect unwrapping in most unwrapping algorithms. Once noise effect is eliminated prior to unwrapping. Then, unwrapping can take place in a more efficient way undisturbed by noise, thus providing the unwrapping algorithm with an independent path, which it can follow throughout the two-dimensional phase map image.

The GA will be represented in three different ways. The first technique uses local search methods to highlight inconsistencies within the phase map image called "residues", then eliminating them by using branch cuts that excludes them from the image while unwrapping. The second technique uses a global search method to minimise the minimum squared error between the ideal unwrapped phase map and the actual wrapped phase map. The final method is a hybrid form of unwrapping that uses both the local and the global methods in unwrapping.

The GA for phase unwrapping will be used as an artificial intelligence optimisation method in order to achieve fast and efficient unwrapping results on noisy data where no unwrapping algorithm has been successful to date. It has proven its efficiency in different fields especially image processing. It is a very powerful method in overcoming noise from an application [1].

Salah Karout
[1] Karout. S. A, Gdeisat. M. A, Burton. D. R. and Lalor. M. J, "Phase Unwrapping Using Hybrid Genetic Algorithms", Applied Optics, Vol. 46, No. 5, pp 730-743, 2006.

Three-dimensional phase unwrapping

Building on our work in two-dimensional phase unwrapping, research staff at the General Engineering Research Institute have developed a number of three-dimensional phase unwrappers. Some of these 3D phase unwrappers are published online on our website, as detailed below.

1. Fast, three-dimensional phase-unwrapping algorithm, based on sorting by reliability, following a non-continuous path. (3D-SRNCP)

This 3D phase unwrapping algorithm unwraps the highest quality voxels first and the lowest quality voxels last, in order to prevent error propagation. The quality of a voxel is determined using the second difference algorithm. In a similar manner to its 2D counterpart, the 3D unwrapper follows a discrete path in order to perform the unwrapping process [1].

This 3D unwrapper has been programmed in the C language. We have produced two versions of this algorithm: i.e. with and without a masking option.
In addition Eric Barnhill at the Clinical Research Imaging Centre, The University of Edinburgh has implemented the 3D-SRNCP algorithm as a Java ImageJ Plugin which is available online.

2. Robust three-dimensional best path phase unwrapping algorithm that avoids singularity loops.

This 3D phase unwrapping algorithm combines the advantages and avoids the drawbacks of two well-known three-dimensional phase unwrapping algorithms, namely the three-dimensional phase unwrapping noise immune technique [2] and the three-dimensional phase unwrapping best path technique [1]. This hybrid technique is more robust than its predecessors since it not only follows a discrete unwrapping path depending upon a 3D quality map, but it also avoids any singularity loops that may occur in the unwrapping path.

This algorithm has been programmed in the C computer language. The C code is freely publicly available.

[1] H. Abdul-Rahamn, M. A. Gdeisat, D. R. Burton, M. J. Lalor, F. Lilley, and C. Moore, "Fast And Robust Three-Dimensional Best Path Phase Unwrapping Algorithm", Applied Optics, Vol. 46, No. 26, pp. 6623-6635, 2007.
[2] J. M. Huntley, “Three-dimensional noise-immune phase unwrapping algorithm,” Applied Optics, Vol. 40, pp. 3901-3908, 2001.

Find out more about the research within the General Engineering Research Institute (GERI).

Contact us

For more information about research at Liverpool John Moores University:
Call: 0151 231 8091 | Email: impact@ljmu.ac.uk