Shengping Zhang
email: spzhang@vilab.hit.edu.cn

Hongxun Yao

Shaohui Liu

Dynamic Background Subtraction Based on Local Dependency Histogram *

Traditional background subtraction methods perform poorly when scenes contain dynamic backgrounds such as waving tree, spouting fountain, illumination changes, camera jitters, etc. In this paper, a novel and effective dynamic background subtraction method is presented with three contributions. First, we present a novel local dependency descriptor, called local dependency histogram (LDH), to effectively model the spatial dependencies between a pixel and its neighboring pixels. The spatial dependencies contain substantial evidence for dynamic background subtraction. Second, based on the proposed LDH, an effective approach to dynamic background subtraction is proposed, in which each pixel is modeled as a group of weighted LDHs. Labeling the pixel as foreground or background is done by comparing the new LDH computed in current frame against its model LDHs. The model LDHs are adaptively updated by the new LDH. Finally, unlike traditional approaches which use a fixed threshold to define whether a pixel matches to its model, an adaptive thresholding technique is also proposed. Experimental results on a diverse set of dynamic scenes validate that the proposed method significantly outperforms traditional methods for dynamic background subtraction.

Introduction

Moving objects detection and segmentation from a video sequence is one of the essential tasks in object tracking and video surveillance. A common approach for this task is background subtraction, which first builds an adaptive statistical background model, and then pixels that are unlikely to be generated by this model are labeled as foreground. Despite a large number of background subtraction methods have been proposed in the literature over the past few decades, the task remains challenging when the scenes to be modeled contain dynamic backgrounds such as waving tree, spouting fountain, illumination changes, camera jitters, etc. A robust background subtraction method should work well in these scenes since they are common phenomena in real world. It is always desirable to achieve very high accuracy in the detection of moving objects. The performance of background subtraction depends mainly on the background modeling technique used.

Early approaches operated on the premise that the color of a pixel over time in a static scene could be modeled by a single Gaussian distribution. Wren et al. [START_REF] Wren | Pfinder: Real-time tracking of the human body[END_REF] modeled the color of each pixel with a single three-dimensional Gaussian. Its mean and variance were learned from pixel observations in previous frames. Once the pixel-wise background model was built, the likelihood of each incident pixel generated by this model could be computed. Based on the likelihood, the pixel was labeled as background or foreground. However, a single-Gaussian model is unsuited to most outdoor situations since repetitive object motion, shadows or reflectance often cause multiple pixel colors to belong to the background at each pixel. To overcome the limitations of single-Gaussian model, the mixture of Gaussians (MOG) approach was used to model the complex, non-static scenes [START_REF] Stauffer | Learning patterns of activity using real-time tracking[END_REF]. An incident pixel was compared to every Gaussian distribution in the pixel's model and, if a match (defined by a fixed threshold) was found, the mean and variance of the matched Gaussian distribution was updated, otherwise a new Gaussian distribution with the mean equal to the current pixel color and some initial variance was introduced into the mixture. Each pixel was labeled depending on whether the matched distribution represented the background process. Many authors have proposed improvements and extensions to this algorithm. In Ref. [START_REF] Kaewtrakulpong | An improved adaptive background mixture model for real-time tracking with shadow detection[END_REF], new update algorithms for learning mixture models were presented. In Ref. [START_REF] Zivkovic | Improved adaptive gaussian mixture model for background subtraction[END_REF], not only the parameters but also the number of components of the mixture was adapted for each pixel.

The Gaussian-based methods have an assumption that the pixel color values over time could be modeled by one or multiple Gaussian distributions, however, this assumption does not always hold in the real world. To deal with the limitations of parametric methods, a nonparametric approach to background modeling was proposed in [START_REF] Elgammal | Background and foreground modeling using nonparametric kernel density estimation for visual surveillance[END_REF]. The method utilized a general nonparametric kernel density estimation technique for building a statistical representation of the scene. The probability density function for pixel intensity was estimated directly from the observation data without any assumptions about the underling distributions. In [START_REF] Kim | Background modeling and subtraction by codebook construction[END_REF], a quantization/clustering technique to construct a nonparametric background model was presented. The background was encoded on a pixel by pixel basis and samples at each pixel were clustered into the set of codewords. A similar approach in [START_REF] Yao | Multi-layer background subtraction based on color and texture[END_REF] was proposed, which combined color and texture features by a multi-layer model.

In [START_REF] Karmann | Moving object recognition using an adaptive background memory[END_REF][START_REF] Ridder | Adaptive background estimation and foreground detection using kalmanfiltering[END_REF], each pixel was modeled with a Kalman filter. The method can adapt to changes in illumination, but performs poorly in complex dynamic scenes. This approach was used in the automatic traffic monitoring application presented in [START_REF] Koller | Towards robust automatic traffic scene analysis in real-time[END_REF]. In [START_REF] Mason | Using histogram to detect and tracking objects in color video[END_REF], the dynamic background was modeled by an autoregressive moving average (ARMA) model. A robust Kalman filter algorithm was used to iteratively estimate the intrinsic appearance of the dynamic scenes.

Hidden Markov Models (HMMs) have also been used to model pixel intensity [START_REF] Rittscher | A probabilistic background model for tracking[END_REF][START_REF] Stenger | Topology free hidden markov models: Application to background modeling[END_REF]. In these approaches, the pixel intensity variations were represented as discrete states corresponding to scene modes. In [START_REF] Rittscher | A probabilistic background model for tracking[END_REF], the approach was used in a traffic monitoring application where the pixel states represented the road, vehicles and shadows. In [START_REF] Stenger | Topology free hidden markov models: Application to background modeling[END_REF], HMM states corresponded to global intensity modes each modeled with a single Gaussian distribution. The model was capable of handling sudden illumination changes.

Although the methods mentioned above demonstrated their success cases, their performance will notably deteriorate in the presence of dynamic backgrounds such as waving tree, spouting fountain, illumination changes, camera jitters, etc. There are two causes for this. First, these methods model the background model of a pixel exploiting only its intensity information and ignoring the useful dependencies existing in intensities of neighboring pixels. In dynamic scenes, although some pixels significantly changes over time , they should be considered as background. However, the background models of these methods can not effectively model such changes since they exploit the pixel's intensity information lonely. Second, these methods use a fixed threshold to define whether a pixel matches to its model, which also will result in the notable performance deterioration of these methods since the extents of dynamic changes of different pixels are distinctly different. Using a fixed threshold can not model such difference and it will result in the performance deterioration of these methods.

In order to effectively model the dynamic scenes, in this paper, we present a dynamic background subtraction method that has three contributions. First, we present a novel local dependency descriptor, called Local Dependency Histogram (LDH), which is computed over the region centered on a pixel. The LDH effectively extracts the spatial dependency statistics of the center pixel, which contain substantial evidence for labeling the pixel in dynamic scenes. Second, based on the proposed LDH descriptor, we present a novel dynamic background subtraction method, in which each pixel is modeled as a group of weighted LDHs. Labeling the pixel as foreground or background is done by comparing the new LDH computed in current frame against its model LDHs. The model LDHs are adaptively updated by the new LDH. Finally, unlike traditional approaches which define whether a pixel matches to its model using a fixed threshold, an adaptive thresholding technique is also proposed. The proximity value computed using histograms intersection between the LDH and its model LDH over time is modeled by a Gaussian distribution. The match is defined as the proximity value within 2.5 standard deviations of the Gaussian distribution. The Gaussian distribution is adaptively updated using the proximity value.

The rest of the paper is organized as follows: Section 2 describes the proposed local dependency histogram (LDH). The proposed approach to dynamic background subtraction based on LDH is presented in Section 3. The qualitative and quantitative experimental results and analysis are shown in Section 4, followed by some conclusions in Section 5.

Local Dependency Histogram

Let R be an (2N + 1) × (2N + 1) region. (For simplicity, we assume that the region is square.) The color space is quantized into M levels C M = {0, . . . , M -1}. Let P discretely and regularly index the region lattice,

P = {(x, y)| -N ≤ x ≤ N, -N ≤ y ≤ N }. For a pixel p = (x, y), let C(p) ∈ C M denote its color level.
The center pixel of region R is p = (0, 0). For pixel pair, p i = (x i , y i ) and p j = (x j , y j ) we define two types of distances: 1) d(p i , p j ) = max{|x i -x j |, |y i -y j |}, in which the pixel pair can be along any directions, 2) d ′ (p i , p j ) = max{|x i -x j |, |y i -y j |}, in which the pixel pair is confined to be only along the horizontal or vertical direction. The given distance set is denoted by

D L = {d 0 , . . . , d L-1 }.
For the center pixel p, we define L direct neighboring sets as follows:

P l = { p | d(p, p) = d l }, l = 0, . . . , L -1 . (1)
We denote the pixels that are not in the L direct neighboring sets but in the region R as indirect neighboring set P = P -L-1 l=0 P l . To compute the local dependency histogram, we define two quantities:

h C( p),l = #{ p | C(p) = C(p), p ∈ P l } , (2)
H u,l = #{ (p i , p j )|C(p i ) = u, C(p j ) = u, d ′ (p i , p j ) = d l , p i ∈ P , p j ∈ P } , (3)
where u = 0, . . . , M -1, l = 0, . . . , L -1 and # denotes the number of elements of in the set. The h C( p),l is the total number of pixels that are at distance d l from p along any directions and have the same color with p. It models the direct dependencies between p and its direct neighboring pixels. We call this dependency as direct local dependency. The H u, l is the total number of pixel pairs that have the same color u and are d l apart only along the horizontal or vertical direction in the set P . It models the indirect dependencies of p between its indirect neighboring pixels. We call this dependency as indirect local dependency. These two dependency statistics can be integrated as:

H u, l = H u, l + h C( p),l if u = C(p) H u, l else , (4)
where u = 0, . . . , M -1, l = 0, . . . , L -1. Then, the local dependency histogram H is obtained by arranging the matrix (H u, l ) M ×L as a vector in row-major order. The illustration of the spatial dependencies of the center pixel is shown in Fig. 1.

Dynamic background subtraction based on Local Dependency Histogram

In this section, we introduce our approach to dynamic background subtraction based on local dependency histogram (LDH). The algorithm can be divided into three phases, background modeling, background update and foreground detection, respectively described in Section 3.1, 3.3 and 3.4. The proposed adaptive thresholding technique is presented in Section 3.2.

Background Modeling

There are several advantages of using LDH as statistical descriptor for dynamic background subtraction. First, it explicitly models the spatial dependencies of the center pixel from two aspects: the direct dependencies between the center pixel and its direct neighboring pixels computed by Eq. ( 2) and the indirect dependencies of the center pixel between its indirect neighboring pixels computed by Eq. ( 3). These two kinds of dependencies contain substantial evidence for modeling the background model of the center pixel in dynamic scenes. The former models the dynamic motion of the center pixel due to non-periodic motion. For example, the center pixel in previous frame will be a neighboring pixel in current frame. The latter models the dynamic motion occurring in indirect neighboring pixels, which is also very important for labeling the center pixel [START_REF] Geman | Stochastic relaxation, gibbs distributions, and the bayesian restoration of images[END_REF][START_REF] Li | Markov Random Field Modeling in Computer Vision[END_REF]. For example, the center pixel will not be labeled as background if its indirect neighboring pixels are labeled as foreground. These two kinds of dependencies statistics are then integrated into the histogram statistic, which effectively models the complex dependencies between the pixel and its spatial context. Second, it is not sensitive to noisy since the color space is quantized into less levels. Finally, the computation cost is low, since the pixel pairs in indirect neighboring set are confined to be only along the horizontal or vertical direction.

For a given pixel, let R be an (2N + 1) × (2N + 1) square region centered on the pixel. In the following, we describe the background subtraction procedure for this pixel, and the procedure is identical for each pixel. Since we use LDH computed over the region R as the feature vector of the pixel, we can consider the feature vectors of the pixel over time as a histogram process. At time t, the background of the pixel is modeled by a group of adaptive LDHs {h t,0 , . . . , h t,K-1 }, where K is the number of model histograms. The first B(≤ K) model histograms have been identified as representing the background process in last time instant. Each model histogram has a weight between 0 and 1 such that K weights sum to 1. The weight of the kth model histogram is denoted by ω t,k . It denotes the probability that this model histogram belongs to the background process. Initially, the K model histograms are assigned by the LDH computed at t = 1 with weight 1/K.

An Adaptive Thresholding Method

The LDH of the pixel computed at current frame t + 1, is denoted by h. It is compared against all K model histograms using a proximity measure. The histogram intersection is used to measure the proximity value of two LDHs as follows:

ρ(h 1 , h 2 ) = M -1 i=0 min(h 1,i , h 2,i ) max( M -1 j=0 h 1,j , M -1 j=0 h 2,j ) , (5)
where h 1 and h 2 are two LDHs, and M is the number of histogram bins. The denominator is the maximal value of the sums of all elements in two histograms. It is used to normalize the histogram intersection since the sums of all elements in two different LDHs are different.

K proximity values ρ t,0 , . . . , ρ t,K-1 between h and K model histograms are obtained by Eq. ( 5). Unlike traditional approaches which define whether the pixel matches to its model using a fixed threshold, an adaptive thresholding method is also proposed. We consider the K proximity values over time as K proximity values processes and each such process is modeled by a Gaussian distribution

ρ t,k ∼ N (µ t,k , σ 2 t,k ), k = 0, . . . , K -1.
Initially, for each Gaussian distribution the mean µ is assigned by the proximity value computed at time t = 2 and the σ 2 is assigned by a low initial value σ 2 init . The histogram h matching to the model histogram h t,k is defined as the proximity value ρ t,k within 2.5 standard deviations of the kth Gaussian distribution:

(ρ t,k -µ t,k ) 2 σ 2 t,k < 2.5 2 . ( 6
)

Background Update

The background update consists of three aspects: updating the K model histograms, updating the K Gaussian distributions and updating the background process.

If none of the K model histograms matches to h using Eq. ( 6), the model histogram with the lowest weight is replaced with h and assigned a low initial weight. In our experiments, a value of 0.01 was used. The other model histograms and the K Gaussian distributions keep invariant.

If a model histogram h t,k matches to h, the corresponding Gaussian distribution of the model histogram is updated as follows:

µ t+1,k = (1 -γ)µ t,k + γρ t,k , (7)
σ 2 t+1,k = (1 -γ)σ 2 t,k + γ(ρ t,k -µ t,k ) 2 , (8)
where

γ = α g 1 √ 2πσ t,k e - (ρ t,k -µ t,k ) 2 2σ 2 t,k , (9)
α g is the Gaussian learning rate that controls the update speed of the Gaussian distributions. In all matched model histograms, the best matching model histogram h t,k is selected with the highest proximity value. The h t,k is adapted with the new data by updating its bins as follow:

h t+1,k = α b h + (1 -α b )h t,k , (10)
where α b is a background learning rate. The weights of all K model histograms are updated as follows:

ω t+1,k = α w M t,k +(1-α w )ω t,k , (k = 0, . . . , K-1) , (11)
where α w is a weight learning rate and M t,k is 1 for the best matching model histogram and 0 for the others. The adaptive speed of the background model is controlled by the learning rate α b and α w .

All of the model histograms are not necessarily produced by the background process. The weight of the model histogram is used to decide whether the model histogram models the background process or not. All of the model histograms are sorted in decreasing order according to their weights, and the first B model histograms are selected as the background histograms as follows:

B = arg min b ( b-1 k=0 ω k > T B ), T B ∈ [0, 1] , (12)
where T B is a threshold for measuring the minimum portion of the data that should be accounted for by the background.

Foreground Detection

It should be noted that the B background histograms identified using Eq. 12 in Section 3.3 will be used in next time instant. In current time instant, foreground detection is done before updating the background model. It uses the current B background histograms which were identified in the update step at last time instant. The LDH h is compared against the current B background histograms using the same match definition as in the update algorithm. If the match is found for at least one background histogram, the pixel is labeled as background, otherwise, it is labeled as foreground.

Experimental Results and Analysis

In order to confirm the effectiveness of the proposed method for dynamic scenes, we conduct experiments on a variety of sequences presented in previous literature. The widely used Mixture of Gaussian method (MOG) is used to compare with the proposed method. The comparison is done based on qualitative evaluation by looking at processed images provided by the algorithms, and quantitative evaluation in terms of true positive ratio and false positive ratio.

Qualitative Evaluation

Qualitative results on four sequences of dynamic scenes are presented in this section. The first sequence is the waving tree sequence presented in [START_REF] Toyama | Wallflower: Principles and practice of background maintenance[END_REF]. The tree branches heavily waves in the presence of a strong wind. Fig. 2 shows the comparative results. The first row are the original images, the second row shows the detected foreground by MOG. The detected results by the proposed method are shown in the third row. The fourth row are the masked original images. It is stressed that no morphological operators or median filters were used in the presentation of these results. As shown in Fig. 2, since the dynamic motions caused by waving tree do not repeat exactly, it causes substantial performance degradation of the MOG, which detected a large number of background pixels as foreground and also labeled a huge amount of foreground pixels as background on the inner areas of the moving person. The proposed method dramatically outperforms the MOG, and achieves very high accuracy in the detection of moving person.

Fig. 3 shows some results on fountain sequence from [START_REF] Sheikh | Bayesian modeling of dynamic scenes for object detection[END_REF], which involves three sources of dynamic motion: 1) The spouting fountain, 2) the swaying tree branches above, and 3) the shadow of the trees branches on the grass below. The MOG performs poorly with labeling a large number of background pixels as foreground due to the dynamic motions, especially the spouting fountain in the scene. The proposed method manages the situation relatively well and suppresses most false detection by the MOG. In Fig. 4, results on car sequence presented in [START_REF] Zhang | Spatiotemporal gaussian mixture model to detect moving ojbects in dynamic scenes[END_REF] are shown. This is a very difficult scene from the background modeling point of view since it involves fast moving car, heavily swaying vegetation and large area of illumination changes. The MOG outputs a huge amount of background pixels as foreground. Although the proposed method also misses some foreground pixels, the overall performance of the proposed method is better than the performance of the MOG.

Fig. 5 shows results on moving camera sequence from [START_REF] Sheikh | Bayesian modeling of dynamic scenes for object detection[END_REF], which involved a camera mounted on a tall tripod. The wind caused the tripod to sway back and forth causing motion of the camera. The second row shows the detected foreground by MOG, and it is evident that the motion of the camera causes substantial degradation in performance, despite a five-component mixture model and a relatively high learning rate of 0.05. The proposed method detects the moving car and person accurately.

As shown in the first columns of Fig. 2-Fig. 5, the MOG performs poorly and labels a huge number of background pixels as foreground at the beginning of the sequences which do not include foreground objects. On the other hand, the proposed method handles dynamic motions Table 1. The parameter values of the proposed method for four test sequences.

Parameter

N M D L K α w α b α g T B σ 2 init
Value 9 64 {1, 3, 5} 4 0.01 0.01 0.01 0.8 0.025 immediately and achieves accurate detection at the beginning of the sequences. There are two causes for this: First, the proposed method uses LDH as statistical features which effectively models the spatial dependencies of neighboring pixels. The spatial dependencies provide the substantial evidence for labeling the center pixel and they are exploited to sustain high levels of detection accuracy at the beginning of the sequences. However the MOG exploiting only single pixel's color can not accurately detect the foreground objects at the beginning of the sequences since the MOG need to take longer time to train the background models than the proposed method. Second, the MOG defines whether the pixel match to its model using a fixed threshold, which is unsuited to dynamic scenes since the extents of dynamic motions of different pixels are distinctly different. A fixed threshold can not effectively model such difference and it will cause performance degradation at the beginning of the sequences. The proposed method uses an adaptive thresholding technique, which can achieve accurate detection even if at the beginning of the sequences. The parameter values of the proposed method are given in Table . 1. We did not change the parameter values for four test sequences, although better results could be obtained by customizing the values for each sequence.

Quantitative Evaluation

The performance of the proposed method is also evaluated quantitatively in terms of true positive ratio (TPR) and false positive ratio (FPR): TPR = true positives number of foreground pixels in ground truth ,

FPR = false positives number of background pixels in ground truth ,

where true positives are the number of foreground pixels that are correctly detected, false positives are the number of background pixels that are detected as foreground, and ground truth is the correct detection result and was obtained by manual segmentation.

We first perform quantitative evaluation on waving tree sequence, which has total 287 frames and the person moves across the field of view during 243 th to 258 th frames. The TPR and FPR are shown in Fig. 6. As shown in Fig. 6(b), the proposed method gives lower false positives ratio than the MOG for all 287 frames. Especially for the first 242 frames where there are no moving objects, the proposed method outputs zero false positives and is notable superior to the MOG. In the case of true positive ratio, as shown in Fig. 6(a), compared to the MOG the proposed method performs better for 251 th -255 th frames. For the rest of the 11 frames, the proposed method is inferior to the MOG. It should be noticed that, for the proposed method, most of the missing foreground pixels occur on the contour areas of the moving objects (as seen in Fig. 2). This is because spatial dependency features are extracted from the pixel neighboring. In most applications, the accurate contour information is not need. According to the overall performance shown in Fig. 6, the proposed method outperforms the MOG.

In the moving camera sequence, the scene is empty for the first 276 frames, after which two objects (first a person and then a car) move across the field of view. The sequence contained an average camera motion of approximately 14.66 pixels [START_REF] Sheikh | Bayesian modeling of dynamic scenes for object detection[END_REF]. Fig. 7 shows its quantitative evaluation results. As shown in Fig. 7(a), the proposed method achieves the higher true positive ratio than the MOG. In the case of false positive ratio (shown in Fig. 7(b)), the proposed method outperforms the MOG for the first 276 frames and outputs zero false positives. When the moving objects move across the scene after 276 th frame, the proposed method outputs higher false positive ratio than the MOG. This is because that the proposed method labels a large number background pixels as foreground on the contour areas of the moving objects (see Fig. 5). The overall performance of the proposed method is superior to the MOG.

We also measured the speed of the proposed method on waving tree sequence. The image resolution is 160 × 120 pixels. We used a standard PC with a 3.0 GHz processor and 1 GB of memory in our experiments. The proposed method achieved a frame rate of 15 fps. This makes the method well-suited to applications that require real-time processing.

Conclusions

In this paper, we present a dynamic background subtraction method that has three contributions. First, we present a novel local dependency descriptor, called Local Dependency Histogram (LDH), which is computed over the region centered on a pixel. The LDH effectively extracts the spatial dependency statistics of the center pixel which contain substantial evidence for labeling the pixel in dynamic scenes. Second, based on the proposed LDH descriptor, we present a novel dynamic background subtraction method, in which each pixel is modeled as a group of weighted LDHs. Labeling the pixel as foreground or background is done by comparing the new LDH computed in current frame against its model LDHs. The model LDHs are adaptively updated by the new LDH. Finally, unlike traditional approaches which define whether a pixel matches to its model using a fixed threshold, an adaptive thresholding technique is also proposed. The proximity value computed using histograms intersection between the LDH and its model LDH over time is modeled by a Gaussian distribution. The match is defined as the proximity value within 2.5 standard deviations of the Gaussian distribution. The Gaussian distribution is adaptively updated using the proximity value. Experimental results on a variety of dynamic scenes validate that the proposed method significantly outperforms the widely used Mixture of Gaussian (MOG).

Figure 1 .

 1 Figure 1. Illustration of spatial dependencies of the center pixel with given distance set D 3 = { 1, 3, 5 }. The direct neighboring sets of the center pixel are denoted by gray points. Note that some direct neighboring pixels are denoted by dashed for conveniences. The direct dependencies are denoted by gray arrows which can be along any directions. The indirect neighboring set are denoted by black points and the indirect spatial dependencies are denoted by black arrows which are confined to be only along the horizontal or vertical direction.

Figure 2 .

 2 Figure 2. Experimental results on waving tree sequence. Morphological operators were not used in the results. The top row are the original images: 10 th , 246 th , 248 th , 252 th and 254 th frames. The second row are the results obtained by Mixture of Gaussians method (MOG). The third row are the results obtained by the proposed method, and the fourth row are the masked original images.

Figure 3 .

 3 Figure 3. Experimental results on fountain sequence. The top row are the original frames: 10 th , 597 th , 877 th , 1113 th and 1816 th frames. The second row are the results obtained by Mixture of Gaussians method (MOG). The third row are the results obtained by the proposed method, and the fourth row are the masked original images.

Figure 4 .

 4 Figure 4. Experimental results on car sequence. The top row are the original frames: 10 th , 202 th , 208 th , 216 th and 220 th frames. The second row are the results obtained by Mixture of Gaussians method (MOG). The third row are the results obtained by the proposed method, and the fourth row are the masked original images.

Figure 6 .

 6 Figure 6. Quantitative evaluation results on waving tree sequence. (a) True positive ratio and (b) false positive ratio.

Figure 5 .

 5 Figure 5. Experimental results on moving camera sequence. The top row are the original frames: 10 th , 379 th , 396 th , 421 th and 452 th frames. The second row are the results obtained by Mixture of Gaussians method (MOG). The third row are the results obtained by the proposed method, and the fourth row are the masked original images.

Figure 7 .

 7 Figure 7. Quantitative evaluation results on moving camera sequence. (a) True positive ratio and (b) false positive ratio.

* This work is supported by the National Natural Science Foundation of China (Grant No 60775024) and New Century Excellent Talents in University (NCET-05-03-34).


Henri Eberspächer
email: henri.eberspacher@pucpr.br

Michelle Joab

Using roles, rules and contracts to promote group collaboration

Keywords: Role-based collaboration, rule-based contract, collaborative learning

In this paper we introduce Virtus, a web-based platform that provides enhanced functionalities to automate the management of users, groups and virtual communities using an expert rule-based system. Virtus supports collaborative learning using a group contract by automating the execution of the rules of the contract. The originality of our work consists, on the one hand, in proposing a declarative language to express contracts using declarative rules, commitments and role responsibilities assigned to members of a group or participants of a community and, on the other hand, in automatically executing the contract, implemented by an expert system. Once the contract is defined, it is translated into an executable rule language. Periodically, Virtus platform extracts information from the virtual environment and activates a knowledge-based system for each group.

Introduction

Virtual communities with learning or working (or both) purposes generally use collaborative learning and cooperative work in order to improve the benefits of learning/working together and to improve the effectiveness of the social interaction. A community whose organization and methods are based on these techniques normally obtains better results than the ones where individuals are working by themselves [START_REF] Dillenbourg | The evolution of research on collaborative learning[END_REF].

In this direction, we propose a contract model with a role-based coordination approach to support individual and group management in collaborative learning activities. The main idea is to create a contract that can be used to automate some substantial administration work and to both create and maintain mutual commitments between users and their working groups. Our aim is to increase individual and collective efficiency adding an automatic management service which reminds the users their commitments in a personalized way and applies the terms of the contract [START_REF] Eberspächer | Virtus: group support using role-based collaboration[END_REF]. By using explicit contracts in collaborative learning scenarios we intend to encourage the users to commit themselves in the learning process [START_REF] Eberspächer | An Intelligent Web-Based Learning System for Group Collaboration Using Contracts[END_REF]. By defining roles within groups, responsibilities between members can be shared. This sharing is established through the contract, which describes the responsibilities and formalizes the rights and duties of each role.

Virtus platform

The Virtus platform consists of two modules: VirtusWeb which manages the services of the on-line environment (like usual LMS or Groupware systems) and VirtusCharte which implements an Intelligent Support System to support users following the rules of the contract. This means that the Virtus platform supplies a regulation and monitoring mechanism for group activities based on the concepts of contract (a set of rules) and roles. This mechanism is fully configurable through the rules expressed in the proposed contract language using freely defined roles. VirtusCharte is based primarily on an intelligent tool that will automatically support collaborative work using VirtusWeb.

The key point is the dynamic process between VirtusWeb, where users are performing activities and VirtusCharte, which monitors the way the members honor their commitments. The regulation mechanism of VirtusCharte is based on the relation between rules and roles. Rules mean a guideline, a formula that indicates what needs to be done within a certain context. Roles mean that each person is identified with a role, so that he/she can quickly identify his/her participation, prerogatives and commitments. A role is a set of requirements that define how a member should behave in a group [START_REF] Zhu | Role Mechanisms in Collaborative Systems[END_REF]. The assigned user's roles indicate the responsibilities and expected actions of each group member. The rules could question the work carried out by other roles or those that are performed outside the specified time constraints.

Using the charter, the users will benefit from an automatic group management support mechanism. As a human user, VirtusCharte may act on VirtusWeb working environment and could also recall the users' commitments by sending notifications. These actions and/or notifications are obviously a consequence of the group charter execution. To avoid black box behavior, VirtusCharte actions are emphasized as executed by a virtual user.

Conclusions

We have designed and implemented a software component to automate the execution of a contract. The Virtus Platform is composed of VirtusWeb which manages the contexts and services of the learning environment and of VirtusCharte which reasons automatically in terms of the rules of the contract [START_REF] Eberspächer | An Intelligent Web-Based Learning System for Group Collaboration Using Contracts[END_REF]. The regulation and follow-up mechanism is based on the concepts of rules, role and contracts. This contract, freely discussed in the group and then adopted, boosts the commitment of members for the tasks ahead [START_REF] Zhu | Role Mechanisms in Collaborative Systems[END_REF].

VirtusCharte run the contract and monitor how the members of the group comply with the terms of the contract when performing cooperative work. For further developments, our aim is turn Virtus in an adaptive environment [START_REF] Brusilovsky | Adaptive and intelligent Web-based educational systems[END_REF] in the sense that Virtus could propose modifications to the contract in order to be more in line with the members' behavior.


Kris M Kitani
email: kitani@iis.u-tokyo.ac.jp

Takahiro Okabe
email: takahiro@iis.u-tokyo.ac.jp

Yoichi Sato
email: ysato@iis.u-tokyo.ac.jp

Akihiro Sugimoto
email: sugimoto@nii.ac.jp

Discovering Primitive Action Categories by Leveraging Relevant Visual Context

Under the bag-of-features framework we aim to learn primitive action categories from video without supervision by leveraging relevant visual context in addition to motion features. We define visual context as the appearance of the entire scene including the actor, related objects and relevant background features. To leverage visual context along with motion features, we learn a bi-modal latent variable model to discover action categories without supervision. Our experiments show that the combination of relevant visual context and motion features improves the performance of action discovery. Furthermore, we show that our method is able to leverage relevant visual features for action discovery despite the presence of irrelevant background objects.

Introduction

We present a novel framework for the unsupervised learning of primitive human actions from a video corpus by leveraging visual context, where we define visual context as the appearance of the entire scene including the actor, related objects and relevant background features. Since actions can be understood at various temporal resolutions, we focus on the discovery of what we call primitive actions. Primitive actions are human actions that can be defined over a very short period of time (a few seconds). For example, grabbing a cup, typing on a keyboard or flipping the page of a book can be recognized within a few seconds of observing the action. Learning primitive actions are important because they are the basic building blocks of many highlevel activities [START_REF] Moore | Recognizing multitasked activities from video using stochastic context-free grammar[END_REF][START_REF] Hamid | Detection and explanation of anomalous activities: Representing activities as bags of event n-grams[END_REF][START_REF] Kitani | Recovering the basic structure of human activities from a video-based symbol string[END_REF]. Supervised learning techniques using such models as HMMs [START_REF] Starner | Real-time American sign language recognition from video using hidden Markov models[END_REF][START_REF] Ivanov | Recognition of visual activities and interactions by stochastic parsing[END_REF], Bayesian classifiers [START_REF] Shi | Propagation networks for recognition of partially ordered sequential action[END_REF] and temporal dynamics [START_REF] Siskind | Visual event classification via force dynamics[END_REF] have been successful in describing primitive actions but need labeled data or a considerable amount of prior knowledge. While most of these past works have used supervised approaches to learn primitive actions, there have also been several recent works focused on the unsupervised learning of actions.

An approach of growing interest for unsupervised topic discovery is the use of generative latent variable models (mixture models [START_REF] Nigam | Text classification from labeled and unlabeled documents using EM[END_REF], pLSA [START_REF] Hofmann | Probabilistic latent semantic analysis[END_REF], LDA [START_REF] Blei | Latent Dirichlet allocation[END_REF], HDP [START_REF] Teh | Hierarchical Dirichlet processes[END_REF]) based on the bag-of-words paradigm. Most of these methods were originally applied to text processing to learn topics from text in documents. Given the document analogy, a typical language model factorizes the observed documents (corpus items) and words (features) to discover a distribution over a set of hidden topics.

Niebles [START_REF] Niebles | Unsupervised learning of human action categories using spatial-temporal words[END_REF] proposed the application of a generative model to video to learn action categories (topics) from a bag-of-features. They used exactly the same framework as [START_REF] Hofmann | Probabilistic latent semantic analysis[END_REF] by simply replacing document indices with video indices, and words with spatial-temporal (ST) volumes. Their approach showed that similar to text, the local features of an action can be treated as though they were exchangeable (an action can be treated as a bag of uncorrelated features) to learn action categories. However, the conceptual problem with a straightforward use of a language model for action discovery is that the models are uni-modal (e.g. use only words or ST features).

We know from experience that many actions are composed of motions and visual appearance. For example, the hands of a person playing a piano and typing on a keyboard might have very similar motions but can easily be differentiated using the visual context of a piano or a keyboard. In fact, findings from neural science show that actions are mentally perceived as a mix of motions and visual features of present objects [START_REF] Fagg | Modeling parietal-premotor interactions in primate control of grasping[END_REF]. In the light of this fact, many previous approaches to action discovery are limited by the fact that they only consider actions defined strictly by motion. For example, the ST volumes used to describe dynamic human actions in [START_REF] Niebles | Unsupervised learning of human action categories using spatial-temporal words[END_REF] are robust against static spatial features but are also insensitive to visual features produced by related static objects in the scene. Similarly, the approach proposed by Wang [START_REF] Wang | Unsupervised activity perception by hierarchical Bayesian models[END_REF] to automatically classify actions of cars and pedestrians at an intersection uses the change in pixel intensity between two frames as the input feature, making their system robust to the varying color and shape of automobiles and pedestrians. However, to apply their current system to actions that involve interactions between actors and objects will most likely necessitate the incorporation of more complex motion features and appearance features to improve performance.

While the joint use of appearance and motion to describe action is not entirely new, our work differs from previous work in that we leverage appearance information without the use a priori information about the shape or color of actors or objects in the scene. Work using the appearance of related objects to recognize actions has depended on a priori knowledge of the appearance of related objects [START_REF] Gupta | Objects in action: An approach for combining action understanding and object perception[END_REF] or pre-defined object categories [START_REF] Moore | Exploiting human actions and object context for recognition tasks[END_REF].

Work leveraging the appearance of the actor, such as Fanti [START_REF] Fanti | Hybrid models for human motion recognition[END_REF] and Niebles [START_REF] Niebles | A hierarchical model of shape and appearance for human action classification[END_REF], has proposed modified generative models that model the human body and account for both the appearance and motion of body parts. However, explicitly modeling the human body comes at the cost of losing the ability to apply the model to other types of actors. The more important distinction with our work however, is that the use of visual information was limited to pre-defined body parts and therefore could not explicitly take into account other relevant visual information possibly generated by co-occurring objects or scenic context.

In this work, we present a robust framework for primitive action discovery by leveraging both motion and relevant visual context without the use of a priori information (e.g. an explicit shape model or pre-defined object categories). Our experiments show that our method properly leverages relevant visual appearance and is robust against irrelevant visual features (Figure 1) when learning action categories.

Proposed method

Our goal is to learn the primitive action categories that occur within a video corpus. First we extract temporal features and spatial features from each video segment, under the assumption that actions are defined by both temporal motion and visual context (Section 2.1). Then we describe a dimension reduction process to create a codebook for each feature type (Section 2.2). Finally we describe the bi-modal latent variable model that uses the histograms produced by motion and visual context to learn the latent action categories (Section 2.3).

Extracting spatial and temporal features

Here we begin by explaining how spatial (visual) features and temporal (motion) features are extracted. For each frame in the training corpus, we extract a sparse set of spatial features by finding SIFT keypoints [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF]. These keypoints are then represented with a normalized 128-d SIFT descriptor. Other combinations of keypoint detectors and descriptors can be used as well.

Using the same temporal gradient descriptor as [START_REF] Boiman | Detecting irregularities in images and in video[END_REF], a set of temporal features are extracted from the video frames by extracting a 7 × 7 × 4 (a 7 × 7 spatial window over 4 frames) spatio-temporal volume for pixels detected as a good feature to track [START_REF] Shi | Good features to track[END_REF]. Each element of the volume contains the temporal gradient magnitude. The descriptor is a normalized 196-d vector containing the elements of the volume. More complex temporal keypoints can also be used, such as spatio-temporal cuboids [START_REF] Dollár | Behavior recognition via sparse spatio-temporal features[END_REF] or space-time interest points [START_REF] Laptev | On space-time interest points[END_REF].

Feature clustering

For each mode (temporal and spatial) we first implement the standard k-means clustering algorithm to roughly cluster the features and produce the codebook C. A feature histogram v d for each video segment d in the corpus d is created by assigning each extracted feature to the closest cluster. This process yields a set of histograms

V = (v 1 , • • • , v m )
, where m = |d|. We then further reduce the dimensionality of the histograms using a more holistic approach, namely, non-negative matrix factorization (NMF) [START_REF] Lee | Learning the parts of objects by non-negative matrix factorization[END_REF] which projects the set of histograms V onto a lower dimensional non-negative subspace H. Since we assume that actions are additive (actions only produce features and never delete features), we use NMF over other projection techniques like PCA or ICA because NMF decomposes the data V as an additive (non-negative) combination of a lower dimensional basis subspace. It is interesting to note that both pLSA and NMF have been shown to be instances of multinomial PCA [START_REF] Buntine | Variational extensions to EM and multinomial PCA[END_REF]. In fact in our framework, the projected dimensions of NMF r and the number of hidden categories q are set to be equivalent and as a consequence this second stage can also be interpreted to be the pre-discovery of hidden actions categories for each independent modality of input. Formally, NMF decomposes the k × m histogram matrix V (each column v i is a k dimensional histogram of features for the i-th video) into a k ×r basis matrix W and the r ×m encoding matrix H, V ≈ WH.

(

We use the projected gradient method [START_REF] Lin | Projected gradient methods for nonnegative matrix factorization[END_REF] to factorize V and the resulting columns of the encoding matrix H contain the reduced (encoded) version of V.

As with k-means clustering, we run NMF twice independently, once for spatial features and once for temporal features, by projecting the spatial and temporal descriptor histogram matrices V s and V t onto the reduced dimensional spaces H s and H t , respectively. That is, NMF maps a histogram v i from each video segment to a reduced dimensional histogram h i . As a result, the values of H s and H t yield an approximation to the term-by-document frequency matrix. The term-by-document frequency matrix is commonly used as the input for learning language models, where each element n(w, d) of the matrix represents the number of times a feature w was observed in the corpus item d.

Merging motion and visual context via the action model

Parameter learning

Under the framework of Bayesian networks, the joint probability of a set of random variables can be simplified by defining the conditional independence between variables.

In our action model (Fig. 2), we assume that temporal features t are conditionally independent of spatial features s given latent action categories z. That is, we propose a bi-modal expansion of the standard mixture of uni-grams model [START_REF] Nigam | Text classification from labeled and unlabeled documents using EM[END_REF] and define the probability of a video segment d ∈ d as below.

p(d) = z p(d|z)p(z) (2) p(d|z) ∝ s∈d p(s|z) t∈d p(t|z) (3) = s p(s|z) n(s,d) t p(t|z) n(t,d) (4)
Based on the conditional independence of a spatial feature s and a temporal feature t given the latent topic z, the conditional probability of a video segment can be computed as the product of the conditional probabilities of all spatial and temporal features in the video segment. The term n(s, d) represents the number of times a spatial feature s has occurred in a video segment d. The term n(t, d) is interpreted similarly for temporal features.

To learn the parameters of the bi-modal mixture model, we desire to find values for the parameters p(s|z), p(t|z) and p(z), such that the log-likelihood of the entire video corpus d is maximized.

log p(d) = d log z p(d|z)p(z) (5)
We implement the expectation maximization (EM) algorithm to find a locally optimal set of parameters. Since it can be shown the lower bound of the data likelihood can be maximized by equivalently maximizing the expectation of the complete log-likelihood E[L c ] over the posterior p(z|d), we maximize the following function.

E[L c ] = d z p(z|d) log p(d|z)p(z) (6)
In the expectation step, the posterior of the latent variable is computed using Bayes' rule.

p(z|d) = p(d|z)p(z) z p(d|z )p(z ) (7)
By solving for the maxima of the Lagrangian function, which is composed of the complete data log-likelihood and standard conditions on the parameters (i.e. probabilities add to one), we obtain the following re-estimation equations for the maximization step. These re-estimation equations maximize the likelihood of the data given the current posterior.

p(s|z) = d n(s, d)p(z|d) s d n(s, d)p(z|d) (8) p(t|z) = d n(t, d)p(z|d) t d n(t, d)p(z|d) (9) p(z) = d p(z|d) |d| ( 10
)
This process between the expectation step and the maximization step is repeated until the log-likelihood function converges at a maximum.

Inference and recognition

Although recognition is not the focus of this paper, once the parameters of the model have been learned, the naive Bayes model can also be used to recognize primitive actions. Specifically, given a test video segment d, a set of temporal and spatial features are extracted and binned to create a histogram of temporal and spatial features,v t d and v s d respectively. Then the histograms are projected onto the respective encoding spaces to obtain the encoding vectors h t d and h s d using the zeroed least-square solution [START_REF] Okun | Fast nonnegative matrix factorization and its application for protein fold recognition[END_REF]. By normalizing the vectors h t d and h s d we obtain the distribution over the features t d and s d for the test video segment. These distributions are then passed on as likelihood evidence for the naive Bayes model to infer the distribution over the hidden actions p(z|d) using belief propagation [START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF].

Experiments

Publicly available datasets used for human action recognition, like the KTH dataset [START_REF] Schuldt | Recognizing human actions: A local SVM approach[END_REF], have very little background variation (i.e. a wall or a field) and usually involve only actors with no interactive objects [START_REF] Dollár | Behavior recognition via sparse spatio-temporal features[END_REF][START_REF] Blank | Actions as space-time shapes[END_REF][START_REF] Wong | Learning motion categories using both semantic and structural information[END_REF]]. Here we present three new primitive action video datasets, created to include various backgrounds and interactive objects. These datasets are needed to show how our method is able to leverage relevant visual features along with motion information to effectively discover action categories.

Video datasets

Actions with objects corpus

The first motion and object corpus C OBJ consists of eight different primitive actions that involve a related physical object. A list is given below: was 90 frames long and all videos were created at a resolution of 160×120. Notice that all of the actions are repetitive and sometimes involve the same object. Key frames from the corpus are given in Figure 3.

Actions with backgrounds corpus

The motion and background corpus C BG consists of three different motions and three different visual scenes (backgrounds). The three motions are:

1. Take (vertical movement) 2. Wipe (horizontal movement) 3. Open (hand opens and closes in place)

The three background scenes are: The combination of movement and scenes yields nine different actions. Five videos segments for each action resulted in a corpus of 45 videos. Each video segment was 90 frames long and all videos were created at a resolution of 160 × 120. Key frames of several combinations of motions and visual contexts are given in Figure 4.

Actions with objects and backgrounds corpus

The motion with objects and background corpus C BGOB contains the same actions as the first corpus C OBJ but also includes random backgrounds (Figure 5), which act as visual noise. The visual appearance of each video segment was varied by including different random objects in the background. This corpus used the same number of video segments and the same resolution as the first corpus C OBJ .

Experimental setup and results

First, we performed one baseline experiment using the same uni-modal generative model as [START_REF] Niebles | Unsupervised learning of human action categories using spatial-temporal words[END_REF]. Then we performed three experiments using our new framework to show how leveraging visual context improves learning performance.

For each experiment the codebook was generated using k-means clustering, where k = 1500, the stop criteria was a cumulative displacement of cluster centers less than 1, the maximum number of iterations was 10 and distance was measured using the L 2 -norm. We note that similar results were achieved for k within the range of 500 to 3000. To initialize the encoding matrix H for NMF near an optimal solution, we clustered the data into r clusters to compute the initial values. That is, the set of histograms V were clustered with k-means clustering using the top eight principle components (via PCA) of the histograms. For each column in H, the element representing the nearest cluster was set to one and all other entries were set to random nonnegative proper fractions. While in practice the final encoding matrix H is non-zero, zero values can be prevented using Laplacian smoothing [START_REF] Nigam | Text classification from labeled and unlabeled documents using EM[END_REF].

Likewise, to initialize the EM process of the bi-modal mixture model near an optimal solution, the initial values of p(z|d) are set using the results of NMF, namely, the normalized values of the encoding matrix H of one of the modes.

For each experiment, the number of action categories r and q are provided as prior knowledge but can also be The speed of the algorithm depends on the content of the video. That being said, our algorithm on average used about 3.9 minutes to process 1 minute of video (30 fps) using a dual core 3.2 GHz CPU. On average 81.1% of the processing time was used for feature extraction, 18.8% was used for clustering and 0.1% was used for learning the bimodal model. The computational cost can be significantly reduced by parallelizing feature extraction and using online counterparts for clustering.

Results using only temporal features

We first performed a baseline experiment with pLSA [START_REF] Niebles | Unsupervised learning of human action categories using spatial-temporal words[END_REF] using only temporal gradient features. A bar graph of the posterior probabilities p(z|d) (the probability of a latent action category z given the video segment d) computed by pLSA is shown in Figure 6. We also show the average of the posterior probabilities for each true action category in Table 1. A single row of the table is created by taking the average of the posterior probability distributions of a group of video segments from the same action. The columns of the table are ordered in such a way that maximizes the mean of the diagonal elements. We use the mean of the diagonal elements as a measure of performance, which we call the probability of correct categorization (PCC). We use this measure instead of the standard AUC measure because the AUC values for the following experiments are non-informative (i.e. they are all equal to 1).

The PCC of the motion and object corpus C OBJ was 72%. The low level of performance was expected since the simple temporal gradient descriptors only capture motion and they are not invariant to scale or rotation. Nevertheless, the point is that the descriptive power of the temporal features was not sufficient to properly categorize primitive actions involving static objects. This will be true for any temporal feature descriptor based on temporal extrema.

Learning actions using objects

Next we used our method to learn action categories from the same motion and object corpus C OBJ . We observe from the bar graph of the posterior probabilities (Figure 7) that all actions contained in the video corpus have been given a high probability for the correct action category. The PCC of the corpus C OBJ was 99.89%. By leveraging the visual appearance of the action and related objects, we significantly increased performance.

Learning actions using background appearance

The assumption of our approach is that visual context is relevant when it is constantly observed with a certain motion. We used the action and background corpus C BG and tested whether our method was able to distinguish between actions with very similar motions, that can only be differentiated by their visual context. That is, given a video corpus containing three different motions performed in three different environments, can our method discover nine unique actions from the database? The resulting posteriors p(z|d) are given in Figure 8. Notice that each combination of visual context and motion was given a high probability for separate categories. The PCC of the corpus was 94.95%. For this corpus, the visual features induced by the combination of motion and background appearance enabled the system to differentiate the nine different action categories.

As mentioned earlier, we assume that visual context is relevant when it is constantly observed with a certain motion. We note here that our system will have problems when the number of irrelevant background types is less than the number of motion types in the database. That is, if a certain motion is frequently observed in front of the same unrelated object, our proposed method will include those visual features as part of the primitive action. In most cases, this should not be a problem given a sufficiently sized database generated over various backgrounds.

Learning actions using relevant visual context

In reality, primitive actions occur in various types of visual contexts and it is important to be able to leverage only the relevant visual features that should be associated with an action (Figure 1). In this experiment, we apply our proposed method to the motion with object and background corpus C BGOB and show how our method can leverage relevant visual features to discover action categories, even with various cluttered backgrounds.

Our results show that our proposed approach properly discovered the action categories of the corpus C BGOB by assigning high probabilities to the correct action category. The PCC was 99.38% (computed from the posterior probabilities in Figure 9). We were able to obtain good results despite the visual noise generated by the different background objects because the relevant visual features had a stronger signature (occurred more often) in the histograms; a trait of the data which was preserved by NMF. The information gained from the relevant visual features was then used by the bi-modal model to effectively discover all of the latent primitive action categories.

Conclusion

We have proposed a novel framework for discovering action categories by leveraging relevant visual context. To leverage visual context, we implemented a two stage clustering process via k-means clustering and non-negative matrix factorization, to generate two term-by-document matrices as the input to the bi-modal mixture model. The bimodal mixture model used both visual features and temporal features to discover latent action categories. Our experiments showed that our approach is able to accurately categorize actions by leveraging relevant visual context to disambiguate similar motions. It was also shown that our method is robust against irrelevant visual features generated by the background while at the same time leveraging relevant visual context to accurately discover primitive action categories.

Figure 1 .

 1 Figure 1. Leveraging visual features for action recognition: Relevant visual features (green) induced by using the telephone and irrelevant features (purple) produced by unrelated background objects.

Figure 2 .

 2 Figure 2. Bi-modal latent variable model defined by the latent topic z, spatial features s and temporal features t.

1 .Figure 3 .

 13 Figure 3. Key frames for the corpus C OBJ with 8 desktop actions involving objects.

Figure 4 .

 4 Figure 4. Examples from corpus C BG with 9 actions including 3 different motions and 3 different background objects. Direction of motion is shown in white.

Figure 5 .

 5 Figure 5. Examples from corpus C BGOB with 8 different actions with objects and varied random background objects for each video segment.

Figure 6 .

 6 Figure 6. Baseline results: pLSA using only temporal features for corpus C OBJ . The horizontal axes gives the ground truth for each video d and the discovered action category z. The vertical axis is the posterior probability p(z|d).

Figure 7 .

 7 Figure 7. The resulting posterior p(z|d) of corpus C OBJ containing 8 different actions.

Figure 8 .

 8 Figure 8. The resulting posterior p(z|d) of corpus C BG containing 3 motions and 3 backgrounds.

Figure 9 .

 9 Figure 9. The resulting posterior p(z|d) of corpus C BGOB containing 8 actions observed over 45 various messy desktop environments.

Table 1 . Average posterior probabilities for each action category using only temporal features.

 1

				Discovered Actions (z)
		2	4	5	8	6	1	3	7
	Touch-key	0.97	0.01	0.02	0.00	0.00	0.00	0.00	0.00
	Begin-key	0.02	0.82	0.05	0.09	0.01	0.01	0.00	0.00
	Dial-phone	0.02	0.00	0.97	0.00	0.00	0.00	0.00	0.00
	Flip-page	0.00	0.00	0.00	0.53	0.03	0.40	0.00	0.03
	Skim-page	0.00	0.00	0.02	0.00	0.96	0.00	0.00	0.01
	Write-paper	0.01	0.48	0.27	0.09	0.03	0.01	0.00	0.11
	Sift-paper	0.01	0.01	0.01	0.02	0.00	0.01	0.94	0.00
	Take-cup	0.00	0.00	0.03	0.40	0.00	0.00	0.00	0.56
	learned using a model selection criterion.

Acknowledgments

This work was partially supported by Grant-in-Aid for Scientific Research (B) (20300061) of the Ministry of Education, Culture, Sports, Science and Technology of Japan.


Olivier Lindamulage De Silva
email: olivier.lindamulage-de-silva@univ-lorraine.fr

Samson Lasaulce

Irinel-Constantin Morȃrescu

On the efficiency of decentralized epidemic management and application to Covid-19 *

Keywords: Game theory, Nash equilibrium, Epidemic, SIR, Covid-19

In this paper, we introduce a game that allows one to assess the potential loss of efficiency induced by a decentralized control or local management of a global epidemic. Each player typically represents a region or a country which is assumed to choose its control action to implement a tradeoff between socioeconomic aspects and the health aspect. We conduct the Nash equilibrium analysis of this game. Since the analysis is not trivial in general, sufficient conditions for existence and uniqueness are provided. Then we quantify through numerical results the loss induced by decentralization, measured in terms of price of anarchy (PoA) and price of connectedness (PoC). These results allow one to clearly identify scenarios where decentralization is acceptable or not regarding to the retained global efficiency measures.

I. INTRODUCTION

I N 2020, many governments around the world had to take drastic measures to mitigate the propagation of the SARS-Cov2 virus. Especially over the first half of 2020, similar measures were taken over large geographical areas such as countries. One major drawback from implementing such a (uniform) policy was that there has been a mismatch between the measure severity level and the local situation. Among the consequences of this mismatch we find: avoidable local economic losses, potentially avoidable psychological damages, frustration, and thus a degradation in terms of measure effectiveness. In 2021, the experience acquired on the pandemic shows that allowing regions (e.g., provinces in China, states in the USA, Länder in Germany, or regions in France) to locally adjust the decisions may be more suited. This is also true when it comes to vaccination. Consequently, different countries adopted different control strategies prioritizing aspects such as education, social welfare, economy, or health. Also within a given country the measures implemented were different for regions depending on the local situation. These measures have been aiming at achieving a certain tradeoff between socio-economic aspects and health aspects. Motivated by this observation, we propose a mathematical model to analyze the effects of decentralization on the epidemic management. In this context, each region or country is a decision-maker. The proposed model is built on existing models such as the networked epidemic models [START_REF] Pastor-Satorras | Epidemic processes in complex networks[END_REF], [START_REF] Stella | The role of asymptomatic individuals in the Covid-19 pandemic via complex networks[END_REF], [START_REF] Kephart | Directed-graph epidemiological models of computer viruses[END_REF], [START_REF] Mesbahi | Graph theoretic methods in multiagent networks[END_REF]Chapter 9.3]. To assess the potential efficiency loss induced by decentralizing the epidemic management, we consider a mathematical model that is relatively simple while capturing the main effects of interest. This paper considers a strategic-form game which is built from a networked Susceptible-Infected-Recovered (SIR) compartmental model [START_REF] Magal | Final size of an epidemic for a two-group SIR model[END_REF], [START_REF] Mei | On the dynamics of deterministic epidemic propagation over networks[END_REF]. Precisely, we consider a game where each player represents a geographical area which decides social-distancing rules which aim at minimizing a cost; this area may typically correspond to a country or a region of a country but it can also correspond to a metropolis or a group of countries. Each individual cost implements a given trade-off between socio-economic losses and health losses. Indeed, the value of the cost for each region not only depend on its actions but also on the actions of neighboring regions through the network structure and the epidemic dynamics. It is noteworthy that the proposed game model is a static or oneshot game model; a player chooses a control action which is fixed over a given finite time horizon. In practice, this action would need to be updated for each epidemic phase. Moreover, each region is assumed to have its own virus transmission rate (e.g., depending on local population density, weather conditions, the effectiveness level of the taken measures); the propagation among regions occurs with an intensity which is given by the cross transmission rates (e.g., depending on the geographic mobility among regions, the sanitary rules imposed by the corresponding neighbors); the population of each node recovers with a fixed recovery rate (e.g., depending on the capacity and performance of the health system [START_REF] Hota | A closed-loop framework for inference, prediction and control of SIR epidemics on networks[END_REF]). To the best of our knowledge, the game we introduce in this paper differs from existing works for several reasons. In [START_REF] Elie | Contact rate epidemic control of COVID-19: an equilibrium view[END_REF], the players are the individuals but their decision consist in controlling social distancing with others to find a balance between social interactions and the chances of being infected by the virus that spreads through a single region SIR model. The main differences between the present work and the existing results on networked epidemic games (e.g., [START_REF] Hota | Game-theoretic vaccination against networked SIS epidemics and impacts of human decision-making[END_REF], [START_REF] Omic | Protecting against network infections: A game theoretic perspective[END_REF], [START_REF] Hayel | Complete game-theoretic characterization of SIS epidemics protection strategies[END_REF], [START_REF] Trajanovski | Decentralized protection strategies against SIS epidemics in networks[END_REF]) can be summarized as follows: we consider an SIR model while the existing game models are applied to the networked SIS model (Susceptible-Infected-Susceptible); we control the inter-regions transmission rates while the existing works consider networks described by a binary adjacency matrix; we propose a one-shot game over a finite time horizon unlike the existing works consider infinite time games with constant actions.

Our key contributions can be summarized as follows:

• We formulate a strategic form game applied to a networked SIR model, in which: the interactions are described by a weighted adjacency matrix; a player is a node of the network that tries to minimize its own cost capturing a tradeoff between the socio-economic and health losses; the decision of each player affects the costs of his neighbors in the network; the decision of each player is constant during a finite time horizon (working phase).

• We introduce an operating regime called the Weak Interconnection Regime (WIR), that allow us to conduct the Nash equilibrium (NE) of the considered game, by ensuring existence and uniqueness. Furthermore, this analysis ensures the well-posedness of the two equilibrium efficiency measures considered in this work: the Price of Anarchy (PoA) and the Price of Connectedness (PoC).

This paper is structured as follows. In Sec. II, the considered networked SIR epidemic model is described. The proposed strategic form game model to implement the tradeoff of interest and the chosen measures of global efficiency are provided. In Sec. III, we conduct a complete analysis of the corresponding Nash equilibria (existence, uniqueness). In Sec. IV, we show how the studied game can be exploited numerically for a Covid-19-type-scenario and we discuss the effectiveness of the decentralization strategy on the decisionmaking process.

II. PROBLEM STATEMENT

We consider a set of K > 1 interconnected regions (e.g., provinces, states, or cities) that are affected by an epidemic; the region index is denoted by k ∈ K := {1, . . . , K}. The epidemic propagation within a region is assumed to follow a SIR model. This section provides both the model that we consider for the epidemic dynamics in the presence of interconnected regions (Sec. II-A) and the game proposed to model the fact that the epidemic management is decentralized (Sec. II-B). The proposed game model intends to be simple while capturing a key feature, which is the tradeoff between socio-economic losses, and health aspects.

A. Epidemic Model

For Region k ∈ K, we respectively denote by β kk and γ k the virus (endogenous) transmission rate and the removal/recovery rate ( 1 γ k is called the average recovery period). For k = , the quantity β k denotes the transmission rate from Region to Region k. The action of Region k on the epidemics is represented by a scalar control action denoted by

u k ∈ U k where U k := [U min k , U max k ] ⊂ [0, 1) is compact.
The control action u k is assumed to be constant over the time period of interest (working phase) which is the interval [0, T ], T > 0. In this paper, we restrict our attention to the study over a single phase; a phase may typically last few weeks. In practice, the action would need to be updated for each phase. This corresponds to considering a blockwise constant management strategy, which is the easiest to implement in practice. We will denote by u the control action profile or vector: u := (u 1 , . . . , u K ) ∈ U where U := U 1 × . . . × U K and we will also use the notation u -k to refer to the reduced action profile u -k := (u 1 , . . . , u k-1 , u k+1 , . . . , u K ). The fractions of susceptibles, infected, and recovered for Region k are respectively denoted by

s k (t, u k , u -k ) ∈ [0, 1], i k (t, u k , u -k ) ∈ [0, 1], and r k (t, u k , u -k ) ∈ [0, 1].
With this notation, the continuous-time dynamics for the epidemic in Region k in presence of interconnection is assumed to be given by ∀T ∈ R ≥0 , u ∈ U:

                   ∂s k ∂t (t, u) = -s k (t, u) (1 -u k ) K =1 β k i (t, u) ∂i k ∂t (t, u) = - ∂s k ∂t (t, u) -γ k i k (t, u) ∂r k ∂t (t, u) = γ k i k (t, u) s k (t, u) + i k (t, u) + r k (t, u) = 1, (1)
where the initial fractions of susceptibles and infected are chosen as s 0 k > 0 and i 0 k ≥ 0. For the sake of simplicity we assume that the social distancing rules imposed in Region k (namely, u k ) affects uniformly all the infected population of each region in contact with the susceptibles of Region k, i.e., (1 -u k )β k is the controlled rate at which the infected individuals of Region infects the susceptibles in Region k. In practice, it would be quite difficult to measure its value, or to assign it a prescribed value. Then, we assume policy makers of each region k would apply a social-distancing rule close enough to the abstract quantity u k .

B. Game Model

Each region is assumed to seek for a tradeoff between the socio-economic losses and the local health impact of the epidemic, induced by the sanitary rules. This amounts to considering a cost function that comprises three terms. Precisely, we assume that a region aims at minimizing the following composite cost:

J k (u) := a k u k + b k u 2 k socio-economic losses + c k s 0 k -s k (T, u) health losses , (2)
where

(a k , b k , c k ) ∈ R 3 ≥0 are constant.
The reasoning behind this choice is that social-distancing strategies induce both health and socio-economic losses. In particular, we assume the socio-economic cost is a sum of linear and quadratic terms w.r.t the social distancing rules, as motivated in the related literature of optimal control applied to epidemic that spreads in a single Region (see e.g., [START_REF] Lauro | COVID-19 and flattening the curve: A feedback control perspective[END_REF], [14, Section 2.4]); this assumption seems to be commonly accepted in economic studies, according to [15, Eq. 8 in Section 2.2.2]. On the other hand, we consider the health losses to be proportional to the final size of the epidemic after a working phase. In particular, the decision of each node has an impact on its neighbors, through the network structure and the epidemic dynamics. The strategic form (see e.g., [START_REF] Lasaulce | Game theory and learning for wireless networks: fundamentals and applications[END_REF]) of the static game under consideration is therefore given by:

G := K, U k 1≤k≤K , J k 1≤k≤K , (3)
in which the players (nodes of the network) are the regions of a country (or simply countries); the action space for Player k is given by [START_REF] Stella | The role of asymptomatic individuals in the Covid-19 pandemic via complex networks[END_REF]. Region k ∈ K expresses its interests by setting the triple (a k , b k , c k ), whereas the set of action U k is imposed by a social planner (e.g., a country or an international organization, depending on the nature of the player). In the case where players are countries, we assume that the social planner might be a worldwide organization such as the WHO (World Health Organization). In addition, we emphasize that the theoretical results established in this paper hold for a multistage game setup in which the one-shot game is repeated at each stage (for which the parameters are updated) and different constant control actions are applied during it. In this letter we make the choice not to add a constraint on the region states. For instance, there is no constraint on i k (t, u) to account e.g., for the number of intensive care units (ICU) in a region. To treat the problem in presence of coupling constraints one would need to resort to more advanced notions such as the generalized NE, which is left as an extension of the proposed analysis. Notice that the third term of the cost functions can already be seen as a way of controlling the epidemic and the number of people requiring ICUs.

U k = [U min k , U max k ] ⊂ (0, 1); the individual cost function of Player k ∈ K is given by J k in

C. Efficiency measures

One of the main objectives of this paper is to assess the potential inefficiencies that might be induced by letting each region choose its control action. A famous and well-used measure of global efficiency is given by the Price of Anarchy (PoA) of a game [START_REF] Papadimitriou | Algorithms, games, and the internet[END_REF]. Before defining the PoA, let us remind the definition of a Nash equilibrium (NE). An action profile

u NE is an NE if: ∀k, ∀u k , J k (u NE ) ≤ J k (u k , u NE -k ).
The PoA is defined by:

PoA := max u∈U NE K k=1 J k (u) min u∈U K k=1 J k (u), (4)
where U NE is the set of NE of G. The function K k=1 J k is often referred as the social cost of the game. The PoA thus compares the performance of the worst NE to the performance of the centralized solution. Implicitly, the PoA assumes that the social cost is a relevant metric to measure the global performance. In particular, when the PoA is too high the decentralization strategy will not be effective at the risk of observing selfish behavior from Players. To have a second measure of global efficiency, we also introduce the Price of Connectedness (PoC), which is defined as follows:

PoC := max u∈U NE K k=1 J k (u) K k=1 min u k ∈U k J k (u k ), (5)
where J k (u k ) is the cost that Region k would obtain if they do not consider the influence of the network i.e., the crossing transmission rates β k , k = , would be vanishing in [START_REF] Pastor-Satorras | Epidemic processes in complex networks[END_REF]. This therefore corresponds to the performance that Region k would expect to obtain by neglecting the interactions with the other regions while these actually exist, hence the term PoC. Such as for the other efficiency measure, we consider that when the PoC is too high Regions should take into account the network structure before taking a decision.

III. NASH EQUILIBRIUM ANALYSIS

Since one of our main objectives is to measure efficiency at NE through the PoA and PoC in (4)- [START_REF] Magal | Final size of an epidemic for a two-group SIR model[END_REF], it is necessary to conduct the complete equilibrium analysis of the NE. This analysis includes the study of the existence and uniqueness of the NE.

A. Existence

In this section, we state our main result concerning the existence of a pure NE. Notice that the existence of a mixed NE is ensured by the continuity of the cost functions J k , k ∈ K (see [START_REF] Lasaulce | Game theory and learning for wireless networks: fundamentals and applications[END_REF]), but it is of no practical interest in our setting. The existence of a pure NE is strongly related to the geometrical properties of the cost functions J k , k ∈ K, such as the quasiconvexity properties. Since the dependency of the third term of J k on u k is not explicit, the quasi-convexity analysis of J k appears to be a non-trivial problem. This is the reason why we define a working regime in which it is possible to prove that J k is quasi-convex w.r.t. u k .

Weak Interconnection regime (WIR):

The game G is said to be in the WIR, if ∀(k, ) ∈ K 2 : = k there exists ν β,k > 0 such that β k ≤ ν β,k and J k is quasi-convex w.r.t. u k on U k (i.e, ∀u -k ∈ U -k , ∀λ ∈ R, the lower level set L k (u -k , λ) := {u k ∈ U k : J k (u k , u -k ) ≤ λ} is convex).
The motivation behind the definition of the WIR is given by the following result.

Proposition 1: In the WIR the game G has at least one pure NE. Proof: See Appendix-A.

An important practical question would be: "When is the game in the WIR?". To answer this technical question, let us introduce the following working assumption.

Assumption 1: Let ∀(k, ) ∈ K 2 , ρ k := β k /γ . Condition (i): The matrix B whose entries are given by: B k, = β k , is non-singular. Condition (ii): ∀k, ∀u, ∀T ∈ T one has that s k (t, u) > 0. Condition (iii): T = R ≥0 where

T := t ∈ R ≥0 : ∀k, ∀u, (1 -u k )s k (t, u) ≤ 1 K =1 ρ k .
Condition (i) is ensured when B is strictly diagonally dominant (which is often the case in practice because intraregions interactions are much stronger than inter-regions ones); Condition (ii) is trivially satisfied as far as the epidemic does not affect the entire population; Condition (iii) is needed to characterize a bound for the interregions interactions i.e., to quantitatively describe the WIR with ν β,k :=

min ∈K γ (1-U min k )s 0 k -β kk 4.
In what follows, we propose to exhibit a sufficient condition such that the game is in the WIR. To establish the corresponding result, a few notations are in order. Let T ∈ T , u ∈ U and s(T, u) = (s 1 (T, u), . . . , s K (T, u)) , i(T, u) = (i 1 (T, u), . . . , i K (T, u)) , r = (r 1 (T, u), . . . , r K (T, u)) . To be able to express the derivative of s k w.r.t. u k and exploit the implicit function theorem, let us introduce the two square matrices B := diag(1 -u) B and Γ := diag(γ), where γ := (γ 1 , . . . , γ K ). The reformulated system (1) in a collective dynamics form:

∀t ∈ [0, T ],            ∂s ∂t (t, u) = -diag(s(t, u))Bi(t, u) ∂i ∂t (t, u) = diag(s(t, u))Bi(t, u) -Γi(t, u) ∂r ∂t (t, u) = Γi(t, u). (6)
Using ( 6) and [5, Section 2], one can write the following identity:

d dt [BΓ -1 (s(t, u) + i(t, u)) -ln(s(t, u))] = 0. (7)
Therefore, by integrating ( 7) on [0, T ], one has that BΓ -1 (s(T, u) + i(T, u) -x 0 ) = ln(s(T, u)) -ln(s 0 ), where s 0 = s(0, •), i 0 = i(0, •) and x 0 = s 0 + i 0 . Let F : U × (0, 1] 2K → R K such that, for any k ∈ K, the k th -component of F is given by F k : U × (0, 1] 2K → R:

F k (u, s, i) = (1 -u k ) K =1 ρ k s + i -x 0 + ln s 0 k s k .
We define the set of non-monotonic players as K NM := {k ∈ K : J k is not monotone w.r.t. u k }, (i.e., k ∈ K NM if the assigned weights of socio-economic and health losses are such as J k is non-monotone w.r.t. u k ). Now that we have introduced all the notations needed to establish the main result of this letter, let us exhibit the following key Lemma that provides, ∀k ∈ K, a lower-bound on the derivative of s k w.r.t. u k .

Lemma 1: Under Assumption 1, ∀T ∈ T , ∀u ∈ U and ∀(k, ) ∈ K 2 one has ∂s k ∂u (T, u) ≥ 0 and

∂s k ∂u k (T, u) ≥ s k (T, u) ln s k (T, u) s 0 k (1 -u k ) [(1 -u k )ρ kk s k (T, u) -1] . Proof: See Appendix-B.
The following Theorem establishes the main result of this paper, by ensuring that the game G is in the WIR.

Theorem 1: Let T ∈ T . Suppose Assumption 1 holds and the less restrictive action profile

u min = (U min 1 , ..., U min K ) ∈ [0, 1) K verifies that, ∀k ∈ K NM , (1 -U min k )s k (T, u min ) ≥ 1 (2ρ kk ). Then, the game G is in the WIR. Proof: See Appendix-C.
The additional condition we introduce means that if the epidemics are sufficiently controlled, then the game G is a quasi-convex game that ensures the existence of a pure NE, according to Proposition 1. In practice, that would mean that the social planner would need to track the regions at least partially (e.g., by imposing some minimum epidemic management measures).

B. Uniqueness

In practice having the uniqueness of the NE may be a useful feature for a government (when players are the regions) or for an international organization (when players are countries). It is typically convenient to be able to predict the outcome of the game. If the game models the interactive situation sufficiently well, an NE can be effectively observed. If there is only one NE, the situation becomes predictable, which is not the case in the presence of multiple equilibria. It is known that uniqueness typically requires additional conditions ( [START_REF] Lasaulce | Game theory and learning for wireless networks: fundamentals and applications[END_REF]). The following result establish the uniqueness property of the NE, and the convergence of the sequential best-response dynamics.

Theorem 2: Suppose that ∀k ∈ K,

∂ 2 J k ∂u k 2 (u) > K =1, =k ∂ 2 J k ∂u k ∂u (u) .
Then G has a unique NE, and the sequential best-response dynamics converges to this equilibrium. Proof: See Appendix-D. We should note that, if the conditions of Theorem 1 hold for all k ∈ K, then J k is strictly convex w.r.t. u k that is,

∂ 2 J k ∂u k 2 (u) > 0.
Here, the additional condition of Theorem 2 requires that the dependency of the second derivative of J k w.r.t. the control actions of the other regions is sufficiently small. The latter is both useful to predict the epidemic tendency when its management is decentralized and to compute the NE (so the PoA and PoC).

Remark. If the game is not in the WIR but K NM = ∅, the costs J k are all individually quasi-convex and the existence of a pure NE is ensured. Moreover, there is a unique pure NE which lies at the extreme of the interval U, in particular whatever the values of β k .

IV. NUMERICAL PERFORMANCE ANALYSIS

The goal of this section is to quantify the PoA and PoC numerically for a Covid-19-type scenario. The proposed methodology can be applied to other epidemic scenarios where multiple regions are involved. Motivated by a scenario which has been studied by the French government in May 2020. We assume that France is divided in K = 5 regions and we propose to observe the influence of the inter-region virus transmission rates β k on the PoA and PoC. To choose the epidemic's parameters, we have exploited the studies on Covid-19 that have been conducted in [START_REF] Lasaulce | Analysis of the tradeoff between health and economic impacts of the Covid-19 epidemic[END_REF], [START_REF] Casella | Can the COVID-19 epidemic be controlled on the basis of daily test reports[END_REF], [START_REF] Salje | Estimating the burden of SARS-CoV-2 in France[END_REF]. We assume that: Regions k ∈ {1, 2} have selected the weight a k , b k and c k such that only the socio-economic losses matter; Regions k ∈ {3, 4, 5} weighted the weights of each of the losses such that K NM = {3, 4, 5}; see the Table I.

k γ k β kk s 0 k i 0 k a k b k c k 1 0.15 3γ 1 0.8 0.2 2 0 0 2 0.15
2γ 2 0.9 0.1 0.5 0 0 3 0.15 1.5γ 3 0.9 0.005 5 2 50 4 0.15 1.2γ 4 0.9 0.002 2 5 70 5 0.15 1γ 5 0.9 0.001 3 5 70

TABLE I: Epidemic and Game parameters

The time horizon of the considered epidemic phase is set to T = 30 days [START_REF]Open stats coronavirus[END_REF], [START_REF] Cauchemez | Sortie progressive de confinement prerequis et mesures phares[END_REF], [22]. The coupled SIR model is implemented by using the Matlab ODE45 solver with the Runge-Kutta scheme. The action space is chosen by the social planner such as: ∀k ∈ K, U max k = 0.9, u min = (0.6, 0.51, 0.35, 0.2, 0.1) and

U k = {U min k , (U max k - U min k ) • 0.1, . . . , U max k }.
In view of the Table I, the Theorem 1 holds, when the inter-region virus transmission rates β k are lower than the constant threshold ν

β,k = 1 4 •( γ k (1-U min k )s 0 k -β kk ),
which is reasonable in view of the situation in France provided by the National Institute of Statistics and Economic Studies (INSEE) in [START_REF] Guan | Transport effect of COVID-19 pandemic in France[END_REF]. By applying an exhaustive search to find the NE and the social optimal, we show in Fig. 1 and 2 the interpolation of the PoA, PoC w.r.t β k , ∀k = . Each curve corresponds to a scenario where all incoming transmission rates from a given region vary uniformly (i.e.,∀ = k, β k ∈ {0, 1 • 10 -3 , . . . , 1.2 • 10 -2 }), whereas the other transmission rates are fixed at the threshold value ν β,k . We observe that the PoA can be as large as 1.2 for crossing rates greater than 0.2%. Therefore, the outcome in this case is that the social planner should not decentralize the decision making. We emphasize that, when β k ≥ ν β,k the simulation does not fit into our theoretical setup. The PoC measures the impact of ignoring the connection with other regions is even larger and reaches values as large as 3, which shows that a region has a strong interest in accounting for the crossing rates to manage the epidemic locally. u NE = Nash equilibrium strategy; u opt = optimal centralized strategy; u min = less restrictive policy.

In view of the weights a k , b k , c k given in the Table I, a natural question should be raised: "How is the epidemic spreading in the regions k ∈ {3, 4, 5}?" Fig. 3 shows the evolution over the time of i k , for k ∈ {3, 4, 5}, when different strategy is considered and ∀k = , β k = ν β,k . Quantitatively we observe that: when either the NE or optimal strategy is applied, the maximum proportion of infected in Regions k ∈ {3, 4, 5} is less that 0.94%, i.e. if the population sizes in Regions k ∈ {3, 4, 5} are similar to the region " Île-de-France", then the infected proportions are upper-bounded by 112 800 cases, when policy-makers apply either NE or centralized strategy.

V. CONCLUSION

The conducted Nash equilibrium analysis of the proposed game largely relies on the individual quasi-convexity of the cost function of a region. Because one cannot express the state of the fraction of "susceptibles" as a function of the control actions, this analysis turns out to be non-trivial. We exhibit a regime in terms of coupling degree among the regions in which existence is guaranteed; this regime appears to be non-limiting for real scenarios. The numerical analysis allows one to clearly quantify what is lost when regions or countries decide by themselves the way to manage the epidemic locally, without coordination. The proposed approach might be improved e.g., by integrating coupled constraints, by investigating a dynamical game formulation of the problem, or by performing a deeper numerical analysis on the impact of the graph on the price of anarchy and the price of connectedness.

APPENDIX

A. Proof of Proposition 1

Since the action space of each player U k is a convex, compact and non-empty set; the costs J k are jointly continuous that is continuous w.r.t. the action profile u ∈ U; the costs J k are quasi-convex w.r.t. u k on U k . Then, the game G is a quasiconvex game. By Debreu-Fan-Glicksberg theorem for quasiconvex games [16, Theorem 50], the existence of a pure NE is guaranteed.

B. Proof of Lemma 1

Let k ∈ K, u ∈ U, T ∈ T and, X := u, s(T, u), i(T, u) ∈ U × (0, 1] K × (0, 1] K such that F (X) = 0. In what follows, we denote by: D := diag(s(T, u)) -1 -diag(BΓ -1 ) -1 , B := B -diag(B). In view of the expression of F , we have that:

∂F ∂s (X) = -D -1 I K -DBΓ -1 , ∂F ∂u (X) = -diag(1 -u) -1 diag ln (s(T, u)) -ln s 0 . According to Condition (iii) in Assumption 1, we derive that, DBΓ -1 ∞ = max k∈K K =1, =k (1 -u k )ρ k s k (T, u) -1 -(1 -u k )ρ kk < 1.
Therefore, the Neumann series converges and,

I K -DBΓ -1 -1 = +∞ k=0 DBΓ -1 k . According to the implicit function theorem, it follows that, ∂s ∂u (T, u) = - ∂F ∂s (X) -1 ∂F ∂u (X).
We denote by ∂s ∂u (T, u) the approximation of ∂s ∂u (T, u) at the first order of the Neumann series, such that, ∀k, , ∂s ∂u (T, u) := I K + DBΓ -1 D ∂F ∂u (X). Therefore, ∀k, , ∂s k ∂u (T, u) ≥ ∂s k ∂u (T, u) ≥ 0, since Condition (iii) of Assumption 1 holds. The lower bound of ∂s k ∂u k (T, u) given in Lemma 1 corresponds to ∂s k ∂u k (T, u).

C. Proof of Theorem 1

The goal of this proof is to ensure that ∀k ∈ K, J k is quasi-convex w.r.t u k ∈ U k . We know that, ∀k ∈ K \ K NM , J k quasi-convexity property holds. In what follows, we are interest in to show the convexity of costs J k for Players k ∈ K NM . Therefore, we propose to analyze in a first step the convexity of i k w.r.t u k , which allows us to discuss about the concavity of To conclude this proof, ∀k ∈ K, J k is quasi-convex then by definition the game G is in the WIR.

s k w.r.t u k for k ∈ K NM . Let k ∈ K NM , u ∈ U, T ∈ T and X := u, s(T, u), i(T, u) ∈ U × (0, 1] K × (0, 1] K such that F (

D. Proof of Theorem 2

According to [24, Section 2.5-2.6], a sufficient condition to ensure the contraction of the Best-response mapping given by, BR(•) = argmin u∈U1 J 1 (u, •), . . . , argmin u∈U K J K (u, •) is to verify the strict diagonal dominance condition, which yields that: ∇ 2 J 1≤k, ≤K = ∂ 2 J k ∂u k ∂u 1≤k, ≤K > 0 ⇒ ∇ 2 J +∇ 2 J > 0. Hence, according to [25, Theorem 2 and Theorem 6], the diagonally strictly convexity (DSC) condition is verified that ensures the uniqueness of the NE. Moreover, in view of [24, Section 2.5], the sequential best-response algorithm converges to the unique Nash equilibrium of the game G.

Fig. 1 :

 1 Fig. 1: Interpolation of PoA by varying uniformly the incoming transmission rates of each Region k. The dotted curves do not fit into our theoretical setup.

Fig. 2 :

 2 Fig. 2: Interpolation of PoC by varying uniformly the incoming transmission rates of each Region k. The dotted curves do not fit into our theoretical setup.

Fig. 3 :

 3 Fig. 3: Interpolation of infected proportions in each Regions k ∈ {3, 4, 5}.

0 k( 1 - 1 .

 011 X) = 0. By following the same reasoning as in Lemma 1, we apply the implicit function theorem to the function F :U × (0, 1] K × (0, 1] K → R K with: ∂F ∂i (X) = diag(1 -u) BΓ. Hence, we derive that ∂i k ∂u k (T, u) = ∂F ∂i inv kk ln s k (T,u) s u k ) 2 , where b inv kk is the (k, k) th element of B -Let u -k ∈ U -k , λ ∈ R, (u k , u k ) ∈ u k ∈ U : ∂i k ∂u k (T, u) ≤ λ such that u k ≤ u k . Given that: (i) ∀α ∈ [0, 1], u k ≤ αu k + (1 -α)u k ≤ u k ; (ii) s k is increasing w.r.t. u k ; we derive the quasi-convexity of ∂i k ∂u k w.r.t u k , since the following holds.

0 k( 1 -i k ∂u 2 k(. 2 k( 1 -u k ) 3 G 2 k 2 k∂ 2 r k ∂u 2 k( 2 k

 0122132222 αu k +(1-α)u k , u -k ) ≤ γ k b inv kk ln s k (T,u k ,u -k ) s u k ) 2 ≤λ.Let us write the second derivative of i k w.r.t.u k , ∂ 2 u)(1-u k )+2s k (T,u) ln s k (T ,u) s 0 k (1-u k ) 3 s k (T,u) By combining with the lower-bound of ∂s k ∂u k given in Lemma 1, we derive that ∂ 2 i k ∂u (T, u) ≥ γ k b inv kk ln s k (T ,u) s 0 k k (u)whereG k (u) := -γ k γ k -s k (T,u)(1-u k )β kk + 2 . In view of the condition given in Theorem 1, it follows that G k (u min ) ≤ 0 then ∂ 2 i k ∂u (T, u min ) ≥ 0. Since ∂i k ∂u k is quasi-convex w.r.t. u k , then ∀T ∈ T and ∀u ∈ U, ∂ 2 i k ∂u (T, u) ≥ 0. Since, ∀k, r k (T, u) = T 0 γ k i k (t, u)dt, itfollows from the Leibniz's rule for differentiation under the integral sign that u)dt ≥ 0. Hence, ∀T ∈ T , ∀u ∈ U, ∂ 2 s k ∂u (T, u) ≤ 0, since s k = -i k -r k .

This work was supported by ANR via the grant NICETWEET, number ANR-20-CE48-0009 and by CNRS via the grant COVEXIT.