US20110047163A1 - Relevance-Based Image Selection - Google Patents

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.

Description

BACKGROUND
• 1. Field of the Art
• The invention relates generally to identifying videos or their parts that are relevant to search terms. In particular, embodiments of the invention are directed to selecting one or more representative thumbnail images based on the audio-visual content of a video.
• 2. Background
• Users of media hosting websites typically browse or search the hosted media content by inputting keywords or search terms to query textual metadata describing the media content. Searchable metadata may include, for example, titles of the media files or descriptive summaries of the media content. Such textual metadata often is not representative of the entire content of the video, particularly when a video is very long and has a variety of scenes. In other words, if a video has a large number of scenes and variety of content, it is likely that some of those scenes are not described in the textual metadata, and as a result, that video would not be returned in response to searching on keywords that would likely describe such scenes. Thus, conventional search engines often fail to return the media content most relevant to the user's search.
• A second problem with conventional media hosting websites is that due to the large amount of hosted media content, a search query may return hundreds or even thousands of media files responsive to the user query. Consequently, the user may have difficulties assessing which of the hundreds or thousands of search results are most relevant. In order to assist the user in assessing which search results are most relevant, the website may present each search result together with a thumbnail image. Conventionally, the thumbnail image used to represent a video is a predetermined frame from the video file (e.g., the first frame, center frame, or last frame). However, a thumbnail selected in this manner is often not representative of the actual content of the video, since there is no relationship between the ordinal position of the thumbnail and the content of a video. Furthermore, the thumbnail may not be relevant to the user's search query. Thus, the user may have difficulty assessing which of the hundreds or thousands of search results are most relevant.
• Accordingly, improved methods of finding and presenting media search results that will allow a user to easily assess their relevance are needed.
SUMMARY OF THE INVENTION
• A system, computer readable storage medium, and computer-implemented method finds and presents video search results responsive to a user keyword query. A video hosting system receives a keyword search query from a user and selects a video having content relevant to the keyword query. The video hosting system selects a frame from the video as representative of the video's content using a video index that stores keyword association scores between frames of a plurality of videos and keywords associated with the frames. The video hosting system presents the selected frame as a thumbnail for the video.
• In one aspect, a computer system generates the searchable video index using a machine-learned model of the relationships between features of video frames, and keywords descriptive of video content. The video hosting system receives a labeled training dataset that includes a set of media items (e.g., images or audio clips) together with one or more keywords descriptive of the content of the media items. The video hosting system extracts features characterizing the content of the media items. A machine-learned model is trained to learn correlations between particular features and the keywords descriptive of the content. The video index is then generated that maps frames of videos in a video database to keywords based on features of the videos and the machine-learned model.
• Advantageously, the video hosting system finds and presents search results based on the actual content of the videos instead of relying solely on textual metadata. Thus, the video hosting system enables the user to better assess the relevance of videos in the set of search results.
• The features and advantages described in this summary and the following detailed description are not all-inclusive. Many additional features and advantages will be apparent to one of ordinary skill in the art in view of the drawings, specification, and claims hereof.
BRIEF DESCRIPTION OF THE DRAWINGS
• FIG. 1 is a high-level block diagram of avideo hosting system100 according to one embodiment.
• FIG. 2 is a high-level block diagram illustrating alearning engine140 according to one embodiment.
• FIG. 3 is a flowchart illustrating steps performed by thelearning engine140 to generate a learned feature-keyword model according to one embodiment.
• FIG. 4 is a flowchart illustrating steps performed by thelearning engine140 to generate afeature dataset255 according to one embodiment.
• FIG. 5 is a flowchart illustrating steps performed by thelearning engine140 to generate a feature-keyword matrix according to one embodiment.
• FIG. 6 is a block diagram illustrating a detailed view of aimage annotation engine160 according to one embodiment.
• FIG. 7 is a flowchart illustrating steps performed by thevideo hosting system100 to find and present video search results according to one embodiment.
• FIG. 8 is a flowchart illustrating steps performed by thevideo hosting system100 to select a thumbnail for a video based on video metadata according to one embodiment.
• FIG. 9 is a flowchart illustrating steps performed by thevideo hosting system100 to select a thumbnail for a video based on keywords in a user search query according to one embodiment.
• FIG. 10 is a flowchart illustrating steps performed by theimage annotation engine160 to identify specific events or scenes within videos based on a user keyword query according to one embodiment.
• The figures depict preferred embodiments of the present invention for purposes of illustration only. One skilled in the art will readily recognize from the following discussion that alternative embodiments of the structures and methods illustrated herein may be employed without departing from the principles of the invention described herein.
DETAILED DESCRIPTIONSystem Architecture
• FIG. 1 illustrates an embodiment of avideo hosting system100. Thevideo hosting system100 finds and presents a set of video search results responsive to a user keyword query. Rather than relying solely on textual metadata associated with the videos, thevideo hosting system100 presents search results based on the actual audio-visual content of the videos. Each search result is presented together with a thumbnail representative of the audio-visual content of the video that assists the user in assessing the relevance of the results.
• In one embodiment, thevideo hosting system100 comprises afront end server110, avideo search engine120, avideo annotation engine130, alearning engine140, avideo database175, avideo annotation index185, and a feature-keyword model195. Thevideo hosting system100 represents any system that allows users ofclient devices150 to access video content via searching and/or browsing interfaces. The sources of videos can be from uploads of videos by users, searches or crawls by the system of other websites or databases of videos, or the like, or any combination thereof. For example, in one embodiment, avideo hosting system100 can be configured to allow upload of content by users. In another embodiment, avideo hosting system100 can be configured to only obtain videos from other sources by crawling such sources or searching such sources, either offline to build a database of videos, or at query time.
• Each of the various components (alternatively, modules) e.g.,front end server110, avideo search engine120, avideo annotation engine130, alearning engine140, avideo database175, avideo annotation index185, and a feature-keyword model195, is implemented as part of a server-class computer system with one or more computers comprising a CPU, memory, network interface, peripheral interfaces, and other well known components. The computers themselves preferably run an operating system (e.g., LINUX), have generally high performance CPUs, 1 G or more of memory, and 100 G or more of disk storage. Of course, other types of computers can be used, and it is expected that as more powerful computers are developed in the future, they can be configured in accordance with the teachings here. In this embodiment, the modules are stored on a computer readable storage device (e.g., hard disk), loaded into the memory, and executed by one or more processors included as part of thesystem100. Alternatively, hardware or software modules may be stored elsewhere within thesystem100. When configured to execute the various operations described herein, a general purpose computer becomes a particular computer, as understood by those of skill in the art, as the particular functions and data being stored by such a computer configure it in a manner different from its native capabilities as may be provided by its underlying operating system and hardware logic. A suitablevideo hosting system100 for implementation of the system is the YOUTUBE™ website; other video hosting systems are known as well, and can be adapted to operate according to the teachings disclosed herein. It will be understood that the named components of thevideo hosting system100 described herein represent one embodiment of the present invention, and other embodiments may include other components. In addition, other embodiments may lack components described herein and/or distribute the described functionality among the modules in a different manner. Additionally, the functionalities attributed to more than one component can be incorporated into a single component.
• FIG. 1 also illustrates threeclient devices150 communicatively coupled to thevideo hosting system100 over anetwork160. Theclient devices150 can be any type of communication device that is capable of supporting a communications interface to thesystem100. Suitable devices may include, but are not limited to, personal computers, mobile computers (e.g., notebook computers), personal digital assistants (PDAs), smartphones, mobile phones, and gaming consoles and devices, network-enabled viewing devices (e.g., settop boxes, televisions, and receivers). Only threeclients150 are shown inFIG. 1 in order to simplify and clarify the description. In practice, thousands or millions ofclients150 can connect to thevideo hosting system100 via thenetwork160.
• Thenetwork160 may be a wired or wireless network. Examples of thenetwork160 include the Internet, an intranet, a WiFi network, a WiMAX network, a mobile telephone network, or a combination thereof. Those of skill in the art will recognize that other embodiments can have different modules than the ones described here, and that the functionalities can be distributed among the modules in a different manner. The method of communication between the client devices and thesystem100 is not limited to any particular user interface or network protocol, but in a typical embodiment a user interacts with thevideo hosting system100 via a conventional web browser of theclient device150, which employs standard Internet protocols.
• Theclients150 interact with thevideo hosting system100 via thefront end server110 to search for video content stored in thevideo database175. Thefront end server110 provides controls and elements that allow a user to input search queries (e.g., keywords). Responsive to a query, thefront end server110 provides a set of search results relevant to the query. In one embodiment, the search results include a list of links to the relevant video content in thevideo database175. Thefront end server110 may present the links together with information associated with the video content such as, for example, thumbnail images, titles, and/or textual summaries. Thefront end server110 additionally provides controls and elements that allow the user to select a video from the search results for viewing on theclient150.
• Thevideo search engine120 processes user queries received via thefront end server110, and generates a result set comprising links to videos or portions of videos in thevideo database175 that are relevant to the query, and is one means for performing this function. Thevideo search engine120 may additionally perform search functions such as ranking search results and/or scoring search results according to their relevance. In one embodiment, thevideo search engine120 find relevant videos based on the textual metadata associated with the videos using various textual querying techniques. In another embodiment, thevideo search engine120 searches for videos or portions of videos based on their actual audio-visual content rather than relying on textual metadata. For example, if the user enters the search query “car race,” thevideo search engine120 can find and return a car racing scene from a movie, even though the scene may only be a short portion of the movie that is not described in the textual metadata. A process for using the video search engine to locate particular scenes of video based on their audio-visual content is described in more detail below with reference toFIG. 10.
• In one embodiment, thevideo search engine120 also selects a thumbnail image or a set of thumbnail images to display with each retrieved search result. Each thumbnail image comprises an image frame representative of the video's audio-visual content and responsive to the user's query, and assists the user in determining the relevance of the search result. Methods for selecting the one or more representative thumbnail images are described in more detail below with reference toFIGS. 8-9.
• Thevideo annotation engine130 annotates frames or scenes of video from thevideo database175 with keywords relevant to the audio-visual content of the frames or scenes and stores these annotations to thevideo annotation index185, and is one means for performing this function. In one embodiment, thevideo annotation engine130 generates feature vectors from sampled portions of video (e.g., frames of video or short audio clips) from thevideo database175. Thevideo annotation engine130 then applies a learned feature-keyword model195 to the extracted feature vectors to generate a set of keyword scores. Each keyword score represents the relative strength of a learned association between a keyword and one or more features. Thus, the score can be understood to describe a relative likelihood that the keyword is descriptive of the frame's content. In one embodiment, thevideo annotation engine130 also ranks the frames of each video according to their keyword scores, which facilitates scoring and ranking the videos at query time. Thevideo annotation engine130 stores the keyword scores for each frame to thevideo annotation index185. Thevideo search engine120 may use these keyword scores to determine videos or portions of videos most relevant to a user query and to determine thumbnail images representative of the video content. Thevideo annotation engine130 is described in more detail below with reference toFIG. 6.
• Thelearning engine140 uses machine learning to train the feature-keyword model195 that associates features of images or short audio clips with keywords descriptive of their visual or audio content, and is one means for performing this function. Thelearning engine140 processes a set of labeled training images, video, and/or audio clips (“media items”) that are labeled with one or more keywords representative of the media item's audio and or visual content. For example, an image of a dolphin swimming in the ocean may be labeled with keywords such as “dolphin,” “swimming,” “ocean,” and so on. Thelearning engine140 extracts a set of features from the labeled training data (images, video, or audio) and analyzes the extracted features to determine statistical associations between particular features and the labeled keywords. For example, in one embodiment, thelearning engine140 generates a matrix of weights, frequency values, or discriminative functions indicating the relative strength of the associations between the keywords that have been used to label a media item and the features that are derived from the content of the media item. Thelearning engine140 stores the derived relationships between keywords and features to the feature-keyword model195. Thelearning engine140 is described in more detail below with reference toFIG. 2.
• FIG. 2 is a block diagram illustrating a detailed view of thelearning engine140 according to one embodiment. In the illustrated embodiment, the learning engine comprises a click-throughmodule210, afeature extraction module220, akeyword learning module240, anassociation learning module230, a labeledtraining dataset245, afeature dataset255, and akeyword dataset265. Those of skill in the art will recognize that other embodiments can have different modules than the ones described here, and that the functionalities can be distributed among the modules in a different manner. In addition, the functions ascribed to the various modules can be performed by multiple engines.
• The click-throughmodule210 provides an automated mechanism for acquiring a labeledtraining dataset245, and is one means for performing this function. The click-throughmodule210 tracks user search queries on thevideo hosting system100 or on one or more external media search websites. When a user performs a search query and selects a media item from the search results, the click-throughmodule210 stores a positive association between keywords in the user query and the user-selected media item. The click-throughmodule210 may also store negative association between the keywords and unselected search results. For example, a user searches for “dolphin” and receives a set of image results. The image that the user selects from the list is likely to actually contain an image of a dolphin and therefore provides a good label for the image. Based on the learned positive and/or negative associations, the click-throughmodule210 determines one or more keywords to attach to each image. For example, in one embodiment, the click-throughmodule210 stores a keyword for a media item after a threshold number of positive associations between the image and the keyword are observed (e.g., after 5 users searching for “dolphin” select the same image from the result set). Thus, the click-throughmodule210 can statistically identify relationships between keywords and images, based on monitoring user searches and the resulting user actions in selecting search results. This approaches takes advantage of the individual user's knowledge of what counts as relevant images for a given keywords in the ordinary course of their search behavior. In some embodiments, thekeyword identification module240 may use natural language techniques such as stemming and filtering to pre-process search query data in order to identify and extract keywords. The click-throughmodule210 stores the labeled media items and their associated keywords to the labeledtraining dataset245.
• In an alternative embodiment, the labeledtraining dataset245 may instead store training data fromexternal sources291 such as, for example, a database of labeled stock images or audio clips. In one embodiment, keywords are extracted from metadata associated with images or audio clips such as file names, titles, or textual summaries. The labeledtraining dataset245 may also store data acquired from a combination of the sources discussed above (e.g., using data derived from both the click-throughmodule210 and from one or more external databases291).
• Thefeature extraction module220 extracts a set of features from the labeledtraining data245, and is one means for performing this function. The features characterize different aspects of the media in such a way that images of similar objects will have similar features and audio clips of similar sounds will have similar features. To extract features from images, thefeature extraction module220 may apply texture algorithms, edge detection algorithms, or color identification algorithms to extract image features. For audio clips, thefeature extraction module220 may apply various transforms on the sound wave, like generating a spectrogram, apply a set of band-pass filters or auto correlations, and then apply vector quantization algorithms to extract audio features.
• In one embodiment, thefeature extraction module220 segments training images into “patches” and extracts features for each patch. The patches can range in height and width (e.g., 64×64 pixels). The patches may be overlapping or non-overlapping. Thefeature extraction module220 applies an unsupervised learning algorithm to the feature data to identify a subset of the features that most effectively characterize a majority of the images patches. For example, thefeature extraction module220 may apply a clustering algorithm (e.g., K-means clustering) to identify clusters or groups of features that are similar to each other or co-occur in images. Thus, for example, thefeature extraction module220 can identify the 10,000 most representative feature patterns and associated patches.
• Similarly, thefeature extraction module220 segments training audio clips into short “sounds” and extracts features for the sounds. As with the training images, thefeature extraction module220 applies unsupervised learning to identify a subset of audio features most effectively characterizing the training audio clips.
• Thekeyword identification module240 identifies a set of frequently occurring keywords based on the labeledtraining dataset245, and is one means for performing this function. For example, in one embodiment, thekeyword identification module240 determines the N most common keywords in the labeled training dataset (e.g., N=20,000). Thekeyword identification module220 stores the set of frequently occurring keywords in thekeyword dataset265.
• Theassociation learning module230 determines statistical associations between the features in thefeature dataset255 and the keywords in thekeyword dataset265, and is one means for performing this function. For example, in one embodiment, theassociation learning module230 represents the associations in the form of a feature-keyword matrix. The feature-keyword matrix comprises a matrix with m rows and n columns, where each of the m rows corresponds to a different feature vector from thefeature dataset255 and each of the n columns corresponds to a different keyword from the keyword dataset265 (e.g., m=10,000 and n=20,000). In one embodiment, each entry of the feature-keyword matrix comprises a weight or score indicating the relative strength of the correlation between a feature and a keyword in the training dataset. For example, an entry in the matrix dataset may indicate the relative likelihood that an image labeled with the keyword “dolphin” will exhibit a feature particular feature vector Y. Theassociation learning module230 stores the learned feature-keyword matrix to the learned feature-keyword model195. In other alternative embodiments, different association functions and representations may be used, such as, for example, a nonlinear function that relates keywords to the visual and/or audio features.
• FIG. 3 is a flowchart illustrating an embodiment of a method for generating the feature-keyword model195. First, thematrix learning engine140 receives302 a set of labeledtraining data245, for example, from anexternal source291 or from the click-throughmodule210 as described above. Thekeyword learning module240 determines304 the most frequently appearing keywords in the labeled training data245 (e.g., the top 20,000 keywords). Thefeature extraction module220 then generates306 features for thetraining data245 and stores the representative features to thefeature dataset255. Theassociation learning module230 generates308 a feature-keyword matrix mapping the keywords to features and stores the mappings to the feature-keyword model195.
• FIG. 4 illustrates an example embodiment of a process for generating306 the features from the labeledtraining images245. In the example embodiment, thefeature extraction module220 generates402 color features by determining color histograms that represent the color data associated with the image patches. A color histogram for a given patch stores the number of pixels of each color within the patch.
• Thefeature extraction module220 also generates404 texture features. In on embodiment, thefeature extraction module220 uses local binary patterns (LBPs) to represent the edge and texture data within each patch. The LBPs for a pixel represents the relative pixel intensity values of neighboring pixels. For example, the LBP for a given pixel may be an 8-bit code (corresponding to the 8 neighboring pixels in a circle of radius of 1 pixel) with a 1 indicating that the neighboring pixel has a higher intensity value and a 0 indicating that neighboring pixel has a lower intensity value. The feature extraction module then determines a histogram for each patch that stores a count of LBP values within a given patch.
• Thefeature extraction module220 applies406 clustering to the color features and texture features. For example, in one embodiment, thefeature extraction module220 applies K-means clustering to the color histograms to identify a plurality of clusters (e.g. 20) that best represent the patches. For each cluster, a centroid (feature vector) of the cluster is determined, which is representative of the dominant color of the cluster, thus creating a set of dominant color features for all the patches. Thefeature extraction module220 separately clusters the LBP histograms to identify a subset of texture histograms (i.e. texture features) that best characterizes the texture of the patches, and thus identifies the set of dominant texture features for the patches as well. Thefeature extraction module220 then generates408 a feature vector for each patch. In one embodiment, texture and color histograms for a patch are concatenated to form the single feature vector for the patch. Thefeature extraction module220 applies an unsupervised learning algorithm (e.g., clustering) to the set of feature vectors for the patches to generate410 a subset of feature vectors representing a majority of the patches (e.g., the 10,000 most representative feature vectors). Thefeature extraction module220 stores the subset of feature vectors to thefeature dataset255.
• For audio training data, thefeature extraction module220 may generate audio feature vectors by computing Mel-frequency cepstral coefficients (MFCCs). These coefficients represent the short-term power spectrum of a sound based on a linear cosine transform of a log power spectrum on a nonlinear frequency scale. Audio feature vectors are then stored to thefeature dataset255 and can be processed similarly to the image feature vectors. In another embodiment, thefeature extraction module220 generates audio feature vectors by using stabilized auditory images (SAI). In yet another embodiment, one or more band-pass filters are applied to the audio data and features are derived based on correlations within and among the channels. In yet another embodiment, spectrograms are used as audio features.
• FIG. 5 illustrates an example process for iteratively learning a feature-keyword matrix from thefeature dataset255 and thekeyword dataset265. In one embodiment, theassociation learning module230 initializes502 the feature-keyword matrix by populating the entries with initial weights. For example, in one embodiment, the initial weights are all set to zero. For a given keyword, K, from thekeyword dataset265, theassociation learning module230 randomly selects504 a positive training item p+ (i.e. a training item labeled with the keyword K) and randomly selects a negative training item p− (i.e. a training item not labeled with the keyword K). Thefeature extraction module220 determines506 feature vectors for both the positive training item and the negative training item as described above. Theassociation learning engine230 generates508 keyword scores for each of the positive and negative training items by using the feature-keyword matrix to transform the feature vectors from the feature space to the keyword space (e.g., by multiplying the feature vector and the feature-keyword matrix to yield a keyword vector). Theassociation learning module230 then determines510 the difference between the keyword scores. If the difference is greater than a predefined threshold value (i.e., the positive and negative training items are correctly ordered), then the matrix is not changed512. Otherwise, the matrix entries are set514 such that the difference is greater than the threshold. Theassociation learning module230 then determines516 whether or not a stopping criterion is met. If the stopping criterion is not met, the matrix learning performs anotheriteration520 with new positive and negative training items to further refine the matrix. If the stopping criterion is met, then the learning process stops518.
• In one embodiment, the stopping criterion is met when, on average over a sliding window of previously selected positive and negative training pairs, the number of pairs correctly ordered exceeds a predefined threshold. Alternatively, the performance of the learned matrix can be measured by applying the learned matrix to a separate set of validation data, and the stopping criterion is met when the performance exceeds a predefined threshold.
• In an alternative embodiment, in order for the scores to be compatible between keywords, keyword scores are computed and compared for different keywords rather than the same keyword K in each iteration of learning process. Thus, in this embodiment, the positive training item p+ is selected as a training item labeled with a first keyword K₁and the negative training item p− is selected as a training item that is not labeled with a different keyword K₂. In this embodiment, theassociation learning module230 generates keywords scores for each training item/keyword pair (i.e. a positive pair and a negative pair). Theassociation learning module230 then compares the keywords scores in the same manner as described above even though the keyword scores are related to different keywords.
• In alternative embodiments, theassociation learning module230 learns a different type of feature-keyword model195 such as, for example, a generative model or a discriminative model. For example, in one alternative embodiment, theassociation learning module230 derives discriminative functions (i.e. classifiers) that can be applied to a set of features to obtain one or more keywords associated with those features. In this embodiment, theassociation learning module230 applies clustering algorithms to specific types of features or all features that are associated with an image patch or audio segment. Theassociation learning module230 generates a classifier for each keyword in thekeyword dataset265. The classifier comprises a discriminative function (e.g. a hyperplane) and a set of weights or other values, where the weights or values specify the discriminative ability of the feature in distinguishing a class of media items from another class of media items. Theassociation learning module230 stores the learned classifiers to the learned feature-keyword model195.
• In some embodiments, thefeature extraction module220 and theassociation learning module230 iteratively generate sets of features fornew training data245 and re-train a classifier until the classifier converges. The classifier converges when the discriminative function and the weights associated with the sets of features are substantially unchanged by the addition of new training sets of features. In a specific embodiment, an on-line support vector machine algorithm is used to iteratively re-calculate a hyperplane function based on features values associated withnew training data245 until the hyperplane function converges. In other embodiments, theassociation learning module230 re-trains the classifier on a periodic basis. In some embodiments, theassociation learning module230 retrains the classifier on a continuous basis, for example, whenever new search query data is added to the labeled training dataset245 (e.g., from new click-through data).
• In any of the foregoing embodiment, the resulting feature-keyword matrix represents a model of the relationship between keywords (as have been applied to images/audio files) and feature vectors derived from the image/audio files. The model may be understood to express the underlying physical relationship in terms of the co-occurrences of keywords, and the physical characteristics representing the images/audio files (e.g., color, texture, frequency information).
• FIG. 6 illustrates a detailed view of thevideo annotation engine130. In one embodiment, thevideo annotation engine130 includes avideo sampling module610, afeature extraction module620, and athumbnail selection module630. Those of skill in the art will recognize that other embodiments can have different modules than the ones described here, and that the functionalities can be distributed among the modules in a different manner. In addition, the functions ascribed to the various modules can be performed by multiple engines.
• Thevideo sampling module610 samples frames of video content from videos in thevideo database175. In one embodiment, thevideo sampling module610 samples video content from individual videos in thevideo database175. Thesampling module610 can sample a video at a fixed periodic rate (e.g., 1 frame every 10 seconds), a rate dependent on intrinsic factors (e.g. length of the video), or a rate based on extrinsic factors such as the popularity of the video (e.g., more popular videos, based on number of views, would be sampled at a higher frequency than less popular videos). Alternatively, thevideo sample module610 uses scene segmentation to sample frames based on the scene boundaries. For example, thevideo sampling module610 may sample at least one frame from each scene to ensure that the sampled frames are representative of the whole content of the video. In another alternative embodiment, thevideo sample module610 samples entire scenes of videos rather than individual frames.
• Thefeature extraction module620 uses the same methodology as thefeature extraction module220 described above with respect to thelearning engine140. Thefeature extraction module620 generates a feature vector for each sampled frame or scene. For example, as described above each feature vector may comprise 10,000 entries, each being a representative of a particular feature obtained through vector quantization.
• Theframe annotation module630 generates keyword association scores for each sampled frame of a video. Theframe annotation module630 applies the learned feature-keyword model195 to the feature vector for a sample frame to determine the keyword association scores for the frame. For example, theframe annotation module630 may perform a matrix multiplication using the feature-keyword matrix to transform the feature vector to the keyword space. Theframe annotation module630 thus generates a vector of keyword association scores for each frame (“keyword score vector”), where each keyword association score in the keyword score vector specifies the likelihood that the frame is relevant to a keyword of the set of frequently-used keywords in thekeyword dataset265. Theframe annotation module630 stores the keyword score vector for the frame in association with indicia of the frame (e.g. the offset of the frame in the video the frame is part of) and indicia of the video in thevideo annotation index185. Thus, each sampled frame is associated with a keyword vector score that describes the relationship between each of keywords and the frame, based on the feature vectors derived from the frame. Further, each video in the database is thus associated with one or more sampled frames (which can be used for thumbnails) and these sampled frames are associated with keywords, as described.
• In alternative embodiments, thevideo annotation engine130 generates keyword scores for a group of frames (e.g. scenes) rather for each individual sampled frame. For example, keywords scored may be stored for a particular scene of video. For audio features, keyword scores may be stored in association with a group of frames spanning a particular audio clip, such as, for example, speech from a particular individual.
Operation and Use
• When a user inputs a search query of one more words, thesearch engine120 accesses thevideo annotation index185 to find and present a result set of relevant videos (e.g., by performing a lookup in the index185). In one embodiment, thesearch engine120 uses keyword scores in thevideo annotation index185 for the input query words that match the selected keywords, to find videos relevant to the search query and rank the relevant videos in the result set. Thevideo search engine120 may also provide a relevance score for each search result indicating the perceived relevance to the search query. In addition to or instead of the keyword scores in thevideo annotation index185, thesearch engine120 may also access a conventional index that includes textual metadata associated with the videos in order to find, rank, and score search results.
• FIG. 7 is a flowchart illustrating a general process performed by thevideo hosting system100 for finding and presenting video search results. Thefront end server110 receives702 a search query comprising one or more query terms from a user. Thesearch engine120 determines704 a result set satisfying the keyword search query; this result set can be selected using any type of search algorithm and index structure. The result set includes a link to one or more videos having content relevant to the query terms.
• Thesearch engine120 then selects706 a frame (or several frames) from each of the videos in the result set that is representative of the video's content based on the keywords scores. For each search result, thefront end server110 presents708 the selected frames as a set of one or more representative thumbnails together with the link to the video.
• FIGS. 8 and 9 illustrate two different embodiments by which a frame can be selected906 based on keyword scores. In the embodiment ofFIG. 8, thevideo search engine120 selects a thumbnail representative of a video based on textual metadata stored in association with the video in thevideo database175. Thevideo search engine120 selects802 a video from the video database for thumbnail selection. Thevideo search engine120 then extracts804 keywords from metadata stored in association with the video in thevideo database175. Metadata may include, for example, the video title or a textual summary of the video provided by the author or other user. Thevideo search engine120 then accesses thevideo annotation index185 and uses the extracted keyword to choose806 one or more representative frames of video (e.g., by selecting the frame or set of frames having the highest ranked keyword score(s) for the extracted keyword). Thefront end server110 then displays808 the chosen frames as a thumbnail for the video in the search results. This embodiment beneficially ensures that the selected thumbnails will actually be representative of the video content. For example, consider a video entitled “Dolphin Swim” that includes some scenes of a swimming dolphin but other scenes that are just empty ocean. Rather than arbitrarily selecting a thumbnail frame (e.g., the first frame or center frame), thevideo search engine120 will select one or more frames that actually depicts a dolphin. Thus, the user is better able to assess the relevance of the search results to the query.
• FIG. 9 is a flowchart illustrating a second embodiment of a process for selecting a thumbnail to present with a video in a set of search results. In this embodiment, the one or more selected thumbnails are dependent on the keywords provided in the user search query. First, thesearch engine120 identifies902 a set of video search results based on the user search query. Thesearch engine120 extracts904 keywords from the user's search query to use in selecting the representative thumbnail frames for each of the search results. For each video in the result set, thevideo search engine120 then accesses thevideo annotation index185 and uses the extracted keyword to choose906 one or more representative frame of video (e.g., by selecting the one or more frames having the highest ranked keyword score(s) for the extracted keyword). Thefront end server110 then displays908 the chosen frames as thumbnails for the video in the search results.
• This embodiment beneficially ensures that the video thumbnail is actually related to the user's search query. For example, suppose the user enters the query “dog on a skateboard.” A video entitled “Animals Doing Tricks” includes a relevant scene featuring a dog on a skateboard, but also includes several other scenes without dogs or skateboards. The method ofFIG. 9 beneficially ensures that the presented thumbnail is representative of the scene that the user searched for (i.e., the dog on the skateboard). Thus, the user can easily assess the relevance of the search results to the keyword query.
• Another feature of thevideo hosting system100 allows a user to search for specific scenes or events within a video using thevideo annotation index185. For example, in a long action movie, a user may want to search for fighting scenes or car racing scenes, using query terms such as “car race” or “fight.” Thevideo hosting system100 then retrieves only the particular scene or scenes (rather than the entire video) relevant to the query.FIG. 10 illustrates an example embodiment of a process for finding scenes or events relevant to a keyword query. Thesearch engine120 receives1002 a search query from a user and identifies1004 keywords from the search string. Using the keywords, thesearch engine120 accesses the video annotation index185 (e.g., by performing a lookup function) to retrieve a number of frames1006 (e.g., top 10) having the highest keyword scores for the extracted keyword. The search engine then determines1008 boundaries for the relevant scenes within the video. For example, thesearch engine120 may use scene segmentation techniques to find the boundaries of the scene including the highly relevant frame. Alternatively, thesearch engine120 may analyze the keyword scores of surrounding frames to determine the boundaries. For example, thesearch engine120 may return a video clip in which all sampled frames have keyword scores above a threshold. Thesearch engine120 selects1010 a thumbnail image for each video in the result set based on the keyword scores. Thefront end server110 then displays1012 a ranked set of videos represented by the selected thumbnails.
• Another feature of thevideo hosting system100 is the ability to select a set of “related videos” that may be displayed before, during, or after playback of a user-selected video based on thevideo annotation index185. In this embodiment, thevideo hosting system100 extracts keywords from the title or other metadata associated with the playback of the selected video. Thevideo hosting system100 uses the extracted keywords to query thevideo annotation index185 for videos relevant to the keywords; this identifies other videos that are likely to be similar to the user selected video in terms of their actual image/audio content, rather than just having the same keywords in their metadata. Thevideo hosting system100 then chooses thumbnails for the related videos as described above, and presents the thumbnails in a “related videos” portion of the user interface display. This embodiment beneficially provides a user with other videos that may be of interest based on the content of the playback video.
• Another feature of thevideo hosting system100 is the ability to find and present advertisements that may be displayed before, during, or after playback of a selected video, based on the use of thevideo annotation index185. In one embodiment, thevideo hosting system100 retrieves keywords associated with frames of video in real-time as the user views the video (i.e., by performing a lookup in theannotation index185 using the current frame index). Thevideo hosting system100 may then query an advertisement database using the retrieved keywords for advertisements relevant to the keywords. Thevideo hosting system100 may then display advertisements related to the current frames in real-time as the video plays back.
• The above described embodiments beneficially allow a media host to provide video content items and representative thumbnail images that are most relevant to a user's search query. By learning associations between textual queries and non-textual media content, the video hosting system provides improved search results over systems that rely solely on textual metadata.
• The present invention has been described in particular detail with respect to a limited number of embodiments. Those of skill in the art will appreciate that the invention may additionally be practiced in other embodiments. First, the particular naming of the components, capitalization of terms, the attributes, data structures, or any other programming or structural aspect is not mandatory or significant, and the mechanisms that implement the invention or its features may have different names, formats, or protocols. Further, the system may be implemented via a combination of hardware and software, as described, or entirely in hardware elements. Also, the particular division of functionality between the various system components described herein is merely exemplary, and not mandatory; functions performed by a single system component may instead be performed by multiple components, and functions performed by multiple components may instead performed by a single component. For example, the particular functions of the media host service may be provided in many or one module.
• Some portions of the above description present the feature of the present invention in terms of algorithms and symbolic representations of operations on information. These algorithmic descriptions and representations are the means used by those skilled in the art to most effectively convey the substance of their work to others skilled in the art. These operations, while described functionally or logically, are understood to be implemented by computer programs. Furthermore, it has also proven convenient at times, to refer to these arrangements of operations as modules or code devices, without loss of generality.
• It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise as apparent from the present discussion, it is appreciated that throughout the description, discussions utilizing terms such as “processing” or “computing” or “calculating” or “determining” or “displaying” or the like, refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within the computer system memories or registers or other such information storage, transmission or display devices.
• Certain aspects of the present invention include process steps and instructions described herein in the form of an algorithm. All such process steps, instructions or algorithms are executed by computing devices that include some form of processing unit (e.g,. a microprocessor, microcontroller, dedicated logic circuit or the like) as well as a memory (RAM, ROM, or the like), and input/output devices as appropriate for receiving or providing data.
• The present invention also relates to an apparatus for performing the operations herein. This apparatus may be specially constructed for the required purposes, or it may comprise a general-purpose computer selectively activated or reconfigured by a computer program stored in the computer, in which event the general-purpose computer is structurally and functionally equivalent to a specific computer dedicated to performing the functions and operations described herein. A computer program that embodies computer executable data (e.g. program code and data) is stored in a tangible computer readable storage medium, such as, but is not limited to, any type of disk including floppy disks, optical disks, CD-ROMs, magnetic-optical disks, read-only memories (ROMs), random access memories (RAMs), EPROMs, EEPROMs, magnetic or optical cards, application specific integrated circuits (ASICs), or any type of media suitable for persistently storing electronically coded instructions. It should be further noted that such computer programs by nature of their existence as data stored in a physical medium by alterations of such medium, such as alterations or variations in the physical structure and/or properties (e.g., electrical, optical, mechanical, magnetic, chemical properties) of the medium, are not abstract ideas or concepts or representations per se, but instead are physical artifacts produced by physical processes that transform a physical medium from one state to another state (e.g., a change in the electrical charge, or a change in magnetic polarity) in order to persistently store the computer program in the medium. Furthermore, the computers referred to in the specification may include a single processor or may be architectures employing multiple processor designs for increased computing capability.
• Finally, it should be noted that the language used in the specification has been principally selected for readability and instructional purposes, and may not have been selected to delineate or circumscribe the inventive subject matter. Accordingly, the disclosure of the present invention is intended to be illustrative, but not limiting, of the scope of the invention.

Claims (51)

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 ofclaim 1, wherein the media items comprise images.

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

4. The method ofclaim 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 ofclaim 4, wherein the patches are at least partially overlapping.

6. The method ofclaim 4, further comprising:

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

7. The method ofclaim 6, further comprising:

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

8. The method ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 14, wherein selecting the keyword representative of the desired video content comprises using the keyword query as the selected keyword.

17. The method ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 21, wherein the media items comprise images.

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

24. The computer readable storage medium ofclaim 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 ofclaim 24, wherein the patches are at least partially overlapping.

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

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

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

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

28. The computer readable storage medium ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 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 ofclaim 51, wherein the video annotation index maps keywords to videos in a video database according to a machine-learned model.

Images