Abstract

The branch-cut method is a powerful tool for correct unwrapping of phase maps in optical metrology. However, this method encounters the problem of the correct setting of the cuts, which belongs to the class of nondeterministic-polynomial-time-complete problems. Simulated annealing is an algorithm used to solve problems of this kind in a polynomial-time execution. However, the algorithm still requires an enormous calculation time if the number of discontinuity sources and thus the number of branch cuts is high. We illustrate the motivation for the use of this algorithm and show how the running time can be severely reduced by use of reverse simulated annealing, starting from the nearest-neighbor solution to find a proper initial configuration, and by clustering of discontinuity sources.

© 1999 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. D. C. Ghiglia, G. A. Mastin, L. A. Romero, “Cellular-automata method for phase unwrapping,” J. Opt. Soc. Am. A 4, 267–280 (1987).
    [CrossRef]
  2. M. Takeda, “Recent progress in phase unwrapping techniques,” in Optical Inspection and Micromeasurements, C. Gorecki, ed., Proc. SPIE2782, 334–343 (1996).
    [CrossRef]
  3. R. M. Goldstein, H. A. Zebker, C. L. Werner, “Satellite radar interferometry: two dimensional phase unwrapping,” Radio Sci. 23, 713–720 (1988).
    [CrossRef]
  4. J. M. Huntley, “Noise-immune phase unwrapping algorithm,” Appl. Opt. 28, 3268–3270 (1989).
    [CrossRef] [PubMed]
  5. L. D. Barr, V. Coudé du Foresto, J. Fox, G. A. Poczulp, J. Richardson, C. Roddier, F. Roddier, “Large mirror testing facility at the National Astronomy Observatories,” Opt. Eng. 30, 1405–1414 (1991).
    [CrossRef]
  6. R. Cusack, J. M. Huntley, H. T. Goldrein, “Improved noise-immune phase unwrapping algorithm,” Appl. Opt. 35, 781–789 (1995).
    [CrossRef]
  7. M. R. Garey, D. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness (Freeman, New York, 1979).
  8. 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]
  9. J. A. Quiroga, A. González-Cano, E. Bernabeu, “Stable-marriages algorithm for preprocessing phase maps with discontinuity sources,” Appl. Opt. 34, 5029–5038 (1995).
    [CrossRef] [PubMed]
  10. M. Takeda, T. Abe, “Phase unwrapping by a maximum cross-amplitude spanning tree algorithm: a comparative study,” Opt. Eng. 35, 2345–2351 (1996).
    [CrossRef]
  11. S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, “Optimization by simulated annealing,” Science 220, 671–680 (1983).
    [CrossRef] [PubMed]
  12. R. V. V. Vidal, ed., Applied Simulated Annealing (Springer-Verlag, Berlin, 1993).
    [CrossRef]
  13. E. Aarts, J. Korst, Simulated Annealing and Boltzmann Machines, Wiley-Interscience Series in Discrete Mathematics and Optimization (Wiley, Chichester, N.Y., 1989).
  14. Because there are usually some sources connected to the boundary of the measurement range, we have Nbc ≥ (N+ + N-)/2.
  15. Image used with the kind permission of Fabrice Brémand, Laboratoire de Méchaniques des Solides, Université de Poitiers, France.
  16. 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]
  17. S. Flügge, ed., Encyclopedia of Physics, Vol. IV: Principles of Electrodynamics and Relativity (Springer, Berlin, 1962).
  18. A. Dittler, B. Gutmann, R. Lichtenberger, H. Weber, G. Kasper, “Optical in situ measurement of dust cake thickness distributions on rigid filter media for gas cleaning,” Powder Technol. 99, 177–184 (1998).
    [CrossRef]
  19. Image used with the kind permission of the Department of Physics, Applied Optics, Carl von Ossietzky University, Oldenburg, Germany.

1998 (2)

A. Dittler, B. Gutmann, R. Lichtenberger, H. Weber, G. Kasper, “Optical in situ measurement of dust cake thickness distributions on rigid filter media for gas cleaning,” Powder Technol. 99, 177–184 (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]

1996 (1)

M. Takeda, T. Abe, “Phase unwrapping by a maximum cross-amplitude spanning tree algorithm: a comparative study,” Opt. Eng. 35, 2345–2351 (1996).
[CrossRef]

1995 (3)

1991 (1)

L. D. Barr, V. Coudé du Foresto, J. Fox, G. A. Poczulp, J. Richardson, C. Roddier, F. Roddier, “Large mirror testing facility at the National Astronomy Observatories,” Opt. Eng. 30, 1405–1414 (1991).
[CrossRef]

1989 (1)

1988 (1)

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

1987 (1)

1983 (1)

S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, “Optimization by simulated annealing,” Science 220, 671–680 (1983).
[CrossRef] [PubMed]

Aarts, E.

E. Aarts, J. Korst, Simulated Annealing and Boltzmann Machines, Wiley-Interscience Series in Discrete Mathematics and Optimization (Wiley, Chichester, N.Y., 1989).

Abe, T.

M. Takeda, T. Abe, “Phase unwrapping by a maximum cross-amplitude spanning tree algorithm: a comparative study,” Opt. Eng. 35, 2345–2351 (1996).
[CrossRef]

Barr, L. D.

L. D. Barr, V. Coudé du Foresto, J. Fox, G. A. Poczulp, J. Richardson, C. Roddier, F. Roddier, “Large mirror testing facility at the National Astronomy Observatories,” Opt. Eng. 30, 1405–1414 (1991).
[CrossRef]

Bernabeu, E.

Buckland, J. R.

Coudé du Foresto, V.

L. D. Barr, V. Coudé du Foresto, J. Fox, G. A. Poczulp, J. Richardson, C. Roddier, F. Roddier, “Large mirror testing facility at the National Astronomy Observatories,” Opt. Eng. 30, 1405–1414 (1991).
[CrossRef]

Cusack, R.

R. Cusack, J. M. Huntley, H. T. Goldrein, “Improved noise-immune phase unwrapping algorithm,” Appl. Opt. 35, 781–789 (1995).
[CrossRef]

Dittler, A.

A. Dittler, B. Gutmann, R. Lichtenberger, H. Weber, G. Kasper, “Optical in situ measurement of dust cake thickness distributions on rigid filter media for gas cleaning,” Powder Technol. 99, 177–184 (1998).
[CrossRef]

Fox, J.

L. D. Barr, V. Coudé du Foresto, J. Fox, G. A. Poczulp, J. Richardson, C. Roddier, F. Roddier, “Large mirror testing facility at the National Astronomy Observatories,” Opt. Eng. 30, 1405–1414 (1991).
[CrossRef]

Garey, M. R.

M. R. Garey, D. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness (Freeman, New York, 1979).

Gelatt, C. D.

S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, “Optimization by simulated annealing,” Science 220, 671–680 (1983).
[CrossRef] [PubMed]

Ghiglia, D. C.

Goldrein, H. T.

R. Cusack, J. M. Huntley, H. T. Goldrein, “Improved noise-immune phase unwrapping algorithm,” Appl. Opt. 35, 781–789 (1995).
[CrossRef]

Goldstein, R. M.

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

González-Cano, A.

Gutmann, B.

A. Dittler, B. Gutmann, R. Lichtenberger, H. Weber, G. Kasper, “Optical in situ measurement of dust cake thickness distributions on rigid filter media for gas cleaning,” Powder Technol. 99, 177–184 (1998).
[CrossRef]

Huntley, J. M.

Johnson, D.

M. R. Garey, D. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness (Freeman, New York, 1979).

Kasper, G.

A. Dittler, B. Gutmann, R. Lichtenberger, H. Weber, G. Kasper, “Optical in situ measurement of dust cake thickness distributions on rigid filter media for gas cleaning,” Powder Technol. 99, 177–184 (1998).
[CrossRef]

Kirkpatrick, S.

S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, “Optimization by simulated annealing,” Science 220, 671–680 (1983).
[CrossRef] [PubMed]

Korst, J.

E. Aarts, J. Korst, Simulated Annealing and Boltzmann Machines, Wiley-Interscience Series in Discrete Mathematics and Optimization (Wiley, Chichester, N.Y., 1989).

Lichtenberger, R.

A. Dittler, B. Gutmann, R. Lichtenberger, H. Weber, G. Kasper, “Optical in situ measurement of dust cake thickness distributions on rigid filter media for gas cleaning,” Powder Technol. 99, 177–184 (1998).
[CrossRef]

Lu, Y.

Mastin, G. A.

Poczulp, G. A.

L. D. Barr, V. Coudé du Foresto, J. Fox, G. A. Poczulp, J. Richardson, C. Roddier, F. Roddier, “Large mirror testing facility at the National Astronomy Observatories,” Opt. Eng. 30, 1405–1414 (1991).
[CrossRef]

Quiroga, J. A.

Richardson, J.

L. D. Barr, V. Coudé du Foresto, J. Fox, G. A. Poczulp, J. Richardson, C. Roddier, F. Roddier, “Large mirror testing facility at the National Astronomy Observatories,” Opt. Eng. 30, 1405–1414 (1991).
[CrossRef]

Roddier, C.

L. D. Barr, V. Coudé du Foresto, J. Fox, G. A. Poczulp, J. Richardson, C. Roddier, F. Roddier, “Large mirror testing facility at the National Astronomy Observatories,” Opt. Eng. 30, 1405–1414 (1991).
[CrossRef]

Roddier, F.

L. D. Barr, V. Coudé du Foresto, J. Fox, G. A. Poczulp, J. Richardson, C. Roddier, F. Roddier, “Large mirror testing facility at the National Astronomy Observatories,” Opt. Eng. 30, 1405–1414 (1991).
[CrossRef]

Romero, L. A.

Takeda, M.

M. Takeda, T. Abe, “Phase unwrapping by a maximum cross-amplitude spanning tree algorithm: a comparative study,” Opt. Eng. 35, 2345–2351 (1996).
[CrossRef]

M. Takeda, “Recent progress in phase unwrapping techniques,” in Optical Inspection and Micromeasurements, C. Gorecki, ed., Proc. SPIE2782, 334–343 (1996).
[CrossRef]

Turner, S. R. E.

Vecchi, M. P.

S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, “Optimization by simulated annealing,” Science 220, 671–680 (1983).
[CrossRef] [PubMed]

Weber, H.

A. Dittler, B. Gutmann, R. Lichtenberger, H. Weber, G. Kasper, “Optical in situ measurement of dust cake thickness distributions on rigid filter media for gas cleaning,” Powder Technol. 99, 177–184 (1998).
[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. 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]

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

Appl. Opt. (4)

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

Opt. Eng. (2)

L. D. Barr, V. Coudé du Foresto, J. Fox, G. A. Poczulp, J. Richardson, C. Roddier, F. Roddier, “Large mirror testing facility at the National Astronomy Observatories,” Opt. Eng. 30, 1405–1414 (1991).
[CrossRef]

M. Takeda, T. Abe, “Phase unwrapping by a maximum cross-amplitude spanning tree algorithm: a comparative study,” Opt. Eng. 35, 2345–2351 (1996).
[CrossRef]

Powder Technol. (1)

A. Dittler, B. Gutmann, R. Lichtenberger, H. Weber, G. Kasper, “Optical in situ measurement of dust cake thickness distributions on rigid filter media for gas cleaning,” Powder Technol. 99, 177–184 (1998).
[CrossRef]

Radio Sci. (1)

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

Science (1)

S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, “Optimization by simulated annealing,” Science 220, 671–680 (1983).
[CrossRef] [PubMed]

Other (8)

R. V. V. Vidal, ed., Applied Simulated Annealing (Springer-Verlag, Berlin, 1993).
[CrossRef]

E. Aarts, J. Korst, Simulated Annealing and Boltzmann Machines, Wiley-Interscience Series in Discrete Mathematics and Optimization (Wiley, Chichester, N.Y., 1989).

Because there are usually some sources connected to the boundary of the measurement range, we have Nbc ≥ (N+ + N-)/2.

Image used with the kind permission of Fabrice Brémand, Laboratoire de Méchaniques des Solides, Université de Poitiers, France.

M. Takeda, “Recent progress in phase unwrapping techniques,” in Optical Inspection and Micromeasurements, C. Gorecki, ed., Proc. SPIE2782, 334–343 (1996).
[CrossRef]

S. Flügge, ed., Encyclopedia of Physics, Vol. IV: Principles of Electrodynamics and Relativity (Springer, Berlin, 1962).

M. R. Garey, D. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness (Freeman, New York, 1979).

Image used with the kind permission of the Department of Physics, Applied Optics, Carl von Ossietzky University, Oldenburg, Germany.

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

Fig. 1
Fig. 1

Phase map with discontinuity sources. Using path A in Eq. (10) yields zero, whereas path B yields -2π, because path B encircles a discontinuity source (marked by the square).

Fig. 2
Fig. 2

Generation mechanism to apply a small change to the actual set of branch cuts. Two sources of opposite sign are selected randomly. Depending on the initial situation, branch cuts are deleted and new branch cuts are set.

Fig. 3
Fig. 3

Typical incorrect sets of branch cuts that are local minima of the energy and cannot be escaped by an energy-decreasing move defined by the generation mechanism in Fig. 2.

Fig. 4
Fig. 4

Four states of a cooling process for 530 discontinuity sources. Energy and temperature decrease from the initial configuration (a) to the final solution (d).

Fig. 5
Fig. 5

Virtual sources at the border of the measurement range.

Fig. 6
Fig. 6

Parameters for calculating the probability that a dipole of length d¯ is split by the border. The distance of an arbitrary chosen source is given by e; the orientation of the dipole is given by α.

Fig. 7
Fig. 7

Running time of the simulated annealing algorithm versus the number of discontinuity sources for different values of the cooling parameter. The curves are fitted with Eq. (21) and Table 2.

Fig. 8
Fig. 8

Example for the heating algorithm: the nearest-neighbor solution (a) of a distribution of discontinuity sources is heated until neighboring dipoles are connected (b). A further increase of the temperature leads to connections between dipoles by means of longer distances (c).

Fig. 9
Fig. 9

Energy and temperature for a cooling process and a heating process with successive cooling for 384 discontinuity sources at δ = 0.5. The solution found by heating with successive cooling is slightly better.

Fig. 10
Fig. 10

Shadow moiré fringes of the surface contour of a telephone keyboard.

Fig. 11
Fig. 11

Discontinuity sources after evaluation of the phase map of Fig. 10. Owing to local object discontinuities and areas of low fringe modulation, the distribution of sources is inhomogeneous. The phase map contains 102 discontinuity sources.

Fig. 12
Fig. 12

Polynomial behavior of the running time of the simulated annealing algorithm after preprocessing with clustering. A given number of sources is divided into several clusters. If the small clusters are chosen, the number of clusters is almost linear to the number of sources; thus the overall running time tends to be linear, too. The data fit shows the power c and the correlation coefficient R.

Fig. 13
Fig. 13

Clusters of the sources in Fig. 11 achieved by the diffusion process with a binomial mask (r = 21) and a successive closing operation with two iterations. The operation resulted in 24 clusters, 9 of which are charged (marked with gray) with a summed charge of q = 10.

Fig. 14
Fig. 14

Electrostatic potential of a dipole and a positive monopole. The figure shows that the influence of the monopole reaches much farther than the influence of the dipole.

Fig. 15
Fig. 15

Electrostatic potential around charged clusters of Fig. 13.

Fig. 16
Fig. 16

Modulus of the electrostatic field around charged clusters of Fig. 13. High values of the electrostatic field occur between clusters of opposite charge.

Fig. 17
Fig. 17

New detected clusters after growing of charged clusters along high values of the electromagnetic field. The sources are now grouped in 15 clusters that consist of one charged cluster with a remaining charge of q = 2.

Fig. 18
Fig. 18

Phase map of a topographic measurement of a filter cake with projected fringes.

Fig. 19
Fig. 19

Discontinuity sources of the phase map in Fig. 18.

Fig. 20
Fig. 20

Detected clusters of discontinuity sources of Fig. 19 and branch cuts after simulated annealing for the discontinuity sources within each cluster. The size of the convolution mask for cluster detection was enlarged by Δ = 2 to ensure that matching dipoles are within the same cluster. Charged clusters were found only at the border where dipoles have been split.

Fig. 21
Fig. 21

Height map of the filter cake after phase unwrapping. The map shows no obvious errors; thus the clustering method did not produce significant false branch cuts.

Fig. 22
Fig. 22

Phase map of an ESPI out-of-plane deformation measurement of a terra-cotta fragment treated with a conservation agent to investigate the influence of humidity changes. The original phase map was preprocessed with median filtering.

Fig. 23
Fig. 23

Discontinuity sources of the phase map in Fig. 22.

Fig. 24
Fig. 24

Detected clusters of discontinuity sources of Fig. 23 and branch cuts after simulated annealing for the discontinuity sources within each cluster. The size of the convolution mask for cluster detection was reduced by Δ = -4, because corresponding sources are not separated far from each other. Charged clusters (located mainly at the border) were neutralized wherever possible.

Fig. 25
Fig. 25

Phase map of the out-of-plane deformation after phase unwrapping.

Tables (3)

Tables Icon

Table 1 Estimation of the Number of Border Connections for Different Applicationsa

Tables Icon

Table 2 Results of Fitting Eq. (21) to Experimental Data for Different Values of Cooling Parameter δa

Tables Icon

Table 3 Experimental Results for the Topographic Measurement of the Dust Filter Cake with Fringe Projection and for the Out-of-Plane Deformation Measurement with ESPIa

Equations (42)

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

Ix, y=I0x, y+ax, ycos ϕx, y,
ϕwpx, y=ϕx, ymod 2π.
ϕx, y=ϕwpx, y+2πΛx, y,
Wˆϕxi=ϕxi+2πkxi,  kxi
ˆϕwpxi=Wˆϕwpxi-ϕwpxi-1,
ϕxN=ϕwpx0+i=1N ˆϕxi.
i=1NA ˆϕxiA-i=1NB ˆϕxiB=0,
-ˆϕwpxi=-Wˆϕwpxi-ϕwpxi-1=Wˆϕwpxi-1-ϕwpxi,
i=1NA ˆϕxiA+i=1N-B ˆϕxi-B=0
i ˆϕCi=0
i ˆϕCi=2πn,  n.
Ek=i=1Nbc |ai|2
ΔE=Ek+1-Ek
p=1  if ΔE0,  p=exp-ΔE/T  if ΔE>0.
Lmc=Nbc2,
Tk+1=Tk1+Tk ln1+δ/3σk,
fs=2πs tanacoss/d¯-1
Psplit=e<s fsfedsde+-e<-s fsfedsde==1π.
Nborder=Nd¯/π+ΔN
p=Nborder/Nbc;
tcalc=a+bN++N-c
E=λ i=1Nbc |ai|q+i,j=1Nbc μijai·aj|aiaj|+ i=1Nbc |ai·grad ϕxi, yi|.
λ/1/20001/10000
dD2=4πmnNbc
E¯=Nbci=1Nbc dD2=4π mn.
tcluster=ka+bN++N-kc=ka+b N++N-ckc-1=ak1-k-c+tcalckc-1
tcalctclus=tcalcak1-k-c+tcalck1-ckc-1.
tclustcalckc-1  N++N-ckc-1  N++N-cN++N-c-1=N++N-.
r=dD,  if dD is odd,  r=dD-1,  if dD is even,
ρx, y=1Ωi,j=-qq Dx-i, y-jBri, j,
Ω=i,j=-qq Bri, j,  q=r-1/2,
Ψx=Vρex|x-x|d3x=i=1N+1|xi-x|-j=1N-1|xj-x|
Ex=-gradΨx.
Ex=-ΔxΨΔyΨ,
|Ex|=ΔxΨ2+ΔyΨ21/2,
ΔxΨ=Ψx, y-Ψx-1, y,
ΔyΨ=Ψx, y-Ψx, y-1.
Fx=qEx,
tdiff  r×m×n,
tpot  p×s,
tfield  p.
tdiff<a+bN++N-c1-k1-c-ak1-k-c.

Metrics