No description available.

No description available.

This report investigates how the construction and query time of multiple spatial partitioning data structures is impacted by spatial distribution of and number of agents in a crowd simulation. In addition a method is investigated for updating the data structures less frequently at the cost of increasing the radius queried, without affecting the correctness of the queries. The data structures are tested in a simulation using a Boids model and update and query times are measured. It is found that the performance of the grid is better than the quad tree and the kd- tree for low number of agents, but deteriorates more quickly when the number of agents increase. It is also found that this approach can decrease the sum of time spent updating and the time spent querying in the simulation. The effectiveness of this method is highly dependent on the update of the data structure. / Denna rapport undersöker hur konstruktion och grannsökning av flera datastrukturer för spatial partitionering påverkas av spatial fördelning av simuleringens agenter och antal agenter i simuleringen. Dessutom undersöks en metod för att uppdatera datastrukturerna mindre ofta, på bekostnad av att utöka grannsökningens radie, utan att påverka grannsökningens korrekthet. Datastrukturerna testas i en simulering baserad på Boids och uppdaterings- och frågetider för datastrukturerna mäts. Det visar sig att prestandan av grid är bättre än prestandan av quad tree och kd- tree för ett litet antal agenter, men att prestandan för grid försämras snabbare när antalet agenter ökar. Dessutom visar sig denna metod kunna ge en minskning i den totala tiden som går åt till att göra grannsökningar och uppdateringar av datastrukturen. Hur effektiv denna metod är beror i hög grad på hur lång uppdateringstiden är för den använda datastrukturen.

Je présente dans ce mémoire mes travaux sur les limites d'échelle de grandes structures aléatoires. Il s'agit de décrire les structures combinatoires dans la limite des grandes tailles en prenant un point de vue objectif dans le sens où on cherche des limites des objets, et non pas seulement de paramètres caractéristiques (même si ce n'est pas toujours le cas dans les résultats que je présente). Le cadre général est celui des structures critiques pour lesquelles on a typiquement des distances caractéristiques polynomiales en la taille, et non concentrées. Sauf exception, ces structures ne sont en général pas adaptées aux applications informatiques. Elles sont cependant essentielles de part l'universalité de leurs propriétés asymptotiques, prouvées ou attendues. Je parle en particulier d'arbres uniformément choisis, de graphes aléatoires, d'arbres couvrant minimaux et de partitions récursives de domaines du plan:<br/> <strong>Arbres aléatoires uniformes.</strong> Il s'agit ici de mieux comprendre un objet limite essentiel, l'arbre continu brownien (CRT). Je présente quelques résultats de convergence pour des modèles combinatoires ''non-branchants'' tels que des arbres sujets aux symétries et les arbres à distribution de degrés fixée. Je décris enfin une nouvelle décomposition du CRT basée sur une destruction partielle.<br/> <strong>Graphes aléatoires.</strong> J'y décris la construction algorithmique de la limite d'échel-le des graphes aléatoires du modèle d'Erdös--Rényi dans la zone critique, et je fais le lien avec le CRT et donne des constructions de l'espace métrique limite. <strong>Arbres couvrant minimaux.</strong> J'y montre qu'une connection avec les graphes aléatoires permet de quantifier les distances dans un arbre convrant aléatoire. On obtient non seulement l'ordre de grandeur de l'espérance du diamètre, mais aussi la limite d'échelle en tant qu'espace métrique mesuré. Partitions récursives. Sur deux exemples, les arbres cadrant et les laminations du disque, je montre que des idées basées sur des théorèmes de point fixe conduisent à des convergences de processus, où les limites sont inhabituelles, et caractérisées par des décompositions récursives.

Cette thèse a pour objectif d'étudier et d'analyser une nouvelle stratégie de compression, dont le principe consiste à compresser conjointement des données issues de plusieurs modalités, en utilisant un codeur unique. Cette approche est appelée " Compression Multimodale ". Dans ce contexte, une image et un signal audio peuvent être compressés conjointement et uniquement par un codeur d'image (e.g. un standard), sans la nécessité d'intégrer un codec audio. L'idée de base développée dans cette thèse consiste à insérer les échantillons d'un signal en remplacement de certains pixels de l'image " porteuse " tout en préservant la qualité de l'information après le processus de codage et de décodage. Cette technique ne doit pas être confondue aux techniques de tatouage ou de stéganographie puisqu'il ne s'agit pas de dissimuler une information dans une autre. En Compression Multimodale, l'objectif majeur est, d'une part, l'amélioration des performances de la compression en termes de débit-distorsion et d'autre part, l'optimisation de l'utilisation des ressources matérielles d'un système embarqué donné (e.g. accélération du temps d'encodage/décodage). Tout au long de ce rapport, nous allons étudier et analyser des variantes de la Compression Multimodale dont le noyau consiste à élaborer des fonctions de mélange et de séparation, en amont du codage et de séparation. Une validation est effectuée sur des images et des signaux usuels ainsi que sur des données spécifiques telles que les images et signaux biomédicaux. Ce travail sera conclu par une extension vers la vidéo de la stratégie de la Compression Multimodale

This study aims to investigate and identify how to effectively generate blurred geospatial heatmaps for use in geo-spatial map engines. We focus on how to store the points in a way that facilitates efficient window querying, with support for zoom-level handling. We decide on primarily using a Morton-ordered variant of the point-region quadtree, which we name a HeatMap Quadtree (HMQ). The nodes of the HMQ each have access to the points they contain, through storing the number of points and the lower bound of where to look at in the input point set, which we also store in Morton order. The HMQ also has the functionality to allow for window querying at different levels of detail. We parallelize the generation of the HMQ as well as the Gaussian blurring of the raster resulting from the window query using CUDA, and compare this implementation with that of two naive solutions as well as a linear point-region quadtree. In conclusion we find that the HMQ provides a significant improvement in window querying time, at the cost of additional construction time. / Denna studie avser att undersöka och identifiera hur man effektivt kan generera Gaussiskt oskarpa geospatiala värmekartor för användning i geospatiala kartmotorer. Vi fokuserar på hur man ska lagra punkterna på ett sätt som underlättar effektiv `window querying', med stöd för zoomnivå-hantering. Vi bestämmer oss för att huvudsakligen använda oss av en Morton-ordnad variant av ett `point-region quadtree', vilket vi döper till `HeatMap Quadtree' (HMQ). Noderna i vårt HMQ har alla tillgång till punkterna dom innehåller, genom att lagra antalet punkter och den lägre gränsen för var man ska leta efter punkterna i den ursprunliga punktlistan, som vi också lagrar i Morton-ordning. Vårt HMQ har också funktionaliteten att tillåta `window querying' på olika detaljnivåer. Vi parallelliserar genererandet av vårt HMQ samt uträknandet av den Gaussiska oskärpan på rastret som resulterar från vår `window query' med hjälp av CUDA, och jämför denna implementation med två naiva lösningar samt ett linjärt `point-region quadtree'. Vår slutsats är att vårt HMQ ger en signifikant förbättring i `window query'-tid, till en kostnad av extra konstruktionstid.

I detta arbete jämförs prestanda mellan olika implementationer av algoritmer som utför samma uppgift. Som sammanhang för algoritmerna har flockbeteende inom datorspel använts. En anledning till att använda flockbeteende i datorspel och film är att öka realismen i det som presenteras på bildskärmen. Detta ökar betraktarens acceptans av den digitala verkligheten. Under arbetets gång har en artefakt utvecklats med syfte att mäta prestandan för de valda algoritmerna: Alla mot alla, QuadTree och OverlapCircle. Artefakten är utvecklad i spelmotorn Unity för att enklare koppla ihop implementationen med ett spelprojekt. Analysen visar att den av de tre undersökta algoritmerna som ger bäst prestanda är OverlapCircle. En trolig anledning till att den presterar bäst är att den baseras till stor del på inbyggd funktionalitet i den använda plattformen Unity och kan på så sätt dra nytta av den underliggande arkitekturen. / <p>Det finns övrigt digitalt material (t.ex. film-, bild- eller ljudfiler) eller modeller/artefakter tillhörande examensarbetet som ska skickas till arkivet.</p>

Currently living in the digital age, so the manipulation of data and images is often all day. Due to the problem of space for storage of pictures and time of transmission, many compression techniques had been developed, and a great challenge is to make these techniques to bring good results in terms of compression rate, picture quality and processing time. The Fractal Compression technique developed by Fisher, was described, implemented and tested in this work and it brought great results, and considerable improvement in terms of execution time, which was rather low. Another area that has been emphasizing is the use of biometric techniques to the people recognition. A very used technique is the iris recognition that has shown enough reliability. Thus, connecting the two technologies brings great benefits. In this work, images of iris were compressed by the method implemented here and were made simulations of the technique iris recognition developed by Libor Maseck. The results show that it is possible to compress fractally the images without damage the recognition system. Comparisons were made and was possible realize that even with changes in pixels of images, the system remains very reliable, bringing benefits to storage space. / Atualmente vive-se na era digital, por isso a manipulação de dados e imagens é freqüente todos os dias. Devido ao problema de espaço para armazenamento dessas imagens e tempo de transmissão, foram desenvolvidas várias técnicas de compressão, e um grande desafio é fazer com que essas técnicas tragam bons resultados em termos de taxa de compressão, qualidade da imagem e tempo de processamento. A técnica de compressão Fractal desenvolvida por Fisher, foi descrita, implementada e testada neste trabalho e trouxe ótimos resultados, e melhoria considerável em termos de tempo de execução, que foi bastante reduzido. Outra área que vem se destacando é o uso de técnicas biométricas para reconhecimento de pessoas. Uma técnica muito usada é o reconhecimento de íris que tem mostrado bastante contabilidade. Assim, aliar as duas tecnologias traz grandes benefícios. No presente trabalho, imagens de íris foram comprimidas pelo método aqui implementado e foram realizadas simulações da técnica de reconhecimento de íris desenvolvida por Maseck. Os resultados mostram que é possível comprimir fractalmente as imagens sem prejudicar o sistema de reconhecimento. Comparações foram realizadas e foi possível perceber que mesmo havendo mudanças nos pixels das imagens, o sistema permanece bastante confiavel, trazendo vantagens em espaço de armazenamento. / Mestre em Ciências

This paper explores different bump mapping techniques and their implementation. Bump mapping is a technique that is used in computer games to make simple 3D objects look more detailed than what they really are. The technique involves using a texture to change the objects normals to simulate bumps and is used to avoid rendering high polygonal objects. Over the years some different techniques have been developed based on bump mapping, these are normal mapping, relief mapping, parallax occlusion mapping, quadtree displacement mapping and so on. The first part of this paper we go through our goals and our research methodology. We then write about four different techniques and describe how they work. We also go through how they are implemented. After that we start our experiments and measure the different techniques against each other. When the first testing has been done, we start to optimize the techniques and run a second test to see how much faster, if it is faster, the optimization is compared to the previous tests. When the tests are done, we present our test data and analyse them. Finally we discuss the techniques and the testing. Then we finish up with a conclusion. / Mikaels telefon: 072-181 77 29 Ermins telefon: 076-178 97 59

The goal of the master &#769;s thesis is to study index methods, spatial data type objects in PostgreSQL database systems and to create SP-GiST index by quadtree in the PostGIS. The PostGIS is spatial database, which extends of PostgreSQL. PostGIS adds support for geographic and spatial objects. It is a big benefit. PostGIS has its own data types, methods and GiST index too, but there is SP-GiST index missing, therefore master's thesis was created.