Methods and apparatus for alignment of images

• US 5,054,097 A
• Filed: 11/23/1988
• Issued: 10/01/1991
• Est. Priority Date: 11/23/1988
• Status: Expired due to Term

• Current Assignee: Credence Systems Corporation (COHU Incorporated)
• Original Assignee: Schlumberger Technologies Incorporated (SLB)
• Inventors: Concina, Stefano E., Flinois, Xavier A.
• Primary Examiner(s): Razavi, Michael
• Assistant Examiner(s): Jung, Yon
• Application Number:
  US07/276,359
• Time in Patent Office: 1,042 Days
• Field of Search: 382/47, 382/48, 382/45.44, 382/27, 382/42, 382/23, 356/23, 356/24, 356/25, 364/728.01, 364/728.03, 364/723, 358/428, 358/139
• US Class Current: 382/294
• CPC Class Codes: G06T 3/153 using elastic snapping
• CPC Class Codes: G06T 5/80 Geometric correction

Abstract

Methods and apparatus are disclosed for rapid and interactive "warping" of a first image made up of pixels to form a resulting image made up of pixels which are aligned, pixel-for-pixel, with a second image made up of pixels. The images may be stroboscopic voltage contrast images representing operating states of two integrated circuit devices--a failing device and a fully functional device. The aligned images permit an engineer who may have little knowledge of the device to diagnose dynamic failures of the failing device by comparing the aligned images to produce an image showing the differences.

Claims

1. A method of preparing from a first image a resultant image which is aligned pixel-for-pixel with a second image, each said image comprising a set of machine-displayable pixels and having visible features defined by said pixels when displayed, each pixel defined by a display coordinate position and an intensity value, comprising the steps of:

a. i. recording coordinate positions of at least three selected features of said first image,

ii. recording coordinate positions of at least three selected features of said second image with which said at least three selected features of said first image are to be aligned in a resultant image, and

iii. calculating from said recorded coordinate positions a matrix of floating point values from which coordinate positions of said first image can be mapped into respective coordinate positions of said resultant image;

b. transforming said matrix of floating point values into respective fixed point representations;

c. using said fixed point representations to calculate with fixed point arithmetic, for each display coordinate position of said resultant image, a corresponding coordinate position of said first image; and

d. extrapolating a resultant image pixel intensity value for each display coordinate position of said resultant image, from intensity values of pixels surrounding said corresponding coordinate position of said first image, thereby producing a set of pixels defining said resultant image;

whereby said resultant image comprises a version of said first image having features aligned with features of said second image, the pixels of said resultant image being aligned with respective display coordinate positions of pixels of said second image.

2. The method of claim 1, wherein said first and second images are stroboscopic voltage contrast images produced by an electron-beam test system and are representative of integrated circuit operating states.

3. The method of claim 1, wherein step a. further comprises the step of displaying said first and second images on a display screen.

4. The method of claim 1, wherein said values representative of said selected features are recorded with sub-pixel precision.

5. The method of claim 1, wherein said matrix comprises a 2×

2 matrix of values representing factors for correction of rotation, tilt and magnification distortion between said first and second images.

6. The method of claim 1, wherein step b. includes storing said fixed point representations in a register, and wherein step c. comprises calculating said corresponding coordinate positions of said first image in a microprocessor device.

7. The method of claim 1, wherein step d. comprises the steps of:

i. calculating floating point values representing distances between said corresponding coordinate position and said pixels surrounding said corresponding coordinate position.

ii. converting said floating point values representing distances into fixed point values representing distances, and

iii. calculating said resultant image pixel intensity value from said fixed point values representing distances and from said intensity values of pixels surrounding said corresponding coordinate position in a processor employing fixed point arithmetic,

such that said resultant pixel intensity value comprises an average of intensity values of said pixels surrounding said corresponding coordinate position, said average being weighted by said fixed point values representing distances.

8. The method of claim 1, further comprising the steps of calculating a table of fixed-point values, each value of said table representing a weighted contribution of one of said pixels surrounding said corresponding coordinate position to said resultant image pixel intensity value, and storing said table of values, wherein step d. further comprises the step of retrieving a value from said table for each of said pixels surrounding said corresponding coordinate position and combining said retrieved values to form said resultant image pixel intensity value.

9. The method of claim 8, wherein each stored value of said table is associated with a stored index value, and wherein said step of retrieving a value from said table comprises the steps of (i.) calculating a calculated index value from the intensity value of at least one of said pixels surrounding said corresponding coordinate position and from respective distances between said at least one of said pixels surrounding said corresponding coordinate position and said corresponding coordinate position, and (ii.) matching said calculated index value with said stored index value to select a stored value to be retrieved from said table.

10. Apparatus for preparing from a first image a resultant image which is aligned pixel-for-pixel with a second image, each said image comprising a set of pixels capable of being displayed on a visual display terminal and having visible features defined by said pixels when displayed, each pixel defined by a display coordinate position and an intensity value, comprising:

I. recording means for;

a. recording coordinate positions of at least three selected features of said first image, and

b. recording coordinate positions of at least three selected features of said second image with which said at least three selected features of said first image are to be aligned in a resultant image; and

II. computing means for;

a. calculating from said coordinate positions recorded in said recording means a matrix of floating point values from which coordinate positions of said first image can be mapped into respective coordinate positions of said resultant image;

b. transforming said matrix of floating point values into respective fixed point representations;

c. using said fixed point representations to calculate with fixed point arithmetic, for each display coordinate position of said resultant image, a corresponding coordinate position of said first image; and

d. extrapolating a resultant image pixel intensity value for each display coordinate position of said resultant image, from intensity values of pixels surrounding said corresponding coordinate position of said first image, thereby producing a set of pixels defining said resultant image;

whereby said set of pixels defining said resultant image comprises a version of said first image having features aligned with features of said second image, the pixels of said resultant image being aligned with respective display coordinate positions of pixels of said second image.

11. The apparatus of claim 10, further comprising electron-beam probe means for acquiring said first and second images as stroboscopic voltage contrast images representative of integrated circuit operating states.

12. The apparatus of claim 10, further comprising means for is displaying said first and second images on a display screen.

13. The apparatus of claim 10, wherein said recording means is capable of recording values representative of said selected features with sub-pixel precision.

14. The apparatus of claim 10, wherein said matrix comprises a 2×

2 matrix of values representing factors for correcting of rotation, tilt and magnification distortion between said first and second images.

15. The apparatus of claim 10, further including means for storing said fixed point representations.

16. The apparatus of claim 10, wherein said computing means comprises means for (i) calculating floating point values representing distances between said corresponding coordinate position and said pixels surrounding said corresponding coordinate position, (ii) converting said floating point values representing distances into fixed point values representing distances, and (iii) calculating said resultant image pixel intensity value from said fixed point values representing distances and from said intensity values of pixels surrounding said corresponding coordinate position, employing fixed point arithmetic, such that said resultant image pixel intensity value comprises an average of the intensity values of said pixels surrounding said corresponding coordinate position, said average being weighted by said fixed point values representing distances.

17. The apparatus of claim 10, further comprising table means for calculating a table of fixed-point values, each value of said table representing a weighted contribution of one of said pixels surrounding said corresponding coordinate position to said resultant image pixel intensity value, and storing said table of values, and wherein said computing means comprises means for retrieving a value from said table for each of said pixels surrounding said corresponding coordinate position and means for combining said retrieved values to form an extrapolated resultant image pixel intensity value.

18. The apparatus of claim 17, wherein each stored value of said table is associated with a stored index value, and wherein said computing means comprises means for retrieving a value from said table, calculating a calculated index value from the intensity value of at least one of said pixels surrounding said corresponding coordinate position and from respective distances between said at least one of said pixels surrounding said corresponding coordinate position to said corresponding coordinate position, and matching said calculated index value with said stored index value to select a stored value to be retrieved from said table.

19. A method of preparing from a first image a resultant image which is aligned pixel-for-pixel with a second image, each said image comprising a set of machine-displayable pixels and having visible features defined by said pixels when displayed, each pixel defined by a display coordinate position and an intensity value, comprising the steps of:

a. calculating a matrix of floating point values from which coordinate positions of said first image can be mapped into respective coordinate positions of said resultant image;

b. transforming said matrix of floating point values into respective fixed point representations;

c. using said fixed point representations to calculate with fixed point arithmetic, for each display coordinate position of said resultant image, a corresponding coordinate position of said first image; and

d. extrapolating a resultant image intensity value for each display coordinate position of said resultant image to produce a set of pixels defining said resultant image, said step of extrapolating comprising the steps of, for each said display coordinate position of said resultant image;

i. calculating floating point values representing distances from said corresponding coordinate position to pixels of said first image surrounding said corresponding coordinate position,

ii. converting said floating point values into fixed point values, and

iii. calculating said resultant image pixel value from said fixed point values and from intensity values of pixels of said first image surrounding said corresponding coordinate position such that said resultant image pixel value comprises an average of intensity values of pixels of said first image surrounding said corresponding coordinate position, said average being weighted by said distance values;

whereby said resultant image comprises a version of said first image having features aligned with features of said second image, and having pixels aligned with respective display coordinate positions of pixels of said second image.

20. A method of preparing from a first image a resultant image which is aligned pixel-for-pixel with a second image, each said image comprising a set of machine-displayable pixels and having visible features defined by said pixels when displayed, each pixel defined by a display coordinate position and an intensity value, comprising the steps of:

a. calculating a matrix of floating point values from which coordinate positions of said first image can be mapped into respective coordinate positions of said resultant image;

b. transforming said matrix of floating point values into respective fixed point representations;

c. using said fixed point representations to calculate with fixed point arithmetic, for each display coordinate position of said resultant image, a corresponding coordinate position of said first image;

d. extrapolating a resultant image pixel intensity value for each display coordinate position of said resultant image, from intensity values of pixels surrounding said corresponding coordinate position of said first image, to produce a set of pixels defining said resultant image, said step of extrapolating comprising the steps of, for each said display coordinate position of said resultant image;

i. retrieving a first value from pre-calculated table of fixed-point values, said first value representing a weighted contribution of the values of a first pair of surrounding pixels to said resultant pixel intensity value,

ii. retrieving a second value from a pre-calculated table of fixed-point values, said second value representing a weighted contribution of the values of a second pair of surrounding pixels to said resultant pixel intensity value, and

iii. combining said first value and said second value to form said resultant pixel intensity value;

whereby said resultant image comprises a version of said first image having features aligned with features of said second image and having pixels aligned with respective display coordinate positions of pixels of said second image.

21. The method of claim 20, wherein each value of said pre-calculated table is associated with a stored index value, and wherein retrieving a value from said table comprises the steps of calculating a calculated index value from the value of at least one said surrounding pixel and from the distances of said at least one surrounding pixel to said corresponding coordinate position, and matching said calculated index value with said stored index value to select a value to be retrieved from said table.

22. Apparatus for preparing from a first image a resultant image which is aligned pixel-for pixel with a second image, each said image comprising a set of pixels capable of being displayed on a visual display terminal and having visible features defined by said pixels when displayed, each pixel defined by a display coordinate position and an intensity value, comprising:

a. means for calculating a matrix of floating point values from which coordinate positions of said first image can be maped into respective coordinate positions of said resultant image;

b. means for transforming said matrix of floating point values into respective fixed point representations;

c. means for using said fixed point representations to calculate with fixed point arithmetic, for each display coordinate position of said resultant image, a corresponding coordinate position of said first image; and

d. means for extrapolating a resultant image pixel intensity value for each display coordinate position of said resultant image, from intensity values of pixels surrounding said corresponding coordinate position of said first image, to produce a set of pixels defining said resultant image, said extrapolating means comprising means for;

i. calculating floating point values representing distances from said corresponding coordinate position to said pixels surrounding said corresponding coordinate position,

ii. converting said values representing distances into fixed point values, and

iii. calculating said resultant image pixel intensity value from said fixed point values and from intensity values of pixels surrounding said corresponding coordinate position in a processor employing fixed point arithmetic such that said resultant image pixel value comprises an average of said surrounding pixel intensity values, said average being weighted by said distance values.

whereby said set of pixels defining said resultant image comprises a version of said first image having features aligned with features of said second image and having pixels aligned with respective display coordinate positions of pixels of said second image.

23. Apparatus for preparing from a first image a resultant image which is aligned pixel-for pixel with a second image, each said image comprising a set of pixels capable of being displayed on a visual display terminal and having visible features defined by said pixels when displayed, each pixel defined by a display coordinate position and an intensity value, comprising:

a. means for calculating a matrix of floating point values from which coordinate positions of said first image can be mapped into respective coordinate positions of said resultant image;

b. means for transforming said matrix of floating point values into respective fixed point representations;

c. means for using said fixed point representations to calculate with fixed point arithmetic, for each display coordinate position of said resultant image, a corresponding coordinate position of said first image; and

d. means for extrapolating a resultant image pixel intensity value for each display coordinate position of said resultant image, from intensity values of pixels surrounding said corresponding coordinate position of said first image, to produce a set of pixels defining said resultant image, said extrapolating means comprising means for;

i. retrieving a first value from a pre-calculated table of fixed-point values, said first value representing a weighted contribution of the values of a first pair of surrounding pixels to said resultant pixel intensity value,

ii. retrieving a second value from a pre-calculated table of fixed-point values, said second value representing a weighted contribution of the values of a second pair of surrounding pixels to said resultant pixel intensity value, and

iii. combining said first value and said second value to form said resultant pixel intensity value;

whereby said set of pixels defining said resultant image comprises a version of said first image having features aligned with features of said second image and having pixels aligned with respective display coordinate positions of pixels of said second image.

24. The apparatus of claim 23, wherein each stored value of said table is associated with a stored index value, and wherein said extrapolating means comprises means for calculating a calculated index value from the value of at least one said surrounding pixel and from the distances of said at least one surrounding pixel to said corresponding coordinate position, and matching said calculated index value with said stored index value to select a value to be retrieved from said table.