DESIGN OF FAST MULTIDIMENSIONAL FILTERS BY GENETIC ALGORITHMS
Undergraduate
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.