Navigation system for document image database

• US 5,995,978 A
• Filed: 09/24/1997
• Issued: 11/30/1999
• Est. Priority Date: 09/24/1997
• Status: Expired due to Term

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Hull, Jonathan J., Cullen, John F.
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): PARDO, THUY N
• Application Number:
  US08/936,336
• Time in Patent Office: 797 Days
• Field of Search: 707/3, 707/2, 707/4, 707/104, 707/101, 382/283, 382/248, 382/232, 395/356
• US Class Current: 1/1
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/5846 using extracted text
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

An interactive database organization and searching system employs text search and image feature extraction to automatically group documents together by appearance. The system automatically determines visual characteristics of document images and collect documents together according to the relative similarity of their document images.

Claims

1. A method for searching for a particular document image in a database containing a plurality of document images, each document image having a textual component, a compressed representation, and a non-compressed representation, said method comprising:

accepting text from a user as a keyword to search;

searching the textual component of said plurality of document images for said keyword;

detecting similarity of features extracted from document images having textual components that contain said keyword, wherein said detecting is based on processing of the compressed representation or the non-compressed representation of the document images;

grouping document images having similar extracted features into a plurality of clusters of document images;

selecting a representative document image for each of the plurality of clusters of document images;

displaying the representative document image for each of the plurality of clusters of document images; and

accepting input from the user indicating a particular cluster of document images.

2. The method of claim 1 wherein said compressed representation is generated from said document image by applying a CREW algorithm to said document image.

3. The method of claim 1 wherein said detecting comprises:

extracting image feature information about said particular document image; and

applying a clustering algorithm to said image feature information to form said plurality of clusters of document images.

4. The method of claim 3 wherein said extracting step comprises computing statistical information for said particular document image.

5. The method of claim 4 wherein said extracting step additionally comprises computing component connections for said particular document image.

6. The method of claim 3 wherein said clustering algorithm comprises a "k-means" clustering algorithm.

8. The method of claim 1 wherein said selecting comprises:

calculating a center for each cluster of document images; and

selecting a document image nearest to said center as the representative document image.

9. The method of claim 1 further comprising:

iteratively applying the grouping, selecting displaying, and accepting to form a hierarchical search pattern through the database.

10. The method of claim 1 wherein said displaying comprises:

displaying said compressed representation of each representative document image using a web browser.

11. The method of claim 1 wherein said displaying comprises:

displaying said representative document image using a web browser.

7. A method for searching for a particular document image in a database containing a plurality of document images, wherein each document image has a textual component a compressed representation and a non-compressed representation, said method comprising:

accepting text from a user as a keyword to search;

searching the textual component of said plurality of document images for said keyword;

grouping document images having textual components that contain said keyword into a plurality of clusters of document images based upon processing of the compressed representation or the non-compressed representation of the document images, wherein said processing includes

extracting image feature information about said particular document image, and

applying a "k-means" clustering algorithm to said image feature information to form said plurality of clusters of document images;

displaying, based on said processing, a representative document image for each of the plurality of clusters of document images; and

accepting input from the user indicating a particular cluster of document images,

wherein said plurality of clusters consists of between 5 and 10 document images.

12. A method for organizing a plurality of document images in a database comprising:

compressing each particular document image in said plurality of document images;

extracting feature information about said particular document image;

detecting similarity of features extracted from said plurality of document images, wherein said detecting is based on processing of a compressed representation or a non-compressed representation of the document images;

grouping said plurality of document images together to form clusters of document images;

selecting a representative document image for each of the clusters of document images; and

displaying each representative document image.

13. The method of claim 12 wherein said compressing comprises applying a CREW algorithm to said particular document image.

14. The method of claim 12 wherein said extracting comprises:

computing statistical information from said particular document image; and

extracting text keywords from textual information contained in said particular document image.

15. The method of claim 14 wherein said extracting additionally comprises computing component connections for said particular document image.

16. The method of claim 12 wherein said grouping comprises applying a "k-means" clustering algorithm to form a plurality of representative document groups.

18. The method of claim 12 wherein said selecting comprises:

calculating a center for each cluster of document images; and

selecting a document image nearest to said center as the representative document image.

19. The method of claim 12 additionally comprising:

accepting user input selecting a particular representative document image as a starting point for searching; and

iteratively applying the grouping, selecting, displaying, and accepting to form a hierarchical search method.

20. The method of claim 12 wherein said displaying comprises displaying said compressed representation of each representative document image using a web browser.

21. The method of claim 12 wherein said displaying comprises displaying said representative document image using a web browser.

17. A method for organizing a plurality of document images in a database comprising:

compressing each particular document image in said plurality of document images;

extracting image feature information about said particular document image;

grouping said plurality of document images together to form clusters of document images, wherein said grouping comprises applying a "k-means" clustering algorithm;

selecting a representative document image for each of the clusters of document images; and

displaying each representative document image,

wherein said clusters include between 5 and 10 document images.

22. A computer program product comprising:

code that accepts text from a user as a keyword to search;

code that searches a database of document images, each document image having a textual component and a compressed representation, for document images with textual components that contain said keyword;

code that detects similarity of features extracted from documents having textual components that contain said keyword;

code that groups document images having similar extracted features together into clusters of document images;

code that selects a representative document image for each of the clusters for display;

code that displays selected representative document images; and

a computer readable storage medium configured to store the codes.

23. The computer program product of claim 22 further comprising:

code that generates said compressed representation from said document image by applying a CREW algorithm to said document image.

24. The computer program product of claim 22 further comprising:

code that accepts user input selecting images from the selected representative document images for iterative search to form a hierarchical organization of said document images.

25. The computer program product of claim 22 wherein said code that groups document images employs a "k-means" algorithm.

27. The computer program product of claim 22 wherein said code that groups document images comprises:

code that extracts image feature information from image component of said document images.

28. The computer program product of claim 27 wherein said code that extracts image feature information comprises:

code that computes statistical information; and

code that extracts connected component information.

29. The computer program product of claim 22 wherein said code that selects the representative document image comprises code that calculates a center for each cluster of document images and selects a document image nearest to said center as the representative document image.

30. The computer program product of claim 22 wherein said code that displays selected representative document images comprises code that displays said compressed representations of said document images using a web browser interface.

31. The computer program product of claim 22 wherein said code that displays selected representative document images comprises code that displays said document images using a web browser interface.

26. A computer program product comprising:

code that accepts text from a user as a keyword to search;

code that searches a database of document images, each document image having a textual component and a compressed representation, for document images with textual components that contain said keyword;

code that groups document images together into clusters of document images based upon processing of the image component of said document images, wherein said clusters include between 5 and 10 document images;

code that selects a representative document image for each of the clusters for display;

code that displays selected representative document images; and

a computer readable storage medium configured to store the codes.

32. A document image database organizing system comprising:

an electronic storage unit that stores a document image database;

a display that displays document images;

a processor unit coupled to said electronic storage device and said display, said processor unit operative to;

compress document images;

extract feature information about document images;

detect, based on a compressed representation or a non-compressed representation of said document images similarity of features extracted from said document images;

group said document images into a plurality of clusters of document images according to said detected similarity of features;

select a representative document image for each cluster;

display said representative document image; and

accept input commands to manipulate document images.