Abstract

Phase unwrapping (PU) represents an important step in synthetic aperture radar interferometry (InSAR) and other interferometric applications. Among the different PU methods, the so called branch-cut approaches play an important role. In 1996 M. Costantini [Proceedings of the Fringe ’96 Workshop ERS SAR Interferometry (European Space Agency, Munich, 1996), pp. 261–272] proposed to transform the problem of correctly placing branch cuts into a minimum cost flow (MCF) problem. The crucial point of this new approach is to generate cost functions that represent the a priori knowledge necessary for PU. Since cost functions are derived from measured data, they are random variables. This leads to the question of MCF solution stability: How much can the cost functions be varied without changing the cheapest flow that represents the correct branch cuts?  This question is partially answered: The existence of a whole linear subspace in the space of cost functions is shown; this subspace contains all cost differences by which a cost function can be changed without changing the cost difference between any two flows that are discharging any residue configuration. These cost differences are called strictly stable cost differences. For quadrangular nonclosed networks (the most important type of MCF networks for interferometric purposes) a complete classification of strictly stable cost differences is presented. Further, the role of the well-known class of node potentials in the framework of strictly stable cost differences is investigated, and information on the vector-space structure representing the MCF environment is provided.

© 2004 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. R. Bamler, P. Hartl, “Synthetic aperture radar interferometry,” Inverse Probl. 14, R1–R54 (1998).
    [CrossRef]
  2. D. Ghilia, M. Pritt, Two-Dimensional Phase Unwrapping: Theory, Algorithms and Software (Wiley, New York, 1998).
  3. 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]
  4. M. Costantini, “A phase unwrapping method based on network programming,” Proceedings of the Fringe ’96 Workshop ERS SAR Interferometry (European Space Agency, Munich, 1996), pp. 261–272.
  5. M. Costantini, “A novel phase unwrapping method based on network programming,” IEEE Trans. Geosci. Remote Sens. 36, 813–821 (1998).
    [CrossRef]
  6. R. Ahuja, T. Magnanti, J. Orlin, Network Flows: Theory, Algorithms and Applications (Prentice Hall, Englewood Cliffs, N.J., 1993).
  7. 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.
  8. G. F. Carballo, P. W. Fieguth, “Probabilistic cost functions for network flow phase unwrapping,” in Proceedings of the International Geoscience and Remote Sensing Society, T. Stein, ed. (IEEE Press, Piscataway, N.J., 1999), Vol. III, pp. 1531–1533.
  9. C. Chen, H. 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. Refice, G. Satalino, 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. M. Hubig, S. Suchandt, N. Adam, “Equivalence of cost generators for minimum cost flow phase unwrapping,” J. Opt. Soc. Am. A 19, 64–70 (2002).
    [CrossRef]
  12. N. Jacobson, Lectures in Abstract Algebra I: Basic Concepts (Van Nostrand Reinhold, New York, 1953).
  13. N. Jacobson, Lectures in Abstract Algebra II: Linear Algebra (Van Nostrand Reinhold, New York, 1953).

2002

2000

1998

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]

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

Adam, N.

M. Hubig, S. Suchandt, N. Adam, “Equivalence of cost generators for minimum cost flow phase unwrapping,” J. Opt. Soc. Am. A 19, 64–70 (2002).
[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]

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

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

Carballo, G. F.

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

Chen, C.

Chiaradia, M. T.

A. Refice, G. Satalino, 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 (European Space Agency, Munich, 1996), 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 Geoscience and Remote Sensing Society, T. Stein, ed. (IEEE Press, Piscataway, N.J., 1999), Vol. III, pp. 1531–1533.

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. Hubig, S. Suchandt, N. Adam, “Equivalence of cost generators for minimum cost flow phase unwrapping,” J. Opt. Soc. Am. A 19, 64–70 (2002).
[CrossRef]

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.

Jacobson, N.

N. Jacobson, Lectures in Abstract Algebra I: Basic Concepts (Van Nostrand Reinhold, New York, 1953).

N. Jacobson, Lectures in Abstract Algebra II: Linear Algebra (Van Nostrand Reinhold, New York, 1953).

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]

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. Satalino, 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.

Satalino, G.

A. Refice, G. Satalino, 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. Satalino, 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.

Suchandt, S.

Veneziani, N.

A. Refice, G. Satalino, 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.

IEEE Trans. Geosci. Remote Sens.

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.

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

J. Opt. Soc. Am. A

Other

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

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

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

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.

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

A. Refice, G. Satalino, 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.

N. Jacobson, Lectures in Abstract Algebra I: Basic Concepts (Van Nostrand Reinhold, New York, 1953).

N. Jacobson, Lectures in Abstract Algebra II: Linear Algebra (Van Nostrand Reinhold, New York, 1953).

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

Fig. 1
Fig. 1

Vortices of the wrapped gradient ̲Ψ, called residues. They are positioned in the interpixel spaces of four adjacent phase values Ψ in the rectangular scheme of the image.

Fig. 2
Fig. 2

Left, every arc a connects exactly two vertices, its endpoints {a+,a-}. Right, A(v) is the disjoint union of the set A+(v) of all arcs for which v is the positive endpoint and of the set A-(v) of all arcs for which v is the negative endpoint.

Fig. 3
Fig. 3

Model problem network G=(A, V), with M1=M2=3, N=|A|=24, M=|V|=9. Vertex numbers are given in boxes, arc numbers without boxes.

Tables (3)

Tables Icon

Table 1 Flow Conservation Matrix B of the Model Problem Network G

Tables Icon

Table 2 Transformation of an Example Cost Function c of the Model Problem Network G

Tables Icon

Table 3 Cost Functions c and c Applied to Flows f1f12 in Model Problem Network G

Equations (132)

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

aA+(v)f(a)-aA-(v)f(a)=r(v) forallverticesvinV,
c[f]  aAc(a)f(a).
X:AIRN:aek ifa=Ak,
Ψ:VIRM:vek ifv=Vk.
X:FIRN:faAf(a)X(a)X(f ),
X:C*IRN:caAc(a)X(a)X(c).
Ψ:RIRM:rvVr(v)Ψ(v)Ψ(r).
c[f]=aAc(a)f(a)=X(c)|X(f ).
Bf=rforallrinRandforallfinF(r).
dim[W(B)]N-M,dim[U(B)]M.
c|g-f0forallginF(r).
F(c, r)=F(c, r).
Δc|g-f=c|g-f-c|g-f=0.
V  {(i, j)inIR2|1iM1,1jM2}.
X(i)+  {[(i, j),(i, j+1)]|1jM2-1}forall1iM1,
X(i)-  {[(i, j+1),(i, j)]|1jM2-1}forall1iM1,
Y(j)+  {[(i, j),(i+1, j)]|1iM1-1}forall1jM2,
Y(j)-  {[(i+1, j),(i, j)]|1iM1-1}forall1jM2.
A  (i=1,,M1X(i)+)(i=1,,M1X(i)-)
(i=1,,M2Y(i)+)(i=1,,M2Y(i)-).
a-  v,a+  w
V(a)  {a-, a+}.
fY(a)  1ifainY,
fY(a)  0ifanotinY.
FY  {fD|DinY}.
t=tx(i, j)  {[(i, j),(i, j+1)],[(i, j+1),(i, j)]},
t=ty(i, j)  {[(i+1, j),(i, j)],[(i, j),(i+1, j)]}.
A*+(Ω(v))=Ξ(A+(v)),
A*-(Ω(v))=Ξ(A-(v)) forallvinV,
Ω(a+)=Ξ(a)+,
Ω(a-)=Ξ(a)- forallainA.
s[p]:AIR:as[p](a)  p(a+)-p(a-).
c|f=c|f+KforallfinF(r).
{g-f| forallrinR:forallg,finF(r)}=W(B).
dimW(B)3M1M23dimU(B).
c|g-f=c+Δc|g-f=c|g-f+Δc|g-f.
c|g-f=c|g-f0.
c|f-h=c|f-hforallhinF(c, r),
c|g-h=c|g-hforallhinF(c, r).
c|g-c|f=c|g-c|fforallf,ginF(r),
c|g-c|g=c|f-c|fforallf,ginF(r).
c|g-f=c|g-c|f=c|g-K+K-c|f=(c|g-K)+(K-c|f)=(c|g-c|g+c|g)+(c|f-c|f-c|f)=c|g-f.
c|g-f=c|g-fforallrinR,forallginF(r),andforallfinF(c, r).
c-c|h=0forallhinW(B).
0=sATAMαsfs.
-sMαsfs=sTαsfs,
ft(b)=1,andforallothersinT\{t}:
fs(a)=fs(b)=0.
-sMαsfs(b)=0;
0=sTαsfs(b)=αt0.
dimH=dim W(B).
S*  {fa|ainD}with 
D  Y+(1)X+(1)X+(M1).
BS*  {rinR|r=Bfs foranysinD}.
Bfa=i=1,,nBfa2i+Bfa0+i=1,,nBfb1i=i=1,,nBfa2i+Bfa0-i=1,,nBfa1i.
0=α0Bfa0++αnBfan.
0=α0[Bfa0](v)++αn[Bfan](v)=αi[Bfai](v)=±αi0,
|S*|=|Y+(1)|+M1|X+(1)|=(M1-1)+M1(M2-1)=M1M2-1.
|BS*|=|S*|=M1M2-1.
dim Im(B)=dimBS=|BS*|=M1M2-1.
dim IRN=dim Im(B)+dim Ker(B).
dim W(B)=dim Ker(B)=dim IRN-dim Im(B)=4M1M2-2(M1+M2)-M1M2+1=3M1M2-2(M1+M2)+1.
|AT|=M1(M2-1)+M2(M1-1)=2M1M2-M1-M2,
|AM|=(M1-1)(M2-1)=M1M2-M1-M2+1,
|H|=|AT|+|AM|=3M1M2-2(M1+M2)+1.
Bft=B(g-f )=Bg-Bf=0.
Bfm=B(g-f )=Bg-Bf=0.
H{g-f|rinR; f,ginF(r)}W(B),
H{g-f|rinR; f,ginF(r)}W(B).
W(B)=H{g-f|rinR; f,ginF(r)}W(B),
dim IRN=4M1M2-2(M1+M2).
dim U(B)=dim IRN-dim W(B)=M1M2-1.
s[p]|g=p(w)-p(v).
s[p]|g=a<A(s[p](a))g(a)=aA(p(a+)-p(a-))g(a).
s[p]|g=aA(p(a+)-p(a-))g(a)=p(w)-p(v).
s[p]:AIR:as[p](a)  p(a+)-p(a-),
c  c+s[p].
c|g-c|g=c+s[p]|g-c|g=s[p]|g.
g(a)=qRPgq(a),
s[p]|g=qRPs[p]|gq=qRP(p(q+)-p(q-)).
c|g-c|g=qRP(p(q+)-p(q-)).
c|g-c|g=c|f-c|f,
c|g-f=c|g-f.
s[P]=U(B)
dim s[P]=dim P-dim Ker s=M-1.
dim U(B)=M-1.
s[p]|h=0.
s[p](a)=0forallainA.
p(a+)-p(a-)=s[p](a)=0forallainA.
p(w)-p(v)=s[p]|h=aAs[p](a)h(a)=0.
Ker s={p:VIR:vp(v)=p0|p0 inIR}.
X:AIRN:aiei foralli=1,,24,
Ψ:VIRM:vjej forallj=1,,9,
f=e1+e2+e9+e12,
g=e7+e10+e5+e6.
H̲  H1H̲2,withH1  {h1,,h12},
H̲2  {h̲13,,h̲16}.
hk  ek+e12+k,k={1,,12}.
h̲13  e1+e8+e15+e19-0.5h1-0.5h8-0.5h3-0.5h7,
h̲14  e2+e9+e16+e20-0.5h2-0.5h9-0.5h4-0.5h8,
h̲15  e4+e12+e18+e23-0.5h4-0.5h12-0.5h6-0.5h11,
h̲16  e3+e11+e17+e22-0.5h3-0.5h11-0.5h5-0.5h10.
G̲=G1G̲2 withG1={g1,,g4},
G̲2={g5,,g8},
g1  -e1-e7+e13+e19,
g2  -e2+e9+e14-e21,
g3  -e5+e10+e17-e22,
g4  +e6+e12-e18-e24,
g5  +e1-e8-e2-e13+e14+e20+0.5g1-0.5g2,
g6  -e3+e7-e10+e15-e19+e22+0.5g1+0.5g3,
g7  +e4+e9-e12-e16-e21+e24-0.5g2+0.5g4,
g8  +e5-e6+e11+e17+e18-e23+0.5g3+0.5g4.
d1  +e1-e2,d2  +e2-e3,
d3  +e4-e5,d4  +e5-e6,
d5  +e7-e8,d6  +e8-e9,
d7  +e1-e4,d8  +e4-e7.
Q(x)=+0.25e1+0.125e2+0.125e3+0.125e4+0.125e5+0.25e6+0.25e7+0.125e8+0.125e9+0.125e10+0.125e11+0.25e12-0.25e13-0.125e14-0.125e15-0.125e16-0.125e17-0.25e18-0.25e19-0.125e20-0.125e21-0.125e22-0.125e23-0.25e24.
P(x)=+0.75e1-0.125e2-0.125e3+0.875e4-0.125e5-0.25e6-0.25e7+0.875e8-0.125e9-0.125e10-0.125e11+0.75e12+0.25e13+0.125e14+0.125e15+0.125e16+0.125e17+0.25e18+0.25e19+0.125e20+0.125e21+0.125e22+0.125e23+0.25e24.
c=S-1c,c=Sc.
c=i=1,,Niei.
L:f1=e1+e2+e9+e12,
f2=e1+e2+e9+e16+e11+e18,
f3=e1+e2+e9+e16+e15+e10+e5+e6,
f4=e1+e8+e4+e12,
f5=e1+e8+e11+e6,
f6=e1+e8+e15+e10+e5+e6,
f7=e7+e10+e5+e6,
f8=e7+e10+e5+e23+e4+e12,
f9=e7+e10+e5+e23+e20+e2+e9+e12,
f10=e7+e3+e11+e6,
f11=e7+e3+e4+e12,
f12=e7+e3+e20+e2+e9+e12.

Metrics