Patent US5809171A successfully refreshed from Google Patents.
US5809171A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Image processing method and apparatus for correlating a test image with a template
Assignee: McDonnell Douglas Corp
•
Filing: 1996-01-05
•
Granted: 1998-09-15
•
Expires: 2016-01-05
Abstract
Abstract The image correlation method and apparatus correlates or matches a test image with a template. The image correlation apparatus includes an image processor for partitioning the template into a number of labels, for determining the total number of pixels N T which form the template and for determining the number of pixels N i which form each of the labels i. The image correlation apparatus also includes comparator for comparing the test image to the template. The comparator respectively determines, for each predetermined gray level j, the number of pixels of the test image N j ,i representative of a predetermined gray level j which correspond to a predetermined label i of the template. The comparator respectively also determines, for each predetermined gray level j, the number of pixels of the test image N j representative of a predetermined gray level j which correspond to the template. The image correlation apparatus further includes correlation means for determining the correlation X between the test image and the template according to a predetermined equation which is based, at least in part, upon N j ,i, N j , N i and N T . The image correlation apparatus can also include an address generator for creating a number of relative offsets between the template and the test image. Thus, the test image can be compared to the template at each relative offset and the relative offset which provides the greatest correlation therebetween can be determined. Consequently, the test image and the template can be effectively matched such that a preselected object designated within the template can be located and identified within the test image.
Inventors
- 👤 Michael G. Neff
- 👤 Ted L. Johnson
- 👤 Steven A. Wright
- 👤 Victor E. Ratkowski, Jr.
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 15:06
CPC Classifications
F; F41; F41G; F41G7/00; F41G7/20; F41G7/22; F41G7/2273; F41G7/2293; F41G7/007; F41G7/2226; F41G7/2253; G; G06; G06T; G06T7/00; G06T7/30; G06T7/33; G06T7/337; G06V; G06V10/00; G06V10/70; G06V10/74; G06V10/75; G06V10/751; G06V10/7515; G06V10/94
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
237 words
A method for correlating a test image with a template to identify a specific object wherein both the test image and the template are comprised of a plurality of pixels representative of respective predetermined gray levels, the method comprising the steps of: partitioning the template into a plurality of labels, wherein each label is comprised of at least one pixel; determining the total number of pixels N T which comprise the template; determining the number of pixels N i which form each of the plurality of labels i of the template; comparing the template to the test image such that at least some of the pixels of the template correspond to respective pixels of the test image; determining, for each of a plurality of predetermined gray levels j, the number of pixels of the test image N j ,i representative of a predetermined gray level j which correspond to a predetermined label i of the template; determining, for each of a plurality of predetermined gray levels j, the number of pixels of the test image N j representative of a predetermined gray level j which correspond to the template; and determining the correlation X between the test image and the template to identify said object according to: ##EQU4## wherein i min and i max are the minimum and maximum label designations, respectively, and wherein j min and j max are the minimum and maximum gray levels, respectively.
Claim 2
Independent Claim
237 words
A method for correlating a test image with a template to identify a specific object wherein both the test image and the template are comprised of a plurality of pixels representative of respective predetermined gray levels, the method comprising the steps of: partitioning the template into a plurality of labels, wherein each label is comprised of at least one pixel; determining the total number of pixels N T which comprise the template; determining the number of pixels N i which form each of the plurality of labels i of the template; comparing the template to the test image such that at least some of the pixels of the template correspond to respective pixels of the test image; determining, for each of a plurality of predetermined gray levels j, the number of pixels of the test image N j ,i representative of a predetermined gray level j which correspond to a predetermined label i of the template; determining, for each of a plurality of predetermined gray levels j, the number of pixels of the test image N j representative of a predetermined gray level j which correspond to the template; and determining the correlation X between the test image and the template to identify said object according to: ##EQU4## wherein i min and i max are the minimum and maximum label designations, respectively, and wherein j min and j max are the minimum and maximum gray levels, respectively.
Claim 3
Dependent Claim
149 words
A method according to claim 1 further comprising the step of creating a plurality of relative offsets between the template and the test image, wherein said comparing step comprises the step of comparing the test image to the template at each relative offset, wherein said N j ,i determining step comprises the step of determining, at each relative offset, the number of pixels of the test image N j ,i representative of a predetermined gray level j which correspond to a predetermined label i of the template, wherein said N j determining step comprises the step of determining, at each relative offset, the number of pixels of the test image N j representative of a predetermined gray level j which correspond to the template, and wherein said correlation determining step comprises the step of determining the correlation X between the test image and the template at each relative offset.
Claim 4
Dependent Claim
29 words
A method according to claim 2 wherein said comparing step comprises the step of concurrently comparing the test image to the template at a plurality of the relative offsets.
Claim 5
Dependent Claim
27 words
A method according to claim 2 further comprising the step of determining the relative offset between the test image and template which provides the greatest correlation therebetween.
Claim 6
Dependent Claim
154 words
A method according to claim 1 further comprising the step of creating at least one relative rotational offset between the template and the test image, wherein said comparing step comprises the step of comparing the test image to the template at each relative rotational offset, wherein said N j ,i determining step comprises the step of determining, at each relative rotational offset, the number of pixels of the test image N j ,i representative of a predetermined gray level j which correspond to a predetermined label i of the template, wherein said N j determining step comprises the step of determining, at each relative rotational offset, the number of pixels of the test image N j representative of a predetermined gray level j which correspond to the template, and wherein said correlation determining step comprises the step of determining the correlation X between the test image and the template at each relative rotational offset.
Claim 7
Dependent Claim
28 words
A method according to claim 5 further comprising the step of determining the relative rotational offset between the test image and template which provides the greatest correlation therebetween.
Claim 8
Dependent Claim
151 words
A method according to claim 1 further comprising the step of scaling the template relative to the test image according to at least one predetermined scale, wherein said comparing step comprises the step of comparing the test image to the template at each predetermined scale, wherein said N j ,i determining step comprises the step of determining, at each predetermined scale, the number of pixels of the test image N j ,i representative of a predetermined gray level j which correspond to a predetermined label i of the template, wherein said N j determining step comprises the step of determining, at each predetermined scale, the number of pixels of the test image N j representative of a predetermined gray level j which correspond to the template, and wherein said correlation determining step comprises the step of determining the correlation X between the test image and the template at each predetermined scale.
Claim 9
Dependent Claim
27 words
A method according to claim 7 further comprising the step of determining the predetermined scale which provides the greatest correlation between the template and the test image.
Claim 10
Dependent Claim
39 words
A method according to claim 1 wherein said comparing step comprises the step of overlaying the template on the test image such that at least some of the pixels of the test image correspond to pixels of the template.
Claim 11
Dependent Claim
149 words
A method according to claim 1 wherein said partitioning step comprises the steps of: dividing the plurality of predetermined gray levels into a plurality of bins, wherein each bin includes a range of gray levels; determining, for each of the plurality of bins, an actual count of the number of pixels of the template which are representative of gray levels within the range of gray levels included within the respective bin; assigning a predetermined minimum count to each bin which has an actual count determined by said count determining step which is less than the predetermined minimum count; and reassigning the plurality of predetermined gray levels to the plurality of bins such that the greater of the predetermined minimum count or the actual count for each respective bin is within a predetermined range, wherein the pixels which are representative of gray levels within a respective bin form a label.
Claim 12
Dependent Claim
57 words
A method according to claim 10 further comprising the steps of: determining the maximum number of pixels of the template which are representative of a single predetermined gray level; and computing the predetermined minimum count to be equal to a predetermined percentage of the maximum number of pixels which are representative of a single predetermined gray level.
Claim 13
Dependent Claim
35 words
A method according to claim 1 further comprising the step of determining in N j ,i and in N j prior to said correlation determining step such that the correlation X can be efficiently computed.
Claim 14
Independent Claim
292 words
An apparatus for correlating a test image and a template to identify a specific object wherein both the test image and the template are comprised of a plurality of pixels representative of respective predetermined gray levels, the apparatus comprising: template processing means for processing the plurality of pixels which comprise the template, wherein said template processing means comprises: means for partitioning the template into a plurality of labels, wherein each label is comprised of at least one pixel; means for determining the total number of pixels N T which comprise the template; and means for determining the number of pixels N i which form each of the plurality of labels i of the template; and comparison means, responsive to said template processing means, for comparing the test image to the template such that at least some of the pixels of the test image correspond to respective pixels of the template, wherein said comparison means comprises: means for determining, for each of a plurality of predetermined gray levels j, the number of pixels of the test image N j ,i representative of a predetermined gray level j which correspond to a predetermined label i of the template; means for determining, for each of a plurality of predetermined gray levels j, the number of pixels of the test image N j representative of a predetermined gray level j which correspond to the template; and correlation means, responsive to said template processing means and said comparison means, for determining the correlation X between the test image and the template to identify said object according to: ##EQU5## wherein i min and i max are the minimum and maximum label designations, respectively, and wherein j min and j max are the minimum and maximum gray levels, respectively.
Claim 15
Independent Claim
292 words
An apparatus for correlating a test image and a template to identify a specific object wherein both the test image and the template are comprised of a plurality of pixels representative of respective predetermined gray levels, the apparatus comprising: template processing means for processing the plurality of pixels which comprise the template, wherein said template processing means comprises: means for partitioning the template into a plurality of labels, wherein each label is comprised of at least one pixel; means for determining the total number of pixels N T which comprise the template; and means for determining the number of pixels N i which form each of the plurality of labels i of the template; and comparison means, responsive to said template processing means, for comparing the test image to the template such that at least some of the pixels of the test image correspond to respective pixels of the template, wherein said comparison means comprises: means for determining, for each of a plurality of predetermined gray levels j, the number of pixels of the test image N j ,i representative of a predetermined gray level j which correspond to a predetermined label i of the template; means for determining, for each of a plurality of predetermined gray levels j, the number of pixels of the test image N j representative of a predetermined gray level j which correspond to the template; and correlation means, responsive to said template processing means and said comparison means, for determining the correlation X between the test image and the template to identify said object according to: ##EQU5## wherein i min and i max are the minimum and maximum label designations, respectively, and wherein j min and j max are the minimum and maximum gray levels, respectively.
Claim 16
Dependent Claim
148 words
An apparatus according to claim 13 further comprising offset means for creating a plurality of relative offsets between the template and the test image, wherein said comparison means is responsive to said offset means for comparing the test image to the template at each relative offset, wherein said N j ,i determining means comprises means for determining, at each relative offset, the number of pixels of the test image N j ,i representative of a predetermined gray level j which correspond to a predetermined label i of the template, wherein said N j determining means comprises means for determining, at each relative offset, the number of pixels of the test image N j representative of a predetermined gray level j which correspond to the template, and wherein said correlation means comprises means for determining the correlation X between the test image and the template at each relative offset.
Claim 17
Dependent Claim
26 words
An apparatus according to claim 14 further comprising means for determining the relative offset between the test image and template which provides the greatest correlation therebetween.
Claim 18
Dependent Claim
153 words
An apparatus according to claim 13 further comprising rotation means for creating at least one relative rotational offset between the template and the test image, wherein said comparison means is responsive to said rotation means for comparing the test image to the template at each relative rotational offset, wherein said N j ,i determining means comprises means for determining, at each relative rotational offset, the number of pixels of the test image N j ,i representative of a predetermined gray level j which correspond to a predetermined label i of the template, wherein said N j determining means comprises means for determining, at each relative rotational offset, the number of pixels of the test image N j representative of a predetermined gray level j which correspond to the template, and wherein said correlation means comprises means for determining the correlation X between the test image and the template at each relative rotational offset.
Claim 19
Dependent Claim
32 words
An apparatus according to claim 16 further comprising means, responsive to said correlation means, for determining the relative rotational offset between the test image and template which provides the greatest correlation therebetween.
Claim 20
Dependent Claim
149 words
An apparatus according to claim 13 further comprising scaling means for scaling the template relative to the test image according to at least one predetermined scale, wherein said comparison means is responsive to said scaling means for comparing the test image to the template at each predetermined scale, wherein said N j ,i determining means comprises means for determining, at each predetermined scale, the number of pixels of the test image N j ,i representative of a predetermined gray level j which correspond to a predetermined label i of the template, wherein said N determining means comprises means for determining, at each predetermined scale, the number of pixels of the test image N j representative of a predetermined gray level j which correspond to the template, and wherein said correlation means comprises means for determining the correlation X between the test image and the template at each predetermined scale.
Claim 21
Dependent Claim
32 words
An apparatus according to claim 18 further comprising the means, responsive to said correlation means, for determining the predetermined scale which provides the greatest correlation between the template and the test image.
Claim 22
Dependent Claim
174 words
An apparatus according to claim 13 wherein said partitioning means comprises: means for dividing the plurality of predetermined gray levels into a plurality of bins, wherein each bin includes a range of gray levels; means, responsive to said dividing means, for determining, for each of the plurality of bins, an actual count of the number of pixels which are representative of gray levels within the range of gray levels included within the respective bin; means, responsive to said actual count determining means, for assigning a predetermined minimum count to each bin which has an actual count determined by said count determining step which is less than the predetermined minimum count; and means, responsive to said actual count determining means and said assigning means, for reassigning the plurality of predetermined gray levels to the plurality of bins such that the greater of the predetermined minimum count or the actual count for each respective bin is within a predetermined range, wherein the pixels which are representative of gray levels within a respective bin form a label.
Claim 23
Dependent Claim
73 words
An apparatus according to claim 20 wherein said partitioning means further comprises: means for determining the maximum number of pixels of the template which are representative of a single predetermined gray level; and means, responsive to said means for determining the maximum number of pixels, for computing the predetermined minimum count to be equal to a predetermined percentage of the maximum number of pixels which are representative of a single predetermined gray level.
Claim 24
Dependent Claim
48 words
An apparatus according to claim 13 further comprising means, responsive to said N j ,i determining means and said N j determining means, for determining ln N j ,i and ln N j prior to determining the correlation X such that the correlation X can be efficiently computed.
References Cited (Backward Citations)
EP0463242A1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-09-14 | 2002-03-16 | 2002-09-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-09-14 | 2006-03-16 | 2006-09-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-09-14 | 2010-03-16 | 2010-09-15 | $7700.00 | Window Closed / Lapsed |