Method and apparatus for flash correlation

• US 5,583,950 A
• Filed: 09/29/1994
• Issued: 12/10/1996
• 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): NOT, DEFINED
• Assistant Examiner(s): Prikockis, Larry J.
• Application Number:
  US08/314,729
• Time in Patent Office: 803 Days
• Field of Search: 382/210, 382/211, 382/212, 382/213, 382/214, 382/209, 382/217, 382/218, 382/278, 356/159, 356/401, 359/560, 359/561
• US Class Current: 382/212
• 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 10/761 Proximity, similarity or dissimilarity measures
• 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 comparing an unknown pattern of dispersed elements of varying intensity values and a known pattern of dispersed elements of varying intensity values to determine the presence or absence of an artifact indicative of a similarity between the unknown and known patterns, said method comprising the steps:

a) overlaying in the spatial domain the unknown and known patterns and rotating one of the known and unknown patterns with respect to the other about a point, so that the known and unknown patterns are rotationally unaligned, to produce a composite pattern of the combined elements therefrom;

b) sensing first and second average intensities respectively of all of the combined elements within a first area of said composite pattern and of all of the combined elements within a second area of said composite pattern disposed about said first area; and

c) detecting the presence of said artifact produced by the combined elements of the composite pattern by determining a variation between said first and second average intensities greater than a selected threshold value and detecting the absence of said artifact by determining a variation of said first and second average intensities not greater than said selected threshold value;

wherein the presence of an artifact is indicative of a similarity between the unknown and known patterns.

2. The method of comparing as claimed in claim 1, wherein said step a) establishes said point of rotating within the combined elements of the composite pattern.

3. The method of comparing as claimed in claim 2, wherein there is further included before step a) a step of inverting the intensity values of the elements of one of the unknown and known patterns.

4. The method of comparing as claimed in claim 3, wherein the intensity values of the elements of the unknown and known patterns lie within a given reference scale, said inverting step inverting the intensity values of the elements of said one pattern within said given reference scale.

5. The method of comparing as claimed in claim 3, wherein said determining step c) further includes the substeps of translating in a given, first direction one of the unknown and known patterns with respect to the other of the unknown and known patterns, and of sensing whether said first area has moved in a second direction at an angle with respect to said first direction to thereby determine that said first area is said artifact.

6. The method of comparing as claimed in claim 4, wherein said substep of sensing determines whether the intensity value of said first region is above a threshold intensity value to thereby determine that said first area is said artifact.

7. The method of comparing as claimed in claim 2, wherein said determining step c) includes the substep of identifying said first area disposed about said point of rotating.

8. The method of comparing as claimed in claim 1, wherein there is included a plurality of known patterns said method further including before step a) the step of combining said plurality of known patterns to form a composite known pattern of the combined elements of said combined known patterns, before overlaying in said spatial domain the unknown pattern and the composite known pattern.

9. The method of comparing as claimed in claim 8, wherein there is further included the step of moving laterally at least one of said plurality of known patterns with respect to the other of said plurality to form said composite known pattern.

10. The method of comparing as claimed in claim 8, wherein there is further included the step of rotating about a point at least one of said plurality known patterns with respect to the others of said plurality to form said composite known pattern.

11. The method of comparing as claimed in claim 1, wherein said method includes before step a) the steps of replicating the known pattern to provide a duplicate pattern thereof, and of translating and overlaying in the spatial domain one of the known patterns and the duplicate pattern with respect to the other to provide a composite known pattern of the combined elements of the known patterns and the duplicate pattern, before overlaying in step a) the unknown pattern and the composite known pattern.

12. The method of comparing as claimed in claim 1, wherein there is further included the step of determining the degree of similarity between said unknown and known patterns based upon the magnitude of the variation of said first and second average intensities.

13. A method of characterizing a data base comprising first and second known patterns of dispersed elements of varying intensity values, said first and second known patterns to be compared with at least one unknown pattern of dispersed elements of varying intensity values to determine the degree of similarity between said unknown pattern and at least one of said first and second known patterns, said method comprising the steps of:

a) overlaying in the spatial domain said first and second known patterns and rotating one of said first and second known patterns with respect to the other about a point so that said first and second known patterns are rotationally unaligned, to form a reference artifact of the combined elements of said first and second patterns;

b) measuring a characteristic value of said reference artifact to provide a corresponding reference value;

c) overlaying in the spatial domain said first and second known patterns and said unknown pattern and rotating said known patterns with respect to said unknown pattern, so that said known patterns and said unknown pattern are rotationally unaligned, to form a comparison artifact; and

d) measuring the characteristic of said comparison artifact to provide a corresponding comparison value and comparing said reference and comparison values to provide an indication of the degree of similarity between said unknown pattern and said one known pattern.

14. The method of characterizing a database as claimed in claim 13, wherein said step b) of measuring includes rotating repeatedly through a given angle one of said first and second known patterns with respect to the other to a sequence of positions offset from an initial position, and taking a corresponding sequence of measurements of the characteristic at each of said sequence of positions.

15. The method of characterizing a database as claimed in claim 13, wherein after step a) there is further included the step of inverting the characteristic values of the elements of one of said first and second known patterns.

16. The method of characterizing a database as claimed in claim 13, wherein said characteristic is size and after step a) there is included the step of varying the size of said first and second known patterns to a given degree, the size of said known pattern to be varied to said given degree before said varied unknown and known patterns are compared.

17. The method of characterizing a database as claimed in claim 13, wherein before step a) there is included the step of varying the characteristic values of the elements of the first and second known patterns to a given degree, the characteristic values of the elements of the unknown pattern to be varied to said given degree before the varied unknown and known patterns are compared.

18. The method of characterizing a database as claimed in claim 13, wherein before step a) there is included the step of sampling the elements of the first and second known patterns in a given fashion to provide first and second sampled known patterns, the elements of the unknown patterns to be sampled in said given fashion to provide a sampled unknown pattern before the sampled unknown and known patterns are compared.

19. The method of characterizing a database as claimed in claim 13, wherein the first known pattern is a copy of said second known pattern, said step b) of measuring measures a characteristic value of the overlaid first and second patterns at a highest level within a range of said characteristic values.

20. The method of characterizing a database as claimed in claim 13, wherein there is further included the step of predicting the characteristic of an artifact produced by the overlaying of one of the first and second known patterns with the unknown pattern.

21. The method of characterizing a database as claimed in claim 13, wherein said first and second known patterns are different.

22. The method of characterizing a database as claim in claim 13, wherein said first and second known patterns are the same.

23. The method of characterizing a database as claim in claim 22, wherein said second known pattern is a complement of said first known pattern.

24. The method of characterizing as claimed in claim 14, wherein said step b) of measuring further includes examining and selecting one of said sequence of characteristic measurements as said corresponding reference value.

25. The method of characterizing as claimed in claim 14, wherein said step b) of measuring further includes selecting a maximum or minimum one of said sequence of characteristic measurements as said corresponding reference value.

26. The method of characterizing a database as claimed in claim 24, wherein after step b) there is further included the step of determining a difference between an initial intensity value of said reference artifact produced at said initial position and said intensity values as measured at each of said other positions of said sequence, and determining the greatest difference between said intensity values and identifying the angle of said artifact corresponding to the determined greatest difference.

27. A method of comparing an unknown pattern of dispersed elements of varying intensity values and a known pattern of dispersed elements of varying intensity values to sense the presence or absence of an apparent artifact and to determine whether said apparent artifact is valid or false, said valid artifact being indicative of a similarity between the unknown and known patterns, said method comprising the steps:

a) overlaying in the spatial domain the unknown and known patterns and rotating one of the known and unknown patterns with respect to the other about a point to produce a composite pattern of the combined elements therefrom;

b) sensing first and second average intensities respectively of all of the combined elements within a first area of said composite pattern and of all of the combined elements within a second area of said composite pattern disposed about said first area;

c) detecting the presence of an apparent artifact produced by the combined elements of the composite pattern by determining a variation between said first and second average intensities; and

d) determining whether said apparent artifact is a valid artifact or a false artifact by translating in a given, first direction one of the unknown and known patterns with respect to the other of the unknown and known patterns, and of sensing whether said first area has moved in a second direction transverse with respect to said first direction to thereby determine that said apparent artifact is valid.

28. The method of comparing as claimed in claim 27, wherein said step d) further senses whether said first area has moved in a second direction aligned with said first direction to thereby determine that said apparent artifact is false.

29. A method of determining the degree of similarity between a known pattern and an unknown pattern, said method comprising the steps of:

a) determining a reference value of a selected characteristic of a reference artifact provided by said known pattern;

b) overlaying in the spatial domain said known and unknown patterns and rotating one of said known and unknown patterns with respect to the other, so that said known and unknown patterns are rotationally unaligned, to produce a comparison artifact; and

c) measuring the characteristic of said comparison artifact to provide a corresponding comparison value thereof and comparing said reference and comparison values to provide an indication of the degree of similarity between said known and unknown patterns.

30. The method of determining the degree of similarity between said known and unknown patterns as claimed in claim 29, wherein said selected characteristic is intensity.

31. The method of determining the degree of similarity of between said known and unknown patterns as claimed in claim 29, wherein said selected characteristic is size.

32. A method of comparing unknown and known patterns of dispersed elements of varying intensity values to determine the presence or absence of an artifact indicating a similarity between the known and unknown patterns, said method comprising the steps of:

a) overlaying in the spatial domain a plurality of copies of at least one of the known or unknown patterns to form a stack of the at least one pattern;

b) overlaying in the spatial domain the stack of the at least one pattern and at least one of another of the known and unknown patterns, and imparting relative rotation between said stack and said other pattern, so that said one stack and said other pattern are rotationally unaligned, to produce a composite pattern of the combined elements from the patterns overlaid in this step;

c) sensing first and second average intensities respectively of all of the combined elements within a first area of the composite pattern and of all of the combined elements within a second area of the composite pattern disposed about said first area; and

d) detecting the presence of said artifact produced by the combined elements of the composite pattern by determining a variation between said first and second average intensities greater than a selected threshold value and detecting the absence of said artifact by determining a variation of said first and second average intensities not greater than said selected threshold artifact is indicative of a similarity between at least one of the patterns in said stack and said other pattern.

33. The method of comparing unknown and known patterns as claimed in claim 32, wherein after step a) at least one of said plurality of copies of the one pattern in said stack is displaced with respect to the remaining of said plurality of copies of the one pattern.

34. The method of comparing unknown and known patterns as claimed in claim 33, wherein said at least one displaced pattern is offset linearly along known coordinates.

35. The method of comparing unknown and known patterns as claimed in claim 33, wherein said one displaced pattern is rotated.

36. A method of comparing unknown and known patterns of dispersed elements of varying intensity values to determine the presence or absence of an artifact indicative of a similarity between the unknown and known patterns, said method comprising the steps of:

a) rearranging the known and unknown patterns in a like manner to provide scrambled known and unknown patterns respectively;

b) overlaying in the spatial domain the scrambled unknown and known patterns and rotating one of the scrambled known and unknown patterns with respect to the other, so that the scrambled known and unknown patterns are rotationally unaligned, about a point to produce a composite pattern of the combined elements therefrom;

c) sensing first and second average intensities respectively of all of the combined elements within a first area of said composite pattern and of all of the combined elements within a second area of said composite pattern disposed about said first area; and

d) detecting the presence of said artifact produced by the combined elements of said composite pattern by determining a variation between said first and second average intensities greater than a selected threshold value and detecting the absence of said artifact by determining a variation of said first and second average intensities not greater than said selected threshold value;

wherein the presence of an artifact is indicative of a similarity between the known and unknown patterns.

37. A method of comparing pixelized known and unknown patterns of dispersed elements of binary intensity values to determine the presence of a valid artifact indicative of a similarity between the unknown and known patterns or of a false artifact indicative of a lack of similarity between the unknown and known patterns, one of the known and unknown patterns being rendered as a positive and the other of the known and unknown patterns being rendered as a negative, said method comprising the steps of:

a) overlaying in the spatial domain the unknown and known patterns and rotating one of the known and unknown patterns with respect to the other about a point to produce an apparent artifact; and

b) detecting the presence of a valid artifact by determining whether the apparent artifact is of a square configuration or the presence of an invalid artifact by determining whether the apparent artifact is of a configuration other than square.

38. The method of comparing known and unknown images as claimed in claim 37, wherein step b) includes the step of detecting the presence of a valid artifact by determining that the size of the apparent artifact changes as said one of the known and unknown patterns is rotated.

39. The method of comparing known and unknown images as claimed in claim 37, wherein step b) includes determining the ratio of black to white elements in said artifact to indicate the degree of similarity of the unknown and known patterns, higher ratios indicating a higher degree of similarity.

40. The method of comparing known and unknown patterns as claimed in claim 39, wherein a determination in step b) of a 100% ratio is an indication that the known and unknown images are exactly alike.

41. A method of comparing unknown and known patterns of dispersed elements of varying intensity values to determine the presence or absence of an artifact indicating a similarity between the known and unknown patterns, said method comprising the steps of:

a) disposing a plurality of copies of one of the known or unknown patterns in a side by side arrangement to form a first assembly thereof;

b) disposing a like plurality of copies of the other of the known or unknown patterns in said side by side arrangement and imparting a rotational movement to each of said other patterns from its position in said side by side arrangement to a position rotationally unaligned with said first assembly to form a second assembly thereof;

c) overlaying in the spatial domain said first and second assemblies to produce a like plurality of composite patterns of said combined elements from the patterns overlaid in this step;

d) sensing first and second average intensities respectively of a first area and a second area disposed about said first area for each composite pattern of said like plurality; and

e) detecting the presence of an artifact produced by said combined elements of each of said like plurality of composite patterns by determining a variation between said first and second average intensities greater than a selected threshold value and detecting the absence of said artifact by determining a variation of said first and second average intensities not greater than said selected threshold value;

wherein the presence of an artifact is indicative of a similarity between the known and unknown patterns.

42. The method of comparing unknown and known patterns as claimed in claim 41, wherein step b) each of said other patterns is offset linearly from its displaced position in said side by side arrangement.

43. The method of comparing unknown and known patterns as claimed in claim 41, wherein step b) imparting a further rotational movement to each of said other patterns from its displaced position in said side by side arrangement.

44. The method of comparing unknown and known patterns as claimed in claim 41, wherein each of said steps a) and b) disposes respectively said one and said other patterns into a mosaic thereof.

45. The method of comparing unknown and known patterns as claimed in claim 41, wherein each of said steps a) and b) disposes respectively said one and said other patterns into a plurality of adjacent columns.