Method for object recognition and describing structure of graphical objects

• US 9,224,040 B2
• Filed: 09/23/2011
• Issued: 12/29/2015
• Est. Priority Date: 03/28/2003
• Status: Active Grant

• Current Assignee: ABBYY Development LLC
• Original Assignee: ABBYY Development LLC
• Inventors: Zuev, Konstantin, Tuganbaev, Diar
• Primary Examiner(s): STORK, KYLE R
• Application Number:
  US13/242,218
• Publication Number:
  US 20120011434A1
• Time in Patent Office: 1,558 Days
• Field of Search: 715/234, 715/243, 715/254, 715/221
• US Class Current: 1/1
• CPC Class Codes: G06V 30/413 Classification of content, e.g. text, photographs or tables
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text

Abstract

The invention involves a method for processing of machine-readable forms or documents of non-fixed format. The method makes use of, for example, a structural description of characteristics of document elements, a description of a logical structure of the document, and methods of searching for document elements by using the structural description. A structural description of the spatial and parametric characteristics of document elements and the logical connections between elements may include a hierarchical logical structure of the elements, specification of an algorithm of determining the search constraints, specification of characteristics of every searched element, and specification of a set of parameters for a compound element identified on the basis of the aggregate of its components. The method of describing the logical structure of a document and methods of searching for elements of a document may be based on the use of the structural description.

Claims

1. An apparatus configured to store data for access by an application program being executed on a data processing system, the data related to a structural description of the spatial and parametric characteristics of an element and logical connections with other elements of a non-fixed layout document, the apparatus comprising:

a processor;

a storage coupled to the processor;

wherein the storage is configured to store a data structure, wherein the data structure includes information related to the non-fixed layout document;

wherein the data structure is configured to include a plurality of assigned descriptions of logical connections of the element with the other elements, wherein the assigned descriptions of logical connections are represented as a hierarchical sequence of elements;

wherein the data structure is further configured to include a plurality of assigned descriptions of spatial connections of the element, wherein the spatial connections relate to the other elements and a plurality of assigned descriptions of parametric characteristics of the element;

wherein the data structure is configured to include an assigned algorithm for determining element search constraints and an assigned set of parameters for identification of a compound element on the basis of aggregate constituents, wherein the compound element is made up of a combination of the element and a plurality of the other elements.

2. The apparatus of claim 1, wherein the storage is configured to store

a variant of the element;

and

an algorithm of estimating a quality rating of an obtained variant of the element.

3. The apparatus of claim 2, wherein the algorithm of estimating the quality rating of the obtained variant of the element is set in a form of a reference table.

4. The apparatus of claim 2, wherein the algorithm of estimating the quality rating of the obtained variant of the element is set in the form of a graph.

5. The apparatus of claim 1, wherein the data structure further includes

an auxiliary brief description for determination of a spatial orientation of an image of the non-fixed layout document.

6. The apparatus of claim 1, wherein the data structure further includes

an auxiliary brief description for selecting a type of the non-fixed layout document;

a plurality of comprehensive descriptions; and

a selected comprehensive description for the non-fixed layout document, the selected comprehensive description being selected from the plurality of comprehensive descriptions.

7. A method for identifying a layout of a paper-based non-fixed layout document, the method comprising:

acquiring an electronic image of the paper-based non-fixed layout document;

creating a structural description of the spatial, parametric characteristics of an element and logical connections thereof with other elements that may be in the electronic image of the paper-based non-fixed layout document, comprising;

identifying and storing an assigned description for each of a plurality of logical connections between elements;

identifying and storing an assigned description of spatial characteristics of each of the elements;

identifying and storing an assigned description of parametric characteristics of each of the elements;

identifying and storing an assigned algorithm that is capable of determining element search constraints; and

identifying an assigned set of parameters for identification of a compound element on the basis of the aggregate of its constituents, said assigned set of parameters including one or more logical connections represented as a hierarchical sequence of elements.

8. The method as recited in claim 7, further comprising:

creating and storing an algorithm capable of estimating a quality rating for any variant of elements that may be in the electronic image of the paper-based non-fixed layout document.

9. The method as recited in claim 8, wherein the algorithm capable of estimating the quality rating for any variant of elements that may be in the electronic image of the paper-based non-fixed layout document is set in the form of a reference table.

10. The method as recited in claim 7, wherein the method further comprises:

specifying an auxiliary brief description for determination of a spatial orientation of the electronic image of the paper-based non-fixed layout document.

11. The method as recited in claim 10, wherein the method further comprises:

specifying a plurality of comprehensive descriptions for types of documents;

searching the electronic image of the paper-based non-fixed layout document and

identifying, using the plurality of comprehensive descriptions for types of documents, a type of document and its corresponding comprehensive description.

12. A system, comprising a computing device;

and a computer-readable medium coupled to the computing device and having instructions stored thereon which, when executed by the computing device, cause the computing device to perform operations for identifying a layout of a paper-based non-fixed layout document comprising;

acquiring an electronic image of the paper-based non-fixed layout document;

creating a structural description of the spatial, parametric characteristics of an element and logical connections thereof with other elements that may be in the electronic image of the paper-based non-fixed layout document, comprising;

identifying and storing an assigned description for each of a plurality of logical connections between elements;

identifying and storing an assigned description of spatial characteristics of each of the elements;

identifying and storing an assigned description of parametric characteristics of each of the elements;

identifying and storing an assigned algorithm that is capable of determining element search constraints; and

identifying an assigned set of parameters for identification of a compound element on the basis of the aggregate of its constituents, said assigned set of parameters including one or more logical connections represented as a hierarchical sequence of elements.

13. The method as recited in claim 12, further comprising:

creating and storing an algorithm capable of estimating a quality rating for any variant of elements that may be in the electronic image of the paper-based non-fixed layout document.

14. The method as recited in claim 13, wherein the algorithm capable of estimating the quality rating for any variant of elements that may be in the electronic image of the paper-based non-fixed layout document is set in the form of a reference table.

15. The method as recited in claim 12, wherein the method further comprises:

specifying an auxiliary brief description for determination of a spatial orientation of the electronic image of the paper-based non-fixed layout document.

16. The method as recited in claim 12, wherein the method further comprises:

specifying a plurality of comprehensive descriptions for types of documents;

searching the electronic image of the paper-based non-fixed layout document and identifying, using the plurality of comprehensive descriptions for types of documents, a type of document and its corresponding comprehensive description.