Image processing and matching

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.

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