Shape recognition process

• US 5,546,476 A
• Filed: 05/13/1994
• Issued: 08/13/1996
• Est. Priority Date: 05/26/1993
• Status: Expired due to Term

• Current Assignee: Panasonic Electric Works Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Works Ltd (Panasonic Holdings Corporation)
• Inventors: Fujiwara, Yoshimasa, Ikebuchi, Hiroyuki, Mitaka, Ryosuke
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Bella, Matthew C.
• Application Number:
  US08/242,669
• Time in Patent Office: 823 Days
• Field of Search: 382/22, 382/34, 382/25, 382/201, 382/202, 382/203, 382/218, 382/258, 382/281, 382/197
• US Class Current: 382/201
• CPC Class Codes: G06V 10/46 Descriptors for shape, contour or point-related descriptors, e.g. scale invariant feature transform [SIFT] or bags of words [BoW]; Salient regional features colour feature extraction G06V10/56
• CPC Class Codes: G06V 10/471 using approximation functions
• CPC Class Codes: G06V 10/757 Matching configurations of points or features

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.

Claims

1. 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.

3. 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.

5. 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.

7. 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.

9. 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.

11. 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.

13. 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.

15. The process according to claim 1, wherein respective segments of the shape model are compared with respective segments of the objective shape.

17. 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.

19. 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.

21. 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.

23. 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.

25. 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.

27. 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.

29. 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.

31. 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.

33. 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.

35. 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.

2. 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.

4. 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.

6. 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.

8. 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.

10. 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.

12. 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.

14. 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.

16. The process according to claim 2, wherein respective segments of the shape model are compared with respective segments of the objective shape.

18. 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.

20. 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.

22. 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.

24. 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.

26. 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.

28. 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.

30. 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.

32. 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.

34. 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.

36. 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.