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

• US 6,477,269 B1
• Filed: 04/20/1999
• Issued: 11/05/2002
• Est. Priority Date: 04/20/1999
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Brechner, Eric L.
• Primary Examiner(s): Mancuso, Joseph
• Assistant Examiner(s): BHATNAGAR, ANAND P
• Application Number:
  US09/295,018
• Time in Patent Office: 1,295 Days
• Field of Search: 382/248, 382/165, 382/305, 382/167, 382/168, 382/170, 382/206, 382/190, 382/306, 382/203, 707/1, 707/2, 707/6
• 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 method for finding images in an image catalog that are similar to a selected image, comprising:

(a) determining a wavelet signature for the selected image by;

(i) performing a wavelet transform on the selected image to determine the coefficients of the color planes of the selected image;

(ii) selecting a predetermined number of coefficients for each color plane based on the magnitude of the coefficients;

(iii) encoding said selected coefficients by ordering said coefficients in a shell matrix based on wavelet resolution;

(iv) encoding the signs of said selected coefficients by ordering said signs in said shell matrix in accordance with said wavelet resolution;

(v) storing the selected, encoded coefficients in a sorted array; and

(vi) storing the encoded signs of said selected coefficients as the wavelet signature of the selected image;

(b) determining a color signature for the selected image;

(c) for each image in the image catalog;

(i) determining a wavelet signature for the catalog image by;

(aa) performing a wavelet transform on the catalog image to determine the coefficients of the color planes of the catalog image;

(bb) selecting a predetermined number of coefficients for each color plane based on the magnitude of the coefficients;

(cc) encoding said selected coefficients by ordering said coefficients in a shell matrix based on wavelet resolution;

(dd) encoding the signs of said selected coefficients by ordering said signs in said shell matrix in accordance with said wavelet resolution;

(ee) storing the selected, encoded coefficients in a sorted array; and

(ff) storing the encoded signs of said selected coefficients as the wavelet signature of the catalog image;

(ii) determining a color signature for the catalog image;

(iii) determining a wavelet metric by;

(aa) comparing the wavelet signature for the selected image to the wavelet signature for the catalog image; and

(bb) based on the comparison, computing, for each color plane, a wavelength metric by totalizing the value of the selected coefficients for the color plane and dividing the result by the value of the selected coefficients that match the coefficients of the selected image for the same color plane;

(iv) computing a color metric by comparing the color signature for the selected image to the color signature for the catalog image; and

(d) returning to a user the images found in the image catalog that most closely match the selected image based on the wavelet metric and the color metric.

2. The method of claim 1, further comprising:

(a) storing the larger of the color metric and the wavelet metric for each image in the image catalog; and

(b) the images returned to the user comprising a plurality of catalog images with the largest stored metrics.

3. The method of claim 2, wherein the images that are returned to the user have a metric value that exceeds a threshold value.

4. The method of claim 2, wherein there is a predetermined number for the plurality of catalog images that are returned to the user.

5. The method of claim 4, wherein the predetermined number of images to be returned to the user is no more than 60.

6. The method of claim 1, wherein the wavelet transform is a standard Haar transform.

7. The method of claim 1, wherein the plurality of the largest coefficients is no more than 40 of the largest coefficients.

8. The method of claim 1, further comprising ignoring coefficients less than a threshold value.

9. The method of claim 1, further comprising prior to performing a wavelet transform to determine the wavelet signature for both the selected image and the catalog image:

(a) centering the image on a field;

(b) converting the image to a standard color space; and

(c) normalizing the colors into color planes.

10. The method of claim 9, wherein the field is white.

11. The method of claim 9, wherein the standard color space is YIQ.

12. The method of claim 9, wherein normalizing the colors comprises scaling colors to vary from 0-1.

13. The method of claim 1, wherein determining a color signature for both the selected image and the catalog image comprises:

(a) accumulating image pixels in a plurality of buckets based on the color of the pixel;

(b) computing a percentage of pixels accumulated in each bucket;

(c) selecting a predetermined number of buckets based on the largest percentages;

(d) encoding the results of the selection; and

(e) storing the results of the encoding as the color signature of the image.

14. The method of claim 13, further comprising prior to accumulating image pixels in a plurality of buckets based on the color of the pixel for both the selected image and the catalog image:

(a) blurring the image; and

(b) converting the image to a standard color space.

15. The method of claim 14, wherein blurring the image is performed using a 3×

3 kernel.

16. The method of claim 14, wherein the standard color space is HSV.

17. The method of claim 13, further comprising ignoring colors with a percentage below a threshold value.

18. The method of claim 13, including applying weighting factors to color matches and matches of similar colors when accumulating image pixels in a plurality of buckets based on the color of the pixel.

19. The method of claim 18, wherein color matches are exact color matches.

20. The method of claim 13, wherein the color signature for the selected image is compared to the color signature for the catalog image by:

(aa) summing the minimum coverage times a color weight value for all pairs of colors in the images; and

(bb) raising the resulting color weight sum by a power that creates a color metric that is normalized to said wavelet metric.

21. A computer-readable medium having computer-executable instructions for performing the method recited in any one of claims 1, 9, 13, and 20.

22. A system for finding images in an image catalog that are similar to a selected image, comprising:

(a) a processing unit; and

(b) a storage medium coupled to the processing unit, the storage medium storing program code implemented by the processing unit for;

(i) determining a wavelet signature for the selected image by;

(aa) performing a wavelet transform on the selected image to determine the coefficients of the color planes of the selected image;

(bb) selecting a predetermined number of coefficients for each color plane based on the magnitude of the coefficients;

(cc) encoding said selected coefficients by ordering said coefficients in a shell matrix based on wavelet resolution;

(dd) encoding the signs of said selected coefficients by ordering said signs in said shell matrix in accordance with said wavelet resolution;

(ee) storing the selected, encoded coefficients in a sorted array; and

(ff) storing the encoding signs of said selected coefficients as the wavelet signature of the selected image;

(ii) determining a color signature for the selected image;

(iii) for each image in the image catalog;

(aa) determining a wavelet signature for the catalog image by;

i) performing a wavelet transform on the catalog image to determine the coefficients of the color planes of the catalog image;

ii) selecting a predetermined number of coefficients for each color plane based on the magnitude of the coefficients;

iii) encoding said selected coefficients by ordering said coefficients in a shell matrix based on wavelet resolution;

iv) encoding the signs of said selected coefficients by ordering said signs in said shell matrix in accordance with said wavelet resolution;

v) storing the selected, encoded coefficients in a sorted array; and

vi) storing the encoded signs of said selected coefficients as the wavelet signature of the catalog image;

(bb) determining a color signature for the catalog image;

(cc) determining a wavelet metric by;

i) comparing the wavelet signature for the selected image to the wavelet signature for the catalog image; and

ii) based on the comparison, computing, for each color plane, a wavelength metric by totalizing the value of the selected coefficients for the color plane and dividing the result by the value of the selected coefficients that match the coefficients of the selected image for the same color plane;

(dd) computing a color metric by comparing the color signature for the selected image to the color signature for the catalog image; and

(iv) returning to a user the images found in the image catalog that most closely match the selected image based on the wavelet metric and the color metric.

23. The system of claim 22, wherein the program code implemented by the processing unit further:

(a) stores the larger of the color metric and the wavelet metric for each image in the image catalog; and

(b) returns to the user a plurality of catalog images with the largest stored metrics.

24. The system of claim 23, wherein the images that are returned to the user have a metric value that exceeds a threshold value.

25. The system of claim 23, wherein there is a predetermined number for the plurality of catalog images that are returned to the user.

26. The system of claim 25, wherein the predetermined number of images to be returned to the user is no more than 60.

27. The system of claim 22, further comprising prior to performing a wavelet transform to determine the wavelet signature for both the selected image and the catalog image:

(a) centering the image on a field;

(b) converting the image to a standard color space; and

(c) normalizing the color into color planes.

28. The system of claim 27, wherein the field is white.

29. The system of claim 27, wherein the standard color space is YIQ.

30. The system of claim 27, wherein normalizing the colors comprises scaling colors to vary from 0-1.

31. The system of claim 22, wherein the wavelet transform is a Haar transform.

32. The system of claim 22, wherein the plurality of the largest coefficients is no more than 40 of the largest coefficients.

33. The system of claim 22, further comprising ignoring coefficients less than a threshold value.

34. The system of claim 22, wherein determining a color signature for both the selected image and the catalog image comprises:

(a) accumulating image pixels in a plurality of buckets based on the color of the pixel;

(b) computing a percentage of pixels accumulated in each bucket;

(c) selecting a predetermined number of buckets based on the largest percentages;

(d) encoding the results of the selection; and

(e) storing the results of the encoding or the color signature of the image.

35. The system of claim 34, further comprising prior to accumulating image pixels in a plurality of buckets based on the color of the pixel for both the selected image and the catalog image:

(a) blurring the image; and

(b) converting the image to a standard color space.

36. The system of claim 35, wherein blurring the image is performed using a 3×

3 kernel.

37. The system of claim 35, wherein the standard color space is HSV.

38. The system of claim 35, further comprising ignoring colors with a percentage below a threshold value.

39. The system of claim 35, including applying weighting factors to color matches and matches of similar colors when accumulating image pixels in a plurality of buckets based on the color of the pixel.

40. The system of claim 39, wherein color matches are exact color matches.

41. The system of claim 34, wherein the color signature for the selected image is compared to the color signature for the catalog image by:

(aa) summing the minimum coverage times a color weight value for all pairs of colors in the images; and

(bb) raising the resulting color weight sum by a power that creates a color metric that is normalized to said wavelet metric.

42. A method for finding images in an image catalog that are similar to a selected image, comprising:

(a) determining a wavelet signature for the selected image;

(b) determining a color signature for the selected image by;

(i) accumulating image pixels in a plurality of buckets based on the color of the pixel;

(ii) computing a percentage of pixels accumulated in each bucket;

(iii) selecting a plurality of buckets based on the largest percentages;

(iv) encoding the results of the selection; and

(v) storing the results of the encoding as the color signature of the selected image.

(c) for each image in the image catalog;

(i) determining a wavelet signature for the catalog image;

(ii) determining a color signature for the catalog image by;

(aa) accumulating image pixels in a plurality of buckets based on the color of the pixel;

(bb) computing a percentage of pixels accumulated in each bucket;

(cc) selecting a predetermined number of buckets based on the largest percentages;

(dd) encoding the results of the selection; and

(ee) storing the results of the encoding as the color signature of the catalog image;

(iii) computing a wavelet metric by comparing the wavelet signature for the selected image to the wavelet signature for the catalog image; and

(iv) computing a color metric by comparing the color signature for the selected image to the color signature for the catalog image; and

(d) returning to a user the images found in the image catalog that most closely match the selected image based on the wavelet metric and the color metric.

43. The method of claim 42, further comprising:

(a) storing the larger of the color metric and the wavelet metric for each image in the image catalog; and

(b) the images returned to the user comprising a plurality of catalog images with the largest stored metrics.

44. The method of claim 42, wherein the images that are returned to the user have a metric value that exceeds a threshold value.

45. The method of claim 42, including applying a weighting factor to exact color matches and matches of similar colors when accumulating image pixels in a plurality of buckets based on the color of the pixel.

46. The method of claim 45, wherein color matches are exact color matches.

47. The method of claim 42, wherein the color signature for the selected image is compared to the color signature for the catalog image by summing the minimum coverage times a color weight value for all pairs of colors in the images to create a color metric.

48. The method of claim 42, further comprising prior to accumulating image pixels in a plurality of buckets based on the color of the pixel for both the selected image and the catalog image:

(a) blurring the image; and

(b) converting the image to a standard color space.

49. The method of claim 48, wherein blurring the image is performed using a 3×

3 kernel.

50. The method of claim 48, wherein the standard color space is HSV.

51. The method of claim 48, further comprising ignoring colors with a percentage below a threshold value.

52. A computer-readable medium having computer-executable instructions for performing the method recited in any one of claims 42, 48, and 47.

53. A system for finding images in an image catalog that are similar to a selected image, comprising:

(a) a processing unit; and

(b) a storage medium coupled to the processing unit, the storage medium storing program code implemented by the processing unit for;

(i) determining a wavelet signature for the selected image;

(ii) determining a color signature for the selected image by;

(aa) accumulating image pixels in a plurality of buckets based on the color of the pixel;

(bb) computing a percentage of pixels accumulated in each bucket;

(cc) selecting a plurality of buckets based on the largest percentages;

(dd) encoding the results of the selection; and

(ee) storing the results of the encoding as the color signature of the selected image;

(iii) for each image in the image catalog;

(aa) determining a wavelet signature for the catalog image;

(bb) determining a color signature for the catalog image by;

i) accumulating image pixels in a plurality of buckets based on the color of the pixel;

ii) computing a percentage of pixels accumulated in each bucket;

iii) selecting a predetermined number of buckets based on the largest percentages;

iv) encoding the results of the selection; and

v) storing the results of the encoding as the color signature of the catalog image;

(cc) computing a wavelet metric by comparing the wavelet signature for the selected image to the wavelet signature for the catalog image; and

(dd) computing a color metric by comparing the color signature for the selected image to the color signature for the catalog image; and

(iv) returning the images found in the image catalog that most closely match the selected image based on the wavelet metric and the color metric to a user.

54. The system of claim 53, wherein the program code implemented by the processing unit further:

(a) stores the larger of the color metric and the wavelet metric for each image in the image catalog, and

(b) returns to the user a plurality of catalog images with the largest stored metrics.

55. The system of claim 54, wherein the images that are returned to the user have a metric value that exceeds a threshold value.

56. The system of claim 53, further comprising prior to accumulating image pixels in a plurality of buckets based on the color of the pixel for both the selected image and the catalog image:

(a) blurring the image; and

(b) converting the image to a standard color space.

57. The system of claim 56, wherein blurring the image is performed using a 3×

3 kernel.

58. The system of claim 56, wherein the standard color space is HSV.

59. The system of claim 56, further comprising ignoring colors with a percentage below a threshold value.

60. The system of claim 53, including applying a weighting factor to exact color matches and matches of similar colors when accumulating image pixels in a plurality of buckets based on the color of the pixel.

61. The system of claim 60, wherein color matches are exact color matches.