System and methods for providing adaptive media property classification

• US 7,376,672 B2
• Filed: 11/15/2004
• Issued: 05/20/2008
• Est. Priority Date: 08/20/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Weare, Christopher B.
• Primary Examiner(s): LE, DEBBIE M
• Application Number:
  US10/988,810
• Publication Number:
  US 20050071329A1
• Time in Patent Office: 1,282 Days
• Field of Search: None
• US Class Current: 707/753
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/634 Query by example, e.g. query by humming
• CPC Class Codes: G06F 16/635 Filtering based on additional data, e.g. user or group profiles
• CPC Class Codes: G06F 16/639 using playlists
• CPC Class Codes: G06F 16/683 using metadata automatically derived from the content
• CPC Class Codes: Y10S 707/914 Video
• CPC Class Codes: Y10S 707/915 Image
• CPC Class Codes: Y10S 707/916 Audio
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A system and methods are provided for automatically classifying data according to perceptual properties of the data to form a classification chain that is suited to the searching and sorting of large databases of media entities. During classification, experts assign each media entity in the training data set to one or more classes, with each class corresponding to a given subset of perceptual properties of the data. In conjunction with digital signal processing properties of the data corresponding to the perceptual properties, the classified data is then used to construct an initial classification chain. During operation, when presented with an unclassified entry, the classification chain returns an estimate of the class of the entry, as well as a confidence measure that is proportional to the level of confidence of the class assignment. Over time, as the classification chain evolves, the classification chain becomes more and more effective for quickly characterizing media entities.

Claims

1. A method of classifying data according to perceptual properties of the data, the method being suited for searching and sorting large databases of media entities, including music, video and image databases, the method comprising:

assigning to each media entity of a plurality of media entities in a data set to at least one class, each class of said at least one class corresponding to a subset of perceptual properties pre-defined for the data set;

processing each media entity of said data set to extract at least one digital signal processing characteristic for each media entity;

generating a plurality of feature vectors for said plurality of media entities, wherein each vector includes said at least one class and said at least one digital signal processing characteristic; and

forming a classification chain based upon said plurality of feature vectors, wherein a human adds a new subset of perceptual properties to the classification chain defined by the plurality of feature vectors.

2. The method according to claim 1, further comprising calculating a neighborhood distance within the vector space of said classification chain for each of said at least one perceptual class.

3. The method according to claim 2, wherein said neighborhood distance defines a distance within which two vectors in the classification chain space are in the same neighborhood.

4. The method according to claim 2, wherein said calculating of a neighborhood distance for each of said at least one perceptual class includes determining a distance within which two vectors of the classification chain possess the same class given a threshold degree of error.

5. The method according to claim 4, wherein a human determines said threshold degree of error that will be tolerated, said threshold degree of error placing a maximum limit on the distance that may be used for determining neighborhoods.

6. The method according to claim 1, further comprising:

processing an unclassified media entity to extract at least one digital signal processing characteristic for the unclassified media entity;

generating a vector for the unclassified media entity including said at least one digital signal processing characteristic;

presenting the vector for the unclassified media entity to the classification chain; and

classifying the unclassified entry with an estimate of at least one perceptual class by calculating the representative at least one perceptual class of the subset of the plurality of vectors of the classification chain located in the neighborhood of the vector for the unclassified entity.

7. The method according to claim 6, wherein said classifying of the unclassified entry includes locating the subset of the plurality of vectors of the classification chain located in the neighborhood.

8. The method according to claim 7, wherein said locating includes calculating, as the set of vectors of the plurality of vectors of the classification chain within the neighborhood distance, the set of vectors of the plurality of vectors of the classification chain within a maximum Euclidian distance for classifying new unclassified entities within a threshold tolerance.

9. The method according to claim 8, wherein a human determines said maximum Euclidian distance for purposes of determining the neighborhood vectors within the threshold tolerance.

10. The method according to claim 6, wherein said classifying of the unclassified entry includes classifying the unclassified entry with a median class represented by the neighborhood.

11. The method according to claim 6, wherein said class is described by a numerical value and said classifying of the unclassified entry includes classifying the unclassified entry with a mean of numerical values found in the neighborhood.

12. The method according to claim 6, wherein said classifying includes returning at least one number indicating the level of confidence of the class assignment.

13. The method according to claim 12, wherein said classifying includes returning a ratio defined by the number of entries in the neighborhood having the representative class over the number of entries in the neighborhood not having the representative class.

14. The method according to claim 12, wherein said class is described by a numerical value and said classifying includes returning a standard deviation of the numerical values in the neighborhood.

15. A computer-readable storage medium having stored thereon instructions for classifying data according to perceptual properties of the data, the instructions being suited for searching and sorting large databases of media entities, including music, video and image databases, the instructions when executed, perform the steps of:

assigning to each media entity of a plurality of media entities in a data set to at least one class, each class of said at least one class corresponding to a subset of perceptual properties pre-defined for the data set;

processing each media entity of said data set to extract at least one digital signal processing characteristic for each media entity;

generating a plurality of feature vectors for said plurality of media entities, wherein each vector includes said at least one class and said at least one digital signal processing characteristic; and

forming a classification chain based upon said plurality of feature vectors, wherein a human adds a new subset of perceptual properties to the classification chain defined by the plurality of feature vectors.

16. A computing system, comprising:

a processor including;

a classification chain data structure stored thereon having a plurality of classification vectors, wherein each vector includes data representative of at least one perceptual class as classified by humans and digital signal processing data as classified by at least one computing device;

wherein;

the classification chain data structure comprises a subset of perceptual properties defined by the plurality of feature vectors newly added thereto; and

a human adds a new subset of perceptual properties to the classification chain; and

processing means for comparing an unclassified media entity to the classification chain data structure to determine at least one perceptual class of said unclassified media entity.

17. The computing system according to claim 16, wherein said comparing includes determining a set of classification vectors that are within a neighborhood distance from a vector represented by said unclassified media entity.

18. The computing system according to claim 17, wherein said neighborhood distance defines a distance within which two vectors in the classification chain space are in the same neighborhood.

19. The computing system according to claim 18, wherein said neighborhood distance is determined for each of said at least one perceptual class, and said determination includes determining a distance within which two vectors of the classification chain data structure possess the same class given a threshold degree of error.

20. The computing device according to claim 19, wherein a human determines said threshold degree of error that will be tolerated, said threshold degree of error placing a maximum limit on the distance that may be used for determining neighborhoods.

21. The computing system according to claim 17, wherein said processing means classifies the unclassified entry with an estimate of at least one perceptual class based upon the vectors within the neighborhood of a vector representing the unclassified entity.

22. The computing system according to claim 21, wherein said classifying includes classifying the unclassified entry with a median class represented by the neighborhood.

23. The computing system according to claim 21, wherein said at least one perceptual class is described by a numerical value and said classifying of the unclassified entry includes classifying the unclassified entry with a mean of numerical values found in the neighborhood.

24. The computing system according to claim 21, wherein said classifying includes returning at least one number indicating the level of confidence of the class assignment.

25. The computing system according to claim 24, wherein said classifying includes returning a ratio defined by the number of entries in the neighborhood having the representative class over the number of entries in the neighborhood not having the representative class.

26. The computing system according to claim 24, wherein said class is described by a numerical value and said classifying includes returning a standard deviation of the numerical values in the neighborhood.

27. The computing system according to claim 16, further comprising:

an input device for receiving a new unclassified media entity; and

an output device for outputting at least one perceptual class of said new unclassified media entity based upon said classification chain based upon processing of said processing means.

28. A method of generating a classification chain for searching and sorting databases of media entities including music, video, and image databases, the classification chain having a plurality of vectors describing a plurality of media entities, the method comprising:

assigning, by an expert, a first value to a media entity according to a pre-defined perceptual characteristic of media entities;

assigning, by a computing system, a second value to the media entity according to a pre-defined digital signal processing characteristic;

generating a vector based on at least said first value and said second value;

adding said vector to a classification chain data structure, wherein a human adds a new subset of perceptual properties to the classification chain data structure defined by the new unclassified data structure;

calculating a neighborhood distance within the vector space of said classification chain for each of said at least one perceptual class, wherein;

said neighborhood distance defines a distance within which two vectors in the classification chain space are in the same neighborhood;

said calculating of a neighborhood distance for each of said at least one perceptual class includes determining a distance within which two vectors of the classification chain possess the same class given a threshold degree of error;

said threshold degree of error places a maximum limit on the distance that may be used for determining neighborhoods; and

said threshold degree of error is determined by a human.

29. The method according to claim 28, wherein said method is repeated until a sufficient number of vectors have been added to said classification chain data structure, such that said classification chain data structure successfully classifies unclassified media entities within a threshold degree of success.

30. The method according to claim 29, further comprising:

inputting a vector representative of a new unclassified media entity;

comparing said vector to the vector space of the classification chain data structure; and

outputting an estimate of the perceptual class of the new unclassified media entity based upon vectors found in a neighborhood of the classification chain data structure, wherein a neighborhood of vectors is defined as a set of vectors located within a neighborhood distance.

31. The method according to claim 30, further comprising:

outputting an estimate of the confidence level with which said estimate of the perceptual class is correct.

32. The method according to claim 31, wherein if said estimate of the confidence level is low, a human examines the new unclassified media entity and said human determines an action for said classification chain data structure based thereon.

33. The method according to claim 32, wherein the new unclassified media entity is rejected from the classification chain as an outlier.

34. The method according to claim 32, wherein the performance level of the classification chain improves over time due to the examination of unclassified media entities that have a low confidence level associated therewith.

35. The method according to claim 30, wherein it is determined whether said vector representing said new unclassified media entity has been previously processed, thereby obviating the need to re-process said vector via the classification chain.