IP Library › Granted Patent US 9,076,076
Granted Patent B1
US 9,076,076 · App. 13/586,269 · Granted Jul 7, 2015

Image similarity determination

View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 9,076,076
App. No.
13/586,269
Granted
Jul 7, 2015
Kind
B1
Abstract

A system and method is provided that determines whether objects in one image are visually similar to objects in another image by replacing the images' backgrounds with other images, such as a solid color or an image with texture, and comparing the resulting histograms.

Claims (56)

1. A computer-implemented method comprising:

obtaining a pair of images comprising a first image and a second image;

segmenting each image of the pair into a respective foreground region and a respective background region;

generating (i) a first modified version of the first image by modifying the background region of the first image, (ii) a different, second modified version of the first image by modifying the foreground region of the first image, (iii) a first modified version of the second image by modifying the background region of the second image, and (iv) a different, second modified version of the second image by modifying the foreground region of the second image;

generating an image descriptor for each of (i) the first modified version of the first image in which the background region of the first image is modified, (ii) the different, second modified version of the first image in which the foreground region of the first image is modified, (iii) the first modified version of the second image in which the background region of the second image is modified, and (iv) the different, second modified version of the second image in which the foreground region of the second image is modified;

generating an aggregated image descriptor for the first image based at least on (i) the image descriptor for the first modified version of the first image in which the background region of the first image is modified, and (ii) the image descriptor for the different, second modified version of the first image in which the foreground region of the first image is modified;

generating an aggregated image descriptor for the second image based at least on (i) the image descriptor for the first modified version of the second image in which the background region of the second image is modified, and (ii) the image descriptor for the different, second modified version of the second image in which the foreground region is modified; and

classifying the pair of images as similar or as not similar based at least on (i) the aggregated image descriptor for the first image and (ii) the aggregated image descriptor for the second image.

2. The method of claim 1 , wherein the image descriptors each comprise an image histogram.

3. The method of claim 1 , wherein generating a different, second modified version of the first image by modifying the foreground region of the first image comprises:

replacing the background region of the obtained first image with a background region that has a single color that is different than a single color of the background region of the first modified version of the first image.

4. The method of claim 1 , wherein generating an aggregated image descriptor for the first image based at least on (i) the image descriptor for the first modified version of the first image in which the background region of the first image is modified, and (ii) the image descriptor for the different, second modified version of the first image in which the foreground region of the first image is modified comprises:

determining an intersection between (i) the image descriptor for the first modified version of the first image, and (ii) the image descriptor for the different, second modified version of the first image; and

generating the aggregated image descriptor as a representation of the determined intersection.

5. The method of claim 1 , wherein classifying the pair of images as similar or as not similar based at least on (i) the aggregated image descriptor for the first image and (ii) the aggregated image descriptor for the second image comprises:

determining the (i) the aggregated image descriptor for the first image and (ii) the aggregated image descriptor for the second image satisfy a similarity threshold; and

in response to determining the (i) the aggregated image descriptor for the first image and (ii) the aggregated image descriptor for the second image satisfy a similarity threshold, classifying the pair of images as similar.

6. The method of claim 5 , comprising:

providing data associated with the second image for output based on classifying the pair of images as similar.

7. A system comprising:

one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:

obtaining a pair of images comprising a first image and a second image;

segmenting each image of the pair into a respective foreground region and a respective background region;

generating (i) a first modified version of the first image by modifying the background region of the first image, (ii) a different, second modified version of the first image by modifying the foreground region of the first image, (iii) a first modified version of the second image by modifying the background region of the second image, and (iv) a different, second modified version of the second image by modifying the foreground region of the second image;

generating an image descriptor for each of (i) the first modified version of the first image in which the background region of the first image is modified, (ii) the different, second modified version of the first image in which the foreground region of the first image is modified, (iii) the first modified version of the second image in which the background region of the second image is modified, and (iv) the different, second modified version of the second image in which the foreground region of the second image is modified;

generating an aggregated image descriptor for the first image based at least on (i) the image descriptor for the first modified version of the first image in which the background region of the first image is modified, and (ii) the image descriptor for the different, second modified version of the first image in which the foreground region of the first image is modified;

generating an aggregated image descriptor for the second image based at least on (i) the image descriptor for the first modified version of the second image in which the background region of the second image is modified, and (ii) the image descriptor for the different, second modified version of the second image in which the foreground region is modified; and

classifying the pair of images as similar or as not similar based at least on (i) the aggregated image descriptor for the first image and (ii) the aggregated image descriptor for the second image.

8. The system of claim 7 , wherein the image descriptors each comprise an image histogram.

9. The system of claim 7 , wherein generating a different, second modified version of the first image by modifying the foreground region of the first image comprises:

replacing the background region of the obtained first image with a background region that has a single color that is different than a single color of the background region of the first modified version of the first image.

10. The system of claim 7 , herein generating an aggregated image descriptor for the first image based at least on (i) the image descriptor for the first modified version of the first image in which the background region of the first image is modified, and (ii) the image descriptor for the different, second modified version of the first image in which the foreground region of the first image is modified comprises:

determining an intersection between (i) the image descriptor for the first modified version of the first image, and (ii) the image descriptor for the different, second modified version of the first image; and

generating the aggregated image descriptor as a representation of the determined intersection.

11. The system of claim 7 , wherein classifying the pair of images as similar or as not similar based at least on (i) the aggregated image descriptor for the first image and (ii) the aggregated image descriptor for the second image comprises:

determining the (i) the aggregated image descriptor for the first image and (ii) the aggregated image descriptor for the second image satisfy a similarity threshold; and

in response to determining the (i) the aggregated image descriptor for the first image and (ii) the aggregated image descriptor for the second image satisfy a similarity threshold, classifying the pair of images as similar.

12. The system of claim 11 , the operations comprising:

providing data associated with the second image for output based on classifying the pair of images as similar.

13. A non-transitory computer-readable medium storing software comprising instructions executable by one or more computers which, upon such execution, cause the one or more computers to perform operations comprising:

obtaining a pair of images comprising a first image and a second image;

segmenting each image of the pair into a respective foreground region and a respective background region;

generating (i) a first modified version of the first image by modifying the background region of the first image, (ii) a different, second modified version of the first image by modifying the foreground region of the first image, (iii) a first modified version of the second image by modifying the background region of the second image, and (iv) a different, second modified version of the second image by modifying the foreground region of the second image;

generating an image descriptor for each of (i) the first modified version of the first image in which the background region of the first image is modified, (ii) the different, second modified version of the first image in which the foreground region of the first image is modified, (iii) the first modified version of the second image in which the background region of the second image is modified, and (iv) the different, second modified version of the second image in which the foreground region of the second image is modified;

generating an aggregated image descriptor for the first image based at least on (i) the image descriptor for the first modified version of the first image in which the background region of the first image is modified, and (ii) the image descriptor for the different, second modified version of the first image in which the foreground region of the first image is modified;

generating an aggregated image descriptor for the second image based at least on (i) the image descriptor for the first modified version of the second image in which the background region of the second image is modified, and (ii) the image descriptor for the different, second modified version of the second image in which the foreground region is modified; and

classifying the pair of images as similar or as not similar based at least on (i) the aggregated image descriptor for the first image and (ii) the aggregated image descriptor for the second image.

14. The medium of claim 13 , wherein the image descriptors each comprise an image histogram.

15. The medium of claim 13 , wherein generating a different, second modified version of the first image by modifying the foreground region of the first image comprises:

replacing the background region of the obtained first image with a background region that has a single color that is different than a single color of the background region of the first modified version of the first image.

16. The medium of claim 13 , wherein generating an aggregated image descriptor for the first image based at least on (i) the image descriptor for the first modified version of the first image in which the background region of the first image is modified, and (ii) the image descriptor for the different, second modified version of the first image in which the foreground region of the first image is modified comprises:

determining an intersection between (i) the image descriptor for the first modified version of the first image, and (ii) the image descriptor for the different, second modified version of the first image; and

generating the aggregated image descriptor as a representation of the determined intersection.

17. The medium of claim 13 , wherein classifying the pair of images as similar or as not similar based at least on (i) the aggregated image descriptor for the first image and (ii) the aggregated image descriptor for the second image comprises:

determining the (i) the aggregated image descriptor for the first image and (ii) the aggregated image descriptor for the second image satisfy a similarity threshold; and

in response to determining the (i) the aggregated image descriptor for the first image and (ii) the aggregated image descriptor for the second image satisfy a similarity threshold, classifying the pair of images as similar.

Assignments (2)
CHANGE OF NAME Recorded Oct 2, 2017
From: GOOGLE INC.
To: GOOGLE LLC
Reel/Frame 044334/0466 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Aug 21, 2012
From: IOFFE, SERGEY; CHINEN, TROY
To: GOOGLE INC.
Reel/Frame 028825/0304 →