Automatic large scale video object recognition

• US 8,792,732 B1
• Filed: 07/26/2012
• Issued: 07/29/2014
• Est. Priority Date: 02/02/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Zhao, Ming, Yagnik, Jay
• Primary Examiner(s): CHAWAN, SHEELA C
• Application Number:
  US13/559,420
• Time in Patent Office: 733 Days
• Field of Search: 382/181, 382/190, 382/195, 382/197, 382/224, 382/155, 382/100, 382/128, 382/191, 382/203, 382/173, 382/232, 382/236, 382/226, 382/107, 707/999, 707/E17.028, 706/12, 706/16, 706/19, 706/20, 706/45, 706/15, 375/E7.11, 375/240.14, 375/E7.026, 375/240, 348/699
• US Class Current: 382/224
• CPC Class Codes: G06F 18/213 Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06V 10/761 Proximity, similarity or dissimilarity measures

Abstract

An object recognition system performs a number of rounds of dimensionality reduction and consistency learning on visual content items such as videos and still images, resulting in a set of feature vectors that accurately predict the presence of a visual object represented by a given object name within an visual content item. The feature vectors are stored in association with the object name which they represent and with an indication of the number of rounds of dimensionality reduction and consistency learning that produced them. The feature vectors and the indication can be used for various purposes, such as quickly determining a visual content item containing a visual representation of a given object name.

Claims

1. A computer-implemented method performed by a computer system, the method comprising:

for each object name of a plurality of object names;

selecting a plurality of visual content items from a visual content repository, and

associating, with the object name, a set of feature vectors by extracting a feature vector from each of the selected visual content items; and

for each object name of the plurality of object names;

performing consistency learning on the set of feature vectors associated with the object name until there is at least a minimum measure of similarity within the set of feature vectors associated with the object name, and

storing, as the classification model for the object name, the set of feature vectors associated with the object name.

2. The computer-implemented method of claim 1, further comprising, for each object name of the plurality of object names:

performing a number of dimensionality reduction rounds on the set of feature vectors associated with the object name, each round producing a set of reduced feature vectors as input for a next round, thereby producing multiple sets of reduced feature vectors for the object name.

3. The computer-implemented method of claim 2, wherein the number of dimensionality reductions performed on the set of feature vectors for an object name in order to reach the minimum measure of similarity varies with respect to different ones of the object names.

4. The computer-implemented method of claim 1, wherein the plurality of visual content items are automatically selected from the visual content repository based at least in part on a relationship between the object name and textual descriptions of the visual content items.

5. The computer-implemented method of claim 1, further comprising:

receiving a visual content item for which no classification model has yet been stored;

performing a plurality of consistency learning rounds on the received visual content item, each round resulting in a set of feature vectors associated with the visual content item;

identifying object names of the plurality of object names having classification models similar to the set of feature vectors associated with the received visual content item;

producing probabilities that the received visual content item contains visual representations corresponding to the object names; and

storing the probabilities in a recognition repository in association with their respective object names and with the received visual content item.

6. The computer-implemented method of claim 5, further comprising determining, for an object name, a plurality of visual content items in the visual content repository having the highest probabilities of containing a visual representation of the object name, the determining based at least in part on the probabilities of the recognition repository.

7. The computer-implemented method of claim 5, further comprising:

identifying a plurality of object names having highest probabilities of having a visual representation within a first visual content item in the visual content repository;

revising a list of labels within metadata associated with the first visual content item, based at least in part on the identified plurality of object names.

8. The computer-implemented method of claim 5, wherein a classification model is considered to be similar to the set of feature vectors associated with the received visual content item if the classification model'"'"'s feature vectors have been stored in a same cluster of feature vectors as the set of feature vectors associated with the received visual content item, according to a feature vector clustering algorithm.

9. The computer-implemented method of claim 1, wherein the plurality of object names comprises at least 50,000 object names.

10. The computer-implemented method of claim 1, further comprising extracting the plurality of object names from one of a group consisting of a lexical database and a search engine index.

11. The computer-implemented method of claim 1, wherein the visual content items have textual descriptions that are related to the object names by semantic similarity.

12. The computer-implemented method of claim 1, wherein performing consistency learning on the set of feature vectors associated with the object name comprises computing a measure of similarity for a feature vector based at least in part on comparisons between the feature vector and other feature vectors, wherein matches between the feature vector and other feature vectors for the same object name increase the score, and matches between the feature vector and feature vectors for different object names decrease the score.

13. A non-transitory computer readable storage medium storing executable computer instructions comprising:

instructions for, for each object name of a plurality of object names;

selecting a plurality of visual content items from a visual content repository, and

associating, with the object name, a set of feature vectors by extracting a feature vector from each of the selected visual content items; and

instructions for, for each object name of the plurality of object names;

performing consistency learning on the set of feature vectors associated with the object name until there is at least a minimum measure of similarity within the set of feature vectors associated with the object name, and

storing as the classification model for the object name, the associated plurality of feature vectors.

14. The non-transitory computer readable storage medium of claim 13, the instructions further comprising, for each object name of the plurality of object names:

instructions for performing a number of dimensionality reduction rounds on the set of feature vectors associated with the object name, each round producing a set of reduced feature vectors as input for a next round, thereby producing multiple sets of reduced feature vectors for the object name.

15. The non-transitory computer readable storage medium of claim 13, the instructions further comprising:

instructions for receiving a visual content item for which no classification model has yet been stored;

instructions for performing a plurality of consistency learning rounds on the received visual content item, each round resulting in a set of feature vectors associated with the visual content item;

instructions for identifying object names of the plurality of object names having classification models similar to the set of feature vectors associated with the received visual content item;

instructions for producing probabilities that the received visual content item contains visual representations corresponding to the object names; and

instructions for storing the probabilities in a recognition repository in association with their respective object names and with the received visual content item.

16. The non-transitory computer readable storage medium of claim 15, the instructions further comprising instructions for determining, for an object name, a plurality of visual content items in the visual content repository having the highest probabilities of containing a visual representation of the object name, the determining based at least in part on the probabilities of the recognition repository.

17. The non-transitory computer readable storage medium of claim 13, wherein a classification model is considered to be similar to the set of feature vectors associated with the received visual content item if the classification model'"'"'s feature vectors have been stored in a same cluster of feature vectors as the set of feature vectors associated with the received visual content item, according to a feature vector clustering algorithm.

18. The non-transitory computer readable storage medium of claim 13, wherein performing consistency learning on the set of feature vectors associated with the object name comprises computing a measure of similarity for a feature vector based at least in part on comparisons between the feature vector and other feature vectors, wherein matches between the feature vector and other feature vectors for the same object name increase the score, and matches between the feature vector and feature vectors for different object names decrease the score.

19. The non-transitory computer readable storage medium of claim 13, wherein the set of object names comprises at least 50,000 entries.

20. A computer implemented method performed by a computer system, the method comprising:

accessing a recognition repository having;

a plurality of object names, and

a plurality of associations, each association associating an object name, a visual content item, and a probability that the visual content item contains a visual representation corresponding to the object name;

receiving a query comprising an object name; and

identifying a plurality of visual content items having the highest probabilities of containing a visual representation of an object corresponding to the object name, based at least in part on the probabilities of the recognition repository.