System for efficient content-based retrieval of images

• US 6,418,430 B1
• Filed: 06/10/1999
• Issued: 07/09/2002
• Est. Priority Date: 06/10/1999
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Chopra, Rajiv, Annamalai, Melliyal, Srinivsan, Jagannathan, DeFazio, Samuel
• Primary Examiner(s): Metjahic, Safet
• Assistant Examiner(s): Veillard, Jacques
• Application Number:
  US09/329,530
• Time in Patent Office: 1,125 Days
• Field of Search: 707/2, 707/3, 707/5, 707/6, 707/101-104, 382/232, 382/305, 382/224, 382/115, 382/209, 382/218, 382/219, 382/220
• US Class Current: 1/1
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches
• 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/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A system creates and uses a visual image index for visual image retrieval. The visual image index uses multi-level filtering to reduce the processing and storage needed to identify visual images in a table that have similar characteristics to those of a query image. Information about a visual image is stored in an image signature that contains data about basic visual primitives of the image (e.g., global color, local color, texture and structure). The signature is stored in a database table along with the image itself (or a link to the image). Visual image retrieval is performed by searching for signatures in the database that are similar to the signature of the query image. The multi-level filtering reduces the number of candidate images, before a full comparison is done on the filtered-set of candidate image signatures. The first sub-filter performs a range-based query on a table of image attributes culled from the image signature, each attribute in this table is indexed. The results of the range-based sub-filter are processed by a functional predicate sub-filter which determines a distance measure of each resultant image from the query image. The results of the functional predicate sub-filter are compared, using full signature comparison logic, to the query image signature to determine whether the query image is similar to a visual image in the table.

Claims

1. A system for storing visual images comprising:

a store having a plurality of visual images held therein, each visual image having a respective computable visual image signature derived from a plurality of image primitives and a plurality of signature attributes derived from the visual image signature;

a query image having a respective computable query image signature derived from the plurality of the image primitives and a plurality of the signature attributes derived from the query image signature;

a visual image feature structure in the store having a plurality of containers for holding visual images, each contained including an identifier and the signature attributes for the respective visual image, each of the signature attributes for the respective visual image having an index;

a reduction filter that reduces the number of containers that are candidates for full comparison into a candidate result; and

an evaluator for performing the full comparison of the visual image signature of each stored visual image represented in the candidate result against the query image signature and returning a final result of the visual images that are similar to the query image;

wherein the reduction filter further comprises at least one of;

a range query filter that processes the visual image feature structure and produces an intermediate result of range query filtered containers whose signature attributes for the visual image represent a range into which the corresponding signature attributes for the query image fit; and

a functional predicate filter that processes the intermediate result of range query filtered containers and produces a candidate result of functional predicate filtered containers, the visual signature attributes of each container satisfying a distance measure when compared to the query image signature attributes.

2. The system of claim 1 wherein the store is a database, the feature structure, the intermediate result, and the candidate result are database tables and the container is a row within a database table.

3. The system of claim 1 wherein the signature attributes are grouped into primitive groups, each primitive group sensitive to a weighted selectivity factor during signature attribute comparisons.

4. The system of claim 1 wherein the index is a bitmap index.

5. The system of claim 1 further comprising an interface facilitating the creation of the index.

6. The system of claim 1 further comprising an interface facilitating the querying of the index, including a command to determine a similarity score representing the similarity between the query image and one of the stored visual images.

7. The system of claim 1 further comprising an interface facilitating an evaluation of similarity, including a command to determine similarity by comparing the similarity score and a user defined similarity threshold.

8. A system for storing visual images comprising:

a store having a plurality of visual images held therein, each visual image having a respective computable visual image signature derived from a plurality of image primitives and a plurality of signature attributes derived from the visual image signature;

a query image having a respective computable query image signature derived from the plurality of the image primitives and a plurality of the signature attributes derived from the query image signature;

a visual image feature structure in the store having a plurality of containers for holding visual images, each container including an identifier and the signature attributes for the respective visual image, each of the signature attributes for the respective visual image having an index;

a reduction filter that reduces the number of containers that are candidates for full comparison into a candidate result;

an evaluator for performing the full comparison of the visual image signature of each stored visual image represented in the candidate result against the query image signature and returning a final result of the visual images that are similar to the query image; and

an optimization module which determines conditions that indicate that at least a portion of the reduction filter should not be run and disables the respective portion of the reduction filter.

9. The system of claim 8 wherein the portion of the reduction filter is a functional predicate filter.

10. A method for storing visual images comprising:

(a) populating a store having a plurality of visual images stored therein, each visual image having a respective computable visual image signature derived from a plurality of image primitives and a plurality of signature attributes derived from the visual image signature;

(b) identifying a query image having a respective computable query image signature derived from the plurality of the image primitives and a plurality of the signature attributes derived from the query image signature;

(c) storing in a visual image feature structure of the store a plurality of containers representing visual images, each container including an identifier and the signature attributes for the respective visual image, each of the signature attributes for the respective visual image having an index;

(d) performing a range query filter that processes the visual image feature structure and produces an intermediate result of range query filtered containers whose signature attributes for the visual image represent a range into which corresponding the signature attributes for the query image fit;

(e) performing a functional predicate filter that processes the intermediate result of range query filtered containers and produces a evaluation result of functional predicate filtered containers, the visual signature attributes of each container satisfying a distance measure when compared to the query image signature attributes; and

(f) performing a full comparison of the visual image signature of each stored visual image represented in the evaluation result against the query image signature and returning a final result of the visual images that are similar to the query image.

11. The method of claim 10 further comprising grouping the signature attributes into primitive groups, each primitive group sensitive to a weighted selectivity factor during signature attribute comparisons.

12. The method of claim 10 wherein the index is a bitmap index.

13. The method of claim 10 further comprising optimizing the functional predicate filter such that conditions indicating when the functional predicate filter should not be run are determined and, under those conditions, the functional predicate filter is not run.

14. A computer program product comprising:

a computer usable medium for storing visual images;

a set of computer program instructions embodied on the computer usable medium, including instructions to;

populate a store having a plurality of visual images stored therein, each visual image having a respective computable visual image signature derived from a plurality of image primitives and a plurality of signature attributes derived from the visual image signature;

identify a query image having a respective computable query image signature derived from the plurality of the image primitives and a plurality of the signature attributes derived from the query image signature;

store in a visual image feature structure of the store a plurality of containers representing visual images, each container including an identifier and the signature attributes for the respective visual image, each of the signature attributes for the respective visual image having an index;

perform a range query filter that processes the visual image feature structure and produces an intermediate result of range query filtered containers whose signature attributes for the visual image represent a range into which corresponding the signature attributes for the query image fit;

perform a functional predicate filter that processes the intermediate result of range query filtered containers and produces a evaluation result of functional predicate filtered containers, the visual signature attributes of each container satisfying a distance measure when compared to the query image signature attributes; and

perform a full comparison of the visual image signature of each stored visual image represented in the evaluation result against the query image signature and returning a final result of the visual images that are similar to the query image.

15. The computer program product of claim 14 wherein the instructions further include instructions to:

group the signature attributes into primitive groups, each primitive group sensitive to a weighted selectivity factor during signature attribute comparisons.

16. The computer program product of claim 14 wherein the index is a bitmap index.

17. The computer program product of claim 14 wherein the instructions further include instructions to:

optimize the functional predicate filter such that conditions indicating when the functional predicate filter should not be run are determined and, under those conditions, the functional predicate filter is not run.

18. A system for filtering visual images represented by signature attributes with a query image represented by query image signature attributes, the system comprising:

a range query filter that processes the visual images and produces an intermediate result of a range query filtered visual images whose signature attributes for the visual images represent a range into which the corresponding query image signature attributes for the query image fit; and

a functional predicate filter that processes the intermediate result of range query filtered visual images and produces a candidate result of functional predicate filtered visual images, the signature attributes of each candidate visual image satisfying a distance measure when compared to the query image signature attributes.

19. A method for filtering visual images represented by signature attributes with a query image represented by query image signature attributes, comprising:

filtering the visual images using a range query filter to produce an intermediate result of range query filtered visual images whose signature attributes for the visual images represent a range into which the corresponding query image signature attributes for the query image fit; and

filtering the intermediate result of range query filtered visual images using a functional predicate filter to produce a candidate result of functional predicate filtered visual images, the signature attributes of each candidate visual image satisfying a distance measure when compared to the query image signature attributes.

20. A computer program product comprising:

a computer usable medium for filtering visual images represented by signature attributes;

a set of computer program instructions embodied on the computer usable medium, including instructions to;

filter the visual images using a range query filter to produce an intermediate result of range query filtered visual images whose signature attributes for the visual images represent a range into which the corresponding query image signature attributes for the query image fit; and

filter the intermediate result of range query filtered visual images using a functional predicate filter to produce a candidate result of functional predicate filtered visual images, the signature attributes of each candidate visual image satisfying a distance measure when compared to the query image signature attributes.