Automatic learning of logos for visual recognition

• US 8,438,163 B1
• Filed: 12/07/2011
• Issued: 05/07/2013
• Est. Priority Date: 12/07/2010
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Li, Yuan, Adam, Hartwig
• Primary Examiner(s): Truong, Dennis
• Application Number:
  US13/314,061
• Time in Patent Office: 517 Days
• Field of Search: 707/706, 707/722, 707/737, 707/754, 707/915, 707/999.001, 382/159, 382/195, 382/209
• US Class Current: 707/737
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/51 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/58 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 18/28 Determining representative reference patterns, e.g. by averaging or distorting; Generating dictionaries
• CPC Class Codes: G06F 2218/12 Classification; Matching
• CPC Class Codes: G06V 2201/07 Target detection
• CPC Class Codes: G06V 30/1914 Determining representative reference patterns, e.g. averaging or distorting patterns; Generating dictionaries, e.g. user dictionaries
• CPC Class Codes: G06V 30/242 Division of the character sequences into groups prior to recognition; Selection of dictionaries

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for automatically extracting logos from images. Methods include generating a query list including a plurality of logo search queries, for each logo search query of the plurality of logo search queries: generating a plurality of image search results, each image search result including image data, and clustering the plurality of image search results into a plurality of clusters, each cluster including a plurality of images of the plurality of image search results, extracting, for each cluster of the plurality of clusters, a representative image to provide a plurality of representative images, and a name corresponding to the representative image to provide a plurality of names, and providing the plurality of representative images and the plurality of names to a logo index, the logo index being accessible to identify one or more logo images in a query image.

Claims

1. A system comprising:

one or more processors;

a computer-readable medium coupled to the one or more processors having instructions stored thereon which, when executed by the one or more processors, cause the one or more processors to perform operations comprising;

generating a query list comprising a plurality of logo search queries, wherein generating a query list comprises;

searching a query log based on a term;

identifying one or more image search queries of the query log corresponding to the term; and

populating the query list with the one or more image search queries;

for each logo search query of the plurality of logo search queries;

generating a plurality of image search results, each image search result comprising image data, and

clustering the plurality of image search results into a plurality of clusters, each cluster comprising a plurality of images of the plurality of image search results;

extracting, for each cluster of the plurality of clusters, a representative image to provide a plurality of representative images, and a name corresponding to the representative image to provide a plurality of names; and

providing the plurality of representative images and the plurality of names to a logo index, the logo index being accessible to identify one or more logo images in a query image.

2. The system of claim 1, wherein each of the plurality of image search results comprises a document identification and image meta-data.

3. The system of claim 1, wherein the actions further comprise:

determining an image score for each image of the image search results;

comparing the image score of an image to a threshold image score; and

removing the image from the image search results when the image score is less than the threshold image score.

4. The system of claim 1, wherein the actions further comprise:

determining a number of images populating a cluster of the plurality of clusters;

comparing the number of images to a threshold number of images; and

removing the cluster from the plurality of clusters when the number of images is less than the threshold number of images.

5. The system of claim 1, wherein clustering comprises:

generating an image template for each image of the plurality of image search results to provide a plurality of image templates;

determining a similarity score based on a first image template and a second image template; and

clustering an image corresponding to the first image template and an image corresponding to the second image template into a cluster when the similarity score is greater than a threshold similarity score.

6. The system of claim 1, wherein extracting a representative image comprises:

identifying an image of a plurality of images in each cluster having a highest document count score as an initial image;

comparing the initial image to other images in the plurality of images;

identifying an image of the other images as a matching image; and

identifying one of the initial image and the matching image as a representative image of a corresponding cluster.

7. The system of claim 6, wherein identifying an image of the other images as a matching image comprises:

determining a matching score based on the initial image and the image of the other images; and

identifying the image of the other images as the matching image when the matching score is greater than a threshold matching score.

8. The system of claim 6, wherein identifying one of the initial image and the matching image as a representative image of a corresponding cluster comprises:

determining a quality score of the initial image;

determining a quality score of the matching image; and

identifying the initial image as the representative image when the quality score of the initial image is greater than the quality score of the matching image, and identifying the matching image as the representative image when the quality score of the matching image is greater than the quality score of the initial image.

9. The system of claim 1, wherein the actions further comprise:

identifying a first logo search query and a second logo search query as duplicate logo search queries in the query list; and

merging a representative image and name corresponding to the first logo search query and a representative image and name the second logo search query to provide a merged representative image and name.

10. The system of claim 9, wherein identifying a first logo search query and a second logo search query as duplicate logo search queries comprises:

removing pre-defined terms from each of the first logo search query and the second logo search query to provide a modified first logo search query and a modified second logo search query, respectively; and

determining that the modified first logo search query and the modified second logo search query exactly match.

11. The system of claim 9, wherein identifying a first logo search query and a second logo search query as duplicate logo search queries comprises:

determining an edit distance between the first logo search query and the second logo search query; and

determining that the edit distance is less than a threshold edit distance.

12. The system of claim 9, wherein identifying a first logo search query and a second logo search query as duplicate logo search queries comprises:

determining a first set of image identifiers corresponding to image search results of the first logo search query;

determining a second set of image identifiers corresponding to image search results of the second logo search query; and

determining that the first logo search query and the second logo search query are duplicates based on the first set of image identifiers and the second set of image identifiers.

13. The system of claim 12, wherein determining that the first logo search query and the second logo search query are duplicates is based on an intersection of the first set of image identifiers and the second set of image identifiers.

14. The system of claim 12, wherein determining that the first logo search query and the second logo search query are duplicates is based on a ratio of overlapping image identifiers of the first set of image identifiers and the second set of image identifiers.

15. The system of claim 9, wherein the actions further comprise matching images between image search results associated with each of the first logo search query and the second logo search query to provide a number of matched images, wherein identifying a first logo search query and a second logo search query as duplicate logo search queries is based on the number of matched images.

16. The system of claim 1, wherein the actions further comprise:

processing one or more representative images of the logo index to determine a presence of product packaging in the one or more representative images; and

removing a representative image and name from the logo index when the presence of product packaging is determined in the representative image.

17. The system of claim 1, wherein the actions further comprise:

processing one or more representative images of the logo index to determine a presence of one or more faces in the one or more representative images; and

removing a representative image and name from the logo index when the presence of one or more faces is determined in the representative image.

18. A non-transitory computer-readable medium coupled to one or more processors having instructions stored thereon which, when executed by the one or more processors, cause the one or more processors to perform operations comprising:

generating a query list comprising a plurality of logo search queries, wherein generating a query list comprises;

searching a query log based on a term;

identifying one or more image search queries of the query log corresponding to the term; and

populating the query list with the one or more image search queries;

for each logo search query of the plurality of logo search queries;

generating a plurality of image search results, each image search result comprising image data, and

clustering the plurality of image search results into a plurality of clusters, each cluster comprising a plurality of images of the plurality of image search results;

extracting, for each cluster of the plurality of clusters, a representative image to provide a plurality of representative images, and a name corresponding to the representative image to provide a plurality of names; and

providing the plurality of representative images and the plurality of names to a logo index, the logo index being accessible to identify one or more logo images in a query image.

19. A computer-implemented method, comprising:

generating a query list comprising a plurality of logo search queries, wherein generating a query list comprises;

searching a query log based on a term;

identifying one or more image search queries of the query log corresponding to the term; and

populating the query list with the one or more image search queries;

for each logo search query of the plurality of logo search queries;

generating a plurality of image search results, each image search result comprising image data, and

clustering the plurality of image search results into a plurality of clusters, each cluster comprising a plurality of images of the plurality of image search results;

extracting, for each cluster of the plurality of clusters, a representative image to provide a plurality of representative images, and a name corresponding to the representative image to provide a plurality of names; and

providing the plurality of representative images and the plurality of names to a logo index, the logo index being accessible to identify one or more logo images in a query image.