Abstract

We present a cross-entropy (CE)-based method for the design of optimum two-dimensional (2D) zero reference codes (ZRCs) in order to generate a zero reference signal for a grating measurement system and achieve absolute position, a coordinate origin, or a machine home position. In the absence of diffraction effects, the 2D ZRC design problem is known as the autocorrelation approximation. Based on the properties of the autocorrelation function, the design of the 2D ZRC is first formulated as a particular combination optimization problem. The CE method is then applied to search for an optimal 2D ZRC and thus obtain the desirable zero reference signal. Computer simulation results indicate that there are 15.38% and 14.29% reductions in the second maxima value for the 16×16 grating system with n1=64 and the 100×100 grating system with n1=300, respectively, where n1 is the number of transparent pixels, compared with those of the conventional genetic algorithm.

© 2010 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. J. Saez-Landete, S. Salcedo-Sanz, M. Rosa-Zurera, J. Eusebio, and A. Bernabeu, “Design of two-dimensional zero reference codes with a genetic algorithm,” Opt. Lett. 31, 1648–1650(2006).
    [CrossRef] [PubMed]
  2. Y. Chen, W. Huang, and X. Dang, “Design and analysis of two-dimensional zero-reference marks for alignment systems,” Rev. Sci. Instrum. 74, 3549–3553 (2003).
    [CrossRef]
  3. Y. Li, “Optical valve using bar codes,” Optik (Jena) 79, 67–74 (1988).
  4. X. Yang and C. Yin, “A new method for the design of zero reference marks for grating measurement systems,” J. Phys. E 19, 34–37 (1986).
    [CrossRef]
  5. J. Saez-Landete, J. Alonso, and E. Bernabeu, “Design of two-dimensional zero reference codes by means of a global optimization method,” Opt. Express 13, 4230–4236 (2005).
    [CrossRef] [PubMed]
  6. R. Y. Rubinstein and D. P. Kroese, The Cross-Entropy Method (Springer, 2004).
  7. J. Chen, “Design of zero reference codes using cross-entropy method,” Opt. Express 17, 22163–22170 (2009).
    [CrossRef] [PubMed]
  8. Y. Li, “Autocorrelation function of a bar code system,” J. Mod. Opt. 34, 1571–1575 (1987).
    [CrossRef]
  9. If no design was done, we may randomly generate a binary 2D ZRC c. In this case, however, we still need an extra operation to fix the number of 1s in the binary strings to n1. This can be carried out by the restricted search operator , which randomly adds or removes the necessary 1s to meet the number of the transparent pixels.
  10. S. Salcedo-Sanz, G. Camps-Valls, F. Perez-Cruz, J. Sepulveda-Sanchis, and C. Bousono-Calzon, “Enhancing genetic feature selection through restricted search and Walsh analysis,” IEEE Trans. Syst. Man Cybern. C 34, 398–406 (2004).
    [CrossRef]
  11. J. Saez-Landete, S. Salcedo-Sanz, F. Cruz-Roldan, P. Amo-Lopez, and M. Blanco-Velasco, “Design of two-dimensional optical alignment signals robust to diffractive effects,” J. Lightwave Technol. 26, 1702–1707 (2008).
    [CrossRef]

2009 (1)

2008 (1)

2006 (1)

2005 (1)

2004 (1)

S. Salcedo-Sanz, G. Camps-Valls, F. Perez-Cruz, J. Sepulveda-Sanchis, and C. Bousono-Calzon, “Enhancing genetic feature selection through restricted search and Walsh analysis,” IEEE Trans. Syst. Man Cybern. C 34, 398–406 (2004).
[CrossRef]

2003 (1)

Y. Chen, W. Huang, and X. Dang, “Design and analysis of two-dimensional zero-reference marks for alignment systems,” Rev. Sci. Instrum. 74, 3549–3553 (2003).
[CrossRef]

1988 (1)

Y. Li, “Optical valve using bar codes,” Optik (Jena) 79, 67–74 (1988).

1987 (1)

Y. Li, “Autocorrelation function of a bar code system,” J. Mod. Opt. 34, 1571–1575 (1987).
[CrossRef]

1986 (1)

X. Yang and C. Yin, “A new method for the design of zero reference marks for grating measurement systems,” J. Phys. E 19, 34–37 (1986).
[CrossRef]

Alonso, J.

Amo-Lopez, P.

Bernabeu, A.

Bernabeu, E.

Blanco-Velasco, M.

Bousono-Calzon, C.

S. Salcedo-Sanz, G. Camps-Valls, F. Perez-Cruz, J. Sepulveda-Sanchis, and C. Bousono-Calzon, “Enhancing genetic feature selection through restricted search and Walsh analysis,” IEEE Trans. Syst. Man Cybern. C 34, 398–406 (2004).
[CrossRef]

Camps-Valls, G.

S. Salcedo-Sanz, G. Camps-Valls, F. Perez-Cruz, J. Sepulveda-Sanchis, and C. Bousono-Calzon, “Enhancing genetic feature selection through restricted search and Walsh analysis,” IEEE Trans. Syst. Man Cybern. C 34, 398–406 (2004).
[CrossRef]

Chen, J.

Chen, Y.

Y. Chen, W. Huang, and X. Dang, “Design and analysis of two-dimensional zero-reference marks for alignment systems,” Rev. Sci. Instrum. 74, 3549–3553 (2003).
[CrossRef]

Cruz-Roldan, F.

Dang, X.

Y. Chen, W. Huang, and X. Dang, “Design and analysis of two-dimensional zero-reference marks for alignment systems,” Rev. Sci. Instrum. 74, 3549–3553 (2003).
[CrossRef]

Eusebio, J.

Huang, W.

Y. Chen, W. Huang, and X. Dang, “Design and analysis of two-dimensional zero-reference marks for alignment systems,” Rev. Sci. Instrum. 74, 3549–3553 (2003).
[CrossRef]

Kroese, D. P.

R. Y. Rubinstein and D. P. Kroese, The Cross-Entropy Method (Springer, 2004).

Li, Y.

Y. Li, “Optical valve using bar codes,” Optik (Jena) 79, 67–74 (1988).

Y. Li, “Autocorrelation function of a bar code system,” J. Mod. Opt. 34, 1571–1575 (1987).
[CrossRef]

Perez-Cruz, F.

S. Salcedo-Sanz, G. Camps-Valls, F. Perez-Cruz, J. Sepulveda-Sanchis, and C. Bousono-Calzon, “Enhancing genetic feature selection through restricted search and Walsh analysis,” IEEE Trans. Syst. Man Cybern. C 34, 398–406 (2004).
[CrossRef]

Rosa-Zurera, M.

Rubinstein, R. Y.

R. Y. Rubinstein and D. P. Kroese, The Cross-Entropy Method (Springer, 2004).

Saez-Landete, J.

Salcedo-Sanz, S.

Sepulveda-Sanchis, J.

S. Salcedo-Sanz, G. Camps-Valls, F. Perez-Cruz, J. Sepulveda-Sanchis, and C. Bousono-Calzon, “Enhancing genetic feature selection through restricted search and Walsh analysis,” IEEE Trans. Syst. Man Cybern. C 34, 398–406 (2004).
[CrossRef]

Yang, X.

X. Yang and C. Yin, “A new method for the design of zero reference marks for grating measurement systems,” J. Phys. E 19, 34–37 (1986).
[CrossRef]

Yin, C.

X. Yang and C. Yin, “A new method for the design of zero reference marks for grating measurement systems,” J. Phys. E 19, 34–37 (1986).
[CrossRef]

IEEE Trans. Syst. Man Cybern. C (1)

S. Salcedo-Sanz, G. Camps-Valls, F. Perez-Cruz, J. Sepulveda-Sanchis, and C. Bousono-Calzon, “Enhancing genetic feature selection through restricted search and Walsh analysis,” IEEE Trans. Syst. Man Cybern. C 34, 398–406 (2004).
[CrossRef]

J. Lightwave Technol. (1)

J. Mod. Opt. (1)

Y. Li, “Autocorrelation function of a bar code system,” J. Mod. Opt. 34, 1571–1575 (1987).
[CrossRef]

J. Phys. E (1)

X. Yang and C. Yin, “A new method for the design of zero reference marks for grating measurement systems,” J. Phys. E 19, 34–37 (1986).
[CrossRef]

Opt. Express (2)

Opt. Lett. (1)

Optik (Jena) (1)

Y. Li, “Optical valve using bar codes,” Optik (Jena) 79, 67–74 (1988).

Rev. Sci. Instrum. (1)

Y. Chen, W. Huang, and X. Dang, “Design and analysis of two-dimensional zero-reference marks for alignment systems,” Rev. Sci. Instrum. 74, 3549–3553 (2003).
[CrossRef]

Other (2)

If no design was done, we may randomly generate a binary 2D ZRC c. In this case, however, we still need an extra operation to fix the number of 1s in the binary strings to n1. This can be carried out by the restricted search operator , which randomly adds or removes the necessary 1s to meet the number of the transparent pixels.

R. Y. Rubinstein and D. P. Kroese, The Cross-Entropy Method (Springer, 2004).

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

Fig. 1
Fig. 1

Two-dimensional alignment system based on 2D ZRCs.

Fig. 2
Fig. 2

Two-dimensional ZRC found by the proposed CE method with 16 × 16 elements and 64 transparent pixels.

Fig. 3
Fig. 3

Two-dimensional ZRC found by the proposed CE method with 100 × 100 elements and 300 transparent pixels.

Fig. 4
Fig. 4

Autocorrelation signal obtained with a 2D ZRC of 100 × 100 elements and 300 transparent pixels. The second maxima is 12.

Fig. 5
Fig. 5

Average height of the second maxima versus iterations.

Fig. 6
Fig. 6

Two-dimensional ZRC found by the proposed CE method with 32 × 32 elements and 100 transparent pixels.

Fig. 7
Fig. 7

Two-dimensional ZRC found by the proposed CE method with 50 × 50 elements and 200 transparent pixels.

Tables (1)

Tables Icon

Table 1 Comparison of the Second Maximas Obtained by Chen’s Method [2], the Genetic Algorithm [1], the Proposed Cross-Entropy Algorithm, and the Theoretical Lower Bound

Equations (13)

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

c i j = { 1 , if a transparent pixel is located at the i j position 0 , otherwise ,
i = 1 n j = 1 n c i j = n 1 ,
S k l ( c ) = i = 1 n k j = 1 n l c i j c i + k , j + l ,
σ = max k 2 + l 2 0 { S k l ( c ) } ,
ω * = arg min ω q Ω C sel ( ω q ) ,
ω q = [ I i j ] = [ I 11 I 1 n I n 1 I n n ] , q = 1 , 2 , , Q ,
I i j = { 1 , if a transparent pixel is located at the i j position 0 , otherwise .
f ( ω q , p ) = i = 1 n j = 1 n p i j I i j ( ω q ) ( 1 p i j ) 1 I i j ( ω q ) ,
p i j ( t ) = m = 1 M I { C sel ( ω q ( m , t ) ) r ( t ) } I i j ( ω q ( m , t ) ) m = 1 M I { C sel ( ω q ( m , t ) ) r ( t ) } ,
I { C sel ( ω q ( m , t ) ) r ( t ) } = { 1 , if C sel ( ω q ( m , t ) ) r ( t ) 0 , otherwise .
p ( t ) = λ × p ( t ) + ( 1 λ ) × p ( t 1 ) ,
σ σ 1 = ( 2 n 2 + n 1 ) ( 2 n 2 + n 1 ) 2 4 ( 1 + 1 n ) n 1 ( n 1 1 ) 2 ( 1 + 1 n ) .
( 100 × 100 300 ) / ( 16 × 16 64 )

Metrics