Methods of imaging based on wavelet retrieval of scenes

Details Methods of imaging based on wavelet retrieval of scenes Methods of imaging based on wavelet retrieval of scenes

1999-08-10

2004-06-15

Mariam, Daniel G. (Department: 2621)

Image analysis

Image transformation or preprocessing

Image storage or retrieval

C382S173000, C382S190000, C382S205000, C382S209000, C382S218000, C382S225000, C358S403000, C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

06751363

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to methods of content-based imaging. More specifically, the invention relates to content-based imaging effected by decomposing an image into a series of regions and extracting the image by comparing the regions to similar regions of stored images.
2. Description of the Related Art
Modern computers have developed increased processor speeds, improved graphics capabilities and advanced image processing which have all helped to make digital images easily viewable. The Internet has greatly proliferated the need for fast and accurate downloading of digital images and, consequently, applications requiring content-based querying and searching of images are now ubiquitous in data mining techniques, multimedia messaging, medical imaging, weather prediction, insurance, television production, satellite image databases and E-commerce applications, for example.
Traditionally, the retrieval of images that match a query image from a large database of images has heretofore been accomplished by computing a feature signature for each query image, mapping all signatures to d-dimensional points in some metric space, and building an index on all signatures for fast retrieval. In this method, an appropriate distance function, for example a Euclidean distance, is defined for each pair of signatures. Then, given a query, the index is used to locate signatures close to the query point. The set of images corresponding to the signatures, which constitutes the result of the query, are then returned.
Typical methods of computing signatures utilize color histograms to characterize the color composition of an image without regard to of its scale or orientation. The problem with color histograms, however, is that they do not contain any shape, location or texture information. As a result, two images with similar color composition may in fact contain very different shapes and thus be completely unrelated semantically. In order to alleviate this problem, prior imaging techniques define separate distance functions for color, shape and texture and subsequently combine them to derive the overall result. An alternate approach to solving this problem is to use the dominant wavelet coefficients for an image as its signature. Since wavelets capture shape, texture and location information in a single unified framework, their use tends to ameliorate some of the problems associated with prior imaging algorithms.
The above-mentioned schemes for imaging typically do not work well since they compute a single signature for the entire image. As a result, they usually fail when images contain similar objects having different locations and/or varying sizes. These algorithms simply fail with respect to scaling and translation of objects within images because a single signature computed for the whole image cannot sufficiently capture the important properties of individual objects. It would therefore be desirable to provide a system that is more robust with respect to resolution changes, dithering effects, color shifts, orientation, size and location for the whole image as well as for individual objects within the whole image.
Other segmentation strategies for decomposing images into their individual objects have been proposed. Approaches that involve manual extraction of regions from an image are extremely time-consuming and are therefore impractical for large image collections. Thus, most prior image segmentation techniques rely on being able to identify region boundaries, sharp edges between objects, and a number of other factors such as color, shape and connectivity. Besides being computationally expensive, these techniques are frequently inaccurate in identifying objects and are generally not robust with respect to object granularity. Since the definition of an object is largely subjective, a single method cannot successfully identify the correct objects for all applications and usually decomposes what the user of the system perceives as a single object into several smaller objects. Moreover, these kinds of image segmentation techniques utilize domain-specific constraints and are, at best, application specific.
There accordingly exists long-felt, but unfulfilled, needs in the art for imaging techniques that can resolve images across a wide spectrum of image domains. These methods should be computationally efficient and able to resolve images containing similar objects at different locations and of varying sizes. It would also be desirable if such imaging techniques and methods were robust with respect to resolution changes, dithering effects, color shifts, orientation, size and location both with regard to the entire image as well as individual objects within the image. Such results have not heretofore been achieved in the art.
SUMMARY OF THE INVENTION
The aforementioned long-felt needs are met, and problems solved, by the methods of imaging objects provided in accordance with the present invention. The inventive methods improve on prior imaging techniques by increasing the granularity of the query image, constructing multiple signatures based on multiple regions of the query image, and applying a wavelet transformation to the multiple regions to decompose the signatures into feature vectors or sets that can be matched to multiple regions of target images. This allows fast and robust decorrelation of the data in the regions which causes the algorithms that implement the methods of the present invention to be computationally efficient.
In a preferred embodiment, the inventive methods utilize Haar wavelets to compute the feature signatures of the regions since they efficiently represent functions as a coarse overall approximation together with detail coefficients that influence the function at various scales. Haar wavelets have been found to be the fastest to compute and therefore speed up the overall computation tasks of the inventive methods. Other wavelet representations are also usable in accordance with the present invention, but the inventors have found that Haar wavelets provide the best image matching results in a computationally acceptable amount of time.
Methods of imaging based on wavelet retrieval of scenes disclosed and claimed herein efficiently and effectively compute fixed-size, low-dimensional feature signatures independent of resolution, image size and dithering effects. The inventive methods are computationally inexpensive and so can be run with the appropriate software on general purpose digital computers. Additionally, the algorithms that implement wavelet retrieval in accordance with the invention are very fast as compared to prior imaging techniques and are able to differentiate and image objects containing complex colors, textures and shapes, as well as multiple images within an object. Such results have not heretofore been achieved in the art.


REFERENCES:
patent: 5819288 (1998-10-01), De Bonet
patent: 5899999 (1999-05-01), De Bonet
patent: 6182069 (2001-01-01), Niblack et al.
patent: 6226636 (2001-05-01), Abdel-Mottaleb et al.
patent: 6240423 (2001-05-01), Hirata
patent: 6285995 (2001-09-01), Abdel-Mottaleb et al.
patent: 6347313 (2002-02-01), Ma et al.
patent: 6389169 (2002-05-01), Stark et al.
patent: 6389417 (2002-05-01), Shin et al.
patent: 6463426 (2002-10-01), Lipson et al.
Remias, et al “Block-Oriented Image Decomposition and Retrieval in Image Databse Systems”, IEEE, 1996, PP. 85-92.*
Carson, et al “Region-Based Image Querying”, IEEE, 1997, PP. 42-49.*
Yue, et al “Texture Image Retrieval by Universal Classification for Wavelet Transform Coefficients”, IEEE, PP. 220-223.*
Wang, et al “Wavelet-Based Image Indexing Techniques with Partial Sketch Retrieval Capability”, IEEE, 1997, PP. 13-24.*
Servetto, et al “A Successively Refinable Wavelet-Based Representation for Content-Based Image Retrieval”, IEEE, 1997, PP. 325-330.*
Eakins, et al “Similarity Retrieval of Trademark Images”, IEEE, 1998, PP. 53-63.*
Deng, et al “An Efficient Low-Dimensional Color Indexing Scheme for Region-Based Image Retrieval”, IEEE, Mar.

Affiliated with

Also associated with

Rating

Methods of imaging based on wavelet retrieval of scenes does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Methods of imaging based on wavelet retrieval of scenes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods of imaging based on wavelet retrieval of scenes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3344385