Multilevel image analysis

• US 8,606,015 B2
• Filed: 12/21/2011
• Issued: 12/10/2013
• Est. Priority Date: 12/17/2002
• Status: Expired due to Fees

• Current Assignee: ABBYY Production LLC (ABBYY Software)
• Original Assignee: ABBYY Development LLC
• Inventors: Anisimovich, Konstantin, Deryagin, Dmitry, Rybkin, Vladimir
• Primary Examiner(s): Mehta, Bhavesh
• Assistant Examiner(s): Dunphy, David F
• Application Number:
  US13/334,004
• Publication Number:
  US 20120163719A1
• Time in Patent Office: 720 Days
• Field of Search: None
• US Class Current: 382/195
• 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

Disclosed is a method of bit-mapped image analysis that comprises a whole image data representation via its component objects. The objects are assigned to different levels of complexity. The objects may be hierarchically connected by spatially-parametrical links. The method comprises preliminarily generating a classifier of image objects consisting of one or more levels differing in complexity; parsing the image into objects; attaching each object to one or more predetermined levels; establishing hierarchical links between objects of different levels; establishing links between objects within the same level; and performing an object feature analysis. Object feature analysis comprises generating and examining a hypothesis about object features and correcting the concerned object'"'"'s features of the same and other levels in response to results of hypothesis examination. Object feature analysis may also comprise execution of a recursive X-Y cut within the same level.

Claims

1. A device for performing image analysis, the device comprising:

a processor;

a memory in electronic communication with the processor, wherein the memory is configured with instructions, the instructions comprising;

classifying types of objects that are present within an image into one or more levels differing in complexity;

parsing the said image into objects;

attaching every said object to one of said levels of complexity;

establishing links between said objects of said different levels of complexity;

establishing links between said objects within each level of complexity;

performing an object feature analysis, said object feature analysis comprising;

forming a hypothesis about a spatial feature or a parametrical feature of the object, wherein the spatial feature or the parametrical feature is associated with a level of complexity,

examining the said hypothesis about the spatial feature or the parametrical feature of the object, and

when necessary, correcting the spatial feature or the parametrical feature of the object of the same and other levels depending on a result from the said examining of the hypothesis.

2. The device as recited in claim 1, wherein said object feature analysis further comprises execution of at least one recursive X-Y cut on objects within a same level of complexity.

3. The device as recited in claim 1, wherein said hypothesis about a spatial feature or a parametrical feature of the object comprises at least a list of objects of lower complexity incorporated into the object, and wherein the method further comprises outputting the results to a subsequent process.

4. The device as recited in claim 3, wherein said image analysis is performed by moving from a higher complexity level to a lower complexity level and wherein the subsequent process is a character recognition process.

5. The device as recited in claim 1, wherein said image analysis is performed by moving from a lower complexity level to a higher complexity level, and wherein the spatial feature or the parametrical feature of the object includes at least the following data:

a list of objects of lower complexity incorporated into the object subject to the object feature analysis, and

a relationship factor estimation of objects within a same level of complexity, said relationship factor estimation including at least a spatial estimation and a parametrical estimation.

6. The device as recited in claim 1, wherein said image analysis is performed by applying the method to any level and further moving to any level in an order and a number of times as determined by the image analysis, and wherein the image analysis is performed by moving from a higher complexity level to a lower complexity level.

7. The device as recited in claim 1, wherein said image analysis is performed by moving from a lower level of complexity to a higher level of complexity.

8. The device as recited in claim 1, wherein said image analysis is performed by applying the image analysis to a given level of complexity and subsequently applying it to a lower level of complexity or to a higher level of complexity.

9. The device as recited in claim 1, wherein the levels of complexity include characters, word tokens, words, lines, paragraphs, regions, tables, and non-text regions.

10. The device as recited in claim 9, wherein after examining a hypothesis at least at one level of complexity, performing a recursive X-Y cut to obtain subsidiary data about a spatial feature or a parametrical feature of the same and other levels.

11. One or more physical non-transitory computer-readable media configured with instructions for processing in an image, the instructions comprising:

classifying types of objects that are present within an image into one or more levels differing in complexity;

parsing the said image into objects;

attaching every said object to one of said levels of complexity;

establishing links between said objects of said different levels of complexity;

establishing links between said objects within each level of complexity;

performing an object feature analysis, said object feature analysis comprising;

forming a hypothesis about a spatial feature or a parametrical feature of the object, wherein the spatial feature or the parametrical feature is associated with a level of complexity,

examining the said hypothesis about the spatial feature or the parametrical feature of the object, and

when necessary, correcting the spatial feature or the parametrical feature of the object of the same and other levels depending on a result from the said examining of the hypothesis.

12. The one or more physical non-transitory computer-readable media as recited in claim 11, wherein said object feature analysis further comprises execution of at least one recursive X-Y cut on objects within a same level of complexity.

13. The one or more physical non-transitory computer-readable media as recited in claim 11, wherein said hypothesis about a spatial feature or a parametrical feature of the object comprises at least a list of objects of lower complexity incorporated into the object, and wherein the method further comprises outputting the results to a subsequent process.

14. The one or more physical non-transitory computer-readable media as recited in claim 13, wherein said image analysis is performed by moving from a higher complexity level to a lower complexity level and wherein the subsequent process is a character recognition process.

15. The one or more physical non-transitory computer-readable media as recited in claim 11, wherein said image analysis is performed by moving from a lower complexity level to a higher complexity level, and wherein the spatial feature or the parametrical feature of the object includes at least the following data:

a list of objects of lower complexity incorporated into the object subject to the object feature analysis, and

a relationship factor estimation of objects within a same level of complexity, said relationship factor estimation including at least a spatial estimation and a parametrical estimation.

16. The one or more physical non-transitory computer-readable media as recited in claim 11, wherein said image analysis is performed by applying the method to any level and further moving to any level in an order and a number of times as determined by the image analysis, and wherein the image analysis is performed by moving from a higher complexity level to a lower complexity level.

17. A method for analyzing an image or part of an image with objects, the method comprising:

parsing the image into objects;

assigning a plurality of objects present within the image into one or more levels, wherein each level differs in complexity from all other levels;

performing an object feature analysis on one or more objects, said object feature analysis including;

forming a hypothesis about a spatial feature of the object in a horizontal direction and in a vertical direction, wherein the spatial feature is associated with a level of complexity,

examining the hypothesis in a horizontal direction and in a vertical direction;

selecting a best direction for parsing of a remainder of objects based at least in part upon said examining of the hypothesis in the horizontal direction and in the vertical direction;

examining the said hypothesis about the spatial feature or the parametrical feature of the object, and

when necessary, correcting the spatial feature or the parametrical feature of the object of the same and other levels depending on a result from the said examining of the hypothesis.

18. The method of claim 17, wherein the method further comprises:

after assigning the plurality of objects into one or more levels, establishing links between objects of one level with objects assigned to another level of complexity.

19. The method of claim 17, wherein direction of parsing is chosen separately for each object within the same level of complexity.

20. The method of claim 17, wherein the object feature analysis includes:

performing a recursive X-Y cut by parsing the image into non-intersected regions within one level of complexity.