Fast algorithms for the wavelet transform.
This research was carried out in collaboration with Dr. Umberto
Amato while visiting Istituto per Applicazioni della Matematica of Naples,
Italy.
The discrete wavelet transform (DWT) has proved its utility in various
signal processing problems such as data compression or noise reduction.
It is therefore important, both for research and for industrial applications,
to dispose of fast software performing the various versions of the DWT.
Several software tools for this purpose were designed by Dr. Vuza,
which are currently used in the activity of the named institute. Since
Wavelet Theory is relatively new, software product adapted to specific
needs are not easy available yet so that we had to develop our own.
An object-oriented approach to the DWT by developing a hierarchy of
C++ classes covering the cases of periodic DWT and finite-interval DWT
has been proposed . The code was presented in two versions:
- as C++ code, designed to be portable to all C++ platforms and hence
intended primarily for research;
- as assembly language code, designed for integration into real-time
applications based on INTEL processors of 80386 type or higher.
The assembly version was optimized for speed by means of a non-standard
use of the floating-point unit in order to achieve the following purposes:
- reducing the number of memory references by making use of all eight
floating-point unit registers (in contrast with usual compilers, which
generally use up to three of them);
- ensuring a high degree of sequentiality of execution stream by reducing
the number of jumps.
Both 16 bit and 32 bit versions were produced.
The table below presents a comparison between the timings achieved
with the C++ and assembly versions respectively. The test consisted in
running the DWT for 200 times on a sequence of 4096 data and taking the
average execution time, expressed below in milliseconds. The test was performed
on a 90 Mhz PENTIUM computer running Windows for Workgroups 3.11 with the
Win32s add-on.
|
16 bit code |
32 bit code |
| C++ code |
166.14 |
52.45 |
| ASM code |
26.36 |
16.75 |
It is expected that applications based on processors not as highly
optimized as the PENTIUM (in particular, those without branch prediction)
could take an even greater advantage from the proposed assembly routines.
A possible research subject could be therefore the adaption of the
above methods to other types of DWT beside periodic and finite interval
and to other kinds of processors.
For applications it is equally important to dispose of filter coefficients
for DWT computed to a high precision. In the report mentioned below the
authors proposed a program for the MATHEMATICA environment for computing
the boundary filter coefficients needed by the finite interval DWT which
takes advantage of the capability of MATHEMATICA of working with arbitrary
high degrees of precision. Research on this topic could also be continued
for other types of DWT.
Reference from list
of works related to this topic: technical report [1].