Abstract

Phase unwrapping represents a crucial step in processing phase data obtained with techniques such as synthetic aperture radar interferometry, speckle interferometry, and magnetic resonance imaging. The so-called branch-cut approaches form an important class of phase unwrapping algorithms. In 1996, Costantini proposed to transform the problem of correctly placing branch cuts into a minimum cost flow problem [Proceedings of the Fringe ‘96 Workshop (European Space Agency, Munich, 1996), pp. 261–272]. The critical point of this new approach is to generate cost functions that have to represent all the a priori knowledge necessary for phase unwrapping. Any function transforming a priori knowledge into a cost function is called a cost generator. Several types of algorithms ranging from heuristic approaches to generators based on probability-theory interpretations were suggested. A problem arising from the growing diversity of algorithms is to find a criterion for the equivalence of different cost generators. Two cost generators are equivalent if they produce cost functions with the same minimal flow for every residue configuration on every image with all possible a priori knowledge. Comparing the results of different cost generators on test scenes can show only their nonequivalence. We solve this problem by proving the following mathematical classification theorem: Two cost generators are equivalent if and only if one can be transformed into the other by multiplication by a fixed constant.

© 2002 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. G. Fornaro, G. Franceschetti, R. Lanari, E. Sansosti, “Robust phase-unwrapping techniques: a comparison,” J. Opt. Soc. Am. A 13, 2355–2366 (1996).
    [CrossRef]
  2. 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]
  3. D. Ghilia, M. Pritt, Two-Dimensional Phase Unwrapping: Theory, Algorithms and Software (Wiley, New York, 1998).
  4. R. Ahuja, T. Magnanti, J. Orlin, Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, Englewood Cliffs, N.J., 1993).
  5. M. Costantini, “A phase unwrapping method based on network programming,” Proceedings of the Fringe ’96 Workshop ERS SAR Interferometry, Zurich, Switzerland (European Space Agency, Munich, 1996), SP-406, pp. 261–272.
  6. M. Costantini, “A novel phase unwrapping method based on network programming,” IEEE Trans. Geosci. Remote Sens. 36, 813–821 (1998).
    [CrossRef]
  7. R. Bamler, P. Hartl, “Synthetic aperture radar interferometry,” Inverse Probl. 14, R1–R54 (1998).
    [CrossRef]
  8. R. Bamler, N. Adam, G. Davidson, D. Just, “Noise-induced slope distortion in 2-D phase unwrapping by linear estimators with application to SAR Interferometry,” IEEE Trans. Geosci. Remote Sens. 36, 913–921 (1998).
    [CrossRef]
  9. M. Eineder, M. Hubig, B. Milcke, “Unwrapping large interferograms using the minimum cost flow algorithm,” in Proceedings of the International Geoscience and Remote Sensing Society, T. Stein, ed. (IEEE Press, Piscataway, N.J., 1998), pp. 83–87.
  10. A. Refice, G. Satelino, S. Stramaglia, M. T. Chiaradia, N. Veneziani, “Weights determination for minimum cost flow InSAR phase unwrapping,” in Proceedings of the International Geoscience and Remote Sensing Society, T. Stein, ed. (IEEE Press, Piscataway, N.J., 1999), Vol. II, pp. 1342–1344.
  11. G. F. Carballo, P. W. Fieguth, “Probabilistic cost functions for network flow phase unwrapping,” in Proceedings of the International Science and Remote Sensing Society, T. Stein, ed. (IEEE Press, Piscataway, N.J., 1999), Vol. III, pp. 1531–1533.
  12. C. W. Chen, 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]

2000 (1)

1998 (4)

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

R. Bamler, P. Hartl, “Synthetic aperture radar interferometry,” Inverse Probl. 14, R1–R54 (1998).
[CrossRef]

R. Bamler, N. Adam, G. Davidson, D. Just, “Noise-induced slope distortion in 2-D phase unwrapping by linear estimators with application to SAR Interferometry,” IEEE Trans. Geosci. Remote Sens. 36, 913–921 (1998).
[CrossRef]

1996 (1)

Adam, N.

R. Bamler, N. Adam, G. Davidson, D. Just, “Noise-induced slope distortion in 2-D phase unwrapping by linear estimators with application to SAR Interferometry,” IEEE Trans. Geosci. Remote Sens. 36, 913–921 (1998).
[CrossRef]

Ahuja, R.

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

Bamler, R.

R. Bamler, P. Hartl, “Synthetic aperture radar interferometry,” Inverse Probl. 14, R1–R54 (1998).
[CrossRef]

R. Bamler, N. Adam, G. Davidson, D. Just, “Noise-induced slope distortion in 2-D phase unwrapping by linear estimators with application to SAR Interferometry,” IEEE Trans. Geosci. Remote Sens. 36, 913–921 (1998).
[CrossRef]

Carballo, G. F.

G. F. Carballo, P. W. Fieguth, “Probabilistic cost functions for network flow phase unwrapping,” in Proceedings of the International Science and Remote Sensing Society, T. Stein, ed. (IEEE Press, Piscataway, N.J., 1999), Vol. III, pp. 1531–1533.

Chen, C. W.

Chiaradia, M. T.

A. Refice, G. Satelino, S. Stramaglia, M. T. Chiaradia, N. Veneziani, “Weights determination for minimum cost flow InSAR phase unwrapping,” in Proceedings of the International Geoscience and Remote Sensing Society, T. Stein, ed. (IEEE Press, Piscataway, N.J., 1999), Vol. II, pp. 1342–1344.

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, “A phase unwrapping method based on network programming,” Proceedings of the Fringe ’96 Workshop ERS SAR Interferometry, Zurich, Switzerland (European Space Agency, Munich, 1996), SP-406, pp. 261–272.

Davidson, G.

R. Bamler, N. Adam, G. Davidson, D. Just, “Noise-induced slope distortion in 2-D phase unwrapping by linear estimators with application to SAR Interferometry,” IEEE Trans. Geosci. Remote Sens. 36, 913–921 (1998).
[CrossRef]

Eineder, M.

M. Eineder, M. Hubig, B. Milcke, “Unwrapping large interferograms using the minimum cost flow algorithm,” in Proceedings of the International Geoscience and Remote Sensing Society, T. Stein, ed. (IEEE Press, Piscataway, N.J., 1998), pp. 83–87.

Fieguth, P. W.

G. F. Carballo, P. W. Fieguth, “Probabilistic cost functions for network flow phase unwrapping,” in Proceedings of the International Science and Remote Sensing Society, T. Stein, ed. (IEEE Press, Piscataway, N.J., 1999), Vol. III, pp. 1531–1533.

Fornaro, G.

Franceschetti, G.

Ghilia, D.

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

Hartl, P.

R. Bamler, P. Hartl, “Synthetic aperture radar interferometry,” Inverse Probl. 14, R1–R54 (1998).
[CrossRef]

Hubig, M.

M. Eineder, M. Hubig, B. Milcke, “Unwrapping large interferograms using the minimum cost flow algorithm,” in Proceedings of the International Geoscience and Remote Sensing Society, T. Stein, ed. (IEEE Press, Piscataway, N.J., 1998), pp. 83–87.

Just, D.

R. Bamler, N. Adam, G. Davidson, D. Just, “Noise-induced slope distortion in 2-D phase unwrapping by linear estimators with application to SAR Interferometry,” IEEE Trans. Geosci. Remote Sens. 36, 913–921 (1998).
[CrossRef]

Lanari, R.

Lu, Y.

Magnanti, T.

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

Milcke, B.

M. Eineder, M. Hubig, B. Milcke, “Unwrapping large interferograms using the minimum cost flow algorithm,” in Proceedings of the International Geoscience and Remote Sensing Society, T. Stein, ed. (IEEE Press, Piscataway, N.J., 1998), pp. 83–87.

Orlin, J.

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

Pritt, M.

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

Refice, A.

A. Refice, G. Satelino, S. Stramaglia, M. T. Chiaradia, N. Veneziani, “Weights determination for minimum cost flow InSAR phase unwrapping,” in Proceedings of the International Geoscience and Remote Sensing Society, T. Stein, ed. (IEEE Press, Piscataway, N.J., 1999), Vol. II, pp. 1342–1344.

Sansosti, E.

Satelino, G.

A. Refice, G. Satelino, S. Stramaglia, M. T. Chiaradia, N. Veneziani, “Weights determination for minimum cost flow InSAR phase unwrapping,” in Proceedings of the International Geoscience and Remote Sensing Society, T. Stein, ed. (IEEE Press, Piscataway, N.J., 1999), Vol. II, pp. 1342–1344.

Stramaglia, S.

A. Refice, G. Satelino, S. Stramaglia, M. T. Chiaradia, N. Veneziani, “Weights determination for minimum cost flow InSAR phase unwrapping,” in Proceedings of the International Geoscience and Remote Sensing Society, T. Stein, ed. (IEEE Press, Piscataway, N.J., 1999), Vol. II, pp. 1342–1344.

Veneziani, N.

A. Refice, G. Satelino, S. Stramaglia, M. T. Chiaradia, N. Veneziani, “Weights determination for minimum cost flow InSAR phase unwrapping,” in Proceedings of the International Geoscience and Remote Sensing Society, T. Stein, ed. (IEEE Press, Piscataway, N.J., 1999), Vol. II, pp. 1342–1344.

Zebker, H. A.

IEEE Trans. Geosci. Remote Sens. (2)

R. Bamler, N. Adam, G. Davidson, D. Just, “Noise-induced slope distortion in 2-D phase unwrapping by linear estimators with application to SAR Interferometry,” IEEE Trans. Geosci. Remote Sens. 36, 913–921 (1998).
[CrossRef]

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

Inverse Probl. (1)

R. Bamler, P. Hartl, “Synthetic aperture radar interferometry,” Inverse Probl. 14, R1–R54 (1998).
[CrossRef]

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

Other (6)

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

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

M. Costantini, “A phase unwrapping method based on network programming,” Proceedings of the Fringe ’96 Workshop ERS SAR Interferometry, Zurich, Switzerland (European Space Agency, Munich, 1996), SP-406, pp. 261–272.

M. Eineder, M. Hubig, B. Milcke, “Unwrapping large interferograms using the minimum cost flow algorithm,” in Proceedings of the International Geoscience and Remote Sensing Society, T. Stein, ed. (IEEE Press, Piscataway, N.J., 1998), pp. 83–87.

A. Refice, G. Satelino, S. Stramaglia, M. T. Chiaradia, N. Veneziani, “Weights determination for minimum cost flow InSAR phase unwrapping,” in Proceedings of the International Geoscience and Remote Sensing Society, T. Stein, ed. (IEEE Press, Piscataway, N.J., 1999), Vol. II, pp. 1342–1344.

G. F. Carballo, P. W. Fieguth, “Probabilistic cost functions for network flow phase unwrapping,” in Proceedings of the International Science and Remote Sensing Society, T. Stein, ed. (IEEE Press, Piscataway, N.J., 1999), Vol. III, pp. 1531–1533.

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

Fig. 1
Fig. 1

One-dimensional illustration of phase unwrapping. Left, absolute phase function; right, its wrapped phase (solid curves) and correctly unwrapped phase (dashed curve).

Fig. 2
Fig. 2

One-dimensional four-pixel problem of branch-cut application. Left, absolute phase (solid lines) and its wrapped version (dashed lines); right, unwrapped phase without branch cut (black line) and unwrapped phase with branch cut (gray line). The branch cut is located between pixels 2 and 3.

Fig. 3
Fig. 3

MCF situation: arcs a and vertices v are located in the inter pixel spaces of the phase image consisting of the wrapped phase values Ψ.

Fig. 4
Fig. 4

Phase image residuals are defined by a nonvanishing sum of wrapped phase differences ΔΨ along the circle of a four-point pixel neighborhood.

Fig. 5
Fig. 5

Pixel field with shrunken pixels (gray rectangles), potential branch cuts (dashed lines), residues (black and white rectangles) and a branch cut discharging the residues (gray line).

Fig. 6
Fig. 6

Illustration of A(v): All arcs having a particular vertex v as an end point form the set A(v). It is the disjoint union of A+(v), the set of arcs of which v is the positive end point (a, c, e, g) and A-(v), the set of arcs of which v is the negative end point (h, b, d, f).

Fig. 7
Fig. 7

Example of a residue configuration on the set of vertices v: positive residues (+1) are indicated by black circles, negative residues (-1) by white circles. The flows f (gray) discharge the residues.

Fig. 8
Fig. 8

Flows f1, f2=fi, fk and the residues +1 and -1 on the vertices v1 and v2 are constructed for the proof of the classification theorem.

Fig. 9
Fig. 9

SRTM data are used to compute cost functions. Left, amplitude of one the two SAR images used to form the interferogram; right, coherence of the interferogram. The two parts belong to the same image area and are 50 × 36 pixels in size.

Fig. 10
Fig. 10

Cost functions computed in the experiment. From top to bottom: sum of amplitude costs and coherence costs (case I), sum of amplitude costs and coherence costs multiplied with 2.0 (case II), and sum of amplitude costs multiplied by 2.0 and coherence costs multiplied by 2.0 (case III). For each case the cost functions for the images x and y direction are shown on the left and right, respectively.

Fig. 11
Fig. 11

Detail of a SRTM interferogram (50 × 36 pixels) used in the experiment overlaid with the MCF solutions for cases I–III from top to bottom. Positive and negative residues are shown in black; branch cuts are indicated in white. While the MCF solutions are identical for the cost functions of cases I and III, that of case II differs notably remarkably from the others.

Equations (46)

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

vVr(v)=0.
aA+(v)f(a)-aA-(v)f(a)=r(v)forallverticesvinV.
c[f]aAf(a)c(a).
c[f]c[g]for allginF(r).
ca=G(a, xa)forallainA.
Property(1):foralla,binA:[xa=xb  G(a, xa)=G(b, xb)].
G(xa)  ca=G(a, xa)forallainA.
F[G(x), r]=F[H(x), r].
G(xa)=sH(xa).
H(x)[f]H(x)[g]forallfinF(H(x), r))and
forallginF(r) .
aAf(a)H(xa)aAg(a)H(xa),
saAf(a)H(xa)saAg(a)H(xa).
aAf(a)(sH(xa))aAg(a)(sH(xa)),
aAf(a)G(xa)aAg(a)G(xa).
G(x)[f]G(x)[g]forallfinF(H(x), r) and
forallginF(r).
G(x)[f]G(x)[g]forallfinF(G(x), r) and
forallginF(r)
H(x)/G(x)H(y)/G(y).
H(x)/G(x)>H(y)/G(y),
H(x)/H(y)>G(x)/G(y).
H(x)/H(y)>(1+δ)G(x)/G(y).
(1+δ)>(H(x)/H(y))(n/m)>1
H(x)<H(y)  m<n,
H(y)<H(x)  n<m.
(n/m)/(1+δ)<(H(y)/H(x))
(n/m)/(1+δ)<(H(y)/H(x))<(G(y)/G(x))/(1+δ),
n/m<G(y)/G(x).
nG(x)<mG(y).
nH(x)>mH(y).
za  yiff2(a)=0,
za  xiff2(a)=1.
H(z)[g]mH(y)=H(z)[f1].
H(z)[g]mH(x)+2rH(x)=nH(x)>mH(y)=H(z)[f1].
f1 inF(H(z), r).
za  yiff1(a)=1,
za  xiff1(a)=0.
H(z)[g]nH(x)>mH(y)=H(z)[f1].
H(z)[g]nH(y)+2rH(y)=mH(y)=H(z)[f1].
f1 inF(H(z), r).
G(z)[f1]=mG(y)>nG(x)=G(z)[f2],
c=w0ac+w1cc.
caseI:w0=1.0,w1=1.0,
caseII:w0=1.0,w1=2.0,
caseIII:w0=2.0,w1=2.0

Metrics