Similarity detection and clustering of images

• US 20070078846A1
• Filed: 09/30/2005
• Published: 04/05/2007
• Est. Priority Date: 09/30/2005
• Status: Active Grant

• Current Assignee: IAC Search & Media Incorporated (Match Group, Inc.)
• Original Assignee: IAC Search & Media Incorporated (Match Group, Inc.)
• Inventors: Yang, Tao, Liu, Xin, Gulli, Antonino, Savona, Antonio, Choksi, Ankur, Carnevale, Luigi, Li, Beitao, Tanganelli, Filippo
• Granted Patent: US 7,801,893 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06V 10/56 relating to colour
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

A method for determining if a set of images in a large collection of images are near duplicates is described. The method includes processing the set of images, generating an image signature for each image in the set of images, and comparing the generated image signatures. The method can be used in clustering and ranking of images.

Claims

1. A computer system, comprising:

a communication network;

a client connected to the communication network, the client having an input/output interface to submit a query;

a server connected to the communication network, the server having an input/output interface to receive a query from the client;

a database of images stored on the server;

a search module stored on the server, the search module configured to search the database utilizing the query to generate a search result, wherein the search engine is configured to determine images that are near duplicates.

2. The system recited in claim 1, wherein the search engine is configured to cluster images determined as being near duplicates of each other.

3. The system recited in claim 1, wherein the search engine is configured to determine rank of an image in the set of images.

4. A method for determining near duplicate images in a set of images, the method comprising:

generating an image signature for each image in the set of images; and

comparing the generated image signatures.

5. The method recited in claim 4, wherein the image signatures are compared to generate an indication of similarity of images in the set of images, wherein the indication of similarity is used to determine if the images are near duplicates.

6. The method recited in claim 4, wherein the set of images is at least a subset of images obtained by a search engine upon searching for an image search term.

7. The method recited in claim 4, wherein generating an image signature for each images in the set of images comprises:

creating a signature for each image in the set of images; and

reducing the size of the wavelet signature.

8. The method recited in claim 5, wherein comparing the generated image signatures comprises:

determining distances between the generated image signatures.

9. The method recited in claim 4, further comprising:

pre-processing the set of images.

10. The method recited in claim 9, wherein pre-processing the set of images comprises:

gathering statistics for each image in the set of images;

scaling each image in the set of images to a uniform size; and

computing a luminance matrix for each scaled image in the set of images.

11. The method recited in claim 5, further comprising:

reducing the number of comparisons required for detecting near duplicate images within the set of images.

12. The method recited in claim 11, wherein reducing the number of comparisons required for detecting near duplicate images within the set of images comprises:

sorting the images according to aspect ratio;

defining a window of comparison over the sorted images; and

reducing a number of comparisons within the window of comparisons.

13. The method recited in claim 5, wherein reducing the number of comparisons required for detecting near duplicate images within the set of images comprises:

determining two images in the set of images to be near duplicates of each other if the two images are near duplicates of a third image in the set of images.

14. The method recited in claim 4, further comprising:

associating an attribute corresponding to a first image to a second image determined to be a near duplicate of the first image.

15. The method recited in claim 12, wherein reducing the number of comparisons required for detecting near duplicate images within the set of images located off-line comprises:

building clusters of images that are determined to be near duplicates;

selecting a representative of each cluster of images; and

merging two clusters of images if their respective representative are determined to be near duplicate images.

16. The method recited in claim 4, further comprising:

determining a popularity level of an image in the set of images based on the number of near duplicate images in the set of images.

17. A method for clustering a set of images, the method comprising:

generating an image signature for each image; and

comparing the image signatures to determine an indicator of similarity between the images, wherein the indicator of similarity is used to cluster images.

18. The method recited in claim 17, further comprising:

defining an image directed graph having the set of images as a set of vertices and the indicator of similarity as edges between the vertices.

19. The method recited in claim 18, further comprising:

linking the image directed graph with one or more layers of a graph comprising multiple layers, the layers including a web page directed graph having a set of web pages as a set of vertices and hyperlinks between the web pages as edges between the vertices, a click-through web page directed graph having a set of web pages selected in response to a query as a set of vertices and a selection of a subset from the set of web pages selected in response to the query as edges between the vertices, and a click-through image directed graph having a set of images selected in response to a query as a set of vertices and a selection of a subset from the set of images selected in response to the query as edges between the vertices.

20. The method recited in claim 19, wherein linking the image directed graph with one or more layers of the graph comprising multiple layers comprises:

determining edges between two images in the image graph based on the edges between web pages comprising the two images in any one of the web page directed graph, the click-through web page directed graph, and the click-through image directed graph.

21. A search engine for determining if two images are near duplicates, the apparatus comprising:

an image signature generator configured to generate an image signature for each image; and

a comparison facility configured to determine if the two images are near duplicate images based on their image signatures.

22. The search engine recited in claim 21, wherein the image signature generator further comprises:

an image processor configured to compute an aspect ratio and a mean value for each primary color chroma channel;

an image scalar configured to scale the images to a uniform size;

a luminance matrix processor configured to compute a luminance matrix on the scaled images.

23. The search engine recited in claim 22, wherein the image signature generator further comprises:

a wavelet transformer configured to generate a wavelet signature for each image.