Cristina Bazgan
email: bazgan@lamsade.dauphine.fr

Sonia Toubaline
email: toubaline@lamsade.dauphine.fr

Daniel Vanderpooten

Efficient algorithms for finding the k most vital edges for the minimum spanning tree problem

Keywords: most vital edges, minimum spanning tree, exact algorithms, mixed integer program

We study in this paper the problem of finding in a graph a subset of k edges whose deletion causes the largest increase in the weight of a minimum spanning tree. We propose for this problem an explicit enumeration algorithm whose complexity, when compared to the current best algorithm, is better for general k but very slightly worse for fixed k. More interestingly, unlike in the previous algorithms, we can easily adapt our algorithm so as to transform it into an implicit exploration algorithm based on a branch and bound scheme. We also propose a mixed integer programming formulation for this problem. Computational results show a clear superiority of the implicit enumeration algorithm both over the explicit enumeration algorithm and the mixed integer program.

Introduction

In many applications involving the use of communication or transportation networks, we often need to identify critical infrastructures. By critical infrastructure we mean a set of links whose damage causes the largest perturbation within the network. Modeling this network by a weighted graph, identifying critical infrastructures amounts to finding a subset of edges whose removal from the graph causes the largest increase in the cost. In the literature this problem is referred to as the k most vital edges problem. In this paper, we are interested in determining a subset of edges of the graph whose deletion causes the largest increase in the weight of a minimum spanning tree (MST). This problem is referred to as k Most Vital Edges MST.

The problem of finding the k most vital edges of a graph has been studied for various problems including shortest path [START_REF] Bar-Noy | The complexity of finding most vital arcs and nodes[END_REF][START_REF] Khachiyan | On short paths interdiction problems : total and node-wise limited interdiction[END_REF][START_REF] Nardelli | A faster computation of the most vital edge of a shortest path[END_REF] and maximum flow [START_REF] Wollmer | Removing arcs from a network[END_REF][START_REF] Ratliff | Finding the n most vital links in flow networks[END_REF][START_REF] Wood | Deterministic network interdiction[END_REF]. For the minimum spanning tree problem defined on a graph G with n vertices and m edges, Frederickson et al. [START_REF] Frederickson | Increasing the weight of minimum spanning trees[END_REF] showed that, for general k, k Most Vital Edges MST is NP -hard and proposed an O(log k)-approximation algorithm. For a fixed k the problem is obviously polynomial. The case k = 1 has been largely studied in the literature [START_REF] Hsu | Finding the most vital edge with respect to minimum spanning tree in a weighted graph[END_REF][START_REF] Iwano | Efficient algorithms for finding the most vital edge of a minimum spanning tree[END_REF][START_REF] Suraweera | Optimal algorithms to find the most vital edge of a minimum spanning tree[END_REF]. Hsu et al. [START_REF] Hsu | Finding the most vital edge with respect to minimum spanning tree in a weighted graph[END_REF] gave two algorithms in O(m log m) and O(n 2 ). Iwano and Katoh [START_REF] Iwano | Efficient algorithms for finding the most vital edge of a minimum spanning tree[END_REF] proposed an algorithm in O(mα(m, n)) using Tarjan's result [START_REF] Tarjan | Applications of path compression on balanced trees[END_REF], where α is the inverse-Ackermann function. Pettie [START_REF] Pettie | Sensitivity analysis of minimum spanning tree in sub-inverse-ackermann time[END_REF] improved the results of Tarjan [START_REF] Tarjan | Applications of path compression on balanced trees[END_REF] and Dixon et al. [START_REF] Dixon | Verification and sensitivity analysis of minimum spanning trees in linear time[END_REF], and therefore the current best deterministic algorithm for solving the case k = 1 is in O(m log α(m, n)). Several exact algorithms based on an explicit enumeration of possible solutions have been proposed [START_REF] Liang | Finding the k most vital edges with respect to minimum spanning trees for fixed k[END_REF][START_REF] Liang | Finding the k most vital edges in the minimum spanning tree problem[END_REF][START_REF] Shen | Finding the k most vital edges with respect to minimum spanning tree[END_REF]. The best one [START_REF] Liang | Finding the k most vital edges with respect to minimum spanning trees for fixed k[END_REF] runs in time O(n k α((k + 1)(n -1), n)) and was achieved by reducing G to a sparse graph. Using Pettie's result [START_REF] Pettie | Sensitivity analysis of minimum spanning tree in sub-inverse-ackermann time[END_REF], the running time of the later algorithm becomes O(n k log α((k + 1)(n -1), n)).

In this paper we propose a new efficient algorithm also based on an explicit enumeration of all possible solutions for k Most Vital Edges MST. Its complexity O(n k log α(2(n -1), n)) for fixed k is theoretically very slightly worse than the complexity of the algorithm proposed by Liang [START_REF] Liang | Finding the k most vital edges with respect to minimum spanning trees for fixed k[END_REF] using Pettie's result [START_REF] Pettie | Sensitivity analysis of minimum spanning tree in sub-inverse-ackermann time[END_REF]. However, given the fact that α(m, n) is always less than 4 in practice, the complexity of these two algorithms can be deemed as equivalent. Moreover, the complexity of our algorithm is better than that of Liang's algorithm for general k. More interestingly, unlike any other algorithm, our algorithm has two specific useful features. First, it can also determine an optimal solution for i Most Vital Edges MST, for each 1 ≤ i ≤ k, with the same time complexity. Second, it can be easily adapted to establish an implicit enumeration algorithm based on a branch and bound procedure. We also present in this paper a formulation by a mixed integer program to solve k Most Vital Edges MST. We implement and test all these proposed algorithms using, for the implicit enumeration algorithm, different branching and evaluation strategies. The results show that the implicit enumeration algorithm is much faster than the explicit enumeration algorithm as well as the resolution of the mixed integer program and its use of memory space can handle instances of significantly larger size. Moreover, we propose an ε-approximate algorithm.

The rest of the paper is organized as follows. In section 2 we introduce notations and some results related to our problem. In section 3 we present a new explicit enumeration algorithm that solves k Most Vital Edges MST. In section 4 we propose another exact algorithm based on an implicit enumeration scheme. In section 5, we present a mixed integer programming formulation for k Most Vital Edges MST. Computational results are presented in section 6. In section 7, we present an ǫ-approximate algorithm and compare it with the exact one. Conclusions are provided in section 8.

Basic concepts and preliminary results

Let G = (V, E) be a weighted undirected connected graph with |V | = n, |E| = m and w(e) ≥ 0 is the integer weight of each edge e ∈ E. We denote by G -E ′ the graph obtained from G by removing the subset of edges E ′ ⊆ E. k Most Vital Edges MST consists of finding a subset of edges S * ⊆ E with |S * | = k that maximizes the weight of a MST in the graph G -S * . We assume that G is at least (k + 1) edge-connected, since otherwise any selection of k edges including the edges of a minimum unweighted cut is a trivial solution. Therefore, we assume k ≤ λ(G)-1, where λ(G) is the edge-connectivity of G. Also, without loss of generality, we suppose in the following that all weights are different (by introducing, if necessary, an arbitrary total order on edges with the same weight). This assumption implies the uniqueness of minimum spanning trees or forests. For a non necessarily connected graph, a minimum spanning forest (MSF) is the union of minimum spanning trees for each of its connected components. In this paper a tree or a forest is considered as a graph but also, for convenience, as a subset of edges. For a set of edges F , w(F ) represents the sum of the weights of the edges in F .

We denote by T 0 the MST of G. Remark that an optimal solution of k Most Vital Edges MST must contain at least one edge of T 0 . For i ≥ 1, let T i be the MSF of the graph G i = G -∪ i-1 j=0 T j . We use in the following the graph U G k = (V, ∪ k j=0 T j ) which has the following interesting property.

Lemma 1. (Liang and Shen [START_REF] Liang | Finding the k most vital edges in the minimum spanning tree problem[END_REF]) For any S ⊆ E, |S| ≤ k, any edge of the MST of graph G -S belongs to U G k .

By Lemma 1, solving k Most Vital Edges MST on G reduces to solving the same problem on the sparser graph U G k whose number of edges is at most

(k + 1)(n -1).
Considering T a MST of a graph, the replacement edge r(e) for an edge e ∈ T is defined as the edge e ′ = e of minimum weight which connects the two disconnected components of T \ {e}. The sensitivity of a minimum spanning tree T , i.e. the allowable variation for each edge weight so that T remains a minimum spanning tree, can be computed in O(m log α(m, n)) [START_REF] Pettie | Sensitivity analysis of minimum spanning tree in sub-inverse-ackermann time[END_REF]. In particular, for edges in T , this algorithm provides replacement edges. As a consequence, we get the following result. Proof : Let T * be a minimum spanning tree in a given graph. We calculate the replacement edges r(e) for all edges e ∈ T * . The most vital edge is the edge e * such that w(r(e * ))w(e * ) = max e∈T * w(r(e))w(e). 2 Actually, replacement edges belong to a specific subset of edges as shown by the following result. Lemma 3. For each edge e ∈ T i , we have r(e) ∈ T i+1 for i = 0, . . . , k -1.

Proof : Given a graph G, Liang [START_REF] Liang | Finding the k most vital edges with respect to minimum spanning trees for fixed k[END_REF] shows that for each edge e ∈ T 0 , r(e) ∈ T 1 . Applying this to graph G i , for which T i is the MSF, we get the result. 2

3 An explicit enumeration algorithm for finding the k most vital edges

We propose an algorithm that constructs a tree search of depth k -1 in a breadth-first mode. At the i th level of this tree search, i = 0, . . . , k -1, a node s is characterized by: • mv(s): a subset of i edges, corresponding to a tentative partial selection of the k most vital edges.

• U (s) = U G ′ (s) k-|mv(s)| where G ′ (s) = (V, E\mv(s)). Hence, U (s) = (V, ∪ k-|mv(s)| i=0 T i (s)) where T i (s) is the MSF in G ′ (s) -∪ i-1
j=0 T j (s). • mst(s): a subset of edges forbidden to deletion. These edges belonging to T 0 (s), will necessary belong to any MST associated with any descendant of s. Depending on the position of s in the tree search, the cardinality of mst(s) varies from 0 to n -2.

Denote by N i , for i = 0, . . . , k -1, the set of nodes of the tree search at the i th level. We describe in the following the exact algorithm.

We first construct the graph U G k . Let a be the root of the search tree with

mv(a) = mst(a) = ∅, U (a) = U G k , w(T 0 (a)) = w(T 0 )
, and N 0 = {a}. For a level i, 0 ≤ i ≤ k -2, we compute for each node s ∈ N i and each edge e ∈ T 0 (s), the replacement edges r(e) in T 1 (s). Node s gives rise to At level k -1, for each node s ∈ N k-1 and for all edges e ∈ T 0 (s) \ mst(s), we find r(e) in T 1 (s) and we determine a node s * that verifies max k -S ′ . Let r be a node of the tree search such that mv(r) ⊆ S ′ and for any child d of r, mv(d) S ′ . Clearly, r exists and corresponds at worst to root a when S ′ ∩ T 0 = ∅. Since, by definition, r is such that no edge of T 0 (r) belongs to S ′ , we have w ′ = w(T 0 (r)). Moreover, since w(T 0 (r)) ≤ w * , we have w ′ ≤ w * .

|T 0 (s)\mst(s)| children in N i+1 . Each such child d, corresponding to an edge e j in T 0 (s)\mst(s) = {e 1 , . . . , e n-1-|mst(s)| }, is characterized by: • mv(d) = mv(s) ∪ {e j }. • mst(d) = mst(s) ∪ (∪ j-1 ℓ=1 {e ℓ }). • U (d) is updated from U (s) as follows (using Lemma 3): • T 0 (d) = T 0 (s) ∪ {r(e j )} \ {e j } and hence w(T 0 (d)) = w(T 0 (s)) -w(e j ) + w(r(e j )). • For j = 1, . . . , k -|mv(d)|, T j (d) is obtained from T j (s)
We compute now the complexity of Algorithm 1. The construction of U G k requires O(kmα(m, n)) using k times the best current algorithms for MST [START_REF] Chazelle | A minimum spanning tree algorithm with inverse-Ackermann type complexity[END_REF][START_REF] Pettie | An optimal minimum spanning tree algorithm[END_REF]. Denote by t u the time for constructing U G k , by t edge-rep the time for finding the replacement edges for all edges of a minimum spanning tree, and by t gen the time for generating any node s of the tree search (that is determining mv(s), mst(s) and

U (s)). Level 0 requires |N 0 |t edge-rep time. Level i takes |N i |t edge-rep + |N i |t gen time, for 1 ≤ i ≤ k -1.
At level k, we compute the k most vital edges. Thus, the total time of Algorithm 1 is given by

t u + k-1 i=0 |N i |t edge-rep + k-1 i=1 |N i |t gen + |N k |
For each node s ∈ N i , subset mv(s) consists of ℓ tree edges of T 0 (a) and (iℓ) edges belonging to the union set of the (iℓ) replacement edges of these ℓ edges, 1 ≤ ℓ ≤ i (the p replacement edges of an edge e ∈ T 0 (a) are the p edges of minimum weight which connect the two disconnected components of T 0 (a)\{e}). This implies that

|N i | = i ℓ=1 n-1 ℓ K i-ℓ ℓ = i ℓ=1 n-1 ℓ i-1 i-ℓ = n+i-2 i = O(n i ), where K p n = n+p-1 p
is the number of combinations with repetition of p elements chosen from a set of n elements.

For a node s

∈ N i , 1 ≤ i ≤ k -1, U (s) contains at most k -i + 1 forests. Then, t gen is in O((k -i + 1)n) time.
Since the replacement edges of a MST in a graph with n vertices and m edges can be computed in O(m log α(m, n)) [START_REF] Pettie | Sensitivity analysis of minimum spanning tree in sub-inverse-ackermann time[END_REF], t edge-rep is in O(n log α(2(n -1), n)) time. Therefore, the complexity of Algorithm 1 is in O(kmα(m, n) + n k log α(2(n -1), n)) time. Note that the time needed to generate all the nodes of the tree search is dominated by the total time to find, for all nodes s of the tree search, the replacement edges r(e) in T 1 (s) for all edges e ∈ T 0 (s).

2

Remark 1. For each node s of the tree search, we could use, instead of the graph U (s), the graph

U (s) = U G ′′ (s) k-|mv(s)|
where G ′′ (s) is the graph obtained from G by contracting the edges of mst(s) and removing the edges of mv(s).

Thus, U (s) = (V, ∪ k-|mv(s)| i=0 T i (s)) where T i (s) is the MSF of G ′′ (s) -∪ i-1
j=0 T j (s). Unfortunately, given a child d of a node s of the tree search, updating efficiently U (d) from U (s) is not as straightforward as for Ũ . However, even if updating U could be performed more efficiently than Ũ , we would get the same complexity since the time for generating all nodes of the tree search is dominated by the total time for finding the replacement edges for all nodes in the tree search.

Discussion For fixed k, by using the result of Dixon et al. [START_REF] Dixon | Verification and sensitivity analysis of minimum spanning trees in linear time[END_REF], Liang [START_REF] Liang | Finding the k most vital edges with respect to minimum spanning trees for fixed k[END_REF] proposes an algorithm to solve k Most Vital Edges MST in O(n k α((k + 1)(n -1), n)) time. Using Pettie's result [START_REF] Pettie | Sensitivity analysis of minimum spanning tree in sub-inverse-ackermann time[END_REF] Liang's algorithm can be implemented in O(t u + n k log α((k + 1)(n -1), n)) time, where t u is the time for constructing U G k . Our algorithm has a complexity that is theoretically slightly worse than that of Liang. Nevertheless, since α(m, n) is always less than or equal to 4 in practice, the complexity of these two algorithms can be considered as equivalent. Moreover, the advantage of our algorithm is to determine, with the same time complexity, an optimal solution for i Most Vital Edges MST, for 1 ≤ i ≤ k. Indeed, at each level i, we can find among nodes of N i , the node with the largest weight of a MST.

For general k, our bound is clearly better than that of Liang. Indeed, in Liang's algorithm, after the determination of U G k , Liang divides the problem into two cases:

(i) |T 0 ∩ S * | = i, 1 ≤ i < k and (ii) |T 0 ∩ S * | = k where S *
represents a subset of k most vital edges. In (i), for every possible combination of i edges among the n -1 edges of T 0 , 1 ≤ i < k, the author constructs a specific graph G with a number of nodes and edges depending only on k, and determines the ki remaining edges in G. In (ii), from every possible choice of (k -1) edges among the n -1 edges of T 0 , the author constructs a MST T ′ in the graph obtained by deleting these (k -1) edges and finds the k th edge to be removed by using the replacement edges of T ′ . Therefore, (i) and (ii) are performed respectively in k-1 i=1 n-1 i (t G + t k-i ) and n-1 k-1 t last time, where t G , t k-i and t last are respectively the time to construct G, the time to determine the ki remaining edges to be removed from G and the time to find the k th edge to be removed from T ′ ∩ T 0 . Note that Liang, who considers only the case where k is fixed, does not need to explicit the term involving t k-i . However, for general k, even if expressing the complexity of his algorithm as in

O(t u + k 3 n k + k-1 i=1 n-1 i t k-i + kn k log α((k + 1)(n -1), n))
, one can observe that it is relatively larger than the complexity of our proposed algorithm that remains in O(t u + n k log α(2(n -1), n)) time.

The other exact algorithms proposed in the literature [START_REF] Liang | Finding the k most vital edges in the minimum spanning tree problem[END_REF][START_REF] Shen | Finding the k most vital edges with respect to minimum spanning tree[END_REF] have a worse complexity than our algorithm both for fixed ad general k.

An implicit enumeration algorithm for finding the k most vital edges

An interesting feature of our explicit enumeration algorithm is that, unlike the algorithms previously proposed, it can easily be adapted to design an implicit algorithm based on a branch and bound scheme. To do this, we use for each node s an upper bound U B(s) based on successive replacements of edges. We also use lower bounds LB(s) constructed by extending the forest, corresponding to s, to a particular minimum spanning tree.

In order to obtain the best possible bounds, we construct U (s) for each node s, instead of using Ũ (s). For each child d of s, U (d) is determined by constructing

T i (d), for 0 ≤ i ≤ k -|mv(d)| from the edges of U (s).

Lower bounds

For a fixed node s of the tree search, k -|mv(s)| edges remain to be deleted from U (s). We present different ways of determining these remaining edges giving rise to three possible lower bounds.

1. LB greedy (s): Given T 0 (s), we compute r(e j ) for all e j ∈ T 0 (s). We delete the edge e * j which realizes max ej ∈T0(s)\mst(s) (w(r(e j ))w(e j )) and replace it by r(e * j ). We update U (s) and repeat the process until we remove k -|mv(s)| edges. The value of this bound is the weight of the last MST obtained. 2. LB f irst (s): We remove the k -|mv(s)| edges of T 0 (s) \ mst(s) having the smallest weight, and we construct a MST from the remaining edges in T 0 (s).

The weight of the MST obtained is the value of this bound. 3. LB best (s): Given T 0 (s), we compute r(e j ) for all e j ∈ T 0 (s). We remove the k -|mv(s)| edges in T 0 (s) \ mst(s) whose difference between the weight of their replacement edge and their weight is the largest, and we construct a MST from the remaining edges in T 0 (s). The value of this bound is the weight of the MST obtained.

In order to test these bounds, we computed, for instances with different values of n and k, these three lower bounds at the root a of the tree search. The instances are generated as explained in section 6. Due to space limitation, we give in Table 1, results for two types of instances. We note that there is no dominance between these three bounds. We also note that LB f irst is the fastest in terms of running time but gives bad values. LB greedy , which gives the best values in most cases, takes much more time than the other bounds. LB best , which gives similar values as LB greedy , takes only about twice as much time as LB f irst and about 40 to 100 times less time than LB greedy .

Table 1. Values of the lower and upper bounds at the root of the tree search

Upper bound

Let s be a given node of the tree search. To compute U B(s), we select the edge in T 1 (s) of largest weight and we replace the edge deleted from T j (s) by the edge with largest weight belonging to T j+1 (s), for j = 1, . . . , k -|mv(s)| -1. We repeat this process k -|mv(s)| -1 times.

Let F be the set of the k -|mv(s)| edges selected from T 1 (s) in this process. Then, we must determine the k -|mv(s)| edges to remove. To obtain an upper bound for all feasible solutions obtained from s, we delete the k-|mv(s)| edges of smallest weight among the edges of F ∪T 0 (s)\mst(s). Denote by E min the subset of these selected edges removed. Therefore, U B(s) = w(T 0 (s))+w(F )-w(E min ).

We computed, for instances with different values of n and k, this upper bound at the root a of the tree search (see Table 1). The main observation is that U B(a) is rather close to the optimal value for small values of k and deteriorates as k increases.

Branching strategy

Let a be the root of the tree search. The branching strategy is the same as for the explicit enumeration algorithm. We start with a feasible solution value corresponding to max{LB greedy (a), LB f irst (a), LB best (a)}. We tested two different best first search strategies. The first one is the standard strategy (Branching: best upper bound) where the node with the largest upper bound is selected first. No lower bound is computed and the fathoming test is performed only when we update the current best feasible solution value, which can occur only at level k -1 of the tree search. In the second strategy (Branching: best lower bound), the node with the largest lower bound is selected first. Lower and upper bounds are computed at every node. Since LB best gives values close to the best ones and takes less time, we use this bound for computing a lower bound. Here, the fathoming test is performed at each node by comparing each lower bound value with the current best feasible solution value.

A mixed integer programming formulation for finding the k most vital edges

Consider the graph

U G k = (V, E u ) with E u = ∪ k j=0 T j . Let D = (V, A u
) be the digraph obtained by replacing each edge (i, j) in E u by two arcs (i, j) and (j, i) in A u and let w ij = w(e) for each edge e ∈ E u . In [START_REF] Magnanti | Optimal trees[END_REF], Magnanti and Wolsey present a formulation of the minimum spanning tree problem, called the directed multicommodity flow model. Using this model, we propose the following formulation for k Most Vital Edges MST:

                                       max z∈Z min (i,j)∈Eu (wij + Mij zij)(yij + yji) (j,1)∈Au f ℓ j1 - (1,j)∈Au f ℓ 1j = -1 ∀ℓ ∈ V \{1} (j,i)∈Au f ℓ ji - (i,j)∈Au f ℓ ij = 0 ∀i, ℓ ∈ V \{1}, i = ℓ (j,ℓ)∈Au f ℓ jℓ - (ℓ,j)∈Au f ℓ ℓj = 1 ∀ℓ ∈ V \{1} f ℓ ij ≤ yij ∀(i, j) ∈ Au, ∀ℓ ∈ V \{1} (i,j)∈Au yij = n -1 fij ≥ 0, yij ≥ 0 ∀(i, j) ∈ Au where Z = {zij ∈ {0, 1}, ∀(i, j) ∈ Eu : (i,j)∈Eu zij = k}
In this formulation, we consider node 1 as the root of a MST and every node ℓ = 1 defines a commodity. Denote by f ℓ ij the flow of ℓ passing through (i, j). Variable z ij is equal to 1 if edge (i, j) is deleted and 0 otherwise. In order to discard this edge from any MST, we assign it the weight w ij + M ij where M ij is a large enough constant, e.g.

M ij = max (i,j)∈E w ij + 1 -w ij .
Using the dual of the inner program, we obtain the following mixed integer programming formulation for k Most Vital Edges MST.

• Generated nodes represents the average number of nodes created in the tree search corresponding to instances giving a feasible solutions; • Gap, expressed as a percentage, represents the average over ratios UB -BS UB computed on all instances returning at least one feasible solution, where U B is the final best upper bound and BS is the best solution value found; • Opt/Feas represents the number of instances solved optimally /for which at least one feasible solution was found within the time limit.

We note that the mixed integer program reaches the optimal value for very small instances only. Actually, for n < 100, we only obtain in most cases feasible solutions with rather large gaps which indicates that optimality is far from being reached. Finally, for instances with n ≥ 100, no feasible solutions are returned within the time limit. Moreover, for n = 300 and 400, the execution of the program exceeds the memory after a few seconds (297.437 and 0.56 seconds in average respectively).

From all these remarks, we can conclude that our proposed implicit enumeration algorithm gives better results than the explicit enumeration algorithm as well as the resolution of the mixed integer program and this both in terms of running time and using memory capacity.

ε-approximate algorithm

The proposed algorithm is based on the previous implicit algorithm. The aim being to obtain an ε-approximate solution of the optimum, the condition to generate a node s in the tree search is now (1ε)U B(s) > bestvalue. Indeed, the value v returned by the approximate algorithm must verify opt

(G)(1 -ε) ≤ v ≤ opt(G). Since v is equal to bestvalue, any node for which U B(s)(1 -ε) ≤ bestvalue is fathomed.
The algorithm is implemented in C and tested on the same instances generated in Section 6 and this for ε = 0.01; 0.05 and 0.1. Thus, we compare the ε-approximate algorithm with the implicit algorithm. The results are summarized in Table 3. The meaning of treated and generated nodes is the same as in Section 6 and each given value in the table represents the average over the 10 generated instances for each value of n and k.

We note that the running times of the ε-approximate algorithm are significantly lower than those of the implicit enumeration algorithm. Running times do not exceed 21 seconds for ε = 0.1, 180 seconds for ε = 0.05 and 1 215 seconds for ε = 0.01. We also note that for large instances with n = 300 and 400 nodes, the ε-approximate algorithm solves the problem for ε = 0.05 and 0.1 at the root in a time less than 1 second, and for ε = 0.1 in a time less than 90 seconds while the implicit enumeration algorithm requires 1 793.460 and 7 265.850 seconds respectively. Moreover, the approximate solutions a posteriori are within ε ′ to the optimum, with ε ′ ≤ 0.0006 for ε = 0.01, ε ′ ≤ 0.0047 for ε = 0.05 and ε ′ ≤ 0.00922 for ε = 0.1.

For ε = 0.01, we note that the problem is nearly solved to optimality (ε ′ = 0).

All these remarks show that the proposed lower bounds and upper bound are of very good quality and that the running time of the implicit enumeration algorithm is the time needed to verify the optimality of the solution. Indeed, this optimal solution is either found in a few seconds or determined at the root of the tree search corresponding then to the maximum value of the three lower bounds associated to the root.

Conclusions

Algorithms proposed in this paper can be easily adapted to solve some variants of the k Most Vital Edges MST problem. In a first variant, a removing cost is associated to each edge. The problem consists of finding a subset of edges with total cost bounded by a budget limit whose deletion causes the largest increase in the weight of a minimum spanning tree. In a second variant, we have to determine a minimum number of edges to be removed such that the weight of a minimum spanning tree in the resulting graph is at least a fixed value.

Lemma 2 . 1

 21 Most Vital Edges MST defined on a graph with n vertices and m edges is solvable in O(m log α(m, n)).

  by deleting the replacement edge e rep of the edge deleted from T j-1 (s) and replacing it by its replacement edge r(e rep ) ∈ T j+1 (s). If for a level i and an edge e rep , the replacement edge r(e rep ) does not exist, T j (d) = T j (s)\{e rep } and T ℓ (d) = T ℓ (s) for ℓ = j +1, . . . , k-|mv(d)|. If for a level i, T i (s) = ∅ then T ℓ (d) = ∅ for ℓ = i, . . . , k -|mv(d)|.

s∈N k- 1 maxTheorem 1 .1 8 forall

 118 e∈T0(s)\mst(s) (w(T 0 (s))-w(e)+w(r(e))). An optimal solution is the subset mv(s * ) ∪ {e * } where e * = arg max e∈T0(s * )\mst(s * ) w(T 0 (s * ))w(e) + w(r(e)). The largest weight of a MST in the partial graph obtained by deleting this subset is w(T 0 (s * ))w(e * ) + w(r(e * )). Algorithm 1 describes this procedure. Its correctness and complexity are given in Theorem 1. Algorithm 1 computes an optimal solution for an instance of k Most Vital Edges MST with n vertices and m edges in O(kmα(m, n) + n k log α(2(n -1), n)) time. Algorithm 1: Explicit resolution of k MVE MST /* Let a be the root of the tree search */ Construct U G k ; 2 mv(a) ← ∅; mst(a) ← ∅; w(T0(a)) ← w(T0); U (a) ← U G k ; 3 N0 ← {a}; Ni ← ∅, i = 1, . . . , k -1; 4 for i ← 0 to k -2 do 5 forall s ∈ Ni do 6 forall e ∈ T0(s) do 7 find r(e) in T1(s); /* T0(s)\mst(s) = {e1, . . . , e n-1-|mst(s)| } */ ej ∈ T0(s)\mst(s) do /* create a new node d, a child of s */ 9 mv(d) ← mv(s) ∪ {ej }; 10 w(T0(d)) ← w(T0(s))w(ej ) + w(r(ej )); 11 mst(d) ← mst(s) ∪ (∪ j-1 ℓ=1 {e ℓ }); 12 determine U (d); 13 Ni+1 ← Ni+1 ∪ {d}; 14 max ← 0; 15 forall s ∈ N k-1 do 16 forall e ∈ T0(s) do 17 find r(e) in T1(s); 18 forall e ∈ T0(s)\mst(s) do 19 if w(T0(s))w(e) + w(r(e)) > max then 20 max ← w(T0(s))w(e) + w(r(e)); 21 e * ← e; 22 s * ← s; /* The largest weight of a MST in the partial obtained graph is w(T0(s * ))w(e * ) + w(r(e * )) */ 23 return S * = mv(s * ) ∪ {e * }; Proof : We first show that Algorithm 1 gives an optimal solution for k Most Vital Edges MST. Let S * be the solution returned by Algorithm 1, and w * the weight of the MST in U G k -S * . Consider any solution S ′ , with |S ′ | = k, and w ′ the weight of the MST in U G

Table 3 .

 3 Results of the ε-approximate algorithm

	n k				ε-approximate algorithm
			ε = 0.01			ε = 0.05		ε = 0.1
		Time	Nodes	ε ′	Time	Nodes	ε ′	Time	Nodes	ε ′
		(s)	Treated Generated	(s)	Treated Generated	(s) Treated Generated
	20 3	0.000	162.9	30.6 0.00000 0.000	136.9	14.0 0.00000 0.000	100.6	7.4 0.00198
	5	0.035	3 108.2	384.6 0.00000 0.024	2 068.8	211.1 0.00043 0.012 1 258.4	113.1 0.00267
	7	0.393	33 258.5	4 356.0 0.00000 0.273	21 820.0	2 575.7 0.00323 0.174 13 209.9	1 451.0 0.00922
	9	3.044	237 267.0 32 085.4 0.00000 2.180 160 036.0 20 093.2 0.00421 1.376 93 275.6 10 888.2 0.00735
	25 3	0.000	230.8	26.7 0.00000 0.000	189.8	13.1 0.00263 0.000	98.2	5.7 0.00263
	5	0.093	6 691.6	637.2 0.00060 0.061	4 235.5	345.2 0.00213 0.031 2 002.0	146.1 0.00779
	7	1.648	119 033.8 13 603.0 0.00000 1.066	72 193.8	7 178.9 0.00148 0.606 37 683.2	3 379.8 0.00416
	8	3.513	226 536.1 23 389.9 0.00000 2.255 135 623.2 12 792.9 0.00142 1.242 68 426.4	5 900.1 0.00319
	30 3	0.000	338.1	38.8 0.00000 0.000	280.1	17.3 0.00453 0.000	161.6	7.2 0.00452
	5	0.233	15 137.4	1 171.7 0.00000 0.123	7 302.6	470.5 0.00307 0.059 3 146.2	181.9 0.00363
	7	3.523	209 289.3 18 256.8 0.00000 2.183 119 797.9	9 363.5 0.00470 1.155 57 665.1	4 062.5 0.00721
	50 3	0.025	899.4	48.8 0.00000 0.011	381.6	14.1 0.00000 0.000	76.5	2.4 0.00646
	5	1.790	67 052.0	3 757.3 0.00000 0.635	20 586.6	866.5 0.00178 0.255 7 213.3	241.8 0.00279
	7 74.688 2 534 780.6 130 685.3 0.00000 28.324 820 954.5 36 722.1 0.00053 7.958 193 201.5	7 827.2 0.00316
	75 3	0.092	2 121.1	75.7 0.00000 0.0016	325.4	5.3 0.00241 0.003	75.0	1.0 0.00355
	5	8.334	187 230.6	5 444.6 0.00000 1.679	27 753.6	616.2 0.00168 0.232 2 860.8	50.4 0.00387
	7 510.768 9 838 080.8 336 993.8 0.00000 109.664 1 734 007.8 51 514.5 0.00195 20.661 260 410.7	6 584.0 0.00536
	100 3	0.208	3 341.4	57.4 0.00000 0.013	121.6	1.4 0.00051 0.010	100.0	1.0 0.00308
	5 34.779	561 343.8 10 619.5 0.00000 3.875	41 860.1	611.1 0.00143 0.396 3 307.4	41.6 0.00297
	7 1 214.43 14 901 505.8 377 861.2 0.00000 179.771 1 703 572.1 34 196.8 0.00143 13.940 95 045.1	1 492.2 0.00371
	200 5 165.904	682 703.2 10 147.9 0.00000 0.731	1 693.0	11.5 0.00163 0.131	200.0	1.0 0.00163
	300 5 87.600	164 368.6	1 129.4 0.00030 0.380	300.0	1.0 0.00245 0.379	300.0	1.0 0.00241
	400 5 89.564	80 786.1	257.3 0.00000 0.846	400.0	1.0 0.00000 0.842	400.0	1.0 0.00000

Computational results

All experiments presented here were performed on a 3.4GHz computer with 3Gb RAM. All proposed algorithms are implemented in C. All instances are complete graphs defined on n vertices. Weights w(e) for all e ∈ E are generated randomly, uniformly distributed in [START_REF] Bar-Noy | The complexity of finding most vital arcs and nodes[END_REF]100]. For each value of n and k presented in this study, 10 different instances were generated and tested. The results are reported in Table 2 where each given value is the average over 10 instances. For the implicit enumeration algorithm, treated and generated nodes represent respectively nodes for which we have computed mv, mst, and U and nodes satisfying the condition of not fathoming (U B > bestvalue). Column ♯opt corresponds to the number of instances solved optimally.

We first compare the explicit and implicit enumeration algorithms. The results show that implicit enumeration algorithms are much faster than the explicit enumeration algorithm and can handle instances of considerably larger size. Observe that, for the explicit enumeration algorithm, the tree search size is identical for any instance of the same (n, k) type. As a consequence, either all or none of the instances of a same (n, k) type can be solved. Moreover, for the same reason, computation times show a low variance for all instances of a same (n, k) type. Regarding the implicit enumeration algorithm, the "Branching: best upper bound" strategy yields slightly better running times than the "Branching: best lower bound" strategy. However, the "Branching: best upper bound" strategy, for which fathoming tests are performed less frequently, generates more nodes. Thus, owing to the limited memory capacity, the "Branching: best lower bound" strategy can handle instances of larger size.

We compare now the results obtained by the mixed integer program with those of the implicit enumeration algorithm. For this, we implemented the mixed integer program using the solver CPLEX 12.1 and we run it on the same generated instances. We limited the running time to 1 hour for the instances with 20, 25, 30 and 50 vertices, and to 2 hours for the other instances. The results are also reported in Table 2 where

• Time, given in seconds, is the average running time on the 10 instances. For any instance which is not solved optimally within the time limit, the running time is set to this limit;


Paul Gay

Grégor Dupuy

Carole Lailler

Jean-Marc Odobez

Sylvain Meignier

Paul Deléglise

Comparison of Two Methods for Unsupervised Person Identification in TV Shows

We address the task of identifying people appearing in TV shows. The target persons are all people whose identity is said or written, like the journalists and the well known people, as politicians, athletes, celebrities, etc. In our approach, overlaid names displayed on the images are used to identify the persons without any use of biometric models for the speakers and the faces. Two identification methods are evaluated as part of the REPERE French evaluation campaign. The first one relies on co-occurrence times between overlay person names and speaker/face clusters, and rule-based decisions which assign a name to each monomodal cluster. The second method uses a Conditionnal Random Field (CRF) which combine different types of co-occurrence statistics and pair-wised constraints to jointly identify speakers and faces.

I. INTRODUCTION

The main purpose of this paper is to answer the questions "who is speaking?" and "who is seen?" at any time of the videos. The target persons are both journalists and guests, which can refer either to experts in a specific field, or to politicians, or celebrities. In other words, we try to identify by their names the people of a video using only the information of the video, without any biometric model related to the target persons.

Without any a priori information, person identities can be retrieved either from the speech transcripts or from the overlaid person names (OPN) commonly used to introduce the current speaker (e.g. see Fig 1). Several speaker identification ap- Head: Claude Géuant, unknown OPN: Claude Géant Speaker: Claude Géant proaches using speech transcripts have already been presented in [START_REF] Canseco-Rodriguez | A comparative study using manual and automatic transcriptions for diarization[END_REF][2] [START_REF] Jousse | Automatic named identification of speakers using diarization and ASR systems[END_REF]. Person identification from transcripts generally gives good results when transcripts are well segmented and close to what was said. However, results deteriorates as soon as automatic transcripts, produced by an automatic speech recognition (ASR) system, are used: the error rate in speaker identification increases from [START_REF] Deléglise | Improvements to the lium french asr system based on cmu sphinx: what helps to significantly reduce the word error rate?[END_REF].66% to 75.15% [START_REF] Jousse | Automatic named identification of speakers using diarization and ASR systems[END_REF]. On the other hand, OPNs can be reliably extracted using Optical Character Recognition (OCR) techniques, and their association with people in the videos is easier than analysing whether or not pronounced names in ASR transcripts refer to people appearing in the video.

The identification using OPN, which has started to be investigated 15 years ago [START_REF] Satoh | Name-it: Naming and detecting faces in news videos[END_REF], has since then raised a large amount of work, especially in face clustering tasks [START_REF] Everingham | Hello! my name is... buffy automatic naming of characters in tv video[END_REF], face naming in captioned images [START_REF] Berg | Names and faces in the news[END_REF], and recently, automatic naming within broadcast videos [START_REF] Pham | Naming persons in news video with label propagation[END_REF], [START_REF] Jou | Structured exploration of who, what, when, and where in heterogeneous multimedia news sources[END_REF], [START_REF] Poignant | Unsupervised naming of speakers in broadcast tv: using written names, pronounced names or both?[END_REF], [START_REF] Poignant | Unsupervised speaker identification using overlaid texts in tv broadcast[END_REF], [START_REF] Bendris | Unsupervised face identification in tv content using audio-visual sources[END_REF]. Regarding broadcast news videos, the use of OPNs raises two main challenges i) the sparsity of OPN information which requires to rely on diarization methods to propagate the identification to all person apparitions ii) the ambiguities that arise when several names and clusters co-occur together.

The work we present there has been carried out during the REPERE French evaluation campaign [START_REF] Kahn | A presentation of the repere challenge[END_REF], which focused on multimedia people recognition in television documents. The proposed system, illustrated in Figure 2, consists in a 3-tier architecture.

The first level detects speakers, faces and overlaid person names. The second level associates speakers to faces using cooccurrence statistics between the speaker and the face clusters. In the last level, the overlaid person names are propagated to the speakers, or faces, in order to give, at any time, the identities of the persons in the show. Two identification methods, developped in parallel in different labs, are compared in this paper. The first one relies directly on the co-occurence times between names, faces and speakers and uses a set of rules to assign a name to each monomodal cluster. The second one uses a CRF which jointly performs the naming of all person clusters, thus allowing to account for pair-wised constraints and heterogeneous co-occurrence statistics. Two other consortiums participated to this campaign [START_REF] Poignant | Unsupervised naming of speakers in broadcast tv: using written names, pronounced names or both?[END_REF], [START_REF] Bendris | Unsupervised face identification in tv content using audio-visual sources[END_REF]. Our approach differs from those previous works in, first, the choice of using face diarization directly as a pre-process to work both with speaker and face clusters, and second, the CRF-based identification method.

II. CORPUS

This study was conducted on two corpora from the REPERE French evaluation campaign [START_REF] Kahn | A presentation of the repere challenge[END_REF]. The development corpus (dev) is composed of 28 TV shows. This corpus corresponds to the test corpus of the first evaluation (January 2013). The test corpus (test) is composed of 27 TV shows. It corresponds to the development set of the second evaluation (January 2014). Shows are recorded from the two digital French terrestrial television stations BFM and LCP (respectively MPG2 720 × 576 and MPEG2 544 × 576).

Thoses corpora are balanced between prepared speech, with 15 broadcast news, and more spontaneous speech, from 40 political discussions or street interviews. Only a part of the recordings are annotated, giving respectively a total duration of 3 hours for both corpus.

A keyframe of the corpora is annotated every 10 seconds, giving both identity of speakers and faces. The overlaid text corresponding to a target person is also annotated. The Table I reports some statistics about the corpora, and the Fig 1 shows an example of annotation.

III. LEVEL 1: SPEAKER, FACE AND OPN

The audio processing, known as the speaker diarization task (cf. sub-section III-A), is performed without any prior information regarding speakers: neither the number of speakers, nor their identities, nor voice samples are available. However, speaker diarization only tags audio segments with anonymous automatically-generated labels. The audio stream is split into small segments, which are clustered speakers. The video processing, called face diarization task (cf. sub-section III-B), consists in the same kind of process as the speaker diarization, except it is performed on face tracks in the video stream instead of speech segments in the audio stream. The OPN set (cf. sub-section III-C) is extracted using, first, an OCR on the video stream, then, a named entity detector which uses external ressources (predefined lists, freebase database, google hits,. . . ).

A. Speaker Diarization

The speaker diarization system ("who speak when?") is based on the LIUM Speaker Diarization system [START_REF] Rouvier | An open-source state-of-the-art toolbox for broadcast news diarization[END_REF], freely distributed 1 . This system has achieved the best or second best results in the speaker diarization task on French broadcast news 1 http://www-lium.univ-lemans.fr/en/content/liumspkdiarization evaluation campaigns, such as ESTER2, ETAPE (2011) [START_REF] Gravier | The etape corpus for the evaluation of speech-based tv content processing in the french language[END_REF] and REPERE (january 2012 and january 2013) [START_REF] Galibert | The first official REPERE evaluation[END_REF].

The diarization system is composed of an acoustic Bayesian Information Criterion (BIC)-based segmentation followed by a BIC-based hierarchical clustering. Each cluster represents a speaker and is modeled with a full covariance Gaussian. A Viterbi decoding re-segments the signal using GMMs with 8 diagonal components learned by EM-ML, for each cluster. Segmentation, clustering and decoding are performed with 12 MFCC+E, computed with a 10ms frame rate. Music and jingle regions are removed using a Viterbi decoding with 8 GMMs (trained on french broadcast news data) for music, jingle, silence, and speech (with wide/narrow band variants for the last two, and clean/noised/musical background variants for wideband speech).

Gender and bandwidth are detected before transcribing the signal using the LIUM ASR [START_REF] Deléglise | Improvements to the lium french asr system based on cmu sphinx: what helps to significantly reduce the word error rate?[END_REF]. A new non-speech segmentation is built from the filler words of the transcript. Non-speech segments longer than 0.5 second are removed in the speaker diarization.

In the previous steps, features were used unnormalized in order to preserve information on the background environment, which may help differentiating between speakers. At this point however, each cluster contains the voice of only one speaker, but several clusters can be related to a same speaker. The background environment contribution must be removed from each GMM cluster, through feature gaussianization, in order to obtain a one-to-one relationship between clusters and speakers. Finally, the system is completed with clustering method based on the i-vectors paradigm and Integer Linear Programming (ILP). This new clustering method is fully described in [START_REF] Rouvier | A global optimization framework for speaker diarization[END_REF]. The ILP clustering along with i-vectors speaker models gives better results than the usual hierarchical agglomerative clustering based on GMMs and cross-likelihood distances [START_REF] Barras | Improving speaker diarization[END_REF].

B. Face Diarization

The face diarization ("who appears when?") process consists of four main steps. First, shot boundary detection is performed to split the video stream into homogenous video clips. Second, frontal faces are detected within each shot using Viola And Jones algorithm [START_REF] Viola | Robust real-time face detection[END_REF]. False alarms are filtered out, based on temporal continuity and skin color detection. Then, face tracking is used to temporally extends the face detections within each shot into face tracks and increase the recall detection rate. Eventually, a face clustering step groups all face tracks that belong to the same person together. This last step is carried out using the method from [START_REF] Khoury | Fusing matching and biometric similarity measures for face diarization in video[END_REF]. It is based on a bottom-up algorithm, which computes the face similarities by combining Speeded Up Robust Features based distances, and statistical models built on block-based DCT features. This method reached state of the art results on the publicly available BUFFY dataset [START_REF] Guillaumin | Is that you? metric learning approaches for face identification[END_REF].

C. Overlaid name detection

The process is based on two steps: the first extracts hypotheses sentences from the video overlaid, the second searches for speaker names in the extracted sentences. The system used [START_REF] Chen | Video text recognition using sequential monte carlo and error voting methods[END_REF] to detect texts in the image sequences and transcribe it. The error rates of that system on the January 2012 dry-run corpus of the REPERE campaign is about 12% in terms of character, and 31% in terms of words.

The name research in overlaids is a task of named entity detection reduced to a single entity type: the "persons". Compared to the same task in journalistic texts or audio transcripts, the announcement of the "persons" in the overlaids is well formatted, making the detection easier. Persons are mostly announced over two written lines, where the first refers to the person identity, and the second, the person function. The identity of a person is generally constituted of a firstname followed by a lastname. In some rare cases, the identity of a person only consists in a firstname, as for people interviewed in the street, or a stage name, as for artists.

Usually, named entity detectors use the linguistic context bordering the named entity to help its detection and categorization. The only context in the video overlaids could be the second line which presents the function. We chose to develop a rule-based identities detection system along with identity dictionaries. In that way, transcripts errors are taken into account much more easily than using a CRF-based method, as it was done in name entity detection. Three identity dictionaries were built:

1) target: the first dictionary includes 7345 identities.

Most entries refer to journalists of the processed television stations, political personnalities, athletes and artists recurrently appearing in French media and REPERE training corpus. 2) freebase: The second dictionary is composed of more than 1.7 million of identities extracted from freebase [START_REF] Bollacker | Freebase: A collaboratively created graph database for structuring human knowledge[END_REF]. We only extracted identities of people born after 1900, as well as those for which the birthdate is unknown. 3) firstname: The third and last dictionary consists in more than 17000 firstnames extracted from a specialized web site.

The detection process is only concerned by the first line of the video overlaids (c in the following):

1) Rejection step: c is rejected if the number of characters is less than 3 or more than 30, if c is composed of more than 10 words, or if c includes a keyword belonging to a pre-definite list. That list mostly includes conjugated action verbs. This step aims to reject lines c matching everything else than only an identity, like information messages which start by a person name. 2) c is accepted if it matches an entry from the target dictionary. The search into dictionary is performed using an error tolerance: the identity n of the dictionary is substituted to c if s(c) > 0.8 (eq. 1) such as:

s(c) = min n∈N (1 - d(c, n) max(l(c), l(n)) ) ( 1
)
where N is the target dictionary, d(c, n) the Levenshtein distance between c and n, and l(x) the string length of x. 3) c is accepted if it matches an entry of the freebase dictionary.

Fig. 3. Google roquets for "Laurence Piau" Infobox Images 4) Finally, c is accepted if it starts with a firstname available in the firstname dictionary, if the Google search engine gives clues to confirm the hypothetical identity. The analysis of the HTML page returned by the Google search engine, which answers to a request on c, is used to validate, or invalidate the hypothetical identity (Fig. 3). Analysis criteria on the Google HTML page relies on the frequency of c in the page, the presence of pictures associated to c, the presence of an informative box describing an individual, and the alternative proposed spelling.

IV. LEVEL 2: MATCHING

The next step, using the speaker and face diarization, consists in matching the speaker i ∈ {1, . . . , N } with it's face j ∈ {1, . . . , M }. In the REPERE training corpus, 78.4% of the speakers have their faces appearing on the video. We made the assumption that the more a speaker voice is heard in the same time a face is seen, the higher the chance that speaker and that face correspond to the same person. Therefore, co-occurrence time between speaker i and face j is computed for each pair (i, j). In the following, we refer to that co-occurrence value as δt(i, j). It should be noted that this could be completed with lip activity detection as in [START_REF] Bendris | Unsupervised face identification in tv content using audio-visual sources[END_REF]. The matching problem can be considered as the search of the largest set of pairs (i, j), for which the sum of the co-occurrences δt(i, j) is maximal, and where each speaker i can only be associated to a single face j, et vice versa. Formally, this problem can be formulated as an Integer Linear Programming problem, given in 2, where x i,j is a binary variable equals to 1 when the speaker i is associated with the face j (i.e., (i, j) has been selected).

Maximize:

n i=1 m j=1 δt(i, j)x i,j
Subject to:

n i=1 x i,j = 1, (i = 1, . . . , n) n i=1 x i,j = 1, (j = 1, . . . , m) x i,j ∈ 0, 1 (2)
The number of solution of this problem is p!, with p the higher number between speaker and face cluster numbers. However, an optimal solution to that matching problem can be found in a polynomial time using the Kuhn-Munkres algorithm [START_REF] Munkres | Algorithms for the assignment and transportation problems[END_REF]. In order to use the Kuhn-Munkres algorithm, we transform the maximisation problem into a minimisation problem, by changing the co-occurrence value in:

δt (i, j) = max i,j δt(i, j) -δt(i, j) (3)
After applying the Kuhn-Munkres algorithm, the speaker clusters which have been matched to face clusters are renamed with the same label, in their respective diarization segmentations. To account for segment boundary errors, speakers and faces are only matched if they overlap more than 0.1 second.

V. LEVEL 3: IDENTIFICATION

At this level, audio and video diarization have been already performed. Several speaker clusters have been associated to faces clusters. In addition, the OPNs have been extracted. OPNs are characterized by their appearance and disappearance times, which make them constitute segments. We propose two identification methods. The first one, described in subsection V-A, uses co-occurrence statistics between clusters and OPNs to choose the best identity for each clusters, without any consideration about the identities attributed to the other clusters. The second method (cf. sub-section V-B), inspired from [START_REF] Gay | A conditional random field approach for audio-visual people diarization[END_REF], relies on Conditional Random Fields (CRFs) and performs a joint identification of all person clusters (speakers and faces), allowing to account for uniqueness constraints and co-occurrence statistics between clusters and OPNs (see [START_REF]Face identification from overlaid texts using local face recurrent patterns and crf models[END_REF] for more details).

A. Direct identification

This identification method is first applied to speaker clusters. For speaker clusters that have been associated to a face cluster, the identity is propagated to both speaker and face clusters. Then, this identification method is applied to the face clusters for which no speaker cluster have been matched.

As for the speaker/face clusters matching step (cf. section IV), we used the co-occurrence times δt(C i , P k j ) between the occurrences P k j with k = 1 . . . K j of a OPN P j from the set of OPN P = {P j , j = 1 . . . N P }, and the segments of a speaker or face cluster C i . Each δt(C i , P k j ) is normalized by appearance duration d j k of the occurrence P k j . Each occurrence score of the name P j are then summed. The cluster C i is therefore identified by the name P j giving the highest score among the OPN set P , which refers to all the OPN in cooccurrence with the cluster C i (equation 4).

C i = argmax Pj ∈P Kj k=1 δt(C i , P k j ) d j k (4) d j
k , which is the appearance duration normalization of the occurrence P k j , favours a name P j which recurrently appear during the various person C i interventions, instead of favouring the total appearance durations of OPNs related to the person C i .

B. CRF identification

CRF models enable to efficiently combines heterogeneous statistics by and have been used in a speaker identification task using transcripts [START_REF] Ma | Finding speaker identities with a conditional maximum entropy model[END_REF]. Another advantage is the possibility to introduce pairwise relationships between cluster pairs. Let us denote by C av = {C av i , i = 1 . . . N C av } the set of audiovisual clusters obtained after the speaker/face matching step described in Section IV. Here, each cluster C av i consists either in a speaker/face pair, or a face alone, or a speaker alone. Conversely to the previous method which takes a decision about each mono-modal cluster separately, that method considers audiovisual cluster pairs, thus allowing for more meaningful co-occurrence statistics.

The identification can be seen as an estimation of the label field E = {e i , i = 1 . . . N C av }, such as the label e i corresponds to the name of the cluster C av i . e i takes value from the set of OPNs P , augmented by an anonymous label which should be assigned to anonymous persons. Let G be an undirected graph over the set of random variables C av , P , and E. We then seek to maximize the CRF posterior probability P (E|C av , P ) defined as:

P (E|C av , P ) = 1 Z(P, C av ) × exp 6 i=1 Clq∈Gi λ i f i (Clq) (5)
where Z(P, C av ) is a normalization constant, and each triplet (f i , G i , λ i ) is composed of a feature function f i , the set G i of cliques where this function is defined, and its CRF weight λ i learned at training time.

This naming model exploits four different co-occurrence statistics between clusters and OPNs. First, for each triplet (e i , C av i , P j ), we define:

f audio (e i , C av i , P j ) = Kj k=1 δt(C a i , P k j ) d j k (6)
Where C a i is the audio part of C av i (which can be null). We define similarly two other feature functions for the visual part of C av i : f v alone which counts the co-occurrences when the face is alone in the image, and f v multi which accounts for multi-face images. Thus, the CRF will learn a different λ weight for each case and will be able to weight each type of information. Eventually, we followed the assumption that a person does not appear or speak before the first apparition of his name in an OPN, and defined a function f bef ore (e i , C av i , P )

which returns the number of audio segments from cluster C av i which occurs before the first apparition of the name e i . We also introduce prior knowledge over the anonymous label by defining a fifth feature function f ano (e i , C av i ) which returns 1 if e i is the anonymous label. Lastly, we define a uniqueness function f uniq (e i , C av i , e j , C av j ) over visually overlapping clusters. For such pair C av i , C av j :

f uniq (C av i , C av j , e i , e j ) =
-Inf if e i = e j 0 otherwise VI. EXPERIMENTS

A. Evaluation metrics

The evaluation metric chosen to measure the identification performance is the official REPERE Estimated Global Error Rate (EGER). This metric is defined as follow:

EGER = #f a + #miss + #conf #total (7)
where #total is the number of persons to be detected, #conf the number of persons wrongly identified, #miss the number of missed persons and #f a the number of false alarms. It should be noted that this metric does not take into account the spatial position of the faces but rather focus on evaluating the ability of the system to answer the question "Who is seen?" and "Who is speaking".

To evaluate the impact of the identification, we report the Diarization Error Rate (DER). The metric was introduced by the NIST as the fraction of speaking time which is not attributed to the correct speaker using the best match between references and hypothesis speaker labels. Both DER and EGER are computed using the scoring tool developed by the LNE 2 as part of the REPERE campaigns.

B. Overlaid person name detection results

The Table II shows the evaluation results of the overlaid person names, for the both corpora. The EGER is 15.5%. Most of the errors are due to missed overlaid names, which were too close to the overlaid segment boundaries. The 8 confusion errors come from erroneous transcripts, thus generating a substitution of the transcript name with the most similar target name.

C. Association and Identification results

The speaker DER is 13.12% on the dev set and 15.00% on the test set. A third of DER errors come from missed detection. The reason is that BFM is a television station which continuously broadcast, frequently using jingles to capture the public attention. Those are detected as non-speech areas, even if the host is announcing headlines. Regarding the Face 2 The French National Laboratory of Metrology and Testing diarization, the DER is 77% person on the dev set and 77% on the test set. Overall 75% of the errors come from miss detections due to non profile faces and person seen from the back. Qualitatively, we found that the face diarization method provides pure face clusters, but might split one person into different clusters if the head pose variations are important. The identification results for the different systems are presented in Table III. Table 12) is an oracle simulating the best possible results we would reach with perfect diarization and identification systems, while keeping automatic speech segmentation, face and OPN detections. For the speaker part, errors are mostly due to journalist off-voices, which are not announced by OPNs. Considering the faces, miss errors are mainly divided into non-frontal faces and figurative persons not announced by OPNs. The few confusions and false alarms are due to inaccuracies of segment boundaries. In addition to provide an upper bound for the identification results, those tables highlight the differences among the dev and test sets. The identification on the test set is considerably more difficult with an increase of the EGER from 26.3% to 34.6%.

The tables (3-4) and [START_REF] Everingham | Hello! my name is... buffy automatic naming of characters in tv video[END_REF][START_REF] Berg | Names and faces in the news[END_REF] present the identification results of the direct method. The system in tables (3-4) uses OPN ground truth while the other system uses the OPNs automatically extracted. While performances are stable for the dev test, the use of automatic OPN detection increase the EGER from 41.7% to 43%. This change could probably be explained by the confusions errors in the OPN detections only observed in the test set, in table II.

The increase in the miss rate, with respect to the oracle, is mainly due to diarization errors where a person is split into several clusters. Indeed, those smaller clusters are likely to not co-occur with any OPN, and thus, it is not possible to identify them. Confusion errors arise when a cluster co-occurs with wrong names.

Regarding comparisons with the Direct method and the CRF method (tables 5 to 8), two differences can be highlighted. First, the CRF tends to give a better performance on the speaker identification, with an absolute reduction of the EGER from 39.2% to 37.2% on the test set. Improvements mainly come from a reduction of the confusion errors, meaning that the considered co-occurrence statistics, and the joint audiovisual decision process used by the CRF, can help to solve ambiguities. Secondly, considering the head identification, the Direct method gives more confusion and less miss errors. Actually, this method try to identify all possible faces, and may label two co-occurring clusters with the same name. We found this strategy optimal for the EGER metric which does not take into account the spatial positions of the faces as explained previously. The CRF, by using the uniqueness constraint, provides a more accurate naming at the cost of more miss errors. Although performances are similar regarding EGER metric, the CRF results are more suitable for other tasks such as collecting faces of a given person for unsupervised model training.

VII. CONCLUSIONS

In this work, a method for identifying people using overlaid person names in TV shows has been described. Results shows that such OPNs can be reliably extracted and used to identify face and speaker clusters. Two approaches are explored to associate names and clusters. The first identification method relies on co-occurrence times between overlay person names and speaker/face clusters; the second method uses a CRF to jointly identify the speaker and the face clusters. By jointly the audiovisual information and additional context clues, the CRF provides the best results, mainly by solving ambiguous speaker cases where a same person co-occurs with different OPNs.

The difference of performances between the oracle and the automatic systems show that there is room for improvements in the diarization and identification steps. First, the speaker and face diarizations could be optimised for the identification tasks, for instance by taking into account the OPNs information [START_REF] Bredin | Integer linear programming for speaker diarization and cross-modal identification in tv broadcast[END_REF]. Second, the CRF method could easily be extented to include biometrics models learned in an supervised or unsupervised way [START_REF] Lailler | Semi-supervised and unsupervised data extraction targeting speakers: From speaker roles to fame?[END_REF], [START_REF] Liu | Naming faces in broadcast news video by image google[END_REF]. Last but not least, saliency and namedness features could be used in multi-face images to improve name/face association.

Fig. 1 .

 1 Fig. 1. Example of annotation with an OPN introducing the speaker.

Fig. 2 .

 2 Fig. 2. Overview of the proposed system

Fig. 4 .

 4 Fig. 4. Speaker diarization, Face diarization et OPN

TABLE I .

 I

		NUMBER OF KEY FRAMES, SPEAKERS, FACES AND
		OVERLAID NAMES IN CORPORA
	Corpus	Key frames	Speakers	Heads	Overlaid names
	dev	1229	1229	1449	197
	test	1040	1039	1201	146
	both	2269	2268	2650	343

TABLE II

 II

	.	EVALUATION OF OVERLAID NAME DETECTION
		Corpus	EGER	#conf	#miss	#fa
		DEV	14.2%	0	22	6
		TEST	17.1%	8	16	1
		both	15.5%	8	38	7

TABLE III

 III

	.	PRECISION, RECALL AND F-MESURE ON DEV AND TEST
	CORPORA. RESULTS ARE REPORTED WHILE EVALUATING THE SPEAKER
		ONLY, THE HEAD ONLY AND BOTH
	Corpus		EGER	#conf	#miss	#fa
	(1) DEV: Oracle
	Speaker		20.2%	25 (2.0%)	206 (16.8%)	17 (1.4%)
	Head		31.5%	8 (0.5%)	446 (30.8%)	3 (0.2%)
	Spk + Head	26.3%	33 (1.2%)	652 (24.3%)	20 (0.7%)
	(2) TEST: Oracle
	Speaker		29.9%	23 (2.2%)	284 (27.3%)	4 (0.4%)
	Head		38.6%	2 (0.2%)	461(38.4%)	0 (0%)
	Spk + Head	34.6%	25 (1.1%)	745 (33.3%)	4 (0.2%)
	(3) DEV: System "Direct" with OPN groundtruth
	Speaker		25.0%	114 (11.7%)	181(18.4%)	12 (0.8%)
	Head		37.5%	49 (3.4%)	465 (32.1%)	29 (2%)
	Spk + Head	31.7%	163 (6.1%)	646 (24.1%)	41 (1.5%)
	(4) TEST System "Direct" with OPN groundtruth
	Speaker		37.8%	152 (14.6%)	236 (22.7%)	5 (0.5%)
	Head		45.0%	51 (4.3%)	482 (40.1%)	7 (0.6%)
	Spk + Head	41.7%	203 (9.1%)	718 (32.1%)	12 (0.5%)
	(5) DEV: System "Direct"
	Speaker		25.0%	114 (11.7%)	181 (14.7%)	12 (1.0%)
	Head		37.4%	50 (3.5%)	465 (32.1%)	27 (1.8%)
	Spk + Head	31.7%	164 (6.1%)	646 (24.1%)	39 (1.5%)
	(6) TEST: System "Direct"
	Speaker		39.2%	166 (16%)	236 (22.7%)	5 (0.5%)
	Head		46.4%	68 (5.7%)	482 (40.1%)	7 (0.6%)
	Spk + Head	43.0%	234 (10.5%)	718 (32.0%)	12 (0.5%)
	(7) DEV: System "CRF"
	Speaker	24.9 %	102(8.3%)	192(15.6%)	12(1.0%)
	Head		38.4%	55(3.4%)	480(33.1%)	21(1.4%)
	Spk + Head	32.2%	157(5.9%)	672(25.1%)	33(1.2%)
	(8) TEST: System "CRF"
	Speaker		37.2%	150(14.4%)	233(22.4%)	4(0.4 %)
	Head		46.0%	54(4.5%)	492(41.0%)	7(0.6%)
	Spk + Head	42.0%	204(9.1%)	725(32.4%)	11(0.5%)

ACKNOWLEDGMENT

This research was supported by ANR (French National Research Agency) under contract number ANR-2010-CORD-101-01 (SODA project), as well as by the European Union (project FP7-611057 EUMSSI).


Paul

Khoury Elie

Meignier Sylvain

Odobez Jean-Marc

Deleglise Paul

A CONDITIONAL RANDOM FIELD APPROACH FOR FACE IDENTIFICATION IN BROADCAST NEWS USING OVERLAID TEXT (1,2) Gay

Keywords: Face recognition, Conditionnal Random Fields, Broadcast news, Audio-visual

We investigate the problem of face identification in broadcast programs where people names are obtained from text overlays automatically processed with Optical Character Recognition (OCR) and further linked to the faces throughout the video. To solve the face-name association and propagation, we propose a novel approach that combines the positive effects of two Conditional Random Field (CRF) models: a CRF for person diarization (joint temporal segmentation and association of voices and faces) that benefit from the combination of multiple cues including as main contributions the use of identification sources (OCR appearances) and recurrent local face visual background (LFB) playing the role of a namedness feature; a second CRF for the joint identification of the person clusters that improves identification performance thanks to the use of further diarization statistics. Experiments conducted on a recent and substantial public dataset of 7 different shows demonstrate the interest and complementarity of the different modeling steps and information sources, leading to state of the art results.

INTRODUCTION

Due to the growing amount of multimedia documents, there is a crucial need for search and fast browsing tools. A practical way to index multimedia documents is to identify the faces that appear in them. This approach has started to be investigated 15 years ago [START_REF] Satoh | Name-it: Naming and detecting faces in news videos[END_REF] and has raised since then a large amount of work, especially for face clustering tasks [START_REF] Everingham | Hello! my name is... buffy-automatic naming of characters in tv video[END_REF], face naming in captioned images [START_REF] Berg | Names and faces in the news[END_REF], and more recently for actual automatic naming within broadcast videos [START_REF] Moens | Naming persons in news video with label propagation[END_REF][START_REF] Jou | Structured exploration of who, what, when, and where in heterogeneous multimedia news sources[END_REF][START_REF] Giraudel | The repere corpus: a multimodal corpus for person recognition[END_REF][START_REF] Poignant | Unsupervised naming of speakers in broadcast tv: using written names, pronounced names or both?[END_REF] that allows to monitor who said what and when in news programs.

In this paper, we propose an approach to identify faces using overlaid person names (OPNs) extracted by OCR techniques. These OPNs are used to introduce the most important people in the videos, like journalists and guests as illustrated in Fig. 1, making them very appealing [START_REF] Poignant | identification de personnes dans des flux televises[END_REF][START_REF] Poignant | Unsupervised naming of speakers in broadcast tv: using written names, pronounced names or both?[END_REF]: their extraction is much more reliable than pronounced names ob- tained through Automatic Speech Recognition (ASR), and their association with faces or people in the video is easier than analysing whether pronounced names in ASR transcripts refer to people appearing in the video.

Identification using OPNs requires to solve two main tasks. The first one is the association of OPNs to faces, which is ambiguous when a name co-occurs with several faces as shown in Fig 1b, a situation that occurs more often with modern video editing. Secondly, in parallel, as only few appearances of a person are announced by an OPN, it is crucial to propagate the identity information to all the other face occurrences of that person (see Fig 1a-c ). This later task is closely related to face clustering (also called face diarization), which is a difficult problem due to illumination, pose and camera view point changes.

Previous works have addressed automatic face clustering and identity recognition, for captioned images [START_REF] Guillaumin | Multiple instance metric learning from automatically labeled bags of faces[END_REF][START_REF] Berg | Names and faces in the news[END_REF], or in weakly labelled soap series [START_REF] Deschacht | Naming persons in video: Using the weak supervision of textual stories[END_REF]. There, the co-occurrence statistics between face clusters and names is the main cue for association, but can fail when groups of people co-occur in a similar fashion [START_REF] Guillaumin | Multiple instance metric learning from automatically labeled bags of faces[END_REF]. Note that in these use-cases, the naming co-occurrence statistics to rely on are quite different than in broadcast videos where the OPNs are much sparser. To remove clustering ambiguities contextual and multimodal cues along with constraints has been investigated, including clothing [START_REF] Zhang | Automatic name-face alignment to enable cross-media news retrieval[END_REF][START_REF] Anguelov | Contextual identity recognition in personal photo albums[END_REF][START_REF] Khoury | Face-and-clothing based people clustering in video content[END_REF][START_REF] Zhang | A unified framework for context assisted face clustering[END_REF], cluster/name uniqueness constraints in images containing multiple faces [START_REF] Bredin | Qcompere@ repere 2013[END_REF][START_REF] Anguelov | Contextual identity recognition in personal photo albums[END_REF][START_REF] Deschacht | Naming persons in video: Using the weak supervision of textual stories[END_REF], or face attributes and scene co-occurrence [START_REF] Zhang | Automatic name-face alignment to enable cross-media news retrieval[END_REF][START_REF] Zhang | A unified framework for context assisted face clustering[END_REF] in images from photo albums.

In the video context, improvements have been obtained using the audio modality and talking head detection to propagate identification from speakers to faces [START_REF] Bendris | Unsupervised face identification in tv content using audio-visual sources[END_REF][START_REF] Jou | Structured exploration of who, what, when, and where in heterogeneous multimedia news sources[END_REF][START_REF] Poignant | identification de personnes dans des flux televises[END_REF].

In this paper, we identify faces by alternating between a clustering step and a naming step of those clusters. Each step is performed by a dedicated CRF. First, unlike previous works that do speaker and face clustering separately [START_REF] Bendris | Unsupervised face identification in tv content using audio-visual sources[END_REF][START_REF] Jou | Structured exploration of who, what, when, and where in heterogeneous multimedia news sources[END_REF], we use a joint CRF clustering of face tracks and speaker segments already proposed in [START_REF] Gay | A conditional random field approach for audio-visual people diarization[END_REF]. We extend this model to benefit from the OCR/OPNs information. This is achieved by computing a local face visual background (LFB) around each face track, clustering them and assigning to each face track a signature which characterizes the level of recurrence of its LFB in the data. Intuitively, recurrent LFB characterizes people who are important and can be seen as a soft role assignment distinguishing faces to be named from faces of figurative people and thus concretely encourages faces tracks with recurrent LFB to join named clusters, i.e. overlapping an OPN. Secondly, a second CRF performs the join naming of all person clusters, thus allowing to account for uniqueness constraints and co-occurrence statistics between clusters and OPNs. Experiments on a comprehensive public dataset show the benefit of the modelling elements.

METHOD

2.1. Pre-processing First, faces are detected [START_REF] Viola | Robust real-time face detection[END_REF] and tracked within each shot, resulting in a set of face tracks denoted as V = {V i , i = 1 . . . N V }, where each face track is characterized by a set of visual features x surf i (sets of Speeded-Up-Robust features extracted in up to 9 images of the face track which is the representation chosen in [START_REF] Khoury | Face-and-clothing based people clustering in video content[END_REF]), talking head detection features x av i , and a boolean x lf b i indicating whether V i corresponds to a recurrent LFB. Second, OCR [START_REF] Chen | Video text recognition using sequential monte carlo and error voting methods[END_REF] and Named entity detection techniques based on string matching against external resources (predefined lists, freebase database, google hits,...) are applied to extract the set O = {O i , i = 1 . . . N O } of OPNs. Each O i is characterized by its name x opn i ∈ M where M = {n i , i = 1 . . . N N a } denotes the set of unique names extracted from the video. Finally, the audio stream is segmented into a set A = {A i , i = 1 . . . N A } of continuous speech segments called utterances, each described by a set of acoustic features x a i .

Audio-visual (AV) person diarization

Problem formulation The clustering of face tracks and utterances consists in estimating the label field E = {e a i , i = 1..N A , e v j , j = 1..N V } such that the same person index is used for e a i and e v j when the utterance A i and the face track V j correspond to the same person. The labels e a i and e v j take value in the set of possible person indices denoted as P. To achieve this, let G be an undirected graph over the set of random variables A, V , O, and E. We then seek to maximize the CRF posterior probability

P (E|A, V, O) = 1 Z(A, V, O) × exp 6 i=1 Clique∈Gi λ i f i (Clique) (1)
where each triplet (f i , G i , λ i ) is composed of a feature function f i , the set G i of cliques where this function is defined and its CRF weight λ i learned at training time. This model is summarized on the right part of Fig 2 and the 6 feature functions will be described in the next section. Diarization Model components Taking the first 3 functions would correspond to the model in [START_REF] Gay | A conditional random field approach for audio-visual people diarization[END_REF] and the last 3 ones are introduced in this paper to account for OPN information and unicity constraints.

The association function f av (A i , V j , e a i , e v j ) favours the association of talking heads to utterances. It is based on an SVM classifier and a set of measures x av i (lips activity, average absolute and relative face size, etc.). The visual biometric feature functions f v (V i , e v i ), defined for all face tracks V i ∈ V , indicates how likely the visual features x surf i of V i should be labelled with the person index e a i . This is a face modelling task where for each label e i , we need to define a visual model that is learned from the data currently associated to the label. In practice, f v computes as score between V i and a label e v j the average pair-wise SURF vector distances between x surf i and the SURF features of the current face-tracks associated with this label [START_REF] Khoury | Face-and-clothing based people clustering in video content[END_REF]. The acoustic biometric function f a (A i , e a i ) defined over all utterances A i ∈ A is the audio equivalent of f v . We choose a GMM-UBM model following [START_REF] Ben | Speaker diarization using bottom-up clustering based on a parameter-derived distance between adapted gmms[END_REF].

The LFB feature function is driven by the assumption that faces inside a recurrent LFB are likely to correspond to a person announced by an OPN. To this end, we focus on an area around each face track V i to capture the background context of this face as illustrated in Fig 3 . We do not consider full images as the same image might include different face visual contexts (see Fig 1b ). We then characterized each area with SURF features and cluster them using a hierarchical clustering approach [START_REF] Khoury | Face-and-clothing based people clustering in video content[END_REF]. Then, we set x LF B i to true if face track V i belongs to a cluster whose number of elements is higher than a threshold T lf b . The Fig 3 shows examples of obtained recurrent and non-recurrent patterns.

To favour the face tracks identified as recurrent LF B to join a person cluster which could be named. We define the following feature function: For each face track V i ,

f LF B (V i , e v i ) = 1 if e v i ∈ P opn AND x LF B i = true 0 otherwise
where P opn is the set of person clusters co-occurring with an OPN.

The OPN feature functions favour segments (face tracks or utterances) co-occurring with an OPN O j to be assigned to a person cluster likely to belong to the name x OP N j . For each co-occurring couple (V i , O j ) for which V i is alone in the image we define:

f opn alone (V i , O j , e v i ) = p(x opn j |e v i ) with p(x opn j |e v i )
the probability of a name given a cluster as defined in Sec 2.3. Similarly, we use f opn multi if V i cooccurs with other faces and f opn audio for each co-occurring couple (A i , O j ). Differentiate those 3 cases enables to learn specific λ weights so that the model behaviour is adapted to each situation. The uniqueness feature function enforces two faces that cooccur in the same shot to have different labels [START_REF] Berg | Names and faces in the news[END_REF][START_REF] Deschacht | Naming persons in video: Using the weak supervision of textual stories[END_REF]. For such pair V i , V j :

f uniq (V i , V j , e v i , e v j ) = -Inf if e v i =
P (E N |C, O) = 1 Z(C, O) ×exp 6 i=1 Clique∈Gi λ i f naming i (Clique)
This naming model exploits four different co-occurrence statistics between clusters and OPNs. First, for each triplet (e c i , C i , O j ), for which O j co-occurs visually only with C i , we define:

f naming alone (e c i , C i , O j ) = 1 if x n j = e c i 0 otherwise
As for the OPN diarization model components, we define similarly two other functions f naming multi and f naming audio to account for multi-face images and co-occurrences with the audio data. Eventually, we follow the assumption that a person does not appear or speak before the first apparition of his name in an OPN and define f naming bef ore (e c i , C i , O) which returns how many segments from cluster C i occur before the first apparition of the name e c i . We also introduce prior knowledge over the anonymous label by defining a fifth feature function f naming ano (e c i , C i ) which returns 1 if e c i is the anonymous label. Lastly, we define a uniqueness function f naming uniq (e c i , C i , e c j , C j ) over visually overlapping clusters just as in the diarization step.

Optimization

The CRF inference is conducted by applying the following steps: i) The labels are initialized by first performing separately audio and video clustering (see Sec. 2.5) and then associating the clusters to obtain the potential AV person labels P (audio and face cluster couples). The association is conducted using the Hungarian algorithm and the AV association clues as in [START_REF] Gay | A conditional random field approach for audio-visual people diarization[END_REF]. ii) For each resulting person label p i ∈ P , biometric models are learned from their associated data and naming probabilities for each label P (E N |C, O) are estimated by running the Loopy Belief Propagation algorithm on the naming CRF. iii) Given these models, we get the most probable segment labels E according to the diarization CRF by solving E = arg max E P (E|A, V, O). Steps ii) and iii) can be iterated in a Expectation-Maximization style. Faces are eventually identified using the naming probabilities P (E N |C, O). Experiments 2.5. Data and experimental protocol Data and metrics. Experiments are done using the corpora dev2 and test1 from the REPERE evaluation campaign [START_REF] Galibert | The first official repere evaluation[END_REF]. dev1 is used to train the CRFs and optimise the LFB threshold T lf b and test1 for evaluation. Each set consists in 3 hours of annotated data extracted from 7 different shows which include TV news, reports, debates and talk shows (see Fig 1). The evaluation metric chosen to measure identification performance is the official REPERE Estimated Global Error Rate (EGER). This metric is defined as follow:

EGER = #f alse + #miss + #conf identity #total
where #total is the total number of faces to be detected, #conf identity the number of faces wrongly identified, #miss the number of missed faces and #f alse the number of false alarms. We also study the behaviour of the clustering error rate CER = #conf label

#total

where #conf label is the number of faces assigned to the wrong cluster. It is measured before the naming step. Initialisation. The initial face clustering uses a bottom-up algorithm which combines SURF descriptors and statistical models [START_REF] Khoury | Fusing matching and biometric similarity measures for face diarization in video[END_REF]. The initial speaker diarization is performed using a bottom-up approach with an ILP formulation and ivector representation [START_REF] Rouvier | An open-source state-of-the-art toolbox for broadcast news diarization[END_REF]. Model comparisons To analyse the contribution of the audio modality, we evaluate two versions of the naming model. The first one CRF na AV is as described in Sec 2.3. The second one, denoted as CRF na V takes into account co-occurrences with the visual data only. Moreover, we provide results with an oracle which is the best obtainable result with a perfect facename association and propagation system. Thus, oracle errors are faces annotated in the reference but not announced by an OPN and miss face detections. Results have been reported on this dataset in [START_REF] Bredin | Qcompere@ repere 2013[END_REF]. His approach use the same cues as in this paper (talking head, co-occurrence with OPNs, uniqueness constraint) and combine them in a hierarchical person clustering framework.

Results

The results are shown in Table 1. The system (1) consists only in the visual biometric models and the monomodal naming model CRF na V . It obtains an EGER of 42.6 % which is comparable to [START_REF] Bredin | Qcompere@ repere 2013[END_REF].

The system (2) is the same as (1) augmented with the use of the LF B patterns and OPN feature functions. In this case, the CER improves from 6.7% to 5.2%. As mentioned above, the use of LFB recurrence encourages tracks labelled as recurrent to join named clusters to enable their identification in the naming step. We observe that it improves the diarization first On the other hand, wrong assignments happen when a face track of a figurative person is labelled as recurrent, but this is less frequent. The contribution of the OPN feature function is less significant, which makes sense given the sparsity of OPN presence. Regarding identification results, it seems that the naming model CRF na V is not able to profit from the clustering improvement since the EGER remains constant.

With the system (3), the addition of the audio modality seems beneficial to the naming performance. The EGER improves from 42.6% to 40.8%. We found that improvements mainly come from the naming step where the model CRF na AV successfully uses co-occurrences between audio data and OPNs to solve ambiguities in the name-face associations.

The best identification results are achieved by combining all the components with an EGER of 36.8%. It combines the strengths of a person diarization dedicated to identification and an AV naming model able to exploit multimodal co-occurrences and uniqueness constraints. The face diarization obtained with the CRF enables to build more relevant co-occurrence statistics and a better name propagation, and the AV naming model is able to exploit them.

CONCLUSION

In this paper, a method is proposed to unsupervisely identify faces using text overlays in broadcast news. It leverage on two CRF models used for person diarization and person cluster identification. The models combine multiple cues from audio and visual sources. Among them, the characterisation of faces using recurrent LFB patterns optimise the face clustering for the naming task, while the use of the audio modality enables to improve face-name association.

Considering the possible extensions of this work, more faces could be identified by integrating predefined biometric models. Such models can be learned in a supervised or unsupervised manner [START_REF] Liu | Naming faces in broadcast news video by image google[END_REF]. Face recognition in open sets is a difficult problem, but name entity detection from ASR could provide hypothesis on the faces likely to appear.

Fig. 1 .

 1 Fig. 1. Example frames from the REPERE corpus showing the variety of the visual conditions: pose, camera viewpoint, illumination, and the name face association challenges: multi face images (image b) and name propagation (from a to c).

Fig. 2 .

 2 Fig. 2. Factor graphs showing the naming CRF (left) which operates over clusters and OPNs, and the diarization CRF (right) which operates over segments and OPNs.

Fig. 3 .

 3 Fig. 3. The persons on the left are actually announced by an OPN, whereas the persons on the right are non-talking figurative people. (see Fig 1 for the full images)

e v j 0 otherwise 2 . 3 .

 23 Person cluster identification The previous diarization step provides a set of audiovisual clusters C = {C i , i = 1..N C }. The naming step consists in estimating the label field E N = {e c i , i = 1..N C } such that the label e c i corresponds to the name of the cluster C i . e c i takes value from the set of names M augmented by a anonymous label which should be assigned to anonymous persons. As illustrated in the left factor graph of Fig 2, the CRF posterior probability uses 6 feature functions and is expressed as:

Table 1 .

 1 Face identification in EGER and clustering results in CER for the different systems.

	System	EGER CER
	[15]	46.2	-
	(1): fv+ CRF na V	42.6	6.7
	(2): (1) + fopn+f lf b	42.6	5.2
	(3): fv + fa+ fav + CRF na AV	40.8	6.2
	(4): (3) + fopn+f lf b	36.8	5.4
	oracle	32.5	0
	by merging small isolated clusters corresponding to different
	views or poses of a person into that person clusters which co-
	occur with OPNs. Secondly, this approach enable to avoid
	wrong assignments of recurrent LFB tracks to figurative per-
	son clusters which appear during report and off-voice shot.

The authors gratefully acknowledge the financial support from the French Research Agency (ANR) under the Project SODA and from the European Union under the EUMSSI project (grant agreement 611057).