US5546476A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Shape recognition process
Assignee: Panasonic Electric Works Co Ltd
•
Filing: 1994-05-13
•
Granted: 1996-08-13
•
Expires: 2014-05-13
Abstract
Abstract The identity of an object is determined by obtaining an image of the objective shape (e.g., by a camera), obtaining from that image an optimum objective shape representative of the object, and comparing the optimum objective shape with a known shape model of the object. The shape model is represented as a plurality of nodal points interconnected by line segments. The optimum objective shape is selected from a number of objective shapes each comprised of a row of dots having the same number of nodal points as the shape model. Each objective shape is compared with the shape model on the basis of (i) the proximity of the dots of the objective shape to the line segments of the shape model, (ii) the length of the dot segments with respect to the lengths of respective line segments, and (iii) the inclinations of the dot segments with respect to the inclinations of the line segments. The objective shape having the closest similarity to (i.e. smallest deviation from) the shape model is selected as the optimum objective shape to be compared with the shape model for identifying the object.
Inventors
- 👤 Ryosuke Mitaka
- 👤 Yoshimasa Fujiwara
- 👤 Hiroyuki Ikebuchi
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 11:52
CPC Classifications
G; G06; G06V; G06V10/00; G06V10/40; G06V10/46; G06V10/70; G06V10/74; G06V10/75; G06V10/757; G06V10/469; G06V10/471
Claims Analysis
Total Claims: 38
Claim 1
Independent Claim
323 words
In a process of recognizing an object by comparing an objective shape representative of said object with a shape model of the object, the process comprising the steps of: A) representing a known shape model in a two dimensional plane as a plurality of first nodal points and a plurality of line segments interconnecting respective pairs of said first nodal points, each line segment including a length characteristic and gradient characteristic; B) establishing standard values for the length and gradient characteristics, respectively, of each line segment; C) establishing tolerance ranges for the length and gradient characteristics, respectively, of each line segment; D) representing said object as a plurality of separate objective shapes each comprised of a row of dots disposed on a two-dimensional plane and having the same number of nodal points as said shape model, said row comprised of a plurality of second nodal points and a plurality of dot segments interconnecting respective pairs of said second nodal points, E) separately evaluating each objective shape determined from step D by: E1) determining an average spacing of all dots of said dot row from said line segments of said shape model, E2) comparing lengths of said dot segments to said tolerance ranges of respective line segment lengths, to determine a length deviation of each dot segment outside of said tolerance range therefor, and summing said length deviations of all dot segments to establish a length deviation sum, E3) comparing gradients of said dot segments to said tolerance ranges of respective line segment gradients, to determine a gradient deviation of each dot segment outside of said tolerance range therefor, and summing said gradient deviations of all dot segments to establish a gradient deviation sum, E4) summing values of said average spacing, said length deviation sum, and said gradient deviation sum for defining a deviation quantity total, and E5) selecting the objective shape having a lowest deviation quantity total for comparison with the shape model.
Claim 2
Dependent Claim
323 words
In a process of recognizing an object by comparing an objective shape representative of said object with a shape model of the object, the process comprising the steps of: A) representing a known shape model in a two dimensional plane as a plurality of first nodal points and a plurality of line segments interconnecting respective pairs of said first nodal points, each line segment including a length characteristic and gradient characteristic; B) establishing standard values for the length and gradient characteristics, respectively, of each line segment; C) establishing tolerance ranges for the length and gradient characteristics, respectively, of each line segment; D) representing said object as a plurality of separate objective shapes each comprised of a row of dots disposed on a two-dimensional plane and having the same number of nodal points as said shape model, said row comprised of a plurality of second nodal points and a plurality of dot segments interconnecting respective pairs of said second nodal points, E) separately evaluating each objective shape determined from step D by: E1) determining an average spacing of all dots of said dot row from said line segments of said shape model, E2) comparing lengths of said dot segments to said tolerance ranges of respective line segment lengths, to determine a length deviation of each dot segment outside of said tolerance range therefor, and summing said length deviations of all dot segments to establish a length deviation sum, E3) comparing gradients of said dot segments to said tolerance ranges of respective line segment gradients, to determine a gradient deviation of each dot segment outside of said tolerance range therefor, and summing said gradient deviations of all dot segments to establish a gradient deviation sum, E4) summing values of said average spacing, said length deviation sum, and said gradient deviation sum for defining a deviation quantity total, and E5) selecting the objective shape having a lowest deviation quantity total for comparison with the shape model.
Claim 3
Dependent Claim
317 words
In a process of recognizing an object by comparing an objective shape representative of said object with a shape model of the object, the process comprising the steps of: A) representing a known shape model in a two dimensional plane as a plurality of first nodal points and a plurality of line segments interconnecting respective pairs of said first nodal points, each line segment including a length characteristic and gradient characteristic; B) establishing standard values for the length and gradient characteristics, respectively, of each line segment; C) establishing tolerance ranges for the length and gradient characteristics, respectively, of each line segment; D) representing said object as a plurality of separate objective shapes each comprised of a row of dots disposed on a two-dimensional plane and having the same number of nodal points as said shape model, said row comprised of a plurality of second nodal points and a plurality of dot segments interconnecting respective pairs of said second nodal points, E) separately evaluating each objective shape determined from step D by: E1) determining an average spacing of all dots of said dot row from said line segments of said shape model, E2) comparing lengths of said dot segments to said standard values therefor, to determine a length deviation of each dot segment outside of said standard values, and summing said length deviations of all dot segments to establish a length deviation sum, E3) comparing gradients of said dot segments to said standard values therefor, to determine a gradient deviation of each dot segment outside of such standard values, and summing said gradient deviations of all dot segments to determine a gradient deviation sum, E4) summing values of said average spacing, said length deviation sum, and said gradient deviation sum for defining a deviation quantity total, and F) selecting the objective shape having the lowest deviation quantity total for comparison with the shape model determined from step E4.
Claim 4
Dependent Claim
317 words
In a process of recognizing an object by comparing an objective shape representative of said object with a shape model of the object, the process comprising the steps of: A) representing a known shape model in a two dimensional plane as a plurality of first nodal points and a plurality of line segments interconnecting respective pairs of said first nodal points, each line segment including a length characteristic and gradient characteristic; B) establishing standard values for the length and gradient characteristics, respectively, of each line segment; C) establishing tolerance ranges for the length and gradient characteristics, respectively, of each line segment; D) representing said object as a plurality of separate objective shapes each comprised of a row of dots disposed on a two-dimensional plane and having the same number of nodal points as said shape model, said row comprised of a plurality of second nodal points and a plurality of dot segments interconnecting respective pairs of said second nodal points, E) separately evaluating each objective shape determined from step D by: E1) determining an average spacing of all dots of said dot row from said line segments of said shape model, E2) comparing lengths of said dot segments to said standard values therefor, to determine a length deviation of each dot segment outside of said standard values, and summing said length deviations of all dot segments to establish a length deviation sum, E3) comparing gradients of said dot segments to said standard values therefor, to determine a gradient deviation of each dot segment outside of such standard values, and summing said gradient deviations of all dot segments to determine a gradient deviation sum, E4) summing values of said average spacing, said length deviation sum, and said gradient deviation sum for defining a deviation quantity total, and F) selecting the objective shape having the lowest deviation quantity total for comparison with the shape model determined from step E4.
Claim 5
Dependent Claim
28 words
The process according to claim 1, wherein step E4 further comprises providing respective weighted values for said average spacing, said length deviation sum, and said gradient deviation sum.
Claim 6
Dependent Claim
28 words
The processing according to claim 2, wherein step E4 further comprises providing respective weighted values for said average spacing, said length deviation sum, and said gradient deviation sum.
Claim 7
Dependent Claim
78 words
The process according to claim 1, wherein step D further comprises subjecting said row of dots to a polygonal line approximation step which defines said dot segments as respective straight lines whose points of intersection define said nodal points, step E2 comprising comparing lengths of said straight lines to said tolerance ranges of said respective line segment lengths, and step E3 comprises comparing gradients of said straight lines to said tolerance ranges of said respective line segment gradients.
Claim 8
Dependent Claim
78 words
The process according to claim 2, wherein step D further comprises subjecting said row of dots to a polygonal line approximation step which defines said dot segments as respective straight lines whose points of intersection define said nodal points, step E2 comprising comparing lengths of said straight lines to said tolerance ranges of said respective line segment lengths, and step E3 comprises comparing gradients of said straight lines to said tolerance ranges of said respective line segment gradients.
Claim 9
Dependent Claim
106 words
The process according to claim 1, wherein step D comprises subjecting said row of dots to a polygonal line approximation step which defines said dot segments as respective straight lines whose points of intersection define said nodal points; and selecting candidate nodal points when the number of nodal points of an objective shape is less than the number of nodal points of the shape model, said candidate nodal points comprising all nodal points disposed within a predetermined range adjacent to a selected nodal point, the candidate nodal point having a minimum deviation quantity total being selected as a nodal point for comparison with the shape model.
Claim 10
Dependent Claim
106 words
The process according to claim 2, wherein step D comprises subjecting said row of dots to a polygonal line approximation step which defines said dot segments as respective straight lines whose points of intersection define said nodal points; and selecting candidate nodal points when the number of nodal points of an objective shape is less than the number of nodal points of the shape model, said candidate nodal points comprising all nodal points disposed within a predetermined range adjacent to a selected nodal point, the candidate nodal point having a minimum deviation quantity total being selected as a nodal point for comparison with the shape model.
Claim 11
Dependent Claim
25 words
The process according to claim 1, wherein step D further comprises subjecting said row of dots to a Hough transformation to establish a Hough curve.
Claim 12
Dependent Claim
25 words
The process according to claim 2, wherein step D further comprises subjecting said row of dots to a Hough transformation to establish a Hough curve.
Claim 13
Dependent Claim
128 words
The process according to claim 1, wherein step D further comprises subjecting said row of dots to a polygonal line approximation step which defines said dot segments as respective straight lines whose points of intersection define said nodal points; and further comprising the steps of selecting candidate nodal points when the number of nodal points of the objective shape is less than the number of nodal points in the shape model, said candidate nodal points comprising a dot in said dot row located between a pair of adjacent nodal points which possess a maximum distance from a straight line extending between said pair of adjacent nodal points, the candidate nodal point having the smallest said distance being selected as a nodal point for comparison with said objective shape.
Claim 14
Dependent Claim
128 words
The process according to claim 2, wherein step D further comprises subjecting said row of dots to a polygonal line approximation step which defines said dot segments as respective straight lines whose points of intersection define said nodal points; and further comprising the steps of selecting candidate nodal points when the number of nodal points of the objective shape is less than the number of nodal points in the shape model, said candidate nodal points comprising a dot in said dot row located between a pair of adjacent nodal points which possess a maximum distance from a straight line extending between said pair of adjacent nodal points, the candidate nodal point having the smallest said distance being selected as a nodal point for comparison with said objective shape.
Claim 15
Dependent Claim
26 words
The process according to claim 1, wherein step D includes performing an interpolation to fill a vacancy of one or more dots in the dot arrow.
Claim 16
Dependent Claim
26 words
The process according to claim 2, wherein step D includes performing an interpolation to fill a vacancy of one or more dots in the dot arrow.
Claim 17
Dependent Claim
22 words
The process according to claim 1, wherein respective segments of the shape model are compared with respective segments of the objective shape.
Claim 18
Dependent Claim
22 words
The process according to claim 2, wherein respective segments of the shape model are compared with respective segments of the objective shape.
Claim 19
Dependent Claim
30 words
The process according to claim 1, wherein the shape recognition is repeated with said tolerance of said feature for the shape model automatically altered on the basis of previous comparisons.
Claim 20
Dependent Claim
30 words
The process according to claim 2, wherein the shape recognition is repeated with said tolerance of said feature for the shape model automatically altered on the basis of previous comparisons.
Claim 21
Dependent Claim
28 words
The process according to claim 1, further including the step of comparing the objective shape selected in step F, with said shape model by a dynamic programming step.
Claim 22
Dependent Claim
28 words
The process according to claim 2, further including the step of comparing the objective shape selected in step F, with said shape model by a dynamic programming step.
Claim 23
Dependent Claim
77 words
The process according to claim 1, wherein steps A through E4 are performed for each of a plurality of sections of said object, step E4 comprising establishing a threshold value with respect to said deformation quantity total, whereby when the deviation quantity total being calculated in step E4 for a given section exceeds the threshold value, the calculation for the given section is stopped, and the calculation of deviation quantity total for the next section is initiated.
Claim 24
Dependent Claim
77 words
The process according to claim 2, wherein steps A through E4 are performed for each of a plurality of sections of said object, step E4 comprising establishing a threshold value with respect to said deformation quantity total, whereby when the deviation quantity total being calculated in step E4 for a given section exceeds the threshold value, the calculation for the given section is stopped, and the calculation of deviation quantity total for the next section is initiated.
Claim 25
Dependent Claim
34 words
The process according to claim 1, wherein the nodal points are selected from the dot row of the objective shape with the knowledge relative to at least one nodal point of the shape model.
Claim 26
Dependent Claim
34 words
The process according to claim 2, wherein the nodal points are selected from the dot row of the objective shape with the knowledge relative to at least one nodal point of the shape model.
Claim 27
Dependent Claim
47 words
The process according to claim 1, wherein a limited range is set for the shape model so that, when the deviation quantity total exceeds this limited range during step E4, this calculation of the deviation quantity is stopped, and the deviation quantity for next selection is calculated.
Claim 28
Dependent Claim
47 words
The process according to claim 2, wherein a limited range is set for the shape model so that, when the deviation quantity total exceeds this limited range during step E4, this calculation of the deviation quantity is stopped, and the deviation quantity for next selection is calculated.
Claim 29
Dependent Claim
37 words
The process according to claim 1, wherein after comprising a whole shape of the objective shape with the whole shape model, a portion of the objective shape is compared with a corresponding portion of the shape model.
Claim 30
Dependent Claim
37 words
The process according to claim 2, wherein after comprising a whole shape of the objective shape with the whole shape model, a portion of the objective shape is compared with a corresponding portion of the shape model.
Claim 31
Dependent Claim
56 words
The process according to claim 1, wherein a threshold value is provided with respect to the minimum value of the deviation quantity total so that, when the minimum value of the deformation quantity is larger than said threshold value, a degree of coincidence of the objective shape with the shape model is concluded to be low.
Claim 32
Dependent Claim
56 words
The process according to claim 2, wherein a threshold value is provided with respect to a minimum value of the deviation quantity total so that, when the minimum value of the deformation quantity is larger than said threshold value, a degree of coincidence of the objective shape with the shape model is concluded to be low.
Claim 33
Dependent Claim
48 words
The process according to claim 1, wherein the degree of coincidence of the objective shape with respect to the shape model is judged through a comparison of a positional relationship of at least two of the nodal points of the objective shape with a preliminarily set evaluation standard.
Claim 34
Dependent Claim
48 words
The process according to claim 2, wherein a degree of coincidence of the objective shape with respect to the shape model is judged through a comparison of a positional relationship of at least two of the nodal points of the objective shape with a preliminarily set evaluation standard.
Claim 35
Dependent Claim
53 words
The process according to claim 1, wherein a plurality of shape models of mutually different shapes are provided, the shape models being respectively compared with the objective shape selected in step F, and the shape model having a minimum deviation quantity total is selected as the shape model coinciding with the objective shape.
Claim 36
Dependent Claim
53 words
The process according to claim 2, wherein a plurality of shape models of mutually different shapes are provided, the shape models being respectively compared with the objective shape selected in step F, and the shape model having a minimum deviation quantity total is selected as the shape model coinciding with the objective shape.
Claim 37
Dependent Claim
62 words
The process according to claim 1, wherein a plurality of shape models of mutually different shapes is provided, the respective shape models are compared with the objective shape in a pre-set order, and a first one of the respective shape models whose deviation quantity total is below a pre-set threshold value is selected as the shape model coinciding with the objective shape.
Claim 38
Dependent Claim
62 words
The process according to claim 2, wherein a plurality of shape models of mutually different shapes is provided, the respective shape models are compared with the objective shape in a pre-set order, and a first one of the respective shape models whose deviation quantity total is below a pre-set threshold value is selected as the shape model coinciding with the objective shape.
References Cited (Backward Citations)
US3979722A
Cited
US4015239A
Cited
JPH01161487A
Cited
US4891762A
Cited
US5065439A
Cited
JPH03172978A
Cited
US5220621A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-08-13 | 2000-02-12 | 2000-08-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-08-13 | 2004-02-12 | 2004-08-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-08-13 | 2008-02-12 | 2008-08-13 | $7700.00 | Window Closed / Lapsed |