Saraos Andrès
email: andres.saraosluna@irisa.fr

Valérie Luna

Bruno Gouranton

Arnaldi

The Perceptive Puppet

Keywords: Teamwork, Virtual Environment, Embodiment, Training

We present a novel mechanism that allows real and virtual humans to dynamically exchange the control of their embodiment in virtual environments. Such a mechanism raises two important issues: the possibility of dynamic embodiment exchanges between real humans and virtual humans and the continuity of actions of the team members after an exchange. To address these issues we introduce a new entity, the Perceptive Puppet that abstracts real and virtual humans into one common entity containing its own knowledge.

INTRODUCTION

In Collaborative Virtual Environments for Training (CVET), a group can learn and practice the completion of a task as a team using all the assets provided by Virtual Reality: low cost and risk-free for the trainees, no need for costly physical equipment, the possibility to repeat the task as many times as necessary and the trainees' progress can be saved and used later on for further analysis [START_REF] Boulanger | Hapto-audio-visual environments for collaborative training of ophthalmic surgery over optical network[END_REF]. Another main asset is the introduction of virtual humans in the team training, as replacements for missing team members and as collaborators working with the trainees. They can act as collaborators that contribute to the completion of the task, teachers that guide and provide contextual help whenever they are needed or even troublemakers that challenge the trainees. All these different roles are classified in two main groups [START_REF] Sycara | Literature review of teamwork models[END_REF]: an equal team member or an assistant to either the team as a whole or just one particular individual.

In this paper we provide a mechanism that allows real and virtual humans to exchange their embodiments during the simulation. Such a mechanism offers new usages for both designers and users of CVETs. Industrial applications of VR training go from maintenance procedure [START_REF] Gerbaud | GVT: a platform to create virtual environments for procedural training[END_REF] to military applications [START_REF] Fonseca | A software architecture for collaborative training in virtual worlds: F-16 airplane engine maintenance[END_REF]. To further illustrate this claim let us use an illustrative scenario in industrial training. We consider various groups of two workers trainees that are learning how to operate a machine. In each group, one of the team members is a real human, the other one is a virtual one. The actions of all groups are being monitored by an expert trainer who is not embodied in the virtual world. The trainer can take over the control of the virtual coworker's embodiment and monitor the on-going work directly in the field. From there, the trainer has various options:

• if the trainee cannot operate correctly, the trainer can take over the control of the trainee's embodiment in order to move forward with the procedure before letting the trainee continues, now back on his tracks.

• if the trainee has trouble achieving his tasks, the trainer can help him by directly collaborating with him in the virtual world as his coworker.

• if the trainee is doing well, perturbations can be added to test his adaptive capabilities.

The trainee does not need to know that the control of his coworker is being swapped, the whole process is transparent for the trainee. This allows the trainer to play a more active role in its teaching, while giving him more flexibility to test the trainees capacities. Furthermore, the trainer can adapt its implication depending on the level of each trainee. Similar scenarios can be described for Medical Training [START_REF] Gallagher | Virtual reality training for the operating room and cardiac catheterisation laboratory[END_REF][START_REF] Kunkler | The role of medical simulation: an overview[END_REF] and Emergency Training [START_REF] Dugdale | Emergency fire incident training in a virtual world[END_REF] applications.

Our contribution proposes an exchange mechanism by addressing: (1) an abstract representation of real and virtual humans, (2) knowledge management. In section 2 we investigate previous work. In sections 3 and 4 we present our exchange mechanism along with our current implementation before concluding in section 5.

RELATED WORK

Our review of related work focuses on how the users and their virtual teammates are modeled, and how the knowledge is handled in existing work (CVET).

Users in CVETs

In the COVET [START_REF] Oliveira | Virtual theater for industrial training: A collaborative virtual environment[END_REF] application and in most medical collaborative training applications, only one person can interact. Others are spectators and learn the procedure. Each one is confined in its initial role during the simulation.

The GVT 1 [START_REF] Gerbaud | GVT: a platform to create virtual environments for procedural training[END_REF] platform allows collaborative training between real and virtual humans. The trainees do not have direct control of their embodiments. This system could allow the users to pass on their commands to a different embodiment during the simulation and thus perform an effective exchange. However, it does not allow users to interact directly with their environment thus simplifying the process.

For the MASCARET [START_REF] Buche | MASCARET: pedagogical Multi-Agents sys-tem for virtual environment for training[END_REF] model, implemented in the SecureVI application, the user collaborates with virtual humans by collecting their knowledge and giving them orders. A trainer oversees the training without being incarnated in the virtual world. He has the possibility to play the role of a working virtual human and act in its place. Although this represents a first step to a full-fledged exchange mechanism, only the trainer has this ability, virtual humans cannot initiate an exchange nor can the trainee.

Our analysis shows that the possibility of an exchange between users has not been addressed thoroughly. Also we did not find an existing model that gives both real humans and virtual humans a common point of entry to the virtual environment that could be exchanged at will.

Knowledge Base

Sycara et al. [START_REF] Sycara | Literature review of teamwork models[END_REF] describe various theories that aim to depict team knowledge in 1 Generic Virtual Training -http://www.gvt-nexter.fr/ teams, mixed with real and virtual humans. This has been the subject of relatively few research.

Among them, an interesting approach is the shared mental model theory. According to the psychology and cognitive science literature [START_REF] Klimoski | Team mental model: Construct or metaphor?[END_REF], people use internal representations of the world to understand and act upon it. They serve as reasoning mechanism that exists in a person's mind and allows to predict, reason and form explanations of his surrounding environment.

One popular trend in teamwork related work is the notion of a shared mental model used to improve team performance [START_REF] Jonker | Shared mental models: A conceptual analysis. Coordination, Organization, Institutions and Norms in Multi-Agent Systems@ AAMAS[END_REF][START_REF] Mathieu | The influence of shared mental models on team process and performance[END_REF]. This theory is notably used in multi-agents context [START_REF] Yen | Agents with shared mental models for enhancing team decision makings[END_REF].

None of the existing CVET has an implementation of team knowledge with mixed teams. The way knowledge is handled is central to allow continuous actions after an exchange is performed. One convenient and often used way to include the knowledge is to grant virtual humans with omniscience over the whole environment, and assume the real users know the procedure beforehand. This is how most CVETs, including Dugdale's fire simulation training [START_REF] Dugdale | Emergency fire incident training in a virtual world[END_REF] and GVT [START_REF] Gerbaud | GVT: a platform to create virtual environments for procedural training[END_REF] handle the knowledge of their virtual humans. Omniscience, for real or virtual humans, is a very strong and not realistic assumption because they are not supposed to have the same access to a full knowledge base.

Synthesis

We review the key points of our analysis of existing work. None of them successfully implements an exchange mechanism that would allow the scenarios described in our introduction to be used. Real humans and virtual humans are always considered as separate entities and therefore interact with the virtual world through different channels, making a generic control exchange mechanism difficult. The continuity of actions may be achieved through omniscient agents although the mechanism has not been tackled on directly. However there is a lack of a distributed approach that does not assume that the real humans also have the privilege of omniscience.

THE PERCEPTIVE PUPPET

The objectives of our contributions are: (1) the definition of an abstraction of the team members encompassing both real and virtual humans, (2) the construction of a model, independent from the nature of the team member, that allows the continuity of actions after an exchange is performed, (3) the formalization of the exchange process.

For this purpose we introduce the Perceptive Puppet, an abstraction (section 3.1) encompassing both real and virtual humans that combines an interaction model (section 3.2) and a knowledge base (section 3.3) to address the issues an exchange mechanism rises (section 3.4).

Concept

We introduce a specific element, the Perceptive Puppet (Fig. 1). It serves as a mediator that connects together the real or virtual humans and the virtual world. The Perceptive Puppet serves as a gateway unifying the actions sent by the team members and relaying the knowledge acquired from within the virtual world. However, it is deprived of any kind of decision process and cannot interact in the virtual world without some puppeteer pulling the strings. The team members thus act as puppeteers taking control of their respective Perceptive Puppets to act upon the virtual world. As the acquired knowledge is independent from the controlling team member, they benefit from the perceptive capabilities, the knowledge base and the interactive abilities of the Perceptive Puppet they are controlling as a base to their decision process. A Perceptive Puppet is composed of two main parts: (1) an Interaction model that describes how the Perceptive Puppet interacts with the virtual world and how it can be controlled by a real or virtual human, (2) a Knowledge base fueled by the perceptive capabilities of the Perceptive Puppet. The knowledge is independent of the real or virtual human that controls it.

With the Perceptive Puppet, an exchange of embodiment between real and virtual humans is defined as an exchange of control over the real and virtual humans' respective Perceptive Puppets. As the Perceptive Puppet contains its own knowledge base at the real and virtual humans' disposal, the controlling real or virtual human can gather data about the actions previously undertaken by the Perceptive Puppet and carry them on.

Interaction Model

Our goal with the exchange mechanism is to allow any team member to exchange their Perceptive Puppet with another one. The interaction model has to take into account that: (1) each team member takes control of a Perceptive Puppet, (2) the Perceptive Puppet interacts with other objects, (3) objects can interact with each other.

We defined an interaction model, called Collaborative-STORM (Saraos [START_REF] Luna | Collaborative Virtual Environments For Training: A Unified Interaction Model For Real Humans And Virtual Humans[END_REF] that is an extension of the STORM model [START_REF] Mollet | STORM: a generic interaction and behavioral model for 3D objects and humanoids in a virtual environment[END_REF] and therefore shares the same core mechanics. The STORM model links together behavioral objects, composed of internal behaviors and a set of communicating interfaces, that are interacting with each other. The combination of an internal behavior and a communication channel is called a capacity. A relation is defined as a link between objects that are in interaction through matching capacities. The models are a complete solution to design complex behavioral objects and complex interactions between such objects in virtual environments. The Collaborative-STORM model introduces a new relation, the Control Relation that allows one object to take control of a set of parameters of another object. In this way, one object could take control of one or several properties of another object. Our ad-dition to this model is the definition of the Perceptive Puppet as an object controllable through the Control Relation. This mechanism allows the team members, modeled as a Collaborative-STORM object, to take control of a Perceptive Puppet. The Perceptive Puppet can in turn interact with other objects of the environment (Fig. 2).

Knowledge Base

After an exchange, any team member, real or virtual, need to be able to pursue the actions of the previous owner of the Perceptive Puppet he now controls. It needs to have an understanding of what was the previous team member's actions and goals using the Perceptive Puppet knowledge, self-contained and independent of its controlling entity. The knowledge base of the Perceptive Puppet needs to be compatible and usable by all team members, particularly the real humans. This knowledge needs to be accessible so that all team members, especially real humans, can find relevant information in the Perceptive Puppet's knowledge base.

The perceptive abilities of a Perceptive Puppet are its main source of information. It is composed of two parts: the Sensory Channels and the Filter Pipeline. The Sensory Channels acquire data from the virtual environment through perceptive abilities such as vision or sound. The Filter Pipeline then filters the data according to various criteria such as relevance, spatial proximity or usefulness in the current task.

By giving the Perceptive Puppet its own knowledge and perceptive abilities, we assure that the data gathered is independent of the controlling team member. This assures us that when an exchange is performed, the knowledge of the Perceptive Puppet remains consistent.

The Exchange Protocol

We formalize the usage of an exchange of embodiments in a dedicated protocol that handles how the exchanges of Perceptive Puppets are performed. When a team member wants to take control of another Perceptive Puppet, the protocol ensures the transaction can be done before performing the exchange.

The acceptance conditions are fully customizable as they are platform and application dependent. The protocol specifies who can initiate an exchange and if virtual humans are allowed to be the instigators of an exchange or not. From another point of view, a trainer should always be able to initiate an exchange with a trainee, even without warning him. It is the trainer's decision whether an exchange can benefit the trainee's training.

The protocol also specifies the situations in which an exchange is acceptable. Indeed, team members may not be authorized to engage in an exchange while they are performing an action.

IMPLEMENTATION

In this section we provide an implementation of the embodiment exchange in an existing CVET, the GVT platform. We chose the GVT platform because its latest version allows collaborative teamwork between real humans and virtual humans. The GVT architecture mainly contains three engines: (1) the Scenario engine that describes the step by step procedure the team has to realize, (2) the Interaction engine that contains the environment composed of various behavioral objects, it follows the Collaborative-STORM model and (3) the Humanoid engine that handles the humanoid representation of the participants.

The Perceptive Puppet is added to the GVT platform as an object of the environment. It is implemented between the team members and their humanoid representation. Each team member will control a Perceptive Puppet that will in turn control an humanoid representation in the virtual environment. We describe the implementation of the Perceptive Puppet in section 4.1, the exchange protocol in section 4.2 and our test scenario used to validate our concept in section 4.3.

Perceptive Puppets

The architecture proposed to implement the Perceptive Puppet (Fig. 3) is composed of three main parts:

• Each team member, virtual and real, is linked to the Perceptive Puppets he controls.

• The Environment Interface (perception and interaction) is the link between the virtual environment and the Perceptive Puppet.

• The Knowledge Base encompasses all the knowledge base of the Perceptive Puppet.

We break down into three components: a perceptive model, a knowledge base and an interaction model. The first two ensure the continuity of actions after an exchange is performed, the last one gives real and virtual humans the ability to perform an exchange.

Perception: the Perceptive Puppet perceives its environment through a number of sensory channels. In our implementation, only a basic line of sight through ray tracing is implemented. The acquired knowledge is filtered by a pipeline of filters in order to only retain the information deemed important by the Perceptive Puppet. The filtered knowledge is then dispatched to the knowledge base.

Knowledge: part of the knowledge is taskspecific, such as the actions and tasks that are possible or required by the simulation. Others, like the position of objects and teammates and the team members' skills, are more generic and can be reused in different simulations. In our implementation, we take advantage of the GVT platform scenario engine to fuel the action related knowledge base of the Perceptive Puppets. The Perceptive Puppet stores knowledge about entities that are perceived through their sensory channels, for example storing the name of the object and the last time they have seen it. If an already known object is sighted, the time stamp is updated.

Interaction: an interaction relation is implemented as a GVT relation. The relation links Interactors (object that can take control of other objects) and Interactive Objects (objects that can be controlled by others). Once the relation is established, it passes on the commands and parameters from the Interactor to the Interactive Object. The Perceptive Puppet is implemented as a GVT object with the Interactive Object capacity. Real and virtual humans both control the Perceptive Puppet through this channel.

Exchange Protocol

The exchange protocol is encapsulated inside a dedicated GVT relation. This relation links two GVT objects disclosing the Exchange Capacity, and handles the exchange of control. The Perceptive Puppet is thus constructed as a GVT object containing amongst other capacities the exchange capacity. The current parameters are: virtual humans always agree to an exchange, virtual humans cannot initiate an ex-change, real humans are asked if they want to perform an exchange and an exchange can be performed at any time.

During the simulation, a real human triggers the exchange relation by selecting another Perceptive Puppet. If the selected Perceptive Puppet is controlled by another virtual human, the exchange is performed right away. If a real human is controlling it, a pop-up window informs him of the exchange demand and he has the choice to either validate or refuse the demand.

Test scenario

Our test application consists of a team of five soldiers having to perform a specific procedure to open fire with their armored vehicle. They need to perform a serie of coordinated actions on various parts of the vehicle. Each soldier has a well-defined role that has to be handled by a real or virtual human.

At launch, the trainee is prompted to select a role to begin the scenario. He is then given control of the corresponding Perceptive Puppet and can perform his part of the procedure regardless of the nature of the other team members. The other roles, and the associated Perceptive Puppets, are controlled by virtual humans or by other trainees. The trainee is notified of any new knowledge the Perceptive Puppet gains through its perceptive ability. The Perceptive Puppets could see their environment and keep all the perceived knowledge in their knowledge base. All the objects contained in the knowledge of the team member's Perceptive Puppet are listed in a GUI window and the trainee can select a specific object to obtain detailed information about it such as the last time it has been seen or its last known location (Fig. 4).

At any time during its work, any team member can perform an exchange with another team member by selecting its Perceptive Puppet in the application. Once the exchange has been accepted, the Perceptive Puppet controls are exchanged between the two team members. He can thus continue the process in a brand new role by using the knowledge contained in the Perceptive Puppet. This test scenario successfully demonstrates the exchange mechanism at work.

CONCLUSION

We defined a new object, the Perceptive Puppet, that provides new issues: (1) an abstraction encompassing both real human and virtual human and (2) a set of tools to ensure the continuity of actions once an exchange is performed. The Perceptive Puppet mainly achieves this by acting as a mediator be- tween the team members, real or virtual, and the virtual world. The Perceptive Puppet and its controlling entity are connected through an interaction link that works the same way for real humans and virtual humans. Additionally the Perceptive Puppet has its own knowledge and perceptive channels, independently of any controlling team member.

Figure 1 :

 1 Figure 1: The relation between the team members, the Perceptive Puppet and the Virtual World.

Figure 2 :

 2 Figure 2: Collaborative-STORM Example: a team member, either real or virtual, is controlling a Perceptive Puppet in the virtual world. Through the Perceptive Puppet, it controls a screwdriver and a screw. He then can trigger the screwing relation by using these objects with a female plug

Figure 3 :

 3 Figure 3: Architecture Implementation.

Figure 4 :

 4 Figure 4: User interface allowing Real Humans to browse the knowledge of the Perceptive Puppet it controls. The knowledge about the cannon is selected (A). The cannon is thus highlighted in the environment (B), and all the known data about it is displayed (C).

Acknowledgments

This work was partially supported by the French Research National Agency project named CORVETTE (ANR-10-CONTINT-CORD-012) and by the OSEO project named FUI11 SIFORAS.


V Bonnaillie-Noël

C Léna

Spectral minimal partitions of a sector

Keywords: Spectral theory, minimal partitions, nodal domains, Aharonov-Bohm Hamiltonian, numerical simulations, finite element method MSC classification. 35B05, 35J05, 35P15, 49M25, 65F15, 65N25, 65N30

In this article, we are interested in determining the spectral minimal k-partition for angular sectors. We first deal with the nodal cases for which we can determine explicitly the minimal partitions. Then, in the case where the minimal partitions are not given by eigenfunctions of the Dirichlet Laplacian, we analyze the possible topologies of the minimal partitions. We first exhibit symmetric minimal partitions by using mixed Dirichlet-Neumann Laplacian and then use a double covering approach to catch non symmetric candidates.

Introduction

Let us first state the definition of a minimal partition and review briefly known results about this object. In the following, Ω is an open, bounded, and connected set in R 2 . We assume that ∂Ω satisfies some regularity properties. Following [START_REF] Helffer | Nodal domains and spectral minimal partitions[END_REF], we can for example assume that ∂Ω is compact, piecewise C 1,+ and that Ω satisfies the uniform cone property. The set of all k-partitions is denoted by P k . If we do not want to specify the number of domains, we simply speak of a partition.

For any bounded open set ω ∈ R 2 , the sequence (λ k (ω)) k≥1 denotes the eigenvalues of the Dirichlet Laplacian on ω, in increasing order and counted with multiplicity. We are concerned in this paper with minimizing this energy for angular sectors. Definition 1.3 For any integer k ≥ 1, we set

L k (Ω) = inf D∈P k Λ k (D). A partition D ∈ P k such that Λ k (D) = L k (Ω) is called a minimal k-partition.
The following existence result was proved in [START_REF] Conti | An optimal partition problem related to nonlinear eigenvalues[END_REF][START_REF] Conti | A variational problem for the spatial segregation of reaction-diffusion systems[END_REF][START_REF] Conti | On a class of optimal partition problems related to the Fučík spectrum and to the monotonicity formulae[END_REF].

Theorem 1.4 For any integer k ≥ 1, there exists a minimal k-partition of Ω. Furthermore, minimal partitions are strong.

Similar existence results were previously proved in a more general setting in [START_REF] Bucur | Existence results for some optimal partition problems[END_REF].

Let us now define a regular partition. Definition 1.5 If D = {D i : 1 ≤ i ≤ k} is a strong partition, its boundary set is defined by

N (D) = k i=1 Ω ∩ ∂D i .
The partition D is called regular if the following properties are satisfied: (i) The set N (D) ∩ Ω is locally a C 1,1 -curve, except in the neighborhood of a finite set {X i : 1 ≤ i ≤ n}. The elements of this set are called interior singular points.

(ii) For each 1 ≤ i ≤ n, there is an integer ν i ≥ 2 such that in a neighborhood of X i , the set N (D) is the union of ν i half curves of class C 1,+ meeting at X i .

(iii) The set N (D) ∩ ∂Ω is finite. Its elements are called boundary singular points. If Z ∈ N (D) ∩ ∂Ω, there is an integer ρ ≥ 1 such that in the neighborhood of Z, the set N (D) is the union of ρ half curves of class C 1,+ in Ω meeting ∂Ω at Z.

(iv) At each interior singular point, the half curves meet with equal angles.

(v) At each boundary singular point, the half curves and ∂Ω meet with equal angles.

As proved in [START_REF] Helffer | Nodal domains and spectral minimal partitions[END_REF], we have the following regularity result:

Theorem 1.6 For any k ≥ 1, minimal k-partitions are regular (up to zero capacity sets).

We give additional definitions that help us to describe the topology of a partition.

Definition 1.7 Let D = {D i : 1 ≤ i ≤ k} be a strong partition. Two domains D i and D j are said to be neighbors if Int D i ∪ D j \ ∂Ω is connected.

Definition 1.8 A strong partition is called bipartite if one can color its domains, using only two colors, in such a way that two neighbors have a different color.

Let us recall some definitions and results from the spectral theory of the Laplacian. They are used throughout the paper. Let u be an eigenfunction for the Dirichlet Laplacian. Definition 1.9 We call nodal set of u the set

N (u) = {x ∈ Ω : u(x) = 0}.
The connected components of Ω \ N (u) are called the nodal domains of u. The number of nodal domains is denoted by µ(u). The set

{D i : 1 ≤ i ≤ µ(u)},
where the D i 's are the nodal domains of u, is a regular partition of Ω, called the nodal partition associated with u.

The following result was proved by Courant (cf. [START_REF] Courant | Methods of mathematical physics[END_REF]).

Theorem 1.10 If k ≥ 1 and u is an eigenfunction associated with λ k (Ω),

µ(u) ≤ k.
Following [START_REF] Helffer | Nodal domains and spectral minimal partitions[END_REF], we introduce a new definition.

Definition 1.11 Let k ≥ 1. An eigenfunction u for the Dirichlet Laplacian associated with λ k (Ω) is said to be Courant-sharp if µ(u) = k.
To give some upper-bound for L k (Ω), it could be interesting to use k-partitions obtained from eigenfunctions. Thus, we introduce a new spectral element. Definition 1.12 For k ≥ 1, L k (Ω) is the smallest eigenvalue of the Dirichlet Laplacian that has an eigenfunction with k nodal domains. If there is no such eigenvalue, we set

L k (Ω) = +∞.
With this notation, Theorem 1.10 reads as the inequality

λ k (Ω) ≤ L k (Ω).
We can now give two results of [START_REF] Helffer | Nodal domains and spectral minimal partitions[END_REF] that link minimal and nodal partitions. Theorem 1.13 A minimal partition D is nodal if, and only if, it is bipartite.

Theorem 1.14 For any integer k ≥ 1, λ k (Ω) ≤ L k (Ω) ≤ L k (Ω). Furthermore, if L k (Ω) = L k (Ω) or λ k (Ω) = L k (Ω), then λ k (Ω) = L k (Ω) = L k (Ω),
and in this case, any minimal k-partition is nodal.

Let us point out a few consequences of Theorem 1.14.

Remark 1.15 A nodal partition associated with a Courant-sharp eigenfunction is minimal.

Remark 1.16 Minimal 2-partitions are nodal. Indeed, let u be an eigenfunction associated with λ 2 (Ω). The function u is orthogonal to the eigenspace for λ 1 (Ω) and thus has at least two nodal domains. It has at most two nodal domains by Courant's theorem. It is therefore Courant-sharp, which implies that L 2 (Ω) = λ 2 (Ω) and that any minimal 2-partition of Ω is nodal.

In this article, we are concerned with the minimal k-partitions of angular sectors. For 0 < α ≤ 2π, we set

Σ α = (ρ cos θ, ρ sin θ) : 0 < ρ < 1 and -α 2 < θ < α 2 .
This set is the circular sector of opening α. We denote by (λ k (α)) k≥1 the eigenvalues of the Dirichlet Laplacian on Σ α , in increasing order and counted with multiplicity. Due to the inclusion of the form domains and the min-max principle, the function α → λ k (α) is decreasing for any k ≥ 1. In Section 2, we make explicit the spectrum of the Dirichlet Laplacian on Σ α and determine the minimal 2-partitions. In Section 3, we prove that for any k, the minimal k-partition is nodal as soon as α is small enough. In Sections 4-6, we focus on the 3-partitions. First, we determine when the minimal 3-partition is nodal (Section 4). Then, Section 5 deals with non nodal symmetric minimal 3-partitions, with some remarks about the particular case α = π/3. Then we use a double covering approach to exhibit some non symmetric candidates in Section 6. In this way, we find some non symmetric candidates which are better than any symmetric candidate. Finally we give in Section 7 some negative results for minimal k-partitions when k = 4, 5, 6 and give configurations of partitions that are never minimal.

λ m,n (α) = j 2 m π α ,n , u α m,n (ρ, θ) = J m π α (j m π α ,n ρ) sin(mπ( θ α + 1 2 )
), where j m π α ,n is the n-th positive zero of the Bessel function of the first kind J m π α . Proof:

These rather classical results are presented for example in [START_REF] Courant | Methods of mathematical physics[END_REF]. One can compute the eigenvalues of the Dirichlet Laplacian on Σ α by separation of variables. In polar coordinates, the Laplacian reads

-∂ 2 ρ - 1 ρ ∂ ρ - 1 ρ 2 ∂ 2 θ .
We look for a solution (λ, u) of

-∆u = λu in Σ α , u = 0 on ∂Σ α ,
where λ > 0 and u is not identically zero. If we set u(ρ, θ) = ϕ(ρ)ψ(θ), this yields

- ψ (θ) ψ(θ) = ρ 2 ϕ(ρ) ϕ (ρ) + 1 ρ ϕ (ρ) + λϕ(ρ) .
According to the Dirichlet conditions, ψ(-α 2 ) = ψ( α 2 ) = 0. Therefore there exists an integer m ≥ 1 such that, up to a constant multiplicative factor,

ψ(θ) = sin mπ α θ + α 2 .
Then, we get

ϕ (ρ) + 1 ρ ϕ (ρ) + λ - m 2 π 2 α 2 ρ 2 ϕ(ρ) = 0. If we set ν = π α , λ = ω 2 , t = ωρ, f (t) = ϕ(ρ),
we recognize the Bessel differential equation

f (t) + 1 t f (t) + 1 - m 2 ν 2 t 2 f (t) = 0.
The function u is assumed to be in H 1 (Σ α ) and to satisfy the Dirichlet boundary condition. This implies that f is proportional to the Bessel function of the first kind J mν and that ω is a zero of J mν .

We have obtained a family of eigenmodes (λ m,n (α), u α m,n ) indexed by m ≥ 1 and n ≥ 1. More precisely, we have the expressions

λ m,n (α) = j 2 mν,n , (2.1)
where j mν,n is the n-th positive zero of the function J mν and u α m,n (ρ, θ) = J mν (j mν,n ρ) sin(mν(θ + α 2 )).

(2.2)

We can check that the set {u α m,n } m,n is orthogonal and spans L 2 (Σ α ). Therefore there is no other eigenvalue. Corollary 2.2 For any k ≥ 2 and α ∈ (0, 2π], we have the first estimate

λ k (α) ≤ L k (α) ≤ L k (Σ α ) ≤ inf{λ m,n (α) : mn = k}.

Proof:

It is enough to use Theorem 1.14, Proposition 2.1 and to notice that for any m ≥ 1, n ≥ 1, and α ∈ (0, 2π], the eigenfunction u α m,n has mn nodal domains.

In Figure 1 are plotted some eigenvalues λ m,n (α) for 1 ≤ m ≤ 7, 1 ≤ n ≤ 4, and α ∈ (0, 2π].

Minimal nodal partition

Proposition 2.3 For 2 ≤ k ≤ 5, we define

α 2 k = inf{α ∈ (0, 2π] : λ k,1 (α) < λ 1,2 (α)}.
Then for any α ∈ [α 2 k , 2π], the nodal partition associated with u α k,1 is a minimal k-partition and we have

L k (Σ α ) = λ k,1 (α).
For 2 ≤ k ≤ 5 and α ∈ (α 2 k , 2π], the minimal k-partition consists then of k angular sectors with the same aperture. For k ≥ 6, any k-partition constituted of k angular sectors is never minimal. By continuity of α → λ k,1 (α), the real number α 2 k is well defined for 2 ≤ k ≤ 5, and for any α ∈ (α 2 k , 2π], we have

λ k,1 (α) < λ 1,2 (α) for k = 2, . . . , 5.
Using the definition of α 2 k , we have

λ k (α) = λ k,1 (α), ∀α ∈ (α 2 k , 2π].
Since u α k,1 has k nodal domains, it is Courant-sharp and its nodal partition, composed of k equal angular sectors, is minimal according to Remark 1.15. For k ≥ 6, we observe that λ k,1 (α) > λ 1,2 (α) for any α ∈ (0, 2π]. Then λ k,1 (α) > λ k (α), the eigenfunction u α k,1 is not Courant-sharp, and its nodal partition is not minimal. Still assuming k ≥ 6, let us prove by contradiction that a k-partition D k = (D 1 , . . . , D k ) with D i angular sector cannot be minimal. Let us assume that it is minimal. Then the aperture for each sector must be the same, otherwise we could decrease the energy by increasing some angles and decreasing others. The partition D k is therefore nodal, associated with u k,1 , and thus not minimal.

Minimal 2-partition

According to Remark 1.16, we know that

L 2 (Σ α ) = λ 2 (α), ∀0 < α ≤ 2π.
Furthermore a minimal 2-partition is given by the nodal partition associated with λ 2 (α).

To be more precise, for α < α 2 2 , λ 2 (α) is simple and equal to λ 1,2 (α) and for α > α 2 2 , λ 2 (α) is simple and equal to λ 2,1 (α). For α < α 2 2 and α > α 2 2 , there is a unique minimal 2-partition, given by the nodal domains of u α 1,2 and u α 2,1 respectively. Thus we have Proposition 2.4

L 2 (Σ α ) = λ 1,2 (α) for 0 < α ≤ α 2 2 , λ 2,1 (α) for α 2 2 ≤ α ≤ 2π.
Figure 3 gives the unique minimal 2-partition when α = α 2 2 . We notice that the eigenfunction u α 1,2 is symmetric according to the axis {y = 0} while u α 2,1 is antisymmetric.

0 < α < α 2 2 α 2 2 < α ≤ 2π L 2 (Σ α ) = λ 1,2 (α) L 2 (Σ α ) = λ 2,1 (α)
Let us determine α 2 2 and the associated eigenvalue. We set ν = π/α 2 2 and j = j ν,2 = j 2ν,1 . The pair (ν, j) is a solution of the (nonlinear) system

J ν (j) = 0, J 2ν (j) = 0.
We can solve this system numerically by any iterative method. The initial values must be chosen so that j is indeed the second zero of J ν and the first of J 2ν . In practice we find approximations of j and ν thanks to Figure 2 and use them as initial values. We get

α 2 2 0.3541 π 1.1125, λ 2 (α 2
2 ) 90.7745.

For α = α 2 2 , λ 2 (α) = λ 1,2 (α) = λ 2,1 (
α) has a two-dimensional eigenspace and the nodal domains of any nonzero linear combination of u α 1,2 and u α 2,1 give a minimal 2-partition (see Figure 4).

t = 0 t = 0.2 t = 0.3516 t = 0.4 t = 0.6 t = 0.8 t = 1 Figure 4: Minimal 2-partitions obtained as nodal partitions of (1 -t)u α 1,2 + tu α 2,1 , α = α 2 2 .

Minimal partition for small angles

For sufficiently small angles, the minimal k-partition is nodal as explained in the following proposition.

Proposition 3.1 Let k ≥ 2, we define

α 1 k := inf{α ∈ (0, 2π] : λ 1,k (α) ≥ λ 2,1 (α)}. (3.1)
Then α 1 k > 0 and for any 0 < α < α 1 k , there is a unique minimal k-partition of Σ α , which is nodal, and more precisely consists of the nodal sets of u α 1,k .

Proof:

Using [START_REF]NIST Digital Library of Mathematical Functions[END_REF], we determine the asymptotic expansion of the n-th zero j ν,n of the Bessel function J ν for large ν :

j ν,n = ν -2 -1/3 a n ν1/3 + O ν-1/3 .
Here a n is the n-th negative zero of the Airy function Ai. Together with equation (2.1) and the relation ν = mπ/α, this yields an asymptotic expansion for the eigenvalues :

λ m,n (α) = m 2 π 2 α 2 + 2 2/3 |a n | mπ α 4/3 + O α -2/3 . (3.2)
Let k ≥ 2 be an integer. The asymptotic expansion (3.2) implies that for α small enough, λ 1,k (α) < λ 2,1 (α). Then the real number α 1 k defined by relation (3.1) is strictly positive. For α ∈ (0, α 1 k ), we have λ 1,k (α) < λ 2,1 (α) and therefore the first k eigenvalues of the Dirichlet Laplacian on Σ α are λ 1,1 (α), . . . , λ 1,k (α). These eigenvalues are simple. Let u α 1,1 , . . . , u α 1,k be the associated eigenfunctions defined by (2.2). The eigenfunction u α 1,k has k nodal domains and therefore is Courant-sharp. According to Theorem 1.15, the nodal partition associated with u α 1,k is minimal. Furthermore, the eigenspace associated with λ α

1,k has dimension 1 and thus this partition is unique. Figure 5 gives the first ten eigenvalues λ 1,k (α) compared with λ 2,1 (α) and shows the critical angles α 1 k . We have

λ 1,1 λ 1,2 λ 1,3 λ 1,4 λ 1,5 λ 1,6 λ 1,7 λ 1,8 λ 1,9 λ 1,10 λ 2,1
α 1 2 = α 2 2 , α 1 k < α 2 k , for k = 3, . . . , 5.
We deduce

Proposition 3.2 For any 2 ≤ k ≤ 5, L k (Σ α ) = λ k (α), ∀α ∈ (0, α 1 k ] ∪ [α 2 k , 2π], λ k (α) < L k (Σ α ) < L k (α), ∀α ∈ (α 1 k , α 2 k ).
Remark 3.3 Using the asymptotic expansion, we deduce that λ 1,k (α) ≤ λ k,1 (α) as soon as α is small enough. Let k be a prime number, we define

β k = inf{α ∈ (0, 2π] : λ 1,k (α) ≥ λ k,1 (α)}. (3.3)
Then , we have

β 2 = α 1 2 = α 2 2 and L k (Σ α ) ≤ λ 1,k (α) if 0 < α ≤ β k , λ k,1 (α) if β k ≤ α ≤ 2π.

Minimal nodal 3-partition

As in the case of the 2-partition, we estimate numerically the transition angles α 6:

• for 0 < α ≤ α 1 3 , L 3 (Σ α ) = λ 3 (α) = λ 1,3 (α), • for α 1 3 < α ≤ β 3 , λ 2,1 (α) = λ 3 (α) < L 3 (Σ α ) < L 3 (Σ α ) = λ 1,3 (α),
• for If α ≤ α 1 3 or α ≥ α 2 3 , the eigenvalue λ 3 (α) has a Courant-sharp eigenfunction. According to Remark 1.15, L 3 (Σ α ) = λ 3 (α) and the minimal 3-partition is nodal, given by the nodal sets of an eigenfunction associated with λ 3 (α). On the other hand, if α 1 3 < α < α 2 3 , no minimal 3-partition is nodal. Table 1 gives the nodal partition associated with the third eigenfunction. We notice that the eigenfunctions u α 1,3 and u α 3,1 are symmetric according to the axis {y = 0}.

β 3 ≤ α ≤ β 2 , λ 2,1 (α) = λ 3 (α) < L 3 (Σ α ) < L 3 (Σ α ) = λ 3,1 (α), • for β 2 ≤ α < α 2 3 , λ 1,2 (α) = λ 3 (α) < L 3 (Σ α ) < L 3 (Σ α ) = λ 3,1 (α), • for α 2 3 ≤ α ≤ 2π, L 3 (Σ α ) = λ 3 (α) = λ 3,1 (α).
β 3 <β 2 α/π λ m,n (α) λ 1,3 λ 3,1 λ 2,1 λ 1,2
Let us now look at the transition angles α 1 3 and α 2 3 . For such angles, the minimal 3-partition is no more unique. Figure 7 represents the nodal partitions of some linear combination (1 -t)u α 1,3 + tu α 2,1 for α = α 1 3 . We observe a transition between a 2-partition and a 3-partition. When we have

0 < α ≤ α 1 3 α 1 3 < α < α 1 2 α 1 2 < α < α 2 3 α 1 3 ≤ α ≤ 2π L 3 (Σ α ) = λ 1,3 (α) λ 2,1 (α) < L 3 (Σ α ) λ 1,2 (α) < L 3 (Σ α ) L 3 (Σ α ) = λ 3,1 (α) minimal 3-partition minimal 3-partition
Table 1: Nodal partition associated with λ 3 (α) on Σ α . a 3-partition, it is a minimal one since the eigenfunction is associated with λ 3 (α) and then Courant-sharp (see Remark 1.15). Notice that the function u α 1,3 is symmetric with respect to the y-axis whereas the function u α 2,1 is antisymmetric. Thus, by considering linear combinations, we break the symmetry of the 3-partition and exhibit some minimal 3-partitions which are non symmetric.

Minimal 3-partition t = 0 t = 0.2 t = 0.4 t = 0.49 t = 0.6 t = 0.8 t = 1 Figure 7: Nodal partitions of (1 -t)u α 1,3 + tu α 2,1 , α = α 1 3 .
The following proposition gives information about the transition in the linear combinations between 2-partition and 3-partition.

Proposition 4.1 There are eigenfunctions associated with λ 3 (α 1 3 ) whose nodal set has a boundary singular point with two nodal lines which hit at this point. The polar coordinates of this boundary singular point is either (ρ c , α 1 3 /2) or (ρ c , -α 1 3 /2) with ρ c 0.6558.

Proof:

We recall that

λ 3 (α 1 3 ) = λ 1,3 (α 1 3 ) = λ 2,1 (α 1 3 ). We set ν = π α 1 3 , j = j ν,3 = j 2ν,1 .
Any associated eigenfunction is of the form u(ρ, θ) = aJ ν (jρ) cos(νθ) + bJ 2ν (jρ) sin(2νθ),

where a and b are coefficients to be determined. It can be factorized as u(ρ, θ) = J 2ν (jρ) cos(νθ) a J ν (jρ) J 2ν (jρ) + 2b sin(νθ) .

Let us define

v(ρ, θ) = a J ν (jρ) J 2ν (jρ) + 2b sin(νθ).

We are looking for values of a and b for which v has a zero that is also a singular point.

The equation ∇v(ρ, θ) = 0 can be solved and yields

θ c = ±α 1 3 /2, ρ c 0.6558.
Thanks to the equation v(θ c , ρ c ) = 0, we then find a and b up to a common multiplicative factor.

Similarly, Figure 8 gives the nodal partition associated with the linear combination (1 -t)u α 1,2 + tu α 3,1 for α = α 2 3 . In this case, the functions u 1,2 and u 3,1 are both symmetric with respect to the y-axis. Then any linear combination satisfies this symmetry too. As previously, we observe a transition between a 2-partition and a 3-partition. When we have a 3-partition, it is still a minimal one. We can characterize the transition between 2-partition and 3-partition: Proposition 4.2 There are eigenfunctions associated with λ 3 (α 2 3 ) for which the point of coordinates (1, 0) is a boundary singular point. Two nodal lines meet at this point.

Proof:

This proposition is proved in the same way than proposition 4.1.

Minimal 3-partition

t = 0 t = 0.2 t = 0.4 t = 0.5169 t = 0.6 t = 0.8 t = 1 Figure 8: Nodal partition of (1 -t)u α 1,2 + tu α 3,1 , α = α 2 3 .

Minimal symmetric 3-partitions

In this section, we propose candidates to be minimal symmetric 3-partitions. This approach was used in [START_REF] Bonnaillie-Noël | Numerical simulations for nodal domains and spectral minimal partitions[END_REF] to catch symmetric candidates for the square and the disk.

Looking at nodal minimal 3-partitions obtained in Section 4, we observe that for any α ∈ (0, α 1 3 ] ∪ [α 2 3 , 2π], there exists a symmetric minimal 3-partition. Now, we exhibit symmetric candidates to be minimal symmetric 3-partitions for α ∈ (α 1 3 , α 2 3 ). We refer to [START_REF] Bonnaillie-Noël | Numerical simulations for nodal domains and spectral minimal partitions[END_REF] to explain the possible symmetric configurations. Using the Euler formula (cf. [START_REF] Helffer | On minimal partitions: new properties and applications to the disk[END_REF]), there are only three configurations, represented in Figure 9, for the minimal 3-partition when α 1 3 < α < α 2 3 :

(a) The 3-partition has one interior singular point X 0 , which is necessarily on the symmetry axis.

(b) The 3-partition has two interior singular points X 0 , X 1 and no boundary singular point.

(c) The 3-partition has two interior singular points and two boundary singular points.

Moreover ∂D 1 ∩ ∂D 2 consists of two curves, each one joining one boundary singular point to one interior singular point.

In configurations (b) and (c), the interior singular points X 0 , X 1 (and boundary singular points for case (c)) are either on the symmetry axis, or symmetric to each other.

(a1) (b1) (c1) O M X 0 • • • O M X 0 X 1 • • • • O M X 0 X 1 • • • • (a2) (b2) (c2) O M X 0 • • • O M X 0 X 1 • • • • O M X 0 X 1 • • • • Figure 9:
Configuration of the non bipartite symmetric minimal 3-partition.

Partition with one interior singular point

Let us first consider configurations of type (a). To catch such configuration, it is enough to deal with the half-domain Σ + α = Σ α ∩{y > 0} and look at 2-partitions on this half-domain. The main advantage is that the minimal 2-partitions are nodal; to determine them, it is enough to compute the second eigenfunction. The unknown parameter is the position of the singular point X

     -∆ϕ = λϕ in Σ + α , ∂ n ϕ = 0 on [O, X α 0 ], ϕ = 0 elsewhere. (a2)      -∆ϕ = λϕ in Σ + α , ∂ n ϕ = 0 on [X α 0 , M ], ϕ = 0 elsewhere,
For each mixed problem, the nodal line of the second eigenvector meets the axis {y = 0} at a point of abscissa denoted by y N D (x α ) and y DN (x α ) respectively. The choice of the interior singular point X α 0 gives a 3-partition after symmetrization if and only if

• y N D (x α ) ≥ x α in the Neumann-Dirichlet case,
• y DN (x α ) ≤ x α in the Dirichlet-Neumann case. x α is such that x α < y N D (x α ), we obtain a 3-partition whose energy can be reduced by removing the Dirichlet line (Y N D (x α ), X α 0 ) (where Y N D (x α ) is the point of coordinates (y N D (x α ), 0)) in this sub-domain of the partition. We can make a similar analysis in the Dirichlet-Neumann case (see Figure 10(b)). Since the function x → λ N D 2 (x) is decreasing with x and x → λ DN 2 (x) is increasing with x, the optimal singular points are:

y N D (x α ) > x α y N D (x α ) < x α 3-partition 2-partition (
x N D α = max{x α : y N D (x α ) ≥ x α }, x DN α = min{x α : y DN (x α ) ≤ x α }. (5.1)
For numerical simulations, we use the discretization

α ∈ { k 100 π, 16 ≤ k ≤ 77} and x α ∈ { j 100 , 0 ≤ j ≤ 100}.
We denote by xND α and xDN α the singular points defined by (5.1) for a discretization x α ∈ { j 100 , 0 ≤ j ≤ 100}. Figure 11 represents these singular points according to α. The 3-partitions obtained after symmetrization give upper-bounds for L 3 (α) as illustrated in Figure 12. We observe that the energy for the Neumann-Dirichlet Laplacian is smaller than the one obtained with the Dirichlet-Neumann Laplacian and smaller than L 3 (α). Thus using Theorem 1.14, we deduce Proposition 5.1 For any α ∈ (α 1 3 , α 2 3 ),

λ 3 (α) < L 3 (Σ α ) ≤ L sym 3 (α) < L 3 (α), with L sym 3 (α) := min(λ DN 2 (x DN α ), λ N D 2 (x N D α )) = λ N D 2 (x N D α ).
Figure 13 gives examples of minimal symmetric 3-partitions of type (a) for several angles. We denote by D sym α the best candidate obtained like this.

Partition with two interior singular points

We have now to deal with the other configurations (b) and (c). Then, as illustrated in Figure 9, the two interior singular points X 0 and X 1 are either on the axis {y = 0}, or symmetric to each other. Their coordinates are therefore:

1. X 0 = (x 0 , 0) and X 1 = (x 1 , 0) in case (b1) or (c1), 2. X 0 = (x 0 , y 0 ) and X 1 = (x 0 , -y 0 ) in case (b2) or (c2).

Let us first rule out configurations (b2) and (c2):

Lemma 5.2 Let α ∈ (α 1 3 , α 2
3 ) and D α be a minimal 3-partition. We assume that this partition is symmetric according to the y-axis. Then the interior singular points are necessarily on the axis {y = 0}.

Proof:

This is clear for configuration of type (a) and we have used this property previously. Let us now assume that the partition D α is of type (b2) or (c2). Then, since

D + α = D α ∩{y > 0} is
(α) = λ 1,3 (α) if α 1 3 < α ≤ β 3 and λ N 3 (α) = λ 3,1 (α) if β 3 ≤ α < α 2 3 , that is to say λ N 3 (α) = L 3 (α), ∀α ∈ (α 1 3 , α 2
3 ). Using Proposition 5.1 and Figure 12, we observe that for any α ∈ (α 1 3 , α 2 3 ), we find a symmetric 3-partition D sym α of type (a1) such that

Λ 3 (D sym α ) < L 3 (α) ≤ Λ 3 (D α
). Thus D α cannot be a minimal 3-partition.

We have then reduced the study to configurations (b1) and (c1). The associated mixed problems read

Neumann-Dirichlet-Neumann Dirichlet-Neumann-Dirichlet (b1)      -∆ϕ = λϕ in Σ + α , ∂ n ϕ = 0 on [O, X α 0 ] ∪ [X α 1 , M ], ϕ = 0 elsewhere, (c1)      -∆ϕ = λϕ in Σ + α , ∂ n ϕ = 0 on [X α 0 , X α 1 ], ϕ = 0 elsewhere.
Using the results of Subsection 5.1 for the configuration (a), we can restrict the possible critical points for configuration (c1):

Proposition 5.3 Let D = (D 1 , D 2 , D
3 ) be a symmetric 3-partition of type (c1) with the interior singular points X α 0 and X α 1 of coordinates (x 0 , 0) and (x 1 , 0). We assume either

x 0 < x 1 ≤ x N D α , or x DN α ≤ x 0 < x 1 .
Then this partition cannot be minimal.

Proof:

We assume that

x 0 < x 1 < x N D
x 0 < x 1 ≤ x N D α , we have λ DN D 2 (x 0 , x 1 ) > λ N D 2 (x 1 ) ≥ λ N D 2 (x N D α ) = L sym 3 (α) ≥ L 3 (α).
Thus the partition D can not be minimal. The proof is similar if we assume x DN α ≤ x 0 < x 1 .

Figure 11 gives an approximation at 1/100 for x N D α and x DN α and thus the location for possible interior singular points for configuration (c1). When we search for candidates of type (b1) or (c1) numerically, we use the discretization

α ∈ { k 100 π, 16 ≤ k ≤ 77} and X α k = (x α k , 0), x α k ∈ { j 100 , 0 ≤ j ≤ 100}, k = 0, 1.
As in [START_REF] Bonnaillie-Noël | Numerical simulations for nodal domains and spectral minimal partitions[END_REF] for the square and the disk, the second eigenfunction associated with these mixed problems never produces a configuration of type (b) or (c). Then the mixed Neumann-Dirichlet problem provides the best symmetric candidates for any α ∈ (α 1 3 , α 2 3 ).

Angular sector of opening α = π/3

Let us analyze more specifically the case α = π/3. Using the approach developed in Subsection 5.1, the best candidate obtained is represented in Figure 14 with xND π/3 = 0.64 (we recall that for the numerics, x α ∈ {k/100, 0 ≤ k ≤ 100}). It seems that the nodal lines are straight lines. This is compatible with the equal angle properties: At the interior singular point, the nodal lines have to meet with angle 2π/3 whereas the nodal lines meet the boundary at right angles. Let us try to understand some properties of such a partition. We reproduce this 3-partition of Σ π/3 by rotation of ±π/3 and ±2π/3 to tile the disk. Figure 15 of Σ π/3 , assuming that the nodal lines are straight lines. We denote by A the interior singular point of coordinates (L, 0). Let B be the boundary singular point of coordinates L/4(3, √ 3) and C its symmetric point according to the axis {y = 0}. The area of the total disk Disk equals A(Disk) = π. The area of the regular hexagon plotted in red in Figure 15 is

A(Hex) = 3 √ 3 2 L 2 .
We deduce

A(Ω 1 ) = √ 3L 2 4 .
Let us now compute the area of Ω 2 . We have

A(Ω 2 ) = 1 12 (A(Disk) -A(Hex)) = 2π -3 √ 3L 2 24
.

With L = 0.64, we obtain A(Ω 1 ) 0.177 and A(Ω 2 ) 0.173.

Since the accuracy on L is 10 -2 , this gap is not significant. Let us determine now for which value of L we have the equality:

A(Ω 1 ) = A(Ω 2 ) ⇐⇒ √ 3L 2 4 = 2π -3 √ 3L 2 24 ⇐⇒ L = 2π 9 √ 3 0.634 875.
In this case, we have A(Hex) = π/3. This result is coherent with the discretization step for x α which equals 1/100. Therefore it seems that the areas of every domains of the partition are equal.

Laplacian on the double covering

The method proposed in Section 5 can only catch symmetric candidates. However, we have seen in Figure 7 that for the angle α = α 1 3 , there exists non symmetric minimal 3-partitions. So we would like to find a method to catch non symmetric candidates. The method we use now was introduced in [START_REF] Bonnaillie-Noël | Aharonov-Bohm Hamiltonians, isospectrality and minimal partitions[END_REF] to explain why we find two symmetric configurations with the same energy in the square. Let us explain this method. Let us go back to a general bounded open and simply connected set Ω with piecewise C 1,+ boundary. In the non nodal case, there are three topological types possible for a minimal 3-partition of such a domain. They are given by configuration (a), (b), and (c) in Section 5, removing the symmetry assumption. As suggested by the numerical study of the symmetric case, we only look for minimal partitions of type (a). Then, there is an interior singular point where three half-curves meet. Following [START_REF] Bonnaillie-Noël | Aharonov-Bohm Hamiltonians, isospectrality and minimal partitions[END_REF], we consider a double Riemannian covering of the domain Ω punctured by this point. We then look for a minimal partition of Ω as the projection of a nodal partition of the double covering.

Double covering of the domain

We will give a rather informal description of the double covering. Let us consider a point X 0 ∈ Ω. We denote Ω \ {X 0 } by Ω X 0 . We now choose a simple regular curve γ contained in Ω that links X 0 to a point in ∂Ω. We consider two copies of Ω \ γ that we glue in such a way that a side of γ on one sheet is connected to the opposite side on the other sheet (cf. Figure 16). The resulting object is a two dimensional manifold with boundary, that we denote by Ω X 0 , with a natural projection map Π : Ω X 0 → Ω X 0 . It is a double covering of Ω X 0 , that we equip with the Riemannian metric lifted from Ω X 0 through Π. A rigorous and general construction is explained in [START_REF] Helffer | Nodal sets for groundstates of Schrödinger operators with zero magnetic field in nonsimply connected domains[END_REF]. In particular, it can be shown that the result does not depend on the choice of γ.

0 0 1 1 0 0 1 1 0 1 Ω X 0 G X 0 Π 1 2 γ 2 1 γ X 0 X 0 Ω X 0

Symmetric and antisymmetric eigenvalues

Let us now define a mapping G from Ω X 0 onto itself, called the deck map. For any X 1 ∈ Ω X 0 , G(X 1 ) is the only element X 2 ∈ Ω X 0 such that X 2 = X 1 and Π(X 2 ) = Π(X 1 ).

Intuitively, the mapping G moves points from one sheet of the double covering to the other one. We have of course

G 2 = Id. A function f : Ω X 0 → C is said to be symmetric if f • G = f and antisymmetric if f • G = -f .
If we call S (resp. A) the space of functions in L 2 ( Ω X 0 ) that are symmetric (resp. antisymmetric), we have the orthogonal decomposition:

L 2 ( Ω X 0 ) = S ⊕ A.
We call lifted Laplacian the Laplace-Beltrami operator on Ω X 0 with Dirichlet boundary condition. The lifted Laplacian preserves symmetric and antisymmetric functions. We can therefore choose a basis of eigenfunctions for each subspace S and A. Their reunion is a basis of eigenfunctions for L 2 ( Ω X 0 ). The eigenvalues associated with a symmetric (resp. antisymmetric) eigenfunction will be called symmetric (resp. antisymmetric). The symmetric eigenvalues are actually the eigenvalues of the Dirichlet Laplacian on Ω, since any symmetric eigenfunction is lifted from an eigenfunction on Ω X 0 . We call the antisymmetric eigenvalues Aharonov-Bohm eigenvalues, denoted by λ AB k , since they can be considered as the eigenvalues of a so-called Aharonov-Bohm operator with pole at X = X 0 and flux Φ = 1/2 (cf. [START_REF] Aharonov | Significance of electromagnetic potentials in the quantum theory[END_REF][START_REF] Helffer | Nodal sets for groundstates of Schrödinger operators with zero magnetic field in nonsimply connected domains[END_REF][START_REF] Alziary | Eigenfunctions and Hardy inequalities for a magnetic Schrödinger operator in R 2[END_REF][START_REF] Pankrashkin | Spectral and scattering theory for the Aharonov-Bohm operators[END_REF]).

Let us now consider a nodal partition D = {D i : 1 ≤ i ≤ } associated with an antisymmetric eigenfuction u. The image of a domain of D by the deck map G is another domain where u has the opposite sign. We can therefore group together the domains of D in pairs {D i , D j } such that D i ∩ D j = ∅ and Π(D i ) = Π(D j ). The set Π(D) = {Π(D i ) : 1 ≤ i ≤ } is then a strong k-partition of Ω, with 2k = (we deduce in particular that is even). Furthermore, contrary to D, the partition Π(D) is not necessarily bipartite. We will use this to build non nodal candidates to be a minimal k-partition. Consequently, if we find for some α a singular point X such that there exists an antisymmetric eigenfunction with 6 nodal domains and associated with λ 6 ( (Σ α ) X ) such that λ 6 ( (Σ α ) X ) < Λ 3 (D sym α ), then the symmetric 3-partition D sym α is not minimal. Indeed, the projection of this sixth eigenfunction on the first sheet is a 3-partition whose energy is less than Λ 3 (D sym α ). We have another way of checking that a 3-partition is not minimal. According to [13, Remark 5.2], a minimal 3-partition must be Courant-sharp for the Aharonov-Bohm operator, that is to say, its energy must be λ AB 3 . Let us now combine the double covering approach and the results of Section 5 to obtain more information. The first result consists in invalidating possibly some candidates of type (a1) obtained in Subsection 5.1. Let us use the best candidates obtained in Subsection 5.1. For any α ∈ {kπ/100, 16 ≤ k ≤ 76}, we compute the first eigenvalues of the Dirichlet Laplacian on the double covering (Σ α ) X with X = (x N D α , 0) and we split the spectrum between the symmetric eigenvalues λ k (Σ α ) and the antisymmetric ones λ AB k ((Σ α ) X ). Figure 17 gives the first seven eigenvalues on (Σ α ) X and the nodal partition of the eigen-

j (( Σ α ) X ), with X = (x N D α , 0), α ∈ { kπ 100 , 16 ≤ k ≤ 76, 1 ≤ j ≤ 7}.
functions are represented on Figure 18 for several α. We notice that

Λ 3 (D sym α ) = λ 7 ( (Σ α ) X ) = λ AB 4 ((Σ α ) X ) > λ 5 ( (Σ α ) X ) = λ AB 3 ((Σ α ) X ), for α = 16π/100, Λ 3 (D sym α ) = λ 7 ( (Σ α ) X ) = λ AB 4 ((Σ α ) X ) > λ 6 ( (Σ α ) X ) = λ AB 3 ((Σ α ) X ), for α = 17π/100, Λ 3 (D sym α ) = λ 6 ( (Σ α ) X ) = λ AB 3 ((Σ α ) X )
, for α ∈ { kπ 100 , k = 18, . . . , 76}. Consequently, the minimal symmetric 3-partition D sym α is not minimal for α = 16π/100 and α = 17π/100.

To make simulations, we use the techniques we have previously explained in [START_REF] Bonnaillie-Noël | Numerical analysis of nodal sets for eigenvalues of Aharonov-Bohm Hamiltonians on the square with application to minimal partitions[END_REF]: this consists in meshing the double covering for the domain and using the Finite Element Library Mélina (see [START_REF] Martin | Mélina, bibliothèque de calculs éléments finis[END_REF]).

α = kπ 100 λ 2 (( Σ α ) X ) λ 3 (( Σ α ) X ) λ 4 (( Σ α ) X ) λ 5 (( Σ α ) X ) λ 6 (( Σ α ) X ) λ 7 (( Σ α ) X ) k = 16 k = 17 k = 18 k = 20 k = 31 k = 35 k = 40 k = 50
(( Σ α ) X ), X = (x N D α , 0), α = kπ 100 , 2 ≤ j ≤ 7.

Numerical simulations for non symmetric candidates

Let us consider an angle α = α 1 3 + ε with ε very small and positive. We have seen that the 3-partition D sym α is not minimal when ε is small enough. We would like to use the double covering approach to catch some non symmetric candidates. For any point X ∈ Ω, we compute the first six eigenvalues of the Dirichlet Laplacian on the double covering (Σ α ) X . The symmetric eigenvectors are those of the Dirichlet Laplacian on Σ α and we are interested in the antisymmetric ones. We move the puncturing point on Σ α and hope to find a 3-partition given by the 6-th eigenfunction of the Dirichlet Laplacian on (Σ α ) X . Proposition 4.1 gives us an idea to localize the puncturing point X. Starting with Σ α for α = α 1 3 , we can pick an eigenfunction whose nodal set has a boundary singular point with polar coordinates (ρ c , α 1 3 /2). Its nodal partition has three domains and a boundary singular point at (ρ c , α 1 3 /2) where two lines meet. We recall that at a singular point, nodal lines satisfy the equal angle property. We can use this property to localize a possible singular point for Σ α with α = α 1 3 + ε. If the minimal 3-partition for Σ α has a singular point on the boundary {y = x tan α 2 } with only one nodal line reaching this point, then this nodal line is normal to the boundary at the singular point. If ε is very small, the distance between this singular point and the origin should be close to ρ c . When the angle is increasing, this approximation is not efficient. For α = π/3, the boundary singular point seems to have polar coordinates (ρ 3 , π/6) with ρ 3 = L √ 3/2 0.5498. For numerical computations, we choose X on some perpendicular axes to the boundary (see Figure 19 For different sectors, we proceed in the same way and obtain new candidates whose energy is represented in orange color in Figure 12 (see also Figure 20). We obtain a better candidate than the symmetric one for angles close to α 1 3 and especially for α = 16π/100 and α = π/6. For larger angles, the double covering approach gives candidates whose energy is so close to those of the symmetric candidates that we cannot be affirmative. This is probably due to the fact that the best candidate obtained by the double covering approach has an interior singular point close to (or on) the symmetry axis for larger α and then, by continuity, the eigenvalues are close to those of the mixed Neumann-Dirichlet Laplacian.

Notice that for α = α 2 3 , all candidates in Figure 8 are symmetric. This encourages us to make the conjecture:

3 ), the minimal 3-partitions are non symmetric,

• for α ∈ (α 3 3 , α 2 3 ), any minimal 3-partition is symmetric.

7 Negative results for minimal k-partitions, k = 4, 5, 6 We observe that λ 2,2 (α) > λ 4 (α). Consequently, partitions having the topology illustrated in Figure 22 cannot be minimal for any α.

5-partition

Since k = 5 is a prime number, we only have the bounds given by Proposition 3.2 and Remark 3.3:

L 5 (α) = λ 5 (α)
for α ∈ (0, α 1 5 ] ∪ [α 2 5 , 2π], λ 5 (α) < L 5 (α) < L 5 (Σ α ) ≤ min(λ 1,5 (α), λ 5,1 (α))

for α ∈ (α 1 5 , α 2 5 ).

Definition 1 . 1

 11 For any integer k ≥ 1, a k-partition is a finite setD = {D i : 1 ≤ i ≤ k}of open, connected and mutually disjoint subsets of Ω. The D i 's are called the domains of the k-partition. The k-partition D is called strong if Int

Definition 1 . 2

 12 With any k-partition D = {D i : 1 ≤ i ≤ k}, is associated the energy Λ k (D) = max 1≤i≤k λ 1 (D i ).

Proposition 2 . 1

 21 The eigenmodes (λ m,n (α), u α m,n ) of the Dirichlet Laplacian on the angular sector Σ α are given by

Figure 3 :

 3 Figure 3: Minimal 2-partition on Σ α .

Figure 5 :

 5 Figure 5: λ 1,k (α) vs. α/π for 1 ≤ k ≤ 10, compared with λ 2,1 (α).

Figure 6 :

 6 Figure 6: Lower and upper bounds for L 3 (Σ α ).

α 0 .

 0 Thus we compute the second eigenvector of the Neumann-Dirichlet and Dirichlet-Neumann Laplacian on Σ + α and move the singular point all along the axis {y = 0}; we denote by x α the abscissa of the singular point X α 0 and by λ N D 2 (x α ) and λ DN 2 (x α ) the second eigenvalue of the Neumann-Dirichlet and Dirichlet-Neumann Laplacian respectively (see Figures 9(a1) and 9(a2)): Neumann-Dirichlet Dirichlet-Neumann (a1)

Figure 10 gives

 10 Figure 10 gives examples of nodal partitions for several values of x α . The Dirichlet condition on the boundary are represented in blue line and the Neumann condition in red dotted line. The nodal line is plotted in black. For the Neumann-Dirichlet configuration (see Figure 10(a)), we obtain a 2-partition after symmetrization if x α is too large. If x α is such that x α < y N D (x α ), we obtain a 3-partition whose energy can be reduced by removing the Dirichlet line (Y N D (x α ), X α 0 ) (where Y N D (x α ) is the point of coordinates (y N D (x α ), 0)) in this sub-domain of the partition. We can make a similar analysis in the Dirichlet-Neumann case (see Figure 10(b)).

  a) Neumann-Dirichlet condition.y DN (x α ) > x α y DN (x α ) < x α 2-partition 3-partition (b) Dirichlet-Neumann condition.

Figure 10 :

 10 Figure 10: Examples of nodal partition for the mixed problems.

3 ABFigure 12 :

 312 Figure 11: xND α and xDN α vs. α ∈ {kπ/100, 16 ≤ k ≤ 77}.

Figure 13 :

 13 Figure 13: Best candidates for symmetric 3-partition.

a 3 -

 3 partition with Neumann condition on the symmetry axis {y = 0}, we infer, by the min-max principle, Λ 3 (D α ) ≥ λ N 3 (α), where λ N 3 (α) is the third eigenvalue on Σ + α with Neumann condition on {y = 0} and Dirichlet condition elsewhere. But λ N 3

α and that D 1 2 ( 2 (

 122 ⊂ {y > 0} and D + 3 = D 3 ∩ {y > 0} = ∅. Then the partition D + = (D 1 , D + 3 ) satisfies the Dirichlet-Neumann-Dirichlet problem (c1) and we have then, by the min-max principle, Λ 3 (D) ≥ λ DN D x 0 , x 1 ), with λ DN D x 0 , x 1 ) the second eigenvalue of the Dirichlet-Neumann-Dirichlet Laplacian (c1) on Σ + α . By monotonicity due to the Dirichlet condition and since

Figure 14 :

 14 Figure 14: Symmetric candidate for Σ π/3 .

Figure 15 :

 15 Figure 15: Tiling of the disk with the 3-partition of Figure 14.

Figure 16 :

 16 Figure 16: Double covering of Ω X 0 .

  Figure 17:λ j (( Σ α ) X ), with X = (x N D α , 0), α ∈ { kπ 100 , 16 ≤ k ≤ 76, 1 ≤ j ≤ 7}.

Figure 18 :

 18 Figure 18: Nodal partition associated with λ j(( Σ α ) X ), X = (x N D α , 0), α = kπ 100 , 2 ≤ j ≤ 7.

  ): X ∈ {X k = (1 -k 100 )C ρ + k 100 A ρ , 0 ≤ k ≤ 100}, where C ρ and A ρ are the points of coordinatesC ρ = ρ(cos α 2 , sin α 2 ) and A ρ = ρ(1/ cos α 2 , 0), with ρ ∈ {0.54 + k/50, k = 0, . . . , 6}.Then we catch a 3-partition among the 6-th eigenfunction of the Dirichlet Laplacian on (Σ α ) X . With this method, we obtain, for several values of α, new partitions D AB α better than the minimal symmetric 3-partition D sym α obtained by the mixed Neumann-Dirichlet approach (see Figure20).

Figure 19 :

 19 Figure 19: Localization of the puncturing point for numerical simulations, α = 0.5.

Λ 3 Figure 20 :

 320 Figure 20: Candidates for the minimal 3-partition of Σ α .

7.1 4

 4 Figure 21 illustrates the lower and upper bounds for L 4 (Σ α ): λ 4 (α) ≤ L 4 (Σ α ) ≤ min(λ 1,4 (α), λ 2,2 (α), λ 4,1 (α)).

4 Figure 21 :

 421 Figure 21: Bounds for L 4 (Σ α ).

Figure 22 :

 22 Figure 22: Non minimal 4-partition.

5 Figure 23 :

 523 Figure 23: Bounds for L 5 (Σ α ).

7. 3 6 Figure 24 :

 3624 Figure 24: Bounds for L 6 (Σ α ).

Figure 25 :

 25 Figure 25: Non minimal 6-partitions.

Ackonwledgements.

The authors thank Bernard Helffer for many suggestions and discussions concerning this work. This work was partially supported by the ANR (Agence Nationale de la Recherche), projects GAOS n o ANR-09-BLAN-0037-03 and Optiform n o ANR-12-BS01-0007-02. The first author is grateful to the Mittag-Leffler Institute where this paper was achieved.


Swaminathan Sankaranarayanan
email: s.sankaranarayanan@student.tudelft.nl

Dr Francois Bremond
email: francois.bremond@inria.fr

Dr David Tax

Qualitative Evaluation of Detection and Tracking Performance

A new evaluation approach for detection and tracking systems is presented in this work. Given an algorithm that detects people and simultaneously tracks them, we evaluate its output by considering the complexity of the input scene. Some videos used for the evaluation are recorded using the Kinect sensor which provides for an automated ground truth acquisition system. To analyze the algorithm performance, a number of reasons due to which an algorithm might fail is investigated and quantified over the entire video sequence. A set of features called Scene Complexity measures are obtained for each input frame. The variability in the algorithm performance is modeled by these complexity measures using a polynomial regression model. From the regression statistics, we show that we can compare the performance of two different algorithms and also quantify the relative influence of the scene complexity measures on a given algorithm.

I. INTRODUCTION

The approach to performance evaluation can be majorly classified into two types: Evaluation with ground truth in which case it is performed offline ( [START_REF] Bashir | Performance Evaluation of Object Detection and Tracking Systems[END_REF], [START_REF] Brown | Performance evaluation of surveillance systems under varying conditions[END_REF]) and Online tracker performance evaluation without ground truth ( [START_REF] Wu | Online empirical evaluation of tracking algorithms[END_REF]). Several methods have been proposed to evaluate the tracker performance in either case. The offline performance evaluation remains as a benchmark against which the online methods are compared with respect to accuracy whereas the online performance evaluation does not require any ground truth data which saves a lot of time and labour.

The existing approaches to tracking evaluation have limitations in providing qualitative information about the tracker performance. The metrics used for evaluation at best give out two types of information: how accurate the detection algorithm performs and how consistent the tracker is. They do not address the question of why a tracker has performed poorly (the question of 'why' generally arises in light of poor performance). Consider two tracking algorithms T1,T2 and an input video which has lighting changes over the entire sequence. Only T1 is capable of handling high variations in illumination but in other aspects T2 is much better than T1. In such a scenario, the metrics might report that T1 had performed exceedingly well but it cannot be inferred directly from the metrics why T1 has failed. This paper makes an attempt in providing such qualitative information by pointing out how a tracker performs in the frames that matter. The main contribution of this work is to explain the tracker performance by using a set of Scene Complexity measures that quantify the difficulty of each input frame. In addition, we also attempt to compare different tracking algorithms based on the regression model parameters that is obtained to describe their performance.

The issues faced by any tracking system can be classified into two types based on the input. The failures of the tracker due to occlusion/lighting changes etc., can be attributed to the variation in the input video. The issues that affect the tracker that are independent of the input video can be variation in encoding of the ground truth and limitations of the metrics which measure the tracker performance. This work mainly concentrates on describing how a tracker is affected by the input and compares the results with the stateof-art evaluation metrics used for tracking. The experiments are run on indoor video sequences recorded using the Kinect sensor. The rest of the paper is organized as follows: Section II explains the different approaches taken in the past for formulating ground truth including the methods for overcoming the subjectivity of the formulations. Section III presents the methodology of the proposed evaluation framework. Section IV explains the computation of the various complexity measures.

II. RELATED WORK

With the development of many tracking algorithms over the years, the evaluation of tracking systems has become an important area to concentrate on. Various attempts have been made in the past to evaluate trackers based on spatial and temporal information that is given out by the tracker. The result of the evaluation system is usually a set of numbers based on the output of the algorithm and the metrics. This section surveys the related work in the field of tracking evaluation and states how the current approach can be seen as an improvement. The notation used in this section and the rest of the paper is defined as follows :

• GT refers to the ground truth information • N x refers to the count of x where x can be false positives (f p ), false negatives(f n ), true positives (t p ) or Ground Truth objects(g t ).

• N f rames is the total number of frames in the video sequence for which GT is available.

Bashir et al [START_REF] Bashir | Performance Evaluation of Object Detection and Tracking Systems[END_REF] provide two sets of tracking metrics, Tracker Detection Rate (TRDR) and False Alarm Rate (FAR) which are linear functions of N tp ,N fp and N gt .

Brown et al [START_REF] Brown | Performance evaluation of surveillance systems under varying conditions[END_REF] propose a two pass scheme for matching output tracks and ground truth tracks. In the first pass, many to one association is performed from system tracks to (many) ground truth track(s) (not vice versa) based on temporal and spatial overlap. In phase two, multiple system tracks are matched to each GT track. After the matching procedure, the output metric is given as average spatial and temporal overlap over the entire sequence.

Bernardin et al [START_REF] Bernardin | Evaluating multiple object tracking performance: The CLEAR MOT metrics[END_REF] define a set of metrics for tracking and detection as part of the CLEAR workshop. The tracking performance is expressed by two numbers: "tracking precision", which expresses how well exact positions of objects are estimated, and "tracking accuracy", which shows how many mistakes the tracker made in terms of misses, false positives and mismatches. The mapping procedure makes sure that the Split or Merge errors committed by the tracker are accounted for.

All the above methods evaluate the tracker solely based on the tracker output and do not relate the characteristics of the input video to the tracking algorithm. Nghiem et al [START_REF] Nghiem | A new evaluation approach for video processing algorithms[END_REF] present an evaluation approach in which they derive the upper bound for the algorithm capacity to handle different video processing problems. The most recent approach towards measuring the complexity of the video sequence was done by Chu et al [START_REF] Chu | Thirteen hard cases in visual tracking[END_REF] in their work describing thirteen hard cases for Visual tracking. They provide a very good account of the different factors, which we shall address as failure modes, that affect the tracking performance and have managed to quantify them and compare different trackers based on these factors. The input videos in [START_REF] Chu | Thirteen hard cases in visual tracking[END_REF] are preset videos and each video varies only in one failure mode. The evaluation framework developed in this work measures different complexity measures for any given video and is thus a more general approach to evaluate any tracker.

III. QUALITATIVE EVALUATION FRAMEWORK

We propose an evaluation framework for tracking systems that give out qualitative information about the performance of the tracking system. The reasons for the errors of a detection/tracking algorithm cannot be understood clearly using the available evaluation metrics. The metrics usually quantify the magnitude of the errors being made and not why such errors are made. When the video sequences analyzed are larger in size, an Evaluation system that can point out specific frames that need to be looked at, would come in very handy. To analyze the algorithm's performance over a video sequence, the complexity of the frames has to be quantified. The cases of complexity that are considered in this work are Occlusion, Clutter, Changes in Lighting and Lower Contrast Objects. The following procedure is followed to perform this evaluation :

• The value of an evaluation metric which represents the performance of the algorithm is obtained for each frame. The metric value can be chosen as any of the framewise metrics used for tracking evaluation. For the current work, we choose the Frame Detection Accuracy (FDA) metric, which is defined in [START_REF] Bernardin | Evaluating multiple object tracking performance: The CLEAR MOT metrics[END_REF]. • Scene complexity measures SC i t are computed simultaneously for each frame.

• A polynomial regression model is fit with the metric value as dependent variable and the complexity measures as predictor variables. The model accounts for linear, interaction and quadratic effects.

M Vt = f (SC i t , (SC i t ) 2 , (SC i t * SC j t ))i,j=1..4 (1)
where M V t is the metric value for the frame t and SC i t is the i th Scene Complexity for frame t. Function f represents a polynomial regression equation that accounts for the interaction effects between the predictor variables. The goodness-of-fit of the regression model can be evaluated using the F-score and/or the R-square statistic. Once the regression coefficients are obtained, we can compare them to identify which complexity measure affects the algorithm the most. It should be noted that we cannot expect the regression model to explain the entire variability in the metric values since the list of Complexity measures is by no way exhaustive. The computation of the Complexity measures is explained in detail in the following section.

IV. MEASURES OF COMPLEXITY

A. Occlusion Complexity

An occlusion occurring in the scene can be classified as either Static or Dynamic. A static occlusion is the one in which a moving object in the scene overlaps with a static object, eg. a person overlapping with a piece of furniture. Dynamic occlusion is the one where two moving objects overlap eg. a person overlapping with another.

To measure Static Occlusion effectively, information about static objects in the scene should be provided. In the absence of this, the SOC measure cannot be used. For the current work, we are not considering the complexity that arises due to Static Occlusion.

A Dynamic occlusion situation consists of two mobile overlapping objects, typically two or more persons crossing each other's path in a video. Dynamic Occlusion is measured as the amount of overlap between the Occluding Objects output by the tracking system. When two people cross each other in the scene, it is inevitable that a part of one person is merged with the other. By observing the behavior of some detection systems we found that there are two specific cases which should be considered when computing the Dynamic Occlusion Complexity measure. A simple block diagram representing both the cases are shown in Fig. 1. This is the trivial case of Dynamic Occlusion where the objects in question overlap and hence the complexity measure is a straight-forward computation of the overlap between pairs of objects output by the tracking system for the entire frame. The complexity measure for this case can be formulated as:

M1(t) = 1 N 2 t N t -1 X i=1 N t X j=i+1 Overlap(i, j) areai + areaj ! (2)
where Overlap(i, j) is the common area of the bounding box enclosing the detected objects i and j, area i is the area of the bounding box enclosing detected object i and N t is the number of objects in frame t.

• Case 2: This case involves a situation where the objects occur close enough to each other in a given frame but do not directly overlap. When people walk close enough to each other, this provides enough distraction for the detection algorithm to merge them as a single person.

To account for these errors, we have to compute the Occlusion complexity for the current case as follows:

M2(t) = 1 - 1 N 2 t N t -1 X i=1 N t X j=i+1 |cix -cjx| wi + wj ! (3)
where c ix is the x-coordinate of the centroid of the bounding box enclosing object i and w i is the width of the same bounding box. This Occlusion measure is searched for in both x and y dimensions. The final measure is an arithmetic mean of the Static and Dynamic Occlusion Complexities.

B. Lighting Complexity

Changes in lighting conditions on a given scene presents a tough challenge to any tracking system. There have been several model based approaches in the past that try to predict the pattern in lighting change and find the best fit. We measure the complexity due to lighting changes by analyzing the intensity distribution of the input scene. The difficulty associated by a change in illumination can be analyzed by considering the following:

• A change in illumination between consecutive frames in the video can distract a detection algorithm very much. • The amount of lighting incident on a given frame determines how good the detection algorithm can perform. If the intensity histogram is peaked at the extremes, ie if the lighting is either too high or too low, then most detection approaches cannot deliver a good performance. Fig. 2 gives an example of the case being discussed here. Thus, to measure any illumination change completely both global and local changes have to be accounted for. In addition to this, the inherent complexity of the lighting intensity (peakedness of the histogram) should also be measured. The following procedure is followed to compute the final measure.

The Global change for illumination is measured by computing the mean difference in the intensity values between the grayscale version of the current and the previous images.

The next step is to check for any local changes in illumination using the corrected image from the previous step. To check for local changes in illumination, a given image frame t is split into multiple equally sized patches. These patches traverse the entire image and does not exclude any foreground pixels. For each image patch, an intensity histogram is computed and compared with the histogram of the corresponding image patch in frame t -1. The distance measure used here is the Earthmover's distance (EMD) which has a very good ability to differentiate intensity histograms. Let H t i be the intensity histogram of the patch i. The final measure is computed as follows:

EM D(It, It-1) = 1 N N X i=1 EM D(H t i , H t-1 i ) (4)
The final step is to compute the complexity due to the existing lighting in the image. If the intensity histogram is highly peaked, then it is highly likely that the detection algorithm would fail. To measure this complexity, the kurtosis measure of the intensity histogram is computed.

K(It) = E " " H(It) -µ σ « 4 # (5)

C. Quantifying Clutter

Measuring Clutter is more a subjective problem than a statistical one. It becomes very important in this case to correlate the statistical measure that we obtain to quantify clutter with how it describes the images that are being used. Clutter is a very broad term and it is important to specify what is being measured and hence what is to be expected of such a metric. Clutter can mean either textural changes in foreground or background or even Static or Dynamic occlusion that occurs in the foreground. The Clutter metric used here mainly deals with Variations in Texture. Any scene which is highly textured can be associated with a very high value for clutter. From an object detection perspective, it is very difficult to search for an object (person) in an highly textured environment. Thus, the metric for clutter should typically give higher score to highly cluttered environments and lower scores otherwise.

The metric for measuring Clutter that we have chosen to adopt is from Rosenholtz et al [START_REF] Rosenholtz | Measuring visual clutter[END_REF], who propose a clutter measure using the concept of feature congestion. Their feature congestion clutter measure is based on a Statistical Saliency Model (SSM), which models the degree to which a feature vector T, is an outlier to the local distribution of feature vectors with mean µ and covariance Σ. The saliency is given as follows:

δ = (T -µ) ′ Σ -1 (T -µ) (6)
The clutter value is an aggregate of the saliency values across scales.

D. Complexity due to Low Contrast Objects

The detection algorithm faces a very difficult task when it encounters objects which are very similar in contrast to the background. Not many algorithms are robust to this kind of complexity. A metric used to quantify low contrast object complexity should take into account the contrast level of the detected objects with respect to their neighbourhoods. We start by identifying a region around the each detected object which is a rectangular region bigger than the dimensions of the object. In case of Kinect recording, the detected object is a shape countour and only the relevant pixels are used for contrast computation. In general, the detector output is a rectangular bounding box. The Root Mean Square (RMS) contrast for both the image patches is computed in the three color channels (RGB). The resulting complexity measure for a detected object is the difference in RMS contrast between the object bounding box and its surrounding rectangle. This can be formulated as follows:

CC t = 1 - Nt i=1 (|RM S s -RM S o |) i C max (7)
where RM S o is the RMS contrast of the object, RM S s is the RMS contrast of the region surrounding the bounding box , C max is the maximum intensity value of the corresponding channel and N t is the number of objects in frame t.

V. EXPERIMENTS

The experiments were carried out over two video sequences both of which were recorded using Kinect sensor. Sequence S1 consists of 300 frames with two people walking into a room with changes in lighting and a simple case of occlsuion. Sequence S2 spans over 400 frames in a cluttered room consisting of two people initially and two others crossing the room in the middle of the video presenting a difficult case for occlusion. Three different tracking systems were evaluated on these sequences which can be listed as follows :

• T1 -Processing chain consisting of People Detection from [START_REF] Yao | Fast human detection from videos using covariance features[END_REF] and tracking from [START_REF] Chau | Robust mobile object tracking based on multiple feature similarity and trajectory filtering[END_REF]. • T2 -Raw tracking output from the OpenNi library using the depth map from the Kinect sensor. • T3 -Processing chain consisting of People Detection from [START_REF] Corvee | Haar like and LBP based features for face, head and people detection in video sequences[END_REF] and tracking from [START_REF] Chau | Robust mobile object tracking based on multiple feature similarity and trajectory filtering[END_REF]. As explained earlier, the each tracking system is evaluated using anavailable evaluation metric and the variability in the metric is modeled using a polynomial regression fit. The metric used here is the Frame Detection Accuracy (FDA) which is a framewise measure of the detection accuracy over the successfully tracked objects. We have chosen this metric since it provides a compact representation of both detection inaccuracies and the tracking errors committed by the algorithm. The results we have obtained for the credibility (goodness-of-fit) of the regression models are shown in Figure 3. The results of the MOTP metric ( [START_REF] Bernardin | Evaluating multiple object tracking performance: The CLEAR MOT metrics[END_REF]) for tracking evaluation is shown in Figure 4. It can be seen that the prediction ability of the model is directly related to how erroneous the tracking algorithm performs. Thus we already have a measure which represents the performance of the tracking system on the entire sequence.

It should be noted here that the F-score is the coefficient of determination which is used to evaluate regression models and the r 2 value explains the amount of variation in the dependent variable that the model is able to explain. The polynomial regression model that we use consists of linear, interaction and quadratic terms. Before using the polynomial model, we should identify if all the predictor variables are relevant. To do this, we use the stepwise fitting approach. We start with the empty model and keep adding each predictor variable to the model and continue with the model if a given criterion is achieved. The criterion that we use here is the increase in F-score and its significance. This procedure is performed iteratively until the increase in the F-score is not significant. At the end of this procedure, we end up with the relevant complexity measures for the model.

Let us look at an example which demonstrates this procedure. Consider the evaluation of the output of algorithm T2 on sequence S1. Some frames of interest of sequence S1 are shown in Figure 5. The output data that we have are the FDA metric values for each frame and the four scene complexity measures for each frame which are the predictor variables for our regression model. Figure 3 shows the GoF values for the model using all the predictor variables. If we perform a stepwise regression to select the optimal set of predictor variables, we get the result shown in Figure 6.

The excluded column here (Column 3) is the Clutter Complexity measure. If we perform the polynomial regression fit with the updated model we get the following result: Fscore = 58.75, p ≪ 0.001. Though the F-score is slightly lesser in this case, this is achieved with a lesser number of parameters and the p-value is still very low indicating the credibility of the model is very high. If we look at the adjusted R-square coefficient for the two models, the full model has the value r 2 = 0.72, while the current model has the value r 2 = 0.709. Thus we do not lose any information at all but we have a simpler model now. This step, though not necessary, is generally recommended especially when there is a danger of over-fitting when using many parameters.

We run different regression models using the reduced set of predictor variables which include interaction and quadratic terms. The best possible fit that we obtain that

This model shows that the algorithm is most influenced by the Occlusion complexity measure and slightly influenced by the presence of low contrast objects. The lighting effect was not observed as a significant factor from which we can infer that the algorithm copes quite well with Illumination Changes. For the purpose of comparing two algorithms, we shall run the same procedure for algorithm T3 on the same sequence S1

F DA = 0.19 -0.76 * OC -0.71 * (OC * IC) (9)
The magnitude of the regression coefficients and the terms present in the model equation show how the Scene Complexity measures affect the observed metric values. This prediction was made based on the model parameters and the input video. From the regression equations above, we can see that system T3 is more sensitive to illumination changes and occlusion while system T1 is prone to occlusion and weakly contrast objects but to a lesser extent. The information obtained from the two models can be further visualized by plotting the standard errors of the regression models in both the cases, as shown in Figure 7. We can observe that the model is able to explain the T1 system better than the T3 system. The pointers in the inset show the specific video frames where the model commits large errors. For the T3 system there are two such portions which signifies the portion of the video where Lighting changes and Occlusion occurs. For the T1 system there is only a single region where Occlusion occurs. The relative magnitude of errors are also larger for the T3 system. These results also confirm the predictions that were made earlier using the regression equations. This approach was further tested on longer sequences from the PETS workshops consisting of more than 1000 frames and the fitting accuracy was not as high as we obtained for shorter sequences. The low fitting accuracy does not allow us to make stronger inferences that we could make when we get significantly higher accuracy. This implies that this approach has a limitation when applied over longer and complex sequences where the tracking system commits more errors which are out of scope of the Scene Complexities considered here.

VI. CONCLUSIONS AND FUTURE WORK

The main contribution of this work is the development of an evaluation framework that attempts to provide qualitative information about the tracker failure. We have motivated our choices of the different complexity measures and have modeled the output of the evaluation metrics using the Least Sum of Squares Regression model considering the interaction between the different complexity terms. We have tested our approach on the videos recorded with the Kinect consisting of reasonably difficult cases of the Scene Complexity. We have shown that this approach can successfully explain the output of a tracking algorithm and can also be used to differentiate between different algorithms. The amount of information that we obtain when performing such comparison is much more as compared to traditional evaluation methods. However, the generalization ability of this model based approach is limited by the number of complexity measures that are employed, as seen in the r 2 values in Figure 3. If more complexities such as Camera Motion, Shadow Detection etc are added, the model will then be strong enough to be able to explain the entire variability in the metrics. Furthermore, to overcome the disability of this model to explain longer sequences a cascade based approach could be employed which can be implemented by splitting the longer sequence into several sub-sequences and creating a model for each sub-sequence. The use of only two tracking algorithms does not yet allow us to give a general conclusion about this approach. We intend to address these issues in the future.

Figure 1 :

 1 Figure 1: Different cases when to consider Dynamic Occlusion Complexity

Figure 2 :

 2 Figure 2: Illustration of Global changes in illumination. The image in the middle is the original image. The images at the left and right show peaked intensity version of the original image

Figure 3 :Figure 4 :

 34 Figure 3: Tableshowingthe goodness-of-fit(GoF) measure for the regression models in terms of F-score and its associated r 2 value.

Figure 5 :Figure 6 :

 56 Figure 5: Interest Frames from sequence S1 Step Column Added p-value of model 1 4 4.4e-08 2 1 3.4e-08 3 1 0.01

Figure 7 :

 7 Figure 7: Plot of Errors (vs) Frame Number for algorithms T1 and T3.