ABSTRACT

The need for fast multidimensional signal processing arises in many areas. One of the more demanding applications is real time visualization of medical data acquired with eg magnetic resonance imaging where large amounts of data can be generated. This data has to be reduced to relevant clinical information, either by image reconstruction and enhancement or automatic feature extraction.

Design of fast-acting multidimensional filters has been subject to research during the last three decades. Usually methods for fast filtering are based on applying a sequence of filters of lower dimensionality acquired by eg weighted low-rank approximation. Filter networks is a method to design fast multidimensional filters by decomposing multiple filters into simpler filter components in which coefficients are allowed to be sparsely scattered. Up until now, coefficient placement has been done by hand, a procedure which is time-consuming and difficult.

The aim of this thesis is to investigate whether genetic algorithms can be used to place coefficients in filter networks. A method is developed and tested on 2-D filters and the resulting filters have lower distortion values while still maintaining the same or lower number of coefficients than filters designed with previously known methods.

Introduction

Multidimensional signals are generated in a large area of applications. In health care, such signals are used extensively and are generated with imaging techniques such as computed tomography (CT), magnetic resonance imaging (MRI) and ultrasound imaging. These techniques produce large data sets that has to be processed and visualized, a process that is computationally complex and time consuming. Improvements in imaging techniques has made it possible to acquire not only ordinary images but e.g. 3-D ’pictures’ of the human body. With increased dimensionality of signals, the amount of data produced and the number of computations required for processing increases exponentially. This creates a need for computationally efficient signal processing methods.

Multidimensional Signal Processing

The most common example of multidimensional signals are actually ordinary digital images. A 512×512 grayscale image can be represented by a 512×512 matrix with integer values representing intensity. Signals can be multidimensional in another sense, however. In an RGB colour image, each pixel contains three elements, One value for red, green and blue respectively, and is essentially a vector field. This signal has outer dimensionality 2 and inner dimensionality 3.

The outer dimensions can be e.g. spatial or temporal. An image sequence (movie) for instance has two spatial dimensions and one temporal. This has implications on the expected spectrum and, if the sequences are captured and processed in real time, causality of the filters along the temporal dimension. In a stored image sequence, temporal dimensions can usually be treated as spatial in terms of causality and the sequence can be viewed as a volume.

In health care several imaging modalities are used to generate 3-D signals.

Fast Filtering

Design of fast multidimensional filters has been subject to research at least since 1971. Although computers have developed tremendously since, filtering of large multidimensional signals is still very time-consuming and more efficient filter implementations are called for. Usually methods for fast filtering are based on applying a sequence of filters of lower dimensionality, e.g. by making a low-rank approximation. Filter networks is a method to design fast multidimensional filters by decomposing multiple filters into simpler filter components in which coefficients are allowed to be sparsely scattered. Up until now, coefficient placement has been done by hand, a procedure which can be time-consuming and difficult for larger filter network implementations and require a large amount of experience in design and implementation of filters and filter networks.

Genetic Algorithms

Genetic algorithms is an optimization method inspired by evolution in biological systems. They are an abstract model of sexual reproduction within a population of a species where the genetic material is modeled by some data structure, most often a string of symbols. This can be compared to DNA which can be seen as two coupled strings of symbols from a four letter alphabet. The use of a two-string representation (or diploid encodings) as in DNA is possible, but most often only one string (or haploid encoding) is used. Within the population, fit individuals survive to reproduce and their genetic material is recombined to new individuals. New genetic material is introduced through mutations and through this process sucessively better and better individuals of the species are bred.

In nature, evolution can be seen as responsible for the evolution of hardware. Bodies of animals get better and better adapted to the environment through this process and our brains are also the product of evolution. This adaptation can be seen as a learning across generations and is a very slow process often requiring several million years to produce any discernible effects. A natural question is how such a process can be used to evolve solutions in a computer in reasonable time. The answer is in the time it takes to evaluate if an individual is fit for reproduction or not. In nature, this evaluation is performed by the surrounding environment and is often a process of several years. In computers, this task is performed by a fitness function taking the role of the environment and this evaluation is often performed in a matter of seconds. Therefore many more generations can pass and a good solution can evolve in reasonable time.

Aims of this Study

The aim of this study is to investigate if genetic algorithms can be used to place coefficients in filter networks. This is done by developing a method of applying genetic algorithms to the design of filter networks and this method is tested on a number of examples. Results will also be analysed to see if any guidelines for design of filter networks can be found.