# US 2008/0304755 A1 · Face Annotation Framework With Partial Clustering And Interactive Labeling

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2008/0304755 A1
- Document ID: US20080304755A1
- Status: Published application
- Kind: A1
- Application number: 11/760,641
- Filed: 2007-06-08
- Published: 2008-12-11
- Earliest claimed: 2007-06-08
- Assignees: Microsoft Corporation
- Inventors: Rong Xiao; Fang Wen; Xiaoou Tang
- Web page: https://patentgrep.com/patent/US20080304755A1

## CPC

- G06F 16/51: Indexing; Data structures therefor; Storage structures
- G06F 16/40: of multimedia data, e.g. slideshows comprising image and additional audio data (retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70)
- G06F 16/58: Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
- G06F 18/2321: using statistics or function optimisation, e.g. modelling of probability density functions
- G06F 18/41: {Interactive pattern learning with a human teacher}
- G06V 10/763: {Non-hierarchical techniques, e.g. based on statistics of modelling distributions}
- G06V 10/7788: {the supervisor being a human, e.g. interactive learning with a human teacher}
- G06V 40/172: {Classification, e.g. identification}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## Abstract

Systems and methods are described for a face annotation framework with partial clustering and interactive labeling. In one implementation, an exemplary system automatically groups some images of a collection of images into clusters, each cluster mainly including images that contain a person's face associated with that cluster. After an initial user-labeling of each cluster with the person's name or other label, in which the user may also delete/label images that do not belong in the cluster, the system iteratively proposes subsequent clusters for the user to label, proposing clusters of images that when labeled, produce a maximum information gain at each iteration and minimize the total number of user interactions for labeling the entire collection of images.

## Claims

### Claim 1

A method, comprising:
identifying clusters of images in a collection of images, wherein each cluster mostly contains images of a face of a person characterizing the cluster;
accepting a user interaction to label each cluster;
iteratively formulating proposed clusters from remaining images in the collection to solicit subsequent user interactions for labeling images in each proposed cluster, and
wherein each iteration of the formulating proposes a cluster such that the subsequent user interactions maximize an information efficiency for subsequently labeling the remaining images in the collection while using a minimum number of user interactions.

### Claim 2 (depends on 1)

The method as recited in claim 1, wherein identifying clusters comprises including an image in a cluster when a face in the image is identified with a high degree of certainty as the face of the person common to other images in the cluster; and
wherein images that contain faces that are not identified with a high degree of certainty remain unclustered in the collection of images.

### Claim 3 (depends on 1)

The method as recited in claim 1, wherein the iteratively formulating proposed clusters maximizes an information efficiency for formulating subsequent proposed clusters using a minimum number of user operations.

### Claim 4 (depends on 1)

The method as recited in claim 1, wherein iteratively formulating proposed clusters includes selecting a group of images for each cluster to solicit a user interaction for maximizing the information gain based on a global system entropy.

### Claim 5 (depends on 1)

The method as recited in claim 1, wherein maximizing the information efficieny is based on a global system entropy.

### Claim 6 (depends on 1)

The method as recited in claim 1, wherein iteratively formulating proposed clusters includes selecting a group of images for each cluster to solicit a user interaction for minimizing the subsequent user interactions for labeling the remaining images in the collection.

### Claim 7 (depends on 6)

The method as recited in claim 6, wherein minimizing subsequent user interactions is based on a subset-saliency entropy.

### Claim 8 (depends on 1)

The method as recited in claim 1, wherein identifying clusters of images in a collection of images includes the automatic steps of:
detecting and aligning faces;
deriving features associated with each image, including facial features, clothing features, and temporal features;
deriving a Bayesian combination of the features into a similarity matrix containing similarity pairs;
spectrally embedding the similarity pairs in a compact manifold; and
applying an iterative expectation-maximization technique to discern images belonging to one of the clusters.

### Claim 9 (depends on 8)

The method as recited in claim 8, wherein the deriving a Bayesian combination includes calculating facial feature distances, clothing feature distances, and time feature distances;
wherein calculating the feature distances uses a time prior such that a face of a person is associated with the same clothing features during short intervals; and
wherein calculating the feature distances uses a cannot-link prior such that a face of a person appears only once in a single image.

### Claim 10 (depends on 8)

The method as recited in claim 8, further comprising replacing a K-means component of spectral clustering with partial clustering such that only evident clusters emerge.

### Claim 11 (depends on 10)

The method as recited in claim 10, wherein the similarity pairs are modeled as a mixture of Gaussian distributions in the compact manifold, wherein the mixture includes a uniform background noise distribution and an exponential prior to control variances of each component Gaussian distribution in the mixture.

### Claim 12 (depends on 10)

The method as recited in claim 10, further comprising using an iterative Expectation-Maximization (EM) technique to derive evident clusters.

### Claim 13 (depends on 8)

The method as recited in claim 8, wherein the iterative EM technique solves a Maximum a Posteriori (MAP) estimation of a posterior likelihood function.

### Claim 14

A system, comprising:
a storage device for storing a collection of digital images;
a face annotation engine to label the digital images using a minimal number of user interactions;
a partial clustering engine in the face annotation engine to automatically cluster some of the digital images into evident clusters, each evident cluster containing mainly images that include a face of a single person; and
an efficient labeling engine in the face annotation engine to iteratively propose clusters of unlabeled images such that user interactions to label the proposed clusters maximize labeling of the digital images and achieve the minimal number of user interactions.

### Claim 15 (depends on 14)

The system as recited in claim 14, further comprising:
a feature extractor in the partial clustering engine to derive multiple features, including facial features, clothing features, and temporal features of each image; and
a Bayesian face similarity comparator to combine the multiple features into a similarity matrix containing similarity pairs.

### Claim 16 (depends on 15)

The system as recited in claim 15, further comprising a spectral partial clustering module to concentrate similarity pair data based on a mixture of Gaussian distributions, wherein a Gaussian mixture model contains a uniform background noise distribution and an exponential prior to control the variances of each component Gaussian distribution.

### Claim 17 (depends on 16)

The system as recited in claim 16, further comprising an expectation-maximization engine in the partial clustering engine to iteratively solve a Maximum a Posteriori (MAP) estimation of a posterior likelihood to discern images belonging to each of the evident clusters.

### Claim 18 (depends on 14)

The system as recited in claim 14, wherein the efficient labeling engine further includes an information efficiency optimizer to maximize an information gain for automatically labeling unlabeled images in the collection of digital images while minimizing the number of user interactions to label the unlabeled images.

### Claim 19 (depends on 18)

The system as recited in claim 18, wherein the information efficiency optimizer includes:
an information gain model based on global system entropy; and
a user interactions decrease model based on a subset-saliency entropy.

### Claim 20

A system, comprising:
means for automatically grouping some images of a collection of images into clusters, each cluster including only images that reliably contain a face a person associated with that cluster; and
means for user-labeling the clusters; and
means for iteratively proposing subsequent clusters that when user-labeled, minimize the number of user interactions for labeling the remaining unlabeled images based on global system entropy and subset-saliency entropy.
