Information processing method, information processing apparatus, and storage medium

• US 5,982,933 A
• Filed: 12/31/1996
• Issued: 11/09/1999
• Est. Priority Date: 01/12/1996
• Status: Expired due to Term

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Yoshii, Hiroto, Arai, Tsunekazu, Takasu, Eiji
• Primary Examiner(s): Tadayon, Bijan
• Application Number:
  US08/777,249
• Time in Patent Office: 1,043 Days
• Field of Search: 382/189, 382/197, 382/138, 382/159, 382/178, 382/225, 382/228, 382/202, 382/224, 382/175, 382/192, 382/311, 382/267, 382/173, 382/177, 382/181, 382/182, 382/183, 382/184 , 382/185, 382/186, 382/187, 382/188, 382/190, 382/191, 382/195, 382/201, 382/203, 382/209, 382/217, 382/218, 382/226, 382/227, 382/229, 382/230, 382/231, 382/232 , 382/251, 382/252, 382/321, 382/253, 382/278, 382/305, 382/306, 382/309, 382/312, 382/317, 358/405, 358/530, 358/540, 358/426
• US Class Current: 382/226
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06F 18/28 Determining representative reference patterns, e.g. by averaging or distorting; Generating dictionaries
• CPC Class Codes: G06V 30/1914 Determining representative reference patterns, e.g. averaging or distorting patterns; Generating dictionaries, e.g. user dictionaries

Abstract

This relates to a classification generation method whereby, in order to efficiently and accurately recognize a pattern having a large number of characteristics, a pattern classification tree is generated, with which a macro structural characteristic of a pattern is appropriately reflected and a competitive relationship between categories is adequately reflected, and to a method for recognizing an input pattern by using the generated classification tree. When an input pattern is formed using strokes, a training stroke is divided into a plurality of segments, and vector quantization is performed for the strokes in the segments. Among the quantized strokes in the segments, adjacent stroke sets are synthesized to repetitively generate upper rank stroke vectors. A stroke vector for which a predetermined entropy function is maximized is selected from the upper rank stroke vectors in a layered stroke vector series, and development is performed extending down into the lower rank stroke vector sets. As a result, a classification tree is prepared.

Claims

1. An information processing method for generating a classification tree, which is a recognition dictionary used for character recognition, comprising:

a division step of dividing a predetermined training stroke into a plurality of segments;

a vector quantization step of performing vector quantization of said strokes in said segments obtained at said division step;

a layered stroke vector generation step of synthesizing adjacent strokes of said segments, obtained at said division step, to obtain stroke sets to generate upper rank stroke vectors, and of producing a layered vector series; and

a classification tree generation step of selecting a stroke vector, for which a predetermined entropy function is the greatest, from upper rank stroke vectors in said layered stroke vector series that is obtained at said layered stroke vector generation step, and of developing said stroke vector to produce lower rank stroke vectors to generate a classification tree.

2. A method according to claim 1, wherein, at said vector quantization step, said strokes in said segments obtained at said division step are quantized to obtain vectors in eight directions, with intersecting angles formed by adjacent vectors being equal to each other.

3. A method according to claim 1, wherein, at said vector quantization step, said strokes in said segments obtained at said division step are quantized to obtain vectors in sixteen directions, with intersecting angles formed by adjacent vectors being equal to each other.

4. A method according to claim 1, wherein said entropy function is a function whereby an entropy reducing value is output when information is obtained for a lower rank vector set of one of said upper stroke vectors of said layered stroke vector series, which is generated at said layered stroke vector generation step.

5. A method according to claim 1, wherein at said classification tree generation step, if a training stroke corresponding to said lower rank stroke vector set is not present, said lower rank stroke vector set for said classification tree is regarded as invalid.

6. A method according to claim 5, wherein at said classification tree generation step, if a training stroke for a single category that corresponds to said lower rank stroke vector set is present, a number for said single category is attached to said lower rank stroke vector set.

7. A method according to claim 6, wherein at said classification tree generation step, if a training stroke for a plurality of categories that corresponds to said lower rank stroke vector is present, an upper rank stroke vector with which said predetermined entropy function is maximized is selected from upper rank stroke vectors for said lower rank stroke vector set.

8. A method according to claim 1, further comprising the step of recognizing a character using the generated classification tree, said recognizing step including:

a division step of dividing an input stroke into a plurality of segments;

a vector quantization step of performing vector quantization of strokes in said segments obtained at said division step;

a layered stroke vector generation step of synthesizing adjacent strokes of said segments, obtained at said division step, to obtain stroke sets to generate upper rank stroke vectors, and of producing a layered vector series; and

a recognition step of acquiring a recognition category by tracing said classification tree in order from said upper rank stroke vectors to lower rank stroke vectors in said layered stroke vector series, which is generated at said layered stroke vector generation step.

39. A method according to claim 1, further comprising a sub-pattern extraction step of extracting sub-patterns from a training pattern,

wherein each of said extracted sub-patterns is dealt as said training stroke to be divided in said division step.

40. A method according to claim 39, further comprising a layering step of layering in advance said sub-patterns that are extracted,

wherein said classification tree generation step generates a classification tree for said sub-patterns based on sub-pattern layers that are obtained.

41. An information processing method according to claim 40, wherein at said layering step, data are produced by degeneration, beginning with detailed data in said sub-patterns.

42. An information processing method according to claim 40, wherein at said classification tree step, data are so developed from upper rank through lower rank data in said sub-pattern layers.

43. An information processing method according to claim 40, wherein said sub-patterns are pattern parts obtained by dividing said training pattern.

44. An information processing method according to claim 40, wherein at said classification tree generation step, a variable with which classification efficiency is maximized is selected, and said classification tree is generated according to said variable.

45. An information processing method according to claim 40, further comprising:

a pattern input step of inputting a pattern;

an input pattern layering step of layering said pattern that is input; and

an identification step of identifying said pattern by tracing said classification tree from upper rank through lower rank data of said pattern for which layering is performed.

46. An information processing method according to claim 40, wherein said pattern is a bit-mapped data.

47. An information processing method according to claim 40, wherein said pattern is stroke data.

48. An information processing method according to claim 40, wherein said pattern is speech data.

69. A method according to claim 1, wherein said training stroke is replaced by a training voice waveform pattern and said training voice waveform pattern is divided in said division step.

9. An information processing apparatus for generating a classification tree, which is a recognition dictionary used for character recognition, comprising:

division means for dividing a predetermined training stroke into a plurality of segments;

vector quantization means for performing vector quantization of said strokes in said segments obtained by said division means;

layered stroke vector generation means for synthesizing adjacent strokes of said segments, obtained by said division means, to obtain stroke sets to generate upper rank stroke vectors, and for producing a layered vector series; and

classification tree generation means for selecting a stroke vector, for which a predetermined entropy function is the greatest, from upper rank stroke vectors in said layered stroke vector series that is obtained by said layered stroke vector generation means, and for developing said stroke vector to produce lower rank stroke vectors to generate a classification tree.

10. An apparatus according to claim 9, wherein said vector quantization means quantizes said strokes in said segments, obtained by said division means in order to acquire vectors in eight directions, with intersecting angles formed by adjacent vectors being equal to each other.

11. An apparatus according to claim 9, wherein said vector quantization means quantizes said strokes in said segments, obtained by said division means, in order to acquire vectors in sixteen directions, with intersecting angles formed by adjacent vectors being equal to each other.

12. An apparatus according to claim 9, wherein said entropy function is a function whereby an entropy reducing value is output when information is obtained for a lower rank vector set of one of said upper stroke vectors of said layered stroke vector series, which is generated by said layered stroke vector generation means.

13. An apparatus according to claim 9, wherein, if a training stroke corresponding to said lower rank stroke vector set is not present, said classification tree generation means regards, as invalid, said lower rank stroke vector set for said classification tree.

14. An apparatus according to claim 13, wherein, if a training stroke for a single category that corresponds to said lower rank stroke vector set is present, said classification tree generation means attaches a number for said single category to said lower rank stroke vector set.

15. An apparatus according to claim 14, wherein if a training stroke for a plurality of categories that corresponds to said lower rank stroke vector is present, said classification tree generation means selects an upper rank stroke vector, with which said predetermined entropy function is maximized, from upper rank stroke vectors for said lower rank stroke vector set.

16. An apparatus according to claim 9, further comprising means for recognizing a character using the generated classification tree, said recognizing means including:

division means for dividing an input stroke into a plurality of segments;

vector quantization means for performing vector quantization of strokes in said segments obtained by said division means;

layered stroke vector generation means for synthesizing adjacent strokes of said segments, obtained by said division means, to obtain stroke sets to generate upper rank stroke vectors, and for producing a layered vector series; and

recognition means for acquiring a recognition category by tracing said classification tree in order from said upper rank stroke vectors to lower rank stroke vectors in said layered stroke vector series, which is generated by said layered stroke vector generation means.

49. An apparatus according to claim 9, further comprising a sub-pattern extraction means for extracting sub-patterns from a training pattern,

wherein each of said extracted sub-patterns is dealt as said training stroke to be divided in said division means.

50. An apparatus according to claim 49, further comprising a layering means for layering in advance said sub-patterns that are extracted,

wherein said classification tree generation means generates a classification tree for said sub-patterns based on sub-pattern layers that are obtained.

51. An information processing apparatus according to claim 50, wherein at said layering means, data are produced by degeneration, beginning with detailed data in said sub-patterns.

52. An information processing apparatus according to claim 50, wherein at said classification tree step, data are so developed from upper rank through lower rank data in said sub-pattern layers.

53. An information processing apparatus according to claim 50, wherein said sub-patterns are pattern parts obtained by dividing said training pattern.

54. An information processing apparatus according to claim 50, wherein at said classification tree generation means, a variable with which classification efficiency is maximized is selected, and said classification tree is generated according to said variable.

55. An information processing apparatus according to claim 50, further comprising:

a pattern input means for inputting a pattern;

an input pattern layering means for layering said pattern that is input; and

an identification means for identifying said pattern by tracing said classification tree from upper rank through lower rank data of said pattern for which layering is performed.

56. An information processing apparatus according to claim 50, wherein said pattern is a bit-mapped data.

57. An information processing apparatus according to claim 50, wherein said pattern is stroke data.

58. An information processing apparatus according to claim 50, wherein said pattern is speech data.

70. An apparatus according to claim 9, wherein said training stroke is replaced by a training voice waveform pattern and said training voice waveform pattern is divided in said division step.

17. A computer accessible memory in which are stored stroke vector classification tree data that are constituted by a stroke vector series extending from a low-level to a high-level layer, said stroke vector classification data comprising:

root node production data,

leaf node attribute data, an attribute of which is that only a stroke vector series of a single category is present, that include said stroke vector series of said single category, and

node attribute data, for plural categories, an attribute of which is that only a stroke vector series for said plurality of categories is present, that include said stroke vector series of said plurality of categories,

wherein said stroke vector series, in said low-rank to high-rank layers, is assigned, for each of said layers, to respective nodes for said leaf node attribute data and said node attribute data for plural categories, while said root node attribute data are regarded as a start node of a lowest-level layer; and

wherein, when a stroke vector series, composed of a plurality of categories, that is constituted by a plurality of stroke vector series is present in a training stroke vector series at said layers, a stroke vector with which a predetermined entropy function is maximized is selected from a stroke vector series that is included in said node for said node attribute data for plural categories, and a lower rank stroke vector series is developed for said stroke vector that is selected, so that a node at the next layer is acquired that is linked with said node for said node attribute data for plural categories, to which said stroke vector series for plural categories is assigned.

59. A computer accessible memory according to claim 17, further comprising a sub-pattern extraction step of extracting sub-patterns from a training pattern,

wherein each of said extracted sub-patterns is dealt as said training stroke to be divided in said division step.

60. A computer accessible memory according to claim 59, further comprising a layering step of layering in advance said sub-patterns that are extracted,

wherein said classification tree generation step generates a classification tree for said sub-patterns based on sub-pattern layers that are obtained.

61. A computer accessible memory according to claim 60, wherein at said layering step, data are produced by degeneration, beginning with detailed data in said sub-patterns.

62. A computer accessible memory according to claim 60, wherein at said classification tree step, data are so developed from upper rank through lower rank data in said sub-pattern layers.

63. A computer accessible memory according to claim 60, wherein said sub-patterns are pattern parts obtained by dividing said training pattern.

64. A computer accessible memory according to claim 60, wherein at said classification tree generation step, a variable with which classification efficiency is maximized is selected, and said classification tree is generated according to said variable.

65. A method according to claim 60, further comprising:

a pattern input step of inputting a pattern;

an input pattern layering step of layering said pattern that is input; and

an identification step of identifying said pattern by tracing said classification tree from upper rank through lower rank data of said pattern for which layering is performed.

66. A computer accessible memory according to claim 60, wherein said pattern is a bit-mapped data.

67. A computer accessible memory according to claim 60, wherein said pattern is stroke data.

68. A computer accessible memory according to claim 60, wherein said pattern is speech data.

71. A computer accessible memory according to claim 17, wherein said training stroke is replaced by a training voice waveform pattern and said training voice waveform pattern is divided in said division step.

18. An information processing method for generating a layered pattern comprising:

a first degenerated pattern generation step of calculating, for a pattern divided into a plurality of segments, a logical sum for data of adjacent segments among said plurality of segments, and of generating a first degenerated pattern;

a second degenerated pattern generation step of calculating a logical sum for data of adjacent segments among a plurality of segments of said first degenerated pattern obtained at said first degenerated pattern generation step, and of generating a second degenerated pattern; and

a repetition step of repeating a process at said second degenerated pattern generation step a predetermined n times, based on said second degenerated pattern obtained at said second degenerated pattern generation step, and of generating a layered pattern of n-1 layers.

19. An information processing method according to claim 18, wherein said pattern that is divided into said plurality of segments is a training character pattern for a character recognition dictionary.

20. An information processing method according to claim 18, wherein said plurality of segments are like sized rectangles.

21. An information processing method according to claim 18, wherein said adjacent segments are ranged as an equivalent of continuous 2×

2 segments.

22. An information processing method according to claim 18, further comprising a classification tree generation step of generating a classification tree based on a plurality of layered patterns that are generated at said repetition step, said classification tree generation step including:

a link generation step of generating, for each layer of said layered pattern, a link from a segment extending from a degenerated pattern to a corresponding segment, including a pattern part, at a lower layer; and

a repetition step of repeating a process at said link generation step until a corresponding segment, including a pattern part, is not present in a lower layer, and of generating a classification tree.

23. An information processing method according to claim 18, wherein, at said link generation step, for each layer of said layered pattern a segment wherein a predetermined entropy function is maximized is selected from said segments, including said degenerated pattern, and wherein a link is generated in a segment at a lower layer, including a pattern part, that corresponds to said segment that is selected.

24. An information processing method according to claim 23, wherein said entropy function is a function whereby an entropy reducing value is output when, for each layer of said layered pattern, information is obtained for a lower layer segment corresponding to one of said segments that includes said degenerated pattern parts.

25. An information processing method according to claim 18, further comprising an N-gram table generation step of applying a predetermined layered pattern to said classification tree, which is acquired at said classification tree generation step, to generate an N-gram table.

26. An information processing method according to claim 25, wherein said N-gram table generation step includes:

an occurrence probability generation step of applying said predetermined layered pattern to said classification tree that is acquired at said classification tree generation step; and

a step of, when multiple patterns belonging to the same category belong to different links, selecting a link for a pattern for which occurrence is most probable, of abandoning remaining patterns that belong to the same category but belong to links other than said link that is selected, and of generating said N-gram table.

27. An information processing method according to claim 25, wherein said N-gram table that is acquired at said N-gram table generation step is searched to recognize a category that corresponds to an input character pattern.

72. A method according to claim 18, further comprising a sub-pattern extraction step or extracting sub-patterns from a training pattern, wherein each of said extracted sub-patterns is dealt as said pattern to be divided into said plurality of segments in said division step.

28. An information processing apparatus for generating a layered pattern comprising:

first degenerated pattern generation means for calculating, for a pattern divided into a plurality of segments, a logical sum for data of adjacent segments among said plurality of segments, and for generating a first degenerated pattern;

second degenerated pattern generation means for calculating a logical sum for data of adjacent segments among a plurality of segments of said first degenerated pattern obtained by said first degenerated pattern generation means, and for generating a second degenerated pattern; and

repetition means for repeating a process performed by said second degenerated pattern generation means a predetermined n times, based on said second degenerated pattern obtained by said second degenerated pattern generation means, and for generating a layered pattern of n-1 layers.

29. An information processing apparatus according to claim 28, wherein said pattern that is divided into said plurality of segments is a training character pattern for a character recognition dictionary.

30. An information processing apparatus according to claim 28, wherein said plurality of segments are like sized rectangles.

31. An information processing apparatus according to claim 28, wherein said adjacent segments are ranged as an equivalent of continuous 2×

2 segments.

32. An information processing apparatus according to claim 28, further comprising classification tree generation means for generating a classification tree based on a plurality of layered patterns that are generated by said repetition means, said classification tree generation means including:

link generation means for generating, for each layer of said layered pattern, a link from a segment extending from a degenerated pattern to a corresponding segment, including a pattern part, at a lower layer; and

repetition means for repeating a process performed by said link generation means until a corresponding segment, including a pattern part, is not present in a lower layer, and for generating a classification tree.

33. An information processing apparatus according to claim 28, wherein, for each layer of said layered pattern, by said link generation means is selected a segment wherein a predetermined entropy function is maximized from said segments, including said degenerated pattern, and wherein a link is generated in a segment at a lower layer, including a pattern part, that corresponds to said segment that is selected.

34. An information processing apparatus according to claim 33, wherein said entropy function is a function whereby an entropy reducing value is output when, for each layer of said layered pattern, information is obtained for a lower layer segment corresponding to one of said segments that includes said degenerated pattern parts.

35. An information processing apparatus according to claim 28, further comprising N-gram table generation means for applying a predetermined layered pattern to said classification tree, which is acquired by said classification tree generation means, to generate an N-gram table.

36. An information processing apparatus according to claim 35, wherein said N-gram table generation means includes:

occurrence probability generation means for applying said predetermined layered pattern to said classification tree that is acquired by said classification tree generation means; and

means for, when multiple patterns belonging to the same category belong to different links, selecting a link for a pattern for which occurrence is most probable, for abandoning remaining patterns that belong to the same category but belong to links other than said link that is selected, and for generating said N-gram table.

37. An information processing apparatus according to claim 35, wherein said N-gram table that is acquired by said N-gram table generation means is searched to recognize a category that corresponds to an input character pattern.

73. An apparatus according to claim 28, further comprising a sub-pattern extraction means for extracting sub-patterns from a training pattern, wherein each of said extracted sub-patterns is dealt as said pattern to be divided into said plurality of segments in said division means.

38. A computer program product having a storage medium in which is stored computer accessible program code for generating a layered character pattern, said program code including:

program code for calculating, for a character pattern divided into a plurality of segments, a logical sum for data of adjacent segments among said plurality of segments, and for generating a first degenerated character pattern;

program code for calculating a logical sum for data of adjacent segments among a plurality of segments of said first degenerated character pattern, and for generating a second degenerated character pattern; and

program code for repeating a process for generating said second degenerated character pattern a predetermined n times based on said second degenerated character pattern, and for generating a layered character pattern of n-1 layers.

74. A computer program product according to claim 38, further comprising a sub-pattern extraction step or extracting sub-patterns from a training pattern, wherein each of said extracted sub-patterns is dealt as said pattern to be divided into said plurality of segments in said division step.