Relevance-Based Image Selection

• US 20110047163A1
• Filed: 08/24/2009
• Published: 02/24/2011
• Est. Priority Date: 08/24/2009
• Status: Abandoned Application

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Bengio, Samy, Chechik, Gal
• Application Number:
  US12/546,436
• Publication Number:
  US 20110047163A1
• Time in Patent Office: Days
• US Class Current: 707/741
• CPC Class Codes: G06F 16/70 of video data
• CPC Class Codes: G06F 16/738 Presentation of query results
• CPC Class Codes: G06F 16/743 a collection of video files or sequences
• CPC Class Codes: G06F 16/78 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/783 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/7844 using original textual content or text extracted from visual content or transcript of audio data
• CPC Class Codes: G06F 16/7867 using information manually generated, e.g. tags, keywords, comments, title and artist information, manually generated time, location and usage information, user ratings
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

A system, computer readable storage medium, and computer-implemented method presents video search results responsive to a user keyword query. The video hosting system uses a machine learning process to learn a feature-keyword model associating features of media content from a labeled training dataset with keywords descriptive of their content. The system uses the learned model to provide video search results relevant to a keyword query based on features found in the videos. Furthermore, the system determines and presents one or more thumbnail images representative of the video using the learned model.

Claims

1. A computer-implemented method for creating a searchable video index, the method executed by a computer system, and comprising:

receiving a labeled training dataset comprising a set of media items together with one or more keywords descriptive of content of the media items;

extracting features characterizing the content of the media items;

training a machine-learned model to learn correlations between the extracted features of the media items and the keywords descriptive of the content; and

generating the video index mapping frames of videos in a video database to keywords based on features of the videos in the video database and the machine-learned model.

2. The method of claim 1, wherein the media items comprise images.

3. The method of claim 1, wherein the media items comprise audio clips.

4. The method of claim 1, wherein extracting the features characterizing the content of the media items comprises:

segmenting each image into a plurality of patches;

generating a feature vector for each of the patches; and

applying a clustering algorithm to determine a plurality of most representative feature vectors in the labeled training data.

5. The method of claim 4, wherein the patches are at least partially overlapping.

6. The method of claim 4, further comprising:

determining a plurality of most commonly found keywords in the labeled training dataset.

7. The method of claim 6, further comprising:

storing associations between the most representative keywords and the most commonly found feature vectors.

8. The method of claim 6, wherein storing associations between the most commonly found keywords and the most commonly found feature vectors comprise:

generating a set of association functions, each association function representative of an association strength between one of the most representative feature vectors and one of the most commonly found keywords.

9. The method of claim 7, wherein storing associations between the most commonly found keywords and the most commonly found feature vectors comprises:

generating a feature-keyword matrix, wherein entries in a first dimension of the feature-keyword matrix each correspond to a different one of the most representative feature vectors, and wherein entries in a second dimension of the feature-keyword matrix each correspond to a different one of the most commonly found keywords.

10. The method of claim 9, wherein generating the feature-keyword matrix comprises:

initializing the feature-keyword matrix by populating the entries with initial weights;

selecting a positive training media item associated with a first keyword and a negative training media item not associated with a second keyword;

extracting features for the positive and negative training media items to obtain a positive feature vector and a negative feature vector;

applying a transformation to the positive feature vector using the feature-keyword matrix to obtain a first keyword score for the positive training media item;

applying a transformation to the negative feature vector using the feature-keyword matrix to obtain a second keyword score for the negative training media item;

determining if the keyword score for the positive media training item is at least a threshold value higher than the keyword score for the negative training media item; and

responsive to the keyword score for the positive media training item not being at least a threshold value higher than the keyword score for the negative training media item, adjusting the weights in the feature-keyword matrix.

11. The method of claim 1, wherein generating the video index comprises:

sampling frames of a video in the video database;

computing a first feature vector for a first sampled frame of the video representative of content of the first sampled frame;

applying the machine-learned model to the first feature vector to generate a keyword association score between the first sampled frame and the selected keyword; and

storing the keyword association score in association with the first sampled frame in the video index.

12. The method of claim 1, wherein generating the video index comprises:

sampling scenes of a video in the video database;

computing a first feature vector for a first sampled scene of the video representative of content of the first sampled scene;

applying the machine-learned model to the first feature vector to generate a keyword association score between the first sampled scene and the selected keyword; and

storing the keyword association score in association with the first sampled scene in the video index.

13. A computer-implemented method for presenting video search results, the method executed by a computer system, and comprising:

receiving a video;

selecting a frame from the video as representative of content of the video using a video annotation index that stores keyword association scores between frames of a plurality of videos and keywords associated with the frames of the plurality of videos; and

providing the selected frame as a thumbnail for the video.

14. The method of claim 13, wherein selecting the frame from the video as representative of the video'"'"'s content comprises:

selecting a keyword representative of desired video content;

accessing the video annotation index to determine keyword association scores between frames of the video and the selected keyword; and

selecting the frame having a highest ranked keyword association score with the selected keyword according to the video annotation index.

15. The method of claim 14, wherein selecting the keyword representative of the desired video content comprises using a title of the video as the selected keyword.

16. The method of claim 14, wherein selecting the keyword representative of the desired video content comprises using the keyword query as the selected keyword.

17. The method of claim 13, wherein receiving the video comprises:

receiving a keyword query from a user; and

selecting the video from a database of videos as having content relevant to the keyword query.

18. The method of claim 18, wherein selecting the video having content relevant to the keyword query comprises:

determining a frame of video having a high keyword association score with a keyword from the keyword query;

determining scene boundaries of a scene relevant to the keyword query, the scene of video including the frame having the high keyword association score; and

selecting the scene as the selected video.

19. The method of claim 18, further comprising:

ranking the selected video among a plurality of videos in a result set based on the keyword association scores between frames of videos in the result set and keywords in the keyword query.

20. The method of claim 18, further comprising:

presenting a relevance score for the selected video based on the keyword association scores between frames of the video and keywords in the keyword query.

21. A computer readable storage medium storing computer executable code for creating a searchable video index, the computer executable program code when executed cause an application to perform the steps of:

receiving a labeled training dataset comprising a set of media items together with one or more keywords descriptive of content of the media items;

extracting features characterizing the content of the media items;

training a machine-learned model to learn correlations between the extracted features of the media items and the keywords descriptive of the content; and

generating the video index mapping frames of videos in a video database to keywords based on features of the videos in the video database and the machine-learned model.

22. The computer readable storage medium of claim 21, wherein the media items comprise images.

23. The computer readable storage medium of claim 21, wherein the media items comprise audio clips.

24. The computer readable storage medium of claim 21, wherein extracting the features characterizing the content of the media items comprises:

segmenting each image into a plurality of patches;

generating a feature vector for each of the patches; and

applying a clustering algorithm to determine a plurality of most representative feature vectors in the labeled training data.

25. The computer readable storage medium of claim 24, wherein the patches are at least partially overlapping.

26. The computer readable storage medium of claim 24, further comprising:

determining a plurality of most commonly found keywords in the labeled training dataset.

27. The computer readable storage medium of claim 26, further comprising:

storing associations between the most commonly found keywords and the most commonly found feature vectors.

28. The computer readable storage medium of claim 26, wherein storing associations between the most commonly found keywords and the most commonly found feature vectors comprise:

generating a set of association functions, each association function representative of an association strength between one of the most representative feature vectors and one of the most commonly found keywords.

29. The computer readable storage medium of claim 27, wherein storing associations between the most commonly found keywords and the most representative feature vectors comprises:

generating a feature-keyword matrix, wherein entries in a first dimension of the feature-keyword matrix each correspond to a different one of the most representative feature vectors, and wherein entries in a second dimension of the feature-keyword matrix each correspond to a different one of the most commonly found keywords.

30. The computer readable storage medium of claim 29, wherein generating the feature-keyword matrix comprises:

initializing the feature-keyword matrix by populating the entries with initial weights;

selecting a positive training media item associated with a first keyword and a negative training media item not associated with a second keyword;

extracting features for the positive and negative training media items to obtain a positive feature vector and a negative feature vector;

applying a transformation to the positive feature vector using the feature-keyword matrix to obtain a first keyword score for the positive training media item;

applying a transformation to the negative feature vector using the feature-keyword matrix to obtain a second keyword score for the negative training media item;

determining if the keyword score for the positive media training item is at least a threshold value higher than the keyword score for the negative training media item; and

responsive to the keyword score for the positive media training item not being at least a threshold value higher than the keyword score for the negative training media item, adjusting the weights in the feature-keyword matrix.

31. The computer readable storage medium of claim 21, wherein generating the video index comprises:

sampling frames of a video in the video database;

computing a first feature vector for a first sampled frame of the video representative of content of the first sampled frame;

applying the machine-learned model to the first feature vector to generate a keyword association score between the first sampled frame and the selected keyword; and

storing the keyword association score in association with the first sampled frame in the video index.

32. The computer readable storage medium of claim 21, wherein generating the video index comprises:

sampling scenes of a video in the video database;

computing a first feature vector for a first sampled scene of the video representative of content of the first sampled scene;

applying the machine-learned model to the first feature vector to generate a keyword association score between the first sampled scene and the selected keyword; and

storing the keyword association score in association with the first sampled scene in the video index.

33. A computer readable storage medium storing computer executable code for presenting video search results, the computer executable program code when executed cause an application to perform the steps of:

receiving a video;

selecting a frame from the video as representative content of the video using a video annotation index that stores keyword association scores between frames of a plurality of videos and keywords associated with the frames of the plurality of videos; and

providing the selected frame as a thumbnail for the video.

34. The computer readable storage medium of claim 33, wherein selecting the frame from the video as representative of the video'"'"'s content comprises:

selecting a keyword representative of desired video content;

accessing the video index to determine keyword association scores between frames of the video and the selected keyword; and

selecting the frame having a highest ranked keyword association score with the selected keyword according to the video annotation index.

35. The computer readable storage medium of claim 34, wherein selecting the keyword representative of the desired video content comprises using a title of the video as the selected keyword.

37. The computer readable storage medium of claim 34, wherein selecting the keyword representative of the desired video content comprises using the keyword query as the selected keyword.

38. The computer readable storage medium of claim 33, wherein receiving the video comprise:

receiving a keyword query from a user; and

selecting the video from a database of videos as having content relevant to the keyword query.

39. The computer readable storage medium of claim 38, wherein selecting the video having content relevant to the keyword query comprises:

determining a frame of video having a high keyword association score with a keyword from the keyword query;

determining scene boundaries of a scene relevant to the keyword query, the scene of video including the frame having the high keyword association score; and

selecting the scene as the selected video.

40. The computer readable storage medium of claim 38, further comprising:

ranking the selected video among a plurality of videos in a result set using the keyword association scores between frames of videos in the result set and keywords in the keyword query.

41. The computer readable storage medium of claim 38, further comprising:

presenting a relevance score for the selected video based on the keyword association scores between frames of the video and keywords in the keyword query.

42. A video hosting system for finding and presenting videos relevant to a keyword query, the system comprising:

a front end server configured to receive a keyword query from a user and present a result set comprising a video having content relevant to the keyword query and a thumbnail image representative of the content of the video;

a video annotation index comprising a mapping between keywords and frames of video, the mapping derived from a machine-learned model; and

a video search engine configured to access the video annotation index to determine the video having content relevant to the keyword and to determine the thumbnail image representative of the content of the video.

43. The system of claim 42, further comprising:

a video database storing videos searchable by the video search engine, wherein frames of the stored videos are indexed in the video annotation index to map the frames to keywords descriptive of their content.

44. The system of claim 42, further comprising:

a video annotation engine configured to determine a mapping between frames of videos in a video database and keywords descriptive of their content using a learned feature-keyword model obtained through machine learning.

45. The system of claim 44, wherein the video annotation engine comprises:

a video sampling module configured to sample frames of video from a video database;

a feature extraction module configure to generate a feature vector representative of each of the sampled frames of video; and

a frame annotation module configured to apply the learned feature-keyword model to the feature vectors in order to determine keyword scores for each of the sampled frames of video, the keyword scores indexed to the video annotation index in association with the relevant sampled frames.

46. The system of claim 42, further comprising:

a learning engine configured to learn a feature-keyword model mapping features of images or audio clips in a labeled training dataset to keywords descriptive of their content.

47. The system of claim 45, wherein the learning engine comprises:

a feature extraction module configured to generate a feature dataset comprising a plurality of most representative feature vectors for the labeled training dataset;

a keyword learning module configured to generate a keyword dataset comprising a plurality of most commonly occurring keywords in the labeled training dataset; and

an association learning module adapted to generate the keyword-feature model mapping associations between the feature vectors in feature dataset and the keywords in the keyword dataset.

48. The system of claim 47, wherein the learning engine further comprises:

a click-through module configured to automatically acquire labels for the labeled training data by tracking user search queries on a media search web site, and learning labels for media items by observing search results selected by a user and search results not selected by the user.

49. A method for presenting advertisements, the method executed by a computer and comprising:

playing a selected video using a web-based video player;

monitoring a current frame of video during playback of the selected video;

accessing a video annotation index using the current frame of video to determine one or more keywords associated with the current frame,

accessing an a advertising database using the one or more keywords to select an advertisement associated with the one or more keywords; and

providing the advertisement for display during playback of the current frame.

50. The method of claim 49, wherein the video annotation index maps frames of video to one or more keywords according to a machine-learned model.

51. A method for presenting a set of related videos, the method executed by a computer and comprising:

playing a selected video using a web-based video player;

extracting metadata associated with the selected video, the metadata including one or more keywords descriptive of the selected video;

accessing a video annotation index using the one or more keywords to determine one or more related videos; and

providing the one or more related videos for display, each related video represented by a thumbnail image representative of its content.

52. The method of claim 51, wherein the video annotation index maps keywords to videos in a video database according to a machine-learned model.