Bayesian video search reranking

• US 8,180,766 B2
• Filed: 09/22/2008
• Issued: 05/15/2012
• Est. Priority Date: 09/22/2008
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Yang, Linjun, Wang, Jingdong, Hua, Xian-Sheng, Tian, Xinmei
• Primary Examiner(s): Stevens, Robert
• Application Number:
  US12/235,509
• Publication Number:
  US 20100082614A1
• Time in Patent Office: 1,331 Days
• Field of Search: 707/999.5, 707/726, 707/723, 707/758
• US Class Current: 707/723
• 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/785 using colour or luminescence
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06F 18/2155 characterised by the incorporation of unlabelled data, e.g. multiple instance learning [MIL], semi-supervised techniques using expectation-maximisation [EM] or naïve labelling
• CPC Class Codes: G06F 18/29 Graphical models, e.g. Bayesian networks
• CPC Class Codes: G06V 10/774 Generating sets of training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06V 10/7753 Incorporation of unlabelled data, e.g. multiple instance learning [MIL]

Abstract

A general framework for video search reranking is disclosed which explicitly formulates reranking into a global optimization problem from the Bayesian perspective. Under this framework, with two novel pair-wise ranking distances, two effective video search reranking methods, hinge reranking and preference strength reranking, are disclosed. Experiments conducted on the TRECVID dataset have demonstrated that the disclosed methods outperform several existing reranking approaches.

Claims

1. A method for improving the ranking of a document search system, the method comprising:

obtaining video data, wherein the video data includes features of a number of individual videos;

extracting the features from the video data;

obtaining a query descriptive of a subset of individual videos of the video data;

obtaining a ranked list of individual videos, wherein the ranking of the individual videos is based on a search technique using text associated with the videos; and

re-ranking the ranked list of individual videos, wherein the individual videos are re-ranked based at least in part on maximizing a product of (i) a conditional prior that is indicative of a consistency of ranking scores among individual videos in which the extracted features of the individual videos are determined to be visually similar, and (ii) a likelihood that is reflective of a disagreement between the ranked list of individual videos and the re-ranked list.

2. The method of claim 1 wherein re-ranking the ranked list of individual videos involves the use of a quadratic optimization technique.

3. The method of claim 2 wherein the quadratic optimization technique utilizes:

4. The method of claim 1 wherein re-ranking the ranked list of individual videos involves the use of a preference strength technique.

5. The method of claim 4 wherein the preference strength technique utilizes:

2 Lr= c

where L is the Laplacian matrix and r is a sample of a ranking score.

6. The method of claim 1, wherein obtaining video data and extracting the features from the video data are executed when the search system is crawling the videos from the Web.

7. An image search system for improving the ranking, the image search system including a processor and a memory, the system comprising:

a component for obtaining image data, wherein the image data includes features of a number of individual images;

a component for extracting the features from the image data, wherein the processor executes instructions stored in the memory to extract the features from the image data;

a component for obtaining a query descriptive of a subset of individual images of the image data;

a component for obtaining a ranked list of individual images, wherein the ranking of the individual images is based on a search technique using text associated with the videos; and

a component for re-ranking the ranked list of individual images, wherein the individual images are re-ranked based at least in part on maximizing a product of (i) a conditional prior that is indicative of a consistency of ranking scores among individual images in which the extracted features of the individual images are determined to be visually similar, and (ii) a likelihood that is reflective of a disagreement between the ranked list of individual images and the re-ranked list, and wherein the processor executes instructions stored in the memory to re-rank the ranked list of individual images.

8. The system of claim 7 wherein re-ranking the ranked list of individual images involves the use of a quadratic optimization technique.

9. The system of claim 8 wherein the quadratic optimization technique utilizes:

10. The system of claim 7 wherein re-ranking the ranked list of individual images involves the use of a preference strength technique.

11. The system of claim 10 wherein the preference strength technique utilizes:

2 Lr= c

where L is the Laplacian matrix and r is a sample of a ranking score.

12. The system of claim 7, wherein obtaining image data and extracting the features from the image data are executed when the search system is crawling the videos from the Web.

13. The system of claim 7, wherein extracting features includes extracting data that describes color, edge, and texture.

14. The image search system of claim 7, wherein the individual images are re-ranked based at least in part on maximizing a product of the conditional prior and the likelihood.

15. A computer-readable storage media comprising computer executable instructions to, upon execution, perform a process method for improving ranking scores of a document search system, the process including:

obtaining video data, wherein the video data includes features of a number of individual videos;

extracting the features from the video data;

obtaining a query describing a subset of individual videos of the video data;

obtaining a ranked list of individual videos, wherein the ranking of the individual videos is based on a search technique using the text; and

re-ranking the ranked list of individual videos, wherein the individual videos are re-ranked based at least in part on maximizing a product of (i) a conditional prior that is indicative of a consistency of ranking scores among individual videos in which the extracted features of the individual videos are determined to be visually similar, and (ii) a likelihood that is reflective of a disagreement between the ranked list of individual videos and the re-ranked list.

16. The computer-readable storage media of claim 15, wherein the process of re-ranking the ranked list of individual videos involves the use of a quadratic optimization technique.

17. The computer-readable storage media of claim 16, wherein the quadratic optimization technique utilizes:

18. The computer-readable storage media of claim 15, wherein the process of re-ranking the ranked list of individual videos involves the use of a preference strength technique.

19. The computer-readable storage media of claim 18, wherein the preference strength technique utilizes:

2 Lr= c

where L is the Laplacian matrix and r is a sample of a ranking score.

20. The computer-readable storage media of claim 15, wherein obtaining video data and extracting the features from the video data are executed when the search system is crawling the videos from the Web.

21. The computer-readable storage media of claim 15, wherein extracting features includes extracting data that describes color, edge, and texture.

22. The computer-readable storage media of claim 15, wherein the individual videos are re-ranked based at least in part on maximizing a product of the conditional prior and the likelihood.