System for efficient content-based retrieval of images

Details System for efficient content-based retrieval of images System for efficient content-based retrieval of images

1999-06-10

2002-07-09

Metjahic, Safet (Department: 2175)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000, C382S115000, C382S209000, C382S220000, C382S224000, C345S419000, C345S215000

Reexamination Certificate

active

06418430

ABSTRACT:

BACKGROUND
Images are very useful in a variety of computer applications including medical applications where images can be used to identify specific anatomy and electronic sales catalogs applications where images can be used to display merchandise offered for sale. Additionally, images are useful in many document management applications to enhance document production, as well as in many other computer applications.
Traditionally images have been stored on computers individually in separate flat files of various formats, for example Bitmap (“BMP”), Graphics Interchange Format (“GIF”), Tagged Image File Format (“TIFF”), and Joint Photographic Experts Group (“JPEG”) format. More recently, database systems have added support for storing images through the implementation of binary large object (“BLOB”) datatypes. There are many advantages to managing images using a database system including, transaction control, backup/recovery, security and content-based searching.
Once images are stored in a database system it is desirable to retrieve them based upon their content. Various ways exists to do retrieval, including developing keywords to describe the image. For example, an image of a mountain landscape may be described by keywords such as “mountain”, “valley”, “snow caps”, and “cliffs”. One problem with keyword searching is that it is subjectively based upon the author of the keywords, so what one author calls a “hill” another may call a “mountain”. Users need tools to match the similarity of images such that images that “look alike” can be retrieved.
Image signatures, derived from basic visual primitives, can be produced to digitally describe and objectively compare images. Signatures can be compared for similarity, the comparison produces a numeric value between 0 (identical) and 100 (very dissimilar). It is up to the user to set an appropriate threshold to decide at what numeric value two images are similar. Signature comparison is a good technique to determine the similarity of two images, but a signature by signature comparison of all images is computationally expensive.
SUMMARY
The present system for content-based retrieval of images addresses the storage, indexing and retrieval of images in a computer storage system. More specifically, the present system relates to the efficient retrieval of selected images in a computer database system by comparing a query image to stored images. General database indexing techniques can be applied to benefit image retrieval.
In particular, the system provides efficient, content-based, searching of visual images through the use of storage indexes and multi-level filters. The image indexes are created from a set of indexable image attributes, these image attributes are derived from an image signature (indexing the image signature itself is not feasible due to its size and structure).
Visual image retrieval can be performed by searching for image signatures in storage structures, such as database tables, that are similar to the image signature of the query image. The process of retrieval incorporates a multi-level filter to reduce 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 having, for example, the rowid of the image row and image attributes derived 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 produce a determination as to whether the query image is similar to any visual image stored in the table.
An image (or a link to an image) can be stored in a database table along with the image's signature. A particular system for visual image indexing and retrieval comprises a database having multiple images stored therein, each visual image having a respective computable visual image signature. This signature is derived from image primitives. The image signature can be further acted upon to produce image signature attributes, these image signature attributes are indexable.
A second (query) image is used to compare against images stored in the database, the query image also having a computable query image signature derived from image primitives. A visual image feature table is created in the database having rows for representing visual images, each row including an identifier and the signature attributes for the respective visual image. Each of the signature attributes for the visual image have an index created upon it.
A range query filter processes the visual image feature table and produces an intermediate result of range query filtered rows whose signature attributes for the visual image represent a range into which corresponding the signature attributes for the query image fit. A functional predicate filter processes the intermediate result of range query filtered rows and produces an evaluation result of functional predicate filtered rows, each functional predicate filtered row satisfying a distance measure as compared to the respective stored visual image. An evaluator performs a full comparison on the visual image signature of each stored visual image represented in the evaluation result against the query image signature resulting in a determination of image similarity as defined by the user.
One embodiment of the present system produces an image signature from a visual image, derives image signature attributes of low cardinality from the image signature and creates an index for each image signature attribute. The resultant indices can be queried to produce an intermediate result of visual images, the intermediate result can be processed using a set of predicate functions to produce a candidate result and a final result of visual images can be determined by comparing the image signatures in the candidate result for similarity.


REFERENCES:
patent: 5647058 (1997-07-01), Agrawal et al.
patent: 5893095 (1999-04-01), Jain et al.
patent: 5893104 (1999-04-01), Srinivasan et al.
patent: 5911139 (1999-06-01), Jain et al.
patent: 5913205 (1999-06-01), Jain et al.
patent: 5915250 (1999-06-01), Jain et al.
patent: 6084595 (2000-07-01), Bach et al.
patent: 6181818 (2001-01-01), Sato et al.
Duda, R.O., et al., “Linear Properties,” InPattern Classification and Scene Analysis,Section 9.3.2, (NY:A. Wiley & Sons), pp. 345-348 (1973).

Affiliated with

Also associated with

Rating

System for efficient content-based retrieval of images does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System for efficient content-based retrieval of images, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for efficient content-based retrieval of images will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2876137