## Network approaches to two-dimensional phase unwrapping: intractability and two new algorithms

JOSA A, Vol. 17, Issue 3, pp. 401-414 (2000)

http://dx.doi.org/10.1364/JOSAA.17.000401

Enhanced HTML Acrobat PDF (364 KB)

### Abstract

Two-dimensional (2-D) phase unwrapping, that is, deducing unambiguous phase values from a 2-D array of values known only modulo 2*π*, is a key step in interpreting data acquired with synthetic aperture radar interferometry. Noting the recent network formulation of the phase unwrapping problem, we apply here some well-established ideas of network theory to formalize the problem, analyze its complexity, and derive algorithms for its solution. It has been suggested that the objective of phase unwrapping should be to minimize the total number of places where unwrapped and wrapped phase gradients differ. Here we use network constructions to show that this so-called minimum *NP*-hard, or one that complexity theory suggests is impossible for efficient algorithms to solve exactly. Therefore we must instead find approximate solutions; we present two new algorithms for doing so. The first uses the network ideas of shortest paths and spanning trees to improve on the Goldstein *et al*. residue-cut algorithm [Radio Sci. 23, 713 (1988)]. Our improved algorithm is very fast, provides complete coverage, and allows user-defined weights. With our second algorithm, we extend the ideas of linear network flow problems to the nonlinear

© 2000 Optical Society of America

**OCIS Codes**

(120.3180) Instrumentation, measurement, and metrology : Interferometry

(280.6730) Remote sensing and sensors : Synthetic aperture radar

(350.5030) Other areas of optics : Phase

**History**

Original Manuscript: June 18, 1999

Revised Manuscript: October 12, 1999

Manuscript Accepted: October 14, 1999

Published: March 1, 2000

**Citation**

Curtis W. Chen and Howard A. Zebker, "Network approaches to two-dimensional phase unwrapping: intractability and two new algorithms," J. Opt. Soc. Am. A **17**, 401-414 (2000)

http://www.opticsinfobase.org/josaa/abstract.cfm?URI=josaa-17-3-401

Sort: Year | Journal | Reset

### References

- H. Zebker, R. Goldstein, “Topographic mapping from interferometric SAR observations,” J. Geophys. Res. 91, 4993–4999 (1986). [CrossRef]
- H. A. Zebker, T. G. Farr, R. P. Salazar, T. H. Dixon, “Mapping the world’s topography using radar interferometry: the TOPSAT mission,” Proc. IEEE 82, 1774–1786 (1994). [CrossRef]
- A. K. Gabriel, R. M. Goldstein, H. A. Zebker, “Mapping small elevation changes over large areas: differential radar interferometry,” J. Geophys. Res. 94, 9183–9191 (1989). [CrossRef]
- D. Massonnet, M. Rossi, C. Carmona, F. Adragna, G. Peltzer, K. Feigl, T. Rabaute, “The displacement field of the Landers earthquake mapped by radar interferometry,” Nature (London) 364, 138–142 (1993). [CrossRef]
- H. A. Zebker, P. A. Rosen, R. M. Goldstein, A. Gabriel, C. Werner, “On the derivation of coseismic displacement fields using differential radar interferometry: the Landers earthquake,” J. Geophys. Res. 99, 19617–19634 (1994). [CrossRef]
- R. M. Goldstein, H. A. Zebker, “Interferometric radar measurements of ocean surface currents,” Nature (London) 328, 707–709 (1987). [CrossRef]
- R. M. Goldstein, H. Englehardt, B. Kamb, R. M. Frolich, “Satellite radar interferometry for monitoring ice sheet motion: application to an Antarctic ice stream,” Science 262, 1525–1530 (1993). [CrossRef] [PubMed]
- M. Costantini, “A novel phase unwrapping method based on network programming,” IEEE Trans. Geosci. Remote Sens. 36, 813–821 (1998). [CrossRef]
- T. J. Flynn, “Two-dimensional phase unwrapping with minimum weighted discontinuity,” J. Opt. Soc. Am. A 14, 2692–2701 (1997). [CrossRef]
- R. M. Goldstein, H. A. Zebker, C. L. Werner, “Satellite radar interferometry: two-dimensional phase unwrapping,” Radio Sci. 23, 713–720 (1988). [CrossRef]
- J. R. Buckland, J. M. Huntley, S. R. E. Turner, “Unwrapping noisy phase maps by use of a minimum-cost-matching algorithm,” Appl. Opt. 34, 5100–5108 (1995). [CrossRef] [PubMed]
- D. C. Ghiglia, L. A. Romero, “Minimum Lp-norm two-dimensional phase unwrapping,” J. Opt. Soc. Am. A 13, 1999–2013 (1996). [CrossRef]
- D. C. Ghiglia, M. D. Pritt, Two-Dimensional Phase Unwrapping: Theory, Algorithms, and Software (Wiley, New York, 1998).
- R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, Englewood Cliffs, N.J., 1993).
- D. C. Ghiglia, L. A. Romero, “Robust two-dimensional weighted and unweighted phase unwrapping that uses fast transforms and iterative methods,” J. Opt. Soc. Am. A 11, 107–117 (1994). [CrossRef]
- M. D. Pritt, “Phase unwrapping by means of multigrid techniques for interferometric SAR,” IEEE Trans. Geosci. Remote Sens. 34, 728–738 (1996). [CrossRef]
- G. Fornaro, G. Franceschetti, R. Lanari, E. Sansosti, “Robust phase unwrapping techniques: a comparison,” J. Opt. Soc. Am. A 13, 2355–2366 (1996). [CrossRef]
- H. A. Zebker, Y. Lu, “Phase unwrapping algorithms for radar interferometry: residue-cut, least-squares, and synthesis algorithms,” J. Opt. Soc. Am. A 15, 586–598 (1998). [CrossRef]
- M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, Calif., 1979).
- F. K. Hwang, “On Steiner minimal trees with rectilinear distance,” SIAM J. Appl. Math. 30, 104–114 (1976). [CrossRef]
- N. H. Ching, D. Rosenfeld, M. Braun, “Two-dimensional phase unwrapping using a minimum spanning tree algorithm,” IEEE Trans. Image Process. 1, 355–365 (1992). [CrossRef] [PubMed]
- H. A. Zebker, J. Villasenor, “Decorrelation in interferometric radar echoes,” IEEE Trans. Geosci. Remote Sens. 30, 950–959 (1992). [CrossRef]
- H. A. Zebker, P. A. Rosen, S. Hensley, “Atmospheric effects in interferometric synthetic aperture radar surface deformation and topography maps,” J. Geophys. Res. 102, 7547–7563 (1997). [CrossRef]
- R. Fjørtoft, A. Lopès, P. Marathon, E. Cubero-Castan, “An optimal multiedge detector for SAR image segmentation,” IEEE Trans. Geosci. Remote Sens. 36, 793–802 (1998). [CrossRef]
- M. R. Garey, D. S. Johnson, “The rectilinear Steiner tree problem is NP-Complete,” SIAM J. Appl. Math. 32, 826–834 (1977). [CrossRef]
- M. Hanan, “On Steiner’s problem with rectilinear distance,” J. SIAM Appl. Math. 2, 255–265 (1966). [CrossRef]
- M. R. Garey, R. L. Graham, D. S. Johnson, “The complexity of computing Steiner minimal trees,” SIAM J. Appl. Math. 32, 835–859 (1977). [CrossRef]
- G. M. Guisewite, P. M. Pardalos, “Minimum concave-cost network flow problems: applications, complexity and algorithms,” Annals Oper. Res. 25, 75–100 (1990). [CrossRef]

## Cited By |
Alert me when this paper is cited |

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

### Figures

Fig. 1 |
Fig. 2 |
Fig. 3 |

Fig. 4 |
Fig. 5 |
Fig. 6 |

Fig. 7 |
Fig. 8 |
Fig. 9 |

Fig. 10 |
Fig. 11 |
Fig. 12 |

Fig. 13 |
||

« Previous Article | Next Article »

OSA is a member of CrossRef.