US5495537A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Methods and apparatus for machine vision template matching of images predominantly having generally diagonal and elongate features
Assignee: Cognex Corp
•
Filing: 1994-06-01
•
Granted: 1996-02-27
•
Expires: 2014-06-01
Abstract
Abstract A machine vision apparatus of the type having a match-scoring functionality for generating a metric as a function, e.g., a correlation, of applied image signals features an improvement for estimating a location of a template in a candidate image. The improvement is characterized by a segment peak finding element that applies to the match-scoring element a plurality of pairs of image signals along a "segment." Each such pair includes a signal representing the template and a signal representing a respective portion of the candidate image taken along a first axis. Thus, ignoring their template components, plural pairs of signals can represent successive adjacent portions of the candidate image that are "in line" along a first axis. Functionality within the segment peak finder determines a peak value of the metric generated by the match-scoring element in response to application of the pairs within the segment. A hill climbing element invokes the segment peak finder means to determine an image peak from among a plurality of segment peaks. To this end, the hill climber invokes the segment peak finder, e.g., with successive adjacent segments along the y-axis, where each segment itself is oriented, e.g., along the x-axis. The hill climber determines the image peak directly from the segment peaks, or by interpolation or extrapolation therefrom. The location of the template within the candidate image is, itself, determined from the position of the image peak.
Inventors
- 👤 David P. Bedrosian
- 👤 William M. Silver
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 04:53
CPC Classifications
G; G06; G06V; G06V10/00; G06V10/70; G06V10/74; G06V10/75; G06V10/751; G06V10/7515
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
288 words
In a machine vision apparatus of the type having match scoring means, responsive to a plurality of pairs of applied image signals, for generating a plurality of score signals as a selected function of said plurality of pairs of applied image signals, the improvement for estimating a location of a template in a candidate image, comprising: segment peak finding means, coupled to said match-scoring means, for applying thereto said plurality of pairs of image signals along a "segment," each such pair including a signal representative of said template and a signal representative of a respective successive portion of said candidate image along a first axis, said segment peak finding means including means for determining a peak value, and location thereof, of the score signals generated by said match-scoring means in connection with application of the plurality of pairs of image signals comprising said segment, such peak value and location thereof being referred to as a segment peak, a store of best-fit geometric surface characteristics, hill climbing means, coupled to said segment peak finding means, and to said store of geometric surface characteristics, for invoking said segment peak finding means, only if said best-fit geometric surface characteristics satisfy a predetermined condition, to determine the segment peaks of a plurality of segments, each such segment including image signals from different respective portions of said candidate image along a second axis, said hill climbing means including means for determining a peak value, and location thereof, of the segment peaks associated with said plurality of segments, such peak value and location thereof being referred to as an image peak, and means for estimating a location of said template in said candidate image as a function of a location of said image peak.
Claim 2
Dependent Claim
288 words
In a machine vision apparatus of the type having match scoring means, responsive to a plurality of pairs of applied image signals, for generating a plurality of score signals as a selected function of said plurality of pairs of applied image signals, the improvement for estimating a location of a template in a candidate image, comprising: segment peak finding means, coupled to said match-scoring means, for applying thereto said plurality of pairs of image signals along a "segment," each such pair including a signal representative of said template and a signal representative of a respective successive portion of said candidate image along a first axis, said segment peak finding means including means for determining a peak value, and location thereof, of the score signals generated by said match-scoring means in connection with application of the plurality of pairs of image signals comprising said segment, such peak value and location thereof being referred to as a segment peak, a store of best-fit geometric surface characteristics, hill climbing means, coupled to said segment peak finding means, and to said store of geometric surface characteristics, for invoking said segment peak finding means, only if said best-fit geometric surface characteristics satisfy a predetermined condition, to determine the segment peaks of a plurality of segments, each such segment including image signals from different respective portions of said candidate image along a second axis, said hill climbing means including means for determining a peak value, and location thereof, of the segment peaks associated with said plurality of segments, such peak value and location thereof being referred to as an image peak, and means for estimating a location of said template in said candidate image as a function of a location of said image peak.
Claim 3
Dependent Claim
47 words
In a machine vision apparatus according to claim 1, the improvement wherein said segment peak finding means includes means for generating, for inclusion in each respective pair of signals along a segment, a signal representing a successive adjacent portion of said candidate image along said first axis.
Claim 4
Dependent Claim
51 words
In a machine vision apparatus according to claim 1, the improvement wherein said segment peak finding means includes means for determining said peak value as a function of the score signals generated in connection with application to said match-scoring means of the plurality of pairs of image signals comprising said segment.
Claim 5
Dependent Claim
33 words
In a machine vision apparatus according to claim 3, the improvement wherein said segment peak means includes means for determining said peak value by any one of interpolating or extrapolating said score signals.
Claim 6
Dependent Claim
52 words
In a machine vision apparatus according to claim 1, the improvement wherein said hill climbing means includes means for invoking said peak finding means to determine segment peaks for successive adjacent segments along a second axis relative to said candidate image, where said second axis is substantially perpendicular to said first axis.
Claim 7
Dependent Claim
58 words
In a machine vision apparatus according to claim 5, the improvement wherein said hill climbing means includes means for comparing segment peaks generated by said peak finding means to determine a direction in which those segment peaks increase, and for invoking said peak finding means to determine segment peaks for successive adjacent segments in such direction of increase.
Claim 8
Dependent Claim
114 words
In a machine vision apparatus according to claim 1, the improvement further comprising: training means for applying to said match-scoring means a plurality of pairs of image signals, said match-scoring means determining for each such pair a value of said selected function, each such pair of image signals comprising a signal representative of said template and a signal representative of a respective successive portion of a model image, index means, coupled to said match-scoring means, for indexing the value of said function for each such pair of image signals to provide indexed values, and best fit means, coupled to said index means, for identifying a geometric surface of best fit to said indexed values.
Claim 9
Dependent Claim
37 words
In a machine vision apparatus according to claim 7, the improvement wherein said training means comprises means for generating said model portion representative signals to represent portions of said model image over a putative search region thereof.
Claim 10
Dependent Claim
29 words
In a machine vision apparatus according to claim 7, the improvement wherein said best fit means includes means for identifying an ellipsoid of best fit to said indexed values.
Claim 11
Dependent Claim
67 words
In a machine vision apparatus according to claim 9, the improvement wherein said predetermined condition includes both of the following constituent conditions: i) an axis of said ellipsoid of best fit must be angularly displaced by no more than about 22.5 degrees with respect to at least one of said first and second axes, ii) an elongation ratio of said ellipsoid must be greater than about 2.8.
Claim 12
Dependent Claim
49 words
In a machine vision apparatus according to claim 9, the improvement wherein said segment peak finding means includes means for generating said signals representing successive adjacent portion of said candidate image to lie on a first axis defined in accord with an axis of greatest slope of said ellipsoid.
Claim 13
Dependent Claim
71 words
In a machine vision apparatus according to claim 1, the improvement wherein said predetermined condition includes at least one of the following constituent conditions: i) an axis of said ellipsoid of best fit must be angularly displaced by no more than a pre-selected angle with respect to at least one of said first and second axes, and ii) an elongation ratio of said ellipsoid must be greater than a selected value.
Claim 14
Dependent Claim
276 words
In a method of operating a machine vision apparatus of the type having match-scoring means, responsive to a plurality of pairs of applied image signals, for generating a plurality of score signals as a selected function of said plurality of pairs of applied image signals, an improvement for estimating a location of a template in a candidate image, comprising: a selectively invocable segment peak finding step for applying to said match-scoring means said plurality of pairs of image signals defining a segment, each such pair including a signal representative of said template and a signal representative of a respective successive portion of said candidate image along a first axis, said segment peak finding step including a step of determining a peak value, and location thereof, of the score signals generated by the match-scoring means in connection with application of the plurality of pairs of image signals comprising said segment, such peak value and location thereof being referred to as a segment peak, storing best-fit geometric surface characteristics, a hill climbing step for invoking said segment peak finding step, only if said best-fit geometric surface characteristics satisfy a predetermined condition, to determine the segment peaks of a plurality of segments, each such segment including image signals from different respective portions of said candidate image along a second axis, said hill climbing step including a step for determining a peak value, and location thereof, of the segment peaks associated with said plurality of segments, such peak value and location thereof being referred to as an image peak, and estimating a location of said template in said candidate image as a function of a location of said image peak.
Claim 15
Dependent Claim
276 words
In a method of operating a machine vision apparatus of the type having match-scoring means, responsive to a plurality of pairs of applied image signals, for generating a plurality of score signals as a selected function of said plurality of pairs of applied image signals, an improvement for estimating a location of a template in a candidate image, comprising: a selectively invocable segment peak finding step for applying to said match-scoring means said plurality of pairs of image signals defining a segment, each such pair including a signal representative of said template and a signal representative of a respective successive portion of said candidate image along a first axis, said segment peak finding step including a step of determining a peak value, and location thereof, of the score signals generated by the match-scoring means in connection with application of the plurality of pairs of image signals comprising said segment, such peak value and location thereof being referred to as a segment peak, storing best-fit geometric surface characteristics, a hill climbing step for invoking said segment peak finding step, only if said best-fit geometric surface characteristics satisfy a predetermined condition, to determine the segment peaks of a plurality of segments, each such segment including image signals from different respective portions of said candidate image along a second axis, said hill climbing step including a step for determining a peak value, and location thereof, of the segment peaks associated with said plurality of segments, such peak value and location thereof being referred to as an image peak, and estimating a location of said template in said candidate image as a function of a location of said image peak.
Claim 16
Dependent Claim
46 words
In a method according to claim 13, the improvement wherein said segment peak finding step includes the step of generating, for inclusion in each respective pair of signals along a segment, a signal representing a successive adjacent portion of said candidate image along said first axis.
Claim 17
Dependent Claim
50 words
In a method according to claim 13, the improvement wherein said segment peak finding step includes a step of determining said peak value as a function of the score signals generated in connection with application to said match-scoring means of the plurality of pairs of image signals comprising said segment.
Claim 18
Dependent Claim
33 words
In a method according to claim 15, the improvement wherein said segment peak finding step includes a step of determining said peak value by any one of interpolating or extrapolating said score signals.
Claim 19
Dependent Claim
51 words
In a method according to claim 13, the improvement wherein said hill climbing step includes a step of invoking said peak finding step to determine segment peaks for successive adjacent segments along a second axis relative to said candidate image, where said second axis is substantially perpendicular to said first axis.
Claim 20
Dependent Claim
57 words
In a method according to claim 17, the improvement wherein said hill climbing step includes a step of comparing segment peaks generated by said peak finding step to determine a direction in which those segment peaks increase, and for invoking said peak finding step to determine segment peaks for successive adjacent segments in such direction of increase.
Claim 21
Dependent Claim
105 words
In a method according to claim 13, the improvement further comprising: a training step for applying to said match-scoring means a plurality of pairs of image signals, said match-scoring means determining for each such pair a value of said selected function, each such pair of image signals comprising a signal representative of said template and a signal representative of a respective successive portion of a model image, an index step for indexing the value of said function for each such pair of image signals to provide indexed values, and a best fit step, for identifying a geometric surface of best fit to said indexed values.
Claim 22
Dependent Claim
36 words
In a method according to claim 19, the improvement wherein said training step comprises a step for generating said model portion representative signals to represent portions of said model image over a putative search region thereof.
Claim 23
Dependent Claim
28 words
In a method according to claim 19, the improvement wherein said best fit step includes a step for identifying an ellipsoid of best fit to said indexed values.
Claim 24
Dependent Claim
65 words
In a method according to claim 21, the improvement wherein said predetermined condition includes both of the following constituent conditions: i) an axis of said ellipsoid of best fit must be angularly displaced by no more than about 22.5 degrees with respect to at least one of said first and second axes, ii) an elongation ratio of said ellipsoid must be greater than about 2.8.
Claim 25
Dependent Claim
48 words
In a method according to claim 21, the improvement wherein said segment peak finding step includes a step for generating said signals representing successive adjacent portion of said candidate image to lie on a first axis defined in accord with an axis of greatest slope of said ellipsoid.
Claim 26
Dependent Claim
69 words
In a method according to claim 13, the improvement wherein said predetermined condition includes at least one of the following constituent conditions: i) an axis of said ellipsoid of best fit must be angularly displaced by no more than a pre-selected angle with respect to at least one of said first and second axes, and ii) an elongation ratio of said ellipsoid must be greater than a selected value.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-02-26 | 1999-08-28 | 2000-02-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-02-26 | 2003-08-28 | 2004-02-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-02-26 | 2007-08-28 | 2008-02-27 | $7700.00 | Window Closed / Lapsed |