Object recognition and describing structure of graphical objects

• US 9,015,573 B2
• Filed: 04/17/2012
• Issued: 04/21/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, Filimonova, Irina
• Primary Examiner(s): STORK, KYLE R
• Application Number:
  US13/449,240
• Publication Number:
  US 20120201420A1
• Time in Patent Office: 1,099 Days
• Field of Search: 715/234, 715/243, 715/254, 715/221, 706/48
• US Class Current: 715/221
• 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

Methods for processing machine-readable forms or documents of non-fixed format are disclosed. The methods make 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 searched elements, 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. A method for searching for elements of a form of a non-fixed format, the method comprising:

obtaining a structural description of the form of a non-fixed format, wherein the structural description includes a description of spatial and parametric characteristics of elements of the form;

searching for objects in a form image corresponding to those of the form;

identifying text objects to be recognized from the found objects in the form image;

performing a character recognition (CR) function via a computer processor on each of said text objects;

obtaining a search constraint of an element from the structural description;

finding the element associated with the search constraint in the form image based on found objects;

identifying variants corresponding to the element associated with the search constraint;

examining each of the variants corresponding to the element; and

selecting a variant for the element.

2. The method as recited in claim 1, wherein searching for elements of the form image is based on items including:

spatial characteristics of a search area for the element;

a parametric characteristic of the element;

a spatial characteristic of the element represented as an exact value or as an interval of values; and

a result of preliminary text recognition.

3. The method as recited in claim 1, wherein said examining each of the variants corresponding to the element comprises:

estimating a quality of identification related to an identity of the element;

identifying hypotheses corresponding to the element;

analyzing results of testing the hypotheses about a presence, completeness of composition of an element that is a compound element, or types of parts of an element that is a compound element including analyzing types of parts corresponding to a hypothesis about a type of the compound element; and

estimating a total reliability of each variant of the plurality of variants.

4. The method as recited in claim 1, wherein the method further comprises:

after selecting the variant for the element, optimizing the selected variant based on a revision of compound element combinations when the element is a compound element.

5. The method as recited in claim 4, wherein said optimizing the selected variant comprises:

identifying a number of variants that satisfy a quality rating and discarding variants that do not satisfy a quality rating; and

searching for a preferred variant of the compound element based on a preferred total quality rating based on ratings of accountable composite parts, regardless of their number.

6. The method as recited in claim 1, wherein the method further comprises:

determining an orientation of the form image.

7. The method as recited in claim 6, wherein all or a portion of elements of the structural description are used to determine a desired image orientation for the form image, and wherein the search constraint is based on a result of said performed CR function.

8. The method as recited in claim 6, wherein an auxiliary brief description is specified to determine the orientation of the form image.

9. The method as recited in claim 1, wherein the type of a document corresponding to the form is selected from several preliminarily specified document types based on a structural description of the form in reference to a type of element found in the form.

10. The method as recited in claim 9, wherein a supplementary brief structural description is assigned for determining a document type for the form and for selecting a comprehensive document description from the several preliminarily specified types.

11. The method as recited in claim 1, wherein the spatial characteristics of an element comprise at least a set of absolute coordinates or relative coordinates.

12. The method as recited in claim 1, wherein exact, interval characteristics or exact and interval characteristics of a search element are identified.

13. The method as recited in claim 5, wherein searching for a next element is performed when no variant for the current element is selected or the total quality rating is lower than a predefined value.

14. The method as recited in claim 1, wherein when no object is found in a specified region of the image, searching for an object corresponding to a next element of the structural description.

15. One or more non-transitory computer readable media encoded with instructions for causing one or more processors to perform a method for searching for an element of a form of non-fixed layout using a structural description, the instructions causing acts comprising:

obtaining a structural description of the form of a non-fixed format, wherein the structural description includes a description of spatial characteristics of elements of the form;

searching for objects in a form image corresponding to those of the form of a non-fixed format;

identifying text objects to be recognized;

performing a character recognition (CR) function via said one or more processors on each of said text objects;

obtaining a search constraint of an element from the structural description;

finding the element in the form image based on found objects;

identifying variants corresponding to the element;

examining each of the variants corresponding to the element; and

selecting a variant for the element.

16. The one or more non-transitory computer readable media of claim 15, wherein the search constraint is based on a result of said CR function.

17. The one or more non-transitory computer readable media of claim 15, wherein the type of a document corresponding to the form is selected from several preliminarily specified document types based on a structural description of the form in reference to a type of element likely to be found in the form.

18. The one or more non-transitory computer readable media of claim 17, wherein a supplementary brief structural description is assigned, prior to obtaining a structural description of the form of a non-fixed format, for determining a document type for the form.

19. A device for searching for elements of a form of a non-fixed format, the device comprising:

a processor;

a memory in electronic communication with the processor, wherein the memory is configured with instructions to cause the processor to perform actions comprising;

obtaining a structural description of the form of a non-fixed format, wherein the structural description includes a description of spatial and parametric characteristics of elements of the form;

searching for objects in a form image corresponding to those of the form of a non-fixed format;

identifying text objects to be recognized;

performing a character recognition (CR) function via a computer processor on each of said text objects;

obtaining a search constraint of an element from the structural description;

finding the element in the form image based on one or more found objects;

identifying variants corresponding to the element;

examining each of the variants corresponding to the element, wherein examining includes estimating a value related to quality of identification of the element; and

selecting a variant for the element based on said examining each of the variants.

20. The device of claim 19, wherein examining of each of the variants further includes:

reducing a number of identified variants by providing a quality rating to each of the identified variants;

where a variant is a compound variant, combining quality ratings of components of said compound variant to obtain a total quality rating for said compound variant; and

reducing the number of identified variants by taking a preferred number of variants based on respective quality ratings.