High precision image alignment detection

• US 6,295,083 B1
• Filed: 02/27/1998
• Issued: 09/25/2001
• Est. Priority Date: 02/27/1998
• Status: Expired due to Term

• Current Assignee: Tektronix Incorporated (Fortive Corp.)
• Original Assignee: Tektronix Incorporated (Fortive Corp.)
• Inventors: Kuhn, Alexander
• Primary Examiner(s): Eisenzopf, Reinhard J.
• Assistant Examiner(s): DESIR, JEAN WICEL
• Application Number:
  US09/032,640
• Time in Patent Office: 1,306 Days
• Field of Search: H04/N 1.700, 348/180, 348/181, 348/185, 348/189, 348/190, 348/192, 348/461, 348/473, 348/263, 348/806, 348/807, 348/745, 348/746, 348/747, 348/658, 382/294, 382/151
• US Class Current: 348/190
• CPC Class Codes: G06T 2207/20016 Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
• CPC Class Codes: G06T 2207/30168 Image quality inspection
• CPC Class Codes: G06T 7/0002 Inspection of images, e.g. flaw detection
• CPC Class Codes: G06T 7/32 using correlation-based methods
• CPC Class Codes: H04N 17/004 for digital television systems

Abstract

High precision image alignment detection uses an iterative part pixel shift detection algorithm to accurately determine the displacement of a received image with respect to a reference image. An alignment pattern is inserted into the original image and a portion of the alignment pattern, such as a single line, also is stored as a reference image. Using cross-correlation the received image is compared with the reference image to locate the alignment pattern, and selected portions of the received image alignment pattern are then used in conjunction with the reference image to determine the total pixel shift of the received image. An integer pixel shift is determined by cross-correlation of the received alignment pattern with the reference image. Using the integer pixel shift to identify a starting point, data is extracted from the received alignment pattern about a specific feature and a part pixel shift is measured. The received alignment pattern is then shifted by the part pixel shift, the data is again extracted and an additional part pixel shift is measured. These steps are iterated, using the sum of all prior part pixel shifts for each subsequent shift. At completion the total of the integer pixel shift value and all the part pixel shift values determines the pixel shift required for registration of the received image vis a vis the original image.

Claims

1. A method of high precision image alignment detection for registering an image with a reference image comprising the steps of:

locating a multiple line alignment pattern in the image by cross-correlation with a reference image corresponding to the alignment pattern; and

iteratively detecting a precision part pixel shift value for the image using data points from the image determined by an integer pixel shift value achieved by cross-correlation of the reference image and a portion of the located alignment pattern from the image, the data points being measured to determine an initial part pixel shift value and each successive iteration being performed on the data points for the image as shifted by the sum of the part pixel shift values from prior iterations until the precision part pixel shift value is achieved according to specified end conditions.

2. The method as recited in claim 1 wherein the locating step comprises the steps of:

cross-correlating the image with the reference image, the image having the alignment pattern inserted therein and the reference image corresponding to one line of the alignment pattern, to locate an approximate initial point of the alignment pattern in the image; and

cross-correlating the image with the reference image over a limited search area determined by the approximate initial point to select the central lines of the alignment pattern from the image as the image for processing by the detecting step.

3. The method as recited in claim 1 wherein the detecting step comprises the steps of:

cross-correlating selected lines of the alignment pattern from the image with the reference image to determine the integer shift pixel value;

measuring a selected series of data points centered on specific features of the alignment pattern from the image, the data points being selected as a function of the integer shift pixel value, to determine the initial part pixel shift value;

shifting the selected lines of the alignment pattern according to the initial part pixel shift value by interpolation;

repeating the measuring and shifting steps, the shifting step in each iteration being a function of the total of the part pixel shift values for all prior iterations starting with the initial part pixel shift value, until a specified end condition is achieved, the sum of all iterations being the precision part pixel shift value.

4. The method as recited in claim 3 wherein the detecting step further comprises the step of multiplying the total part pixel shift values from the prior iterations by a corrector value prior to shifting the selected lines of the alignment pattern in the shifting step.

5. The method as recited in claims 3 or 4 wherein the detecting step further comprises the steps of:

shifting the selected lines of the alignment pattern by one-half pixel if the initial part pixel shift value exceeds a specified threshold; and

cross-correlating the selected lines of the alignment pattern for the image as shifted by the first iteration of the shifting step with the reference image to redetermine the integer pixel shift value prior to the first iteration of the measurement step.

6. The method as recited in claim 5 wherein the detecting step further comprises the step of cross-correlating the selected lines of the alignment pattern from the image as shifted by each subsequent iteration of the shifting step with the reference image to redetermine the integer pixel shift value prior to each subsequent iteration of the measuring step.