Time series are ubiquitous in the day-by-day of human beings. A diversity of application domains generate data arranged in time, such as medicine, biology, economics, and signal processing. Due to the great interest in time series, a large variety of methods for mining temporal data has been proposed in recent decades. Several of these methods have one characteristic in common: in their cores, there is a (dis)similarity function used to compare the time series. Dynamic Time Warping (DTW) is arguably the most relevant, studied and applied distance measure for time series analysis. The main drawback of DTW is its computational complexity. At the same time, there are a significant number of data mining tasks, such as motif discovery, which requires a quadratic number of distance computations. These tasks are time intensive even for less expensive distance measures, like the Euclidean Distance. This thesis focus on developing fast algorithms that allow large-scale analysis of temporal data, using similarity-based methods for time series data mining. The contributions of this work have implications in several data mining tasks, such as classification, clustering and motif discovery. Specifically, the main contributions of this thesis are the following: (i) an algorithm to speed up the exact DTW calculation and its embedding into the similarity search procedure; (ii) a novel DTW-based spurious prefix and suffix invariant distance; (iii) a music similarity representation with implications on several music mining tasks, and a fast algorithm to compute it, and; (iv) an efficient and anytime method to find motifs and discords under the proposed prefix and suffix invariant DTW. / Séries temporais são ubíquas no dia-a-dia do ser humano. Dados organizados no tempo são gerados em uma infinidade de domínios de aplicação, como medicina, biologia, economia e processamento de sinais. Devido ao grande interesse nesse tipo de dados, diversos métodos de mineração de dados temporais foram propostos nas últimas décadas. Muitos desses métodos possuem uma característica em comum: em seu núcleo, há uma função de (dis)similaridade utilizada para comparar as séries. Dynamic Time Warping (DTW) é indiscutivelmente a medida de distância mais relevante na análise de séries temporais. A principal dificuldade em se utilizar a DTW é seu alto custo computacional. Ao mesmo tempo, algumas tarefas de mineração de séries temporais, como descoberta de motifs, requerem um alto número de cálculos de distância. Essas tarefas despendem um grande tempo de execução, mesmo utilizando-se medidas de distância menos custosas, como a distância Euclidiana. Esta tese se concentra no desenvolvimento de algoritmos eficientes que permitem a análise de dados temporais em larga escala, utilizando métodos baseados em similaridade. As contribuições desta tese têm implicações em variadas tarefas de mineração de dados, como classificação, agrupamento e descoberta de padrões frequentes. Especificamente, as principais contribuições desta tese são: (i) um algoritmo para acelerar o cálculo exato da distância DTW e sua incorporação ao processo de busca por similaridade; (ii) um novo algoritmo baseado em DTW para prover invariância a prefixos e sufixos espúrios no cálculo da distância; (iii) uma representação de similaridade musical com implicações em diferentes tarefas de mineração de dados musicais e um algoritmo eficiente para computá-la; (iv) um método eficiente e anytime para encontrar motifs e discords baseado na medida DTW invariante a prefixos e sufixos.

Time series are ubiquitous in the day-by-day of human beings. A diversity of application domains generate data arranged in time, such as medicine, biology, economics, and signal processing. Due to the great interest in time series, a large variety of methods for mining temporal data has been proposed in recent decades. Several of these methods have one characteristic in common: in their cores, there is a (dis)similarity function used to compare the time series. Dynamic Time Warping (DTW) is arguably the most relevant, studied and applied distance measure for time series analysis. The main drawback of DTW is its computational complexity. At the same time, there are a significant number of data mining tasks, such as motif discovery, which requires a quadratic number of distance computations. These tasks are time intensive even for less expensive distance measures, like the Euclidean Distance. This thesis focus on developing fast algorithms that allow large-scale analysis of temporal data, using similarity-based methods for time series data mining. The contributions of this work have implications in several data mining tasks, such as classification, clustering and motif discovery. Specifically, the main contributions of this thesis are the following: (i) an algorithm to speed up the exact DTW calculation and its embedding into the similarity search procedure; (ii) a novel DTW-based spurious prefix and suffix invariant distance; (iii) a music similarity representation with implications on several music mining tasks, and a fast algorithm to compute it, and; (iv) an efficient and anytime method to find motifs and discords under the proposed prefix and suffix invariant DTW. / Séries temporais são ubíquas no dia-a-dia do ser humano. Dados organizados no tempo são gerados em uma infinidade de domínios de aplicação, como medicina, biologia, economia e processamento de sinais. Devido ao grande interesse nesse tipo de dados, diversos métodos de mineração de dados temporais foram propostos nas últimas décadas. Muitos desses métodos possuem uma característica em comum: em seu núcleo, há uma função de (dis)similaridade utilizada para comparar as séries. Dynamic Time Warping (DTW) é indiscutivelmente a medida de distância mais relevante na análise de séries temporais. A principal dificuldade em se utilizar a DTW é seu alto custo computacional. Ao mesmo tempo, algumas tarefas de mineração de séries temporais, como descoberta de motifs, requerem um alto número de cálculos de distância. Essas tarefas despendem um grande tempo de execução, mesmo utilizando-se medidas de distância menos custosas, como a distância Euclidiana. Esta tese se concentra no desenvolvimento de algoritmos eficientes que permitem a análise de dados temporais em larga escala, utilizando métodos baseados em similaridade. As contribuições desta tese têm implicações em variadas tarefas de mineração de dados, como classificação, agrupamento e descoberta de padrões frequentes. Especificamente, as principais contribuições desta tese são: (i) um algoritmo para acelerar o cálculo exato da distância DTW e sua incorporação ao processo de busca por similaridade; (ii) um novo algoritmo baseado em DTW para prover invariância a prefixos e sufixos espúrios no cálculo da distância; (iii) uma representação de similaridade musical com implicações em diferentes tarefas de mineração de dados musicais e um algoritmo eficiente para computá-la; (iv) um método eficiente e anytime para encontrar motifs e discords baseado na medida DTW invariante a prefixos e sufixos.

The present thesis utilises dynamic time warping and cluster analysis with the aim of discovering different touristic profiles. GPS data of cruise passengers intra-destination movement at the destination of Visby, Gotland, was used in the analysis. Further stop detection was performed so as to compare stop activity and stop allocation between the clusters. Four tourist profiles were derived by juxtaposing the category of attractions/areas where high stop densities were found, with the spatial dispersal of stop activity, denoted as either exhibiting a concentrated or exploring pattern. Some key influencers of tourists' spatio-temporal behaviour were also identified. These included whether the cruise passengers appeared to have taken some mode of transportation upon their on-shore visit, whether the area was dense in activities/facilities oriented towards tourists and the time spent at the destination. The contribution of this thesis is twofold. First this thesis contributes to previous research by developing and testing a methodological approach utilising dynamic time warping to investigate cruise passengers' spatio-temporal behaviour at a destination. Second, the results of the thesis may aid destination managers in finding tools and strategies that are tailored after the unique opportunities and challenges posed by different tourist profiles.

This thesis explores the feasibility of clustering mixed data and unevenly spaced time series for customer segmentation. The proposed method implements the Gower dissimilarity as the local distance function in dynamic time warping to calculate dissimilarities between mixed data time series. The time series are then clustered with k−medoids and the clusters are evaluated with the silhouette score and t−SNE. The study further investigates the use of a time warping regularisation parameter. It is derived that implementing time as a feature has the same effect as penalising time warping, andtherefore time is implemented as a feature where the feature weight is equivalent to a regularisation parameter. The results show that the proposed method successfully identifies clusters in customer transaction data provided by Nordea. Furthermore, the results show a decrease in the silhouette score with an increase in the regularisation parameter, suggesting that the time at which a transaction occurred might not be of relevance to the given dataset. However, due to the method’s high computational complexity, it is limited to relatively small datasets and therefore a need exists for a more scalable and efficient clustering technique. / Denna uppsats utforskar klustring av ojämnt fördelade tidsserier med numeriska och kategoriska variabler för kundsegmentering. Den föreslagna metoden implementerar Gower dissimilaritet som avståndsfunktionen i dynamic time warping för att beräkna dissimilaritet mellan tidsserierna. Tidsserierna klustras sedan med k-medoids och klustren utvärderas med silhouette score och t-SNE. Studien undersökte vidare användningen av en regulariserings parameter. Det härledes att implementering av tid som en egenskap hade samma effekt som att bestraffa dynamic time warping, och därför implementerades tid som en egenskap där dess vikt är ekvivalent med en regulariseringsparameter.  Resultaten visade att den föreslagna metoden lyckades identifiera kluster i transaktionsdata från Nordea. Vidare visades det att silhouette score minskade då regulariseringsparametern ökade, vilket antyder att tiden transaktion då en transaktion sker inte är relevant för det givna datan. Det visade sig ytterligare att metoden är begränsad till reltaivt små dataset på grund av dess höga beräkningskomplexitet, och därför finns det behov av att utforksa en mer skalbar och effektiv klusteringsteknik.

Dynamic Time Warping (DTW) é uma técnica do tipo pattern matching para reconhecimento de padrões de voz, sendo baseada no alinhamento temporal de um sinal com os diversos modelos de referência. Uma desvantagem da DTW é o seu alto custo computacional. Este trabalho apresenta uma versão da DTW que, utilizando a Transformada Wavelet Discreta (DWT), reduz a sua complexidade. O desempenho obtido com a proposta foi muito promissor, ganhando em termos de velocidade de reconhecimento e recursos de memória consumidos, enquanto a precisão da DTW não é afetada. Os testes foram realizados com alguns fonemas extraídos da base de dados TIMIT do Linguistic Data Consortium (LDC) / Dynamic TimeWarping (DTW) is a pattern matching technique for speech recognition, that is based on a temporal alignment of the input signal with the template models. One drawback of this technique is its high computational cost. This work presents a modified version of the DTW, based on the DiscreteWavelet Transform (DWT), that reduces the complexity of the original algorithm. The performance obtained with the proposed algorithm is very promising, improving the recognition in terms of time and memory allocation, while the precision is not affected. Tests were performed with speech data collected from TIMIT corpus provided by Linguistic Data Consortium (LDC).

Les séries temporelles d’images satellites (STIS) sont des données cruciales pour l’observation de la terre. Les séries temporelles actuelles sont soit des séries à haute résolution temporelle (Spot-Végétation, MODIS), soit des séries à haute résolution spatiale (Landsat). Dans les années à venir, les séries temporelles d’images satellites à hautes résolutions spatiale et temporelle vont être produites par le programme Sentinel de l’ESA. Afin de traiter efficacement ces immenses quantités de données qui vont être produites (par exemple, Sentinel-2 couvrira la surface de la terre tous les cinq jours, avec des résolutions spatiales allant de 10m à 60m et disposera de 13 bandes spectrales), de nouvelles méthodes ont besoin d’être développées. Cette thèse se focalise sur la comparaison des profils d’évolution radiométrique, et plus précisément la mesure de similarité « Dynamic Time Warping », qui constitue un outil permettant d’exploiter la structuration temporelle des séries d’images satellites. / Satellite Image Time Series are becoming increasingly available and will continue to do so in the coming years thanks to the launch of space missions, which aim at providing a coverage of the Earth every few days with high spatial resolution (ESA’s Sentinel program). In the case of optical imagery, it will be possible to produce land use and cover change maps with detailed nomenclatures. However, due to meteorological phenomena, such as clouds, these time series will become irregular in terms of temporal sampling. In order to consistently handle the huge amount of information that will be produced (for instance, Sentinel-2 will cover the entire Earth’s surface every five days, with 10m to 60m spatial resolution and 13 spectral bands), new methods have to be developed. This Ph.D. thesis focuses on the “Dynamic Time Warping” similarity measure, which is able to take the most of the temporal structure of the data, in order to provide an efficient and relevant analysis of the remotely observed phenomena.

Microsoft Kinect įrenginys išleistas tik 2010 metais. Jis buvo skirtas Microsoft Xbox 360 vaizdo žaidimų konsolei, vėliau 2012 metais buvo pristatytas Kinect ir Windows personaliniams kompiuteriams. Taigi tai palyginus naujas įrenginys ir aktualus šiai dienai. Daugiausiai yra sukurta kompiuterinių žaidimų, kurie naudoja Microsoft Kinect įrenginį, bet šį įrenginį galima panaudoti daug plačiau ne tik žaidimuose, viena iš sričių tai sportas, konkrečiau treniruotės, kurias būtų galima atlikti namuose. Šiuo metu pasaulyje yra programinės įrangos, žaidimų, sportavimo programų, kuri leidžia kontroliuoti treniruočių eigą sekdama ar žmogus teisingai atlieka treniruotėms numatytus judesius. Kadangi Lietuvoje panašios programinės įrangos nėra, taigi reikia sukurti įrangą, kuri leistų Lietuvos treneriams kurti treniruotes orientuotas į šio įrenginio panaudojimą. Šio darbo pagrindinis tikslas yra atlikti Kinect įrenginiui skirtų gestų atpažinimo algoritmų tyrimą, kaip tiksliai jie gali atpažinti gestus ar gestą. Pagrindinis dėmesys skiriamas šiai problemai, taip pat keliami, bet netyrinėjami kriterijai kaip atpažinimo laikas, bei realizacijos sunkumas. Šiame darbe sukurta programa, judesius bei gestus atpažįsta naudojant Golden Section Search algoritmą. Algoritmas palygina du modelius ar šablonus, ir jei neranda atitikmens, tai pirmasis šablonas šiek tiek pasukamas ir lyginimo procesas paleidžiamas vėl, taipogi tam tikro kintamojo dėka galime keisti algoritmo tikslumą. Taipogi... [toliau žr. visą tekstą] / Microsoft Kinect device was released in 2010. It was designed for Microsoft Xbox 360 gaming console, later on in 2012 was presented Kinect device for Windows personal computer. So this device is new and current. Many games has been created for Microsoft Kinect device, but this device could be used not only in games, one of the areas where we can use it its sport, specific training, which can be performed at home. At this moment in world are huge variety of games, software, training programs which allows user to control training course by following a person properly perform training provided movements. Since in Lithuania similar software is not available, so it is necessary to create software that would allow Lithuania coaches create training focused on the use of this device. The main goal of this work is to perform research of the Kinect device gesture recognition algorithms to study exactly how they can recognize gestures or gesture. It will focus on this issue mainly, but does not address the criteria for recognition as the time and difficulty of realization. In this paper, a program that recognizes movements and gestures are using the Golden section search algorithm. Algorhithm compares the two models or templates, and if it can not find a match, this is the first template slightly rotated and comparison process is started again, also a certain variable helping, we can modify the algorithm accuracy. Also for comparison we can use Hidden Markov models algorhithm received... [to full text]

Submitted by Jordan (jordanbiblio@gmail.com) on 2017-05-04T13:38:27Z No. of bitstreams: 1 DISS_2015_Gracyeli Santos Souza Guarienti.pdf: 4160382 bytes, checksum: 066e507b4df1c012a091983043416a9b (MD5) / Approved for entry into archive by Jordan (jordanbiblio@gmail.com) on 2017-05-04T15:41:01Z (GMT) No. of bitstreams: 1 DISS_2015_Gracyeli Santos Souza Guarienti.pdf: 4160382 bytes, checksum: 066e507b4df1c012a091983043416a9b (MD5) / Made available in DSpace on 2017-05-04T15:41:01Z (GMT). No. of bitstreams: 1 DISS_2015_Gracyeli Santos Souza Guarienti.pdf: 4160382 bytes, checksum: 066e507b4df1c012a091983043416a9b (MD5) Previous issue date: 2015-05-27 / CAPES / Variáveis climatológicas podem ser estudadas a partir de seu comportamento temporal. Nesse sentido, este trabalho desenvolveu uma técnica computacional de processamento espaço-temporal de variáveis climatológicas que utiliza busca por similaridade e a possibilidade de comparação em várias resoluções temporais. Para demonstração do uso da técnica e verificação dos resultados, sequências de processamento foram aplicadas em séries de precipitação de um período de quinze anos usando os algoritmos Dynamic Time Warping (DTW) e wavelet em quatro biomas: Amazônia, Cerrado, Pantanal e Mata Atlântica. A técnica foi aplicada nas séries originais e em suas wavelets, com resoluções temporais mensal, semestral, anual e quinze anos de forma a permitir que análises específicas em cada resolução possam ser aplicadas. A flexibilidade e a variedade de resoluções temporais permitidas pela técnica torna possível acrescentar aos processos de monitoramento ambiental novas perspectivas em tomadas de decisão. / Climatic variables can be studied from its temporal behavior. In this sense, this study developed a temporal analysis technique for climatological variables using similarity search and the possibility of comparison in various temporal resolution levels. For the income statement, several processing sequences were applied in series of precipitation a period of fifteen years using the Dynamic Time Warping algorithm (DTW) and wavelet on four biomes: Amazon, Cerrado, Pantanal and Atlantic Forest. The technique was applied to the original data and wavelets, in the temporal resolution of time monthly, semi-annual, annual and fifteen years enable visualization and comparison of data on these different scales. Application the technique developed in this study, provide new perspectives to decision-making in environmental monitoring processes.

Dynamic Time Warping (DTW) é uma técnica do tipo pattern matching para reconhecimento de padrões de voz, sendo baseada no alinhamento temporal de um sinal com os diversos modelos de referência. Uma desvantagem da DTW é o seu alto custo computacional. Este trabalho apresenta uma versão da DTW que, utilizando a Transformada Wavelet Discreta (DWT), reduz a sua complexidade. O desempenho obtido com a proposta foi muito promissor, ganhando em termos de velocidade de reconhecimento e recursos de memória consumidos, enquanto a precisão da DTW não é afetada. Os testes foram realizados com alguns fonemas extraídos da base de dados TIMIT do Linguistic Data Consortium (LDC) / Dynamic TimeWarping (DTW) is a pattern matching technique for speech recognition, that is based on a temporal alignment of the input signal with the template models. One drawback of this technique is its high computational cost. This work presents a modified version of the DTW, based on the DiscreteWavelet Transform (DWT), that reduces the complexity of the original algorithm. The performance obtained with the proposed algorithm is very promising, improving the recognition in terms of time and memory allocation, while the precision is not affected. Tests were performed with speech data collected from TIMIT corpus provided by Linguistic Data Consortium (LDC).

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Images captured in endoscopy examinations show some distortion, the radial is the most visible. The radial distortion appears in images due to lens used in endoscopes. When a doctor or researcher is analyzing a distorted image, he can not see the exact size of an organ, tumor or lesion, due the magnification in the center of the image and a contraction in the peripheral regions caused by such distortion. This paper aims to propose a new method for correction of radial distortion in endoscopic images. The proposed method is based on concepts of Morphing and Warping, which are techniques widely used in computer graphics to transform the image of one person to another or to cause objects deformations. The system presents the advantage of automatic application of these techniques, since the vast majority of correction algorithms need user interaction. The proposed method uses a pattern image, created for the calibration of the transformations that are applied to the images of endoscopy. The developed system receives the pattern image captured by endoscope, divides the image into a triangular mesh, make the matching of each triangle of the meshes and store the affine transformations of each triangular region of the mesh separately. After calibration, the affine transformations of each triangular region are used in real image of endoscopic examinations performed by the same endoscope used for calibration to correct the images. Finally, the method was compared with others in the literature and has been made quantitative and qualitative analysis with the results. / Imagens capturadas em exames de endoscopia apresentam algumas distorções, sendo a distorção radial a principal. A distorção radial surge na imagem devido ao sistema de lentes utilizado nos endoscópios. Quando um médico ou pesquisador está analisando uma imagem distorcida, não consegue perceber qual o tamanho exato de um órgão, lesão ou tumor, pois tal distorção causa uma ampliação no centro da imagem e uma contração nas regiões periféricas. Este trabalho tem como objetivo propor um novo método para a correção de distorções radiais em imagens de endoscopia. O método proposto baseia-se em conceitos de Morphing e Warping, que são técnicas bastante utilizadas em computação gráfica para transformar a imagem de uma pessoa em outra ou para causar deformações em objetos. O sistema apresentado tem como diferencial a aplicação automática destas técnicas, visto que a grande maioria de algoritmos que fazem uso delas funciona com interação do usuário. O método proposto utiliza uma imagem padrão, criada para a calibração das transformações que serão aplicadas nas imagens de exames de endoscopia. O sistema desenvolvido recebe a imagem padrão capturada por endoscópio, divide a imagem em uma malha triangular, faz a correspondência de cada triângulo desta malha com a malha da imagem padrão original e armazena as transformações afins em cada região da malha separadamente, transformando assim a imagem capturada na imagem original. Após a calibração, as mesmas transformações afins armazenadas para cada elemento triangular da malha são utilizadas em imagem reais de exames endoscópicos feitos pelo mesmo endoscópio utilizado na calibração, para corrigir a deformação. Por fim, o método desenvolvido foi comparado com outros da literatura e foram feitas análises quantitativas e qualitativas dos resultados obtidos.