Method of producing character templates using unsegmented samples

• US 5,706,364 A
• Filed: 04/28/1995
• Issued: 01/06/1998
• 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
• Primary Examiner(s): Mancuso, Joseph
• Application Number:
  US08/431,714
• Time in Patent Office: 984 Days
• Field of Search: 382/155, 382/156, 382/157, 382/159, 382/160, 382/161, 382/209, 382/216, 382/294, 382/295, 395/20, 395/21, 395/23
• US Class Current: 382/159
• CPC Class Codes: G06F 18/28 Determining representative reference patterns, e.g. by averaging or distorting; Generating dictionaries

Abstract

A method for producing, or training, a set of character templates uses as the source of training samples an image source of character images, called glyphs, that are not previously segmented or isolated for training. Also used is a labeled glyph position data structure that includes, for each glyph in the image source, a glyph image position in the image source associating an image location of the glyph with a character label paired with the glyph image position that indicates the character in the character set being trained. The labeled glyph position data is used to identify a collection of glyph sample image regions in the image source for each character in the character set; each glyph sample image region is large enough to contain a glyph and typically contains adjacent glyphs for other characters. The invention mathematically characterizes the template construction problem using unsegmented samples as an optimization problem that optimizes a function that represents the set of character templates being trained as an ideal image to be reconstructed to match the input image. The method produces all of the character templates contemporaneously by using a novel pixel scoring technique that implements an approximation of a maximum likelihood criterion subject to a constraint on the templates produced which holds that foreground pixels in adjacently positioned character images have substantially nonoverlapping foreground pixels. The character templates produced may be binary templates or arrays of pixel color probability values, and may also have substantially disjoint supports, such that adjacently imaged templates have substantially no overlapping foreground pixels.

Claims

1. A method of operating a machine to train a set of character templates;

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

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

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

the method comprising;

operating the processor to receive and store, in the memory device of the machine, an image definition data structure including a plurality of image pixel positions defining an image;

the image definition data structure, hereafter referred to as an image glyph source, including a plurality of glyphs occurring therein;

each glyph 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 and store, in the memory device of the machine, a plurality of labeled glyph position data items;

each labeled glyph position data item indicating one of the plurality of image pixel positions in the image glyph source as an image glyph source location of a glyph occurring therein;

each labeled glyph position data item further indicating a glyph label, hereafter referred to as a respectively paired glyph label, paired with the image pixel position identifying the glyph indicated by the image pixel position as a respective one of the plurality of characters in the character set;

operating the processor to determine a sample image region included in the image glyph source for each labeled glyph position data item;

the sample image region including the image pixel position indicating the image glyph source location of a glyph and being identified as a training data sample for the character template indicated by the respectively paired glyph label;

each sample image region including a plurality of image pixel positions in the image glyph source, hereafter referred to as sample pixel positions, each indicating a sample pixel value;

operating the processor to produce, for each respective character template to be trained, a template image region including a plurality of template pixel positions for storing the respective character template; and

operating the processor to produce the set of character templates using the template image regions and the sample image regions;

producing the set of character templates including

(a) computing template pixel scores for respective ones of the template pixel positions in the template image regions using the sample pixel values indicated by the sample pixel positions included in the sample image regions;

(b) assigning a foreground pixel value to a template pixel position, referred to as an assigned template pixel position, in one of the template image regions;

the assigned template pixel position being selected on the basis of the template pixel scores;

(c) modifying the sample pixel values of the sample pixel positions used in computing the template pixel score for the assigned template pixel position to indicate modified sample pixel values that, when used in computing a subsequent template pixel score for an unassigned template pixel position, reduce the chance that a foreground pixel value will be assigned to the unassigned template pixel position on the basis of the subsequent template pixel score; and

(d) repeating substeps (a), (b) and (c) until a stopping condition indicates that the set of character templates is complete.

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

the template pixel scores computed for respective ones of the template pixel positions in the template image regions are computed for template pixel positions included in at least first and second template image regions;

and

when a first assigned template pixel position is included in the first template image region, a foreground pixel value may be assigned to an unassigned template pixel position in the second template image region on the basis of the template pixel score computed for the unassigned template pixel position before all template pixel positions included in the first template image region have been assigned, such that the first and second character templates in the set of character templates are produced substantially contemporaneously with each other.

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

each character template stored in a respective template image region has a foreground probability parameter associated therewith indicating a probability value that the foreground pixel values indicated by the template pixel positions in the template image region are valid foreground pixel values;

and

the substep (a) of computing the template pixel scores for respective ones of the template pixel positions in the template image regions further includes computing the template pixel scores for a respective one of the template image regions using the probability value associated with the respective template image region.

4. The method of operating a machine to train a set of character templates of claim 3 wherein each character template stored in a respective template image region further has a background probability parameter associated therewith indicating a probability value that the background pixel values indicated by the template pixel positions in the template image region are valid background pixel values;

and wherein the template pixel scores computed for template pixel positions in a respective one of the template image regions are computed using a threshold data item indicating a threshold value that represents a relationship between the foreground probability parameter and the background probability parameter associated with the respective character template stored in the respective template image region.

5. The method of operating a machine to train a set of character templates of claim 3 wherein the foreground probability parameter associated with each character template in the set of character templates indicates an identical probability value associated with each character template.

6. The method of operating a machine to train a set of character templates of claim 3 wherein the foreground probability parameter associated with each character template indicates a probability value that varies by character template in the set of character templates.

7. The method of operating a machine to train a set of character templates of claim 3 wherein the probability value indicated by the foreground probability parameter associated with each character template is related to a model of the image glyph source that models image noise present in the image glyph source resulting from an operation used to produce the image glyph source.

8. The method of operating a machine to train a set of character templates of claim 3

wherein at least one character template in the set of character templates being trained represents a character that, when imaged on a marking medium, is perceived as having white foreground pixels imaged against black background pixels, referred to as a reverse video character;

the at least one character template representing the reverse video character being referred to as a reverse video character template;

the template image region storing the reverse video character template being referred to as a reverse video template image region;

wherein the white foreground pixels of the reverse video character are stored as black foreground pixels in a reverse video template image region representing the reverse video character, and the black background pixels of the reverse video character are stored as white background pixels in the reverse video template image region; and

wherein the foreground probability parameter associated with the reverse video character template indicates a low probability value indicating that the black foreground pixel values indicated by the template pixel positions in the reverse video template image region are less likely to be valid black foreground pixel values, such that an operation using the reverse video character template interprets the black foreground pixel values as white foreground pixels.

9. The method of operating a machine to train a set of character templates of claim 8

wherein each reverse video character template further has a background probability parameter associated therewith indicating a probability value that the background pixel values indicated by the template pixel positions in the reverse video template image region are valid background pixel values;

and

wherein the template pixel scores computed for template pixel positions in a respective one of the reverse video template image regions are computed using a threshold data item indicating a threshold value that represents a relationship between the foreground probability parameter and the background probability parameter associated with the respective reverse video character template.

10. The method of operating a machine to train a set of character templates of claim 8 wherein the set of character templates being trained includes a "space" character template defined as a plurality of foreground template pixel positions each indicating a background pixel value;

the template image regions produced for storing respective character templates including a template image region, hereafter referred to as a "space" template image region for storing the "space" character template;

the "space" character template being produced using the "space" template image region and using at least one sample image region identified as a training sample for a "space" character in the character set; and

wherein the "space" character template is trained in the same manner as a reverse video character template.

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

wherein each template pixel position included in a respective template image region has a foreground probability parameter associated therewith indicating a probability value that the foreground pixel value indicated by the template pixel position is a valid foreground pixel value;

and

wherein the substep (a) of computing the template pixel scores for respective ones of the template pixel positions in the template image regions further includes computing each template pixel score for a respective template pixel position using the probability value associated with the respective template pixel position.

12. The method of operating a machine to train a set of character templates of claim 11

wherein the probability value indicated by the foreground probability parameter associated with each template pixel position is selected from a set of predetermined probability values;

and

wherein the substep (a) of computing each template pixel score for the respective template pixel position using the probability value associated with the respective template pixel position further includes selecting a probability value to be associated with the template pixel position from the set of predetermined probability values, and assigning the probability value to the template pixel position.

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

wherein each template pixel position in each template image region is identified relative to a local template region origin position defined according to a local template coordinate system;

one of the template pixel positions included in each template image region being designated as a template origin position having a displacement from the local template region origin position in the local template coordinate system;

wherein a plurality of sample image regions identified by respectively paired glyph labels as training data samples for a respective one of the character templates is included in a glyph sample collection data structure, referred to as a glyph sample collection, for the respective character template;

wherein each sample pixel position in each sample image region in each glyph sample collection is identified relative to a local sample region origin position according to a local sample coordinate system;

the image pixel position in each sample image region that indicates the image glyph source location of a glyph in the image glyph source being positioned in the sample image region at a displacement from the local sample region origin position equal to the displacement of the template origin position from the local template region origin position in the template image region representing the character template identified by the glyph sample collection, such that the sample image regions included in a glyph sample collection are effectively aligned at their respective image glyph source locations, being hereafter referred to as aligned sample image regions;

each sample pixel position in a first one of the aligned sample image regions being respectively paired with a sample pixel position at the same displacement from the local sample region origin position in a second one of the aligned sample image regions, and being respectively paired with a template pixel position at the same displacement from the local template region origin position in the template image region representing the character template identified by the glyph sample collection; and

wherein the substep (a) of computing the template pixel scores for respective ones of the template pixel positions in the template image regions further includes computing each template pixel score for a respective template pixel position using respectively paired sample pixel positions in the aligned sample image regions included in the glyph sample collection identifying training data samples for the respective template image region.

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

wherein each template pixel score computed for a respective template pixel position is a function of a count of foreground pixel values indicated by the sample pixel positions included in the sample image regions used for computing the template pixel score;

wherein substep (b) of assigning a foreground pixel value to a template pixel position further includes selecting the template pixel position on the basis of a maximum template pixel score; and

wherein substep (c) of modifying the sample pixel values of the sample pixel positions used in computing the template pixel score for an assigned template pixel position includes modifying the sample pixel values to indicate background pixel values, such that a subsequently-computed template pixel score computed for an unassigned template pixel position using the modified sample pixel values will be reduced, thereby reducing the likelihood that a foreground pixel value will be assigned to the unassigned template pixel position on the basis of the subsequently-computed template pixel score.

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

wherein a first one of the sample image regions including a first image pixel position indicating a first image glyph source location as a first glyph and identified as a training data sample for a first character template;

the first sample image region having size dimensions large enough to further include a second image pixel position included in the image glyph source indicating a second image glyph source location as a second glyph, such that the first sample image region includes sample pixel positions belonging to the first and second glyphs;

wherein a second sample image region also includes the second image pixel position indicating the second image glyph source location as the second glyph;

the second sample image region being identified as a training data sample for a second character template by a second respectively paired glyph label;

the second sample image region also including sample pixel positions belonging to the second glyph; and

wherein the set of character templates for the characters in the character set is produced without requiring all sample pixel positions in a sample image region to belong to a single glyph.

16. A method of operating a machine to train a set of character templates;

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

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

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

the method comprising;

operating the processor to receive and store, in the memory device of the machine, an image definition data structure including a plurality of image pixel positions defining an image;

the image definition data structure, hereafter referred to as an image glyph source, including a plurality of glyphs occurring therein;

each glyph 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 and store, in the memory device of the machine, a plurality of labeled glyph position data items;

each labeled glyph position data item indicating one of the plurality of image pixel positions in the image glyph source as an image glyph source location of a glyph occurring therein;

each labeled glyph position data item further indicating a glyph label, hereafter referred to as a respectively paired glyph label, paired with the image pixel position identifying the glyph indicated by the image pixel position as a respective one of the plurality of characters in the character set;

operating the processor to produce, for each respective character template to be trained, a template image region including a plurality of template pixel positions for storing the respective character template;

operating the processor to determine a sample image region included in the image glyph source for each labeled glyph position data item;

the sample image region including the image pixel position indicating the image glyph source location of a glyph and being identified as a training data sample for the character template indicated by the respectively paired glyph label;

each sample image region including a plurality of image pixel positions in the image glyph source, hereafter referred to as sample pixel positions, each indicating a sample pixel value; and

operating the processor to produce the set of character templates using the template image regions and the sample image regions;

producing the set of character templates including

(a) producing an image definition data structure for defining and storing an ideal image;

the ideal image being represented as a function of the set of character templates being trained, and being a reconstruction of the image glyph source formed by positioning respective ones of the character templates in an image plane at image pixel positions identified as image glyph source locations of glyphs occurring in the image glyph source;

each respective one of the character templates positioned in the ideal image being identified by the glyph label paired with the image glyph source location;

(b) computing pixel scores for template pixel positions in template image regions using selected ones of the sample pixel positions in selected ones of the sample image regions included in the image source of glyphs; and

(c) sequentially assigning a pixel value to selected template pixel positions in selected template image regions;

the selected template pixel positions being selected on the basis of the pixel scores optimizing the function representing the ideal image such that, when all template pixel positions have been assigned pixel values, the pixel value assigned to each selected template pixel position optimizes a matching score measuring a match between the image glyph source and the ideal image.

17. The method of operating a machine to train a set of character templates of claim 16

wherein glyphs occurring in the image glyph source are positioned according to a characteristic image positioning property such that, when a second glyph is positioned in the image glyph source with a glyph image origin position thereof displaced from a glyph image origin position of a preceding first glyph by a set width thereof, a first bounding box entirely containing the first glyph overlaps in the image glyph source with a second bounding box entirely containing the second glyph, and the first and second glyphs have substantially nonoverlapping foreground pixel positions;

wherein each sample image region has size dimensions large enough to include at least two glyphs positioned in the image glyph source according to the characteristic image positioning property;

wherein each character template in the set of character templates being trained is defined relative to a template origin position;

the function representing the ideal image requiring that respective ones of the character templates forming the ideal image in the image plane be positioned according to the characteristic image positioning property, such that, when a second character template is positioned in the ideal image with the template origin position thereof displaced from the template origin position of a preceding first character template by a character set width thereof, a first bounding box entirely containing the first character template is permitted to overlap in the image with a second bounding box entirely containing the second character template as long as the first and second character templates have substantially nonoverlapping foreground pixel positions; and

wherein the selected template pixel positions selected on the basis of the pixel scores optimizing the function representing the ideal image are selected further on the basis of the pixel scores optimizing the matching score between the image glyph source and the ideal image when the ideal image has character templates positioned according to the characteristic image positioning property.

18. The method of operating a machine to train a set of character templates of claim 16

wherein the selected pixel positions in selected sample image regions are selected by character template to include a plurality of sample image regions, referred to as a glyph sample collection, identified by respectively paired glyph labels as training data samples for a respective one of the character templates;

wherein each template pixel position in each template image region is identified relative to a local template region origin position defined according to a local template coordinate system;

one of the template pixel positions included in each template image region being designated as a template origin position having a displacement from the local template region origin position in the local template coordinate system; and

wherein each sample pixel position in each sample image region in each glyph sample collection is identified relative to a local sample region origin position according to a local sample coordinate system;

the image pixel position in each sample image region that indicates the image glyph source location of a glyph in the image glyph source being positioned in the sample image region at a displacement from the local sample region origin position equal to the displacement of the template origin position from the local template region origin position in the template image region representing the character template identified by the glyph sample collection, such that the sample image regions included in a glyph sample collection are effectively aligned at their respective image glyph source locations, being hereafter referred to as aligned sample image regions;

each sample pixel position in a first one of the aligned sample image regions being respectively paired with a sample pixel position at the same displacement from the local sample region origin position in a second one of the aligned sample image regions, and being respectively paired with a template pixel position at the same displacement from the local template region origin position in the template image region representing the character template identified by the glyph sample collection;

the selected pixel positions used by the template assignment selection criteria being the respectively paired pixel positions in the aligned sample image regions.

19. The method of operating a machine to train a set of character templates of claim 16 wherein each pixel score computed for a respective template pixel position is a function of a count of foreground pixel values indicated by the sample pixel positions included in the sample image regions used for computing the pixel score.

20. The method of operating a machine to train a set of character templates of claim 16 wherein

each character template stored in a respective template image region has a foreground probability parameter associated therewith indicating a probability value that the foreground pixel values indicated by the template pixel positions in the template image region are valid foreground pixel values;

and

the substep (b) of computing the pixel scores for the template pixel positions in the template image regions further includes computing the pixel scores for a respective one of the template image regions using the probability value associated with the respective template image region.

21. The method of operating a machine to train a set of character templates of claim 20 wherein the set of character templates being trained includes a "space" character template defined as a plurality of foreground template pixel positions each indicating a background pixel value;

the template image regions produced for storing respective character templates including a template image region, hereafter referred to as a "space" template image region for storing the "space" character template;

the "space" character template being produced using the "space" template image region and using at least one sample image region identified as a training sample for a "space" character in the character set;

wherein the white foreground pixels of the "space" character are stored as black foreground pixels in the "space" template image region representing the "space" character, and the black background pixels of the "space" character are stored as white background pixels in the "space" template image region; and

wherein the foreground probability value associated with the "space" character template is a low probability value indicating that the black foreground pixel values indicated by the template pixel positions in the "space" template image region are less likely to be valid black foreground pixel values, such that an operation using the "space" character template interprets the black foreground pixel values as white foreground pixels.

22. A method of operating a machine to train a set of character templates;

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

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

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

the method comprising;

operating the processor to receive and store, in the memory device of the machine, an image definition data structure including a plurality of image pixel positions defining an image;

the image definition data structure, hereafter referred to as an image glyph source, including a plurality of glyphs occurring therein;

each glyph 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 and store, in the memory device of the machine, a plurality of labeled glyph position data items;

each labeled glyph position data item indicating one of the plurality of image pixel positions in the image glyph source as a glyph image origin position of a glyph occurring therein;

the plurality of labeled glyph position data items identifying positions of glyphs occurring in the image glyph source without requiring identification of minimal bounding boxes for the glyphs;

each labeled glyph position data item further indicating a glyph label, hereafter referred to as a respectively paired glyph label, paired with the image pixel position identifying the glyph indicated by the image pixel position as a respective one of the plurality of characters in the character set;

operating the processor to produce, for each respective character template to be trained, a template image region including a plurality of template pixel positions for storing the respective character template;

one of the template pixel positions being designated as a template origin position;

operating the processor to determine a sample image region included in the image glyph source for each labeled glyph position data item;

the sample image region including the image pixel position indicating the glyph image origin position of a glyph and being identified as a training data sample for the character template indicated by the respectively paired glyph label;

each sample image region including a plurality of image pixel positions in the image glyph source, hereafter referred to as sample pixel positions, each indicating a sample pixel value;

each sample image region having no minimal size restriction such that a sample image region is not required to include sample pixel positions belonging only to a single glyph; and

operating the processor to produce the set of character templates using the template image regions and the sample image regions;

each character template being based on a character template model defining character image positioning, referred to as the sidebearing template model of character image positioning, wherein each character template is defined relative to a template origin position;

each character template produced having a characteristic image positioning property such that, when a second character template is positioned in an image with the template origin position thereof displaced from the template origin position of a preceding first character template by a character set width thereof, a first bounding box entirely containing the first character template is permitted to overlap in the image with a second bounding box entirely containing the second character template as long as the first and second character templates have substantially nonoverlapping foreground pixel positions;

the set of character templates being produced by sequentially assigning, in a template assignment order, a foreground pixel value to a selected template pixel position in a selected template image region until the set of character templates is complete;

the template assignment order being determined on the basis of template assignment selection criteria determined using the sample pixel values indicated by the sample pixel positions in the sample image regions;

the template assignment selection criteria determining which sample pixel positions in which sample image regions to use in selecting template pixel positions for foreground pixel value assignment such that a sample pixel position included in a first sample image region identified as a training data sample for a first character template that is identical to a sample pixel position included in a second sample image region identified as a training data sample for a second character template is used in a manner that produces character templates that substantially observe the characteristic imaging property of the sidebearing template model.

23. The method of operating a machine to train a set of character templates of claim 22 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 glyph sample width data computed using the sample image regions identified as training data samples for the respective character template.

24. A machine for training a set of character templates including

an image input device for providing image definition data defining images;

image input circuitry connected for receiving the image definition data defining images from the image input device;

input circuitry for receiving signal data;

the input circuitry being connected to a signal source for providing the signal data;

a processor; and

a memory device for storing data;

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

the processor being connected to the image input circuitry for receiving the image definition data defining an image;

the processor being further connected to the input circuitry for receiving the signal data;

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

the processor, in executing the instructions,

receiving and storing, in the memory device of the machine, an image definition data structure including a plurality of image pixel positions defining an image;

the image definition data structure, hereafter referred to as an image glyph source, including a plurality of glyphs occurring therein;

each glyph 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; and

receiving and storing, in the memory device of the machine, a plurality of labeled glyph position data items;

each labeled glyph position data item indicating one of the plurality of image pixel positions in the image glyph source as an image glyph source location of a glyph occurring therein;

each labeled glyph position data item further indicating a glyph label, hereafter referred to as a respectively paired glyph label, paired with the image pixel position identifying the glyph indicated by the image pixel position as a respective one of the plurality of characters in the character set;

the processor, further in executing the instructions,

producing, for each respective character template to be trained, a template image region including a plurality of template pixel positions for storing the respective character template; and

determining a sample image region included in the image glyph source for each labeled glyph position data item;

the sample image region including the image pixel position indicating the image glyph source location of a glyph and being identified as a training data sample for the character template indicated by the respectively paired glyph label;

each sample image region including a plurality of image pixel positions in the image glyph source, hereafter referred to as sample pixel positions, each indicating a sample pixel value;

the processor, further in executing the instructions, producing the set of character templates using the template image regions and the sample image regions;

wherein producing the set of character templates includes

(a) producing an image definition data structure for defining and storing an ideal image;

the ideal image being represented as a function of the set of character templates being trained, and being a reconstruction of the image glyph source formed by positioning respective ones of the character templates in an image plane at image pixel positions identified as image glyph source locations of glyphs occurring in the image glyph source;

each respective one of the character templates positioned in the ideal image being identified by the glyph label paired with the image glyph source location;

(b) computing pixel scores for template pixel positions in template image regions using selected ones of the sample pixel positions in selected ones of the sample image regions included in the image source of glyphs; and

(c) sequentially assigning a pixel value to selected template pixel positions in selected template image regions;

the selected template pixel positions being selected on the basis of the pixel scores optimizing the function representing the ideal image such that, when all template pixel positions have been assigned pixel values, the pixel value assigned to each selected template pixel position optimizes a matching score measuring a match between the image glyph source and the ideal image.