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 L0-norm problem is 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 L0 case. This algorithm yields excellent approximations to the minimum L0 norm. Using interferometric data, we demonstrate that our algorithms are highly competitive with other existing algorithms in speed and accuracy, outperforming them in the cases presented here.

© 2000 Optical Society of America

Full Article  |  PDF Article

Errata

Curtis W. Chen and Howard A. Zebker, "Network approaches to two-dimensional phase unwrapping: intractability and two new algorithms: erratum," J. Opt. Soc. Am. A 18, 1192-1192 (2001)
https://www.osapublishing.org/josaa/abstract.cfm?uri=josaa-18-5-1192

References

  • View by:
  • |
  • |
  • |

  1. H. Zebker, R. Goldstein, “Topographic mapping from interferometric SAR observations,” J. Geophys. Res. 91, 4993–4999 (1986).
    [CrossRef]
  2. 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]
  3. 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]
  4. 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]
  5. 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]
  6. R. M. Goldstein, H. A. Zebker, “Interferometric radar measurements of ocean surface currents,” Nature (London) 328, 707–709 (1987).
    [CrossRef]
  7. 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]
  8. M. Costantini, “A novel phase unwrapping method based on network programming,” IEEE Trans. Geosci. Remote Sens. 36, 813–821 (1998).
    [CrossRef]
  9. T. J. Flynn, “Two-dimensional phase unwrapping with minimum weighted discontinuity,” J. Opt. Soc. Am. A 14, 2692–2701 (1997).
    [CrossRef]
  10. R. M. Goldstein, H. A. Zebker, C. L. Werner, “Satellite radar interferometry: two-dimensional phase unwrapping,” Radio Sci. 23, 713–720 (1988).
    [CrossRef]
  11. 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]
  12. D. C. Ghiglia, L. A. Romero, “Minimum Lp-norm two-dimensional phase unwrapping,” J. Opt. Soc. Am. A 13, 1999–2013 (1996).
    [CrossRef]
  13. D. C. Ghiglia, M. D. Pritt, Two-Dimensional Phase Unwrapping: Theory, Algorithms, and Software (Wiley, New York, 1998).
  14. R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, Englewood Cliffs, N.J., 1993).
  15. 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]
  16. M. D. Pritt, “Phase unwrapping by means of multigrid techniques for interferometric SAR,” IEEE Trans. Geosci. Remote Sens. 34, 728–738 (1996).
    [CrossRef]
  17. G. Fornaro, G. Franceschetti, R. Lanari, E. Sansosti, “Robust phase unwrapping techniques: a comparison,” J. Opt. Soc. Am. A 13, 2355–2366 (1996).
    [CrossRef]
  18. 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]
  19. M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, Calif., 1979).
  20. F. K. Hwang, “On Steiner minimal trees with rectilinear distance,” SIAM J. Appl. Math. 30, 104–114 (1976).
    [CrossRef]
  21. 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]
  22. H. A. Zebker, J. Villasenor, “Decorrelation in interferometric radar echoes,” IEEE Trans. Geosci. Remote Sens. 30, 950–959 (1992).
    [CrossRef]
  23. 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]
  24. 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]
  25. M. R. Garey, D. S. Johnson, “The rectilinear Steiner tree problem is NP-Complete,” SIAM J. Appl. Math. 32, 826–834 (1977).
    [CrossRef]
  26. M. Hanan, “On Steiner’s problem with rectilinear distance,” J. SIAM Appl. Math. 2, 255–265 (1966).
    [CrossRef]
  27. 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]
  28. G. M. Guisewite, P. M. Pardalos, “Minimum concave-cost network flow problems: applications, complexity and algorithms,” Annals Oper. Res. 25, 75–100 (1990).
    [CrossRef]

1998

M. Costantini, “A novel phase unwrapping method based on network programming,” IEEE Trans. Geosci. Remote Sens. 36, 813–821 (1998).
[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]

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]

1997

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]

T. J. Flynn, “Two-dimensional phase unwrapping with minimum weighted discontinuity,” J. Opt. Soc. Am. A 14, 2692–2701 (1997).
[CrossRef]

1996

1995

1994

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]

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]

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]

1993

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]

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]

1992

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]

1990

G. M. Guisewite, P. M. Pardalos, “Minimum concave-cost network flow problems: applications, complexity and algorithms,” Annals Oper. Res. 25, 75–100 (1990).
[CrossRef]

1989

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]

1988

R. M. Goldstein, H. A. Zebker, C. L. Werner, “Satellite radar interferometry: two-dimensional phase unwrapping,” Radio Sci. 23, 713–720 (1988).
[CrossRef]

1987

R. M. Goldstein, H. A. Zebker, “Interferometric radar measurements of ocean surface currents,” Nature (London) 328, 707–709 (1987).
[CrossRef]

1986

H. Zebker, R. Goldstein, “Topographic mapping from interferometric SAR observations,” J. Geophys. Res. 91, 4993–4999 (1986).
[CrossRef]

1977

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]

M. R. Garey, D. S. Johnson, “The rectilinear Steiner tree problem is NP-Complete,” SIAM J. Appl. Math. 32, 826–834 (1977).
[CrossRef]

1976

F. K. Hwang, “On Steiner minimal trees with rectilinear distance,” SIAM J. Appl. Math. 30, 104–114 (1976).
[CrossRef]

1966

M. Hanan, “On Steiner’s problem with rectilinear distance,” J. SIAM Appl. Math. 2, 255–265 (1966).
[CrossRef]

Adragna, F.

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]

Ahuja, R. K.

R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, Englewood Cliffs, N.J., 1993).

Braun, M.

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]

Buckland, J. R.

Carmona, C.

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]

Ching, N. H.

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]

Costantini, M.

M. Costantini, “A novel phase unwrapping method based on network programming,” IEEE Trans. Geosci. Remote Sens. 36, 813–821 (1998).
[CrossRef]

Cubero-Castan, E.

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]

Dixon, T. H.

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]

Englehardt, H.

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]

Farr, T. G.

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]

Feigl, K.

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]

Fjørtoft, R.

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]

Flynn, T. J.

Fornaro, G.

Franceschetti, G.

Frolich, R. M.

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]

Gabriel, A.

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]

Gabriel, A. K.

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]

Garey, M. R.

M. R. Garey, D. S. Johnson, “The rectilinear Steiner tree problem is NP-Complete,” SIAM J. Appl. Math. 32, 826–834 (1977).
[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]

M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, Calif., 1979).

Ghiglia, D. C.

Goldstein, R.

H. Zebker, R. Goldstein, “Topographic mapping from interferometric SAR observations,” J. Geophys. Res. 91, 4993–4999 (1986).
[CrossRef]

Goldstein, R. M.

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

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]

R. M. Goldstein, H. A. Zebker, C. L. Werner, “Satellite radar interferometry: two-dimensional phase unwrapping,” Radio Sci. 23, 713–720 (1988).
[CrossRef]

R. M. Goldstein, H. A. Zebker, “Interferometric radar measurements of ocean surface currents,” Nature (London) 328, 707–709 (1987).
[CrossRef]

Graham, R. L.

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]

Guisewite, G. M.

G. M. Guisewite, P. M. Pardalos, “Minimum concave-cost network flow problems: applications, complexity and algorithms,” Annals Oper. Res. 25, 75–100 (1990).
[CrossRef]

Hanan, M.

M. Hanan, “On Steiner’s problem with rectilinear distance,” J. SIAM Appl. Math. 2, 255–265 (1966).
[CrossRef]

Hensley, S.

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]

Huntley, J. M.

Hwang, F. K.

F. K. Hwang, “On Steiner minimal trees with rectilinear distance,” SIAM J. Appl. Math. 30, 104–114 (1976).
[CrossRef]

Johnson, D. S.

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]

M. R. Garey, D. S. Johnson, “The rectilinear Steiner tree problem is NP-Complete,” SIAM J. Appl. Math. 32, 826–834 (1977).
[CrossRef]

M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, Calif., 1979).

Kamb, B.

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]

Lanari, R.

Lopès, A.

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]

Lu, Y.

Magnanti, T. L.

R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, Englewood Cliffs, N.J., 1993).

Marathon, P.

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]

Massonnet, D.

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]

Orlin, J. B.

R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, Englewood Cliffs, N.J., 1993).

Pardalos, P. M.

G. M. Guisewite, P. M. Pardalos, “Minimum concave-cost network flow problems: applications, complexity and algorithms,” Annals Oper. Res. 25, 75–100 (1990).
[CrossRef]

Peltzer, G.

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]

Pritt, M. D.

M. D. Pritt, “Phase unwrapping by means of multigrid techniques for interferometric SAR,” IEEE Trans. Geosci. Remote Sens. 34, 728–738 (1996).
[CrossRef]

D. C. Ghiglia, M. D. Pritt, Two-Dimensional Phase Unwrapping: Theory, Algorithms, and Software (Wiley, New York, 1998).

Rabaute, T.

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]

Romero, L. A.

Rosen, P. A.

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]

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]

Rosenfeld, D.

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]

Rossi, M.

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]

Salazar, R. P.

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]

Sansosti, E.

Turner, S. R. E.

Villasenor, J.

H. A. Zebker, J. Villasenor, “Decorrelation in interferometric radar echoes,” IEEE Trans. Geosci. Remote Sens. 30, 950–959 (1992).
[CrossRef]

Werner, C.

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]

Werner, C. L.

R. M. Goldstein, H. A. Zebker, C. L. Werner, “Satellite radar interferometry: two-dimensional phase unwrapping,” Radio Sci. 23, 713–720 (1988).
[CrossRef]

Zebker, H.

H. Zebker, R. Goldstein, “Topographic mapping from interferometric SAR observations,” J. Geophys. Res. 91, 4993–4999 (1986).
[CrossRef]

Zebker, H. A.

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]

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]

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]

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]

H. A. Zebker, J. Villasenor, “Decorrelation in interferometric radar echoes,” IEEE Trans. Geosci. Remote Sens. 30, 950–959 (1992).
[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]

R. M. Goldstein, H. A. Zebker, C. L. Werner, “Satellite radar interferometry: two-dimensional phase unwrapping,” Radio Sci. 23, 713–720 (1988).
[CrossRef]

R. M. Goldstein, H. A. Zebker, “Interferometric radar measurements of ocean surface currents,” Nature (London) 328, 707–709 (1987).
[CrossRef]

Annals Oper. Res.

G. M. Guisewite, P. M. Pardalos, “Minimum concave-cost network flow problems: applications, complexity and algorithms,” Annals Oper. Res. 25, 75–100 (1990).
[CrossRef]

Appl. Opt.

IEEE Trans. Geosci. Remote Sens.

M. D. Pritt, “Phase unwrapping by means of multigrid techniques for interferometric SAR,” IEEE Trans. Geosci. Remote Sens. 34, 728–738 (1996).
[CrossRef]

M. Costantini, “A novel phase unwrapping method based on network programming,” IEEE Trans. Geosci. Remote Sens. 36, 813–821 (1998).
[CrossRef]

H. A. Zebker, J. Villasenor, “Decorrelation in interferometric radar echoes,” IEEE Trans. Geosci. Remote Sens. 30, 950–959 (1992).
[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]

IEEE Trans. Image Process.

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]

J. Geophys. Res.

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]

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]

H. Zebker, R. Goldstein, “Topographic mapping from interferometric SAR observations,” J. Geophys. Res. 91, 4993–4999 (1986).
[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]

J. Opt. Soc. Am. A

J. SIAM Appl. Math.

M. Hanan, “On Steiner’s problem with rectilinear distance,” J. SIAM Appl. Math. 2, 255–265 (1966).
[CrossRef]

Nature (London)

R. M. Goldstein, H. A. Zebker, “Interferometric radar measurements of ocean surface currents,” Nature (London) 328, 707–709 (1987).
[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]

Proc. IEEE

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]

Radio Sci.

R. M. Goldstein, H. A. Zebker, C. L. Werner, “Satellite radar interferometry: two-dimensional phase unwrapping,” Radio Sci. 23, 713–720 (1988).
[CrossRef]

Science

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]

SIAM J. Appl. Math.

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]

M. R. Garey, D. S. Johnson, “The rectilinear Steiner tree problem is NP-Complete,” SIAM J. Appl. Math. 32, 826–834 (1977).
[CrossRef]

F. K. Hwang, “On Steiner minimal trees with rectilinear distance,” SIAM J. Appl. Math. 30, 104–114 (1976).
[CrossRef]

Other

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).

M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, Calif., 1979).

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (13)

Fig. 1
Fig. 1

Example network equivalent of the phase unwrapping problem. The numbers represent the 2-D array of phase samples (normalized to one cycle). Each 2×2 clockwise loop integral of wrapped phase gradients is a node in the network, and positive and negative residues result in supply and demand nodes. Neighboring nodes are connected by arcs, or possible flow paths. The amount of flow on an arc represents the difference (in cycles) between the unwrapped and the wrapped phase gradients associated with that arc. The net amount of flow out of a node must be equal to the node’s surplus.

Fig. 2
Fig. 2

Residue arrangement and flow in the presence of topographic layover with radar illumination from the left and hence range increasing toward the right. The residue arrangement reflects two peaks in layover. The arrows represent flow in the directions shown, with magnitudes indicated by the numbers. The L0 optimal solution (left) correctly reflects the multiple-cycle discontinuity, whereas the L1 optimal solution (right) does not.

Fig. 3
Fig. 3

A minimum spanning tree connects all residues (a). The tree branches are possible locations of discontinuities (b), which occur where flow on the tree is nonzero. The numbers represent flow magnitudes.

Fig. 4
Fig. 4

Residues and cuts are associated with phase values (gray boxes) in the original implementation of the residue-cut algorithm. This allows the cuts to close on themselves so that pixel X cannot be unwrapped. When discontinuities are associated with phase differences (heavy lines), as in Fig. 1, no pixels are isolated. Note that the tree shown is a spanning tree but not a minimum spanning tree.

Fig. 5
Fig. 5

Original and residual arcs for an L1 network problem. The residual arcs represent the costs and possible flow paths for an incremental amount of flow δ given the existing flow.

Fig. 6
Fig. 6

A nonoptimal flow in the L1 sense (a) may be improved on by augmenting flow on a closed, directed cycle (dashed line) with a net negative residual cost. The result (b) is a feasible solution with a smaller total cost. The numbers indicate flow magnitudes. The cycle shown also has negative cost with respect to the L0 metric for δ=2 but not for δ2.

Fig. 7
Fig. 7

Original and residual arcs for the L0 network problem. The nonlinearity of the L0 objective makes arc costs in the residual network dependent on the flow in the current solution.

Fig. 8
Fig. 8

Data used to test the algorithms: (a) wrapped interferogram with magnitude in gray-scale and phase in color, (b) locations of phase residues, (c) reference DEM with shaded relief in gray-scale and elevation in color.

Fig. 9
Fig. 9

Algorithm results with uniform weights: (a) residue-cut, (b) MST, (c) DCC, (d) LSQ, (e) MCF, (f) Lp-norm. The color represents relative phase error calculated with the reference DEM.

Fig. 10
Fig. 10

Algorithm results with interferogram coherence used as weights: (a) weight mask, (b) MST, (c) DCC, (d) LSQ, (e) MCF, (f) Lp-norm. The color represents relative phase error.

Fig. 11
Fig. 11

Algorithm results with edge detection used for weights: (a) weight mask, (b) MST, (c) DCC, (d) LSQ, (e) MCF, (f) Lp-norm. The color represents relative phase error.

Fig. 12
Fig. 12

L0 network formulation of a RST problem instance. Positive residues are located at the points in S, and negative residues are lined up to the right of the rightmost positive residue. The optimal L0 solution must be a single minimum Steiner tree, whose length is n units longer than the minimum length for the original RST problem.

Fig. 13
Fig. 13

Part of an L0 solution, where the numbers indicate flow magnitudes. (a) Noninteger flows must be arranged in closed loops if the net flow out of a node is equal to the node’s charge. (b) The loop can always be broken and the flows reallocated to form integer flows constituting a better feasible L0 solution.

Tables (2)

Tables Icon

Table 1 Summary of Error Measures for Unwrapped Solutions Presented

Tables Icon

Table 2 Computational Costs of Algorithms

Equations (4)

Equations on this page are rendered with MathJax. Learn more.

minimizei,jwi,j(x)|Δϕi,j(x)-Δψi,j(x)|p+i,jwi,j(y)|Δϕi,j(y)-Δψi,j(y)|p,
lRn+(ymax-y0)+(y0-ymin)+(m-1).
lRlR=n+(ymax-y0)+(y0-ymin).
0000000.25000.750.500000.

Metrics