Phan Trung Huy

Nguyen Hai Thanh
email: nhthanh@moet.gov.vn

Cheonsick Kim

Relationship between Correcting Code and Module Technique in Hiding Secret Data

Keywords: module, ring, characteristic 2, data hiding, binary image, steganography, correcting codes, covering function, MSDR

In this paper, we show the role of modules over rings of finite characteristics in data hiding area. Applications of correcting codes and covering functions in data hiding are shown as special cases of our module approach. Applications of modules over rings of characteristic 2 to design new embedding schemes for hiding secret data in binary images are introduced.

Introduction

Data hiding can be applied in copyright, annotation, and communication, and can be achieved by altering some nonessential pixels in the cover image. For example, in a given color image (including grayscale image), the least-significant bit (LSB) of each pixel can be changed to embed the secret data. However, two color images embedded by secret data are very sensitive and can be easily detected by the human eyes. One of the most challenging problems is hiding the secret data into binary images with a high ratio of secret data, and low image distortion. In case of palette images, ones need to prevent steganalysis, especially to histogram-based attacks (see for examples some analysis in [START_REF] Xinpeng ; Zhang | Vulnerability of pixel-value differencing steganography to histogram analysis and modification for enhanced security[END_REF], if the alpha ratio of the number of changed pixels to the number of total pixels of a given palette image is lower than 0.1, it is very difficult to guess if the image contains hidden data. In block-based approaches, each binary image is partitioned into binary blocks of the same size N, each block can be seen as an N-bit string of size N. In such a block F of size N, by taking WL scheme [START_REF] Wu | Anovel data embedding method for two-color fascimile images[END_REF] one can embed one bit by changing at most one bit of F. From CPT scheme proposed by Chen-Pan-Tseng (2000) [START_REF] Chen | A secure of data hiding scheme for two-color images[END_REF], in F one can embed r=log 2 (N+1) bits, by changing at most two bits of F. By correcting codes approach, with notion of covering codes, Crandall [START_REF] Crandall | Some notes on steganography[END_REF] refers to an unpublished article by Bierbrauer [START_REF] Bierbrauer | Crandall's problem[END_REF] that brings deep tech-data. For examples, the matrix encoding technique used in F5 algorithm by Westfeld [START_REF] Westfeld | High Capacity Despite Better Steganalysis (F5-A Steganographic Algorithm)[END_REF] permit us to modify at most 1 pixel among 2 k -1 pixels to hide k secret bits. The distortion of image then is reduced with the high ratio of the embedding scheme, which reached MSDR 1 . Matrix encoding technique using correcting codes show that after the embedding phase, the syndromes generated by a parity check matrix in the extracting phase will present exactly secret data embedded in stego-images. In covering code technique, the covering radius of the code reflects the maximal number of pixels changed to embed secret data and the dimension of code reflects the capacity of bits can be embedded, by a scheme used this approach.

Given the linear space W n = F n q of dimension n over the finite field F q and a natural number d > 1. Due to Hamming's work origined from 1947, an error correcting code over F q is defined as a subset C  W n for which d is the minimum distance between two distinct code words x ≠ y  C. In error correcting codes area, each codeword vC can be seen as an (exact) encoded bit string we need to transmit on a noise channel. If there are at most r = d/2 errors appear on transmission, that is v is changed to v'=v+e for some error vector e whose Hamming weight w(e) ≤ r, then we can correct v' to recover v after erasing e, by some methods detecting e. The size of C is defined as |C|-the number of code words in C.

If the code is linear, we can find some effective ways to detect the error vector e.

A linear code C of type [n, k, d] is a linear subspace of W n having its dimension k < n, with d the minimum (Hamming) distance between distinct code words x≠yC. The covering radius  of code C is defined as  = max v ∈ W d(v;C), where d(v;C) denotes the minimum Hamming distance from the vector v to the code C. A parity check matrix of C is a matrix H of size t  n, t=n-k, which permit us to obtain for any v  W n its syndrome vector s(v) = H.v T , where v T is the column vector form of v, so that s(v)= 0 if and only if v ∈ C. The syndrome s(v) is used to detect and correct the error e if w(e)=k (the number of errors), k ≤ r = d/2, appeared on transmission, to recover the correct message v from the received message v'=v+e as follows: since s(v')=H.v'=H.(v+e) T =H.v T +H.e T =s(v)+s(e)=s(e), we find e so that s(e) = s(v') and w(e) ≤ r = d/2, and correct v' to v = v'-e. To obtain an efficient way recognizing the error e, the coset technique is developed.

A coset C + v is the set of all vectors in W n with the same syndrome s(v). A vector l r(v) of the minimum weight in C + v can be called a leader of the coset. We define the syndrome map s :

W n → W t by s(v) = H . v T .
In steganography (see [START_REF] Bierbrauer | Constructing good covering codes for applications in Steganography[END_REF][START_REF] Ould | A Novel Steganographic Protocol from Errorcorrecting Codes[END_REF]), one can make use of the syndrome map s : W n → W t as the extracting map of the embedding scheme [n, t, ] which can be defined by: 1. Let n and t be positive integers, t ≤ n, and let X be a finite set of symbols. An embedding scheme of type [n, t,] over X is given by a pair of maps c : X t ×X n → X n and s : X n → X t such that s(c(p, v)) = p for all (plaintext) p ∈ X t and v (stego-block) ∈ X n . Maps c and s are the embedding and the extracting maps, respectively. The covering radius of the scheme is defined as

ρ = max{d(v, c(p, v)) | p ∈ X t , v ∈ X n },
where d is the Hamming distance.

2. The embedding scheme [n t,ρ] allows us to hide p (as a string of t secret symbols) into v (as an n-string v of n cover symbols), by changing at most ρ of n cover symbols. The following algorithm shows this idea.

Coset algorithm. Given p,v a) Compute u = s(v) -p, b) Set v'= c(p; v) = v -l u ,
where l u is a leader of the coset C + u of all the vectors in W n with the same syndrome of u. The Hamming weigh w(l u ) = j ≤ ρ together with vector l u show the exact j positions on which we need to change with the cover vector v by equation v' = v -l u . So, s(l u ) = u. This provides us in the extract phase: by using (a) above, the syndrome s(v') = s(v)-s(l u )=s(v)-u = p is obtained, the exact plaintext as claimed.

Concretely (see, such as [START_REF] Bierbrauer | Constructing good covering codes for applications in Steganography[END_REF]), in case X = F 2 (also Z 2 ) for designing an embedding scheme [n, t,ρ], we can use a covering function COV(ρ,n,t) which permit us to embed any t-bit string p in any n-bit string v (as a block of n bits) by changing at most ρ positions on v.

Good covering codes

In [START_REF] Bierbrauer | Constructing good covering codes for applications in Steganography[END_REF] the authors show some interest classes of cover functions:

1. COV (2, 5 • 2 a-1 -1, 2a + 1) for a ≥1 by equation (1). 2. COV (2, 6 • 4 a-1 -1, 4a
), a ≥ 2 by equation ( 4). The first members of this family are COV [START_REF] Chang | A High Payload Steganographic Scheme based on (7,4) Hamming Code for Digital Images[END_REF]23,[START_REF] Lee | A novel data hiding scheme based on modulus function[END_REF], COV [START_REF] Chang | A High Payload Steganographic Scheme based on (7,4) Hamming Code for Digital Images[END_REF]95,[START_REF] Preparata | A class of optimum nonlinear double-error-correcting codes[END_REF].

By our interest, for high quality of stego-images, in this paper we focus only on small values, especially for ρ=1, 2.

k-maximal secret data ratio of embedded bits

In this part, given an image G, for simplicity we only concentrate on one fixed block F = (F 1 ,F 2 ,.., F N ) of N pixels of G, and F is considered as a vector of dimension N). In F each entry F i can be understood as a pixel whenever the index i is referring, also as the color of this pixel whenever its color value is mentioned. Suppose each color F i can be changed to q-1 new colors F i ' closed to F i , by one of q-1 different ways. In the case of binary images, q=2. In the general case q 2 for color images.

We consider here k-embedding schemes in which secret bits can be embedded in each block F by changing at most k entries, with k small, k = 1,2. Together with F, each new block F' after changing pixels of F is called a configuration. Denote by MSDR k the k-Maximal Secret Data Ratio which presents the largest number of embedded bits in each block F of N pixels by changing colors of at most k pixels in F. In the case k=1, since we change colors in at most one element in F, with N elements, 1+(q-1)N ways can be taken. This means that for any 1-embedding scheme, we can hide at most MSDR 1 = log 2 (1+(q-1).C(N,1)) secret bits in each block F. In the cases k=2 or 3, similarly, we have MSDR 2 = log 2 (1+(q-1).C(N,1)+(q-1) 2 .C(N,2)) and MSDR 3 = log 2 (1+(q-1).C(N,1)+(q-1) 2 .C(N,2) )+(q-1) 3 .C(N,3)) . For example, in binary images, if N = 5 then MSDR 2 = 4. In the case of grey images, with N=1, q=16, MSDR 1 = log 2 (1+15.1) = 4. That means in each pixel F (a block of 1 pixel) if its color has 15 other ways to change, then any 4 secret bits can be hidden in F by some appropriate change. This is the case achieved in [START_REF] Lee | A novel data hiding scheme based on modulus function[END_REF].

3

Modules over rings of characteristic 2 in hiding secret data

Application of modules in hiding secret data

Each (right) module M over the ring Z q is an additive abelian group M with zero 0 together with a scalar multiplication "." to assign each couple (m,t) in M × Z q with an element m.t in M. Let Z q = {0,1,..,q-1}. We need some following basic properties, which will be used in the sequent: We call a k-embedding scheme any embedding scheme that permits in each block F of N elements ones can change at most k elements to hide data. In the case v=1, it is obvious that U=M-{0} is the unique 1-base.

P1) m.0 = 0; m.1=m; P2) m+n = n+m for all m,n in M. P3) m.(t+l) = m.t + m.l for all m in M, t,l in Z q . Definition 1. Given a natural number v > 0, a subset U ⊆ M-{0}, we call U a v- base of M if
In this paper, the main of our interest are the cases v = 1,2 for binary images (according to the characteristic q =2 and M =Z 2 × Z 2 ×..× Z 2 is the n-fold cartesian product of Z 2 , which can be seen as a (right) Z 2 -module. For binary image we have q=2. The addition in Z 2 can be seen as the operation XOR (exclusive -OR) on bits, Each element x=(x 1 ,x 2 ,..,x n ) in M can be presented as an n-bit string x=x 1 x 2 ..x n , with operations defined as follows: As one can see, an 1-embedding scheme can be reduced from a 2-embedding scheme. Hence, at first we consider 2-embedding schemes.

Application of 2-bases for 2-embedding schemes

Let U ⊆ M-{0}, U be a 2-base of a Z 2 -module M. Suppose |U| =n. Consider any binary block F =(F 1 , F 2 ,.., F s ) of a given binary image G, and binary secret key K=

(K 1 ,K 2 ,..,K s ), F i , K i ∈ Z 2, i=1, .., N.
Suppose s ≥ n. For F, we can assign a surjective function h F : {1,2,..,N} → U as a weight function of indexes i of F i . Since F is fixed in the scope, for simplicity we write h instead. We can embed any secret element d ∈ M in F by changing colors of at most 2 elements in F as the following 2-embedding scheme.

Embedding a secret element d

Set S[F,K] =  1≤ i≤ N h(i).T i , by taking operations on the Z 2 -right module M.

Step 0) Given a secret key as a binary vector K=(k 0 , k 1 ,.., k N ),

k i ∈ Z 2 .
Change the color F i of each

F i ∈ F into a marked color T i =F i +k i (in Z 2 ).

We present this computation by T=F⊕K; Step 1) Compute m = S[F,K];

Step 2) Compare m and d: -Case m = d: keep F intact; -Case d m: then find d -m=a, for some a ∈ M-{0}. There are two following cases happen: i) a ∈ U: since h is surjective, there exists F q in F , such that h(q) = a =d-m. Then change the color F q to new color F q '=Next(F q )=F q +1.

ii) a ∉ U : Since U is a 2-base of M -a Z 2 -module -we can find (successfully) two elements x,y in U such that a=x+y, and therefore find two entries F p ,F q in F such that h(p)=x, h(q)=y.

Then we change F p to new color F p '=F p +1, and change F q to new color F q '=F q +1;

Extracting the secret element embedded in F.

Step

1) Computing u=S[F,K];

Step 2) Return u as the secret element d embedded in S (that is u=d) .

Correctness of the method. Theorem 1. The element u extracted in step 1 of the extracting stage 3.2.2 above is exactly the secret element d hidden into S in the embedding stage 3.2.1.

Proof. We need consider only the case d  m and prove that u=d. Indeed, if the step (2i) in 3.2.1 is taken place, after changing the color F q to F q ' =F q +1 by step 2(ii) in 3.2.1 with h(q)=a=d-m, we get T q '= T q +1. Then,

u =  1≤ q i≤ N h(i).T i + h(q).(T q +1) =  1≤ q i≤ N h(i).T i + h(q).(T q ) +h(q).1 =  1≤ i≤ N h(i).T i + h(q)=m+d-m =d.
For the case that the step (2ii) in 3.2.1 is taken place, using d -m =a = x+ y, h(p)=x, h(q)=y, by the same arguments we deduce T p '=T p +1 and T q '=T q +1. Therefore

by properties of modules u = 1≤p,qi≤N h(i).T i +h(p).T p '+h(q).T q =  1≤p,qi≤N h(i).T i + h(p).T p +h(p)+h(q).T q +h(q) =  1≤ i≤ N h(i).T i + h(p).T p + h(q).T q + h(p)+h(q)

=  1≤ i≤ N h(i).T i + h(p)+h(q) = m+a = m+d-m = d. This completes the proof. || Example 1. The subset U={0001,0010,0100,1000,1111} is a 2-base of the module

M = Z 2  Z 2  Z 2  Z 2 .
Therefore, we can use it to hide data. In any block F of 5 pixels, we can change at most two pixels to hide 4 bits. That is the MSDR 2 is obtained:

MSDR 2 = log 2 (1+5(5+1)/2)  = 4 = log 2 (|M|).
Remark 1. Applications of k -bases for k-embedding schemes are similarly established, for any k>0, hence we do not mention in details.

Designing 2 -bases of Z 2 n

In this part we introduce a method to design 2-bases of Z 2 n inductively. Denote by (ii) 00..0x r x r-1 ..x 1 1 with any x r x r-1 ..x 1  V r .

V n = Z 2 n = Z 2  Z 2 ..  Z 2 the Z 2 -
(X) = V t . Lemma 2. If X is a 2-base of V n such that PL m (X) =V m for some integer 0 < m < n, then there exist a 2-base Y of V n+1 such that PL m (Y) =V
By assumption on X, any element of the form y 1 ..y m 0 in V n+1 can be presented as a linear combination of at most two elements in Y. For any element of the form y 1 ..y m x 1 ..x r 1 in V n+1 , by PL m (X) =V m there exists n-bit string of X of the form y 1 ..y m v 1 ..v r , for some r-bit string v 1 ..v r . So y 1 ..y m v 1 ..v r 0 belongs to Y by definition.

Define u 1 ..u r = x 1 ..x r  v 1 ..v r . Then y 1 ..y m x 1 ..x r 1 = 00..0u 1 ..u r 1  y 1 ..y l v 1 ..v r . Hence Y is a 2-base of V n+1 . Obviously, |Y|=|X|+2 r , m+r=n and PL m (Y) =V m . || Remark 2. By duality, from a 2-base X satisfying PR r (X)=V r , we can define a 2base Z of V n+1 having all elements in one of two forms: 1y 1 ..y m 00..0, with any m-bit string y 1 ..y m in V m , and 0x 1 ..x m u 1 ..u r , with any n-bit string x 1 ..x m u 1 ..u r in X.

Theorem 3. For any n ≥ 4, there exist 2-bases X in CL m,r, , Y in CR m,,r such that if m,r >1, m+r=n then |X|, |Y| ≤ 2 m + 2 r -3.

Proof. Firstly, one can see that: a) CL 2,2 contains the set Z={0001, 0010, 0100, 1110, 1001}, this set satisfies the claim |Z| = 5 = 2 2 +2 2 -3 , and CR 2,2 contains the set T={1000,0100,0010,0111,1001} with |T|=5 which satisfies the claim.

b) For all CL m,r , CR m,r , m+r=n, n ≥ 4, m, r >1, one can prove easily the theorem by induction on n, starting from two 2-bases Z, T above and applying Lemma 2 together with Remark 2 by duality. □ Example 1. a) the class CL 2,1 contains the set X={110,100,010,001}, and CR 1,2 contains the set Y = {011,001,010,100}.

Generally, for any n>0, we can define the set X contains all n+1-bit strings in one of two forms: b n b n-1 ..b 1 0 ≠ 00..0 and 00..01. Then X belongs to CL n,1 . We define the set Y contains all n+1-bit strings of two forms: 0b n b n-1 ..b 1 ≠00..0 and 100..0, then Y belongs to CL n,1 .

b) CL 2,3 contains the set of 9 elements X = {00010, 00100, 01000, 11100, 10010, 00001, 00011, 00101, 00111} c) CL 3,3 contains the set of 13 elements {000010, 000100, 001000, 011100, 010010, 000001, 000011, 000101, 000111, 100000, 110000, 101000, 111000}.

4

Correcting codes and module method in data hiding 4.1. Correcting code and covering function as special cases of module method In data hiding area, by the essential relation between correcting code and covering function, for simplicity we need only to show the relation between correcting codes and module methods. Indeed, by the coset algorithm in the part 2.1, section 2, in the extract phase, a plaintext p hidden in the cover-string v' can be extracted from v' by computing the syndrome of v' as p = s(v')=H.v' T , where v'= v -l u and H is the parity checking matrix of size t  n which can be presented as H = (C 1 ,..,C i ,..,C n ), where each column vector C i with size t  1 is considered an element in W t , a Z 2 -module. Suppose v'= (x 1 ,..,x n ), x i Z 2 , i=1,..,n. It is obvious that the syndrome s(v') = H.v' =  1≤ i ≤ n C i . x i is exactly the sum we compute by module method, where the weight function h: {1,..,n} →M-{0} is defined by h(i) = C i for all i=1,..,n with the Z 2module M = W t . Computing v'= v -l u means that we need to find some positions on v to flip if in the coset leader l u of u = s(v)-p, the corresponding positions are different from 0. In the following example, we present the arguments in details.

Example 2. The Hamming code can supply us an instance for module approach in hiding data. In details, we have the embedding scheme [START_REF] Bierbrauer | Constructing good covering codes for applications in Steganography[END_REF][START_REF] Chen | A secure of data hiding scheme for two-color images[END_REF][START_REF] Bierbrauer | Crandall's problem[END_REF] by using the Hamming code [START_REF] Bierbrauer | Constructing good covering codes for applications in Steganography[END_REF][START_REF] Kim | Data Hiding in a Halftone Image Using Hamming Code[END_REF], taking W 3 -{0} = {1,2,..,7} and considering each column C 1 ,C 2 ,..,C 7 of the parity checking matrix H of size 3  7 as a 3-bit presentation of these numbers Each block F of the binary image can be seen as a column vector u of 7 entries: u= (x 1 ,x 2 ,..x 7 ) T . Then taking operations on Z 2 -module we can write H.u = C 1 .x 1 + C 2 .x 2 + ... + C 7 .x 7 where each column C i can be seen as a vector in V 3 =Z 2 3 and the set C={C 1 , C 2 , C 3 , C 4 , C 5 , C 6 , C 7 } is nothing but an 1-base in Z 2 -module V 3 . For security reason, one can choose an extra binary key k -as a column vector of 7 entries, k=(k 1 ,k 2 ,..,k 7 ) T and taking operation XOR, with u we get v =u  k = (y 1 ,y 2 ,..,y 7 ) and H.v= C 1 .y 1 +C 2 .y 2 +..+C 7 .y 7 .

Replacing a position x j in u by x j 1 implies that the same position y j in v is replaced by y j 1. This gives us the marked vector v' satisfying the equation H.v' = H.v  C j . Now, suppose H.v=e and we need to hide a vector d (of 3 bits) which is considered as an element in W 3 . We can flip at most one position x j in u to hide d as follows:

Case d=e, the block u is kept intact, so that in the extracting phase, ones recover H.v = d. Case d ≠ e, or equivalent, e-d ≠ 0, we can find in C (an 1-base of W 3 ) a vector C j so that C j = e-d (that means C= e d in W 3 ). After flip x j to x j 1 in u, we have H.v' = H.v  C j = e  e  d=d, the result one needs to recover in the extract phase. Let us remark that the sum C 1 .y 1 +C 2 .y 2 +..+C 7 .y 7 is exactly the result we get by the steps in 3.2.1 where C i .y i is nothing but h(i).T i in that steps, with h(i)=C i for i=1,2,..,7.

Experimental results for finding 2-bases

As some results generated from our program, we obtained: (i)

The 2-base X={0001, 0010, 0100, 1110, 1001} and Y= {1000, 0100, 0010, 0111, 1001} provide us 2-embedding schemes which permit in each block of 5 pixels, by changing at most two pixels one can hide 4 bits. Hence regarding 2embedding schemes, our schemes can be seen as some expanded for the list COV (2, 6 • 4 a-1 -1, 4a) with a=1, by equation ( 4) [START_REF] Bierbrauer | Constructing good covering codes for applications in Steganography[END_REF] mentioned in section 2. (ii) The 2-base X = {1, 2, 3, 4, 5, 6, 8, 16, 24, 37, 45, 53, 58} and Y= {1, 2, 3, 4, 5, 6, 8, 16, 24, 32, 47, 55, 63} in W 6 = Z 2 6 (the numbers can be seen as 6-bit strings). We provide new 2-bases with 13 elements, which permit us to hide 6 bits in each block of 13 pixels. Then we can extend them by the techniques mentioned in Lemma 2 to obtain new 2-bases for hiding 7-bit strings.

Conclusion

By flexibility of module approach for which correcting codes and covering function techniques are considered as the special cases, we can offer more new and powerful schemes to hide data without of using radius or distances as in correcting and covering codes.

In color images (24bpp with three channels Red, Green, Blue), or in palette images, especially for grayscale images, ones can obtain a higher ratio of secret bits hiding in each block of images by using some other module, such as Z q , q>2.

Several works consider some ways to hide as much as secret data in each block of pixels with low image distortion if it is possible. In preventing from steganalysis attacks, ones need a very high quality of stego-images, generally in palette images, hiding bits in each pixel is not good enough for security reason. In these situations, changing only a small k = 1, 2, 3 pixels in each block of pixels, using a huge number of key matrices to prevent effectively from exhausted attacks, by some k-embedding scheme modified for color images we can obtain stego-images with the high quality. These will be studied in future works.

  D1) x+y = z 1 z 2 ..z n where z i =x i ⊕y i , i=1,..,n , For x=x 1 x 2 ..x n , y=y 1 ..y n in M, k in Z 2 , D2) x.k= z 1 z 2 ..z n where z i =x i .k = x i AND k. Given a binary image G, we set C G = Z 2 ={0,1} as the set of two colors of G. The color changing function Next: Z 2  Z 2 is given by: (3.1 ) c'= c+1 = Next(c), for all c in Z 2 and changing a color c means that c is replaced by c' = Next(c).

  module whose elements can be presented simply as the form b = b n b n-1 ..b 1 , an n-bit strings. Denote by PR k (V n ) the projection getting k right components in V n and PL k (V n ) the projection getting k left components in V n . Concretely, PR k (b n b n-1 ..b r ..b 1 ) = b k b k-1 ..b 1 and PL k (b n b n-1 ..b 2 b 1 )= b n b n-l .. b n-k+2 b n-k+1

  m and |Y|=|X|+2 r , m+r=n. Proof. Define Y is the set of all n+1-bit string x in one of two following forms: (i) b n b n-1 ..b 1 0, with any b n b n-1 ..b 1 in X and whose right most bit is 0.

Fig. 1 .

 1 Fig.1. Parity checking matrix H in Hamming code[START_REF] Bierbrauer | Constructing good covering codes for applications in Steganography[END_REF][START_REF] Kim | Data Hiding in a Halftone Image Using Hamming Code[END_REF]

1 ,t 2 ,..,t n in

  for any xM -{0}, x can be presented by a linear combination of at most v elements in U. That means there exist n elements u 1 ,u 2 ,..,u n in U, n≤v, together with t Z q such that x = u 1 .t 1 +u 2 .t 2 +..+u n .t n .

  .

	Denote by CL k,t a class of 2-bases X of V n satisfying |X|=2 k + 2 t -3,n=k+t, and
	PL k (X) = V k . Denote by CR k,t a class of 2-bases X of V n satisfying |X|=2 k + 2 t -3,n=k+t, and
	PR t

This work is partially supported by Vietnamese National Foundation for Science & Technology Development (NAFOSTED)


Florin-Constantin Mihai
email: mihai.florinconstantin@gmail.com

contains supplementary material)

Keywords: drinking water, sanitation, waste wanagement , energy, utilities, public policy, pollution, environment, SDGs, human ecology, global inequalities

The paper aims to reveal one integrated global map which points out the major geographical inequalities in providing basic utilities across the countries using multivariate analysis and thematic cartography. Sixteen indicators with global coverage were selected taking into account the waste collection services, sanitation facilities, drinking water sources, energy, electricity, habitat and demographic conditions. Several data are broken down for the total, urban and rural population in order to outline the rural-urban disparities between and within countries. A special focus is given to waste collection coverage, in order to compute a comprehensive global assessment of this key indicator of public health, which is one of the poorest monitored basic utility. The world countries were divided into 10 classes according to the hierarchical cluster analysis. Each class has particular features outlining the gaps between high, middle and lowincome countries with direct impact on quality of life, public health, and environment.

Introduction:

There are major disparities among and within continents, countries, regions, cities and rural municipalities the access of people to safe drinking water sources, sanitation facilities, regular waste collection services, electricity, and other critical amenities. There are both conguities and disparities overlapping along shared geographical and socio-economic lines as well as historical antecedents. The global report of WHO and UNICEF's Joint Monitoring Programme for Water Supply and Sanitation (JMP) reveals some startling inequalities, particularly in the water, sanitation and hygiene sector (WASH) where 2.5 billion people have no access to an ‖improved‖ sanitation facility and 1 billion people still practice open defecation (WHO-UNICEF, 2014). The Global Waste Management Outlook (UNEP-GWMO 2015) estimates that 2 billion people lack solid waste collection services and 3 billion of people lack access to controlled waste disposal facilities. More than half of world population (54 %) in 2014 lives in urban areas (UN 2014). Population growth and rapid urbanization in developing countries continues to offer serious challenges regarding basic public utilities. Rural to urban migration often means that urban municipalities are overwhelmed, therefore providing poor quality services. Overall, 70 % of those without access to improved sanitation facilities live in rural areas (WHO-UNICEFF 2014). This paper aims a holistic or descriptive approach which combines WASH data sets with other statistics on basic utilities such as waste collection coverage, access to electricity. These are broken down for urban(U) and rural(R) populations and are related to key demographic features in a geographical context at global scale. This paper examines the population access to basic utilities at the national level (T or total) and broken down for urban and rural population (U, R) where these data are available. Sixteen indicators with global coverage are selected for the cluster analysis. Each variable is expressed in percentage values. Most of the aggregate data are provided by international organizations, except for the waste collection coverage (T, U, R). I relied on literature review and reasonable assumptions to compute such data.

Selected basic utilities -data provided by international organizations

Improved drinking water sources available for total, urban and rural population (T,U,R) -According to WHO/UNICEEF Joint Monitoring Programme (JPM) for Water Supply and Sanitation an "improved drinking-water source is one that, by the nature of its construction, or through active intervention adequately, protects the source from outside contamination, particularly faecal matter". Following drinking sources are taken into consideration by JMP: piped water into dwelling, piped water to yard/plot, public tap or standpipe, tubewell or borehole, protected dug well, protected spring, rainwater. See more: http://www.wssinfo.org/definitionsmethods/watsan-categories.

Improved Sanitation facilities (T, U, R) -WHO/UNICEF defines an "improved sanitation facility as the one that hygienically separates human excreta from human contact." Following sanitation facilities are considered improved by JMP: flush toilet, piped sewer system, septic tank, flush/pour flush to pit latrine, ventilated improved pit latrine (VIP), pit latrine with slab, composting toilet.

Access to Electricity (T) -This indicator refers to the percentage of total population connected to electricity. The data source is provided by the World Bank via Global Electrification database (http://data.worldbank.org/indicator/EG.ELC.ACCS.ZS). The electrification rate for urban and rural refers rather to the percentage of households connected to electricity and assumptions about an average household size are used by IEA (2014) in order to determine access rates as a percentage of the population.

Population. Using solid fuels as an energy resource (T) -This indicator is part of the Millenium

Development Goals (MDG S ) monitored by UN Statistics which outlines -the percentage of the population that relies on solid fuels as the primary source of domestic energy for cooking and heating‖. According to the UN, the solid fuels include biomass fuels, such as wood, charcoal, crops or other agricultural waste, dung, shrubs and straw, and coal. (http://mdgs.un.org/unsd/mdg/Metadata.aspx?IndicatorId=29).

Assessment of global waste collection services (WCS)

-The share of the population covered by regular municipal waste collection services. This indicator is the most difficult to measure and to interpret at global scale due to the following: multiple sources of information and documents, scarcity of reliable data for low and middle-income countries, and some data are provided only for urban areas and total coverage must be extrapolated based on demographic data. Also, there not be a clear distinction whether the data refers to a capital city or for all urban areas, and there are various definitions of municipal wastes/household/domestic waste in different countries. Data sources used in order to compute the waste collection coverage vary across countries as do reliable estimates of waste collected out of the total generated (collection efficiency). Therefore, data inconsistencies are inherent at the global scale. A comparative analysis is performed between data provided by organizations, national statistics, -gray‖ and peer-reviewed literature, websites in order to improve data as much as possible as shown in the appendix. Urban population served (WCS_U) -data concerning waste collection coverage rates in urban areas are available in the literature and technical reports, but their quality varies from one source to another. Poorly updated data are the norm in the case of developing countries in Africa and Asia. Some data are available only for one city. Previous studies used such data in order to extend this rate to all urban areas due to the poor availability of data but this should be avoided because within a country major urban disparities may exist between large, middle and small cities. In such cases, the means are calculated representing the waste collection service rates for the urban population. Detailed info is available in the appendix.

Rural population served (WCS_R) -The paper uses following assumptions for low-income countries -no formal waste collection provided in rural areas (0.5 %) except in the cases where such data are available in the literature or other sources as shown in the appendix. Demographic features: urban population (%); slum of urban population (%), population in the largest city (%) as part of UN-World Urbanization Prospects (detailed info in the appendix) Data processing and limitation of study are further examined in the appendix.

Results

The average values (arithmetic means) of this classification (179 spatial units) outline several features: the population lives in urban areas (58 %) of which 21.61 % in slum areas with poor access to basic utilities. Largest cities (often the country's capital) concentrate 33.39 % of the urban population. The inhabitants of all 179 states and territories are less covered by waste collection services (59.49 %) and sanitation facilities (74 %) which are key elements for a decent public health. The population is better served by drinking facilities (88 %) and electricity (79%), but 32 % of them are still dependent on solid fuels for basic needs (cooking, heating, warm water etc). Urban-rural disparities are significant in the case of low and middle-income countries. At the global scale, 76.16 % of the urban population are connected to regular waste collection services and 79.68 % to improved sanitation facilities, but these indicators drop to 43 % and 68.4 % in rural areas. Improved drinking water sources and electrification rate have higher coverage rates in urban areas. Hierarchical cluster analysis outline following 10 typologies, as shown in Fig 1.

Class 1: This class includes most spatial units (60) across America, Europe, Asia and Oceania where the population is well served (>94 %) by each basic facility above the global trend (central bar). Class 2 : It has severe problems regarding the population access to improved drinking water facilities (48.7 %) with significant impact on public health! The other basic utilities are poorly available even for urban population (< 50 %) which are most concentrated in the rudimentary slum areas (75 %!) the highest level across all classes. Class 3: this class groups city-states, island or small high-income countries where the major population lives in the capital -city. The population has almost full access to all basic utilities such as Singapore, San Marino, Kuwait, Hong Kong, Bahamas. Class 4: The second largest class with 27 countries which has a low coverage to WCS (mean -17 % !). Less than half of the urban population has access to regular waste collection services and such services are lacking in rural areas. Population access to drinking water source, sanitation facilities and electricity is below the global average. Almost 2/3 of the population is using solid fuels for domestic purposes! Class 7: this class includes urbanized developing countries (73.85 %) where the majority of the urban population lives in the capital city (74%) of which 25 % in slum areas (Gabon, Djibouti,) with but poorer access to electricity, Rural areas are often neglected with no waste collection services and sanitation facilities are provided for less than 50 % of the population.

Class 8: This class represents one of the worst-case scenarios. Waste collection services are lacking or poorly provided even in urban areas (37.31 %). The population of these countries has the poorest access to waste collection services (12.72 %!) and improved sanitation facilities (16,33 %)! Households are dependent on solid waste fuels (90.8 %!) and with most restricted access to electricity (20.15%) across all classes. Class 9: this class has significant values above the central bar for total urban and rural population. Major inhabitants (>89%) are covered by improved drinking water, sanitation and electricity services despite the fact the share of urban population is only 30% (lowest of all classes) compared with class 1 (78.56 %) or class 7 (73.85 %).

Class 10: this class has poor waste collection coverage rates with major disparities between urban (71.7%) and rural population (6.8%). Such discrepancies are also found for sanitation facilities. More than half of the population uses solid fuels as a domestic energy source and lives in rural areas.

See the Supplementary material ( APPENDIX 1 and 2 for a further examination of data processing and limitations of this study.)

Discussions

Sustainable Development Goals (SDGs) have a key-target to ensure access for all to adequate, safe and affordable housing and basic services, and upgrade by 2030. Furthermore, UNEP-GMWO (2015) establish as priorities the extension of the municipal solid waste collection to 100% of the urban population, to eliminate uncontrolled dumping and open burning by 2020. Such targets are difficult to be achieved in the current context. This paper estimates that approximately 2.8 billion of people (109) lack waste collection services, 0.9 billion in urban areas and 1.9 billion in rural areas! This estimation reveals a worse situation at the global scale than those 2 billion of people reported by UNEP - GMWO (2015). This result may be explained by the fact that this study integrates more spatial units with specific data which are broken down for the total, urban and rural population. Despite the fact, MDGs ignore the role of the municipal waste management sector as a key indicator for sustainable development, [START_REF] Gonzenbach | Solid waste management and the Millennium Development Goals[END_REF] highlight the significant progress which a sound solid waste management can produce to these goals. The waste management sector regularly covers the large and middle cities, but small urban areas and rural regions are exposed to uncontrolled waste disposal practices. Rural areas are often neglected by waste collection services, improved sanitation and drinking water facilities and they have a poor connection to electricity. The disparities between urban and rural settlements are significant in the large and well-populated countries (C5&C10). Rural migration of poor people to the slum areas of mega-cities amplifies this environmental crisis.

Population living in urban slums is highly predisposed to pollution due to the lack or rudimentary waste and sanitation facilities across the world as shown by classes C2, C4 & C8. The solid waste services from African countries are the most decentralized and fragmented of all basic services involving public, private, informal and civil society sectors (UCGL, 2013). Open defecation and waste dumping on surroundings are common practices of poor people.

The population of high-income countries does not use solid fuels as an energy source for domestic activities compared to lower income countries where these are crucial for daily life (C2, C4, C8 & C10). Solid fuels are used more than 90 % of inhabitants in several African countries, Asia (Bangladesh, Laos) and Haiti from Central America. Poor energy access translates into poverty through poor economic performance, in this context waste incineration and landfill gas may be alternative energy sources for African urban areas [START_REF] Scarlat | Evaluation of energy potential of Municipal Solid Waste from African urban areas[END_REF]. Frequently, a high share of the urban population of a country may have a positive effect on waste collection coverage or sanitation facilities (C01 &C03), but in developing countries, major disparities may appear from one country/city to another. Sanitation facilities are related to waste management systems and such disparities must be examined in the field, but frequently WASH studies ignore this aspect. The population which lives in informal settlements is often excluded from such statistics therefore, it is difficult to have accurate data. Despite the fact the low-income countries generate smaller amounts of household waste, they also have low collection rates around 41 %, but there are enormous variation in service across and within cities, especially between slum and non-slum areas (UCLG,2013). Rural population from Africa has serious challenges to get access to safe drinking water sources which frequently are considered as inadequate, unreliable and inaccessible [START_REF] Alhassan | When water is scarce: the perception of water quality and effects on the vulnerable[END_REF]. Countries from classes C2 & C8 [START_REF]Municipal waste management -good practices[END_REF] are most deprived by this basic need for survival, which includes only one country outside Africa continent such as Haiti. Pullen et al., (2014) performed a critical analysis with proper estimations concerning population access to drinking and sanitation facilities at national and subnational levels for Sub-Saharan Africa, outlining the regional disparities within countries. Poor Asian countries and emergent economies (included in C4) have outdated sanitation and waste management infrastructures and the improved drinking facilities are below the global average. The natural hazards damage these poor infrastructures such as earthquakes (Haiti, Nepal) or floods (Bangladesh, India). Post or current conflict areas and political disputes weaken the public or private investments in order to improve the basic utilities for population (Afghanistan, Irak, Syria, Libya). Neither former soviet countries across Central and Eastern European (included in C5 & C6) do not have a full coverage of improved sanitation or waste collection services. New EU members have many challenges in order to fulfill the EU requirements in sanitation and waste management sector (World Bank, 2011). After the breakup of the Soviet Union, the Eurasian countries were left with sufficiently developed water supply and sanitation, district heating, and urban public transport, but solid waste management received less attention (UCGL,2013).

The paper estimates that waste collection coverage is under 50 % of total population in 76 countries and under 50 % of rural population in 105 countries.

Poor coverage rates of improved sanitation facilities (<50%) are found in 49 countries in the case of the total population, 33 of urban and 60 of the rural population. Population access to electricity is under 50 % in 45 countries and electrification rate is under 50 % in 55 spatial units. Despite the fact improved drinking water facilities have a better coverage at the global scale, there are 18 countries where half or less of the rural population has access to such facilities. Frequently, the rural waste management almost is non-existent in developing countries or official data are not available. At least half of the population from 66 countries and territories depend on solid fuels for daily life. Some countries have coverage rates below 10 % for all three basic indicators as waste collection services, improved sanitation facilities (T) and electricity, highlighting severe living conditions (Malawi, Niger, South Sudan). The map highlights that worst scenario cases regarding the population access to basic utilities are encountered across African countries.

Restricted access to electricity, poor sanitation facilities combined with the lack or rudimentary waste collection services in rural and crowd slum areas make living conditions to be barely supportable in developing countries. The poor urban population is concentrated in slum areas (>40 %) in 49 countries particularly in Africa and Asia.

Conclusions:

The map and hierarchical cluster analysis reveal major disparities across the globe concerning population access to basic utilities in a holistic approach. There are three classes (C2, C8, & C04) which include 48 countries (40-Africa, 7-Asia,1-Oceania) with severe issues in providing all basic utilities representing the worst scenario cases! In such countries, the poor conditions of daily life based on solid fuels are the norm unthinkable for those from classes C1& C3 (65 spatial units) where these basic utilities are ordinary almost for all. Furthermore, C7 & C10 have a better coverage of improved drinking water facilities, but poor sanitation and waste collection services (14 spatial units). The class 5 (25 spatial units) includes countries which have serious difficulties in providing waste collection and improved sanitation facilities, particularly in rural areas. The global trend with values close to the general average is reflected by the class C6 (17 spatial units) which partially cover the population to basic utilities and major improvements are needed for small cities and rural areas. The decent life of full population supported by basic utilities is afforded only by 65 countries and territories out of 179 spatial units (36.3 %) included in the cluster analysis. Such geographical inequalities are also amplified by demographic features. The population of developing countries is frequently concentrated in slum areas and larger cities due to internal migration which it makes more difficult to enhance these utilities.

A high share of poor people depends on solid fuels as a domestic energy source and the access to electricity is very limited in the poorest countries. Governments of low and middle-income countries fail to provide the basic needs. Every country, state, region, county, city, and village should have access to basic utilities.

Funding : This work is the result of a fully independent research without funding.

APPENDIX I A. Assessment of global waste collection services (WCS) (1) Total population (WCS_T)

The lack of proper waste management data is notorious because of the limited incentive for central or local governments to provide reliable waste statistics. Such data are provided across the globe by international organizations such UNDS (last update March 2011), Hoornweg and Bhada (2012), Matthews (2012), Waste Atlas Partnership (D-Waste) and with a continental focus as Eurostat (Europe), SWEEP (Maghreb countries), PAHO (Latin America and Carribean) and Asian Development Bank (2014) for the Pacific region. D-Waste web platform was the main source of data for some countries (Niger, Angola, Nigeria). National waste management strategies & plans (Montenegro, Rep. of Moldova), environmental reports (Bosnia & Herzegovina, Romania), PhD thesis (Etriki, 2013-Libya) and other technical reports were consulted in order to complete the database for Ukraine (Demus and Zhechkov 2014), Belarus, Estonia (Reco Baltic Tech,2012). Russian Federation (Perelet and Solovyeva, 2011). Capo Verde (Coelho de Carvalho, 2013), China (CIEPEC, 2013), Lesotho (Bureau of Statistics, 2013), Swaziland (NWM strategy). Waste collection coverage is a key indicator in order to assess the population access to basic public utilities, therefore, several developing countries could not be included in the multivariate analysis due to the lack of any information for this indicator from Asia (North Korea,) Africa (Equatorial Guinee, Guinee-Bissau, Sao Tome and Principe) and Oceania (Papua New Guinea, Fiji, Kiribati, Palau, Micronesia, Nauru, Solomon Islands, Timor-Leste). No data for sanitation facilities were available in the JMP report for Saint Kitts and Nevis, Saint Lucia, Saint Vincent and the Grenadines and Brunei Darussalam.

Collection efficiency is most difficult to translate into the share of population served by waste collection services. Collection efficiency vs waste collection coverage: For example, in Ireland, the collection efficiency is over 90%, but only 78% of total population are served by kerbside collection (72% subscribed to this service) in 2013, according to EPA Ireland report (2014). The difference comes from the -bring system‖ where population outside the kerbside system transports their waste in order to dispose of them in special collection points. Furthermore, the role of informal sector may increase the collection efficiency, particularly in urban areas of developing countries; even the share of urban population served by formal waste collection services is poor. On the other side, there may be a full coverage to WCS, but a poorer collection efficiency due to obsolete waste management infrastructure, littering behavior, low rate of sanitation fee collection, poor management of waste operators, etc.

Cointreau (2006) argues that the most low-income countries experience low levels of waste collection services (30-60 %) and these are slightly higher (50% to 80%) in the case of middleincome countries. UNEP (2011) asserts that waste collection coverage is over 95 % in highincome countries, 70-95 % in middle-income countries and less than < 70 in low-income countries.

Another global analysis (Hornweg and Bhata 2012) shows that collection rates range from a low of 41% in low-income countries to a high of 98% in high-income countries. The recent UNEP-GWMO report (2015) points out the collection coverage rates on a regional basis as follows: Africa (25% to 70%); Asia (50% to 90%); Latin America and Caribbean (80% to 100%), Europe (80% to 100%) and North America (100%). Also, UCGL (2013) reveal that about 63% of local governments in Asia-Pacific have solid waste management programs. However, these values often reflect the urban areas, not total population, especially where the rural population has an important share such as for low and middle-income countries! This paper uses assumptions for high-income countries only where any information about waste collection services is absent, such as total population coverage is 90, urban population, 95 and rural share is calculated based on demographic data provided by Words Urbanization Prospects 2014. These assumptions were applied in the case of Saudi Arabia, E.A.U., Qatar and Oman where attention to solid waste management is increasing (Nizami et Hornweg and Bhata (2012) provide a list of data concerning the waste collection coverage rates for the total or urban population across the world, but some data for the total population are relevant only for urban areas or data are not supported by other sources. As an example, Armenia has 80 % of the total coverage rate, according to Hornweg and Bhata (2012), but this value is not confirmed by other studies which reveal lower coverage rates even for urban areas and poor services in rural areas such as Sergoyan et al., (2011). Belarus has a full coverage for waste collection services according to Hornweg and Bhata (2012), but only 70 % estimated by Reco Baltic (2012).

These cases, described above, outline the importance of a global monitoring of waste management services which should be performed by international organizations in strong relationship with national and regional governments

Calculation of national urban waste collection coverage:

Such calculations are performed in the case of Latin America and Caribbean countries retrieving primary data from PAHO (large and medium nuclei population). Multiple sources for the same country with different values reflect the difficulties in estimating a national urban coverage of waste collection services. In the case of countries where data are available for only one city, this paper proposes further calculations in order to outline an urban national coverage: CCcf is applied taken into account the class of country income level from the list of economies (WB, 2012) as follows: 0.6 for low-income countries (LIC), 0.7 for lower middle-income countries (LMI), 0.8 for upper-middle income countries (UMI).These correction factors highlight the urban disparities which are frequently noticed above (20-40 %) between the capital city, middle and small cities within a country, in the case of the LIC and UMI countries.

Such calculations were applied to 28 countries and the results are revealed in Table 1. These values offer a better clue about national urban waste collection coverage, particularly in the case of poor countries where official waste statistics are not recorded. . These informal settlements which often lacks in providing proper drinking water, sanitation and waste collection services are different from one region to another with their particular geographical features such as -favelas‖ (Brazil) -Boonville‖ (francophone regions), -gear‖ areas (Mongolia) etc. The data provided are not available for all spatial units, in the case of high-income countries (OECD) with full coverage (100%) of WCS, sanitation facilities, improved drinking water sources, electricity a value of 0.5 % was considered.

Pop. in the largest city (% of urban population _provided by UN-World Urbanization Prospects): -population in the largest city is the percentage of a country's urban population living in that country's largest metropolitan area -(http://data.worldbank.org/indicator/EN.URB.LCTY.UR.ZS). Data are not available for all countries, but calculations were performed for the rest of spatial units, taking into account the capital city population or the most populated urban area within a country (http://www.citypopulation.de/mapindex.html) and UN -World Urbanization Prospects 2014 C. Data processing and limitation of study These 16 variables are not available for all countries and some of them have not been updated taking into account the last year available data, particularly for waste management and sanitation sector. Major of these data is provided by international organizations. Data for smallest or island countries are most problematic on the one hand, because of the incomplete data across those 16 indicators chosen for the analysis (most cases of Caribbean, African, and Pacific island countries) and on the other hand, the lack of visibility on the global map where classification could be made (e.g Seychelles, Singapore, San Marino, Marshall Islands, Maldives etc). Data monitored and provided by WHO/UNICEF JMP and UN-MDG indicators are estimations which frequently may differ from national bodies, but they are the main source of information at global scale. The data collected for waste collection coverage reveal the difficulties encountered to compute this key-indicator based on national data and peer-reviewed literature at such scale. The global analysis of the population access to basic utilities requests cautions due to the data availability and reliability, but solid patterns are revealed. This paper integrates the WASH sector with other public utilities and demographic features highlighting a more holistic approach. The paper focuses on the role of waste collection coverage because this indicator is key issue of public health, often ignored, which JMP and MDG indicators should monitor it! Multivariate analysis is performed by agglomerative hierarchical cluster analysis on a measurement table which uses the Euclidean metric with standardization. Each class has own features and statistical values (maximum, minimum, means, standard deviations) which may not reflect the single-country situation due to the cluster analysis. The profile class outlines the mean distances (positives-above the average or negatives-below) in standard deviations of each variable, from the central bar (equivalent to general or global average) which help to interpret the results. These calculations and cartographic representation are made with PhilCarto (http://philcarto.free.fr/) and the detailed results are found in the supplemental file -cluster analysis statistical data. Hierarchical cluster analysis was performed for 179 spatial units (92 %) of the total 194 sovereign states, according to the UN (193 UN members + 1 UN Observer states as Palestine) including independent countries and other territories (Hong Kong). These spatial units include 99.47 % of the world population or 7.175.282 thousand people, according to UN-World Urbanization Prospects 2014 (data for 194 spatial units). This cluster analysis uses the partition number 9 with 10 classes which aggregate the 78.81 % of input data. It is valid only for current primary data used. Any changes such as a new input or update of data (which are necessary for several LIC and UMI countries in the future) could modify the structure of some classes. International organizations or author's assumptions are inevitable in order to complete the database breakdown for total, urban and rural populations at such scale. Improvement of such databases with more accurate data (across all variables taken into consideration) will be desirable for a better analysis of the population access to basic utilities at such scale in the future studies. This paper points out the lack of proper monitoring of such utilities, particularly for the solid waste management sector.

Appendix II -Source of data

Figure 1 .

 1 Figure 1. Population access to basic utilities: global disparities

  Quezon city_100 % (Scheinberg et al., 2010), Bais city _35 % (Paul et al., 2010 ) Bayawan city -30 % (Paul, 2012), Pais city_33 % (Paul et al., 2007), Metro Manila is 83 % and urban national level 40-70 % (Borongan and Okumura, 2010 ) Romania: urban disparities in North-East Region (Mihai, 2013), In the case of Indonesia, Hornweg and Bhata (2012) reveal a national urban coverage of 80 %, but only half (40 % collection efficiency) is assumed by WB (2014) and 70 % by Meidiana et Gamse (2010). Chaerul et al. (2007) show data for 8 large cities which have an average of 91 %. The same difficulties are valid for India, where several data at the city level are analyzed: Surat 93 %, New Delhi -90, Bengaluru_70 (Scheinberg et al., 2010) Jaipur_80 % where the average of cities from class I is 82% according to the data provided by CPCB (2009). Kumar (2015) reveal an urban national coverage of 72 % (which is assumed by this paper), 50-70 % by Zhu et al., (2008) and 51.1 % collection efficiency rate according to D-Waste atlas.

	Uzbekistan: Tashkent (capital city) 100 % (ADB, 2012), 5-58.3 % for urban areas (NWM
	Strategy)
	Philippines: Ghana: Acra -60% (Palczynski, 2002), Atonsu-30 % (Boateng et al, 2014) urban national_85
	% (Scheinberg et al., 2010)
	Georgia: Tiblisi -100 %, Batumi_42 %, Kutaisi 92 % (Hornweg and Bhata, 2012)
	Ethiopia : 67 % Bahir Dar (Lohri et al., 2013 ), Adama_63 % (Hailemariam et Ajeme, 2014)
	Adis Abeba_65 % ( Regassa et al., 2011)., Adis Abeba_80 % (PPIAF May 2011)
	Camerron: Yaounde _ 44%, Douala-60% Achankeng (2003), Buea -30 % (Ndum, 2013)
	Armenia: Erevan_60 % (Arzumanyan, 2004), Berdd_50 % (Buttler, 2008), Hornweg and Bhata,
	2012) total population _100 % (?!)	al., 2015; EA Abu Dhabi
	2013, Palanivel and Sulaiman, 2014 Tanzania: 48 urban national (Hornweg and Bhata, 2012), Moshi-61 % (Scheinberg et al.,
	2010), Dar es Salem_less than 40 % (WB, 2014)
	(2) Urban waste collection coverage (%)
	(2.1.) Data from literature
	Urban disparities regarding WCS:
	Previous studies outlined such disparities across urban areas as follows: Nepal: Kathmandu
	94% in 2003 (Hornweg and Bhata, 2012), Ghoraki -46 % (Scheinberg et al., 2010)
	Mozambique: Maputo-82% (Wilson et al., 2015), Villankula-coastal town 40-50 % (Tas and
	Belon, 2014)
	Pakistan: 50-80% in large cities which drop to 40% in small cities (WB Punjab, 2007), Lahore
	-77 % (Wilson et al., 2015)
	Nicaragua: Managua (capital city)-82 %, all urban areas 65 % (Scheinberg et al., 2010)
	Myanmar: Yangoon (capital city) -80 %, 24 % rest of urban areas (UNEP RCC.AP 2008 )
	Botswana: Gaborone (capital city) 90 %, Mogoditshane -11.7 % (CRA, 2013)
	Mali: Bamako (capital city) -57% (Scheinberg et al., 2010), Sisako_25 % (WB, 2014)

Some cross-countries data at city levels are outlined by Scarlat et al., (2015), Rodic et al., (2010), Karak et al., (2010) Glawe et al., (2005), Achankeng (2003). Other papers provide useful data for total or urban areas in particular countries such as: Bahrain (Al Sabbagh et al., 2013); Bangladesh (Iftekhar et al., 2005), Kuwait (Al Salem and Letieri, 2009), Malaysia (Abas and Wee, 2014), Malawi (Hove, 2011), Sierra Leone (Gora et al., 2015), Vietnam (Matsui et al., 2015), FYR Macedonia (Sapuric and Dimitrovski, 2015) South Africa (CSIR, 2012), Somalia (Collivignarelli et al., 2011), Uganda (Okumu and Nyenje, 2011), Mongolia (Altantuya et al., 2012), Kyrgyzstan (Sim et al., 2013), Gabon (Mbombo et Edou, 2005), Togo (Edjabou et al., 2012), Sri Lanka (Karunarathna & Lokuliyana, 2014), Iran (Fahiminia et al., 2014; Nouri et al., 2014) and Zimbabwe

[START_REF] Sango | Analysis of the solid waste management practices in Chinhoyi: bridging the missing link[END_REF]

. Despite the general trend of increasing coverage rates since the 1990's in some Africa urban areas witness significant decreasing rates. In Abidjan (Cote D'Ivoire), waste collection services dropped from 81 % in 2009 to 59% in 2010 (MIE,2011) and in Harare, the capital city of Zimbabwe, it dropped from 100 % in the 1990s (Achaweg, 2003) drops to 30 % (TARSC, 2010).

Table 1 .

 1 WCSu = {Pllcs-CCf* WCSc (Up-Plcs)}*100/Up where: WCSu = share of urban population (%) served by WCS, Plcs = population of largest city served by WCS (nr. of inhabitants, data from http://www.citypopulation.de/mapindex.html)CCcf = collection coverage correction factor WCSc = share of the largest city population served by WCS Up= urban population (inhabitants) Results of urban national coverage rates (WCSuauthor calculations)

	Country	City	WCSc	Data source	Urban_national
					(WCSu)
	Afghanistan	Kabul	30	Forouhari and Hristovski (2012)	23
	Bhutan	Thimpu	72	Glawe et al. (2005)	60
	Burkina Faso	Ouagadougou	40	Meunier (2007)	30
	Burundi	Bujumbura	41	Mwesigye (2009)	37
	Cambodia	Phnom Penh	80	Glawe et al. (2005)	64
	Central African	Bangui	10	PPIAF_CAF_dec 2012	9
	Republic
	Chad	N'Djamena	20	Karak et al. (2010)	17.6
	Congo R.D.	Kinshasa	3.5	D-Waste Atlas , PPIAF_RD Congo	3
				2011
	Congo	Brazaville	25	Faller & Young (2015)	24.85
	Cote D'Ivoire	Abidjan	70	Ministere des Infrastructures	58
				Economiques,2011
	Djibouti	Djibouti	70	AFD 2014	62
	Gabon	Libreville	20	Mombo and Edou (2005)	22
	Gambia	Banjul	35	Achankeng (2003)	19
	Guinea	Conakry	90	Ouedraogo (2005)	70
	Irak	Bagdad	86	Hoornweg and Bhada (2012)	68
	Kazahstan	Astana	75	Inglezakis et al. (2014)	63
	Liberia	Monrovia	33	Wilson et al. 2015	32
	Lybia	Tripoli	70	Etriki (2013)	62
	Malawi	Blantyre	25	Hove (2011)	22
	Namibia	Windhoek	93	D-Waste Atlas	81
	Senegal	Dakar	77	Ouedraogo (2005)	73
	Sierra Leone	Freetown	40	Gogra et al. (2010)	33.56
	South Sudan	Juba	30.6	Karija et al. (2013)	23.5
	Sudan	Khartoum	65	WMA (2014)	52
	Syria	Damasc	90	Karak et al. (2010)	59
	Rwanda	Kigali	43	REMA 2013 report	36
	Eritreia	Asmara	95.6	Department of Environment in the	79
				Ministry of Land, Water and
				Environment, Asmara
	Togo	Lome	42.1	Edjabou et al. (2012)	34.8

  Table 1 shows the severe situations of some African capital cities concerning the waste collection coverage. Also, Scheinberg et al., (2010) point out that -collection coverage in the 20 reference cities, as in urban areas in general, varies widely, ranging from 25 to 75 per cent in cities where the norm for waste disposal is still open dumping.‖ (3) Rural waste collection coverage:Major African countries lack any formal waste collection services in rural areas except Mauritania (5 %, SWEEP report 2014). , Algeria (70 %), Tunisia (5%) Egypt (15 %) and insular countries such as Mauritius, Seychelles, Capo Verde. This situation is also confirmed by[START_REF] Mwesigye | Africa review report on waste management[END_REF] which outlines that waste management infrastructure is largely nonexistent in rural areas of Africa. Data for Latin American and Carribean countries are provided by PAHO using as reference the small nuclei population for municipalities < 15 000 inhabitants. Central and Eastern European countries have serious difficulties in providing regular waste collection services, particularly in rural areas as confirmed by EPF (2007), EEA(2010) Urban population -the share of the population which lives in urban areas of the total country's population. Data are provided by UN-World Urbanization Prospects 2014 revision for all spatial units. The distinction between urban and rural areas vary from one country to another due to various geographic levels.

							Brink et
	al., (2011), ISWA (2012), Mihai (2015) and Makovetska (2014). Collection coverages rates
	widely vary across Asian countries as follows: Sri Lanka_2% (Vidanaarachchi et al., 2006),
	Yemen-5%, Iran 12 % (Fahiminia et al., 2014), Vietnam-15%, Malaysia-60% (Abas and Wee,
	2014.), Lebanon (99), South Korea (100). Some rural communities are served by waste
	operators, but no concrete data are available about national rural coverage. In such cases, local
	assumption was made according to waste management situation: Azerbaidjan-10 %, Indonesia -
	5 %, Moldova -10 %, Philippines-5 %, India -11 % ( GEC_2012 : 22.86 % in Gujarat State).
	B Demographic features:
	The slum of urban population is part of UN -MDG indicators. It describes the proportion of
	urban population living in slums it ‖is measured by a proxy, represented by the urban population
	living in households with at least one of the four characteristics: (a) lack of access to improved
	water supply; (b) lack of access to improved sanitation; (c) overcrowding (3 or more persons per
	room);and	(d)	dwellings	made	of	non-durable	material.‖
	(http://mdgs.un.org/unsd/mdg/Metadata.aspx?IndicatorId=0&SeriesId=711


Paula Lago

Fréderic Lang
email: frederic.lang@inria.fr

Claudia Roncancio
email: claudia.roncancio@imag.fr

Claudia Jiménez-Guarín

Radu Mateescu
email: radu.mateescu@inria.fr

Nicolas Bonnefond
email: nicolas.bonnefond@inria.fr

The ContextAct@A4H real-life dataset of daily-living activities Activity recognition using model checking

Keywords: Smart home, context, activity recognition, temporal logic

Research on context management and activity recognition in smart environments is essential in the development of innovative well adapted services. This paper presents two main contributions. First, we present ContextAct@A4H, a new real-life dataset of daily living activities with rich context data 4 . It is a high quality dataset collected in a smart apartment with a dense but non intrusive sensor infrastructure. Second, we present the experience of using temporal logic and model checking for activity recognition. Temporal logic allows specifying activities as complex events of object usage which can be described at different granularity. It also expresses temporal ordering between events thus palliating a limitation of ontology based activity recognition. The results on using the CADP toolbox for activity recognition in the real life collected data are very good.

Introduction

Activity recognition in smart environments is a necessary step for the development of innovative services. In the health-care domain, recognizing activities of daily living (ADL) enables health status monitoring, functional assessments and smart assistance. Despite the broad efforts made in recent years to improve activity recognition, ADL recognition (e.g. cooking, washing dishes, showering) is still not commercially available as is physical activity recognition (e.g. running, cycling). ADL recognition is complex and some barriers have hindered its passage from laboratory settings to real-life. One of these barriers is the difficulty of evaluating methods in real-life scenarios, which differ widely from the scripted scenarios that are usually used for testing activity recognition algorithms. Reallife scenarios are inherently imbalanced, not only because some activities are more frequent than others but also because of the different durations of the activities. Learning from imbalanced data poses new challenges and can impact the performance of traditional algorithms [START_REF] Garcia | Learning from Imbalanced Data[END_REF]. Moreover, in real-life there are often several ongoing activities, making it challenging to recognize the "interesting" ones [START_REF] Krishnan | Activity recognition on streaming sensor data[END_REF]. More real-life datasets and shared activity labels are needed to allow researchers evaluating their proposals and comparing the results of their recognition methods [START_REF] Brush | Activity Recognition Research: The Good, the Bad, and the Future[END_REF].

Activity recognition methods are broadly classified into data-based and knowledge-based [START_REF] Chen | Sensor-based activity recognition[END_REF]. Data based methods use machine learning or data mining algorithms to learn a model of activities. However, supervised methods require labeled data which is often hard to acquire. On the other hand, knowledge based methods specify the semantics of activities to be inferred from sensor measurements. Ontologies that specify both objects used and other characteristics of an activity (e.g. actor, location, duration) is one of the most used knowledgebased method for their ability to specify concepts at different granularity and their reasoning capabilities on uncertain knowledge. Nevertheless, ontologies lack support for the temporal characterization of activities [START_REF] Riboni | Is ontology-based activity recognition really effective?[END_REF] which is an important aspect of activity recognition as they take place during a span of time. For ADL recognition it is important to consider context information such as environmental conditions, visitor presence, current location and part of day [14]. Nonetheless, the usefulness of different context variables has not been proven in real-life scenarios due to the lack of available data in the same dataset.

In this paper we present two main contributions. First, we present a real-life dataset of daily living activities. This new dataset, named ContextAct@A4H, will be publicly available with reference to this paper. ContextAct@A4H includes sensor raw data reflecting the context as well as standard daily living annotated activities. Context information can help study how contextual changes affect user behavior and preferences [14]. To the best of our knowledge it will be the first public available dataset including such rich real-life data. ContextAct@A4H was gathered at the Amiqual4Home flat using a large variety of sensors to improve the potential reuse of the data. Researchers can choose the desired "configuration" according to their evaluation requirements. We highlight the experience of collecting the dataset and some lessons learned in the process. The second contribution of this paper, is the experience of using temporal logic for activity recognition. Using temporal logic allows specifying activities as complex events of object usage which can be described at different granularity. It also expresses temporal order between events thus palliating a limitation of ontology based activity recognition. The results on using the CADP toolbox [START_REF] Garavel | CADP 2011: A Toolbox for the Construction and Analysis of Distributed Processes[END_REF] for ADL recognition in the real life collected data are very good.

The rest of this paper is organized as follows: Section 2 presents the experience and the setting up of our experience to collect ContextAct@A4H, a real life dataset of ADL and context data. Section 3 presents the formalism of temporal logic used for ADL recognition in real life settings. Section 4 presents the results of using temporal logic in the recognition of ADL in the ContextAct@A4H dataset. In Section 5 we present a summary of related work in activity recognition methods and real-life datasets. Finally, in Section 6 we present the conclusions of this work and research perspectives.

Amiqual4Home System Architecture and Experience Setup

Amiqual4Home is an experimental platform consisting of a smart apartment, a rapid prototyping platform and tools for observing human activity. For collecting the ContextAct@A4H dataset of activities of daily living, a 28 years old woman lived in the apartment during one week in July 2016 and three weeks in November 2016. The woman is a part of the research group designing the experiment.

In the following we first describe the sensing infrastructure at the apartment and then present the activity annotation process and the dataset itself.

Sensing infrastructure at the smart home

The Amiqual4Home apartment is equipped with 219 sensors and actuators. To make activity monitoring non-intrusive, in our experience all sensors are ambient sensors. No wearable sensors nor cameras were used for this experiment. Sensors allow observing both object usage and context conditions of each room and the exterior. Measuring context conditions is one of the new contributions of the ContextAct@A4H dataset with respect to other publicly available datasets.

We measured the following context variables: temperature, CO2, noise, humidity, presence and music information for each room and weather information for the exterior. Appliance and object usage are measured through electric/water consumption sensors, contact sensors and state change sensors (for lamps, curtains and switches). These measurements are precise indicators of object usage. Other sensors are indirect measures of object usage such as pressure sensor in the bed. The main advantage of the sensing methods we used is that sensors do not interfere with the normal use of objects (no RFID tags that need to be taken care of for example). Table 1 presents a summary of the sensing infrastructure. Some sensors, as those related with energy consumption, are integrated in a single device.

Amiqual4Home uses the OpenHab6 integration platform for all the sensors and actuators installed. Sensors use different communication protocols such as KNX, MQQT or UPnP to send measurements to the central server. To preserve privacy, only local network access is permitted to the sensing infrastructure, no cloud platforms are used. The general architecture of the platform is shown in Fig. 1.

Activity annotation

The choice of activities to be annotated was motivated by two main concerns: being in concordance with available datasets and with the classification of basic

Inhabitant Position Wearable device

Table 1: Sensing devices deployed at the Amiqual4Home apartment Fig. 1: General architecture of the data collection system and instrumental ADL that can be measured at home. Some activities can be measured at different granularity levels. For example eating is annotated as eating breakfast in the ARAS dataset [START_REF] Alemdar | ARAS Human Activity Datasets In Multiple Homes with Multiple Residents[END_REF]. We chose high level labels to reduce the number of different activities preserving the desired semantics while considering time of day as part of context. Some activities were not annotated (like doing laundry) but the event using washing machine fully corresponds with this activity (same for watching tv). The following is the list of annotated and measured activities. Activities were annotated by self-reporting in place at the moment of starting and ending each activity. For this, three different interfaces were available: a web and mobile app, a remote control and a button interface placed strategically Fig. 2: Interfaces used to annotate the ContextAct@A4H dataset.

Activities of Daily

(see Fig. 2). The combination of annotation methods allowed the inhabitant to remember easily to do the annotations and minimized interruptions of the activities. The inhabitant annotated the beginning and end of each activity. The inhabitant reported missing some annotations, specially at the end of the second period when there was more familiarity with the environment. This confirms the fact that sensing technology "dissapears" when it truly blends with our environments.

ContextAct@A4H dataset

We collected a dataset for one week during summer and three weeks during fall in the same apartment configuration. Having data of different months of the year enables both the analysis of the generalization of a model of activities and the analysis of changing behavior throughout the year. As mentioned before, 219 properties were measured during the whole experiment. For the duration of the experiment, all sensors logged their measurements successfully. The accuracy of the measurements was not verified and filtering methods were not used. The properties represent either object interactions or context features. Most object interactions are measured redundantly. For example, opening the fridge is measured by the electric consumption and the door state of the fridge. In this way, the dataset enables many different forms of detecting activities. Context features are measured per room. They include: temperature, carbon dioxide level, noise level, relative humidity, luminosity level and presence in the room. Each context feature is measured at a constant rate, but a change point representation is available. A change is considered when the value varies more than 2% with respect to the last measurement. Additionally, weather information from OpenWeather 7 is logged every hour and visitor presence is self-reported by the user.

The dataset with changepoint representation of features contains a total of 1 473 011 tuples (364394 in july and 1108617 in november) of sensor measurements. A tuple consists of a timestamp, a sensor id and a measurement value. Of those 397 correspond to activity records (157 in july and 240 in november). Figure 3 shows the distribution of time in each activity. Other data logged that can be exploited for different applications is the music information (title, artist, genre and timestamp) corresponding to the music the inhabitant listened while in the apartment.

Using the MCL Temporal Logic to Monitor Activities in Logs of Events

An alternative to self-reporting of activity annotations is automatic detection of activities by analysing the sensor raw data present in the dataset. In this section, we report on our use of model checking techniques to do so.

Model checking [START_REF] Baier | Principles of Model Checking[END_REF] is a formal verification technique that consists in exploring a user-written formal model of a system in order to check the satisfaction of properties describing its proper functioning. The formal model generally has the form of an automaton obtained from a description in a language with mathematically defined semantics. The most general way of defining properties is to use temporal logics [START_REF] Pnueli | The temporal logic of programs[END_REF], which combine the standard connectors of logic with modalities and fixpoint operators that enable to reason about the necessity or possibility to reach certain states of the model.

In this work, we consider so-called action-based temporal logics, which are appropriate to reason about the actions which involve a state change in the model (e.g., the communication actions in a distributed/concurrent system), rather than the contents of states (e.g., the state variables).

In cases where there is no formal model of a system, it turns out that actionbased temporal logics can also be used to analyze sequences of actions generated by a concrete, running system (e.g., logs of events). Indeed, such sequences can be (trivially) seen as particular cases of automata. The model can be simply replaced by the log, which becomes the object on which checks are performed. In this work, we thus naturally consider ContextAct@A4H as log of events.

In practice, we use the CADP toolbox [START_REF] Garavel | CADP 2011: A Toolbox for the Construction and Analysis of Distributed Processes[END_REF], which is equipped for such a task. Among the (more than) 50 tools and code libraries present in CADP, we use in particular the following ones:

-SEQ.OPEN [START_REF] Garavel | Seq.open: A tool for efficient trace-based verification[END_REF] is a tool that can parse a sequence of actions in the SEQ format of CADP and provide an application programming interface with the CADP verification tools, following the principles of OPEN/CAESAR [START_REF] Garavel | OPEN/CAESAR: An Open Software Architecture for Verification, Simulation, and Testing[END_REF]. -EVALUATOR 4.0 [START_REF] Mateescu | A model checking language for concurrent value-passing systems[END_REF] is a model checker that evaluates temporal logic formulas written in the language MCL, an alternation-free modal mucalculus [START_REF] Kozen | Results on the Propositional µ-Calculus[END_REF] extended with data handling, regular expressions, and fairness operators. EVALUATOR 4.0 can be used to verify formulas on any system connected to the OPEN/CAESAR interface, thus including action sequences in the SEQ format.

In the framework our experiment, each event constitutes a line in the log, in CSV format. Each line contains first the event occurrence date (including day time), the sensor id, and the sensor value, separated by semicolons. The first step is to translate this log into the SEQ textual format of CADP, which is done using a simple Unix sed script. The transformation principally consists in turning lines of the form "date; sensor id; sensor value" into the form "A !date !sensor id !sensor value" accepted as input by SEQ.OPEN, where A is a dummy symbol added here for technical (and unimportant) reasons, and where "!" is the symbol used to delimit action fields in CADP.

MCL macro definitions can then be defined to interpret log lines as more abstract events. Each macro definition can be understood as an action pattern that recognizes certain fields in log lines. For instance, the following macro definition recognizes that the light of the office is on, sensor L14 corresponding to a light dimmer located in the office of the Smart apartment: macro Office_Light_On () = { A ... !"L14" ?value:Nat where value > 0 } end_macro Note how the "..." symbol (wildcard) allows the date field to be ignored and how the "?" symbol allows some typed field to be captured in a variable, whose value can be constrained by a Boolean condition (guard) specified by the "where" clause.

Macro definitions can be parameterized as the following one, which matches log lines indicating that a light button in the bathroom (whose sensor id starts with I7 or I11 ) has the value SWITCH passed as parameter: macro Bathroom_Button (SWITCH) = { A ... ?snsr:String SWITCH where (prefix (snsr, 3) = "I7_") or (prefix (snsr, 4) = "I11_") } end_macro Other, more complex macro definitions can be defined by combining simpler ones using Boolean connectors. For instance, the macro definition below detects the fact that either the oven or the cooktop is switched on, where Cooktop On and Oven On are already defined macro definitions: macro Cooking_Appliance_On () = (Cooktop_On or Oven_On) end_macro

In our experiment, we wrote 125 macro definitions.

Once macros have been defined to give simple meanings to complex log events, thus facilitating the log analysis, they can be used in temporal logic formulas to detect activities in the log. We give two examples.

The first example below is a formula that detects the beginning of a shower activity, which is defined as follows: the door of the shower is open then closed, and then the water flows. Angles denote the existence of a sequence of events, defined by a regular expression. The symbol "." denotes sequential composition, "*" denotes repetition (0 or more times), true matches any log event, and not and or have their usual meaning. This formula evaluates to true if their exists a sequence in the log that matches this regular expression.

< true* . Shower_Door (!"OPEN") .

(not Shower_Door (!"CLOSED"))* . Shower_Door (!"CLOSED") .

(not Shower_Door (!"OPEN"))* . Shower_Water_On > true Note how the "!" symbol allows a field to be matched against the value of a data expression (here, a character string constant).

The second example, defined in Figure 4, is slightly more complex. It detects the start of a cooking activity, defined as follows: a food container (the fridge or a drawer) was opened and at least one cooking appliance is on.

This formula is defined as a least fixpoint (mu) which, evaluated on a sequence (as opposed to a general automaton), can be seen as a recursive function on the events of the log. It has two parameters, namely a Boolean Fd Cntnr Opn, which is initially false and becomes true once an event corresponding to the opening of a food container is detected, and a natural number N Ckng Appl On, which counts the number of cooking appliances that are currently on (initially 0). When Fd Cntnr Opn is true and N Ckng Appl On is greater than 0, then the start of a cooking activity was detected. Otherwise, the property is applied recursively depending on the next event that is found in the sequence, parameters being updated accordingly.

CADP detects the time the activity starts as the time when all conditions defined by the model are met. It creates a file with all sensor measurements up to this time as an output. To detect all occurrences of an activity we find the difference between the original dataset and the output file using the grep utility on Linux, and then use this new file as the input log file. This process is repeated until the output file is empty.

Experimental Evaluation

We evaluated the model checking approach for activity start and/or end recognition using ContextAct@A4H taking annotation as ground truth. We defined models to recognize the start of the sleeping, cooking and washing dishes activities and the end of the showering and using toilet activities. When the model infers the start or end of the same activity within 3 minutes, we take the smaller time (greater time) as the start time of the activity (end time of the activity). We mu Ckng_Act ( Fd_Cntnr_Opn: Bool := false, (* true if fridge or drawer was opened *) N_Ckng_Appl_On: Nat := 0 (* nb of cooking appliances that are on *) ) .

if Fd_Cntnr_Opn and (N_Ckng_Appl_On > 0) then true (* cooking activity detected *) else < Food_Container_Door (!"OPEN") > Ckng_Act (true, N_Ckng_Appl_On) or < Cooking_Appliance_On > Ckng_Act (Fd_Cntnr_Opn, N_Ckng_Appl_On+1) or < Cooking_Appliance_Off > if N_Ckng_Appl_On > 1 then Ckng_Act (Fd_Cntnr_Opn, N_Ckng_Appl_On-1) else (* was not a cooking activity *) Ckng_Act (Fd_Cntnr_Opn, 0) end if or < not Food_Container_Door (!"OPEN") and not Cooking_Appliance_On and not Cooking_Appliance_Off > Ckng_Act (Fd_Cntnr_Opn, N_Ckng_Appl_On) end if Fig. 4: MCL formula for detecting the start of a cooking activity calculate the difference between the inferred time and the actual time annotated by the inhabitant. Table 2 shows the results obtained. To evaluate the performance of the activity recognition approach we calculate its precision and recall considering that the annotated activities are the relevant ones that should be recognized. A recognized activity is considered "relevant" if it corresponds effectively to an annotated activity. Precision is the fraction of the recognized activities that are relevant wrt the number of recognized activities. Recall is the fraction of annotated activities that are successfully recognized wrt the number of annotated activities.

Most of the activities have high precision and recall measures, similar to results reported with hidden markov models or support vector machines in other datasets. To provide a comparison, the highest average f-measure (a weighted average of the precision and recall ) reported by Krishnan et al. [START_REF] Krishnan | Activity recognition on streaming sensor data[END_REF] was 0.61 while our average f-measure is 0.72. This depends on many factors such as sensors used, features selected and the number of activities making the comparison non-depending on just the recognition method. In our case, the high precision is due to the precise object usage measurements that we gathered thanks to the sensing devices installed. We can see that the average time difference between the inferred start or end of the activity and the time the inhabitant annotated is rather small. The activity washing dishes has a low precision due to a high number of false positives. The false positives are due to the fact that the only detectable event corresponding to this activity is the sink faucet being opened. Yet, the sink faucet can also be opened for many other activities including washing fruits and vegetables, washing hands, and washing few pieces of tableware while cooking, which were not annotated as washing dishes. Possible ways to increase precision could be to take into account both a minimal proportion of hot water flowing through the sink faucet (taking into account that vegetables and fruits are usually washed with cold water whereas dish washing requires hotter water) and the time during which the sink faucet has been opened (thus requiring to define a minimum time that dish washing usually takes and that hand washing or tableware washing usually do not exceed).

Related Work

In this section we briefly discuss related work on activity recognition and current available datasets of daily living in smart homes.

Daily Living Activity Recognition in Real Life Scenarios

Activity recognition refers to inferring an activity label from observations made through sensing devices. These sensing devices can be either vision-based, wearable sensing or ambient sensing. Vision based sensing is often seen as a privacy invasion and its use is not accepted by many elders. Wearable sensing is better for physical activity such as running or walking and is now commercially available for this. For daily living activities however, wearables can be forgotten by the user and have been used for fined-grained activities such as grabbing a glass or turning the lights on [START_REF] Logan | A long-term evaluation of sensing modalities for activity recognition[END_REF]. Ambient sensing allows inferring object use and coarsed-grained activities. Since activities are often performed with the same objects this is better for daily living monitoring. Also, it is less intrusive as sensing capabilities merge with the environment and do not interfere with normal activity performance.

Sensor-based activity recognition in smart homes methods can be classified in knowledge based and data based [START_REF] Chen | Sensor-based activity recognition[END_REF]. Knowledge based methods use semantic descriptions of activities based on object usage and context features such as location or time of day. The most common methods include ontologies [START_REF] Rodríguez | A survey on ontologies for human behavior recognition[END_REF], situational models and event calculus. Data-based methods, on the other hand, use sensor features to build machine-learned models. The models can be learned with supervised or unsupervised methods. Supervised methods, such as Hidden Markov Models [START_REF] Van Kasteren | Transferring knowledge of activity recognition across sensor networks[END_REF], Bayes Networks and Support Vector Machines [START_REF] Krishnan | Activity recognition on streaming sensor data[END_REF] have shown promising results but need ground truth data to be learned. Unsupervised methods such as clustering, topic models and frequent sequences do not need ground truth data and have been used as methods for activity discovery [START_REF] Rashidi | Stream Sequence Mining for Human Activity Discovery[END_REF].

Most proposed activity recognition methods have been tested in scripted datasets showing promising results. Nevertheless, passing from laboratory settings to real life settings is not as transparent since there are crucial differences in both settings. Activity recognition in real-life datasets differs in the following aspects from activity recognition in scripted datasets:

-Class imbalance: real-life scenarios are inherently imbalanced due to the different frequencies and durations of each activity [START_REF] Logan | A long-term evaluation of sensing modalities for activity recognition[END_REF]. -Intra-class variability: the same activity can be performed in different ways, using different objects, at different locations, etc. [14, 15]. -The Other activity: scripted datasets only represent activities of interest, while in real-life scenarios most of the time it is other activity is being performed [START_REF] Krishnan | Activity recognition on streaming sensor data[END_REF]. This 'other' activity is a highly variable class since it represents many activities.

Datasets of daily living in smart homes

Testing activity recognition and behavior modeling algorithms in real life is difficult due to the lack of real data. Real-life scenarios are difficult to gather both for the costs of equipping a real home and the availability of subjects willing to live in such homes. Therefore, making these datasets public helps advance research and is of great interest for the community. Some equipped apartments over the world, notably: The Aware Home [START_REF] Helal | The Gator tech smart house: A programmable pervasive space[END_REF] at Georgia Tech, Domus at France, Van Kasteren [START_REF] Van Kasteren | Transferring knowledge of activity recognition across sensor networks[END_REF], CASAS at Washington University [START_REF] Crandall | Casas: A smart home in a box[END_REF], PlaceLab [START_REF] Tapia | Activity recognition in the home using simple and ubiquitous sensors[END_REF] at MIT, ARAS [START_REF] Alemdar | ARAS Human Activity Datasets In Multiple Homes with Multiple Residents[END_REF] at Istanbul, Turkey. Most publicly available datasets feature scripted and acted daily life activities, lack ground truth annotations or feature office or other scenario activities that do not correspond to daily living activities. Nonetheless, the Placelab, CASAS and ARAS projects have publicly available datasets of real life daily activities with ground truth annotations. Common activities in these datasets include sleeping, toilet use, taking a shower or bath, eating, leaving home, cooking or preparing meals, washing dishes, working or using computer and leisure activities (relax, watching tv, reading). These are daily living activities that can be measured through available sensors. Eating and fine-grained activities are usually the most complex to recognize [START_REF] Krishnan | Activity recognition on streaming sensor data[END_REF][START_REF] Tapia | Activity recognition in the home using simple and ubiquitous sensors[END_REF]. Context features are often not measured, being the ones measured temperature at some locations and presence in rooms. Nonetheless, rich context information can not only improve activity recognition but also it can help to better understand behavior patterns and user triggers (for example, loud noises may trigger anxiety) [START_REF] Lago | Contextualized behavior patterns for change reasoning in Ambient Assisted Living: A formal model. Expert Systems To Appear[END_REF].

In this paper we have detailed our approach of using temporal logic for ADL recognition in real-life settings showing promising results. We use the CADP tool to describe each activity as a temporal logic property that is checked repeatedly in the log of sensor measurements until all occurrences of the activity have been found. The property is described based on object usage by an expert (in our case the inhabitant). One of the main advantages of this approach over other techniques is the ability to recognize start and end of the activity, thus not requiring to segment sensor data. The model checking approach using CADP also enables to specify durations and gaps between events, by capturing the date fields present in events and storing them as parameters of fixpoint operators. We plan to exploit this feature in the future for carrying out timed analyses of activities. We believe model checking is an interesting alternative for activity recognition in real life settings.

We have also presented the ContextAct@A4H dataset, an annotated real-life dataset of activities and context of daily living covering four weeks of data. One drawback in public datasets for ADL recognition is that there is no correspondence between the activities nor the sensors used, which makes it difficult to compare results from one dataset to the other. This is since available sensors change through time. Data in terms of semantic measured properties can be more stable and we propose to focus on these to compare results and for future datasets. Still, the need of creating shared knowledge and agree on a taxonomy of activities [START_REF] Brush | Activity Recognition Research: The Good, the Bad, and the Future[END_REF] continues, although some common activities emerge. Most datasets include other activities so more data is available but these are not common with other datasets. We have presented a dataset with these common activities and some others as well. The dataset is described with both the sensor measurements and with semantic measured properties.

ContextAct@A4H is the first daily living dataset featuring rich context information. It features six context variables per room in the apartment plus weather, music and number of visitor information. This information is of high interest for applications such as content recommendation, domotics and behavior analysis among others.

Fig. 3 :

 3 Fig. 3: Distribution of activities during summer (left) and fall (right).

Table 2 :

 2 Activity recognition results with model checking approach

This research is supported by the Amiqual4Home Innovation Factory, http://amiqual4home.inria.fr funded by the ANR (ANR-11-EQPX-0002)

http://www.openhab.org/