Habilitation - Universitat, Stuttgart. / Title from e-book title screen (viewed January 2, 2008). Includes bibliographical references (p. [249]-275) and index.

This dissertation deals with the problem of manipulating and storing an image using quadtrees. A quadtree is a tree in which each node has four ordered children or is a leaf. It can be used to represent an image via hierarchical decomposition. The image is broken into four regions. A region can be a solid color (homogeneous) or a mixture of colors (heterogeneous). If a region is heterogeneous it is broken into four subregions, and the process continues recursively until all subregions are homogeneous. The traditional quadtree suffers from dependence on the underlying grid. The grid coordinate system is implicit, and therefore fixed. The fixed coordinate system implies a rigid tree. A rigid tree cannot be translated, scaled, or rotated. Instead, a new tree must be built which is the result of one of these transformations. This dissertation introduces the independent quadtree. The independent quadtree is free of any underlying coordinate system. The tree is no longer rigid and can be easily translated, scaled, or rotated. Algorithms to perform these operations axe presented. The translation and rotation algorithms take constant time. The scaling algorithm has linear time in the number nodes in the tree. The disadvantage of independent quadtrees is the longer generation and display time. This dissertation also introduces an alternate method of hierarchical decomposition. This new method finds the largest homogeneous block with respect to the corners of the image. This block defines the division point for the decomposition. If the size of the block is below some cutoff point, it is deemed to be to small to make the overhead worthwhile and the traditional method is used instead. This new method is compared to the traditional method on randomly generated rectangles, triangles, and circles. The new method is shown to use significantly less space for all three test sets. The generation and display times are ambiguous. More time is taken for each node, but there are, on average, fewer nodes. The worst case is significantly worse.

Advances in hardware acceleration has resulted in development of a variety of hardware accelerated ray tracing libraries. The purpose of this bachelor thesis is to investigate if a simple ray tracer, based on a hardware accelerated ray tracing library, can achieve acceptable frame rates in rendering simple 3D game-related environments. Games are often associated with fast rasterization-based rendering techniques, but rasterization is limited where instead ray tracing holds many advantages. Background research was done to gain knowledge about related work, state-of-the-art in ray tracing and available hardware accelerated libraries. By using a method similar to Kanban and Scrum [36], the implementation was split up into different tasks, prioritizing the tasks of implementing basic functionalities of a ray tracer. A simple ray tracer was implemented based on the chosen library Embree, a framework developed at Intel Corporation. Results show that the scenes rendered in lower resolutions (800 x 600) are good candidates for having a stable frame rate of 30 FPS, which is not enough in order to render a real game. The standard of games today require high resolution (full HD 1920 x 1080) and complex scenes. Earlier studies show that Embree has potential of higher performance and looking back the performance of real-time ray tracing has improved, but is still limited to low resolutions and simple lighting and shading models. / Framsteg inom hårdvaruacceleration har resulterat i att en rad olika hårdvaruaccelererade bibliotek för strålföljning utvecklats. Syftet med denna kandidat-uppsats är att undersöka om en enkel strålföljare, baserad på ett hårdvaruaccelererat bibliotek för strålföljning, kan uppnå acceptabla bildfrekvenser vid rendering av enkla spel-relaterade miljöer i 3D. Datorspel förknippas ofta med snabba renderingstekniker. Rasteriseringsalgoritmen är dock begränsad där istället strålföljning har många fördelar. En litteraturstudie gjordes för att få kunskap om relaterade arbeten, state-of-the-art i strålföljning och tillgängliga hårdvaruaccelererade bibliotek. Genom att använda en metod som kan liknas vid Kanban och Scrum [36], blev implementationen uppdelad i olika uppgifter (eng. tasks), där implementationen av grundläggande funktioner av en strålföljare hade högsta prioritet. En enkel strålföljare implementerades med det valda biblioteket Embree, ett ramverk som utvecklas hos Intel Corporation. Resultaten visar att scenerna som renderas med lägre upplösningar (800 x 600) är goda kandidater för att uppnå en stabil bildfrekvens med 30 bilder per sekund (eng. frames per second), vilket inte är tillräckligt för att rendera ett riktigt spel. Standarden hos spel idag kräver hög upplösning (full HD 1920 x 1080) och komplexa scener. Tidigare studier visar att Embree har potential för högre prestanda och tidigare resultat visar att prestandan av interaktiv strålföljning har förbättrats, men att den fortfarande är begränsad till låga upplösningar och enklare belysningsmodeller.

published_or_final_version / Computer Science / Master / Master of Philosophy

published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

Over the past few years, DNA sequencing technology has been advancing at such a fast pace that computer hardware and software can hardly meet the ever-increasing demand for sequence analysis. A natural approach to boost analysis efficiency is parallelization, which divides the problem into smaller ones that are to be solved simultaneously on multiple execution units. Common architectures such as multi-core CPUs and clusters can increase the throughput to some extent, but the hardware setup and maintenance costs are prohibitive. Fortunately, the newly emerged general-purpose GPU programming paradigm gives us a low-cost alternative for parallelization. This thesis presents GPU-accelerated algorithms for several problems in bioinformatics, along with implementations to demonstrate their power in handling enormous totally different limitations and optimization techniques than the CPU. The first tool presented is SOAP3-dp, which is a DNA short-read aligner highly optimized for speed. Prior to SOAP3-DP, the fastest short-read aligner was its predecessor SOAP2, which was capable of aligning 1 million 100-bp reads in 5 minutes. SOAP3-dp beats this record by aligning the same volume in only 10 seconds. The key to unlocking this unprecedented speed is the revamped BWT engine underlying SOAP3-dp. All data structures and associated operations have been tailor made for the GPU to achieve optimized performance. Experiments show that SOAP3-dp not only excels in speed, but also outperforms other aligners in both alignment sensitivity and accuracy. The next tools are for constructing data structures, namely Burrows-Wheeler transform (BWT) and de Bruijn graphs (DBGs), to facilitate genome assembly of short reads, especially large metagenomics data. The BWT index for a set of short reads has recently found its use in string-graph assemblers [44], as it provides a succinct way of representing huge string graphs which would otherwise exceed the main memory limit. Constructing the BWT index for a million reads is by itself not an easy task, let alone optimize for the GPU. Another class of assemblers, the DBG-based assemblers, also faces the same problem. This thesis presents construction algorithms for both the BWT and DBGs in a succinct form. In our experiments, we constructed the succinct DBG for a metagenomics data set with over 200 gigabases in 3 hours, and the resulting DBG only consumed 31.2 GB of memory. We also constructed the BWT index for 10 million 100-bp reads in 40 minutes using 4 quad-core machines. Lastly, we introduce a SNP detection tool, iSNPcall, which detects SNPs from a set of reads. Given a set of user-supplied annotated SNPs, iSNPcall focuses only on alignments covering these SNPs, which greatly accelerates the detection of SNPs at the prescribed loci. The annotated SNPs also helps us distinguish sequencing errors from authentic SNPs alleles easily. This is in contrast to the traditional de novo method which aligns reads onto the reference genome and then filters inauthentic mismatches according to some probabilities. After comparing on several applications, iSNPcall was found to give a higher accuracy than the de novo method, especially for samples with low coverage. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

In this thesis, we make several significant achievements towards defining a medial axis based shape descriptor which is compact, yet discriminative. First, we propose a novel medial axis spectral shape descriptor called the medial axis spectrum for a 2D shape, which applies spectral analysis directly to the medial axis of a 2D shape. We extend the Laplace-Beltrami operator onto the medial axis of a 2D shape, and take the solution to an extended Laplacian eigenvalue problem defined on this axis as the medial axis spectrum. The medial axis spectrum of a 2D shape is certainly more efficient to compute than spectral analysis of a 2D region, since the efficiency of solving the Laplace eigenvalue problem strongly depends on the domain dimension. We show that the medial axis spectrum is invariant under uniform scaling and isometry of the medial axis. It could also overcome the medial axis noise problem automatically, due to the incorporation of the hyperbolic distance metric. We also demonstrate that the medial axis spectrum inherits several advantages in terms of discriminating power over existing methods. Second, we further generalize the medial axis spectrum to the description of medial axes of 3D shapes, which we call the medial axis spectrum for a 3D shape. We develop a newly defined Minkowski-Euclidean area ratio inspired by the Minkowski inner product to characterize the geometry of the medial axis surface of a 3D mesh. We then generalize the Laplace-Beltrami operator to the medial axis surface, and take the solution to an extended Laplacian eigenvalue problem defined on the surface as the medial axis spectrum. As the 2D case, the medial axis spectrum of a 3D shape is invariant under rigid transformation and isometry of the medial axis, and is robust to shape boundary noise as shown by our experiments. The medial axis spectrum is finally used for 3D shape retrieval, and its superiority over previous work is shown by extensive comparisons. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

No description available.

No description available.

No description available.