Mohamed-Bécha Kaâniche

Recognizing Gestures by Learning Local Motion Signatures of HOG Descriptors

. Results show that the proposed method outperforms recent state-of-the-art methods.

Introduction

Gesture recognition from video sequences is one of the most important challenges in computer vision and behavior understanding since it enables to interact with some human machine interfaces (HMI) or to monitor complex human activities. More precisely, it is considered as the bottleneck for precise human behavior understanding. Indeed, in order to detect sophisticated behavior, we need to analyze human gestures and interactions. So, the efficiency and the effectiveness of the gesture recognizer influence those of the behavior understanding process.

The main challenge for recognizing gestures from video sequences is to cope with the large variety of gestures. Recognizing gestures involves handling a considerable number of degrees of freedom (DoF), huge variability of the 2D appearance depending on the camera view point (even for the same gesture), different silhouette scales (i.e. spatial resolution) and many resolutions for the temporal dimension (i.e. variability of the gesture speed).

There are two main categories of techniques in gesture recognition: [START_REF] Kaâniche | Tracking hog descriptors for gesture recognition[END_REF] postureautomaton model techniques where the spatial (posture or appearance features) and the temporal aspects are modeled separately and (2) motion model techniques where there is a unique spatio-temporal model. The former techniques [START_REF] Munoz-Salinas | Depth silhouettes for gesture recognition[END_REF][START_REF] Chu | Posture and gesture recognition using 3d body shapes decomposition[END_REF] use a recognition process composed of a single stage where the parameters of the real target are extracted and then fitted to the adequate gesture model (composed of posture/appearance states and transitions between them). The model fitting is driven by the attempt to minimize a residual measure between the projected model and the person contours (e.g. edges of the body) which requires a very good segmentation of body parts. Thus, such techniques require video sequences without very strong noise. In addition, the gesture model must be modified when a new gesture needs to be recognized. Moreover, the computational complexity of such approaches is generally huge since it is proportional to the number of gestures to be recognized However, the latter techniques [START_REF] Calderara | Action signature: A novel holistic representation for action recognition[END_REF][START_REF] Liu | Learning human actions via information maximization[END_REF] have gained more and more popularity since they use a two stage recognition technique based on learning motion and then classifying unknown ones. Such techniques are more robust to noise and segmentation quality while they still brittle due to illumination variability and occlusions. Also, adding a new gesture is easier since you just have to update the learned database. Therefore, it is crucial to detect motion features that account and describe more faithfully the concerned gesture. use a unique motion model consisting of sparse spatio-temporal descriptors Global motion descriptors or local motion descriptors can be selected depending on the type of video.

In this paper, we propose a new learning-classification framework for gesture recognition [START_REF] Kaâniche | Gesture recognition by learning local motion signatures[END_REF] using local motion signatures [START_REF] Kaâniche | Tracking hog descriptors for gesture recognition[END_REF] of HOG descriptors as a gesture representation. The developed framework is designed to cope with efficiency-effectiveness trade-off. First, we compute for each detected individual in the scene a set of features (i.e. corner points). For each feature, we associate a 2D descriptor (i.e. Histograms of Oriented Gradients (HOG) [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF]), which is tracked over time to build a reliable local motion signature. Thus a gesture is represented as a set of local motion signatures. Second, we learn the local motion signatures for a given set of gestures by clustering them into local motion patterns (i.e. clusters). Last, we classify the gesture of a person in a new video by extracting the person local motion signatures and voting for the most likely gesture w.r.t. learned local motion patterns. The approach has been validated on two public gesture databases: KTH [START_REF] Schuldt | Recognizing human actions: a local svm approach[END_REF] and IXMAS [START_REF] Weinland | Action recognition from arbitrary views using 3d examplars[END_REF] and results demonstrate an improvement over recent state-of-the-art methods.

The remaining of this paper is structured into six parts. The next section overviews the state-of-the-art in gesture recognition. Section 3 summarizes the building process of local motion signatures. Section 4 presents the learning stage and section 5 details the classification stage. Results are described and discussed in section 6. Finally, section 7 concludes this paper by over-viewing the contributions and exposing future work.

Previous Work

In this section, we focus on over-viewing the state-of-the-art of motion model based gesture recognition algorithms which contains two main categories: (1) global motion based methods and (2) local motion based methods. For global motion based methods, [START_REF] Yilmaz | A differential geometric approach to representing the human actions[END_REF] have proposed to encode an action by an "action sketch" extracted from a silhouette motion volume obtained by stacking a sequence of tracked 2D silhouettes. The "action sketch" is composed of a collection of differential geometric properties (e.g. peak surface, pit surface, ridge surface) of the silhouette motion volume. For recognizing an action, the authors use a learning approach based on a distance and epipolar geometrical transformation for viewpoint changes. Lu and Little [START_REF] Lu | Tracking and recognizing actions at a distance[END_REF] propose to recognize gestures via maximum likelihood estimation with Hidden Markov Models and a global HOG descriptor computed over the whole body. The authors extend their method in [START_REF] Lu | Simultaneous tracking and action recognition using the pca-hog descriptor[END_REF] by reducing the global descriptor size with principal component analysis. [START_REF] Gorelick | Actions as spacetime shapes[END_REF] extract space-time saliency, space-time orientations and weighted moments from the silhouette motion volume. Gesture classification is performed using nearest neighbors algorithm and Euclidean distance. Recently, [START_REF] Calderara | Action signature: A novel holistic representation for action recognition[END_REF] introduce action signatures. An action signature is a 1D sequence of angles (forming a trajectory) which are extracted from a 2D map of adjusted orientation of the gradients of the motion-history image. A similarity measure is used for clustering and classification.

As these methods are using global motion, they strongly depend on the segmentation quality of the silhouette which influences the robustness of the classification. Furthermore, local motion, which can help to discriminate similar gestures, can easily get lost with a noisy video sequence or with repetitive self-occlusions. Local motion based methods overcome these limits by considering sparse and local spatio-temporal descriptors more robust to short occlusions and to noise. For instance, [START_REF] Niebles | Unsupervised learning of human action categories using spatial-temporal words[END_REF] introduce the bag of word paradigm for motion recognition with unsupervised learning of local features: space-time interest points. Similarly, [START_REF] Scovanner | A 3-dimensional sift descriptor and its application to action recognition[END_REF] propose a 3-D (2D + time) SIFT descriptor and apply it to action recognition using the bag of word paradigm. Schuldt et al. [START_REF] Schuldt | Recognizing human actions: a local svm approach[END_REF] propose to use Support Vector Machine classifier with local space-time interest points for gesture categorization. [START_REF] Luo | Human action detection via boosted local motion histograms[END_REF] introduce local motion histograms and use an Ada-boost framework for learning action models. More recently, [START_REF] Liu | Learning human actions via information maximization[END_REF] apply Support Vector Machine learning on correlogram and spatial temporal pyramid extracted from a set of video-word clusters of 3D interest points.

These methods are generally not robust enough since the temporal local windows (with short size and fixed spatial position) do not model the exact local motion but arbitrarily several slices of that motion instead.

To go beyond the state of the art, we propose a novel gesture learning-classification framework based on learning local motion signatures which are built thanks to tracking local HOG descriptors over sufficiently long period of time. The proposed gesture representation combines the advantages of global and local gesture motion approaches in order to improve the recognition quality. Indeed, instead of using local video patches which capture only snapshots of local motion, we track local features in order to capture the whole local motion for each feature point.

Simultaneously to our work, several similar approaches have been proposed but with different technical frameworks. For instance, [START_REF] Sun | Hierarchical spatio-temporal context modeling for action recognition[END_REF] describe a method for action recognition using hierarchical spatio-temporal context modeling with three levels : (1) a feature point descriptor based on SIFT, (2) a trajectory transition descriptor and (3) a trajectory proximity descriptor. Multiple-Kernel Learning is then used for pruning. [START_REF] Brox | Large displacement optical flow[END_REF] use a region descriptor composed of two sub-descriptors (the first one is based on SIFT and the second one is based on RGB colors) with a an euclidean distance based similarity measure and an energy minimization technique to build large displacement Optical Flow for human motion analysis. [START_REF] Reddy | Incremental action recognition using featuretree[END_REF] propose a feature tree of spatio-temporal feature points for action representation. The recognition of an action is done by retrieving the nearest neighbor for a query feature and then applying a voting mechanism. [START_REF] Messing | Activity recognition using the velocity histories of tracked keypoints[END_REF] introduce a new descriptor based on velocity history of tracked Shi-Tomasi feature points (with KLT algorithm). To recognize activities, a markov chain model is used with an Expectation Maximization (EM) process for training and conditional probability maximization for classification. Similarly, [START_REF] Matikainen | Trajectons: Action recognition through the motion analysis of tracked features[END_REF] define trajectons which are quantized trajectory snippets of Shi-Tomasi tracked feature points. A bag of words training step along with a Support Vector Machine (SVM) based classification step are used for motion categorization. Lately, [START_REF] Raptis | Tracklet descriptors for action modeling and video analysis[END_REF] build a descriptor dictionary based on the average of oriented gradients and the average of optical flow. Agglomerative clustering and k-medoids are used for building clusters and Support Vector Machine (SVM) is used for classification. Latterly, [START_REF] Yao | A hough transform-based voting framework for action recognition[END_REF] use a Hough-transform based voting framework by training random trees in order to find a mapping between 3D feature patches (i.e. cuboids) and their votes in the Hough space. The classification is based on the multi-class classifier based on the leaves of the trees.

Compared to these works, we believe that our method tackle the recognition problem differently. First, our recognition process is based on the assumption that a gesture is composed of three phases: (1) pre-stroke, (2) stroke and (3) post-stroke; as claimed by [START_REF] Mcneill | Hand and Mind: What Gestures Reveal about Thought[END_REF]. Each phase has different motion patterns compared to other phases. So, we rely on the feature orientation trajectory representation (combining local and global motion information), the dimensional reduction (which is done with PCA by selecting only the most important motion information) and the learning algorithm (tuned to form a meaningful number of motion clusters according to the number of gestures to be recognized), in order to identify the three motion clusters for each gesture. In such way, similar gestures can share one or two motion clusters but not more. Second, we use a people detection step (using background subtraction) in order to reduce noisy motion: only motions relative to human being actions are detected. Finally, we use a probability inference framework with weighted voting scheme for classification process. This framework handle the many-to-many mapping between gesture labels and motion clusters. This contrast with classical methods which use a one-to-many mapping or feature-tree based classifiers (e.g. [START_REF] Reddy | Incremental action recognition using featuretree[END_REF], [START_REF] Yao | A hough transform-based voting framework for action recognition[END_REF]). In addition, the proposed classifier can handle the differentiation between similar gestures and gives a recognition likelihood for each of them.

Local Motion Signatures Generation

People Detection and Feature Selection

People detection is performed by background subtraction to determine moving regions followed by a morphological dilation [START_REF] Nghiem | Controlling background subtraction algorithms for robust object detection[END_REF]. Then a people classifier is applied to determine bounding boxes around single individuals. The people bounding boxes define a mask for feature point extraction. This step not only limits the search space for feature points but also separates distinct moving regions: corresponding to different individuals. This enables to apply the gesture recognition process to different people until they overlap each other.

Feature selection is then performed for each detected person using Shi-Thomasi corner detector [START_REF] Shi | Good features to track[END_REF] or Features from Accelerated Segment Test (FAST) corner detector [START_REF] Rosten | Machine learning for high-speed corner detection[END_REF]. Then corner points are sorted in decreasing order according to the corner strength. After that, we select the most significant corners by ensuring a minimum distance among them. Thus, feature points enable us to localize points where HOG descriptors can be computed since they usually correspond to locations where motion can be easily discernible.

HOG Descriptor Generation

For each feature point, we compute a local HOG descriptor [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] from a descriptor block composed of 3 × 3 cells; each of them having a pixel size of 5 × 5: The feature point is the center of the central cell of the block. The gradient magnitude g and the gradient orientation θ are computed for all the pixels in the block using respectively equation 1 and equation 2 from the image gradients computed by simple 1D-filters (g x and g y ).

g(u, v) = g x (u, v) 2 + g y (u, v) 2
(1)

θ(u, v) = arctan g y (u, v) g x (u, v) (2)
For each cell c ij where (i, j) ∈ {1, 2, 3} 2 in the block, we compute a feature vector f ij by quantizing the unsigned orientation into K orientation bins weighted by the gradient magnitude as defined by equation 3.

f ij = [f ij (β)] T β∈[1..K] (3)
where f ij (β) is defined by equation 4.

f ij (β) = (u,v)∈cij g(u, v) δ[bin(u, v) -β] (4)
The function bin(u, v) returns the index of the orientation bin associated to the pixel (u,v) and the function δ[] is the Kronecker delta. Therefore, the 2D descriptor of the block is a vector concatenating the feature vectors of all its cells normalized by the coefficient ρ which is defined in equation 5.

ρ = 3 i=1 3 j=1 K β=1 f ij (β) (5)

Feature/HOG descriptor Tracking

Let us suppose that we have detected a feature point and associated to it a HOG descriptor d t-1 in the frame f t-1 , we are now interested to determine the descriptor d t in the frame f t which can be identified to d t-1 (the center of that descriptor can be identified to the previous feature point). The basic idea is to minimize a quadratic error function E(d t , d t-1 ) in a neighborhood V ft in the frame f t corresponding to the predicted position of d t-1 obtained by an extended Kalman filter. In the case when several descriptors (d 1 t , d 2 t , ..., d k t ) in this neighborhood satisfy the minimum of the error function, we compute the visual evidence (intensity difference in gray-scale) between each descriptor and the descriptor of the previous frame to track d t-1 . The tracker will choose the descriptor that has the nearest visual evidence to d t-1 .. A newly computed descriptor initializes a new tracking process through the extended Kalman filter. For a tracked HOG descriptor d t-1 in the frame f t-1 , we determine the descriptor d t in the frame f t which can be identified to d t-1 through the "Predict" and "Correct" stages of the Kalman filter. When a descriptor is lost, it may be replaced by a new computed descriptor associated to a newly detected corner. Fig. 1 illustrates the tracking algorithm of HOG Descriptors. In the following, we describe respectively the Kalman filtering with descriptor metrics and the effective HOG descriptor tracking algorithm (actually performing the measurement after prediction and before correction).

Kalman Filtering and Descriptor Metrics

In order to track the descriptor position, we use a Kalman filter with a linear randomwalk motion model for prediction. The basic idea of a Kalman filtering based tracker is to recursively estimate the state vector given the last estimate and a new measurement which is made by the traditional tracker. The state vector X used by the Kalman filter is defined by equation 6.

X = [ p x p y v x v y d ] T (6)
where (p x , p y ) is the position of the descriptor, (v x , v y ) is its velocity and d is the descriptor value. A candidate descriptor (which has not been tracked yet) is described by a measurement vector Z as defined in equation 7.

Z = [ p x p y d ] T (7)
When a corner point is newly detected and its correspondent descriptor is computed (first appearance of the individual or replacing a lost descriptor), the Kalman filter is initialized with the state X (0) with the speed of the individual centroid and with the initial covariance matrix P (0) using large variances for the speed. At each tracking step, the Kalman filter predicts a state X (t) from the previous actual state X (t-1) and the motion model. Using the predicted state and the apriori covariance matrix, the HOG tracking algorithm returns the actual current measure to the filter. Finally, the filter computes the actual current state by updating the predicted state with the innovation between the actual measure and the predicted measure. Hereafter, the static filtering of the descriptor is detailed. First of all, we define an error function E that measures the dissimilarity between two given descriptors d (n) and d (m) according to equation 8:

E(d (n) , d (m) ) = 9×K i=1 (d (n) i -d (m) i ) 2 (8)
where

d (n) i and d (m) i
are respectively the i th component of the descriptors d (n) and d (m) . We want to calculate the estimate d such that the least square error between past measurements (i.e. d (1) , ..., d (t) ) and the descriptor value d of the state vector is minimum. The solution for this minimization problem is given by this equation:

d = 1 t t i=1 d (i) (9)
Since we aim to have an estimate of the state of the descriptor at each step of the tracking, we use the recursive least square method by using the results of equation 10.

d(t)

actual state

= d(t-1)

predicted state

+ Gain 1 t ( Actual measure d t - Predicted measure d(t-1) ) Innovation ( 10
)
Here the gain specifies how much do we pay attention to the difference between what we expected and what we actually get. Note that the gain decreases while the tracking advance which means that we become more and more confident in the descriptor estimation while the tracking progress. To decide whether the descriptor is correctly tracked, the following constraint should be verified:

E( d(t) , d(1) ) ≤ 9 × K 100 ( 11
)
where the constant 9/100 is set empirically. In order to compute the actual measure, the HOG tracking algorithm needs two metrics: A distance between a state vector and a measurement vector and a confidence measure between these two vectors. Equation 12 defines a distance D between a candidate descriptor Z in the current frame and a tracked descriptor X through previous frames.

D(Z, X ) = α E(Z d , X d ) σ d ||Z d || + ||X d || + 1 + γ ||Z p -X p || σ p (12)
where α and γ are empirically derived weight parameters, Z d , X d , Z p , X p are respectively the estimated value and the descriptor position of Z and X , and σ d and σ p are the covariance parameters extracted from the Kalman filter's covariance matrix. The first term of the distance represents the scaled difference between the two descriptor values and the second term represents the difference between the candidate and predicted descriptor location. The confidence C in the candidate descriptor Z to correspond to the tracked descriptor X is defined by equation 13.

C(Z, X ) = 1 1 + D(Z, X ) (13)

The HOG Descriptor Tracking Algorithm

The tracking algorithm consists in a downhill search around the predicted position by minimizing the quadratic error function E. Thus, we determine search regions for next measurements using last states, predicted states and uncertainties and then we get new measurements in the search regions. Note that as a preliminary stage, all positions in the search area are used to compute the candidate descriptors. The confidence measure (as defined in equation 13) is used to select the best solution, if the downhill search gives several solutions. For each descriptor, the tracking algorithm of 2D HOG descriptors is run as described hereafter. Where the ellipse procedure returns the ellipse with foci ( X (t-1) , X (t) ) and eccentricity e defined by equation 14.

e = c a ( 14
)
where c is the focal distance and a is the semi-major axis of the ellipse which is computed as defined by formula 15.

a = c 2 + b 2 ( 15
)
where b is the semi-minor axis computed as defined by formula 16.

b = c + σ 2 x + σ 2 y ( 16
)
Algorithm 1 2D HOG descriptor tracking algorithm

Require: X (t-1) , X (t) , P - t {Last estimated state, predicted state and error covariance matrix} Ensure: Z (t) {The actual measure} 1: R ← ellipse( X (t-1) , X (t) , P - t ) {Compute the search region} 2: S ← ∅ {Initialize the set of candidate measures} 3: for all Z ∈ R do

4: if E(Z, X (t) ) < 9 K 100 then 5: S ← S ∪ {Z} 6:
end if 7: end for 8: maxConf idence ← 0 9: for all Z ∈ S do 10:

conf idence ← C(Z, X (t) )+C(Z, X (t-1) ) 2 11:
if conf idence > maxConf idence then 12:

maxConf idence ← conf idence 13:

Z (t) ← Z 14:
end if 15: end for where σ x and σ y are the variance extracted from the covariance matrix P - t of the Kalman filter. Note that b ≥ c which implies that b 2 + c 2 > 2 c 2 and thus a ≥ √ 2 c (using equation 15). This ensures that the search region has a minimum size according to the focal distance which is the half of the predicted motion of the descriptor.

LMSs extraction

For each tracked HOG descriptor, we associate to it a temporal HOG descriptor from which we extract a local motion signature (LMS) by applying several normalizations. The temporal HOG descriptor is the vector obtained by the concatenation of the final descriptor estimate d and the positions of the descriptor during the tracking process. The dimension of this vector is 9 × K + 2 × where is the number of the 2D tracked positions. If we assume that T d = [(x 1 , y 1 ), ..., (x , y )] T is the array of the descriptor d locations, then the temporal HOG descriptor is the heterogeneous vector V = [ d T d ] T . Given the tracked position vector T d , we define the line trajectory vector L as:

L d = [(w 1 , h 1 ), ..., (w -1 , h -1 )] T (17)
where w i = x i+1 -x i and h i = y i+1 -y i . The trajectory orientation vector

Θ d = [θ 1 , ..., θ -2 ]
T is computed thanks to the formula defined by equation 18.

∀i ∈ [1, -2];

θ i = arctan(h i+1 , w i+1 ) -arctan(h i , w i ) (18)
where the arctan function returns the orientation of the given line with respect to the x axis. Since -2π ≤ θ i ≤ 2π, we normalize the vector by dividing all its components by 2π. Thus, given as input the set S of annotated local motion signatures generated with all the training videos, the k-means algorithm outputs k video-words S i , i = 1, 2, ..., k. The value of k is empirically chosen so that is large enough to describe correctly the set of the m gestures to learn (k > 3 × m). The lower bound for choosing of k is justified by analyzing the videos illustrating gestures [START_REF] Mcneill | Hand and Mind: What Gestures Reveal about Thought[END_REF]: gestures are usually composed of three units of coherent motion (i.e. pre-stroke, stroke and post-stroke) and in our representation, these units of motion correspond to local motion patterns. Thanks to the cluster membership map provided by the k-means algorithm, we annotate each video-word with the gesture labels associated with the LMSs of this cluster.

Maximization of Mutual Information

Once we have obtained the video-words, an optional step is to reduce their dimensionality by compacting them into code-words. To achieve this goal, we propose to apply Maximization of Mutual Information (MMI) algorithm [START_REF] Liu | Learning human actions via information maximization[END_REF] on the clusters generated by the k-means algorithm. Let C be the centroids of the generated clusters

C ∈ C = [µ 1 ..µ k ]. Let G be the gesture labels G ∈ G = [g 1 ..g m ].
With the cluster membership map A : S → C, we define the conditional probability distributions P (C|G) and P (G|C) by equations 19 and 20.

P (C = µ i |G = g i ) = Card(Label -1 (g i ) ∩ A -1 (µ i )) Card(Label -1 (g i )) (19)
P (G = g i |C = µ i ) = Card(Label -1 (g i ) ∩ A -1 (µ i )) Card(A -1 (µ i )) (20)
Where the function Label is the map between feature LMSs and gesture labels; Card(.) is the cardinal operator. By taking as definition of the marginal distributions of C and G the formulas 22 and 23, we can verify that these definitions (i.e. equations 19 and 20) match the conditional probability definition (c.f . equation 21).

P (G = g i |C = µ i ) = P (G = g i , C = µ i ) P (C = µ i ) = P (C = µ i |G = g i ) P (G = g i ) P (C = µ i ) (21)
P (C = µ i ) = Card(A -1 (µ i )) Card(S) (22)
P (G = g i ) = Card(Label -1 (g i )) Card(S) (23)
Thus, we can deduce the joint distribution of C and G from equation 21 which gives:

P (G = g i , C = µ i ) = Card(Label -1 (g i ) ∩ A -1 (µ i )) Card(S) (24)
Hence, the mutual information between C and G which measures how much information from C is contained in G is:

M I(C, G) = µi∈C,gi∈G P (C = µ i , G = g i ) log P (C = µ i , G = g i ) P (C = µ i )P (G = g i ) (25)
The goal of MMI algorithm is to reduce incrementally the size of the video-words C in order to obtain a compact set of code-words Ĉ by keeping the value of M I( Ĉ, G) as high as possible and the value of M I( Ĉ, C) (which measures the compactness of Ĉ with respect to C) as low as possible. At each step of the algorithm, the pair of videowords that gives the minimum loss of mutual information when merged, is chosen. The merge is actually done if and only if the loss of mutual information (c.f . formula 26) generated by the merge of this optimal pair is not larger than a predefined threshold or if the minimal number of clusters is reached. Before the optimization process, the set C corresponds to video-words and after that process, the optimal set Ĉ corresponds to code-words.

So, the trade-off between the compactness of the optimal set and the discrimination criterion (maximum of mutual information) when merging video-words µ i and µ j can be solved by equation 26(c.f . Liu & Shah 2008 [START_REF] Liu | Learning human actions via information maximization[END_REF]).

∆M I(µ i , µ j ) = k∈{i,j}

P (C = µ k )D KL (P (G|C = µ k )||Q(G|C = µ)) (26)
Where D KL (.||.) is the Kullback-Leibler divergence (c.f . formula 27 ), Q(G = g|C = µ) is defined by equation 28 and µ is the resulting merged video-word.

D KL (P (.|y)||Q(.|z)) = x P (x|y) log( P (x|y) Q(x|z) ) (27)
Q(G = g|C = µ) = P (C = µ i )P (G = g|C = µ i ) P (C = µ i ) + P (C = µ j ) + P (C = µ j )P (G = g|C = µ j ) P (C = µ i ) + P (C = µ j ) (28)
The non-recursive version of the MMI algorithm is described hereafter (Algorithm 2). Note that ⊗ is the merging operator which is applied to two video-words.

Compared to the code-words of [START_REF] Liu | Learning human actions via information maximization[END_REF], our code-words already integrate the spatiotemporal structural information which is not the case of the formers. Indeed, our codeword is a compact information of local motion signature clusters which can characterize directly gestures.

5 Gesture Classification

Offline Recognition

The k-nearest neighbor algorithm is one of the most common classifier in the literature. The main idea behind this algorithm is to select the k-nearest neighbors (i.e. code-words) of an input LMSs and then assign it to the gesture label that casts a majority vote. In order to obtain always a majority vote, the "k" parameter is usually an odd number to prevent tie cases. The main advantage of this algorithm is that it is an universal approximator and can model any many-to-one mapping very well. The drawbacks consist of the lack of robustness for high dimension spaces and high computational complexity with huge training data-set. In order to adapt this algorithm to our training data-set, we must cope with the many-to-many mapping between code-words and gesture labels. A suitable solution is to make a voting mechanism which transforms this mapping into a many-to-one mapping.

Let T = {(c, g)/c ∈ C&g ∈ G&g ∈ Label -1 (c)} our final learned database with cardinal N . The likelihood L(c|g) of a particular cluster c given a gesture g is defined by equation 29. for all µ i , µ j ∈ Ĉ/µ i = µ j do 6:

L(c|g) = P (G = g|C = c) (29
Compute ∆M I(µ i , µ j )

7:
if ∆M I(µ i , µ j ) < minimalLoss then 8:

minimalLoss ← ∆M I(µ i , µ j )

9:

merge i ← µ i 10:

merge j ← µ j 11:
end if

12:
end for 13:

if minimalLoss < &[Card( Ĉ) -1] > Card(G) then 14: Ĉ ← Ĉ -{merge i , merge j } 15: Ĉ ← Ĉ ∪ {merge i ⊗ merge j } 16:
Compute the new conditional density Ĉ 17:

C ← Ĉ 18:
end if 19: end while We define the likelihood measure of a gesture g according to k observed clusters c i , i ∈ [1..k] by:

L(g|c 1 , ... , c k ) = k i=1 L(c i |g) h∈G k i=1 L(c i |h) (30)
Note that this likelihood measure satisfies the equation 31.

g∈G

L(g|c 1 , ... , c k ) = 1 (31)
During the classification process, testing a video sample generates several LMSs lms i , i ∈ [1..M ]. Each descriptor casts votes for k nearest code-words. If we note L(g|lms i ) the likelihood measure of a gesture g according to the k nearest code-words from lms i , then the gesture associated to the sample is defined by equation 32 and its recognition likelihood RL is defined by equation 33.

g recognized = arg max g∈G M i=1 L(g|lms i ) (32) RL(g recognized ) = M i=1 L(g recognized |lms i ) M (33)
When ties (i.e. several gestures with the same likelihood) occur, the classifier is unable to classify the new input. Then, the new input is fed to the learner which prompts the user for the gesture label. Two cases can be distinguished:

• The new gesture has been already learned: The user decides which gesture wins the vote and the learned clusters are updated according to this choice.

• The new gesture has not been learned: The user gives the appropriate gesture label and existing clusters are updated and eventually new clusters are created for the new gesture label.

Algorithm 3 describes the modified version of the k-nearest neighbors for our learning-classification framework. This version of the algorithm supposes that each Algorithm 3 k-nearest neighbors -offline version Require: T {The training data-set} lms i , i >= 1 {The generated local motion signatures from the test sequence} Ensure: g recognized , recognitionLikelihood(g recognized )

1: M ← 1 2: while an lms i is generated do

3:
execute the usual k-nearest neighbors for lms i 4:

g M recognized ← arg max g∈G Likelihood M (g) 5:
Compute RL(g recognized )

6:

M ← M + 1 7: end while test sequence contains one and only one gesture.

On-line Recognition

Now, we are interested to adapt this algorithm for on-line recognition where several gestures can occur in a video sequence. For that purpose, we cannot wait for all local motion signatures to be computed in order to estimate the likelihood of gesture recognition. So we derive a recursive equation from equation 32 by considering that local motion signatures lms i , i ∈ [1..M ] are indexed by their chronological order of computation which gives the equation 34.

g M recognized = arg max g∈G Likelihood M (g) (34)
Where Likelihood 1 (g) = L(g|lms 1 ) and for M > 1, Likelihood M (g) verifies the recursion defined by equation 35.

Likelihood M (g) =Likelihood M -1 (g) + 1 M (L(g|lms M ) -Likelihood M -1 (g)) (35)
In addition, we must integrate the time duration of a gesture in the learning-classification process to decide when to stop the recognition process and to start a new one. We assume that the duration of any gesture is ruled by a duration of life law (i.e. Poisson law). So, the samples (i.e. videos) of the training data-set for a given gesture are instances of a random variable with exponential distribution. We know that if p is the number of instances of a gesture in the training data set and i , i ∈ [1.

.s] are the duration of these samples, then a 100(1 -α)% exact confidence interval for the mean duration 1 λ is given by equation 36.

1 λ 2s χ 2 2s;α/2 < 1 λ < 1 λ 2s χ 2 2s;1-α/2 (36)
Where 1 λ is defined by equation 37 and χ 2 k;x is the value of the chi squared distribution with k degrees of freedom that gives x cumulative probability.

1 λ = p i=1 i p (37)
Then, we can consider that a gesture is recognized if and only if its duration is in the confidence interval and we have reached a local maximum of likelihood. So the on-line version of the k-nearest neighbors can be described by algorithm 4. To use this on-lineversion, we can compute a sliding window algorithm [START_REF] Kim | Simultaneous gesture segmentation and recognition based on forward spotting accumulative hmms[END_REF] which detects the pre-stroke phase of gestures, calls the on-line classifier and solves the issue of overlapping prestrokes.

Experiments and Results

In order to validate the proposed algorithms, we have carried out three experiments: one for the tracking algorithm validation and two for gesture recognition algorithms.

Tracking algorithm validation

We have carried out tests for our tracking algorithm on three data-sets: a synthetic dataset and two real data-set (KTH [START_REF] Schuldt | Recognizing human actions: a local svm approach[END_REF] and IXMAS [START_REF] Weinland | Action recognition from arbitrary views using 3d examplars[END_REF]). We have chosen to use K = 9 orientation bins. So the size of a 2D HOG Descriptor is 81. We have found that the optimal values for the empirical weights α and γ of the distance D are respectively 5 and 2. The minimum distance between corner points (i.e. HOG descriptors) is set to 9. These parameters and the noise variances of the Kalman filter have been fixed by testing the algorithm on the validation data-set of the KTH database. Hereafter, we detail the results for each data-set. Compute RL(g M recognized )

11:

M ← M + 1 12:
end while 13: until duration ∈ conf idenceInterval(g recognized ) & previousLikelihood > RL(g M recognized )

Tracking Results on Synthetic Sequence

In order to demonstrate the effectiveness of the HOG tracker, we have tested it on a synthetic data-set as illustrated by fig. 2. The generated sequence is composed of 247 frames. This experiment has been carried out only for benchmarking and as a proof of consistency of our tracking algorithm. The test sequence contains a single static sprite moving with a variable velocity (linear and angular) in a uniform background. During the whole sequence our tracker has lost only 39 descriptors while the mean number of descriptors per frame is 35. The lost of descriptor occurs when there is a sudden and strong change in the motion direction. This is due to the linear motion model used by the Kalman filter. An improvement to cope with this high temporal gradient is to use more sophisticated motion model (e.g. Brownian motion).

Tracking Results on KTH Sequence

To go forward in the validation of the developed tracker, we have carried out a test on the validation data-set of the KTH database. Fig. 3 illustrates the results on KTH database and table 1 resumes the obtained results. This table describes the mean, variance, minimum and maximum values of the number of descriptors (detected, tracked and lost) per frame. The proposed tracker outperforms the KLT feature point tracker [START_REF] Shi | Good features to track[END_REF] (there are only nine tracked feature points per frame in average) which is sensitive to noise and thus loses many more feature points.

Gesture Recognition on KTH Database

The KTH database [START_REF] Schuldt | Recognizing human actions: a local svm approach[END_REF] contains 600 videos illustrating six actions/gestures: (1) walking, (2) jogging, (3) running, (4) hand waving, (5) hand clapping and (6) boxing. Each action/gesture is performed many times by 25 actors for four different scenarios. Thus, A multi-view experiment has been also carried out excluding the fifth view point (i.e. the top view) in order to compare the results with [START_REF] Liu | Learning human actions via information maximization[END_REF]. We learn gestures from three selected views and classify gestures with the remaining view. We repeat the

Discussion

In this paper we have proposed four new techniques: (1) the feature/HOG descriptor tracking algorithm with Kala filtering, (2) gesture modeling technique which represents a gesture as a set of LMSs, (3) gesture learning technique which uses k-means followed by MMI and (4) Gesture classifying technique which uses k-NN with a novel voting mechanism. For the gesture learning, the novelty is the estimation of the k parameter of the k-means algorithm (number of LMSs clusters). In fact, the value of the k parameter for both k-means and k-nearest neighbor algorithms is mainly dependent on the number of gestures to be recognized, the gesture database size (i.e. number of gestures, number of view points per gesture). Indeed, when we process a multi-view database of n gestures all captured under m view points, the constraint on the parameter k of the k-means algorithm becomes k > 3×n×m since local motion patterns for each gesture phase (i.e. pre-stroke, stroke and post-stroke) can be different for the view points. To avoid tuning parameter k, the Mean Shift clustering algorithm [START_REF] Georgescu | Mean shift based clustering in high dimensions: A texture classification example[END_REF] and the SVM classifier can be used. Also, the time precedence constraints among local motion signatures is to be studied. However, when the different gestures to recognize are composed of different local motion patterns, this requirement is not necessary. Nonetheless, if we want to differentiate two very similar gestures sharing the same motion patterns but in different time-line order then it will be convenient to use it. The main issue for the on-line recognition is to set up an overlapping sliding window to detect presto and so launch the recognition process. We are currently working to solve it.

We think that we have developed a generic approach. Indeed a low resolution of the video is the main limitations of the approach (in particular to track corner points). But even with KTH database, significant numbers of corners and LMSs have been obtained. Moreover, LMSs enable to represent large variety of actions. In fact, we have proposed the most compact representation to address gestures in KTH and IXMAS databases but more features can be added to recognize finer gestures. For instance, adding time to LMSs will enable to differentiate between slow or fast motion, adding the relative position of LMSs to the body center will enable to differentiate between similar gestures (e.g. waving from left or from right hand), and so on.

Conclusion

A novel learning-classification framework using local motion signatures has been proposed for gesture recognition. Our main contribution is the gesture representation combining advantages of global and local gesture motion models. Also a novel HOG tracking algorithm have been proposed to build this gesture representation. The local motion signatures can be considered as a local version of the global action signature proposed by [START_REF] Calderara | Action signature: A novel holistic representation for action recognition[END_REF] with the advantage of capturing also local motion. Compared to the global PCA-HOG descriptor proposed by [START_REF] Lu | Simultaneous tracking and action recognition using the pca-hog descriptor[END_REF] (one global HOG descriptor for each gesture/action), the proposed gesture/action representation consists of a set of local signatures which accounts more faithfully for local motion. Instead of computing a global HOG volume for a person already tracked, we use local HOGs tracked independently. Our method contrasts from common local motion methods by tracking salient HOG descriptors instead of computing arbitrary time-volume of HOG descriptors. We propose also a novel voting mechanism to deal with the many-to-many mapping between video-words and gesture labels. Results show an improvement w.r.t. recent state-of-the-art methods. As future work, we plan to validate the on-line version of the proposed classifier on realworld video databases like Home-care applications. The gesture representation can be enhanced to enable the detection of the frailty level of elderly people by analyzing the way people are sitting down or getting up from a chair (e.g. characterizing the gesture manner, the gesture speed). This protocol is already used by doctors for evaluating elders and the challenge is to automate this protocol.

  Our gesture representation is a set of Local Motion Signatures (LMSs) which are generated through four steps: (1) People Detection/Feature Selection, (2) HOG Descriptor Generation, (3) Feature/HOG descriptor Tracking and (4) LMSs extraction.

Figure 1 :

 1 Figure 1: HOG Descriptor tracking using extended Kalman filter

) Algorithm 2

 2 Maximization of Mutual Information (MMI) Algorithm Require: C, G, C, G {inputs} Ensure: Ĉ, Ĉ {outputs} 1: Ĉ ← C 2: minimalLoss ← 0 3: while minimalLoss < & Card( Ĉ) > Card(G) do

Figure 2 :

 2 Figure 2: Synthetic data-set: Red rectangles represent the tracked descriptors and the lines represent their trajectories.

Figure 3 :

 3 Figure 3: KTH data-set: red rectangles represent the tracked descriptors, white ones represent the newly detected descriptors and the lines represent the trajectories of tracked descriptors.

Figure 4 :

 4 Figure 4: Frames from the IXMAS database illustrating a turn-around action.

  (a) Output of the proposed tracker with short term motion: only few descriptors and their correspondent motions are displayed. (b) Output of the proposed tracker with long term motion: different colors indicate different motion directions

Figure 5 :

 5 Figure 5: Outputs of the proposed tracker with short term and long term motion.

  The resulting vector is noted Θd . The local motion descriptor is defined as the concatenation of the descriptor estimation d which indicates the texture involved in the motion and the normalized trajectory orientation vector Θd which represents the motion. Its dimension is 9 × K + -2. To reduce the dimension of the local motion descriptor, we apply Principal Component Analysis (PCA) and project the θ i on the three first principal axis θ1 , θ2 , θ3 . Since PCA cannot handle trajectories of different length, we first extract all sub-trajectories of length 3 from available trajectories by slicing them. These sub-trajectories are used to feed the PCA process. Thus we get a final local motion descriptor Θd = [d θ1 θ2 θ3 ] T . Compared to the global PCA-HOG descriptor proposed by[START_REF] Lu | Simultaneous tracking and action recognition using the pca-hog descriptor[END_REF] (one global HOG descriptor for each gesture/action), the proposed gesture/action descriptor consists in a set of local motion descriptors which accounts more faithfully for local motion. Instead of computing a global HOG volume from a person already tracked, we use local HOGs tracked independently. Our method contrasts from traditional local motion methods by using the tracking process of 2D descriptors instead of 2D descriptor time-volume.

	4 Gesture Learning
	4.1 K-means Clustering

For learning gestures, we assume that the training data-set is built with videos, each of them containing one and only one gesture instance. For each training video sequence, LMSs are extracted and annotated with the corresponding gesture label. Then, we apply the k-means algorithm in order to group these LMSs into clusters called videowords which are the local motion patterns. The similarity measure used for comparing two different LMSs in k-means is the Euclidean distance. Indeed we have carried out different experiments with different distances and found out that the euclidean distance gives the best results.

  Algorithm 4 k-nearest neighbors -on-line version Require: T {The training data-set} lms i , i >= 1 {The generated local motion signatures from the test sequence} Ensure: g recognized , recognitionLikelihood(g recognized )

	1: M ← 1
	2: duration ← 0
	3: previousLikelihood ← 0
	4: repeat
	5:	duration ← duration + 1
	6:	save the previous likelihood if any in previousLikelihood
	7:	while a lms i is generated do
	8:	execute the usual k-nearest neighbors for lms i
	9:	g M recognized ← arg max g∈G Likelihood M (g)
	10:

Table 1 :

 1 Results of HOG tracking module with the validation data-set of the KTH database.

		Mean	Var	Min	Max
	#Desc./frame	22.32 03.37 15.15 34.38
	#Tracked/frame 20.70 03.57 15.00 27.88
	#Lost/frame	01.62 01.50 00.15 06.50

Table 2 :

 2 Results of HOG tracking module with the IXMAS database. Similarly to the ones for KTH, the results on IXMAS video database are over-viewed in table 2. The better performance of our algorithm on IXMAS database can be explained by the fact that the video resolution (390x291) is better than in KTH database (160x120). Additionally, the actors in IXMAS database are always near the camera and noise is almost nonexistent.

		Mean	Var	Min	Max
	#Desc./frame	57.00 02.25 48.00 60.00
	#Tracked/frame 56.75 01.97 51.57 59.75
	#Lost/frame	00.12 00.03 00.09 00.17
	sents the correspondent output of our tracker with short term (five frames) and long
	term motion being displayed.

Table 4 :

 4 Comparison of different results of the KTH database.

	Method	Variant	Precision
	Our method	Shi-Tomasi	91.33%
		FAST	94.67%
	Liu and Shah [8]	SVM VWCs	91.31%
		VWC Correl.	94.16%
	Luo et al. [16]		85.10%
	Kim et al. [29]		95.33%

Table 5 :

 5 Precision, recall and F-score of the proposed method on KTH database. In addition, we choose to carry out this experiment with the FAST corner detector only since it gives better results on KTH database. The confusion matrix for this experiment is given in table 6 and table 8 presents the performance metrics. We compare the results of our method to those of[START_REF] Weinland | Action recognition from arbitrary views using 3d examplars[END_REF] in table7. Note that the results with the compacted learned database (i.e. using the MMI algorithm) are slightly better (7%) than the ones with the non-compacted version. Unsurprisingly gestures with large motion (e.g. sit down, get up, turn around, walk) are much better recognized than gestures with small motion (e.g. scratch head, wave, point) which besides, share some common motion patterns. The mean processing time of the offline k-NN classifier for the IXMAS database is 35 seconds per gesture which is quite reasonable knowing that a gesture is in mean depicted by 80 frames.

		Precision Recall	F-score
	with Shi-Tomasi	91.33%	99.07% 95.04%
	with FAST	94.67%	99.78% 97.15%

clustering algorithm. As said in section 4, the three phases of a gesture (i.e. pre-stroke, stroke and post-stroke) can generate different 2D motion patterns from different points of view. So for each action, we can expect 3 × 5 = 15 motion patterns. Due to the fact that the IXMAS database contains 13 gestures, the expectation grows to 13 × 15 = 195 motion patterns. For the learning phase, we use two learning procedures: (1) without MMI and (2) with MMI. For the classification phase, we use the same value of the k parameter (i.e. 5) as for KTH database. The classification is carried out independently for each gesture video corresponding to the remaining actor (i.e. discarded by the leaveone-out rule). So, for each actor (1 out of 12), each gesture (1 out of 13) and at a particular step of the cross-validation, there are 5 × 3 = 15 video sequences (5 views and 3 manners) to be classified versus 11 × 5 × 3 = 165 video sequences used for learning.

Table 8 :

 8 Precision, recall and F-score of the proposed method on IXMAS database.

			Precision Recall	F-score
	without MMI	83.23%	87.46% 85.29%
	with MMI		90.57%	85.72% 88.07%
	Table 9: Multi-view results for IXMAS database: precision of the classification of each
	view.
	Method		cam1	cam2	cam3	cam4
	Our method	75.34% 67.11% 69.52% 74.95%
	Liu & Shah [8] 72.29% 61.22% 64.27% 70.59%

Acknowledgment

The authors would like to thank ST Microelectronics Rousset which supported this work under PS26/27 Smart Environment project financed by Conseil Régional Provence-Alpes-Côte d'Azur.

 3) a testing data-set for evaluation (9 actors). All videos from this database were taken over homogeneous background thanks to a static camera with 25fps frame rate. The spatial resolution of each video is 160x120 pixels. We train our algorithm on the KTH training data-set and test it on the corresponding test data-set. All the parameters of the framework have been tuned using the validation data-set. Since a gesture is composed of three motion patterns (c.f . section 4), we have tested all the values of k between 18 and 57 for the k-means clustering algorithm. We realized that the best classification results is when k = 27. Finally, the best value of the k parameter of the k-nearest neighbor algorithm is k = 5. Results are illustrated by the confusion matrix 3 and are compared to the state of the art methods in table 4. We obtain better or slightly better results than recent methods. We also find out that FAST corners outperform Shi-Tomasi corners which is consistent with results in [START_REF] Rosten | Machine learning for high-speed corner detection[END_REF]. Note that even if [START_REF] Kim | Tensor canonical correlation analysis for action classification[END_REF] obtain slightly better results, their results are not comparable to ours since they use a different experimental protocol (Leave-one-out cross-validation) which includes more learning videos and enables to train better code-words. Table 5 shows the performance metrics (i.e. precision, recall and F-score) of the proposed framework. It has a high sensitivity which means that there is few false negatives. However, the precision can be improved.

Gesture Recognition on IXMAS Database

The IXMAS database [START_REF] Weinland | Action recognition from arbitrary views using 3d examplars[END_REF] experiment for all possible combinations. Only the version with MMI algorithm has been tested. Table 9 overviews the average precision for each experiment. We can notice an improvement w.r.t. [START_REF] Liu | Learning human actions via information maximization[END_REF]. we can see that the first and the last view points are more dependent on other view points hence they achieve better precision.


Juliusz Chroboczek

Sylvain Lebresne

Juppix: a Linux Live-CD for Undergraduate Students

Juppix is a Linux Live-CD with a comfortable programming environment for the Java, C and O'Caml programming languages that has been distributed to hundreds of undergaduate students at the University of Paris 7 over the last few years. We describe the lessons we learnt while compiling and distributing Juppix, and outline our future plans.

Background and motivation

Undegraduate teaching of programming at the University of Paris 7 is mostly based on Unix. During the first year, we use the Java programming language with some locally-developed packages [START_REF] Yunés | La classe Deug[END_REF] and the Emacs editor, in the second year, we add C and PHP, and third year students get to enjoy O'Caml.

While on campus, our students do have access to a few dozen reasonably configured machines running a system consisting of FreeBSD Unix and the KDE desktop. In periods of high affluence, such as just before a project deadline, our computer rooms tend to be overcrowded. Even in normal times, many students prefer to work from the comfort of their homes or to sit with their laptop in a nearby café.

It used to be the case that well-meaning lecturers and tutors helped students set up a Linux distribution on their personal machine. Unfortunately, destroying a student's MP3 collection by mistake is not a good way of staying popular, and visiting a student's home (especially a female student's home), even with the laudable goal of helping with a Linux installation, makes some of us uncomfortable.

Perhaps more importantly, many first year students are overwhelmed with the change in habits that we require from them: after years of clicking on the pretty icons of a Microsoft Windows environment, they are suddenly required to use a fairly sober KDE desktop, the command line and Emacs. The slight differences between the carefully tuned configuration that they access at the university and the default configuration of a general-purpose Linux distribution are often enough to confuse them.

Live-CDs A Live-CD is a bootable CD that provides a full operating system environment that can be run from the CD with no need to install any software on a computer's hard disk. While Linux Live-CDs have been around for as long as anyone can remember, with some very early Linux distributions using a Live-CD format [START_REF] Richter | ANNOUNCE: Alpha release of turnkey Linux/GNU/X system on CDROM[END_REF], they have only become popular in recent years, probably because of CD-ROM drives becoming fast enough.

In recent years, the Live-CD concept has become increasingly popular, and there is a vast array of available Live-CD implementations of general-purpose operating systems, but also of appliance software such as routers, firewalls and kiosks to be deployed in public places. The concept has become popular enough for at least one major Linux distribution to risk using a Live-CD as their primary installation media [6].

Our department had had some extensive experience with Live-CDs in the late nineties and early naughts [START_REF] Vincent Balat | The DemoLinux manual[END_REF]. It was natural for us to think of distributing software to our students in this format.

The early days

In the autumn of 2004, the second author started experimenting with using a Knoppix Linux LiveCD [START_REF] Knopper | [END_REF] and manually replacing some little-used pieces of software (such as the KDE games and network security tools) with a full set of packages for Java programming. He distributed a few copies of these to members of his tutorial groups, encouraging them to try this at home.

When his CDs turned out to be fairly successful with his students, the first author convinced him to turn his one-day hack into a more ambitious project. Within a few weeks, we had compiled a list of Free software packages used for teaching in our first, second and third year courses, and started writing a set of scripts that would build a "Juppix" Live-CD image with no human interaction.

Writing the scripts turned out to be a pointlessly exciting exercice. At the time, Debian GNU/Linux, the Linux distribution on which Knoppix, and hence Juppix, is based, was not quite ready for unattended installation. Some packages refused to install or uninstall without human interaction, and others had configuration defaults that would lead to a broken installation. Hence, our scripts needed to go around patching the Knoppix filesystem before starting to uninstall and then install software.

Reconfiguring software Another issue was that of the default configuration. Since the home directory of a LiveCD's user is typically not persistent, we wanted to provide our students with a comfortable default configuration, one that, as noted above is as similar as possible to the configuration of the machines in the university's computer rooms. In particular, we wanted a clean KDE desktop without annoying popup windows 1 , and we wanted the default shortcuts to follow the well-established pattern of the university configuration (a terminal, an Emacs editor, a keyboard layout switcher, etc.). We also wanted the shipped web browsers to include set of bookmarks that were likely to be useful, such as pointers to timetables, lecture notes, exam schedules, and, of course, to xkcd.

Older software turned out to be easy to reconfigure. For example, reconfiguring Emacs was a simple matter of adding a ".emacs" file to the default user's home directory ; reconfiguring the shell was done by appending some code to the default ".bashrc".

The KDE desktop, however, had clearly not been designed to be reconfigured from a script. KDE distributes its configuration files in a complex hierarchy rooted at a directory ".kde" in the user's home directory, and finding the exact location of Konqueror's bookmarks or of Kicker's icons and working out these files' syntax turned out to be a tedious and error-prone task. Our scripts remain brittle with respect to KDE version changes.

The FireFox web browser turned out to be an interesting case. A FireFox user's configuration is stored in a directory the name of which is randomly chosen on a per-user basis; the authors have no idea why this is done, and suspect that the Fire-Fox developers like to be gratuitiously annoying. However, once the name du jour of the configuration directory has been identified, configuring FireFox is a simple matter of modifying two relatively well documented files ("bookmarks.html" and "prefs.js").

Legal issues

In the small-scale experiments performed in 2004, we had ignored some licensing issues, notably with the distribution of the Java "Development Kit" (JDK). Since the 2005 version was to be more widely distributed, we decided we could not afford an uncertain legal situation.

We considered a number of alternate implementations of Java that didn't have distribution issues. Unfortunately, all of the implementations that we experimented with at the time exhibited differences with Sun's implementation that, while minor, were significant enough to confuse beginners.

Sun's legal department were friendly and sympathetic, and encouraged us to include their Java implementation. Unfortunately, they appeared to be unwilling to state anything clearly. It took the first author two weeks of consistent harrassment over e-mail across 9 timezones before he managed to trick a very nice lady into producing a statement that was clear enough for our Head of Department.

We also had to give up on some software for legal reasons. At the time, our thirdyear course in Logic Programming used a well-known Prolog implementation from a Portuguese university. After investigating its licensing, it turned out that it contained an advertising clause, which we find obnoxious, and that some of the bundled libraries had a distinct license that did not allow redistribution at all. A painful week of e-mail exchanges did not allow us to converge to a satisfactory solutionthe authors did not appear to care what we did with their software, but they were not willing to make any changes to their licensing. All versions of Juppix to date have shipped without a Prolog implementation.

Juppix 2005 By the end of October 2005 (two weeks after the start of the semester), we had a set of scripts that generated a CD image that we did not fear would not undermine our professional façade. We burnt 40 CDs by hand, and distributed them to our first-year students, 2 per tutorial group, asking them to share and copy the CDs among themselves.

Fixing mistakes

In the process of preparing and distributing the 2005 version of Juppix, we had made a number of fairly serious mistakes, which we felt we needed to fix for 2006.

Systematic distribution While most of our students have a fair amount of experience with copying CDs, asking them to organise distribution of Juppix turned out to be a mistake. In many cases, a tutor managed to make sure that all of hist students got a copy; in some groups, however, the original CDs ended up stuck at somebody's home after just a few copies had been made.

Additionally, the fact that our distributon was selective created a feeling of injustice among the students who weren't able to get a copy. There was even a formal complaint to our Head of Department, which he dutifully dumped on our desks before ignoring it.

At the encouragement of our Head of Department, we decided that if we were to distribute CDs to our students, we would distribute them to everyone, and order at least as many professionally-pressed CDs as we had first-year students.

Test suite During the development of the 2005 version of Juppix, we lost a lot of time dealing with silly mistakes. We would encounter an issue with e.g. the Caml mode not being configured properly in Emacs, which we would promptly fix, only in order to discover that, although they had been working perfectly the week before, the locally-installed Java classes were now broken.

We therefore proposed a fifth year project that consisted in developing a test suite for Juppix. The project was taken up by Glenn Rolland, who wrote a comprehensive set of shell scripts that tested the "serious" aspects of Juppix, notably the Emacs setup, the C and Java compilers and libraries, and the Apache/PHP installation. The test suite can be run on a Juppix instance connected to the Internet by simply downloading the scripts and running a shell script. Being able to comprehensively test what we feel is the core of Juppix whenever we build a new image has significantly reduced our chances of developing a stomach ulcer.

Working with Rolland turned out to be even more helpful than expected. As the first outsider who had ever had to run our scripts, Rolland did a fair amount of work to clean them up and make them easier to use. He automated the creation of bookmark files, so that we now could generate bookmarks for Konqueror and FireFox from a single source. His project report [START_REF] Rolland | Rapport de projet long. Master 2 d'[END_REF] remains the best description of the 2006 version of Juppix.

Results

In October 2006, we designed cover art for Juppix and ordered a batch of 2000 professionally-pressed Juppix CDs; this cost our department roughly e2500. A few weeks later, we received five boxes of 400 CDs each. We set-up an e-mail alias for support (populated with a few Ph.D. students with good Linux experience), and gave out 40 CDs to every tutorial group.

Numbers Over two years later, three generations of first-year students have received Juppix CDs, and the 2000 units are mostly gone. Over the last three academic years, we estimate that roughly 1000 copies have been distributed to our first year students, an extra 500 copies went to students in higher years and in other departments (notably Bio-Informatics), and some 150 copies were distributed in other universities. Additionally, some 300 copies have been given out at various public events, notably the "Fête de la Science," an annual exposition open to the general public (and their children).

We are aware of at least two instances of other universities burning their own runs of unmodified Juppix CDs. On the other hand, we are not aware of anyone modifying our scripts to produce Juppix-like CDs.

Students Students tend to consider the use of Juppix as being a compulsory part of their education, and they are very surprised when they learn that we don't object to their using a stock Linux distribution instead. While we have not performed any large-scale surveys, our tutors' estimates and the amount of traffic on the support alias indicate that usage rates are low at the beginning of the semester (in the 10 % range), and increase dramatically in the last week before the November exams. After they become more proficient with Linux, most students end up installing a stock Linux distribution, typically in their second or third year.

An unexpected but pleasant side effect is that the authors have earned the reputation of being Linux gurus, and hence have acquired the moral right to be Free Software fanatics. In past years, the first author would receive complaints that his Operating Systems lecture was too strongly centered around Unix, and didn't contain enough "useful" information, i.e. information that is directly applicable to Microsoft Windows. He is pleased to report that his students are now surprised when they discover that his lecture does mention Windows after all, and that he is not the Unix monoculturalist that they expected him to be.

Teaching staff Our teaching colleagues received Juppix in an overwhelmingly positive manner. A number of lecturers now systematically recommend Juppix at the beginning of their lectures, and we regularly receive requests for small batches of Juppix from tutors whom we don't personally know.

Some of our colleagues are Unix veterans, and consider Free Unices with a mixture of sarcasm and bitterness ("You youngsters are just repeating what we did in the eighties, without giving proper credit"). They were clearly impressed with our ability to compile a CD of useful software in a few months of our copious free time, and distribute it legally to hundreds of students at a reasonable cost. The authors are pleased to report that they are now allowed to speak to the Unix veterans without first being spoken to 2 .

Technical staff

We were uncertain of the reactions of the system administrators, who, we feared, might consider that we were encroaching on their territory. Just like the teaching staff, however, they soon realised that Juppix would reduce their support load, and were quick to recommend it to their users. The only complaints we have received from system administrators were about Juppix not being sufficiently up-to-date.

Current work: Juppix 2009

Over the last years, the 2006 version of Juppix has become increasingly out of date. While the software it contains is still useful, it fails to boot on an increasing number of recent machines, which is a serious issue as first year students tend to have very new hardware. Additionally, a number of hardware and software changes have occurred in the intervening years, which makes it possible to build a better Juppix now than it was in 2006.

New storage media

The price of DVD duplication has dropped significantly, to the extent that it becomes reasonable to consider distributing a live-DVD rather than a live-CD. While we have no intention of significantly expanding the functionality of Juppix, the increase in capacity (4.7 GB instead of 750 MB) will simplify our work, as we will no longer have to compromise between the conflicting goals of providing a complete programming environment and keeping the image size below 750 MB.

Additionally, most of our students own flash keys of 1 GB or more, rather than the 128 MB that were typical in 2006. It becomes useful to offer a version of Juppix that can be booted off a flash key, thus avoiding the slow speed of optical media.

Other changes Since Wifi access points are more common now than they were in 2006, we hope to provide good support for common wireless hardware. This will probably require shipping with a Linux kernel different from Debian's default.

The licensing conditions of Sun's Java implementation have changed. The stock 1.6 JDK is still proprietary software, but can be redistributed under fairly reasonable conditions, and there exists a version called OpenJDK that is Free Software. We are currently evaluating the use of OpenJDK, with the option of switching back to the JDK if it proves unsuitable.

Live-Helper Since we compiled Juppix 2006, Live-CD technology has improved significantly. Of particular note is the inclusion in the Debian GNU/Linux distribution of the live-helper and live-initramfs packages, which allow the reasonably automated creation of a live-CD, a live-DVD or a live-USB key.

We are currently working on a version of Juppix based on the live-helper scripts and on Debian's lenny distribution. The new version will still be built by a custom set of scripts, but these scripts will be driving the live-helper scripts rather than modifying an existing image. We expect to physically distribute a Live-DVD version to our students; for people wishing to download an image, we will offer at least two versions:

• an iso-large version, suitable for burning on DVD media, and including full documentation, graphical development environment, a complete TeX system and a word processor;

• an iso-small version, suitable for burning on CD media, including reasonable documentation, Emacs, and a minimal TeX system.

At the time of writing, it is not clear to us whether we will need to ship separate images for flash keys, or whether we will be able to install on a flash key from a live system booted from DVD.

Conclusions

Four years' experience with Juppix has taught us some important lessons.

• If your underground project is cool, tell your boss about it. If you think it's cool, he'll likely think so too.

• If you distribute something to your students, either distribute it to all of them, or don't do it at all. Students are quick to perceive differences in treatment as injustice.

• Don't lose time arguing with people who think that advertising clauses are a good idea, or who forbid redistribution. Dropping their software is easier on the nerves.

• Students are cheap, but the private sector is cheaper. Don't burn your own CDs, get them professionally pressed.

• Don't be afraid of the old Unix crowd.

• Don't be afraid of your system administrator.

Software availability

Ready-to-burn Juppix image files, the scripts used to build Juppix, and the test suite are available from http://www.pps.jussieu.fr/~jch/software/juppix.

Nonetheless, the authors bear no grudge towards the author of the infamous KTip applet.

We have been avoiding the painful subjects, notably software patents.