The goal of this thesis is the development of a fast and robust algorithm that is able to detect patterns in flow fields independent from their orientation and adequately visualize the results for a human user. This thesis is an interdisciplinary work in the field of vector field visualization and the field of pattern recognition. A vector field can be best imagined as an area or a volume containing a lot of arrows. The direction of the arrow describes the direction of a flow or force at the point where it starts and the length its velocity or strength. This builds a bridge to vector field visualization, because drawing these arrows is one of the fundamental techniques to illustrate a vector field. The main challenge of vector field visualization is to decide which of them should be drawn. If you do not draw enough arrows, you may miss the feature you are interested in. If you draw too many arrows, your image will be black all over. We assume that the user is interested in a certain feature of the vector field: a certain pattern. To prevent clutter and occlusion of the interesting parts, we first look for this pattern and then apply a visualization that emphasizes its occurrences. In general, the user wants to find all instances of the interesting pattern, no matter if they are smaller or bigger, weaker or stronger or oriented in some other direction than his reference input pattern. But looking for all these transformed versions would take far too long. That is why, we look for an algorithm that detects the occurrences of the pattern independent from these transformations. In the second part of this thesis, we work with moment invariants. Moments are the projections of a function to a function space basis. In order to compare the functions, it is sufficient to compare their moments. Normalization is the act of transforming a function into a predefined standard position. Moment invariants are characteristic numbers like fingerprints that are constructed from moments and do not change under certain transformations. They can be produced by normalization, because if all the functions are in one standard position, their prior position has no influence on their normalized moments. With this technique, we were able to solve the pattern detection task for 2D and 3D flow fields by mathematically proving the invariance of the moments with respect to translation, rotation, and scaling. In practical applications, this invariance is disturbed by the discretization. We applied our method to several analytic and real world data sets and showed that it works on discrete fields in a robust way.

The availability of a scalable and explainable rule extraction technique via motif discovery is crucial for identifying the health states of a system. Such a technique can enable the creation of a repository of normal and abnormal states of the system and identify the system’s state as we receive data. In complex systems such as ECG, each activity session can consist of a long sequence of motifs that form different global structures. As a result, applying machine learning algorithms without first identifying the local patterns is not feasible and would result in low performance. Thus, extracting unique local motifs and establishing a database of prototypes or signatures is a crucial first step in analyzing long temporal data that reduces the computational cost and overcomes imbalanced data. The present research aims to streamline the extraction of motifs and add explainability to their analysis by identifying their differences. We have developed a novel framework for unsupervised motif extraction. We also offer a robust algorithm to identify unique motifs and their signatures, coupled with a proper distance metric to compare the signatures of partially similar motifs. Defining such distance metrics allows us to assign a degree of semblance between two motifs that may have different lengths or contain noise. We have tested our framework against five different datasets and observed excellent results, including extraction of motifs from 100 million samples in 8.02 seconds, 99.90% accuracy in self-supervised ECG data classification, and an average error of 16.66% in RUL prediction of bearing failure.

Event Stream Processing (ESP) Systeme überwachen kontinuierliche Datenströme, um benutzerdefinierte Queries auszuwerten. Die Herausforderung besteht darin, dass die Queryverarbeitung zustandsbehaftet ist und die Anzahl von Teilübereinstimmungen mit der Größe der verarbeiteten Events exponentiell anwächst. Die Dynamik von Streams und die Notwendigkeit, entfernte Daten zu integrieren, erschweren die Zustandsverwaltung. Erstens liefern heterogene Eventquellen Streams mit unvorhersehbaren Eingaberaten und Queryselektivitäten. Während Spitzenzeiten ist eine erschöpfende Verarbeitung unmöglich, und die Systeme müssen auf eine Best-Effort-Verarbeitung zurückgreifen. Zweitens erfordern Queries möglicherweise externe Daten, um ein bestimmtes Event für eine Query auszuwählen. Solche Abhängigkeiten sind problematisch: Das Abrufen der Daten unterbricht die Stream-Verarbeitung. Ohne eine Eventauswahl auf Grundlage externer Daten wird das Wachstum von Teilübereinstimmungen verstärkt. In dieser Dissertation stelle ich Strategien für optimiertes Zustandsmanagement von ESP Systemen vor. Zuerst ermögliche ich eine Best-Effort-Verarbeitung mittels Load Shedding. Dabei werden sowohl Eingabeeevents als auch Teilübereinstimmungen systematisch verworfen, um eine Latenzschwelle mit minimalem Qualitätsverlust zu garantieren. Zweitens integriere ich externe Daten, indem ich das Abrufen dieser von der Verwendung in der Queryverarbeitung entkoppele. Mit einem effizienten Caching-Mechanismus vermeide ich Unterbrechungen durch Übertragungslatenzen. Dazu werden externe Daten basierend auf ihrer erwarteten Verwendung vorab abgerufen und mittels Lazy Evaluation bei der Eventauswahl berücksichtigt. Dabei wird ein Kostenmodell verwendet, um zu bestimmen, wann welche externen Daten abgerufen und wie lange sie im Cache aufbewahrt werden sollen. Ich habe die Effektivität und Effizienz der vorgeschlagenen Strategien anhand von synthetischen und realen Daten ausgewertet und unter Beweis gestellt. / Event stream processing systems continuously evaluate queries over event streams to detect user-specified patterns with low latency. However, the challenge is that query processing is stateful and it maintains partial matches that grow exponentially in the size of processed events. State management is complicated by the dynamicity of streams and the need to integrate remote data. First, heterogeneous event sources yield dynamic streams with unpredictable input rates, data distributions, and query selectivities. During peak times, exhaustive processing is unreasonable, and systems shall resort to best-effort processing. Second, queries may require remote data to select a specific event for a pattern. Such dependencies are problematic: Fetching the remote data interrupts the stream processing. Yet, without event selection based on remote data, the growth of partial matches is amplified. In this dissertation, I present strategies for optimised state management in event pattern detection. First, I enable best-effort processing with load shedding that discards both input events and partial matches. I carefully select the shedding elements to satisfy a latency bound while striving for a minimal loss in result quality. Second, to efficiently integrate remote data, I decouple the fetching of remote data from its use in query evaluation by a caching mechanism. To this end, I hide the transmission latency by prefetching remote data based on anticipated use and by lazy evaluation that postpones the event selection based on remote data to avoid interruptions. A cost model is used to determine when to fetch which remote data items and how long to keep them in the cache. I evaluated the above techniques with queries over synthetic and real-world data. I show that the load shedding technique significantly improves the recall of pattern detection over baseline approaches, while the technique for remote data integration significantly reduces the pattern detection latency.

The global loss of biodiversity calls for robust large-scale diversity assessment. Biological diversity is a multi-faceted concept; defined as the “variety of life”, answering questions such as “How much is there?” or more precisely “Have we succeeded in reducing the rate of its decline?” is not straightforward. While various aspects of biodiversity give rise to numerous ways of quantification, we focus on temporal (and spatial) trends and their changes in species diversity. Traditional diversity indices summarise information contained in the species abundance distribution, i.e. each species' proportional contribution to total abundance. Estimated from data, these indices can be biased if variation in detection probability is ignored. We discuss differences between diversity indices and demonstrate possible adjustments for detectability. Additionally, most indices focus on the most abundant species in ecological communities. We introduce a new set of diversity measures, based on a family of goodness-of-fit statistics. A function of a free parameter, this family allows us to vary the sensitivity of these measures to dominance and rarity of species. Their performance is studied by assessing temporal trends in diversity for five communities of British breeding birds based on 14 years of survey data, where they are applied alongside the current headline index, a geometric mean of relative abundances. Revealing the contributions of both rare and common species to biodiversity trends, these "goodness-of-fit" measures provide novel insights into how ecological communities change over time. Biodiversity is not only subject to temporal changes, but it also varies across space. We take first steps towards estimating spatial diversity trends. Finally, processes maintaining biodiversity act locally, at specific spatial scales. Contrary to abundance-based summary statistics, spatial characteristics of ecological communities may distinguish these processes. We suggest a generalisation to a spatial summary, the cross-pair overlap distribution, to render it more flexible to spatial scale.

Le domaine de la modélisation du trafic routier vise à comprendre son évolution. Dans les dernières années, plusieurs modèles du trafic ont été proposés dans l’objectif de géolocaliser les embouteillages au sein du trafic, détecter des motifs dans le trafic routier, estimer l’état du trafic etc. La plupart des modèles proposés considèrent le trafic routier en termes de ses constituants ou comme une entité agrégée en fonction de l’échelle choisie et expliquent l’évolution du trafic quantitativement en tenant compte des relations entre les variables de trafic comme le flot, la densité et la vitesse. Ces modèles décrivent le trafic en utilisant des données très précises acquises par différents capteurs. La précision des données rend son calcul coûteux en termes de ressources requises. Une des solutions à ce problème est la représentation qualitative du trafic routier qui réduit le nombre de ressources de traitement nécessaires. Puisque le trafic routier est un phénomène spatio-temporel, les modèles proposés pour représenter ce type de phénomène pourraient être appliqués dans le cas du trafic routier. Les modèles spatio-temporels, proposés par la communauté de l’Analyse Spatio-Temporelle, ont comme objectif la représentation d’un phénomène tant du point de vue qualitatif que quantitatif. Certains de ces modèles proposent une discrétisation des phénomènes modélisés en considérant un phénomène comme constitué d’entités. Appliquée au trafic routier, cette notion permet d’identifier différentes entités, comme les véhicules, les piétons, les bâtiments etc., qui le constituent. Ces entités influent sur l’évolution du trafic. Les modèles spatio-temporels qualitatifs définissent l’effet des différentes entités les unes sur les autres en terme de relations spatiales. L’évolution spatio-temporelle du phénomène modélisé est représenté par la variation temporelle de ces relations. La prise en compte des entités du trafic et des relations spatiales formalise une structure qui peut être représentée en utilisant un graphe, où les nœuds modélisent des entités et les arcs des relations spatiales. Par conséquent, l’évolution du trafic, modélisée via ce graphe, devient l’évolution du graphe et peut être représenté en terme de la variation de la structure du graphe ainsi que celle des attributs de ses nœuds et de ses arcs. Dans cette thèse, nous proposons une modélisation du trafic routier de ce type basée sur la théorie des graphes. Une des applications à la modélisation du trafic routier est la détection des motifs pertinents au sein du trafic. Dans les modèles du trafic existants, les motifs détectés sont statistiques et sont représentés en utilisant des caractéristiques numériques. Le modèle que nous pro posons dans cette thèse met en avant la structure représentant le trafic routier et peut donc être utilisé pour définir des motifs structurels du trafic qui prennent en compte des différentes entités du trafic et leurs relations. Ces motifs structurels sont sous-jacents à une modélisation sous forme de graphe dynamique. Dans cette thèse, nous proposons un algorithme pour détecter ces motifs structurels du trafic dans le graphe spatio-temporel représentant le trafic routier. Ce problème est formalisé comme celui de l’isomorphisme de sous-graphe pour des graphes dynamiques. L’algorithme proposé est évalué en fonction desdifférents paramètres de graphes. / For past several decades, researchers have been interested in understanding traffic evolution, hence, have proposed various traffic models to identify bottleneck locations where traffic congestion occurs, to detect traffic patterns, to predict traffic states etc. Most of the existing models consider traffic as many-particle system, describe it using different scales of representation and explain its evolution quantitatively by deducing relations between traffic variables like flow, density and speed. Such models are mainly focused on computing precise information about traffic using acquired traffic data. However, computation of such precise information requires more processing resources. A way to remedy this problem is to consider traffic evolution in qualitative terms which reduces the required number of processing resources. Since traffic is spatio-temporal in nature, the models which deal with spatio-temporal phenomenon can be applied in case of traffic. Such models represent spatio-temporal phenomenon from qualitative as well as quantitative standpoints. Depending on the intended application, some models are able to differentiate between various entities taking part in the phenomenon, which proves useful in case of traffic since different objects like vehicles, buildings, pedestrians, bicycles etc., directly affecting traffic evolution, can be included in traffic models. Qualitative spatio-temporal models consider the effects of different entities on each other in terms of spatial relations between them and spatio-temporal evolution of the modeled phenomenon is described in terms of variation in such relations over time. Considering different traffic constituents and spatial relations between them leads to the formation of a structure which can be abstracted using graph, whose nodes represent individual constituents and edges represent the corresponding spatial relations. As a result, the evolution of traffic, represented using graph, is described in terms of evolution of the graph itself, i. e. change in graph structure and attributes of nodes and edges, with time. In this thesis, we propose such a graph model to represent traffic. As mentioned above, one of the applications of existing traffic models is in detecting traffic patterns. However, since such models consider traffic quantitatively, in terms of acquired traffic data, the patterns detected using such models are statistical (a term employed by Pattern Recognition researchers) in the sense that they are represented using numerical description. Since graph-based traffic model proposed in this thesis represents the structure of traffic, it can be employed to redefine the meaning of traffic patterns from statistical to structural (also a term from Pattern Recognition community). Structural traffic patterns include different traffic constituents and their inter-links and are represented using time-varying graphs. An algorithm to detect a given structural traffic pattern in the spatio-temporal graph representing traffic is proposed in this thesis. It formalizes this problem as subgraph isomorphism for time-varying graphs. In the end, the performance of the algorithm is tested using various graph parameters.

No description available.

Made available in DSpace on 2014-12-17T14:56:07Z (GMT). No. of bitstreams: 1 JesseHNB_DISSERT.pdf: 2206144 bytes, checksum: 191ca3ce00f97e4019b5bdb2bc9ab914 (MD5) Previous issue date: 2012-10-18 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / The vision is one of the five senses of the human body and, in children is responsible for up to 80% of the perception of world around. Studies show that 50% of children with multiple disabilities have some visual impairment, and 4% of all children are diagnosed with strabismus. The strabismus is an eye disability associated with handling capacity of the eye, defined as any deviation from perfect ocular alignment. Besides of aesthetic aspect, the child may report blurred or double vision . Ophthalmological cases not diagnosed correctly are reasons for many school abandonments. The Ministry of Education of Brazil points to the visually impaired as a challenge to the educators of children, particularly in literacy process. The traditional eye examination for diagnosis of strabismus can be accomplished by inducing the eye movements through the doctor s instructions to the patient. This procedure can be played through the computer aided analysis of images captured on video. This paper presents a proposal for distributed system to assist health professionals in remote diagnosis of visual impairment associated with motor abilities of the eye, such as strabismus. It is hoped through this proposal to contribute improving the rates of school learning for children, allowing better diagnosis and, consequently, the student accompaniment / A vis?o ? um dos cinco sentidos do corpo humano e, em crian?as, ? respons?vel por at? 80% da percep??o do mundo ao redor. Estudos revelam que 50% das crian?as com m?ltiplas defici?ncias possuem alguma defici?ncia visual, sendo que 4% de todas as crian?as s?o diagnosticadas com estrabismo. O estrabismo ? uma defici?ncia ocular associada ? capacidade de movimenta??o dos olhos, caracterizada por qualquer desvio no alinhamento ocular perfeito. Al?m do aspecto est?tico, a crian?a pode relatar vista emba?ada ou dupla . Problemas oftalmol?gicos n?o diagnosticados corretamente s?o motivos de muitos abandonos da escola. O Minist?rio da Educa??o do Brasil aponta as defici?ncias visuais como um grande desafio aos educadores de crian?as, principalmente no processo de alfabetiza??o. O exame oftalmol?gico tradicional para diagn?stico do estrabismo pode ser realizado induzindo os movimentos oculares atrav?s de instru??es do m?dico ao paciente. Esse procedimento pode ser reproduzido com aux?lio computacional atrav?s da an?lise de imagens capturadas em v?deo. Este trabalho apresenta uma proposta de sistema de teleoftalmologia para auxiliar profissionais da sa?de no diagn?stico a dist?ncia de defici?ncias visuais associadas ? capacidade motora dos olhos, como o estrabismo. Espera-se atrav?s deste trabalho contribuir diretamente para a melhoria dos ?ndices do aprendizado escolar infantil, permitindo melhores condi??es de diagn?stico e, consequentemente, acompanhamento do aluno

Vector Quantization (VQ) is a classic optimization problem and a simple approach to pattern recognition. Applications include lossy data compression, clustering and speech and speaker recognition. Although VQ has largely been replaced by time-aware techniques like Hidden Markov Models (HMMs) and Dynamic Time Warping (DTW) in some applications, such as speech and speaker recognition, VQ still retains some significance due to its much lower computational cost — especially for embedded systems. A recent study also demonstrates a multi-section VQ system which achieves performance rivaling that of DTW in an application to handwritten signature recognition, at a much lower computational cost. Adding sensitivity to temporal patterns to a VQ algorithm could help improve such results further. SOTPAR2 is such an extension of Neural Gas, an Artificial Neural Network algorithm for VQ. SOTPAR2 uses a conceptually simple approach, based on adding lateral connections between network nodes and creating “temporal activity” that diffuses through adjacent nodes. The activity in turn makes the nearest-neighbor classifier biased toward network nodes with high activity, and the SOTPAR2 authors report improvements over Neural Gas in an application to time series prediction. This report presents an investigation of how this same extension affects quantization and prediction performance of the self-organizing incremental neural network (SOINN) algorithm. SOINN is a VQ algorithm which automatically chooses a suitable codebook size and can also be used for clustering with arbitrary cluster shapes. This extension is found to not improve the performance of SOINN, in fact it makes performance worse in all experiments attempted. A discussion of this result is provided, along with a discussion of the impact of the algorithm parameters, and possible future work to improve the results is suggested. / Vektorkvantisering (VQ; eng: Vector Quantization) är ett klassiskt problem och en enkel metod för mönsterigenkänning. Bland tillämpningar finns förstörande datakompression, klustring och igenkänning av tal och talare. Även om VQ i stort har ersatts av tidsmedvetna tekniker såsom dolda Markovmodeller (HMM, eng: Hidden Markov Models) och dynamisk tidskrökning (DTW, eng: Dynamic Time Warping) i vissa tillämpningar, som tal- och talarigenkänning, har VQ ännu viss relevans tack vare sin mycket lägre beräkningsmässiga kostnad — särskilt för exempelvis inbyggda system. En ny studie demonstrerar också ett VQ-system med flera sektioner som åstadkommer prestanda i klass med DTW i en tillämpning på igenkänning av handskrivna signaturer, men till en mycket lägre beräkningsmässig kostnad. Att dra nytta av temporala mönster i en VQ-algoritm skulle kunna hjälpa till att förbättra sådana resultat ytterligare. SOTPAR2 är en sådan utökning av Neural Gas, en artificiell neural nätverk-algorithm för VQ. SOTPAR2 använder en konceptuellt enkel idé, baserad på att lägga till sidleds anslutningar mellan nätverksnoder och skapa “temporal aktivitet” som diffunderar genom anslutna noder. Aktiviteten gör sedan så att närmaste-granne-klassificeraren föredrar noder med hög aktivitet, och författarna till SOTPAR2 rapporterar förbättrade resultat jämfört med Neural Gas i en tillämpning på förutsägning av en tidsserie. I denna rapport undersöks hur samma utökning påverkar kvantiserings- och förutsägningsprestanda hos algoritmen självorganiserande inkrementellt neuralt nätverk (SOINN, eng: self-organizing incremental neural network). SOINN är en VQ-algorithm som automatiskt väljer en lämplig kodboksstorlek och också kan användas för klustring med godtyckliga klusterformer. Experimentella resultat visar att denna utökning inte förbättrar prestandan hos SOINN, istället försämrades prestandan i alla experiment som genomfördes. Detta resultat diskuteras, liksom inverkan av parametervärden på prestandan, och möjligt framtida arbete för att förbättra resultaten föreslås.