High speed pattern recognizer

• US 4,736,437 A
• Filed: 04/21/1987
• Issued: 04/05/1988
• Est. Priority Date: 11/22/1982
• Status: Expired due to Term

• Current Assignee: GSI Lumonics Corporation (Novanta Inc.)
• Original Assignee: View Engineering, Inc. (Quality Vision International, Inc.)
• Inventors: Liudzius, Valerie A., DeZotell, Gary, DeKlotz, Richard E., Sacks, Jack
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Mancuso, Joseph
• Application Number:
  US07/052,140
• Time in Patent Office: 350 Days
• Field of Search: 382/44, 382/45, 382/46, 382/48, 382/8, 382/30, 382/34, 364/518, 364/559, 364/731, 340/727, 358/22, 358/106
• US Class Current: 382/216
• CPC Class Codes: G06V 30/1478 of characters or characters lines

Abstract

An apparatus and method for storing a reference scene and a scene under search in separate addressable memories. The reference scene is addressed along a scan line at a selected angle giving the impression that the reference memory has been rotated. The search area information is convolved with a stored reference information to obtain a count representing the number of matches for each search position at a plurality of selected angles. The convolved count is accumulated and the search stopped when the accumulated count exceeds a given threshold value. The X Y coordinates of the best search is determined by evaluating the highest accumulation count. The angle orientation of the search area is determined by addressing each scan line readout of the stored reference area at small angles, convolving the readout against the memory readout, accumulating the count for a selected number of scan angles and determining the angle position having the highest count as a measure of the alignment angle of the search area.

Claims

1. A pattern recognition method for rapidly determining the location and orientation between a reference area and a search area comprising the steps of:

generating a series of clocked digitized video pulses representative of a reference area,

recording said series of clocked pulses representative of a reference area in a plurality of separate addressable memory locations,

generating a series of clocked digital pulses representative of a search area,

recording said series of clocked pulses representative of a search area in a plurality of separate addressable memory locations,

electronically addressing each scan line of said stored reference area in memory at any selected coarse scan angle,

correlating said stored pulses received from said search area with each of said stored reference pulses derived from addressing the reference area to obtain an accumulation count for each coarse scan angle selected,

repeating said scan for a plurality of coarse scan angles to obtain a coarse scan angle having an accumulation count greater than a threshold count,

selectively addressing each scan line of said stored reference area in memory at fine discrete search angles about the coarse scan angle having an accumulation count greater than a threshold count,

accumulating a separate count for each of a plurality of different fine discrete scan angles about said coarse scan angle having an accumulation count greater than said threshold count in separate addressable memory locations aassociated with each selected fine discrete scan angle position,

statistically determining from the separate counts for fine discrete scan angles the precise angular alignment of the search area and the coordinates of the search area.

2. A pattern recognition method according to claim 1 in which accumulation counts are recorded for each of a plurality of said fine discrete scan angles.

3. A pattern recognition method according to claim 2 which includes the method step of performing a mathematical evaluation of the accumulated counts to determine a fine angle representing the angular alignment of the search area.

4. A patter recognition method according to claim 2 in which each selected fine discrete scan angle is two degrees.

5. A pattern recognition method for rapidly determining the location and orientation between a reference area and a search area comprising the steps of:

generating a series of clocked digitized video pulses representative of a reference area,

recording said series of clocked pulses representative of a reference area in a plurality of separate addressable memory locations,

generating a series of clocked digital pulses representative of a search ares,

recording said series of clocked pulses representative of a search area in a plurality of separate addressable memory locations,

electronically addressing each scan line of said stored reference area in memory and at any selected angle,

establishing an incremental threshold defined as an intermediate accumulated count having a value from which the maximum number of matches remaining could not accumulate a desired high accumulation count,

correlating said stored pulses received from said search area with each of said stored reference pulses derived from addressing the reference area to obtain an accumulation count for each coarse scan angle selected,

repeating said scan for a plurality of coarse scan angles to obtain a selected coarse scan angle having an accumulation count greater than a threshold count,

stopping the completion of a scan at an intermediate point when the accumulated count for the scan is below the incremental threshold and selecting a new angle for scanning,

accumulating a separate count for each of a plurality of different fine scan angles about said selected coarse scan angle in separate addressable memory locations associated with each selected fine scan angle position, and

statistically determining from each of said separate accumulated counts the precise angular coordinate of a final scan angle which corresponds to the highest theoretical accumulation count that would be derived if all the pulses matched.

6. A pattern recognition method for determining the best comparison between a reference area and a search area comprising the steps of:

generating a series of clocked digitized video pulses representative of a reference area,

recording said series of clocked pulses representative of a reference area in a plurality of separate addressable memory locations,

generating a series of clocked digital pulses representative of a search area,

recording said series of clocked pulses representative of a search area in a plurality of separate addressable memory locations,

electronically addressing each scan line of said stored reference area in memory and at any selected angle,

correlating said stored pulses in said search area with said stored reference pulses to obtain an accumulation count representing the number of matches for each search position of said plurality of selected angles,

repeating said scan for a plurality of angles to obtain an accumulation count for each angle selected,

storing the accumulation count for a plurality of different angles in separate addressable memory associated with each selected angle position;

establishing a threshold level for the accumulation count,

stopping the correlating action at a first scan line angle whenever the accumulation count is above the threshold value,

determining the X Y coordinates of the search area at the first scan line angle,

electronically addressing the stored reference area in memory at smaller angles about the first scan line angle used to determine the X Y coordinates of the search area and accumulating the counts for each of said plurality of different smaller angles in separate addressable memory associated with each angle position,

performing a mathematical evaluation of the accumulated counts to determine a final scan line angle corresponding to the highest theoretical accumulation count, and

said final scan line angle representing the angular alignment of the search area.

7. A pattern recognition method according to claim 6 which includes the step of recalculating the location coordinates of the reference in the search area based on the angular alignment position of the search area.

8. A pattern recognition system for determining the best comparison between a reference area and a search area at high speeds consistent with a production process comprising:

means for generating a series of clocked digitized video pulses representative of a reference area,

means for recording said series of clocked pulses representative of a reference area in a plurality of separate addressable memory locations,

means for generating a series of clocked digital pulses representative of a search area,

means for recording said series of clocked pulses representative of a search area in a plurality of separate addressable memory locations,

means for electronically addressing a plurality of scan lines of said stored reference area in memory at any selected angle,

means for correlating said stored pulses in said search area with said stored reference pulses to obtained an accumulation count representing the number of matches for each search position of said plurality of selected angles,

means for repeating said scan for a plurality of angles to obtain an accumulation count for each angle selected,

means for storing the accumulation count for a plurality of different angles in separate addressable memory associated with each selected angle position,

means for establishing a threshold level for the accumulation count,

means for stopping the correlating action at a first scan line angle whenever the accumulation count is above the threshold value,

means for determining the X Y coordinates of the search area at the first scan line angle,

means for electronically addressing the stored reference area in memory at smaller angles about the first scan line angle to determine the X Y coordinates of the search area and accumulating the counts for each of said plurality of different smaller angles in separate addressable memory associated with each angle position,

means for performing a mathematical evaluation of the accumulated counts to determine a final scan line angle corresponding to the highest theoretical accumulation count, and

said final scan line angle representing the angular alignment of the search area.

9. A pattern recognition method for rapidly determining the location and orientation of a scene in a search area relative to a reference pattern held in picture element form in a first memory comprising the steps of:

storing the scene in picture element form in a second memory,

reading the picture elements from the second memory in sequential fashion to provide a scene image representation in the form of a first succession of picture element signals,

concurrently reading picture elements representing a reference scene from the first memory in sequential fashion but at a controllable scan angle relative to the reference pattern held in the first memory to provide a reference image representation in the form of a second succession of picture element signals, the reference image having a size and shape matching the scene image representation with each picture element of the reference image corresponding to a pixel of the scene image,

matching the images by counting the number of like corresponding picture elements in the two successions of signals, and

repeating the matching step with different reference image scan angles until the count reaches a predetermined threshold that identifies an image scan angle corresponding to a known degree of match,

wherein the matching step further comprises;

selecting fixed small scan angles;

accumulating further counts from each matching of the object image to the reference pattern at fine scan angles about the scan angle at which the given threshold is first exceeded; and

statistically calculating the scan angle at which an optimum match exists.

10. The method as set forth in claim 9 above, wherein the one out of a number of picture elements in successive sets are matched in periodic fashion to provide a coarse search.

11. The method as set forth in claim 10 above, further including the steps of calculating a fixed number of incremental values for each angular deviation in the scan angle from parallelism to a rectangular matrix, and determining picture elements to be read from the first memory at any chosen scan angle from the incremental values.

12. The method as set forth in claim 9 above, wherein the scan angles vary by about 6°

and wherein the scan angles are varied first in one direction and then the other from a staring position.

13. A pattern recognition method for rapidly determining the location and orientation of a scene in a search area relative to a reference pattern held in picture element form in a first memory comprising the steps of:

storing the scene in picture element form in a second memory,

reading the picture elements from the second memory in sequential fashion to provide a scene image representation in the form of a first succession of picture element signals,

concurrently reading the picture elements from the first memory in sequential fashion but at al controllable scan angle relative to the reference image to provide a reference image representation in the form of a second succession of picture element signals,

matching the images by counting the number of like picture elements in the two successions of signals,

repeating the matching step with different reference image scan angles until the count reaches a predetermined threshold count that identifies an image scan angle corresponding to a known degree of match, and

establishing an intermediate incremental threshold count defining an intermediate count which is so low that the predetermined threshold count could not be reached even with a perfect match, and stopping a given matching step and proceeding to another reference image scan angle when the intermediate count is below the intermediate incremental threshold.

14. A pattern recognition method for rapidly determining the location and orientation of a scene in a search area relative to a reference pattern held in picture element form in a first memory comprising the steps of:

storing the scene in picture element form in a second memory,

reading the picture elements from the second memory in sequential fashion to provide a scene image representation in the form of a first succession of picture element signals,

concurrently reading the picture elements from the first memory in sequential fashion but at a controllable scan angle relative to the reference image held in the first memory to provide a reference image representation in the form of a second succession of picture element signals,

matching the images by counting the number of like picture elements in the two successions of signals,

repeating the matching step with different reference image scan angles which vary by a predetermined minimum angle until the count reaches a predetermined threshold that identifies an image scan angle corresponding to a known degree of match, and

further defining the angle at which the scene image matches the reference pattern by matching the images with the reference pattern scanned at angles deviating from that image scan angle at which the count reached a predetermined threshold, such angles being less than the predetermined minimum.

15. The method as set forth in claim 14 above, wherein the method further includes the steps of deriving second counts from matching the images at angles relative to the image scan angle at which the count reached a predetermined threshold, and statistically computing a final angle representing optimum correlation from the derived second counts.

16. The method as set forth in claim 15 above, wherein the method further includes the step of deriving the second counts using a number of scan angles on each side of the image scan angle at which the count reached a predetermined threshold, and calculating from the counts the peak of the characteristic bell-shaped curve distribution established when matching the scene to the reference pattern as the later is rotated through different angles.

17. A system for identifying the position and orientation of an object corresponding to a reference pattern, comprising:

scanning means for viewing the object and providing a scene signal carrying picture element information which represents an object scene that includes the object;

first storage means receiving the scene signal and storing scene data representing the scene as a plurality of picture elements;

second storage means for storing reference data comprising a multiplicity of picture elements which represent the reference pattern, said second storage means including means for addressing the second storage means to read therefrom at varying scan angles to the reference pattern picture elements representing a reference scene which corresponds in size and shape to the object scene;

correlator means coupled to the first and second storage means for matching picture elements representing the object scene with picture elements representing the reference scene read out at different scan angles, said correlator means including counter means for accumulating the number of matches derived at each scan angle;

threshold means responsive to the counter means for determining when the count derived from a given scan angle exceeds a predetermined amount indicting a selected degree of match;

means coupled to the correlator means for storing accumulated counts for a number of matches derived from different scan angles about the given scan angle; and

means coupled to receive the stored accumulated counts for statistically analyzing the variation in matching characteristics with scan angle to derive the precise angle orientation and coordinate position of the object.

18. The invention as set forth in claim 17 above, wherein the system further includes incremental threshold means coupled to the correlator means for comparing the accumulated count at an intermediate point in the matching sequence to the predetermined amount, the incremental threshold means operating to terminate the matching at the then existing scan angle prematurely when the predetermined amount cannot be reached if the matching is carried to conclusion.

19. A system for identifying the position and orientation of an object corresponding to a reference pattern, comprising:

scanning means for viewing the object to provide a sequence of scene picture element signals;

first storage means receiving the scene picture element signals and storing scene data;

second storage means for storing reference data comprising a multiplicity of picture elements, said second storage means including means for addressing the second storage means to read the picture elements out at varying scan angles to the reference pattern;

correlator means coupled to the first and second storage means for matching picture elements from the scene data with picture elements from the reference pattern read out at different scan angles, said correlator means including counter means for accumulating the number of matches derived at each scan angle, the correlator means and means for storing including means for generating a first coarse match by varying the scan angle by predetermined angular increments, and means for generating a second match by varying the scan angle about the given scan angle at angular increments smaller than the predetermined angular increments;

threshold means responsive to the counter means for determining when the count derived from a given scan angle exceeds a predetermine amount indicating a selected degree of match;

means coupled to the correlator means for storing accumulated counts for a number of matches derived from different scan angles about the given scan angle; and

means coupled to receive the stored accumulated counts for statistically analyzing the variation in matching characteristics with scan angle to derive the precise angle orientation and coordinate position of the object.

20. The invention as set forth in claim 19 above, wherein the means for addressing the second storage means comprise means for selecting picture elements in accordance with a fixed number of precalculated incremental variables defining the succession of picture element positions needed for a given scan angle.

21. The invention as set forth in claim 20 above, wherein the correlator means generates the first coarse match at higher speed by using only one out of each given number of picture elements, and generates the second match by using each of the picture elements.

22. A system for determining the orientation of an object relative to a reference pattern stored as a matrix of picture elements in an addressable memory, comprising:

means for providing a stored image, as a plurality of picture elements, of the object;

means for addressing the memory to read out the picture elements from the matrix with any of a number of different individual scan angles varying from each other by at least a predetermined amount;

means for concurrently reading out the picture elements from the stored image of the object at a fixed angle;

means for matching the picture elements of the object image and the reference pattern during readout to derive an accumulated count of picture element matches for each scan angle;

means responsive to the accumulated count and controlling the means for matching to terminate use of scan angles varying by the predetermined amount when a given threshold is first exceeded; and

means coupled to the means for matching and the means for addressing for deriving a final orientation value for the object from scan, with scan angles less than the predetermined amount, about the scan angle at which the given threshold is first exceeded.

23. The invention as set forth in claim 22 above, wherein the means for deriving a final orientation value includes means for selecting fixed small scan angles, means for accumulating further counts from each matching of the object image to the reference pattern at fine scan angles about the scan angle at which the given threshold is first exceeded, and means responsive to the further counts for statistically calculating the scan angle at which an optimum match exists.