System And Method For Annotating And Searching Media

• US 20110314367A1
• Filed: 06/21/2011
• Published: 12/22/2011
• Est. Priority Date: 12/22/2008
• Status: Abandoned Application

• Current Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Original Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Inventors: Chang, Shih-Fu, Jebara, Tony, Wang, Jun
• Application Number:
  US13/165,553
• Publication Number:
  US 20110314367A1
• Time in Patent Office: Days
• US Class Current: 715/230
• CPC Class Codes: G06F 16/437 Administration of user profiles, e.g. generation, initialisation, adaptation, distribution

Abstract

A system and method for labeling and classifying multimedia data is provided that includes novel label propagation techniques and classification function characteristics. The system and method corrects and propagates a small number of potentially erroneous labels to a large amount of multimedia data and generate optimal ways of ranking, classification, and presentation of the data sets. The disclosed systems and methods improve upon prior systems and methods and provide an improved approach to the problems of imbalanced data sets and incorrect label data.

Claims

1. A method for labeling multimedia objects comprising:

storing a multimedia affinity graph in one or more memories, wherein said affinity graph represents a group of multimedia data samples as nodes and comprises edges measuring relatedness among data samples;

storing a multimedia label set in said one or more memories, wherein the labels in said label set correspond to a subset of said multimedia data samples;

calculating an classification function based on the initial label set and weights of the affinity graph using a processor associated with said one or more memories, wherein calculating said optimization function comprises iteratively performing at least updating an existing label in said label set or predicting a new label for a sample using said processor; and

outputting a set of labeled multimedia objects using said processor.

2. The method of claim 1 wherein said multimedia label set is input by a user.

3. The method of claim 1 wherein said multimedia label set is automatically input.

4. The method of claim 1, wherein iteratively predicting a new label comprises automatically selecting the most informative data sample, predicting its corresponding class and labeling the corresponding data sample.

5. The method of claim 1, wherein updating an existing label in said label set comprises using said processor to perform a greedy search among the gradient direction of said classification function.

6. The method of claim 1, wherein each labeled data sample is further normalized based on a regularization matrix calculated using members of a corresponding class and connectivity degrees of the corresponding nodes in the graph.

7. The method of claim 1, wherein calculating an classification function comprises incremental calculation using graph superposition, wherein a newly added label is incorporated incrementally without calculating the optimal classification function using all labels.

8. The method of claim 1 wherein noisy labels are replaced.

9. The method of claim 8, wherein replacing noisy labels comprises adding one or more new labels for every label that is removed.

10. The method of claim 9, wherein replacing noisy labels or predicting new labels comprises updating a node regularization matrix.

11. The method of claim 1, wherein replacing noisy labels or predicting new labels comprises minimizing an objective function.

12. A method for changing noisy labels in a data set comprising:

calculating an objective function based on a label set and a classification function over at least one of a labeled data set and an unlabeled data set using a processor;

performing a greedy search among gradient directions of said classification function to modify the objective function using said processor;

removing a label from said data set based on said greedy search of said classification function using said processor.

13. The method of claim 12 further comprising adding one or more labels to said label set based on said greedy search among gradient directions of said classification function using said processor.

14. The method of claim 13 further comprising updating a node regularization matrix.

15. The method of claim 12, wherein calculating an classification function comprises incremental calculation using graph superposition, wherein a newly added label is incorporated incrementally without calculating the optimal classification function using all labels.

16. The method of claim 12 wherein performing a greedy search among gradient directions of said classification function comprises performing a bidirectional search.

17. The method of claim 12 wherein removing a label comprises unlabeling previously labeled nodes that have the maximum value of the gradient function.

18. The method of claim 13 wherein adding one or more labels comprises labeling one or more previously unlabeled nodes having the minimum values of the gradient function.

19. A system for labeling multimedia objects comprising:

one or more memories storing a multimedia affinity graph, wherein said affinity graph represents a group of multimedia data samples as nodes and comprises edges measuring relatedness among data samples, and storing a multimedia label set, wherein the labels in said label set correspond to a subset of said multimedia data samples;

a processor coupled to said one or more memories, wherein said processor;

calculates a classification function based on the initial label set and weights of the affinity graph, wherein calculating said optimization function comprises iteratively performing of updating an existing label in said label set or predicting a new label for a sample; and

outputs a set of labeled multimedia objects.

20. The system of claim 19 wherein said multimedia label set is input by a user using an input device coupled to said one or more memories.

21. The system of claim 19 wherein said multimedia label set is automatically input.

22. The system of claim 19, wherein iteratively predicting a new label comprises automatically selecting the most informative data sample, predicting its corresponding class and labeling the corresponding data sample using said processor.

23. The system of claim 22 wherein iteratively updating said label set is based on a greedy search among the gradient direction of said classification function performed by said processor.

24. The system of claim 19, wherein each labeled data sample is further normalized based on a regularization matrix calculated using members of a corresponding class and connectivity degrees of the corresponding nodes in the graph.

25. The system of claim 19, wherein calculating a classification function comprises incremental calculation using graph superposition, wherein a newly added label is incorporated incrementally without calculating the optimal classification function using all labels.

26. The system of claim 19 wherein noisy labels are replaced using said processor.

27. The system of claim 26, wherein replacing noisy labels comprises adding one or more new labels using said processor for every label that is removed and said.

28. The system of claim 27, wherein replacing noisy labels or predicting new labels comprises updating a node regularization matrix using said processor.

29. The system of claim 19, wherein replacing noisy labels or predicting new labels comprises minimizing an objective function using said processor.

30. A system for changing noisy labels in a label set comprising:

a processor instructed to;

calculate an objective function based on a classification function and a label set using a processor;

perform a greedy search among gradient directions of said classification function using said processor; and

remove a label from said data set based on said greedy search of said classification function.

31. The system of claim 30 wherein said processor adds one or more labels to said label set based on said greedy search among gradient directions of said classification function.

32. The system of claim 31 wherein where said processor further updates a node regularization matrix.

33. The system of claim 30 wherein performing a greedy search among gradient directions of said classification function by said processor comprises performing a bidirectional search.

34. The system of claim 30 wherein removing a label by said processor comprises unlabeling previously labeled nodes that have the maximum value of the gradient function.

35. The system of claim 31 wherein adding one or more labels by said processor comprises labeling one or more previously unlabeled nodes having the minimum values of the gradient function.

36. A computer readable media containing digital information which when executed cause a processor to:

calculate a classification function based on a initial label set and weights of an affinity graph, wherein said affinity graph represents a group of multimedia data samples as nodes and comprises edges measuring relatedness among data samples, wherein calculating said optimization function comprises iteratively performing at least updating an existing label in said label set or predicting a new label for a data sample; and

output a set of labeled multimedia objects.

37. The media of claim 36 wherein iteratively predicting a new label comprises automatically selecting the most informative data sample, predicting its corresponding class and labeling the corresponding data sample.

38. The media of claim 37 wherein said digital information when executed causes said processor to update an existing label in said label set based on a greedy search among the gradient direction of said classification function.

39. The media of claim 36 wherein said digital information when executed further causes said processor to normalize each labeled data sample based on a regularization matrix calculated using members of a corresponding class and connectivity degrees of the corresponding nodes in said affinity graph.

40. The media of claim 36, wherein calculating a classification function comprises incremental calculation using graph superposition, wherein a newly added label is incorporated incrementally without calculating the optimal classification function using all labels.

41. The media of claim 36, where said digital information when executed further causes said processor to replace noisy labels.

42. The media of claim 41, wherein replacing noisy labels comprises adding one or more new labels for every label that is removed.

43. The media of claim 42, wherein replacing noisy labels or predicting new labels comprises updating a node regularization matrix.

44. The media of claim 36, wherein replacing noisy labels or predicting new labels comprises minimizing an objective function.

45. A computer readable media containing digital information which when executed cause a processor to:

calculate an objective function based on a label set and a classification function over at least one of a labeled data set and an unlabeled data set;

perform a greedy search among gradient directions of said classification function to modify the objective function;

remove a label from said label set based on said greedy search of said classification function.

46. The media of claim 45 wherein said digital information when executed further cause a processor to add one or more labels to said label set based on said greedy search among gradient directions of said classification function.

47. The media of claim 46 wherein said digital information when executed further cause a processor to update a node regularization matrix.

48. The media of claim 45 wherein performing a greedy search among gradient directions of said classification function comprises performing a bidirectional search.

49. The media of claim 45 wherein removing a label comprises unlabeling previously labeled nodes that have the maximum value of the gradient function.

50. The media of claim 46 wherein adding one or more labels comprises labeling one or more previously unlabeled nodes having the minimum value of the gradient function.

51. A method for normalizing labels associated with data samples from data classes of different sizes comprising:

storing in one or more memories an affinity graph, wherein said affinity graph represents a group of data samples as nodes and comprises edges measuring relatedness among data samples, and a label set, wherein the labels in said label set correspond to a subset of said data samples;

calculating a regularization matrix based on class members of said data samples and the connectivity degrees of nodes corresponding to said data samples in the graph;

normalizing labels associated with data samples by label weights, wherein said normalization is based on said regularization matrix

52. A system for normalizing labels associated with data samples from data classes of different sizes comprising:

one or more memories storing an affinity graph, wherein said affinity graph represents a group of data samples as nodes and comprises edges measuring relatedness among data samples, and storing a label set, wherein the labels in said label set correspond to a subset of said data samples;

a processor instructed to;

calculate a regularization matrix based on corresponding class members of said data samples and the connectivity degrees of nodes corresponding to said data samples in the graph;

normalize labels associated with data samples by label weights, wherein said normalization is based on said regularization matrix

53. A computer readable media containing digital information which when executed cause a processor to:

access an affinity graph from one or more memories, wherein said affinity graph represents a group of data samples as nodes and comprises edges measuring relatedness among data samples;

access a label set from said one or more memories, wherein the labels in said label set correspond to a subset of said data samples;

calculate a regularization matrix based on class members of said data samples and the connectivity degrees of nodes corresponding to said data samples in the graph;

normalize labels associated with data samples by label weights, wherein said normalization is based on said regularization matrix.

54. A method for labeling multimedia objects comprising:

storing a plurality of multimedia affinity graphs in one or more memories, wherein each of the plurality of affinity graphs represents one or more features of a group of multimedia data samples as nodes and comprises edges measuring relatedness among data samples;

storing a multimedia label set in said one or more memories, wherein the labels in said label set correspond to a subset of said multimedia data samples;

calculating the optimal prediction functions for each of the plurality of affinity graphs;

calculating the weighted combination over the prediction functions for each of the plurality of affinity graphs resulting in a weight assigned to each affinity graph wherein larger weight values indicate a higher degree of relevance for the corresponding affinity graph;

calculating an classification function based on the initial label set and weights of the affinity graphs using a processor associated with said one or more memories, wherein calculating said optimization function comprises iteratively performing at least updating an existing label in said label set or predicting a new label for a sample using said processor; and

outputting a set of labeled multimedia objects using said processor.

55. A system for labeling multimedia objects comprising:

one or more memories storing a plurality of multimedia affinity graphs, wherein each of the plurality of affinity graphs represents one or more features of a group of multimedia data samples as nodes and comprises edges measuring relatedness among data samples, and storing a multimedia label set, wherein the labels in said label set correspond to a subset of said multimedia data samples;

a processor coupled to said one or more memories, wherein said processor;

calculates the optimal prediction functions for each of the plurality of affinity graphs;

calculates the weighted combination over the prediction functions for each of the plurality of affinity graphs resulting in a weight assigned to each affinity graph wherein larger weight values indicate a higher degree of relevance for the corresponding affinity graph;

calculates a classification function based on the initial label set and weights of the affinity graphs, wherein calculating said optimization function comprises iteratively performing of updating an existing label in said label set or predicting a new label for a sample; and

outputs a set of labeled multimedia objects.