Method and apparatus for flash correlation

• US 5,982,932 A
• Filed: 12/09/1996
• Issued: 11/09/1999
• Est. Priority Date: 09/16/1992
• Status: Expired due to Term

• Current Assignee: Mikos Limited
• Original Assignee: Mikos Limited
• Inventors: Prokoski, Francine J.
• Primary Examiner(s): Tadayon, Bijan
• Assistant Examiner(s): Novik, Dmitry A.
• Application Number:
  US08/762,102
• Time in Patent Office: 1,065 Days
• Field of Search: 382/278, 382/141, 382/142, 382/209, 382/218, 382/219, 382/220, 382/221, 382/215, 382/224, 382/228, 359/560, 359/561, 386/4, 386/6-8, 386/46, 386/52, 386/65, 386/68-70
• US Class Current: 382/224
• CPC Class Codes: G06F 17/153 Multidimensional correlation or convolution
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: G06V 20/80 Recognising image objects characterised by unique random patterns

Abstract

Flash correlation instantaneously compares two or more patterns to determine whether they are the same or essentially the same, regardless of the complexity of the images, and in spite of the addition of noise, local changes, and variations in resolution and focus. Flash correlation artifacts also provide cues to quantitative assessment of relative movement, stretching, blurring, and warping of one image with respect to the other. Presence of a flash correlation artifact between two stacks of patterns is sufficient to identify the stacks as containing at least one pair of massively correlated patterns. Precise control of registration, image size and orientation is not required. An image may be combined with other images, either by overlays or concatenation, and still be identified. A Flash correlation engine may utilize optical, analog or digital processing to provide rapid sorting, classification, and identification functions with minimal computational complexity.

Claims

1. A method of determining whether and to what degree a first array of dispersed elements has changed with time, said first array created at a first instance in time, said method comprising the steps of:

a) creating at a second instance in time not earlier than said first time instance a second array of dispersed elements;

b) overlaying in a spatial domain said first and second arrays;

c) imparting a rotational movement to at least one of said first and second arrays relative to the other of said first and second arrays; and

d) determining the strength of a correlation artifact to indicate the degree of similarity between said first and second arrays.

2. The change determining method of claim 1, wherein said dispersed element of said first and second arrays have varying intensity values and there is included before step b) a step of inverting the intensity values of said dispersed elements of one of said first and second arrays with respect to said dispersed elements of the other of said first and second arrays.

3. The change determining method of claim 1, wherein before step b) there is included a step of sampling said dispersed elements of said first array in a given fashion to provide said first sampled array, said dispersed elements of said second array to be sampled in said given fashion to provide said second sampled array before the degree of similarity between said first and second arrays is determined in step d).

4. The change determining method of claim 1, wherein before step b) there is included a step of rearranging said first and second arrays in a like manner to provide scrambled first and second arrays respectively.

5. The method of change determining of claim 1, wherein there is further included the steps of affixing a reference pattern to an article, capturing at said first time instance an image of the article with the affixed reference pattern thereon as said first array of elements, capturing at the second time instance an image of the article with the affixed reference pattern thereon as said second array of elements, the strength of said correlation artifact indicating the degree of similarity with said reference pattern.

6. The change determining method of claim 5 as applied to a process for manufacturing an article, wherein said second array represents a properly manufactured article and the presence of said correlation artifact indicates a properly manufactured article.

7. The change determining method of claim 6, wherein said manufacturing process comprises the steps of:

1) affixing said reference pattern to the article before said step of capturing said first array of dispersed elements is performed;

2) subjecting said article to at least one manufacturing step whereby said reference pattern may be changed; and

3) performing steps b, c and d to determine whether said article is being properly manufactured.

8. The change determining method of claim 7, wherein after step c), rotating one of said first and second arrays with respect to the other about a point so that said first and second arrays of dispersed elements are rotationally unaligned, to produce a composite array of the combined elements therefrom.

9. The change determining method of claim 8, wherein there is further included the step of sensing first and second average intensities respectively of all of the combined elements within first and second distinct areas of said composite array.

10. The change determining method of claim 9, wherein there is further included the step of detecting the presence of said correlation artifact produced by the combined elements of the composite array by determining a variation between said first and second average intensities greater than a selected threshold value to indicate a properly manufactured article and by determining a variation of said first and second average intensities not greater than said selected threshold value to indicate the absence of said correlation artifact to indicate an improperly manufactured article.

11. The change determining method of claim 5, wherein the reference pattern has been warped to impose scalar distortions Sx and Sy on said second array, and there is further included a step of dewarping said second array so that its scale and orientation at one of a plurality of x,y grid points of predetermined increments correspond to the scale and orientation of said first array.

12. The change determining method of claim 11, wherein said dewarping step includes the steps of:

after step c) rotating one of said first and second arrays through an angle θ

with respect to the other;

moving one of said first and second arrays a predetermined distance, Δ

_x, in a first direction;

measuring the corresponding displacements C_x, C_y, of said correlation artifact, C_x being parallel to the first direction, and C_y being perpendicular to the first direction;

subsequently moving said one array a predetermined distance, Δ

_y, in a second direction, perpendicular to the first direction;

measuring the corresponding displacements D_x, D_y, of said correlation artifact, D_x being perpendicular to the second direction, and D_y being parallel to the second direction;

evaluating the rotation angle, θ

, and scalar distortions S_x, S_y, between said first and second arrays at the location of said correlation artifact using the measured displacements according to following relationships;

##EQU25## repositioning at least one of the images under said correlation artifact according to the following relationships;

space="preserve" listing-type="equation">δ

.sub.x =x.sub.o (1-[X]S.sub.x cos θ

)+y.sub.o S.sub.x sin θ

space="preserve" listing-type="equation">δ

.sub.y =-x.sub.o S.sub.y sin θ

+y.sub.o (1-S.sub.y cos θ

)

where x_o, y_o are the coordinates of the x, y grid point in said second array, and

δ

_x, δ

_y are the distances along the respective axes that the record information at the grid point (x_o, y_o) must be moved to dewarp the array information for that grid point; and

repeating the foregoing steps for each x,y grid point.

13. The change determining method of claim 12, wherein there is further included the steps of:

generating a superimposed image of said dewarping second array and said corresponding first array; and

inspecting said superimposed image to identify regions at variance with corresponding regions of said first array to thereby identify changes occurring in the reference pattern.

14. A method of examining a sequence of images including the method of determining as claimed in claim 1, wherein a sequence of images includes at least first and second images, and said first and second arrays of dispersed elements correspond respectively to the first and second images, and there is further included the steps of storing at said first time instance said first array, and executing steps b) and c) to indicate the presence of said correlation artifact as an indication of similarity between the first and second images.

15. The image examining method as claimed in claim 14, wherein the image sequence comprises a plurality of images, and the first and second image are spaced apart.

16. The image examining method as claimed in claim 15, wherein each of the plurality of images is approximately the same size and the first and second images are spaced a selected number of images apart.

17. The image examining method as claimed in claim 16, wherein the image sequence includes at least two sets of sequential images corresponding to distinct scenes, using the absence of said correlation artifact to identify a change of scenes.

18. The image examining method as claimed in claim 17, wherein the image sequence is recorded on a video recording medium.

19. A method of automatic advancing to the next scene of images recorded on the video recording medium including the image examining method of claim 18, wherein detecting the absence of said correlation artifact terminates the advancing of the video recording medium to view the first image on the next scene.

20. A method of automatic advancing to the next scene of images stored on the video recording medium including the image examining method of claim 18, wherein the video recording medium is automatically advanced as long as correlation artifact is present.

21. A method of determining whether an unknown article is one of a plurality of known articles including said change determining method of claim 1, further including the steps of:

capturing an image of the plurality of known articles to provide a corresponding plurality of first arrays of dispersed elements;

creating a database of said plurality of first arrays;

said step a) including capturing an image of the unknown article to provide said second array of dispersed elements;

said steps b), c) and d) including overlaying said second array on said database and using flash correlation to identify the strongest match between said second array and one of said plurality of arrays.

22. The method of determining of claim 21, wherein the unknown and plurality of articles are fibers of varying sizes, colors, and shapes.

23. The method of determining of claim 22, wherein each of said capturing steps takes an image of a pattern previously applied to each of said known and unknown articles.

24. The method of determining of claim 23, wherein the applied patterns are tooling marks on fired bullets and shell casings.

25. The method of determining of claim 23, wherein the applied pattern are printed information including bar codes.

26. The method of claim 23, wherein the applied patterns are biometric indicators.

27. A method of determining the degree of similarity between a first array of dispersed elements and a second array of dispersed elements, said method comprising the steps of:

a) providing said first and second arrays;

b) overlaying in a spatial domain said first and second arrays;

c) imparting a rotational movement to at least one of said first and second arrays relative to the other of said first and second arrays; and

d) determining the strength of a correlation artifact to indicate the degree of similarity between said first and second arrays.

28. The change determining method of claim 27, wherein said rotational movement occurs about a point, and said point is disposed within said spatial domain of said overlaid first and second arrays.

29. The change determining method of claim 27, wherein said dispersed elements of said first and second arrays have varying intensity values and there is included before step b) a step of inverting the intensity values of said dispersed elements of one of said first and second arrays with respect to said dispersed elements of the other of said first and second arrays.

30. The change determining method of claim 27, wherein before step b) there is included a step of sampling said dispersed elements of said first array in a given fashion to provide said first sampled array, said dispersed elements of said second array to be sampled in said given fashion to provide said second sampled array before the degree of similarity between said first and second sampled arrays is determined in step d).

31. The change determining method of claim 27, wherein before step b) there is included a step of rearranging said first and second arrays in a like manner to provide scrambled first and second arrays respectively.