Preprocessing means for use in a pattern classification system

• US 5,657,397 A
• Filed: 02/15/1994
• Issued: 08/12/1997
• Est. Priority Date: 10/10/1985
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: Caere Corp. (Mexico) (Microsoft Corporation)
• Inventors: Bokser, Mindy R.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Tran, Phuoc
• Application Number:
  US08/196,845
• Time in Patent Office: 1,274 Days
• Field of Search: 382/14, 382/15, 382/36, 382/38, 382/155, 382/159, 382/160, 382/161, 382/224, 382/225, 382/227
• US Class Current: 382/225
• CPC Class Codes: G06F 18/23 Clustering techniques

Abstract

A method for recognizing an object by processing reference feature vectors a collection of reference feature vectors is generated; each representing a reference pattern that belongs to one of a plurality of predefined classes. Each class has associated all reference feature vectors representing reference patterns belonging to that class. For a selected class, an associated hierarchy of one or more sets of possibility regions is generated, wherein for a selected set in the hierarchy the number of possibility regions in said selected set is significantly less than the number of reference feature vectors belonging to said selected class, and such that each reference feature vector belonging to said selected class is contained in at least one possibility region of said selected set, and such that each possibility region of said selected set contains relatively few reference feature vectors not belonging to said selected class.

Claims

1. A method using a computer, having a memory and a processor, for recognizing an object by processing reference feature vectors comprising the steps of:

generating a collection of reference feature vectors, each of said reference feature vectors stored in said memory. and representing a reference pattern that belongs to one of a plurality of predefined classes stored in said memory;

associating with each class all reference feature vectors representing reference patterns belonging to that class; and

generating using said processor, for a selected class, an associated hierarchy of one or more sets of possibility regions, said sets stored in said memory wherein for a selected set in the hierarchy the number of possibility regions in said selected set is significantly less than the number of reference feature vectors belonging to said selected class, and such that each reference feature vector belonging to said selected class is contained in at least one possibility region of said selected set, and such that each possibility region of said selected set contains relatively few reference feature vectors not belonging to said selected class.

2. The method as in claim 1 wherein said reference feature vectors include a plurality of reject feature vectors, each reject feature vector representing a pattern which does not belong to any of said predefined classes.

3. The method as in claim 1 wherein said predefined classes are characters.

4. The method as in claim 3 wherein said reject feature vectors include feature vectors representing improperly segmented characters.

5. The method as in claim 3 wherein said reject feature vectors include feature vectors representing the most common pairs of characters.

6. The method as in claim 3 wherein said reject feature vectors include feature vectors representing noise patterns.

7. The method of claim 1 wherein the step of forming a set in the hierarchy of sets of possibility regions associated with a selected class comprises the step of:

selecting, using said processor, a number of reference feature vectors belonging to said selected class such that each reference feature vector of said number of reference feature vectors forms the center of a possibility region in said set of possibility regions.

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

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

10. The method as in claim 7 wherein said step of selecting a number of said reference feature vectors comprises the steps of:

(a) determining the center of mass of the reference feature vectors of said selected class;

(b) determining the reference feature vector of said selected class which is closest to said center of mass;

(c) using said reference feature vector which is closest to said center of mass as a center of region; and

(d) forming the substantially smallest possible region around said center of region which includes all reference feature vectors of said selected class.

11. The method as in claim 7 wherein said step of selecting a number of said reference feature vectors comprises the steps of:

(a) defining the maximum number of possibility regions desired;

(b) defining a measure of intrusion of reference feature vectors not of said selected class within said possibility region;

(c) defining a limit of intrusion of reference feature vectors not of said selected class within said possibility region; and

(d) generating one or more possibility regions, not to exceed said maximum number of possibility regions, such that all reference feature vectors of said selected class are contained in one or more of said possibility regions such that said limit of intrusion is not exceeded.

12. The method as in claim 11 wherein said measure of intrusion is defined as a measure of separation between the boundary of said possibility region and the reference feature vector not of said selected class within said possibility region which is furthest from the boundary of said possibility region.

13. The method as in claim 12 wherein said step of defining a limit of intrusion comprises the steps of:

(a) fixing a temporary limit of intrusion;

(b) determining approximately the largest possibility region which can be formed to contain one or more of said reference feature vectors of said selected class and not exceed said temporary limit of intrusion;

(c) determining approximately the largest possibility region which can be formed to contain one or more of said reference feature vectors of said selected class which are not contained in a previously formed possibility region and not exceed said temporary limit of intrusion;

(d) repeating step (c) until either all of said reference feature vectors of said selected class are contained in one or more of said possibility regions, or said maximum number of possibility regions desired is reached; and

(e) if said maximum number of possibility regions desired is reached and substantial all of said reference feature vectors of said selected class are not contained in one or more of said possibility regions, then

(i) increase said temporary limit of intrusion; and

(ii) repeat steps (b) through (e).

14. The method as in claim 13 which includes the step of fixing a maximum limit of intrusion which said temporary limit of intrusion cannot exceed.

15. The method as in claim 13 wherein a region is defined to be largest when it contains the largest number of reference feature vectors of said selected class.

16. The method as in claim 13 wherein a region is determined to be largest when it encloses the largest N dimensional volume, where N is defined as the number of features contained in each said reference feature vector.

17. The method of claim 1 wherein, for each class, the sets in its associated hierarchy of possibility regions are ordered by increasing number of possibility regions in each set.

18. The method of claim 1 wherein, for each class, the sets in its associated hierarchy of possibility regions are ordered by decreasing number of reference feature vectors not belonging to said selected class which are contained in the possibility regions of each set.

19. A method using a computer, having a memory and a processor, for obtaining classification information useful in classifying an unknown pattern as belonging to an associated pattern class comprising the steps of:

predefining and storing a plurality of pattern classes in the memory;

providing to said processor a set of input data associated with a set of reference patterns, each reference pattern belonging to one of said pattern classes;

manipulating said input data in said processor to obtain a collection of reference feature vectors, each reference feature vector representing one of said reference patterns;

associating with each class in said plurality of pattern classes all reference feature vectors representing reference patterns belonging to that class;

generating for a selected class in said plurality of pattern classes, 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 contains a plurality of reference feature vectors belonging to said selected class and does not contain reference feature vectors that 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; and

wherein said generating step comprises 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 selected class and not contain reference feature vectors which are not of said selected class;

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

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

storing, for each pattern class, a set of classification information representing said set of certainty regions formed for each pattern class; and

generating, for each pattern class, an associated hierarchy of possibility sets of possibility regions wherein for a possibility set, the number of possibility regions in said possibility set is significantly less than the number of certainty regions in a certainty set of certainty regions associated with said selected class and such that each reference feature vector belonging to said selected class is contained in at least one possibility region of said possibility set, and such that each possibility region of said possibility set contains relatively few reference feature vectors not belonging to said selected class.

20. The method as in claim 19 wherein for each class, the hierarchy of possibility sets associated with said selected class is formed such that each possibility region is associated with one certainty region in said certainty set.

21. The method as in claim 20 wherein the center of each said possibility region is equal to the center of its associated certainty region.

22. The method as in claim 20 wherein each of said possibility regions is formed by enlarging its associated certainty region.

23. A method of recognizing an object using a computer, having a memory and a processor, by processing reference feature vectors comprising the steps of:

predefining and storing a plurality of predefined pattern classes in said memory;

generating, using said processor, a collection of reference feature vectors, each reference feature vector stored in said memory and representing a reference pattern;

associating with each predefined pattern class all reference feature vectors representing reference patterns belonging to that class; and

for a selected class;

(a) generating, using said processor, an associated certainty set of certainty regions, said set of certainty regions stored in said memory of said computer, wherein;

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

each certainty region of said associated certainty set contains a plurality of reference feature vectors belonging to said selected class and does not contain reference feature vectors not belonging 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 certainty set of certainty regions; and

(b) generating an associated hierarchy of one or more possibility sets of possibility regions wherein for a selected possibility set in the hierarchy the number of possibility regions in said selected possibility set is significantly less than the number of reference feature vectors belonging to said selected class, and such that each reference feature vector belonging to said selected class is contained in at least one possibility region of said selected possibility set, and such that each possibility region of said selected possibility set contains relatively few reference feature vectors not belonging to said selected class.

24. The method as in claim 23 wherein said reference feature vectors include a plurality of reject feature vectors, each reject feature vector representing a pattern which does not belong to any of said predefined pattern classes.

25. The method as in claim 23 wherein said predefined pattern classes are characters.

26. The method as in claim 24 wherein said reject feature vectors include feature vectors representing improperly segmented characters.

27. The method as in claim 25 wherein said reject feature vectors include feature vectors representing the most common pairs of characters.

28. The method as in claim 25 wherein said reject feature vectors include feature vectors representing noise patterns.

29. The method as in claim 23 wherein the number of possibility regions in said selected possibility set is significantly less than the number of certainty regions in said selected certainty set.

30. The method as in claim 23 wherein said step of generating an associated certainty set of certainty regions using said processor comprises 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 selected class and not contain reference feature vectors which are not of said selected class;

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

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

31. The method of claim 23 wherein said step of generating an associated certainty set further comprises the step of selecting, for said selected class, a number of reference feature vectors belonging to said selected class such that each reference feature vector of said number of reference feature vectors forms the center of one certainty region of the certainty set.

32. The method of claim 23 wherein for each class, each certainty region in its associated certainty set has an associated confidence region which is formed by enlarging said certainty region.

33. The method of claim 32 wherein each said certainty region is enlarged by the same factor to create its associated confidence region.

34. The method of claim 32 wherein each said certainty region is enlarged by one of a selected set of factors to create its associated confidence region.

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

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

37. The method of claim 23 wherein said number of said reference feature vectors is selected to be approximately equal to the minimum number required to create said plurality of certainty regions.

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

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

40. The method of claim 23 wherein a region is determined to be largest when it contains the largest number of said reference feature vectors of said selected class.

41. The method of claim 28 wherein a region is determined to be largest when it encloses the largest N dimensional volume, where N is defined as the number of features contained in each said reference feature vector.

42. The method as in claim 30 wherein said steps of determining approximately the largest region comprise the steps of:

(a) determining the reference feature vector of said selected class which is not yet contained in a previously formed region which has approximately the largest distance from its nearest reference feature vector not of said selected class;

(b) using said reference feature vector of step (a) as a center; and

(c) forming the substantially largest possible region around said center which does not contain reference feature vectors which are not of said selected class.

43. The method as in claim 42 which further comprises the steps of:

(a) determining the center of mass of the reference feature vectors of said selected class which are contained in said region;

(b) determining the reference feature vector of said selected class which is contained in said region and which is closest to said center of mass;

(c) using said reference feature vector which is closest to said center of mass as a center of region;

(d) forming the substantially largest possible region around said center of region;

(e) repeating steps (a), (b), (c) and (d) until either a predefined number of iterations is performed or said center of region is equal to said center of mass; and

(f) selecting as said region, the region formed by step (d) which is either the last such region formed by step (d) or the largest of such regions formed by step (d) or the largest of such regions formed by step (d).

44. The method of claim 43 wherein said center of mass is determined using said reference feature vectors of said selected class which are contained in said region and which are not contained in a previously formed region.

45. The method of claim 43 wherein said center of mass is determined using said reference feature vectors of said selected class which are contained in said region and including those reference vectors contained in said region which are also contained in a previously formed region.

46. The method of claim 23 wherein the step of forming a set in the hierarchy of sets of possibility regions associated with a selected class comprises the step of:

selecting a number of reference feature vectors belonging to said selected class such that each reference feature vector of said number of reference feature vectors forms the center of a possibility region in said set of possibility regions.

47. The method as in claim 46 wherein said step of selecting a number of said reference feature vectors comprises the steps of:

(a) determining the center of mass of the reference feature vectors of said selected class;

(b) determining the reference feature vector of said selected class which is closest to said center of mass;

(c) using said reference feature vector which is closest to said center of mass as a center of region; and

(d) forming the substantially smallest possible region around said center of region which includes all reference feature vectors of said selected class.

48. The method as in claim 46 wherein said step of selecting a number of said reference feature vectors comprises the steps of:

(a) defining the maximum number of possibility regions desired;

(b) defining a measure of intrusion of reference feature vectors not of said selected class within said possibility region;

(c) defining a limit of intrusion of reference feature vectors not of said selected class within said possibility region; and

(d) generating one or more possibility regions, not to exceed said maximum number of possibility regions, such that all reference feature vectors of said selected class are contained in one or more of said possibility regions such that said limit of intrusion is not exceeded.

49. The method as in claim 48 wherein said measure of intrusion is defined as a measure of separation between the boundary of said possibility region and the reference feature vector not of said selected class within said possibility region which is furthest from the boundary of said possibility region.

50. The method as in claim 49 wherein said step of defining a limit of intrusion comprises the steps of:

(a) fixing a temporary limit of intrusion;

(b) determining approximately the largest possibility region which can be formed to contain one or more of said reference feature vectors of said selected class and not exceed said temporary limit of intrusion;

(c) determining approximately the largest possibility region which can be formed to contain one or more of said reference feature vectors of said selected class which are not contained in a previously formed possibility region and not exceed said temporary limit of intrusion;

(d) repeating step (c) until either all of said reference feature vectors of said selected class are contained in one or more of said possibility regions, or said maximum number of possibility regions desired is reached; and

(e) if said maximum number of possibility regions desired is reached and substantially all of said reference feature vectors of said selected class are not contained in one or more of said possibility regions, then

(i) increase said temporary limit of intrusion; and

(ii) repeat steps (b) through (e).

51. The method as in claim 50 which includes the step of fixing a maximum limit of intrusion which said temporary limit of intrusion cannot exceed.

52. The method as in claim 50 wherein a region is defined to be largest when it contains the largest number of reference feature vectors of said selected class.

53. The method as in claim 50 wherein a region is determined to be largest when it encloses the largest N dimensional volume, where N is defined as the number of features contained in each said reference feature vector.

54. The method of claim 23 wherein, for each class, the sets in its associated hierarchy of possibility regions are ordered by increasing number of possibility regions in each set.

55. The method of claim 23 wherein, for each class, the sets in its associated hierarchy of possibility regions are ordered by decreasing number of reference feature vectors contained in the possibility regions of each set that do not belong to said selected class.