William Mocaër
email: william.mocaer@irisa.fr

Eric Anquetil
email: eric.anquetil@irisa.fr

Richard Kulpa
email: richard.kulpa@irisa.fr

Early Recognition of Untrimmed Handwritten Gestures with Spatio-Temporal 3D CNN

Early recognition of untrimmed handwritten gestures is the task of recognizing as soon as possible gestures drawn in a continuous stream, one after another. This is particularly challenging for multi-touch gestures because it is impossible to know when the gesture has started and finished. For mono-stroke gestures, in an application context where the finger is never removed from the device between gestures, the recognition is even more complex. In this work we present an extension of the Online Long-Term Convolutional 3D (OLT-C3D) network to address the task of early recognition of untrimmed gestures which have been addressed by very few works. To evaluate our approach, we created two synthetic datasets using freely available benchmarks, MTGSetB and ILGDB, simulating the streaming data in two different application scenarios. Furthermore, we propose a new evaluation metric for this specific task. Our approach achieves good performances on the two new datasets and will be a baseline for future works on this challenging task.

I. INTRODUCTION

From the user-interaction point of view, reactive and natural interactions with tactile devices are essential for a successful experience. Gesture interaction allows the user to manipulate naturally the device, but they are often limited to very basic functionalities like zooming, rotating and scrolling. The difficulty of adding new gestures is two folds: recognition accuracy and system reactivity. Increasing the number of gestures increases the probability of having gestures with common beginning. As a consequence, the system cannot predict the gesture from first traces without potentially executing undesirable commands. Waiting until the end of gesture is not an option considering we want a real-time reaction of the device. To apply a zoomming effect when a user make the zooming gesture, we need to detect the gesture from the first instant to produce a direct feedback. To be able to handle such direct manipulations, we need a system capable to recognize very early user gestures, just after that the common part between gestures is passed. Nowadays, it only works for very few well-designed gestures with hand-crafted basic approach that can not be generalized.

Another difficulty in user interaction with gesture is application contexts when gestures are made one after another, then the gestures starting and finishing bounds are not always clear (see figure 1) and can scramble the recognition. This is particularly true with mono-stroke gestures when the finger is never removed from the device between gestures, similarly to a handwritten word but the gestures are completely mixed up spatially. This is also challenging with multi-touch/multistroke gestures due to the intra-gesture breaks (when all fingers are removed from the device) between two strokes that cannot be distinguished from an inter-gesture break, so we are not able to tell where the beginning of the gesture is.

The task of early recognition of untrimmed handwritten gesture is to recognize the gestures being drawn continuously as soon as possible and before the gesture is fully finished. Few works address this challenging problem, most of them addressed the early recognition of action made by a full human body, either from RGB videos [START_REF] Molchanov | Online detection and classification of dynamic hand gestures with recurrent 3d convolutional neural network[END_REF] or 3D skeleton videos [START_REF] Weber | Lstmbased early recognition of motion patterns[END_REF]- [START_REF] Boulahia | Détection précoce d'actions squelettiques 3D dans un flot non segmenté à base de modèles curvilignes[END_REF]. Regarding 2D gesture recognition, some work addressed the early recognition of trimmed gestures [START_REF] Uchida | Early recognition of sequential patterns by classifier combination[END_REF]- [START_REF] Mocaër | Online spatio-temporal 3d convolutional neural network for early recognition of handwritten gestures[END_REF], but not in untrimmed context.

To address this problem, we present an approach based on a spatio-temporal 3D CNN called OLT-C3D [START_REF] Mocaër | Online spatio-temporal 3d convolutional neural network for early recognition of handwritten gestures[END_REF] designed for trimmed gesture recognition. OLT-C3D, coupled with a temporal reject system, is able to postpone a detection to avoid misclassified detection, but it can be unstable because the consistence between frames is not explicitly trained, making it unreliable in untrimmed context. We extend it to address the untrimmed context by regularizing the network with the CTC (Connectionist Temporal Classification) loss [START_REF] Graves | Connectionist temporal classification: Labelling unsegmented sequence data with recurrent neural networks[END_REF] which improves the system stability and robustness. To handle this task we defined a new evaluation protocol. We created two artificial datasets to simulate gestures stream, and we propose a new evaluation metric.

The contributions of this paper are summarized as follows:

stability over time we propose to regularize the network with the CTC loss. • We propose two speed-independent gesture representation strategies for multi-touch and mono-stroke gestures. • We built two new challenging datasets of gesture sequences generated to evaluate our system on applicative scenarios and we propose a new metric to specifically evaluate early recognition of untrimmed gestures.

II. RELATED WORKS

Some works addressed the task of early recognition of 2D gestures. Uchida et al. [START_REF] Uchida | Early recognition of sequential patterns by classifier combination[END_REF] built a system based on multiple frame classifiers, one weak classifier is built per frame. At each current frame, the system combines results from previous and current frame classifiers to determine the current classification. Another classifier combination approach is also used in the work of Chen et al. [START_REF] Chen | Early recognition of handwritten gestures based on multi-classifier reject option[END_REF], they designed length-dependent classifiers and a reject system based on the confidence scores and repetition of prediction. Yamagata et al. [START_REF] Yamagata | Handwriting prediction considering inter-class bifurcation structures[END_REF] designed an approach explicitly modeling the trajectory bifurcations between handwritten digits, an LSTM network is used to predict class and the future trajectory. Recently, a new approach based on a 3D Convolutional Neural Network (CNN) called OLT-C3D (for Online Long-Term Convolutional 3D) [START_REF] Mocaër | Online spatio-temporal 3d convolutional neural network for early recognition of handwritten gestures[END_REF] has been designed to handle long-term visibility without the need of any recurrence layer thanks to temporal dilated convolutions. This approach has a reject system to avoid classification errors in early stages. All these approaches were made for a trimmed context with one gesture at a time, and do not consider the untrimmed context.

Early 3D gesture recognition from a full 3D human body has more been considered in previous works. Regarding trimmed early recognition of 3D gestures, early works used template-based methods to try matching partial gesture sequence [START_REF] Mori | Early recognition and prediction of gestures[END_REF], [START_REF] Kawashima | Adaptive template method for early recognition of gestures[END_REF]. More recently, Wang et al. [START_REF] Wang | Progressive teacher-student learning for early action prediction[END_REF] designed a model trained with teacher-student scheme, two networks are trained to have a close internal representation. The first network (teacher) is able to see the whole sequence while the second network (student) can only see an early part of the sequence. Wang et al. [START_REF] Wang | Dear-net: Learning diversities for skeleton-based early action recognition[END_REF] built a network able to predict multiple plausible actions, this is particularly useful in the early stages when the action cannot be clearly identifiable. Also, the model is trained with a weakly supervised strategy by predicting future postures, this helps the network to generalize well. Another way to handle early stages is to define a reject option strategy related to the confidence like some other approaches [START_REF] Chen | Early recognition of handwritten gestures based on multi-classifier reject option[END_REF], [START_REF] Mocaër | Online spatio-temporal 3d convolutional neural network for early recognition of handwritten gestures[END_REF], [START_REF] Boulahia | Cudi3d: Curvilinear displacement based approach for online 3d action detection[END_REF].

Regarding the untrimmed case, action prediction of 3D gestures in an untrimmed stream has been addressed by Escalante et al. [START_REF] Escalante | A naïve bayes baseline for early gesture recognition[END_REF] and Liu et al. [START_REF] Liu | Skeletonbased online action prediction using scale selection network[END_REF]. Their networks are able to predict the class based on partial observation, but no strategy to handle early stages are used. The architecture of Liu et al. is inspired by WaveNet [START_REF] Van Den Oord | Wavenet: A generative model for raw audio[END_REF], using a stack of causal and dilated 1D convolutional layers. SSNet is able to handle a stream in real time, giving a new response to each new frame.

Weber et al. [START_REF] Weber | Lstmbased early recognition of motion patterns[END_REF] addressed the early recognition problem with a recurrent network. An LSTM network is trained with an additional blank class to represent the inter-gesture frames. Molchanov et al. [START_REF] Molchanov | Online detection and classification of dynamic hand gestures with recurrent 3d convolutional neural network[END_REF] proposed a convolutional recurrent network (CRNN), the input stream was split into short clips before feature extraction by a CNN. Then, the features are fed into a RNN to extract long-term temporal information. A reject system based on the classifier score is used to handle early stages of gestures. Boulahia et al. [START_REF] Boulahia | Détection précoce d'actions squelettiques 3D dans un flot non segmenté à base de modèles curvilignes[END_REF] used a combination of SVMs trained with a set of hand-crafted features, a complex reject system based on confidence scores has been designed.

From these works, we can notice that the task of early recognition of 2D gesture has not been addressed in the context of untrimmed gestures stream. In the 3D gesture context, most of these methods are trained with a per frame strategy, which can lead to unstable predictions results between consecutive frames, making the method unusable in an application context. Moreover this instability is rarely taken into account in the final evaluation metric since it is often a frame-based metric. In our work, we propose a training strategy which explicitly considers time stability with a CTC (Connectionist Temporal Classification) regularization. Furthermore we present a new metric which hardly penalize unstable predictions over time.

III. METHOD

In an application context where a gesture is associated with one command, each misclassified detection will lead to an undesirable command execution. To avoid detecting something in the early stages where the gesture is not clearly identifiable we first need an efficient reject mechanism. Secondly, we need to ensure the stability of the predictions to be consistent between consecutive frames.

Our method extends the Online Long-Term Convolutional 3D (OLT-C3D) [START_REF] Mocaër | Online spatio-temporal 3d convolutional neural network for early recognition of handwritten gestures[END_REF] network to address the early recognition of untrimmed gestures task. First, the online signal of the trace of fingers on the device has to be translated into an image sequence. We designed two new strategies to model the gesture completion in time, inspired by previous ones. The representation is used as the input of the OLT-C3D network trained to handle an untrimmed stream of gestures. A reject option system is used to postpone the detection in early stages. To address the consistency of the detected gesture between frames, an additional output is added to be trained with the CTC loss.

A. Gesture Representation

To choose our gesture representation we need to consider the two different application scenarios which require early recognition in an untrimmed context. In the first scenario, we consider multi-touch gestures made the ones after the others. Between two strokes, all the fingers can be removed from the device, and this is also the case between two gestures. In the second scenario, the finger is never removed from the device, making only mono-stroke gestures, like when we are writing a word with letters.

Like the representation in [START_REF] Mocaër | Online spatio-temporal 3d convolutional neural network for early recognition of handwritten gestures[END_REF], we choose to represent the gesture being drawn on images to be usable with the OLT-C3D network, at each significant new information we create a new frame representing the gesture at this stage.

We get from the device the online signal, i.e., a list of points, with the timestamp and the positions of the fingers, and we need to convert it into a sequence of images. First, to obtain a speed-independent representation, we resample the gesture using quantity of displacement instead of using the time. Between each new image, the same quantity of displacement (that we called θ) has been drawn on the device, if multiple strokes are done at the same time (multi-touch gesture), then the displacement of all strokes are taken into account to compute the quantity of displacement. We can get the new set of points S from the set of points P not already drawn and ordered by time as following: S = p t ∈ P pt=1 ∥p t-1 -p t ∥ < θ . Note that this resampling strategy is applicable in the online case and if the fingers are not moving, then no processing is required and no new result is given.

Another difficulty is that we cannot guess in advance which size the gesture would be, the user can make the gesture at any scale, but our image has a finite spatial resolution. To address this difficulty, we predefined a scale by advance and if the gesture reaches the border of the image, then we shift the image to the opposite direction to let some space.

To represent the dynamic in the fixed image, we add a second channel on the image to notify the presence of a finger on the device. This second channel is very sparse and contains only ones in positions where the fingers are at, in each image. With this channel, the network can deduce in which direction the stroke is being drawn.

In the previous approach, the gesture was translated into an image sequence where each new image contains the new positions of the fingers with all its previous trajectories, making appear some patterns. In untrimmed context, this is not possible since we don't know when the gesture does start, and we cannot keep all the trajectory of all gestures because the trace will overlap with previous gestures trajectories. Instead, we need a representation strategy compatible with a gesture sequence. This strategy must depend on the context of the scenario described above. We can address differently the multitouch gestures representation strategy and the mono-stroke gestures one.

1) Multi-Touch Representation Strategy: For multi-touch gestures representation, the trajectory will be completely reset when all fingers have been removed from the device during a very short instant, this can be an inter-stroke moment, or an inter-gesture one. In this way, the trajectory of the gesture is accumulated until strokes done simultaneously are finished. We can add a black image when it happens to notify this event more explicitly to the network. Moreover it allows the network to predict something on this black frame while being sure that the stroke is finished, which is very important for detecting gestures which are subpart of other gestures. This strategy is not applicable to mono-stroke gestures if the finger is never removed from the device.

2) Mono-stroke representation strategy: For mono-stroke gestures, as there is no identifiable break points, the gesture trajectory is accumulated into an overlapping sliding window ψ. Each image will contain ψ × θ quantity of displacement. A big sliding window will lead to noisy images, with pieces of previous gestures, and a too short one will not make appear any pattern on the spatial dimensions. An example of the representation is shown in Figure 2.

B. OLT-C3D Architecture with Temporal Reject System and CTC Regularization

The OLT-C3D [START_REF] Mocaër | Online spatio-temporal 3d convolutional neural network for early recognition of handwritten gestures[END_REF] (Online Long-Term Convolutional 3D) network is composed of a stack of 3D convolution layers. The convolutions are causal: to compute the output of each frame, the future is completely disregarded. This ensures the usability for online applications. The convolutions are temporally dilated in order to increase the receptive field in the time dimension. With two blocks of 5 convolutional layers with increasing dilatation rate, the network can make a prediction while seeing up to 64 previous frames. 64 frames are enough to see at least one full gesture completion. See [START_REF] Mocaër | Online spatio-temporal 3d convolutional neural network for early recognition of handwritten gestures[END_REF] for more details about the network architecture.

We modify the network to have four outputs: the confidence score (1 output neuron, called g), the classification scores (f ), the combination of a blank and the class scores (out ctc ) and the auxiliary output (h). These outputs are represented in Figure 3. Three losses are used to train the network. 1) Temporal Reject System: The OLT-C3D network is trained with a per frame loss, originally inspired by the Selec-tiveNet loss [START_REF] Geifman | Selectivenet: A deep neural network with an integrated reject option[END_REF], incorporating a confidence output training.

This loss is computed as follows:

L (f,g) = 1 m m i=1 ℓ (f (x i ) , y i ) g (x i ) + λΨ c -φ (g) (1)
where Ψ(a) = max(0, a) 2 , λ is a hyperparameter relative to the importance of the coverage constraint (we set it to λ = 32 like the previous approach). c is the targeted coverage. φ (g) is the empirical coverage, i.e. the average value of g(x), and ℓ is the cross entropy loss.

During the inference, we will consider that the prediction frame is accepted if g is over a threshold γ, set to 0.5.

The auxiliary output h consists of class predictions like f , but is trained by a traditional per-frame cross-entropy loss L h .

The temporal reject loss and the auxiliary loss are per-frame losses, and no consideration is given to consistency between consecutive frames. We address this problem with the CTC regularization.

2) Regularization with the Connectionist Temporal Classification (CTC) Loss: The out ctc output of the network is trained with the CTC loss L ctc . Note that the class scores which is part of out ctc is shared with the temporal reject loss.

The CTC loss [START_REF] Graves | Connectionist temporal classification: Labelling unsegmented sequence data with recurrent neural networks[END_REF] is used to optimize the alignment between a sequence-level label (i.e., the classes happening during the sequence, without the start/end segmentation bounds) and a per-frame output. The per-frame output is processed in the CTC loss to remove consecutive identical prediction. A blank is also used as a reject to predict none of the available classes.

The use of CTC loss is not necessary for training the network since we have the temporal segmentation of the gestures, we could have trained our network only with the per-frame loss. But CTC brings temporal prediction stability to the network because it requires a good alignment between the sequence-level label and the predicted sequence, and this is very useful for our task. We can notice that the role of the blank in the CTC is relatively close to the one of the confidence score of the temporal reject system. The main advantage of the confidence score compared to the blank is that we can easily tweak it using different parameters (targeted coverage c, λ, confidence threshold γ).

For the final detection, we use the class prediction output f with the confidence score g. The CTC loss is just used to train the internal representation of the network and to smooth the class prediction along the time, we can see it as a regularization strategy.

3) Final optimized loss: The final optimized loss is computed as

L = αL (f,g) + (1 -α)L h + ωL ctc (2)
where we fixed α = 0.5 and ω = 0.01 to make the CTC loss magnitude close to the one of the other losses.

IV. EXPERIMENTS

A. Network details

The images generated by our representation are 40 by 40 pixels, with a quantity displacement θ equals to 4.4 for ILGDB and 1.5 for MTGSetB (once scaled by 0.2 for ILGDB and 0.03 for MTGSetB). The sliding window ψ for the representation of ILGDB is set to 2. Dropout is used in all convolutional and dense layers, with a rate of 0.1 for convolutional and 0.2 for dense layers. Each convolutional layer learns 30 filters. One dense layer of 100 units is used after the convolutional layers, all outputs shared this layer. One additional dense layer, with the same number of units, is used just before the final confidence output layer. During the training, random rotation (following normal distribution with µ = 0 and σ = 15 • ) is applied to sequence (the same rotation for all images in a sequence) to improve the generalization. Coverage c of the temporal reject loss is fixed to 0.7 for MTGSetB and 0.3 for ILGDB. The training is done with a batch size of 5 sequences.

B. Synthetic Datasets Generation

To evaluate our approach on the task we generated two datasets from ILGDB [START_REF] Renau-Ferrer | The ilgdb database of realistic pen-based gestural commands[END_REF] and MTGSetB [START_REF] Chen | Recognize multi-touch gestures by graph modeling and matching[END_REF]. ILGDB is a mono-stroke gesture dataset containing 21 gesture classes performed by 38 users. These 21 classes are divided into 7 groups of 3 classes, where these 3 classes shared a common begin, making nearly impossible early detection before the bifurcation of these 3 gestures. We generate sequences with between 4 and 8 randomly selected gestures per sequence. The sequence is generated in order that the last point of a gesture is the same point as the first point of the following gesture. Following the original train/test split, 119 sequences are used for training and 210 are used for testing. This dataset is particularly challenging because sequence does not have any breaks so it's very hard to determine the starting and the ending of gestures. Moreover it has few training examples. To tackle the few amounts of data, we generated an augmented dataset using size scaling (5 different scales) and using the same gesture into multiple sequences (each gesture put into 5 sequences). At the end, each training gesture is used 25 times in the sequences, leading to 2621 training sequences. An example of a generated sequence is given in figure 1.

MTGSetB is a multi-touch gesture dataset containing 31 different classes made by 33 users. We built sequences of 4-8 random gestures in order to being unable to differentiate an inter-stroke blank and an inter-gesture blank, each gesture is re-centered according to the previous gesture into the sequence, making impossible a spatial segmentation between gestures. According to the original user-separated train/test split, it leads to 607 gestures sequences for training, and 672 for testing. We also generated an augmented version of the dataset with size-scaling (3 different scales) and using each gesture into 2 sequences. This led to 3076 training sequences.

These two datasets are freely available1 .

C. Bounded Online Detection (BOD) Metric

We propose a new metric we called "Bounded Online Detection (BOD) Metric", inspired by computer vision detection metrics. The main idea of this metric is to allow only one detection per ground truth bound, conditioning the detection to a certain amount of overlap between the ground truth bound and the detection bound. Any noisy detection will be considered as a false positive. The algorithm allowing to compute the metric is the Algorithm 1.

Algorithm 1

The algorithm to compute the proposed metric. Note that to compute this metric we need the bounds of the predictions. If we have a per frame classification output, we will need a strategy to transform it into a bounded output. This strategy should be compatible with the online context i.e., we should not use future predictions to estimate a starting and ending bound. In our case, the first accepted frame is considered as the start of the gesture, and the next rejection or different class prediction is the end of this gesture.

We designed the IoU st which is a variant of the Intersection Over Union measure for online context. Because we don't want to penalize late prediction on this criterion, we compute the overlap from the prediction start bound:

IoU st = Intersection U nionst
where the U nion st is computed from the starting bound of the prediction. A high IoU st characterizes detection which well matches the ground truth bound from the prediction starting bound.

The metric has two parameters: "canCorrect" and ∆. can-Correct is a boolean, if it is true, it allows the model to correct itself if it has made a detection error on a given gesture. ∆ is a value between 0 and 1, and correspond to the minimum IoU st value allowed to consider the gesture as a true positive (TP). For application context which does not require to keep the prediction during the gesture (just a peak), ∆ can be set to 0. A value of 1 would mean that the prediction end bound should match exactly the ground truth end bound to be a TP.

Detection is considered as a TP if the ground truth with the maximum IoU st has not been already correctly detected (or falsely detected if canCorrect = F alse), if it is the correct class prediction, and if the IoU st is strictly over ∆. Otherwise it is considered as a false positive (FP). An example of the application of the metric is shown in figure 4. Once Precision and Recall are computed, we can compute the final global micro-averaged FMeasure using the traditional computation: F M easure = 2 * Recall * P recision P recision+Recall . We also compute the Normalized Distance To Detection (NDToD) used in previous works [START_REF] Chen | Early recognition of handwritten gestures based on multi-classifier reject option[END_REF], [START_REF] Mocaër | Online spatio-temporal 3d convolutional neural network for early recognition of handwritten gestures[END_REF], which measure the earliness of the detection. The NDToD metric is counted only for TP detections.

D. Results

1) Trimmed Early Recognition Results:

To compare our approach with previous works, we evaluated our approach in a trimmed context. In this context, only the first detection is used because an application would know that only one gesture is being drawn. The comparison with the MTGSetB dataset is shown in table I. Detections happen a little later than [START_REF] Mocaër | Online spatio-temporal 3d convolutional neural network for early recognition of handwritten gestures[END_REF] but it is well balanced with a significant improvement of the TAR (True Acceptance Rate) and the FAR (False Acceptance Rate) values. Also, almost no gesture is rejected (RR: Reject Rate). This shows particularly the good impact of the CTC regularization, even in trimmed context. The figure 5a shows the behaviour of the system according to the normalized gesture completion. 50 % of the gestures were detected before 27 % of their completion. Among them, 95.4 % were correctly classified. As shown in figure 5b, the earliness can vary drastically between gesture categories, from near 100 % for A 02 to less than 15 % for B 04. This depends on the length of the common begins between gestures. Regarding accuracy without earliness, taking the prediction at the last frame for each gesture, we obtain a score of 97.33 % versus 94.45 % for [START_REF] Mocaër | Online spatio-temporal 3d convolutional neural network for early recognition of handwritten gestures[END_REF].

2) Untrimmed Early Recognition Results: We evaluated our approach in the untrimmed context on the two datasets previously described with the BOD Metric. The results are shown in table II for MTGSetB and ILGDB. The method has been evaluated with different metric parameters combination. For MTGSetB we obtained a FMeasure from 83.6 % to 76.1 % depending on the ∆ value, without the possibility to correct the error, and from 88.2 % to 86.8 % if the model can correct itself. These results show that the network is able to predict well until the end of the gesture for this dataset. For ILGDB, the results vary much more depending on ∆, this means that the network is not able to identify correctly when the gesture finishes, this is consistent with the difficulty of this dataset because the gestures are totally chained, and the transitions between gestures are not easily identifiable. 3) Impact of CTC Regularization: To show the importance of the CTC regularization we evaluated the system with and without this regularization, the results are shown in table III. On both datasets, the CTC regularization has a significative impact on the results, especially on ILGDB. Because of the CTC loss which encourages the predictions to be consistent between frames, the precision and the earliness is particularly impacted: +1.6 % of precision for MTGSetB and +8.8 % for ILGDB. However, it has a negative impact on the earliness, +0.4 % and +2.7 %, the gestures are detected slightly later. We can deduce that the network preferred to postpone more its detection to avoid detection instability, which is consistent with an application scenario.

A example of detection of the network trained with and without the CTC regularization is shown in figure 6. We can see on the last gesture that the detection switch between three gestures, this is the kind of behaviour which is hardly penalized by the CTC loss. Final detections without CTC Fig. 6. Example of detections on MTGSetB with the network trained with CTC (second line) and without CTC (third line). We see that the last gesture is detected differently with the two versions, the final detection is more unstable without CTC.

4) Qualitative Results: Figure 7 (top) shows an example of a sequence of MTGSetB with the predictions and detections of the network. For the first gesture, we see that the network rejects predictions (i.e., confidence below 0.5) until the beginning of the second stroke of the "X" gesture to be sure not to confuse with the "W" gesture which is also contained in the dataset. For the next two gestures, it also waits until the common parts with other gestures are passed. We observe a similar behaviour on ILGDB (figure 7, bottom), but due to the difficulty of this dataset, it has difficulties to keep a consistent confidence score, which can produce false positive and missed detection.

V. CONCLUSION

We presented an approach to address the challenging task of early recognition of untrimmed gestures. First, new representation strategies are designed to consider sequences of multistroke or mono-stroke gestures. We proposed to regularize the spatio-temporal CNN using the CTC loss to bring predictions stability. Moreover, we propose a new evaluation protocol with a new metric, and two artificial datasets. Our method obtained superior results when compared with other approaches in trimmed context. Good results are obtained in untrimmed context, which will be a strong baseline for future works.

Applying the CTC loss can be an open door to weaklysupervised training, using only the sequence-level annotation, this will be explored in future works. We will also address the task of early action recognition of a full 3D human body.

Fig. 1 .

 1 Fig. 1. Example of an untrimmed sequence generated from ILGDB. Each color represents different gestures. In untrimmed context the gestures are chained in the same space. (a): along the three dimensions, x, y and the time. (b): only spatial dimensions.

Fig. 2 .

 2 Fig. 2. Example of the representation of a sequence of three gestures. A sliding window ψ of two displacement units is used in this example: each image contains a new piece of information with the previous one.

  blank

Fig. 3 .

 3 Fig. 3. The network is composed of four outputs. The class prediction output is shared with the CTC output to train a common internal representation.

Inputs:

  Predictions bounds, Labels bounds ; Parameters : canCorrect, ∆. Sort Predictions and Labels by starting bound. for all pred in Predictions do GT * ← argmax GT ∈Labels IoUst(pred, GT ) if flag(GT * ) = 0 and class(GT * ) = class(pred) and IoUst(pred, GT * ) > ∆ then Add a True Positive ; flag(GT * ) ← 1 earliness ← start(pred)-start(GT * )+1 end(GT * )-start(GT * )+1 else Add a False Positive if not canCorrect then flag(GT * ) ← 1 end if end if end for Precision ← T P T P +F P ; Recall ← T P length(Labels) NDToD ← average(earliness)

Fig. 4 .

 4 Fig. 4. Example of an application of the Bounded Online Detection (BOD) Metric with ∆=50 %.

Fig. 5 .

 5 Fig. 5. Performance of the system on MTGSetB (trimmed evaluation).

Fig. 7 .

 7 Fig. 7. Example of detections on MTGSetB (top) and ILGDB (bottom). a. Ground truth, b. Class predictions, c. Confidence, d. Final detections. The network waits until decisive instants to get a high confidence. Note that some intermediate frames have been removed for the visibility.

TABLE I COMPARISON

 I WITH PREVIOUS APPROACHES ON MTGSETB FOR A CLOSE EARLINESS VALUE (NDTOD), TRIMMED EVALUATION.

	Method	TAR	FAR	RR	NDtoD
	Chen et al. [6]	81.89 %	14.56 %	3.54 %	37.04 %
	OLT-C3D [7]	89.25 %	7.24 %	3.51 %	30.77 %
	This work	93.5 %	6.44 %	0.1 %	33.1 %

TABLE II UNTRIMMED

 II EVALUATION ON MTGSETB AND ILGDB (UNTRIMMED VERSIONS) WITH DIFFERENT PARAMETERS OF THE BOD METRIC.

			MTGSetB	ILGDB
	canCorrect	∆	FMeasure	NDToD	FMeasure	NDToD
		0.0	83.6 %	32.7 %	61.1 %	68.7 %
	False	0.5	77.1 %	32.5 %	45.1 %	68.2 %
		0.95	76.1 %	32.4 %	24.3 %	71.9 %
		0.0	88.2 %	34.0 %	68.0 %	69.3 %
	True	0.5	87.7 %	35.8 %	54.3 %	70.4 %
		0.95	86.8 %	36.1 %	30.9 %	75.4 %

TABLE III IMPACT

 III OF THE CTC REGULARIZATION, UNTRIMMED CONTEXT, BOD METRIC WITH canCorrect = F alse, ∆ = 0.25

						Ground truth
						Final detections
						with CTC
	Dataset	Variant	Precision	Recall	FMeasure	NDtoD
	MTGSetB	CTC No CTC	70.7 % 69.1 %	87.0 % 85.2 %	78.0 % 76.3 %	32.7 % 32.3 %
	ILGDB	CTC No CTC	56.4 % 47.6 %	55.6 % 54.2 %	56.0 % 50.7 %	69.2 % 66.5 %

• We designed a method for the task of early recognition of untrimmed gestures using a spatio-temporal 3D CNN with a temporal reject system. To improve its prediction

Datasets available at: https://www-intuidoc.irisa.fr/en/mtgsetb-and-ilgdb-untrimmed/

ACKNOWLEDGMENT

This study is funded by the ANR within the framework of the PIA EUR DIGISPORT project (ANR-18-EURE-0022).


Christian Rey
email: rey@eurecom.fr

Karine Amis Cavalec

Jean-Luc Dugelay

Ramesh Pyndiah
email: ramesh.pyndiah@enst-bretagne.fr

Annie Picart
email: annie.picart@enst-bretagne.fr

Karine Amis
email: karine.amis@enst-bretagne.fr

Enhanced robustness in image watermarking using block turbo codes

Keywords: Image, Watermarking, Error Correcting Codes, Product Codes, Turbo Codes, Robustness

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

The explosion of digital multimedia documents circulating worldwide through communication networks (e.g. WWW or WLAN) or commercial networks (e.g. CD or DVD) has created a strong demand for efficient watermarking techniques in order to protect these documents. Watermarking 1 includes a complex trade-off between three parameters: distortion, payload and robustness. Different watermarking solutions have already been proposed in the literature. One major challenge is to design a technology that offers an efficient robustness while keeping a fair distortion and payload. The range of possible attacks on images is very large. One possibility to overcome this problem could consist in specifying algorithms relatively to a given category of attacks (e.g. JPEG [START_REF] Koch | Towards robust and hidden image copyright labeling[END_REF] or shifting and scaling [START_REF] Tsekeridou | Copyright protection of Still Images using Self-similar Chaotic Watermarks[END_REF] ) or to a specific service (e.g. including a very low payload). The watermarking scheme considered in this paper is based on self-similarities, and uses a blind mode of extraction (which is mandatory for most of practical applications). In its basic version [START_REF] Rey | Tech. demo.: Image Watermarking for Owner and Content Authentication[END_REF] (i.e. without any advanced error correcting coding scheme), the considered approach already includes an efficient and generic robustness against most of both possible photometric and geometric attacks (including Stirmark [START_REF] Dugelay | Image watermarking: possible counterattacks against random geometric distortions[END_REF] ) but with some limitations. For example, if one considers JPEG compression in particular, our technology may have some difficulties when dealing with factor of quality lower than 50%. The motivation of this work is then to globally increase performances of the watermarking scheme in terms of robustness against some specific photometric attacks (such as lossy compression) through the use of Error Correcting Codes (EEC), while keeping at the same level other parameters in terms of visibility and payload, and without reducing its performances against other attacks (i.e. without specialization). EEC have been successfully used in digital communication systems and data storage applications in order to achieve reliable transmission on a noisy channel. However, the introduction of EEC in this application is not straightforward and requires a specific design to cope with the characteristics of the watermarking technique.

The paper is organized as follows: We first shortly described in Section 2 the main steps involved in the watermarking technology used here. One weakness of the considered approach is that the insertion probability (i.e. host pixels) is quite low (less than 1 out of 2). Powerful error correcting codes are required to recover the non-inserted bits and to improve robustness against some photometric attacks. In Section 3, we draw a short panorama of some previous works in the aforementioned topic and then gradually introduce the ECC framework investigated more particularly in this article. The Section 4 describes our proposed watermarking scheme with the optimised ECC, namely block turbo codes. In Section 5, we report a set of selected simulation results that clearly demonstrate that ECC can play a significant role for enhancing robustness in image watermarking. Finally, we conclude by some remarks and perspectives in Section 6.

WATERMARKING

Basic Recalls on Watermarking

Image watermarking is now a major domain within multimedia processing. Basically, digital watermarking gives the possibility to owners (or providers) to hide an invisible and robust message inside multimedia content, often for security purposes, in particular for owner or content authentication. There exists a complex trade-off between three parameters in digital watermarking: payload, watermarking distortion and robustness. Robustness means that the retriever is still able to recover the hidden message even if the watermarked content has been altered by additive noise, JPEG compression or geometrical attacks.

Eurécom's core technology

The simulation results reported in this paper have been performed using the Eurecom's still image watermarking technology [START_REF] Dugelay | Method of marking a multimedia document having improved robustness[END_REF] that can be summarized as follows. The considered approach is derived from fractal image coding theory, in particular the notion of self-similarity. The main idea is to use some invariance properties of fractal coding, such as invariance by local affine (geometric and photometric) transformations, to ensure watermark robustness. The extraction mode is supposed to be blind.

Signer. The watermark embedding process can be described by the following three steps: formatting and encryption of the message to hide, cover generation, merging of the watermark and the cover.

(i) Formatting and encryption of the watermark. The message bits to be hidden are redundantly distributed: by over-sampling and duplication of the message to obtain a watermark of the size of the image. This redundancy is necessary for a good robustness. Finally, the watermark is globally encrypted using an XOR with a pseudo-random binary sequence generated using a secret key, yielding the encrypted watermark W. The XOR operation enables, on one hand, to secure the hidden message, and on the other hand, to remove repetitive patterns reducing in this way the psycho-visual impact of the watermark embedding.

(ii) Cover generation First, a "fractal approximation" Iapprox is computed from the original image I original . The cover I cover corresponds to the error image that is the signed difference between the original image and its fractal approximation. approx original cover

I I I - = (1)
(iii) Merging of the watermark and the cover The last step of the embedding process consists in modulating the cover I cover with W. The modulation consists of zeroing some of the cover pixels depending on their sign and the corresponding watermark bit to hide. In some other words, only one bit out of two in average really carries hidden information. For visibility reasons, pixels in I cover superior to a given threshold will not host hidden data. Finally, the modulated cover Î cover is added to the fractal approximation I approx to produce the watermarked image I watermarked . cover approx d watermarke

Î I I + = (2)
In average, one pixel out of two of the resulting picture is either equal to its original value or its approximated one.

Retriever.

The watermark extraction algorithm is similar to the embedding algorithm (i.e. dual operations) and its complexity is very similar too. First a fractal approximation is calculated from the watermarked image, which generates a cover close to the original one. Finally the cover is decoded according to the modulation rules (e.g. a positive pixel is supposed to carry a one valued bit and a negative pixel a zero valued bit). The crucial point is that most geometric transformations on the watermarked image are also transferred to the cover: the mark is not lost but the noise has to be correctly positioned with respect to the cover before applying XOR. Therefore, some additional bits called 'resynchronization bits' are added to the useful message bits in order to allow a self and blind resynchronization of samples via two procedures: one for global geometric distortion (rotation and rescaling) based on FFT properties of periodic signals and Hough transform, one for local geometric distortion based on block-matching. Then the watermark can be decrypted and the message recovered.

Use of Error Correcting Codes in watermarking

Since early nineties, a wide range of algorithms and techniques for still image watermarking have been proposed, emerging from various communities. Most algorithms can be characterized according to the strategies used for (i) formatting the message to be hidden, (ii) the choice of a workspace to perform the hiding operation, and then (iii) the method of merging the message and the cover. In general, steps (i) and (ii) are performed in parallel. By default, ECC are mainly involved in step (i). Currently, most of watermarking techniques use, in order to guarantee a minimum of robustness, a redundancy based on a basic repetition of each bit to be hidden. For the technology herein used for our test, the formatting step performed on the payload msg1 can be summarized as follows:

(i) msg1 is over-sampled as illustrated in figure 1 in order to obtain a msg2; (ii) msg2 is then duplicated till the size of the picture as illustrated in figure 2 in order to obtain msg3; (iii) msg3 is globally encrypted (i.e. XOR with a pseudo random binary sequence) as illustrated in figure 3 in order to finally obtain msg4. In order to improve robustness against attacks including more or less complex impacts on luminance values [START_REF] Voloshynovskiy | Generalized watermarking attack based on watermark estimation and perceptual remodulation[END_REF] , an error correcting code can be inserted prior to over-sampling and duplication of the message. It seems obvious that it would be more efficient to use correcting codes instead of a simple duplication of bits. Indeed, this approach appears natural if one compares the watermarking problem with the transmission of a signal over a noisy channel. This model considers the cover as the channel, the watermark as the message to send, and the different attacks as noise. Error-correcting codes are widely used in digital communications which should make them also useful for watermarking issues. Nevertheless, early studies in this field unfortunately report that the present problem is not trivial in practice (correcting codes have not originally been designed for such a context). Basically, the introduction of an error correcting code in the formatting of the watermark increases the number of bits to hide; consequently the number of repetitions of each bit of the watermark decreases in the same proportion.

ERROR CORRECTING CODES IN WATERMARKING

Previous works

Early watermarking techniques used repetition codes to protect the watermark against possible attacks intentional or not. Repetition codes are not efficient in terms of error correction since they exhibit a coding gain of zero dB. Therefore, in a more recent literature, one can find watermarking techniques using more powerful error correcting codes, such as convolutional codes [START_REF] Hernández | Improving Data Hiding by Using Convolutional Codes and Soft-Decision Decoding[END_REF] , BCH codes [START_REF] Tefas | Multi-bit image watermarking robust to geometric distortions[END_REF][START_REF] Darbon | Error Correcting Code Performance for Watermark Protection[END_REF][START_REF] Baudry | Analyses of error correction strategies for typical communication channels in watermarking[END_REF] or concatenated codes based on a convolutional code followed by a Reed-Solomon code [START_REF] Brandão | Improving Spread Spectrum Based Image Watermarking Through Non-binary Channel Coding[END_REF] or even Convolutional Turbo Codes [START_REF] Kesal | Iteratively Decodable Codes for Watermarking Applications[END_REF][START_REF] Pereira | Effective Channel Coding for DCT Watermarks[END_REF][START_REF] Balado | Turbo Coding for Sample-level Watermarking in the DCT domain[END_REF] . Most of the tests were carried out in a JPEG attack context. For very low JPEG quality (under 20%), repetition codes seem the best solution. Note that for such low values, the image is no more exploitable. For the watermarking technique considered here, very powerful and efficient error correcting codes are required to optimize its robustness against some specific attacks (e.g. JPEG or noise) as this technique has been originally designed for a generic and default context of payload, visibility and robustness against attacks, malicious or not (with a special emphasis on geometrical ones). Product codes using iterative decoding techniques [START_REF] Pyndiah | Near optimum decoding of product codes: block turbo codes[END_REF] are an attractive solution for this application as they achieve high error-correction capability with reasonable decoding complexity.

Product codes

Introduced by Elias in 1954, product codes are a serial concatenation of two or more block codes. Let us consider the product code C 1 ⊗C 2 , resulting from the concatenation of C 1 (n 1 ,k 1 ,δ 1 ) and C 2 (n 2 ,k 2 ,δ 2 ), where n i , k i and δ i respectively denote the code length, its dimension and its minimum Hamming distance. A product code word is obtained as follows.

The k 1 ×k 2 matrix information bits are placed in a k 1 ×k 2 matrix. Each row (respectively column) of the matrix is first encoded by C 2 (respectively C 1 ). The resulting n 2 columns (respectively n 1 rows) are then encoded by C 1 (respectively C 2 ). An interesting property of product codes is that all rows are code words of C 2 and all columns code words of C 1 . The product code parameters are the product of the corresponding elementary code parameters. Another interesting feature of such codes is their low decoding complexity. Indeed an elementary block code having the same minimum distance δ exhibits a decoding complexity in 2 δ/2 . The product code can be decoded by first decoding all rows and then decoding all columns (or vice versa) and its decoding complexity is thus given by 2 ξ/2 , with ξ = max(δ 1 ,δ 2 ).

The Chase algorithm

Block codes can be algebraically decoded using Petersons's direct method or the Berlekamp algorithm. This hard decoding is not optimal in the case of soft channel outputs. In this case, the optimal algorithm consists in minimizing the Euclidean distance between the observation and the code word set. Chase proposed an algorithm that achieves nearoptimum decoding. The Maximum Likelihood (ML) decoding looks for the most probable code word among all possible code words. Chase proposed to reduce the searching space to a sphere centered on the hard observation. From this hard observation, a test sequence is built by commuting the least reliable positions. Each test sequence is then algebraically decoded. Among the resulting code word sub-set, the one that minimizes the Euclidean distance with the observation is selected as the decision.

Soft product code decoding : the Chase-Pyndiah algorithm

The near-optimal soft-decoding of product codes was first proposed by Pyndiah [START_REF] Pyndiah | Near-Optimum Decoding of Product Codes[END_REF] and is an extension of the Turbo iterative principle introduced by Berrou for parallel concatenation of two convolutional codes [START_REF] Berrou | Near Shannon limit Error Correcting Coding and Decoding: Turbo Codes[END_REF] . One decoding iteration consists of a decoding of all rows followed by a decoding of all columns or vice versa. Each elementary decoder uses the Chase algorithm and at each step, from the resulting code words sub-set, the most probable code word is selected and for each position, a competing code word is searched. These two code words are used to compute a metric, approximation of the Logarithm of the Likelihood Ratio (LLR) corresponding to the current position. The extrinsic information is extracted from this LLR value to feed the next decoder input.

PROPOSED FRAMEWORK

Let us consider a payload of k 1 ×k 2 binary elements. The payload is encoded by product code C 1 ⊗C 2 . Then synchronization bits are introduced to fight against geometric attacks and the resulting matrix is called S. Each bit of S is locally repeated by a factor (e 1 ×e 2 ) resulting in matrix P. This over-sampling aims at increasing robustness against low-pass filtering. P is then replicated L times to fit the cover image size. Finally the binary elements of the resulting matrix X are summed modulo-2 to a pseudo-random binary sequence in order to obtain a matrix W of independent and identically distributed binary elements. This step is crucial for security in order to prevent malicious modifications of the watermark. The resulting formatted mark W is then inserted in the cover following the Eurécom method explained in Section 1.

At the receiver side, after the watermark extraction and the resynchronization procedure, the soft values corresponding to each coded bit are processed to build an n 1 ×n 2 observation matrix R. R is turbo-decoded according to the iterative process described in Section 2. The decoded message gives an estimation of the original payload.

A compromise must be found between payload size (k 1 ×k 2 ), code length (n 1 ×n 2 ), over-sampling factor (e 1 ×e 2 ) and replication factor L for a given image size (N 1 ×N 2 ) and average number of synchronization bits introduced per coded bit (α). For a given image size, over-sampling factor, code length and average number of synchronization bits introduced per coded bit, the replication factor is upper bounded by: ( )

        × × + × × × ≤ 2 1 2 1 2 1 1 e e n n N N L α (3)
In our application, (N 1 =N 2 =512; e 1 =e 2 =3; α=1). For a code length (n 1 ×n 2 =16×16=256), we obtain L<57. For a code length (n 1 ×n 2 =32×32=1024), we obtain L<15. Statistically, the probability that a bit of the watermark is inserted in the image is less or equal to 50% (see Section 2.2). Moreover, so as to preserve the original image quality, that is to say guarantee the watermark invisibility, a threshold is used to prevent insertions leading to large distortions. This will again reduce the insertion probability (25-50%). A sufficiently large replication factor L is therefore required to combat insertion loss as well as image cropping. Furthermore, L is also lower bounded by unity and thus the code length is upper bounded by: ( ) ( )

        × × + × ≤ × 2 1 2 1 2 1 1 e e N N n n α (4)
In our application (n 1 ×n 2 ) ≤ 120 2 . This limits the range of codes (16, 32, 64) used in this application. For a given code length, we can use different code dimensions to adapt the payload size. Simulation results are presented in next Section.

PRELIMINARY RESULTS

In this section, first results performed on a database of 75 images of size 512×512 pixels are presented. All the results are expressed in terms of message error rate (MER). We define the MER as the ratio of the number of erroneous watermarks on the number of extracted watermarks. A watermark is erroneous so at least one of its bits is false. In figure 4 we show the experimentally measured MER versus the quality level of the JPEG compression applied to the watermarked images. The payload was set to 121 bits. In this figure, several curves have been plotted corresponding to different coding (and decoding) strategies (repetition code only, BCH(128,120), BCH(256,123) and product code BCH (16,11) 2 ). For any given JPEG quality, concatenation of repetition and product codes using soft-decoding algorithm appears to be the best solution. The watermark is recovered without any bit error down to 30% JPEG quality, while some errors are observed at 50% JPEG quality when using only repetitions. Concatenation of repetition and BCH codes also performs better than a simple repetition code, but it is less efficient than concatenation of repetition and product codes. Moreover, when the repetition codes are hard-decoded, the performances of the turbo decoder decrease significantly. Figure 5 and 6 shows Message Error Rate performances against JPEG compression and additive gaussian noise for different payloads (i.e. 77, 121, 441 and 676 bits) and code lengths using concatenation of repetition and product codes. For constant code lengths (256 or 1024) we observe that there is a mild degradation as we increase the pay load. As we increase the pay load at constant code length, the error correction capability decreases and results in a lower coding gain. On the other hand, there is a much larger degradation when the code length is increased for codes with the same minimum distance ((16,11) 2 and (32,26) 2 ). Theoretically, as we increase code length for a given minimum distance the coding gain increases. However, this coding gain is not sufficient to compensate the loss due to the decrease in the replication factor L which is here divided by 4. The received signal energy per information bit is divided by 4 and the insertion probability of a given information bit varies as (1-(1-p) -L ) where p is the insertion probability per pixel. Thus as we increase code length in order to achieve higher pay loads, there is a significant penalty in terms of robustness.

CONCLUDING REMARKS

In this paper, we have proposed an enhanced still image watermarking scheme using powerful error correction block turbo codes to improve its resistance to photometric attacks. Simulation results show that for a fixed distortion (by default fixed to 38dB) and a given payload (here 121), the message error rate is still equal to zero down to 30% of quality instead of 50% without product codes. For different tested payloads and attacks (JPEG or additive Gaussian noise), there is a significant global gain. Our results confirm previous ones reported by Kesal et al. that BTC coding scheme outperforms all other coding solutions for watermarking applications. Our perspectives will focus on the study of a channel model in order to determine the theoretical capacity, and then to compare simulation results with theoretical performances. Also, we plan to investigate how obtained results on error correcting codes can be extended to other watermarking technologies. Finally, some possibly more powerful product codes and flexible BTC in terms of payloads and code rates will be investigated.

Figure 1 :

 1 Figure 1: over-sampling of the binary sequence msg1

Figure 2 :

 2 Figure 2: message duplicated Figure 3: pseudo random binary sequence

  Rpt. codes (hard) Rpt. codes (soft) + BCH(128,120) Rpt. codes (soft) + BCH(256,123) Rpt. codes (hard) + BCH(16,11) 2 Rpt. codes (soft) + BCH(16,11) 2

Figure 4 :

 4 Figure 4: Message error rate versus JPEG quality for different coding (and decoding) schemes

Figure 5 :

 5 Figure 5: Message error rate versus JPEG quality (left) and gaussian noise (right), for different payloads and code lengths.