Directional decomposition of an image consists of separating it into several components, each containing directional information in some specific directions. It has many applications in digital image processing, such as image improvement or linear feature detection, and could be used on seismic data to help geophysicists finding faults. In this thesis, we look at a directional filter bank (DFB) introduced by Bamberger and Smith and how to implement it efficiently on CPU and GPU. Graphics Processing Units (GPUs) are becoming increasingly more suitable for general scientific computing, and applications with suitable properties run much quicker on a GPU than a CPU. For instance, NVIDIA CUDA (Compute Unified Device Architecture) is a new programming interface that lets users program NVIDIA General Purpose GPUs (GPGPUs) in a C-like fashion for data parallel intensive computation. We translate the DFB algorithm from a theoretical signal processing description to an algorithmic description from computer scientists'point of view, including a readable C implementation. Tools are developed to ease our DFB investigation, including a tailored library to manipulate images in suitable text-based and binary formats and for generating test images with suitable properties. Several implementations of 1D filter banks are also provided. Finally, part of the Bamberger DFB is implemented efficiently using the CUDA environment for NVIDIA GPUs. We show that directional filter banks can efficiently be executed on GPUs and demonstrate that the CPU-GPU bandwidth affects performance considerably. Hence, care should be taken to do as many steps as possible on the GPU before returning results to the CPU.

This master-thesis considers implementation of automated multimodal volume-to-volume registration of images, in order to provide neurosurgeons with valuable information for planning and intraoperative guidance. Focus has been on medical images from magnetic resonance (MR) and ultrasound (US) for use in surgical guidance. Prototype implementations for MRI-to-US registration have been proposed, and tested, using registration methods available in the Insight Toolkit (ITK). Mattes' Mutual Information has been the similarty metric, based on unpreprocessed angio-graphic volumes from both modalities. Only rigid transformations has been studied, and both types of Gradient Descent and Evolutionary optimizers has been examinated. The applications have been tested on clinical data from relevant surgical operations. The best results were obtained using an evolutional (1+1) optimizer for translational transformations only. This application was both fast and accurate. The other applications, using types of Gradient Descent optimizers, has proved to be significantly slower, inaccurate and more difficult to parameterize. It has been experienced that registration of angio-graphic volumes are easier to accomplish than registration of volumes of other weightings, due to their more similar characteristics. Angio-graphic images are also readily evaluated using volume renderings, but other methods should be constructed to provide a less subjective measure of success for the registration procedures. The obtained results indicate that automatic volume-to-volume registration of angio-graphic images from MRI and US, using Mattes' Mutual Information and an Evolutionary Optimizer, should be feasible for the neuronavigational system considered here, with sufficient accuracy. Further development include parameter-tuning of the applications, to possibly achieve increased accuracy. Additionally, a non-rigid registration application should be developed, to account for local deformations during surgery. Development of additional tools for performing accurate validation of registration results should be developed as well.

Pattern matching in bio-informatics is a discipline in sturdy growth, and has a great need for searching through large amounts of data. At NTNU, a prototype specified in VHDL has been developed for an FPGA-solution identifying short motifs or patterns in genetic data using a Position-Weight Matrix (PWM). But programming FPGAs using VHDL is a complicated and time consuming process that requires intimate knowledge of how hardware works, and the prototype is not yet complete in terms of required functionality. Consequently, a desirable alternative is to make use of co-design languages to facilitate the use of hardware for a software developer, as well as to integrate the environment for development of soft- and hardware. This thesis deal with specification and implementation of a co-design based alternative to the existing VHDL based solution, as well as an evaluation of productivity vs final performance of the newly developed solution compared to the VHDL based solution. The chosen co-design language is Impulse-C, created by Impulse Accelerated Technologies Inc., which is a co-design language designed for data-flow oriented applications, but with the flexibility to support other programming models as well. The programming model simplifies the expression of highly parallel algorithms through the use of well-defined data communication, message passing and synchronization mechanisms. The affiliated development environment, CoDeveloper, contains tools that allow the FPGA system to be developed and debugged using Impulse-C. The software-to-hardware compiler and optimizer translates C-language processes to (RTL) VHDL code, while optimizing the generated logic and identifying opportunities for parallelism. Ease-of-use for the CoDeveloper environment is evaluated in this thesis, based on the authors experiences with the tools. In total, four variations of the Impulse-C solution has been implemented; a basic solution and a multicore solution, both implemented in a floating-point and a 'fixed-point' version. The implemented solutions are analyzed through various experiments described in this thesis, done during simulation using CoDeveloper. Attempts were made to get the solutions to run on the target platform, the Cray XD1 supercomputer Musculus, but these were unsuccessful. A wrong choice of properties and constraints in Xilinx ISE are believed to have caused the FPGA programming file to be generated faulty. There was no time to confirm and correct this. Some information about device utilization and performance could still be extracted from the Xilinx ISE 'Static timing' and 'Place and route' reports.

Nortura, Norway’s largest producer of meat, faces many challenges in their operation. One of these challenges is to decide which products to make out of each of the slaughtered animals. The meat from the animals can be made into different products, some more valuable than others. However, someone has to buy the products as well. It is therefore important to produce what the customers ask for. This thesis is about a computer system based on online optimisation which helps the meat cutters decide what to make. Two different meat cutting plants have been visited to specify how the system should work. This information has been used to develop a program which can give a recommendation for what to produce from carcasses during cutting. The system has been developed by considering both the attributes of the animals and the orders from the customers. The main focus of the thesis is how to deal with the fact that the attributes are only known for a small number of the animals, since they are measured right after slaughtering. A method has been made to calculate what should be made from the different carcasses, and this method has been realised with both exact and heuristic algorithms.

Metric indexing is a branch of search technology that is designed for search non-textual data. Examples of this includes image search (where the search query is an image), document search (finding documents that are roughly equal) to search in high-dimensional Euclidean spaces. Metric indexing is based on the theory of metric spaces, where the only thing known about a set of objects is the distance between them (defined by a metric distance function). A large number of methods have been proposed to solve the metric indexing problem. In this thesis, we have concentrated on new approaches to solving these problems, as well as combining existing methods to create better ones. The methods studied in this thesis include D-Index, GNAT, EMVP-Forest, HC, SA-Tree, SSS-Tree, M-Tree, PM-Tree, M*-Tree and PM*-Tree. These have all been implemented and tested against each other to find strengths and weaknesses. This thesis also studies a group of indexing methods called hybrid methods which combines tree-based methods (like SA-Tree, SSS-tree and M-Tree), with pivoting methods (like AESA and LAESA). The thesis also proposes a method to create hybrid trees from existing trees by using features in the programming language. Hybrid methods have been shown in this thesis to be very promising. While they may have a considerable overhead in construction time,CPU usage and/or memory usage, they show large benefits in reduced number of distance computations. We also propose a new way of calculating the Minimal Spanning Tree of a graph operating on metric objects, and show that it reduces the number of distance computations needed.

In this project, a complex, serial application that models networks of oil wells is analyzed for today's parallel architectures. By heavy use of the profiling tool Valgrind, several serial optimizations are achieved, causing up to a 30-50x speedup on previously dominant sections of the code, on different architectures. Our initial main goal is to parallelize our application for GPGPUs (General Purpose Graphics Processing Units) such as the NVIDIA GeForce 8800GTX. However, our optimized application is shown not to have a high enough computational intensity to be suitable for the GPU platforms, with the data transfer over the PCI-express port showing to be a serious bottleneck. We then target our applications for another, more common, parallel architecture -- the multi-core CPU. Instead of focusing on the low-level hotspots found by the profiler, a new approach is taken. By analyzing the functionality of the application and the problem it is to solve, the high-level structure of the application is identified. A thread pool in combination with a task queue is implemented using PThreads in Linux, which fit the structure of the application. It also supports nested parallel queues, while maintaining all serial dependencies. However, the sheer size and complexity of the serial application, introduces a lot of problems when trying to go multithreaded. A tight coupling of all parts of the code, introduces several race conditions, creating erroneous results for complex cases. Our focus is hence shifted to developing models to help analyze how suitable applications with traversal of dependence-tree structures, such as our oil well network application is, given benchmarks of the node times. First, we benchmark the serial execution of each child in the network and predict the overall parallel performance by computing dummy tasks reflecting these times on the same tree structure on two given well networks, a large and a small case. Based on these benchmarks, we then predict the speedup of these two cases, with the assumption of balanced loads on each level in the network. Finally, the minimum amount of time needed to calculate a given network is predicted. Our predictions of low scalability, due to the nature of the oil networks in the test cases, are then shown. This project thus concludes that the amount of work needed to successfully introduce multithreading in this application might not be worth it, due to all the serial dependencies in the problem the application tries to solve. However, if there are multiple individual networks to be calculated, we suggest using Grid technology to manage multiple individual instances of the application simultaneously. This can be done either by using script files or by adding DRMAA API calls in the application. This, in combination with further serial optimizations, is the way to go for good speedup for these types of applications.

Go is an ancient two player board game that has been played for several thousand years. Despite its simple rules, the game requires players to form long-term strategic plans and also possess strong tactical skills to handle the complex fights that often occur during a game. From an artificial intelligence point of view, Go is notable as a game that has been highly resistant to all traditional game playing approaches. In contrast to other board games such as chess and checkers, top human Go players are still significantly better than any computer Go playing programs. It is believed that the strategic depth of Go will require the use of new and more powerful artificial intelligence methods than the ones successfully used to create computer players for such other games. There have been some promising new developments using new Monte Carlo-based techniques to play computer Go in recent years, and programs based on this approach are currently the strongest computer Go players in the world. However, even these programs still play at an amateur level, and they cannot compete with professional or strong amateur human players. In this thesis we explore the idea of reusing experience from previous games to identify strategically important moves for a Go board position. This is based on finding a previous game position that is highly similar to the one in the current game. The moves that were played in this previous game are then adapted to generate new moves for the current game situation. A new computer Go playing system using Monte Carlo-based Go methods was designed as a part of this thesis work, and a prototype implementation of this system was also developed. We extended this initial prototype using case based reasoning (CBR) methods to quickly identify the most strategically valuable areas of the board at the early stages of the game, based on finding similar positions in a collection of professionally played games. The last part of the thesis is an evaluation of the developed system and the results observed using our implementation. These results show that our CBR-based approach is a significant improvement over the initial prototype, and in the opening game it allows the program to quickly locate the most strategically interesting areas of the board. However, by itself our approach does not find strong tactical moves within these identified areas, and thus it is most valuable when used to provide strategic guidelines for other methods that can find tactical plays.

The tasks : discriminating music, speech and other sounds and language identification have a broad range of applications in todays multilingual multimedia community. Both tasks gave a lot of possibilities regarding methods and development tools which also brings some risk. The Language Identification(LID) problem ended up with two different approaches. One approach was discarded due to poor results in the pre-study while the other approach had some promising potential but did not deliver as hoped in the first place. On the other hand, the music, speech discrimination was solved with great accuracy using 3 simple time domain features and Support Vector Machines(SVM). Adding 'other sounds' to this discrimination problem did complicate the problem but the final solution delivered great results using the enormous BBC Sound Effects library as examples of non speech and music. Both tasks were tried being solved using Gaussian Mixture Models(GMM) because of it's known great ability to model arbitrary feature space segmentations. The tools used were Matlab together with a number of different toolboxes explained further in the text.

The use of Linux in embedded systems is steadily growing in popularity. The UC3A is a series of high performance, low power 32-bit microcontrollers aimed at several industrial and commercial applications including PLC, instrumentation, phones, vending machines and more. The main goal of this project was to complete the adaptation of the Linux kernel, compiler and loader software, in order to enable the Linux kernel to load and run applications on this device. In addition, a set of useful applications should be picked, compiled and tested on the target platform to indicate a complete software solution. This master's thesis is a continuation, by the same three students, of the work of a student project during the fall of 2008. In this report we present in detail the findings, challenges, choices and and solutions involved in the working process. During the course of this project, we have successfully adapted the Linux kernel, and a toolchain for generating binaries loadable by Linux. A set of test applications have been compiled and tested on the resulting platform. This project has resulted in the submission of a revised patch series for the U-Boot boot loader, one patch series for Linux, and one for the toolchain. Requirements have been created, and tests for the requirements have been carried out.

In this project we seek to explore whether it is possible for an artificial agent to learn how to play curling. To achieve this goal we developed a simulator that works as an environment where different agents can be tested against each other. Our most successful agent use a Linear Target Function as a basis for selecting good moves in the game. This agent has become very adept at placing stones, but we discovered that it lacks the ability to employ advanced strategies that reach over more than just one stone. In an effort to give the agent this ability we expanded it using Q-learning with UCT, however this was not successful. For the agent to work we need a good representation of the information in curling, and our representation was quite broad. This caused the training of the agent to take an unreasonably large amount of time.