System for searching a corpus of document images by user specified document layout components

• US 5,999,664 A
• Filed: 11/14/1997
• Issued: 12/07/1999
• Est. Priority Date: 11/14/1997
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Blomberg, Jeanette L., Shin, Christian K., Trigg, Randall H., Mahoney, James V.
• Primary Examiner(s): Couso, Yon J.
• Application Number:
  US08/971,022
• Time in Patent Office: 753 Days
• Field of Search: 382/180, 382/305, 382/293, 382/295, 382/173, 382/176, 707/517, 707/520, 707/523
• US Class Current: 382/305
• CPC Class Codes: G06F 16/58 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 16/5846 using extracted text
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1444 Selective acquisition, locating or processing of specific regions, e.g. highlighted text, fiducial marks or predetermined fields
• 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

A document search system provides a user with a programming interface for dynamically specifying features of documents recorded in a corpus of documents. The programming interface operates at a high-level that is suitable for interactive user specification of layout components and structures of documents. In operation, a bitmap image of a document is analyzed by the document search system to identify layout objects such as text blocks or graphics. Subsequently, the document search system computes a set of attributes for each of the identified layout objects. The set of attributes which are identified are used to describe the layout structure of a page image of a document in terms of the spatial relations that layout objects have to frames of reference that are defined by other layout objects. After computing attributes for each layout object, a user can operate the programming interface to define unique document features. Each document feature is a routine defined by a sequence of selections operations which consume a first set of layout objects and produce a second set of layout objects. The second set of layout objects constitutes the feature in a page image of a document. Using the programming interface, a user flexibly defines a genre of document using the user-specified document features.

Claims

1. A method for searching a corpus of document images stored in a memory, comprising the steps of:

segmenting each document image in the corpus of document images into a first set of layout objects;

each layout object in the first set of layout objects being one of a plurality of layout object types;

each of the plurality of layout object types identifying a structural element of a document;

for each segmented document image, computing attributes for each layout object in the first set of layout objects;

the computed attributes of each layout object having values that quantify properties of a structural element and identify spatial relationships with other segmented layout objects;

providing a program interface for composing a routine that includes a sequence of selection operations for identifying certain of the layout objects in the first set of layout objects of an example document image selected from the corpus of document images;

the certain layout objects defining a feature of the example document image;

executing the sequence of selection operations of the routine for identifying the feature of the example document image in ones of the document images in the corpus of document images;

for each segmented document image, the sequence of selection operations receiving as input the first set of layout objects and the computed attributes to produce as output a second set of layout objects;

said executing step identifying the ones of the document images in the corpus of document images that include at least one layout object in the second set of layout objects as having the feature of the example document image; and

displaying at the program interface the ones of the document images in the corpus of document images identified by said executing step.

2. The method according to claim 1, further comprising the step of highlighting in the example document image the feature identified by the routine composed at a program interface.

3. The method according to claim 1, wherein one of the selection operations executed by said executing step is a filtering operation that produces a second set of layout objects having attribute values between a minimum threshold value and a maximum threshold value.

4. The method according to claim 1, wherein one of the selection operations executed by said executing step is a gating operation that produces a second set of layout objects equal to the first set of layout objects when each of the layout objects in a document image have attribute values between a minimum threshold value and a maximum threshold value.

5. The method according to claim 1, wherein one of the selection operations executed by said executing step is an accumulation operation that identifies an attribute value for the layout objects in the first set of layout objects.

6. The method according to claim 1, further comprising the step of forming the corpus document images in the memory by scanning hardcopy documents.

7. The method according to claim 1, wherein said segmenting step defines one of the plurality of layout objects to be a text block of.

8. The method according to claim 1, further comprising the step of defining a structural model for identifying a genre of document;

the structural model defining a set of features absent and a set of features present in document images to specify a class of document images which express a common communicative purpose that is independent of document content.

9. A program storage device readable by a machine, embodying a program of instructions executable by the machine to perform method steps for searching a corpus of document images stored in a memory of a document management system, said method steps comprising:

segmenting each document image in the corpus of document images into a first set of layout objects;

each layout object in the first set of layout objects being one of a plurality of layout object types;

each of the plurality of layout object types identifying a structural element of a document;

for each segmented document image, computing attributes for each layout object in the first set of layout objects;

the computed attributes of each layout object having values that quantify properties of a structural element and identify spatial relationships with other segmented layout objects;

providing a program interface for composing a routine that includes a sequence of selection operations for identifying certain of the layout objects in the first set of layout objects of an example document image selected from the corpus of document images;

the certain layout objects defining a feature of the example document image;

executing the sequence of selection operations of the routine for identifying the feature of the example document image in ones of the document images in the corpus of document images;

for each segmented document image, the sequence of selection operations receiving as input the first set of layout objects and the computed attributes to produce as output a second set of layout objects;

said executing step identifying the ones of the document images in the corpus of document images that include at least one layout object in the second set of layout objects as having the feature of the example document image; and

displaying at the program interface the ones of the document images in the corpus of document images identified by said executing step.

10. The program storage device as recited in claim 9, wherein said method steps further comprise the step of defining a structural model for identifying a genre of document;

the structural model defining a set of features absent and a set of features present in document images to specify a class of document images which express a common communicative purpose that is independent of document content.

11. A document management system for searching a corpus of document images, comprising:

a memory for storing the corpus of document images and image processing instructions of the document management system;

a display; and

a processor coupled to the memory and the display for executing the document image processing instructions of the document management system;

the processor in executing the document image processing instructions;

segmenting each document image in the corpus of document images into a first set of layout objects;

each layout object in the first set of layout objects being one of a plurality of layout object types;

each of the plurality of layout object types identifying a structural element of a document;

for each segmented document image, computing attributes for each layout object in the first set of layout objects;

the computed attributes of each layout object having values that quantify properties of a structural element and identify spatial relationships with other segmented layout objects;

providing a program interface on the display for composing a routine that includes a sequence of selection operations for identifying certain of the layout objects in the first set of layout objects of an example document image selected from the corpus of document images;

the certain layout objects defining a feature of the example document image;

executing the sequence of selection operations of the routine for identifying the feature of the example document image in ones of the document images in the corpus of document images;

for each segmented document image, the sequence of selection operations receiving as input the first set of layout objects and the computed attributes to produce as output a second set of layout objects;

identifying the ones of the document images in the corpus of document images that include at least one layout object in the second set of layout objects to have the feature of the example document image; and

displaying at the program interface on the display the ones of the document images in the corpus of document images identified as having the feature of the example document image.

12. The document management system according to claim 11, further comprising means for displaying at the program interface on the display an example document with the feature highlighted.

13. The document management system according to claim 11, wherein the program interface on the display comprises:

a first display area for specifying a name for the feature;

a second display area for specifying a set of images which exemplify the feature;

a third display area for specifying a set of input layout objects;

the set of input layout objects limiting the first set of layout objects of the document image consumed by the sequence of selection operations of the routine; and

a fourth display area for defining the sequence of selections operations of the feature.

14. The document management system according to claim 11, further comprising a program interface on the display for defining a model of a genre of document.

15. The document management system according to claim 14, wherein the program interface on the display comprises:

means for specifying that a feature is present in the genre of document; and

means for specifying that a feature is absent from the genre of document.

16. The document management system according to claim 14, wherein the genre of document specified is a letter.

17. The document management system according to claim 14, wherein the genre of document specified is a memo.

18. The document management system according to claim 11, wherein the document image is a bitmap image.

19. The document management system according to claim 11, wherein one of the sequence of selection operations is a filtering operation given by:

space="preserve" listing-type="equation">F(L,A,u,v,N)={lε

L;

uN≦

A(l)<

vN}, where;

L is a set of layout objects to which the filtering operation is applied;

A is an attribute;

u and v are threshold arguments; and

N is a normalization argument.

20. The document management system according to claim 11, wherein one of the sequence of selection operations is a gate operation given by:

##EQU3## L is a set of layout objects to which the gate operation is applied;

A is an attribute;

u and v are threshold arguments; and

N is a normalization argument.