Detecting and indexing characters of videos by NCuts and page ranking

• US 8,705,810 B2
• Filed: 12/28/2007
• Issued: 04/22/2014
• 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: Wang, Tao, Li, Jianguo, Yangzhou, Du, Zhang, Yimin
• Primary Examiner(s): Liew, Alex
• Application Number:
  US12/006,019
• Publication Number:
  US 20090169065A1
• Time in Patent Office: 2,307 Days
• Field of Search: 382/103, 382115-118
• 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 identify images of a video as a plurality of faces of characters of the video and features associated with the plurality of faces; and

a cast indexing module coupled with the feature extraction module to create a cast of characters of the video based upon the plurality of faces of characters of the video, the cast indexing module to partition the plurality of faces into sets of faces by forming clusters of the faces based upon the features, partitioning the clusters, and detecting the cast of characters based upon partitions, wherein;

the sets of faces represent the cast of characters of the video;

different sets of faces represent different characters of the cast of characters; and

the faces within a set of faces represent the faces of a single character of the cast of characters.

2. The apparatus of claim 1, wherein:

the plurality of faces of the characters of the video comprises a plurality of face sets, wherein;

a face set comprises a set of faces of a single character in a shot;

a shot comprises a set of video frames captured by a single camera in a consecutive recording session;

the feature extraction module comprises a shot detection module to detect shots of the video; and

the partitioning the plurality of faces into sets of faces comprises merging face sets from separate shots of a character of the characters of the video into a single face set of the character.

3. The apparatus of claim 2, wherein the feature extraction module is to detect and track faces of characters of the video to generate the face sets.

4. The apparatus of claim 3, wherein the detecting faces comprises detecting near frontal faces.

5. The apparatus of claim 2, wherein the shot detection module is to detect shot boundary and scene segmentation.

6. The apparatus of claim 2, wherein the feature extraction module is to normalize the faces of the face sets and to extract local scale invariant features from the face sets.

7. The apparatus of claim 6, wherein the feature extraction module is to use an active shape model-based (ASM-based) face alignment algorithm to detect facial landmarks and to apply scale invariant feature transforms to the facial landmarks to obtain the local scale invariant features.

8. The apparatus of claim 1, wherein the cast indexing module is to partition the plurality of faces of the characters of the video into sets of faces of the characters of the video by using at least one of a normalized cut process, a hierarchical clustering process, and a spectral clustering process.

9. The apparatus of claim 8, wherein the cast indexing module is to partition the plurality of faces of the characters of the video into sets of faces of the characters of the video by using a normalized cut process.

10. The apparatus of claim 9, wherein the cast indexing module is to determine a distance between representations of two faces by a local neighborhood distance.

11. The apparatus of claim 10, wherein the local neighborhood distance between a face x_imε

S_i and a face x_jnε

S_j, wherein S_i and S_j comprise face sets, is defined as;

12. The apparatus of claim 11, wherein:

the cast indexing module is to merge face sets S_i and S_j when the distance between face sets S_i and S_j is sufficiently small.

13. The apparatus of claim 12, wherein the cast indexing module is to merge face sets S_i and S_j and bridging face sets {S_b} when:

the distance between S_i and S_j is not sufficiently small; and

face sets S_i and S_j are bridged by the bridging face sets {S_b}.

14. The apparatus of claim 1, wherein the cast indexing module is to determine a frequency of appearance of the characters of the cast of characters, a duration of appearance of the characters of the cast of characters, and scenes containing appearances of the characters of the cast of characters.

15. The apparatus of claim 1, further comprising a cast ranking module coupled with the cast indexing module, the cast ranking module to sort the characters of the cast of 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.

16. The apparatus of claim 15, wherein the cast ranking module is to rank the characters of the cast of characters of the video by importance factor (IF), wherein IF is determined by the formula:

IF(C_i)=w_tA_t(C_i)+w_fA_f(C_i)+w_pA_p(C_i),

wherein C_i is a character of the cast of characters of the video, A_t is an Appearance Time score of C_i, A_f is an Appearance Frequency score of C_i, the w'"'"'s represent weights wherein the weights total to 1.0, and A_p is a page rank score of C_i.

17. The apparatus of claim 16, wherein the page rank value A_p of a character C_i of a character of the cast of characters of the video is defined recursively as follows:

1. Initially, A_p=1 for each character of the cast of characters of the video,

2. At each further iteration,

18. A system, comprising:

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

a feature extraction module to identify images of a video as a plurality of faces of characters of the video and features associated with the plurality of faces and to group the faces into face sets of the characters of the video, wherein;

a face set comprises a set of faces of a single character in a shot; and

a shot comprises a set of video frames captured by a single camera in a consecutive recording session; and

the feature extraction module comprises a shot detection module to detect shots of the video; and

a cast indexing module coupled with the feature extraction module to detect characters of the video to determine a cast of the characters of the video by forming clusters of faces based upon the features, partitioning the clusters, and detecting the characters based upon partitions.

19. The system of claim 18, wherein:

the cast indexing module is to form the clusters by merging face sets from separate shots of a character of the characters into a single face set of the character.

20. The system of claim 19, wherein:

the feature extraction module is to;

detect and track faces of characters to generate the face sets;

normalize the faces of the face sets;

extract local scale invariant features from the face sets by using an active shape model-based (ASM-based) face alignment algorithm to detect facial landmarks; and

apply scale invariant feature transforms to the facial landmarks to obtain the local scale invariant features;

the shot detection module is to detect shot boundary and scene segmentation;

the cast indexing module is to partition the plurality of faces of characters into sets of faces by merging face sets from separate shots of a character into a single face set by means of a normalized cut process, the normalized cut process using a local neighborhood distance to determine a distance between representations of two faces, wherein;

the local neighborhood distance between a face x_imε

S_i and a face x_jnε

S_j, wherein S_i and S_j comprise face sets, is defined as;

21. A computer program product comprising a non-transitory computer usable medium having computer usable program code for identifying characters of a video, wherein the video comprises a plurality of video frames, the computer program product including:

computer usable program code to identify images of a video as a plurality of faces of characters of the video and features associated with the plurality of faces; and

computer usable program code to create a cast of characters of the video based upon the plurality of faces of characters of the video, the computer usable program code to partition the plurality of faces into sets of faces by forming clusters of the faces based upon the features, partitioning the clusters, and detecting the cast of characters based upon partitions, wherein;

the sets of faces represent the cast of characters of the video;

different sets of faces represent different characters of the cast of characters; and

the faces within a set of faces represent the faces of a single character of the cast of characters.

22. The computer program product of claim 21, wherein:

the plurality of faces of the characters of the video comprises a plurality of face sets, wherein;

a face set comprises a set of faces of a single character in a shot;

a shot comprises a set of video frames captured by a single camera in a consecutive recording session;

the computer usable program code for extracting comprises computer usable program code to detect shots of the video; and

the computer usable program code for partitioning comprises computer usable program code to merge face sets from separate shots of a character of the characters of the video into a single face set of the character.

23. The computer program product of claim 22, wherein:

the computer program product further comprises computer usable program code to;

detect and track faces of characters to generate the face sets;

normalize the faces of the face sets;

extract local scale invariant features from the face sets by using an active shape model-based (ASM-based) face alignment algorithm to detect facial landmarks; and

apply scale invariant feature transforms to the facial landmarks to obtain the local scale invariant features;

the computer usable program code for detecting shots to detectshot boundary and scene segmentation;

the computer usable program code for identifying images comprises computer usable program code to detect shots of the video;

the computer usable program code for partitioning comprises computer usable program code to partition the plurality of faces of characters into sets of faces by merging face sets from separate shots of a character into a single face set by means of a normalized cut process, the normalized cut process using a local neighborhood distance to determine a distance between representations of two faces, wherein;

the local neighborhood distance between a face x_imε

S_i and a face x_jnε

S_j, wherein S_i and S_j comprise face sets, is defined as;