Detecting and indexing characters of videos by NCuts and page ranking

• US 20090169065A1
• Filed: 12/28/2007
• Published: 07/02/2009
• Est. Priority Date: 12/28/2007
• Status: Active Grant

• Current Assignee: Tahoe Research Limited (f/k/a Learndale Limited) (Vector Capital Corporation)
• Original Assignee: Intel Corporation
• Inventors: Yangzhou, Du, Wang, Tao, Li, Jianguo, Zhang, Yimin
• Granted Patent: US 8,705,810 B2
• Time in Patent Office: Days
• US Class Current: 382/118
• CPC Class Codes: G06F 16/70 of video data
• CPC Class Codes: G06V 40/168 Feature extraction; Face representation

Abstract

Apparatuses, systems, and computer program products that detect and/or index characters of videos are disclosed. One or more embodiments comprise an apparatus an apparatus having a feature extraction module and a cast indexing module. The feature extraction module may extract features of a scale invariant feature transform (SIFT) for face sets of a video and the cast indexing module may detect one or more characters of the video via one or more associations of clusters of the features. Some alternative embodiments may include a cast ranking module to sort characters of the video, considering such factors as appearance times of the characters, appearance frequencies of the characters, and page rankings of the characters. The apparatus may associate or partition the clusters based on a normalized cut process, as well as detect the characters based on measures of distances of nodes associated with the features. Numerous embodiments may detect the characters based upon partitioning the clusters via solutions for eigenvalue systems for matrices of nodes of the clusters.

Claims

1. An apparatus, comprising:

a feature extraction module to extract features of a scale invariant feature transform for face sets of a video; and

a cast indexing module to detect characters of the video, wherein the detection is via an association of clusters of the features.

2. The apparatus of claim 1, further comprising a cast ranking module coupled with the cast indexing module, the cast ranking module to sort characters of the video via at least one of appearance times of the characters, appearance frequencies of the characters, and page rankings of the characters.

3. The apparatus of claim 1, further comprising at least one of a shot detection module to detect shots of the video and a scene detection module to detect scenes of the video.

4. The apparatus of claim 1, wherein the feature extraction module is arranged to detect and track faces of the video to generate the face sets.

5. The apparatus of claim 1, wherein the feature extraction module is arranged to normalize at least one face of faces in the video and detect a plurality of facial landmarks for the normalized face.

6. The apparatus of claim 1, wherein the association of clusters is determined via at least one of a normalized cut process, a hierarchical clustering process, and a spectral clustering process.

7. The apparatus of claim 6, wherein the detection of the character is via a distance measure of nodes associated with the features.

8. The apparatus of claim 1, wherein generation of the association comprises evaluation of facial features of the face sets.

9. A system, comprising:

storage medium to store video, wherein the video comprises faces of a character;

a feature extraction module to extract features of the faces and generate a plurality of clusters of nodes via the features; and

a cast indexing module to detect the character based upon face clustering, wherein the face clustering is via at least one of normalized cuts of the nodes, a hierarchical clustering process, and a spectral clustering process.

10. The system of claim 9, further comprising a cast ranking module coupled with the cast indexing module, the cast ranking module to rank the character based upon consideration of at least one of a duration of time that the character appears in the video, a frequency of appearance for the character, and a number of appearances of the character with other characters.

11. The system of claim 9, wherein the feature extraction module is arranged to detect shots or scenes of the video and track the face in the shots or scenes.

12. The system of claim 9, wherein the partitioning of the nodes of the normalized cuts is via a plurality of distance measures of the nodes.

13. The system of claim 12, wherein the detection of the character comprises partitioning the clusters via a solution for an eigenvalue system for matrices of nodes of the clusters.

14. A computer program product comprising a computer usable medium having computer usable program code for detecting a character of a video, the computer program product including:

computer usable program code for extracting features of a scale invariant feature transform (SIFT) for a first face set and a second face set of the video;

computer usable program code for generating a first cluster of features for the first face set and a second cluster of features for the second face set; and

computer usable program code for detecting the character based on an association of the first cluster and the second cluster.

15. The computer program product of claim 14, further comprising computer usable program code for tracking a face of the character in frames of the video, wherein the tracking is used to generate at least one of the first and second face sets.

16. The computer program product of claim 14, further comprising computer usable program code for determining a distance measure between a first node of the first cluster and a second node of the second cluster, wherein each of the first node and the second node is a face set of continuous faces of a shot.

17. The computer program product of claim 16, further comprising computer usable program code for partitioning the first cluster and the second cluster, wherein the association comprises the determination of the partition.

18. The method of claim 17, wherein the computer usable program code for partitioning the first cluster and the second cluster comprises computer usable program code for separating the first and the second clusters based upon a normalized cut process.

19. The method of claim 14, further comprising computer usable program code for ranking the character based upon an importance factor.

20. The method of claim 19, wherein the computer usable program code for ranking the character based upon an importance factor comprises computer usable program code for calculating a linear weighted average, wherein further the linear weighted average comprises an appearance time, an appearance frequency, and a page rank of the character in the video.