Method and system for searching for images based on color and shape of a selected image

• US 7,194,127 B2
• Filed: 08/02/2005
• Issued: 03/20/2007
• Est. Priority Date: 04/20/1999
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Brechner, Eric L.
• Primary Examiner(s): Bali; Vikkram
• Assistant Examiner(s): BHATNAGAR, ANAND P
• Application Number:
  US11/195,026
• Publication Number:
  US 20050265635A1
• Time in Patent Office: 595 Days
• Field of Search: 382/100, 382/162, 382/165, 707/3
• US Class Current: 382/165
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A method and system that allows a user to find images using a query by example is disclosed. Images similar to the selected image are retrieved based on color or shape. Each clip in a clip catalog is assigned a color metric and a wavelet, i.e., shape, metric. The selected clip is also assigned a color metric and a wavelet metric. Those clips that are most similar based on either the wavelet metric or the color metric are returned to the user.

Claims

1. A computer-implemented method for finding images, comprising:

computing a first set of signatures that describes shapes in a selected image, the first set of signatures being a set of largest coefficients of a wavelet transform for each color plane of the selected image without calculating types of quantized coefficients;

computing a second signature that describes colors in the selected image; and

finding images that are similar to the selected image using the first set of signatures and the second signature.

2. The method of claim 1, further comprising storing standard color space weight values in an array for retrieval, the array being a table of weights for each color channel.

3. The method of claim 2, wherein the act of computing the first set of signatures includes computing a wavelet signature and storing the wavelet signature for the selected image.

4. The method of claim 1, wherein the acts of computing the first set of signatures and the second signature are executed at any time for all images stored in an image catalog.

5. The method of claim 1, wherein the acts of computing the first set of signatures and the second signature occur whenever an image is added to a clip catalog.

6. The method of claim 1, wherein the acts of computing the first set of signatures and the second signature occur whenever an image in a clip catalog is modified.

7. A computer-readable medium having computer-executable instructions stored thereon for implementing a method for finding images, comprising:

computing a first signature that describes shapes in a selected image without computing quantized coefficients for each subband separately;

computing a second signature that describes colors in the selected image using a color cross correlation matrix which specifies weighted values; and

finding images that are similar to the selected image using the first signature and the second signature.

8. The computer-readable medium of claim 7, further comprising storing standard color space weight values in an array for retrieval, the array being a table of weights for each color channel.

9. The computer-readable medium of claim 8, wherein the act of computing the first signature includes computing a wavelet signature and storing the wavelet signature for the selected image.

10. The computer-readable medium of claim 7, wherein the acts of computing the first signature and the second signature are executed at any time for all images stored in an image catalog.

11. The computer-readable medium of claim 7, wherein the acts of computing the first signature and the second signature occur whenever an image is added to a clip catalog.

12. The computer-readable medium of claim 7, wherein the acts of computing the first signature and the second signature occur whenever an image in a clip catalog is modified.

13. A computer-implemented method for finding images, comprising:

computing a wavelet decomposition that contains coefficients for a selected image without using Daubechies orthonormal wavelet filter to obtain subbands;

deriving signatures that describe shapes of the selected image from the coefficients;

computing an image querying metric from the signatures by truncating the coefficients to retain those with the largest magnitude for each color channel; and

comparing a number of coefficients a query has in common with target images to find desired images by storing the number of coefficients in a sorted array and linearly comparing the number of coefficients.

14. The method of claim 13, wherein the act of computing the wavelet decomposition includes centering the selected image on a field, the field being white and its dimensions being about 128 pixels by 128 pixels.

15. The method of claim 14, wherein the act of computing the wavelet decomposition includes converting the selected image to a standard color space, wherein the standard color space includes a color space uses by broadcast television.

16. The method of claim 15, wherein the act of computing the wavelet decomposition includes rescaling the colors to produce normalized values.

17. The method of claim 16, wherein the act of computing the wavelet decomposition includes performing a wavelet transform on the normalized values.

18. The method of claim 17, wherein the act of computing the wavelet decomposition includes determining the number of the largest coefficients by using magnitude for each color plane.

19. The method of claim 18, wherein the act of computing the wavelet decomposition includes truncating a sequence of coefficients to retain coefficients with the largest magnitude.

20. The method of claim 19, wherein the act of computing the wavelet decomposition includes encoding row and column locations of coefficients by increasing the resolution.