## Design of two-dimensional zero reference codes by means of a global optimization method

Optics Express, Vol. 13, Issue 11, pp. 4230-4236 (2005)

http://dx.doi.org/10.1364/OPEX.13.004230

Acrobat PDF (183 KB)

### Abstract

A method to obtain the absolute measure of the position is by means of the autocorrelation of two zero reference marks. In one-axis measurement systems one dimensional mark are used and the design of these marks is relatively complex. When the movement is in two-axes, two dimensional reference marks are required and they are even harder to design. We report a method of global optimization to calculate the optimal two dimensional zero reference marks which generate the reference signal with the highest central peak. This method proves to be a powerful tool for solving this problem.

© 2005 Optical Society of America

## 1. Introduction

3. Xiangyang Yang and Chunyong Yin, “A new method for the design of zero reference marks for grating measurement systems” J. Phys. E Sci. Instrum. **19**, 34–7 (1986). [CrossRef]

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

6. J. Sáez-Landete, J. Alonso, and E. Bernabeu, “Design of zero reference codes by means of a global optimization method” Op. Ex. **13**, 195–201 (2005), http://www.opticsexpress.org/abstract.cfm?URI=OPEX-13-1-195. [CrossRef]

7. Y. Chen, W. Huang, and X. Dang, “Design and analysis of two-dimensional zero-reference marks for alignment systems” Review of Scientific Instruments , **74**, 3549–53 (2003). [CrossRef]

*et al*. proposed a new kind of 2-dimensional binary codes for precise positioning and alignment. These 2D codes are made up of unevenly located, opaque pixels on a transparent substrate. The system operation is similar to the one used with one-dimensional zero reference signals. When the movement takes place on the XY plane, the signal is obtained as the two-dimensional correlation of the ZRCs. Therefore, two-axis alignment can be detected with a simple system. Despite the simplicity of the optical alignment system, high quality two-dimensional ZRCs are much harder to design than its one-dimensional counterparts. In this work we demonstrate that a global optimization algorithm can also be used to quickly obtain two-dimensional ZRCs with optimal correlation properties.

## 2. General considerations

*n*

^{2}is the total number of elements of the ZRC,

*c*=1 if a transparent pixel is located at the

_{ij}*ij*-position, and

*c*=0 elsewhere. The number of transparent pixels is

_{ij}*n*

_{1}. The sizes of the transparent and opaque regions in the ZRC are integer multiples of the width of a single pixel.

*k*and

*l*units in the X and Y directions respectively, the signal registered in the photodiode is proportional to

*k,l=-n*+1,…,

*n*-1, and the signal

*S*is the autocorrelation matrix of the two ZRC defined in Eq. (1).

_{kl}*S*

_{00}is the signal obtained when the relative displacement between the ZRCs is zero. It is the central maximum and is equal to the number of transparent pixels,

*n*

_{1}

*k*

^{2}+

*l*

^{2}≠0 mean that

*k*≠0 and

*l*≠0 at the same time.

*K*=

*σ/S*

_{00}. A good zero reference signal must be a single and well distinct peak, so the secondary maxima of the correlation signal must be low. The smaller

*K*value, the higher the sensitivity and robustness of the zero reference signal.

*n*and

*n*

_{1}predetermined and we have to minimize the second maximum of the signal,

*σ*.

## 3. The lower bound of the second maximum

*et al*. Ref. [7

7. Y. Chen, W. Huang, and X. Dang, “Design and analysis of two-dimensional zero-reference marks for alignment systems” Review of Scientific Instruments , **74**, 3549–53 (2003). [CrossRef]

*n*

_{1}transparent pixels are concentrated in one corner of the ZRC. This lower bound is very conservative, and it is given by:

*x*and

*y*directions, the integrated light intensity registered in the photodiode is:

*S*.

_{k,l}=S_{-k,-l}*S*is equal to the number of coincident transparent pixels when a code is displaced

_{kl}*k*and

*l*units in the x and y directions respectively. In this case, a transparent pixel (

*c*=1) coincide with other transparent pixel (

_{ij}*c*=1) if both elements are in the code, that is, if there is a substructure with dimension (

_{i+k,j+l}*k*+1,

*l*+1) in the ZRC,

*X*∈{0,1}. Moreover, the value of

*S*is the number of these type of substructures in the ZRC with dimension (

_{kl}*k*+1,

*l*+1). Being the code dimension

*n*×

*n*, the maximum number of substructures contained in the code are (

*n*-|

*k*|)(

*n*-|

*l*|), so

*k*| and |

*l*| (approaching

*n*), the number of substructures contained in the ZRC is small and this upper bound is also small,

*S*0 for

_{kl≤}*k=n*and

*l=n*. On the other hand, when the displacements |

*k*| and |

*l*| are small (approaching 0), the upper bound is large and very rough,

*S*for

_{kl≤}n^{2}*k*=0 and

*l*=0.

*S*

_{00}in Eq. (3) and the second maximum

*σ*in Eq. (4), we can establish another upper bound for the signal,

*σ=n*

_{1}≤

*n*

^{2}.

*k*and

*l*close to

*n*, the lowest bound is given by Eq. (8), and for

*k*and

*l*close to 0, Eq. (9) establishes the lowest bound. A limit between two regions can be established when two bounds are equal.

*l*|≤|

*l*

_{1}| the lowest bound is the Eq. (9), whereas if |

*l*|≤|

*l*

_{1}| it is the Eq. (8). For some values of

*k*

_{1}and s, the Eq. (10) can be negative and we only have the bound given in Eq. (8). These values are for

*k*|≤

*n*-

*σ/n, S*has two upper bounds,

_{kl}*k*|>

*n-σ/n*we only consider an upper bound,

*σ*, we replace the signal

*S*by the upper bound in the Eq. (6). For this purpose, by means of property (ii), we split the Eq. (6) in three terms:

_{kl}*k*and

*l*, and using the inequalities given in Eq. (8) and Eq. (12),

*σ*

_{1}, the lower bound for the second maximum of the signal, it is one of the solutions of the second order equation, Eq. (17). In particular,

*n*and

*n*

_{1}, at least one ZRC could be found for which the equality sign holds.

## 4. Direct algorithm

*et al*. Ref. [8

8. D. R. Jones, C. D. Perttunen, and B. E. Stuckman. “Lipschitzian Optimization without the Lipschitz Constant” J. Optim. Theory Appl. **79**, 157–181 (1993). [CrossRef]

## 5. Description of the modeling and results

*f*(

**c**)=

*σ*is the second maximum of the autocorrelation signal,

**c**is a binary matrix and the constraint is

*et al*. (Eq. (5)), and the value of the second maximum reached with DIRECT is shown in Fig. 2. The optimizations were done with 100 elements,

*n*=10, and a variable number of slits in the interval from 1 to 99. From this figure, it can be seen that in few cases it is possible to reach the theoretical lower bound and this takes place when the number of transparent pixels is small. In Fig. 3, we show the optimum autocorrelation signal for a ZRC with 10×10 elements and 50 slits.

6. J. Sáez-Landete, J. Alonso, and E. Bernabeu, “Design of zero reference codes by means of a global optimization method” Op. Ex. **13**, 195–201 (2005), http://www.opticsexpress.org/abstract.cfm?URI=OPEX-13-1-195. [CrossRef]

## 5. Conclusions

## Acknowledgments

## References and Links

1. | M. C. King and D. H. Berry, “Photolithografic mask alignment using moiré techniques” Appl. Opt. |

2. | V. T. Chitnis and Y. Uchida, “Moiré signals in reflection” Optics Communications |

3. | Xiangyang Yang and Chunyong Yin, “A new method for the design of zero reference marks for grating measurement systems” J. Phys. E Sci. Instrum. |

4. | Li Yajun, “Autocorrelation function of a bar code system” J. Mod. Opt. |

5. | Li Yajun, “Optical valve using bar codes” Optik |

6. | J. Sáez-Landete, J. Alonso, and E. Bernabeu, “Design of zero reference codes by means of a global optimization method” Op. Ex. |

7. | Y. Chen, W. Huang, and X. Dang, “Design and analysis of two-dimensional zero-reference marks for alignment systems” Review of Scientific Instruments , |

8. | D. R. Jones, C. D. Perttunen, and B. E. Stuckman. “Lipschitzian Optimization without the Lipschitz Constant” J. Optim. Theory Appl. |

9. | Donald R. Jones. |

10. | Bjorkman, Mattias, Holmstrom, and Kenneth. “Global Optimization Using the DIRECT Algorithm in Matlab” Advanced Modeling and Optimization , |

11. | Daniel E. Finkel and C. T. Kelley. “Convergence analysis of the DIRECT algorithm” Optimization Online (2004). |

12. | J. M. Gablonsky. |

**OCIS Codes**

(050.2770) Diffraction and gratings : Gratings

(120.0120) Instrumentation, measurement, and metrology : Instrumentation, measurement, and metrology

(120.3940) Instrumentation, measurement, and metrology : Metrology

(220.0220) Optical design and fabrication : Optical design and fabrication

(230.0230) Optical devices : Optical devices

**ToC Category:**

Research Papers

**History**

Original Manuscript: April 26, 2005

Revised Manuscript: May 19, 2005

Published: May 30, 2005

**Citation**

José Sáez-Landete, José Alonso, and Eusebio Bernabeu, "Design of two-dimensional zero reference codes by means of a global optimization method," Opt. Express **13**, 4230-4236 (2005)

http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-13-11-4230

Sort: Journal | Reset

### References

- M. C. King and D. H. Berry, �??Photolithografic mask alignment using moiré techniques�?? Appl. Opt. 11, 2455-2459 (1972). [CrossRef] [PubMed]
- V. T. Chitnis and Y. Uchida, �??Moiré signals in reflection�?? Optics Communications 54, 207-211 (1985). [CrossRef]
- Xiangyang Yang and Chunyong Yin, �??A new method for the design of zero reference marks for grating measurement systems�?? J. Phys. E Sci. Instrum. 19, 34-7 (1986). [CrossRef]
- Li Yajun, �??Autocorrelation function of a bar code system�?? J. Mod. Opt. 34, 1571-5 (1987). [CrossRef]
- Li Yajun, �??Optical valve using bar codes�?? Optik 79, 67-74 (1988).
- J. Sáez-Landete, J. Alonso, E. Bernabeu, �??Design of zero reference codes by means of a global optimization method�?? Op. Ex. 13, 195-201 (2005), <a href="http://www.opticsexpress.org/abstract.cfm?URI=OPEX-13-1-195.">http://www.opticsexpress.org/abstract.cfm?URI=OPEX-13-1-195.</a> [CrossRef]
- Y. Chen, W. Huang and X. Dang, �??Design and analysis of two-dimensional zero-reference marks for alignment systems�?? Review of Scientific Instruments, 74, 3549-53 (2003). [CrossRef]
- D. R. Jones, C. D. Perttunen, and B. E. Stuckman. �??Lipschitzian Optimization without the Lipschitz Constant�?? J. Optim. Theory Appl. 79, 157-181 (1993). [CrossRef]
- Donald R. Jones. DIRECT Global optimization algorithm. Encyclopedia of Optimization. (Kluwer Academic Publishers, Dordrecht, 2001).
- Bjorkman, Mattias and Holmstrom, Kenneth. �??Global Optimization Using the DIRECT Algorithm in Matlab�?? Advanced Modeling and Optimization, 1, 17-37 (1999).
- Daniel E. Finkel and C. T. Kelley. �??Convergence analysis of the DIRECT algorithm�?? Optimization Online (2004).
- J. M. Gablonsky. DIRECT Version 2.0 User Guide. (CRSC Technical Report, Raleigh, 2001).

## Cited By |
Alert me when this paper is cited |

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

« Previous Article | Next Article »

OSA is a member of CrossRef.