Face Clustering in Videos with Proportion Prior

1 Introduction

We investigate the problem of clustering faces in real-world videos. It is an important problem in computer vision [Cinbis et al., 2011; Wu et al., 2013; Xiao et al., 2014], which can be applied to many fields, including automatically determining the cast of a feature-length film, content based video retrieval, rapid browsing and organization of video collections, automatic collection of large-scale face data set, etc. However, this task is challenging. In real-world videos, lighting conditions, facial expressions and head poses may drastically change the appearance of faces.

Face clustering is traditionally viewed as an unsupervised process. However, due to the difficulties mentioned above, many efforts have been devoted to seeking for extra knowledge beyond the data instances themselves to obtain weak supervision for clustering. In videos, the most often used knowledge is the relationships within and between the face tracks (where each face track is a sequence of faces) [Wu et al., 2013; Xiao et al., 2014; Zhang et al., 2009], which form two types of constraints during clustering: 1) the must-link constraint: the faces in the same face track must belong to the same person, no matter how different the appearances of the faces look like; 2) the cannot-link constraint: if two face tracks overlap in some frames, then faces in these two tracks must belong to different persons, no matter how similar they look like. Such kind of knowledge can be considered as the "instance-level prior". They cannot regularize the clustering process globally.

∗Corresponding author.

Usually, most of the existing clustering algorithms cannot well cluster the data with unbalanced distributions. However, the unbalanced data are common in real-world applications. In movies or TV series videos, the leading casts appear quite often and the rest appear much less. However, many clustering algorithms cannot well handle such severe unbalance between the data distribution, resulting in that the large class is split apart, and the small class is merged into the large ones and thus missing. To deal with this problem, we propose to make use of the data distribution proportion prior during clustering to protect the large class from being split and the small class from being merged. Such knowledge can be easily obtained by exploiting the external sources such as the script text. One can count the spoken lines of each character in the script text to get the proportion information. Such kind of knowledge can be considered as the "cluster-level prior".

In this paper, we propose a probabilistic clustering model named as Hidden Conditional Random Field (HCRF). This model can incorporate both the instance-level prior and the cluster-level prior in a unified framework. The must-link and cannot-link constraints are naturally embedded in the pairwise potentials of the HCRF model. The proportion prior is set as a regularizer when we optimize the posterior probability of the model given the data.

Our HCRF model is different from the traditional CRF model as the observation model of the traditional CRF is learned in a supervised way. In our model, as there is no class label information available for the hidden nodes during model training, the parameters of the observation model are optimized in an Expectation-Maximization (EM) fashion. Our model is also different from the Hidden Markov Random Fields (HMRF)[Koller and Friedman, 2009] which is used in [Wu et al., 2013]. HMRF is a generative model which focuses on describing how the labels can probabilistically "generate" observations, whereas HCRF is a discriminative model which does not expend modeling efforts on the observations. It directly describes how to take observations and assign them labels [Sutton and McCallum, 2012; Lafferty et al., 2001].

In summary, the contributions of our work include:

1. We propose to use the new proportion prior knowledge generated from external textual sources in the face clustering.
2. As there is no class label known during clustering, it is difficult to determine which cluster best represents which class. Hence, we design a regularizer using the lower bound of KL divergence between the prior proportions and the clustering proportions to minimize the proportion loss.
3. By incorporating both the instance-level and clusterlevel knowledge on the video face data, a HCRF model is developed for face clustering, whose effectiveness is demonstrated in experiments on a public data set with six real-world videos.

The rest of the paper is organized as follows. After reviewing relevant previous works in Section 2, we describe the HCRF model and the use of proportion prior in Section 3, and provide the optimization in Section 4. Experimental evaluations and comparisons of our method are reported in Section 5 and Section 6 concludes the paper.

2 Related work

Face clustering in videos has become a hot topic in recent years. The related works can be grouped into two categories: purely data-driven methods and clustering with prior knowledge. Most of the unsupervised methods[Fitzgibbon and Zisserman, 2002; 2003; R.Wang et al., 2008; Hu et al., 2011; Arandjelovic and Cipolla, 2006] focused on obtaining a good distance measure or mapping raw data to a new space for better representing the structure of the inter-personal dissimilarities from the unlabeled faces.

Above data-driven methods exploit the information inside of the data instances without using any external knowledge. In the videos, the easily available must-link and cannot-link constraints generated from the relationships within and between the face tracks have been explored in the face clustering. In [Vretos et al., 2011], the constraints are exploited to modify the distance matrix and to guide the clustering. However, the method is very computationally expensive. As reported in [Vretos et al., 2011], it takes about 6 days on a data set of 10000 faces. Cinbis et al. [Cinbis et al., 2011] proposed an unsupervised logistic discriminative metric learning (ULDML) method. A metric is learned such that must-linked faces are close, while cannot-linked faces are far from each other. More recently, Wu et al. [Wu et al., 2013] proposed a probabilistic constrained clustering method based on the Hidden Markov Random Fields (HMRF) model for face clustering in videos. The latest work on face clustering with priors was presented by Xiao et al. [Xiao et al., 2014]. They learn a weighted block-sparse low rank representation (WBSLRR). A weighted block-sparse regularizer on the data representation is designed to incorporate the available constraints, so that the resultant data representation is more discriminative.

Face clustering using prior knowledge can be treated as a constrained clustering problem, which has been studied in the works such as COP-KMEANS [Wagstaff et al., 2001], constrained EM [Shental et al., 2004], HMRF-KMeans [Basu et al., 2006] and Penalized Probabilistic Clustering(PPC) [Lu and Todd, 2007]. However, most of the prior knowledge used is on the instance level. Few works exploit the data distribution proportion prior in clustering, which has effects on the cluster level. This is because during the clustering, there is no class label known. It is difficult to determine which cluster best represents which class. Hence, a few works use the proportion prior on classification problems. Yu et al. [Yu et al., 2013] proposed a method called proportion-SVM, which explicitly models the latent unknown instance labels together with the known group label proportions in a large-margin framework. Lefort et al. [Lefort et al., 2011] addressed the inference of probabilistic classification models using the proportion prior.

3 Our method

The faces in videos are usually collected in the form of face tracks. A video usually contains many face tracks appearing along the timeline in the video. During the face clustering, faces in a face track should belong to one cluster while the faces from temporally overlapped face tracks should be assigned into different clusters. Therefore, the problem of face clustering in videos with proportion prior can be defined as follows:

3.1 Problem formulation

Given unlabeled data X = {x1, x2, · · · , xn|xi ∈ Rd }, our goal is to partition X into K (predefined) disjointed clusters. The latent categorical class label set is denoted as Y = {y1, y2, · · · , yn}, y ∈ {1, 2, · · · ,K}. Further provided is the proportion prior for each class in the whole data set, denoted as Π = {π1, · · · , πK}, where πi ∈ [0, 1] is the proportion of class i; and the must-link and cannot-link constraints, denoted as C = {Cml,Ccl}, where the mustlink constraint Cml(xi, xj) indicates that xi and xj should belong to the same cluster while the cannot-link constraint Ccl(xi, xj) indicates that xi and xj should be assigned into different clusters. Based on this information, we want to find a model f : X → Y which can best predict y ∈ Y for observations x ∈ X, pairwise constraints C and proportion prior Π.

3.2 Hidden Conditional RandomField

We introduce a novel model by generalizing the traditional CRF, named as Hidden Conditional Random Field (HCRF), which is shown in Fig. 1. The label variables Y are unobserved, and conditioning on the observations X. Y constitute a Markov random field. The general formulation is given as follows:

where ψu is the unary potential function, ψp is the pairwise potential function, Z(X) =

∑y ∏ni (ψu(yi|X;Θ)ψp(yi, yNi |X; β)) is the partition function, yNi is the neighborhood set of yi, Θ and β are the parameters.

A model with the same name "HCRF" was also given in [Quattoni et al., 2007], which is different from ours. They assume there is an additional latent layer between the observations X and the observed label variables Y . That HCRF is a three-layer model, and used in supervised learning, while our HCRF is a two-layer model, and used in unsupervised learning.

Unary potential function

The unary potential models the relations between observations X and label variables Y . Different from the traditional CRF in which the unary potential function is formulated as the multi-class logistic regression, we adopt the simple exponential function as follows:

where Θ = {θ1, · · · , θK}. I(·) denotes the indicator function: if a = 1, then I(a) = 1, otherwise I(a) = 0.

Pairwise potential function

The pairwise potential embeds the correlations between label variables Y . Since the initial pairwise constraint matrix W that represents Constraints C is usually sparse, it provides limited information to guide clustering. Constraint propagation based on the local smoothness assumption can produce many soft constraints. We use the constraint propagation in [Lu and Ip, 2010] to compute our neighborhood system V as follows:

where α ∈ (0, 1) is the constraint propagation degree and L

is the laplacian matrix. V is a dense constraint matrix where -1 ≤ vij ≤ 1. vij > 0 means the positive correlation, i.e., yi and yj should be same; vij < 0 means the negative correlation, i.e., yi and yj should be different; vij = 0 means no correlation. |vij| indicates the constraint confidence.

Based on neighborhood system V , the pairwise potential between yi and yj is defined as follows:

where φ(yi, yj ) denotes the pairwise energy function, P (yi = yj) is the probability that yi = yj, β is the trade-off parameter between the unary and pairwise potentials, and it will be learned. I(·) denotes the indicator function.

3.3 Cluster proportion loss

In order to deal with the unbalanced distribution of cluster proportions, we use the KL divergence between prior proportions and the actual proportions as the proportion loss. The difficulty to use the proportion prior is that the class label of each cluster is unknown in the clustering. Thus, we cannot determine which prior proportion corresponds to which cluster. There are K! possible correspondences between the prior proportions and the clusters. It is computationally infeasible and unnecessary to enumerate all the correspondences to find the most likely one that minimizes the KL divergence between the two proportion distributions. Assume the actual cluster proportions are denoted as B = {b1, · · · , bK}, we use the KL divergence DKL(sort(Π)||sort(B)) as the proportion loss, where sort(·) is the vector in which the elements are sorted in the ascending(or descending) order.

Theorem 1. DKL(sort(Π)||sort(B)) is the lower bound of DKL(Π||B).

Proof. Given any bijection correspondence between sets Π and B in which any element of set Π corresponds to exactly one element of set B, we sort elements of set Π in the ascending(or descending) order to get vector sort(Π) = π1 · · · πK while maintain the bijection relation to get another vector B1 = b1 · · · bK, where πi corresponds to bi and 1 ≤ i ≤ K. Then we choose any two elements bi and bj, subject to that i < j and (πi - πj) ln bi bj ≤ 0, i.e., (πi - πj)(bi - bj) ≤ 0, and swap them until vector B1 becomes vector sort(B). The change of the KL divergence for the hth swapping can be computed as follows:

where vector Bh becomes new vector Bh+1 after the hth swapping. After all the swappings, the total change of the KL divergence is ∇ = DKL(sort(Π)||sort(B)) - DKL(sort(Π)||B1) = ∑h ∇h ≤ 0. Therefore, DKL(sort(Π)||sort(B)) is the lower bound of DKL(Π||B).

4 Objective function and optimization

4.1 Objective function

The goal is to find the optimal labels Y ∗ and parameters Θ∗ and β∗ that can best explain observations X, pairwise constraints C and proportion prior Π. Since computing the partition function Z in Eq. (1) is intractable, we use the pseudo-

Algorithm 1 EM for Hidden Conditional Random Field

Input: data X, cluster number K, neighborhood system V and proportion prior Π

Output: optimal parameters Θ∗ , β∗ and optimal labels Y ∗

• 1: Initialize Θ(0) and P (0) (Y |X) by Kmeans;
• 2: while not converge do
• 3: t=t+1;
• 4: learn Θ(t) based on P (t-1) (Y |X), β(t-1) and Π;
• 5: learn β(t) based on P (t-1) (Y |X), Θ(t) and Π;
• 6: get P (t) (Y |X) from P (t-1) (Y |X), Θ(t) and β(t) ;
• 7: end while
• 8: return Θ∗ = Θ(t) , β∗ = β(t) and Y ∗ = argmaxY P (t) (Y |X)

likelihood to approximate it. In this way, the posterior probabilities of data X can be factorized as follows:

with

where zi = ∑yi ψu(yi|xi;Θ)ψp(yi, yNi |X; β) is the local partition function.

In order to avoid the extremely small values caused by the production of many posterior probabilities, we turn to the log likelihood. Therefore, the objective function based on the log pseudo-likelihood can be written as follows:

4.2 Optimization

Our HCRF is first initialized via Kmeans and then optimized in an expectation-maximization(EM) framework. The posterior probabilities of each xi ∈ X in K different states are expected and then parameters Θ and β are learned by maximizing the expectations. At last, the optimal labels Y ∗ can be inferred with optimal parameters Θ∗ and β∗ . The main framework is given in Algorithm 1.

E step

We use the mean field theory to approximate the Markov dependencies between label variables Y . In the tth EM iteration, when estimating the probability of label variable yi in state k, i.e., P (t) (yi = k|xi, yNi ; Θ(t) , β(t) ), we consider the probabilities of its neighborhood label variables yNi in that state, i.e., {P (t-1) (yj = k|xj, yNi ;Θ(t-1) , β(t-1) )}yj∈yNi to compute the pairwise potentials of yi. For clarity, we abbreviate P (t) (yi|xi, yNi ; Θ(t) , β(t) ) as P (t) (yi|xi).

M step

In the tth EM iteration, given the posterior probability P (t-1) (yi|xi), we update the parameters by maximizing the expectation of the log pseudo-likelihood in Eq. (8). Parameters Θ and β are learned once in a sequential manner. First, parameter Θ can be optimized by maximizing the following objective function.

where the regularization term λ1‖Θ‖2 is to prevent the overfitting of Θ. We set λ1 = 10-4 in the experiments. Vector sort(Π) = π1 · · · πK and vector sort(B) = b1 · · · bK have the same sorted order. Since Θ = {θ1, · · · , θK}, we need to compute K gradients. The gradient of Eq. (9) with respect to θj(1 ≤ j ≤ K) is

Then parameter β can be learned through maximizing the following objective function.

where λ2‖β‖2 it to avoid the overfitting of β. λ2 is set to 10-4 in the experiments. The gradient of Eq. (13) with regard to β is

with

where φ(yi = k, yNi ) = ∑j∈Ni φ(yi = k, yj) is the neighborhood energy of yi in state k.

5 Experiments

5.1 Experimental settings

We evaluate the performance of our method in the public face data set Big Bang Theory(BBT) given in [Bauml et al., 2013]. It contains episodes 1-6 in the first season of BBT. Each episode has about 20 minutes with 4-6 characters. We get their proportion prior from the script by counting their spoken lines. The character proportions from both the groundtruth and script in the 6 episodes are presented in Fig. 3. It can be observed that the proportion distribution is unbalanced as the biggest proportion is usually 3-10 times the smallest proportion. We can also find that the prior proportion distributions from the script are similar to the groundtruth proportion distributions. This verifies the rationality of our motivation to use the script proportion prior to facilitate the face clustering in the video.

We directly utilize the extracted face data in [Bauml et al., 2013]. Each episode consists of a list of face tracks and each face track has a sequence of faces. The feature of each face is represented by a 240 dimensional Discrete Cosine Transform (DCT) vector. In the experiments, we use the same data preprocessing and result statistics for all the methods. Considering the huge amount of face data in the videos and that the nearby faces in a face track are very similar, we sample the faces to reduce the data volume. First, we uniformly sample 3 faces from each face track. For all the sampled faces in one video, we compute a laplacian matrix in the which the k-nearest neighbor graph is used and k = 10. Then the Laplacian Eigenmaps reduces the feature dimension from 240 to the cluster number. After we get the posterior probability of each sampled face belonging to each cluster, we compute the posterior probabilities of each track. The probability of track t being labeled with k is calculated as p(t, k) = 1n ∑ni=1 P(yi = k|xi), where n is the sampled face number and xi is the ith sampled face in a track. Then we can get the track label by y(t) = argmaxk p(t, k). At last, the face track labels are used to evaluate the clustering performance based on the measures of both accuracy and normalized mutual information(NMI).

5.2 Competing methods

We compare our method to [Wu et al., 2013] and [Lu and Ip, 2010]. They both utilize the pairwise constraints in the clustering and separately achieve state-of-the-art performance when in comparison with different former methods. [Wu et al., 2013] is based on the Hidden Markov Random Fields(HMRF), while [Lu and Ip, 2010] is a constrained spectral clustering called E2CP. Although WBSLRR[Xiao et al., 2014] is more recent and achieves better results, it mainly seeks for the better data representation to improve the clustering performance. Since our method focuses on the clustering rather than the data representation, the comparison with it is not provided. The Kmeans is used as the baseline.

Besides, since the proportion prior in the video face clustering is first investigated in this work, we also design another strategy to utilize it for the comparison. It is straightforward to consider the proportion prior as the cluster prior and use it in the Bayes' rule. Thus, we use it as the third potential function in our model. By incorporating the third potential function, Eq. (6) becomes

In order to use the proportion prior in this way, we need to first find the correspondences between the clusters and the prior proportions. In every iteration of the EM algorithm, we use the cluster sizes as the cues to assign the priors to clusters. We call this strategy as "Bayes prior" in later comparisons.

5.3 Experimental results and analysis

Since we use the EM algorithm to solve our HCRF, we want to investigate how the face clustering performance changes along with the iterations. Fig. 2 shows the average face clustering performance curves of baseline HCRF and its extension with the KL divergence regularizer in 6 videos of BBT. It can be observed that our HCRF largely improves the initial Kmeans clustering accuracy and NMI by about 13% and 10% and it converges quickly in only about 5 iterations. Adding the KL divergence regularizer delays the the convergence but brings obvious improvements over baseline HCRF by about 5% accuracy and about %6 NMI.

Tables 1 and 2 give the comparison of different methods measured by the clustering accuracy and NMI. We can find that our HCRF largely outperforms HMRF and E2CP by more than 7% in both accuracy and NMI. HMRF assumes that the observation node given the hidden node follows the Gaussian distribution. The last step of E2CP is the Kmeans clustering which also favors the Gaussian distribution assumption. If the Gaussian assumption better satisfies, then the two approaches may perform better. However, in real applications, it is known that the face data usually locate on a manifold, thus do not follow the Gaussian distribution. In contrast, our HCRF uses an exponential function to represent the unary potential, which does not expend modeling efforts on the distribution over the observations.

Based on Table 1 and Table 2, our two strategies of using the script proportion prior can both promote the face clustering performance. For the average improvements of accuracy and NMI on the basis of baseline HCRF, the Bayes prior brings about 3.6% and 3.5%, while the KL divergence regularizer contributes about 5.6% and 5.9%. Obviously, the KL divergence regularizer performs better than the Bayes prior. The reason can be explained as follows. For the Bayes prior strategy, the prior proportions are assigned to the clusters once in each EM iteration and then the correspondences between them are fixed in the iteration. This is a greedy assignment strategy. If the assignment is wrong, it cannot be corrected in the current iteration and the wrongness may be magnified in the later iterations. In contrast, the KL divergence regularizer is minimized in the optimization of parameters. During the optimization, the correspondences between the prior proportions and the clusters are not fixed. In each iteration of the gradient descent algorithm, the prior proportions are reassigned to the clusters to compute the KL divergence. By using some techniques to avoid many local minimas, the gradient descent algorithm can take more advantage of the KL divergence regularizer to find better clustering results.

6 Conclusion

In this paper, we have presented the studying on data clustering with cluster proportion prior. We have shown how to exploit the readily available proportion prior to guide the face clustering. A HCRF model has been proposed to predict the class labels of observations. The parameters of the model are learned with the regularization of the proportion loss term in a unified iterative optimization framework. The proposed method has been verified on one public face data set with six real-world TV series episodes. The experiments demonstrate that our HCRF largely outperforms previous state-of-the-art methods and the proposed proportion prior can further improve the face clustering performance.

Acknowledgments

This work was supported in part by the 863 Program (2014AA015104), and the National Natural Science Foundation of China (61332016, 61202325, 61402228).