A Graph Based Approach for Naming Faces in News Photos

Derya Ozkan, Pinar DuyguluCVPR 2006 · DOI

Abstract

Automatically labeling faces in news photographs is a significant challenge due to the "in-the-wild" nature of the images and the noise in accompanying captions. This paper proposes a graph-based method that leverages visual consistency and text-based filtering. By representing face similarities as a graph and identifying the "densest component," the system successfully identifies specific individuals across large datasets without manual training.

Introduction

Identifying people in massive collections of news photos is difficult because traditional face recognition often requires controlled environments. News photos, however, feature varied expressions, lighting, and angles. While captions provide clues, they are often "noisy"—mentioning people not present or omitting those who are. This research bridges the gap by combining text-based filtering with visual similarity to isolate the "true" face associated with a name.

Methodology

The proposed multi-stage pipeline treats face naming as a graph discovery problem:

  1. Integration: The dataset is filtered for photos where a queried name appears in the caption, creating a candidate set of faces.
  2. Similarity Representation: Faces are compared using SIFT (Scale Invariant Feature Transform) descriptors. To ensure accuracy, geometrical constraints (matching points must be in similar relative areas) and unique match constraints (one-to-one mapping) are applied.
  3. Graph Construction: A similarity graph is built where nodes represent faces and edges represent visual proximity based on SIFT point distances.
  4. Finding the Densest Component: Using a greedy algorithm, the system identifies the largest, most tightly-knit cluster. The assumption is that the queried person's faces will be more similar to each other than to any "noise" or detection errors.
Representative faces from the news dataset showing varied poses and expressions.

Experimental Setup and Results

The study utilized a dataset of approximately 30,000 faces associated with over 13,000 names from Yahoo! News. Experiments focused on the 23 most frequent individuals.

The method achieved a 20% increase in precision over text-only searches, with average precision and recall of 71% and 68%, respectively. For certain individuals, precision reached 100%. The system is also computationally efficient, partitioning graphs in less than a second.

Discussion and Limitations

A key insight is the power of unsupervised visual consistency; no labeled training data is required. However, the method relies on the queried person being the most frequent face in the search space.

Saddam Hussein's face, a notable failure case where George W. Bush appeared more frequently in related captions.

A notable failure occurred with Saddam Hussein. In photos where his name appeared, George W. Bush's face appeared more frequently, leading the algorithm to incorrectly cluster Bush's face as Hussein's. Future work may involve algorithms that operate directly on weighted graphs rather than binary ones to preserve more similarity data.

Conclusion

By framing face naming as a graph density problem, this approach provides a robust, unsupervised way to organize large-scale news photo collections, effectively ignoring the "noise" inherent in real-world media.

Summary updated

BibTeX
@inproceedings{ozkan2006graph,
  author = {Derya Ozkan and Pinar Duygulu},
  title = {{A Graph Based Approach for Naming Faces in News Photos}},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year = {2006},
  doi = {10.1109/cvpr.2006.29},
}
Figure