US 6,687,404 B1 · Automatic training of layout parameters in a 2D image model

Abstract

A two-dimensional (2D) image model models the layout structure of a class of document images as an image grammar and includes production rules having explicit layout parameters as data items that indicate information about the spatial relationships among image constituents occurring in images included in the class. The parameters are explicitly represented in the grammar rules in a manner that permits them to be automatically trained by a training operation that makes use of sample document images from the class of modeled documents. After each sample image is aligned with the 2D grammar, document-specific measurements about the spatial relationships between image constituents are taken from the image. Optimal values for the layout parameters are then computed from the measurement data collected from all samples. An illustrated implementation of the 2D image model takes the form of a stochastic context-free attribute grammar in which synthesized and inherited attributes and synthesis and inheritance functions are associated with each production rule in the grammar. The attributes indicate physical spatial locations of image constituents in the image, and a set of parameterized functions, in which the coefficients are the layout parameters, compute the attributes as a function of a characteristic of an image constituent of the production rule. The measurement data is taken from an annotated parse tree produced for each training image by the grammar. A trained grammar can then be used, for example, for document recognition and layout analysis operations on any document in the class of documents modeled by the grammar.

Claims25

Dependent claims

A method for operating a processor-controlled machine to determine an unknown value of a text image layout parameter used with a two-dimensional (2D) image model;

the machine including a signal source for receiving data;
memory for storing data;
and a processor connected for accessing instruction data which is stored in the memory for operating the machine;
the processor being further connected for receiving data from the signal source;
and connected for storing data in the memory;
the method comprising:
obtaining a data structure indicating a 2D image model modeling as an image grammar an image layout structure common to a class of 2D text images;
the 2D image model including a production rule indicating that first and second image constituents occurring in a 2D text image consistent with the image layout structure produce a third image constituent occurring therein;
the production rule including a text image layout parameter that indicates the spatial relationship between the first and second image constituents;
a value of the text image layout parameter being unknown;
receiving a plurality of input two-dimensional (2D) text image data structures from the signal source;
each input 2D text image represented by the plurality of input 2D text image data structures having the image layout structure common to the class of 2D text images and including at least one occurrence of first and second image constituents;
for each respective input 2D text image,
producing a data structure, using the 2D image model, indicating first and second image positions in the input 2D text image identifying respective locations of the first and second image constituents therein;
and
obtaining document-specific measurement data about the first and second image constituents from the data structure;
and
computing a value for the text image layout parameter using the document-specific measurement data obtained from the data structures for the respective input 2D text images;
the value computed for the text image layout parameter representing a class-specific value for all text images in the class of 2D input text images being modeled by the 2D image model.

16 more elements

A method for operating a processor-controlled machine to determine an unknown value of a text image layout parameter used with a two-dimensional (2D) image grammar;

the machine including a signal source for receiving data;
memory for storing data;
and a processor connected for accessing instruction data which is stored in the memory for operating the machine;
the processor being further connected for receiving data from the signal source;
and connected for storing data in the memory;
the method comprising:
obtaining a data structure indicating a 2D image grammar modeling a class of 2D text images as a stochastic context-free attribute grammar;
the 2D image grammar including a production rule indicating that first and second image constituents occurring in a 2D text image included in the class produce a third image constituent occurring therein;
the production rule indicating a mathematical function representing a spatial relationship between the first and second image constituents as a function of a characteristic of at least one of the first and second image constituents;
the mathematical function including a text image layout parameter as a parameter therein;
the text image layout parameter indicating the spatial relationship between the first and second image constituents;
a value of the text image layout parameter being unknown;
receiving a plurality of input two-dimensional (2D) text image data structures from the signal source;
each input 2D text image represented by the plurality of input 2D text image data structures having the image layout structure common to the class of 2D text images and including at least one occurrence of first and second image constituents;
for each respective input 2D text image,
producing an annotated parse tree representation of a layout and content of a respective input 2D text image using the 2D image grammar;
and
obtaining from the annotated parse tree document-specific measurement data about the spatial relationship between the first and second image constituents and a document-specific value of the mathematical function indicated by the production rule producing the third image constituent from the first and second image constituents occurring in the 2D text image;
and
constructing an overall function representing the document-specific measurement data and document-specific function values obtained for all input 2D text images as a function of the text image layout parameter;
and
solving the overall function for an optimal value of the text image layout parameter.

19 more elements

An article of manufacture for use in a machine that includes a memory device for storing data;

a storage medium access device for accessing a medium that stores data;
and a processor connected for accessing the data stored in the memory device and for receiving data from the storage medium access device;
the article comprising:
a data storage medium that can be accessed by the storage medium access device when the article is used in the machine;
and
data stored in the data storage medium so that the storage medium access device can provide the stored data to the processor when the article is used in the machine;
the stored data comprising instruction data indicating instructions the processor can execute;
the processor, in executing the instructions, obtaining a data structure indicating a 2D image model modeling as an image grammar an image layout structure common to a class of 2D text images;
the 2D image model including a production rule indicating that first and second image constituents occurring in a 2D text image consistent with the image layout structure produce a third image constituent occurring therein;
the production rule including a text image layout parameter that indicates the spatial relationship between the first and second image constituents;
a value of the text image layout parameter being unknown;
the processor, further in executing the instructions, receiving a plurality of input two-dimensional (2D) text image data structures from the signal source;
each input 2D text image represented by the plurality of input 2D text image data structures having the image layout structure common to the class of 2D text images and including at least one occurrence of first and second image constituents;
the processor, still further in executing the instructions, for each respective input 2D text image, producing a data structure, using the 2D image model, indicating first and second image positions in the input 2D text image identifying respective locations of the first and second image constituents therein;
and
obtaining document-specific measurement data about the first and second image constituents from the data structure;
the processor, still further in executing the instructions, computing a value for the text image layout parameter using the document-specific measurement data obtained from the data structures for the respective input 2D text images;
the value computed for the text image layout parameter representing a class-specific value for all text images in the class of 2D input text images being modeled by the 2D image model.

15 more elements

Dependencies are inferred from the claim text.

Automatic training of layout parameters in a 2D image model

Life of this patent

Automatic training of layout parameters in a 2D image model

Life of this patent

Abstract

Claims25