Automatic training of character templates using a transcription and a two-dimensional image source model

• US 5,689,620 A
• Filed: 04/28/1995
• Issued: 11/18/1997
• Est. Priority Date: 04/28/1995
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Kopec, Gary E., Chou, Philip Andrew, Niles, Leslie T.
• Primary Examiner(s): Davis, George B.
• Application Number:
  US08/431,223
• Time in Patent Office: 935 Days
• Field of Search: 395/20, 395/23, 382/157, 382/187
• US Class Current: 706/12
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting

Abstract

A technique for automatically training a set of character templates using unsegmented training samples uses as input a two-dimensional (2D) image of characters, called glyphs, as the source of training samples, a transcription associated with the 2D image as a source of labels for the glyph samples, and an explicit, formal 2D image source model that models as a grammar the structural and functional features of a set of 2D images that may be used as the source of training data. The input transcription may be a literal transcription associated with the 2D input image, or it may be nonliteral, for example containing logical structure tags for document formatting, such as found in markup languages. The technique uses spatial positioning information about the 2D image modeled by the 2D image source model and uses labels in the transcription to determine labeled glyph positions in the 2D image that identify locations of glyph samples. The character templates are produced using the input 2D image and the labeled glyph positions without assigning pixels to glyph samples prior to training. In one implementation, the 2D image source model is a regular grammar having the form of a finite state transition network, and the transcription is also represented as a finite state network. The two networks are merged to produce a transcription-image network, which is used to decode the input 2D image to produce labeled glyph positions that identify training data samples in the 2D image. In one implementation of the template construction process, a pixel scoring technique is used to produce character templates contemporaneously from blocks of training data samples aligned at glyph positions.

Claims

1. A method of operating a machine to train a set of character templates for use in a recognition system;

the machine including a processor and a memory device for storing data;

the data stored in the memory device including instruction data which the processor executes to operate the machine;

the processor being connected to the memory device for accessing and executing the instruction data stored therein;

the method comprising;

operating the processor to receive a two-dimensional (2D) image source of glyph samples having a vertical dimension size larger than a single line;

each glyph sample being an image instance of a respective one of a plurality of characters in a character set;

the set of character templates being trained representing respective ones of the plurality of characters in the character set;

operating the processor to receive a transcription network in the form of a finite state network data structure indicating a transcription associated with the 2D image source of glyph samples;

the transcription including an ordered arrangement of transcription labels;

the transcription network indicating the ordered arrangement of the transcription labels in the transcription as at least one transcription path through the transcription network;

operating the processor to access a two-dimensional (2D) image source network in the form of a stochastic finite state network data structure, stored in the memory device of the machine;

the 2D image source network modeling as a grammar a spatial image structure of a set of 2D images, each including a plurality of glyphs;

a first one of the set of 2D images being modeled as at least one path through the 2D image source network that indicates an ideal image consistent with the spatial image structure of the first image;

the at least one path indicating path data items associated therewith and accessible by the processor;

the path data items indicating image positions and glyph labels paired therewith of respective ones of the plurality of glyphs included in the first image;

the 2D image source of glyph samples being one of the images included in the set of 2D images modeled by the 2D image source network;

operating the processor to merge the 2D image source network with the transcription network to produce a transcription-image network;

the transcription-image network being a modified form of the 2D image source network wherein, when the transcription is associated with the first image, the transcription-image network models the first image as at least one complete transcription-image path through the transcription-image network that indicates an ideal image consistent with the spatial image structure of the first image and that further indicates the path data items, the transcription-image path further indicating a sequence of message strings consistent with the ordered arrangement of the transcription labels indicated by the at least one transcription path through the transcription network;

operating the processor to perform a decoding operation on the 2D image source of glyph samples using the transcription-image network to produce at least one complete transcription-image path indicating an ideal image consistent with the spatial image structure of the 2D image source of glyph samples;

operating the processor to produce training samples using the path data items associated with the at least one complete transcription-image path;

each training sample including a 2D image position in the 2D image source of glyph samples indicating an image position therein and a glyph label paired therewith; and

operating the processor to produce the set of character templates using the training samples.

2. The method of claim 1 of operating a machine to train a set of character templates wherein each of the character templates is based on a character template model defining character image positioning of first and second adjacent character images in an image, referred to as a sidebearing model of character image positioning, wherein a template image origin position of the second character image is displaced in the image by a character set width from a template image origin position of the first character image adjacent to and preceding the second character image;

the sidebearing model of character image positioning requiring that, when a first rectangular bounding box drawn to contain the first character image overlaps with a second rectangular bounding box drawn to contain the second character image, the first and 4 second character images have substantially nonoverlapping foreground pixels; and

wherein the step of operating the processor to produce the set of character templates further includes determining, for each character template, a character set width thereof using the training samples.

3. The method of claim 1 of operating a machine to train a set of character templates wherein each of the character templates is based on a character template model defining character image positioning of first and second adjacent character images in an image, referred to as a segmentation-based model of character image positioning, wherein each of the first and second adjacent character images is capable of being entirely contained in a rectangular bounding box and a first rectangular bounding box drawn to contain the first character image does not substantially overlap with a second rectangular bounding box drawn to contain the second character image.

4. The method of claim 1 of operating a machine to train a set of character templates wherein

the transcription data structure associated with the 2D image source of glyph samples includes at least one pair of transcription labels indicating at least first and second alternate message strings for a single image portion of the 2D image source of glyph samples;

the transcription network models the transcription data structure as a series of transcription nodes and a sequence of transitions between pairs of the transcription nodes;

each transition having a transcription label associated therewith; and

the transcription network models the at least one pair of transcription labels indicating the at least first and second alternate message strings as at least first and second alternate sequences of transitions between one of the pairs of the transcription nodes;

each one of the at least first and second alternate sequences of transitions having one of the at least first and second alternate message strings associated therewith.

5. The method of claim 1 of operating a machine to train a set of character templates wherein

the transcription network indicates a tag transcription including at least one nonliteral transcription label, hereafter referred to as a tag, indicating at least one character code representing a character with which a respective glyph in the 2D image source of glyph samples cannot be paired by visual inspection thereof;

the at least one character code indicated by the tag indicating markup information about the 2D image source of glyph samples;

the markup information, when interpreted by a document processing operation, capable of producing at least one display feature included in the 2D image source of glyph samples perceptible as a visual formatting characteristic of the 2D image source of glyph samples; and

the processor, in merging the 2D image source network with the transcription network, designates the transcription labels included in the transcription network as message strings included in the transcription-image network;

the tag being designated as a message string in the transcription-image network such that the transcription-image network models a relationship between the tag and at least one glyph occurring in the 2D image of glyph samples.

6. The method of claim 1 of operating a machine to train a set of character templates wherein

the at least one complete transcription-image path through the transcription-image network is defined by a sequence of transitions between nodes included in the transcription-image network;

the path data items associated with the at least one complete transcription-image path are associated with each transition;

the path data items including a message string, a character template and an image displacement; and

the processor determines, for respective transitions indicated by the complete transcription-image path having non-null character templates associated therewith, the image positions of respective ones of the plurality of glyphs included in the 2D image source of glyph samples by using the image displacements associated with the respective transitions;

the processor further determining the glyph label paired with each respective image origin position using a character label indicated by the non-null character template associated with the respective transition;

the character label indicating a character in the character set.

7. The method of claim 1 wherein

the decoding operation performed on the 2D image source of glyph samples uses a plurality of initial character templates to produce the at least one complete transcription-image path indicating the ideal image.

8. The method of claim 7 further including, after producing the set of character templates using the 2D image source of glyph samples and the training samples occurring therein, performing at least one additional iteration of the steps of performing the decoding operation, producing the training samples, and producing the set of character templates;

the at least one additional iteration of the decoding operation using the set of character templates produced in a prior iteration as the plurality of initial character templates.

9. The method of claim 7 wherein the plurality of initial character templates used by the decoding operation to produce the at least one complete transcription-image path initially has arbitrary pixel content.

10. The method of claim 1 wherein operating the processor to perform a decoding operation on the 2D image source of glyph samples to produce the at least one complete transcription-image path indicating the ideal image includes

performing a dynamic programming operation to compute an optimum score at each of a plurality of lattice nodes in a decoding lattice data structure representing the transcription-image network;

the dynamic programming operation producing and storing an optimizing transition identification data item for each lattice node in the decoding lattice;

the optimizing transition identification data item being produced as a result of computing the optimum score and indicating one of a plurality of possible transitions into a respective one of the lattice nodes that optimizes the score for the respective lattice node; and

performing a backtracing operation to retrieve a sequence of transitions indicating a decoding lattice path;

the backtracing operation starting with a final lattice node and ending with a first lattice node in the decoding lattice path;

the sequence of transitions being retrieved using the optimizing transition identification data item produced for each lattice node as a result of computing the optimum scores;

the decoding lattice path indicating the at least one complete transcription-image path through the transcription-image network.

11. The method of claim 1 wherein operating the processor to perform the decoding operation on the 2D image source of glyph samples to produce the at least one complete transcription-image path indicating the ideal image includes

producing a plurality of complete transcription-image paths through the transcription-image network;

each complete transcription-image path indicating a target 2D ideal image; and

selecting one of the plurality of complete transcription-image paths as a best complete transcription-image path by determining a best-matched target 2D ideal image, from the plurality of target 2D ideal images, that matches the 2D image source of glyph samples according to a matching criterion.

12. The method of claim 11 wherein the matching criterion is an optimized value for a target image pixel match measurement data item computed for each target 2D ideal image by comparing pixel color values indicated by image pixels defining the 2D image source of glyph samples with pixel color values of respectively paired image pixels defining the target 2D ideal image.

13. A method of operating a machine to train a set of character templates for use in a recognition system;

the machine including a processor and a memory device for storing data;

the data stored in the memory device including instruction data which the processor executes to operate the machine;

the processor being connected to the memory device for accessing and executing the instruction data stored therein;

the method comprising;

operating the processor to determine glyph sample pixel positions identifying respective ones of glyph samples occurring in a two-dimensional (2D) image source of glyph samples having a vertical dimension size larger than a single line of glyphs;

each glyph sample included in the 2D image source of glyph samples being an image instance of a respective one of a plurality of characters in a character set;

each one of the set of character templates being trained representing a respective one of the plurality of characters in the character set;

the processor, in determining the glyph sample pixel position of each glyph sample, using a two-dimensional (2D) image source model that models as a grammar a spatial image structure of a set of images that includes the 2D image source of glyph samples;

the 2D image source model including spatial positioning data modeling spatial positioning of the plurality of glyphs occurring in the 2D image source of glyph samples;

the processor using the spatial positioning data to determine the glyph sample pixel position identifying a respective glyph sample;

operating the processor to produce a glyph label to be respectively paired with the glyph sample pixel position of a respective glyph sample;

the respectively paired glyph label indicating a respective one of the characters in the character set;

the processor, in producing the respectively paired glyph label, using mapping data included in the 2D image source model mapping a respective one of the glyphs to a glyph label indicating the character in the character set;

the processor, further in producing the respectively paired glyph label, using a transcription associated with the 2D image source of glyph samples and including an ordered arrangement of transcription labels; and

operating the processor to produce the set of character templates indicating respective ones of the characters in the character set using the glyph sample pixel positions identifying the glyph samples occurring in the 2D image source of glyph samples with their respectively paired glyph labels.

14. The method of claim 13 of operating the machine to train character templates wherein

each character template in the set of character templates is based on a character template model having a characteristic image positioning property such that when a first rectangular bounding box entirely contains a first character image, and a second rectangular bounding box entirely contains a second character image adjacent to the first character image, the first rectangular bounding box does not substantially overlap with the second rectangular bounding box;

and

the step of operating the processor to determine the glyph sample pixel position of each glyph sample occurring in the 2D image source of glyph samples includes determining image coordinates of a respective glyph sample bounding box in the 2D image source of glyph samples that entirely defines image dimensions of a respective one of the glyph samples occurring therein.

15. The method of claim 14 wherein the step of operating the processor to produce the set of character templates includes using the image coordinates in the 2D image source of glyph samples of the respective glyph sample bounding box to define the image dimensions of each glyph sample.

16. The method of claim 14 wherein

the step of operating the processor to determine the glyph sample pixel position of each glyph sample further includes producing an image definition data structure for each glyph sample defining an isolated glyph sample using the image coordinates of the glyph sample bounding box of the glyph sample;

and

the step of operating the processor to produce the set of character templates includes assigning a foreground pixel color value to selected ones of a plurality of template pixel positions included in respective ones of the character templates using pixel color values included in the image definition data structures defining the isolated glyph samples.

17. The method of claim 13 of operating the machine to train character templates wherein

each character template in the set of character templates is based on a character template model having a characteristic image positioning property such that, when a second character template is positioned in an image with a template image origin position thereof displaced from a template image origin position of a preceding first character template by a character set width thereof, and when a first bounding box entirely containing the first character template overlaps in the image with a second bounding box entirely containing the second character template, the first and second character templates have substantially nonoverlapping foreground pixels;

the glyph sample pixel position of each glyph sample occurring in the 2D image source of glyph samples is a single 2D image position in the 2D image source of glyph samples indicating an image origin position of the glyph sample; and

the step of operating the processor to produce the set of character templates includes

determining sample image regions in the 2D image source of glyph samples;

each sample image region including a plurality of image pixel positions in the 2D image source of glyph samples, referred to as sample pixel positions;

a first one of the sample pixel positions being the image origin position of a first glyph sample;

each sample image region further being large enough such that a second one of the sample pixel positions is the image origin position of a second glyph sample; and

assigning pixel color values to template pixel positions included in respective ones of the character templates using pixel color values indicated by the sample pixel positions included in the sample image regions on the basis of template pixel assignment criteria that determine which sample pixel positions in which sample image regions are used to determine a pixel color value for a template pixel position such that all character templates observe the characteristic imaging property of the template model.

18. The method of claim 13 wherein the step of operating the processor to produce the set of character templates includes

producing, for each respective character template, a template image region for storing the respective character template;

the template image region having a pixel position designated as a template origin pixel position;

determining, for each glyph sample pixel position having a respectively paired glyph label identifying the character indicated by the respective character template, a sample image region in the 2D image source of glyph samples including a two-dimensional (2D) array of image pixel positions, referred to as sample pixel positions and including the glyph sample pixel position;

each glyph sample pixel position identifying a glyph sample being positioned at the same relative location in a respective sample image region such that the sample pixel positions in one of the sample image regions are effectively aligned with the sample pixel positions in other sample image regions identified for the respective character template;

the sample image regions being referred to as aligned sample image regions, and the sample pixel positions being referred to as respectively paired sample pixel positions; and

assigning pixel color values to sequentially selected template pixel positions in respective ones of the template image regions in a template assignment order using the aligned sample image regions;

the pixel color values being determined on the basis of template contribution measurements computed using respectively paired sample pixel positions included in the aligned sample image regions;

the template assignment order being determined on the basis of information about a previously-assigned template pixel position.

19. The method of claim 18 wherein the step of assigning pixel color values to sequentially selected template pixel positions further includes

(a) computing the template contribution measurement for each template pixel position using each respectively paired sample pixel position included in the aligned sample image regions;

(b) selecting the template pixel position having the highest positive template contribution measurement as a selected template pixel position;

(c) assigning a foreground pixel color value to the selected template pixel;

(d) modifying each respectively paired sample pixel position paired with the selected template pixel position to indicate a background pixel color value; and

(e) repeating steps (a) through (d) while at least one of the template contribution measurements being computed is positive.

20. The method of claim 13 of operating the machine to train character templates wherein the transcription associated with the 2D image source of glyph samples is produced as an output data structure of a computer-implemented character recognition system.

21. The method of claim 13 of operating the machine to train character templates wherein the machine further includes a user input device connected to input circuitry for providing signals indicating input data from a user of the processor-controlled machine;

the processor being further connected to the input circuitry for receiving the input data from the user; and

wherein the ordered arrangement of transcription labels included in the transcription associated with the 2D image source of glyph samples is produced by the user using the user input device.

22. The method of claim 13 of operating the machine to train character templates wherein the 2D image source of glyph samples is produced as an output of a scanning operation performed on a physical document.

23. The method of claim 13 of operating the machine to train character templates wherein the transcription associated with the 2D image source of glyph samples is a literal transcription;

each transcription label in the ordered arrangement of transcription labels in the transcription indicating a character code representing a character in the character set and being capable of being paired by visual inspection with a single glyph in the 2D image source of glyph samples representative the character in the glyph sample character set indicated by the character code; and

wherein the processor, in producing the glyph label paired with the glyph sample, uses the spatial positioning information about the glyph sample to identify as the glyph label the transcription label in the transcription that is visually paired with the glyph sample.

24. The method of claim 14 of operating the machine to train character templates wherein the transcription associated with the 2D image source of glyph samples is a nonliteral transcription including at least one nonliteral transcription label indicating a character code representing a character selected from the group consisting of (a) a character in a second character set different from the character set of the templates being trained;

and (b) a character with which a glyph in the 2D image source of glyph samples cannot be paired by visual inspection thereof; and

wherein the processor, in producing the glyph label, uses the spatial positioning information about the glyph sample to identify the at least one glyph sample related to the at least one nonliteral transcription label in the transcription and maps the character code indicated by the at least one nonliteral transcription label to a character code indicating a character in the character set to produce the glyph label paired with a glyph sample.

25. The method of claim 13 of operating the machine to train a set of character templates wherein the transcription associated with the 2D image source of glyph samples is a tag transcription including at least one nonliteral transcription label, hereafter referred to as a tag, indicating at least one character code representing a character with which a respective glyph in the 2D image source of glyph samples cannot be paired by visual inspection thereof;

the at least one character code indicated by the tag indicating markup information about the 2D image source of glyph samples;

the markup information, when interpreted by a document processing operation, producing at least one display feature included in the 2D image source of glyph samples perceptible as a visual formatting characteristic of the 2D image source of glyph samples; and

wherein the processor, in producing the glyph label using the transcription and the mapping data, uses the spatial positioning information about the plurality of glyph samples occurring in the 2D image source of glyph samples to identify at least one glyph sample related to the tag, and uses the tag to pair a glyph label with the glyph sample.

26. A method of operating a machine to train a set of character templates for use in a recognition system;

each of the character templates being based on a character template model defining character image positioning referred to as the sidebearing model of character image positioning;

the machine including a processor and a memory device for storing data;

the data stored in the memory device including instruction data which the processor executes to operate the machine;

the processor being connected to the memory device for accessing and executing the instruction data stored therein;

the method comprising;

operating the processor to receive a two-dimensional (2D) image source of glyph samples;

the 2D image source of glyph samples having a vertical dimension size larger than a single line;

each glyph occurring in the 2D image source of glyph samples being an image instance of a respective one of a plurality of characters in a character set;

each one of the set of character templates being trained representing a respective one of the plurality of characters in the character set;

operating the processor to access a two-dimensional (2D) image source model stored in the memory device of the machine;

the 2D image source model modeling as a grammar a set of two-dimensional (2D) images having a common spatial image structure;

the 2D image source of glyph samples being one of the set of 2D images modeled by the 2D image source model;

the 2D image source model including spatial positioning data modeling spatial positioning of the plurality of glyphs occurring in the 2D image source of glyph samples;

operating the processor to determine, for each respective glyph occurring in the 2D image source of glyph samples, a glyph sample image origin position of the respective glyph therein using the spatial positioning data included in the 2D image source model;

operating the processor to produce a glyph label respectively paired with each glyph sample image origin position;

each respectively paired glyph label indicating the character in the character set represented by the respective glyph;

the processor, in producing each respectively paired glyph label, using mapping data included in the 2D image source model mapping respective ones of the glyphs occurring in the 2D image source of glyph samples to respectively paired glyph labels, each indicating the character in the character set represented by the respective glyph;

the processor, further in producing each respectively paired glyph label, using a transcription associated with the 2D image source of glyph samples the transcription including an ordered arrangement of transcription labels;

the processor using the transcription labels and the mapping data to pair a glyph label with a respective glyph sample image origin position of a respective glyph occurring in the 2D image source of glyph samples; and

p1 operating the processor to produce the set of character templates indicating the characters in the character set using the 2D image source of glyph samples, the glyph sample image origin positions and the respectively paired glyph labels;

the processor determining, for each character template, a collection of sample image regions included in the 2D image source of glyph samples using the glyph sample image origin positions and the respectively paired glyph labels;

the process producing the set of character templates using the collections of sample image regions by assigning foreground pixel color values to selected template pixel positions in respective ones of the character templates;

one of the selected template pixel positions in a first one of the set of character templates being selected on the basis of template contribution measurements computed using sample pixel positions included in the collection of sample image regions for the character represented by the first character template;

each character template having a characteristic image positioning property such that, when a second character template is positioned in an image with an image origin position thereof displaced from the image origin position of a preceding first character template by a character set width thereof, and when a fast bounding box entirely containing the first character template overlaps in the image with a second bounding box entirely containing the second character template, the first and second character templates have substantially nonoverlapping foreground pixels.

27. The method of claim 26 of operating the machine to train character templates wherein

the transcription associated with the 2D image source of glyph samples is a tag transcription including at least one nonliteral transcription label, hereafter referred to as a tag, indicating at least one character code representing a character with which a respective glyph in the 2D image source of glyph samples cannot be paired by visual inspection thereof;

the at least one character code indicated by the tag indicating markup information about the 2D image source of glyph samples;

the markup information, when interpreted by a document processing operation, producing at least one display feature included in the 2D image source of glyph samples perceptible as a visual formatting characteristic of the 2D image source of glyph samples; and

the processor, in producing the respectively paired glyph labels using the transcription and the mapping data, uses the spatial positioning information about the glyphs occurring in the 2D image source of glyph samples to identify at least one glyph sample image origin position related to the tag, and uses the tag in producing a respectively paired glyph label.

28. A machine for use in training a set of character templates for use in a recognition operation;

the machine comprising;

a first signal source for providing image data defining a fast image;

image input circuitry connected to the first signal source for receiving the image data defining the first image therefrom;

a second signal source for providing non-image data;

input circuitry connected to the second signal source for receiving the non-image data therefrom;

a processor connected to the image input circuitry for receiving the image data defining the first image therefrom and further connected to the input circuitry for receiving the non-image data therefrom; and

memory for storing data;

the data stored in the memory including instruction data indicating instructions the processor can execute;

the processor being further connected to the memory for accessing the data stored therein;

wherein the processor, in executing the instructions stored in the memory, receives from the image input circuitry a

two-dimensional (2D) image source of glyph samples;

the 2D image source of glyph samples having a vertical dimension size larger than a single line of glyphs;

each glyph included in the 2D image source of glyph samples being an image instance of a respective one of a plurality of characters in a character set;

the set of character templates being trained representing respective ones of the plurality of characters in the character set;

receives from the input circuitry a transcription associated with the 2D image source of glyph samples including an ordered arrangement of transcription labels; and

receives from the input circuitry a two-dimensional (2D) image source model modeling as a grammar a spatial image structure of a set of 2D images including the 2D image source of glyph samples;

the 2D image source model including spatial positioning data indicating spatial positioning information about the plurality of glyphs occurring in the 2D image source of glyph samples;

the 2D image source model indicating mapping data mapping a respective one of the glyphs occurring in the 2D image source of glyph samples to a glyph label indicating a character in the character set;

wherein the processor, further in executing the instructions stored in the memory,

determines a glyph sample pixel position of each of a plurality of glyph samples occurring in the 2D image source of glyph samples using the spatial positioning information included in the 2D image source model;

produces a glyph label respectively paired with each respective one of the glyph sample pixel positions and indicating a respective one of the characters in the character set;

the processor producing the respectively paired glyph label using the mapping data indicated by the 2D image source model and using the ordered arrangement of transcription labels included in the transcription; and

produces the set of character templates using the 2D image source of glyph samples and using the glyph sample pixel positions and the respectively paired glyph labels.

29. The machine for use in training a set of character templates of claim 28 wherein the first signal source for providing the first image is a scanning device;

the image input circuitry connected for receiving the fast image from the first signal source is scanning circuitry capable of receiving an image by a scanning operation performed on a physical document showing marks indicating the image;

the processor receiving the 2D image source of glyph samples from the scanning circuitry.

30. The machine for use in training a set of character templates of claim 28 wherein

the second signal source includes a user input device for receiving signals indicating data from a user of the machine;

the input circuitry being connected for receiving the signals from the user input device; and

the processor receives the transcription associated with the 2D image source of glyph samples from the input circuitry connected for receiving the signals from the user input device.

31. The machine of claim 28 wherein

the 2D image source model is represented as a stochastic finite state network data structure, referred to as a 2D image source network, indicating a regular grammar and representing the mapping data mapping a respective one of the glyph sample pixel positions in the 2D source of glyph samples to a glyph label as a path through the 2D image source network;

the path indicating path data items associated therewith and accessible by the processor;

the path data items indicating image origin positions and respectively paired glyph label of respective ones of the plurality of glyphs included in the 2D image source of glyph samples;

the transcription data structure associated with the 2D image source of glyph samples is represented as a finite state network data structure, referred to as a transcription network, modeling a transcription as a transcription path through the transcription network indicating the ordered arrangement of transcription labels in the transcription; and

the processor, in executing the instructions for determining the plurality of glyph sample pixel positions of glyph samples occurring in the 2D image source of glyph samples and for producing respectively paired glyph labels,

merging the 2D image source network with the transcription network to produce a transcription-image network indicating modified mapping data mapping a respective one of the transcription labels included in the transcription to a glyph sample pixel position of a respective one of the glyphs occurring in the 2D image source of glyph samples;

the modified mapping data being represented as at least one complete transcription-image path through the transcription-image network;

the at least one complete transcription-image path indicating the path data items;

performing a decoding operation on the 2D image source of glyph samples using the transcription-image network to produce the at least one complete transcription-image path through the transcription-image network; and

obtaining the glyph sample pixel position of each glyph sample and the glyph label paired therewith using the path data items indicated by the at least one complete transcription-image path.

32. The machine for use in training a set of character templates of claim 28 wherein

the transcription associated with the 2D image source of glyph samples is a tag transcription including at least one nonliteral transcription label, hereafter referred to as a tag, indicating at least one character code representing a character with which a respective glyph in the 2D image source of glyph samples cannot be paired by visual inspection thereof;

the at least one character code indicated by the tag indicating markup information about the 2D image source of glyph samples;

the markup information, when interpreted by a document processing operation, producing at least one display feature included in the 2D image source of glyph samples perceptible as a visual formatting characteristic of the 2D image source of glyph samples; and

the processor, in executing the instructions for producing the respectively paired glyph label, uses the spatial positioning information about the glyph samples to identify at least one glyph sample related to the tag; and

uses the tag in producing a respectively paired glyph label.