Image processing and matching

Patent metadata

Field	Value
Publication number	US-9697233-B2
Application number	US-201514822092-A
Country	US
Kind code	B2
Filing date	Aug 10, 2015
Priority date	Aug 12, 2014
Publication date	Jul 4, 2017
Grant date	Jul 4, 2017

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.

First claim

What is claimed is:

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

Assignees

• Paypal Inc

Inventors

• Di Wei
• Jagadeesh Vignesh
• Piramuthu Robinson
• Pandey Rohit
• Bhardwaj Anurag

Classifications

• G06F18/23

  Clustering techniques · CPC title

• G06F18/22

  Matching criteria, e.g. proximity measures · CPC title

• G06F16/5838

  using colour · CPC title

• G06F16/583 Primary

  using metadata automatically derived from the content · CPC title

• G06V10/56

  relating to colour · CPC title