Image processing and matching

• US 9,697,233 B2
• Filed: 08/10/2015
• Issued: 07/04/2017
• Est. Priority Date: 08/12/2014
• Status: Active Grant

• Current Assignee: PayPal, Inc. (PayPal Holdings, Inc.)
• Original Assignee: PayPal, Inc. (PayPal Holdings, Inc.)
• Inventors: Jagadeesh, Vignesh, Pandey, Rohit, Di, Wei, Piramuthu, Robinson, Bhardwaj, Anurag
• Primary Examiner(s): Couso, Jose
• Application Number:
  US14/822,092
• Publication Number:
  US 20160048536A1
• Time in Patent Office: 694 Days
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06V 10/464 using a plurality of salient features, e.g. bag-of-words [BoW] representations
• CPC Class Codes: G06V 10/56 relating to colour
• CPC Class Codes: G06V 10/757 Matching configurations of points or features

Abstract

A configured machine performs image matching and retrieval of natural images that may depict logos. The machine generates and uses color-localized spatial masks, which may be computationally less expensive than spatial verification techniques. Key points are detected within images that form a reference database of images. Local masks are defined by the machine around each key point based on the scale and orientation of the key point. To utilize color information presented in logo images, ordered color histograms may be extracted by the machine from locally masked regions of each image. A cascaded index may then be constructed for both visual descriptors and color histograms. For faster matching, the cascaded index maps the visual descriptors and color histograms to a list of relevant or similar images. This list may then be ranked to generate relevant matches for an input query image.

Claims

1. An image-processing method comprising:

by operation of one or more processors, generating a first index that correlates first clusters of local feature descriptors with reference images among a set of reference images, the local feature descriptors being generated based on the set of reference images;

by operation of one or more processors, generating a second index that correlates second clusters of local color descriptors with reference images among the set of reference images, the local color descriptors being generated based on the set of reference images, one of the local color descriptors being generated from a reference image among the set of reference images by concatenating color histograms generated from multiple regions of a mask that corresponds to a key point within the reference image;

by operation of one or more processors, generating a third index that correlates descriptor pairs with reference images among the set of reference images, the descriptor pairs each representing a co-occurrence of a first cluster of local feature descriptors among the first clusters of local feature descriptors with a second cluster of local color descriptors among the second clusters of local color descriptors, wherein a descriptor pair includes local feature descriptor and a corresponding local color descriptor;

by operation of one or more processors, determining that a query image matches the reference image based on the third index correlating a descriptor pair among the descriptor pairs with the reference image; and

by operation of one or more processors, presenting the reference image determined to match the query image.

2. The image-processing method of claim 1, wherein:

the generating of the first index that correlates the first clusters with the reference images includes;

generating the local feature descriptors by analyzing the set of reference images;

clustering the local feature descriptors to generate the first clusters of local feature descriptors; and

encoding the reference images among the set of reference images based on the first clusters of local feature descriptors.

3. The image-processing method of claim 2, wherein:

each of the generated first clusters of local feature descriptors represents a different visual word within a codebook of visual words; and

the encoding of the reference images correlates the reference image with a set of visual words from the codebook of visual words.

4. The image-processing method of claim 1, wherein:

the generating of the second index that correlates the second clusters with the reference images includes;

generating the local color descriptors by analyzing the set of reference images;

clustering the local color descriptors to generate the second clusters of local color descriptors; and

encoding the reference images among the set of reference images based on the second clusters of local color descriptors.

5. The image-processing method of claim 4, wherein:

the generating of the local color descriptors by analyzing the reference images includes;

generating the mask that corresponds to the key point among multiple key points within the reference image;

dividing the generated mask into multiple regions;

generating color histograms of the multiple regions of the generated mask that corresponds to the key point within the reference image; and

concatenating the color histograms of the multiple regions of the mask.

6. The image-processing method of claim 5, wherein:

the generating of the mask includes generating a square mask that corresponds to the key point within the reference image.

7. The image-processing method of claim 5, wherein:

the dividing the generated mask into multiple regions divides the mask into four triangular regions.

8. The image-processing method of claim 5, wherein:

the concatenating of the color histograms of the multiple regions of the mask generates a local color descriptor that corresponds to the key point within the reference image.

9. The image-processing method of claim 4, wherein:

each of the generated second clusters of local color descriptors represents a different color word within a codebook of color words; and

the encoding of the reference images correlates the reference image with a set of color words from the codebook of color words.

10. The image-processing method of claim 1, wherein:

the generating of the third index generates a cascaded index based on the generated first and second indices, the first index correlating the reference image with a first set of visual words from a visual codebook of visual words, the second index correlating the reference image with a second set of color words from a color codebook of color words.

11. The image-processing method of claim 10, wherein:

the cascaded index correlates the reference image with a descriptor pair among the descriptor pairs, the correlated descriptor pair representing a co-occurrence of a visual word among the first set of visual words with a color word among the second set of color words.

12. The image-processing method of claim 1, further comprising:

receiving the query image within a query from a device of a user; and

accessing the generated third index that correlates the descriptor pairs with reference images in response to the receiving of the query image; and

wherein the presenting of the reference image determined to match the query image is in response to the query received from the device of the user.

13. The image-processing method of claim 12, further comprising:

generating local feature descriptors of the query image and local color descriptors of the query image; and

determining tuples that pair each of the generated local feature descriptors of the query image with a corresponding one of the local color descriptors of the query image; and

wherein

the determining that the query image matches the reference image includes matching a tuple among the determined tuples with the descriptor pair correlated with the reference image by the third index.

14. The image-processing method of claim 12, further comprising:

determining that a subset of the reference images matches the query image based on the third index correlating a subset of the descriptor pairs with the subset of the reference images; and

ranking the subset of the reference images based on cosine similarity to the query image; and

wherein

the presenting of the reference image determined to match the query image is based on the ranked subset of the reference images.

15. An image-processing system comprising:

one or more processors; and

memory storing instructions that, when executed by the one or more processors, cause the one or more processors to perform operations comprising;

generating a first index that correlates first clusters of local feature descriptors with reference images among a set of reference images, the local feature descriptors being generated based on the set of reference images;

generating a second index that correlates second clusters of local color descriptors with reference images among the set of reference images, the local color descriptors being generated based on the set of reference images, one of the local color descriptors being generated from a reference image among the set of reference images by concatenating color histograms generated from multiple regions of a mask that corresponds to a key point within the reference image;

generating a third index that correlates descriptor pairs with reference images among the set of reference images, the descriptor pairs each representing a co-occurrence of a first cluster of local feature descriptors among the first clusters of local feature descriptors with a second cluster of local color descriptors among the second clusters of local color descriptors, wherein a descriptor pair includes local feature descriptor and a corresponding local color descriptor;

determining that a query image matches the reference image based on the third index correlating a descriptor pair among the descriptor pairs with the reference image; and

presenting the reference image determined to match the query image.

16. The image-processing system of claim 15, wherein:

the generating of the first index that correlates the first clusters with the reference images includes;

generating the local feature descriptors by analyzing the set of reference images;

clustering the local feature descriptors to generate the first clusters of local feature descriptors; and

encoding the reference images among the set of reference images based on the first clusters of local feature descriptors.

17. The image-processing system of claim 15, wherein:

the generating of the second index that correlates the second clusters with the reference images includes;

generating the local color descriptors by analyzing the set of reference images;

clustering the local color descriptors to generate the second clusters of local color descriptors; and

encoding the reference images among the set of reference images based on the second clusters of local color descriptors.

18. The image-processing system of claim 17, wherein:

the generating of the local color descriptors by analyzing the reference images includes;

generating the mask that corresponds to the key point among multiple key points within the reference image;

dividing the generated mask into multiple regions;

generating color histograms of the multiple regions of the generated mask that corresponds to the key point within the reference image; and

concatenating the color histograms of the multiple regions of the mask.

19. The image-processing system of claim 18, wherein:

the generating of the mask includes generating a square mask that corresponds to the key point within the reference image;

the dividing the generated mask into multiple regions divides the mask into four triangular regions; and

the concatenating of the color histograms of the multiple regions of the mask generates a local color descriptor that corresponds to the key point within the reference image.

20. A non-transitory machine-readable storage medium comprising instructions that, when executed by one or more processors of a machine, cause the machine to perform operations comprising:

generating a first index that correlates first clusters of local feature descriptors with reference images among a set of reference images, the local feature descriptors being generated based on the set of reference images;

generating a second index that correlates second clusters of local color descriptors with reference images among the set of reference images, the local color descriptors being generated based on the set of reference images, one of the local color descriptors being generated from a reference image among the set of reference images by concatenating color histograms generated from multiple regions of a mask that corresponds to a key point within the reference image;

generating a third index that correlates descriptor pairs with reference images among the set of reference images, the descriptor pairs each representing a co-occurrence of a first cluster of local feature descriptors among the first clusters of local feature descriptors with a second cluster of local color descriptors among the second clusters of local color descriptors, wherein a descriptor pair includes local feature descriptor and a corresponding local color descriptor;

determining that a query image matches the reference image based on the third index correlating a descriptor pair among the descriptor pairs with the reference image; and

presenting the reference image determined to match the query image.