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

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.

Avec l'augmentation considérable d'acquisitions de données temporelles dans les dernières décennies comme les systèmes GPS, les séquences vidéo ou les suivis médicaux de pathologies ; le besoin en algorithmes de traitement et d'analyse efficaces d'acquisition longitudinales n'a fait qu'augmenter. Dans cette thèse, nous proposons une extension du formalisme mean-shift, classiquement utilisé en traitement d'images, pour le groupement de séries temporelles multidimensionnelles. Nous proposons aussi un algorithme de groupement hiérarchique des séries temporelles basé sur la mesure de dynamic time warping afin de prendre en compte les déphasages temporels. Ces choix ont été motivés par la nécessité d'analyser des images acquises en imagerie par résonance magnétique sur des patients atteints de sclérose en plaques. Cette maladie est encore très méconnue tant dans sa genèse que sur les causes des handicaps qu'elle peut induire. De plus aucun traitement efficace n'est connu à l'heure actuelle. Le besoin de valider des hypothèses sur les lésions de sclérose en plaque nous a conduit à proposer des méthodes de groupement de séries temporelles ne nécessitant pas d'a priori sur le résultat final, méthodes encore peu développées en traitement d'images. / Due to the dramatic increase of longitudinal acquisitions in the past decades such as video sequences, global positioning system (GPS) tracking or medical follow-up, many applications for time-series data mining have been developed. Thus, unsupervised time-series data mining has become highly relevant with the aim to automatically detect and identify similar temporal patterns between time-series. In this work, we propose a new spatio-temporal filtering scheme based on the mean-shift procedure, a state of the art approach in the field of image processing, which clusters multivariate spatio-temporal data. We also propose a hierarchical time-series clustering algorithm based on the dynamic time warping measure that identifies similar but asynchronous temporal patterns. Our choices have been motivated by the need to analyse magnetic resonance images acquired on people affected by multiple sclerosis. The genetics and environmental factors triggering and governing the disease evolution, as well as the occurrence and evolution of individual lesions, are still mostly unknown and under intense investigation. Therefore, there is a strong need to develop new methods allowing automatic extraction and quantification of lesion characteristics. This has motivated our work on time-series clustering methods, which are not widely used in image processing yet and allow to process image sequences without prior knowledge on the final results.

The thesis deals with one of the non-linear methods for signal processing - dynamic time warping (DTW). The method observes shape changes, which should be used in biomedical signals processing. The thesis involves the method description and consecution for finding DTW optimal way. The method is applied on the number series in the edutainment program, on the group of simulated signals and real electrocardiograms (ECG). ECG recordings were gained by performing experiments on the Masaryk University and their aim was clarifying the influence of voltage-sensitive dye on the heart tissue. One-lead ECG was described in time domain, frequency domain, time-frequency domain and subsequently remitted to DTW algorithm. The method outcomes evaluates the diversity rate of ECG signals obtained in each experiment stages. During the data evaluation were followed up the changes in process of the tension-sensible paint application and the stage of scouring toward control. The difference of elaborating signals group was verified in the time domain (37,5 %), in the frequency domain (75 %) and in the time-frequency domain (25 %). However, due to the small data group was not possible to explicitly approve the activity of voltage-sensitive dye on the heart tissue and to determinate limiting value of minimum algorithm way DTW for each heart round electrocardiogram classification. In the more data group analysis it is supposed to manifest the trend of growth heart round ECG differences in the stage of staining toward the stage of scouring.

The thesis is focused on the recognition methods study used in one-dimensional signal processing. A lot of recognition methods exist, this thesis briefly describes the principle of some of them, e.g. artificial neural networks, fuzzy systems, expert systems and decision trees. Dynamic time warping (DTW) method has been chosen for signal processing available from UBMI database. DTW can be used as a non-linear signal processing method. The result of this method is to determine the similarity of two compared signals on the basis of their distance calculation. One of the reasons for choosing this method was the possibility of various length signal processing. The principle of the method as well as the calculation of the distance between two input data sequences is described in the thesis. DTW path finding method is also mentioned. The method was applied on randomly selected numbers and a set of simulated signals. The method was applied to ECG and action potential signals recorded on the isolated rabbit heart. DTW was used to evaluate shape changes of these signals in repeated phases of the experiment known as ischemia and reperfusion. Selected cardiac cycles were detected and included into different experiment phases on the basis of calculated distance results using DTW. Sensitivity was selected as an evaluative criterion of this classification method. It reached a value of 65%. DTW algorithm was further tested on the selected cardiac cycle mapping to the corresponding minute record in the selected experiment phase. It reached a sensitivity of 68.3%. The motion artifact appearance was monitored using DTW on AP signals. The method functioned more precisely on signals measured in ischemia phases. Along with the above mentioned, the thesis discusses all aspects of heart electrical manifestation activities called as ECG signals and action potentials, such as origin, propagation, recording, post-processing and measuring out.