PaperlayerView exact revision on arXiv

Source-linked AI summary

Clustering Millions of Faces by Identity

Charles Otto, Dayong Wang, Anil K. Jain

arXiv:1604.00989v1cs.CV

TL;DR

The paper addresses scalable clustering of massive collections of unlabeled face images into identities, where the number of images and unknown identities makes runtime and clustering quality challenging. It develops an approximate rank-order clustering method, demonstrates clustering up to 123 million images, and introduces per-cluster quality ranking for manual examination.

  • Problem

    Clustering unlabeled face images into identities is difficult when datasets contain hundreds of millions of images, unknown numbers of identities, noisy or missing labels, and unbalanced identities.

  • Method

    The paper updates rank-order clustering with approximate nearest neighbors and a simplified procedure to improve scalability and clustering accuracy, while defining a per-cluster quality measure.

  • Results

    The method clustered up to 123 million face images into millions of identities and achieved 0.27 pairwise F-measure on the largest dataset considered.

  • Takeaways & Limitations

    An internal quality measure can identify compact, isolated clusters for manual examination, although its performance falls on the largest datasets.

  • Takeaways & Limitations

    Better clustering accuracy still requires improved nearest-neighbor methods, and the method remains limited by challenges in automatically selecting cluster counts and evaluating cluster quality.

Abstract

from arXiv · show

In this work, we attempt to address the following problem: Given a large number of unlabeled face images, cluster them into the individual identities present in this data. We consider this a relevant problem in different application scenarios ranging from social media to law enforcement. In large-scale scenarios the number of faces in the collection can be of the order of hundreds of million, while the number of clusters can range from a few thousand to millions--leading to difficulties in terms of both run-time complexity and evaluating clustering and per-cluster quality. An efficient and effective Rank-Order clustering algorithm is developed to achieve the desired scalability, and better clustering accuracy than other well-known algorithms such as k-means and spectral clustering. We cluster up to 123 million face images into over 10 million clusters, and analyze the results in terms of both external cluster quality measures (known face labels) and internal cluster quality measures (unknown face labels) and run-time. Our algorithm achieves an F-measure of 0.87 on a benchmark unconstrained face dataset (LFW, consisting of 13K faces), and 0.27 on the largest dataset considered (13K images in LFW, plus 123M distractor images). Additionally, we present preliminary work on video frame clustering (achieving 0.71 F-measure when clustering all frames in the benchmark YouTube Faces dataset). A per-cluster quality measure is developed which can be used to rank individual clusters and to automatically identify a subset of good quality clusters for manual exploration.

1 INTRODUCTION

The paper targets scalable clustering of massive unlabeled face collections by identity, motivated by social-media and forensic applications. It develops an approximate Rank-Order approach, evaluates large augmented datasets, and adds per-cluster quality assessment for prioritizing manual review.

  • Motivation: The task is to cluster large numbers of unlabeled face images into identities despite unknown cluster counts, noisy labels, and scalability challenges.Applications include social media and law enforcement, with collections potentially reaching hundreds of millions of faces.
  • Motivation: Unbalanced identity frequencies and difficult image conditions challenge methods such as k-means and face recognition systems.Images may vary in pose, illumination, and occlusion, while k-means tends to generate similarly sized clusters.
  • Contributions: The proposed method updates Rank-Order clustering with approximate nearest neighbors and a simplified procedure to improve scalability and clustering accuracy.The method is paired with a deep-network face representation for large-scale supervised face recognition.
  • Contributions: The study evaluates clustering on LFW augmented with up to 123M unlabeled web images and examines internal quality measures for ranking clusters without identity labels.The evaluation addresses both large-scale clustering and the practical problem of selecting clusters for manual investigation.
  • Contributions: The paper contributes a preliminary video-clustering study and a per-cluster quality measure for prioritizing subsets of millions of detected clusters.These contributions extend the work beyond identity clustering accuracy to exploratory use and manual review.

2 BACKGROUND

The background frames face clustering as a large-scale problem whose results depend on both the representation and clustering algorithm. Prior work spans specialized face methods and general scalable clustering, while approximate nearest-neighbor construction addresses a key runtime bottleneck.

  • Face Clustering: Face-clustering results depend on both the clustering algorithm and the underlying face representation or distance metric.The literature contains varied representations, algorithms, dataset sizes, and numbers of subjects.
  • Face Clustering: Prior face-clustering studies use spectral, contextual, semi-automatic, subspace, hierarchical, and video-specific approaches on relatively small datasets.Examples include personal photographs, annotated photo collections, constrained face benchmarks, and video frames.
  • Face Clustering: Rank-Order clustering compares nearest-neighbor rankings and has been evaluated on small face datasets, while related approximate k-NN work scales to LFW plus 500K unlabeled images without hard cluster assignment.The rank-order representation is based on a basic distance metric and hierarchical clustering.
  • General Image Clustering: General image-clustering work includes approximate nearest-neighbor pipelines for datasets approaching 1.5 billion images and binary k-means for 1.2 million ImageNet images.Near-duplicate detection is related but targets duplicate images rather than grouping people by identity.
  • Approximate Nearest Neighbor Methods: Constructing nearest-neighbor sets for all n samples naively costs O(n^2), motivating approximate k-NN graph construction and approximate nearest-neighbor searches.The paper uses parallelized recursive feature-space subdivision and overlap-based comparison skipping as one runtime strategy.
  • Clustering Evaluation: Clustering quality is evaluated with pairwise precision and recall against identity labels, alongside runtime.Pairwise precision measures identity agreement within clusters, while pairwise recall measures same-identity pairs placed together.

3 PROPOSED FACE CLUSTERING APPROACH

The proposed approach combines deep face representations with an approximate Rank-Order clustering algorithm that uses local nearest-neighbor structure to improve scalability. It modifies the distance and merge procedures so clustering large face collections becomes substantially less costly while retaining the method’s identity-grouping objective.

  • Face representation: A deep convolutional neural network produces 320-dimensional face features from aligned images for unconstrained face clustering.The network is trained on 404,992 face images from 10,533 subjects in CASIA-webface.
  • Rank-Order clustering: Rank-Order clustering initializes each face as its own cluster and merges clusters using distances based on shared nearest-neighbor structure.The original procedure computes symmetric distances between faces, then uses the minimum sample-to-sample distance between clusters for agglomerative merging.
  • Approximate Rank-Order clustering: The proposed approximation computes only top-k neighbors and replaces numerical rank summation with presence or absence of shared neighbors.This modification emphasizes whether neighbors occur within the short list, rather than their exact numerical ranks, and is reported to improve clustering accuracy.
  • Scalability: The modified clustering step checks only samples sharing a nearest neighbor and performs one merge round, reducing its cost to O(n) with pre-computed neighbors.The original iterative procedure has cost proportional to the square of the current number of clusters per iteration.
  • Per-cluster quality evaluation: Internal cluster-validity measures are used to identify compact and isolated clusters for manual investigation when identity clustering still produces too many clusters.The approach targets practical exploration of very large unlabeled face collections rather than only overall clustering evaluation.

4 DATASETS

The experiments use labeled unconstrained face and video datasets for evaluation, a large unlabeled web-face collection for scale, and CASIA-webface for training the feature representation. Together, these datasets support both benchmark assessment and large-scale clustering experiments.

  • Dataset overview: The experiments use CASIA-webface for training, LFW and YouTube Faces for clustering evaluation, and 123M unlabeled web images for large-scale evaluation.Example images from all four datasets are shown in Figure 6.
  • LFW: LFW contains 13,233 face images of 5,749 individuals, including 4,069 individuals represented by only one image.The dataset consists of celebrity and public-figure images collected from the Internet.
  • YouTube Faces: YouTube Faces contains 1,595 subjects in 3,425 videos and 621,126 labeled video frames.The subjects are a subset of those in LFW, and the experiments use pre-cropped frames.
  • Webfaces: Webfaces contains 123,654,141 web images filtered to include automatically detected faces.The collection is used to augment labeled datasets for larger-scale clustering evaluation.
  • CASIA-webface: The CASIA-webface training subset contains 404,992 face images from 10,533 subjects.The subset includes images for which face alignment was performed successfully.

5 EXPERIMENTS

Experiments show that Approximate Rank-Order clustering improves scalability and clustering accuracy across large face and video datasets, while internal quality measures help rank clusters for manual exploration but weaken at extreme scale.

  • Clustering Algorithm Evaluation: The proposed method outperformed k-means and spectral clustering in F-measure while producing a number of clusters close to the true identity count.For k-means and spectral clustering, the best F-measure occurred with roughly 200 clusters because these methods handled unbalanced data poorly.
  • Approximation Performance: The randomized k-d tree approximation achieved the best runtime and clustering accuracy among the evaluated nearest-neighbor methods.The approximation produced more discriminative nearest-neighbor-list features because frequent faces appeared less often than with exact nearest neighbors.
  • Approximation Performance: A 120-fold runtime improvement was achieved on LFW+1M over brute-force computation, although nearest-neighbor computation remained O(n^2).The updated algorithm also improved clustering-step runtime and accuracy relative to the baseline algorithm.
  • Large-Scale Face Clustering: On the largest dataset, nearest-neighbor computation took approximately two weeks using 123 nodes, while clustering accuracy progressively decayed as dataset size increased.The dataset contained up to 123 million images, and runtime increased approximately linearly when additional cores were used.
  • Video Frame Clustering: YTF clustering produced high precision but lower recall, primarily grouping frames within videos rather than identities across videos.The overall recall was 0.589, while some clusters correctly combined frames from different videos of the same individual.
  • Per-Cluster Quality: Internal Measures: The best internal cluster-quality measure correlated with precision at 0.42, improving to 0.46 after excluding size-two clusters, but ranking became less effective beyond LFW+30M.High-scoring zero-precision clusters were size two, while large-scale top-ranked clusters often contained near-duplicates or cartoon faces.

6 CONCLUSIONS

The paper demonstrates feasible clustering of up to 123M unlabeled face images into millions of identity clusters, while acknowledging limits in large-scale cluster-quality evaluation and representation accuracy.

  • Scalability: 123M unlabeled faces were clustered into an unspecified number of identities on the order of millions.The authors frame this as feasible despite computational challenges addressed through approximation methods and parallelization.
  • Clustering accuracy: 0.27 pairwise F-measure was achieved on the largest dataset, combining 123M unlabeled faces with 13,233 labeled LFW images.
  • Cluster quality: An internal per-cluster quality measure ranks clusters without external identity labels for manual examination.The measure targets compact and isolated clusters.
  • Cluster quality: The internal quality measure was extremely effective on smaller datasets, but its performance declined on larger datasets, although some good-quality clusters remained identifiable.
  • Future work: The authors identify improved nearest-neighbor methods, face representations, cluster-number selection, quality evaluation, and pairwise constraints as future work.
Loading 1604.00989v1…