Image analysis – Image transformation or preprocessing – Convolution
Reexamination Certificate
2000-01-11
2004-03-02
Patel, Jayanti K. (Department: 2625)
Image analysis
Image transformation or preprocessing
Convolution
C242S163000, C242S441000, C242S447000, C708S005000, C708S420000, C708S813000
Reexamination Certificate
active
06701028
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to signal processing methods and apparatus for performing convolution on data indicative of a pattern (e.g., image data indicative of a pixel array). In accordance with the invention, the convolution kernel is (or is approximated by) a spline function. Preferably the convolution kernel is (or is approximated by) a polynomial spline function that is piecewise a polynomial function.
BACKGROUND OF THE INVENTION
Convolution is commonly performed on signals in many contexts, including the fields of sound, still image, video, lithography, radio (radar) signal processing. Typically, the signals to be convolved are pattern signals. Each of the expressions “pattern” and “pattern signal” is used herein in a broad sense to denote a one-dimensional sequence or two-dimensional (or higher dimensional) array of data words (which can be, but need not be pixels). Typically, the data words comprise binary bits, and the convolution is performed in discrete fashion on the binary bits using software, digital signal processing circuitry, custom hardware, or FPGA systems (field programmable gate array based computing systems).
The term “data” herein denotes one or more signals indicative of data, and the expression “data word” herein denotes one or more signals indicative of a data word.
The motivations for implementing convolution rapidly, even when processing data indicative of very large patterns, are myriad. The present invention was motivated by the need for proximity correction in the field of lithography. In such problems, one attempts a two-dimensional convolution between data indicative of a large pattern “p” (where the pattern is a large one-dimensional or two-dimensional pixel array) and a diffusion kernel “d”. Often the kernel “d” is Gaussian or a superposition of Gaussians, or is otherwise a smooth kernel. More specifically, the present invention grew out of attempts to establish a suitable “O(N)” algorithm (an algorithm requiring not more than on the order of “N” multiplications and additions) for convolving a one-dimensional pattern comprising N pixels, where N is very large, with a Gaussian kernel (or other smooth kernel) such that the convolution is exact or very close to exact, or a suitable “O(NN′)” algorithm (an algorithm requiring not more than on the order of NN′ multiplications and additions) for convolving a two-dimensional pattern comprising NN′ pixels, where each of N and N′ is very large) with a Gaussian kernel (or other smooth kernel) such that the convolution is exact or very close to exact.
The objective in performing proximity correction (in the field of lithography) is to generate a “raw” optical signal (or “raw” electron beam signal) which can be input to a set of reflective or refractive optics (or electron beam optics), in order to project the output of the optics as a desired pattern on a mask or wafer. To determine the characteristics of a raw optical signal (or raw electron beam signal) that are needed to cause projection of the desired pattern on the mask or wafer, a deconvolution operation is typically performed on a very large array of pixels (which determine a pattern “p”) in order to correct for the well known proximity problem. In the case of electron beam lithography, the proximity problem results from electron scattering in the substrate (mask or wafer) being written. Such scattering exposes broadened areas on the substrate to electrons (i.e., an area surrounding each pixel to be written in addition to the pixel itself), with the scattering effectively broadening the electron beam beyond the beam diameter with which the beam is incident on the substrate.
In nearly all proximity correction schemes, such a deconvolution operation includes at least one convolution step. Accordingly, in performing typical proximity correction, a very large array of pixels (determining a pattern “p”) must be convolved with a diffusion kernel. Although such a convolution is typically performed on a pattern comprising a very large array of binary pixels, this restriction is not essential in the following discussion and is not essential to implement the invention. Indeed, the invention can implement convolution on data indicative of any pattern “p” (which can be large or small, and can be either one-dimensional, two-dimensional, or more than two-dimensional, and can be determined by binary or non-binary data values), using any smooth convolution kernel “d” having characteristics to be described below.
For a data indicative of a pattern “p” and a convolution kernel “d” we consider the cyclic convolution:
(
d
×
p
)
n
=
∑
i
+
j
=
n
(
mod
N
)
d
i
p
j
,
and an acyclic convolution which differs only in the indicial constraint and range:
(
d
×
A
p
)
n
=
∑
i
+
j
=
n
d
i
p
j
,
where “x
A
” denotes that convolution operator x has an acyclic character.
In one-dimensional cases (in which the pattern p is an ordered set of N data values and the kernel is an ordered set of M values), the result of the cyclic convolution has length N (it comprises N data values), and the result of the acyclic convolution has length M+N−1. Both one- and two-dimensional scenarios are of interest. In the case of a two-dimensional pattern “p” (i.e., a pattern determined by an N by N′ array of data values), the indices n, i, j and domain lengths N in the noted formulae are 2-vectors.
It is standard that the convolution d×p can be cast as an equivalent matrix-vector product:
d×p≡Dp,
where D is the circulant matrix of d (hereinafter the “circulant” of d), whose 1-dimensional form is defined as:
D
=
(
d
0
d
1
d
2
d
3
⋯
d
N
-
1
d
N
-
1
d
0
d
1
d
2
⋯
d
N
-
2
⋮
⋮
d
1
d
2
d
3
d
4
⋯
d
0
)
As will be shown later, conventional methods for convolution can be cast in the language of matrix algebra.
The central idea of the invention is to approximate a smooth kernel d by a polynomial spline kernel f (where f is a spline function f(x) which is piecewise a polynomial of degree &dgr; with M pieces f
i
(x)), and then to use appropriate operators that annihilate (or flatten) each polynomial of given degree (in a manner to be explained) to calculate the convolution of f and p quickly. In some embodiments, the smooth kernel d is approximated (in accordance with the invention) by a spline kernel f which is not a polynomial spline kernel, but which consists of M pieces defined over adjacent segments of its range (in typical two-dimensional cases, the latter spline kernel is a radially symmetric function whose range is some continuous or discrete set of values of the radial parameter). Though “spline” convolution in accordance with the invention has features reminiscent of conventional wavelet schemes and is an O(N) algorithm (as are wavelet schemes), an advantage of the inventive “spline” convolution is that it can be performed (on data indicative of a pattern p consisting of N data values) with cN arithmetic operations (multiplications and additions), whereas conventional wavelet convolution on the same data would require bN arithmetic operations, where the factor “b” is typically (i.e., with typical error analysis) significantly larger than the factor “c.” In other words, the implied big-O constant for the spline convolution is significantly smaller than the typical such constant for conventional wavelet convolution.
Other important advantages of the inventive spline convolution method will be discussed below. To better appreciate the advantages of the invention over conventional convolution methods, we next explain two types of conventional convolution methods: Fourier-based convolution and wavelet convolution.
As is well known, Fourier-based convolution is based on the elegant fact that if F is a Fourier matrix, say
F
jk
=e
−2&pgr;ijk/N
,
then the transformation FDF
−1
of the circulant is diagonal, whence we compute:
Dp=F
−1
(
F
Applied Materials Inc.
Kuo Jung-hua
Patel Jayanti K.
Tabatabai Abolfazl
LandOfFree
Method and apparatus for fast signal convolution using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for fast signal convolution using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for fast signal convolution using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3215258