Pattern classification means using feature vector regions preconstructed from reference data

• US 5,060,277 A
• Filed: 04/25/1988
• Issued: 10/22/1991
• Est. Priority Date: 10/10/1985
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: The Palantir Corp. (Microsoft Corporation)
• Inventors: Bokser, Mindy R.
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): Couso, Jose L.
• Application Number:
  US07/163,374
• Time in Patent Office: 1,275 Days
• Field of Search: 382/14, 382/15, 382/16, 382/36-39, 382/48
• US Class Current: 382/160
• CPC Class Codes: G06F 18/23 Clustering techniques

Abstract

A method for classifying an input feature vector representing an unknown pattern as belonging to one of a set of pre-defined pattern classes, wherein the input feature vector is compared with pre-constructed regions. A hierarchy of possibility regions is used to exclude a pattern class from consideration. Certainty regions are used to classify with certainty the input feature vector as belonging to some pattern class. Confidence regions are used to identify, although not with certainty, the unknown input pattern and assign a confidence value indicating the relative confidence associated with the possiblity that this unknown pattern belongs to given pattern class.

Claims

1. The method of classifying an input feature vector representing an input pattern comprising the steps of:

for each selected pattern class in a predefined list of one or more pattern classes, obtaining a hierarchy of one or more sets of possibility regions associated with said selected pattern class, wherein

said associated hierarchy is formed using a large plurality of reference feature vectors;

each possibility region in each set of said associated hierarchy contains a plurality of reference feature vectors beloning to said selected class and may contain reference feature vectors which do not belong to said selected class;

for each set of said associated hierarchy, each reference feature vector belonging to said selected class is contained within at least one possibility region of said set; and

for each set of said associated hierarchy, the number of possibility regions in said set is significantly less than the number of reference feature vectors belonging to said selected class;

receiving said input feature vector; and

excluding from consideration those pattern classes which, for some set in the hierarchy associated with said pattern class, said input feature vector does not lie within any possibility region in said set.

2. The method of claim 1 wherein each set of possibility regions in said associated hierarchy is formed using a substantial plurality of reference feature vectors not belonging to said selected pattern class.

3. The method of claim 1 wherein each set of possibility regions in said associated hierarchy is formed using a substantial plurality of reference feature vectors belonging to said selected pattern class.

4. The method as in claim 1 wherein the possibility regions in each set in said associated hierarchy cumulatively contain a substantially minimum number of reference feature vectors not be selected pattern class, relative to the number of possibility regions in said set.

5. The method as in claim 1 wherein each set in said associated hierarchy is composed of a substantially minimum number of possibility regions, relative to the number of reference feature vectors not belonging to said pattern class that are contained in some possibility region of said set.

6. The method as in claim 1 wherein some set in said hierarchy contains exactly one possibility region.

7. The method as in claim 6 wherein said possibility region contains a minimum number of reference feature vectors not belonging to said associated pattern class.

8. The method as in claim 1 wherein said regions are selected from the group consisting of N-dimensional polygons and N-dimensional ellipses, where N is any integer.

9. The method as in claim 8 wherein N is defined as the number of features contained in each said reference feature vector.

10. The method as in claim 8 wherein each said possibility region is an N-dimensional sphere having a center and a radius and said input feature vector is determined to lie within a possibility region if the distance between said input feature vector and said center is less than or equal to said radius.

11. The method of claim 10 wherein said distance is the euclidian distance.

12. The method as in claim 1 wherein, for each pattern class in said predefined list, the sets in its associated hierarchy are ordered, and wherein said step of excluding comprises the steps of:

(i) selecting, for each pattern class in said predefined list, the set of possibility regions of lowest order in the ordered hierarchy associated with said class;

(ii) determining, for each said selected set, whether the input feature vector is contained in any of the possibility regions in said set;

(iii) eliminating from further consideration those pattern classes whose associated selected set does not contain the input feature vector;

(iv) selecting, for each pattern class in said predefined plurality of pattern classes that has not yet been eliminated from consideration, the set of possibility regions of next lowest order in the ordered hierarchy associated with said class;

(v) repeating steps (ii) through (iv) until all sets of possibility regions have been examined.

13. The method as in claim 12 wherein the sets in said associated hierarchy are ordered by increasing number of possibility regions in each set.

14. The method as in claim 12 wherein the sets in said hierarchy are ordered by decreasing number of reference feature vectors not belonging to said selected pattern class which are contained in the possibility regions of each set.

15. The method as in claim 12 wherein the sets in said hierarchy are ordered by decreasing total volume in the possibility regions of each set.

40. The method as in claim 1 wherein said step of classifying further comprises the steps of:

for each selected pattern class in said predefined list of pattern classes, obtaining an associated set of certainty regions, wherein;

the number of certainty regions in said associated set is significantly less than the number of reference feature vectors belonging to said selected class;

each certainty region of said associated set contains a plurality of reference feature vectors belonging to said selected class and does not contain reference feature vectors which do not belong to said selected class; and

substantially all reference feature vectors belonging to said selected class are contained in at least one certainty region of said associated set of certainty regions,

receiving said input feature vector; and

determining whether the input feature vector lies within any certainty region associated with a pattern class that has not yet been eliminated from consideration, and if so classifying said input pattern as belonging to the pattern class associated with the certainty region that contains said input feature vector.

41. The method as in claim 40 wherein, for each selected pattern class, the associated set of certainty regions are formed using a large plurality of reference feature vectors of said selected pattern class and a large plurality of reference feature vectors not of said selected pattern class.

42. The method as in claim 40 wherein, for each pattern class the number of possibility regions in each set of the hierarchy of possibility regions associated with said pattern class is significantly less than the number of certainty regions associated with said pattern class.

43. The method as in claim 40 wherein said step of determining comprises the steps of:

determining whether the input feature vector lies in any of a relatively small number of certainty regions which have recently been used to classify previously received input feature vectors; and

if so, classifying said input pattern as belonging to the pattern class associated with said certainty region.

44. The method of claim 40 wherein, for each selected pattern class in said predefined list of pattern classes, said associated set of certainty regions comprises a first plurality of one or more certainty regions and a second plurality of one or more certainty regions,

wherein each possibility region associated with said selected pattern class is associated with a certainty region from said first plurality of certainty regions;

and

wherein said step of classifying comprises the steps of;

(i) selecting, for each pattern class in said predefined list, the set of possibility regions of lowest order in the ordered hierarchy associated with said class;

(ii) determining which possibility regions of said selected sets and which certainty regions associated with said possibility regions contain said input feature vector;

(iv) if said input feature vector is contained within one of said associated certainty regions, classifying said input pattern as belonging to the pattern class associated to said associated certainty region, otherwise

(v) eliminating from further consideration those pattern classes associated with said sets of possibility regions not containing said input feature vector;

(vi) selecting sets of possibility regions of the next order within each group associated with classes which have not been eliminated from further consideration; and

(vii) repeating steps (ii) through (vi).

45. The method as in claim 44 wherein said step of determining is performed by the steps of:

(i) selecting a possibility region of a selected set;

(ii) determining if said possibility region contains said input feature vector;

(iii) if said possibility region contains said input feature vector, determining if the certainty region associated with said possibility region also contains said input feature vector; and

(iv) repeating steps (i) through (iii) for such possibility regions of said selected sets.

46. The method of claim 44 wherein the number of certainty regions in said first plurality of certainty region is significantly less than the total number of certainty regions.

47. The method of claim 44 wherein said step of classifying further comprises the step of determining, for each selected pattern class that has not yet been eliminated from consideration, whether said input feature vector is contained in any certainty region in said second plurality of certainty regions associated with said selected pattern class, and if so, classifying said input pattern as belonging to said selected pattern class.

48. The method as in claim 40 wherein said step of classifying further comprising the steps of:

obtaining a plurality of sets of confidence regions each of said set;

being related to an associated class of possible patterns which have not been eliminated from further consideration;

containing a number of confidence regions significantly less than the number of reference feature vectors of said associated class, each said confidence region being formed as an enlarged certainty region; and

which may contain reference feature vectors not of said associated class;

if said input feature vector does not lie in any certainty region, determining in which confidence regions said input feature vector lies; and

creating a candidate list of possible reference classes determined by those confidence regions in which said input feature vector lies.

16. The method of classifying an input feature vector representing an input pattern comprising the steps of:

obtaining a plurality of sets of certainty regions, each of said sets;

being related to an associated pattern class;

being formed using a large plurality of reference feature vectors not of said associated pattern class so as to contain substantially all members of said associated class;

being formed using a large plurality of reference feature vectors not of said associated plattern class so as to contain no reference feature vectors which are not of said associated pattern class and so as to contain substantially no members which are of a pattern class other than said associated pattern class;

containing a number of certainty regions significantly less than the number of reference feature vectors of said associated class; and

wherein each reference feature vector of said associated class lies within at least one certainty region of said set;

having been formed by the steps of;

(a) determining approximately the largest region which can be formed to contain one or more of said reference feature vectors of said associated pattern class and not contain reference feature vectors which are not of said associated pattern class;

(b) determining approximately the largest region which can be formed to contain one or more of said reference feature vectors of said associated pattern class which are not contained in a previously formed region and not contain reference feature vectors which are not of said associated pattern class; and

(c) repeating step (b) until substantially all of said reference feature vectors of said selected pattern class are contained in one or more of said regions;

receiving said input feature vector;

determining whether said input feature vector lies within any certainty region, and if so classifying said input pattern as belonging to the pattern class associated with the certainty region that contains said input feature vector.

17. The method as in claim 16 wherein said regions are selected from the group consisting of N-dimensional polygons and N-dimensional ellipses, where N is any integer.

18. The method as in claim 17 wherein N is defined as the number of features contained in each said reference feature vector.

19. The method as in claim 18 wherein each said certainty region is an N-dimensional sphere having a center and a radius and said input feature vector is determined to lie within a certainty region if the distance between said input feature vector and said center is less than or equal to said radius.

20. The method of claim 19 wherein said distance is the euclidian distance.

21. The method as in claim 16 wherein said step of determining comprises the steps of:

determining whether the input feature vector lies in any of a relatively small number of certainty regions which have recently been used to classify previously received input feature vectors; and

if so, classifying said input pattern as belonging to the pattern class associated with said certainty region.

22. The method as in claim 21 wherein said step of determining whether the input feature vector lies in any of a relatively small number of certainty regions is followed by the step of determining whether said input feature vector lies within any certainty region that has not yet been examined.

23. The method of claim 16 wherein said step of determining uses said sets of certainty regions in a selected order.

24. The method of claim 23 wherein said input feature vector and reference feature vectors represent characters.

25. The method of claim 24 wherein said selected order is determined in part by using subline information of said input feature vector.

26. The method of claim 25 wherein said subline information is used to select pattern classes having similar subline information and wherein certainty regions associated with said pattern classes having similar subline information are compared first with said input feature vector.

27. The method of claim 26 wherein said selected order is determined in part by statistics of character frequency in one or more selected languages.

28. The method of classifying an input feature vector representing an input pattern comprising the steps of:

obtaining a plurality of sets of certainty regions, each of said sets;

being related to an associated pattern class;

formed using a large plurality of reference feature vectors of said associated pattern class so as to contain substantially all members of said associated pattern class;

formed using a large plurality of reference feature vectors not of said associated pattern class so as to contain no reference feature vectors which are not of said associated pattern class and so as to contain substantially no members which are of a pattern class other than said associated pattern class;

containing a number of certainty regions significantly less than the number of reference feature vectors of said associated pattern class; and

wherein each reference feature vector of said associated pattern class lies within at least one certainty region of said set;

obtaining a plurality of sets of confidence regions, each said set;

being related to an associated pattern class;

containing a number of confidence regions significantly less than the number of reference feature vectors of said associated pattern class, each said confidence region being associated with a certainty region and formed by enlarging said certainty region; and

which may contain reference feature vectors not of said associated pattern class;

receiving said input feature vector;

determining in which certainty regions said input feature vector lies;

classifying said input pattern as belonging to the pattern class associated with the certainty regions in which said input feature vector lies;

if said input feature vector does not lie in a certainty region, determining in which confidence regions said input feature vector lies; and

creating a candidate list of possible pattern classes determined by those confidence regions in which said input feature vector lies.

29. The method as in claim 28 wherein said regions are selected from the group consisting of N-dimensional polygons and N-dimensional ellipses, where N is any integer.

30. The method as in claim 29 wherein N is defined as the number of features contained in each said reference feature vector.

31. The method as in claim 28 wherein each said confidence region is an N-dimensional sphere having a center and a radius and said input feature vector is determined to lie within a confidence region if the distance between said input feature vector and said center is less than or equal to said radius.

32. The method of claim 31 wherein said distance is the euclidian distance.

33. The method as in claim 28 including the step of providing a confidence value associated with each one of said possible pattern classes.

34. The method of claim 33 wherein the confidence value associated with a possible reference class is calculated as the smallest distance between said input feature vector and the certainty region associated with a confidence region associated with said possible pattern class in which said input feature vector lies.

35. The method of claim 34 wherein said candidate list does not contain possible reference classes having much less confidence than the greatest confidence value in said candidate list.

36. The method of claim 28 wherein each said certainty region is enlarged by the same factor to create an associated one of said confidence regions.

37. The method of claim 28 wherein each said certainty region is enlarged by one of a selected set of factors to create an associated one of said confidence regions.

38. The method of claim 28 wherein a confidence region contains at most relatively few reference feature vectors not of said associated class.

39. The method of claim 38 wherein said relatively few reference feature vectors not of said associated class represent patterns similar to those of said associated class.

49. The method of classifying an input pattern as possibly not being a member of any pattern class of a preselected collection of pattern classes, comprising the steps of:

obtaining a plurality of regions wherein

each such region is formed using a first plurality of reference feature vectors representing patterns which are not members of any pattern class of said preselected collection of pattern classes; and

each such region is formed so as to contain substantially no reference feature vectors of said first plurality of reference feature vectors;

receiving an input feature vector representing said input pattern; and

classifying said input pattern as possibly not being a member of any pattern class of said preselected collection of pattern classes if said input feature vector is contained in any region of said plurality of regions.

50. The method as in claim 49 wherein said plurality of regions is formed using a second plurality of reference feature vectors, each reference feature vector of said second plurality of reference feature vectors representing a pattern which is a member of one pattern class of said preselected collection of pattern classes, such that substantially all reference feature vectors in said second plurality of reference feature vectors are contained in at least one region of said plurality of regions.

51. The method as in claim 50 wherein the number of regions in said plurality of regions is substantially less than the number of reference feature vectors in said second plurality of reference feature vectors.

52. The method as in claim 49 wherein the number of regions in said plurality of regions is substantially less than the number of reference feature vectors in said first plurality of reference feature vectors.

53. The method as in claim 49 wherein each region in said plurality of regions is substantially as large as possible.

54. The method as in claim 50 wherein said second plurality of reference feature vectors includes, for each selected pattern class of said preselected collection of pattern classes, at least one reference feature vector representing a pattern which is a member of said selected pattern class.

55. The method as in claim 50 wherein said second plurality of reference feature vectors includes, for each selected pattern class of said preselected collection of pattern classes, a large plurality of reference feature vectors each representing a pattern which is a member of said selected pattern class.

56. The method of claim 49 wherein said first plurality of reference feature vectors comprise a plurality of reject reference feature vectors which do not represent any pattern class in said preselected collection of classes.

57. The method as in claim 56 wherein said reject feature vectors represent improperly segmented patterns.

58. The method as in claim 56 wherein said reject reference feature vectors include feature vectors obtained by joining a plurality of patterns representing pattern classes in said preselected collection of pattern classes.

59. The method as in claim 56 wherein said reject feature vectors include feature vectors representing noise patterns.

60. The method as in claim 49 wherein said regions are selected from the group consisting of N-dimensional polygons and N-dimensional ellipses, where N is an integer.

61. The method as in claim 60 wherein N is defined as the number of features contained in each said reference feature vector.

62. The method as in claim 60 wherein each said region is an N-dimensional sphere having a center and a radius and said input feature vector is determined to lie within a region if the distance between said input feature vector and said center is less than or equal to said radius.

63. The method of claim 62 wherein said distance is the euclidian distance.

64. The method of claim 49 wherein said preselected collection of classes are characters.

65. The method of classifying an input pattern comprising the steps of:

(a) analyzing said input pattern to create a list of zero or more classes, chosen from a preselected collection of classes of patterns, which are most likely to contain said input pattern as a member;

(b) analyzing said input pattern to determined if it is possibly not a member of any class in said preselected collection of classes;

(c) if it is determined that said input pattern is possibly not a member of any class of said preselected collection of classes, reconstructing said input pattern as a group of one or more patterns and, for each pattern in said group of patterns, analyzing said pattern to select, from preselected collection of classes of patterns, a list of zero or more classes which are most likely to contain said pattern as a member, thereby creating a group of lists of classes; and

(d) classifying said input pattern by utilizing either the list created in step (a) or the group of lists created in step (b), whichever provides a better recognition of said input pattern.

66. The method of claim 65 wherein said step of reconstructing said input pattern comprises the step of processing to eliminate errors due to noise or improper segmentation.

67. The method of claim 66 wherein said improper segmentation results in an input pattern which is formed by the joinder of two or more patterns belonging to one or more classes of said preselected collection of classes.

68. The method as in claim 65 wherein said step of analyzing said input pattern to determine if it is possibly not a member of any class in said preselected collection of classes comprises the steps of:

obtaining a plurality of regions wherein

each such region is formed using a first plurality of reference feature vectors representing patterns which are not members of any class of paid preselected collection of classes; and

each such region is formed so as to contain substantially no reference feature vectors of said first plurality of reference feature vectors;

receiving an input feature vector representing said input pattern; and

classifying said input pattern as possibly not being a member of any class of said preselected collection of classes if said input feature vector is not contained in any region of said plurality of regions.

69. The method as in claim 68 wherein said plurality of regions is formed using a second plurality of reference feature vectors, each reference feature vector of said second plurality of reference feature vectors representing a pattern which is a member of one class of said preselected collection of classes, such that substantially all reference feature vectors in said second plurality of reference feature vectors are contained in at least one region of said plurality of regions.

70. The method as in claim 69 wherein the number of regions in said plurality of regions is substantially less than the number of reference feature vectors in said second plurality of reference feature vectors.

71. The method as in claim 68 wherein the number of regions in said plurality of regions is substantially less than the number of reference feature vectors in said first plurality of reference feature vectors.

72. The method as in claim 68 wherein each region in said plurality of regions is substantially as large as possible.

73. The method as in claim 69 wherein said second plurality of reference feature vectors includes, for each selected class of said preselected collection of classes, at least one reference feature vector representing a pattern which is a member of said selected class.

74. The method as in claim 68 wherein said second plurality of reference feature vectors includes, for each selected class of said preselected collection of classes, a large plurality of reference feature vectors each representing a pattern which is a member of said selected class.

75. The method of claim 74 wherein said additional classes represent patterns which are formed by joining a plurality of said patterns represented by said preselected collection of classes.

76. The method as in claim 68 wherein said regions are selected from the group consisting of N-dimensional polygons and N-dimensional ellipses, where n is any integer.

77. The method as in claim 76 wherein N is defined as the number of features contained in each said reference feature vector.

78. The method as in claim 76 wherein each said region is an N-dimensional sphere having a center and a radius and said input feature vector is determined to lie within a region if the distance between said input feature vector and said center is less than or equal to said radius.

79. The method of claim 68 wherein said distance in the euclidian distance.

80. The method of claim 65 wherein said preselected collection of classes are characters.

81. The method as in claim 66 wherein said step of analyzing said input pattern to determine if it is possibly not a member of any class in said preselected collection of classes comprises the steps of:

creating for each class in said preselected collection of classes a buffered list of sets of physical dimensions, each such set being the physical dimensions of previous input patterns which were recently classified with a high degree of certainty as belonging to said class;

analyzing said input pattern to determine if it can be classified with a high degree of certainty as being a member of some class in said preselected collection of classes; and

, if not

analyzing said input pattern to create a list of zero or more classes, chosen from said preselected collection of classes, which are most likely to contain said input pattern as a member; and

determining whether, for each class in said list of classes, the physical dimensions of said input pattern differ significantly from each set of physical dimensions in the buffered list of sets of physical dimensions for said class and, if so, classifying said input pattern as possibly not being a member of any class of said preselected collection of classes.

82. The method of claim 81 wherein said preselected collection of classes are characters.

83. The method of claim 82 wherein the physical dimensions include width.

84. The method of claim 82 wherein the physical dimensions include height.

85. The method of claim 81 wherein, for each class in said preselected collection of classes, the buffered list of sets of physical dimensions contains at most the physical dimensions of that previous input pattern which was most recently classified with a high degree of certainty as belonging to said class.

86. The method as in claim 83 wherein each of said buffered lists is reinitialized to an empty list whenever there is evidence of a font change.

87. The method as in claim 65 wherein said step of analyzing said input pattern to determine if it is possibly not a member of any class in said preselected collection of classes comprises the steps of:

buffering the width of the previous input pattern which was most recently classified with a high degree of certainty as belonging to one of a preselected collection of wide character classes; and

classifying said input pattern as possibly not being a member of any class in said preselected collection of classes if its width is significantly larger than the width of said previous input pattern.