METHOD AND SYSTEM FOR DETERMINING NEAR DUPLICATE IMAGES

• US 20100166321A1
• Filed: 12/29/2008
• Published: 07/01/2010
• Est. Priority Date: 12/29/2008
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Sawant, Neela, Sengamedu, Srinivasan H.
• Granted Patent: US 8,213,723 B2
• Time in Patent Office: Days
• US Class Current: 382/209
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06V 10/431 Frequency domain transformation; Autocorrelation

Abstract

The present invention provides a method and system for determining near-duplicate images. The method and system includes performing a Fourier-Mellin transform on each of a plurality of images. For each image of the plurality of images, the method and system includes generating a signature based on the Fourier-Mellin transform. The method and system includes comparing the signature of at least one of the images to at least one of the signatures of the other plurality of images and determining any near duplicate images based on the comparing of the signatures.

Claims

1. A method for determining near-duplicate images, the method comprising:

performing a Fourier-Mellin Transform on each of a plurality of images;

for each image of the plurality images, generating a signature based on the Fourier-Mellin transform;

comparing the signature of at least one of the images to at least one of the signatures of the other plurality of images; and

determining any near-duplicate images based on the comparing of the signatures.

2. The method of claim 1, the step of generating a signature based on the Fourier-Mellin transform comprising:

converting the image to a gray-scale;

if needed, resizing the gray-scale to a fixed size;

transforming the gray scale to a log-polar representation using a center point as a reference point; and

performing median thresholding including;

reordering a first window of the image by a first squared dimensional vector;

finding a median value of the vector;

creating a binary representation of the median value of the vector, creating a second squared binary representation of a second window of the image; and

concatenate the first binary representation and second binary representation to generate the signature.

3. The method of claim 1, wherein generating the signature includes applying a hashing function.

4. The method of claim 1 further comprising:

receiving an image search request;

performing a search operation based on the search request; and

modifying a search results page based on the determining any near duplicate images.

5. The method of claim 4, wherein the modifying the search results page includes culling near-duplicate images from a search results page.

6. The method of claim 4, wherein the image search request includes a search request image, the method comprising:

performing a Fourier-Mellin Transform on the search request image;

generating a search request signature based on the Fourier-Mellin transform; and

performing the search operation using the search request signature.

7. The method of claim 1 further comprising:

storing the plurality of images in a data storage device; and

culling near-duplicate images stored in the data storage device.

8. A system for determining near-duplicate images, the system comprising:

a computer readable medium having executable instructions stored thereon; and

a processing device in communication with the computer readable medium operative to receive the executable instructions therefrom, the processing device, in response to the executable instructions, operative to;

perform a Fourier-Mellin Transform on each of the plurality of images;

for each image of the plurality images, generate a signature based on the Fourier-Mellin transform;

compare the signature of at least one of the images to at least one of the signatures of the other plurality of images; and

determine any near-duplicate images based on the comparing of the signatures.

9. The system of claim 8, wherein the processing device in being operative to generate the signature based on the Fourier-Mellin transform is further operative to:

convert the image to a gray-scale;

if needed, resize the gray-scale to a fixed size;

transform the gray scale to a log-polar representation using a center point as a reference point; and

perform median thresholding including;

reordering a first window of the image by a first squared dimensional vector;

finding a median value of the vector;

creating a binary representation of the median value of the vector, creating a second squared binary representation of a second window of the image; and

concatenate the first binary representation and second binary representation to generate the signature.

10. The system of claim 8, wherein generating the signature includes applying a hashing function.

11. The system of claim 8, the processing device, in response to the executable instructions, further operative to:

receive an image search request;

perform a search operation based on the search request; and

modify a search results page based on the determining any near-duplicate images.

12. The system of claim 11, wherein the modifying the search results page includes culling near-duplicate images from a search results page.

13. The system of claim 11, wherein the image search request includes a search request image, the processing device, in response to the executable instructions, further operative to:

perform a Fourier-Mellin Transform on the search request image;

generate a search request signature based on the Fourier-Mellin transform; and

perform the search operation using the search request signature.

14. The system of claim 8 further comprising:

a data storage device; and

the processing device, in response to the executable instructions, operative to;

store the plurality of images in a data storage device; and

cull near-duplicate images stored in the data storage device.

15. Computer readable media comprising program code that when executed by a programmable processor causes execution of a method for determining near-duplicate images, the computer readable media comprising:

program code for performing a Fourier-Mellin Transform on each of a plurality of images;

for each image of the plurality images, program code for generating a signature based on the Fourier-Mellin transform;

program code for comparing the signature of at least one of the images to at least one of the signatures of the other plurality of images; and

determining any near-duplicate images based oh the comparing of the signatures.

16. The computer readable media of claim 15, wherein the program code for generating a signature based on the Fourier-Mellin transform comprises:

program code for converting the image to a gray-scale;

if needed, program code for resizing the gray-scale to a fixed size;

program code for transforming the gray scale to a log-polar representation using a center point as a reference point; and

program code for performing median thresholding including;

reordering a first window of the image by a first squared dimensional vector;

finding a median value of the vector;

creating a binary representation of the median value of the vector, creating a second squared binary representation of a second window of the image; and

concatenate the first binary representation and second binary representation to generate the signature.

17. The computer readable media of claim 15, wherein generating the signature includes applying a hashing function.

18. The computer readable media of claim 15, further comprising:

program code for receiving an image search request;

program code for performing a search operation based on the search request; and

program code for modifying a search results page based on the determining any near-duplicate images.

19. The computer readable media of claim 18, wherein the program code for modifying the search results page includes program code for culling near-duplicate images from a search results page.

20. The computer readable media of claim 18, wherein the image search request includes a search request image, the computer readable media comprising:

program code for performing a Fourier-Mellin Transform on the search request image;

program code for generating a search request signature based on the Fourier-Mellin transform; and

program code for performing the search operation using the search request signature.

21. The computer readable media of claim 15 further comprising:

program code for storing the plurality of images in a data storage device; and

program code for culling near-duplicate images stored in the data storage device.