Detecting and indexing characters of videos by NCuts and page ranking

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.

FIELD

The embodiments herein generally relate to the field of image analysis. More particularly, the embodiments relate to systems, apparatuses, and computer program products for detecting and/or indexing characters of videos.

BACKGROUND

The explosion of video media, such as video clips on the World Wide Web, digitized movies, recordings of television (TV) programs on personal video recorders, and home videos, has generated an increasing demand for video mining and video indexing. For example, semantic based video mining techniques, such as news abstraction, sports highlights detection, indexing, and retrieval, are commonly sought after by owners of the media. People often want to index the content of such video data, such as indexing the different characters, or cast of characters, in videos. By cast indexing, owners and viewers of the videos can discover and refer to characters in the videos. For example, a person who may desire to view a video on the World Wide Web may first determine who appears in the video, how frequently they appear, in which scenes they appear, with whom they appear, etc. In other words, indexing characters of the video may allow one to more efficiently browse video clips and other video media.

For detecting characters and cast indexing videos, the human face is usually an important visual cue, often more important than auxiliary cues such as voice or speech, and clothing. Automatic face detection and recognition techniques can be employed as main ways and means for cast indexing. However faces in videos, especially films, sitcoms, and home videos, usually have large variations of pose, expression and illumination which help explain why reliable face recognition is still a very challenging problem for computers.

To reduce the adverse effect of variations in image for video-based face recognition, a lot of methods have been attempted with varying degrees of success. Some people have applied affine warping and illumination correction for face images in an attempt to alleviate the adverse effects induced from pose and illumination variations. However, affine warping and illumination correction are unable to adequately handle out-of-plan face rotation. Others have attempted face recognition based on manifold analysis. Unfortunately, the manifolds of faces and relationships among them in real videos are too complex to be accurately characterized by simplified models. Although some people employ three-dimensional face models to enhance the video-based face recognition performance, three-dimensional face modeling techniques encounter difficulty when trying to accurately recover head pose parameters, even when using state-of-the-art registration techniques. Further, such three-dimensional face modeling techniques are often not practical for real-world applications. In a word, it is very hard to build a robust cast indexing system based only on face recognition techniques.

DETAILED DESCRIPTION OF EMBODIMENTS

Apparatuses, systems, and computer program products that detect characters in video, such as to index a cast of characters in the video, are contemplated. Some embodiments comprise 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. Even further alternative embodiments may also include a shot detection module to detect shots of the video and a scene detection module to detect scenes of the video.

In some of the further alternative embodiments, the feature extraction module may detect faces of the video to generate the face sets. In various alternative embodiments, the feature extraction module may normalize one or more faces in the video and detect facial landmarks for the normalized faces. In numerous embodiments, the apparatus may associate the clusters based on a normalized cut process. In various embodiments, the apparatus may detect the character based on a distance measure of nodes associated with the features. At least one embodiment may consider color histogram features of the face sets in generating the association.

Some embodiments comprise a system having a storage medium to store video, a feature extraction module to extract features of a face of a character in the video and generate clusters of nodes via the features, and a cast indexing module to detect the character based upon partitioning of the clusters, wherein the partitioning is via normalized cuts of the nodes. One or more embodiments may also comprise a cast ranking module that ranks the character based upon such factors as an amount of time that the character appears in the video, a frequency of appearance for the character, and/or a number of appearances of the character with a second character.

In some embodiments, the feature extraction module may detect shots or scenes of the video and track the face in the shots or scenes. Various embodiments may partition the nodes based on distance measures of the nodes. Numerous embodiments may detect the character based upon partitioning the clusters via a solution for an eigenvalue system for matrices of nodes of the clusters.

Some embodiments comprise a computer program product with computer usable program code for detecting a character of a video, extracting features of a SIFT for face sets of the video, generating clusters of features for the face sets, and detecting the character based on an association of the clusters. One or more embodiments also include computer usable program code for tracking a face of the character in frames of the video, wherein the tracking is used to generate the face sets. Other embodiments further comprise computer usable program code for determining a distance measure between nodes of clusters.

Numerous embodiments have program code for partitioning clusters of the face sets, wherein at least part of the association process involves creating or determining the partition. Many embodiments have program code for partitioning or separating the clusters based upon normalized cut processes. Some alternative embodiments may also have code for ranking the character based upon an importance factor. In such alternative embodiments, the program code for ranking the character may involve calculating an importance factor. For example, the importance factor may be calculated using a linear weighted average of an appearance time, an appearance frequency, and a page rank of the character in the video.

In the following discussions, terms such as “shots”, “scenes”, and “frames” are used. Similar to processing text with words, sentences, and paragraphs of a document, video processing may be thought of as processing video frames, shots, and scenes of a video file or video sequence. A frame may comprise a single image, which one may consider similar to a digital picture. A shot may comprise a set of video frames captured by a single camera in one consecutive recording session. A scene may be a subdivision of a video in which the setting is fixed and time-continuous, such as presenting a sequence of continuous action in a single location.

Turning now to the drawings,FIG. 1illustrates a computing system100that may detect characters in video. For example, computing system100may comprise a desktop or laptop computer executing a video processing application145in memory140. In alternative embodiments, computing system100may comprise a face recognition system for video, a cast indexing system for movies, a computer used to perform video mining of Internet video clips, a video surveillance system, or a video summarization system, as examples. Video processing application145may detect characters in a video clip downloaded from the Internet or detect characters in a movie or TV show, such as a movie or a TV show recorded by personal video recorder (PVR).

In the embodiment depicted inFIG. 1, video processing application145may index characters, or cast members, of the video by using normalized graph cuts, or normalized cuts (NCuts), and page ranking, which will be discussed in more detail later. The cast indexing system, comprising video processing application145, may have three modules: feature extraction module150, cast indexing module160, and cast ranking module170.

In various embodiments, a computing system like computing system100may execute a variety of different applications. For example, in addition to video processing application145, computing system100may execute a second application180, which may be a video viewing application, such as a web browser or dedicated video player application. Alternatively, in different embodiments, application180may comprise an application unrelated to processing video, such as an Internet instant messaging application, a time management application, an e-mail application, and so on. In other words, computing system100may be used for other purposes, not just for video processing, in one or more embodiments.

In various embodiments, a system may have a processor, such as processor105, for executing program instructions of applications, such as video processing application145and application180, that may be in memory140. While executing program instructions of video processing application145, computing system100may display video images, or information pertaining to the video, on a monitor or other computer display, such as display110. For example, display110may allow a video editor to view different scenes of a movie as video processing application145performs such tasks as detecting shots, detecting scenes, detecting characters in scenes, generating face sets for the characters, etc. Display110may also allow viewing of the end result of such processing operations, such as the names of characters that are in the video, how frequently they appear, etc.

Using input device115the user of computing system100may interact with video processing application145. In one or more embodiments, input device115may comprise a keyboard and/or a mouse, allowing a person to perform such actions as viewing different scenes of a video or loading and saving video files to be used with video processing application145. In some embodiments input device115may comprise a tablet and stylus, such as a pressure-sensitive surface of a personal digital assistant (PDA) that recognizes hand-written characters. In even further embodiments input device115may comprise an audible input device, such as a microphone used for speech recognition, or an infrared remote control interface. For example, in one embodiment input device115may allow a user to perform cast indexing for one or more TV shows or movies that have been recorded by a PVR, using a device such as a remote control.

Depending on the embodiment, computing system100may run a variety of different operating systems. For example, in one embodiment computing system100may use Unix®. In another embodiment, computing system may use Microsoft® Windows®, Linux®, or Mac OS®, as examples. Other alternative embodiments may have no operating system at all. For example, computing system100may comprise a state machine or microcontroller executing firmware instructions stores, such that no operating system is necessary.

One or more videos may be stored on a storage medium of a storage device120and accessed by computing system100. For example, storage device120may comprise one or more of a variety of different mass storage devices used to store video files130and135, which may comprise video clips or movies as examples. For example storage device120may comprise a parallel or serial hard disk drive. Alternatively, storage device120may also comprise an optical storage device, such as a rewritable compact disc (CD) or a digital versatile disc (DVD) drive, having storage mediums of a CD and DVD, respectively. In other embodiments, storage device120may comprise a flash memory device, such as a universal serial bus (USB) thumb drive. Storage device120may also store other information, such as character database125. For example, character database125may store information of characters detected in video files130and135, such as names of the characters, how often each of them appears, which characters appear most frequently, which characters appear with certain other characters, etc.

While not shown inFIG. 1, alternative embodiments of a computing device in a system may connect to other computers of the system using a variety of different hardware. For example, computing system100may comprise a desktop computer connected to another computer via a wireless communications card, or an Ethernet cable coupled to a local or wide area network (LAN or WAN). The desktop computer may download and process video files from the Internet. As the above example illustrates, various embodiments of a system may comprise an almost limitless number of wired and wireless communication devices, allowing computing devices of a system to communicate with each other to share and/or process video files, wherein the computers may be located close to or remote from each other.

In many types of video media, such as movies and recordings of a TV series, characters frequently appear in different shots, resulting in large numbers of consecutive face images. Such different shots may provide rich dynamic facial information and multi-view face exemplars of individual characters, which may allow an apparatus or system to detect characters by clustering faces of those characters. To illustrate in more detail how a system or an apparatus may detect and index characters of video, we turn now toFIG. 2AandFIG. 2B.FIG. 2Aprovides an overview of how a video205may be processed by an apparatus200, comprising a feature extraction module210and a cast indexing module250, to generate a cast list. For example, video205may correspond to video file130shown inFIG. 1, with feature extraction module210and cast indexing module250corresponding to feature extraction module150and cast indexing module160, respectively. Video205may represent a movie having numerous scenes, shots, and frames. For the sake of an example,FIG. 2Bmay represent a portion of video280for video205. The portion of video280depicts one scene from numerous scenes286, where in the scene is shown divided into numerous shots288and further subdivided into numerous frames290.

When operating, feature extraction module210may first detect shot boundary and scene segmentation. For example, feature extraction module210may detect the beginning and ending boundaries of a scene in the portion of the video280, as well as the boundaries for the different shots288, and frames290. The feature extraction module may then detect near frontal faces284, track the faces (element294) in the successive shots and frames, and generate the different face sets282corresponding to the successive frames and shots. The feature extraction module210may normalize the face images of the face sets282and extract local SIFT features from the face sets282.

Based on the shots, scenes, face sets, and facial features detected and generated by feature extraction module210, cast indexing module250may detect characters (element296) in the portion of the video280as well as other portions of video205. Cast indexing module250may use a face set as a basic processing unit to detect characters. Using a face set to detect characters may be approached as solving a pattern clustering problem. By modeling face sets as nodes of a graph, cast indexing module250may employ normalized graph cuts to specify partitions of the nodes. In other words, cast indexing module250may detect characters using an NCut algorithm to cluster face sets. Additionally, in alternative embodiments, cast indexing module250may employ other techniques for clustering of nodes, such as a hierarchical clustering process, or a spectral clustering process. To deal with outlier faces from variations of pose, expression, illumination, and poor face normalizations, cast indexing module250may use a local neighbor distance to measure the similarity between face sets. Additionally, to allow for such benefits as efficient browsing of video clips and movies, cast indexing module250may sort characters by calculating an importance factor (IF) for each of the characters. An IF, which may comprise a fused score of page ranking, appearance time, and appearance frequency used to rank cast characters. Use of page ranking for the characters may also allow for the discovery of latent relationships between characters.

FIG. 3depicts an alternative embodiment of an apparatus300that may process a video, similar to the manner in which apparatus200may process video205. Apparatus300has a feature extraction module310, a cast indexing module340, and a cast ranking module370. Each module of apparatus300may comprise software, hardware, or a combination of both software and hardware. All modules may be of the same form in some embodiments, such all as being implemented as software or firmware encoded instructions, while some modules may be in a different form than the other modules in other embodiments. For example, in one embodiment feature extraction module310and cast ranking module370may comprise program algorithms, such as software routines of a program or application, to be executed by a processor, while cast indexing module340comprises an application-specific integrated circuit (ASIC) chip that uses only hardware components to rapidly determine distance measures and cast detection calculations.

Alternative embodiments of apparatus300may perform more or fewer functions than those illustrated inFIG. 3. For example, for the embodiment of apparatus300depicted inFIG. 3, feature extraction module310could perform the functions of shot and scene detection or face tracking. Alternatively, such functions may be carried out by one or more other modules not shown inFIG. 3. For example, another module may pull segments of video from a video file, process the sequences of images contained in the video file to detect shots and faces in those scenes, track the movement of faces in the shots or scenes, generate face sets, and transfer the generated face sets to feature extraction module310. In other words, alternative embodiments of apparatus300may include more or fewer modules than those depicted inFIG. 3.

Feature extraction module310may use the face sets as basic processing units for cast indexing. Face sets may provide information from previous frames concerning multi-view facial exemplars which belong to the same person or character. The use of face sets may also decrease the data size, or the amount of video footage, needed for face clustering algorithms or functions performed by cast indexing module340.

For each image of a face that is processed, feature extraction module310may use an active shape model-based (ASM-based) face alignment algorithm to detect facial landmarks. For example,FIG. 4Aillustrates how feature extraction module310may detect landmarks on a face and determine local regions for scale invariant feature transform (SIFT) feature extraction. Feature extraction module310may receive an image of a face405. Using the ASM-based face alignment algorithm, landmark detection sub-module320may detect a number of landmarks around the eyebrows, the eyes, the nose, the mouth, and the chin (element410). Using these detected landmarks, landmark detection sub-module320may geometrically normalize the facial images into a standard form by affine transformation to remove variations of translation, scale, in-plane and slight out-of-plane rotation. Landmark detection sub-module320may then generate five local regions around the face (element415) to allow for SIFT feature extraction by SIFT extraction sub-module330. In other words, SIFT extraction sub-module330may use the five local regions generated by landmark detection sub-module320to extract SIFT features for the image of the face405, for the regions surrounding the two eyes, the central region of the two eyes, the nose, and the forehead (element415). SIFT extraction sub-module330may extract local features for the facial images. Using local features may allow for more accurate recognition and verification than using global features. While using local features may not always provide greater accuracy, in numerous situations local features may provide greater accuracy for partial occlusions, pose, and illumination variations.

As alluded to earlier, another module may track faces in the sequences of images and group the faces of the same characters in each shot into face sets. The number of face images in face sets may often differ from scene to scene and shot to shot. Additionally, characters may appear in multiple shots, resulting in multiple face sets for individual characters. As illustrated inFIG. 2B, various embodiments may attempt to group, or cluster, face sets into bigger aggregations that include all the face sets associated with the same character. If the pose, expression, and illumination of faces dynamically change in a face set, such dynamic changes may provide rich multi-view exemplars for the same people. The multi-view exemplars may help bridge face sets with overlapped face exemplars for face clustering.

Numerous embodiments may use a distance measure between two face sets to cluster or associate face sets for the same characters. To illustrate this concept of clustering, we continue with our previous example of apparatus300processing the sequences of images contained in the video file. Feature extraction module310may continue processing facial images in the sequences of images contained in the video file with landmark detection sub-module320and sift extraction sub-module330. The sequences of images may comprise the face sets ofFIG. 4B. For example, face sets420,425,430, and435may represent manifolds of four face sets of two characters in a scene of the video file. Face set420and face set435may represent two face shots for the first character in the different shots. Face set425and face set430may represent two face shots for the second character in the two shots. AsFIG. 4Billustrates, manifolds of the face sets in feature space may be very complex and quite different from each other. For example, the faces of one character can be very distant, while the faces of a different character may be very near in the feature space. However, two face sets with bigger overlap may have a higher probability of belonging to the same character. To determine these overlaps, or proximal distances, the nodes of the extracted local SIFT features may be compared with each other.

Continuing with the example, feature extraction module310may process the facial images to generate a plurality of nodes for the extracted local SIFT features for face sets420,425,430, and435.FIG. 4Cillustrates how corresponding manifolds of the face sets inFIG. 4Bmay be visualized in a two dimensional subspace. In other words, the graph490ofFIG. 4Cmay illustrate the spatial relationship of the plurality of nodes generated for the extracted local SIFT features for face sets420,425,430, and435. Referring to the legend, the “+” symbols may correspond to the nodes for face set420, shown in cluster460, and the “x” symbols may correspond to the nodes for face set435, shown in cluster480. Similarly, the “□” symbols may correspond to the nodes for face set425, shown in cluster470, and the “*” symbols may correspond to the nodes for face set430, shown in cluster450. As the graph490ofFIG. 4Cillustrates, clusters460and480are situated in close proximity with each other and correspond to the extracted local SIFT features for face sets420and435, respectively, belonging to the first character. Likewise, clusters470and450are in close spatial proximity with each other as well and correspond to face sets425and430, respectively, belonging to the second character. In practice, there may be outliers due to misalignment, variations of pose, variations of expression, or variations in illumination, etc. When clustering face sets, including outliers may the associated error and tend to merge face sets of different characters, or bring them within relatively close spatial proximity with other. However, longer duration videos may help provide relatively large quantities of facial information. If outliers occur infrequently, faces with higher density distribution in the feature space may have a relatively high probability of belonging to the same character. In consideration of this, one fundament may be observed: normal samples may have support from their nearest neighborhood same-face-set samples, while outliers may not.

Distance Measure Between Two Faces

Based on the above observation, one may define a measure of distance, or “distance measure”, between two face images by considering their nearest neighborhood support information. In our discussion, k-nearest neighbor may be adopted. Let Siand Sjrepresent two face sets, for two faces ximεSiand xjnεSj, the local neighbor distance between ximand xjnmay be defined as:

d⁡(xim,xjn)=1k2⁢∑xip∈N⁡(xim),xjq∈N⁡(xjn)⁢⁢xip-xjq(1)
where N(xim) is the k neighbors of ximin Siand N(xjn) is the k neighbors of xjnin Sj, ∥·∥ denotes L2distance between two faces. It may be proved:

d⁡(xim,xjn)∝∑xip∈N⁡(xim)⁢⁢xip-∑xjq∈N⁡(xjn)⁢⁢xjq(2)
The distance measure defined by Eq. (1) may be equivalent to first applying a smooth filter on the manifold to weaken or remove outlier disturbances, then calculating the distance between the two averaged data points. A module like distance determination sub-module350may determine or calculate measures of distances between face images as part of indexing a cast of characters for a video. For example, distance determination sub-module350may calculate the distance measure between two faces of face set420, which may correspond to the distance between two nodes (“+”) of cluster460.

For the sake of another more detailed example of how a module like distance determination sub-module350may calculate measures of distances between nodes for face images,FIG. 5Adepicts a first cluster of nodes510for a face set ‘R’, a second cluster of nodes520for a face set ‘G’, and a third cluster of nodes530for a face set ‘B’. As part of indexing a cast of characters for video, distance determination sub-module350may calculate coordinates for nodes that represent an average of the neighborhood points of a cluster. For example, cluster of nodes510may have a first node515that represents an average of the neighborhood points of cluster of nodes510. Similarly cluster of nodes520and530may have nodes525and535that represent averages of the neighborhood points of cluster of nodes520and530, respectively. AsFIG. 5Aillustrates, when an embodiment makes a distance determination using a function like the local neighbor distance function of Eq. (1), which is represented by the distances between nodes515,525, and535, the distance determinations or “separations” of the clusters may be more robust to outliers than using a simple L2 distance ∥xim−xjn∥, or the measure of distance between two closest boundary nodes of each cluster of nodes.

Distance Measure Between Two Face Sets

As mentioned previously, face sets with larger amounts of overlap may generally have a greater probability of belonging to the same character. For a distance measure between two face sets, it may be intuitive to summarize 1 minimum local neighbor distances d(xim, xjn) to evaluate the face set overlap.

After the distance determination sub-module350calculates the distance measures between face sets, NCuts cast detection sub-module360may approach the main cast detection process as a graph partitioning problem, i.e. graph cut. NCuts cast detection sub-module360may represent the face sets as a weighted undirected graph G=(V,E), where the nodes V of the graph are the face sets and the edges are the similarities between pair-wise face sets. For face set clustering, NCuts cast detection sub-module360may seek a suitable or potentially an optimal partition C1, C2, K, Cmsuch that the similarity among the nodes in a sub-graph Ciis high and across similarity between sub-graphs Ci, Cj(i≠j) is low. To optimally partition a graph constituted by face sets, NCuts cast detection sub-module360may employ a normalized cut algorithm.

Normalized Graph Cuts

A graph G=(V,E) can be partitioned into two disjoint sub-graphs A and B with A∪B=V and A∩B=Φ, by removing edges connecting the two parts. The degree of dissimilarity between these two sub-graphs may be computed as a total weight of the edges that have been removed. In graph theoretic language, this may be referred to as the “cut”:

cut⁡(A,B)=∑u∈A,v∈B⁢⁢w⁡(u,v)(4)
A suitable or potentially an optimal bipartition of a graph may be the one that minimizes this cut value. To avoid unnatural bias when partitioning small sets of points, NCuts cast detection sub-module360may use a disassociation measure of a “normalized cut (Ncut)”:

Ncut⁡(A,B)=cut⁡(A,B)assoc⁡(A,V)+cut⁡(A,B)assoc⁡(B,V)(5)
where assoc(A,V)=ΣuεA,tεVw(u,t) is the total connection from the nodes in A to all nodes in the graph and assoc(B,V) is similarly defined. Given a partition of the graph, i.e., dividing V into two disjoint sets A and B, X may be a N=|V| dimensional indication vector, xi=1 if node i is in A and −1 if node i is in B. If one lets d(i)=Σjw(i,j) and D be and N×N diagonal matrix with d on its diagonal, w be an N×N symmetrical matrix with W(i,j)=wij, the approximate discrete solution to minimizing NCuts may be found by solving the generalized eigenvalue system,
(D−W)Y=λDY(6)
where Y is a linear transformation of X and can be used for partition by a threshold.
Cast Detection Algorithm

For two face sets Siand Sj, the graph edge weight wijmay be defined as:

wij={ⅇ-d2⁡(Si,Sj)σ2if⁢⁢Sj⁢⁢is⁢⁢the⁢⁢n⁢⁢nearest⁢⁢neighbor⁢⁢of⁢⁢Si0otherwise.(7)
For example, n may be set to 1/15th ˜ 1/20th of the number of face sets, while σ may be set to 0.8, which may approximate the threshold that two faces are from the same character in a SIFT feature space. By using an NCuts clustering approach, NCuts cast detection sub-module360may employ a cast detection algorithm that consists of the following process: 1. Given the face sets detected by a feature extraction module, set up a weighted graph G=(V,E) using distance function defined by equations (2) and (4). 2. From the graph, create matrices W and D to solve the eigenvalue system (D−W)x=λDx. 3. Use the eigenvector with the second smallest eigenvalue to bipartition the graph by finding the splitting point with the minimum Ncut. 4. Recursively partition the sub-graph when the stopping criterion is not satisfied. Whether continue to bipartition a sub-graph may be determined by attempting a new bipartition. A sub-graph may be partitioned if either of the following two conditions is satisfied: (a) The Ncut(A,B) of the trying bipartition is below a pre-selected value. (b) Computing the histogram of the eigenvector values and the ratio between the minimum and the maximum values in the bins is not smaller than a pre-selected threshold.
Ranking of Characters in Cast

In one or more embodiments, the cast detection module, such as cast indexing module340ofFIG. 3, may generate face set clusters for characters that frequently appear in a video. To sort the important characters and analyze their relationships in scenes of the video, cast indexing module340may output or transmit those face set clusters to cast ranking module370to further rank cast characters (clusters of face sets) by a factor, such as an Importance Factor (IF) calculated by IF calculation sub-module380. More important actors may generally appear with higher durations of appearance, or appearance time. In addition to determining appearance time for characters in a video, IF calculation sub-module380may also determine or calculate the frequency with which they appear, or appearance frequency. Additionally, certain actors may frequently appear with others in various scenes. Consequently, IF calculation sub-module380may measure or discover how frequently characters appear in various scenes, as well as their relationships or association with other characters, based on their joint appearance frequencies in the various scenes.

The IF calculation sub-module380may also rank characters of a video using one or more other measures or factors. For example, IF calculation sub-module380may rank characters based on a scene rank or a “page rank” factor. The scene/page rank factor may be analogous to the PageRank™ technology of Google™ web searching. In other words, each character may be viewed as a web page where joint appearances of multiple characters in a scene may be viewed as linked edges among them. If one character has many connected edges with others, or the character is connected to some one or more important characters, the page rank value may be relatively large. In one or more embodiments, therefore, a module like IF calculation sub-module380may rank the detected characters by an importance factor, wherein the IF may take into consideration a linear weighted average of the factors of appearance time, appearance frequency, and page rank. As an example calculation of an IF, an embodiment may calculate the IF for a character Ci, by using the following formula:
IF(C1)=wtAt(Ci)+wfAf(Ci)+wpAp(Ci)  (8)
where At(·) is the Appearance Time (AT) score, Af(·) is the Appearance Frequency (AF) score and Ap(·) is the page rank score. For example, one or more embodiments may use the following weights: wt=0.2, wf=0.3, wp=0.5, when calculating the IF for a character. The page rank score may be calculated using the following process. For characters Cj, i=1, 2 . . . N, the page rank value of Cjmay be defined as:

Ap⁡(Ci)=(1-d)+d⁢∑j≠i⁢⁢Ap⁡(Cj)/L⁡(Cj),i=1,…⁢,N(9)
where Ap(Ci) is the page rank score of the character Ci, Ap(Cj) is the page rank score of character Cjwhich links to character Ci, i.e. Cjjointly appears with Ciin a particular scene. L(Cj) may represent the outbound links of Cj, i.e., the number of characters that jointly appeared with Cj. The variable d may represent a damping factor. When analyzing scenes of a video, each character may be initially assigned a starting page rank value Ap(Ci)=1, with the damping factor set to 0.8. An embodiment may then employ an iterative process to calculate the page rank scores of the individual characters. The appearance time At(Ci) and the appearance frequency Af(Ci) scores may be calculated according to the character appearance time and the clustered face set number. In more detail, the two scores may be defined as follows:

Using equations like equations (10) and (11), an embodiment may determine the character relationships by a page rank analysis. An illustrative example for the characters ofFIG. 5Ais shown inFIG. 5B, with the corresponding calculated IF scores listed in the table ofFIG. 5C. In the example illustrated byFIGS. 5B and 5C, face sets545may be created from a section of scenes540. The three characters that appear in scenes540, may be referred to as character “r”, character “g”, and character “b” and represented as “Cr”, “Cg”, and “Cb”, respectively. As face sets545inFIG. 5Bshow, Cr may appear in scenes2,3,4, and5. Similarly, Cg may appear in scenes1,2,3, and4, while Cb only appears in scenes5and6. Since Cg and Cr appear with each other in four scenes, represented by the four lines between the nodes of the clusters550, Cg and Cr may be considered more important than Cb, who only appears in one scene with Cr (scene5). In other words, Crmay be deemed more important than Cg since Cr has more relationships with other characters (element555).

The table ofFIG. 5Cshows example factors that may be calculated by an IF calculation module for the three characters ofFIGS. 5A and 5B. Columns560,565, and570may represent the different factors calculated for characters Cr, Cg, and Cb, respectively. In the table, row575shows the appearance times tabulated for each of the characters. Similarly, rows580,585, and590show the appearance frequency, links or appearances that the characters have with other characters, and page rankings for the characters. Row595shows example resulting IF factors that may be calculated for each of the three characters using the various factors (elements575,580,585, and590). As the table illustrates, even though Cb may appear for a greater duration, with At(Cb)=0.6, the appearance time may not be given much consideration, since the corresponding appearance frequency score, Af(Cb)=0.2, and page rank score, Ap(Cb)=0.16, are relatively low.

Another embodiment of the invention may be implemented as a program product, such as firmware, for use with a computing device or platform to detect and/or index characters of videos. The program(s) of the program product may define functions of the embodiments (including the methods described herein) and can be contained on a variety of data and/or signal-bearing media. Illustrative data and/or signal-bearing media include, but are not limited to: (i) information permanently stored on non-writable storage media (e.g., read-only memory devices within a computer, such as on a platform motherboard); (ii) alterable information stored on writable storage media (e.g., floppy disks within a diskette drive or hard-disk drive); and (iii) information conveyed to a computer by a communications medium, such as through a computer or telephone network, including wireless communications. The latter embodiment specifically includes information downloaded from the Internet and other networks. Such data and/or signal-bearing media, when carrying computer-readable instructions that direct the functions of the present invention, represent embodiments of the present invention.

FIG. 6depicts a flowchart600that illustrates a method, which may be implemented by way of a program product such as software or firmware, to enable a computing device to detect and/or index characters of videos. For example, the method may be executed as software instructions of a program, or implemented as a state-machine hardware or firmware in an application-specific integrated circuit chip of an embedded system that detects and/or indexes characters in video clips or movies. Flowchart600begins with tracking faces of characters in frames of video to generate sets of faces (element610) and extracting SIFT features for the sets of faces (element620). For example, video processing application145may have software routines which perform the functions of feature extraction module150, cast indexing module160, and cast ranking module170. Video processing application145may track faces of characters in frames of video, such as a home video or video surveillance for a building or warehouse.

A method according to flowchart600may continue by generating clusters of nodes based on the SIFT features (element630) and determining measures of distances between nodes of the clusters (element640). For example, the software modules of video processing application145may generate clusters of nodes, similar to the clusters of nodes depicted in the graph490ofFIG. 4C, based on the SIFT features of faces contained in a surveillance video. Video processing application145may then determine measures of distances between nodes of the individual clusters, wherein the nodes may represent the average locations of the neighborhood nodes.

A method according to flowchart600may then partition the clusters based on the measures of distances (element650) and detect one or more characters based upon the partitioning (element660). Continuing with our previous example, video processing application145may partition three clusters corresponding to the faces of the three characters in a surveillance video and associate the faces to characters stored in a profile database125. Video processing application145may then calculate importance factors for the characters detected in the surveillance video (element670). For example, cast ranking module170of video processing application145may determine how many times a particular person or character enters the building, as well as the times that the person visits the building and how often the person appears with one or more other people.

It will be apparent to those skilled in the art having the benefit of this disclosure that the present invention contemplates systems, apparatuses, and computer program products that detect and/or index characters in video. It is understood that the form of the invention shown and described in the detailed description and the drawings are to be taken merely as examples. It is intended that the following claims be interpreted broadly to embrace all the variations of the embodiments disclosed.