Transductive multi-label learning for video concept detection

• US 8,218,859 B2
• Filed: 12/05/2008
• Issued: 07/10/2012
• Est. Priority Date: 12/05/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Jingdong, Li, Shipeng, Hua, Xian-Sheng, Zhao, Yinghai
• Primary Examiner(s): Alavi, Amir
• Application Number:
  US12/329,293
• Publication Number:
  US 20100142803A1
• Time in Patent Office: 1,313 Days
• Field of Search: 382159-161, 382/186, 382/187, 382/190, 382/203, 382/209, 382218-220, 382/224, 382/228, 375/240.08, 375/340, 704/200, 704/223, 704/246, 704/255, 704/256.4, 715/723, 348/231.2, 348/699, 348/722, 703/2, 345/419, 345/427, 345/656
• US Class Current: 382/160
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models
• CPC Class Codes: G06V 10/85 Markov-related models; Markov random fields
• CPC Class Codes: G06V 20/41 Higher-level, semantic clustering, classification or understanding of video scenes, e.g. detection, labelling or Markovian modelling of sport events or news items segmenting video sequences G06V20/49

Abstract

This disclosure describes various exemplary method and computer program products for transductive multi-label classification in detecting video concepts for information retrieval. This disclosure describes utilizing a hidden Markov random field formulation to detect labels for concepts in a video content and modeling a multi-label interdependence between the labels by a pairwise Markov random field. The process groups the labels into several parts to speed up a labeling inference and calculates a conditional probability score for the labels, the conditional probability scores are ordered for ranking in a video retrieval evaluation.

Claims

1. A method for a transductive multi-label classification, implemented at least in part by a computing device, the method comprising:

utilizing a hidden Markov random field formulation to identify labels for concepts in a video content;

modeling a multi-label interdependence between the labels by using a pairwise Markov random field, wherein combinations of pairwise relationships over the labels are seamlessly modeled into the hidden Markov random field formulation;

grouping the labels into several parts to speed up a labeling inference; and

calculating conditional probability scores for the labels, wherein the conditional probability scores are ordered for ranking in a video retrieval.

2. The method of claim 1, wherein the modeling comprises determining a compatibility between a label and a pre-given label on labeled data points.

3. The method of claim 1, wherein the modeling comprises determining whether a label consistency exists between neighboring data points that have similar type features.

4. The method of claim 1, wherein the modeling comprises determining whether a multi-label interdependence over unlabeled data points is similar to a multi-label interdependence over labeled data points.

5. The method of claim 1, wherein the grouping the labels into several parts to speed up a labeling inference comprises using a label chunklet analysis to categorize the labels into several subsets.

6. The method of claim 5, wherein the label chunklet analysis further comprises:

measuring a relationship between each pair of labels;

pursuing common concepts that have large relationship degrees with other concepts; and

dividing remaining concepts into several chunklets, wherein a relationship between chunklets that are different is smaller and a relationship within a chunklet is larger.

7. The method of claim 1, further comprising using an optimization algorithm to infer the labels by combining:

a tree-reweighted message passing, which is an iterative statistical inference algorithm; and

graph cuts, which estimate an intermediate inductive decision function.

8. The method of claim 1, further comprising determining the multi-label interdependence between the labels by using concept pairs.

9. The method of claim 1, further comprising integrating in a single formulation, relationships between pairs of labels, the relationships including at least one of:

a positive-positive relationship, a positive-negative relationship, a negative-positive relationship, or a negative-negative relationship.

10. The method of claim 1, wherein the calculating the conditional probability scores for the labels comprises calculating:

a probability between two variables to describe a compatibility;

an aggregated probability that the labeling is consistent between data points with similar features;

or

a probability of the pairwise interdependence between the labels.

11. A computing device storage media storing computer-readable instructions that, when executed, perform acts comprising:

detecting concepts in a video content by using a hidden Markov random field formulation to identify labels for the concepts in the video content;

determining a transductive multi-label classification by finding the labels that are similar as pre-given labels on labeled data points;

determining the labels are consistent between neighboring points;

determining a multi-label interdependence on unlabeled data points is similar to a multi-label interdependence on the labeled data points;

conducting a chunklet analysis for the multi-label interdependence on the unlabeled data points and the multi-label interdependence on the labeled data points; and

retrieving a video based on an ordered score from the transductive multi-label classification.

12. The computing device storage media of claim 11, further comprising an act of integrating in a single formulation, relationships between pairs of labels, the relationships including at least one of:

a positive-positive relationship, a positive-negative relationship, a negative-positive relationship, or a negative-negative relationship.

13. The computing device storage media of claim 11, wherein the chunklet analysis include acts to:

measure a relationship between each pair of labels according to a normalized mutual information (NMI); and

pursue common concepts that have large relationship degrees with other concepts.

14. The computing device storage media of claim 11, further comprising an act of calculating conditional probability scores for the labels, wherein the conditional probability scores are ordered for ranking in a video retrieval.

15. A method for a transductive multi-label classification, implemented at least in part by a computing device, the method comprising:

detecting concepts in a video content by using a hidden Markov random field formulation to identify labels for the concepts by;

determining the transductive multi-label classification by measuring similarity scores based on the labels and pre-given labels on labeled data points;

determining the labels are consistent between neighboring points;

determining a multi-label interdependence on unlabeled data points is similar to a multi-label interdependence on the labeled data points; and

analyzing the concepts for the multi-label interdependence on the unlabeled data points and the multi-label interdependence on the labeled data points by using chunklet analysis.

16. The method of claim 15, further comprising constructing a graph with:

a set of hidden nodes to represent binary-valued labels;

a set of observable nodes to represent pre-given binary-valued labels;

a first set of edges to connect the set of hidden nodes and the set of observable nodes, wherein the first set of edges represents observable edges;

a second set of edges to connect the hidden nodes; and

a third set of edges to connect a pair of nodes.

17. The method of claim 16, wherein:

the set of hidden nodes represents the binary-valued labels that correspond to associated concepts;

the set of observable nodes represents the pre-given binary-valued labels that are over the labeled data points;

the first set of edges represents a compatibility between the set of hidden nodes representing the binary-valued labels that correspond to the associated concepts and the set of observable nodes representing the pre-given binary valued labels that are over the labeled data points;

the second set of edges represents a labeling consistency between the neighboring data points for visually similar videos, if corresponding data points are the neighboring data points; and

the third set of edges models the multi-label interdependence on the unlabeled data points and the multi-label interdependence on the labeled data points for each video.

18. The method of claim 15, wherein the chunklet analysis comprises actions to perform:

measuring a relationship between each pair of labels according to a normalized mutual information (NMI); and

pursuing common concepts that have large relationship degrees with other concepts.

19. The method of claim 15, further comprising calculating probability scores for the labels, wherein the probability scores are ordered for ranking in a video retrieval.

20. The method of claim 15, further comprising determining a multi-label interdependence between the labels on the labeled data points and on the unlabeled data points by analyzing relationships between concept pairs.