US5020112A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Image recognition method using two-dimensional stochastic grammars
Assignee: NCR Voyix Corp
•
Filing: 1989-10-31
•
Granted: 1991-05-28
•
Expires: 2009-10-31
Abstract
Abstract A method of automatically identifying bitmapped image objects. Each of a set of templates in an object template library is compared with all areas of like size of a bitmapped image. A set of signals is generated for each such comparison that satisfies a defined matching criteria between the template and the image area being compared. The set of signals identifies the object based on the matching template, the location of the object in the image and an indication of the goodness of the match between the object and the template. A series of possible parse trees are formed that describe the image with a probability of occurrence for each tree. Each parent node and its child nodes of each parse tree satisfies a grammatical production rule in which some of the production rules define spatial relationships between objects in the image. The one of the possible parse trees which has the largest probability of occurence is selected for further utilization.
Inventors
- 👤 Philip A. Chou
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 10:16
CPC Classifications
G; G06; G06V; G06V30/00; G06V30/10; G06V30/19; G06V30/196; G06V30/1983; G06V30/1985; G06V30/26; G06V30/262; G06V30/274
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
157 words
A method of identifying bitmapped objects of an image comprising the steps of: comparing the templates in an object template library with all areas of like size of the image, generating a set of signals for each such comparison that satisfies a defined matching criteria between the template and the image area being compared, said set of signals identifying the object based on the matching template, the location of the object in the image and an indication of the goodness of the match between the object and the template, forming a series of possible parse trees of the image with a probability of occurrence for each tree, wherein each parent node and its child nodes of each parse tree satisfies a grammatical production rule, in which certain ones of the production rules define spatial relationships between objects in the image, and selecting one of the possible parse trees having the largest probability of occurrence for further utilization.
Claim 2
Independent Claim
157 words
A method of identifying bitmapped objects of an image comprising the steps of: comparing the templates in an object template library with all areas of like size of the image, generating a set of signals for each such comparison that satisfies a defined matching criteria between the template and the image area being compared, said set of signals identifying the object based on the matching template, the location of the object in the image and an indication of the goodness of the match between the object and the template, forming a series of possible parse trees of the image with a probability of occurrence for each tree, wherein each parent node and its child nodes of each parse tree satisfies a grammatical production rule, in which certain ones of the production rules define spatial relationships between objects in the image, and selecting one of the possible parse trees having the largest probability of occurrence for further utilization.
Claim 3
Dependent Claim
26 words
The method of claim 1 further comprising the step of identifying a set of grammatical production rules before the step of forming the possible parse trees.
Claim 4
Dependent Claim
16 words
The method of claim 2 wherein the set of grammatical production rules define a context-free grammar.
Claim 5
Dependent Claim
86 words
The method of claim 1 or claim 3 wherein the parsing step further comprises: testing each object identified by each set of signals with each other such object, including the spatial constraints associated with the objects, to determine if the combination of such objects results in a new object that satisfies the production rules and, if so, calculating the probability of the existence of the combined object in the image, and including the new combined object and its probability as a possible parsing of the image.
Claim 6
Dependent Claim
118 words
The method of claim 4 wherein the probability of an object formed by combining objects a and b is calculated from the formula outprob(s)=prob(r)*outprob(a)* outprob(b)*wsprob(s), where prob(r) is a probability associated with the production rule governing the combination of a and b, outprob(a) and outprob(b) are the probabilities of the existence of objects a and b in the image, as determined from a template, or outprob(s) and wsprob(s) is determined by the equation wsprob(s)=p.sup.d (1-p).sup.(k-d), where k is the area of apparent whitespace in a bounding box for the combined object s, d is the number of black pixels in this whitespace, and p is an empirically determined probability that one pixel in the image is in error.
Claim 7
Dependent Claim
25 words
The method of claim 1 further comprising the step of reestimating the probabilities associated with each production rule from the set of possible parse trees.
Claim 8
Dependent Claim
17 words
The method of claim 1 further comprising the step of reestimating the probability of a pixel error.
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) | 1994-05-27 | 1994-11-26 | 1995-05-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-05-27 | 1998-11-26 | 1999-05-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-05-27 | 2002-11-26 | 2003-05-28 | $7700.00 | Window Closed / Lapsed |