Abstract

A novel hybrid genetic algorithm (HGA) is proposed to solve the branch-cut phase unwrapping problem. It employs both local and global search methods. The local search is implemented by using the nearest-neighbor method, whereas the global search is performed by using the genetic algorithm. The branch-cut phase unwrapping problem [a nondeterministic polynomial (NP-hard) problem] is implemented in a similar way to the traveling-salesman problem, a very-well-known combinational optimization problem with profound research and applications. The performance of the proposed algorithm was tested on both simulated and real wrapped phase maps. The HGA is found to be robust and fast compared with three well-known branch-cut phase unwrapping algorithms.

© 2007 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. J. M. Huntley, "Three-dimensional noise-immune phase unwrapping algorithm," Appl. Opt. 40, 3901-3908 (2001).
    [CrossRef]
  2. R. Cusack, J. M. Huntley, and H. T. Goldrein, "Improved noise-immune phase-unwrapping algorithm," Appl. Opt. 24, 781-789 (1995).
    [CrossRef]
  3. J. R. Buckland, J. M. Huntley, and J. M. Turner, "Unwrapping noisy phase maps by use of a minimum-cost-matching algorithm," Appl. Opt. 34, 5100-5108 (1995).
    [CrossRef] [PubMed]
  4. D. C. Ghiglia and M. D. Pritt, Two-Dimensional Phase Unwrapping: Theory, Algorithms and Software (Wiley, 1998).
  5. B. Gutmann, "Phase unwrapping with the branch-cut method: clustering of discontinuity sources and reverse simulated annealing," Appl. Opt. 38, 5577-5793 (1999).
    [CrossRef]
  6. D. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning (Addison-Wesley, 1989).
  7. W. H. Steeb, The Nonlinear Workbook (World Scientific, 2002).
  8. S. Jung and B. R. Moon, "Toward minimal restriction of genetic encoding and crossovers for the two-dimensional Euclidean TSP," IEEE Trans. Evol. Comput. 6, 557-564 (2002).
    [CrossRef]
  9. Y. Nagata and S. Kobayashi, "An analysis of edge assembly crossover for the traveling salesman problem," in Proceedings of IEEE International Conference on Systems, Man, and Cybernetics (IEEE, 1999), pp. 628-633.
  10. H. K. Tsai, J. M. Yang, Y. F. Tsai, and C. Y. Kao, "An evolutionary algorithm for large traveling salesman problem," IEEE Trans. Syst. Man Cybern. 34, 1718-1729 (2004).
    [CrossRef]
  11. G. A. Jayalakshmi, S. Sathiamoorthy, and R. Rajaram, "A hybrid genetic algorithm--a new approach to solve traveling salesman problem," Int. J. Comput. Eng. Sci. 2, 339-355 (2001).
    [CrossRef]
  12. N. Mansour, H. Tabbara, and T. Dana, "A genetic algorithm approach for regrouping service sites," Comput. Oper. Res. 31, 1318-1333 (2004).
    [CrossRef]
  13. R. Baraglia, J. I. Hidalgo, and R. Perego, "A hybrid heuristic for the traveling salesman problem," IEEE Trans. Evol. Comput. 5, 613-622 (2001).
    [CrossRef]
  14. H. Tsai, "Heterogeneous selection genetic algorithms for traveling salesman problems," Eng. Optimiz. 35, 297-311 (2003).
    [CrossRef]

2004

H. K. Tsai, J. M. Yang, Y. F. Tsai, and C. Y. Kao, "An evolutionary algorithm for large traveling salesman problem," IEEE Trans. Syst. Man Cybern. 34, 1718-1729 (2004).
[CrossRef]

N. Mansour, H. Tabbara, and T. Dana, "A genetic algorithm approach for regrouping service sites," Comput. Oper. Res. 31, 1318-1333 (2004).
[CrossRef]

2003

H. Tsai, "Heterogeneous selection genetic algorithms for traveling salesman problems," Eng. Optimiz. 35, 297-311 (2003).
[CrossRef]

2002

S. Jung and B. R. Moon, "Toward minimal restriction of genetic encoding and crossovers for the two-dimensional Euclidean TSP," IEEE Trans. Evol. Comput. 6, 557-564 (2002).
[CrossRef]

2001

G. A. Jayalakshmi, S. Sathiamoorthy, and R. Rajaram, "A hybrid genetic algorithm--a new approach to solve traveling salesman problem," Int. J. Comput. Eng. Sci. 2, 339-355 (2001).
[CrossRef]

R. Baraglia, J. I. Hidalgo, and R. Perego, "A hybrid heuristic for the traveling salesman problem," IEEE Trans. Evol. Comput. 5, 613-622 (2001).
[CrossRef]

J. M. Huntley, "Three-dimensional noise-immune phase unwrapping algorithm," Appl. Opt. 40, 3901-3908 (2001).
[CrossRef]

1999

1995

J. R. Buckland, J. M. Huntley, and J. M. Turner, "Unwrapping noisy phase maps by use of a minimum-cost-matching algorithm," Appl. Opt. 34, 5100-5108 (1995).
[CrossRef] [PubMed]

R. Cusack, J. M. Huntley, and H. T. Goldrein, "Improved noise-immune phase-unwrapping algorithm," Appl. Opt. 24, 781-789 (1995).
[CrossRef]

Baraglia, R.

R. Baraglia, J. I. Hidalgo, and R. Perego, "A hybrid heuristic for the traveling salesman problem," IEEE Trans. Evol. Comput. 5, 613-622 (2001).
[CrossRef]

Buckland, J. R.

Cusack, R.

R. Cusack, J. M. Huntley, and H. T. Goldrein, "Improved noise-immune phase-unwrapping algorithm," Appl. Opt. 24, 781-789 (1995).
[CrossRef]

Dana, T.

N. Mansour, H. Tabbara, and T. Dana, "A genetic algorithm approach for regrouping service sites," Comput. Oper. Res. 31, 1318-1333 (2004).
[CrossRef]

Ghiglia, D. C.

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

Goldberg, D.

D. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning (Addison-Wesley, 1989).

Goldrein, H. T.

R. Cusack, J. M. Huntley, and H. T. Goldrein, "Improved noise-immune phase-unwrapping algorithm," Appl. Opt. 24, 781-789 (1995).
[CrossRef]

Gutmann, B.

Hidalgo, J. I.

R. Baraglia, J. I. Hidalgo, and R. Perego, "A hybrid heuristic for the traveling salesman problem," IEEE Trans. Evol. Comput. 5, 613-622 (2001).
[CrossRef]

Huntley, J. M.

Jayalakshmi, G. A.

G. A. Jayalakshmi, S. Sathiamoorthy, and R. Rajaram, "A hybrid genetic algorithm--a new approach to solve traveling salesman problem," Int. J. Comput. Eng. Sci. 2, 339-355 (2001).
[CrossRef]

Jung, S.

S. Jung and B. R. Moon, "Toward minimal restriction of genetic encoding and crossovers for the two-dimensional Euclidean TSP," IEEE Trans. Evol. Comput. 6, 557-564 (2002).
[CrossRef]

Kao, C. Y.

H. K. Tsai, J. M. Yang, Y. F. Tsai, and C. Y. Kao, "An evolutionary algorithm for large traveling salesman problem," IEEE Trans. Syst. Man Cybern. 34, 1718-1729 (2004).
[CrossRef]

Kobayashi, S.

Y. Nagata and S. Kobayashi, "An analysis of edge assembly crossover for the traveling salesman problem," in Proceedings of IEEE International Conference on Systems, Man, and Cybernetics (IEEE, 1999), pp. 628-633.

Mansour, N.

N. Mansour, H. Tabbara, and T. Dana, "A genetic algorithm approach for regrouping service sites," Comput. Oper. Res. 31, 1318-1333 (2004).
[CrossRef]

Moon, B. R.

S. Jung and B. R. Moon, "Toward minimal restriction of genetic encoding and crossovers for the two-dimensional Euclidean TSP," IEEE Trans. Evol. Comput. 6, 557-564 (2002).
[CrossRef]

Nagata, Y.

Y. Nagata and S. Kobayashi, "An analysis of edge assembly crossover for the traveling salesman problem," in Proceedings of IEEE International Conference on Systems, Man, and Cybernetics (IEEE, 1999), pp. 628-633.

Perego, R.

R. Baraglia, J. I. Hidalgo, and R. Perego, "A hybrid heuristic for the traveling salesman problem," IEEE Trans. Evol. Comput. 5, 613-622 (2001).
[CrossRef]

Pritt, M. D.

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

Rajaram, R.

G. A. Jayalakshmi, S. Sathiamoorthy, and R. Rajaram, "A hybrid genetic algorithm--a new approach to solve traveling salesman problem," Int. J. Comput. Eng. Sci. 2, 339-355 (2001).
[CrossRef]

Sathiamoorthy, S.

G. A. Jayalakshmi, S. Sathiamoorthy, and R. Rajaram, "A hybrid genetic algorithm--a new approach to solve traveling salesman problem," Int. J. Comput. Eng. Sci. 2, 339-355 (2001).
[CrossRef]

Steeb, W. H.

W. H. Steeb, The Nonlinear Workbook (World Scientific, 2002).

Tabbara, H.

N. Mansour, H. Tabbara, and T. Dana, "A genetic algorithm approach for regrouping service sites," Comput. Oper. Res. 31, 1318-1333 (2004).
[CrossRef]

Tsai, H.

H. Tsai, "Heterogeneous selection genetic algorithms for traveling salesman problems," Eng. Optimiz. 35, 297-311 (2003).
[CrossRef]

Tsai, H. K.

H. K. Tsai, J. M. Yang, Y. F. Tsai, and C. Y. Kao, "An evolutionary algorithm for large traveling salesman problem," IEEE Trans. Syst. Man Cybern. 34, 1718-1729 (2004).
[CrossRef]

Tsai, Y. F.

H. K. Tsai, J. M. Yang, Y. F. Tsai, and C. Y. Kao, "An evolutionary algorithm for large traveling salesman problem," IEEE Trans. Syst. Man Cybern. 34, 1718-1729 (2004).
[CrossRef]

Turner, J. M.

Yang, J. M.

H. K. Tsai, J. M. Yang, Y. F. Tsai, and C. Y. Kao, "An evolutionary algorithm for large traveling salesman problem," IEEE Trans. Syst. Man Cybern. 34, 1718-1729 (2004).
[CrossRef]

Appl. Opt.

Comput. Oper. Res.

N. Mansour, H. Tabbara, and T. Dana, "A genetic algorithm approach for regrouping service sites," Comput. Oper. Res. 31, 1318-1333 (2004).
[CrossRef]

Eng. Optimiz.

H. Tsai, "Heterogeneous selection genetic algorithms for traveling salesman problems," Eng. Optimiz. 35, 297-311 (2003).
[CrossRef]

IEEE Trans. Evol. Comput.

R. Baraglia, J. I. Hidalgo, and R. Perego, "A hybrid heuristic for the traveling salesman problem," IEEE Trans. Evol. Comput. 5, 613-622 (2001).
[CrossRef]

S. Jung and B. R. Moon, "Toward minimal restriction of genetic encoding and crossovers for the two-dimensional Euclidean TSP," IEEE Trans. Evol. Comput. 6, 557-564 (2002).
[CrossRef]

IEEE Trans. Syst. Man Cybern.

H. K. Tsai, J. M. Yang, Y. F. Tsai, and C. Y. Kao, "An evolutionary algorithm for large traveling salesman problem," IEEE Trans. Syst. Man Cybern. 34, 1718-1729 (2004).
[CrossRef]

Int. J. Comput. Eng. Sci.

G. A. Jayalakshmi, S. Sathiamoorthy, and R. Rajaram, "A hybrid genetic algorithm--a new approach to solve traveling salesman problem," Int. J. Comput. Eng. Sci. 2, 339-355 (2001).
[CrossRef]

Other

Y. Nagata and S. Kobayashi, "An analysis of edge assembly crossover for the traveling salesman problem," in Proceedings of IEEE International Conference on Systems, Man, and Cybernetics (IEEE, 1999), pp. 628-633.

D. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning (Addison-Wesley, 1989).

W. H. Steeb, The Nonlinear Workbook (World Scientific, 2002).

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

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

Fig. 1
Fig. 1

Residue calculation and a typical branch cut between two dipoles.

Fig. 2
Fig. 2

Simple genetic algorithm, where P x and P m are the probability of performing crossover and mutation respectively.

Fig. 3
Fig. 3

Residues and their corresponding opposite polarity residue boundary pixels in the masked image.

Fig. 4
Fig. 4

Two opposite polarity chromosomes configured using ARACB coding.

Fig. 5
Fig. 5

Residues and their corresponding opposite polarity residue boundary pixels in the masked image with an emphasis on boundary calculation.

Fig. 6
Fig. 6

Two opposite polarity chromosomes configured using ARMCB coding.

Fig. 7
Fig. 7

Example of an initial population consisting of five negative chromosomes, where each chromosome represents a solution for the branch-cut phase unwrapping problem.

Fig. 8
Fig. 8

(Color online) The 2-opt heuristic method.

Fig. 9
Fig. 9

Selection of edges used to calculate the fitness of the negative chromosome where the positive chromosome is a reference chromosome.

Fig. 10
Fig. 10

Main steps of the selection operator.

Fig. 11
Fig. 11

Example of the main steps of the selection operator on an eight-chromosome population.

Fig. 12
Fig. 12

(Color online) Example of SCX crossover operator developed for the HGA.

Fig. 13
Fig. 13

(Color online) The LK-mutation operator on an eight-gene chromosome performing three-gene mutations.

Fig. 14
Fig. 14

(a) A 256 × 256 noisy simulated wrapped phase map, (b) its corresponding residue map containing 2501 residues, 1255 positive residues and 1246 negative residues.

Fig. 15
Fig. 15

Unwrapped phase map for the simulated wrapped phase map in Fig. 14(a) achieved using (a) SA, (b) RSA (without heating), (c) MCM algorithm, and (d) HGA (without an initial solution).

Fig. 16
Fig. 16

(a) A 512 × 512 noisy IFSAR wrapped phase map obtained from Ref. [4], and (b) its corresponding residue map containing 5877 residues, 2940 positive residues and 2937 negative residues.

Fig. 17
Fig. 17

The distribution of branch cuts in the residue phase map achieved using (a) SA, (b) RSA (with heating), (c) MCM algorithm, and (d) HGA (with an initial solution).

Fig. 18
Fig. 18

Unwrapped phase map for the noisy IFSAR wrapped phase map in Fig. 17(a) achieved using (a) SA, (b) RSA (with heating), (c) MCM algorithm, and (d) HGA (with an initial solution).

Tables (2)

Tables Icon

Table 1 Comparison of the HGA Execution Time, Total Cut-Length Distance, and Unweighted L 0 Measure with Other Algorithms for the Noisey Wrapped Phase Map in Fig. 14

Tables Icon

Table 2 Comparison of the HGA Execution Time, Total Cut-Length Distance, and Unweighted L 0 Measure with Other Algorithms for the IFSAR Wrapped Phase Map

Equations (51)

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

π
+ π
2 π
2 π
2 π
2 π
i M Δ Φ ( p i ) = 0 ,
Φ ( p i )
p i { P }
Δ Φ ( p i )
{ P }
2 π
2 × 2
2 π
1
2 × 2
n = 0
i M Δ Φ ( p i ) = 2 π n .
+ 1
1
C = { c 1 , c 2 , c 3 c N }
Total_Distance = ( d c i , d c i + 1 ) ,
c i c i + 1
R = { r 1 , r 2 , r 3 r N }
B = { b 1 , b 2 , b 3 b N 1 }
L ( r i , r j )
r i
r j
2 × 2
d b
d a < d b
Fitness = i N [ ( x g i + x g i ) 2 + ( y g i + y g i ) 2 ] 1 / 2 .
f n f k < e
{ 2 , N }
d 1
d 2
d 1 < d 2
d 2 < d 1
P x = 0.9
P m = 0.01
P x
P m
L 0
L 0
L 0
L 0
L 0
P x
P m
256 × 256
512 × 512

Metrics