US 6,477,269 B1Granted

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

AssigneeMicrosoft Corporation

InventorEric L. Brechner

Life of this patent

Estimating the term…

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.

Claims61

Dependent claims

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.

23 more elements

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.

26 more elements

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.

19 more elements

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.

22 more elements

Dependencies are inferred from the claim text.

patentgrep

Loading patent…

Abstract

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.

23 more elements