Pattern recognition apparatus and method

• US 4,200,861 A
• Filed: 09/01/1978
• Issued: 04/29/1980
• Est. Priority Date: 09/01/1978
• Status: Expired due to Term

• Current Assignee: General Scanning, Inc. (KOCH Industries Incorporated)
• Original Assignee: View Engineering, Inc. (Quality Vision International, Inc.)
• Inventors: Sacks, Jack, Hubach, Richard A., DeZotell, Gary L.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US05/939,061
• Time in Patent Office: 606 Days
• Field of Search: 340/146.3 H, 340/146.3 Q, 340/146.3 AQ, 340/146.3 MA, 364/728, 364/515
• US Class Current: 382/216
• CPC Class Codes: G06V 10/20 Image preprocessing
• CPC Class Codes: G06V 10/28 Quantising the image, e.g. histogram thresholding for discrimination between background and foreground patterns
• CPC Class Codes: G06V 10/32 Normalisation of the pattern dimensions
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches

Abstract

Video informatin obtained in real time is clocked and digitized according to light intensity. Changing light intensities are adaptively determined to vary the threshold level for determining black and white signals. The scene to be used as a reference is first recorded in a fine format and then in a coarse format. In the search mode the coarse stored information is compared in real time with coarse information from the field of view and convolved to generate a correlation number indicating the percentage of match. The location coordinates in the X and Y dimension for the best match is determined at the location of the highest correlation number. A fine search is then made around the coarse location previously determined by convolving in two dimensions previously stored information against information in real time from the scene under investigation to again determine the highest correlation as a measure of the location where the best possible match can be determined.

Claims

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

generating a clocked digitized video signal having a pulse width termed a pixel,

generating a super pixel having a pulse width greater than a pixel by a given amount,

storing pixels representing a reference scene in an addressable memory location,

storing super pixels representing said same reference scene in a separate addressable memory,

convolving super pixels generated from a search area with super pixels from said memory and generating a count indicative of a comparison in each segment compared,

storing the count in each segment in a separate addressable memory,

determining the maximum count and identifying the coordinate of the address of the memory having the maximum count as a measure of the coarse location of the best match,

establishing a search pattern around said coarse coordinate including an odd number of pixels with the coordinate pixel in the center,

convolving pixels generated from said search pattern with pixels from said memory and generating a count indicative of a comparison in each segment of the search pattern,

storing the count in each pattern in a separate addressable memory, and

determining the maximum count in each of the segments of the search pattern and identifying the coordinate of the address as a measure of the fine location of the best match.

2. A pattern recognition method according to claim 1 in which each super pixel defines an area equal to 16 pixels.

3. A pattern recognition method according to claim 1 which includes the steps of evaluating the quality of the highest count by comparing the highest count with the value of all the counts to establish an arbitrary quality number.

4. A pattern recognition method according to claim 3 which includes the steps of differencing the count in surrounding memory cells from the maximum count determined in the selected memory cell and adding the result to establish the quality number.

5. A pattern recognition method according to claim 1 in which said super pixel generator is a two dimensional digital filter.

14. A pattern recognition system according to claim 2 which includes means for measuring the highest accumulation in each of two memories for determining the address of both memories and hence the coordinates of each is determined.

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

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

recording said series of clocked pulses in a plurality of separate programmable memory locations,

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

recording said series of enlarged clocked pulses in a plurality of separate different programmable memory locations,

generating a series of enlarged clocked digital video pulses of a search area in real time,

convolving in real time said real time enlarged pulses with said stored enlarged pulses in a plurality of separate search positions to obtain a count representing the number of matches in each position,

accumulating the count in each search position in separate addressable memory associated with each search position,

detecting the highest accumulation count in each memory location, and

then determining the address and hence the location coordinates of the memory location having the highest count as a measure of the search position having the best match.

7. A pattern recognition method according to claim 6 which includes the steps of measuring the highest accumulation in each of two memories and then determining the address of both memories and hence the coordinates of each.

8. A method for determining the best comparison between a reference area and a search area and in real time comprising the steps of:

generating a coarse search to determine the coordinates of a search position having the indications of a best match,

establishing a search of an odd number of search positions about the coordinates determined by the coarse search thereby establishing the coordinate search position as the center of the odd number of search positions to be convolved,

convolving pulses generated from the search area with pulses from storage over the complete reference area for each search position to obtain a plurality of individual counts representing the number of matches in each position searched,

storing each of the individual counts in a programmable addressable memory whereby the coordinates of each memory is readably determined,

updating each of the individual counts for each of the total number of odd search positions being searched,

determining the address and hence the coordinate of the memory having the highest count accumulation,

evaluating the quality of the highest count by comparing the highest count with the value of all the counts to establish an arbitrary quality number, and

determining the centroid of points by comparing the counts of all individual counters to establish the highest possible count and the coordinate of that count.

9. A pattern recognition system for determining the best comparison between a reference area and a search area and in real time comprising:

means for generating a clocked digitized video signal having a pulse width termed a pixel,

means for generating a super pixel having a pulse width greater than a pixel by a given amount,

means for storing pixels representing a reference scene in an addressable memory location,

means for storing super pixels representing said same reference scene in a separate addressable memory,

means for convolving super pixels generated from a search area with super pixels from said memory and generating a count indicative of a comparison in each segment compared,

means for storing the count in each segment in a separate addressable memory,

means for determining the maximum count and identifying the coordinate of the address of the memory having the maximum count as a measure of the coarse location of the best match,

means for establishing a search pattern around said coarse coordinate including an odd number of pixels with the coordinate pixel in the center,

means for convolving pixels generated from said search pattern with pixels from said memory and generating a count indicative of a comparison in each segment of the search pattern,

means for storing the count in each pattern in a separate addressable memory, and

means for determining the maximum count in each of the segments of the search pattern and identifying the coordinate of the address as a measure of the fine location of the best match.

10. A pattern recognition system according to claim 9 in which each super pixel defines an area to 16 pixels.

11. A pattern recognition system according to claim 9 which includes means for evaluating the quality of the highest count by comparing the highest count with the value of all the counts to establish an arbitrary quality number.

12. A pattern recognition system according to claim 11 which includes means for differencing the count in surrounding memory cells from the maximum count determined in the selected memory cell and adding the result to establish the quality number.

13. A pattern recognition system according to claim 9 in which said super pixel generator is a two dimensional digital filter.

15. A pattern recognition system for determining the best comparison between a reference area and a search area and in real time comprising:

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

means for recording said series of clocked pulses in a plurality of separate programmable memory locations,

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

means for recording said enlarged series of clocked pulses in a plurality of separate different programmable memory locations,

means for generating a series of enlarged clocked digital video pulses in real time of a search area,

means for convolving in real time said real time enlarged pulses with stored enlarged pulses in a plurality of separate search positions to obtain a count representing the number of matches in each position,

means for accumulating the count in each search position in separate addressable memory associated with each search position,

means for detecting the highest accumulation count in each memory location, and

means for determining the address and hence the location coordinates of the memory location having the highest count as a measure of the search position having the best match.

16. A system for determining the best comparison between a reference area and a search area and in real time comprising:

means for generating a coarse search to determine the coordinates of a search position having the indications of a best match,

means for establishing a search of an odd number of search positions about the coordinates determined by the coarse search thereby establishing the coordinate search position as the center of the odd number of search positions to be convolved,

means for convolving pulses generated from the search area with pulses from storage over the complete reference area for each search position to obtain a plurality of individual counts representing the number of matches in each position searched,

means for storing each of the individual counts in a programmable addressable memory whereby the coordinates of each memory is readably determined,

means for updating each of the individual counts for each of the total number of odd search positions being searched,

means for determining the address and hence the coordinate of the memory having the highest count accumulation,

means for evaluating the quality of the highest count by comparing the highest count with the value of all the counts to establish an arbitrary quality number, and

means for determining the centroid of points by comparing the counts of all individual counters to establish the highest possible count and the coordinate of that count.