VIDEO SEARCH RE-RANKING VIA MULTI-GRAPH PROPAGATION

• US 20090292685A1
• Filed: 05/22/2008
• Published: 11/26/2009
• Est. Priority Date: 05/22/2008
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Liu, Jingjing, Hua, Xian-Sheng, Li, Shipeng, Lai, Wei
• Application Number:
  US12/125,059
• Publication Number:
  US 20090292685A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/73 Querying
• CPC Class Codes: G06F 16/78 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually

Abstract

A video search re-ranking via multi-graph propagation technique employing multimodal fusion in video search is presented. It employs not only textual and visual features, but also semantic and conceptual similarity between video shots to rank or re-rank the search results received in response to a text-based search query. In one embodiment, the technique employs an object-sensitive approach to query analysis to improve the baseline result of text-based video search. The technique then employs a graph-based approach to text-based search result ranking or re-ranking. To better exploit the underlying relationship between video shots, the re-ranking scheme simultaneously leverages textual relevancy, semantic concept relevancy, and low-level-feature-based visual similarity. The technique constructs a set of graphs with the video shots as vertices, and the conceptual and visual similarity between video shots as hyperlinks. A modified topic-sensitive PageRank algorithm is then applied to these graphs to determine the overall relevancy ranking.

Claims

1. A computer-implemented process for ranking the relevance of video returned in response to a search, comprising:

inputting search results of video shots with text-based relevance scores received in response to a text string search query;

creating a set of hierarchical graphs based on different semantic concepts, with the video shots as vertices and hyperlinks, that exploit conceptual similarity and visual similarity between the video shots, as edges;

applying a topic-sensitive ranking procedure to propagate the text-based relevance scores of the video shots through the hyperlinks in each hierarchical graph of the set of hierarchical graphs; and

aggregating the results of the topic-sensitive ranking procedure from the set of hierarchical graphs to determine the final ranking of the video shot search results.

2. The computer-implemented process of claim 1, further comprising prior to applying the topic-sensitive ranking procedure:

converting the text string search query into an object query that identifies targeted objects in the text string search query; and

modifying the text-based relevance scores by assigning greater weight to video shot search results of text string query terms that represent the targeted objects.

3. The computer-implemented process of claim 1 further comprising constructing each hierarchical graph by:

taking the video shots as vertices wherein each text-relevance score is the weight of the vertex; and

assigning a weight of zero to video shots that are determined to be irrelevant to the text string search query.

4. The computer-implemented process of claim 1, further comprising constructing each hierarchical graph by:

for each of a set of concepts,

using a concept detection model that predicts the likelihood of a video shot being related to a given concept and assigns an associated confidence score; and

classifying each video shot into a positive, relevant category or a negative, irrelevant category; and

ranking the video shots according to their confidence scores of being relevant to the given concept.

5. The computer-implemented process of claim 4 further comprising refining the hyperlinks of each hierarchical graph by:

pruning video shot pairs of the hierarchical graph that are not visually similar by employing a content-based visual similarity model.

6. The computer-implemented process of claim 5 wherein the content-based visual similarity model compares the similarity of the video shots using low level features.

7. The computer-implemented process of claim 6 further comprising using color momentum as the low level features.

8. The computer-implemented process of claim 4, further comprising refining the hyperlinks of each hierarchical graph by:

assigning the direction of the hyperlink for each pair of video shots based on the confidence score of each video shot of the pair of video shots.

9. The computer-implemented process of claim 8, further comprising the direction of the hyperlink from the video shot with a lower confidence score to the video shot with a higher confidence score.

10. The computer-implemented process of claim 1, further comprising computing a set of graphs for each semantic concept.

11. The computer-implemented process of claim 1, further comprising:

for each concept,

computing a query-dependent score for each video shot for each graph;

computing a new relevance score for each video shot using the query dependent score; and

aggregating the new relevance score for each video shot for each graph for the given concept to determine the final ranking of the video shot search results for the given concept.

12. The computer-implemented process of claim 11 further comprising aggregating the final ranking of the video shot search results for each concept to determine the final ranking of the video shot search results for all concepts.

13. A computer-implemented process for ranking the relevance of video shots returned in response to a search, comprising:

inputting video shot search results with text-based relevance scores received in response to a text string search query;

determining a first expansion of query terms by expanding the number of query terms by segmenting the test string search query and computing modified text-based relevance scores using the first expansion of the number of query terms;

determining a second expansion of query terms by expanding the number of query terms by performing name entity generalization;

further modifying the modified text-based relevance scores by identifying targeted objects in the text string search query and the first and second expansions of query terms by assigning greater weight to video shot search results of query terms that represent the targeted objects; and

using the further modified text-based relevance scores and the first and second expansion of query terms to determine the final ranking of the video shot search results.

14. The computer-implemented process of claim 13 further comprising identifying the targeted objects by:

using visual content-based detection to compare query terms to a list of concepts;

using part-of-speech identification to tag nouns and noun phrases in the query as targeted objects;

identifying adverbs that with refinement meanings and taking the noun and noun-phrases following the adverbs with refinement meanings as targeted objects; and

identifying name entities in the query extracting the targeted object by identifying the part of the name which is more often used as the reference of the name entity.

15. The computer-implemented process of claim 13 wherein determining the first expansion of query terms and modified text-based relevance scores further comprises:

segmenting the text string search query into term sequences based on an N-gram method;

inputting term sequences into a search engine as different forms of the query;

aggregating the different video shots retrieved by the search query sequences with different weights, where a higher segment n-gram query is assigned a greater relevance weight.

16. The computer-implemented process of claim 13 wherein determining the second expansion of query terms further comprises further comprises:

using name entity generalization to classify name entities in the text string query into several predefined categories;

assigning each name entity a label of its corresponding category;

tagging names in both the text string query and database elements in a database being searched with the same set of category labels; and

using the tagged names to retrieve database elements that contain the same tagged names as are in the text string query.

17. The computer-implemented process of claim 13 wherein using the further modified text-based relevance scores and first and second expansion of query terms to determining the final relevance, further comprises using query term frequency and semantic importance of the targeted objects in re-weighting the text-based relevance scores.

20. The system of claim 17, further comprising a module to use object-sensitive query analysis to modify the ranking of the ranked set of video shots prior to constructing the set of graphs.

18. A system for ranking the results of video data returned in response to a search query, comprising:

a general purpose computing device;

a computer program comprising program modules executable by the general purpose computing device, wherein the computing device is directed by the program modules of the computer program to,

input a ranked set of video shot search results received in response to a text-based search query;

using the ranked set of video shot search results, construct a set of graphs based on semantic similarity with video shots as vertices and semantic concept similarity and visual similarity between video shots as hyperlinks; and

apply a topic sensitive ranking procedure to the set of graphs to re-rank the ranked set of video shots.

19. The system of claim 18, wherein the module to construct a set of graphs further comprises modules to:

weight each vertex of each graph by using a text-based search model;

construct each hyperlink of each graph by employing a concept detection model;

prune each graph by employing a visual similarity comparison model; and

assign each hyperlink of each graph a direction assignment with a confidence score computed using the concept detection model.