End-to-end Face Detection and Cast Grouping in Movies Using Erdős-Rényi Clustering

SouYoung Jin, Hang Su, Chris Stauffer, Erik Learned-Miller

TL;DR

This paper introduces an end-to-end pipeline for grouping movie characters by identity without any prior supervision. By leveraging Erdős-Rényi graph theory, the authors develop a clustering method that prioritizes extremely low false-positive rates, achieving state-of-the-art performance on complex video datasets like The Big Bang Theory and Buffy the Vampire Slayer.

What Problem Does This Paper Address?

Identifying and grouping every face in a full-length movie by identity is a daunting task. Most existing research treats face detection and face clustering as separate problems, often starting with a "clean" set of pre-detected faces. However, real-world video is messy: detectors miss faces (false negatives), trigger on non-faces (false positives), and identities change drastically due to lighting and pose.

Furthermore, many "naming" systems rely on external supervision like subtitles or transcripts to map faces to names. This paper tackles the unsupervised end-to-end problem: taking raw video and automatically grouping all detected faces into clusters representing unique individuals, while accounting for the errors inherent in the detection process itself.

Methods

The authors propose a three-stage pipeline:

  1. Tracklet Generation: Instead of clustering individual frames, the system first creates "tracklets"—short, high-confidence sequences of the same face. It combines a Faster R-CNN face detector with a generic Distribution Field Tracker. The tracker helps fill in gaps where the detector might fail due to difficult angles and ensures that the faces within a tracklet belong to a single identity.
  2. Rank-1 Counts Verification: To decide if two tracklets belong to the same person, the authors introduce a novel similarity measure. Instead of standard Euclidean distance, they use "rank-1 counts." For each dimension in a 4096-D feature vector (extracted from a pre-trained CNN), they check if the values of two images are closer to each other than to any image in a "reference set" of random faces. A high count of such "suspicious coincidences" indicates a match.
  3. Erdős-Rényi Clustering: The core clustering strategy is inspired by random graph theory. The authors argue that in large-scale clustering, a single false positive (linking two different people) is catastrophic as it merges two large clusters. Conversely, because of the properties of Erdős-Rényi graphs, a cluster can become fully connected even if only a small fraction of the correct internal links are found. Therefore, they use a very conservative threshold for their verifier to ensure near-zero false positives, even at the cost of lower recall.
Overview of the end-to-end approach, from raw video frames to tracklet generation and final identity clustering.

Datasets

The system was evaluated on three diverse video datasets and one standard image database:

  • The Big Bang Theory (BBT): Season 1, Episodes 1-6 (5-8 main characters).
  • Buffy the Vampire Slayer: Season 5, Episodes 1-6 (11-17 characters, significant occlusions).
  • Hannah and Her Sisters: A full-length movie with annotations for 235 characters.
  • Labeled Faces in the Wild (LFW): Used for validating the verification method and comparing against standard image-based clustering benchmarks.

To evaluate the end-to-end performance, the authors introduced Unified Pairwise Precision (UPP) and Unified Pairwise Recall (UPR), which penalize detection errors (missed faces or false detections) alongside clustering errors.

Key Insights and Ideas

  • Precision is King in Clustering: The "aha moment" here is the application of Erdős-Rényi theory to clustering. As shown in Figure 3, as the number of nodes ($N$) increases, the probability of a graph being connected jumps from 0 to 1 with a very small increase in the probability ($p$) of an edge existing. This means you don't need to find every link between two people; you just need to find enough to connect the dots without accidentally linking to someone else.
  • The Power of Reference Sets: By comparing features against a random reference set rather than just each other, the "rank-1 counts" method becomes more robust to global shifts in feature space that might plague standard distance metrics in unconstrained video.
  • Handling Constraints: The authors incorporate "do-not-link" constraints—if two faces appear in the same frame, they must be different people. This simple physical constraint significantly prunes the search space and prevents obvious errors.
Simulation showing that for large graphs, a small probability of connected pairs still leads to a high probability of the entire cluster being connected.

Key Results

The proposed link-based clustering with rank-1 counts achieved state-of-the-art results across all tested datasets, significantly outperforming common algorithms like Spectral Clustering, DBSCAN, and K-Means.

  • Quantitative: On the Hannah and Her Sisters dataset, the system achieved an F-score of 0.6813, compared to 0.3344 for Spectral Clustering and 0.2581 for standard L2 distance.
  • Qualitative: As seen in Figure 1, the system successfully maintains consistent identity coloring across different scenes, even with changes in lighting and background.
  • Robustness: The "rank-1 counts" verifier showed much higher recall at extremely low false-positive rates (e.g., $10^{-6}$) compared to standard L2 distance or template adaptation methods.
Qualitative clustering results from the movie Hannah and Her Sisters, showing consistent identity tracking across various scenes.

Limitations and Future Work

While powerful, the authors note a few scenarios that can disrupt the algorithm:

  • High Similarity: Highly similar individuals, such as family members, might still trigger false positive links.
  • Extreme Variations: If a character appears under such different conditions (e.g., heavy makeup or extreme lighting) that no features match the reference set, the cluster may remain fragmented.
  • Unbalanced Clusters: If one character accounts for the vast majority of frames (e.g., 90%), the underlying assumptions of the random graph model might be challenged.

Future work could involve refining the reference set selection or integrating temporal constraints more deeply into the clustering logic itself.

Summary updated

Abstract

We present an end-to-end system for detecting and clustering faces by identity in full-length movies. Unlike works that start with a predefined set of detected faces, we consider the end-to-end problem of detection and clustering together. We make three separate contributions. First, we combine a state-of-the-art face detector with a generic tracker to extract high quality face tracklets. We then introduce a novel clustering method, motivated by the classic graph theory results of Erdős and Rényi. It is based on the observations that large clusters can be fully connected by joining just a small fraction of their point pairs, while just a single connection between two different people can lead to poor clustering results. This suggests clustering using a verification system with very few false positives but perhaps moderate recall. We introduce a novel verification method, rank-1 counts verification, that has this property, and use it in a link-based clustering scheme. Finally, we define a novel end-to-end detection and clustering evaluation metric allowing us to assess the accuracy of the entire end-to-end system. We present state-of-the-art results on multiple video data sets and also on standard face databases.
BibTeX
@inproceedings{jin2017end,
  author = {SouYoung Jin and Hang Su and Chris Stauffer and Erik Learned-Miller},
  title = {{End-to-end Face Detection and Cast Grouping in Movies Using Erdős-Rényi Clustering}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2017},
  doi = {10.1109/iccv.2017.564},
}
Figure