Region-based image archiving and retrieving system

Details Region-based image archiving and retrieving system Region-based image archiving and retrieving system

1999-01-15

2002-12-31

Kindred, Alford W. (Department: 2172)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C345S440000

Reexamination Certificate

active

06502105

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is directed to a system which builds a database of image graphs, and which retrieves images that are similar to a “query” image using this database. Specifically, the invention generates graphs of images based on homogeneous regions thereof, and stores these graphs in the database, together with pointers to the images. The invention then generates a similar graph for the query image, and compares the query image graph to the graphs in the database. Those graphs in the database that are similar to the query image graph are identified, and their corresponding images retrieved.
2. Description of the Related Art
In recent years, it has become commonplace for personal computers and other digital hardware to process and display digital images. This is due, in no small part, to the increase in popularity of digital video on the Internet. As a result of this increased use of digital imagery, it has become necessary to retrieve images from increasingly larger image databases. This typically does not present a problem if there is some way to readily identify the images, such as via a file name or the like.
On the other hand, it is more difficult to retrieve images from a large database if the only way to retrieve the images is based on their content, as is oftentimes the case, e.g., for digital video and for scanned images. For example, a user may wish to locate a video clip based on a single frame of video, or to locate particular frame of video within a video clip. Similarly, a user may wish to determine which of a plurality of pre-stored images best matches a scanned image. In these cases, image retrieval can be difficult.
Current methods of retrieving images, such as frames of video, from a database involve labeling the individual frames, and then searching through the frames manually for particular frames based on these labels. As might be expected, this process is both time consuming and inefficient. Automated content-based image retrieval systems exist. However, these systems are often slow due to the amount of processing required, and often produce erroneous results, particularly for images having different orientations, rotations, scaling, translations, and aspect ratio variations.
Accordingly, there exists a need for an automated content-based image retrieval system that addresses these and other drawbacks of conventional systems. In particular, there exists a need for a system which provides for content-based image retrieval that is both accurate and fast.
SUMMARY OF THE INVENTION
The present invention addresses the foregoing needs by providing a method of building a database from which images, such as frames of video, can be retrieved based on their content. In more detail, the invention inputs images, divides the images into one or more regions based on one or more attributes of the image, such as color, texture, etc., and generates a graph of the regions. This graph is then stored in the database, together with a pointer to the image. This database can then be used to retrieve one or more images (e.g., frames of video) that are similar to an input, or “query” image.
To this end, the invention performs substantially the same processing on the query image as that performed to generate the graphs in the database. That is, the invention divides the query image into regions based on one or more attributes of the image, and generates a graph based on the regions. Thereafter, the graph for the query image is compared to graphs in the database. Images are then retrieved whose graphs have at least a predetermined level of similarity to the “query image” graph. Alternatively, the system retrieves a fixed number of the most similar images, such as the ten images whose graphs are most similar to the query image graph.
By virtue of the foregoing, the present invention provides a way to retrieve images based on content that operates automatically, rather than manually. In other words, the invention eliminates the necessity of physically labeling images, such as frames of video, and then manually “flipping through” those images to locate an image that is similar to a query image. Moreover, because the invention compares image graphs, and particularly features thereof, the invention is able to determine whether two images are similar regardless of image orientation, rotation, scaling, translation, and aspect ratio variations.
Thus, according to one aspect, the present invention is a system (i.e., a method, an apparatus, and computer-executable process steps) for building a database of image-related data. The system inputs a plurality of images, such as key frames of a video sequence. For each input image, the system divides (or “segments”) the image into N
1
(N
1
≧1) regions which are substantially homogenous with respect to one or more attributes of the image, and generates a graph based on M
1
(M
1
≧1) of the N
1
regions, where M
1
may, or may not, equal N
1
. The system then stores data for the graph in the database.
According to another aspect, the invention is a system which uses graphs corresponding to a plurality of images to determine whether a query image is similar to one or more of the plurality of images. In operation, the system inputs the query image, divides the query image into N
2
(N
2
≧1) regions which are substantially homogenous with respect to one or more attributes of the query image, and generates a graph based on M
2
(M
2
≧1) of the N
2
regions, where one or more individual values of N
1
, N
2
, M
1
and M
2
may or may not be equal. The system then compares the generated graph to other graphs in a database that correspond to the plurality of images, and retrieves one or more images having graphs that substantially correspond to the graph of the query image.
This brief summary has been provided so that the nature of the invention may be understood quickly. A more complete understanding of the invention can be obtained by reference to the following detailed description of the preferred embodiment thereof in connection with the attached drawings.


REFERENCES:
patent: 5544267 (1996-08-01), Mahoney et al.
patent: 5751286 (1998-05-01), Barber et al.
patent: 5751852 (1998-05-01), Marimont et al.
patent: 5893095 (1999-04-01), Jain et al.
patent: 5974201 (1999-10-01), Chang et al.
patent: 6121969 (2000-09-01), Jain et al.
patent: 6240424 (2001-05-01), Hirata
PHA 23,390—U.S. patent application Ser. No. 09/062,940, filed Apr. 20, 1999.
Park et al., “Models and Algorithms for Efficient Color Image Indexing”, Proceedings, IEEE Workshop on Content-Based Access of Image and Video Libraries, Cat. No. 97TB100175, Jun. 20, 1997, pp. 36-41, XP002143808.
Doulamis et al., “A Pyramid Graph Representation for Efficient Image Content Description”, 1999 IEEE Third Workshop on Multimedia Signal Processing, Cat. No. 99TH8451, Sep. 1999, pp. 109-114, XP002143809.

Affiliated with

Also associated with

Rating

Region-based image archiving and retrieving system does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Region-based image archiving and retrieving system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Region-based image archiving and retrieving system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2984955