L’alignement de multiples séries temporelles est un problème important non résolu dans de nombreuses disciplines scientifiques. Les principaux défis pour l’alignement temporel de multiples séries comprennent la détermination et la modélisation des caractéristiques communes et différentielles de classes de séries. Cette thèse est motivée par des travaux récents portant sur l'extension de la DTW pour l’alignement de séries multiples issues d’applications diverses incluant la reconnaissance vocale, l'analyse de données micro-array, la segmentation ou l’analyse de mouvements humain. Ces travaux fondés sur l’extension de la DTW souffrent cependant de plusieurs limites : 1) Ils se limitent au problème de l'alignement par pair de séries 2) Ils impliquent uniformément les descripteurs des séries 3) Les alignements opérés sont globaux. L'objectif de cette thèse est d'explorer de nouvelles approches d’alignement temporel pour la classification non supervisée de séries. Ce travail comprend d'abord le problème de l'extraction de prototypes, puis de l'alignement de séries multiples multidimensionnelles. / Temporal alignment of multiple time series is an important unresolved problem in many scientific disciplines. Major challenges for an accurate temporal alignment include determining and modeling the common and differential characteristics of classes of time series. This thesis is motivated by recent works in extending Dynamic time warping for aligning multiple time series from several applications including speech recognition, curve matching, micro-array data analysis, temporal segmentation or human motion. However these DTW-based works suffer of several limitations: 1) They address the problem of aligning two time series regardless of the remaining time series, 2) They involve uniformly the features of the multiple time series, 3) The time series are aligned globally by including the whole observations. The aim of this thesis is to explore a generalized dynamic time warping for time series clustering. This work includes first the problem of prototype extraction, then the alignment of multiple and multidimensional time series.

Qu'il tente de prévenir la chute d'une personne âgée, de traduire la langue des signes ou de contrôler un humain virtuel, l'analyse de gestes est un vaste domaine de recherche qui s'attelle à reconnaître, classifier, segmenter, indexer ou encore évaluer différents types de mouvements. Cependant, peu de travaux se concentrent sur cette dernière approche d'évaluation. Ce travail de thèse propose de mettre en place un outil d’évaluation automatique et générique d’un geste sportif, reposant sur l’utilisation d’une base de données de gestes experts acquis via un système de capture de mouvements. Afin d’extraire un mouvement de référence, l’algorithme de déformation temporelle dynamique (DTW) est considéré pour aligner puis moyenner les gestes. Les méthodes d’alignements et de moyennage de séries temporelles se confrontant aux conséquences néfastes de chemins de déformation du DTW pathologiques, des contraintes locales sont ajoutées et donnent lieu à un nouvel algorithme appelé CDBA. La qualité d’un geste est estimée spatialement et temporellement à chaque instant et pour chaque membre par comparaison avec le geste de référence et pondérée par la dispersion des données expertes autour de ce geste moyen. Le processus ainsi mis en place est validé à partir de gestes de karaté et de tennis annotés par des entraîneurs. Un premier prototype d’outil d’entraînement en ligne est finalement proposé et laisse entrevoir les potentialités d’usage qui pourraient être menées à la suite de ce travail. / Either to reduce falling risks in elderly people, to translate the sign language or to control a virtual human being, gesture analysis is thriving research field that aims at recognizing, classifying, segmenting, indexing and evaluating different types of motions. As few studies tackle the evaluation process, this PhD focuses on the design of an autonomous system for the generic evaluation of sport-related gestures. The tool is trained on the basis of experts’ motions recorded with a motion capture system. Dynamic Time Warping (DTW) is deployed to obtain a reference gesture thanks to data alignment and averaging. Nevertheless, this standard method suffers from pathological paths issues that reduce its effectiveness. For this reason, local constraints are added to the new DTW-based algorithm, called CDBA (Constrained DTW Barycenter Averaging). At each time step and for each limb, the quality of a gesture is spatially and temporally assessed. Each new motion is compared to the reference gesture and weighted in terms of data dispersion around the reference.The process is validated on annotated karate and tennis databases. A first online training prototype is given in order to prompt further research on this subject.

Gesture recognition is becoming increasingly popular as an input mechanism for human-computer interfaces. The availability of MEMS (Micro-Electromechanical System) 3-axis linear accelerometers allows for the design of an inexpensive mobile gesture recognition system. Wearable inertial sensors are a low-cost, low-power solution to recognize gestures and, more generally, track the movements of a person. Gesture recognition algorithms have traditionally only been implemented in cases where ample system resources are available, i.e. on desktop computers with fast processors and large amounts of memory. In the cases where a gesture recognition algorithm has been implemented on a resource-constrained device, only the simplest algorithms were implemented to recognize only a small set of gestures. Current gesture recognition technology can be improved by making algorithms faster, more robust, and more accurate. The most dramatic results in optimization are obtained by completely changing an algorithm to decrease the number of computations. Algorithms can also be optimized by profiling or timing the different sections of the algorithm to identify problem areas. Gestures have two aspects of signal characteristics that make them difficult to recognize: segmentation ambiguity and spatio-temporal variability. Segmentation ambiguity refers to not knowing the gesture boundaries, and therefore reference patterns have to be matched with all possible segments of input signals. Spatio-temporal variability refers to the fact that each repetition of the same gesture varies dynamically in shape and duration, even for the same gesturer. The objective of this study was to evaluate the various gesture recognition algorithms currently in use, after which the most suitable algorithm was optimized in order to implement it on a mobile device. Gesture recognition techniques studied include hidden Markov models, artificial neural networks and dynamic time warping. A dataset for evaluating the gesture recognition algorithms was gathered using a mobile device’s embedded accelerometer. The algorithms were evaluated based on computational efficiency, recognition accuracy and storage efficiency. The optimized algorithm was implemented in a user application on the mobile device to test the empirical validity of the study. / Dissertation (MEng)--University of Pretoria, 2009. / Electrical, Electronic and Computer Engineering / unrestricted

Dans cette thèse nous nous intéressons à des problèmes d’apprentissage automatique dans le cadre de sorties structurées avec une structure séquentielle. D’une part, nous considérons le problème de l’apprentissage de mesure de similarité pour deux tâches : (i) la détection de rupture dans des signaux multivariés et (ii) le problème de déformation temporelle entre paires de signaux. Les méthodes généralement utilisées pour résoudre ces deux problèmes dépendent fortement d’une mesure de similarité. Nous apprenons une mesure de similarité à partir de données totalement étiquetées. Nous présentons des algorithmes usuels de prédiction structuré, efficaces pour effectuer l’apprentissage. Nous validons notre approche sur des données réelles venant de divers domaines. D’autre part, nous nous intéressons au problème de la faible supervision pour la tâche d’alignement d’un enregistrement audio sur la partition jouée. Nous considérons la partition comme une représentation symbolique donnant (i) une information complète sur l’ordre des symboles et (ii) une information approximative sur la forme de l’alignement attendu. Nous apprenons un classifieur pour chaque symbole avec ces informations. Nous développons une méthode d’apprentissage fondée sur l’optimisation d’une fonction convexe. Nous démontrons la validité de l’approche sur des données musicales. / In this manuscript, we consider structured machine learning problems and consider more precisely the ones involving sequential structure. In a first part, we consider the problem of similarity measure learning for two tasks where sequential structure is at stake: (i) the multivariate change-point detection and (ii) the time warping of pairs of time series. The methods generally used to solve these tasks rely on a similarity measure to compare timestamps. We propose to learn a similarity measure from fully labelled data, i.e., signals already segmented or pairs of signals for which the optimal time warping is known. Using standard structured prediction methods, we present algorithmically efficient ways for learning. We propose to use loss functions specifically designed for the tasks. We validate our approach on real-world data. In a second part, we focus on the problem of weak supervision, in which sequential data are not totally labeled. We focus on the problem of aligning an audio recording with its score. We consider the score as a symbolic representation giving: (i) a complete information about the order of events or notes played and (ii) an approximate idea about the expected shape of the alignment. We propose to learn a classifier for each note using this information. Our learning problem is based onthe optimization of a convex function that takes advantage of the weak supervision and of the sequential structure of data. Our approach is validated through experiments on the task of audio-to-score on real musical data.

This diploma thesis deals with cluster analysis for long-term electrocardiograms (ECG) clustering. The linear filtration is used for ECG preprocessing. The ECG sign segmenting in single heart cycles is based on the detection QRS complex and consequently to an application of dynamic time warping algorithms. To an application of all these mentioned processes and to results interpretation, a program called Cluster analysis has been created in the Matlab background. The results of this diploma thesis confirm that cluster analysis is able to distinguish cardiac arrhythmias which are typical with their shape distinctness of normal heart cycles.

Voice user interfaces have been growing in popularity and with them an interest for open vocabulary keyword spotting. In this thesis we focus on one particular approach to open vocabulary keyword spotting, query by example keyword spotting. Three types of query by example keyword spotting approaches are described and evaluated: sequence distances, speech to phonemes and deep distance learning. Evaluation is done on a series of custom tasks designed to measure a variety of aspects. The Google Speech Commands benchmark is used for evaluation as well, this to make it more comparable to existing works. From the results, the deep distance learning approach seem most promising in most environments except when memory is very constrained; in which sequence distances might be considered. The speech to phonemes methods is lacking in the usability evaluation. / Röstgränssnitt har växt i populäritet och med dem ett intresse för öppenvokabulärnyckelordsigenkänning. I den här uppsatsen fokuserar vi på en specifik form av öppenvokabulärnyckelordsigenkänning, den s.k nyckelordsigenkänning- genom- exempel. Tre typer av nyckelordsigenkänning- genom- exempel metoder beskrivs och utvärderas: sekvensavstånd, tal till fonem samt djupavståndsinlärning. Utvärdering görs på konstruerade uppgifter designade att mäta en mängd olika aspekter hos metoderna. Google Speech Commands data används för utvärderingen också, detta för att göra det mer jämförbart mot existerade arbeten. Från resultaten framgår det att djupavståndsinlärning verkar mest lovande förutom i miljöer där resurser är väldigt begränsade; i dessa kan sekvensavstånd vara av intresse. Tal till fonem metoderna visar brister i användningsuvärderingen.

With the increased use of Android smartphones, the Android Pattern Lock graphical password has become commonplace. The Android Pattern Lock is advantageous in that it is easier to remember and is more complex than a five digit numeric code. However, it is susceptible to a number of attacks, both direct and indirect. This fact shows that the Android Pattern Lock by itself is not enough to protect personal devices. Other means of protection are needed as well. In this thesis I have investigated five methods for the analysis of biometric data as an unnoticable second verification step of the Android Pattern Lock. The methods investigated are the euclidean barycentric anomaly detector, the dynamic time warping barycentric anomaly detector, a one-class support vector machine, the local outlier factor anomaly detector and a normal distribution based anomaly detector. The models were trained using an online training strategy to enable adaptation to changes in the user input behaviour. The model hyperparameters were fitted using a data set with 85 users. The models are then tested with other data sets to illustrate how different phone models and patterns affect the results.        The euclidean barycentric anomaly detector and dynamic time warping (DTW) barycentric anomaly detector have a sub 10 \% equal error rate in both mean and median, while the other three methods have an equal error rate between 15 \% and 20 \% in mean and median. The higher performance of the euclidean and DTW barycentric anomaly detector is likely because they account for the time series nature of the data, while the other methods do not. Each user in the data set have provided each pattern at most 50 times, meaning that the long-term effects of user adaptation could not be studied.

In this study, time series decomposition techniques are used in conjunction with Kmeans clustering and Hierarchical clustering, two well-known clustering algorithms, to climate data. Their implementation and comparisons are then examined. The main objective is to identify similar climate trends and group geographical areas with similar environmental conditions. Climate data from specific places are collected and analyzed as part of the project. The time series is then split into trend, seasonality, and residual components. In order to categorize growing regions according to their climatic inclinations, the deconstructed time series are then submitted to K-means clustering and Hierarchical clustering with dynamic time warping. In order to understand how different regions’ climates compare to one another and how regions cluster based on the general trend of the temperature profile over the course of the full growing season as opposed to the seasonality component for the various locations, the created clusters are evaluated.

This thesis proposes a method to reconstruct a frontal facial video basedon encoding done with the facial profile of another video sequence.The reconstructed facial video will have the similar facial expressionchanges as the changes in the profile video. First, the profiles for boththe reference video and for the test video are captured by edge detection.Then, asymmetrical principal component analysis is used to model thecorrespondence between the profile and the frontal face. This allows en-coding from a profile and decoding of the frontal face of another video.Another solution is to use dynamic time warping to match the profilesand select the best matching corresponding frontal face frame for re-construction. With this method, we can reconstructed the test frontalvideo to make it have the similar changing in facial expressions as thereference video. To improve the quality of the result video, Local Lin-ear Embedding is used to give the result video a smoother transitionbetween frames.

No description available.