Abstract

We present here a new integer programming formulation for phase unwrapping of multidimensional data. Phase unwrapping is a key problem in many coherent imaging systems, including time series synthetic aperture radar interferometry (InSAR), with two spatial and one temporal data dimensions. The minimum cost flow (MCF) [IEEE Trans. Geosci. Remote Sens. 36, 813 (1998) ] phase unwrapping algorithm describes a global cost minimization problem involving flow between phase residues computed over closed loops. Here we replace closed loops by reliable edges as the basic construct, thus leading to the name “edgelist.” Our algorithm has several advantages over current methods—it simplifies the representation of multidimensional phase unwrapping, it incorporates data from external sources, such as GPS, where available to better constrain the unwrapped solution, and it treats regularly sampled or sparsely sampled data alike. It thus is particularly applicable to time series InSAR, where data are often irregularly spaced in time and individual interferograms can be corrupted with large decorrelated regions. We show that, similar to the MCF network problem, the edgelist formulation also exhibits total unimodularity, which enables us to solve the integer program problem by using efficient linear programming tools. We apply our method to a persistent scatterer-InSAR data set from the creeping section of the Central San Andreas Fault and find that the average creep rate of 22mmYr is constant within 3mmYr over 1992–2004 but varies systematically with ground location, with a slightly higher rate in 1992–1998 than in 1999–2003.

© 2010 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. M. Costantini, “A novel phase unwrapping method based on network programming,” IEEE Trans. Geosci. Remote Sens. 36, 813-821 (1998).
    [CrossRef]
  2. B. R. Hunt, “Matrix formulation of the reconstruction of phase values from phase differences,” J. Opt. Soc. Am. 69, 393-399 (1979).
    [CrossRef]
  3. R. M. Goldstein, H. A. Zebker, and C. L. Werner, “Satellite radar interferometry: two-dimensional phase unwrapping,” Radio Sci. 23, 713-720 (1988).
    [CrossRef]
  4. N. H. Ching, D. Rosenfeld, and M. Braun, “Two-dimensional phase unwrapping using a minimum spanning tree algorithm,” IEEE Trans. Image Process. 1, 355-365 (1992).
    [CrossRef] [PubMed]
  5. D. C. Ghiglia and L. A. Romero, “Minimum Lp-norm two-dimensional phase unwrapping,” J. Opt. Soc. Am. A 13, 1999-2013 (1996).
    [CrossRef]
  6. M. D. Pritt, “Phase unwrapping by means of multigrid techniques for interferometric SAR,” IEEE Trans. Geosci. Remote Sens. 34, 728-738 (1996).
    [CrossRef]
  7. T. J. Flynn, “Two-dimensional phase unwrapping with minimum weighted discontinuity,” J. Opt. Soc. Am. A 14, 2692-2701 (1997).
    [CrossRef]
  8. H. A. Zebker and 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]
  9. C. W. Chen and H. A. Zebker, “Network approaches to two-dimensional phase unwrapping: intractability and two new algorithms,” J. Opt. Soc. Am. A 17, 401-414 (2000).
    [CrossRef]
  10. A. Hooper and H. Zebker, “Phase unwrapping three dimensions, with applications to InSAR time series,” J. Opt. Soc. Am. A 24, 2737-2747 (2007).
    [CrossRef]
  11. D. C. Ghiglia and 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]
  12. M. Costantini and P. A. Rosen, “A generalized phase unwrapping approach for sparse data,” in IEEE 1999 International Geoscience and Remote Sensing Symposium, 1999, IGARSS'99 (IEEE, 1999), Vol. 1, pp. 267-269.
    [CrossRef]
  13. C. Barber and H. Hudanpaa, Qhull, http://www.qhull. org.
  14. C. W. Chen and H. A. Zebker, “Two-dimensional phase unwrapping with use of statistical models for cost functions in nonlinear optimization,” J. Opt. Soc. Am. A 18, 338-351 (2001).
    [CrossRef]
  15. R. K. Ahuja, D. S. Hochbaum, and J. B. Orlin, “Solving the convex cost integer dual network flow problem,” in Integer Programming and Combinatorial Optimization, G.Cornuéjols, R.E.Burkard, and G.J.Woeginger, eds., Vol. 1610 of Lecture Notes in Computer Science (Springer, 1999), pp. 31-44.
    [CrossRef]
  16. A. J. Hoffman and J. B. Kruskal, “Integral boundary points of convex polyhedral,” in Linear Inequalities and Related Systems, H.W.Tucker and A.W.kuhn, eds. (Princeton Univ. Press, 1965) pp. 223-246.
  17. C. W. Chen and H. A. Zebker, “Phase unwrapping for large SAR interferograms: statistical segmentation and generalized network models,” IEEE Trans. Geosci. Remote Sens. 40, 1709-1719 (2002).
    [CrossRef]
  18. G. Zhou and M. Gen, “Genetic algorithm approach on multi-criteria minimum spanning tree problem,” Eur. J. Oper. Res. 114141-152 (1997).
    [CrossRef]
  19. J. D. Knowles and D. W. Corne, “A comparison of encodings and algorithms for multiobjective minimum spanning tree problems,” in Proceedings of the 2001 Congress on Evolutionary Computation, 2001 (IEEE, 2001) Vol. 1, pp. 544-551.
  20. I. Ryder and R. Burgmann, “Spatial variations in slip deficit on the Central San Andreas Fault from InSAR,” Geophys. J. Int. 175, 837-852 (2008).
    [CrossRef]
  21. P. Shanker and H. Zebker, “Persistent scatterer selection using maximum likelihood estimation,” Geophys. Res. Lett. 34, L22301 (2007).
    [CrossRef]
  22. C. Colesanti, A. Ferretti, F. Novali, C. Prati, and F. Rocca, “SAR monitoring of progressive and seasonal ground deformation using the permanent scatterers technique,” IEEE Trans. Geosci. Remote Sens. 41, 1685-1701 (2003).
    [CrossRef]
  23. A. Pepe and R. Lanari, “On the extension of minimum cost flow algorithm for phase unwrapping of multitemporal differential SAR interferograms,” IEEE Trans. Geosci. Remote Sens. 44, 2374-2383 (2006).
    [CrossRef]
  24. F. Rolandone, R. Bürgmann, D. C. Agnew, I. A. Johanson, D. C. Templeton, M. A. d'Alessio, S. J. Titus, C. DeMets, and B. Tikoff, “Aseismic slip and fault-normal strain along the creeping segment of the San Andreas fault,” Geophys. Res. Lett. 35, L034437 (2007).
  25. R. M. Nadeau and T. V. McEvilly, “Periodic pulsing of characteristic micro earthquakes on San Andreas Fault,” Science 303, 220-222 (2004).
    [CrossRef] [PubMed]
  26. CPLEX, “Using the CPLEX callable library—version 10.0,” (CPLEX Optimization, Inc., 2006).
  27. M. Costantini, M. Costantini, F. Malvarosa, and F. Minati, “A general formulation for robust integration of finite differences and phase unwrapping on sparse multidimensional domains,” presented at ESA FRINGE 2009 Workshop, Frascati, Italy, Nov. 30-Dec. 4, 2009.
  28. A. F. Veinott and G. B. Dantzig, “Integral extreme points,” SIAM Rev. 10, 371-372 (1968).
    [CrossRef]

2008 (1)

I. Ryder and R. Burgmann, “Spatial variations in slip deficit on the Central San Andreas Fault from InSAR,” Geophys. J. Int. 175, 837-852 (2008).
[CrossRef]

2007 (3)

P. Shanker and H. Zebker, “Persistent scatterer selection using maximum likelihood estimation,” Geophys. Res. Lett. 34, L22301 (2007).
[CrossRef]

A. Hooper and H. Zebker, “Phase unwrapping three dimensions, with applications to InSAR time series,” J. Opt. Soc. Am. A 24, 2737-2747 (2007).
[CrossRef]

F. Rolandone, R. Bürgmann, D. C. Agnew, I. A. Johanson, D. C. Templeton, M. A. d'Alessio, S. J. Titus, C. DeMets, and B. Tikoff, “Aseismic slip and fault-normal strain along the creeping segment of the San Andreas fault,” Geophys. Res. Lett. 35, L034437 (2007).

2006 (1)

A. Pepe and R. Lanari, “On the extension of minimum cost flow algorithm for phase unwrapping of multitemporal differential SAR interferograms,” IEEE Trans. Geosci. Remote Sens. 44, 2374-2383 (2006).
[CrossRef]

2004 (1)

R. M. Nadeau and T. V. McEvilly, “Periodic pulsing of characteristic micro earthquakes on San Andreas Fault,” Science 303, 220-222 (2004).
[CrossRef] [PubMed]

2003 (1)

C. Colesanti, A. Ferretti, F. Novali, C. Prati, and F. Rocca, “SAR monitoring of progressive and seasonal ground deformation using the permanent scatterers technique,” IEEE Trans. Geosci. Remote Sens. 41, 1685-1701 (2003).
[CrossRef]

2002 (1)

C. W. Chen and H. A. Zebker, “Phase unwrapping for large SAR interferograms: statistical segmentation and generalized network models,” IEEE Trans. Geosci. Remote Sens. 40, 1709-1719 (2002).
[CrossRef]

2001 (1)

2000 (1)

1998 (2)

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

H. A. Zebker and 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]

1997 (2)

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

G. Zhou and M. Gen, “Genetic algorithm approach on multi-criteria minimum spanning tree problem,” Eur. J. Oper. Res. 114141-152 (1997).
[CrossRef]

1996 (2)

D. C. Ghiglia and L. A. Romero, “Minimum Lp-norm two-dimensional phase unwrapping,” J. Opt. Soc. Am. A 13, 1999-2013 (1996).
[CrossRef]

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

1994 (1)

1992 (1)

N. H. Ching, D. Rosenfeld, and M. Braun, “Two-dimensional phase unwrapping using a minimum spanning tree algorithm,” IEEE Trans. Image Process. 1, 355-365 (1992).
[CrossRef] [PubMed]

1988 (1)

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

1979 (1)

1968 (1)

A. F. Veinott and G. B. Dantzig, “Integral extreme points,” SIAM Rev. 10, 371-372 (1968).
[CrossRef]

Agnew, D. C.

F. Rolandone, R. Bürgmann, D. C. Agnew, I. A. Johanson, D. C. Templeton, M. A. d'Alessio, S. J. Titus, C. DeMets, and B. Tikoff, “Aseismic slip and fault-normal strain along the creeping segment of the San Andreas fault,” Geophys. Res. Lett. 35, L034437 (2007).

Ahuja, R. K.

R. K. Ahuja, D. S. Hochbaum, and J. B. Orlin, “Solving the convex cost integer dual network flow problem,” in Integer Programming and Combinatorial Optimization, G.Cornuéjols, R.E.Burkard, and G.J.Woeginger, eds., Vol. 1610 of Lecture Notes in Computer Science (Springer, 1999), pp. 31-44.
[CrossRef]

Barber, C.

C. Barber and H. Hudanpaa, Qhull, http://www.qhull. org.

Braun, M.

N. H. Ching, D. Rosenfeld, and M. Braun, “Two-dimensional phase unwrapping using a minimum spanning tree algorithm,” IEEE Trans. Image Process. 1, 355-365 (1992).
[CrossRef] [PubMed]

Burgmann, R.

I. Ryder and R. Burgmann, “Spatial variations in slip deficit on the Central San Andreas Fault from InSAR,” Geophys. J. Int. 175, 837-852 (2008).
[CrossRef]

Bürgmann, R.

F. Rolandone, R. Bürgmann, D. C. Agnew, I. A. Johanson, D. C. Templeton, M. A. d'Alessio, S. J. Titus, C. DeMets, and B. Tikoff, “Aseismic slip and fault-normal strain along the creeping segment of the San Andreas fault,” Geophys. Res. Lett. 35, L034437 (2007).

Chen, C. W.

Ching, N. H.

N. H. Ching, D. Rosenfeld, and M. Braun, “Two-dimensional phase unwrapping using a minimum spanning tree algorithm,” IEEE Trans. Image Process. 1, 355-365 (1992).
[CrossRef] [PubMed]

Colesanti, C.

C. Colesanti, A. Ferretti, F. Novali, C. Prati, and F. Rocca, “SAR monitoring of progressive and seasonal ground deformation using the permanent scatterers technique,” IEEE Trans. Geosci. Remote Sens. 41, 1685-1701 (2003).
[CrossRef]

Corne, D. W.

J. D. Knowles and D. W. Corne, “A comparison of encodings and algorithms for multiobjective minimum spanning tree problems,” in Proceedings of the 2001 Congress on Evolutionary Computation, 2001 (IEEE, 2001) Vol. 1, pp. 544-551.

Costantini, M.

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

M. Costantini and P. A. Rosen, “A generalized phase unwrapping approach for sparse data,” in IEEE 1999 International Geoscience and Remote Sensing Symposium, 1999, IGARSS'99 (IEEE, 1999), Vol. 1, pp. 267-269.
[CrossRef]

M. Costantini, M. Costantini, F. Malvarosa, and F. Minati, “A general formulation for robust integration of finite differences and phase unwrapping on sparse multidimensional domains,” presented at ESA FRINGE 2009 Workshop, Frascati, Italy, Nov. 30-Dec. 4, 2009.

M. Costantini, M. Costantini, F. Malvarosa, and F. Minati, “A general formulation for robust integration of finite differences and phase unwrapping on sparse multidimensional domains,” presented at ESA FRINGE 2009 Workshop, Frascati, Italy, Nov. 30-Dec. 4, 2009.

d'Alessio, M. A.

F. Rolandone, R. Bürgmann, D. C. Agnew, I. A. Johanson, D. C. Templeton, M. A. d'Alessio, S. J. Titus, C. DeMets, and B. Tikoff, “Aseismic slip and fault-normal strain along the creeping segment of the San Andreas fault,” Geophys. Res. Lett. 35, L034437 (2007).

Dantzig, G. B.

A. F. Veinott and G. B. Dantzig, “Integral extreme points,” SIAM Rev. 10, 371-372 (1968).
[CrossRef]

DeMets, C.

F. Rolandone, R. Bürgmann, D. C. Agnew, I. A. Johanson, D. C. Templeton, M. A. d'Alessio, S. J. Titus, C. DeMets, and B. Tikoff, “Aseismic slip and fault-normal strain along the creeping segment of the San Andreas fault,” Geophys. Res. Lett. 35, L034437 (2007).

Ferretti, A.

C. Colesanti, A. Ferretti, F. Novali, C. Prati, and F. Rocca, “SAR monitoring of progressive and seasonal ground deformation using the permanent scatterers technique,” IEEE Trans. Geosci. Remote Sens. 41, 1685-1701 (2003).
[CrossRef]

Flynn, T. J.

Gen, M.

G. Zhou and M. Gen, “Genetic algorithm approach on multi-criteria minimum spanning tree problem,” Eur. J. Oper. Res. 114141-152 (1997).
[CrossRef]

Ghiglia, D. C.

Goldstein, R. M.

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

Hochbaum, D. S.

R. K. Ahuja, D. S. Hochbaum, and J. B. Orlin, “Solving the convex cost integer dual network flow problem,” in Integer Programming and Combinatorial Optimization, G.Cornuéjols, R.E.Burkard, and G.J.Woeginger, eds., Vol. 1610 of Lecture Notes in Computer Science (Springer, 1999), pp. 31-44.
[CrossRef]

Hoffman, A. J.

A. J. Hoffman and J. B. Kruskal, “Integral boundary points of convex polyhedral,” in Linear Inequalities and Related Systems, H.W.Tucker and A.W.kuhn, eds. (Princeton Univ. Press, 1965) pp. 223-246.

Hooper, A.

Hudanpaa, H.

C. Barber and H. Hudanpaa, Qhull, http://www.qhull. org.

Hunt, B. R.

Johanson, I. A.

F. Rolandone, R. Bürgmann, D. C. Agnew, I. A. Johanson, D. C. Templeton, M. A. d'Alessio, S. J. Titus, C. DeMets, and B. Tikoff, “Aseismic slip and fault-normal strain along the creeping segment of the San Andreas fault,” Geophys. Res. Lett. 35, L034437 (2007).

Knowles, J. D.

J. D. Knowles and D. W. Corne, “A comparison of encodings and algorithms for multiobjective minimum spanning tree problems,” in Proceedings of the 2001 Congress on Evolutionary Computation, 2001 (IEEE, 2001) Vol. 1, pp. 544-551.

Kruskal, J. B.

A. J. Hoffman and J. B. Kruskal, “Integral boundary points of convex polyhedral,” in Linear Inequalities and Related Systems, H.W.Tucker and A.W.kuhn, eds. (Princeton Univ. Press, 1965) pp. 223-246.

Lanari, R.

A. Pepe and R. Lanari, “On the extension of minimum cost flow algorithm for phase unwrapping of multitemporal differential SAR interferograms,” IEEE Trans. Geosci. Remote Sens. 44, 2374-2383 (2006).
[CrossRef]

Lu, Y.

Malvarosa, F.

M. Costantini, M. Costantini, F. Malvarosa, and F. Minati, “A general formulation for robust integration of finite differences and phase unwrapping on sparse multidimensional domains,” presented at ESA FRINGE 2009 Workshop, Frascati, Italy, Nov. 30-Dec. 4, 2009.

McEvilly, T. V.

R. M. Nadeau and T. V. McEvilly, “Periodic pulsing of characteristic micro earthquakes on San Andreas Fault,” Science 303, 220-222 (2004).
[CrossRef] [PubMed]

Minati, F.

M. Costantini, M. Costantini, F. Malvarosa, and F. Minati, “A general formulation for robust integration of finite differences and phase unwrapping on sparse multidimensional domains,” presented at ESA FRINGE 2009 Workshop, Frascati, Italy, Nov. 30-Dec. 4, 2009.

Nadeau, R. M.

R. M. Nadeau and T. V. McEvilly, “Periodic pulsing of characteristic micro earthquakes on San Andreas Fault,” Science 303, 220-222 (2004).
[CrossRef] [PubMed]

Novali, F.

C. Colesanti, A. Ferretti, F. Novali, C. Prati, and F. Rocca, “SAR monitoring of progressive and seasonal ground deformation using the permanent scatterers technique,” IEEE Trans. Geosci. Remote Sens. 41, 1685-1701 (2003).
[CrossRef]

Orlin, J. B.

R. K. Ahuja, D. S. Hochbaum, and J. B. Orlin, “Solving the convex cost integer dual network flow problem,” in Integer Programming and Combinatorial Optimization, G.Cornuéjols, R.E.Burkard, and G.J.Woeginger, eds., Vol. 1610 of Lecture Notes in Computer Science (Springer, 1999), pp. 31-44.
[CrossRef]

Pepe, A.

A. Pepe and R. Lanari, “On the extension of minimum cost flow algorithm for phase unwrapping of multitemporal differential SAR interferograms,” IEEE Trans. Geosci. Remote Sens. 44, 2374-2383 (2006).
[CrossRef]

Prati, C.

C. Colesanti, A. Ferretti, F. Novali, C. Prati, and F. Rocca, “SAR monitoring of progressive and seasonal ground deformation using the permanent scatterers technique,” IEEE Trans. Geosci. Remote Sens. 41, 1685-1701 (2003).
[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]

Rocca, F.

C. Colesanti, A. Ferretti, F. Novali, C. Prati, and F. Rocca, “SAR monitoring of progressive and seasonal ground deformation using the permanent scatterers technique,” IEEE Trans. Geosci. Remote Sens. 41, 1685-1701 (2003).
[CrossRef]

Rolandone, F.

F. Rolandone, R. Bürgmann, D. C. Agnew, I. A. Johanson, D. C. Templeton, M. A. d'Alessio, S. J. Titus, C. DeMets, and B. Tikoff, “Aseismic slip and fault-normal strain along the creeping segment of the San Andreas fault,” Geophys. Res. Lett. 35, L034437 (2007).

Romero, L. A.

Rosen, P. A.

M. Costantini and P. A. Rosen, “A generalized phase unwrapping approach for sparse data,” in IEEE 1999 International Geoscience and Remote Sensing Symposium, 1999, IGARSS'99 (IEEE, 1999), Vol. 1, pp. 267-269.
[CrossRef]

Rosenfeld, D.

N. H. Ching, D. Rosenfeld, and M. Braun, “Two-dimensional phase unwrapping using a minimum spanning tree algorithm,” IEEE Trans. Image Process. 1, 355-365 (1992).
[CrossRef] [PubMed]

Ryder, I.

I. Ryder and R. Burgmann, “Spatial variations in slip deficit on the Central San Andreas Fault from InSAR,” Geophys. J. Int. 175, 837-852 (2008).
[CrossRef]

Shanker, P.

P. Shanker and H. Zebker, “Persistent scatterer selection using maximum likelihood estimation,” Geophys. Res. Lett. 34, L22301 (2007).
[CrossRef]

Templeton, D. C.

F. Rolandone, R. Bürgmann, D. C. Agnew, I. A. Johanson, D. C. Templeton, M. A. d'Alessio, S. J. Titus, C. DeMets, and B. Tikoff, “Aseismic slip and fault-normal strain along the creeping segment of the San Andreas fault,” Geophys. Res. Lett. 35, L034437 (2007).

Tikoff, B.

F. Rolandone, R. Bürgmann, D. C. Agnew, I. A. Johanson, D. C. Templeton, M. A. d'Alessio, S. J. Titus, C. DeMets, and B. Tikoff, “Aseismic slip and fault-normal strain along the creeping segment of the San Andreas fault,” Geophys. Res. Lett. 35, L034437 (2007).

Titus, S. J.

F. Rolandone, R. Bürgmann, D. C. Agnew, I. A. Johanson, D. C. Templeton, M. A. d'Alessio, S. J. Titus, C. DeMets, and B. Tikoff, “Aseismic slip and fault-normal strain along the creeping segment of the San Andreas fault,” Geophys. Res. Lett. 35, L034437 (2007).

Veinott, A. F.

A. F. Veinott and G. B. Dantzig, “Integral extreme points,” SIAM Rev. 10, 371-372 (1968).
[CrossRef]

Werner, C. L.

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

Zebker, H.

A. Hooper and H. Zebker, “Phase unwrapping three dimensions, with applications to InSAR time series,” J. Opt. Soc. Am. A 24, 2737-2747 (2007).
[CrossRef]

P. Shanker and H. Zebker, “Persistent scatterer selection using maximum likelihood estimation,” Geophys. Res. Lett. 34, L22301 (2007).
[CrossRef]

Zebker, H. A.

Zhou, G.

G. Zhou and M. Gen, “Genetic algorithm approach on multi-criteria minimum spanning tree problem,” Eur. J. Oper. Res. 114141-152 (1997).
[CrossRef]

Eur. J. Oper. Res. (1)

G. Zhou and M. Gen, “Genetic algorithm approach on multi-criteria minimum spanning tree problem,” Eur. J. Oper. Res. 114141-152 (1997).
[CrossRef]

Geophys. J. Int. (1)

I. Ryder and R. Burgmann, “Spatial variations in slip deficit on the Central San Andreas Fault from InSAR,” Geophys. J. Int. 175, 837-852 (2008).
[CrossRef]

Geophys. Res. Lett. (2)

P. Shanker and H. Zebker, “Persistent scatterer selection using maximum likelihood estimation,” Geophys. Res. Lett. 34, L22301 (2007).
[CrossRef]

F. Rolandone, R. Bürgmann, D. C. Agnew, I. A. Johanson, D. C. Templeton, M. A. d'Alessio, S. J. Titus, C. DeMets, and B. Tikoff, “Aseismic slip and fault-normal strain along the creeping segment of the San Andreas fault,” Geophys. Res. Lett. 35, L034437 (2007).

IEEE Trans. Geosci. Remote Sens. (5)

C. Colesanti, A. Ferretti, F. Novali, C. Prati, and F. Rocca, “SAR monitoring of progressive and seasonal ground deformation using the permanent scatterers technique,” IEEE Trans. Geosci. Remote Sens. 41, 1685-1701 (2003).
[CrossRef]

A. Pepe and R. Lanari, “On the extension of minimum cost flow algorithm for phase unwrapping of multitemporal differential SAR interferograms,” IEEE Trans. Geosci. Remote Sens. 44, 2374-2383 (2006).
[CrossRef]

C. W. Chen and H. A. Zebker, “Phase unwrapping for large SAR interferograms: statistical segmentation and generalized network models,” IEEE Trans. Geosci. Remote Sens. 40, 1709-1719 (2002).
[CrossRef]

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

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

IEEE Trans. Image Process. (1)

N. H. Ching, D. Rosenfeld, and M. Braun, “Two-dimensional phase unwrapping using a minimum spanning tree algorithm,” IEEE Trans. Image Process. 1, 355-365 (1992).
[CrossRef] [PubMed]

J. Opt. Soc. Am. (1)

J. Opt. Soc. Am. A (7)

Radio Sci. (1)

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

Science (1)

R. M. Nadeau and T. V. McEvilly, “Periodic pulsing of characteristic micro earthquakes on San Andreas Fault,” Science 303, 220-222 (2004).
[CrossRef] [PubMed]

SIAM Rev. (1)

A. F. Veinott and G. B. Dantzig, “Integral extreme points,” SIAM Rev. 10, 371-372 (1968).
[CrossRef]

Other (7)

CPLEX, “Using the CPLEX callable library—version 10.0,” (CPLEX Optimization, Inc., 2006).

M. Costantini, M. Costantini, F. Malvarosa, and F. Minati, “A general formulation for robust integration of finite differences and phase unwrapping on sparse multidimensional domains,” presented at ESA FRINGE 2009 Workshop, Frascati, Italy, Nov. 30-Dec. 4, 2009.

R. K. Ahuja, D. S. Hochbaum, and J. B. Orlin, “Solving the convex cost integer dual network flow problem,” in Integer Programming and Combinatorial Optimization, G.Cornuéjols, R.E.Burkard, and G.J.Woeginger, eds., Vol. 1610 of Lecture Notes in Computer Science (Springer, 1999), pp. 31-44.
[CrossRef]

A. J. Hoffman and J. B. Kruskal, “Integral boundary points of convex polyhedral,” in Linear Inequalities and Related Systems, H.W.Tucker and A.W.kuhn, eds. (Princeton Univ. Press, 1965) pp. 223-246.

J. D. Knowles and D. W. Corne, “A comparison of encodings and algorithms for multiobjective minimum spanning tree problems,” in Proceedings of the 2001 Congress on Evolutionary Computation, 2001 (IEEE, 2001) Vol. 1, pp. 544-551.

M. Costantini and P. A. Rosen, “A generalized phase unwrapping approach for sparse data,” in IEEE 1999 International Geoscience and Remote Sensing Symposium, 1999, IGARSS'99 (IEEE, 1999), Vol. 1, pp. 267-269.
[CrossRef]

C. Barber and H. Hudanpaa, Qhull, http://www.qhull. org.

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 (8)

Fig. 1
Fig. 1

Comparison of the edgelist formulation and the original MCF formulation. We obtain the constraints of the MCF formulation by summing up constraints of the edgelist formulation.

Fig. 2
Fig. 2

Example 3 × 3 grid with pixel index and the corresponding wrapped phase values shown in ( i , ψ i ) format. The corresponding edgelist constraints are also shown. The optimal solution corresponds to variable n 5 being set to one and all flow variables ( P i j and Q i j ) being set to zero.

Fig. 3
Fig. 3

We illustrate the ability to incorporate GPS observations by using a regularly sampled 2D data grid and two GPS stations labeled “P” and “Q.” With the original MCF formulation (left), a constraint (as shown in the image) corresponding to any path of integration (dotted lines) joining the GPS stations along the edges of the grid can be used to constrain the solution. In the edgelist formulation (right), a constraint similar to Eq. (4) corresponding to a new edge (dotted curve) that directly connects the GPS stations can be used to constrain the solution. It should be noted that the TUM property of the constraint matrix is conserved in case of the edgelist formulation only.

Fig. 4
Fig. 4

Map showing the location of the 40 km × 40 km area (square) being analyzed by using PS-InSAR. Fault traces for the Central San Andreas Fault and Calaveras Fault are also shown in black. Locations of the Melendy Ranch and Slack Canyon creepmeters are also shown.

Fig. 5
Fig. 5

Left, average LOS displacement rate image estimated by using the edgelist phase unwrapping algorithm. The fault trace and the area used for computing the average profile are also indicated. Right, average LOS displacement rate (open circles, red online) as a function of distance from the fault. Assuming that all the displacement was purely due to strike slip motion across the fault, we estimate a slip rate of 22 mm yr .

Fig. 6
Fig. 6

Left, skeletal framework on which the PS-InSAR data set is unwrapped. Each slice represents an interferogram in the PS-InSAR time series. All the node potentials in areas marked by gray are set to zero. The plane of the fault trace is also shown. Right, the cost of the edges cutting across the fault is subsidized as a distance of center of edge from the fault as shown.

Fig. 7
Fig. 7

Average LOS displacement rate in millmeters per year estimated by using the stepwise 3D unwrapping algorithm [10] shown on a geolocated latitude–longitude grid.

Fig. 8
Fig. 8

Cumulative displacement time series for the regions marked out in Fig. 5a. The time series from the creepmeters at Melendy ranch (solid curve) and Slack canyon (dotted curve) are also included for comparison. The creepmeter measurements have been projected onto the radar LOS direction for comparison.

Tables (1)

Tables Icon

Table 1 Parameters Needed To Represent a Regular Grid 2D Unwrapping Problem of Size p × q Pixels by Using Edgelist and MCF Formulations

Equations (19)

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

ϕ i = ψ i + 2 π n i , where i ( 1 , , N )
n j n i + K i j = [ ψ i ψ j 2 π ] , where ( i , j ) E .
( i , j ) E f ( K i j )
n j n i + K i j = [ ψ i ψ j 2 π ] for all ( i , j ) E ,
n i integer , i ( 1 , , N ) ,
K i j integer , ( i , j ) E .
K i j = P i j Q i j for all ( i , j ) E .
( i , j ) E C i j ( P i j + Q i j )
n j n i + P i j Q i j = [ ψ i ψ j 2 π ] for all ( i , j ) E ,
P i j , Q i j 0 and real for all ( i , j ) E ,
n i real , i ( 1 , , N ) .
P i j = ( [ ψ i ψ j 2 π ] > 0 ) , Q i j = ( [ ψ i ψ j 2 π ] < 0 ) .
n p n q = Δ N p , q [ ψ p ψ q 2 π ] ,
0 P i j u for all ( i , j ) E ,
0 Q i j u for all ( i , j ) E ,
{ x R n : A x b } .
[ G n | I ] [ n K ] = b ,
[ A A ] [ n K ] [ b b ] .
P Q K i j = Δ N p , q P Q [ ψ i ψ j 2 π ] ,

Metrics