Image classification

• US 8,478,052 B1
• Filed: 07/17/2009
• Issued: 07/02/2013
• Est. Priority Date: 07/17/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Bengio, Samy, Rosenberg, Charles, Yee, Yangli Hector, Murphy-Chutorian, Erik
• Primary Examiner(s): Bella, Matthew
• Assistant Examiner(s): TORRES, JOSE
• Application Number:
  US12/505,240
• Time in Patent Office: 1,446 Days
• Field of Search: 382/305, 382/155, 382/159, 382/190, 382/224, 707/E17.004, 707/E17.019, 707/E17.02, 707/E17.023
• US Class Current: 382/224
• CPC Class Codes: G06F 16/50 of still image data
• CPC Class Codes: G06F 16/55 Clustering; Classification
• CPC Class Codes: G06F 16/5846 using extracted text
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/18152 Extracting features based on a plurality of salient regional features, e.g. "bag of words"
• CPC Class Codes: G06V 30/19147 Obtaining sets of training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06V 30/194 References adjustable by an adaptive method, e.g. learning

Abstract

An image classification system trains an image classification model to classify images relative to text appearing with the images. Training images are iteratively selected and classified by the image classification model according to feature vectors of the training images. An independent model is trained for unique n-grams of text. The image classification system obtains text appearing with an image and parses the text into candidate labels for the image. The image classification system determines whether an image classification model has been trained for the candidate labels. When an image classification model corresponding to a candidate label has been trained, the image classification subsystem classifies the image relative to the candidate label. The image is labeled based on candidate labels for which the image is classified as a positive image.

Claims

1. A computer-implemented method, comprising:

obtaining a plurality of n-grams, each of the n-grams including a unique set of one or more terms;

for each of the n-grams;

identifying, in a processing device, a plurality of training images for training an image classification model, the plurality of training images comprising;

positive training images having relevance measures, for the n-gram, that satisfy a relevance threshold; and

negative training images having relevance measures, for the n-gram, that do not satisfy the relevance threshold;

selecting, in the processing device, a training image from the plurality of training images, wherein the selecting comprises semi-randomly selecting the training image subject to a selection requirement specifying that a second image be selected with a specified likelihood;

classifying, in the processing device, the training image with the image classification model based on a feature vector of the training image, the feature vector comprising image feature values for the training image; and

training, in the processing device, the image classification model based on the feature vector of the training image and the classification of the training image.

2. The method of claim 1, wherein training the image classification model comprises computing scalars corresponding to feature vectors based on image feature values of classified training images.

3. The method of claim 2, wherein training the image classification model comprises:

computing a classification score for the training image based on the image classification model;

classifying the training image based on the classification score;

determining that the training image is incorrectly classified; and

computing a minimum kernel approximation based on the feature vector for the training image.

4. The method of claim 1, wherein identifying the plurality of training images comprises identifying, as a positive training image, an image having at least a threshold selection rate when referenced in search results for the n-gram.

5. The method of claim 1, further comprising:

obtaining text associated with an image;

determining that an image classification model is trained for an n-gram matching the text;

obtaining a feature vector for the image; and

classifying the image based on the feature vector and the image classification model.

6. The method of claim 5, wherein obtaining text associated with the image comprises obtaining text appearing with the image on a Web page.

7. The method of claim 6, further comprising:

parsing the text into a plurality of candidate labels, each candidate label being a unique n-gram of the text; and

wherein the determining, obtaining and classifying are performed for each of the candidate labels.

8. The method of claim 7, further comprising labeling the image with label corresponding to the candidate label when the image is classified as a positive image for the candidate label.

9. The method of claim 7, wherein determining that an image classification model is trained for an n-gram matching the candidate label comprises determining that an image classification model is trained for an n-gram that is the same as the candidate label.

10. The method of claim 5, wherein obtaining text associated with the image comprises obtaining text that does not appear on a Web page with the image.

11. The method of claim 10, further comprising:

obtaining a user query;

identifying images associated with labels matching the user query; and

providing a boost factor for the images, the boost factor being a value for adjusting a relevance score for an image.

12. The method of claim 1, wherein training the image classification model comprises:

determining that the training image is incorrectly classified;

defining the feature vector of the training image as a support vector for the image classification model; and

adjusting the image classification model based on the support vector.

13. A system, comprising:

a data store storing training images for training an image classification model for an n-gram, the training images including positive images having relevance measures, for the n-gram, that meet a relevance threshold and negative images having relevance measures, for the n-gram, that do not meet the relevance threshold; and

an image classification system coupled to the data store, the image classification system including one or more processors configured to train the image classification model for the n-gram based on feature vectors of the training images, the image classification model comprising scalars corresponding to the feature vectors and a minimum kernel of feature vectors of training images.

14. The system of claim 13, wherein the image classification system is further configured to classify a training image based on the image classification model and adjust the image classification model based on a feature vector of an inaccurately classified training image based on the image classification model.

15. The system of claim 14, wherein the image classification system is further configured to adjust the image classification model by computing scalars of the image classification model based on the feature vectors of the inaccurately classified training images.

16. The system of claim 14, wherein the image classification model is further configured to adjust the image classification model based on an approximation of the minimum kernel of the feature vectors.

17. The system of claim 13, wherein the image classification model is further configured to classify an image relative to text with which the image is associated.

18. The system of claim 17, wherein the image classification model is further configured to label the image based on the classification of the image relative to the text.

19. The system of claim 18, wherein the image classification model is further configured to provide a boost factor for images having labels that match a user query.

20. A non-transitory computer readable medium encoded with a computer program comprising instructions that when executed operate to cause a computer to perform operations:

obtaining a plurality of n-grams, each of the n-grams including a unique set of one or more terms;

for each of the n-grams;

identifying a plurality of training images for training an image classification model, the plurality of training images comprising;

positive training images having relevance measures, for the n-gram, that satisfy a relevance threshold; and

negative training images having relevance measures, for the n-gram, that do not satisfy the relevance threshold;

selecting a training image from the plurality of training images, wherein the selecting comprises semi-randomly selecting the training image subject to a selection requirement specifying that a second image be selected with a specified likelihood;

classifying the training image with the image classification model based on a feature vector of the training image, the feature vector comprising image feature values for the training image; and

training the image classification model based on the feature vector of the training image and the classification of the training image.

21. The computer readable medium of claim 20, wherein the instructions cause the computer to perform operations comprising:

obtaining text associated with an image;

obtaining a feature vector for the image;

parsing, in a processing device, the text into candidate labels, each candidate label being a unique n-gram of the text;

determining, in the processing device, that an image classification model is trained for an n-gram matching one or more candidate labels; and

classifying, in the processing device, the image to the one or more candidate labels based on the feature vector and the image classification model for the n-gram matching the one or more candidate labels.

22. The computer readable medium of claim 21, wherein the determining and classifying are performed for each of the candidate labels.

23. The computer readable medium of claim 21, wherein classifying the image comprises:

computing a classification score for the image to the one or more candidate labels based on the feature vector and the image classification models for the n-gram matching the one or more candidate labels; and

classifying the image to the one or more candidate labels based on the classification score.

24. The computer readable medium of claim 23, wherein classifying the image to the one or more candidate labels based on the classification score comprises:

determining that the image has a classification score to a particular candidate label that meets or exceeds a relevance threshold; and

labeling the image with label corresponding to the particular candidate label.

25. The computer readable medium of claim 24, wherein the determining and labeling is performed for each of the one or more candidate labels.

26. The computer readable medium of claim 21, wherein obtaining text associated with the image comprises obtaining text appearing with the image on a Web page.