Detecting duplicate images using hash code grouping

• US 7,647,331 B2
• Filed: 03/28/2006
• Issued: 01/12/2010
• Est. Priority Date: 03/28/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Li, Mingjing, Wang, Bin, Li, Zhiwei
• Primary Examiner(s): Vital; Pierre M
• Assistant Examiner(s): Mitiku; Berhanu
• Application Number:
  US11/277,727
• Publication Number:
  US 20070239756A1
• Time in Patent Office: 1,386 Days
• Field of Search: None
• US Class Current: 382/218
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A duplicate image detection system generates an image table that maps hash codes of images to their corresponding images. The image table may group images according to their group identifiers generated from the most significant elements of the hash codes based on significance of the elements in representing an image. The image table thus segregates images by their group identifiers. To detect a duplicate image of a target image, the detection system generates a target hash code for the target image. The detection system then identifies the group of the target image based on the group identifier of the target hash code. After identifying the group identifier, the detection system searches the corresponding group table to identify hash codes that have values that are similar to the target hash code. The detection system then selects the images associated with those similar hash codes as being duplicates of the target image.

Claims

1. A computer system with a processor for detecting similar images, comprising:

a generate code component that generates a code for an image, the code having elements whose values are derived from features of the image, the elements having varying levels of significance such that similar images have similar codes with the most significant elements having the same values, the code being generated by creating a feature vector of a certain dimension that represents the image, reduces the dimension of the feature vector, and creates a code from the reduced feature vector with the reduced dimension;

an image table that groups images based on having the same values for the most significant elements; and

a detection component that uses the generate code component to generate a code for a target image, that identifies the group of images with the same values for the most significant elements as the generated code, and that identifies, from the images within the identified group, images whose codes vary less than a threshold amount from the code of the target image.

2. The computer system of claim 1 including a generate image table component that generates the image table by generating codes for images and grouping together images that have the same values for the most significant elements.

3. The computer system of claim 2 wherein the image table contains a group index that is indexed by the most significant elements and contains a reference to a group table for each value of the most significant elements.

4. The computer system of claim 3 wherein a group table maps the codes of images within the group to the images.

5. The computer system of claim 1 wherein the generate code component generates the code as a vector with the reduced dimension with a value set to 0 or 1 depending on the value of the corresponding element in the feature vector with the reduced dimension.

6. The computer system of claim 5 wherein the value of an element is set to 0 or 1 based on the value of the corresponding element of the feature vector with the reduced dimension relative to a mean of the values of the elements of the feature vector with the reduced dimension.

7. The computer system of claim 1 wherein the threshold amount corresponds to the count of values of elements of the least significant elements that are different.

8. A computer-readable storage medium storing computer-executable instructions for controlling a computer to detect similar images by a method comprising:

generating a code for an image by

generating a feature vector of a certain dimension that represents the image;

reducing the dimensions of the feature vector; and

creating a code from the feature vector with the reduced dimensions, the code having an element for each of the reduced dimensions of the feature vector, each element having a value of 0 or 1 that is derived from the corresponding feature of that reduced dimension, the elements having varying levels of significance such that similar images have similar codes with the most significant elements having the same values;

generating an image table that groups images by the most significant elements of their codes; and

identifying images that are similar to a target image by

generating a target code for the target image;

identifying from the image table a group of images with the same values for the most significant elements of their codes as the target code;

identifying, from the images within the identified group, images whose codes vary less than a threshold amount from the target code of the target image

wherein the identified images represent images that are similar to the target image.

9. The computer-readable storage medium of claim 8 wherein the image table has a group index that is indexed by the most significant elements of a code, each entry of the group index having a reference to a group table identifying images within a group.

10. The computer-readable storage medium of claim 9 wherein a group table maps the codes of images within the group to the images.

11. The computer-readable storage medium of claim 8 wherein the code is created as a vector with the reduced dimension with a value of an element set to 0 or 1 depending on the value of the corresponding feature in the feature vector with the reduced dimension.

12. The computer-readable storage medium of claim 8 wherein the value of an element is set to 0 or 1 based on the value of the corresponding feature of the feature vector with the reduced dimension relative to a mean of values of the feature of the feature vector with the reduced dimension of the images grouped by the image table.

13. The computer-readable storage medium of claim 12 wherein the threshold amount corresponds to the count of values of elements of the least significant elements that are different.