Image and document management system for content-based retrieval

• US 5,987,459 A
• Filed: 03/14/1997
• Issued: 11/16/1999
• Est. Priority Date: 03/15/1996
• Status: Expired due to Fees

• Current Assignee: Regents of The University of Minnesota (University of Minnesota)
• Original Assignee: Regents of The University of Minnesota (University of Minnesota)
• Inventors: Hosur, Srinath, Tewfik, Ahmed H., Swanson, Mitchell D.
• Primary Examiner(s): HO, RUAY L
• Application Number:
  US08/818,535
• Time in Patent Office: 977 Days
• Field of Search: 707/1-10, 707/100-104, 707/200-206, 705/34, 395/200.34, 345/501
• US Class Current: 1/1
• CPC Class Codes: G06F 16/51 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

A computerized image and document management system for tent-based retrieval integrating content-based retrieval support directly into the compressed files. The system minimizes a weighted sum of the expected size of the compressed files and the expected query response time. Object searching of documents stored by the system is possible on a scalable resolution basis. The system includes a novel object representation based on embedded prototypes that provides for high-quality browsing of retrieval images at low bit rates.

Claims

1. A computerized method for storing data in an electronically stored file for later retrieval, the method comprising the steps of:

extracting a plurality of query objects from at least one input file;

coding a set of codewords in a particular order, each codeword corresponding to a query object and having a particular length;

determining instances of each query object within the at least one input file; and

,

compressing non-query object data within each input file.

2. The computerized method of claim 1, wherein the particular length of each codeword and the particular order of the set of codewords are optimized to minimize an expected length of the electronically stored file.

3. The computerized method of claim 1, wherein the particular length of each codeword and the particular order of the set of codewords are optimized to minimize an expected query response time in searching the electronically stored file.

4. The computerized method of claim 1, wherein the particular length of each codeword and the particular order of the set of codewords are optimized both to minimize an expected length of the electronically stored file and an expected query response time in searching the electronically stored file.

5. The computerized method of claim 1, wherein each codeword corresponds to a multiresolution representation of each query object.

6. The computerized method of claim 1, wherein each codeword has a particular length n, and is unique compared to the first n characters of every other codeword.

7. A computerized method for decoding an electronically stored file having a file header of concatenated codewords corresponding to query objects, data denoting a plurality of instances of the objects within the file, and non-query object data, the method comprising the steps of:

decoding the query objects from the concatenated codewords; and

,

inserting each query object within the non-query object data at each instance of the query object.

8. The computerized method of claim 7, wherein the non-query object data is compressed, and further comprising the step of decompressing the non-query object data.

9. A computerized method for browsing an electronically stored file having a file header of concatenated codewords corresponding to multiresolution representations of query objects, data denoting a plurality of instances of the objects within the file, and non-query object data, the method comprising the steps of:

decoding at least one query object from the concatenated codewords at a particular resolution;

matching each query object of the at least one query object to a corresponding prototype object for the particular resolution; and

,

inserting the corresponding prototype object for the particular resolution of each query object of the at least one query object at each instance of the query object.

10. A data structure for electronically storing a file comprising:

a file header of concatenated codewords, each codeword corresponding to a query object;

a set of indices denoting a plurality of instances of the objects within the file; and

,

non-query object data.

11. The data structure of claim 10, wherein the non-query object data is compressed.

12. The data structure of claim 10, wherein each codeword corresponds to a multiresolution representation of each query object.

13. A computerized method for storing at least one image in an electronically stored file for later retrieval, the method comprising the steps of:

blocking each image into a plurality of blocks smaller than the image;

defining one or more objects of the image using a segmentation algorithm;

associating each object with a number of the blocks to form a superblock corresponding to the object;

applying a wavelet transform to each superblock to generate query objects;

coding a set of codewords in a particular order, each codeword corresponding to a query object and having a particular length; and

,

determining the instances of each query object within each image.

14. The computerized method of claim 13, further comprising the step of coding non-superblocked regions of each image.

15. The computerized method of claim 13, wherein each codeword corresponds to a multiresolution representation of each query object.

16. The computerized method of claim 15, wherein the multiresolution representation of each query object includes a plurality of subbands.

17. The computerized method of claim 16, wherein the step of coding maps the plurality of subbands to finite dictionaries using vector quantization.

18. The computerized method of claim 15, further comprising the step of mapping one of a like subset of query objects at a particular resolution as a prototype object for the like subset of query objects at the particular resolution.

19. A computerized method for searching for a desired object within an electronically stored file of at least one image comprising the steps of:

associating the desired object with a number of blocks to form a superblock corresponding to the object;

applying a wavelet transform to the superblock to generate a query object;

searching the electronically stored file for the query object on a resolution-by-resolution basis.

20. The computerized method of claim 19, wherein the step of searching comprises the steps of:

searching each image for the query object at a first resolution; and

,

searching the images in which the query object was found at the first resolution for the query object at a second resolution.

21. The computerized method of claim 20, wherein the step of searching further comprises the step of searching the images in which the query object was found at the second resolution for the query object at a third resolution.