|
|
|
| United States Patent | 5689620 |
| Link to this page | http://www.wikipatents.com/5689620.html |
| Inventor(s) | Kopec; Gary E. (Belmont, CA);
Chou; Philip Andrew (Menlo Park, CA);
Niles; Leslie T. (Palo Alto, CA) |
| 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. |
|
|
|
Title Information  |
|
|
|
|
|
|
| Publication Date |
November 18, 1997 |
|
|
|
|
|
| Filing Date |
April 28, 1995 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Title Information  |
|
|
Claims  |
|
|
What is claimed:
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. |
|
|
|
|
Claims  |
|