Mathew Goonewardena
email: mathew-pradeep.goonewardena.1@ens.etsmtl.ca

Hoda Akbari
email: §hodaa@sfu.ca

Wessam Ajib
email: †ajib.wessam@uqam.ca

Halima Elbiaze
email: elbiaze.halima@uqam.ca

On Minimum-Collisions Assignment in Heterogeneous Self-Organizing Networks

Minimum-collisions assignment, in a wireless network, is the distribution of a finite resource set, such that the number of neighbor cells which receive common elements is minimized. In classical operator deployed networks, resources are assigned centrally. Heterogeneous networks contain user deployed cells, therefore centralized assignment is problematic. This paper examines the minimum-collisions assignment problem in the context of physical cell identity (PCI) allocation. Minimumcollisions assignment is NP-complete, therefore a potential-gametheoretic model is proposed as a distributed solution. The players of the game are the cells, actions are the set of PCIs and the utility of a cell is the number of neighbor cells in collision. The price of anarchy and price of stability are derived. Moreover the paper adapts a randomized-distributed-synchronous-update algorithm, for the case, when the number of PCIs is higher than the maximum degree of the neighbor relations graph. It is proven that the algorithm converges to a optimal pure strategy Nash equilibrium in finite time and it is robust to node addition. Simulation results demonstrate that the algorithm is sub-linear in the size of the input graph, thus outperforms best response dynamics.

I. INTRODUCTION

In a heterogeneous and small cell wireless network (Het-SNet), user deployed small cells (SCs), also known as femtocells, must coexist with the operator managed larger cells. Just as any cell, SCs too require operating parameters in order to integrate to the wireless network. The sheer numbers of SCs and the unpredictability of their on-off times have increased the research interest in self-organizing networks (SONs) [START_REF] Peng | Selfconfiguration and self-optimization in LTE-advanced heterogeneous networks[END_REF]. In a SON the network intelligence is distributed among the cells and interactions among the cells define the state to which the network stabilizes. This paper analyzes the equilibrium performance of a self-organizing HetSNet, for the problem of minimum-collisions assignments.

Consider an undirected graph G := (M, E), where M is the set of vertices and E is the set edges. Minimum-collisions assignments is the problem, where the objective is to allocate a finite set of resources N over the vertices of the graph G, such that the sum collisions are minimized. A collision is a situation where two vertices, which share an edge, obtain a common element from N . Examples of minimum-collisions assignment problems are, physical cell identity (PCI) assignment, orthogonal frequency band distribution among cells and scheduling time slots of a finite duration frame over a set of collocated links. The rest of the paper refers to the resource set N , as the set of PCIs and minimum-collisions assignment is synonymously called PCI assignment. PCIs are a limited set of addresses, which is generally lower in number than the cells in the network [START_REF] Gpp | LTE; evolved universal terrestrial radio access (E-UTRA); physical channels and modulation[END_REF].

Minimum-collisions assignment is NP-complete. Consider a reduction from classical graph coloring problem; given a graph G = (M, E) and a positive integer k, can the graph be k-colored? Let this problem be P 1 (G, k) . On the other hand the decision problem of minimum-collisions assignment can be formulated as follows; given the graph G and two positive integers k and τ , is there an assignment of k colors to the nodes such that the number of collisions is at most τ ? This problem is denoted by P 2 (G, k, τ ) . First it is clear that P 2 is NP. Then note that P 1 (G, k) is reduced, in polynomial time, to P 2 (G, k, 0), as P 1 is NP-complete, it follows that P 2 is NPhard. In conclusion since P 2 is NP-hard and is in NP, it is NPcomplete. NP-completeness of the problem justifies seeking heuristic solutions. This paper is concerned with scalable, distributed, heuristic based on the theory of games. Nash equilibrium (NE) is a widely accepted stable solution that characterizes the end result of the interactions among rational agents. The NE PCI assignments provide the network designer a game-theoretical justification of the expected functionality of the network if the control is decentralized among the players.

While minimum-collisions assignment resembles a variation of graph coloring, the objective of the two optimization problems are considerably different. In classical graph coloring optimization, the objective is to minimize the number of colors used, always having sufficient colors to achieve zero collisions [START_REF] Panagopoulou | A game theoretic approach for efficient graph coloring[END_REF]. On the other hand, in minimum-collisions assignment, the number of colors (PCIs) is constant and the objective is to minimize the collisions. There is no motivation to minimize the number of of PCIs used and equally there is no space to scale up the number of PCIs. This key difference sets our research apart from the previous game-theoretic research on coloring problem and for these reasons, the price of anarchy bound of [START_REF] Panagopoulou | A game theoretic approach for efficient graph coloring[END_REF] is not applicable to the objective of this paper.

Yet studying graph coloring problem is useful for some cases of PCI assignment, where a zero collision is known to exist, especially |N | > ∆ (G), where ∆ (G) is the maximum degree of the graph G. In [START_REF] Panagopoulou | A game theoretic approach for efficient graph coloring[END_REF], the classical graph coloring problem is formulated as a potential game played by the vertices. The case considered is when the number of nodes are equal to the number of colors, i.e., |M| = |N |. The considered social cost is the number of colors used by all the players. Clearly in PCI assignment the interest lies in the case when

|M|

|N | and hence [START_REF] Panagopoulou | A game theoretic approach for efficient graph coloring[END_REF] is not directly applicable. Improved bounds for the worst case number of colors required at a NE, under the same setup as in [START_REF] Panagopoulou | A game theoretic approach for efficient graph coloring[END_REF], is presented in [START_REF] Escoffier | Strategic coloring of a graph[END_REF].

A direct adaptation of the algorithm of [START_REF] Moscibroda | Coloring unstructured radio networks[END_REF] for the signal to interference plus noise ration (SINR) model is analyzed in [START_REF] Derbel | Distributed node coloring in the sinr model[END_REF]. In [START_REF] Halldorsson | On spectrum sharing games[END_REF], the problem of assigning a fixed number of channels among base stations (BSs), so that adjacent BSs do not receive the same channel is considered as a game. In [START_REF] Nie | Adaptive channel allocation spectrum etiquette for cognitive radio networks[END_REF], a potential game is introduced for frequency assignment. Their model is based on SINR and the utility is a function of interference. The game discussed in [START_REF] Liu | Common control channel assignment in cognitive radio networks using potential game theory[END_REF], has been modeled to maximize the use of a resource, whereas in our paper the objective is to minimize the use of the same resource among neighbors. There are a number of research works which propose heuristic algorithms for PCI assignment. The algorithm proposed in [START_REF] Oppolzer | Cell identifier assignment in two-tier femtocell networks[END_REF], is decentralized and depends on BSs exchanging neighbor relation tables as opposed to the algorithm in [START_REF] Amirijoo | Neighbor cell relation list and physical cell identity self-organization in LTE[END_REF], which is centralized and makes use of messages from UEs to build the neighbor relation tables and PCI assignment. In [START_REF] Zhang | Dynamic PCI assignment in two-tier networks based on cell activity prediction[END_REF], a dynamic PCI assignment algorithm is proposed. The algorithm categorizes the BSs according to activity level and assigns a unique PCI to busy cells while cells with lower activity obtains a reused PCI. PCI assignment as a graph coloring problem is considered in [START_REF] Bandh | Graph coloring based physicalcell-id assignment for lte networks[END_REF], [START_REF] Wei | Graph theory based physical cell identity self-configuration forLTE-A network[END_REF]. To the best of our knowledge this is the first paper to present a potentialgame theoretic analysis for PCI assignment.

In addition this paper proposes a randomized distributed algorithm to achieve optimal NE, when |N | is at least ∆ (G)+ 1, and proves it to converge in finite time. The algorithm is an improvement upon [START_REF] Chaudhuri | A network coloring game[END_REF], where the proposed algorithm is shown unable to achieve NE for |N | = ∆ (G) + 1. Algorithm of [START_REF] Bohme | Local computation of vertex colorings[END_REF] too requires ∆ (G) + 2 colors for some instances and both, [START_REF] Chaudhuri | A network coloring game[END_REF], [START_REF] Bohme | Local computation of vertex colorings[END_REF] require memory of colors used by neighbors. The proposed algorithm is robust, that is nodes, which have already acquired a color need not change if a downed node reappears in the graph G. Compared to [START_REF] Schneider | Coloring unstructured wireless multihop networks[END_REF], the algorithm of this paper requires communication only among neighbors.

The remainder of the paper is organized as follows. Section II develops the non-cooperative potential game for the problem. Section III analysis the game for price of stability and price of anarchy. Section IV proposes the algorithm and proves convergence. Section V presents numerical results of simulations and finally Section VI concludes the paper.

II. PCI ASSIGNMENT GAME

This paper considers a HetSNet which consists of a set M := {1, . . . , M } of BSs. To avoid trivial instances M ≥ 2. The PCI resource set is N := {1, . . . , N } . The PCI of BS m is denoted by s m . The generation of the graph G = (M, E), has to reflect the requirements of the problem. In the particular case of PCI assignment, the set of edges E, must contain the cells with overlapping coverage areas, to denote possible conflicts. In addition, the edge set also must contain the possible PCI confusions by introducing an edge between two cells which have a common neighbor, even if these two cells may not have common coverage area [START_REF] Ahmed | Distributed graph coloring for self-organization in LTE networks[END_REF]. As shown in the example given in Fig. 1a,edge (d,f ) has to be in G, to denote Following the standard notation of game theory, the vector s -m denotes the choices of all other BSs except m. Let s := (s m , s -m ). Then the total cost, also called the social cost, of the system is the sum cost of the set of BSs,

C (s) := m∈M c m (s m , s -m ) .
The finite strategy normal form game, which is performed by the BSs, is defined by

G M := M, N M , {c m (•) | m ∈ M}
, where N M is the action space of the M players.

To prove the existence of pure strategy NEs of G M , this paper relies on the subclass of non-cooperative games called potential games. Potential games are identified by having a potential function [START_REF] Nisan | Algorithmic game theory[END_REF].

Definition 1. (Weighted potential function) A function φ : N M → R, is a weighted potential function of G M , with weight w, if ∀ m ∈ M, ∀ n, n ∈ N , φ (n, s -m ) -φ (n , s -m ) = w (c m (n, s -m ) -c m (n , s -m )) .
It is well known that all finite games with a potential function posses at least one pure strategy NE and the pure strategy NEs are the local minima of the potential function [START_REF] Nisan | Algorithmic game theory[END_REF]. Furthermore in a finite game with a potential function, the sequential best response (BR) dynamics always converge to a NE [START_REF] Nisan | Algorithmic game theory[END_REF]. The following lemma claims that G M has a weighted potential function and there for posses a NE. Lemma 1. G M has a pure strategy NE.

Proof: The change in cost of player m as it changes its choice, from s m = n to s m = n , n, n ∈ N , while all other players hold their PCIs, (i.e.,s -m constant) is,

∆c m nn , s -m = c m (n , s -m ) -c m (n, s -m ) . ∆c m nn , s -m =a |{m : s m = n , m ∈ M m }| -a |{m : s m = n, m ∈ M m }| . (2)
The corresponding change in total cost is,

∆C nn , s -m =a |{m : s m = n , m ∈ M m }| -a |{m : s m = n, m ∈ M m }| + ∆c nn , s -m , =2∆c nn , s -m . (3)
From ( 2) and (3), the total system cost C (s), is a weighted potential function of G M . The weight in this case is 2.

Now that the existence of NE is established, the next important step in the discussion is to compare the performance of NE solutions against the performance of the optimal solution. The optimal solution solves the problem minimize

s∈N M C (s) . (4)
III. EFFICIENCY OF EQUILIBRIA In general two parameters define the efficiency of NE of a game: price of stability and price of anarchy. The price of stability of a game is the ratio of the minimum cost achievable over all NEs and the optimal cost. The price of anarchy is the ratio of the worst cost over all NEs and the optimal cost [START_REF] Nisan | Algorithmic game theory[END_REF].

The following lemma establishes that there are NEs of the game G M which are as good as the optimal solution of (4).

Lemma 2. The price of stability of G M is 1.

Proof: The proof is by contradiction. Suppose s * is an optimal assignment which minimizes the social cost C (•) . Then let the BSs perform BR dynamics starting from s * . If a BR exist of at least one m ∈ M then the social cost C (•) decreases and s * is not optimal. Therefore there must not exist a BR for any player at the optimal assignment s * . Hence by the definition of NE the optimal assignment is a pure strategy NE and the price of stability of G M is 1.

Lemma 2 is optimistic. Anyhow, a bound for price of anarchy is required to be certain that the the worst case NE performance may not be far from the optimal performance. In the following discussion, it is helpful to imagine the assignment as a routing game on a directed graph G R of two nodes {S, T } and N parallel edges from S to T. Then, in routing terms, all BSs which share the same PCI are on the same edge. But this does not mean that the price of anarchy of an atomic routing game applies to G M . The fundamental difference between a routing game and the PCI assignment is that in a routing game the cost of taking route n ∈ N for player m ∈ M, is a function of all players who take route n. Whereas in PCI assignment the cost is c m , is a function of players who take route n and who belong to M m . Due to this difference in cost function, the bounds given in [START_REF] Nisan | Algorithmic game theory[END_REF], for routing games with linear cost functions are not applicable to game G M . Fig. 2 Proof: The proof is discussed with reference to Fig. 2. Suppose s * is an optimal assignment which solves (4) and s is a NE assignment of G M . For a given assignment s the number of neighbors of m ∈ M on edge s m ∈ N of the routing graph G R of Fig. 2, is denoted by x mn (s). The tightness of the bound ( 5) is yet to be verified. The price of anarchy is not defined for C (s * ) = 0, therefore price of anarchy for d = 0 is not discussed. The following lemma refines the bound for the case when N is larger than the maximum degree of a graph. The degree of a node m ∈ M is M m and maximum degree of graph G is ∆ (G) := max m∈M M m . Lemma 4. Given N > ∆ (G) all NE of G M are socially efficient with zero collisions.

ax msm (s) ≤ax ms * m (s) , ax msm (s) ≤ ax ms * m (s) + ax ms * m (s * ) . Summing over m, C (s) ≤ m ax ms * m (s) + C (s * ) , C (s) C (s * ) ≤ m ax x ms * m (s) C (s * ) + 1. Note that m ax ms * m (s) C(s * ) ≤ m aMm M d . Therefore C (s) C (s * ) ≤ m aM m dM + 1. (5)
Proof: The proof is by contradiction. Suppose there is a NE assignment s, where a BS m ∈ M has collisions.

By assumption the number of neighbors of m is M m < N. Therefore there exists at least one n ∈ N , which is not taken by some m ∈ M m . Therefore m is not playing a BR in the assignment s and therefore by definition of NE, s is not a NE. Therefore at any NE assignment s, all players have zero collisions. Therefore all NEs are globally optimal for (4) and therefore the price of anarchy is 1.

IV. SIMULTANEOUS SYNCHRONOUS UPDATE ALGORITHM

It is well known that the sequential BR dynamics converges to a NE in all potential games. On the other hand simultaneous synchronous BR dynamics generally do not converge to a NE [START_REF] Nisan | Algorithmic game theory[END_REF]. Sequential dynamics are not highly alluring, as only a single player performs an action at a time and also a mechanism is needed to select the next player to perform the BR.

This section proposes a randomized simultaneous synchronous update algorithm which converges to the NE of game G M , for N > ∆ (G) . Note that the game G M does not consider any restriction on the cardinality of resource set N. This algorithm assumes that the nodes posses the knowledge of ∆ (G) . The algorithm assumes message level synchronization, as opposed to symbol level. Lemma 4 dictates that for N > ∆ (G) , all NEs are optimal and have zero collisions. Conversely any zero collision assignment is a NE. Therefore the objective of the algorithm is to assign the set N , to BSs, such that neighbors receive different PCIs and therefore all BSs achieve zero collisions. The proposed algorithm is given in Algorithm 1. The algorithm is local to each BS, i.e., each BS runs an instance of Algorithm 1. The notation, c m (t) denotes the number of collisions of the BS m ∈ M at time t and C (t) = m∈M c m (t) denotes sum collisions at time t ∈ N 0 . The random variable in PCI set N , of player m ∈ M, at time t, is denoted by p m (t, n) . The sampled PCI at time t by player m is denoted by s m (t) .

Initially at time t = 0, BS m, equiprobably samples a PCI from N , call this s m (0) . Then BS m announces its choice to its neighbors m ∈ M m , by the message [s m (0)] and simultaneously listens to the messages from neighbors. A neighbor message can be of two types. It may be a PCI [s m (t)] , or it may be a single bit message set to [START_REF] Peng | Selfconfiguration and self-optimization in LTE-advanced heterogeneous networks[END_REF] . The messages [s m (t)] are from m ∈ M m who have still not acquired a PCI and the single bit message [START_REF] Peng | Selfconfiguration and self-optimization in LTE-advanced heterogeneous networks[END_REF] are from m ∈ M m who have already acquired a PCI, which is same as the one announced by m, i.e. s m (0) = s m (0) . By comparing with neighbor messages BS m can calculate the number of collisions c m (0), at t = 0 and verify if the initial pick s m (0) collides with PCI choices of its neighbors. If it is collision free, i.e., c m (0) = 0, BS m acquires s m (0) , for the rest of its life time and m is said to be in acquired state. If the initial PCI, s m (0) , of m ∈ M experienced collisions, i.e., c m (0) > 0, then m resamples uniformly from N and again shares the new PCI information s m (t) with the neighbors by sending the message [s m (t)] and simultaneously listens to neighbor messages to verify collisions for s m (t) by calculating c m (t) . BS m repeats this process till there is a time t m where all received messages from the neighbors suggest that there is no collision with s m (t m ) and then BS m goes to acquired state with s m (t m ) . Once in acquired state m continues to listen and sends single bit message [START_REF] Peng | Selfconfiguration and self-optimization in LTE-advanced heterogeneous networks[END_REF] to the unacquired set of neighbors Mm ⊂ M m who are in collision with s m (t m ) .

The key difference in Algorithm 1 from [START_REF] Chaudhuri | A network coloring game[END_REF], [START_REF] Bohme | Local computation of vertex colorings[END_REF] is that at each iteration, full set N is sampled, without conditioning on neighbors. An added advantage is that, a node need not maintain a list of choices of its neighbors. The following lemma proves finite time convergence. Notation P (•) denotes probability.

Lemma 5. For N > ∆ (G), Algorithm 1 converges to a 0 collision state in finite time with probability 1.

Proof: The proof is based on first Borel-Cantelli lemma. The proof must show that t∈N0 P (C (t) > 0) < ∞. Without loss of generality, let us consider a BS m ∈ M, which has not acquired a PCI yet. Suppose that by time t ≥ 0, k ≤ M m out of the M m neighbors of m have acquired a PCI. Then the probability that m acquires a PCI in the next time slot is given by

N -k N 1 -1 N Mm-k . Note that N -k N 1 - 1 N Mm-k ≥ N -∆ (G) N 1 - 1 N Mm ≥ 1 ∆ (G) + 1 1 - 1 ∆ (G) + 1 Mm ≥ 1 ∆ (G) + 1 1 - 1 ∆ (G) + 1 ∆(G)+1 ≥ 1 ∆ (G) + 1 • 1 4 ≥ 1 8∆ (G)
.

Let U (t) denote the number of unacquired nodes at the beginning of round t. Then by the above argument, in expectation, at least

p m (0, n) ∼ U m (N ), m ∈ M; #initial uniform distributions# s m (0) = p m (0, n); #sample the random variable # send [s m (0)] to all m ∈ M m ; receive [s m (0)] from m ∈ M m compute c m (0); #
E (U (t)) ≤ E (U (0)) 1 - 1 8∆ (G) t = M 1 - 1 8∆ (G) t .
Then by Markov 's inequality

P (U (t) ≥ 1) ≤ E (U (t)) ≤ M 1 -1 8∆(G) t
. For there to be a collision at time t > 0, there needs be at least one unacquired node at time t -1 ≥ 0. Therefore P (C (t) > 0) ≤ P (U (t -1) > 1) and then

P (C (t) > 0) ≤ 1 + t∈N>0 P (U (t -1) ≥ 1) ≤ 1 + t∈N>0 M 1 - 1 8∆ (G) t-1 ≤ 1 + 8M ∆ (G) .
Finally by the first Borel-Cantelli lemma, since t∈N0 P (C (t) > 0) < ∞, collisions cease after a finite time with probability 1 [START_REF] Williams | Probability with Martingales, ser. Cambridge mathematical textbooks[END_REF]. By Lemma 4, ceasing of collisions is equivalent to each BS acquiring a PCI. Additionally, for G and m eventually acquires. Therefore Algorithm 1 is robust to addition or removal of BSs and neighbor relations (edges). To demonstrate non-robustness of N < ∆ (G) + 1, consider a star graph, where center node has K neighbors, ∆ (G) = K. If initially center node is missing and Algorithm 1 has N < ∆ (G) + 1, there is a non-zero probability that all colors are used by the outer nodes. When the center node comes on, some of the nodes have to be reassigned. V. NUMERICAL RESULTS Fig. 3 demonstrates the convergence of BR dynamics to NEs of G M , hence it verifies that C (s) is a potential function. The simulation environment for Fig. 3 assumes 60 BSs and 5 PCIs. To emphasize on the number of collisions, the cost function parameters are set to, a = 1, d = 0. Therefore the value of sum of cost functions reads the number of collisions. The adjacency matrix, which defines the edges of the graph G = (M, E) , is randomly generated and the maximum number of neighbors for any BS, i.e., ∆ (G), is 41 and the minimum is 18 with an average of 30 neighbors per BS. Two different initial random assignments are considered, init. 1 and init. 2. Also two mechanisms are used to pick the next BS to perform BR dynamics. The first is named "ordered", where BSs are picked according to their index and at the end of the queue circles back to the first BS. The second mechanism is named "random" picks BSs randomly. As can be observed from Fig. 3, the NE depends on both, the initial assignment and the mechanism for picking the next BS. All three curves converge to a their respective NEs.

P (U (t) = 0) ≥ 1-M 1 -1 8∆(G) t > 1-M exp -t 8∆(G) . Letting t = 8δ∆ (G) log M for some constant δ > 0, P (U (t) = 0) > 1 -1 M δ .
To investigate Lemma 4 the network is setup with 14 BSs. The ∆ (G) = 9 and the number of PCIs is 10. The results of BR dynamics are shown in Fig. 4. It is clear that all NEs are achieved with zero collisions and therefore are optimal irrespective of the initial assignment or the BR dynamics, BS selection mechanism. Fig. 5 shows the convergence time of Algorithm 1. The number of PCIs is set to ∆ (G) + 1. Sequential BR for the case N > ∆ (G) requires exactly M iterations to terminate, since each BS needs a chance to verify (and change) its initial assignment. Therefore BR dynamics are linear in the size of the number of BSs. On the other hand, Fig. 5 demonstrates that the empirical average of number of iterations for Algorithm 1 is sub-linear in both the number of BSs M , and the average number of neighbors per BS, i.e., average degree of a node in G. That is an extremely powerful observation because Algorithm 1 outperforms BR dynamics.

VI. CONCLUSION

This paper considered the problem of assigning a finite, N number of resource, to minimize collisions among neighboring cells in a wireless network of M cells. It is shown that the minimum-collisions resource assignment is NP-complete by a reduction of graph coloring problem. The analysis is discussed in the context of physical cell identifier assignment problem. The paper proposed a non-cooperative potentialgame-theoretic solution and demonstrated that the price of stability is 1. Moreover the price of anarchy is upper bounded. In addition a novel fully distributed randomized algorithm for the special case, where the number of neighbors of any node of the network is less than N is developed. The algorithm is proven to converge to a Nash equilibrium solution in finite time and the robustness of the algorithm to addition or deletion of cells and neighbor relations is also proved. Simulations demonstrated that the algorithm grows sub-linearly in the size of the network and therefore outperforms best response dynamics. Several paths remain to be further explored. The tightness of the upper bound for price of anarchy must be investigated. Sub-linearity of the algorithm can be analytically explored. The possibility of a randomized algorithm for the case where the number of neighbors of a BS is higher than N can also be a future extension of this paper.

  (a) For the given PCI assignment, the red and green wiggly arrows denote conflicts and confusions respectively. PCI number is shown above the BS in parenthesis. (b) The only edge not included in neighbor relations graph G is (d, f ). Having the same PCI at nodes d and f does not create collisions.

Figure 1 :

 1 Figure 1: A HetSNet and the corresponding neighbor relations graph G.

Lemma 3 .

 3 provides an example routing graph G R where m ∈ M m but m / ∈ M m . The price of anarchy of G M is upper bounded by m a•Mm d•M + 1, d > 0.

Figure 2 :

 2 Figure 2: The routing graph G R , of game G M . The cost of BS m on link n depends only on the number of neighbors of m that are on n.

  t∈N0

  Thus, in O(δ∆ (G) log M ) rounds, Algorithm 1 converges with probability 1 -1 M δ . Remark 1. (Robustness of Algorithm 1) Removal of an edge or a node does not affect Lemma 5. Consider addition of an edge to graph G, to form G still N > ∆ (G ). Adding a new edge to node m ∈ M, does not affect it if m is already in acquired state. If m has still not acquired, then Lemma 5 holds

Figure 3 :

 3 Figure 3: Convergence of BR dynamics and sub-optimality of Nash equilibria.

Figure 4 :

 4 Figure 4: Numerical analysis of Lemma 4, with max m∈M M m = 9 and 10 number of PCIs.

Figure 5 :

 5 Figure 5: The convergence time of Algorithm 1 is sub-linear in the size of the graph G.

  Simultaneous synchronous update algorithm initialize t = 0; #set timer to zero#

1 8∆(G) U (t) number of nodes acquire a PCI in the next Algorithm 1

  number of collisions # t + +; #increment t by one # while c m (t -1) = 0; #stop when zero collisions# s m (t) = p m (t, n) ; #sample the random variable # send [s m (t)] to all m ∈ M m ; receive [s m (t)] from m ∈ M m compute c m (t); #number of collisions # t + +; end while p m (t, n) ∼ δ (s m (t -1)) ; #fix distribution with P {sm(t -1)} = 1# #at this stage m ∈ M is in acquired state # #continue to listen # while (true) receive [s m (t)] from m ∈ M m ; compute c m (t); #number of collisions # if c (t) > 0 send [1] to m ∈ Mm (t);#only to collision neighbors #

	end if
	t + +;
	end while
	trial period. By backward recursion till t = 0,

Acknowledgment

We are thankful to Dr. Yuval Filmus of Institute for Advanced Study (IAS), Princeton for his comments on NPcompleteness of the problem.


Ronan Sicre
email: ronan.sicre@unicaen.fr

Frédéric Jurie
email: frederic.jurie@unicaen.fr

Discovering and Aligning Discriminative Mid-Level Features for Image Classification

This paper proposes a new algorithm for image recognition, which consists of (i) modeling categories as a set of distinctive parts that are discovered automatically, (ii) aligning them across images while learning their visual model, and, finally (iii) encode images as sets of part descriptors. The so-obtained parts are free of any appearance constraint and are optimized to allow the distinction between the categories to be recognized. The algorithm starts by extracting a set of random regions from the images of different classes, and, using a softassignlike matching algorithm, simultaneously learns the model of each part and assigns image regions to the model's parts. Once the model of the category is trained, it can be used to classify new images by first finding image's regions similar to learned parts and encoding them by the fisher-on-parts encoding, which is another contribution of this paper. The proposed framework is experimentally validated on two publicly available datasets, on which state-of-the-art performance is obtained.

I. INTRODUCTION

This paper addresses the task of image classification, which consists in predicting whether an image contains an object (or a visual concept) based on the content of the image. This topic has received a lot of attention from the computer vision community since the pioneering work of [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF]. The successful approaches rely on the popular bag-of-word model e.g. [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF], [START_REF] Krapac | Modeling spatial layout with Fisher vectors for image categorization[END_REF], [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] or its variants such as the Fisher vectors [START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF].

One key issue raised by image classification is how to efficiently use geometric information. While the first works were building on the pure bag-of-words model e.g. [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF], which consists of pooling the visual features without using their spatial coordinates in any way, it has been shown later (e.g. by [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF]) that performance can be significantly improved by encoding separately a set of multiple (possibly overlapping) regions, which constitutes a first step toward the use of geometry. Using fixed regions (usually image quad-trees) is obviously limited as the corresponding implicit segmentations of the image is not adapted to the image's content. Several recent works such as [START_REF] Krapac | Modeling spatial layout with Fisher vectors for image categorization[END_REF], [START_REF] Krapac | Learning tree-structured descriptor quantizers for image categorization[END_REF] have introduced more flexibility by adapting the shape/position of the regions, but the layout was still supposed to be fixed, for a given category.

Observing that images within a category might have very different layouts (i.e. spatial organization), it has been shown that categories can be efficiently represented by a set of distinctive regions called parts or fragments [START_REF] Vidal-Naquet | Object recognition with informative features and linear classification[END_REF], [START_REF] Maji | Part discovery from partial correspondence[END_REF], [START_REF] Juneja | Blocks that shout: Distinctive parts for scene classification[END_REF], [START_REF] Sharma | Expanded parts model for human attribute and action recognition in still images[END_REF]. For example, if 'car' images can be recognized because of the joint presence of 'wheel', 'road' or 'window'-like parts, the position of these regions can be any as long as they are in the image. This idea of introducing some invariance (or alignment) with respect to the position of the parts have been used [START_REF] Felzenszwalb | Object detection with discriminatively trained part-based models[END_REF]. However, in the case of image classification the relative position of the parts is much less constrained than in the case of object detection. The motivation of our work is precisely to propose a new way to describe images by a set of parts that are aligned across images by construction, without using strong geometric constraints between them. This is achieved by proposing a new model for categories, which states that (i) a category is defined by a set of K parts (ii) these parts are distinctive in the sense that they occur more frequently in the image of the category than in those from other categories (iii) the presence of regions visually similar to the model's part is expected in the image category. These constraints are implemented into an objective function which is optimized during learning. The objective function relies on a match function which links model's parts with image regions. Training can be achieved from a set of images describing the category to be recognized, without having to provide any extra annotations. During training, a part classifier is learned simultaneously with the matching of parts and image regions. In a second time, these classifiers can be used to build a visual descriptor of images, also called image signatures: we introduce in this paper the fisher-on-part descriptor, consisting in aligning the model on the image and in computing the Fisher vectors of the image regions matched with model parts.

To summarize, the motivation of this paper is to introduce a new framework allowing to automatically discover, learn and align distinctive parts representative of a category, as well as to encode images into a descriptor containing the Fisher vectors of image regions matched with category's parts. The proposed approach is validated on two datasets for which state-of-theart performance is obtained. The rest of the paper is organized as follows. Related work is presented in section II. Section III provides details on the proposed system that learns, aligns, and encodes distinctive parts. Finally, the experimental validation is given Section IV, before concluding the paper.

II. RELATED WORK

Image classification has been vastly studied in the recent computer vision literature (e.g. see the abundant literature related to the Pascal VOC challenge [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2012 Results[END_REF]). Most of the modern approaches build on the bag-of-word model [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF], following a 4 step pipeline: 1) extraction of local image features, 2) encoding of local image descriptors, 3) pooling of encoded descriptors into a global image descriptor, 4) training and classification of pooled image descriptors for the purpose of object recognition. Several studies evaluate the performance of the first step of the pipeline, namely the low level features e.g. gradient, shape, color, and texture descriptors, such as [START_REF] Pinto | Comparing state-of-theart visual features on invariant object recognition tasks[END_REF], while other propose combining different levels (low -midhigh) of information [START_REF] Zheng | Detecting object boundaries using low-, mid-, and high-level information[END_REF]. Regarding the second step (image encoding) Fisher vectors [START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF] are considered as achieving stateof-the-art performance at the moment. The (third) pooling step is also shown to provide improvements, and spatial and feature space pooling techniques have been widely investigated [START_REF] Boureau | Ask the locals: multi-way local pooling for image recognition[END_REF], [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF]. Moreover, [START_REF] Krapac | Modeling spatial layout with Fisher vectors for image categorization[END_REF], [START_REF] Krapac | Learning tree-structured descriptor quantizers for image categorization[END_REF] have recently proposed two different strategies for embedding spatial information into the bag-ofwords framework. Regarding the final step of the pipeline, discriminative classifiers like SVM are widely accepted as the reference in terms of classification performance.

Several authors have shown the importance of adding an intermediate representation [START_REF] Parikh | Recognizing jumbled images: the role of local and global information in image classification[END_REF] -often referred as the midlevel features -for leveraging the performance. We observe three mains trends on mid-level description in the recent literature: hand crafted, learned, and unsupervised features. Hand crafted mid-level features aim at encapsulating information on groups of pixel such as superpixels [START_REF] Tighe | Superparsing: scalable nonparametric image parsing with superpixels[END_REF], [START_REF] Sicre | Superpixel based angular differences as a mid-level image descriptor[END_REF], patches [START_REF] Fernando | Effective use of frequent itemset mining for image classification[END_REF] or segments [START_REF] Carreira | Semantic segmentation with second-order pooling[END_REF]. These descriptors are computed similarly for any given image and do not require any learning. On the other hand, a large variety of learned mid-level features have been proposed. One of the first one was the Deformable Part Model, proposed by [START_REF] Felzenszwalb | Object detection with discriminatively trained part-based models[END_REF]. Improvement have been further achieved by using appearance based clustering and sub-categories [START_REF] Divvala | How important are deformable parts in the deformable parts model?[END_REF] and by enforcing steerability and separability of the features [START_REF] Pirsiavash | Steerable part models[END_REF]. Similarly, semantic attributes [START_REF] Niu | Context aware topic model for scene recognition[END_REF], [START_REF] Su | Improving image classification using semantic attributes[END_REF] have received a lot of interest. Within the learned mid-level features techniques, we observe a large variety in the nature of the learning data. While some feature are based on extra training data such as labeled fragments [START_REF] Liao | Building a dictionary of image fragments[END_REF], sketch tokens [START_REF] Lim | Sketch tokens: A learned midlevel representation for contour and object detection[END_REF] or pre-trained object detectors [START_REF] Endres | Learning collections of part models for object recognition[END_REF], most methods use a standard split of training and testing data to learn the distinctive features, as the structural element patch model [START_REF] Chua | Learning structural element patch models with hierarchical palettes[END_REF] or the blocks that shout [START_REF] Juneja | Blocks that shout: Distinctive parts for scene classification[END_REF]. Finally, regarding unsupervised mid-level features, the work of [START_REF] Singh | Unsupervised discovery of midlevel discriminative patches[END_REF] aims at detecting distinctive patches in an image dataset without any label information.

Our work aims at learning distinctive parts without extra annotations. Therefore, closely related work includes the Deformable Part Model (DPM) [START_REF] Felzenszwalb | Object detection with discriminatively trained part-based models[END_REF]. The DPM models categories by using a mixture of parts and classify image regions as object vs non object regions. Classifiers are applied to a representation in which the parts are aligned, by shifting the parts with respect to the root filter. However, for image classification, the variability part positions as well as the variation of appearance within a category makes the problem different.

Our work also bears similarities with [START_REF] Vidal-Naquet | Object recognition with informative features and linear classification[END_REF], which tries to discover the fragments that maximize the mutual information between the category and the presence of the fragment in the image. However, [START_REF] Vidal-Naquet | Object recognition with informative features and linear classification[END_REF] suffers from that (i) contrarily to [START_REF] Felzenszwalb | Object detection with discriminatively trained part-based models[END_REF], part are just image patches and not discriminative classifiers (ii) the decision is made by verifying the presence of the fragments in the image, instead of training a classifier taking fragment descriptors as input. Our approach takes the advantages of both approaches without having their drawbacks.

More recently, [START_REF] Maji | Part discovery from partial correspondence[END_REF] proposes a learning framework for the automatic discovery of image's parts, assuming that partial correspondence between instances of a category are available. These partial correspondences allow the training of part detectors, used in a first time to extract candidates regions. While we share the same motivations, our approach does not require any supervision. In addition, it is worth mentioning [START_REF] Juneja | Blocks that shout: Distinctive parts for scene classification[END_REF] and [START_REF] Sharma | Expanded parts model for human attribute and action recognition in still images[END_REF] which both propose algorithms for learning parts that are good representatives of a given category. Our work follows the same objectives, without the localization constraints imposed by [START_REF] Sharma | Expanded parts model for human attribute and action recognition in still images[END_REF] and the large computation requirement and unoptimized encoding of [START_REF] Juneja | Blocks that shout: Distinctive parts for scene classification[END_REF].

This work finally shows the importance of mid-level information and justifies its use to improve recognition capabilities.

III. PROPOSED METHOD

As explained in the introduction, the proposed method aims at automatically discovering model parts and aligning them with images regions, as well building a description of images based on the so-aligned regions. This section first presents the category model and its associated cost function, which is to be optimized during learning. Secondly, we explain how the parameters of the model can be learned using an iterative framework inspired from the softassign algorithm. Then, more details are given on the algorithm initialization step. Finally, we explain how image signatures can be computed using the learnt model.

A. Category model and objective function

Let us first introduce some notations. We assume having a set of images belonging to the category to be modeled, considered as positive training images and denoted as I + . |I + | represents the number of positive images. In the same way, I -is the set of (negative) images belonging to other categories. The whole training set is denoted as I = I + I - and contains |I| images. From each image I ∈ I, we extract a dense random set of image regions denoted as R I . Each region r is represented by its signatures x r , which is, in practice, the bag-of-word representation of the region. The model of the category includes a set of parts denoted as P. The number of parts, K = |P|, is fixed. In the following, p ∈ P denotes one of these parts.

The model relies on two assumptions: first, it is expected that each part of the model is present in each positive image. Second, parts should be representatives of the category, which means that they should occur more frequently in positive images than in negative ones.

We implement the first constraint by introducing the match function m(r, p) associating model parts and image regions, and by imposing that ∀I ∈ I + and ∀p ∈ P, r∈I m(r, p) = 1. The match function is defined as:

m(r, p) = 1 if region r is assigned to part model p 0 otherwise (1)
In practice, the match function can be seen as a binary matrix with one row per part and one column per image region. We add another constraint ensuring that an image region can be assigned to at most one part, which is written as: ∀I ∈ I + , ∀r ∈ I, p∈P m(r, p) ≤ 1.

Regarding the second assumption, which states that regions should be discriminative, one way to achieve this would be to measure to which extent each part can be matched with regions from the negative set, and promote those occurring more on positive images. However, such process would be very costly. Therefore, as suggested by [START_REF] Juneja | Blocks that shout: Distinctive parts for scene classification[END_REF], we use the LDA technique of [START_REF] Hariharan | Discriminative decorrelation for clustering and classification[END_REF], which consists in learning once and for all a universal model of negative patches. In practice, the parameter vector w of a part classifier, corresponding to the part p, is defined simply as:

w(p, m) = Σ -1 r∈I,∀I∈I + m(r, p) × x r |r ∈ I, ∀I ∈ I + | - r∈I,∀I∈I x r |r ∈ I, ∀I ∈ I|
(2) where Σ is the covariance matrix obtained by taking the whole set of regions from both positive and negative images. Consequently, the part models w(p, m) are fully defined once the match function is defined. In addition, the similarity between a region r and a part p of the model can by computed as

w T (p, m) × x r .
The model is thus fully defined by giving the match function m(r, p). Following the afore mentioned constraints, we define the optimal match function, denoted as m, as the one maximizing:

Learning this model therefore in the (combinatoric) optimization of Eq. (3). Finding the global optimum is not computationally feasible, nevertheless we propose to adapt the point matching algorithm of [START_REF] Gold | New algorithms for 2d and 3d point matching:: pose estimation and correspondence[END_REF] to obtain an approximate solution, as explained in the following section. This algorithm was first introduced to solves simultaneously the correspondence problem as well as the pose estimation of 3D and 2D data. In [START_REF] Gold | New algorithms for 2d and 3d point matching:: pose estimation and correspondence[END_REF], two sets of points X j and Y k are related by a geometric transformation. Both sets can contain outliers. The match matrix m jk is defined as the correspondence matrix such that m jk = 1 if point X j corresponds to point Y k and 0 otherwise. The problem is further presented as finding the pose (i.e. the geometric transformation) and the corresponding match matrix m jk that best relates the two sets of points. These two problems are finally solved simultaneously using an iterative process aiming at minimizing an energy function.

B. Learning the match function using softassign

Our main goal is now to efficiently find a good (suboptimal) solution of the objective function given by Eq. ( 3).

If we ignore, for the moment, the inequality constraint (last constraint of Eq. 3), then the match matrix m can be seen a permutation matrix. We use the deterministic annealing method of [START_REF] Geiger | Parallel and deterministic algorithms from mrfs: Surface reconstruction[END_REF] to turn our combinatoric problem into a continuous one, making the optimization simpler and more efficient. The key idea is to minimize a sequence of objective functions controlled by a parameter β representing the inverse temperature of the system. By increasing the parameter, the objective functions leans towards the discrete function.

The constraints are then relaxed from a permutation matrix constraints to doubly stochastic matrix constraints, meaning that every row and column of the matrix should sum up to 1 (see [START_REF] Gold | New algorithms for 2d and 3d point matching:: pose estimation and correspondence[END_REF] for more explanations). Therefore, the computation of the match function can be achieved iteratively using the softmax formulation:

∀I ∈ I + , ∀r ∈ I, m(r, p) = exp(β × w T (p, m * ) × x r ) r∈I exp(β × w T (p, m * ) × x r ) (4)
Where w(p, m * ) T × x r is the score function relating the similarity between the part p and the region r of the image I, using the match function m * computed at the previous iteration. Such a formulation does produce values in the interval [0, 1], which is expected. Furthermore, when β → ∞, there will be one region per image for which m(r, p) = 1, while for the other ones m(r, p) = 0, therefore satisfying the first constraint.

In practice, we experimentally observed that the previous formulation tends to favor parts converging to the same 'mean part' for small values of β. Therefore, we utilized the following formulation, which leads to better performance as it encourages sparser representations. ∀I ∈ I + and ∀r ∈ I,

m † (r, p) = exp β (w T (p, m * ) × x r ) -max ∀r∈I (w T (p, m * ) × x r ) (5)
In addition, the match matrix m has to satisfy the doubly stochastic constraints. This can be achieved by using Sinkhorn (see more details in [START_REF] Gold | New algorithms for 2d and 3d point matching:: pose estimation and correspondence[END_REF]), by iteratively normalizing rows and columns, see Algorithm 1.

Up to this point, we ignored the inequality constraint stating that ∀I ∈ I + and ∀r ∈ I, p∈P m(r, p) ≤ 1. We address it by turning the inequality constraint into an equality constraint by adding a slack variable [START_REF]Linear programming[END_REF], which can be seen as an additional part (the K + 1-th part of the model) denoted as p s , with the specificity that this extra part can be matched with several image regions (contrarily to regular parts). Most image regions do not match any part of the model and are therefore matched with this slack part. The constraint becomes: ∀I ∈ I + and ∀r ∈ I, p∈P {ps} m(r, p) = 1. This constraint is then satisfied by doing a column normalization of m, which is to say that ∀I ∈ I + and ∀r ∈ I, m(r, p) = m † (r, p)

∀p∈P {ps} m † (r, p) (6)
Please note that at the initial values of m † (r, p s ) are arbitrarily set to 1/K. The resulting algorithm is Algorithm 1.

As the match function m is refined iteratively, initial values of m are required at the beginning. The convergence of the algorithm is shown to be better if parts are initialized to some discriminative regions. To select distinctive initial regions, we first extract the signatures x r of the regions sampled from positive training images. These signatures are then clustered, using K-means. Here again we use the LDA acceleration of [START_REF] Hariharan | Discriminative decorrelation for clustering and classification[END_REF], which means that for each cluster, the classifier w is defined as w = Σ -1 (x -µ 0 ) where x is the average of the signatures within the cluster and µ 0 and Σ the overall mean and covariance matrix.

These classifiers are further applied on the regions of the training images. Maximum responses to the classifiers are then selected per image and averaged over positive and negative subsets, giving us the two scores s + and s -, for a given cluster j, defined as:

s + j = 1 |I + | r * ∈I + w T j x r * s - j = 1 |I -| r * ∈I -w T j x r * (7)
Where ∀I ∈ I + , r * = arg max r∈I (w T j x r ). Then, we denote as C p the K clusters having the largest s + j /s - j ratios, which are selected as initial regions. These initial regions are further used to compute the initial part classifier w(p, m 0 ) as : w(p) ← Σ -1 (C p -µ 0 ), used to compute the initial match matrix m 0 (r, p).

D. Computing image signatures

Once the model is trained, images can be represented by their signatures. Let us denote as I an image to be encoded. We first extract a set of regions r ∈ I and compute their corresponding descriptors x r . We can measure to which extend each region is similar to one of the model parts by using the scoring function defined previously by Eq. ( 2) as w T (p, m) × x r , where m is the match function learned during training.

Then, we want to pool the per part similarities to produce a signature of the image. We propose two different strategies: the bag-of-parts inspired from [START_REF] Juneja | Blocks that shout: Distinctive parts for scene classification[END_REF] and a novel approach so-called the fisher-on-parts.

Encoding images with bag-of-parts:

To compute the bag-of-parts (BOP), the per parts scores are computed for each extracted region on an image. The signature of the image is then given by aggregating, for each part of the model, the average and the maximum of the region scores. Namely, if p j is one of the K parts of our model, the signature of the image I will be represented by the two following components:

r∈I w T (p j , m) × x r |r ∈ I t | and max r∈It w T (p j , m) × x r (8)
When the problem is a multi-class problem, we do the same for each class and aggregate the results. Therefore, we obtain a 2 × K × C-dimensional descriptor, where C is the number of classes. Encoding images with Fisher-on-parts: Fisher-on-parts (FOP) aims at encoding together the maximum response of each parts in an image I t . As in BOP, scores are computed for each region. Then, instead of aggregating average and maximum scores as for the BOP, the maximum scoring region r * for the part p is selected, as follows:

Initialization: w(p) ← Σ -1 (C p -µ 0 ) while β ≤ β f do while m † not
r * = arg max r∈I w T (p, m) × x r (9)
Finally, a Fisher vector is computed on the area of the image covered by the K selected regions r * . Therefore, the final FOP descriptors is 2 × G × D × C-dimensional vector, where G is the number of Gaussian in the mixture model of the Fisher vector, D is the dimensionality of SIFT descriptors and C the number of categories.

IV. EXPERIMENTS

A. Datasets

Three classification datasets are utilized to experimentally validate the proposed approach. The Willow dataset [START_REF] Delaitre | Recognizing human actions in still images: a study of bag-of-features and part-based representations[END_REF] aims at classifying 7 human actions in still images. The Boats Datasets goal is to classify several types of boats, while the MIT 67 dataset [START_REF] Quattoni | Recognizing indoor scenes[END_REF] contains images of 67 types of scenes, to be recognized. [START_REF] Delaitre | Recognizing human actions in still images: a study of bag-of-features and part-based representations[END_REF] is a database for action classification on unconstrained consumer images from the Internet. The dataset contains 911 images split into 7 classes of common human actions, e.g. 'running', 'riding cycle' etc. There are at least 108 images per actions, with 70 images used as training and the rest as testing images. We note that the dataset also offers bounding boxes fitted on humans performing the actions. In our case, we perform the test without using those bounding boxes, as we want to detect parts automatically without any prior knowledge on the scenes.

The Willow actions dataset

The MIT 67 scenes dataset [START_REF] Quattoni | Recognizing indoor scenes[END_REF] is composed of 67 categories of indoor scenes. These categories include stores (e.g. bakery, toy store), home (e.g. kitchen, bedroom), public spaces (e.g. library, subway), leisure (e.g. restaurant, concert hall), and work (e.g. hospital, TV studio). Some scenes can be best characterized by their global layout (corridor), or by the objects they contain (bookshop). Each category has around 80 images for training and 20 for testing.

The RECONSURVE Boats Classification Dataset 1 is composed of 2877 images divided in 5 categories of boats (e.g. boating, fishing, merchant ship, tanker, passenger).

B. Classification pipeline

Extraction of initial regions: for each image, a set of initial regions is generated by randomly sampling 2,000 regions over the entire image.

Regions descriptors: to obtain region descriptors, dense SIFT points are first extracted on each image using VLFEAT [START_REF] Vevaldi | Vlfeat an open and portable library of computer vision algorithms[END_REF] (we use the default 4 scales and sample points every 3 pixels). The SIFT points are further square-rooted to get rootSIFT and the feature dimension is reduced to 80 using PCA [START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF]. Then each region is characterized using a 1,000dimensional bag-of-word.

Parameters of the learning algorithm: regarding the learning algorithm, we empirically set the parameters following the choices of [START_REF] Gold | New algorithms for 2d and 3d point matching:: pose estimation and correspondence[END_REF]: β = 0.41, β r = 1.245, β f = 1.2, I 0 = 4, I 1 = 30 (see Algorithm 1 for the definition of these parameters). The algorithm iterates over the estimation of m until the sum over m of the absolute difference between two iterations is smaller than ǫ = 0.005.

Baseline pipeline: Our approach is compared to the state-of-the-art pipeline [START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF]. Bag-of-words and Fisher vectors are computed on the root SIFT of the full image. Fisher vectors are also computed using the two first layers (i.e. 1×1 and 2×2 segments) of the spatial pyramid.

C. Results

In this section, we first comment on the quantitative results then show some qualitative results (visualization of learned parts) in Figures 1 and2. In the following, the performance on the three datasets are measured using the mean Average Precision (MAP). First, we evaluate the impact of the initialization step in the part-learning process, on the Willow dataset. The objective is to measure the contribution of the initialization process described in section III-C over a simple random initialization of the parts. If we randomly initialize the match function we observe a mAP of 46.0% (with the bag-of-parts encoding). Adding the clustering-based initialization improves the mAP by 5% (51.0%). In addition, to prove the usefulness of the proposed algorithm, we evaluated the performance obtained by initializing the match function with the clustering-based approach and without doing the optimization of m. The performance drops to 46.7%, proving that the proposed algorithm improves significantly over discriminative parts learned by clustering.

The bag-of-parts and Fisher-on-parts are then evaluated on the three datasets (see Table I and Table II). For Willow actions, the performance of the two baseline algorithms (bagof-words and Fisher vectors) are respectively of 50.0% and 1 can be downloaded from https://jurie.users.greyc.fr Method MAP bag-of-words [START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF] 0.345 Fisher vectors [START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF] 0.550 bag-of-parts of [START_REF] Juneja | Blocks that shout: Distinctive parts for scene classification[END_REF] 0.373 our bag-of-parts 0.401 Fisher-on-parts 0.545 Fisher-on-parts based combination 0.600 58.1%. One can notes that the bag-of-parts slightly outperforms the standard bag-of-word. More interestingly, the propose Fisher-on-parts representation largely outperforms Fisher vectors by more than 3%. Please note that the proposed approach does not use any extra annotations, contrarily to most of the proposed approaches (e.g. [START_REF] Sharma | Expanded parts model for human attribute and action recognition in still images[END_REF] bounding boxes giving). It explains why we do not provide any comparisons with these methods, as they would be meaningless. The Boats dataset also shows improvement on both the bag-of-parts and the fisher-on-parts. Furthermore, we observe the best performances for the bag-of-parts with 21% and 6% MAP increase over BOW and Fisher vectors respectively. Concerning MIT 67, we first observe that our bag-of-parts encoding offers better performances than the bag-of-word model as well as the bagof-parts proposed in [START_REF] Juneja | Blocks that shout: Distinctive parts for scene classification[END_REF]. We also notice that our Fisher-onparts improves on the two previous methods. However, we do not obtain better performance than the Fisher vectors extracted on the full image. We believe that this result is due to the fact that the MIT 67 requires a lot of context information to recognize scenes, while our Fisher-on-parts encoding acts as a pooling system that encapsulates most information on the foreground. Combining Fisher-on-parts with Fisher vectors on the whole image (with SPM) gives a MAP of 60.0%, which is significantly better than any other approach.

These experiments show that our descriptors, based on distinctive parts learning, are capable of incorporating midlevel information that can be combined with the full image representation to obtain richer representations.

V. CONCLUSIONS

In this paper, we propose a new algorithm for image recognition by modeling categories as set of distinctive parts that are discovered automatically and aligned across images, while learning their visual model. The parts that are discovered are free of any appearance constraint and allow the distinction between the categories to be recognized. We show how to use the softassign matching algorithm, to simultaneously learn the part models and assign image regions to model's parts, starting from an initial set of randomly extracted image regions. We validated the proposed algorithm on three different datasets on which state-of-the-art performances are obtained.

Fig. 1 .

 1 Fig. 1. On this figure, 2 images from the 'riding cycle' class of the Willow actions dataset are represented with four learned parts

  m(r, p) × w T (p, m) × x r s.t. ∀I ∈ I + , ∀p ∈ P, r∈I m(r, p) = 1 s.t. ∀I ∈ I + , ∀r ∈ I, p∈P m(r, p) ≤ 1

Fig. 2 .

 2 Fig. 2. This figure shows the highest scoring regions for a set of parts learned for the riding horse action. Each row correspond to a part

  converged or # of iteration ≤ I 0 do update match matrix by softassign Compute m † (r, p), based on Eq. 5 while m † not converged or # of iteration ≤ I 1 Algorithm for learning the mach function.

	do
	∀I ∈ I +
	Update m by normalizing rows
	m † 1 (r, p) ← Update m by normalizing columns m † 0 (r,p) r∈I m † 0 (r,p)
	m † 0 (r, p) ←	m † 1 (r,p) p∈P {ps } m † 1 (r,p)
	end
	update parts using LDA Compute w(p, m † 0 ), based on Eq. 2. end
	β ← β r β end
	Algorithm 1:

TABLE I .

 I RESULTS ON WILLOW AND BOATS DATASET. SEE TEXT FOR DETAILS.

	Method	Willow (MAP)	Boats (MAP)
	bag-of-words [36]	0.500	0.673
	Fisher vectors [36]	0.581	0.827
	bag-of-parts	0.510	0.888
	Fisher-on-parts	0.614	0.837

TABLE II

 II

	.	RESULTS ON MIT 67 SCENES DATASET. SEE TEXT FOR
		DETAILS.


Sebastien Razakarivony
email: sebastien.razakarivony@sagem.com

Frédéric Jurie
email: frederic.jurie@unicaen.fr

Discriminative Autoencoders for Small Targets Detection

This paper introduces the new concept of discriminative autoencoders. In contrast with the standard autoencoders -which are artificial neural networks used to learn compressed representation for a set of datadiscriminative autoencoders aim at learning low-dimensional discriminant encodings using two classes of data (denoted such as the positive and the negative classes). More precisely, the discriminative autoencoders build a latent space (manifold) under the constraint that the positive data should be better reconstructed than the negative data. It can therefore be seen as a generative model of the discriminative data and hence can be used favorably in classification tasks. This new representation is validated on a target detection task, on which the discriminative autoencoders not only give better results than the standard autoencoders but are also competitive when compared to standard classifiers such as the Support Vector Machine.

I. INTRODUCTION

This paper addresses the problem of the detection of small targets in aerial images, a task commonly referred as Automatic Target Recognition (ATR). Typical images illustrating this task can be seen from Fig. 1. This is an old -yet unsolvedcomputer vision task. This task is complex and challenging not only because of the smallness of objects but also because of illumination and color changes, pose differences or occlusions. However, this task is important and involved in many applications such as visual surveillance, safety or protection.

Despite the fact that object detection has received a lot of attention during the last 5 years (e.g. [START_REF] Everingham | The pascal voc challenge[END_REF], [START_REF] Carbonetto | Learning to recognize objects with little supervision[END_REF]), our problem differs from these recent works for several reasons. First, representing small targets is difficult: indeed, the afore mentioned recent approaches rely on the use of accurate descriptors capturing fine discriminating details of the objects (e.g. the Dalal and Triggs's HOG descriptor for pedestrian detection [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF]) and/or on the use of part-based models [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF]. These descriptors and models can hardly be used for as small as e.g. 20 pixel-wide objects. Secondly, it is usually difficult to obtain large enough training sets as it is expensive to collect and annotate aerial images. Thirdly, image backgrounds (i.e. the pixels surrounding the targets) are usually not correlated with the objects themselves: vehicles can be on a roads, fields etc. Finally, in some cases, vehicles can even be camouflaged and cannot be distinguished easily from the background. Interestingly, while target's appearance usually belongs to a high dimensional spacee.g. a 20×20 pixel targets lies in a 400-d space -only a few parameters (often called the latent variables) are necessary to explain their appearances. Such parameters can be, for example, the 3D pose or the illumination. Furthermore, it has been shown in the past that manifolds are good candidates to represent small size objects for which distinct features can hardly be extracted ( [START_REF] Pentland | Viewbased and modular eigenspaces for face recognition[END_REF], [START_REF] Zhang | Parametric manifold of an object under different viewing directions[END_REF], [START_REF] Feraud | A fast and accurate face detector based on neural networks[END_REF]). Indeed, they allow to represent the highdimensional manifolds containing the data by low-dimensional representational space. Supporting this assumption, the work of Zhang [START_REF] Zhang | Parametric manifold of an object under different viewing directions[END_REF] shows that images of 3D objects seen from different view-points can be represented as points on a lowdimensional manifold. Different works used manifold learning as a generative model, such as the famous work of Pentland, based on linear manifolds obtained by Principal Component Analysis [START_REF] Pentland | Viewbased and modular eigenspaces for face recognition[END_REF], or the work of Feraud et al. [START_REF] Feraud | A fast and accurate face detector based on neural networks[END_REF] based on nonlinear manifold learning.

However, one strong limitation of these manifold-based approaches is that, while they accurately model object's appearance, they do not focus on the discriminative information, contrarily to state-of-the-art approaches using boosting [START_REF] Viola | Detecting pedestrians using patterns of motion and appearance[END_REF], Support Vector Machines (SVM) [START_REF] Cortes | Support-vector networks[END_REF] or neural networks (NN) [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF]. Once the manifold is learned, hence constituting a generative model of the data, the discriminant information is irremediably lost. This is what motivates this paper. Indeed, this paper proposes a new type of autoencoders denoted as discriminative autoencoders which uses an autoencoder to build a generative model of the discriminative information. In contrast with the standard autoencoders, our discriminative autoencoders learn a manifold which is by construction good at reconstructing the targets while the backgrounds are poorly reconstructed. It opens the door to very simple classification frameworks in which the reconstruction error can be used as a natural, simple and efficient way to classify image windows in a sliding window framework.

Experiments on a dataset including vehicles in aerial images (the VeDAI dataset) show that the proposed approach is not only better than the standard autoencoders but also performs better than discriminative classifiers such as the SVM classifiers.

The rest of the paper is as follows: we first introduce the related works in Section II, we present the discriminative autoencoders in Section III, and, finally, give the experimental validation of the proposed approach in Section IV.

II. RELATED WORKS

Even if target detection has a long history in the computer vision literature, the recent literature on object detection focuses mainly on the detection of large objects in consumer images. Most of the techniques are based on the sliding windows framework, combining descriptors, such as Histogram of Oriented Gradient [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] or Haar Wavelets [START_REF] Mallat | A theory for multiresolution signal decomposition -the wavelet representation[END_REF], with powerful discriminative classifier, such as boosting [START_REF] Viola | Detecting pedestrians using patterns of motion and appearance[END_REF] or SVM [START_REF] Cortes | Support-vector networks[END_REF]. Many improvements have been proposed to enhance these techniques e.g. new kernels [START_REF] Vedaldi | Sparse kernel approximations for efficient classification and detection[END_REF] or part-based models [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF].

More directly related to our problem, some approaches have been specifically designed for the detection of vehicles. In [START_REF] Zhao | Car detection in low resolution aerial images[END_REF], Zhao and Nevatia pose car detection as a 3D object recognition problem, to account for the variation in viewpoint and shadow. Their experiments show promising results on challenging images, but the cars that are not on roads do not seem to be well detected. Eikvil et al. [START_REF] Eikvil | Classification-based vehicle detection in high-resolution satellite images[END_REF] use several different features combined with Linear Discriminant Analysis [START_REF] Fisher | The use of multiple measurements in taxonomic problems[END_REF]. A segmentation step, followed by a two-stages classifier is used. Their work relies on the availability of multispectral and panchromatic images, and on the knowledge of the road network. Despite the authors' promising results, the vehicles can be detected only because they are supposed to be on roads. In [START_REF] Stilla | Airborne monitoring of vehicle activity in urban areas[END_REF], Stilla et al. propose several algorithms adapted to the different sensors they use (color, thermal infrared, radar). They also build local and global features from a 3D model, and use the context as well. [START_REF] Kembhavi | Vehicle detection using partial least squares[END_REF] reports interesting vehicle detection results, obtained by using large and rich sets of application specific image descriptors. The features are based on several geometric and color attributes representative of the vehicles, and perform a Partial Least Square analysis on them. They compare their approach to HOG-SVM-like classifiers [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF], obtaining similar performance. Other works address the detection of small vehicles such as [START_REF] Eikvil | Classification-based vehicle detection in high-resolution satellite images[END_REF], [START_REF] Zheng | An artificial immune approach for vehicle detection from high resolution space imagery[END_REF]. However all of them assume that the vehicles are located on roads, to make the detection easier, and cannot be used in our context. Finally, it worths noting that none of their experiments can be reproduced Fig. 2. Manifolds: vectors of the original Euclidean space H belong to a manifold spanned by the subspace E. f is a mapping function, giving the correspondence between a point in the manifold M in the original space and its projection in the subspace. f -1 is its inverse, going from E to M . because neither the protocols nor the datasets have been made publicly available.

There are very few papers specifically addressing the detection of small objects. These papers are often based on the detection of salient regions. In this case, the objects to be detected are defined as the regions of the image which do not have the same statistics as the background e.g. [START_REF] Rutishauser | Is bottomup attention useful for object recognition?[END_REF], [START_REF] Seo | Visual saliency for automatic target detection, boundary detection, and image quality assessment[END_REF]. Among the rare papers which tried to model small targets explicitly, we can mention the work of [START_REF] Munder | An experiment study on pedestrian classification[END_REF], which -in addition to introducing a new dataset of 36 × 18 pixels pedestrian images -has shown that good performance can be obtained by combining standard features such as Haar wavelets or HOG features with SVM/boosting classifiers [START_REF] Enzweiler | Monocular pedestrian detection: Survey and experiments[END_REF].

Manifolds have been successfully used to model object's appearance. A manifold is a subspace embedded in a higher dimension space which can be locally approximated by an Euclidean subspace, denoted as the latent space. The geodesic distances, which are the shortest paths between two points inside a manifold, are locally preserved in the latent space. Fig. 2 gives an illustration by showing the relationship between the manifold (E) and the Euclidean space (H). A manifold can be learned through different ways. The simplest methods are the linear ones e.g. Linear Discriminant Analysis [START_REF] Fisher | The use of multiple measurements in taxonomic problems[END_REF], or the simple Principal Components Analysis. Regarding non linear methods, some of them are based on the conservation of geodesic distances such as Isomap [START_REF] Tenenbaum | A Global Geometric Framework for Nonlinear Dimensionality Reduction[END_REF]. Local Linear Embedding [START_REF] Saul | Think globally, fit locally: unsupervised learning of low dimensional manifolds[END_REF] and its variants learn linear local approximations of the manifold. Other approaches learn the manifold in a global way, such as the Maximum Variant Unfolding [START_REF] Weinberger | Unsupervised learning of image manifolds by semidefinite programming[END_REF], or autoencoders [START_REF] Kramer | Nonlinear principal component analysis using autoassociative neural networks[END_REF]. It worths pointing out that most of these algorithms have been designed to visualize high-dimensional data in 2D, and thus only give the mapping f (see figure 2), but not its inverse (required by our approach for the detection task, as explained later). Interestingly, Principal Components Analysis (and its variants) and autoencoders can be used to compute both f and f -1 . Manifold learning has already been used by several authors to address detection tasks. In [START_REF] Pentland | Viewbased and modular eigenspaces for face recognition[END_REF], Pentland introduced the well known eigenfaces, using Principal Component Analysis to build linear face manifolds used for face detection. It has also been applied later to hand detection in [START_REF] Moghaddam | Probabilistic visual learning for object representation[END_REF]. In the same spirit, [START_REF] Carvalho | IJCNN[END_REF] uses PCA for object detection, by modeling the background and the objects as linear manifolds. Interesting results are reported on good quality car and pedestrian images, Fig. 3. Illustration of the concept of distance to the manifold. Let Xs be a vector and X ′ s = f -1 •f (Xs) is its projection on the latent space. ||X ′ s -Xs|| is referred as the distance to the manifold. f goes from H to E, and f -1 goes from E to M -which is included in H.

for high dimensional manifolds. In [START_REF] Feraud | A fast and accurate face detector based on neural networks[END_REF], the authors use autoencoders to build face manifolds for face detection, but the false alarm rate is high, probably because the background model can not be learned with such a model. In [START_REF] Razakarivony | Small target detection combining foreground and background manifolds[END_REF], the authors counter this effect by using a distinct background model.

Our approach builds on these recent works by using one of the best current image representations (HOG) combined with a manifold learning approach. The contribution of the paper lies in the new framework allowing to learn discriminative autoencoders. As far as we know, this is the first time such a model is proposed.

III. DISCRIMINATIVE AUTOENCODER

Before presenting the proposed discriminative autoencoders, we start by explaining how manifolds can be used as classifiers, and how to learn manifolds with autoencoders.

A. Manifold as a generative model

Let H denote the input space and x ∈ H a visual signature (also called visual feature) extracted from an image. We remind that building a Riemannian manifold M representative of the visual signatures is equivalent to finding a function f , such as:

∀x ∈ M, ∃!x ∈ R n , x = f (x) (1)
f is called the embedding of M, and is an isometric function.

Obviously, if x lies on the manifold, f -1 • f (x) = x. f -1 • f projects any point of the input space on the manifold M. By denoting P M = f -1 • f , we can define the distance to the manifold by:

D M (x) = ||x -P M (x)|| (2)
where ||x|| represent the Euclidean norm of x. The principle of this projection is illustrated by Fig. 3. This distance can then be used to model a category, as the closer to the manifold a vector is, the more likely it belongs to the category.

B. Autoencoder

Autoencoders are symmetrical neural networks, which learn the identity function under constraints. A typical simple autoencoder is presented Fig. 4, but more complex architectures can be used. One neuron from the layer i is connected to all the neurons of layer i + 1, and only to these neurons. We denote as W ij the matrix of weights connecting the layer i and the layer j. The layers are numbered from 0 (input) to N (middle layer) and then back from N (middle layer) to 0 (output), as shown Fig. 4. As the network is symmetric, dimension(W ji ) = dimension(W T ij ). Each layer j has an output r(x), fully defined by the layer input x and the weights matrix:

r(x) = h(W ij x) (3)
h is called the activation function, and is typically the sigmoid function. When the activation function h is linear for all the layers, the autoencoder computes a PCA [START_REF] Kramer | Nonlinear principal component analysis using autoassociative neural networks[END_REF]. Contrary to this, using non-linear h functions allow the network to approximate any function [START_REF] Cybenko | Approximation by superpositions of a sigmoidal function[END_REF].

Let us denote χ the set of training vectors x. The standard autoencoder minimizes the following loss function [START_REF] Kramer | Nonlinear principal component analysis using autoassociative neural networks[END_REF]:

L(χ) = x∈χ ||x -x|| 2 , (4)
hence minimizing the reconstruction error. x is the reconstruction of x given by the autoencoder. The loss is usually minimized using a stochastic gradient descend, within a backpropagation framework [START_REF] Rumelhart | Learning internal representations by error propagation[END_REF]. f and its inverse are therefore learned simultaneously. The latent space E is available as the output of the middle layer. More efficient convergence rates can be achieved using Restricted Boltzmann Machine [START_REF] Ackley | A learning algorithm for boltzmann machines[END_REF] and Contrastive Divergence [START_REF] Hinton | Training products of experts by minimizing contrastive divergence[END_REF]. The interested reader can see [START_REF] Hinton | Reducing the Dimensionality of Data with Neural Networks[END_REF] for further details.

In the context of manifold learning, the network is usually used to learn f and f only, providing an embedding of data [START_REF] Hinton | Reducing the Dimensionality of Data with Neural Networks[END_REF]. In contrast, we learn the full network, which gives the projection on the manifold P M (x) we are looking for. The distance from the class (which can be used as a classification score) can be computed as simply as in Eq. (2).

C. Discriminative autoencoder

In contrast with standard autoencoders, we introduce the concept of discriminative autoencoders, which use data from two classes (denoted in the following as χ + , the set of positive training vectors, and χ -the set of negative ones) and learn a manifold which is good at reconstructing the data of the positive class while ensuring that those of the negative class are pushed away from the manifold. By doing this, we intend to take advantage of the information carried by negative examples. Let us denotes as t(x) the label of the example x, with t(x) ∈ {-1, 1} and e(x) the distance of that example to the manifold with e(x) = ||x -x||. We substitute the loss function given by Eq. 4 by the following one:

L d (χ + ∪ χ -) = x∈χ + ∪χ - max (0, t(x) • (e(x) -1)) (5)
which is nothing else than the hinge loss function (see Fig. 5 for an illustration), used in many different classification algorithms such as the SVM. In practice, we use the slightly different version of the standard hinge loss, as proposed by [START_REF] Mignon | Pcca: A new approach for distance learning from sparse pairwise constraints[END_REF] the standard one should be L d = x∈χ + ∪χ -max(0, 1-t(x)• e(x)) -more adapted to our problem as the reconstruction errors are all positive. In that sense, our problem is closer to a metric learning task than to a classification task. When the minimum is reached, positive (resp. negative) examples are expected to have a reconstruction error lower (resp. greater) than 1.

To optimize the loss function, we use here again a backpropagation of the error. First we give the equations of the autoencoder, which are:

y = h(W 10 z) and z = k(W 01 x) (6)
As done in [START_REF] Hinton | Reducing the Dimensionality of Data with Neural Networks[END_REF], the activation function k is the identity function, and h is the sigmoid function. To simplify these equations, let us denote u and v as:

u = W 10 z and v = W 01 x ( 7
)
The objective is to estimate the coefficients w ki of W 01 and W 10 by minimizing L(χ + ∪ χ). The optimum values of w ki verify:

∂L ∂w ki = 0 (8)
which can be solved using a stochastic gradient descend. The partial derivatives can be written as:

∂L ∂w ki = ∂L ∂e i • ∂e i ∂y i • ∂y i ∂u i • ∂u i ∂w ki (9)
with:

∂e i ∂y i = -1; ∂y i ∂u i = ∂h(u i ) ∂u i ; ∂u i ∂w ki = z k (10)
Furthermore, in the case of the sigmoid function:

∂h(u i ) ∂u i = y i • (1 -y i ) (11)
Up to here, the derivations are close to the classic backpropagation. Then, by introducing the hinge loss:

∂L ∂e i = e i if t(x) • (e(x) -1) > 0 0 otherwise ( 12
)
we thus obtain the following gradient step:

∆w ki = -ηδ i z k ( 13
)
with δ i = e i ∂h(u i )

∂u i if t(x)
• (e(x) -1) > 0 and 0 otherwise.

For the hidden layer (we give the derivations for only one hidden layer, but this is the same with more hidden layers):

∂L ∂w lk = ∂L ∂z k • ∂z k ∂v l • ∂v l ∂w lk (14)
The two last terms do not change, but the first one becomes:

∂L ∂z k = n e n ∂e n ∂z k if t(x) • (e(x) -1) > 0 (15)
which give us:

∂L ∂z k = n e n ∂(x k -h(u n )) ∂u n • ∂u n ∂z k (16) = - n e n ∂(h(u n )) ∂u n w kn = - n δ(n)w kn (17)
The increment is therefore:

∆w lk = -ηδ k x l (18)
with

δ k = ∂h(v k ) ∂v k n δ(n)w kn if t(x)
• (e(x) -1) > 0 and 0 otherwise. For both increment, η is the learning rate. Different ways exist to optimize it. As it is not the main subject, the reader should see [START_REF] Lecun | Efficient backprop[END_REF] for more information. These equations can be made more robust by adding a margin w to the equation, t(x) • (e(x) -1) > 0, thus becoming t(x) • (e(x) -1) + w > 0. w is chosen by cross validation. Finally, the reconstruction error for a new vector x -which can be used as a classification score -is:

e(x) = ||x -x|| (19)
IV. EXPERIMENTS This section experimentally validates the proposed discriminative autoencoder on the task of small targets detection. We first introduce the dataset used in our experiments, the VeDAI (Vehicle Detection in Aerial Imagery) dataset, and then present our detection pipeline. We finally report the performance of the discriminative autoencoders and compare it with the performances of standard autoencoders and standard discriminative classifiers. We also compare the proposed detector to the Deformable Part Model of [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF]. Fig. 6. 100x100 pixels regions centred on cars, extracted from the VeDAI dataset. Small size, specular reflections, shadows or occlusion make the detection challenging.

A. VeDAI dataset

We did the experimental validation on a dataset built to benchmark small targets detection algorithms, the VeDAI dataset 1 . It contains a total of 1,210 images (of 1024×1024 pixels, 3 color bands) with various backgrounds and vehicles (see illustrative images Fig. 1). These images come from the Utah ARGC website [START_REF] Website | Utah agrc website[END_REF], and more precisely from the 2012 HRO 6 inch orthophotography set. The image resolution is 12.5×12.5cm per pixel. The cars have a size around 20×40 pixels. Their detection is challenging because of occlusions, specular reflections and shadows, as shown by Fig. 6. The intra-class variation is important. We used a 10-fold cross validation process: the 1,210 images are split in 10 folds, each of them containing 134 targets (cars) in 121 different images. During the evaluation, 9 folds are used for training and the last for testing. Each fold is used in turn as the test set.

B. Detection pipeline

Our detection pipeline builds on the standard sliding window framework using manifold learning to score the windows. All the possible rectangular regions of a given aspect ratio are evaluated one by one by our object classifier. This is done in practice by using a multi-scale grid. We used a typical step-size of 8 pixels and a ratio of 2 1 10 between each scales, such as done by [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF]. As the aspect ratio of vehicles can vary a lot depending on the orientation, several distinct classifiers are trained. The aspect ratio clusters are obtained by clustering training image regions. Only four scales were used as the distance to target is the same from one image to another. To improve the efficiency, we adopt a two stage cascade. The first stage is made of 12 linear-SVM classifiers based on HOG features (2 different orientations × 6 different aspect ratios), while the second stage re-scores the detections using 12 discriminative autoencoders (one paired with each SVM classifier). First-stage detectors 1 can be downloaded from https://jurie.users.greyc.fr/ are trained using initial training data while those of the second stage are trained from the hard negative (i.e. the false positive of the first stage with highest scores) of the training images. The number of neurons in the autoencoders (with only one hidden layer) is set by cross validation. During testing, the 12 SVM detectors are run over the entire image and only the windows with a score over -1.0 are kept. Then, as usually with sliding-windows, a non-maximum filtering stage is applied. We use a simple and efficient iterative greedy strategy consisting in keeping only the windows which have the maximum score over a disk (which radius is half the window width). We set the windows so that the selected windows do not overlap by more than 50 percent. Finally, the selected windows are re-scored with a standard or discriminative autoencoder. Our algorithm can virtually use any type of image features as input.

In practice, all the presented experiments are done with HOG.

We also tried to combine the two scores (i.e. the ones of the first-stage SVM classifiers with the ones of the discriminative autoencoders). In this case the final score is computed as:

αS autoencoder (x) + (1 -α)S SV M (x) (20)
α being fixed by cross validation.

C. Results

We measure the performance of the target detector by the mean Average Precision (mAP) over the 10 folds, as well as by the mean detection rate (Recall) at 0.01 false positive per image (FPPI), 0.1 FPPI and 1 FPPI. The mean average precision is computed from an 11 points extrapolation of the precision-recall curve, as done in many detection benchmarks [START_REF] Everingham | The pascal voc challenge[END_REF]. The mean and the standard deviation are computed over the 10 folds. The results are given in Table I. We first observe that the standard autoencoder (using only positive examples) does not give good results on its own. Even when combined with the first-stage SVM, it does not significantly improve the performance of the SVM alone. On the other hand, the discriminative autoencoder performs much better than the standard autoencoder (+38.0 of mAP), but also significantly better than the standard SVM (+9.1 of mAP), even if it uses exactly the same training examples. For the different operating points, the discriminative autoencoder gains +16.3 of recall at 0.1 FPPI, and +6.6 of recall at 1 FPPI compared to the SVM alone. The large standard deviation of 0.01 FPPI makes conclusions not reliable, but the observed gain is of +8.0% on the detection rate. The combination of the score of the discriminative autoencoder and the one of the SVM gives slightly better results than the discriminative autoencoder alone, with a gain of +1.6 of mAP, +1.6 of recall at 1 FPPI and of +2.3 of recall at 0.1 FPPI. Finally, when compared to the Deformable Part Model of [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] (we used the latest release of the author's code), one of the state-of-the-art detector at the moment, the gain is of about 10% of mAP. These results clearly show that not only discriminative autoencoders largely outperform standard autoencoders but also that it significantly outperforms linear SVM or DPM detectors, on this small objects detection task.

V. CONCLUSIONS

This paper introduces the new concept of discriminative autoencoders, which, in addition to optimizing the reconstruction of the positive examples (as standard autoencoders do), push the manifold away from the negative examples. We also show how such autoencoders can be trained, inspired by recent metric learning techniques. In the context of small target detection, where manifold learning is very relevant, we have shown that the discriminative autoencoders perform much better that the traditional autoencoders, and offer a significant gap over other approaches (including the Deformable Part Model) when it is associated with a linear SVM classifier.

Fig. 1 .

 1 Fig. 1. Typical images for automatic target recognition, from the VeDAI Dataset.

Fig. 4 .

 4 Fig. 4. Let H be the input space and E the latent space. It is an illustration of the minimal autoencoder, which is made of 3 layers.

Fig. 5 .

 5 Fig. 5. Hinge Loss. Top: graph of the standard hinge loss. Bottom: the hinge loss used for metric learning.

TABLE I .

 I RESULTS ON THE VEDAI DATASET

	Detector	mAP	Recall @ 0.01 FPPI	Recall @ 0.1 FPPI	Recall @ 1 FPPI
	Deformable Part Model [4]	60.5±4.2	13.4±6.8	31.4±5.8	74.5±4.5
	HOG-SVM (1st stage only)	58.9±3.5	13.2±5.1	30.4±3.9	72.1±4.1
	HOG-SVM followed by Standard Autoencoder	30.0± 3.9	1.5±1.6	6.8 ±1.8	39.5± 4.1
	HOG-SVM combined with Standard Autoencoder	58.8±3.8	12.9±3.5	34.0 ±4.5	71.8±5.4
	HOG-SVM followed by Discriminative Autoencoder	68.0±4.2	21.2±6.9	46.7 ±6.8	78.7±3.4
	HOG-SVM combined with Discriminative Autoencoder	69.6±3.4	20.4 ±6.2	49.0±3.6	80.3±3.1

ACKNOWLEDGMENT

This work was supported by the Agence Nationale de la Recherche et de la Technologie, through the CIFRE sponsorship No 2011/0850 and by SAGEM-SAFRAN group.