Chapter 1 Introduction For Gesture Based Human Computer Interaction

The ease with which we type a text with keyboard, navigate the web with mouse, command smart devices by voice comes from the decades of study on Human-computer interaction (HCI). The current ubiquitous direct manipulation interface, where visible objects on the screen are directly manipulated with a pointing device, was rst demonstrated by Ivan Sutherland in Sketchpad [START_REF] Sutherland | Sketchpad: A man-machine graphical communication system[END_REF] in 1963. It supported the manipulation of objects using a light-pen, including grabbing objects, moving them, changing size, and using constraints. Nowadays, mouse has been a standard device to replace the light-pen as a virtual human nger in the interface. Usually people use two ngers on mouse, by left and right click, to achieve the majority of operations. Multi-touch screen techniques open a way to let people extend these operations on virtual elements. It provides the users a 2D environment enabling people contacting virtual objects with full ngers instead of using two ngers clicking. This technology has penetrated into common electronic devices around us. The smart phone abandons physical keyboard and uses virtual keyboard on screen instead. Traditional notebook is replaced by Touchpad which provides a more convenient writing environment. Large interactive advertisement board appears on the street so that people can easily nd the interest they want.

Since touch gesture has replaced most of the operations of mouse and keyboard on screen, the question then raises whether we can use touch gestures beyond direct manipulations. In reality, hand gesture can be used as a form of non-verbal communication between people through sending and receiving wordless clues. An example is American Sign Language(ASL), which is a natural language that chiey uses manual gesture to convey meaning serves for deaf communities. So is it possible to teach computer the sign language and make people use symbolic gestures to execute commands? Actually, the current handwritten character recognition is one of these techniques. It teaches the computers to recognize the input nger's trajectories and transform the trajectories to corresponding characters. By the nature of character writing, current studies mostly focus on the mono-touch trajectories recognition, i.e. the trajectories are always written by a single nger. There are few research on the study of multi-touch gesture (like the ASL, with both hands, ten ngers) recognition for symbolic command.

In this thesis, we study the multi-touch gesture recognition problem. We explore the possibility of using multi-touch gesture for not only direct manipulation but also indirect symbolic command. The main contribution of this work is to provide tools and algorithms, mainly based from pattern recognition and machine learning theories to enrich User Interface Design solution. Of course, many other contributions that are not addressed in this work are required to design a global system. Specially, human factors and ergonomics, user experiences, user interface scenographies are beyond the scopes of this works. Our goal is to address the complexity of multi-touch gestures and develop a system to well analyze and recognize multi-touch gestures.

Organization of the manuscript

The manuscript of this thesis is organized as following:

Chapter 2: There have been years of studies for the usage of touch gestures. We introduce in this chapter the state-of-the-art research for both direct manipulation and indirect command. We discuss the dierent type of underlying recognition methods for both mono-touch gesture and multi-touch gesture.

1.1. Organization of the manuscript Chapter 3: In this chapter, we propose a graph modeling strategy to characterize the temporal and motion features of multi-touch gesture. To verify our graph modeling and recognition strategy, we build a MTGSet which is a multi-touch gesture dataset as benchmark test.

Chapter 4: The current use of multi-touch gestures is mostly restricted to direct manipulations. We study the possibility of using multi-touch gesture for both direct manipulation and indirect command. We propose an early recognition strategy enabling the systme to recognize a gesture by its beginning part in order to give a feedback to the user as soon as possible.

Chapter 5: The nal goal of our research is to provide a real context that includes dierent types of gesture commands. As a rst step towards this target, we develop a multi-user structured document composition environment where two users can simultaneously use gestures to compose a diagram. We build a multi-user gesture dataset and develop an eager recognition system to recognize the gesture on-the-y in order to give a real time feedback to the users. This project is co-funded by the region of Bretagne and Pay-de-la-Loire. We also thank Excense company for their support.

Chapter 1 Chapter 2

State Of The Art 2.1 Preamble

This chapter presents an overview of the research and development status of the handwritten gesture recognition problem. To broaden the scope of the presentation and clarify some terms related to the domain, in section 2.2, we will rst give a brief introduction of the basic concepts used in human computer interaction. Specically, one important point is to make a distinction between direct manipulations and indirect commands, to introduce the notions of early recognition or lazy recognition. Each of these activities does not provide the same service and it is important to understand what can be expected as outcomes.

Then, in section 2.3, we focus more specically on gesture interaction, and propose a classication of gestures related to the number of strokes, the number of simultaneous touch points, and the number of simultaneous users.The reason being that in this work, one original scope is to address multi-stroke and multi-touch gestures.

When developing a recognition system, the necessity of real-time classication based upon the principle that users must receive immediate and appropriate visual feedback about the eects of their actions has to be considered. In this context, early recognition methods are introduced in section 2.4. This strategy aims at recognizing gestures from their distinctive beginning part and achieves to recognize as soon as possible.

Finally, a global use case is proposed to conclude this chapter through the study of structured document composition systems. Such systems combine multi-touch interaction with recognition paradigms to facilitate digital document production. We will review the general handwritten document recognition methods and discuss the diculties to associate them with multi-touch gesture. 9 Chapter 2

Denition

Devices enabling touch input have been developed over the last decades providing a more convenience way for human-computer interaction. In recent years, touch gesture based applications have been growing considerably due to the prevalence of the smartphone and touch pad. In this section, we will illustrate some important concepts for handwritten gestures that help the readers to understand challenging work in this domain.

Direct manipulation & Indirect command

While as presented in the general introduction, many dierent modalities can be used to perform interaction, we will introduce the concepts of direct manipulation and indirect command using touch gesture examples. From the interaction point of view, touch gesture can be used for two aspects: direct manipulation for (virtual) elements and indirect symbolic gesture for triggering command. Common examples of direct manipulation are: using one nger holding on an element for selecting and dragging the element for moving. A more comprehensive context for direct manipulation can be found in a map view application, where users may scroll (pan) the map by dragging, change the zoom level by using two ngers for a pinch or stretch gesture, rotate the map by placing two ngers on the map and applying a rotate motion. Usually a direct manipulation system would give a continuous feedback, such as scroll the map, while the users move their ngers.

The indirect symbolic gesture is a one-shot operation commonly used in sketch-based interaction. Users may draw a certain gesture to trigger a corresponding pre-dened command. Such examples can be found in [START_REF] Appert | Using strokes as command shortcuts: Cognitive benets and toolkit support[END_REF], where the stroke gestures are used as shortcuts to draw predened objects (shown in Fig. 2.1). Another widely used indirect command example is handwriting, where user input a character by drawing its shape instead of using keyboard. Since the two interactions oer dierent feedback to users, the underlying recognition strategies have a clear dierence. In the following section, we will review the recognition methods based on dierent gestures and dierent interactions.

Touch Gesture

Depending on the dierent interaction contexts, touch gesture varies from shape, number of strokes and number of simultaneous touches. In [START_REF] Schmidt | Template based classication of multi-touch gestures[END_REF], authors summarize the dierent type of touch gestures based on the number of strokes and touches as shown in Fig.

2.2.

Here, a stroke is regarded as the trajectory of a touch (nger, stylus, etc.) during uninterrupted contact on the sensing surface. The touch number indicates the number of concurrent contacts involved. For instance, the single-touch describes gestures only using one touch per stroke. This is the simplest touch gesture that can be used for both direct manipulation and indirect command. Common examples of single touch direct manipulation could be dragging on a virtual element or scrolling on a map application.

The multi-stroke is the gesture which contains at least two strokes by one touch. This gesture is widely used for inputing sketches or characters which contains complex structures that can hardly be achieved by one stroke. Usually systems for multi-stroke give respond only after all the strokes are performed. Therefore multi-strokes gesture is only used for indirect command. The term multi-touch is a more complex gesture such that more than one concurrent touch is involved. Such gestures are mostly used for direct manipulation such as zoom or rotation, where two or more simultaneous touches are performed on a sensing device.

To the best of our knowledge, there is only a few studies and applications using multitouch gesture for indirect command. For instance, a Mac's multi-touch trackpad [Sup16] provide 8 direct and 7 indirect pre-dened gesture commands with dierent number of touches involved. the indirect gestures are simply swipe based, which use 2 or more ngers moving towards a same direction. Only 'show desktop' and 'launchpad' adopt complex gesture, which require 4 ngers spreading or pinching, for indirect commands. Meanwhile, this trackpad does not support for user-dened gesture command so that it is not as convenient as shortcut from keyboard. Another indirect command use case can be found in [START_REF] Sae-Bae | Investigating multitouch gestures as a novel biometric modality[END_REF],

where `multi-touch' gesture are considered as a remarkable biometric signal for user identication. In our view multi-touch gestures are supposed to be of special interest as they involve all degree of freedom. Aiming at the development of a general multi-touch gesture recognition system, our work focus on using multi-touch gesture as indirect command. Lastly, the term Sequential multi-touch is not a common used gesture type. It refers to the gesture if it incorporates at least two subsequent strokes and simultaneous touches.

It is dened and studied in [START_REF] Schmidt | Template based classication of multi-touch gestures[END_REF], where authors aims to provide a classier that covers all kinds of strokes and touches. Fig. 2.16 gives examples of sequential multi-touch.

In section 2.3, we will review the recognition strategies from the basic single touch gesture to the most complex multi-touch gesture.

Early Recognition

In general, an indirect gesture recognition system outputs the result after the end of a gesture. However, since touch trajectories are online data, gestures may have signicant dierences in their beginning part so that the recognition can be achieved before their end.

The underlying strategy is named as Early Recognition (ER), which aims at providing results before input gestures are completed. This strategy is important to develop practical and intelligent gesture or motion based man-machine interface. For example, motion based video games allow user to use motion gesture (such as jumping, squatting, hand waving) to control the game character. If the recognition process is executed after the gesture, there would be a signicant delay between the user and game character. This delay decreases the usability and user experience of the system. In order to reduce the delay, early recognition has to be involved so that gestures can be recognized as soon as possible. we can easily expect correct early recognition results. In contrast, gestures in Fig. 2.4(c) have exactly same beginning part and can only be distinguished near the end. Therefore, an ideal early recognition algorithm should be able to detect these ambiguous common parts and nd a balance between `early' and `accuracy'. In section 2.4, we will review the state-of-the-art methods for early recognition.

Handwritten Gesture Recognition

In this section, we discuss the state-of-the-art handwritten gesture recognition methods for dierent type of gestures.

Single Touch Gesture

As the simplest gesture, single touch gesture is widely used in many interaction system for both direct manipulation and indirect command. While used as direct manipulation, single touch gesture is mostly used for moving a selected virtual element. System need to measure the touch's movement direction, speed and displacement to give a corresponding Chapter 2 movement for the virtual element. Most of these movement information can be obtained directly from the underlying hardware and does not require complex recognition processing.

Figure 2.5: Single touch gesture set for executing commands. [START_REF] Wobbrock | Gestures without libraries, toolkits or training: A $1 recognizer for user interface prototypes[END_REF] It becomes a symbol recognition problem while gestures are used as indirect commands.

As shown in Fig. 2.5, which is a single touch gesture set studied in [START_REF] Wobbrock | Gestures without libraries, toolkits or training: A $1 recognizer for user interface prototypes[END_REF]. Each gesture can be either linked to trigger a command or used as text input. Basically, there are two types of recognition strategies for single touch gesture (also named as single stroke, unistroke gesture): 1) sequence matching; 2) statistical recognition based on global feature.

The online touch stroke data consists of a sequence of touch points from the touch down to the touch up. Dynamic programming algorithms such as dynamic time warping (DTW) can be employed for performing non-linear sequence matching. For more details about DTW, the reader is referred to [START_REF] Vuori | Experiments with adaptation strategies for a prototype-based recognition system for isolated handwritten characters[END_REF].

In [START_REF] Wobbrock | Gestures without libraries, toolkits or training: A $1 recognizer for user interface prototypes[END_REF], authors present another competitive sequence matching algorithm named $1 recognizer , for single stroke recognition. Instead of time warping, $1 resamples each stroke into a xed number of points. Then a candidate C is compared to each stored template T i to nd the average distance between corresponding points using a point-topoint matching equation,

(a) f 1 (X i,t , X i,t-1 ) = [dx, dy, θ] T (b) f 2 (X i,t , X i,t-1 ) = d i,j
d i = N k=1 (C[k] x -T i [k] x ) 2 + (C[k] y -T i [k] y ) 2 N (2.1)
where k is the point index for each symbol. x, y is the coordinate of each point. The template T i with the least path-distance to C is the result of the recognition.

The sequence matching algorithm is easy, cheap and accurate with only a few loaded templates on a small dataset. It requires no complex mathematical procedures, yet competes with approaches that use statistical classication. Such algorithms are highly ecient for recognition of specic sets of simple gestures but do not tolerate much variation in the writing style or drawing process. To generalize the gesture representation and make use of the fast developing statistical recognition method, a tendency of using global features to characterize a gesture can be noticed for gesture recognition.

Generally global features are chosen according to the following criteria. Each feature should be meaningful so that it can be used in gesture semantics as well as for recognition.

There should also be enough features to provide dierentiation between all gestures and should not be too many for eciency reasons. The Rubine 's feature set is a typical global feature set which has been widely used for recognizing single stroke gestures [START_REF] Rubine | Specifying gestures by example[END_REF]. It employs 13 global features which are computed from a complete gesture shape. Fig. 2.7

shows a part of features used by Rubine, where (f 3 ) and (f 4 ) are the length and angle of the bounding box diagonal, (f 5 ) is the distance between the rst and the last point. The full 13 features can be found in [START_REF] Rubine | Specifying gestures by example[END_REF].

After this feature extraction, each gesture is represented by a feature vector, f = [f 1 , ..., f 13 ]. Then classical statistical recognizer or linear/nonlinear machine can be implemented to achieve the classication.

Due to the fact that single touch gestures are chosen to be not ambiguous and simple to Chapter 2 Figure 2.7: Features used to identify strokes. [START_REF] Rubine | Specifying gestures by example[END_REF] be memorized has less variation and writing style, the methods above have been proved being ecient and accurate for single touch gesture recognition even though they are simple and cheap. Unfortunately, they are only moderately successful when applied to multi-touch/multi-stroke pen input. Shape variation, writing order, number of strokes have to be taken into account. We will provide a review of multi-stroke gesture recognition method in next section.

Multi-stroke Gesture

The term multi-stroke gesture here refer to the isolate symbols that contain two or more strokes, and all strokes are written in a sequence by a single contact (nger, stylus, etc.). Obviously multi-stroke gesture is not used for direct manipulation because users always expect an action after the end of the nal stroke instead of during the writing process. Comparing to the single-stroke gesture, multi-stroke gesture contains more stroke variations and oer more freedom for the users. Therefore, it has a diversity of usage such as for drawing characters, pictograms, diagrams, etc. The diversity of patterns and high variation on stroke number and writing order make the recognition becomes a more challenging work. Large variety of methods have been proposed to solve this problem. This section propose to categorize these methods and provides a review of typical recognition methods for each category. Note that this thesis focus more on multi-touch gesture recognition which is more complex but has less studies (shown in next section). We review the recognition methods for multi-stroke gestures in this section to reect the diculties for multi-touch gestures recognition and also enlighten us the way to solve that problem.

Trajectory based

Since multi-stroke gesture is also written by a single contact, the trajectory can still be seen as a sequence of points but containing special pen up/down points. With an appropriate adjustment or constraint, the sequence matching strategy for single stroke gesture is still available for multi-stroke cases.

In [START_REF] Wobbrock | Gestures without libraries, toolkits or training: A $1 recognizer for user interface prototypes[END_REF], authors add pseudo strokes to concatenate each two consecutive strokes.

Each pseudo stroke starts at the end point of a previous stroke and ends at the start point of the following stroke. The multi-stroke gesture is then transformed as a single stroke so that any single stroke recognition method can be used. A similar strategy can be found in [START_REF] Niels | The nicicon database of handwritten icons[END_REF], authors also add the pseudo strokes and implement the traditional DTW algorithm for gestures comparison. They give the constraints for DTW that each point in pseudo stroke can only be matched to a point in another pseudo stroke, same for the real point. Classication of a test sample is performed through nearest neighbor criteria with the DTW distance function.

Even though these methods well transform the multi-stroke problem to the single stroke problem, the concatenation between two strokes limits the gesture to be written in a xed order and direction. To ensure the dierent stroke orders and directions can be properly recognized, [START_REF] Anthony | A lightweight multistroke recognizer for user interface prototypes[END_REF] present $N recognizer which is a signicant extension to the $1 unistroke recognizer introduced in previous section. Basically, $N goes further by recognizing gestures comprising multiple strokes and automatically generalizing from one multi-stroke to all possible multi-strokes using alternative stroke orders and directions.

The main idea is to generate all permutations of the component strokes. Each permutation represents one possible combination of stroke order and direction. There are 2 N combinations for N strokes. Fig. 2.8(a) shows 8 possible permutations for a two-stroke x . The permutations of possible combinations are then converted to unistroke (shown in Fig. 2.8(b)) by simply connecting the endpoints of component strokes as presented in [START_REF] Wobbrock | Gestures without libraries, toolkits or training: A $1 recognizer for user interface prototypes[END_REF] and stored in template set for comparison. At runtime, each candidate multistroke gesture is also connected in the drawn order to form a unistroke and compared to all unistroke permutation templates using the $1 algorithm.

Obviously, the brute force of creating all permutations to represent a multi-stroke gesture results in a combinatoric explosion when the stroke number is large. This method is ecient for the gestures which contains a few strokes but not suited to recognition messy drawing such as Chinese characters or sketchy symbols.

These trajectory based methods are simple, require little processing resource, and easily extensible to new class because most of them rely on nearest-neighbor classication paradigm. This simplicity enable easy incorporation of multi-stroke gesture recognition for user interface prototypes which do not require heavy and complex engine.

Structure based

Instead of transforming the multi-stroke into a single sequence, the structure based methods focus more on each individual stroke and the inner relations between each two strokes.

These methods usually apply to the multi-stroke symbols which contain much more strokes and are insensitive for the writing order, such as handwritten sketch. Fig. 2.9 shows 2 examples of handwritten sketch from [START_REF] Mas Romeu | Automatic Adjacency Grammar Generation from User Drawn Sketches[END_REF] In [START_REF] Liang | Sketch matching on topology product graph[END_REF], authors present a typical state-of-the-art structure based sketch recognition method which exploits topology relations and graph representation for strokes. In sketch recognition domain, since the sketches are complex and contain large number of strokes, raw input of handwritten sketches usually consist of noisy and inaccurate strokes.

As a standard techniques, the strokes are rstly rened and decomposed into a few basic primitives. Authors adopt the renement approach in [START_REF] Xiangyu | On-line Graphics Recognition[END_REF] which has four steps: polygonal approximation, agglomerate points ltering, endpoints renement and convex hull calculation. Details can be referred in [START_REF] Xiangyu | On-line Graphics Recognition[END_REF]. An example is given in Fig. 2.

10
where an open ended triangle becomes closed after processing. The rened strokes are then segmented into sub-strokes and tted to a few primitive shapes. Note that the renement and segmentation perform well on clean dataset, noisy or highly curved strokes are still hard to be segmented properly.

There are plenty of ways to dene the relations for each pair of primitives. Mas et. al By its nature, graph representation usually has a complex topology structure since it measures relations for each primitive pair. Due to the fact that dierent researchers dene dierent topology relations and features for the primitives, it is dicult to give a general recognition strategy for graph representation. Normally, researchers design their specic graph matching and recognition method according to the graph structure and feature they used. Sousa et al. [START_REF] Sousa | Sketch-based retrieval of drawings using spatial proximity[END_REF] use graph spectra to map graphs into vector descriptor.

The spectrum of a graph G (which consist of n eigenvalues, where n is the number of nodes) is computed from the eigenvalues of its adjacency matrix. They compute the similarity between graphs by calculating a distance between the correspondent descriptors.

[LLLW15] dene a novel product operation to calculate the element-wise multiplication of two adjacency matrices. This operation is used to nd the common structure parts of two graphs and measure the similarity between two sketches.

The graph based methods are slow because they perform graph matching for each sketch in the dataset, and their runtime increases with respect to the complexity of graphs.

This makes it hard to directly apply to a large scale database. To accelerate the recognition process, Bunke et al. [START_REF] Riesen | Graph Classication and Clustering Based on Vector Space Embedding[END_REF] present a general method of transforming any graph into vector descriptors. We will detail this method in later section.

Feature based

Extracting features to train and feed a statistical classier, such as kNN, neural networks, support vector machine(SVM), is a more popular solution in pattern recognition. A very close topic which has been widely studied is isolated character recognition [START_REF] Ding | A comparative study of gabor feature and gradient feature for handwritten chinese character recognition[END_REF] where characters can be seen as isolated multi-stroke symbols. In our specic case of indirect multi-stroke gesture recognition, simple features inherited from Rubine's ones can be extended. A tendency is concerned to induce more and more complex feature based on both static (stroke number, convex hull, area) and dynamic (average direction, velocity, curvature) information. In [START_REF] Laviola | A practical approach for writerdependent symbol recognition using a writer-independent symbol recognizer[END_REF] authors design a 14 features set. In [START_REF] Niels | The nicicon database of handwritten icons[END_REF] authors Chapter 2 employed Rubine's features and an additional 15 other global features that make it to 28.

In [START_REF] Willems | Iconic and multi-stroke gesture recognition[END_REF] authors design 20 new global features and add it to those 28 features that results to a 48 features set. In [START_REF] Delaye | Hbf49 feature set: A rst unied baseline for online symbol recognition[END_REF] authors design their own 49 features set.

We will not detail each feature. Most of the features are geometry features as Rubine's features which describe the appearance of the writing result. The role of a feature set is to numerically describe symbols and create boundaries between them, so one symbol can be discriminated from another in the corresponding feature space. It is dicult to tell which feature set or individual feature is most discriminative. The recognition result is also highly related to the recognition method and dataset they used. In [START_REF] Delaye | Hbf49 feature set: A rst unied baseline for online symbol recognition[END_REF] authors compare dierent feature sets on four datasets. There is no evidence to believe that a more complex feature set can always yield a better result. Some simple and universal feature sets can also outperform the systems that were designed, tuned and optimized for recognition of specic datasets.

Multi-touch Gesture

The multi-touch gesture interaction become popular with the development of touch screen display technique in recent years. A common sense for the usage of multi-touch gesture is to directly manipulate a virtual element on the touch interface. Usually a direct manip- In order to detect the user's intention from the trajectories, they dene three motion parameters, respectively related to the three motions, that calculate the displacement of touch points between each time t -1 to t. The denition of three motion parameters are shown in Fig. 2.14. The system triggers the corresponding motion operation when the variation of any motion parameter is larger than a certain threshold. Another similar method can be found in [ORB + 15], where authors dene three distance functions (swipe, rotate and zoom) to evaluate the displacement of ngers. The chosen motion is given by any of the three distance with the highest value.

(a) f 1 (X i,t , X i,t-1 ) = [dx, dy, θ] T (b) f 2 (X i,t , X i,t-1 ) = d i,j (c) f 3 (X i,t , X i,t-1 ) = θ i Figure 2
.14: The motion feature functions: f 1 measures the translation vector of i th point pair between time t -1 and t. f 2 measures the distance d i,j between points in a certain time. f 3 measures the rotation angle θ i of i th node between time t -1 and t. [START_REF] Oh | Mrf-based particle lters for multi-touch tracking and gesture likelihoods[END_REF] To the best of our knowledge, there is few researches aiming at the development of a multi-touch gesture recognition system for indirect command as well as the multi-stroke gesture interaction. Unlike the multi-stroke gesture where strokes are always written in sequence, the strokes in multi-touch gesture may have complex synchronization or intersection relations. Two gestures may have the same appearance but contain dierent inner-stroke relations. A fundamental issue is the modeling of these relations between strokes as the key feature for multi-touch gesture recognition.

Some context dependent works use syntactic approaches, i.e. a textual description for strokes, to describe the movements and temporal progressions of a multi-touch gesture.

For example, Kammer et holding on the screen while another nger is performing synchronously a SEMICIRCLE type gesture. An example is shown in Fig. 2.15. A similar approach can be found in [START_REF] Kin | Pro-ton++: a customizable declarative multitouch framework[END_REF], where authors specify each gesture as a regular expression over a stream of touch event. The recognition is involved by matching the event stream to a list of predened regular expression in order to trigger the operation. These methods abstract each stroke to a predene atomic gesture and focus more on the dynamic relations between strokes. Because of lacking of analyzing global geometry features, these method are believed to apply to simple multi-touch gesture but fail to recognition gestures which have complex shapes. This system analyzes the geometry feature for each stroke and compares two gesture from the global point of view. However, it assumes that each gesture has a xed number of strokes and all strokes are performed synchronously. This strategy is not general enough to deal with the various type of multi-touch gestures.

The most related study can be found in [START_REF] Schmidt | Template based classication of multi-touch gestures[END_REF]. They aim at the development of a multi-touch gesture recognition system for self-dened gestures as well as sketch-based interaction techniques. Fig. 2.16 shows some examples of their gestures set. Fig. 2.17 provides an overview of their recognition procedure. The main contribution of the system is the feature extraction of each stroke and a pairwise stroke matching based classier. In feature extraction, they extract not only the local shape features of each stroke but also the relative structural and temporal features within the gesture.

Based on these features, they independently build a statistical model for each stroke in the gesture. A gesture template is shown as a set of statistical models of all its strokes. The classier is achieved by comparing an input gesture with every gesture template regarding each stroke model. This is done by handling strokes separately and computing a matrix containing pairwise matching likelihoods of template strokes and input strokes. A best matching likelihood is computed by solving the maximum matching problem formulated by this matrix. However, a shortage of this research is that all the gestures in this dataset consist of 3 strokes, authors did not study the robustness for varied number strokes. Moreover, this dataset does contains gestures which have same appearance but only dier from written order (e.g. in Fig. 2.16, gesture No. 07 and No. 08 have same two synchronized strokes, they dier from the written order of the third stroke). But there are no two gestures which have same appearance but dier from the synchronized strokes. These problems have not been addressed in this state-of-the-art work and they may limit to recognize the user's self-dene gestures. The community still need a more general multi-touch gesture dataset and more study on multi-touch gesture recognition problem.

Early Recognition

As we illustrated in previous section, the recognition for direct manipulation gesture and indirect command gesture are completely dierent. The former one use a real-time strategy which analyze the ngers'trajectories during each time interval, while the latter one has to wait until the end of trajectories, and analyze the global structure or shape of the gesture. Normally, practical applications use either of them for human computer interaction. However we imagine a certain context which support both of these interaction, an underlying recognizer may be confused about whether it should interpret the input as direct manipulation or wait until the end. The co-existence of these two usages requires a feedback as soon as possible to be consistent with a direct manipulation. Hence, an Early Recognition (ER) strategy is desirable to cope with these two kinds of commands.

A basic idea of ER is to employ a partial matching method, where the recognition result of an input pattern is determined by the matching distance of its beginning part from reference patterns. To the best of our knowledge, Petit et al. [START_REF] Petit | Unifying gestures and direct manipulation in touchscreen interfaces[END_REF] proposed for the rst This is a typical but imperfect example which well illustrates the strategy and diculty for early recognition. Some gestures may contain very similar beginning part which confuse the system that gives a incorrect feedback. An ideal early recognition system should collect enough information before making a decision and avoid the ambiguous beginning part. Unfortunately, there are few ER works for on-line 2D handwritten gesture.

We will review the early recognition method in related domain in the following part to explore the general idea for early recognition algorithm.

In [MUK

+ 06], Mori et al. use early recognition for motion gesture prediction. The proposed early recognition algorithm is based on conventional dynamic programming (DP). Fig. 2.19 gives an overview of their recognition method. Let I = I 1 , I 2 , . . . , I τ be an input gesture sequence, where I τ represents its feature vector at frame τ . Similar, let R = R 1 , R 2 , . . . , R t be a registered reference gesture sequence, where R t represents its feature vector at frame t. A conventional DP algorithm for recognizing the input gesture sequence I is considered as an optimal nonlinear matching algorithm between I and R.

Their algorithm is described as following:

Step 1: For τ = 1, 2, . . . , repeat Step 2-3.

Step 2: For t = 1, calculate the following DP-recurrence equation:

g 1 (τ ) = 3d 1 (τ ). (2.2)
Chapter 2 where d t (τ ) represents the distance between I τ and R t

Step 3: For t = 2, . . . , T , calculate the following DP-recurrence equation:

g t (τ ) = min    g t-1 (τ -1) + 3d t (τ ) g t-1 (τ -2) + 2d t (τ -1) + d t (τ ) g t-2 (τ -1) + 3d t (τ ) + 3d t (τ )    (2.
3)

The non-linear matching distance at input gesture's frame τ is provided as

d(τ ) = g T (τ ) (2.4)
The above conventional DP algorithm works successfully to matching an input gesture sequence to entire part of a reference gesture. To achieve the early recognition, authors slightly modify the above algorithm. Specically, the distance is re-dened as To deal with the common beginning part problem, in [START_REF] Kawashima | Adaptive template method for early recognition of gestures[END_REF], authors propose to calculate the distance gap between the most and second most similar gestures. Denoting the nearest class c 1 and the second nearest class c 2 , the result is determined as the class c 1 when the dierence of the two classes fullls d(c 2 ) -d(c 1 ) > th. The threshold th is the parameter which determines the timing of early recognition. A large threshold would result a high recognition accuracy with the price of a high recognition time delay. In the worst case, recognizer need to match the entire sequence of the input gesture to make the decision. In other words, there is a trade o between recognition time and accuracy, the earlier decision is made, the less accuracy results.

d * (τ ) = arg min t * g * t (τ )
In [START_REF] Uchida | Early recognition of sequential patterns by classier combination[END_REF], authors present a general early recognition method using multi-classier strategy. They train a set of frame classiers h 1 (x), . . . , h t (x), . . . , h T (x), where h t (x) is a frame classier prepared at tth frame, x is a set of training pattern. The frame classier h t (x) provides a recognition result by only using the feature vector of the tth frame. The recognition result at the tth frame will be determined by combining t recognition results provided by h 1 (x), . . . , h t (x), i.e.,

H t (x) = sign( t τ =1 α τ h τ (x)) (2.6)
where α τ is the weight of each individual classier computed by the error rate of h τ (x). One possible denition of α τ is

α τ = 1 2 ln( 1 -ε t ε t ) (2.7)
where ε t is the error rate. Moreover, authors optimize this procedure using weight propagation. When training the frame classiers from t = 1 to T , the patterns misrecognized by the last classier h t-1 (x) are largely weighted not to be mis-recognized by h t (x). Fig. 2.20 illustrates this procedure. We refer readers to their paper for more details.

This multiple frame classier strategy achieves a better results than each individual frame classier because the multi-classier can form its discrimination boundary in a higher dimensional feature space (As shown in Fig. 2.20(c)). In a short conclusion, the above methods try to solve the early recognition using different strategies, either partial matching between two sequences or multi-classier at each frame. However, there are few works to explore the intrinsic problem of early recognition, i.e. how to well identify the ambiguous common beginning part of dierent gestures and give a optimal trade o between recognition time and accuracy. In chapter 4, we will present our reject option based method for this target. Chapter 2

Structured Document Composition and Recognition

By structured document, we refer to the documents that consists of two-dimensions arranged symbols (e.g. owchart diagrams, musical scores, electrical circuits). Examples of a owchart and a logic circuit are shown in Fig. 2.21. To realize the full diagram recognition, in general two subproblems have to be solved: 1) Detection of elementary units.

2) Retrieval the relations among elements. Unlike the isolated symbol recognition, where all strokes are known to be a part of one symbol, a stroke in a diagram can have many dierent interpretation depending on its context. A stroke could be a one-stroke symbol, a part of multi-stroke symbol or even contains several symbols. The complex stroke combination problem is so challenging that many existing recognition systems avoid it by placing constrains on the way user draws. For instance, some authors require users to draw symbol with only one stroke [START_REF] Landay | Sketching interfaces: Toward more human interface design[END_REF], some others require the user to provide explicit cues, such as making a pause between two symbols [START_REF] Hou | Calligraphic interfaces: Classier combination for sketch-based 3d part retrieval[END_REF]. These constrains facilitate the recognition process but fail to match the way people naturally draw. From the interaction point of view, there are two recognition strategies for structured document recognition, shown in Fig. 2.22. The rst is lazy interpretation, which uses the full document as the input and recognize all the symbols and their relations in one shot.

The analysis process ignores the user's creative phase during the document composition and has full context to make the most sensible decision. Lazy interpretation oers the advantage that every stroke in a completed document is meaningful (despite the noise) for the nearby context. It means that a stroke is certainly either to be an isolated symbol, or supposed to be grouped with nearby strokes to form a multi-stroke symbol since full context is presented. The diculty of detecting elementary units introduced above transforms into a stroke grouping problem based on their spatial and temporal relations. Plenty of research give their eort in this orientation. [START_REF] Awal | First experiments on a new online handwritten owchart database[END_REF] Another strategy is eager interpretation, which is a real-time recognition solution. It tries to interpret each stroke as well as their structure during the composition, more precisely after each input stroke. By eager interpretation, it incrementally updates the recognized document according to the coming stroke and oers a real-time visual feedback to the users. Comparing to the lazy interpretation, eager interpretation gives a more naturally way for human-computer interaction that allows immediately validation and correction from users instead of waiting to the end. However, the diculties are also obvious: not every stroke is meaningful for the nearby strokes when it is completed.

A stroke could be a beginning part of a symbol and the full symbol has not yet been nished. On the one hand, the system need to be intelligent enough to identify the unnished strokes and wait for more information to make the decision. On the other hand, the analysis process must be ecient to keep the use'pace that gives feedback as soon as possible. Eager interpretation still remains a complex and open problem that is rarely exploited. Chapter 2

In our work, we go one step further on structure document composition. We are interesting in the diagram composed by multiple users, which has never been studied before. This project allow users to work together to complete a complex diagram by collaboration. We try to implement the eager interpretation to give a real-time feedback to the users. This eort will be introduced in chapter 5.

Chapter 3

Multi-touch Isolated Gesture Recognition

Introduction

Touch gesture interaction is considered as very natural in human computer interaction.

It oers a more intuitive and convenient user experience than using a mouse and/or a keyboard. As a consequence, in recent years, an increasing number of eorts have been spent on enhancing computers' capabilities to better interpreting the user's gesture commands.

Generally, touch gesture is mainly used in two contexts when performing HCI in Human Computer Interaction (HCI): manipulation and command. The former is an online mode during which a system analyzes the spatial movements of ngers on the y.

Such gestures are mainly object oriented, i.e., two ngers pinching for zoom out, circling for rotation, etc. Users may receive a real-time feedback from the system during the movement of their ngers. The latter is an oine mode and the eect is evaluated after the gesture is completed. The recognition is achieved by analyzing the writing order and global shape of the trajectories as well as sketch-based interaction, e.g. text recognition.

The system will then trigger a pre-dened command based on the recognized gesture.

Currently, multi-touch gestures are mostly used as manipulation mode such as zooming, panning, rotating, etc. Usually, a local analysis of the gesture is performed based on the motion relationships between each nger during short time intervals [START_REF] Oh | Mrf-based particle lters for multi-touch tracking and gesture likelihoods[END_REF], as illustrated in previous chapter in Fig. 2.14. On the other hand, command interaction is generally achieved with mono-touch gestures. Such systems analyze the gesture´s shape, speed, and writing direction to provide a global interpretation [MMM

+ 12] [WNvGV09]
The problem is much more complex if a multi-touch gesture is used to execute a command operation. As stated in [START_REF] Schmidt | Template based classication of multi-touch gestures[END_REF], where the term sequential multitouch is used to subsume multi-stroke and multi-touch gesture, a multi-touch gesture consists, by definition, of a variable number of nger trajectories and simultaneous touches. Spatial In this chapter, we present our eort for an online multi-touch gesture recognition system that eectively addresses the global interpretation issue. Two graph models will be introduced to extract the inner stroke spatial and temporal features. In section 3.2 we will detail our rst graph model which is based on the features of static strokes relations. We combine these stroke relation features with classic geometric features, i.e. HBF49 [START_REF] Delaye | Hbf49 feature set: A rst unied baseline for online symbol recognition[END_REF],

as a supplement to better characterize the multi-touch gesture. To test this graph model we have designed a new multi-touch gesture dataset with 18 gesture classes. Experimental results will be detailed and analyzed in section 3.2.4. Furthermore, to introduce more dynamic motion features into the graph model, we then present in section 3.3 the second graph model with motion based features. In this model we quantify the motion relations between strokes with numeric features instead of categorical features comparing to the rst approach. A more sophisticated graph matching algorithm is proposed based on this new graph model in order to calculate the dissimilarity between graphs. To reect the real challenges and complexities in multi-touch gesture domain, we update our gesture dataset and bring in more multi-touch gestures which have intricate inner stroke relations.

We name this dataset as MTGSet (Multi-Touch Gesture dataset) and make this dataset freely available 1 to constitute a baseline benchmark for the multi-touch gesture recognition community. We present the experimental results in section 3.3.4.

Graph Modeling with Allen's Relations

We introduce here our rst recognition system for multi-touch gestures. Fig. 3.1 shows the global framework of this recognition system. We will rst discuss the graph modeling approach where the strokes and their spatial and temporal relations are respectively represented by vertices and edges in the graph. We then introduce a graph embedding strategy to encode the graph into a xed size vector to feed a vector based classier. An external feature extraction method is used as a complement for the global shape representation.

1 www-intuidoc.irisa.fr/category/bases-de-donnees

Clustering (Local Shape Representation) N Classes (Default = 9)

Strokes to vertices

Relations between vertices

Allen's relations

Graph Modeling

A multi-touch gesture modeling should consider three kinds of information: spatial, temporal and shape information. The spatial information shows the relative position of each single stroke with reference to the others inside the gesture, while a temporal information illustrates the written order or synchronization between the dierent strokes and the duration of each one. The last information should retain knowledge about the intrinsic shape of the stroke, allowing to distinguish for instance between a simple straight line from a more complex curve.

In a rst step, each stroke is represented by three vertices as presented in Fig. 3.2, i.e. a begin vertex (V b ), a stroke vertex (V s ) and an end vertex (V e ). Note that the stroke is not explicitly segmented into three parts to match with the three vertices. These three vertices are used as reference points for the following stroke relation measurement. Secondly, the shape information need to be integrated into the graph. With this rst solution, to simplify the graph classication, we usea discrete codebook to encode each stroke as primitive. Here the primitive refers to the low level basic shape (e.g. line, arc, ellipse) which serves as the abstraction of a stroke. Unlike the other works [START_REF] Liang | Sketch matching on topology product graph[END_REF] [AMG07] in which strokes are decomposed into pre-dened shape primitives, we implement a clustering method for all the strokes in the training set to dene the code book. We extract the HBF49 features [START_REF] Delaye | Hbf49 feature set: A rst unied baseline for online symbol recognition[END_REF] to characterize each stroke and use the standard Euclidean distance based K-means method to achieve the clustering. Each stroke is then represented by the class of primitives. This class label is stored as an attribute on each stroke vertex V s , denoted as Σ Vs = {V c1 , . . . , V cn }, where n is the number of classes.

Since the shape information is measured on each individual stroke, this strategy is named as Local Shape Representation (LSR) in the following paragraph. Consequently, a more general denotation of the type of vertex is Σ V = {V b , V e , V c1 , . . . , V cn }, where V b and V e are specic for the extreme vertices.

Based on these vertex representation, we then measure the spatial and temporal relations between strokes. We make use of the Allen's relations [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF] which originally characterized the inferences about time by discrete labels. Fig. 3.3 shows the illustration and examples of Allen's relations. Such relations enumerate 7 relations between two events on one-dimension. Based on that, we respectively use Allen's relations on t-axis for measuring temporal relation and x,y-axis for spatial relation between two strokes, denoted as Σ R = {Σ Rx , Σ Ry , Σ Rt } = {B x , . . . , F x , B y , . . . , F y , B t , . . . , F t }. Considering a two strokes gesture as an example, Fig. 3.4 shows a general graph prototype with all potential relations that need to be measured. These relations are represented by edges as E s (x, y), E st (x, y, t) and A st (x, y, t) between two corresponding vertices in the graph. The denition of these notations is shown as follows. 1) Edge between stroke vertices (A st (x, y, t)): A st ⊆ Σ R means that the full set of Allen's relations are used to measure the relationships with respect to time, x-axis position and y-axis position between two stroke vertices V s , where the subscript st means both spatial and temporal relation need to be measured. Note that since we measure the relation from time, x-axis and y-axis, the edge A st has a set of three relations as its features.

2) Edges between extreme vertices (E s (x, y) and E st (x, y, t)): Because the extreme vertices represent each of the nger-down or nger-up positions, only Equal time, Chapter 3

x-axis or y-axis relation is measured between extreme vertices. E st (x, y, t) ⊆ {E x , E y , E t } is the edge which has a set of Equal time, x-axis or y-axis property as its features. It is used to represent the relation between begin vertices pair or end vertices pair. Unlike the edge between stroke vertices which has a xed number of three relations, relations between extreme vertices may not satisfy any of an Equal property. Therefore, edge E st can have a varied number of relations from 1 to 3. If none of an Equal property is satised, edge between corresponding extreme vertices would not be generated. The edge

E s (x, y) ⊆ {E x , E y } is simplied from E st (x, y, t).
It is used to represent the relation between a begin vertex and a end vertex. Obviously the Equal time is not satised in this case. It may also have a varied number of relations either 1 or 2, as dened for E st (x, y, t).

We note that the relations (edges) between extreme vertices service as a complementary measurement for Allen's relations. Even though some Equal relations between extreme vertices are also implied in Allen's relations between stroke vertices, we keep these redundant representation in the graph to ensure a rich structure layout. Otherwise, gestures which have a same number of strokes will always have a same graph structure.

In the following we will give two examples and their full graphs to intuitively demonstrate the graph modeling process. to the Allen's relations, the attribute Equal x (E x ), Bef ore y (B y ) and Equal t (E t ) are associated to the edge A st as shown in Fig. 3.5(e). The edge

E st = {E x , E t } between V 1 b and V 2
b indicates the two starting points are written in the same region on x-axis and in the same time. Same property will also be found between the two V e vertices. The edge Primitive set from clustering The corresponding full graph is shown in Fig. 3.6(e). Consequently, comparing to the Flick gesture above, the two graphs have dierent structure and attached attributes on edges and vertices. Therefore, our graph model retains rich structure and attribute information of multi-touch gesture and well capture the temporal relations between strokes.

E s = {E y } for {V 1 b ,V 1 e } pair
C 1 C 2 C 3 ⁞ (a) (b) (c) (d) (e)

Chapter 3

It is discriminative and informative for multi-touch gesture recognition.

Graph Embedding

A graph embedding method aims to transform the graph structure into a feature vector for the benet of using statistical classication method. In this paper, we adopt a graph embedding approach introduced by Sidere et al. [START_REF] Sidere | Vector Representation of Graphs: Application to the Classication of Symbols and Letters[END_REF]. The basic idea of this approach is to build a matrix where each row is relative to a label of vertices or edges while each column corresponds to a sub structures P j of the graph. The value of the matrix at [L i , P j ] is the number of occurrences of the label L i in each sub graph P k which is isomorphic to the sub structures P j . The construction of the vectorial representation can then be performed by transforming the matrix into vector feature space. In our case, we empirically choose three sub structures which are one vertex, two vertices with one edge and three vertices with two edges for the column of the matrix.

The row involves cluster number N (typically 9), labels of begin and end for the vertex, and the seven Allen's relations for three aspects (time, x-axis and y-axis). On the whole, 32 labels will be related to the rows. Accordingly, a graph feature vector with a length of 96 will be generated after the graph embedding.

Global Shape Representation (GSR)

The above LSR helps to integrate the stroke's shape information into the graph. It is generally believed that the global shape information of a full gesture is implied by the LSR and graph topology. For our purpose, this global shape information need to be explicitly described and used for graph classication. To combine the global shape information and graph representation, we extract the HBF49 features on a full gesture and concatenate its feature vector to the graph feature vector achieved above. Note that the HBF49 is a static feature set for charactering mono-touch gesture. It has been proved to achieve a strong result on many mono-stroke or multi-stroke datasets. However, it doesn't contain the temporal relation feature between strokes. Therefore, we make use of this feature set as a complementary description for our graph modeling and enhance the robustness of the recognition system. In the experimental section, we will compare the recognition result with and without this feature set.

Experiments

We conducted experimental evaluation of our proposed recognition system over a multitouch gesture dataset. We will rst introduce this multi-touch gesture dataset and then report the experimental results.

Dataset

There are few standard common dataset for multi-touch gesture recognition. This is because in a common sense multi-touch gestures are used for direct manipulation instead for inputing symbolic command. Therefore, we design a multi-touch gesture dataset which reects the possibility of using multi-touch gestures for indirect symbolic commands. This dataset contains a total of 1,800 multi-touch gesture samples, written by 10 persons. There are 18 dierent multi-touch gestures which are initially designed for indirect command (Fig. 3.8). These gestures are composed of points, linear segments and arcs with a varying number of strokes. Note that most of them have an apparent distinction according to their shape except two pairs, Command C-1 versus Command C-2 and Flick versus Flick-twice.

In gesture C-1, user performs rstly the 'dot' on the left side, then the 'C' shape on the right side. On the contrary, in gesture C-2 the 'dot' is done after the 'C' shape. For the second pair of gesture, the dierence is not in the sequence but in the synchronization :

the Flick gesture is performed with two ngers icking simultaneously, whereas the Flicktwice gesture is done by one nger but icking twice. These two pairs of gestures have the same shape respectively but are dierent from a temporal point of view. We introduce them in the dataset to reect the real challenge of multi-touch gesture characterize and evaluate the capability of our recognition method to discriminate gestures from temporal information.

Fig. 3.9 gives a screen shot of the data acquisition tool we used. Note that we record some basic information (Fig. 3.9(a)) of each user i.e. sex, age and handedness (The name is erased due to a law.....). Although these information are not used in our experiment, we believe that they can be useful for a future work for human behavior analyzing. Since multi-touch gesture have complex dynamic variations, dierent gestures may have a same appearance but dier from writing order. Therefore, we give an animation of each gesture to explicitly show the writing order of touches instead of using a static image (Fig. 3.9(b)).

Results

Since the graph features have been embedded in a vector features, we chose LIBSVM as the classier. The LIBSVM with a Gaussian kernel and default parameters appeared to provide adequate capability for gesture classication.

From the architecture of our gesture recognition system shown in Fig. 4 Experiment 2 (GSR): the HBF49 has been tested on dierent mono-touch gesture datasets and proven to be a powerful feature set. In this strategy, we directly use HBF49 on our multi-touch gesture dataset without graph modeling and embedding to test its competence of characterizing multi-touch gesture. In other words, this experiments takes into account only the shapes of gestures.

Experiment 3 (Graph+GSR): in this trial, we combine the above two representations. The feature vector of GSR is concatenated after the graph features from the rst experiment to achieve a conjoint feature vector.

Experiment 4 (Graph(LSR)): the fourth experiment evaluates the performance of integrating the LSR into the graph. As explained in section 3.2.1, the LSR is based on a non supervised clustering to quantify the stroke shapes, the optimal number of cluster K is set experimentally to 9. The comparison of dierent values of K will be presented below.

Experiment 5 (Graph(LSR)+GSR): nally, we combine the graph with both global and local shape information. It was achieved by concatenating the feature vector of GSR after the vector obtained in the fourth experiment. This experiment correspond to the full recognition procedure as shown in Fig. 3.1.

All the experiments adopted a 5-cross-validation (CV) scheme for testing writerindependent (WI) performance. multi-touch but fails to make a distinction between Command C-1 versus Command C-2 and Flick versus Flick-twice since they are similar in shape, respectively (Fig.

3.11(b)).

The Graph+GSR method results in 90.11% which is slightly lower than Experiment 2. However, when we integrate the shape information of each stroke inside the graph by using clustering method, the recognition rate of Graph (LSR) rises to 92.56%. In accordance to what can be expected, the nal experiment, Graph (LSR) + GSR which integrates all the information together achieves the best recognition rate, 94.50%, that is signicantly better than others. Meanwhile, by evaluating the standard deviation of 5-cross-validation, the two strategies with LSR inside produce smaller variations than the other three strategies in the writer independent situation.

The cluster number K used in the clustering process is also a factor of great concern for the recognition. The comparison results of the recognition rate under dierent values of K are illustrated in Fig. 3.12.

It shows that the same trend in the relationship between cluster number K and recognition rate can be observed from both methods. The peak appears when K is chosen to 9. Neither too large nor too small cluster number are able to well perform. The comparison also proves that the Graph (LSR) + method is always better than the Graph (LSR) method.

We have investigated a method to recognize the multi-touch gestures. Unlike many other works, we study this problem from a new perspective considering a multi-touch gesture as an indirect command. We believe that three kinds of information, spatial, temporal and shape information, of the gesture should be processed for the recognition.

We rst proposed a graph modeling method which measures the spatial and temporal relationships between strokes of the gesture. In order to integrate the shape information into the graph, a clustering method is employed to label the shape of the stroke inside the graph as a local shape feature. Another globe shape feature is extracted with our previous baseline method HBF49 features. Using global shape information extracted through HBF49 features allows to improve these results. However, in this model we characterize the inner stroke features by simply discrete and static relations. To give a more precise measurement for spatial and temporal inner stroke relations, we explore to quantify these relations and use numerical features to better describe a multi-touch gesture. A more complex graph model will be introduced in next section.

Graph Modeling with Motion Based Features

The previous graph modeling measures spatial and temporal relations mainly according to the strokes' pen-up and pen-down points. This modeling doesn't explicitly describe the relations on the middle part of the strokes. Meanwhile, the modeling uses only symbolic descriptions (Allen's relations and stroke shape labels) as features in the graph. These discrete descriptions are not precise enough to quantify the relation and shape features.

To rectify the shortcoming of the modeling, in this section we present a new graph model embedding scalar attributes which allows a more smooth representation. Furthermore, we segment each stroke into small substrokes so that the relation measurement can be allowed on every part of a stroke. Fig. 3.13 gives an overview of our second multi-touch gesture analyzing system. Firstly the nger trajectories will be broken down into substrokes to decrease the redundancy and computation complexity for graph matching. This step will be described in section 3.3.1. We then introduce the new gesture graph in section 3.3.2 to characterize the multi-touch gesture. A set of static shape features is extracted for each substroke. Furthermore, spatial and temporal relations between substrokes are identied to model their relative motion and position. All these information are integrated into the gesture graph. We then, in section 3.

Graph Classification

Graph embedding (To vector)

Train and classification

Graph matching algorithm

Figure 3.13: Overview of the graph based gesture recognition in three stages.

Preprocessing and Stroke Segmentation

An on-line handwriting signal is a sequence of points recording the coordinates (x, y), and time stamp (t) for each input event. For the study of a multi-touch gesture, the most important feature is the dynamic motion relations between its strokes such as closing, spreading, etc. Because these dynamic motion relations changes over time during the writing, it is hard to describe the motion relations between two full strokes. On the other hand, extracting motion relation based on each point-pair is not necessary since it will generate much more redundant information and will signicantly increase the computation cost. Therefore, one solution is to segment the strokes into substrokes and use substrokes as the basic elements to build the graph model. The segmentation is performed by point resampling with a pre-dened spatial step/length ∆. The term substroke is dened as the link between two consecutive re-sampled points. Instead of using a linear interpolation algorithm as in [START_REF] Wobbrock | Gestures without libraries, toolkits or training: A $1 recognizer for user interface prototypes[END_REF] we choose to keep the original points available on the trajectory, as long as they fulll the space displacement constraints. So we can preserve accurate time information, but the length of each segment may not exactly be equal to ∆. Note that we preserve at least the rst and last point, a stroke will generate at least one substroke even if a stroke is just one point. The algorithm is detailed in Algorithm 1 and depicted in 3.14.

At the end of this step, each original stroke is substitute with new re-sampled segments, which are regarded as its substrokes. We will study the spatial and temporal relation for every substroke pair in the graph model.

Gesture to Graph

Basically, a gesture symbol is represented as a set of substrokes computed by algorithm 1 described in the previous section. In this section we will extract two important information : the shape of each substroke and topology relations for each substroke pair. The information and the substroke set are represented by a graph. We characterize each substroke by four geometric features including length (l), angle (θ) and its centroid coordinates (c x , c y ).

F = (l, θ, c x , c y ) (3.1)
The angle θ is measured using the starting and ending points of the stroke and normalized between 0 and 1, i.e. θ = 1 2π tan -1 ((y 1 -y 0 )/(x 1 -x 0 )). R a (S ij , S kl ) = 1 i (k = i and l = j + 1)

(3.2)
With the example of Fig. 3.15 (c), we have: R a (S 21 , S 22 ) = 1; R a (S 31 , S 32 ) = 1; for all other pairs R a (S ij , S kl ) = 0. This relation will preserve the sequential information of the substrokes belonging to the same stroke in the model.

Relation 2 (Synchronous, R s ) . Two substrokes S ij and S kl are synchronous when they belong to dierent strokes and are written at the same time.

This relation indicates that the two substrokes are written by two ngers in a synchronous manner which is a typical property for a multi-touch gesture. Since two substrokes cannot have precisely the same starting and ending times, we compute the degree of synchronicity t s to set the R s relation:

R s (S ij , S kl ) = 1 i (t s (S ij , S kl ) > t λ ), (3.3) where t s (S ij , S kl ) = t o (S ij , S kl ) min(t(S ij ), t(S kl ))
. Based on the features dened in Fig. 3.16, a motion feature vector can be computed as follows:

M (S ij , S kl ) =    m t m s m r    =    dx 2 + dy 2 d e -d s θ/2π    (3.5)
This feature vector will be weighted with the degree of synchronicity t s so that the attribute w s of a synchronous relation is valuated by

w s (R s ) = w s (S ij , S kl ) = t s (S ij , S kl ) • M (S ij , S kl ) (3.6)
Relation 3 (Consecutive, R c ) . Strokes S i and S k are written in sequence when there is no synchronous relation between any of their substrokes S ij and S kl . This relation captures sequential dependencies between two strokes. Since we model the relations at the substroke level, this relation is built only from the last substroke of the rst stroke to the rst substroke of the successive one. To measure the time elapse between two substrokes, an attribute w c is computed relating to the time delay t d between the two substrokes

w c (R c ) = w c (S ij , S kl ) = t d /T (3.7)
This feature is normalized by the duration of the gesture T so that it is scaled to [0,1]. Considering Fig. 3.15, the following substrokes are connected with a R c relation-ships: (S 11 , S 21 ); (S 11 , S 31 ).

Consequently, the full substroke relations of the example Fig. 3.15 are shown in 3.17 (a). The corresponding adjacency matrix is given in Fig. 3 The corresponding adjacency matrix.

Chapter 3

Graph denition

Based on the geometry feature and topology relation we introduced above, we propose a Multi-Touch-Stroke Graph (MTSG) representation to integrate all the information as follow,

Denition 1 (Multi-touch-stroke graph). A MTSG is a four-element tuple G = (V, E, µ, ω).

(1) vertex V : each substroke is represented by a vertex v.

(

) edge E ⊆ V × V : each edge E(v i , v j ) connects a pair of vertices (v i , v j ) that has a certain substroke relation R a , R s , R c . 2
(3) attribute function µ on vertex: the attribute of a vertex is the geometry feature of the substroke µ(v i ) = F (v i ).

(4) attribute function w on edge: according to the type of relationship that denes the edge we associate the following attribute:

w a (v i , v j ) = 1, when R = R a w s (v i , v j ) = t s • M s , when E(v i , v j ) = R s w c (v i , v j ) = t d /T , when E(v i , v j ) =

Graph matching and classication

The work presented gives a full graph representation for multi-touch gesture. Due to the fact that gesture may contain dierent number of strokes, it is dicult to extract a xed length global feature set for classication. Therefore we propose to measure the similarity between two graphs to achieve the graph classication. A traditional way is to calculate the graph edit distance for the dierence between two graph. Generally, the problem of searching the optimal graph matching and the corresponding edit operations is known to be NP-hard. But since we preserve the vertices adjacent relations, the vertices which connected with adjacent edge can be treated as a subgraph. Therefore, instead of performing a global matching algorithm between the two entire graphs such as in [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF] [RNB07], we rstly nd the optimal subgraph matching between two gesture graphs and then extend the optimization at the global level. Note that the subgraph matching is achieved only according to vertex matching, the edge matching is then implied by the alignment of the vertices.

Subgraph matching for stroke comparison

As we denoted in section 3.3.2.2, the adjacent relation/edge indicates that the two connected vertices belong to a same original stroke. These vertices can be regarded as a subgraph vertices set. Given two subgraphs V s = (v 1 , . . . , v n ) and U s = (u 1 , . . . , u m ). We use DTW algorithm to compute the minimal matching cost of the vertices, the minimal matching cost is dened as We may easily deduce the vertex matching from the Viterbi path Φ. For two subgraphs which contain dierent number of vertices, three standard edit operations are considered in order to compute the edit cost. We denote the substitution of two elements u and v by (u → v), the deletion of element u by (u → ε) and the insertion of element v by (ε → v).

c(V s , U s ) = D Φ [d](V s , U s ) = 1 N N n=1 d(v φv(n) , u φu(n) ) (3
Note that in the Viterbi path Φ a vertex can be aligned to multiple vertices under the DTW procedure. In this case, we keep the closest two vertices as matching pair and leave the remaining of multiple matched vertices as delete/insert vertices. Thus, we denote the vertex matching of two subgraphs as Φ * with

φ * =      (φ * v → φ * u ) for V * c × U * c (φ * v → ε) for V c \V * c (ε → φ * u ) for U c \U * c (3.11)
where (φ * v → φ * u ) is the set of matching pair deduced from Φ. In this set, each vertex in V * c is uniquely matched to a vertex in U * c , vice versa. The remained non-matched vertices in V c and U c will be regarded as deletion (φ * v → ε) and insertion (ε → φ * u ) vertices, respectively.

We then deduce the optimal subgraph assignment by computing a matrix containing all pairwise subgraph matching. Given two graphs V = {V 1 s , . . . , V n s } and U = {U 1 s , . . . , U m s }.

A cost matrix C is dened as

C =    c 1,1 • • • c 1,m . . . . . . . . . c n,1 • • • c n,m    (3.12)
where c i,j denotes the assignment cost of a subgraph-to-subgraph matching c(V i s , U j s ). The subgraph assignment problem can be reformulated as nding a permutation p = p 1 , . . . , p n that minimizes the cost n i=1 c i,p i . This is a Linear Sum Assignment Problem that can be eciently solved by Munkres' algorithm [START_REF] Munkres | Algorithms for the Assignment and Transportation Problems[END_REF] in polynomial time. We refer the readers to [RNB07] [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF] for more details about this algorithm. In this approach, it rst nds the subgraph matching permutation that minimize the total cost. Then the remained non-matched subgraphs will be labeled as deletion

(φ * v → ε) or insertion (ε → φ * u
). An example of the full vertices matching process is shown in Fig. 3.20

Consequently, the global subgraph-to-subgraph matching is obtained by solving the cost matrix C. We can easily deduce the global vertex matching, denoted as Φ * all , from the optimal subgraph-to-subgraph matching. Note that all vertices in a deletion or insertion subgraph are labeled as deletion or insertion vertices, respectively. In another words, the Φ * all indicates the edit operation of all the vertices from graphs G 1 to G 2 . The cost of vertex edit operation is composed of the cost of substitution, deletion and insertion denoted as

C v (G 1 , G 2 ) = N 1 n=1 d(v φ * v (n) , u φ * u (n) ) + N 2 n=1 c(v φ * v (n) , ε) + N 3 n=1 c(ε, u φ * u (n) ), φ * ∈ Φ * all ( 3
R s v 1 v 1 v 1 v 2 v 2 u 1 u 1 u 1 u 2 u 2 (b) (c) DTW distance: , , Matching Solver (Munkres' Algorithem)
X X X Optimal matching

Φ * → , → Φ * → , → Φ * → , → Φ *

Graph classication

Based on the graph edit distance, our work explore three strategies for graph classication.

Strategy 1: So far, we have obtained three terms of edit operation cost, one vertex operation cost C v and two edge operations C s , C c . Traditionally, the graph edit distance is dened as the summation of all the costs of edit operations [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF] as

d(G 1 , G 2 ) = (C v + C s + C c ). (3.14)
In such a case, the simplest way for clustering the graph is using a distance based classier such as K-nearest-neighbor.

Strategy 2: A better option regarding graph classication is to use the graph embedding algorithm. We refer to the graph embedding method presented by Kapsar and Horst [START_REF] Riesen | Graph Classication and Clustering Based on Vector Space Embedding[END_REF]. The key idea of this approach is to use the distances of an input graph to a number of prototype graphs as a vectorial description of the graph. The denition is detailed as follow:

Denition 2. Graph Embedding. Let us assume G is an input graph, P = p 1 , . . . , p n is a prototype set with n graphs, the mapping ϕ P n : G → R n is dened as the function

ϕ P n (G) = (d(G, p 1 ), . . . , d(G, p n )), (3.15)
where d(G, p i ) is any graph dissimilarity measure between graph G and i-th prototype graph.

It means that each axis of the vector space ϕ P n (G) is associated with a prototype graph p i and the coordinate values of an embedded graph G are the distances of G to the prototypes. In this way we can represent any graph as a vector of real numbers with the help of prototype graphs. Hence, the vector ϕ P n (G) can be regarded as the feature vector of graph G. Note that prototypes are normally selected from the training graph set under a certain criteria. The selection of the n prototypes is also a critical issue since not only the prototypes but also their number n aect the graph mapping ϕ P n . The prototype selection method is k-means clustering for each class. We refer the readers to [START_REF] Riesen | Graph Classication and Clustering Based on Vector Space Embedding[END_REF] for more details about the graph embedding and prototype selection.

The problem now is reformulated as nding a pattern recognition way using the vectorial description of distances. We use SVM as the classier in the experiment part.

Strategy 3: As Strategy 2 introduces a way to extract a feature vector for an input graph, a more precise feature set, obtained by assumption that the edit operation costs are independent (in contrast to the summation for the graph edit distance), is investigated. Similar to Strategy 2, the feature set is computed by graph embedding. However, the distance between two graphs is dened as a three dimensions feature vector: But the new feature vector after the graph embedding will be in a length as three times of the number of the prototypes, which would signicantly increase the classication complexity. We will compare these three strategies in the experiment part.

d(G 1 , G 2 ) = (C v , C s , C c ).

Experiments

We conducted experimental evaluation to verify the capability of our graph method. We rstly introduce our new multi-touch gesture dataset and three common used datasets.

The results are then presented and compared with other result reported in the literature.

Dataset

As dened in [START_REF] Schmidt | Template based classication of multi-touch gestures[END_REF], most common used datasets contain mono-stroke or multi-stroke symbols. To the best of our knowledge, there are few benchmark datasets for multitouch and sequential multi-touch gesture recognition. To reect the real challenges and complexity in multi-touch gesture recognition, we design more comprehensive multi-touch gesture and update our previous dataset. The new dataset is named as MTGSetB which contains more multi-stroke, multi-touch and sequential multi-touch classes. This section will give a rst result baseline to address this new challenge.

Figure 3.22: The multi-touch gesture templates in MTGSet.

Chapter 3

The dataset consists of 31 classes, with 27 multi-touch gestures and 4 multi-stroke mono-touch gesture. Fig. 3.22 shows the pictograms we provide to the participants.

A stroke indicates a nger movement and a dot means a nger holding on the screen.

The textural description under each gesture illustrates how a gesture is performed. For instance, 2F*1F denotes a gesture is performed by two ngers in one hand and one nger in other hand. nF (n > 1) indicates the number of nger involved while the asterisk (*) species the synchronous movement of the two hands. Meanwhile, if a gesture contains sequential stroke, a plus (+) is used to describe the order of the strokes. Note that the last column in Fig. 3.22 consists of 4 sequential mono-touch gestures. Each two of them have the same shape but with dierent written order (either from left to right or right to left).

These gestures are also performed in a synchronous manner as multi-touch gesture in our dataset. We introduce these gestures to verify that our graph modeling and matching method are able to distinguish the gestures which have the same shape but dierent writing sequence. We invited 33 participants using a 27 inch touch screen for the data acquisition. In addition of these pictograms, participants are also provided with a short animation of each gesture for understanding the written order and direction (We use the same tool in Fig. 3.9). Each participant is asked to perform gestures from the rst one to the last one and repeat for 6 times instead of repeating a same gesture 6 times. 6138 gestures are collected after discarding some mistaken gestures. The dataset is partitioned that 2790 gestures from 15 users are used for training, the remaining 3348 gestures from 18 users for testing. Meanwhile, we also test our method on three common used online symbol datasets, LaViola, ILG and NicIcon. Note that these three datasets contain only mono-touch gestures which are not the cases we focus on. We make use of these datasets for the reason of evaluating the capability of our graph method on mono-touch symbols and comparing to other benchmark gesture classication methods.

The LaViola dataset [START_REF] Laviola | A practical approach for writer-dependent symbol recognition using a writer-independent symbol recognizer[END_REF] contains 11,160 digits, characters and symbols acquired from 11 users. This dataset has a high number of classes (48). Mono-stroke symbols constitute the majority of samples while only a few classes contain two or three strokes samples. The data is clean and style-consistent. Results on this dataset have been re-

ported in [DA13] [SKC08]

The ILG dataset [START_REF] Renau-Ferrer | The ILGDB database of realistic pen-based gestural commands[END_REF] is a collection of mono-stroke pen-based gesture. 38 users were asked to perform gestures for triggering 21 dierent commands in a simulated image edition software. The dataset is partitioned to 3 groups. Note that the rst two groups contain user-dened gestures (user is allowed to design own gesture to trigger command, see the details in [START_REF] Renau-Ferrer | The ILGDB database of realistic pen-based gestural commands[END_REF]). Obviously, this two groups can only be used for writer-dependent experiments since it only oers few training samples for each class.

To obtain a more general result, we select the third group (1926 samples) which has more classical properties: users all performed the same 21 gestures.

The last NicIcon dataset [START_REF] Niels | The nicicon database of handwritten icons[END_REF] contains 26,163 pen-based symbols from 34 writers. Users were asked to draw the sketch of 14 special icons that are important in the domain of crisis management and incident response system. This dataset is more challenging because the samples are quite noisy and varying number and order of strokes.

Comparative results

The rst experiment aims to evaluate the meta parameter and the three types of classication for our approach. Since our approach mainly targets on the multi-touch gesture problem, this experiment is only conducted on the MTGSet. For Strategy 1, we choose the 1-nearest-neighbor algorithm for classication. Obviously, it is costly to search the entire training set to nd the nearest neighbor. We implement the same prototype selection algorithm in Strategy 2 and Strategy 3, and compare their accuracy rate under dierent number of prototypes. Table 3.1 shows the accuracy rate according to dierent number of prototypes. We note that there are few recognition systems which globally analyze and recognize the multi-touch gestures as symbolic gestures. We can hardly compare our method to other's work. Therefore, we make use of our previous work HBF49 [START_REF] Delaye | Hbf49 feature set: A rst unied baseline for online symbol recognition[END_REF] as the benchmark result for the symbol recognition task. We implement both method on all four datasets to compare the accuracy rate. In this experiment we choose the Strategy 3 with 20 prototypes per class since it achieves the best results in the previous experiment. Table 3.2 shows the results. By comparing these datasets, it can be seen that the HBF49 feature set performs better on the three mono-touch gesture sets. The reasons are that these three datasets do not need the synchronization relation between strokes and the features for a single stroke in our approach are far simpler than in the HBF49. Therefore, our approach is less powerful on the shape analysis aspect comparing to the HBF49. But the results of our approach are still competitive. On la viola and ILG sets, it shows close results compared with the HBF49. On the other hand, on MTGSet our graph modeling and matching method (98.97%) signicantly outperforms the HBF49 (91.36%). This is mainly because the MTGSet contains gestures which are similar in shape but have dierent inner strokes temporal relations.

The comparison between HBF49 features and our graph modeling proves that our method has the ability to capture the synchronous and asynchronous writing relations between strokes. It is therefore dedicated to the multi-touch gesture recognition problem.

That is why we oer a freely available multi-touch gesture database as a rst baseline to multi-touch gesture recognition problems.

Conclusion

In this chapter, we report two graph models with two recognition systems for multi-touch gesture recognition problem. Comparing to the existent symbol recognition method, our graph models focus more on the feature extraction for inner stroke relations including spatial and temporal relations. In other words, our methods analyze the multi-touch gestures not only from their shape but also from their writing order and synchronism. As the rst trial, the rst system helped us to verify the eectiveness of graph modeling and graph embedding for feature extraction and gesture recognition. To better characterize the motion relations for multi-touch gestures, we then propose the second system based on quantied motion features. With the graph embedding and SVM classication methods, our system is proved to be able to distinguish the multi-touch gesture from global interpretation. Meanwhile, we make eort to create a challenge and comprehensive multitouch gesture dataset (MTGSet). We have made it available online and hope it could be used as a benchmark dataset in community for further multi-touch gesture studies.

Chapter 4 Reject Option Based Early Recognition Algorithm 4.1 Introduction

In the previous section, we propose to use multi-touch gestures as indirect commands and introduce a classication method to recognize the gestures after their completion.

However, in a common sense multi-touch gestures have widely been used for direct manipulation. One problem is that whether both of the two interactions can coexist in a same application, i.e. users can use multi-touch gestures for both interface/virtual element manipulation and executing commands. An example can be found in [START_REF] Petit | Unifying gestures and direct manipulation in touchscreen interfaces[END_REF],

authors use mono-touch gesture to achieve scrolling, rotation as manipulation and text input as command. A conict is that these two interactions oer completely dierent feedback to the users. The direct manipulation need to give an instant feedback along with the nger's trajectory, whereas the indirect command need to wait until the end of a gesture. Obviously it is not possible to distinguish the user's intention at the very beginning of a gesture. In Fig. 4.1 we illustrate this conict with an example in [START_REF] Petit | Unifying gestures and direct manipulation in touchscreen interfaces[END_REF].

Therefore, the problem becomes to whether we can correctly recognize a gesture by a short beginning part so that we can quickly nd the user's intention and choose a correct feedback. How much information we need to recognize a gesture from a gesture set and how fast we can achieve. With these questions, we explore the Early Recognition (ER) strategy for multi-touch gestures.

Fig. 4.2 illustrates the general diculties of ER. Since these three gestures have a common beginning part, there is no evidence to distinguish the gestures before λ 1 . The ER is actually a tradeo between `earliness' and `accuracy', the more time/trajectory it waits for, the more distinctive information it would have for decision. An ideal ER system should be able to learn the common part and avoid making a decision before λ 1 .

Meanwhile, it should also be able to distinguish the gesture A from B and C soon after From the state-of-the-art, the ER works have been mostly developed for motion pre-

diction problems [MUK + 06] [KSNT11]
. A basic idea is to employ a partial matching method, where the recognition result of an input pattern is determined by the matching distance of its beginning part from reference patterns. The Dynamic Time Warping (DTW) algorithm is a widely used method to search for an optimal partial alignment.

Another approach is combination of classiers {h 1 ,...,h t ,.

..,h T }[ISS10][UA08]

, where h t is a weak frame classier at t th frame (i.e., time t). The recognition result at the t th frame will be determined by combining t recognition results provided by {h 1 , ..., h t }. This method assumes the input pattern having the same performing speed as the reference pattern.

The time frame based ER works have a pre-dened context that every gesture is written in a same velocity. In our opinion, the gesture trajectory on each time frame is just an external representation, the substantive information is the motion's variation, i.e.

the length of the trajectory. For instance, a gesture which moves very slowly contains less information frame by frame. Therefore, We propose that the early recognition should be investigated based on length of the motion's trajectory rather than the time frame. Note that this strategy excludes the factor of writing velocity variation, but meanwhile it loses the capacity to distinguish two gestures which have same shape but only dier in writing velocity.

We study in this work early recognition for handwritten touch gestures. Unlike the previous works that investigate the early recognition based on time frame, we believe that the time frame does not represent the motion information, e.g. a gesture which moves very slowly contains less information frame by frame. We propose that the early recognition should be investigated based on dierence of the motion rather than dierence of the time.

For the practice of ER system in a real application, another diculty is the gesture size normalization. In training process, usually a classication system need to normalize each gesture to a xed size bounding box before feature extraction so that the value of features can be unied to a xed scale. However, in a gesture size free context, it is dicult to normalize the early part of a gesture without knowing the size of the full gesture. In this work, we propose to build an early recognition system being able to deal with Chapter 4 ambiguous common parts under free drawing context for handwriting gesture recognition.

We control the progress of the gesture using its length instead of time duration. A reject option is proposed to postpone the decision until enough condence is achieved.

The rest of the paper is organized as follows. Section 4.2 presents the structure of the multi-classier method and the reject option strategy. Next in section 4.3, we report the experimental result to show the earliness and accuracy of the system. Experiments are conducted on two freely available dataset ILG [START_REF] Renau-Ferrer | The ILGDB database of realistic pen-based gestural commands[END_REF] and MGSet [START_REF] Chen | Recognize multi-touch gestures by graph modeling and matching[END_REF] 1 .

The ILG dataset contains common mono-touch gestures which are assumed for abstract command while the MGSet contains special multi-touch gestures which can be both used for abstract command and direct manipulation. Finally, we conclude this work and discuss the perspectives in section 4.4.

Multi-classier Early Recognition

To deal with the size normalization problem for ER in a size free context, we propose a multi-classier recognition system as shown in Fig. 4.4. Each classier is trained by a xed length of partial gesture so that dierent classier is responsible to recognize dierent length of coming incomplete gesture. However, as we explain in the previous section, a trajectory with a length l could be a small part of a large gesture or a large part of small gesture. In other words, a coming incomplete gesture (i.e. an incomplete trajectory) can not be explicitly sent to a certain classier according to its length because we can not estimate the size of its potential full gesture. Therefore, the incomplete trajectory will be recognized by all classiers. The recognition result is determined by a fusion of the results from all classiers. Details will be described in section 4.2.1. To deal with the ambiguous beginning parts shown in Fig. 4.2, the result is ltered by a reject option, i.e. a result with low condence value will be rejected so that system will wait for enough information to make a decision. The rejection algorithm and fusion of classiers will be proposed in section 4.2.2. From all the training gestures, we build N segment sets S i , with i = 1, ..., N , where each S i set represents all the segments of Seg i whose length is equal or less than il ∆ . Fig. 4.5(b) shows the training procedure of each classier and its corresponding segment set.

Segment Classier

Note that although the normalization step normalize the size of each gesture into a xed bounding box, the trajectory length of dierent gestures are still dierent. Consequently, a long trajectory can generate more segments to feed the segment sets while a short one may generate only one segment. Therefore, the number of training segments in dierent set S i may be dierent. S 1 will always cover the beginning part of all the training gestures, while S N only contains the gestures which are longer than (N -1)l ∆ . We denote the segment classiers as {h 1 ,...,h i ,...,h N }, each classier h i is trained by the feature vectors of the ith segment set S i .

In the recognition step, as we explained in Fig. 4.3 an arbitrary input gesture x at length l ((i -1)l I < l < il I ) can not be specically recognized by classier h i because of the size free context. Therefore, an arbitrary gesture x should be processed by all the classiers and determined by the one giving the highest probability value. Let h j (x, c i ) be the probability of the best class c i obtained by the classier h j , the result of multi-classier is

H(x, c i ) = max j=1,...,N h j (x, c i ) (4.1)

Rejection Algorithm

Referring to the work in [START_REF] Zhu | Rejection optimization based on threshold mapping for oine handwritten chinese character recognition[END_REF] [MA06], our reject option is designed from two aspects: ambiguity and outlier.

ψ Amb i = s i -s j s i , (4.2)
where i = C 1 , j = C 2 . And we have the rejection decision as:

r Amb = ψ Amb i < T Amb i . (4.3)
T Amb i is the class dependent threshold that the result will be rejected if ψ Amb i < T Amb i .

Outlier rejection

Since each classier is trained by a set of segments of a certain length, a classier should be able to reject a gesture which is not similar to any of the training data. It ensures that in the multi-classier structure, only the relative classier will give response to an input gesture while others would make rejection.

Shown in

ψ Out i = e - (d i -µ i ) 2 2σ 2 i (4.6)
where µ i and σ i are the mean distance and deviation for each class i learned from the validation set.

r Out = ψ Out i < T Out i (4.7)
where s i is the output score of the best class. T O i ut is the class dependent threshold that the result will be rejected if ψ Out i < T Out i .

Threshold optimization

We rstly dene some notations to better explain the result of the reject option. Considering a set of N training samples, Table 4.1 shows the notations to represent the number of samples in dierent condition after recognition and reject option.

N = N A + N R = N cor + N err = N T A + N F A + N F R + N T R Sample set (N) Reject option Accept (N A ) Reject(N R ) Correctly classied (N cor ) True Accept (N T A ) False Reject (N F R ) Mis-classied (N err ) False Accept (N F A ) True Reject (N T R )
To evaluate the threshold, we compute the False Accept Rate (FAR), and False Reject Rate (FRR) as:

F AR = N F A N (4.8) F RR = N F R N (4.9)
For ambiguity rejection, N F R are the training samples which are correctly classied but wrongly rejected by reject option while the N F A are wrongly classied but accepted. Note that it is better to prepare a validation dataset since the high precision in training data makes N F A close to 0, which leads to unavailable optimization. For outlier rejection, since each classier is trained with a set of segments in certain length, the positive samples are the classier's training set while the negative samples are the training sets for other classiers. The acceptance of negative samples will be count for N F A and the rejection of positive samples will be N F R .

In rejection, the aim is to obtain the lowest error rate while rejecting least correct results. Intuitively, the optimization of the threshold is to nd a trade-o between the F AR and F RR. Therefore, the optimal threshold for class i is dened as:

T opt i = arg min T i α e F AR 2 i (T i ) + α r F RR 2 i (T i ) (4.10)
where the weights α e and α r are used to balance the impact of each rate. In general case, these parameters are set to 1. Since we use the class-wise threshold, we measure the F AR i and F RR i based on each class i to learn the threshold. The two thresholds are learned independently.

Finally, the rejection of an input gesture is made if it is rejected by either reject option. r = max(r Amb , r Out )

(4.11)
If the input gesture is accepted, the probability h j (x, c i ) of the class i, as shown in (4.1), is the conjunction of both reliability function:

h j (x, c i ) = ψ Amb i * ψ Out i (4.12)
With the reject option, the equation (4.1) will be changed to

H(x, c i ) =        Reject, if j r j,i (x) = 1 max j (r j,i (x) * h j (x, c i )) , otherwise (4.13)

Experimental Result

The evaluation experiment has been conducted on the MTGSetB and ILG datasets as referred in section 3.3.4.1. Note that for both datasets, we partition 20% of the data from the training set as a validation set to learn the ambiguity threshold.

The number of classiers in our experiment is set to 3. Before training, each gestures is normalized into a 500x500 pixels bounding box and segmented to 3 partial gestures with length 250, 500, 750 pixels to feed for the 3 classiers, respectively. The classier we used for each h i is Graph + LibSVM as described in 3.3. The condence scores for ambiguity threshold learning are the probabilities from LibSVM. For outlier threshold, we use clustering algorithm to nd three centers for each class, and compute the distances of a input gesture to the centers. The minimum distance is used as s i in (4.4) to learn the outlier threshold. These can be replaced by any classiers which give output condence score for each class.

For the early recognition, each input gesture is recognized on every 50 pixels of its incremental length. We rstly evaluate the early recognition with regarding to the dierent length of input gestures. Referring to the notations in table 4.1, we measure the False Accept Rate (F AR = N F A /N ) and Reject Rate (RR = N R /N ) when using the reject option and compare them with the traditional Error Rate (ER = N err /N ) without reject strategy. The results are shown in Fig. 4.7.

Both results show that without the rejection algorithm, the ER is very high at the beginning since gestures are still ambiguous to take a distinction. Accordingly, the rejection algorithm is eective to reject most of the gestures at beginning. The RR decreases along with the decreasing of ER (without reject) which means that it well rejects the ambiguous gestures but accept the gesture as soon as it has enough distinctive information. This strategy leads to a good performance of FAR which is very low at the beginning and always lower than ER at any input length. Meanwhile, the RR is always higher than ER in the ending part, which means that some correctly classied gestures are rejected. This is the negative eect of the reject option; a low error rate is obtained at the cost of a high reject rate.

In operational use case, a reasonable strategy to prevent noisy decisions consists in ltering the decision by considering several consecutive outputs of the classier. Consequently, a decision is nally accepted when the classier gives n consecutive times the Chapter 4 paring to the third result with no reject option, where the decision is also achieved around 33.98% length by 3 consecutive same results, the FAR is less than half of the ER. With the increasing of the time for consistence checking, the decision is postponed to obtain less errors. The FAR decreases from 14.56% to 3.41% while the RR increases from 3.54% to 19.17%. It indicates that we have to nd a trade-o between the error rate and the reject rate. The result by n = 2 may be considered as an acceptable one where the FAR is 10.85% and RR is 5.71%. The comparable result from no reject option is shown at n = 4 where the CR is 79.59% (3.85% lower than TAR:83.44%) and ER is 20.41% (9.56% higher than FAR:10.85%). In other words, the reject options minimize the error rate by oering reject Although there are 5.71% samples are rejected during the recognition, we believe that in a real practice it is better to reject an input and provide some ambiguous options to select than giving a wrong result. By this way, user only need to make a selection instead of removing the wrong input and re-draw it again.

However, the result on ILG shows not as good as MGSet. The accuracy rate is only 30.65% for the rst decision. From the Fig. 4.7(b), the FAR is around 20% to 30% from 50 to 200 points. Decisions made on this stage cause much more errors than MGSet.

Therefore, the rst time decision may not be acceptable in this situation. The accuracy rate on ILG dataset shows a great improvement using consistence checking. With n = 2, the TAR is 33.5% higher than n = 1 while the FAR decreases 52.73% comparing to n = 1. A higher time of consistence checking seems not useful since the corresponding Avg. length is over 90%.

Conclusion

In this chapter, we focus on the diculties of involving both direct manipulation and indirect command gesture in a same context. To resolve the conict of these two interactions, we propose a reject option based multi-classier system for handwritten gesture early recognition. The principle is to recognize gestures as soon as possible from their beginning part but also avoid the recognition if gestures contain similar beginning parts.

We propose a multi-classier structure that dierent classiers are responsible to recognize dierent part of partial gestures. Since our system is considered to be used in a large screen and gesture size free context, taking into account the gesture size normalization inconsistence between training and testing, the early recognition result is determined by the fusion of all classiers. The reject option for each classier is designed to deal with the ambiguous early parts between gestures. The experiment gives a promising result on MTGSet. The system achieve 83.44% accuracy rate with 46.82% earliness of input gestures. Comparing to the no reject option system, the error rate is very low at the beginning part which proves that our reject algorithm works well to reject the ambiguous gestures.

Our future work will focus on investigating the automatic selection of the optimal number of classiers and segment length for training instead of using empirical selection as in our experiment. Meanwhile, we will develop a application to mix the usage of direct manipulation and command shortcut for multi-touch gestures and better analyze the usability of early recognition for handwritten gestures. In the next section we develop a structure document composition context as a rst prototype which involves multi-touch gestures for complex commands.

Chapter 5 Structured Document Composition in Multi-user Context

Introduction

A large multi-touch display allows multiple users to simultaneously interact in the same context and work together. Indeed, many researches and commercial products propose tangible interfaces which support simultaneous participation of multiple users. However, most of these interfaces only allow users to interact with virtual elements which need only simple direct manipulation. To the best of our knowledge, there are no research focusing on the freely-drawn sketch or indirect commands for multiple users.

In this chapter we study the diculties of multi-user freely-drawn sketch context. This work is supported by Excense company who dedicates to design a handwriting diagram context that make people propose and exchange their idea between each other. We choose the use case of sketch drawing to illustrate the complexity of multiple users composing a structured document. Indeed sketches as mind map or owchart need lot of dierent gestures to draw a various type of symbols as nodes and arrows. Fig. 5.1 shows a prototype of the multi-user interface, it allows two users to simultaneously input symbolic elements in a mind map context. Generally, an ideal mind map diagram composition interface should consists roughly of the following features [START_REF] Blostein | General diagram-recognition methodologies[END_REF]: 1) Stroke segmentation/grouping, to isolated symbols.

2) Symbol recognition.

3) Identication of spatial and logical relations among symbols. Our current study focuses on the rst two features. The rests stand as future perspective. In a multi-user context, it becomes more dicult to make a clear stroke segmen-79 Chapter 5 tation/grouping since there are no clear spatial or temporal boundaries between isolated symbols from the stroke stream. Meanwhile, to provide a freely-drawn context, users are allowed to input a symbol by multi-touch gestures. Therefore, the challenges of our study can be described as: how to recognize the multi-stroke and multi-touch gestures in a multi-user composition context. In section 5.2, we introduce the dataset we acquired to support our study. We will describe the data acquisition procedure and discuss the multi-user features compared to a traditional diagram dataset. In section 5.3, we present our rst strategy for stroke grouping and gesture recognition method based on eager interpretation. The experimental results are given in section 5.4. Finally the last section concludes with the perspectives to improve the results and go further in the process.

Multi-user diagram database

Since there are few works on multi-user handwritten analyzing, it is essential to begin with a representative multi-user handwritten document dataset. In order to be closely engaged with a practical application, we propose to use mind map diagram as the multiuser scenario. In this section we present the data acquisition procedure and the multi-user features of the dataset. This dataset is achieved with the help of Excense company.

Diagram acquisition

A mind map is a diagram used to visually organize information. It is often created around a single concept to which associated representation of ideas such as words, images, symbols are added. The ideas are usually connected by lines, arrows or grouped by shapes, boundaries. An example of a mind map diagram is shown in Fig. 5.2 (a). As a rst step towards a more complex dataset, we focus more on the graphical symbols and their links rather than the text. We oer the users a white board scenario with all descriptive texts on it. Each time we ask two users (standing side by side) to draw the correct graphical symbols around the texts and connect them using lines, double-lines or arrows using either ngers or styluses. An example of the collected handwritten diagram is shown in Fig. 5.2 (b). We designed two layouts of this mind map for more diversity in the data acquisition.

A total of 21 people partitioned half to half into two groups participated. Each pair of participants was asked to switch their position after completing a map and drew again.

As each couple draw also the two layouts, it means that each couple of users generate 4 diagram samples. Consequently, 42 handwritten diagrams have been collected. 10 participants of group 1 were asked to draw the symbols on a 27" touch screen by ngers.

To record the way people naturally draw, participants were given all the freedom to draw the symbols in any way or order they prefer. Since users in this group draw symbols by ngers, some participants tend to use multi-touch manner to draw the multi-stroke symbols such as `bracket' and `double line'. Users from group 2 made the acquisition on a 80" touch screen by stylus. In this case they have more free space to draw the symbols and may simultaneously draw dierent symbols very close to each other. Since all the symbols are drawn by stylus, the multi-touch case does not exist in this group. Fig. 5.1 shows the data acquisition scenario from group 2. The stroke grouping and groundtruth labeling tasks were achieved manually after data acquisition with a dedicated application.

Diversity of the content

The predened symbols can be classied into 9 categories shown in Fig. 5.3. In observing the collected data, users may draw a same symbol with dierent number of strokes.

Examples of rectangle symbols are displayed in Fig. 5.4. Note that one of the examples shows a very special broken straight stroke case. The User intends to draw a straight stroke, but his nger accidentally lifted up because of the unstable friction on the screen. This situation causes some symbols containing an unusual large number of strokes.

As we introduced in the previous section, some `bracket' and `double line' symbols may be drawn by multi-touch manner, which means the two strokes of the symbol are drawn simultaneously. Some `arrow' symbols are written by one stroke, while some others are rstly written as a `line' and waited after a long time delay the head added. If the head of an `arrow' is drawn within the same stroke or immediately added just after the straight line stroke, we group the strokes and label them as `arrow'. If the head is added after a signicant long time delay, during which the body of arrow is supposed to be processed as the `line', we would make an independent `direction' class for the head. The heads of double ways arrows are also labeled as `direction'. Table 5.1 shows the distribution of the symbols in the dataset with also the average and max number of strokes used to draw The most important feature of this dataset is the mixture of multi-touch and multistroke symbols by multiple users in the same time. A key problem is how to correctly group the strokes under this complicated context. The Fig. 5.5 (a) shows an example where a 'rectangle' and an 'arrow' symbol are drawn simultaneously. The diagram in the right describes the temporal activity of their strokes. Obviously, the alternately emerging of the strokes from two users makes it more dicult to group the strokes. Meanwhile, since the symbol is allowed to be written in multi-touch manner, the synchronized strokes (as shown in Fig. 5.5 (b)) can hardly be determined whether they belong to one user or two. Approximately 65% strokes are simultaneously written in this dataset.

Eager interpretation based recognition system

From the practice point of view, a multi-user document composition system aims at providing a real-time feedback context so that users can easily exchange their ideas. We exploit eager interpretation, which updates the analyzed document after each input stroke and providing an instant corresponding feedback as illustrated in section 2.4. Ideally, a recognition result should be given on the screen in a short delay after the completion of each symbol. However, since the dataset contains multi-stroke gestures, the ending of a stroke is not exact the ending of a gesture. Therefore, the system need to adopt early recognition strategy to detect if input strokes can form a meaningful shape or need to wait for more strokes. On the other hand, the most important feature of this dataset is the mixture of multi-touch and multi-stroke symbols by multiple users in the same time. The alternately emerging of the strokes in the stroke stream from two users is so complex that two strokes concatenated in time domain may not even belong to a same user. Moreover, the existence of multi-touch gesture makes it more dicult that two synchronized strokes can belong to either a multi-touch gesture or two gestures from two users. Therefore, instead of designing an explicit stroke grouping method, we use brute force grouping technique as a rst attempt to recognize all combinations of strokes and let the classier take the decision of selection the correct gesture thanks to a dedicated training. Although the computation cost would become very high when the number of candidate strokes is large, due to the fact that the eager interpretation system gives feedback in a short delay, the number of strokes in a short time window will not be so large for brute force computation.

Fig. 5.6 shows the global framework of our proposed eager interpretation system.

After each end of a stroke, this stroke will be rstly stored in a stroke list. Then system will generate all combination of strokes if there exists multiple strokes in the list. A classier is then used for each stroke combination to detect if any of them can form a concrete symbol. If not, strokes will keep in the stroke list and wait for more strokes from users.

Figure 5.6: The framework of eager interpretation system.

Note that the classier is responsible to not only recognize the correct symbol, but also need to reject the wrong combination and unnished partial gesture. We therefore train the classier with wrong combination sample and unnished sample as negative symbol in addition to the original isolated symbol set. These two negative sample sets are generated as following:

Wrong Combination: a wrong combination is a stroke set whose strokes come from dierent gestures. Given a training gesture set G = {g 1 , g 2 , ..., g n } where the subscript index follows the input stream of the gestures, each one composed of 1 or more strokes.

strokes are more likely to be unnished symbols and then the possibility for a symbol to stay unnished decrease in time. The possibility then decreases with time elapsing. If the stroke can not be combined with others after a long time delay, the stroke itself is an isolated symbol that a decision has to be made for it. Therefore, we add a weight to the output of unnished gesture class as:

p un (t d ) = λ(1 - t d t f ) * p un (5.1)
where p un is the condence value of unnished gesture class output by classier. λ is a constant value determining the increased mount of possibility at beginning. We empirically set λ = 1.5. t d is the time delay between the stroke ending time and the recognition time. t f is the nal decision time at when the possibility will be decreased to 0 so that any other result of isolated symbol will be larger than the unnished gesture A problem is how to select an appropriate t f for the nal decision time. A small t f may force the system to make an early decision while the rest part of the symbol is still in writing. A larger one will postpone the decision and cause the stroke list to store too many strokes which makes more expensive to compute all combinations and increase the risk of generating false positive gestures. In the following experiment section we evaluate the recognition results with dierent values of t f . Fig. 5.9 gives a full view of stroke combination and recognition process. Taking 3 strokes for example, the gure shows all the 7 possible stroke combinations (candidates)

and their corresponding recognition scores. Among all the 7 candidates, 5 possible groups the feedback such as mis-recognition or long recognition delay. Since the dataset are collected without giving any recognition feedback to the users, there is no noise in the stroke stream. We evaluate the performance of system in terms of correct stroke grouping rate and recall rate based on dierent values of parameter t f . The underlying classier is the Graph Modeling with Motion Based Features classier illustrated in section 3.3 in order to well recognize the multi-touch gestures. The results are presented in Table 5.2. As far as nal decision time t f is concerned, the result at 500ms gives the best performance. It proves that neither too fast nor too slow could achieve a better result. An early decision may cause a partial gesture being recognized as a isolated symbol, while a later decision may cause a large stroke waiting list that leads to more mis-grouping. At step 55 the triangle is mis-segmented into two parts as a line and later (step 57) a direction. Step 51

Step 52

Step 53

Step 54

Step 55

Step 56

Step 57 To solve these problems, our rst attempt is developing an eager interpretation system which launch the recognition at each end of a stroke. Instead of designing a explicit stroke grouping method to cope with the complex stroke relation for multi-stroke and multi-touch gestures, we employ the brute force stroke grouping method to traverse all stroke combinations in a short time window. The underlying classier is trained with negative samples so that it can reject the wrong segmentation and unnished gestures.

A postponed parameter is employed for unnished gesture class so that a partial stroke can wait for enough time before recognition in case of forming another potential gesture with following strokes. First experimental results shows that system can well recognize majority of gestures from the stroke stream.

There are several perspectives about this work. The rst one is to exploit the complex stroke relations so that an explicit stroke grouping module can be achieved before gesture recognition. It would therefore simplify the classier with less negative sample to detect.

The second perspective is to involve dierent gestures command and manipulation such as Erase, Translation or even zooming, etc. i.e. to mix direct and indirect command in the gesture stream. To deal with direct command, the eager gesture recognition strategy should be merged in our global strategy, for example by not waiting the end of a stroke to try to recognize the gestures. The goal is to design an application that all commands and manipulations are achieved by gestures. As illustrated in section 5.1, more future work should be done following the features 3-6 involving context grammar and text recognition to achieve a complete application.

Chapter 6 Conclusion & Perspectives 6.1 Conclusion

The development of touch gesture operation facilities human computer interaction. Currently, multi-touch gestures have been mainly used and studied for direction manipulation such zooming, rotating, etc. There is few research studying to use multi-touch gesture to execute indirect commands. The work of this thesis aims at expanding the usage of multi-touch gestures and focuses more on the techniques of multi-touch gesture modeling and recognition.

To globally analyze and characterize a multi-touch gesture, the core problem is the synchronization relations, in both temporal and spatial domains, between touch trajectories. The main contribution of our work is the proposal of dierent graph modeling to integrate the shape information with temporal and motion relations between trajectories. The rst graph-based approach extracts static shape feature on each trajectory and uses Allen's relations as temporal description between the trajectories. We demonstrated that this modeling is simple and ecient to characterize and recognize multi-touch gestures. However it is not precise enough to capture the dynamic motion relations between trajectories.

We then progress to the second graph modeling which segments trajectories into small pieces and extracts synchronization features and dynamic motion features between each piece pair. To achieve the graph recognition, based on this gesture graph we studied the graph matching algorithm which nds the optimal vertex to vertex and edge to edge matching so that the cost of edit distance between two graphs can be calculated. Based on this edit distance, a graph embedding algorithm is then employed to transform the graph into a vectorial description to allow the use of classical pattern recognition classiers.

To evaluate this graph modeling and recognition system for multi-touch gestures, we found that there is few available multi-touch gesture dataset for a benchmark test in the community. We therefore designed and collected the MTGSet which is a multi-touch gesture dataset containing dierent type of gestures in terms of dierent stroke number 93 and complex inner-stroke relations. This dataset is fully annotated and free available on the website. We demonstrate that our graph modeling recognition method can better recognize these multi-touch gestures comparing to other reference systems based on static features.

The second phase of our work concerns the development of using multi-touch gestures for commands. Due to the fact that usually multi-touch gestures are regularly used for direct manipulation, we extend the study of the mixed usage of multi-touch gestures, i.e.

using multi-touch gestures for both direct manipulation and indirect command in a same context. We propose an early recognition system, which is based on a multi-classier, able to recognize a gesture as soon as possible, so that the user can have a suitable feedback.

Considering the ambiguous common part between gestures, classiers are designed with a reject option so that it can detect these ambiguous beginning parts and avoid making an ambiguous decision without enough information. The system achieves 83.44% accuracy rate with 46.82% earliness of input gestures on MTGSet.

The nal phase of our work is to design a structured document composition context.

This work is supposed to develop a real application so that all the touch gesture interaction techniques can be veried in this context. In an ideal context, it allows multiple users to compose structured diagrams using multi-stroke gestures and manipulate the diagram using multi-touch gestures. At the beginning step of this research, we rstly collected a multi-user diagram composition dataset. We designed an eager recognition system aiming at recognizing gestures at every ending of a trajectory and providing a real-time feedback to the user. We achieved a promising result but still have a long way to go to use it for practice.

Perspectives

There is a signicant tendency that large touch screens or even touch screen walls become more prevalent in our daily life. The goal of our research is to provide more freedom to the user to control the interaction system with dierent type of gestures. From the current study, we can suggest some perspectives to be achieved in a future work.

-The graph modeling need to involve more shape feature for a gesture. Our graph modeling is originally designed for multi-touch gestures which contain many dynamic features between strokes. According to the results on mono-touch gesture set, the involved shape features are too weak to recognize mono-touch gesture comparing to others. From the current graph modeling, one solution is to generate more substrokes for each stroke so that the shape will be represented more precisely. However, it will also signicantly increase the scale of a graph that results in a more expensive graph matching.

-In early recognition, we empirically select the number of classiers and each corresponding training segment length. In an ideal case, an early recognition system need to

Reconnaissance de gestes multipoints

A la différence des gestes mono-points où les tracés sont produits en séquence, dans le cas des gestes multipoints, les différents tracés ont des relations temporelles beaucoup plus complexes. Deux gestes ayant le même rendu visuel final peuvent avoir été produits de façon très différente. Nous chercherons à modéliser les relations inter-tracés telles qu'elles ont été produites afin de pouvoir distinguer ces différents types de geste. Compte-tenu du nombre variable de points de contacts, il est difficile d'extraire un nombre fixe de caractéristiques pour décrire les relations spatiales et temporelles entre les tracés. Pour cela, nous proposons d'utiliser un modèle à base de graphes pour représenter ces relations spatiales et temporelles, ainsi que l'aspect de chaque élément du tracé. Dans cette section, nous proposons deux types de graphes avec la méthode de classification associée pour permettre la reconnaissance du geste correspondant.

Modèle de graphe utilisant les relations d'Allen

La figure 2 présente le synoptique général de l'approche proposée.

Construction du graphe

La figure 3 2) Arêtes entre les noeuds extrémités (E s and E st ): Ces arêtes modélisent les relations existantes entre les extrémités des traits. A la différence des arêtes entre les noeuds centraux qui avaient un nombre fixe de trois relations, ici un nombre variable de 1 à 3 relations peuvent exister. Enfin, quand l'on considère une paire de noeuds extrémités opposés, seules les relations spatiales sont étudiées et l'arc se réduit à E s . Cet arc porte alors les relations spatiales en x et en y entre un noeud début et un noeud fin de trait.

Il est à noter que les relations portées par les arêtes entre les noeuds extrémités renforcent les mesures établies par les relations d'Allen. Bien que certaines de ces relations soient déjà présentes implicitement dans les arêtes des noeuds centraux associés aux traits, nous choisissons de conserver cette redondance. Ainsi, des gestes avec le même nombre de traits pourront avoir des structures de graphe différentes.

Plongement de graphe

La méthode de « graph embedding » cherche à ramener dans un espace vectoriel de dimension fixe un graphe de topologie variable afin de pouvoir utiliser des méthodes classiques de classification statistique. Dans ce travail, nous avons adopté l'approche proposée par by Sidere et al. [START_REF] Sidere | Vector Representation of Graphs: Application to the Classication of Symbols and Letters[END_REF]. L'étape initiale consiste à construire une matrice dont chaque ligne représente une étiquette possible d'un sommet ou d'une arête du graphe tandis que chaque colonne correspond à une sousstructure choisie du graphe. Cette matrice sert d'accumulateur pour dénombrer les occurrences des labels dans les sous-graphes iso-morphiques aux sous-structures. Ensuite, la concaténation des lignes de la matrice permet d'obtenir la représentation vectorielle.

Pour les colonnes de la matrice, nous avons choisi de considérer trois sous-structures : un seul sommet, deux sommets reliés par une arête et trois sommets reliés par deux arêtes. Nous aurons un total de 32 lignes, représentant les 9 (par défaut) symboles de forme issus du clustering attribuables au sommet Vs, le label début et fin et pour les sommets extrémités V b et V e et les 7 relations d'Allen pour les trois relations E st (temps, x et y). Conséquemment, un vecteur de taille 3x32 = 96 sera disponible à la suite de cette opération.

Représentation Globale de la Forme (Global Shape Representation, GSR)

Nous avons ci-dessus intégré la description locale (LSR) des traits à la représentation globale définie par le graphe. Une alternative à l'utilisation du graphe serait d'extraire directement du geste complet un vecteur de représentation global (GSR). À cet effet, nous extrayons globalement les caractéristiques HBF49 du geste complet, ces dernières pourront être considérées soit de façon isolée, soit en étant adjointes à celles provenant de la modélisation par graphe.

Expériences

Ces expériences mettent en oeuvre la base MTGSetA, qui contient 1 800 gestes multipoints, représentant 18 classes et provenant de 10 personnes différentes. La figure 4 illustre les 18 classes de gestes. Expérience 1 (GSR): seules les caractéristiques HBF49 en mode global sont utilisées. Celles-ci ont prouvé être très performantes dans des contextes mono-points. Nous les utilisons directement sur les tracés multipoints sans prendre en compte le modèle de graphe. En d'autres termes, dans cette expérience les conditions de synchronisation des tracés sont perdues.

Expérience 2 (Graph(LSR)): ici, nous utilisons le graphe pour modéliser le tracé puis sa description par un vecteur de taille fixe. Comme nous l'avons expliqué dans la section 3.2.1, l'approche LSR est basée sur un clustering non supervisé pour quantifier la forme des traits, le nombre optimal de cluster a été fixé empiriquement à 9.

Expérience 3 (Graph(LSR)+GSR): Finalement, nous concaténons les deux représentations précédentes pour intégrer à la fois les descripteurs de formes locaux et globaux.

Toutes ces expériences sont faites avec un protocole de validation croisée (5-cross-validation) pour permettre d'être indépendant des utilisateurs.

Modélisation par graphe avec des caractéristiques de déplacement

Le graphe précédent comporte certaines limitations. Les dépendances spatiales et temporelles ne sont prises en compte qu'aux extrémités des traits. De plus, le modèle ne retient que des descriptions symboliques (les relations d'Allen et les labels des traits) en tant qu'attribut du graphe. Ces descriptions discrètes ne sont sans doute pas suffisamment précises pour décrire les formes et les relations entre ces formes. Pour circonvenir à ces limitations, nous proposons dans cette section une nouvelle approche qui intègre des attributs scalaires permettant une représentation plus continue de l'espace des caractéristiques. La figure 5 présente le schéma général de l'approche.

Figure 5. Approche de reconnaissance basée graphe en trois étapes

Prétraitement et découpage des traits

Il faut trouver un bon compromis entre extraire un mouvement global entre deux traits, ce qui est trop réducteur de la diversité des situations rencontrées, et extraire un mouvement local entre chaque point du tracé, ce qui serait très lourd et inutilement bruité. La solution proposée consiste à ré-échantillonner les traits avec un pas spatial prédéfini, et travailler avec les sous-traits ainsi définis entre chaque paire de points.

Du geste au graphe

A ce stade, de façon élémentaire, un geste est disponible sous la forme d'un ensemble de sous-traits. Dans cette section, nous verrons comment extraire deux informations importantes : la forme de chaque sous-trait et les relations topologiques entre paire de sous-traits. Ces informations sont portées par un graphe. A partir de ces grandeurs, telles que définies par la figure 7

Mise en correspondance de graphes

Nous proposons de calculer une distance d'édition pour obtenir une mesure de (di-)similarité entre deux graphes représentatifs de deux gestes. Au lieu de réaliser une mise en correspondance globale sur les deux graphes entiers comme dans [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF][RB10], nous cherchons d'abord une mise en correspondance optimale de sous-graphes en ne considérant que les sommets, les arêtes seront ensuite automatiquement ajoutées.

Nous commençons par grouper les sommets qui appartiennent au même trait pour former des ensembles de sous-graphes qui sont en fait dans ce cas des chaines. L'algorithme DTW est utilisé pour calculer le coût d'association de deux de ces sous-graphes. Une matrice de coût C récapitule l'ensemble des coûts d'association des différentes paires possibles de sous-graphes. Puis l'algorithme de Munkres [START_REF] Munkres | Algorithms for the Assignment and Transportation Problems[END_REF] permet de trouver en temps polynomial l'ensemble optimal des assignations de sous-graphes. Il est possible alors de déduire la fonction de mise en correspondance entre chaque sommet des deux graphes. La distance d'édition se calcule alors simplement comme la distance euclidienne entre les vecteurs des sommets associés. La figure 9 présente la mise en correspondance des sous-graphes et la matrice de coûts C.

Classification basée graphe

Nous proposons une alternative à l'utilisation directe de la distance précédente par une méthode de K-ppv en reprenant l'idée proposée par Kapser and Horst [START_REF] Riesen | Graph Classication and Clustering Based on Vector Space Embedding[END_REF] proposant une représentation vectorielle du graphe qui utilise la distance disponible. L'idée de base est d'utiliser la distance du graphe à plusieurs formes prototypes pour construire un descripteur sous forme de vecteur. Un classifieur de type SVM est ensuite utilisée pour l'étape de classification du graphe.

Expérimentations

Nous effectuons les expérimentations sur la base MTGSetB, qui est une extension de MTGSetA. Nous ajoutons des classes plus complexes et étendons donc l'ensemble à 6138 échantillons et 31 classes. Dans le même temps, nous utilisons trois jeux de symboles mono-touch standard : LaViola, ILG et NicIcon, pour évaluer la performance de notre méthode sur les symboles mono-point. Nous comparons dans le Tableau 2 notre modélisation de graphe + plongement de graphe avec l'utilisation du jeu de caractéristiques HBF49 [4], qui est une approche statique conçue à l'origine pour le geste mono-point. Ces scores de confiance sont alors comparés à des seuils pour décider de l'acceptation ou non de la forme. Ces seuils sont appris sur une base de validation en minimisant le taux de fausse acceptation (FAR) et le taux de faux de rejet (FRR). Ici, le taux de rejet signifie que le geste partiel n'a pas n fois consécutives le même résultat ou a été rejeté par les trois classificateurs jusqu'à la fin. La précocité signifie le pourcentage moyen d'un geste qui est écrit au moment où il est reconnu. Le résultat pour n = 3 peut être considéré comme optimal lorsque les taux de fausse acceptation et de rejet sont équilibrés autour de 8,8% et la décision est prise en moyenne à 55,89% du tracé. Sans option de rejet, il faut monter à n = 5 pour un résultat comparable en terme de précocité (à 54,93%). Par contre, le taux d'erreur (13,72%) est supérieur de 55% au taux de fausse acceptation (8,85%) obtenu avec notre stratégie d'option de rejet.

Reconnaissance précoce basée sur l'utilisation du rejet

Expérimentations

Composition de document structurés dans le cadre multi-utilisateur

Dans cette dernière partie nous nous sommes intéressés à la problématique de la composition de documents lorsque plusieurs utilisateurs participent à cette tâche. Le point fondamentale qui change par rapport aux contextes des chapitres précédents est que plusieurs gestes peuvent être composés simultanément. Lorsqu'il y a plusieurs contacts en même temps, il n'est pas possible a priori de décider si ces traits composent un seul geste ou sont dessinés par deux utilisateurs. En plus de la tâche de reconnaissance il y a donc une tache de segmentation de la séquence en gestes. De plus, pour garder une fluidité d'utilisation, il faut reconnaitre un geste dès qu'il est terminé.

Base de diagrammes multi-utilisateurs

Pour réaliser cette étude, nous avons commencé par collecter une nouvelle base de gestes réalisés en condition multi-utilisateurs. Des diagrammes de type "cartes mentales" ont été recopiés (sans texte) par deux utilisateurs simultanément. 21 utilisateurs ont participé à collecter 42 diagrammes composés de 2011 gestes de 9 classes différentes. Certains symboles sont multi-points, d'autres multi-traits ou encore mono-traits. La Figure 13 donne un exemple de diagramme saisi.

Figure 13. Exemple de diagramme multi-utilisateur composé de 9 gestes différents : crochets, ellipse, rectangle, triangle, losange, ligne simple, double ligne, flèche et pointe de flèche.

Système de reconnaissance

La figure 14 illustre le fonctionnement global du système. À chaque fin de trait saisi par un des utilisateurs, ce dernier est ajouté à une liste de trait. À partir de cette liste, nous allons générer tous les gestes possibles. Chaque hypothèse de geste est évaluée par un classifier . Il y a trois types d'hypothèses qui peuvent être rencontrés : les gestes complets qui doivent être renvoyés à l'utilisateur ; les gestes incomplets qui doivent attendre d'être complétés ; et les mauvaises compositions de traits qui doivent être rejetées.

Les gestes détectés par le système sont renvoyés à l'utilisateur et leur traits sont retirés de la liste de traits en attente. Les traits restants seront ré-utilisés lorsqu'un nouveau trait sera saisi.

Figure 14. Architecture du système de reconnaissance multi-utilisateur.

Pour prendre ces trois types de décision, le classifieur est entrainé en utilisant une base de symboles valides, une base de symboles incomplets et une base de mauvaises combinaisons de traits. Comme évoqué dans la section précédente, certains gestes complets peuvent correspondre au début d'un geste plus long. Dans ce cas un conflit entre la classe du geste court et la classe "geste incomplet" bloque la reconnaissance du geste court. Pour éviter cette situation, nous proposons une pondération de la classe "geste incomplet" grâce à l'âge du trait concerné. En effet les traits composant un symbole complexe sont généralement dessinés dans un laps de temps assez court, donc un trait qui vient juste d'être saisi sera sûrement complété pour composer un symbole plus complexe, alors qu'un trait qui reste en attente depuis trop longtemps doit être utilisé.

Résultats

La

Conclusion

Notre travail explore la possibilité d'utiliser le geste multi-point pour la manipulation directe et la commande indirecte. Nous avons développé un système de reconnaissance utilisant une modélisation par graphes pour reconnaître une commande multi-point comme un symbole isolé. Pour évaluer la performance de notre système, nous avons construit un jeu de données MTGSet, qui contient 6138 gestes multi-point avec des relations spatiales et temporelles internes complexes. Nous avons atteint 98,97% de taux de reconnaissance sur ce jeu de données et montré que notre système de reconnaissance peut bien capturer les propriétés des gestes multi-point en le comparant à d'autres approches classiques. Pour explorer la possibilité d'utiliser un geste multi-point pour la manipulation directe et la commande indirecte dans un même contexte, nous avons proposé une stratégie de reconnaissance précoce visant à reconnaître un geste à partir de sa partie initiale. Nous avons proposé une structure multi-classifieur avec option de rejet. Le résultat expérimental montre que nous avons atteint un taux de reconnaissance de 82,38% avec une précocité moyenne de 55,89% en conservant un taux d'erreur est inférieur au système sans option de rejet.

Enfin nous avons proposé une architecture de reconnaissance adaptée à la saisie de gestes tactiles multi-points par plusieurs utilisateurs simultanément. La solution proposée est entièrement entrainable à partir d'une base de gestes saisis en conditions réelles (une base dédiée a été collectée). Les résultats avec 9 classes de symboles pour la saisie de cartes mentales sont très stables, autour de 90% avec tous les gestes reconnus au plus tard après 500ms.

Figure 1 . 1 :

 11 Figure 1.1: Touch gesture based manipulation interface.

Figure 2 .

 2 Figure 2.1: Handwritten touch gesture for indirect command: (a) Users may input an icon from the menu. The menu also shows the mapping from strokes to icons. (b) Using stroke as the shortcut to input the icon instead of selecting from menu. [AZ09]

Figure 2 . 2 :

 22 Figure 2.2: (a) A surface gesture taxonomy based on the number of strokes and touches. [SW13] (b) Examples of dierent type of gestures.

Fig. 2 .

 2 3 gives 4 examples of multi-touch indirect gesture commands, which are used as a shortcut to open Mission Control or show Notication Center. Most of Chapter 2

Figure 2 . 3 :

 23 Figure 2.3: Indirect gesture commands supported by Mac's trackpad.

Figure 2 . 4 :

 24 Figure 2.4: Gestures in feature space. (a) Two gestures have no common part. (b) Middle parts are common. (c) Beginning parts are common. [MUK + 06]

Fig. 2 .

 2 [START_REF]a) A anchor rotate gesture. b) Spatial relationship between strokes. c) Temporal relationship between strokes. d) Primitive set from clustering. e) Graph model with labels[END_REF] shows an example of DTW matching studied in[START_REF] Niels | Dynamic time warping applied to tamil character recognition[END_REF]. Each point is represented by its x and y coordinates as the local feature. In some other works, more elaborate local features are extracted for each point, such as velocity, pressure, curvature, etc. The DTW is then used to calculate a distance of the two sequences according to the points matching (as shown in Fig.2.6(b)).

Figure 2 . 6 :

 26 Figure 2.6: Example of a DTW matching. [NV05]

Chapter 2 (

 2 Figure 2.8: Example of all permutations for a two-stroke x and its unistroke representations. [AW10]

Figure 2

 2 Figure 2.9: (a) Examples of architectural plans in [MRLSL06]. (b) Example of engineering drawing in [LLLW15].

Chapter 2 Figure 2 .

 22 Figure 2.10: Example of stroke renement.[XWJS02]

Figure 2 .

 2 Figure 2.11: Examples of topology relations between primitives.[LLLW15]

Figure 2 .

 2 Figure 2.12: A sketch and its topology graph with the relations and geometry feature on edges. R ad means adjacency relation for two primitives which have a common endpoint. R hc means half-cross relation that one primitive has a endpoint joining some inner point of another primitive. [LLLW15]

  Figure2.13: The displacement of three touch points from time t-1 to t can be translation, scaling and rotation simultaneously. The f 1 , f 2 and f 3 are feature functions which are respectively related to translation, scaling and rotation.[START_REF] Oh | Mrf-based particle lters for multi-touch tracking and gesture likelihoods[END_REF]

Figure 2 .

 2 Figure 2.15: Rotate gesture described by GeForMT, where 1F means number of nger, HOLD and SEM ICIRCLE are predene atomic gestures, o means the nger is focusing on an object. [KWK + 10]

Figure 2 .

 2 Figure 2.16: Examples of indirect command oriented multi-touch gestures presented in [SW13]. Larger dots are depicting the start of a trajectory (from one touch), the arrows their movement and dashed smaller dots symbolize their end. Dierent strokes are colored dierently, black elements belong to the rst stroke, gray ones to the second.

Figure 2 .

 2 Figure 2.17: The overview of a multi-touch symbolic gesture classier's architecture presented in [SW13].

Figure 2 .

 2 Figure 2.18: An example of early recognition for a gesture, the recognizer give dierent feedback according to the progressing of trajectory. [PM13].

  the DP algorithm uses a local minimum distance at t *th frame of the reference gesture as the partial matching distance (Shown in Fig.2.19(b)). This method is simple and provide recognition results with far shorter recognition times than conventional algorithm. However, a simple distance based recognizer does not have the ability to identify the common beginning part of dierent gestures. This ambiguity or common beginning part strongly degrades the accuracy of the prediction results.

Figure 2 .

 2 Figure 2.19: (a) Conventional gesture recognition. (b) Early recognition strategy. [MUK + 06].

Figure 2 .

 2 Figure 2.20: Three frame classiers combined with weight propagation. [UA08].

Figure 2 .

 2 Figure 2.21: (a) Examples of diagrams with structure in [BPP + 14]. (b) A digital logic sketch in [PSDA10].

Figure 2 .

 2 Figure 2.22: (a) Lazy interpretation of musical score. (b) Eager interpretation of musical score [MA09].

  33and temporal relations between these trajectories, including synchronicity, are important properties to recognize dierent gestures. Such relations are useful to distinguish shapes with dierent writing orders. We described in chapter 2 some State-of-the-art methods[START_REF] Kin | Pro-ton++: a customizable declarative multitouch framework[END_REF] [LC02] [LLLW15] study these relations and their underlying semantics using individual segment instead of a global point of view. Some other multi-stroke sketch matching methods[START_REF] Manuel | Sketch-based Interfaces and Modeling, chapter Sketch-based Retrieval of Vector Drawings[END_REF] [LLLW15] exploit the topology relations between sketch primitives and give a global interpretation but obviously the temporal relations are not concerned.

Figure 3

 3 Figure 3.1: The graph modeling and classier training architecture of gesture recognition system.

Figure 3 . 2 :

 32 Figure 3.2: A stroke is represented by three vertices in a graph. V b : begin vertex; V s : stroke vertex; V e : end vertex.

Figure 3 . 3 :

 33 Figure 3.3: Examples of seven Allen's relations.

Figure 3 . 4 :

 34 Figure 3.4: An example of a general graph modeling for a two strokes gesture.

Figure 3 Fig. 3 .

 33 Figure 3.5: a) A ick gesture. b) Spatial relationship between strokes. c) Temporal relationship between strokes. d) Primitive set from clustering. e) Graph model with labels.

and {V 2 b ,V 2 e

 2 } pair means that the extreme points are written in the same region on y-axis. Comparing to the general case in Fig.3.4, the edges betweenV 1 b and V 2 e , V 2 b and V 1e in Fig.3.5(e) are removed because the corresponding two points are not located at the same position on neither x-axis nor y-axis. According to the primitive set shown in Fig.3.5(d) (A real primitive set should be acquired from the clustering of all strokes. Here we use an articial set to demonstrate the LSR process), both of the two strokes are classied to C 1 . Therefore, each stroke vertex V s is set to V c1 .

Figure 3 . 6 :

 36 Figure 3.6: a) A anchor rotate gesture. b) Spatial relationship between strokes. c) Temporal relationship between strokes. d) Primitive set from clustering. e) Graph model with labels.

Fig. 3 .

 3 Fig. 3.6(a) gives another example of an Anchor rotation gesture. This gesture is written by two ngers following a semi-synchronous way in time domain (as shown in 3.6(c)).

Figure 3 . 7 :

 37 Figure 3.7: Vectorial representation of the graph in 3.5(e).

Figure 3 .

 3 Figure 3.8: Multi-touch gestures prototypes in our experimental dataset.

Figure 3

 3 Figure 3.9: (a) We record some basic information from the users. (b) Data acquisition tool. In the top right, a animation is used to show the groundtruth of a multi-touch gesture.

Fig. 3 .

 3 Fig.3.10 summarizes the recognition rates obtained by dierent methods or their combination. The results show that the graph strategy, containing only spatial and temporal information, obtains 87.50% recognition rate which is lower than the HBF49 based GSR method (90.44 %). With a deeper investigation from the confusion matrix in Fig.3.11, most of the mis-classications by graph strategy happens between the gestures Command C-1, Command C-2 and Command X because they have similar spatial relationships between strokes (Fig.3.11(a)). We can note that GSR is able to classify the majority of

Figure 3 .

 3 Figure 3.10: Recognition rate obtained by dierent modules.

Figure 3 .

 3 Figure 3.11: Confusion matrix of some typical misclassied gestures of dierent classication methods. The row relates to the ground truth.

Figure 3 .

 3 Figure 3.12: Performance evaluation of dierent values of cluster number K used for LSR.

Figure 3 .

 3 Figure 3.14: Stroke segmentation and substroke representation. (a) a raw bracket like gesture; (b) the gesture is segmented into four substrokes and normalized inside a unit square bounding box. Each substroke has a feature vector composed of its length (l), angle (θ) and centroid (c).

Fig. 3 .Figure 3 .

 33 Figure 3.15: Example of temporal activity of substrokes in a multi-touch interaction. (a) A three strokes gesture. (b) The substroke representation, S ij indicates the jth substroke of stroke i. (c) Temporal activity of substrokes.

Chapter 3 Relation 1 (

 31 Adjacent, R a ) . Substrokes S ij and S kl are adjacent when they belong to the same stroke and are consecutive in time.

( 3 Fig. 3 .

 33 Fig. 3.16 illustrates the denition of these three motions.

Figure 3 .

 3 Figure 3.16: Motion features of two synchronous substrokes S ij , S kl . Translation motions (d x , d y ) are based on c s and c e , the centroids of starting point pair and ending point pair, respectively. Scaling motions (d s , d e ) are the distance of starting and ending point pairs, respectively. Rotation motion is the θ from the starting point pair to the ending point pair.

Figure 3 .

 3 Figure 3.17: (a) Illustration of the substroke relationships from example of Fig. 3.15. (b)

  R c Using the above graph denition, the gesture in 3.15(a) is represented in the form of weighted graph, which characterize both geometric and topological features as shown in Fig. 3.18(b). The comparison of two gestures is transformed into a graph matching problem. Another example is shown in Fig. 3.19. In this example, we show that gestures which have a same appearance may generate dierent graphs. If the two strokes are written in a synchronous manner, the corresponding graph is shown in Fig. 3.19(b). In another case, if two strokes are written in sequence, the graph representation is shown in Fig. 3.19(c). It proves that our graph modeling can well capture the stroke temporal relations and give out dierent representation even if gestures have a same appearance. It is discriminative for gesture recognition. While many other sketching matching works [LLLW15] [FFJ11] [LC02] use more comprehensive topology relation to capture the geometry or structural information between strokes such as Cross, Half-Cross, Parallelism, our denition focuses more on their temporal and motion relation which contains the main semantic intention of a multi-touch gesture. Meanwhile, a gesture which performed by multiple ngers would not have a complex structural relation between strokes. Therefore, our graph preserves the position and geometry information of each substroke on vertex and uses edge to describe their temporal relations which has never been done before. It is discriminative and informative for multi-touch gesture matching.

Figure 3 .

 3 Figure 3.18: (a) Substrokes and their relations as depicted in Fig. 3.17(a). (b) The graph representation of the gesture. (c) The attributes associated to the vectices and edges.

Figure 3 .

 3 Figure 3.19: Two graph representations of a gesture. (a) The original gesture which is also shown in Fig. 3.14. (b) The graph representation if two strokes are written in a synchronous manner, i.e. (s 11 synchronizes to s 21 , s 12 synchronizes to s 22 ). (c) The graph representation if the stroke s 21 , s 22 is written after the stroke s 11 , s 12 .

  .8) where the DTW distance D Φ [d](V s , U s ) is the alignment distance according to the Viterbi path dened as Φ = (φ(1), . . . , φ(N )), (3.9) with the alignment pair φ = (φ v , φ u ) : 1, . . . , N → {v 1 , . . . , v n } × {u 1 , . . . , u m }, (3.10) which denotes an alignment of vertex pair in corresponding regions in V s and U s . The DTW nds the optimal alignment path in the sense that it minimizes the distance between two sequences. The local distance function d of two vertices is the Euclidean distance of their feature vectors F as described in section 3.3.2.1.

Figure 3 .

 3 Figure 3.20: (a) Two gestures represented by substrokes and substroke relations. (b) The graph representation of two gestures. The vertices which belong to a same original stroke are grouped into a subgraph V n s ,U m s . (c) The DTW distance matrix is solved by Munkres'Algorithm to nd the optimal vertices matching between two graphs. Consequently, the vertices edit operation set Φ * all can be deduced from the DTW alignment.

Figure 3 . 3 . 3 . 3 . 2

 33332 Figure 3.21: The edge matching and edit operation of the two gestures in Fig. 3.20. The edge matching is implied by the vertices edit operation set Φ * all .

( 3 .

 3 16)By this way the local shape and structural/relation information is handled separetely.

Fig. 3 .

 3 23 presents a part of examples and their variations.

Figure 3 .

 3 Figure 3.23: Samples and their variations in MTGSet.

λ 1 . 2 Figure 4 . 2 :

 1242 Figure 4.1: Early recognition for a Heart gesture. In stage 3, the trajectory is recognized as Drag manipulation which gives an instant feedback along with the trajectory. In stage 4, the trajectory is recognized as a Symbolic-pattern, i.e. an indirect command. System need to wait until the end of the trajectory to interpret it as a Heart symbol. [PM13].

Fig. 4. 3 showsFigure 4 . 3 :

 343 Figure 4.3: (a) A normalized gesture as a template. (b) (c) In a size free context, due to the input gestures having a variety of the size, a trajectory with a length of l may cover dierent parts of a same type gesture.

  Consider a set of N training gestures x i |i = 1, ..., N , each gesture x i is a sequence of points x = p 0 , ..., p e normalized and centered in the unit square bounding box. As we discussed in section 4.1, users may perform a same gesture at dierent velocity. In other words, during a xed time interval ∆t, the length of the gestures performed by dierent users may be dierent. Therefore, our early recognition is based on the curvilinear distance segmentation rather than a time segmentation, i.e. each classier is trained by xed length partial trajectories. Fig.4.5(a) illustrates the segmentation of a gesture based on

Figure 4 . 4 :

 44 Figure 4.4: The structure of multi-classier early recognition system.

Figure 4 Figure 4 . 6 :

 446 Figure 4.5: (a) Trajectory of an example gesture. p 0 and p e are the starting and ending point, respectively. p k1 is the keypoint where the length of seg 1 (from p 0 to p k1 )is l ∆ . p k2 represents the point at 2l ∆ . Since the total length is less than 3l ∆ , this trajectory will oer three segments for training. (b) Classiers are trained with dierent segments.

Fig.4. 6 ,

 6 the outlier samples locate far from the center of each class. Therefore, the most important information for this rejection option is the intrinsic description of the learned data.Depending of the used classier, this information is not always directly available[START_REF] Mouchere | A unied strategy to deal with dierent natures of reject[END_REF]. If the classier outputs approximate the probability density of the learned data as in classiers like RBFNN, Mixture of Gaussian, then the reliability function can be dened as equation 4.4.ψ Out i = s i (4.4)In our case, we use SVM classier based on the distance to graph prototypes representing the dierent classes (see graph embedding in section 3.3). So by construction, the distance to these prototypes is a good feature to extract the intrinsic description of the training data. Thus in the experiments we use the equation 4.5 to compute the minimum distance of sample x to the set of prototype P i of class i using the distance d as dened in equation 3.14. d i (x) = min p j ∈P i d(x, p j ) (4.5) Then the reliability function ψ Out i can be dened with equation 4.6 and used in the rejection decision as equation 4.7.

4)

  Direct manipulation or indirect command gesture to interact with the existed elements. 5) Text separation. 6) Text recognition.

Figure 5

 5 Figure 5.1: The diagram data acquisition procedure on a 80" touch screen. Two users are drawing the diagram together using stylus.

Figure 5 . 2 :

 52 Figure 5.2: Example of a mind map diagram and the corresponding handwritten diagram without text.

Figure 5 . 3 :

 53 Figure 5.3: Samples of isolated symbols in diagram.

Figure 5 . 4 :

 54 Figure 5.4: Variability of the rectangle symbol.

  (a) A two strokes `rectangle' synchronizes with a three strokes `arrow'. (b) A two strokes `arrow' synchronizes with a two strokes `double line'.

Figure 5 . 5 :

 55 Figure 5.5: Example of temporal activity of strokes under 2 users condition. S ij indicates the jth stroke from user i.

Figure 5 . 8 :

 58 Figure 5.8: The score of unnished class is manually increased at the ending time of a stroke and decreased with time elapsing.

Fig. 5 .

 5 Fig. 5.10 shows a screen shot of two full example diagrams. The green gestures are correctly grouped and recognized. Oranges are mis-grouped gestures. Most of them are multi-stroke gestures that wrongly being segmented into several parts. The reds ones are mis-recognized by classier.

Fig. 5 .

 5 Fig. 5.11 shows the detail of the drawing of Fig. 5.10 (b) after 50 strokes drawn.

Fig. 5 .

 5 Fig. 5.11 (b) shows the current stroke list and their decisions at each step. The group of strokes recognized as unnished stay in the stroke list for next step. The group recognized as concrete symbol are removed from current list. We can notice that the stroke drawn at step 51 is recognized as unnished for two steps until step 53 where it recognized as line. This illustrates the impact of age of the stroke on the decision (see equation 5.1).

  (a) Example of recognition results of layout 1. (b) Example of recognition results of layout 2.

Figure 5 .

 5 Figure 5.10: Recognition result for two example diagrams. Gestures in green are correctly recognized. Oranges are mis-grouped gestures. Reds are correctly grouped but misrecognized gestures.

( b )

 b Stroke stream between steps 51 and 57. (c) Final context at step 57.

Figure 5 .

 5 Figure 5.11: Stroke stream and their recognition results between steps 50 and 57 from Fig. 5.10 (b). The recognition decisions of each step are bounded in dashed rectangles.

  Figure 1. Deux types d'interaction tactileDe nos jours, les gestes tactiles mono-points (un seul point de contact à chaque instant) sont largement utilisés et étudiés à la fois pour de la manipulation directe et pour des commandes indirectes. Les utilisateurs ont même la possibilité de spécifier leurs propres gestes et de les associer aux commandes de leurs choix. Par contre, concernant les interactions multipoints, il existe de nombreuses limitations qui les contraignent à de la manipulation directe, telle que zoomer avec deux doigts. Le travail proposé dans cette thèse étend l'usage des gestes multipoints pour les rendre utilisable dans un cadre de commande indirecte (tel que copier, coller, etc.) et pour élargir les manipulations directes envisageables. Un des enjeux de notre problématique est de proposer des

Figure 2 .

 2 Figure 2. Structure générale de la construction du graphe et de sa reconnaissance. Nous mesurons ensuite les relations spatiales et temporelles entre les différents traits. À titre d'exemple, considérons un geste avec deux traits dont le graphe général est donné figure 3. Sur ce

Figure 3 .

 3 Figure 3. Structure générale d'un graphe d'un geste avec deux traits. 1) Arête entre les noeuds centraux (A st ): Le jeu complet des relations d'Allen est utilisé pour établir les relations vis-à-vis du temps, de la position en x et de la position en y entre deux traits V s . L'indice st signifie que les relations spatiales et temporelles sont considérées. Il en résulte que l'arc A st contient un triplet de relations comme attribut.

Figure 4 .

 4 Figure 4. Pictogrammes des gestes de la base Dans la mesure où les gestes tactiles ont été traduits par des vecteurs de caractéristiques, tous les classifieurs statistiques sont envisageables. Nous avons retenu pour cette expérience un classifieur SVM issu de la librairie LIBSVM en retenant un noyau gaussien et les méta-paramètres par défaut. Trois séries d'expériences sont proposées pour évaluer ce premier système.

Figure 6 .

 6 Figure 6. Segmentation des traits et diagramme d'activité des sous-traits. Chaque sous-trait est défini par quatre paramètres géométriques, sa longueur ( ), son inclinaison, l'angle ( ) et son centre de gravité ( , )

Figure 7 .

 7 Figure 7. Caractéristiques de mouvement entre deux sous-traits synchrones S ij , S kl . Le vecteur de translation (d x , d y ) est basé sur les centres de gravité c s et c e , des paires des points de départ et d'arrivée respectivement. Le facteur d'échelle (d s , d e ) mesure les distances entre les points de départ et d'arrivée. L'angle θ définit la rotation permettant de passer de la direction du couple de points de départ au couple de points d'arrivée.

Figure 8 .

 8 Figure 8. (a) Sous-traits correspondant à la figure 6(a) et leurs relations. (b) Le graphe correspondant. (c) Les attributs associés aux sommets et aux arêtes. Une fois que la distance entre les sommets est calculée, le calcul est étendu en prenant en compte les arêtes adjacentes. Comme il y a trois types d'arêtes avec chacune des attributs différents, les coûts d'association ne sont faits que sur les arêtes de même type.

Figure 9 .

 9 Figure 9. (a) Deux gestes avec les sous-traits et leurs relations. (b) Le graphe représentatif de chaque geste. Les sommets qui appartiennent au même trait sont regroupés dans les sous-graphes , . (c) L'assignation optimale de la matrice de coûts DTW solutionnée par l'algorithme de Munkres, et la mise en correspondance des sommets Φ * .

  Dans la section précédente, nous avons proposé une méthode de classification pour reconnaître après leur achèvement les gestes multi-point de commandes indirectes. Si dans une même application, les utilisateurs doivent pouvoir utiliser des gestes multi-point en commande directe et aussi indirecte, un conflit entre ces deux interactions apparaît. En effet elles offrent une rétroaction complètement différente pour les utilisateurs. La manipulation directe doit donner une rétroaction instantanée pendant la trajectoire du doigt, tandis que la commande indirecte peut attendre la fin d'un geste, alors que le début des deux gestes peut être très similaire. Dans cette section, nous explorons une stratégie de reconnaissance précoce visant à reconnaître un geste dès le début afin de prendre une décision dès que possible.

Figure 10 .

 10 Figure 10. Deux gestes avec une partie commune ambigue pour la reconnaissance précoce. Reconnaissance précoce par combinaison de classifieurs Nous proposons une structure multi-classifieur pour la reconnaissance précoce des gestes, comme le montre la figure 11. Chaque classifieur est entraîné sur une sous-partie du geste de sorte que les différents classifieurs sont responsables de différentes phases du geste. Dans un cas idéal, un geste d'entrée incomplet à venir (d'une longueur de l) est d'abord affecté au classificateur h1. S'il ne peut pas être distingué avec un autre geste en raison de leur début commun, on attendra une autre longueur de trajectoire et l'assignera au classificateur h2. Le même processus est utilisé pour les classificateurs suivants jusqu'à ce qu'un classificateur trouve suffisamment de différences pour faire une reconnaissance. Cependant, nous n'imposons pas de taille minimale ou maximale à un geste, il est impossible à partir d'un geste en cours de formation de savoir quelle proportion du geste est réalisée. Il peut donc y avoir conflit entre un début de geste et un autre geste complet. Par conséquent, dans notre système multi-classifieur, nous assignons chaque geste incomplet à tous les classifieurs et laissons un module de fusion pour décider si le geste peut être accepté ou non.

Figure 11 .

 11 Figure 11. Architecture du système multi-classifieur pour la reconnaissance précoce.Option de rejetSur la base de la structure multi-classifieur, nous mettons en oeuvre deux options de rejet pour chaque classificateur: le rejet d'ambiguïté et le rejet de distance. Le premier est utilisé pour détecter la partie commune entre les gestes en conflits et permettre au système d'attendre plus de trajectoire. Le second est utilisé pour rejeter un geste partiel qui n'est pas compatible avec un des classifieurs et laisser les autres prendre une décision. La figue. 12 illustre la différence entre ces deux options de rejet.

Figure 12 .

 12 Figure 12. Différence entre le rejet d'ambiguïté et le rejet de distance. Nos options de rejet sont basées sur les scores triés par ordre décroisant de chaque classe donnés par chaque classifieur. Les fonctions de confiance pour le rejet d'ambiguïté et le rejet de distance sont données par :

3. 10

 10 Recognition rate obtained by dierent modules. . . . . . . . . . . . . . . . 3.11 Confusion matrix of some typical misclassied gestures of dierent classication methods. The row relates to the ground truth. . . . . . . . . . . . 3.12 Performance evaluation of dierent values of cluster number K used for LSR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.13 Overview of the graph based gesture recognition in three stages. . . . . . . 3.14 Stroke segmentation and substroke representation. (a) a raw bracket like gesture; (b) the gesture is segmented into four substrokes and normalized inside a unit square bounding box. Each substroke has a feature vector composed of its length (l), angle (θ) and centroid (c). . . . . . . . . . . . . 3.15 Example of temporal activity of substrokes in a multi-touch interaction. (a) A three strokes gesture. (b) The substroke representation, S ij indicates the jth substroke of stroke i. (c) Temporal activity of substrokes. . . . . . 3.16 Motion features of two synchronous substrokes S ij , S kl . Translation motions (d x , d y ) are based on c s and c e , the centroids of starting point pair and ending point pair, respectively. Scaling motions (d s , d e ) are the distance of starting and ending point pairs, respectively. Rotation motion is the θ from the starting point pair to the ending point pair. . . . . . . . . . 3.17 (a) Illustration of the substroke relationships from example of Fig. 3.15. (b) The corresponding adjacency matrix. . . . . . . . . . . . . . . . . . . 3.18 (a) Substrokes and their relations as depicted in Fig. 3.17(a). (b) The graph representation of the gesture. (c) The attributes associated to the vectices and edges. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.19 Two graph representations of a gesture. (a) The original gesture which is also shown in Fig. 3.14. (b) The graph representation if two strokes are written in a synchronous manner, i.e. (s 11 synchronizes to s 21 , s 12 synchronizes to s 22 ). (c) The graph representation if the stroke s 21 , s 22 is written after the stroke s 11 , s 12 . . . . . . . . . . . . . . . . . . . . . . . . . 3.20 (a) Two gestures represented by substrokes and substroke relations. (b) The graph representation of two gestures. The vertices which belong to a same original stroke are grouped into a subgraph V n s ,U m s . (c) The DTW dis- tance matrix is solved by Munkres' Algorithm to nd the optimal vertices matching between two graphs. Consequently, the vertices edit operation set Φ * all can be deduced from the DTW alignment. . . . . . . . . . . . . . 3.21 The edge matching and edit operation of the two gestures in Fig. 3.20. The edge matching is implied by the vertices edit operation set Φ * all . . . . 3.22 The multi-touch gesture templates in MTGSet. . . . . . . . . . . . . . . . 3.23 Samples and their variations in MTGSet. . . . . . . . . . . . . . . . . . . .

  3.3 introduce the graph matching algorithm, based on graph edit distance involving dynamic time warping (DTW) algorithm, to measure the similarity between two graphs. A new distance based graph embedding algorithm is nally presented to transform the graph into feature vector for classication.

	Preprocessing	Gesture to Graph
	Stroke segmentation	Shape feature on substroke (vertex)
		Motion relation
		between substroke
		(edge)

  Algorithm 1 Stroke resampling in a length of ∆ Input: original trace P org (p 0 , . . . , p n ) Output: new trace P new (p 0 , . . . , p m )

	1: P new ← p 0
	2: D ← 0
	3: for all p i (i ≥ 1) in P org do
	4:	d ← Distance (p i-1 , p i )
	5:	if (D + d) ≥ ∆ then
	6:	(P new ← p i )
	7:	D ← 0
	8:	else
	9:	D ← D + d
	10:	end if
	11: end for

12: P new ← p n 13: return P new

  .17 (b).

		S 21			S 21	S 22	S 31	S 32
			S 22	S 11	R c	-	R c	-
					S 21	R a	R s	-
	S 11	S 31	S 32			S 22	-S 31	R s R a
							S 32

Table 3 .

 3 1: Recognition accuracy as the function of prototype number per class. Chapter 3 and Strategy 3 show more stable results comparing to Strategy 1. They achieve a good performance even with a small prototype set by the help of graph embedding and SVM classier. Generally, the Strategy 2 and Strategy 3 outperform the Strategy 1, but are very close between each other.

			Prototype number per class
	1	3	5	10	20	30	50
	Strategy 1 74.97% 81.33% 81.48% 85.48% 87.14% 86.43% 85.21%
	Strategy 2 96.35% 97.34% 97.51% 98.22% 98.39% 98.29% 98.22%
	Strategy 3 97.64% 97.91% 98.02% 98.59% 98.97% 98.29% 98.22%

Not surprisingly, the accuracy rate increases accordingly with the increasing of the prototype number per class for all three classiers. They reach at the peak at 20 prototypes per class and slightly decrease for more prototypes. It is remarkable that the Strategy 2

Table 3 .

 3 2: Recognition accuracy of dierent methods.

		Mono-touch gestures	Multi-touch gestures
		La viola	ILG	NicIcon	MTGSet
	HBF49+SVM	93.64%	93.54%	97.44%	91.36%
	Strategy 3(20 prototypes)	93.18%	91.30%	93.17%	98.97%

Table 4 .

 4 1: Notations to represent the number of samples in dierent conditions. With these notations:

Table 5 .

 5 1: Symbols' distribution and their average and maximum stroke number in the complete dataset composed of 20 diagrams drawn by ngers and 22 drawn with stylus.

		Symbols Av. #strokes Max. #strokes
	Bracket	140	2.05	3
	Ellipse	278	1.02	2
	Rectangle	158	1.89	7
	Triangle	88	1.39	5
	Diamond	92	1.48	4
	Line	446	1.00	2
	Double line	140	2.02	3
	Arrow	424	1.86	4
	Direction	242	1.19	2

Table 5

 5

	.2: Correct stroke grouping and recognition rate
	t f (ms)	300	500	1000	2000
	Segment Number	691	687	675	649
	Correct Segments	592	596	593	578
	Segment Recall Rate	89.43%	90.03% 89.58% 87.31%
	Symbol Recall Rate	75.68%	76.28%	76.13%	74.77%
	The performances in terms of stroke grouping rate are around 90%. It means that
	system makes 1 mis-grouping every 10 multi-stroke gestures and leads to a denite mis-
	recognition. The global recall rates are around 75% which is signicantly lower the
	grouping rate. It means that with the correct stroke grouping, system results around
	15% mis-recognition rate. As we illustrated in section 3.3.4.2, our Graph Modeling with
	Motion Based Features classier is specially designed for multi-touch gestures. With the
	additional complex negative sample sets, it gives out an even low result.

Résumé en Français 1. Introduction Les

  interactions gestuelles tactiles font parties des interactions personne-machine les plus naturelles. Elles permettent une expérience utilisateur plus intuitive et plus appropriées que l'usage du clavier et de la souris. Avec le développement des écrans tactiles, un nombre croissant d'usagers se familiarise avec ce type d'interactions gestuelles. D'un point de vue interaction, les gestes tactiles sont utilisables selon deux modalités : la manipulation directe de certains éléments de l'interface et de façon complémentaire le déclenchement a posteriori d'une commande résultant de l'interprétation d'un geste symbolique que l'on qualifiera de commande indirecte. Un usage explicite d'une commande directe peut être donné en considérant le cas de la manipulation d'un plan cartographique où l'utilisateur pourra déplacer la carte par des glissements du doigt ou encore changer le zoom en écartant ou en resserrant deux doigts, faire pivoter la carte en appliquant une rotation d'un doigt autour d'un autre. Dans un cas général, une telle commande directe produit un retour continu au fur et à mesure de la production du geste initiateur. Ainsi, avec l'exemple du glissement de doigt (scroll) sur la carte, le déplacement de celle-ci se produit concomitamment avec celui-ci.

  Un des enjeux de notre problématique est de proposer des modèles d'analyse et de reconnaissance aptes à traiter les gestes multipoints, comme il en existe aujourd'hui pour les gestes mono-points.Pour modéliser les gestes multipoints, nous avons privilégié une approche basée graphe (section 2). Les caractéristiques du geste multipoint telles que sa forme, les relations spatiales et temporelles entre les trajectoires des doigts vont être prises en compte pour construire le graphe de représentation. Une description vectorielle du graphe (graph embedding) couplée à un classifieur SVM permettra d'assurer la reconnaissance du geste. Afin de mettre au point, d'entrainer et de tester nos différents systèmes, nous avons conçu, collecté et annoté une base d'exemples, MTGSet, qui réunit 7 938 gestes de 41 classes différentes. Pour traiter les problèmes d'ambigüités entre manipulation directe et commande indirecte sans connaissance du contexte, nous proposons une stratégie de reconnaissance précoce pour des gestes multipoints (section 3). L'objectif est de reconnaitre le geste en considérant le début du tracé pour permettre un retour utilisateur avant la fin du tracé. Nous proposons également des stratégies d'implémentation pour traiter une application effective. Finalement, nous abordons les difficultés spécifiques de la composition multiutilisateurs de documents dans un contexte multipoints (section 4). Dans ce cas, il s'agit pour reconnaitre les gestes de chaque utilisateur de pourvoir distinguer les traces respectives produites par chacun.

  montre le graphe pour un geste composé de deux traits. Chaque trait est représenté par trois noeuds, un noeud associé à chaque extrémité, V b (begin) et V e (end), et un noeud central V s . Ces trois noeuds serviront pour introduire les relations entre les traits grâce aux arêtes qui en seront issues.Ensuite, l'information de forme du trait est encodée dans le graphe. Nous utilisons pour cela un dictionnaire de formes élémentaires (ligne, arc, ellipse, …) pour décrire de façon discrète chaque trait. Chaque trait est alors associé au représentant du cluster auquel il appartient. Dans la mesure, où seules des informations de formes locales à chaque trait sont utilisées, cette stratégie est appelée Local Shape Représentation (LSR).

À la différence d'autres travaux [LLLW15] [AMG07] où ces formes sont prédéfinies de façon empirique, nous avons construit le dictionnaire par un algorithme de clustering non supervisé à partir d'une base d'apprentissage. Pour cela, l'algorithme des K-means avec la distance Euclidienne dans l'espace des caractéristiques HBF49 [DA13] est utilisé.

  Le tableau 1 résume les taux de reconnaissance obtenus avec les deux approches et leur combinaison. Les résultats montrent que l'approche structurelle par modèle de graphe, contenant des informations spatiales, temporelles et de formes locales, obtient un taux de reconnaissance de 92,56% ce qui est meilleur que celui obtenu avec les caractéristiques globales HBF49 (90,44 %). Cela montre que la modélisation proposée sous forme de graphe est bien apte à capter des informations importantes pour ces gestes multipoints. De façon complémentaire, la troisième expérience qui intègre les deux jeux de caractéristiques précédents obtient les meilleurs résultats avec un taux de 94,50 %, ce qui est significativement supérieur.

		Tableau 1. Résultats de reconnaissance sur la base MTGSetA
	Méthode	Taille du vecteur	Taux de reconnaissance (%) Ecart type (%)
	GSR	49	90.44	0.034
	Graph(LSR)	96	92.56	0.013
	Graph(LSR)+GSR	145	94.50	0.020

  , on construit le vecteur de mouvement suivant:Cette grandeur est normalisée par la durée totale du geste pour la ramener dans l'intervalle [0,1].

	,	,	, /2
	Relation 3 (Consécutivité, R Globalement, l'ensemble des relations de l'exemple de la figure 6 est présenté sur la figure 8 (a). En
	utilisant les caractéristiques géométriques et les relations définies ci-dessus, nous pouvons construire
	un graphe, appelé Multi-Touch-Stroke Graph (MTSG), tel que présenté à la figure 8(b).

c ). Deux traits S i et S k sont dits consécutifs, soit tracés en séquence quand ils ne partagent pas de sous-traits synchrones.

Dans la mesure où le modèle est construit au niveau des sous-traits, cette relation va être établie entre le dernier sous-trait d'un trait et le premier sous-trait d'un trait consécutif. Un attribut mesurant le retard temporel t d entre les deux sous-traits est calculé , /

  Tableau 2. Taux de reconnaissance pour les 4 bases de test Nous constatons que l'ensemble de caractéristiques HBF49 fonctionne mieux sur les trois jeux de gestes mono-point. Les raisons sont que ces trois ensembles de données n'ont pas de relation de synchronisation complexe entre les traits et que les caractéristiques extraites pour chaque trait dans notre approche sont beaucoup plus simples que celles de HBF49. Par conséquent, notre approche est moins puissante sur l'aspect analyse de la forme par rapport à HBF49. Cependant, notre méthode de modélisation et d'appariement de graphes surpasse de manière significative le HBF49 sur MTGSetB. Principalement parce que le MTGSetB contient des gestes qui sont de forme similaire mais qui ont des relations temporelles internes différentes. Notre méthode est donc dédiée au problème de reconnaissance gestuelle multi-point.

		LaViola	ILG	NicIcon	MTGSetB
	HBF49	93.64%	93.54%	97.44%	91.36%
	Graph modeling	93.18%	91.30%	93.17%	98.97%

  Nous évaluons notre système sur la base MTGSetB qui contient 3589 gestes d'entraînement et 2549 gestes pour l'ensemble de test. Nous utilisons 20% des échantillons de l'ensemble d'entraînement comme un ensemble de validation pour l'apprentissage des seuils. Le nombre de classifieurs est fixé à 3. Avant l'apprentissage, chaque geste est normalisé dans un cadre de 500x500 pixels et segmenté en 3 gestes partiels de longueur 250, 500, 750 pixels pour alimenter respectivement les 3 classifieurs. Notez que chaque geste n'a pas plus de 750 pixels. Si un geste est inférieur à 500 pixels, il ne sera segmenté que sur deux gestes partiels et alimentera les deux premiers classifieurs. Lors du test, un geste est tenté d'être reconnu tous les 50 pixels de sa trajectoire. Dans le cas d'utilisation réelle, une stratégie raisonnable consiste à filtrer les décisions en considérant plusieurs sorties consécutives du classificateur (i.e. à différentes longueurs). Par conséquent, une décision est finalement acceptée lorsque le classificateur donne n fois consécutives la même sortie. Dans le tableau 3 nous comparons la précision de reconnaissance avec une stratégie sans rejet pour n = 1 à 6. Tableau 3. Résultat pour la reconnaissance précoce de gestes avec ou sans utilisation du rejet pour n décisions identiques consécutives.

			Avec Rejet			Sans Rejet
	n	Taux vrai acceptation	Taux fausse acceptation	Taux de Rejet	Précocité	Taux de Reconnaissance	Taux d'Erreur	Précocité
	1	81.89%	14.56%	3.54%	37.04%	24.88%	75.15%	8.13%
	2	83.44%	10.85%	5.71%	46.82%	48.78%	51.22%	21.32%
	3	82.38%	8.85%	8.77%	55.89%	67.60%	32.40%	33.98%
	4	82.20%	6.06%	11.73%	66.16%	79.59%	20.36%	45.44%
	5	80.35%	4.60%	15.05%	71.03%	85.83%	13.72%	54.93%
	6	77.42%	3.41%	19.17%	77.54%	88.62%	11.39%	62.34%

  tableau 4 montre les résultats obtenus en fonction de t s l'âge maximum d'un trait non utilisé. Plus t s est long, plus les gestes simples en conflit restent en attente longtemps. Si les traits sont utilisés trop tôt, certaines compositions sont manquées, si les gestes sont conservés trop longtemps, certains mauvais regroupements sont pris pour ces gestes. Le meilleur compromis est obtenu pour 500ms avec un taux de reconnaissance de 90%. Tableau 4. Taux de bonne segmentation et taux de reconnaissance en fonction de t s .

	t s (ms)	300	500	1000	2000
	Segment Number	691	687	675	649
	Correct Segment	592	596	593	578
	Segment Recall Rate	89.43%	90.03%	89.58%	87.31%
	Symbol Recall Rate	75.68%	76.28%	76.13%	74.77%

Chapter 0

automatically learn these parameters from training dataset so that it can nd the optimal early decision time for each gesture. Our future work will focus on investigating an adaptive system to learn these information.-Last but not least, the eager interpretation system for multi-user structured document composition need more improvements. On the one hand, a better stroke grouping strategy need to be explored. Instead of using brute force stroke combination, a spatial feature based preprocess is required to prune the number of stroke combination. On the other hand, as discussed above a more powerful isolated symbol classier is essential to the current system. Moreover, with a better early recognition system, we will try to engage both direct manipulations and indirect commands into this application.

FAR and RR are obtained using the reject option while ER is the traditional mis-classied rate.

same output. Results on the two datasets are shown in Table 4.2 from n = 1 to 6. Referring to the notation of Table 4.1, TAR is True Accept Rate (T AR = N T A /N ), FAR is False Accept Rate, RR is Reject Rate which represent the percentage of gestures which are rejected at every length until their completion, CR is correct rate (C R = N cor /N ).

The earliness means the average percentage of the a gesture being written at the time it is recognized. Since the ILG data does not contain the time label, the average decision time (Avg.T) is only measured on MTGSet. To generate this negative sample set, we extract random number of strokes among the strokes belonging to two consecutive gestures g i and g i+1 . As a negative set, obviously it can not cover all the negative possibility. However, dierent size of this negative set can be generated to balance the ratio of positive (correct gestures) and negative (wrong segmentation) samples.

Unnished Gesture: an unnished gesture is a sub-stroke set of a completed gesture.

Given a n stroke gesture g = {s 1 , s 2 , ..., s n }, we extract all its sub-stroke set following the input sequence as {s 1 },{s 1 , s 2 },...,{s 1 , s 2 , ..., s n-1 }. As the size of this set is comparable to the number of positive gestures (depending of the average number of strokes per gesture),

we use them all. However, subsampling is possible to better balance the training set.

As shown in Fig. 5.6, strokes which are recognized as wrong combination or unnished gesture will be restored into the stroke list and wait for new strokes. We dier them as two independent negative classes because of a special situation: an unnished gesture can be comparable to an isolated full symbol (shape and synchronization). Take a straight line for example, without context information, it can be recognized as either an isolated line symbol or the beginning part of a potential rectangle as unnished gesture (Shown in

line part of a rectangle

A line symbol has a similar shape as the part of a rectangle From the classier point of view, it is dicult to distinguish these two cases since they have the same appearance. From the practice point of view, it is reasonable to postpone the decision after the end of a stroke in case of forming another potential gesture with following strokes. To take into account this principle in the decision process, we can not use only the classier outputs (as done in the previous chapter with reject option). Indeed, the stroke itself will not change in time, so if a potential conict is detected thanks to the class scores (e.g. `line' score and `unnished' score are close), this conict will remain the same in future. If a symbol is completed by new strokes, then the new symbol can have a strong score and its strokes will be removed from the stroke list. If the partial symbol is never completed, it means that it is a full symbol and after a certain period the next decision should be used instead of `unnished'.

5.6

The framework of eager interpretation system. . . . . . . . . . . . . . . . .

5.7

The decision for some shape should be postponed in case of forming another For this purpose, we analyze the shape of the gesture's motion trajectories and the temporal and spatial relations between trajectories in order to characterize a multi-touch gesture. We propose a graph modeling to characterize these motion features and develop a graph based analysis and recognition system. To resolve the conflict between interface manipulation and shortcut command inputs, we study and validate an early recognition strategy for multi-touch gesture. We built a reject option based multi-classifier early recognition system to recognize multi-touch gestures in early stage.

To set-up, train and validate our systems, we built MTGSet, a multi-touch gesture dataset formed by 7938 gestures from 41 different classes collected in isolated contexts and MUMTDB a dataset of gestures collected in a real multi-user usage case of diagram drawing. The experimental results prove that our system can well recognize multi-touch gestures in these different situations.