System and method for automated interpretation of input expressions using novel a posteriori probability measures and optimally trained information processing networks

• US 5,727,081 A
• Filed: 08/04/1994
• Issued: 03/10/1998
• Est. Priority Date: 12/31/1991
• Status: Expired due to Term

• Current Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Denker, John Stewart, Burges, Christopher John
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Tran, Phuoc
• Application Number:
  US08/286,147
• Time in Patent Office: 1,314 Days
• Field of Search: 382/229, 382/230, 382/231, 382/228, 382/226, 382/177, 382/178, 382/179, 382/156, 382/157, 382/159, 382/160, 382/161, 382/101, 382/102
• US Class Current: 382/229
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/15 Cutting or merging image elements, e.g. region growing, watershed or clustering-based techniques
• CPC Class Codes: G06V 30/153 using recognition of characters or words

Abstract

A method and system for forming an interpretation of an input expression, where the input expression is expressed in a medium, the interpretation is a sequence of symbols, and each symbol is a symbol in a known symbol set. In general, the system processes an acquired input data set representative of the input expression, to form a set of segments, which are then used to specify a set of consegmentations. Each consegmentation and each possible interpretation for the input expression is represented in a data structure. The data structure is graphically representable by a graph comprising a two-dimensional array of nodes arranged in rows and columns and selectively connected by directed arcs. Each path, extending through the nodes and along the directed arcs, represents one consegmentation and one possible interpretation for the input expression. All of the consegmentations and all of the possible interpretations for the input expression are represented by the set of paths extending through the graph. For each row of nodes in the graph, a set of scores is produced for the known symbol set, using a complex of optimally trained neural information processing networks. Thereafter the system computes an a posteriori probability for one or more symbol sequence interpretations. By deriving each a posteriori probability solely through analysis of the acquired input data set, highly reliable probabilities are produced for competing interpretations for the input expression.

Claims

1. A system for analyzing an input expression and scoring possible interpretations of said input expression, said system comprising:

segment producing means for analyzing an input data set representative of said input expression and dividing said input data set into a plurality of segments, each said segment having specifiable boundaries and being classifiable as possibly representing any one of a plurality of symbols in a predetermined symbol set,

said input data set comprising a set of pixels associated with an acquired image of a graphically represented sequence of symbols, and said segment producing means analyzing said set of pixels and dividing said set of pixels into a plurality of image segments, such that each said image segment has specified boundaries and is classifiable as possibly representing any one or more of said plurality of symbols in a predetermined symbol set;

segment scoring means for analyzing each segment in said plurality of segments, and assigning a score to each possible classification of said segment associated with a particular symbol in said predetermined symbol set;

representation means for representing a plurality of possible interpretations for said input expression, and a plurality of image consegmentations, wherein each said possible interpretation consists of a different sequence of symbols selected from said plurality of symbols, and each said consegmentation consists of a different sequence of said plurality of segments;

consegmentation scoring means for assigning scores to said plurality of consegmentations based on the scores assigned to said segments;

candidate interpretation identifying means for identifying one or more candidate symbol interpretations from said plurality of possible interpretations based on the scores assigned to said plurality of segments;

symbol sequence scoring means for assigning scores to said one or more candidate interpretations based on the scores assigned to one or more of said plurality of segments;

first score evaluation means for evaluating the scores assigned to said one or more candidate interpretations;

second score evaluation means for evaluating the scores assigned to said plurality of possible interpretations; and

normalized score producing means for producing a normalized score for each candidate interpretation using the evaluated score for said plurality of possible interpretations.

2. The system of claim 1, wherein said segment scoring means analyzes each image segment in said plurality of image segments and assigns a score to each possible classification of said image segment, wherein each said assigned score is associated with a particular symbol in said predetermined character set.

3. The system of claim 2, wherein said representation means represents a plurality of possible symbol sequences and a plurality of image consegmentations, wherein each said possible symbol sequence consists of a sequence of said symbols, and each said consegmentation consists of a sequence of said image segments.

4. The system of claim 3, wherein said consegmentation scoring means assigns scores to said plurality of image consegmentations based on the scores assigned to said image segments, and wherein said candidate symbol sequence identifying means identifies one or more candidate symbol sequences based on the scores assigned to said image segments.

5. The system of claim 4, wherein said symbol sequence scoring means assigns scores to said one or more candidate symbol sequences based on the scores assigned to said image segments, and wherein said first score evaluation means evaluates the scores assigned to said one or more candidate symbol sequences.

6. The system of claim 5, wherein said second score evaluation means evaluates the scores assigned to said plurality of possible symbol sequences, and said score normalizing means normalizes the scores assigned to each said candidate symbol sequence using the evaluated score for said plurality of possible symbol sequences.

7. The system of claim 6, wherein said representation means comprises a data structure representable by a graph comprising a two-dimensional array of nodes arranged in rows and columns and selectively connected by directed arcs, wherein each said column of nodes is indexed by one character position, and each said row of nodes is indexed by one said image segment in an order that corresponds to the spatial structure of said acquired image, and wherein each path extending through said nodes and along said directed arcs represents one said image consegmentation and one said possible symbol sequence, and substantially all of said image consegmentations and substantially all of said possible symbol sequences are represented by the set of paths extending through said graph.

8. The system of claim 7, wherein said each said node further comprises a set of recognition-arcs, and each said recognition-arc represents one said character and is associated with one said assigned score.

9. The system of claim 1, wherein said representation means implicitly represents said plurality of possible interpretations and said plurality of image consegmentations.

10. The system of claim 9, wherein said representation means comprises a data structure representable by a graph comprising a two-dimensional array of nodes arranged in rows and columns and selectively connected by directed arcs, wherein each said column of nodes is indexed by one symbol position, and each said row of nodes is indexed by one said segment in an order that substantially corresponds to the sequential structure of said input data set, and wherein each path extending through said nodes and along said directed arcs represents one said consegmentation and one said possible interpretation for said input expression, and substantially all of said consegmentations and substantially all of said possible interpretations are represented by the set of paths extending through said graph.

11. The system of claim 1, wherein said representation means comprises a data structure representable by a graph comprising a two-dimensional array of nodes arranged in rows and columns and selectively connected by directed arcs, wherein each said column of nodes is indexed by one symbol position, and each said row of nodes is indexed by one segment in an order that substantially corresponds to the sequential structure of said input data set, and wherein each path extending through said nodes and along said directed arcs represents one said consegmentation and one said possible interpretation for said input expression, and all of said consegmentations and all of said possible interpretations are represented by the set of paths extending through said graph.

12. A method for forming an interpretation of an input expression, where said input expression is expressed in a medium, said interpretation is a sequence of symbols, and each symbol being an element in a predetermined symbol set, said method comprising the steps:

(a) acquiring an input data set representative of said input expression, said input data set comprising a set of pixels associated with an acquired image of a graphically represented sequence of symbols;

(b) processing said input data set so as to form a set of image segments, each said image segment having specified boundaries and being classifiable as possibly representing any one or more of said plurality of symbols in said predetermined symbol set;

(c) forming a data structure that represents a set of consegmentations and a set of possible interpretations for said input expression, each said consegmentation consisiting of a set of said segments which collectively represent said input data set and being arranged in an order that substantially preserves the sequential structure of said input data set, each said possible interpretation for said input expression consisting of a possible symbol sequence, and each symbol in said possible symbol sequence being selected from said predetermined symbol set and occypying a symbol position in said possible symbol sequence, said data structure being graphically representable by a graph comprising a two-dimensional array of nodes arranged in rows and columns and selectively connected by directed arcs, each said column of nodes being indexable by one said symbol position, and each said row of nodes being indexable by one said image segment in an order that corresponds to the logical structure of said acquired input data set, and each path extending through said nodes and along said directed arcs representing one said consegmentation and one said possible interpretation for said input expression, and all of said consegmentations and all of said possible in interpretations for said input expression being represented by the set of paths extending through said graph;

(d) for each row of nodes in said graph, producing a set of scores for said predetermined symbol set represented by each node in said row, wherein the production of each said set of scores includes analyzing the segment indexing the row of nodes for which said set of scores is produced;

(e) implicitly or explicitly attributing a path score to paths through said graph; and

(f) analyzing the path scores attributed to the paths through said graph in step (e) in order to select one or more possible interpretations for said input expression.

13. The method of claim 12, wherein each said node further comprises a set of recognition-arcs, and each said recognition arc represents one said predetermined symbol and is associated with one said score produced during step (d).

14. The method of claim 13, wherein step (d) comprises using a plurality of adjustable parameters to produce said set of scores.

15. The method of claim 14, wherein an information processing means characterized by said plurality of adjustable parameters, is used during step (d) for analyzing each said segment and for producing said set of scores therefor.

16. The method of claim 13, wherein step (f) further comprises:

for at least said one possible interpretation for said input expression, computing a quantity corresponding to an a posteriori probability, wherein each said quantity is computed as the ratio of a numerator portion to a denominator portion,

wherein the numerator portion corresponds to the sum of path scores for substantially all the paths through the graph representing one said possible interpretation for said input expression, where each said path score corresponds to the product of scores associated with the recognition arcs along one said path, and wherein the denominator portion corresponds to the sum of path scores for substantially all paths through the graph representing substantially all of said possible interpretations for said input expression where each said path score corresponds to the product of scores associated with the recognition arcs along one said path.

17. The method of claim 16, which further comprises during step (f),

(1) determining the path through said graph having the highest path score,

(2) identifying the possible interpretation for said input expression which is represented by the path determined in substep (1),

(3) computing said quantity for said possible interpretation for said input expression identified in substep (2);

and

(4) providing as output, the quantity computed in substep (3) and indicia representative of the possible interpretation for said input expression identified in substep (2).

18. The method of claim 16, which further comprises during step (f),

(1) determining a set of paths through said graph having a high set of path scores,

(2) identifying the set of possible interpretations for said input expression which is represented by said set of paths determined in substep (1),

(3) computing a set of said quantities for said set of possible interpretations for said input expression, identified in substep (2);

(4) analyzing said set of quantities computed in substep (3) so as to determine which said possible interpretation for said input expression has a high-scoring a posteriori probability; and

(5) providing as output, the possible interpretation for said input expression identified in substep (2) and indicia representative of the high-scoring a posteriori probability determined in substep (4).

19. The method of claim 16, wherein each said a posteriori probability is computed as the ratio of a numerator portion to a denominator portion, and wherein step (f) further comprises,

(1) determining a set of paths through said graph having a high set of path scores,

(2) identifying the set of possible interpretations for said input expression which is represented by said set of paths determined in substep (1),

(3) computing a set of said quantities for said set of possible interpretations for said input expression, identified in substep (2);

and

(4) providing as output, the set of possible interpretations for said input expression, identified in substep (2), and the quantities computed in substep (3).

20. The method of claim 14, wherein during step (d), said set of adjustable parameters specify the relationship between said segment provided to said information processing means for analysis, and said set of scores produced from said information processing means.

21. The method of claim 20, which further comprises training said information processing means by

(1) processing a number of known sequences of symbols using said information processing means, and

(2) for each known sequence, incrementally adjusting said set of adjustable parameters so that the probability assigned to the correct interpretation increases on the average, and the probability assigned to incorrect interpretations decreases on the average.

22. The method of claim 21, wherein said information processing means comprises a neural information processing network.

23. The method of claim 12, wherein said input expression is expressed using printed or cursive writing techniques and graphically recorded on a recording medium.

24. A system for forming an interpretation of an input expression, where said input expression is expressed in a medium, said interpretation is a sequence of symbols, and each said symbol is an element in a predetermined symbol set, said system comprising:

data set acquisition means for acquiring input data set representative of said input expression;

data processing means for processing said acquired data set so as to produce a plurality of segments, each said segment having specificable boundaries and being classifiable as possibly representing any one of a plurality of symbols in a predetermined symbol set;

consegmentation specifying means for producing data specifying a set of consegmentations, each said segmentation consisting of a set of said segments collectively representing said acquired input data set and being arranged in an order that substantially preserves the sequential structure of said acquired input data set;

symbol sequence interpretation specifying means for producing data specifying a set of possible interpretations for said input expression, each said possible interpretation for said input expression consisting of a possible sequence of symbols and each said symbol in said possible sequence of symbols being selected from said predetermined symbol set and occupying a symbol position in said possible sequence of symbols;

data storing means for storing in a data structure, the produced data representative of each said consegmentation and each said possible interpretation for said input expression, wherein said data structure is graphically representable by a graph comprising a two-dimensional array of nodes arranged in rows and columns and selectively connected by directed arcs, and wherein each said column of nodes is indexable by one said symbol position and each said row of nodes is indexable by one said segment in an order that corresponds to the sequential structure of said acquired input data set, wherein each path extending through said nodes and along said directed arcs represents one said consegmentation and one said possible interpretation for said input expression, wherein said set of consegmentations and said set of possible interpretations for said input expression are represented by the set of paths extending through said graph;

segment analyzing means for analyzing the data in each said segment, and producing, for each row of nodes in said graph, a set of scores for said symbol set represented by each node in said row;

path score computing means for computing a path score for each said path through said graph; and

path score analyzing means for analyzing the computed path scores in order to select one or more said possible interpretations for said input expression.

25. The system of claim 24, wherein each said node further comprises a set of recognition-arcs, and each said recognition-arc represents one said known symbol and is associated with one said computed score.

26. The system of claim 25, wherein said path score analyzing means further comprises means for computing a quantity corresponding to an a posteriori probability for each said possible interpretation for said input expression.

27. The system of claim 26, wherein each said quantity is computed as the ratio of a numerator portion to a denominator portion,

wherein the numerator portion corresponds to the sum of path scores for substantially all paths through the graph representing one said possible interpretation for said input expression where each said path score corresponds to the product of scores associated with the recognition arcs along one said path, and

wherein the denominator portion corresponds to the sum of path scores for substantially all paths through the graph representing substantially all of said possible interpretations for said input expression, where each said path score corresponds to the product of scores associated with the recognition arcs along one said path.

28. The system of claim 24, which further comprises

means for determining the path through said graph having the highest path score,

means for identifying the possible interpretation for said input expression which is represented by said determined path having the highest path score,

means for computing said quantity for each said possible interpretation for said input expression;

and

means for providing as output, indicia representing said computed quantity and said possible interpretation for said input expression.

29. The system of claim 28, wherein said path score analyzing means further comprises

means for determining a set of paths through said graph having the highest set of path scores,

means for identifying the set of possible interpretations for said input expression which is represented by said determined set of paths,

means for computing a set of said quantities for said identified set of possible interpretations for said input expression,

means for analyzing said computed set of quantities and determining which said possible interpretation for said input expression has the highest a posteriori probability of said highest set of path scores;

and

means for providing as output, indicia representing said possible interpretation for said input expression having the highest a posteriori probability, and said determined highest a posteriori probability.

30. The system of claim 26, wherein said segment analyzing means comprises a set of adjustable parameters which specify the relationship between said segment provided for analysis and said set of scores produced from said segment analysis means.

31. The system of claim 30, which further comprises

system training means for training said system using a plurality of training data sets, each said training data set including an acquired data set of an input expression and a known-to-be correct interpretation for said input expression, said system training means further including parameter adjustment means for incrementally adjusting said set of adjustable parameters so that the average probability measure for said known-to-be correct interpretation increases, and the average probability measure for said set of known-to-be incorrect interpretations decreases.

32. The system of claim 26, wherein said input expression is graphically recorded on a recording medium.

33. The method of claim 32, wherein said input expression is expressed using printed or cursive writing techniques.

34. A system for forming an interpretation of an input expression, where said input expression is expressed in a medium, said interpretation is a sequence of symbols, and each said symbol is an element in a predetermined symbol set, said system comprising:

image acquisition means for acquiring an image of said input expression;

image processing means for processing said image so as to form a set of image segments, each said image segment being a sub-image of said acquired image;

image consegmentation specifying means for producing data specifying a set of image consegmentations, each said image consegmentation consisting of a set of said image segments collectively representing said acquired image and being arranged in an order that substantially preserves the spatial structure of said acquired image;

symbol sequence interpretation specifying means for producing data specifying a set of possible interpretations for said input expression, each said possible interpretation for said input expression consisting of a sequence of symbols, each said symbol in said sequence of symbol being selected from said predetermined symbol set and occupying a symbol position in said sequence of symbols;

data storage means for storing in a data structure, the produced data representative of each said image consegmentation and each said possible interpretation for said input expression, wherein said data structure is graphically representable by a directed acyclic graph comprising a two-dimensional array of nodes arranged in rows and columns and selectively connected by directed arcs, and wherein each said column of nodes is indexable by one said symbol position, and each said row of nodes is indexable by one said image segment in an order that corresponds to the spatial structure of said acquired image, and wherein each path extending through said nodes and along said directed arcs represents one said image consegmentation and one said possible interpretation for said input expression, and all of said image consegmentations and all of said possible interpretations for said input expression are represented by the set of paths extending through said graph;

image segment analyzing means for analyzing each said image segment, and producing, for each row of nodes in said graph, a set of scores for said predetermined symbol set represented by each node in said row;

path score computing means for computing a path score for each said path through said graph; and

path score analyzing means for analyzing the computed path scores in order to select one or more of said possible interpretations for said input expression.

35. The system of claim 34, wherein said input expression is graphically recorded on an electrically-passive medium.

36. The system of claim 34, wherein said input expression is graphically recorded on an electrically-active medium.

37. The method of claim 34, wherein said input expression is written using printed or cursive writing techniques.