US 5,907,628 AGrant
Apparatus and Method for Comparing and Aligning Two Digital Representations of an Image
Issue Date:1999-05-25
•9 Claims
•20 Drawing Sheets
Abstract
A method for comparing first and second digital representations of an image, the method comprising the steps of: for each individual translation from among a plurality of translations from the first digital representation to the second digital representation: for each individual image location from among a plurality of image locations within a comparison entity within the first digital representation, determining a binary legitimacy value of the individual translation for the individual image location by comparing the individual image location to a location in the second digital representation defined by operating the individual translation on the individual image location; and combining the binary legitimacy values of image locations within the comparison entity, thereby to generate a comparison entity legitimacy value determining whether the individual translation is legitimate for the comparison entity; and announcing a defect for the comparison entity if none of the plurality of translations are legitimate therefor.
Metadata
Assignee
- Orbot Instruments Ltd.
Inventors
- Joel Yolles
- Meir Aloni
- Yair Eran
- Haim Kaplan
Application Information
Application Number:US 7014856
Filing Date:1996-08-22
Priority Date:1992-07-27
Art Unit:271
Classifications
IPC:
G06K 900
Field of Search:
382356141;145;149;151;199;209394
Patent Drawings (20 sheets)
Description
FIELD OF THE INVENTION
The present invention relates to methods and apparatus for comparing two data streams representing respective images of patterned objects, in order to find defects in one or both of the images.
BACKGROUND OF THE INVENTION
Defect detection systems find defects in an image of an object to be inspected, denoted O in the present specification, such as a reticle, wafer, PCB or other patterned object. The patterned object is typically formed in accordance with a digital precursor thereof. Defects in the image are found by comparing the image, denoted I in the present specification, of the object O, to another, reference image, denoted R, DB or "database" in the present specification. The reference image R is sometimes modified, as by translation, scaling and/or rotation, prior to the defect detection process to bring it into accordance with the image I. Alternatively or in addition, the image I may be modified prior to defect detection to bring I into accord with R. Scaling and rotation transformations are typically applied to the image R.
Typically, discrepancies between the image I and the reference image R have more than one origin. Possible origins of discrepancies between the I and R images include the following:
a. Inaccuracies of the apparatus employed to generate the object O to be inspected from its digital precursor.
b. Inaccuracies of the imaging apparatus employed to generate the image I from the object O, such as mechanical vibrations and optical distortions.
c. Inaccuracies in generating the reference image R from a precursor thereof, such as rounding errors.
d. Differences of scale, offset or orientation between image I and reference image R.
e. Defects in the object O.
It is often very difficult to differentiate between discrepancies between the I and R images which are the result of defects in the object O, and discrepancies between the I and R images which have other origins, as detailed in (a)-(d) above. A discrepancy of the second type is also termed herein an "expected difference". In other words, an expected difference is a discrepancy between I and R which falls into one of categories (a) to (d) above. One type of expected difference between I and R images is an expected translation error. An expected translation error occurs when corresponding portions of the I and R images "drift".
State of the art approaches to defect detection may be classified as either "compensate and compare" approaches or "features" approaches. The word "compensate" is intended to refer to a characteristic of "compensate and compare" approaches whereby expected differences between compared objects are anticipated or allowed for and are not considered defects. The two approaches may be employed separately or in combination. The two approaches are now described.
Compensate and Compare Approach
In the compensate and compare approach, comparison entities are defined in I. Each comparison entity corresponds to an area in I and comparison entities may overlap.
Each comparison entity in a first one of the images, such as I, is compared to a multiplicity of locations in the other one of the images, such as R, each location in R typically having the same dimensions as the comparison entity. From among the multiplicity of R locations, a plurality of locations in R is identified, each of which resembles the comparison location in I in some sense. The relationship between the multiplicity of locations in R and the location of the comparison entity in I defines a multiplicity of translations from I to R.
Alternatively, only a single translation may be defined from I to R by directly computing a translation between I and R which translates the comparison entity under consideration in I to a location in R which is as similar as possible, in some sense, thereto.
A compensate-and-compare type defect detection method comprises the following steps:
I. Computing I-R difference for each translation of each comparison entity: For each comparison entity and for each translation, comparing the comparison entity, and the location in R corresponding to that translation, by obtaining a difference measure. For example, the sum of differences of corresponding pixel values may be used as a difference measure.
II. Computing I-R difference for each comparison entity: Computing a difference measure for each comparison entity by combining the difference measures for each translation considered for that comparison entity. For example, the comparison entity difference measure may be defined as the minimum of all the difference measures corresponding to all translations considered for that comparison entity.
III. Finding defects: Providing an indication of defects using the comparison entity difference measures. For example, a defect may be indicated for a particular comparison entity if its difference measure value exceeds some predetermined threshold.
The quality of performance of a "compensate and compare" detection method is influenced by at least the following factors:
a. Expected differences compensation: If the compensation for expected differences is good, high similarity requirements may be imposed in the comparison stage I, and consequently, sensitive defect detection may be achieved. Various factors affect the quality of expected difference compensation. For example, shape and size of the comparison entities may affect accuracy of compensation for translation errors.
b. Defect compensation: If differences due to defects are compensated for, they may not be identified as defects in the comparison stage. Therefore, a scheme that minimizes defect compensation increases detection sensitivity.
c. Comparison accuracy: If the comparison procedure of step II above is accurate, high-sensitivity defect detection may be achieved. Conversely, if noise accumulates in the course of the comparison step, comparison thresholds must be increased, with consequent reduction in sensitivity.
To summarize, a compensate and compare detection scheme gives good results if it maximizes expected difference compensation and comparison accuracy and minimizes defect compensation.
Features Approach
According to the "features" approach to defect detection, predetermined features such as 90 degree corners or grey gradients in some direction are identified in both image I and reference image R. The features employed must remain relatively invariant for all translations between I and R which are considered during the process. A process of comparison at the feature level is employed to identify defects.
The advantage of a "features" approach is that it may not be affected by small expected discrepancies that are difficult to compensate for. However, in order to be used effectively the features need to be chosen such that they can be extracted in a reliable manner, without being dependent on specific sampling grid placement, and such that they reliably describe a variety of image geometries, including dense image geometries.
U.S. Pat. No. 4,805,123 to Specht et al describes a compensate and compare approach to defect detection. The comparison entities are large image regions which have a height of several rows and extend over the entire width of the image. Specht et al employ a direct computation to compute a compensating translation. The computation involves the steps of:
a. Computing a correlation function on large windows in I and R, where the function is computed at whole pixel intervals, thereby to obtain a sampled correlation surface.
b. Finding the minimum point of the sampled correlation surface.
c. Fitting a quadratic surface to points in the neighborhood of the minimum point, in order to compute a subpixel minimum point or line.
d. Using the subpixel location to compute a subpixel translation, to be applied to reference image R.
e. Once the two images are aligned, the two images are compared, using the following substeps:
summing differences in corresponding 2.times.2 pixel windows in image I and in transformed reference image R; and
applying thresholds to the sums.
The approach of Specht et al has several disadvantages, including the following:
a. Errors in computing the translation: The Specht method does not always find the minimum point of the continuous correlation surface. The quadratic surface fitting is done in the neighborhood of the minimum of the sampled correlation surface. However, these two minimum points may not be adjacent. In such cases a false alignment transformation may be chosen, causing false alarms in the comparison step. Therefore, Specht et al cannot reliably handle images which include certain problematic geometries. Sample problematic images are images that contain mostly edges in a first direction and only a small number of short edges in a second perpendicular direction.
b. Insufficient expected difference compensation: The comparison entity is a large region. The same translation is applied to all its points. Hence, some expected discrepancies cannot be compensated for, e.g. edge related discrepancies. This reduces detection sensitivity.
c. Reduced comparison accuracy: If more than one edge falls within the 2.times.2 comparison window, the magnitude of expected differences is higher and a higher threshold must be used. Therefore, the detection sensitivity for small defects is low for dense images or image portions.
U.S. Pat. No. 4,579,455 to Levy et al and U.S. Pat. No. 4,805,123 to Specht et al describe a compensate and compare approach to defect detection in which the compensation step includes a search step. The comparison entities are 3.times.3 pixel windows. The comparison step is carried out by summing squared differences or absolute differences of corresponding pixels in the compared I and R entities. Each such sum is then compared to a threshold. The disadvantages of the method disclosed by Levy et al and Specht et al include the following:
a. Existence of defect compensation: Due to the small size of the comparison entity (3.times.3 window), defects may sometimes be compensated for, with resulting loss of sensitivity. Enlarging the window would not be a satisfactory solution. Since differences are summed over the entire window, the accumulation of inaccuracies over a large window would be too large.
b. Insufficient expected differences compensation: If more than one edge falls within the window, there is no way to compensate for edge related expected discrepancies. As a consequence, the expected difference is relatively large, and larger comparison thresholds are used in such cases. This results in reduced sensitivity for images comprising dense geometries.
U.S. Pat. No. 4,532,650 to Whil et al describes a "features" approach to defect detection. The features employed by Whil et al are the following:
Directional edges: an edge in one of the x, y, 45 and 135 degree directions. In other words, there are four types of directional edges.
Directional toggles: a pixel value sequence of high-low-high or of low-high-low in a specific direction. In other words, there are eight types of directional toggles because there are two toggle types for each of four directions (x, y, 45 degrees and 135 degrees).
Clear field: A location in which there are no directional edges and no directional toggles.
For each location, the above features are detected using a 7.times.7 window surrounding that location. If a feature is identified in one image without a corresponding canceller feature, located within +/-2 pixels, being identified in the other image, a defect is announced.
The disadvantages of the Wihl et al method include the following:
a. The method is not operative to detect defects generally. Only those defects which affect the specific features defined by Whil et al are found.
b. The operators used to compute the features cover a relatively large area of the image. Therefore, the method of Whil et al is not effective for dense images or dense image portions.
c. Feature generation depends on the specific placement of the sampling grid, which may vary when the comparison process is repeated. Therefore, the comparison process is not reliably repeatable.
SUMMARY OF THE INVENTION
The present invention seeks to provide an improved "compensate and compare" system for comparing digital images.
The present invention additionally seeks to provide an improved set of comparison entities.
The present invention further seeks to provide an improved comparison process.
The Improved Set of Comparison Entities:
A particular feature of the present invention is that more than one type of comparison entity is used. Two types of comparison entities, termed image regions and image edge neighborhoods, are, inspected in parallel by two respective cooperating processes, termed the regional comparison process and the local comparison process. The advantage of using more than one type of comparison entity is that more than one defect type may be detected, each with a relatively high detection sensitivity.
The regional comparison process inspects image regions. The dimensions of the image regions are relatively large and therefore, several or many edges may fall within a single image region. This allows defective positioning of one or a few edges or edge portions to be detected because each defectively positioned edge or edge portion is normally "anchored" by accurately positioned adjacent edges within the same image region. However, the dimensions of each image region are also small enough to ensure that good compensation for I-R misalignment may be provided by operating a single translation on the entire image region. In summary, the size of each image region is selected such that good compensation is achieved for expected differences and compensation for defects is minimal.
In the illustrated embodiment, each image region is a rectangle 30 pixels long and 60 pixels wide. Typically, image regions overlap such that the distance between centers of adjacent regions is half-region lengths along one axis and half-region widths along the other axis.
The local comparison process inspects edge neighborhoods. It is a particular feature of the present invention that compensation is provided not only for global I-R misalignment, in which the entire image I is transformed or translated relative to the entire image R, but also for distortions of single edges in I relative to the corresponding edges in R. Compensation at the level of single edges results in a particularly sensitive comparison of I and R.
The local comparison process is useful in detecting defects which cause local changes in the shape of the I image, relative to the R image. The term local change or local defect refers to a change in the shape of an individual image edge. The local comparison process generally does not detect defects in which an entire edge drifts without causing local changes in the shape of any individual portion of the line.
The length of each individual edge neighborhood is selected to be large relative to the width of defects for which the process is intended. For example, in the illustrated embodiment, each edge neighborhood is 6 pixels long. This keeps defect compensation, which is undesirable, to a minimum, thereby improving detection sensitivity for local defects.
In sum, the image unit in the local comparison process is the edge neighborhood. Each edge neighborhood comprises a plurality of image locations arranged to cover a portion of an image edge. The number of image locations included in each edge neighborhood is determined in accordance with the size of defect which the local detection process is intended to detect. For example, if it is desired to detect defects whose size exceeds 0.8 pixels, each edge neighborhood may comprise a 5.times.1 pointer-linked array of overlapping image locations, corresponding to a 6.times.2 array of WP's. The pointer data defining the structure of the edge neighborhood is termed "E-NEIGHBORS data", as explained in detail below. Typically, edge neighborhoods overlap such that an edge neighborhood is centered around each individual image location containing an edge.
The Improved Comparison Process:
The method of the present invention, like other "compensate and compare" methods, includes a comparison process, termed "step I" in the Background section, which is specific to a particular comparison entity in I and a particular translation of that comparison entity from I to R. In the comparison process, the comparison entity in I is compared to a location in R to which the comparison entity corresponds according to the translation. In "compensate and compare" methods, the comparison process of step I typically comprises the following two substeps:
A. Compute numerical image location difference values: Compute an image location difference value for each of a plurality of small units, also termed herein image locations, defined within the comparison entity. The image location difference value of a small unit represents the difference between that small unit in I and a corresponding small unit in R. For example, in conventional defect detection systems, the small unit is a pixel and the image location difference value of each pixel may comprise either the square or the absolute value of the difference between the value of that pixel in the comparison entity and the value of the pixel corresponding thereto in R.
B. Combine image location difference values: The local values computed in the comparison entity are combined over the small units, thereby to obtain a single difference measure for the comparison entity.
Both step A and step B of step I of the method shown and described herein are improved relative to steps A and B respectively of step I in conventional methods. The improved step A of the present invention is described in detail below with reference to box 240 of the flowchart of FIG. 11. The improved step B of the present invention is described in detail below with reference to box 242 of the flowchart of FIG. 11.
It is a particular feature of the present invention that step B employs a non-linear combining function rather than a linear function such as the summing function employed in conventional systems. According to the present invention, step B includes the following substeps:
i. Transform the numerical image location difference values computed in step A to boolean image location difference values by thresholding. Specifically, the boolean image location difference value may be "true" (1) if the numerical image location difference value does not exceed a threshold and the boolean image location difference value may be "false" (0) if the numerical image location difference value is greater than the threshold.
ii. AND the boolean image location difference values, thereby to obtain a single boolean or binary difference measure for the comparison entity.
If the same threshold value is employed for all small units, steps i and ii are equivalent to the steps of:
taking the maximum over all the image location difference values; and
applying the threshold to the maximum in order to obtain a single boolean difference measure for the comparison entity.
The image location difference value combining step ii of the present invention has the advantage, relative to conventional systems, that inaccuracies do not accumulate over the comparison entity. Due to the maintenance of a low noise level, small defects may be reliably detected.
Another particular feature of the present invention is improved computation of image location difference values in step A. As explained above, in step A of the method described herein and of conventional methods, a difference measure is computed for each small unit. In conventional systems, a small unit may either be a single pixel or a 2.times.2 pixel window. In either case, however, the difference measure reflects a difference in the black area included in the entire I window, relative to the black area included in the entire corresponding R window.
In contrast, step A of the method of the present invention employs two computation levels rather than a single computation level. Specifically, in the method shown and described herein, each small unit is further partitioned into components and the difference measure reflects differences in the black areas included in each component of the I window, relative to the black area included in each corresponding component of the corresponding R window. Reference is made briefly to FIGS. 1-5 which conceptually illustrate the advantage of the present method relative to conventional methods.
FIG. 1 illustrates a small unit in I. FIG. 2 illustrates a location in R corresponding to the small unit of FIG. 1. As shown, each of FIGS. 1 and 2 include a top black portion T and a bottom black portion B. However, the top black portion T of FIG. 1 is larger than the top black portion B of FIG. 2 and the bottom black portion B of FIG. 1 is smaller than the bottom black portion B of FIG. 2.
FIGS. 3 and 4 conceptually illustrate first and second components of an image location difference value of the small unit of FIG. 1. The component illustrated in FIG. 3 represents the difference between the top black portions in I and R. The component illustrated in FIG. 4 represents the difference between the bottom black portions in I and R. FIG. 5 conceptually illustrates the image location difference value of the small unit of FIG. 1.
It is appreciated that the image location difference value illustrated in FIG. 5 is greater than the image location difference value which would result if only the top black portions were present in FIGS. 1 and 2, or if only the bottom black portions were present in FIGS. 1 and 2. Some conventional systems would produce a non-zero image location difference value if only the top black portions were present in FIGS. 1 and 2, or if only the bottom black portions were present in FIGS. 1 and 2. However, the image location difference value would be 0 in conventional systems if top and bottom black portions were both present as in FIGS. 1 and 2, because the discrepancy between the areas of the top black portions T is cancelled out by the discrepancy between the areas of the bottom black portions B.
A further particular feature of the compensate-and-compare defect detection method of the present invention is that two computation levels are employed rather than a single computation level. The two computation levels are now described in detail:
Image location level: A plurality of overlapping image locations is defined to cover the image. In the illustrated embodiment, each image location is a 2.times.2 pixel window, and there is a one-pixel overlap between adjacent image locations in both the horizontal and the vertical directions. For each image location, a plurality of translations are inspected using a local edge related criterion, as explained in more detail herein. Using the local edge related criterion, a translation of a particular image location is assigned an image location difference value (ILDV) of either:
a. `true` (1), indicating that it is legitimate for an image location, i.e. that it translates the image location to a similar DB location; or a value of
b. `false` (0), indicating that the translation is not legitimate for the particular image location, i.e. that the DB location to which the image location is translated is not similar to the image location.
Comparison entity level: Each comparison entity comprises a plurality of image locations. The ILDV's for the various image locations included in a particular comparison entity are combined by applying a boolean AND operation to obtain the set of translations legitimate for all image locations within the particular comparison entity. If this set is empty, that is, if no single translation is legitimate for all image locations in the comparison entity, a defect is announced.
An advantage of providing two computational levels as described above is that a relatively simple hardware implementation may thereby be provided, as described in detail below. The hardware described herein performs a plurality of comparisons at the image location level. Thereby, a bit map of legitimate translations is formed for each image location. The bitmaps for the various image locations are used more than once in order to perform comparisons at the comparison entity level.
Another advantage of the apparatus shown and described herein is a computational gain resulting from the overlap of comparison entities. Because each individual image location is normally included in several comparison entities which overlap thereat, relatively expensive comparisons may be carried out once for the individual image location stored, and used several times in order to compare the several comparison entities overlapping at that image location.
In summary, the method and apparatus of the present invention enjoy at least the following advantages relative to conventional defect detection systems:
1. Good compensation for expected differences: The size of regions used as comparison entities in the regional comparison process of the present invention is chosen to enhance compensation for expected differences. The local comparison process further enhances compensation for expected differences by compensating at the level of individual edges.
2. Low level of defect compensation: In the regional process, region size is selected to be large enough to reduce the level of defect compensation, for defects of all types, and also small enough to substantially prevent compensation for misplaced edges. In the local comparison process, the length of edges used as comparison entities is selected to be large enough to reduce the level of compensation for the local-type defects, as defined above, which the local process detects.
3. Processing speed: Due to the accuracy of the comparison step (step I), the system can process images with dense geometries. Also, for images with less dense geometries, pixel size can be enlarged with consequent increase in processing speed.
4. Simple implementation: The two-level apparatus shown and described herein, including a comparison-entity level and an image-location level, provides relatively simple and efficient manipulation of boolean values. For example, the comparison-entity level uses at least some of the boolean values computed at the image-location level at least twice, corresponding to the at least two comparison entities overlapping at an individual image location.
There is thus provided in accordance with a preferred embodiment of the present invention a method for comparing first and second digital representations of an image, the method including the steps of:
for each individual translation from among a plurality of translations from the first digital representation to the second digital representation:
for each individual image location from among a plurality of image locations within a comparison entity within the first digital representation, determining a binary legitimacy value of the individual translation for the individual image location by comparing the individual image location to a location in the second digital representation defined by operating the individual translation on the individual image location, and
combining the binary legitimacy values of image locations within the comparison entity, thereby to generate a comparison entity legitimacy value determining whether the individual translation is legitimate for the comparison entity, and
announcing a defect for the comparison entity if none of the plurality of translations are legitimate therefor.
Further in accordance with a preferred embodiment of the present invention, the steps of determining, combining and announcing are repeated for each of a plurality of comparison entities defined in the first digital representation.
Still further in accordance with a preferred embodiment of the present invention, the method also includes the step of comparing the binary legitimacy values of the plurality of translations and selecting at least one translation suitable for realignment of the first and second digital representations.
Additionally in accordance with a preferred embodiment of the present invention, the plurality of comparison entities includes a plurality of adjacent image regions.
Further in accordance with a preferred embodiment of the present invention, the step of combining includes the step of ANDing the binary legitimacy values of all image locations within the comparison entity.
Still further in accordance with a preferred embodiment of the present invention, the step of comparing and selecting includes the steps of:
summing the comparison entity legitimacy values of each individual translation from among the plurality of translations, over a plurality of adjacent comparison entities, and
selecting at least one translation with a relatively high sum of comparison entity legitimacy values.
There is also provided, in accordance with another preferred embodiment of the present invention, a method for comparing first and second digital representations of an image, the method including the steps of:
for each individual translation from among a plurality of translations from the first digital representation to the second digital representation:
for each individual image location from among a plurality of image locations within a comparison entity within the first digital representation, determining legitimacy of the individual translation for the individual image location by comparing the individual image location to a location in the second digital representation defined by operating the individual translation on the individual image location, and
generating a nonlinear combination of the legitimacies of all image locations within the comparison entity, thereby defining the legitimacy of the individual translation for the comparison entity, and
announcing a defect for the comparison entity if none of the translations thereof are legitimate.
Further in accordance with a preferred embodiment of the present invention, the legitimacy of an individual translation is a binary value.
There is further provided, in accordance with a further preferred embodiment of the present invention, a method for comparing first and second digital representations of an image, the method including the steps of:
comparing each individual one of a multiplicity of comparison entities of a first type in the first digital representation to at least one corresponding location in the second digital representation, the correspondences between the individual comparison entity of the first type and the at least one locations in the second digital representation respectively defining at least one transformations from the first digital representation to the second digital representation,
comparing each individual one of a multiplicity of comparison entities of a second type in the first digital representation to at least one corresponding location in the second digital representation, the at least one locations in the second digital representation corresponding respectively to the at least one transformations applied to the individual comparison entity of the second type, and
providing an output indication of differences between the first and second digital representations in accordance with the results of the comparing steps,
wherein the two comparing steps are performed in parallel.
There is also provided, in accordance with another preferred embodiment of the present invention, a method for comparing first and second digital representations of an image, the method including the steps of:
I. for each individual translation from among a plurality of translations from the first digital representation to the second digital representation:
A. for each individual image location from among a plurality of image locations within a comparison entity within the first digital representation:
i. comparing the individual image location to a location in the second digital representation defined by operating the individual translation on the individual image location,
ii. evaluating the geometrical complexity of the vicinity of the location in the second digital representation, and
iii. determining the legitimacy of the individual translation for the individual image location in accordance with the results of the comparing and evaluating steps, and
B. combining the legitimacies of all image locations within the comparison entity, thereby defining the legitimacy of the individual translation for the comparison entity, and
II. announcing a defect for the comparison entity if none of the translations thereof are legitimate.
Further in accordance with a preferred embodiment of the present invention, the step of evaluating is performed once for all image locations within an individual comparison entity.
There is further provided, in accordance with a further preferred embodiment of the present invention, a method for detecting errors in alignment of first and second digital representations of an image, the method including the steps of:
for each individual location from among a multiplicity of locations within the first digital representation, determining at least one best translation from the first digital representation to the second digital representation for translating the individual location, and
announcing an alignment error if the at least one best translations of a plurality of adjacent locations are mutually discrepant.
There is still further provided, in accordance with still a further preferred embodiment of the present invention, a method for aligning first and second digital representations of an image, the method including, for each individual large location from among a plurality of relatively large locations covering the first digital representation, the steps of:
A. for each individual translation from among a plurality of translations from the first digital representation to the second digital representation:
i. for each individual small location from among a multiplicity of relatively small locations included in the individual large location, determining a binary legitimacy value of the individual translation for the individual small location, and
ii. combining the binary legitimacy values of the small locations included in the individual large location into a success score representing the success of the individual translation in translating the individual large location, and
B. improving the alignment of the first and second digital representations by operating an individual translation on the individual large location, wherein the individual translation is selected from the plurality of translations on the basis of the success score of the individual translation for the individual large location.
There is also provided, in accordance with a preferred embodiment of the present invention, apparatus for comparing first and second digital representations of an image, the apparatus including:
a per-image location translation legitimacy determining unit operative to generate, for each individual translation from among a plurality of translations from the first digital representation to the second digital representation and for each individual image location from among a plurality of image locations within a comparison entity within the first digital representation, a binary legitimacy value of the individual translation for the individual image location,
a per-comparison entity translation legitimacy determining unit operative to combine the binary legitimacy values of image locations within the comparison entity, thereby to generate a comparison entity legitimacy value determining whether the individual translation is legitimate for the comparison entity, and
a defective comparison entity announcing unit operative to announce a defect for the comparison entity if none of the plurality of translations are legitimate therefor.
Further in accordance with a preferred embodiment of the present invention, the legitimacy determining units and the defective comparison entity announcing unit are operative for each of a plurality of comparison entities defined in the first digital representation.
Still further in accordance with a preferred embodiment of the present invention, the apparatus also includes a realignment unit operative to compare the binary legitimacy values of the plurality of translations and to select at least one translation suitable for realignment of the first and second digital representations.
Still further in accordance with a preferred embodiment of the present invention, the plurality of comparison entities includes a plurality of adjacent image regions.
Additionally in accordance with a preferred embodiment of the present invention, the per-comparison entity translation legitimacy determining unit includes ANDing apparatus operative to AND the binary legitimacy values of all image locations within the comparison entity.
Further in accordance with a preferred embodiment of the present invention, the realignment unit includes a summer operative to sum the comparison entity legitimacy values of each individual translation from among the plurality of translations, over a plurality of adjacent comparison entities, and a selector operative to select at least one translation with a relatively high sum of comparison entity legitimacy values.
In accordance with another preferred embodiment of the present invention, there is provided apparatus for comparing first and second digital representations of an image and including:
a per-image location translation legitimacy determining unit operative, for each individual translation from among a plurality of translations from the first digital representation to the second digital representation and for each individual image location from among a plurality of image locations within a comparison entity within the first digital representation, to determine legitimacy of the individual translation for the individual image location by comparing the individual image location to a location in the second digital representation defined by operating the individual translation on the individual image location,
a non-linear legitimacy combining unit operative to generate a nonlinear combination of the legitimacies of all image locations within the comparison entity, thereby defining the legitimacy of the individual translation for the comparison entity, and
a defective comparison entity announcing unit operative to announce a defect for the comparison entity if none of the translations thereof are legitimate.
Further in accordance with a preferred embodiment of the present invention, the legitimacy of an individual translation is a binary value.
There is also provided in accordance with another preferred embodiment of the present invention, apparatus for comparing first and second digital representations of an image, the apparatus including:
first-type comparison entity comparing apparatus operative to compare each individual one of a multiplicity of comparison entities of a first type in the first digital representation to at least one corresponding location in the second digital representation, the correspondences between the individual comparison entity of the first type and the at least one locations in the second digital representation respectively defining at least one transformations from the first digital representation to the second digital representation,
second-type comparison entity comparing apparatus operative to compare each individual one of a multiplicity of comparison entities of a second type in the first digital representation to at least one corresponding location in the second digital representation, the at least one locations in the second digital representation corresponding respectively to the at least one transformations applied to the individual comparison entity of the second type, and
a difference announcer operative to provide an output indication of differences between the first and second digital representations in accordance with output received from the comparing apparatus, wherein the two comparing apparatus operate in parallel.
There is further provided, in accordance with a further preferred embodiment of the present invention, apparatus for comparing first and second digital representations of an image, the apparatus including an image location comparison unit and a geometrical complexity evaluator,
wherein, for each individual translation from among a plurality of translations from the first digital representation to the second digital representation and for each individual image location from among a plurality of image locations within a comparison entity within the first digital representation:
the image location comparison unit is operative to compare the individual image location to a location in the second digital representation defined by operating the individual translation on the individual image location and to provide a suitable output, and
the geometrical complexity evaluator is operative to evaluate the geometrical complexity of the vicinity of the location in the second digital representation and to provide a suitable output,
a per-image location translation legitimacy determining unit operative to determine the legitimacy of an individual translation for an individual image location in accordance with the outputs of the image location comparison unit and of the geometrical complexity evaluator for the individual translation and for the individual image location,
a per-comparison entity translation legitimacy determining unit operative to combine the legitimacies of all image locations within an individual comparison entity, thereby defiling the legitimacy of the individual translation for the comparison entity, and
a defective comparison entity announcer operative to announce a defect for the comparison entity if none of the translations thereof are legitimate.
Further in accordance with a preferred embodiment of the present invention, the geometrical complexity evaluator provides uniform output for all image locations within an individual comparison entity.
There is also provided, in accordance with a preferred embodiment of the present invention, apparatus for detecting errors in alignment of first and second digital representations of an image, the apparatus including a best translation identifier operative to determine, for each individual location from among a multiplicity of locations within the first digital representation, at least one best translation from the first digital representation to the second digital representation for translating the individual location, and a best translation discrepancy analyzer operative to announce an alignment error if the at least one best translations of a plurality of adjacent locations are mutually discrepant.
There is also provided, in accordance with another preferred embodiment of the present invention, apparatus for aligning first and second digital representations of an image, the apparatus including, for each individual large location from among a plurality of relatively large locations covering the first digital representation:
a per-large location success score generator operative to generate a success score for each individual translation from among a plurality of translations from the first digital representation to the second digital representation, the success score representing the success of the individual translation in translating the individual large location, the success score generator including:
a per-small location binary legitimacy value generator operative to generate, for each individual small location from among a multiplicity of relatively small locations included in the individual large location, a binary legitimacy value of the individual translation for the individual small location, and
a small-location result combining unit operative to combine the binary legitimacy values of the small locations included in an individual large location into a success score thereof, and
an alignment unit operative to improve the alignment of the first and second digital representations by operating an individual translation on an individual large location, wherein the individual translation is selected from the plurality of translations on the basis of the success score of the individual translation for the individual large location.
BRIEF DESCRIPTION OF THE DRAWINGS
The present invention will be understood and appreciated from the following detailed description, taken in conjunction with the drawings in which:
FIGS. 1 and 2 are conceptual illustrations of corresponding small units in image and reference datastreams, respectively;
FIGS. 3 and 4 are conceptual illustrations of first and second components of an image location difference value for the small unit of FIG. 1;
FIG. 5 is a conceptual illustration of both components of an image location difference value for the small unit of FIG.
FIG. 6 is a high-level simplified block diagram of a defect detection system constructed and operative in accordance with a preferred embodiment of the present invention;
FIGS. 7A and 7B, taken together, are a simplified block diagram of a preferred embodiment of image edge preprocessing unit 82, image shift unit 84, and alignment computation unit 88, all of which form part of the defect detection subsystem of FIG. 6;
FIG. 8 is a simplified flowchart of a preferred method for computing image edge data which may be performed by image edge preprocessing unit 82 of FIG. 7;
FIG. 9 is a simplified block diagram of a preferred embodiment of DB preprocessing unit 90 of FIG. 6;
FIG. 10 is a simplified flowchart of a preferred method for computing a database local geometry code which may be performed by DB preprocessing unit 90 of FIG. 9;
FIG. 11 is a simplified flow chart of a preferred defect detection method which may be performed by defect detection subsystem 86 of FIG. 6;
FIGS. 12 and 13 are conceptual illustrations of first and second search grids which may be employed by defect detection subsystem 86 of FIG. 6;
FIGS. 14 and 15 are conceptual illustrations of two search grids respectively employed in an individual detection module of FIG. 17 and in an individual detection unit of FIG. 18;
FIG. 16 is a simplified block diagram of a preferred embodiment of defect detection subsystem 86 of FIG. 6;
FIG. 17 is a simplified block diagram of a preferred embodiment of an individual defect detection module forming part of defect detection subsystem 86 of FIG. 16;
FIG. 18 is a simplified block diagram of a preferred embodiment of an individual defect detection unit forming part of the defect detection module of FIG. 17;
FIG. 19 is a simplified flow chart illustrating a preferred method which may be employed by comparing unit 336 of FIG. 18 in order to implement step 240 of the method of FIG. 11 in the course of a regional detection process;
FIG. 20 is a simplified flow chart illustrating a preferred method which may be employed by comparing unit 336 of FIG. 18 in order to implement step 240 of the method of FIG. 11 in the course of a local detection process;
FIG. 21 is a simplified block diagram of a preferred embodiment of comparing unit 336 forming part of the detection unit of FIG. 18;
FIG. 22 is a simplified block diagram of a preferred embodiment of a data spanning unit forming part of the comparing unit of FIG. 21;
FIG. 23 is a simplified block diagram of a preferred embodiment of a location comparator unit forming part of the comparing unit of FIG. 21;
FIGS. 24A and 24B, taken together, are a simplified block diagram of a preferred embodiment of a regional combining unit forming part of the detection unit of FIG. 18;
FIG. 25 is a conceptual illustration of adjacent image regions; and
FIG. 26 is a simplified block diagram of a preferred embodiment of a local combining unit forming part of the defect detection unit of FIG. 18.
DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS
In the present specification and claims, the term digital representation of an image is intended to refer to any representation of an image which is expressed in discrete symbols, such as numerical symbols. A common digital representation of an image is a digital file or a stream of digital data comprising a plurality of numerical values corresponding to a plurality of pixels into which the image has been divided.
In order to simplify understanding of the present specification and claims, the following data structure elements are defined:
Whole Pixel (WP): A unit of representation of the database and image (I) streams on a first predetermined grid which may or may not be of the same resolution as the resolution in which the image was sampled. Whole pixels are also termed herein "pixels". Each whole pixel comprises 2.times.2 half-pixels, defined below.
Half-pixel (HP): A unit of representation of the database and image streams in a second predetermined grid each of whose axes has twice the resolution of the corresponding axes of the first predetermined grid. Each half pixel is represented by a numerical value indicating the percentage of black area inside the HP. In the illustrated embodiment, each half-pixel is represented in 4 bits and each WP, comprising 4 HP's, is therefore represented in 16 bits, however this need not be the case.
Image location: A 2.times.2 array of whole pixels. Since each whole pixel is a 2.times.2 array of half-pixels, an image location is also a 4.times.4 array of half-pixels. The image is covered by a multiplicity of overlapping image locations. The centers of adjacent image locations are typically spaced one pixel apart. It is appreciated that the above image location dimensions and spacings are merely exemplary and are not intended to be limiting.
E.sub.-- position data: For each image location, data which categorizes each of the four pixels in the image location into one of three categories, termed herein selected, non-selected and other. A pixel which is categorized as selected in relation to a particular image location contains a portion of an edge which has been selected for that image location. A pixel which is categorized as non-selected contains at least a portion of an edge other than the selected edge and may or may not contain a portion of the selected edge. An other pixel does not contain any portion of any edge. In the illustrated embodiment, the E.sub.-- POSITION data for each image location is represented as four 2-bit values.
If an individual image location includes more than one edge portion, only one of the included edge portions is selected, preferably the longest edge portion. If an individual image location includes more than one longest edge portions, either of the longest edge portions may be selected. Typically, each edge portion in the image is selected for at least one image location.
A preferred method for providing E-POSITION data for each image location is described below with reference to FIG. 8.
E.sub.-- NEIGHBORS data: For each image location two pointers pointing to two respective adjacent ("neighbor") image locations, if such exist, whose selected edge portions are each a continuation of the selected edge portion included in the individual image location. An adjacent image location having this characteristic is termed herein an "edge neighbor". Typically, zero, one or two of the 8 image locations adjacent an individual image location are edge neighbors thereof. Each pointer is preferably represented in 4 bits. One bit indicates whether or not an edge neighbor exists and the remaining three bits identify which of the 8 adjacent image locations is the edge neighbor.
Reference is now made to FIG. 6 which is a block diagram of a defect detection system, referenced generally 80, operative to detect defects in microscopic objects and constructed and operative in accordance with a preferred embodiment of the present invention. Defect detection system 80 is operative to compare two digital representations of an image which are received as two datastreams, indicated as the DB (database or reference) stream and the I (image) stream. The DB stream includes a binary raster representation of a database wherein each pixel is described by 36 (6.times.6) bits. The I stream comprises a stream of 16-bit WP's, as defined above.
A gray precursor of the image stream may be directly provided by an imaging system (not shown) that scans an object to be inspected such as a reticle. Alternatively, the image stream may be provided by a digital storage unit such as a disk which stores images to be inspected. A commercially available imaging system is the MaxVideo 20 system, available from Datacube Inc., 4 Dearborn Rd., Peabody Mass. 01960, USA.
In order to convert the gray image data provided by the imaging system into WP representation, a binarization process for converting each gray pixel into a 6.times.6 array of binary pixels may be employed. Subsequently, a binary pixel count may be employed in order to generate area values for each HP. The binarization process may be implemented using conventional edge detection and segmentation methods such as those described in the following articles, the disclosures of which are incorporated herein by reference:
Hildreth, E. C., "Implementation of a Theory of Edge Detection", Report AI-TR-579, AI Laboratory, MIT, Mass, USA, April, 1980.
The image stream is received by an image edge preprocessing unit 82. Image edge preprocessing unit 82 computes the E.sub.-- POSITION and E.sub.-- NEIGHBORS data streams defined above. These two data streams collectively are also termed herein edge data. The image stream, E.sub.-- POSITION stream and E.sub.-- NEIGHBORS stream collectively are also termed herein the I* stream.
An image shift unit 84 receives I*, including the image stream and the edge data, from image edge preprocessing unit 82. Image shift unit 84 is operative to control delay of the I* datastream, thereby to shift the image relative to the database in accordance with alignment information pertaining to the relative positions of the image and database. The image/database alignment information is provided to image shift unit 84 by a defect detection subsystem 86 via an alignment computation unit 88, both of which are discussed in more detail below.
It is a particular feature of the present invention that it is not necessary to conduct, for alignment purposes, a separate comparison of the I and DB datastreams, in addition to the I and DB comparison process carried out by defect detection subsystem 86 for defect detection purposes. Rather, the results of the comparison carried out for defect detection purposes are also employed to determine the relative positions of image and database.
The second stream of data, termed herein "the database stream", may comprise design data of the object to be inspected, converted into 6.times.6 bit per pixel format. However, the second stream of data need not, in fact, be a database and may alternatively comprise a binarized image, provided by an imaging system or retrieved from digital storage, as described above with reference to the image stream.
The database stream is received by a database preprocessing unit 90 which groups the 36 bit per pixel database stream into 9 parallel 16-bit per WP data streams. The database preprocessing unit also provides a classification of the local geometry of the database, termed herein the "FD code", as explained in detail below with reference to FIG. 9. The FD code stream is provided to defect detection subsystem 86 which utilizes the code to select thresholds for local defect detection. If the FD code indicates a complex edge structure in a particular location of the database, then relatively high local detection thresholds are employed and conversely, relatively low thresholds are employed when inspecting simple edge structures such as single edges or single corners. The grouped database stream and the FD code stream are provided to defect detection subsystem 86 which is operative to compare the DB and I data streams.
Defect detection subsystem 86 receives the image data and image edge data streams from image shift unit 84, compares the image data stream to the database data stream and provides an output indication of differences between the I and DB streams. Defect detection subsystem employs an improved compensate-and-compare algorithm to detect defects and is described in detail below with reference to FIG. 16.
The output indication of differences provided by defect detection subsystem 86 includes a datastream indicative of the relative goodness of various image to database translations and termed herein the translation map. Alignment computation unit 88 receives the translation map from defect detection subsystem 86 and computes alignment information pertaining to the relative positions of the image and database. The alignment information is employed for at least the following two purposes:
(a) Providing indications of defects: The alignment information is useful in identifying defects because it can identify extreme fluctuations in the relative positions of the image and database. Small fluctuations in alignment may be due to inaccuracies of the imaging apparatus and therefore are not classified as defects. Fluctuations which are too large to be attributed to inaccuracies of the imaging apparatus may be defects. The information regarding extreme fluctuations in alignment is provided to a defect reporting unit 92.
(b) Providing shift information: The alignment information is also employed by image shift unit 84 in order to maintain the distance between image and database within the limits of the search process implemented in detection subsystem 86. For example, if the limits of the search process are plus/minus 1.5 pixels, shift instructions may be provided to image shift unit 84 only when the distance between image and database is found to be more than approximately 0.75 pixels.
Defect reporting unit 92 receives separate output from the regional and local defect detection processes carried out in defect detection subsystem 86 as well as receiving the defect-indication output of alignment computation unit 88. Defect reporting unit 92 combines these three inputs and outputs them to an external source, such as a digital file, stored in any suitable medium such as a disk or RAM. Preferably, the output of defect reporting unit 92 comprises, for each individual image location, an output indication of:
a. presence or absence of a local defect in the edge neighborhood centered at the individual image location,
b. presence or absence of a regional defect in the region to which the image location belongs, and
c. presence or absence of an alignment defect in an integration area comprising a plurality of adjacent regions. An alignment defect indicates that a large discrepancy exists between the identified misalignments of regions within the integration area.
A control processor 94 is provided which coordinates the operations of the various components of the system 80. The control processor preferably provides a status code to detection subsystem 86 which reflects user decisions regarding at least one of the following characteristics of the system:
a. Defect types to be detected. Some or all of regional, local, and alignment defects may be detected.
b. Detection sensitivity of the system for each type of defect to be detected.
The various components of FIG. 6 are now described in detail. First, image edge processing unit 82, image shift unit 84 and alignment computation unit 88 are described with reference to FIGS. 7A & 7B, and database preprocessing unit 90 is described with reference to FIG. 9. Next, a preferred method and structure for implementing defect detection subsystem 86 is described with reference to FIGS. 11, 16-18 and 21-24A & B.
Reference is now made to FIGS. 7A & B, which together form a block diagram of a preferred embodiment of image edge preprocessing unit 82, image shift unit 84 and alignment computation unit 88 of FIG. 6.
Image edge preprocessing unit 82 is now described in detail. As explained above, image edge processing unit 82 receives the image stream from outside the system. Each 4 bits of the image stream I received by image edge preprocessing unit 82 represents the percentage of black area in a single HP or half-pixel. As explained above, each 4 HP's defines a WP or whole pixel. Image edge preprocessing unit 82 computes edge data pertaining to locations of edges in the image. The edge data comprises the E.sub.-- POSITION and E.sub.-- neighbor data streams defined above. The output of the image edge preprocessing unit 82 is the original I data stream together with the computed E.sub.-- POSITION and E.sub.-- NEIGHBORS streams.
As explained above, the E.sub.-- position data categorizes each pixel as selected, nonselected or other, in relation to a particular image location. The E.sub.-- NEIGHBORS data for each image location comprises two pointers each of which points to a neighboring image location, if such exists, whose selected edge portion is a continuation of the selected edge portion included in the individual image location. Normally, there are zero, one or two image locations from among the 8 image locations adjacent an individual image location whose selected edge portion is a continuation of the selected edge portion of the image. Each pointer is represented in 4 bits in the illustrated embodiment.
Reference is now made to FIG. 8 which is a flowchart of a preferred method for computing the E.sub.-- NEIGHBORS and E.sub.-- POSITION data, which may be performed by image edge preprocessing unit 82.
The method of FIG. 8 preferably comprises the following steps:
Step 130: Convert each HP value of the image datastream into one of three ordinal values, termed herein HIGH, LOW and OTHER. For example, if each input HP is represented by 4 bits, an HP value of 15 is converted to HIGH, an HP value of 0 is converted to LOW and HP values of 1 to 14 are converted to OTHER.
Step 132: Generate a binary edge map in HP resolution in which each HP that includes an edge receives a value `1`, and each HP that does not include an edge receives a value `0`.
The edge map value of V0, an individual HP, may be computed in accordance with the following formula:
where the HP's in the vicinity of V0 are denoted a s follows:
V0 V1
V2 V3
Steps 130 and 132 may be performed by unit 120 of FIG. 7. Step 130 may be implemented by a 16 bit-in 8 bit-out table, which provides, for each 16-bit WP, an 8-bit notation for its 4 2-bit ordinally represented HP's. Step 132 may be implemented by four 8 bit-in 1 bit-out tables, each determining a binary edge value for a single HP. Apart from the above 5 tables, unit 120 of FIG. 7 also includes suitable delay units.
Step 134: Compute E.sub.-- POSITION data for each image location in the image, using the binary edge map of step 132. As explained above, the E.sub.-- POSITION data includes four 2-bit values which categorize each of the four WP's in an individual image location into one of three categories, termed selected, non-selected and other. A pixel which is categorized as selected in relation to a particular image location contains a portion of an edge selected for that image location. A pixel which is categorized as non-selected contains at least a portion of an edge other than the selected edge and may or may not contain a portion of the selected edge. An "other" pixel does not contain any portion of any edge.
The process for selecting an edge for an individual image location may be as follows: If there is only one edge in the image location, that edge is the selected edge. If there is more than one edge in the image location, the longer one (in HP's) is defined as the selected edge. A preferred criterion for connecting HP's into edges is 8-connectedness.
Step 134 may be performed by E.sub.-- POSITION unit 121 of FIG. 7. The 16 1-bit edge map values corresponding to each image location may be used to address a 16 bit-in, 8 bit-out table which provides the 4.times.2=8 bits of E.sub.-- POSITION data for each image location.
Step 136: The binary edge map computed in step 132 is employed to find, for each WP that contains an edge, all neighboring WP's in which the edge continues. Typically, there are 0, 1 or 2 such neighbors. Information regarding each of the two neighbor pointers for each WP is preferably represented by a 4 bit code. 3 bits are used to indicate neighbor location. The fourth bit is used to indicate existence of at least one neighbor.
Step 136 may be performed by WP neighbors unit 122 of FIG. 7. For each individual WP, a 4.times.4 HP portion of the binary edge map which is centered around the individual WP is employed to address a 16 bit-in 8 bit-out table, which determines the 4 bit code for each of the two neighbors.
In steps 138, 140 and 142, candidate neighbors are identified for each image location. Candidate neighbors of a current image location are adjacent image locations whose selected edge is a continuation of the selected edge passing in a current edge location. The output of the candidate neighbor identification process for each current image location preferably includes two 8-bit words, indicating the legality of each of the 8 neighbors of the current image location regarding first and second continuations, respectively, of the selected edge of the current image location. The term legality here characterizes a neighboring image location which "qualifies" as a candidate neighbor of a current image location.
The three steps 138, 140 and 142 of the process whereby candidate neighboring image locations of an individual current image location are identified are now discussed in detail.
Step 138: From among the 4 WP's included in the current image location, select a WP through which the selected edge passes. This step is implemented by addressing a 4-bit in 2-bit out table with the E.sub.-- POSITION data.
Step 140: Identify the two WP neighbors of the WP selected in step 138. These two neighbors are referred to herein as n1 and n2. In order to perform step 140, the WP neighbor data stream computed in step 136 is suitably delayed.
Step 142: Mark the legality of the neighbors relative to n1 and n2. An image location neighbor is legal with respect to neighboring WP n1, if the location n1 is a selected edge within it (i.e. the pixel n1 has a `selected` categorization).
Step 142 may be implemented by four 16 bit-in 4 bit-out tables, each of which handles two neighbors. Each table is addressed by the locations of the two neighbors (4+4 bits) concatenated with E.sub.-- POSITION data for the two candidate neighbors (4+4 bits). The output of each two-neighbor table includes two legality bits for neighbor n1 and two legality bits for neighbor n2.
Step 144: Assign a centrality rank for each image location. Centrality ranks are determined as a function of the percentage of white area in an individual image location (%W). Specifically, the centrality rank of an image location typically equals %W if %W does not exceed 50. If %W exceeds 50, the centrality rank of the image location equals %W-50.
Step 144 may be performed by unit 124 of FIG. 7A. A 16 bit-in 4 bit-out table may be provided to sum the white area for each WP. A 16 bit-in 3 bit-out table may be provided to receive the output of the above table, and sum the area of each image location by summing the white areas of the four WPs included in each image location, thereby to provide a 3 bit centrality rank. steps 146 and 148, two of the 8 neighbors of each individual image location are selected as E.sub.-- NEIGHBORS for the individual image location. Each of the two E.sub.-- NEIGHBORS of an individual image location contains a selected edge which is a continuation of the selected edge of the individual image location.
The E.sub.-- NEIGHBORS are selected as the two highest centrality-ranking candidates from among the legal candidate neighbors found in step 142. The selection process may be implemented in unit 125 of FIG. 7A by prefixing a legality bit to the 3-bit centrality ranking for each of the candidates of step 142, and then identifying the two candidates having maximum values. In step 146, a first E.sub.-- neighbor is found. In step 148, a second E.sub.-- neighbor is found. Steps 146 and 148 are now discussed in detail.
Step 146: The legal candidate neighbors identified in step 142 are divided into two groups, each containing four legal candidate neighbors. For each group, the highest centrality ranking candidate neighbor location is identified, using a 16 bit-in 5 bit-out table. The 5-bit output includes 3 bits indicating the centrality rank of the highest ranking candidate neighbor and two bits identifying the highest ranking candidate neighbor within the group of 4 legal candidate neighbors to which it belongs.
The two 5-bit words provided by the tables of the two groups respectively are employed to address a 10 bit-in 4 bit-out table which outputs an E.sub.-- neighbor code identifying the first neighbor.
Step 148: The second E.sub.-- neighbor is selected as follows:
The process may be similar to the process of step 146, except that the legality bit of the E.sub.-- neighbor selected in step 146 is "turned off". This may be implemented by addressing a 12 bit-in 8 bit-out legality bit updating table with the 8 legality bits and the 4 bit code of the E.sub.-- neighbor identified in step 146.
Referring back to FIG. 7B, image shift unit 84 is now described in detail. From image edge preprocessing unit 82, image shift unit 84 receives input preferably including the following components:
a. 16 bits of image data pertaining to the WP's of a current row; and
b. 16 bits of E.sub.-- POSITION and E.sub.-- NEIGHBORS data pertaining to the image locations of the current and next rows.
The output of image shift unit 84 includes all information pertaining to the image locations of the current and next rows. In other words, the output of image shift unit 84 preferably includes pixel values for the WP's of the current and next rows (32 bits) and edge related data for the current and next rows (16 bits).
Image shift unit 84 receives shift commands from alignment computation unit 88 which specify suitable x and y shift values for the image. According to a preferred embodiment of the present invention, each shift value can only be -1, 0 or 1 WP's along either a row or a column and an overlap of 1 WP is provided between image locations which are adjacent along either a row or a column. An advantage of this embodiment is that image data is not lost due to alignment correction. In other words, it is guaranteed that each image row received by image shift unit 84 will also leave image shift unit 84.
As shown in FIG. 7B, image shift unit 84 preferably comprises a controller unit 114 and a cyclic buffer memory unit 116. Image data entering image shift unit 84 is written into cyclic buffer memory unit 116. The input and output pointers of cyclic buffer unit 116 are maintained by controller unit 114. Image shift commands are implemented by changing the output pointer of the buffer. Memory unit 116 is large enough to store data pertaining to a number of image rows, where the number of rows depends on the maximal desired delay between the input and output of the image shift unit. For example, a maximal capacity of 100 image rows may be used.
Alignment computation unit 88 of FIG. 6 is now described in detail with reference to FIG. 7A. As explained above with reference to FIG. 6, alignment computation unit 88 is operative to receive a translation map datastream, also termed herein a subsystem level regional translation map, from defect detection subsystem 86 of FIG. 6. Each translation map pertains to an individual region defined in the image datastream. In the illustrated embodiment, each of the 324 components of an individual translation map pertaining to an individual region is indicative of the legitimacy of one of 324 I-DB translations, for translating the individual region into a corresponding location in the database.
According to a preferred embodiment of the present invention, the translation map data is transmitted from defect detection subsystem 86 to alignment computation unit 88 at a rate of 1 bit per time unit, where a time unit is the time required to process a single WP. This is possible if the number of time units in which each region is current (60.times.120, in the illustrated embodiment) is larger than the number of translations in the search grid of the defect detection subsystem 86 (324, in the illustrated embodiment).
As shown in FIG. 7A, the alignment computation unit 88 preferably comprises a translation strength computation unit 110, and an alignment processor 112.
Translation strength computation unit 110 integrates information regarding a plurality of translation maps. Specifically, unit 110 is operative to generate, for each of a plurality of overlapping integration areas of the image, a translation strength map, which has 324 elements in the illustrated embodiment. Each element of the translation strength map indicates the success of an individual translation from among the 324 translations of the search grid in translating all regions falling within the integration area. Each individual element of the translation strength map is computed by summing corresponding elements of the translation maps of all regions falling within the integration area.
The dimensions of each integration area and the mutual overlap therebetween are preferably determined as a function of mechanical vibrations and variations in other physical parameters of the scanning process which cause image-database misalignment. For example, for a scanning process having a scanning width of 1024. WP's per row, whose mechanical vibrations have a period of 200 rows of WP's, each integration area may have dimensions of 1024 WP's.times.200 WP's and the mutual overlap between adjacent integration areas may be 100 or 150 rows of WP's.
Preferably, translation strength computation unit 110 comprises a memory having a plurality of cells corresponding in number to the number of translations in the search grid. In the present embodiment, the memory of unit 110 includes 324 cells. In each time unit, a single bit, pertaining to an individual translation of a single region, is added to the cell corresponding to the individual translation.
Alignment processor 112 receives the translation strength map from translation strength computation unit 110 and computes alignment information status and alignment data. The alignment information status is indicative of the type of alignment data which may be determined and typically comprises one of the following three options:
Best point: If it is possible to determine a single translation which is stronger than all or most other translations, for the current integration area.
Best line: If it is possible to determine the location of a linear array of translations which are stronger than all or most other translations, for the current integration area.
No information: If neither a best point nor a best line can be determined.
The alignment data is either an indication of best point, or an indication of best line, or blank.
Alignment data and the status thereof may be computed as follows:
Alignment processor 112 scans the translation strength map to find a set of translations having maximal or relatively high strengths. If this set is entirely included within a circle of a predetermined radius, such as a radius of 3 map elements, then the center of gravity of the translations is defined as the best alignment point, and the alignment status is "best point". Otherwise, if the translation are generally arranged along a line, the line parameters are extracted using any suitable technique such as a least squares technique and the alignment status is "best line". Otherwise, the alignment status is "no information".
Alignment processor 112 employs the alignment status and alignment data for at least the following purposes:
a. Issuing a "shift image" command to image shift unit 84, in order to maintain the distance between the image and database within the limits of the search process implemented in detection subsystem 86. A "shift image" command may be issued if the "best point" translation or the "best line" translations are operative to translate individual image locations to individual database locations which are more than a predetermined distance away. For example, an "image shift" command may be issued if the "best" translation or translations define a location in the DB whose distance from the corresponding I location is more than 0.75 WP;
b. Finding alignment defects by monitoring "best" translations over time, thereby to identify fluctuations in the relative positions of the image and database which are too large to be accounted for by the inaccuracies of the imaging system; and
c. Providing control processor 94 of FIG. 6 with information on the status of alignment of the I and DB datastreams.
Reference is now made to FIG. 9 which is a block diagram of a preferred embodiment of DB preprocessing unit 90. The input to DB preprocessing unit 90 is the DB stream, in which each WP is described by a 6.times.6 binary map. The DB preprocessing unit 90 preferably comprises a DB channels grouping unit 170, and a PD (feature detection) unit 172.
DB channels grouping unit 170 receives the binary DB datastream and provides 9 differently-offset streams of DB data in HP representation to the 9 modules included in defect detection subsystem 86, as explained in detail below. DB channels grouping unit 170 may include a plurality of associated tables, which implements a binary pixel count for each HP.
The FD computation unit 172 receives a single DB channel, comprising HP-represented DB data. FD computation unit 172 computes the 4 bit FD code described hereinabove which categorizes the local geometry in the data base.
A preferred method for computing a 4 bit code which is indicative of the local geometry of the data base is now described, with reference to the flowchart of FIG. 10. Steps 220 and 222; 224; 226; and 228 and 230 of the method of FIG. 10 are implemented by units 174, 176, 178 and 180, respectively, of FIG. 9.
The method of FIG. 10 preferably includes the following steps:
Steps 220 and 222: A binary HP edge map is generated preferably by first converting received DB HP values into one of three categories: HIGH, LOW, OTHER. Steps 220 and 222 may be generally identical to steps 130 and 132 of the method of FIG. 8.
Step 224: Employ the binary edge map in order to identify, for each edge-containing WP, two neighboring WP's in which the edge continues. Each neighbor is designated by a 4 bit code. 3 of the bits are employed to designate one of the eight neighbors of the edge-containing WP. The fourth bit indicates whether or not a neighbor exists.
Step 224 may be generally identical to step 136 of the method of FIG. 8.
Step 226: For each edge-containing WP, employ the neighbor information computed in step 224 in order to generate a 4-WP pixel sequence comprising the edge-containing WP, its two neighbors and an additional neighbor of the second neighbor. The area of each of the four WP's in the sequence may be coded in 3 bits (total: 4.times.3=12 bits), and the relative positions of the 4 pixels in the sequence may be represented by 2 angles, each coded in 3 bits (total: 2.times.3=6 bits). The resulting 8-bit coding of the 4 WP sequence may be employed to address a table which provides a share classification code of the edges included in the 4 WP's of the pixel sequence. In other words, the shape classification code of a particular 4 WP sequence is indicative of the local geometry or edge structure complexity of the image location which includes the 4 WP's of the pixel sequence.
One coding system for the shape classification code may include at least the following code values:
0: no classification. This code may be assigned to the sequence if the edge-containing WP has no neighbors.
1: edge
2: 90 degree corner
3: 135 degree corner
4: 45 degree corner
Alternatively, as many as 16 separate code values may be employed.
Steps 228 and 230: For each individual WP, compute an FD code value characterizing a 3.times.3 WP window centered at the individual WP. This is done on the basis of the shape classification codes of each of the 9 pixels in the window, as computed in step 226. The FD code may be generated from the 9 shape classification codes using any suitable apparatus and method such as off-line construction of a suitable hierarchical LUT array (step 228).
Preferably, the FD code of an individual 3.times.3 WP window in the DB includes an indication of whether or not the 3.times.3 WP window includes at least one edge. The local defect detection process is preferably disabled for portions of the DB which contain no edges. The FD code also is indicative of the complexity of the local edge structure, which in turn determines the magnitude of local detection thresholds, as explained herein.
A preferred method and structure for implementing defect detection subsystem 86 of FIG. 6 is now described with reference to FIGS. 11, 16-18, and 21-24.
Specific reference is now made to FIG. 11 which is a generalized flowchart of a defect detection method useful in implementing defect detection subsystem 86 of FIG. 6.
The defect detection method of FIG. 11 interacts with the image stream on two separate levels, defining two separate units for comparison to the database stream. The unit of comparison at the top level is termed a comparison entity and the unit of comparison at the bottom level is termed an image location. The defect detection method of FIG. 11 employs two cooperating detection processes, termed the regional process and the local process, which differ as to the type of image entity (region or edge neighborhood, respectively) which is compared to the database. Both types of image entity comprise a plurality of image locations.
The method of FIG. 11 comprises three steps. In the first step, step 240, individual image locations are compared to corresponding individual locations in the database. For each image location, each database location defines an individual image-database translation. Step 240 is performed for each image location and for each translation of that image location.
In the second step of the method of FIGS. 11, step 242, the per-image location and per-translation results of step 240 are combined, preferably by an AND function, over comparison entities. The output of step 242 is, therefore, specific to individual translations of individual comparison entities.
In the third step of the method of FIG. 11, step 244, the per-comparison entity and per-translation results of step 242 are combined, preferably by an OR function, over translations. The output of step 244 is specific to individual comparison entities and is indicative of defects in the individual comparison entities.
The various steps of the method of FIG. 11 are now described in detail.
Step 240: Compare image locations to database:
In step 240, each image location is compared to a plurality of locations of the database, corresponding to a predetermined plurality of translations of the image datastream. The comparison is performed as follows:
For each database location, a regional comparison value (RCV) and a local comparison value (LCV) is computed, using any suitable difference measure. The regional and local comparison values computed for each pair of image and database locations are compared to comparison thresholds.
According to a preferred embodiment of the present invention, the comparison thresholds for the regional and local processes, respectively, are not equal, and are therefore termed herein regional comparison thresholds and local comparison thresholds, respectively. The binary result of each comparison between a regional comparison value and a regional comparison threshold is termed herein a regional location-specific legitimacy value or a RLSLV. The binary result of each comparison between a local comparison value and a local comparison threshold is termed herein a local location-specific legitimacy value or a LLSLV.
For example, if the regional comparison value of a particular translation is less than the regional comparison threshold, the RLSLV of that translation may be defined as 1, and the translation is termed herein legitimate for the particular image location, as far as the regional inspection process is concerned. If the regional comparison value of the translation exceeds the regional comparison threshold, the RLSLV of the translation may be defined as 0 and the translation is termed herein illegitimate for the particular image location.
Each RLSLV and each LLSLV is specific to a particular pair of image and database locations, because each RLSLV and each LLSLV is specific to a particular image location and to a particular image-database translation. Also, as explained above, a plurality of database locations are compared to each image location. Therefore, a corresponding plurality of RLSLV's are defined for each image location, one per image-database translation. The plurality of RLSLV's defined for an individual image location defines a vector corresponding to that image location which is termed herein a regional location-specific legitimacy vector or RLSL vector. If 324 database locations are compared to each image location, the RLSL vector of each individual image location has 324 components.
Similarly, since a plurality of database locations are compared to each image location, a corresponding plurality of LLSLV's are defined for each image location, one per image-database translation. The plurality of LLSLV's defined for an individual image location defines a vector corresponding to that image location which is termed herein a local location-specific legitimacy vector or LLSL vector. If 324 database locations are compared to each image location, the LLSL vector of an individual image location has 324 components.
Step 242: Combine comparison information over regions/edge neighborhoods:
For each comparison entity (region or edge neighborhood), an entity-specific legitimacy vector is computed by combining the information obtained in step 240 for each of the image locations included in the individual comparison entity. Specifically, the regional and local-location-specific legitimacy vectors of the image locations included in the individual region or edge neighborhood are ANDed componentwise in order to obtain the entity-specific legitimacy vector of the comparison entity. As explained above, the components of the regional and local location-specific legitimacy vectors are termed RLSLV's and LLSLV's, respectively. The result of ANDing all RLSLV's pertaining to a particular translation, over an individual region, is termed herein a regional entity-specific legitimacy value (RESLV). The result of ANDing all LLSLV's pertaining to a particular translation, over an individual edge neighborhood is termed herein a local entity-specific legitimacy value (LESLV).
An entity-specific legitimacy vector defined by a plurality of RESLV's all pertaining to a single region but corresponding to a plurality of translations is termed herein a region legitimacy vector or an RL-vector. An entity-specific legitimacy vector defined by a plurality of LESLV's all pertaining to a single edge neighborhood but corresponding to a plurality of translations is termed herein an edge-neighborhood legitimacy vector or an ENL-vector.
Step 244:Indicate defects by combining comparison information over translations for each region or edge neighborhood:
This step corresponds to steps II and III of conventional compensate-and-compare defect detection methods, as explained in the Background section of the specification. The entity-specific legitimacy vector of an individual comparison entity (region or edge neighborhood) is employed to determine whether a defect exists in the vicinity of the region or edge neighborhood. Typically, if the entity-specific legitimacy vector of an individual comparison entity indicates that no legitimate translation from image to database exists for that comparison entity, a defect indication is provided for that comparison entity. In other words, for each individual comparison entity, the translation-specific components of its entity-specific legitimacy vector are ORed to determine whether or not a defect exists in the comparison entity.
A computer listing of a software implementation of the method of FIG. 11 and batch files for activation thereof are appended hereto and referenced Appendix A. The software implementation of Appendix A is operative in either a local or a regional defect detection mode and employs a user-defined constant threshold for each of these modes. The computer listing of the method of FIG. 11 is written in C and the batch files are SUN UNIX Script files. The computer listings of Appendix A are operative on a suitable workstation such as a SPARC workstation, commercially available from SUN.
A preferred structure for defect detection subsystem 86 which implements the method of FIG. 11 is described below with reference to FIGS. 16-18 and 21-24.
The foregoing discussion relates generally to a plurality of search modes which may be employed by defect detection subsystem 86 and to a preferred hierarchical arrangement of defect detection subsystem 86. Subsequently, detailed reference is made to each of FIGS. 16-18 and 21-24 in order to describe each of the hierarchically arranged components of defect detection subsystem 86 in detail, in top-to-bottom order.
As described above, the defect detection subsystem 86 is operative to compare a plurality of translations of a multiplicity of image portions with respect to a corresponding multiplicity of database portions. The plurality of translations or search grid inspected for each image portion is determined by the search mode employed by the detection system 80. Preferably, a plurality of search modes are provided such as first and second user-selectable search modes differing in the resolution of their search grids.
Reference is made briefly to FIGS. 12 and 13 which illustrate first and second search grids employed respectively by the first and second search modes. As shown, in the search mode of FIG. 12, a search grid resolution of 1/6 WP is used whereas in the search mode of FIG. 13, a search grid resolution of 1/2 WP is employed. Both search grids are, in the illustrated embodiment, 18 translations long and 18 translations wide. In each time unit, the detection subsystem 86 inspects, preferably in parallel, the legitimacy of 18.times.18=324 translations in the search grid for a current region and a current edge neighborhood.
The detection subsystem 86 of FIG. 6 preferably is arranged hierarchically, as may be appreciated from a comparison of FIGS. 6, 16 and 17. As shown in FIG. 16, the detection subsystem comprises a plurality of detection modules 320, such as 9 detection modules 320. As shown in FIG. 17, which is a block diagram of a single detection module 320, each detection module 320 comprises a plurality of detection units 322 such as three detection units. In other words, in the illustrated embodiment, the detection subsystem 86 is arranged in three hierarchical levels.
In the illustrated embodiment, the first level comprises the detection subsystem as a whole which is operative to inspect the 324 translations in the 18.times.18 search grid of the detection subsystem. The second level comprises 9 detection modules operating in parallel, each being operative to inspect 36 translations in parallel. The 36 translations are arranged on a 6.times.6 grid with a displacement of 1 HP between adjacent translations, as illustrated in FIG. 14. The third level comprises 27 detection units operating in parallel, each being operative to inspect 12 translations in parallel. The 12 translations are arranged on a 2.times.6 grid with a displacement of 1 HP between adjacent translations, as illustrated in FIG. 15, such that the three 2.times.6 grid inspected by the three detection units 322 included in a single detection module 320, form the 6.times.6 grid of the detection module 320.
The relative placement of the nine search grids employed respectively by the 9 detection modules 320 depends on the search mode. In the high resolution search mode of FIG. 12, the 9 search grids overlap and have a relative displacement of 1/6 WP, thereby to form the search grid of FIG. 12. In the low resolution search mode of FIG. 13, the 9 search grids do not overlap, but are rather placed side by side, thereby to form the search grid of FIG. 13.
A preferred hierarchical mode of operation according to which the detection subsystem 86 may operate in order to detect defects in current regions or edge neighborhoods, in accordance with steps 240, 242 and 244 of the defect detection method of FIG. 11, is now described.
Step 240 of FIG. 11 is performed at the unit level. In other words, step 240 is performed independently by each of the 27 detection units 322. In each unit of time, each detection unit 322 compares an individual image location to 12 database locations in parallel and computes a 12-component RLSL vector and a 12-component LLSL vector. Each vector is specific to an image location. Within each vector, each component is specific to a database location or image-database translation.
Step 242 of FIG. 11 is also performed at the unit level. In other words, step 242 is also performed independently by each of the 27 detection units 322. Each detection unit 322 performs a component-wise AND operation on the RLSL vectors accumulated for an entire region, thereby to obtain a 12-component RL vector, also termed herein a unit-level regional translation map. Each RL vector is specific to an individual region. Within each region-specific vector, each component is specific to an image-database translation.
Each detection unit 322 also performs a component-wise AND operation on the LLSL vectors accumulated for an entire region, thereby to obtain a 12-component ENL vector. Each ENL vector is specific to an individual edge-neighborhood. Within each edge neighborhood-specific vector, each component is specific to an image-database translation.
OR-step 244 is carried out in three stages, which are performed at the unit level, the module level and the subsystem level, respectively. The first stage of OR-step 244 is performed separately for each of the 27 detection units 322, like steps 240 and 242. Each unit-level result of the first stage of OR-step 244 pertains to 12 translations from among the 324 translations in the search grid of detection subsystem 86.
In the second stage of OR-step 244, the unit-level results of each three units forming a single module are merged, thereby to define 9 module-level results. Each module-level result of the second stage of OR-step 244 pertains to 36 translations from among the 324 translations in the search grid of detection subsystem 86. In the third stage of OR-step 244, the module-level results of all 9 modules within detection subsystem 86 are merged, thereby to define a single subsystem-level result which pertains to all 324 translations in the search grid of detection subsystem 86.
In the illustrated embodiment, each of the 27 unit-level results computed by the unit-level stage of step 244 of FIG. 11 includes the following 3 components:
a. A 2-bit unit-level regional translation map, also termed herein an RL vector, which comprises a sequence of the 12 RESLV's computed in step 242.
b. A binary unit-level regional result (ULRR) computed by ORing the 12 RESLV's computed in step 242. This result indicates whether or not at least one translation from among the 12 translations is legitimate for the current region.
c. A binary unit-level local result (ULLR) computed by ORing the 12 LESLV's computed in step 242. This result indicates whether or not at least one translation from among the 12 translations for which an individual unit is responsible is legitimate for the current edge neighborhood.
In the illustrated embodiment, each of the 9 module-level results computed by the module-level stage of step 244 of FIG. 11 includes the following 3 components:
a. A 36-bit module-level regional translation map, which comprises a concatenated sequence of the 3 unit-level legitimate regional translation map sequences computed in the unit-level stage of step 244.
b. A binary module-level regional result (MLRR) computed by ORing 3 unit-level regional results computed in the unit-level stage of step 244. This result indicates whether or not at least one translation from among the 36 translations for which an individual module is responsible is legitimate for the current region.
c. A binary module-level local result (MLLR) computed by ORing 3 unit-level local results computed in the unit-level stage of step 244. This result indicates whether or not at least one translation from among the 36 translations for which an individual module is responsible is legitimate for the current edge neighborhood.
In the illustrated embodiment, the detection subsystem level result computed by the top-level stage of step 244 of FIG. 11 which forms the output of detection subsystem 86 includes the following 3 components:
a. A 324-bit top-level regional translation map, which comprises a concatenated sequence of the 9 module-level legitimate regional translation map sequences computed in the module-level stage of step 244.
b. binary top-level regional result (TLRR) computed by ORing 9 module-level regional results computed in the module-level stage of step 244. This result indicates whether or not at least one translation from among the 324 translations in the search grid of defect detection subsystem 86 is legitimate for the current region. A value of `0` means that no legitimate translation has been found for the region, and therefore the current region contains a defect.
c. A binary top-level local result (TLLR) computed by ORing 9 module-level local results computed in the module-level stage of step 244. This result indicates whether or not at least one translation from among the 324 translations in the search grid of defect detection subsystem 86 is legitimate for the current edge neighborhood. A value of `0` means that no legitimate translation has been found for the edge neighborhood and therefore the current edge neighborhood contains a defect.
Components b and c of the output of defect detection subsystem 86 are provided to defect reporting unit 92 of FIG. 6. Component a is provided to alignment computation unit 88.
The components of defect detection subsystem 86 are now described with specific reference to FIG. 16.
As explained above with reference to FIG. 6, the defect detection subsystem 86 receives the following four input streams of data:
(a) image data from image shift unit 84 of FIG. 6;
(b) database data from database preprocessor 90 of FIG. 6, to which the image data is compared;
(c) FD data which categorizes the database geometry, also from database preprocessor 90 of FIG. 6; and
(d) status data from control processor 94 of FIG. 6 which indicates, inter alia, the desired search mode. For example, the status data in the illustrated embodiment indicates whether the system is to operate in the high resolution search mode of FIG. 12 or the low-resolution, broad search area mode of FIG. 13.
As explained above, the detection subsystem of the present embodiment includes 9 detection modules 320 each of which operate in parallel to inspect 36 translations from among the 324-translation search grid-of the present embodiment.
The image stream arrives directly at the detection modules 320 from image shift unit 84. Each individual portion of the image stream arrives at all 9 detection modules simultaneously. The image stream is 32 bits wide and comprises the following ts:
(a) a 16-bit stream representing a column of image data which is 4 HP's (2 pixels) wide, each HP being represented in 4 bits; and
(b) 16 bits of edge data useful for the local comparison process described above, the edge data comprising E.sub.-- POSITION data (8 bits) and E.sub.-- NEIGHBORS data (8 bits), as defined above.
The database stream arrives directly at the detection modules 320 from database preprocessor 90. The database stream, in the illustrated embodiment, is 9.times.16 bits wide.
Each individual portion of the database stream arrives at the 9 detection modules at 9 respective times, which are all different. The relative offset between the data in the streams is determined by the search mode, as indicated by the status code.
For example, when the search mode of FIG. 12 is operative, the following shifts, given in WP, are employed for the 9 detection modules, respectively:
(0, 0) (0, 1/6) (0, 2/6)
(1/6,0) (1/6,1/6) (1/6,2/6)
(2/6,0) (2/6,1/6) (2/6,2/6).
When the search mode of FIG. 13 is operative, the following shifts, given in WP, are employed for the 9 detection modules, respectively:
(0,0) (0,3) (0,6)
(3,0) (3,3) (3,6)
(6,0) (6,3) (6,6).
The first and second coordinates in each of the above ordered pair are the shift, in pixels, along a first axis along which the object to be inspected is scanned, and along a second axis perpendicular to the first axis, respectively.
The FD and status data streams are received by a threshold selecting unit 324 which provides each detection module 320 with an indication of comparison thresholds, termed herein a threshold data stream.
The threshold data stream is 9.times.16 bits wide in the illustrated embodiment and comprises the following components:
(a) an 8-bit regional threshold value; and
(b) an 8-bit local threshold value.
Preferably, threshold selecting unit 324 comprises a table which stores regional and local threshold values and is addressed by the FD and status codes. As explained above, the FD code characterizes the complexity of local edge structure and is employed to select a local threshold value. The table of threshold selecting unit 324 may be constructed off-line by empirically comparing the results of regional and local detection on a selected representative set of images, using a variety of regional and local threshold levels, respectively.
According to a preferred embodiment, the table of threshold selection unit 324 may be dynamically modified by the user and/or by the system, via control processor 94 of FIG. 6.
The threshold data stream provided by threshold selecting unit 324 arrives at detection modules 320 via a threshold delay unit 326. The threshold delay unit 326 is operative to appropriately delay the local and regional thresholds, if necessary.
For example, if the search mode of FIG. 12 is employed, identical regional and local thresholds may be sent to all detection modules at each individual time, and no delay is introduced, because the distance between the database locations processed by the 9 detection modules at a given time is relatively small. Therefore, it is assumed that the local geometries of the 9 database locations processed at a given time are similar. However, if the search mode of FIG. 13 is employed, the local geometries of the 9 database locations processed at a given time are not assumed to be similar. In this case, the 3-pixel offset delay schedule described above as being used to delay the database stream, may be employed.
The detection modules 320 are operative to perform steps 240 and 242 of the defect detection method of FIG. 11, as described in detail above. The detection modules 320 are also operative to perform the module-level stage of step 244 of the defect detection method of FIG. 11. Specifically, as explained above, each module 320 is operative to combine the per-region and per-edge neighborhood results obtained for each of the 36 translations for which that module is responsible, into single per-region and per-edge neighborhood results. As described above, the output of module 320 includes a MLRR and a module-level regional translation map for each region inspected, and a MLLR for each edge neighborhood inspected.
The three output components of each of the 9 detection modules 320 are received by a result merging unit 328. Result merging unit 328 is operative to perform the top-level stage of step 244 of FIG. 11. In other words, result merging unit 328 merges the 9 module-level regional results, using an OR operation, to provide a top-level regional result (TLRR), described above, which indicates the existence of a defect in a current region. The TLRR is transmitted to defect reporting unit 92 of FIG. 6.
Result merging unit 328 is also operative to merge the 27 module-level local results, using an OR operation, to provide a top-level local result (TLLR), described above, which indicates the existence of a defect in a current edge neighborhood. The TLLR is transmitted to defect reporting unit 92 of FIG. 6.
Result merging unit 328 is also operative to merge the 27 module-level regional translation maps, using an OR operation, in order to provide a top-level regional translation map. The map is provided to alignment computation unit 88 of FIG. 6.
Reference is now made to FIG. 17 which is a block diagram of a preferred embodiment of an individual defect detection module 320. As explained above, each module 320 receives three streams of data: an I stream, a DB stream compared thereto in accordance with regional and local procedures described above and a threshold stream which determines regional and local comparison thresholds for the regional and local procedures respectively.
As explained above, the detection module 320 of the present embodiment includes 3 detection units 322 each of which operates in parallel to the others to inspect 12 translations from among the 36 translations for which the detection module 320 is responsible.
The image stream arrives directly at the detection units 322 from image shift unit 84. Each individual portion of the image stream arrives at all 3 detection units simultaneously.
The database stream comprises a 2.5 WP wide column. In other words, in each time unit, an array of 2.times.5 database HP is provided to each detection module 320. The database stream arrives at the detection modules 320 via a DB delay unit 330. DB delay unit 330 is operative to delay the DB streams for each of the 3 detection units such that the three detection units may simultaneously operate to inspect three respective distinct sets of 12 database locations each. The relative delay of the database stream between adjacent detection units 322 is two rows of HP's because, as may be appreciated by a comparison of FIG. 14 and FIG. 15, the relative displacement of portions of the reference image for which adjacent detection units are responsible is two rows of HP's.
The threshold data stream is received by a threshold delay unit 332 which is operative to simultaneously provide to each of the three detection units, a threshold stream suitable to the respective geometry of the distinct set of database locations for which that detection unit is responsible. The relative delay of the threshold stream between adjacent detection units 322 is two rows of HP's because, as may be appreciated by a comparison of FIG. 14 and FIG. 15, the relative displacement of portions of the reference image for which adjacent detection units are responsible is two rows of HP's.
The detection units 322 are operative to perform steps 240 and 242 of the defect detection method of FIG. 11, as described in detail above. The detection units 322 are also operative to perform the unit-level stage of step 244 of the defect detection method of FIG. 11. Specifically, as explained above, each unit 322 is operative to combine the per-region and per-edge neighborhood results obtained for each of the 12 translations for which that unit is responsible into a single per-region result and a single per-edge neighborhood result. As explained above, the output of the unit-level stage of step 244 performed by each unit 322 comprises a unit-level regional result, a unit-level local result and a unit-level regional translation map.
The three-component output of each of the 3 detection units 322 are received by a result merging unit 334. Result merging unit 334 is operative to merge the 3 unit-level regional results, using an OR operation, to provide a module-level regional result (MLRR), described above, which indicates the existence of a defect in a current region. The MLRR is transmitted to result merging unit 328 of FIG. 16.
Result merging unit 334 is also operative to merge the 3 unit-level local results, using an OR operation, to provide a module-level local result (MLLR), described above, which indicates the existence of a defect in a current edge neighborhood. The MLLR is transmitted to result merging unit 328 of FIG. 16.
Result merging unit 334 is also operative to merge the 3 unit-level regional translation maps, using an OR operation, in order to provide a module-level regional translation map. The map is provided to alignment computation unit 88 of FIG. 6 in concatenation with 8 other module-level regional translation maps provided by the remaining 8 modules 320.
Reference is now made to FIG. 18 which illustrates an individual defect detection unit 322. As described above, in each time unit, each individual detection unit 322 inspects, in parallel, the legitimacy of 12 translations with respect to some current region and with respect to some current edge neighborhood.
Each detection unit 322 comprises a comparing unit 336 which receives the database stream from database delay unit 330 of FIG. 17, the image stream, including E.sub.-- POSITION data, from image shift unit 84 of FIG. 6, and threshold stream data from threshold delay unit 332 of FIG. 17. Comparing unit 336 is operative to perform step 240 of FIG. 11 for 12 translations from among the 324 translations inspected by the defect detection subsystem 86 (FIG. 6) as a whole. Step 240 is performed in both regional and local modes. The output of comparing unit 336 from the regional and local modes preferably comprises 12 regional comparison values and 12 local comparison values, respectively, for each image location.
Preferred methods which may be employed by comparing unit 336 in order to perform step 240 of FIG. 11 in the regional and local modes are described below with reference to FIGS. 19 and 20, respectively.
The 12 regional comparison values for each image location are supplied to a regional combining unit 338 which combines the regional comparison values for all image locations within each image region in accordance with step 242 of the method of FIG. 11. The output of regional combining unit 338 comprises 12 regional entity-specific legitimacy values (RESLV's) for each of the respective 12 translations for which the individual detection unit 322 is responsible.
The 12 local comparison values for each 2.times.2 image location are supplied to a local combining unit 340 which combines the local comparison values for all 2.times.2 image locations within each edge neighborhood in the image in accordance with step 242 of the method of FIG. 11. The output of local combining unit 340 comprises 12 local entity-specific legitimacy values (LESLV's) for each of the respective 12 translations for which the individual detection unit 322 is responsible.
A result merging unit 344 is operative to receive the 12 RESLV's from regional combining unit 338 and the 12 LESLV's from local combining unit 340, and perform the unit-level stage of ORing step 244 of FIG. 11, thereby to obtain a unit-level regional result (ULRR), a unit-level local result (ULLR) and a unit-level legitimate regional translation map, as explained above.
The unit-level regional and local results are provided to result merging unit 334 of FIG. 17 which merges these results with other unit-level regional and local results, respectively, arriving from other detection units. The unit-level legitimate regional translation map is transmitted to result merging unit 334 over a 1-bit. channel.
The various components of FIG. 18 are now described in detail with reference to FIGS. 19-24. First, preferred regional and local methods useful in implementing comparing unit 336 are described with reference to FIGS. 19 and 20, respectively. A preferred structure for comparing unit 336 which implements the methods of FIGS. 19 and 20 is then described with reference to FIGS. 21-23. Finally, units 338 and 340 of FIG. 18 are described with reference to FIGS. 24 and 26 respectively.
Reference is now made specifically to FIG. 19 which illustrates a preferred method, suitable for the regional detection process, which may be employed by comparing unit 336 of FIG. 18 in order to implement step 240 of FIG. 11. In the method of FIG. 19, an individual image location is compared to an individual database location and a binary regional location-specific legitimacy value (RLSLV) is computed. The RLSLV is indicative of the legitimacy of a translation for translating the individual image location to the individual database location.
In order to simplify understanding, the method will be explained with reference to the following sample image and DB locations, represented in half-pixels.
Step 410. Sum HP's within each WP
1. The sum of the four half-pixels within each pixel of the image location and each pixel of the database location is computed. The resulting 2.times.2 sum image and database matrices for the above example are as follows:
Step 412: Compute pixel difference matrix
The absolute values of the differences between corresponding elements in the sum matrices computed in step 410 are now computed. In the present example, the pixel difference matrix is as follows:
Step 414; Compute inequality matrix:
Each half-pixel in the image location is compared to the corresponding half-pixel in the database location, thereby to define a 4.times.4 inequality flag matrix comprising 16 binary values indicative of inequality/equality, here represented as 1 and 0 respectively, of corresponding half-pixels.
The inequality matrix of the above pair of locations is as follows:
1 1 1 1
0 1 1 1
0 0 0 0
1 1 1 1
Step 416: Identify inequality components
Four components are defined which respectively correspond to the four WP's in the image location. The four WP's are termed A, B, C and D in the present discussion, where pixels A, B, C and D are arranged as follows:
A B
C D
Component A is empty if pixel A does not include any 1's. If pixel A includes any 1's, the 1's in pixel A define a sequence of connected 1's, also termed an inequality sequence. In the present example, an 8-connectedness criterion is employed, so the inequality sequence defined by pixel A extends through pixel B. Component A is the set of all pixels which include part of the inequality sequence defined by pixel A. Therefore, in the present example, component A comprises pixels A and B.
Component B is empty unless pixel B includes 1's which are not included in the inequality sequence of pixel A. If component B is not empty, pixel B defines an-inequality sequence and component B is the set of all pixels which include part of the inequality sequence defined by pixel B. In the present example, component B is empty because the only 1's in pixel B are part of the inequality sequence of pixel A.
Component C is empty unless pixel C includes 1's which are not included in the inequality sequences of pixels A and B, if any. If component C is not empty, pixel C defines an inequality sequence and component C is the set of all pixels which include part of the inequality sequence defined by pixel C. In the present example, component C is not empty because both 1's in pixel C are not part of the inequality sequence of pixel A. Therefore, component C comprises pixels C and D.
Component D is empty unless pixel D includes 1's which are not included in the inequality sequences of pixels A, B and C, if any. If component D is not empty, pixel D defines an inequality sequence and component D is the set of all pixels which include part of the inequality sequence defined by pixel D. Component D never includes more than a single pixel, pixel D, because pixels A, B and C are always included in components A, B or C and the components are a partition of the set of pixels A, B, C and D. In the present example, component D is empty because the only 1's in pixel D are part of the inequality sequence of pixel C.
Step 418: Obtain sum of differences for each component
For each of Components A-D, the values of the pixel difference matrix corresponding to the pixels within that component, are summed, thereby to obtain four values SumA, SumB, SumC and SumD. Each value indicates the sum of the differences between image and database in a particular component.
In the present example,
SumA=58; SumB=0; SumC=32; SumD=0.
Step 420: Determine legitimacy of image-database translation The four values SuA, . . . , SumD are compared to a regional comparison threshold which is preferably specific to the location in the database to which the image location is presently being compared. If each of the four is less than the regional comparison threshold, the RLSLV is 1, indicating that the particular translation of the particular image location within the image is legitimate in the regional detection process. If any of the four values exceeds the regional comparison threshold, the RLSLV is 0, indicating illegitimacy of the particular translation for the particular image location in the regional detection process.
In the present example, if a threshold value of 50 is used, the difference value for component.sub.-- A, 58, exceeds the threshold, and hence the legitimacy value accepted is 0.
Reference is now made to FIG. 20 which illustrates a preferred method, suitable for the local detection process, which may be employed by comparing unit 336 of FIG. 18 in order to implement step 240 of FIG. 11. In the method of FIG. 20, an individual image location is compared to an individual database location and a binary local location-specific legitimacy value (LLSLV) is computed. The LLSLV is indicative of the legitimacy of a translation for translating the individual image location to the individual database location.
Steps 430 and 432 of the local legitimacy value computation method of FIG. 20 may be identical to steps 414 and 416 respectively of the regional process legitimacy value computation method of FIG. 19. These steps may be performed only once and the results may be utilized for computation of both the RLSLV, in accordance with steps 418-420 of the method of FIG. 19, and the LLSLV, in accordance with steps 434 and 436 in the method of FIG. 20.
Steps 434 and 436 of the local process legitimacy value computation method of FIG. 20 may be as follows:
Step 434: Categorize components as selected non-selected, other:
Categorization of each component A, B, C and D as either selected, non-selected or other is determined in accordance with the E.sub.-- POSITION values provided for each image location. A component is defined as-selected if it includes a selected pixel and includes no non-selected pixels. In other words, a selected component contains a portion of the selected edge and does not contain any portion of any other edge.
For example, if the E.sub.-- POSITION data for the four WP's of an individual image location is:
then component.sub.-- A is a selected component.
Step 436: Determine legitimacy of I-DB translation:
The selected/nonselected status of components A-D is employed to determine the LLSLV which indicates the legitimacy of the I-DB translation for the local detection process.
Specifically, if none of the components A, B, C and D are selected, the LLSLV is 1. If at least one of components A, B, C and D is selected, the selected ones from among the four values SumA, . . . , SumD are compared to a local comparison threshold which is preferably specific to the location in the database to which the image location is presently being compared.
If each of the selected values from among the four values is less than the local comparison threshold, then the LLSLV is 1, indicating legitimacy of the translation. If any of the selected values from among the four values exceeds the local comparison threshold, the LLSLV is 0, indicating illegitimacy of the translation.
Using the example previously employed with reference to FIG. 19, if the local threshold value is 34 and SUM.sub.-- A=58, the LLSLV is 0.
A preferred structure for comparing unit 336 including apparatus for implementing the above-described methods of FIGS. 19 and 20 is now described with reference to FIGS. 21-23.
Reference is now made specifically to FIG. 21 which is a block diagram of a preferred structure for comparing unit 336 of FIG. 18 which is suitable for implementing the regional and local detection methods described above with reference to FIGS. 19 and 20 respectively. As described above, comparing unit 336 is operative to perform step 240 of FIG. 11, which step is described in further detail in FIGS. 19 and 20, and which step comprises the process of comparing an image location to 12 locations in the database. The output of the comparing step performed by comparing unit 336 comprises 12 regional comparison values and 12 local comparison values.
As seen in FIG. 21, comparing unit 336 preferably comprises a data spanning unit 446 interfacing an array of 12 location comparators 448. The number of location comparators 448 corresponds to the 12 translations for which the detection unit 322 (FIG. 18) of which comparing unit 336 is a part, is responsible. Data spanning unit 446 is operative to perform steps 410, 412 and 414 of the method of FIG. 19, and step 430 of FIG. 20.
The array of location comparators 448 is operative to perform the remaining steps of the methods of FIGS. 19 and 20, namely steps 416, 418 and 420 of the method of FIG. 19, and steps 432, 434 and 436 of the method of FIG. 20. Data spanning unit 446 and location comparators 448 are now described in detail with reference to FIGS. 22 and 23, respectively.
Reference is made specifically to FIG. 22 which is a block diagram of a preferred embodiment of data spanning unit 446. As explained above, data spanning unit 446 implements steps 410, 412 and 414 of the method of FIG. 19, for each of 12 image--database location pairs. Data spanning unit 446 also implements step 430 of the method of FIG. 20, because step 430 of FIG. 20 is identical to step 414 of FIG. 19.
The data spanning unit 446 preferably includes an image WP summing unit 452 which implements step 410 for the image channel, database WP summing and delay units 451 and 453 respectively which implement step 410 for the database channel, an array of 12 WP subtraction units 454 which implements step 412 of FIG. 19, and an array of 12 HP comparing units 456 which implements step 414 of FIG. 19 which is identical to step 430 of FIG. 20. Only two of WP subtraction units 454 and only two of HP comparing units 456 are shown in FIG. 22.
The components of data spanning unit 446 are now described in detail:
The image WP summing unit 452 receives the HP image datastream from image shift unit 84 and sums each group of 4 HP's arriving therefrom. In other words, summing unit 452 provides a WP channel by summing each 4 image HP's into a single image WP (step 410 of FIG. 19 for the image channel).
The database WP summing unit 451 receives the HP database stream from DB delay unit 330 and sums each group of 4 database HP's arriving therefrom into a single database WP (step 410 of FIG. 19 for the database channel). Database WP delay unit 453 is operative to delay the summed data so to create 12 WP channels having the following relative shifts:
(0, 0) (0, 0.5) (0, 1) (0, 1.5) (0, 2) (0, 2.5)
(0.5, 0) (0.5, 0.5) (0.5, 1) (0.5, 1.5) (0.5, 2) (0.5, 2.5).
The relative shifts correspond to the relative locations of the 12 translations for which the individual data spanning unit. 446 is responsible and which are best seen in FIG. 15.
Each WP subtraction unit 454 performs step 412 of the method of FIG. 19 for a single image location and a single database location. Specifically, each individual one of the 12 WP subtraction units 454 receives the WP output channel of summing unit 452, which carries the sum matrix for the image location, and a corresponding one of the 12 WP output channels of delay unit 453, which carries the sum matrix for the database location. The individual subtraction unit 454 computes the absolute differences between corresponding elements in the image and database sum matrices. The absolute differences computed by each individual one of WP subtraction units 454 are provided to a corresponding one of location comparators 448 of FIG. 21.
Each HP comparing unit 456 performs step 414 of the method of FIG. 19 for a single image location and a single database location. Specifically, each individual one of the 12 HP comparing units 456 receives the HP output channel of summing unit 452 and a corresponding one of the 12 HP output channels of delay unit 453. The individual HP comparing unit 456 computes the equality/inequality between corresponding HP's in the image and database streams. The equality/inequality values computed by each individual one of HP comparing units 456 are provided to a corresponding one of location comparators 448 of FIG. 21.
In summary, the data spanning unit 446 of FIG. 22 computes 12 sets of output data, corresponding to the 12 I-DB translations for which the data spanning unit 446 is responsible. The 12 sets of output data are provided to respective ones of the 12 location comparators 448 of FIG. 21. Each of the 12 sets of output data comprises the following data-items:
(a) The absolute values of the differences between corresponding ones of the 4 WP sums in the image and database locations;
(b) A 4.times.4 inequality flag matrix comprising 16 binary values indicative of inequality/equality of corresponding ones of the 16 HP's in image and DB locations; and
(c) Regional and local comparison thresholds.
Data spanning unit 446 also comprises a threshold delay unit 459. Threshold delay unit 459 is operative to introduce delay in the threshold channel received from threshold delay unit 332, so as to provide a suitably delayed database comparison threshold to each of the 12 location comparators 448 of FIG. 21, using the same delay schedule as delay unit 453, in order to take into account the fact that 12 different database locations are simultaneously processed by the array of 12 location comparators 448.
It will be appreciated by persons skilled in the art that, in the illustrated embodiment, the regional and local comparison thresholds employed to determine whether or not the I and DB streams are discrepant are not uniform as inspection of the image and database proceeds but rather vary as a function of the local database geometry as indicated by the FD code. It is appreciated that, alternatively or in addition, the thresholds may vary as a function of the local image geometry. It is further appreciated that, if the thresholds do not vary as a function of local database geometry, threshold delay units 459 of FIG. 22, 332 of FIG. 17 and 326 of FIG. 16 may be eliminated. According to yet another alternative, the regional threshold and local threshold may each be assigned constant values which do not vary as a function of either database or image geometry, in which case threshold selection unit 324 of FIG. 16 may also be eliminated.
Reference is now made to FIG. 23 which is a block diagram of a preferred embodiment of an individual image location comparator unit 448. The image location comparator unit 448 preferably comprises a connected component logic unit 460, a component summing unit 462 and regional (R) and local (L) decision logic units 464 and 466 respectively. Connected components logic unit 460 receives the HP inequality data from HP comparing unit 456 of FIG. 22 and implements step 416 of FIG. 19 by identifying inequality components. Connected components logic 460 also implements step 432 of FIG. 20 which is identical to step 416 of FIG. 19. Component summing unit 462 receives the WP difference matrix computed by WP subtraction unit 454 of FIG. 22 and implements step 418 of FIG. 19 by summing the differences over components. Regional decision logic unit 464 receives the per-component difference sums from component summing unit 462 and implements step 420 of FIG. 19 by comparing each component difference sum to a threshold. Local decision logic unit 466 implements steps 434 and 436 of FIG. 20.
A detailed description of the structure of each of the components of image location comparator 448 and the relationship therebetween appears in Appendix B. Appendix B employs VHDL, which is a hardware description language complying with IEEE standard 1076-1987, recognized as an American National Standard by the ANSI.
Reference is now made to FIGS. 24A & 24B, which taken together form a block diagram of a preferred embodiment of regional combining unit 338 of FIG. 18. Regional combining unit 338 implements step 242 of FIG. 11 for the regional process. In other words, regional combining unit 338 is operative to combine per-translation comparison information over regions.
The regional combining process performed by regional combining unit 338 preferably employs a partition of the image I into a plurality of subregions. As explained above, a plurality of regions each comprising a multiplicity of image locations are defined to cover the image. In the illustrated embodiment, the distance between centers of adjacent regions is 0.5 region lengths along one axis and 0.5 region widths along the other axis. The plurality of subregions may be defined by partitioning each region into four non-overlapping subregions such that the length of each subregion is 0.5 region lengths and the width of each subregion is 0.5 region widths.
Reference is made briefly to FIG. 25 which illustrates an image portion including 9 subregions 1-9. It is appreciated that the image portion of FIG. 25 also includes 4 complete regions A, B, C and D, respectively comprising the following subregions:
A: subregions 1, 2, 4, 5
B: subregions 2, 3, 5, 6
C: subregions 4, 5, 7, 8
D: subregions 5, 6, 8, 9
The regional combining method for implementing step 242 of FIG. 11 includes the following two steps:
(a) Compute subregion legitimacy vector for each subregion:
For each subregion, AND the regional location-specific legitimacy vectors (RLSL vectors) computed in step 240 for each image location, over all image locations included in the subregion. The result of ANDing the RLSL vectors over an individual subregion is termed herein a subregion legitimacy vector.
Regional combining unit 338 includes a subregion combining unit 470 which is operative to perform the above subregion combining step.
(b) Combine subregion legitimacy vectors into region legitimacy vectors:
For each individual region, the subregion legitimacy vectors of each of the typically four subregions included in that region are ANDed. The result is a region legitimacy vector indicating which image-to-database translations of the individual region are legitimate.
Regional combining unit 338 includes a full region combining unit 472 which receives subregion-specific information from subregion combining unit 470 and performs the above full region combining step thereupon.
Subregion combining unit 470 and full region combining unit 472 are now described in detail, still with reference to FIGS. 24A-24B.
Subregion combining unit 470 comprises region control unit 570, data selector unit 574, AND unit 578 and row delay unit 580. Region control unit 570 supplies two signals: first region row and first region column, indicating whether a current image location is in the first row or column, respectively, of the current region, or not. The data that enters sub-regions combining unit 470 is ANDed by AND unit 578 with appropriate data selected by data selection unit 574. Data is selected by unit 574 as follows: If the current image location is in the first column and the first row of a region--a value of all 1's is selected. If the current image location is in the first region column but not in the first row of the region, data delayed from the previous row by row delay unit 580 is selected. If the current image location is not in the first column of the current region, then the result of the last AND operation is selected.
Row delay unit 580 is operative to introduce a one-row delay in data received and is enabled by the "first column" signal provided by region control unit 570. In the illustrated embodiment, there are no more than 32 regions per image row. Therefore, the length of the delay line of row delay unit 580 is, in the illustrated embodiment, 32 12-bit data words.
Full regions combining unit 472 comprises an AND gate 582, a 1-word delay unit 584, an AND unit 586, a 1-row delay unit 588 and an AND unit 590. 1-word delay unit 584 together with AND unit 586 are operative to combine subregions data in a horizontal direction. 1-row delay unit 588 together with AND unit 590 are operative to combine the subregions data in the vertical direction.
Reference is now made to FIG. 26 which is a block diagram of local combining unit 340 of FIG. 18, constructed and operative in accordance with a preferred embodiment of the present invention. As explained above, local combining unit 340 is operative to perform step 242 of the method of FIG. 11, for the local process only. In other words, local combining unit 340 is operative to combine per-image location information comprising LLSL vectors over edge neighborhoods. The result, as described above with reference to FIG. 11, is an ENL vector for each edge neighborhood which indicates the legitimacy of a plurality of I-DB translations for the entire edge neighborhood.
The local combining process performed by local combining unit 340 preferably comprises the following two steps:
(a) The LLSL vector of each image location is ANDed with the LLSL vectors of its two neighbors, as indicated by the two E-NEIGHBORS pointers provided for that image location. The result of the AND operation is an intermediate vector for each image location; and
(b) The intermediate vector of each image location is ANDed with the intermediate vectors of its two neighbors, as indicated by the two E.sub.-- NEIGHBORS pointers provided for that image location. The result of this AND operation is an ENL vector for each individual image location, indicative of the legitimacy of a plurality of I-DB translations for the edge neighborhood centered at the individual image location. The ENL vector for a particular edge neighborhood, when computed as above, equals the ANDed combination of the 5 LLSL vectors corresponding to the 5 image locations included in that edge neighborhood, due to the associativity of the AND function.
Referring again to FIG. 26, local combining unit 340 preferably comprises a first neighbor operator 490 for receiving local location-specific legitimacy values (LLSLV's) from comparing unit 336 of FIG. 18 and performing ANDing step (a), above, thereupon. Local combining unit 340 also preferably comprises a second neighbor operator 492 for receiving the output of first neighbor operator 490 and performing ANDing step (b) thereupon. Both neighbor operators 490 and 492 receive E-NEIGHBORS data from image shift unit 84 of FIG. 6. The E-NEIGHBORS data is received by second neighbor operator 492 via a delay unit 494. Delay unit 494 is operative to introduce a suitable delay in the E-NEIGHBORS data, preferably a two cycle delay, where a cycle is the time required for each neighbor operator to AND a single image location with its two neighbors.
The first neighbor operator unit 490 comprises a neighbors selection units 496 which spans 3 rows of data. In other words, neighbor operator unit 490 is operative to simultaneously supply LLSL vectors for a current image location and two neighbors thereof. Neighbor operator unit 490 also comprises an ANDing unit 498 for ANDing the three outputs of neighbors selection unit 496.
Second neighbor operator unit 492 may be substantially identical to first neighbor operator 490.
It is appreciated that designation in the specification of the number of bits per stream of data is merely intended to clarify the description of the illustrated embodiment and, being merely exemplary, is not intended to be limiting.
It will be appreciated by persons skilled in the art that the present invention is not limited to what has been particularly shown and described hereinabove. Rather, the scope of the present invention is defined only by the claims that follow:
Claims
We claim:
1. A method for aligning first and second digital representations of an image, the method comprising, for each individual large location from among a plurality of relatively large locations covering the first digital representation: for each individual translation from among a plurality of translations from the first digital representation to the second digital representation: for each individual small location from among a multiplicity of relatively small locations included in the individual large location, determining a binary legitimacy value of the individual translation for the individual small location, the binary legitimacy value comprising: a legitimacy-indicating value if the translation translates the small location onto a small location of similar appearance within the second digital representation: and a non-legitimacy-indicating value if the translation translates the small location onto a small location of dissimilar appearance within the second digital representation; combining the binary legitimacy values of the small locations included in the individual large location into a success score representing the success of the individual translation in translating the individual large location; and improving the alignment of the first and second digital representations by operating an individual translation on the individual large location, wherein the individual translation is selected from the plurality of translations on the basis of the success score of the individual translation for the individual large location, wherein success of a translation in translating a large location is an increasing function of the number of small locations within the large locations whose binary legitimacy value comprises said legitimacy-indicating value.
2. Apparatus for aligning first and second digital representations of an image, the apparatus comprising, for each individual large location from among a plurality of relatively large locations covering the first digital representation: a per-large location success score generator operative to generate a success score for each individual translation from among a plurality of translations from the first digital representation to the second digital representation, the success score representing the success of the individual translation in translating the individual large location, the success score generator comprising: a per-small location binary legitimacy value generator operative to generate, for each individual small location from among a multiplicity of relatively small locations included in the individual large location, a binary legitimacy value of the individual translation for the individual small location, the binary legitimacy value comprising: a legitimacy-indicating value if the translation translates the small location onto a small location of similar appearance within the second digital representation, and a non-legitimacy-indicating value if the translation translates the small location onto a small location of dissimilar appearance within the second digital representation; and a small-location result combining unit operative to combine the binary legitimacy values of the small locations included in an individual large location into a success score thereof; and an alignment unit operative to improve the alignment of the first and second digital representations by operating an individual translation on an individual large location, wherein the individual translation is selected from the plurality of translations on the basis of the success score of the individual translation for the individual large location, wherein success of a translation in translating a large location is an increasing function of the number of small locations within the large locations whose binary legitimacy value comprises said legitimacy-indicating value.
3. A method according to claim 1 wherein the image comprises a patterned object employed in the course of manufacturing semiconductors.
4. The method of claim 1, further comprising the step of: announcing a defect in the individual large location if the success score thereof is outside a permitted threshold.
5. The method of claim 1, further comprising the step of: announcing a defect if at least one selected individual translation of an individual large location is mutually discrepant from selected individual translation for other individual large location of the first digital representation.
6. The method of claim 1, wherein the step of combining the binary legitimacy values comprises an AND function.
7. The apparatus of claim 2, further comprising a defective entity announcing unit operative to announce a defect for an individual large location if the success score thereof is outside a permitted threshold.
8. The apparatus of claim 2, further comprising a translation discrepancy analyzer operative to announce a defect if at least one selected individual translation of an individual large location is mutually discrepant from selected individual translation for other individual large location of the first digital representation.
9. The apparatus of claim 2, wherein the small-location result combining unit comprises an AND circuit.