# Patent

## Title
End-to-end design of electro-optic imaging systems using the nonequidistant discrete Fourier transform

## Abstract

A unified design strategy takes into account different subsystems within an overall electro-optic imaging system. In one implementation, the design methodology predicts end-to-end imaging performance using a spatial model for the source and models for the optical subsystem, the detector subsystem and the digital image processing subsystem. The optical subsystem and digital image processing subsystems are jointly designed taking into account the entire system. Unconventional techniques such as the nonequidistant DFT (nDFT) are used to accelerate the design process.

## Background
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to the design of electro-optic imaging systems, and more particularly, to the “end-to-end” design of these systems using nonequidistant discrete Fourier transforms, including for example the nonequidistant fast Fourier transform.
2. Description of the Related Art
Electro-optic imaging systems typically include an optical subsystem (e.g., a lens assembly), an electronic detector subsystem (e.g., CCD detector array) and a digital image processing subsystem (e.g., typically implemented in dedicated chips or software). Traditional methods for designing these systems generally involve two discrete stages. First, the optical subsystem is designed with the goal of forming a high quality intermediate optical image of the source (subject to cost, physical and other non-imaging constraints). Next, after the optical subsystem has been designed, the digital image processing subsystem is designed to compensate for remaining defects in the sampled intermediate optical image.
The two design stages typically occur with very little coordination between the optical designer and the image processing designer. One drawback to the traditional design approach is that synergies between the optical subsystem and the digital image processing subsystem may be overlooked. There may be unwanted interactions between the two independently designed subsystems and potential synergies between the two subsystems may go unrealized.
Recently, more holistic design approaches have been proposed. For example, see U.S. patent application Ser. No. 11/155,870, “End-to-End Design of Electro-Optic Imaging Systems,” which is incorporated by reference herein. These design processes combine traditional optical design with digital imaging processing, including characteristics of the imaging sensor. This provides a framework for the end-to-end design of a complete electro-optic imaging system.
The design process typically includes an optimization step that jointly optimizes parameters for the optical subsystem, the detector subsystem and/or the digital image processing subsystem. At each iteration of the optimization, the overall performance of the electro-optic imaging system is modeled, including propagation through each of the subsystems. This modeling is used to calculate a performance metric. The performance metric is optimized with respect to the design parameters. However, modeling propagation through each of the subsystems can be computationally time-consuming, which in turn results in a slow optimization and long design cycle.
Thus, there is a need for faster design techniques based on an end-to-end design of the electro-optic imaging system.
SUMMARY OF THE INVENTION
The present invention overcomes the limitations of the prior art by accelerating the end-to-end design of electro-optic imaging systems, for example by allowing more flexibility in the choice of sampling grids which can then be better suited to the tasks at hand. Examples include using sampling grids that are not regular rectangular grids, using the nonequidistant DFT (nDFT), including the nonequidistant FFT (nFFT), and/or using better suited quadrature approaches for numerical integration.
One aspect of the invention is a method for designing an electro-optic imaging system for imaging a source. The electro-optic imaging system includes an optical subsystem, a detector subsystem and a digital image processing subsystem. Propagation of the source through the optical subsystem, the detector subsystem and the digital image processing subsystem is modeled based on a spatial model of the source. This modeling includes calculating a pupil function for the optical subsystem, where the pupil function is sampled on a non-rectangular grid. A post-processing performance metric is calculated, which is a function of the modeled propagation. The performance metric accounts for a contrast capability of the optical subsystem and for noise from the detector subsystem and/or the digital image processing subsystem. The optical subsystem and the digital image processing subsystem are jointly designed based directly on the post-processing performance metric.
In another aspect, the modeling includes tracing rays through the optical subsystem, where the rays sample a pupil of the optical subsystem on a non-rectangular grid, even though they may eventually be interpolated to a rectangular grid for later computation. Examples of non-rectangular grids include polar grids and linogram grids. For certain situations, tracing 250 or fewer rays is sufficient to estimate a wavefront error function with an accuracy of better than λ/10.
Later computations may include nDFTs. For example, the ray trace may be used to calculate a pupil function. An nDFT may then be applied to the pupil function G to calculate a complex-amplitude point spread function U. An nDFT may also be applied to the corresponding intensity point spread function PSF to calculate an optical transfer function OTF. The OTF can then be used to calculate the integrand of the post-processing performance metric. The integral may be approximated using a quadrature-type numerical integration. In one approach, the post-processing performance metric is a Wiener filter-based mean square error (MSE). The features described above may be used together or separately.
In another aspect, the design process is performed iteratively and the accuracy of the modeling may be adjusted for different interations. For example, earlier iterations may have lower accuracy in order to achieve faster iterations. As a design solution is converged upon, the iterations may be adjusted to have higher accuracy. In some aspects, the user may control the adjustment. In other aspects, the adjustment may occur automatically.
Other aspects of the invention include software and tools to implement the design methods described above, and devices, systems and subsystems created by this design approach.



BRIEF DESCRIPTION OF THE DRAWINGS
The invention has other advantages and features which will be more readily apparent from the following detailed description of the invention and the appended claims, when taken in conjunction with the accompanying drawings, in which:
FIG. 1 is a block diagram illustrating the problem of designing an electro-optic imaging system.
FIG. 2 is a flow diagram illustrating a method for designing an electro-optic imaging system according to the present invention.
FIG. 3 is a block diagram illustrating one software implementation of the end-to-end design approach.
FIG. 4 is a block diagram illustrating one approach to calculating the performance metric of FIG. 3.
FIG. 5 is a plot of aggregate OPD error versus number of rays traced.
FIGS. 6A and 6B are plots of aggregate MSE error versus number of rays traced.
FIG. 7 is a one-dimensional cut through Se, showing approximations by different order polynomials.
FIGS. 8A-8C are plots of quadrature node locations for different types of numerical integration.
FIGS. 9A-9C are plots of MSE approximation as a function of order of the approximation.
FIG. 10 is a block diagram of a system illustrating user control over sampling.



DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
Introduction
FIG. 1 is a block diagram illustrating the problem of designing an electro-optic imaging system 100. The imaging system 100 includes an optical subsystem 110, detector subsystem 120 and digital image processing subsystem 130. The imaging system 100 is intended to image a source 150 and produces digital image 180. The general design problem is to design the imaging system 100 to “optimize” its overall performance, subject to certain constraints. In many cases, the goal of optimization is to produce a digital image 180 which matches the application-specific idealized version 155 of the input source.
FIGS. 1 and 2 illustrate an example method for designing an electro-optic imaging system 100 according to the present invention. Referring to FIG. 2, the design method includes generating 210 a spatial model of the source 150. The spatial model of the source may be derived for a specific situation, empirically measured, based on previously developed models or otherwise provided. Illumination, radiometry and geometry are factors that may be reflected in the source model. The spatial model preferably includes a statistical model of the source. Further examples will be described below.
The design space for the electro-optic imaging system is also defined 220. In FIG. 1, each of the subsystems is defined by its parameters θo, θd and θi, respectively. For example, the design space for the optical subsystem 110, described by the vector θo, may be defined by number, type and size of lenses, radii of curvature, stops, etc. The design space for the detector subsystem 120, described by the vector θd, may parameterize the number of pixels, detector spacing, fill factor, bandwidth, pixel geometry, etc. The design space for the digital image processing subsystem 130, described by the vector θi, may identify the type(s) of digital image processing to be applied and parameters for that type of processing (e.g., linear or nonlinear filters, number of taps, tap weights, etc). Various non-imaging constraints or costs 170 associated with the designs may also be defined. The size of the design space of each subsystem will vary depending on the application. In some cases, there may be much latitude in designing a subsystem. In other cases, the design of the subsystem may be tightly constrained or even pre-defined (e.g., if the detector array is selected a priori).
A post-processing performance metric 190 is also defined 230. The performance metric is post-processing in the sense that it is based on performance after image processing rather than before image processing. For examples, measures of the wavefront error or spot size of the intermediate optical image produced by the optical subsystem alone may be conventional error metrics for the optical subsystem but they are not post-processing performance metrics. In FIG. 1, the post-processing performance metric 190 is based on a comparison of the digital image 180 produced by the imaging system 100 compared to the ideal digital image 155. In many design situations, the image 180 produced by the system is calculated by modeling propagation of the source characteristics 150 through the subsystems 110, 120 and 130 based on the spatial model of the source.
The design step 240 can be described as selecting a design within the design space that optimizes the post-processing performance metric 190, possibly subject to certain constraints (e.g., limits on certain costs 170). The optical subsystem 110 and the digital image processing subsystem 130 are designed together, rather than sequentially as is the case in conventional design approaches. Mathematically, using the notation of FIG. 1, the design step can be described as selecting the system parameters θo, θd and θi to directly optimize the performance metric, possibly subject to certain constraints on the costs 170. For example, an image-based post-processing performance metric 190 may be optimized subject to a maximum financial cost. Alternately, the financial cost may be minimized subject to some minimum acceptable post-processing performance metric 190 for the digital image 180.
A number of optimization algorithms can be used. For some linear cases, parameters may be solved for analytically or using known and well-behaved numerical methods. For more complicated cases, including certain nonlinear cases, techniques such as expectation maximization, gradient descent and linear programming can be used to search the design space.
Note that in both FIGS. 1 and 2, there is no requirement for the optical subsystem 110, the detector subsystem 120 or the digital image processing subsystem 130, taken alone, to be optimal. It is quite possible for these subsystems to exhibit less than optimal performance when considered alone, while the overall electro-optic imaging system 100 still exhibits good or even optimal performance. This is in direct contrast to conventional design methods where, for example, the optical subsystem 110 typically is designed by directly optimizing the image quality of the intermediate optical image formed by it. For example, the optical subsystem 110 may be designed based directly on minimizing the RMS wavefront error or the RMS spot size. In contrast, for the design approach of FIG. 2, the intermediate optical image formed by the optical subsystem 110 may have worse image quality (e.g., as measured by wavefront error or spot size), which is then corrected by the digital image processing subsystem 130. The optical subsystem 110 is not designed based directly on improving the image quality of the intermediate optical image. Rather, it is designed jointly with the digital image processing subsystem 130, based directly on optimizing the post-processing performance metric 190.
FIG. 3 is a block diagram illustrating one software implementation based on commercially available lens design programs, such as Zemax. These programs typically have ray tracing capability 310 as well as optimization capability 320. In a conventional lens design, the designer would first identify the potential design space for the lens system by entering a description of the lens design problem. This description typically would include source points to be ray traced and a general description of the lens system (curvatures, thicknesses, spacings, etc.) as well as which lens design parameters are to be iterated. The ray tracing module 310 would trace rays from the source points through the lens system to the image plane. The optimization module 320 would iterate on the optical design parameters in order to directly optimize some cost function, typically the OPD-RMS, subject to other design constraints (minimum edge thicknesses, edge spacings, etc).
The implementation of FIG. 3 takes advantage of the built-in ray tracing and optimization functions, but replaces the wavefront error function with a post-processing performance metric 330 that takes into account the entire electro-optical system. Specifically, the output of the ray tracing module 310 is the OTF of the optical subsystem (or information that can be used to calculate the OTF) for several locations across the image field. In this example, the OTF is spatially-varying and approximated by interpolation between grid points. This same approach can be used for spatially-varying point spread functions or MTFs. Module 330 receives the MTF information as one input. It also uses the spatial model of the source (which typically will be different than the source points used in the ray tracing), and information about the detector subsystem and digital image processing subsystem to model propagation of the source through the electro-optic imaging system.
The post-processing performance metric module 330 may have self-contained loops or optimizations. For example, a different digital image processing subsystem may be designed for each new OTF and this process may or may not be iterative. Module 330 outputs the post-processing performance metric, which is used by the optimization module 320 to iterate the design of the optical subsystem. Note that the design of the digital image processing subsystem changes as the design of the optical subsystem changes. Different image processing is used to compensate for different errors introduced by different optical subsystems. Thus, the optical subsystem and the digital image processing subsystem are jointly designed based on the post-processing performance metric. For example, the design software may generate linear filter coefficients, as well as the final optical subsystem design.
FIG. 3 is just one example implementation, which is driven primarily by the availability of ray tracing and optimization modules 310 and 320 in commercially available lens design programs. Other implementations will be apparent. For example, in an alternate embodiment, the software architecture is based on the block diagram of FIG. 1. One software module implements the spatial model of the source 150. Other modules implement propagation of the source through the various subsystems 110, 120 and 130. These propagation modules receive the current system parameters and cost functions as inputs. Another module receives the simulated digital image 180 and ideal image 155 as inputs, and calculates the post-processing performance metric 190 based on them. This is used to iterate the system parameters.
System Model in the Continuous Domain
FIG. 4 is a block diagram illustrating one approach to calculating the performance metric 330 of FIG. 3. This approach is based on the following model of the electro-optic imaging system. The optical subsystem is characterized by a geometric measure of optical aberrations. Computing these quality measures involves tracing small sets of rays through the optical subsystem and computing a single number which measures the geometric deviation of these rays from those by a perfect optical system. The most common geometric measure is based on the optical path difference (OPD) between an ideal reference sphere and the actual wavefront at the exit pupil of the optical subsystem. This is known as the wavefront error function. This function, Φ(r, φ), can be expressed in polar coordinates with normalized radius, that is, Φ: [0, 1]×[0, 2π]→C. Typically, this wavefront error function is sampled using a small set of rays traced through the optical subsystem and combined using an L2 norm. This figure of merit is referred to as the OPD-RMS. Computation of this optical figure of merit can be extremely efficient given that most field locations require tracing fewer than 20 rays per field location.
The diffraction integral is based on the pupil function, G(r, φ), defined as

G(r,φ)=A(r,φ)exp(iΦ(r,φ))  (1)

where A is the (non-negative) transmission function. For typical optical subsystems, the pupil function is an unobstructed pupil and thus we set A to be constant=1. For the remainder of this example, we consider G(r, φ)=exp(iΦ(r, φ)).

Applying a Fourier transform operator F to the pupil function performs the Fraunhofer approximation to the diffraction integral producing the complex-amplitude point-spread function U:




  
    
      
        
          
            
              
                U
                ⁡
                
                  (
                  
                    u
                    ,
                    θ
                  
                  )
                
              
              =
              
              ⁢
              
                
                  F
                  ⁡
                  
                    (
                    G
                    )
                  
                
                ⁢
                
                  (
                  
                    u
                    ,
                    θ
                  
                  )
                
              
            
          
        
        
          
            
              =
              
              ⁢
              
                
                  1
                  π
                
                ⁢
                
                  
                    ∫
                    0
                    1
                  
                  ⁢
                  
                    
                      ∫
                      0
                      
                        2
                        ⁢
                        π
                      
                    
                    ⁢
                    
                      
                        G
                        ⁡
                        
                          (
                          
                            r
                            ,
                            φ
                          
                          )
                        
                      
                      ⁢
                      
                        exp
                        ⁡
                        
                          [
                          
                            2
                            ⁢
                            π
                            ⁢
                            
                              
                            
                            ⁢
                            i
                            ⁢
                            
                              
                            
                            ⁢
                            ru
                            ⁢
                            
                              
                            
                            ⁢
                            
                              cos
                              ⁡
                              
                                (
                                
                                  φ
                                  -
                                  θ
                                
                                )
                              
                            
                          
                          ]
                        
                      
                      ⁢
                      
                        d
                        r
                      
                      ⁢
                      
                        d
                        φ
                      
                    
                  
                
              
            
          
        
      
    
    
      
        (
        2
        )
      
    
  




The intensity point-spread function (or simply PSF) is given by

PSF=|U|2  (3)

The modulation transfer function (MTF) is the absolute value of the optical transfer function (OTF) H, which is given by

H=F(PSF)  (4)

The OTF H is a measure of the contrast capability of the optical subsystem. Higher values of H correspond to higher contrast levels.

In one approach, the performance metric 330 is the predicted mean-square-error (MSE) of the final digital image. Assuming Wiener filtering, the predicted MSE is a function of the optical subsystem's OTF H, the signal's power spectral density (PSD) function Suu, and the noise power spectral density Snn. Given these three components, the final digital image error spectral density is given by




  
    
      
        
          
            S
            e
          
          ⁡
          
            (
            
              
                ω
                1
              
              ,
              
                ω
                2
              
            
            )
          
        
        =
        
          
            
              
                S
                uu
              
              ⁡
              
                (
                
                  
                    ω
                    1
                  
                  ,
                  
                    ω
                    2
                  
                
                )
              
            
            ⁢
            
              
                S
                nn
              
              ⁡
              
                (
                
                  
                    ω
                    1
                  
                  ,
                  
                    ω
                    2
                  
                
                )
              
            
          
          
            
              
                
                  
                  
                    H
                    ⁡
                    
                      (
                      
                        
                          ω
                          1
                        
                        ,
                        
                          ω
                          2
                        
                      
                      )
                    
                  
                  
                
                2
              
              ⁢
              
                
                  S
                  uu
                
                ⁡
                
                  (
                  
                    
                      ω
                      1
                    
                    ,
                    
                      ω
                      2
                    
                  
                  )
                
              
            
            +
            
              
                S
                nn
              
              ⁡
              
                (
                
                  
                    ω
                    1
                  
                  ,
                  
                    ω
                    2
                  
                
                )
              
            
          
        
      
    
    
      
        (
        5
        )
      
    
  




The quantity Se is a function of both the contrast capability of the optical subsystem (as reflected in H) and noise from the non-optical components (as reflected in Snn).

Computation of the predicted MSE is based on integrating the error spectral density function over the spectral bandwidth of the electro-optic imaging system. Since electro-optical imaging systems of interest typically have a digital sampling rate that is much lower than the diffraction limit, the error Se(ω1, ω2) normalized by the diffraction limit D of the optical subsystem, is integrated only over the region where |ω1|<u, |ω2|<u, where u is the Nyquist frequency of the detector subsystem. The ratio T=u/D is also called the undersampling factor of the system. The final MSE figure of merit is defined as




  
    
      
        
          M
          ⁢
          
            
          
          ⁢
          S
          ⁢
          
            
          
          ⁢
          
            E
            ⁡
            
              (
              u
              )
            
          
        
        =
        
          
            1
            
              2
              ⁢
              π
            
          
          ⁢
          
            
              ∫
              
                
                  
                  
                    ω
                    ⁢
                    
                      
                    
                    ⁢
                    1
                  
                  
                
                <
                u
              
            
            ⁢
            
              
                ∫
                
                  
                    
                    
                      ω
                      ⁢
                      
                        
                      
                      ⁢
                      2
                    
                    
                  
                  <
                  u
                
              
              ⁢
              
                
                  
                    S
                    e
                  
                  ⁡
                  
                    (
                    
                      
                        ω
                        1
                      
                      ,
                      
                        ω
                        2
                      
                    
                    )
                  
                
                ⁢
                
                  d
                  
                    ω
                    1
                  
                
                ⁢
                
                  d
                  
                    ω
                    2
                  
                
              
            
          
        
      
    
    
      
        (
        6
        )
      
    
  




This MSE is then optimized relative to the design space of the optical subsystem, which implicitly also optimizes the digital image processing subsystem.

Traditional Discretization of the Continuous System Model
The calculation of the MSE, starting with ray tracing and following through the continuous model given by Eqns. 1-6, is typically implemented by a computer using discretized versions of Eqns. 1-6. The wavefront error function Φ is sampled at selected locations on the exit pupil through which rays are traced by ray tracing software. Once the wavefront error function values are available at those pupil locations the Fourier transform of the pupil function values is computed. In a conventional implementation of this step, the Fourier transform operator is substituted by the discrete Fourier transform (DFT) and implemented using a conventional FFT algorithm. However, in order to apply the conventional FFT algorithm to calculation of the complex-amplitude point spread function (see Eqn. 2), pupil function values must be made available on an N×N regular, rectangular grid. The sampling grid is regular in the sense that, along each dimension, the spacing between two adjacent samples is always the same, although the sample-to-sample spacing may be different in the x and y directions. Usually, the sample-to-sample spacing is the same in the x and y directions, so the sampling grid would be a regular square grid. For example, a commonly used setting might sample the pupil on a regular square grid of size N=64. In order to compute the FFT without aliasing, the N×N pupil function values are zero-padded by a factor of 2 in each dimension. As a result, samples of the complex-amplitude point spread function are obtained on a 2N×2N square grid (e.g. 128×128 grid).
In order to compute the OTF, typically no zero-padding of the intensity PSF is performed before applying the conventional FFT to the PSF. As a result, OTF samples on a 2N×2N square grid are obtained. The discretization of the integration over the Wiener filter error estimate Se is performed via approximation by numerical integration using the rectangle rule with rectangle width equal to 1/N for all values of Tε(0, 1]. For example, the Wiener filter error Se may be computed on a 128×128 grid. Subsequently, the numerical integration via rectangle rule is performed over the samples in the grid interval [−B, B]2 with B=TN.




  
    
      
        
          M
          ⁢
          
            
          
          ⁢
          S
          ⁢
          
            
          
          ⁢
          E
        
        =
        
          
            
              (
              
                2
                ⁢
                TN
              
              )
            
            
              -
              2
            
          
          ⁢
          
            
              ∑
              
                
                  
                    -
                    B
                  
                  ≤
                  n
                
                ,
                
                  m
                  ≤
                  B
                
              
            
            ⁢
            
              
                S
                e
              
              ⁡
              
                (
                
                  n
                  ,
                  m
                
                )
              
            
          
        
      
    
    
      
        (
        7
        )
      
    
  




Using regular rectangular grids at all sampling steps in the system model enables the use of the conventional FFT in computing the MSE, but results in the following bottlenecks. First, Eqn. 2 calls for the Fourier transform of the pupil function G, which depends on the wavefront error function Φ. If the conventional FFT is used to compute this Fourier transform, then G and Φ must be sampled on a regular rectangular grid of a certain density and extent in order to achieve sufficient sampling for later functions. The total number of sample points required can be fairly high. The wavefront error function Φ is determined by ray tracing. Requiring a large number of samples of Φ on a regular rectangular grid requires tracing a large number of rays, which is computationally expensive.
Second, for low-resolution sensors (e.g., u<0.2), the approximation of the integral of Eqn. 6 via the rectangle rule can require a large number of PSF samples in order to achieve acceptable accuracy. This, in return, requires many samples of Φ and corresponding amounts of ray tracing.
More Efficient Discretization of the Continuous System Model
FIG. 4 uses a different, more computationally efficient discretization of the continuous system model given by Eqns. 1-6. Use of the conventional FFT requires the use of regular rectangular sampling grids in both the space and (spatial) frequency domains, and dictates a specific relationship between the extent of the sampling grid in the space domain and the corresponding sample spacing in the frequency domain. For example, if N×N square grids are used and the sample spacing is Δx and Δy in the space domain, then this dictates that the sample spacing will be a specific Δp and Δq in the frequency domain and the extent of the sampling grid will be NΔp×NΔq (where p and q are the spatial frequency coordinates). If a different sample spacing or sample extent is desired in the frequency domain, corresponding changes must be made in the space domain in order to use the conventional FFT.
Instead of requiring sampling grids based on the conventional FFT for all sampling operations, FIG. 4 adds flexibility to the sampling operations by allowing grids of different topology at various locations in the system model. One advantage of this added flexibility is to adapt the sampling topology to the subsystem parameters such as optical aberrations or sensor characteristics. Since the acceptable grid topologies will not necessarily form regular rectangular grids of the correct sample spacing or sample extent, applying the conventional FFT algorithm to propagate source information from the original optical source to the final digital image may no longer be the most computationally efficient.
In the following example, conventional FFT operations are replaced by nonequidistant FFT (nFFT) operations. A nonequidistant FFT uses a fast algorithm for calculation for the discrete Fourier transform, but the samples in the space domain and/or in the frequency domain are not all equally spaced. Consider a one dimensional example. In the equidistant (or conventional) FFT, assume K space domain samples at a sample spacing of Δx. Thus, the actual sample locations might be x=0, Δx, 2Δx, . . . (K−1)Δx. Recall also that the FFT is based on a periodic function with period (or sample extent) of Tx=KΔx. Thus, the space domain samples are all equidistant, including accounting for the periodicity. That is, the sample spacing is constant between the 0th sample to the 1st sample, the 1st sample to the 2nd sample, and so on all the way including the sample spacing between the (K−1)st sample to the Kth (0th) sample. The corresponding frequency domain period (or sample extent) Tp is determined by Tx. The frequency domain samples must then have a sample spacing of Δp=Tp/K. This sample spacing yields equally spaced samples in the frequency domain.
In the nFFT, the sampling requirements for the conventional FFT are not met. For example, the frequency domain samples may be spaced by δp≠Δp. If there are K samples, then the sample extent in the frequency domain is K δp≠Tp. In this situation, the frequency domain sampling will be described as on a regular grid, but the samples are not equidistant since the distance from the 0th to the 1st sample is not the same as the distance from the (K−1)st sample to the Kth sample. In another example, the frequency domain samples may be on an irregular grid. For example, the distance from the 0th to the 1st sample may be different than from the 1st to the 2nd sample. The general case where the sampling requirements for the conventional FFT are not met will be referred to as the nonequidistant DFT. The nDFT includes both the case where a fast algorithm is used (nFFT) and not.
Referring to FIG. 4, steps 410, 422 and 432 show the non-traditional sampling:

    
    
        Step 410 determines sampling for pupil sampling (i.e., ray tracing), which in this example uses an L×K sampling that is not regular, rectangular sampling
        Step 422 determines sampling for computation of the PSF, which in this example uses an N*×N* square sampling
        Step 432 determines sampling for computation of Se(ω1, ω2) and MSE, which in this example uses 2p×p sampling
    
    


The introduction of flexible sampling topologies allows one to choose sampling topologies that better match system characteristics, such as choosing a polar grid for OPD sampling or a quadrature grid for Se sampling. A direct consequence is that fewer rays typically must be traced compared to the traditional high-resolution rectangular grid. Less ray tracing means faster execution time. In some numerical experiments that have been performed, tracing approximately 240 rays using the flexible sampling described below yields the same MSE accuracy as tracing 4096 rays using the traditional high-resolution rectangular sampling. This leads to a speed-up by a factor of 20.
In more detail, steps 410-416 concern sampling the pupil function G. The pupil sample locations are determined 410. In FIG. 4, the sample locations are an L×K array of samples. Rays are traced 412 through the selected pupil locations. Based on the ray trace, wavefront error function Φ is calculated 414. The pupil function G is then determined 416 based on Eqn. 1 above.
At this point, the pupil function G is sampled at the L×K locations. In FIG. 4, the PSF is determined on a regular square grid, so the L×K samples of the pupil function are interpolated 420 to yield values of the pupil function G on an N×N regular, square grid. An appropriate value for N depends on the complexity of the optical design. It should be large enough so that diffraction effects are represented in the PSF computed from the N×N samples. In the numerical experiments described below, N typically was at least 64.
In step 422, the N*×N* regular square sampling grid for the PSF is determined. The complex-amplitude point spread function, sampled on an N*×N* grid, is then calculated from the pupil function G, sampled on an N×N grid, using the nFFT 424. This is the discrete form of Eqn. 2. Both the N×N and N*×N* grids are regular square grids, but the sample spacing does not meet the requirements for the conventional FFT. The amplitude squared operator 430 implements Eqn. 3 to yield the PSF, sampled on an N*×N* grid. Unlike the traditional approach, N and N* are not constrained by a conventional FFT relationship. Instead, N* can be more freely selected. N* typically can be less than or equal to N. In one approach, N* is set equal to N. In many cases, the spread of the PSF is contained in a smaller area so N* can be set much lower. Setting, N*=N/2 yielded good results in the numerical experiments below.
In step 432, the 2p×p sampling for Se is determined. This formulation takes advantage of the fact that the integrand Se is a symmetric function. Therefore, computing the quadrature on one half-plane is sufficient. The symmetry is caused by the PSF being real and the OTF being the Fourier transform of a real function, which is symmetric, and by the other quantities Suu, and Snn, also being modeled as symmetric. The nFFT implements Eqn. 4, calculating 2p×p samples of the OTF H based on N*×N* samples of the PSF. Eqn. 5 (calculation of Se) is implemented in step 440 and Eqn. 6 (calculation of MSE) in step 450. In this particular example, quadrature-type numerical integration is used, which determines the 2p×p sampling. The value of p depends on the smoothness of the integrand function Se, If Se can be well approximated by a polynomial of order 2p, then p nodes in Gauss quadrature are sufficient.
Now consider selection of the different samplings. Some of the following samplings are benchmarked against a singlet design:

    
    
        F/4.6
        Thickness of surface 1 in the range 0 to 3 mm, sampled at 25 equally spaced locations.
        Curvature on surface 2 in the range −0.1 to 0.1 (inverse mm), sampled at 25 equally spaced locations.

The Zemax design software outputs the four Seidel aberrations astigmatism, coma, spherical aberration, and field curvature for this design. Data generated initially from a sampling of the pupil at high resolution serves as ground truth data. For this the sampling size in one dimension N is set to 256 or 64. Applying the traditional sampling approach to this starting resolution, the PSF and the error estimate Se are then both evaluated on a 2N×2N grid.

    
    


Sampling of the Pupil Function
The wavefront error function can usually be well approximated in the continuous domain by only a few Seidel aberration terms forming a polynomial of lower order. Therefore, we sample the pupil at selected locations and interpolate the values at the grid locations from those given samples instead of directly applying ray tracing to all of the N×N square grid locations. Due to the representation of Seidel aberrations as polynomials in radius and angle, in this example, we use a polar grid restricted to a few rings and arms.
Since most of the Seidel aberrations are of order of at least 2 in r, it is recommended to sample the radial direction at rl=tl2 where tl=l/L is an equally spaced sampling of the interval [0, 1] for L+1 samples, l=0, . . . , L. In the presence of very high coma, it may be better to change to a linear sampling, i.e. rl=tl. The angular domain is sampled linearly as θk=2πk/K for K samples, k=0, . . . , K−1.
Following the sampling, bilinear interpolation is performed to compute approximate wavefront error values at square grid locations. This forms the basis of the pupil function approximation.
In order to assess the accuracy of a particular sampling scheme, the wavefront error function is evaluated for each location in the aberration space A of the benchmark design. This aberration space includes the four aberrations astigmatism, coma, spherical aberration, and field curvature. Defocus is added to this set. Given a set of undersampling factors {0.05, 0.1, 0.15, 0.2, 0, 25, 0, 3, 0.35, 0.4, 0.45, 0.5}, a range of defocus [−6, 1] is determined experimentally from the ground truth data that contains the globally optimal MSE solutions for all undersampling factors. The wavefront error function computed via ray tracing to all locations of an n×n square grid is denoted by OPDn×n. In contrast, the wavefront error function computed via ray tracing at all the locations of the L×K polar grid and then interpolated to an n×n square grid is denoted by OPDL×K→n×n.
As a first step, a distance between OPD values for different sampling strategies is defined. For the ground truth MSE values J, the location w* of the global minimum of the MSE merit function is determined as

w*=argminwεAJ(w)  (8)

The defocus component of w* is denoted by w20*, and an epsilon neighborhood around that component defined as ε(w20*). In the experiments presented here, the size for the neighborhood, in terms of samples on a regular rectangular grid of size 25×25, is set to ε=4.

For each location w in the 5-dimensional aberration space A, the L2 error between the sampled OPD values of the ground truth data and the sampling strategy under test is computed as

dOPD[K,L,n](w)=∥OPDn×n(w)−OPDL×K→n×n(w)∥L2  (9)

The distance of OPD values over the entire design space is now defined as





  
    
      
        
          
            
              d
              A
            
            ⁡
            
              [
              
                K
                ,
                L
                ,
                n
              
              ]
            
          
          ⁢
          
            (
            
              
                O
                ⁢
                
                  
                
                ⁢
                P
                ⁢
                
                  
                
                ⁢
                
                  D
                  
                    n
                    ×
                    n
                  
                
              
              ,
              
                O
                ⁢
                
                  
                
                ⁢
                P
                ⁢
                
                  
                
                ⁢
                
                  D
                  
                    L
                    ×
                    
                      K
                      ⟶
                      n
                    
                    ×
                    n
                  
                
              
            
            )
          
        
        =
        
          
            ∫
            Ω
          
          ⁢
          
            
              ∫
              
                ∈
                
                  (
                  
                    w
                    20
                    *
                  
                  )
                
              
            
            ⁢
            
              
                
                  
                  
                    
                      O
                      ⁢
                      
                        
                      
                      ⁢
                      P
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          D
                          
                            n
                            ×
                            n
                          
                        
                        ⁡
                        
                          (
                          
                            w
                            ,
                            
                              w
                              20
                            
                          
                          )
                        
                      
                    
                    -
                    
                      O
                      ⁢
                      
                        
                      
                      ⁢
                      P
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          D
                          
                            L
                            ×
                            
                              K
                              ⟶
                              n
                            
                            ×
                            n
                          
                        
                        ⁡
                        
                          (
                          
                            w
                            ,
                            
                              w
                              20
                            
                          
                          )
                        
                      
                    
                  
                  
                
                
                  L
                  2
                
              
              ⁢
              
                d
                
                  w
                  20
                
              
              ⁢
              
                d
                w
              
            
          
        
      
    
    
      
        (
        10
        )
      
    
  




where Ω is the aberration subspace containing only the four Seidel aberrations and not defocus. The restriction of the defocus dimension to a neighborhood around the optimal location is performed since the location varies with the undersampling factor, and integration over the entire defocus interval would, therefore, lead to some bias. In essence, the approximation error is captured in a neighborhood around the position of optimal focus. The distance measure dA is used to measure the approximation accuracy of the wavefront error. We base dA on OPD values since OPD is a well understood measure of aberration strength in the optical design community.

In a second step the following distance measure between MSE values is introduced.




  
    
      
        
          
            
              d
              J
            
            ⁡
            
              [
              
                K
                ,
                L
                ,
                m
                ,
                nT
              
              ]
            
          
          ⁢
          
            (
            
              M
              ⁢
              
                
              
              ⁢
              S
              ⁢
              
                
              
              ⁢
              
                E
                
                  
                    n
                    ×
                    n
                  
                  ,
                
              
              ⁢
              M
              ⁢
              
                
              
              ⁢
              S
              ⁢
              
                
              
              ⁢
              
                E
                
                  L
                  ×
                  
                    K
                    ⟶
                    m
                  
                  ×
                  m
                
              
            
            )
          
        
        =
        
          
            [
            
              
                
                  
                    
                      
                        ∫
                        Ω
                      
                      ⁢
                      
                        ∫
                        
                          ∈
                          
                            (
                            
                              w
                              20
                              *
                            
                            )
                          
                        
                      
                    
                    ❘
                    
                      
                        M
                        ⁢
                        
                          
                        
                        ⁢
                        S
                        ⁢
                        
                          
                        
                        ⁢
                        
                          E
                          
                            n
                            ×
                            n
                          
                        
                        ⁢
                        
                          (
                          
                            w
                            ,
                            
                              w
                              20
                            
                          
                          )
                        
                      
                      -
                    
                  
                
              
              
                
                  
                    M
                    ⁢
                    
                      
                    
                    ⁢
                    S
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        
                          E
                          
                            L
                            ×
                            
                              K
                              ⟶
                              m
                            
                            ×
                            m
                          
                        
                        ⁡
                        
                          (
                          
                            w
                            ,
                            
                              w
                              20
                            
                          
                          )
                        
                      
                      2
                    
                    ⁢
                    
                      d
                      
                        w
                        20
                      
                    
                    ⁢
                    
                      d
                      w
                    
                  
                
              
            
            ]
          
          0.5
        
      
    
    
      
        (
        11
        )
      
    
  




The two measures dA and dJ evaluate the differences between OPD and MSE values obtained via different sampling strategies averaged over the entire singlet design space restricted around the optimal defocus location and are, therefore, reasonable global approximations.

FIGS. 5 and 6 show results using these two error measures for a field location of h=0.95. In FIG. 5, OPD differences are measured via dA[K, L, n] for n=64 and various polar grids L=2, . . . 10, K=4, . . . 32. In FIGS. 6A and 6B, MSE differences measured via dJ[K, L, m, n, T] are computed for different polar grids determined by pairs (L, K), L=2, . . . 10, K=4, . . . 32; a selection of undersampling factors T=0.1, 0.25, 0.5; and different square-grids of size n×n. In FIG. 6A, n=64 and n=256 in FIG. 6B. The variable N reflects the total number of rays to be traced for the polar grid sampling and is computed as

N=L·K  (12)

The graph of FIG. 5 shows that the pupil function error is less than 1/10 wave OPD-RMS at N/4=60. The graphs in FIG. 5 suggest that tracing N=240 rays through a polar grid is enough to obtain an acceptable error of approximately 0.1 waves in the OPD approximation.
The MSE measures dJ in FIG. 6 for undersampling factors of T=0.1, 0.25, 0.5 seem to be well correlated with the OPD measure. Some differences between a square grid resolution of 64×64 and 256×256 are noticeable, e.g. for T=0.1 the values for grid resolution of 64×64 seem to be larger in general, but the correlation with the OPD values does not change. Based on this observation, we use a square grid of 64×64 for ground truth data generation in the following sections.
A general rule of thumb in traditional optical design is that the Peak-to-Valley OPD should be ≦1⁄4λ which should be 3-5 times the OPD-RMS. The P-V OPD of ≦1⁄4 is correlated with a Strehl ratio of 0.80. This rule of thumb is applied to optical designs used in a variety of areas such as astronomy (microscopes) and microlithography. Therefore, an OPD-RMS value of ≦0.1λ seems to certainly fulfill the design criteria for optical image quality for a JOIPO system. Smaller values for L and K may lead to decreased accuracy. However, it depends on the purpose of the overall design what level of accuracy is acceptable. For example, in an initial design phase it may be acceptable to perform the optimization to an accuracy level of OPD difference of ≦0.5λ from ground truth data, but once an initial design has been determined, fine-tuning of the design can be performed by increasing the accuracy level and setting the OPD error threshold to 0.1λ
The above example is based on polar sampling. However, other sampling schemes can also be used, for example linogram sampling.
Interpolation of the Pupil Function onto Rectangular Grid
In order to allow for accurate computations of the Fourier transform of the pupil function samples, an interpolation from the selected pupil sampling grid values to values on a grid with higher sampling resolution in a neighborhood of the boundary of the pupil may be necessary. In one embodiment, the pupil sampling grid values are interpolated to a regular square grid of size N=64. Interpolation may be performed via linear interpolation on triangles using barycentric coordinates or bilinear interpolation on trapezoids, for example.
Sampling of the Point Spread Function (PSF)
The PSF is defined in the spatial domain. Even though in theory the support of the PSF for a diffracted optical system in the continuous model is infinite, in the discretized case the approximated PSF function has finite support. In FIG. 4, that support is included in an interval of N*×N* samples, typically centered at the origin of the PSF. The size N* depends on the magnitude and characteristics of the aberrations, for example by the locations where the marginal and chief rays hit the image plane or from the ray fan diagram. In the traditional approach, the PSF is sampled on a 2N×2N grid, where N was the size of the regular square grid that was used for pupil sampling. The flexible approach reduces the number of samples of the PSF, thus leading to decreased computational complexity.
Sampling and Integral Approximation of MSE
In the traditional approach, the Wiener filter error estimate is oversampled. Values of Se are computed via FFT at frequency locations equally spaced in the interval [−1, 1]2. For an undersampling factor of T<1 however, integration of Se takes place only over a subinterval [−T, T]2⊂[−1, 1]2. That means not all frequency locations evaluated by the FFT are needed in the integration. Furthermore, for small undersampling factors, it is not clear whether the uniform discretization of the frequency locations by the FFT provides enough samples in the small interval [−T, T]2 to accurately estimate the MSE error. Accuracy of numerical integration can be controlled by applying a quadrature-type integration method. The general concept of numerical integration via quadrature is to approximate the integral over a function ƒ as a finite sum of weighted function values of ƒ at certain locations.




  
    
      
        
          
            ∫
            a
            b
          
          ⁢
          
            
              f
              ⁡
              
                (
                x
                )
              
            
            ⁢
            
              d
              x
            
          
        
        ≈
        
          
            ∑
            
              k
              =
              1
            
            p
          
          ⁢
          
            
              w
              k
            
            ⁢
            
              f
              ⁡
              
                (
                
                  x
                  k
                
                )
              
            
          
        
      
    
    
      
        (
        13
        )
      
    
  




The locations xk are called nodes and the parameters wk are the weights of the quadrature. p is called the order of the quadrature. If the integrand can be written as ƒ(x)=g(x)W(x) where g(x) is approximately polynomial and W(x) is known, then the nodes are linked to zeros of certain orthogonal polynomials. The most popular type of quadrature is Gauss quadrature. In this case W(x)=1, [a, b]=[−1, 1], and the nodes are zeros of Legendre polynomials being independent of the integrand function ƒ. The accuracy of the approximation depends on the smoothness of the function ƒ. If ƒ is a polynomial of order 2p, then a Gaussian quadrature of order p is enough to represent the integral exactly.
When trying to apply the quadrature approach to the integration of Se, note that the integrand is not a very smooth function. The MTF function |H| is continuous, but may not be everywhere differentiable. Therefore, we cannot expect that a low order quadrature will give acceptable results. Experimentally we investigated what order of a polynomial approximation of Se yields acceptable results. For field point h=0.95 and T=1 we picked a location w with w20=−2.75, wastig=1.4089, wcoma=−1.2602, wspherical=1.5578, wfc=2.7198 near the global minimum location of the MSE merit function and determined experimentally by visual inspection that a polynomial of order 26 seems to provide an acceptable fit.
FIG. 7 plots a one-dimensional cut through the Se values for the example location in aberration space. The curve 700 represents the computed signal Se(ω1, 0) and the curves 710, 720 and 726 represent polynomial fits of orders 10, 20 and 26 respectively. The order 20 and 26 fits match the computed signal well. Fitting Se with a polynomial over the entire square [−1, 1]2 did not give very good results due to strong even symmetry properties of Se. From these experimental results, a quadrature approximately of order 13=26/2 should produce acceptable results in the numerical integration. Note that in this example Se is a function with axial symmetry around at least one of the axes caused by the fact that the PSF is a real-valued function.
Assuming we want to perform integration via quadrature, we need to evaluate the integrand function at the quadrature node locations. These locations may differ from the ones provided by the FFT. To solve this problem we apply the nonequidistant DFT (nDFT) to the PSF in order to compute the OTF at the quadrature node locations. The nDFT may be implemented by a nonequidistant FFT, which may be based on FFT(s) followed by interpolation.
In general the numerical approximation of the 2-dimensional MSE merit function is defined as follows




  
    
      
        
          M
          ⁢
          
            
          
          ⁢
          S
          ⁢
          
            
          
          ⁢
          
            E
            ⁡
            
              [
              T
              ]
            
          
        
        ≈
        
          
            ∑
            j
          
          ⁢
          
            
              ∑
              k
            
            ⁢
            
              
                u
                
                  j
                  ,
                  k
                
              
              ⁢
              
                
                  S
                  e
                
                ⁡
                
                  (
                  
                    
                      ω
                      
                        1
                        ,
                        j
                        ,
                      
                    
                    ⁢
                    
                      ω
                      
                        2
                        ,
                        k
                      
                    
                  
                  )
                
              
            
          
        
      
    
    
      
        (
        14
        )
      
    
  




with ω1,j,ω2,k being sampling locations in the interval [−TN, TN]. As examples, consider the following different strategies related to numerical integration and quadrature. Without loss of generality, we describe the different approximation techniques in the following over the first quadrant [0, T]×[0, T] only. FIGS. 8A-8C shows the sampling grids for the numerical integration techniques described below, for order p=16.

Traditional: Rectangle rule, sampled on a regular rectangular grid. The traditional approach uses FFTs to compute Se at frequency locations on an equally spaced square grid. The integral is approximated using the rectangle rule. The integration restricted to the first quadrant is approximated as follows.




  
    
      
        
          J
          ⁢
          
            
          
          ⁢
          M
          ⁢
          
            
          
          ⁢
          S
          ⁢
          
            
          
          ⁢
          
            E
            ⁡
            
              [
              T
              ]
            
          
        
        ≈
        
          
            ∑
            
              j
              =
              0
            
            p
          
          ⁢
          
            
              ∑
              
                k
                =
                0
              
              p
            
            ⁢
            
              
                q
                j
              
              ⁢
              
                v
                k
              
              ⁢
              
                
                  S
                  e
                
                ⁡
                
                  (
                  
                    
                      x
                      j
                    
                    ,
                    
                      y
                      k
                    
                  
                  )
                
              
            
          
        
      
    
    
      
        (
        15
        )
      
    
  




with node locations





  
    
      x
      j
    
    =
    
      
        j
        ⁢
        
          
        
        ⁢
        T
      
      p
    
  
  ,
  
    
      y
      k
    
    =
    
      kT
      p
    
  
  ,
  
    j
    =
    0
  
  ,
  ...
  ⁢
  
    
  
  ,
  p
  ,
  
    k
    =
    0
  
  ,
  ...
  ⁢
  
    
  
  ,
  p
  ,




and weights





  
    
      q
      j
    
    =
    
      
        v
        j
      
      =
      
        1
        
          p
          +
          1
        
      
    
  
  ,




where the size of p relates directly to the quality of the approximation and is called the order of the approximation. In the traditional approach, p is set to p=└N×T┘. FIG. 8A shows a square grid sampling.

Trapezoidal sampled on a regular rectangular grid. The integration accuracy can be improved by using the trapezoidal rule for integration. That means




  
    
      
        
          J
          ⁢
          
            
          
          ⁢
          M
          ⁢
          
            
          
          ⁢
          S
          ⁢
          
            
          
          ⁢
          
            E
            ⁡
            
              [
              T
              ]
            
          
        
        ≈
        
          
            ∑
            
              J
              =
              0
            
            P
          
          ⁢
          
            
              ∑
              
                K
                =
                0
              
              P
            
            ⁢
            
              
                q
                j
              
              ⁢
              
                v
                k
              
              ⁢
              
                
                  S
                  e
                
                ⁡
                
                  (
                  
                    
                      x
                      j
                    
                    ,
                    
                      y
                      k
                    
                  
                  )
                
              
            
          
        
      
    
    
      
        (
        16
        )
      
    
  




with node locations





  
    
      x
      j
    
    =
    
      
        j
        ⁢
        
          
        
        ⁢
        T
      
      p
    
  
  ,
  
    
      y
      k
    
    =
    
      kT
      p
    
  
  ,
  
    j
    =
    0
  
  ,
  ...
  ⁢
  
    
  
  ,
  p
  ,
  
    k
    =
    0
  
  ,
  ...
  ⁢
  
    
  
  ,
  p
  ,




and weights





  
    
      q
      j
    
    =
    
      
        v
        j
      
      =
      
        
          
            1
            p
          
          ⁢
          
            
              
            
            ⁢
            
              
            
          
          ⁢
          for
          ⁢
          
            
          
          ⁢
          j
        
        =
        1
      
    
  
  ,
  ...
  ⁢
  
    
  
  ,
  
    p
    -
    1
  
  ,
  
    
      q
      0
    
    =
    
      
        v
        0
      
      =
      
        1
        
          2
          ⁢
          p
        
      
    
  
  ,
  
    
      q
      N
    
    =
    
      
        v
        N
      
      =
      
        
          1
          
            2
            ⁢
            p
          
        
        .
      
    
  




FIG. 8A shows a square grid sampling.

Gauss quadrature. If the Gauss-Legendre quadrature is applied in each dimension separately then the integral is approximated by




  
    
      
        
          J
          ⁢
          
            
          
          ⁢
          M
          ⁢
          
            
          
          ⁢
          S
          ⁢
          
            
          
          ⁢
          
            E
            ⁡
            
              [
              T
              ]
            
          
        
        ≈
        
          
            ∑
            
              J
              =
              1
            
            P
          
          ⁢
          
            
              ∑
              
                K
                =
                1
              
              P
            
            ⁢
            
              
                q
                j
              
              ⁢
              
                v
                k
              
              ⁢
              
                
                  S
                  e
                
                ⁡
                
                  (
                  
                    
                      x
                      j
                    
                    ,
                    
                      y
                      k
                    
                  
                  )
                
              
            
          
        
      
    
    
      
        (
        17
        )
      
    
  




where p is the order of the quadrature; xj and yk, for j, k=1, . . . , p are the quadrature nodes; and qj, vk, for j, k=1, . . . , p are the quadrature weights. Since for a Gauss quadrature the nodes are not located on a regular rectangular grid, the values of the OTF cannot be calculated with a regular FFT, but a nonequidistant DFT (nDFT) can be used instead. FIG. 8B shows the quadrature nodes.

Gauss quadrature in radial trapezoidal rule in angular sampled on a modified polar grid. Due to the radial symmetry of the PSF it is useful to consider the polar representation of Se.




  
    
      
        
          
            ∫
            0
            T
          
          ⁢
          
            
              ∫
              0
              T
            
            ⁢
            
              
                
                  S
                  e
                
                ⁡
                
                  (
                  
                    
                      ω
                      1
                    
                    ,
                    
                      ω
                      2
                    
                  
                  )
                
              
              ⁢
              
                d
                
                  ω
                  1
                
              
              ⁢
              
                d
                
                  ω
                  2
                
              
            
          
        
        =
        
          
            ∫
            0
            
              π
              2
            
          
          ⁢
          
            
              ∫
              0
              
                r
                ⁡
                
                  (
                  
                    θ
                    ,
                    T
                  
                  )
                
              
            
            ⁢
            
              
                
                  S
                  e
                
                ⁡
                
                  (
                  
                    r
                    ,
                    θ
                  
                  )
                
              
              ⁢
              r
              ⁢
              
                d
                r
              
              ⁢
              
                d
                θ
              
            
          
        
      
    
    
      
        (
        18
        )
      
    
  




with ω1=r cos θ and ω2=r sin θ.

Since the sensor's geometric shape is usually a square rather than a circle, the quadrant preferably is sampled on a “modified polar grid” and not on a regular polar grid. The modified polar grid samples the entire rectangular quadrant, not just an angular segment. Therefore, the upper bound in the integration over the radius r depends on the undersampling factor T and the angle θ.
The angular integral is approximated by integration via the trapezoidal rule, whereas the Gauss-Legendre quadrature is applied to the radial integral.




  
    
      
        
          J
          ⁢
          
            
          
          ⁢
          M
          ⁢
          
            
          
          ⁢
          S
          ⁢
          
            
          
          ⁢
          
            E
            ⁡
            
              [
              T
              ]
            
          
        
        ≈
        
          
            ∑
            
              k
              =
              0
            
            p
          
          ⁢
          
            
              v
              k
            
            ⁢
            
              
                ∑
                
                  j
                  =
                  1
                
                p
              
              ⁢
              
                
                  q
                  r
                
                ·
                
                  r
                  j
                
                ·
                
                  
                    S
                    e
                  
                  ⁡
                  
                    (
                    
                      
                        x
                        jk
                      
                      ,
                      
                        y
                        jk
                      
                    
                    )
                  
                
              
            
          
        
      
    
    
      
        (
        19
        )
      
    
  




where p is the order of the quadrature; (xjk, yk), j=1, . . . , p, k=0, . . . , p are the nodes on the modified polar grid with xjk=rj sin θk, yjk=rj cos θk for





  
    θ
    k
  
  =
  
    
      
        k
        ⁢
        
          
        
        ⁢
        π
      
      
        2
        ⁢
        p
      
    
    ⁢
    
      
    
    ⁢
    and
  








  
    r
    j
  
  =
  
    {
    
      
        
          
            
              T
              ·
              
                1
                
                  cos
                  ⁢
                  
                    
                  
                  ⁢
                  
                    y
                    k
                  
                
              
            
            ,
          
        
        
          
            0
            ≤
            
              θ
              k
            
            ≤
            
              π
              4
            
          
        
      
      
        
          
            
              T
              ·
              
                1
                
                  cos
                  ⁡
                  
                    (
                    
                      
                        π
                        2
                      
                      -
                      
                        y
                        k
                      
                    
                    )
                  
                
              
            
            ,
          
        
        
          
            0
            ≤
            
              θ
              k
            
            ≤
            
              π
              2
            
          
        
      
    
    }
  




qj, j=1, . . . , p are the quadrature weights; and





  
    v
    k
  
  =
  
    
      k
      ⁢
      
        
      
      ⁢
      π
    
    
      2
      ⁢
      p
    
  




are the weights for integration via trapezoidal rule for





  
    k
    =
    1
  
  ,
  ...
  ⁢
  
    
  
  ,
  
    p
    -
    1
  
  ,
  
    
      v
      0
    
    =
    
      
        v
        p
      
      =
      
        π
        p
      
    
  




for the angular dimension. The values of Se at node locations (xjk, yjk) preferably are computed with an nFFT. FIG. 8C shows the locations of the quadrature nodes.

Accuracy. We numerically analyze the approximation properties of the various integration methods for one location in the aberration space of the benchmark design: wastig=1.4089, wcoma=−1.2602, wspherical=1.5578, wfc=2.7198 and field location h=0.95. This location is close to the optimal location for minimal MSE over the entire design space for that field location. The field location is chosen since it is close to one of the quadrature nodes used when integrating the merit function over the entire field of view.
For this aberration example, the MSE value is computed for T=0.2 and three focus locations w20ε{−6.0, −2.75, 1.0} using different orders p=4, 8, 12, 16, 32, 64 in the numerical integration, starting always with PSF values sampled on a 128×128 grid. The value w20=−2.75 is close to the optimal defocus location, whereas the other two values are at the boundary of the considered defocus interval [−6.0, 1.0]. FIGS. 9A-9C plot the results. FIG. 9A corresponds to w20=−6.0, FIG. 9B to w20=−2.75 and FIG. 9C to w20=1.0. In each of these figures, there are four curves, corresponding to traditional rectangular integration, trapezoidal, Gauss quadrature in two dimensions, and the Gauss-quadrature-trapezoidal method described above.
Ideally, the MSE values for a specific value of T computed for different orders p should be constant, i.e. should lie on a horizontal line. In all graphs diverging behavior for small orders of integration is visible. For the two focus locations away from the optimal one the methods using an equispaced grid show some erratic behavior at small values of p, whereas the quadrature methods yield a more consistent drop. For w20=−2.75 close to the optimal defocus location all methods seems to provide acceptable results even for small values of p, whereas for defocus location far away from the optimal one MSE values become unstable for small p. In general an order of p≧16 seems to produce stable results across all three defocus locations in this example.
FIG. 10 is a block diagram of a system illustrating user control over sampling. The system includes a user interface 1010 and a computation engine 1050. In one embodiment, these are implemented as software executing on a computer system. The computation engine 1050 includes different modules that implement the various computations. The pupil function module 1060 calculates the pupil function G. This is typically achieved by ray tracing the optical subsystem according to the selected pupil sampling scheme. The PSF module 1070 calculates the PSF from the pupil function G. The OTF module 1080 calculates the OTF from the PSF. The MSE module 1090 calculates Se and the Wiener filter-based MSE.
In FIG. 10, the various sampling schemes are determined by the user via user interface 1010. Using the example of FIG. 4, the user can set the L×K pupil sampling scheme, the N*×N* PSF sampling scheme and/or the 2p×p Se sampling scheme. There is an inherent tradeoff between accuracy and computation speed. Thus, the user may select coarser sampling during the initial design in order to iterate more quickly and then transition to denser sampling in order to fine tune the final design. In alternate embodiments, the sampling schemes may be adjusted automatically by the system, rather than the user.
Although the detailed description contains many specifics, these should not be construed as limiting the scope of the invention but merely as illustrating different examples and aspects of the invention. It should be appreciated that the scope of the invention includes other embodiments. Various other modifications, changes and variations which will be apparent to those skilled in the art may be made in the arrangement, operation and details of the method and apparatus of the present invention disclosed herein without departing from the spirit and scope of the invention as defined in the appended claims.

## Claims

1. A method for designing an electro-optic imaging system for imaging a source, the electro-optic imaging system including an optical subsystem, a detector subsystem and a digital image processing subsystem, the method comprising:
modeling propagation of the source through the optical subsystem, the detector subsystem and the digital image processing subsystem, said modeling comprising:
calculating a pupil function G for the optical subsystem, the pupil function sampled on a non-rectangular grid;

calculating a post-processing performance metric that is a function of the modeled propagation, the performance metric accounting for a contrast capability of the optical subsystem and for noise from the detector subsystem and/or the digital image processing subsystem; and
jointly designing the optical subsystem and the digital image processing subsystem based directly on the performance metric.

2. The method of claim 1 wherein calculating a pupil function for the optical subsystem comprises:
tracing rays through the optical subsystem, the rays sampling a pupil of the optical subsystem on the non-rectangular grid, wherein the pupil function is calculated from the traced rays.

3. The method of claim 2 wherein the rays sample the pupil of the optical subsystem on a polar grid.

4. The method of claim 2 wherein the rays sample the pupil of the optical subsystem on a linogram grid.

5. The method of claim 2 wherein the rays sample the pupil of the optical subsystem along radially extending arms, the rays distributed evenly with respect to distance along each arm.

6. The method of claim 2 wherein the rays sample the pupil of the optical subsystem along radially extending arms, the rays distributed evenly with respect to distance squared along each arm.

7. The method of claim 2 wherein fewer than 250 rays are traced for each sampling of the pupil, and the ray trace is sufficient to estimate a wavefront error function with an accuracy of better than λ/10.

8. The method of claim 2 wherein a sufficient number of rays are traced to estimate a wavefront error function with an accuracy of better than λ/10.

9. The method of claim 2 wherein calculating a pupil function for the optical subsystem further comprises:
calculating the pupil function sampled on a square grid, by interpolating from the non-rectangular grid to the square grid.

10. The method of claim 1 wherein modeling propagation of the source further comprises:
applying an nDFT to the pupil function to calculate a complex-amplitude point spread function U.

11. The method of claim 1 wherein modeling propagation of the source further comprises:
applying an nDFT to an intensity point spread function PSF to calculate an optical transfer function OTF.

12. The method of claim 1 wherein the post-processing performance metric is defined as an integral of an error metric that is a function of the modeled propagation and that accounts for a contrast capability of the optical subsystem and for noise from the detector subsystem and/or the digital image processing subsystem, and the integral is evaluated using a quadrature-type numerical integration.

13. The method of claim 1 wherein the post-processing performance metric is a Wiener filter-based mean square error (MSE).

14. The method of claim 13 wherein:
the steps of modeling propagation of the source through the optical subsystem, the detector subsystem and the digital image processing subsystem and calculating a post-processing performance metric consist essentially of:
tracing rays through the optical subsystem, the rays sampling a pupil of the optical subsystem on an L×K non-rectangular grid;
calculating a pupil function G sampled on an N×N square grid, based on the ray trace sampled on the non-rectangular grid, said calculating including interpolating from the non-rectangular grid to the square grid;
applying an nFFT to the pupil function G to calculate a complex-amplitude point spread function U sampled on an N*×N* square grid;
calculating an intensity point spread function PSF from the complex-amplitude point spread function U;
applying an nFFT to the intensity point spread function PSF to calculate an optical transfer function OTF sampled at nodes of a quadrature function;
calculating a digital image error spectral density Se from the optical transfer function OTF; and
calculating the Wiener filter-based MSE by numerically integrating the digital image error spectral density Se using a quadrature-type numerical integration; and

the step of jointly designing the optical subsystem and the digital image processing subsystem comprises:
iteratively designing the optical subsystem to minimize the Wiener filter-based MSE.

15. The method of claim 14 further comprising:
in response to user input, varying values of L, K, N and/or N* for different iterations.

16. The method of claim 14 further comprising:
automatically varying values of L, K, N and/or N* for different iterations.

17. The method of claim 14 further comprising:
increasing values of L, K, N and/or N* for later iterations.

18. A non-transitory computer readable storage medium containing instructions to cause a processor to design an optical subsystem of an electro-optic imaging system by executing the following steps:
modeling propagation of the source through the optical subsystem, the detector subsystem and the digital image processing subsystem, said modeling comprising:
calculating a pupil function for the optical subsystem, the pupil function sampled on a non-rectangular grid;
calculating a post-processing performance metric that is a function of the modeled propagation, the performance metric accounting for a contrast capability of the optical subsystem and for noise from the detector subsystem and/or the digital image processing subsystem; and
jointly designing the optical subsystem and the digital image processing subsystem based directly on the performance metric.

19. The non-transitory computer readable storage medium of claim 18 wherein:
the post-processing performance metric is a Wiener filter-based mean square error (MSE);
the steps of modeling propagation of the source through the optical subsystem, the detector subsystem and the digital image processing subsystem and calculating a post-processing performance metric consist essentially of:
tracing rays through the optical subsystem, the rays sampling a pupil of the optical subsystem on an L×K non-rectangular grid;
calculating a pupil function G sampled on an N×N square grid, based on the ray trace sampled on the non-rectangular grid, said calculating including interpolating from the non-rectangular grid to the square grid;
applying an nFFT to the pupil function G to calculate a complex-amplitude point spread function U sampled on an N*×N* square grid;
calculating an intensity point spread function PSF from the complex-amplitude point spread function U;
applying an nFFT to the intensity point spread function PSF to calculate an optical transfer function OTF sampled at nodes of a quadrature function;
calculating a digital image error spectral density Se from the optical transfer function OTF; and
calculating the Wiener filter-based MSE by numerically integrating the digital image error spectral density Se using a quadrature-type numerical integration; and

the step of jointly designing the optical subsystem and the digital image processing subsystem comprises:
iteratively designing the optical subsystem to minimize the Wiener filter-based MSE.

20. The non-transitory computer readable storage medium of claim 19 wherein the step of iteratively designing the optical subsystem comprises:
varying values of L, K, N and/or N* for different iterations.