Phase unwrapping

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 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 here on our website 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 licence. Phase unwrapping algorithms may also be customised in order to meet your application requirements. Please contact Dr. Francis Lilley F.Lilley@ljmu.ac.uk if you have a commercial enquiry regarding use of our phase unwrapping algorithms.

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 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 utilised neural networks to try to solve the phase unwrapping problem and at GERI our Institute 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 as Microsoft Word file or pdf file. Also an introduction to the two-dimensional phase unwrapping problem can be downloaded as Microsoft Word file or 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.

At GERI we have developed a number of robust and fast two-dimensional phase unwrappers. Examples of these algorithms are described below.

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

This quality-guided, path-following, phase unwrapping algorithm unwraps pixels in an order depending upon their quality. High quality pixels are unwrapped first and low quality pixels are unwrapped last, in order to minimise error propagation. The quality or reliability of a pixel is determined using the second difference quality map technique. This phase unwrapper follows a non-continuous path in order to perform the phase unwrapping process, as described in [1]. The determination of the unwrapping path using this non-continuous method gives much better results than the well-known flood-fill technique.

We have coded this algorithm in the C language and there are several different versions of the algorithm, which are described below.

1.1 2D-SRNCP phase unwrapper

This code implements the algorithm explained in [1]. The code was written with speed and simplicity in mind. Hence the code is very easy to follow and has been designed to execute very quickly on digital computers. As a general guideline to the algorithm’s performance levels, this code was benchmarked on a 2.4 GHz Pentium 4 PC with 2Gb RAM and the execution time required to unwrap a wrapped phase map of dimensions 512 x 512 pixels is of the order of 0.25 seconds.

1.2 2D-SRNCP phase unwrapper with mask

This program has a masking facility so that corrupted pixels can be masked and excluded from the unwrapping process. An independent binary masking map is required for this unwrapper, that must be provided by the user.

2. Iso-phase 2D phase unwrapper

This algorithm uses a region merging principle to perform the phase unwrapping process. The operation of this phase unwrapper is explained in [2].

2.1 Iso-Phase 2D phase unwrapper

In addition Eric Barnhill at the Clinical Research Imaging Centre, The University of Edinburgh has implemented the 2D-SRNCP and Iso-Phase 2D algorithms as Java ImageJ Plugins which are available online.

[1] M. Arevalillo Herráez, D. R. Burton, M. J. Lalor and M. A. Gdeisat, "A Fast two-dimensional phase unwrapping algorithm based on sorting by reliability following a non-continuous path," Applied Optics, Vol. 41, No. 35, pp 7437-7444, 2002.

[2] M. Arevalillo Herráez,  M. A. Gdeisat, D. R. Burton, and M. J. Lalor,  "Robust, fast, and effective two-dimensional automatic phase unwrapping algorithm based on image decomposition," Applied Optics, Vol. 41, No. 35, pp 7445-7455, 2002.

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.

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.

Phase unwrapping solutions can be tailored to a given specific application. In this manner, information extracted from physical properties which are associated with the application can help in improving the performance of the phase unwrapper and hence better results may be produced.

This principle has been applied to 2D phase unwrappers. For example, the correlation map produced by SAR radar applications can be used as a quality map in order to guide 2D phase unwrappers. The unwrapped phase produced using this method delivers better results than that produced by simply extracting the quality map from the wrapped phase map [1]. A second example, this time in the field of fringe pattern analysis, is that of the use of the phase-stepping method to measure 3D surface height. In this method, the wrapped phase and the visibility of the fringes can be extracted. The visibility image can also be used as a quality map in order to guide 2D phase unwrappers [2].

An example that uses this principle for 3D phase unwrappers is explained in [3]. In magnetic resonance imaging (MRI) of arterial flow, the physical properties of flowing blood are used to help the 3D unwrapper in its operation [3].

In GERI, we have more than twenty years experience in conducting research into the phase unwrapping problem and we have designed many very robust phase unwrappers. We have published the source code of some of these unwrappers on our website. If you have an application that you feel may benefit from the customisation of one our advanced high-performance phase unwrappers, we would be happy to provide you with this service. To contact GERI regarding this matter, please send an email to m.a.gdeisat@ljmu.ac.uk

We have customised our 2D-SRNCP and 3D-SRNCP phase unwrapping algorithms for a number of clients. Examples of a number of customised phase unwrappers and their source code are given below.

1.1 2D-SRNCP Phase unwrapper with wrap-around option

This algorithm is explained in reference [4] and is implemented using the C programming language. The algorithm has a wrap-around option that is useful in the unwrapping of 2D images for MRI applications. The wrap-around option is provided for both x and y axes.

1.2 2D-SRNCP Phase unwrapper with mask and wrap-around options

As above in 1.1, but with a masking facility to discount areas of bad/missing data.

1.3 3D-SRNCP Phase unwrapper with wrap-around option

This algorithm is explained in reference [5] and is implemented using the C programming language. The algorithm has a wrap-around option that is useful in the unwrapping of 3D phase volumes for MRI applications. The wrap-around option is provided for the x, y and z axes.

1.4 3D-SRNCP Phase unwrapper with mask and wrap-around options

As above in 1.3, but with a masking facility to discount areas of bad/missing data.

References

[1] D. C. Ghiglia and M. D. Pritt, Two-dimensional phase unwrapping theory, algorithms and software, John Wiley & Sons, 1998.

[2] D. W. Robinson and G. T. Reid, Interferogram Analysis Digital Fringe Pattern Measurement techniques, Institute of Physics Publishing, 2003.

[3] M. F. Salfity, P. D. Ruiz, J. M. Huntley, M. J. Graves, R. Cusack and D. A. Beauregard, "Branch cut surface placement for unwrapping of undersampled three-dimensional phase data: application to magnetic resonance imaging arterial flow mapping, " Applied Optics, Vol.45, No. 12, pp. 2711-2722.

[4] M. Arevalillo Herráez, D. R. Burton, M. J. Lalor and M. A. Gdeisat, "A Fast two-dimensional phase unwrapping algorithm based on sorting by reliability following a non-continuous path," Applied Optics, Vol. 41, No. 35, pp 7437-7444, 2002.

[5] 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.