# US 2010/0166321 A1 · Method and system for determining near duplicate images

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2010/0166321 A1
- Document ID: US20100166321A1
- Status: Published application
- Kind: A1
- Application number: 12/344,744
- Filed: 2008-12-29
- Published: 2010-07-01
- Earliest claimed: 2008-12-29
- Assignees: Yahoo! Inc.
- Inventors: Neela Sawant; Srinivasan H. Sengamedu
- Web page: https://patentgrep.com/patent/US20100166321A1

## CPC

- G06F 16/5838: {using colour}
- G06V 10/431: {Frequency domain transformation; Autocorrelation}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 4)

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

### Claim 6 (depends on 4)

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.

### Claim 7 (depends on 1)

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.

### Claim 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.

### Claim 9 (depends on 8)

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.

### Claim 10 (depends on 8)

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

### Claim 11 (depends on 8)

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.

### Claim 12 (depends on 11)

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

### Claim 13 (depends on 11)

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.

### Claim 14 (depends on 8)

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.

### Claim 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.

### Claim 16 (depends on 15)

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.

### Claim 17 (depends on 15)

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

### Claim 18 (depends on 15)

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.

### Claim 19 (depends on 18)

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.

### Claim 20 (depends on 18)

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.

### Claim 21 (depends on 15)

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.