Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-11-20
2001-05-01
Amsbury, Wayne (Department: 2771)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06226636
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is directed to a system which builds a database of images, which retrieves images from the database based on a “query” image, and which determines whether the retrieved images are similar to the query image. In building the database, the system generates binary representations for regions of an image, and then uses these binary representations to store pointers to the image in binary trees. In retrieving images from the database, the system generates binary representations of the query image, selects an image from the database by traversing its binary trees using the binary representations, and retrieves pointers for the image from the binary trees.
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 tile 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 a 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.
In view of the foregoing, researchers have developed systems for selecting and retrieving an image based on its content. In general, these systems operate by inputting a “query” image, such as an individual frame of digital video, a scanned image, or the like, determining which image in a database is similar to the query image, and then retrieving that image. Conventional systems of this type, however, suffer from several drawbacks, particularly with respect to operational speed.
Specifically, conventional content-based image retrieving systems tend to be relatively slow. That is, conventional systems typically rely on some form of feature extraction and comparison in order to determine which images in the database are similar to the query image. While such comparisons can provide accurate results, they require a significant amount of processing, particularly in cases where the images have a relatively high resolution, or where there are numerous comparisons to be made. This excess processing significantly slows down the process.
Accordingly, there exists a need for a content-based image retrieval system that addresses the foregoing and other drawbacks of conventional systems. In particular, there exists a need for a system which provides for accurate content-based image retrieval, and which also operates more quickly than its conventional counterparts.
SUMMARY OF THE INVENTION
The present invention addresses the foregoing needs by building a database of images using binary representations of the images' histograms, and then determining which image(s) in the database are similar to a query image by traversing the database using a binary representation of the query image. By using binary representations of the images to build the database and to determine similar images, the invention reduces the amount of processing required to retrieve images based on their content. As a result, the invention operates more quickly than its conventional counterparts.
Thus, according to one aspect, the present invention is a system (e.g., a method, an apparatus, and computer-executable process steps) for building a database which stores data corresponding to a plurality of images. The system begins by dividing each image into N (N≧1) regions. Thereafter, for each of the N regions of an image, the system calculates a histogram of the region, generates a binary representation of the histogram, and stores data corresponding to the image in a binary tree based on the binary representation.
In preferred embodiments of the invention, the system calculates the histogram for the region based on color image data in the region, and generates the binary representation by performing a Haar transform on the histogram to generate wavelet coefficients therefor and then quantizing the coefficients. By virtue of these features of the invention, it is possible to generate a substantially unique binary representation of each image, thereby eliminating the need to store excessive amounts of data in the database. As a result, databases can be generated which contain data for a relatively large number of images, and which can be traversed relatively quickly without sacrificing accuracy.
In other preferred embodiments of the invention, the system stores the data in the binary tree by comparing at least some bits in the binary representation to corresponding nodes up to a current node in the binary tree, and then determining whether the current node in the binary tree stores data for more than a predetermined number of images. In a case that the current node in the binary tree stores data for more than the predetermined number of images, the invention splits the current node into two subsequent nodes, and stores the data in subsequent nodes. On the other hand, in a case that the current node in the binary tree stores data for less than or equal to the predetermined number of images, the invention stores the data at the current node in the binary tree. By virtue of these features, it is possible to build the database adaptively, such that data can be stored at fewer nodes. As a result, smaller binary trees can be generated, thereby decreasing the size of the database and, consequently, the time that it takes to traverse the database.
According to another aspect, the present invention is a system that determines which images in a database are similar to a query image, where the database is comprised of N (N≧1) binary trees, and where each of the N binary trees stores data corresponding to one or more predetermined images. Specifically, the system divides the query image into N regions, each of which corresponds to one of the N binary trees, and retrieves data corresponding to one or more predetermined images from the binary trees corresponding to the N regions. Thereafter, the system determines which of the predetermined images is similar to the query image based on the retrieved data. By using binary trees and binary representations of image regions, this aspect of the invention reduces the time that it takes to determine which of the images in the database are similar to the query image. By reducing this time, the invention also reduces the overall the amount of time that it takes to retrieve such an image from memory.
In preferred embodiments of the invention, the data corresponding to the predetermined images comprises pointers to the predetermined images in memory. In these embodiments, the system determines which of the predetermined images is similar to the query image based on which pointers were retrieved. Specifically, the predetermined image for which a most number of pointers was retrieved is determined to be the most similar to the query image among the images in the database.
In other preferred embodiments, the system determines which of the predetermined images is similar to the query image by identifying candidate images among the predetermined images that could correspond to the query image, ranking the candidate images in order from an image most likely to correspond to the query image to an image least likely to correspond to the query image, and displaying a list of the ranked candidate images. By virtue of these features, the invention provides a ranked list of candidate images to the user. The user may then view and select
Abdel-Mottaleb Mohamed
Krishnamachari Santhana
Amsbury Wayne
Pardo Thuy
Philips Electronics North America Corp.
Thorne Gregory L.
LandOfFree
System for retrieving images using a database 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 retrieving images using a database, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for retrieving images using a database will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2556303