Go to: Title Page Chapter 1 Appendix A Appendix J Copyright Chapter 2 Appendix B Appendix K Abstract Chapter 3 Appendix C Appendix L Acknowledgements Chapter 4 Appendix D References Table of Contents Chapter 5 Appendix E List of Figure Conclusions/ Appendix F List of Tables Future Directions Appendix G List of Audio Examples Appendix H List of Programs Appendix I
I. Overview, compiling with lifted_wavelet_transforms.h and normal_wavelet_transforms.h
This appendix documents wavelet transform code used in chapters 3 through 6. All programs written for chapters 3 through 6 make use of the functions contained in the C++ files lifted_wavelet_transforms.h and normal_wavelet_transforms.h. The procedures contained in these two header files perform forward and inverse wavelet transforms on arbitrary blocks of data which do not necessarily have to be sound samples. Nonetheless, both of these files #include the file ac.h for certain type and macro definitions; therefore, users of the functions in lifted_wavelet_transforms.h and normal_wavelet_transforms.h should make sure that ac.h is in the compiler's header file search path at compile time. Since all wavelet transform functions and support functions are declared and defined in the two header files, no additional linking is required to use the transform functions - simply #include either lifted_wavelet_transforms.h or normal_wavelet_transforms.h and make sure "ac.h" is in the compiler's search path.
As explained in Chapter 3, two sets of wavelet transform functions were implemented for this thesis - one method, the lifted wavelet transform, uses interpolation to compute the wavelet and scaling coefficients, while the other method, normal circular convolution filtering, uses basic time-domain convolution to compute wavelet and scaling coefficients. In general, the lifted wavelet transform has reduced boundary artifacts for signals which are exact polynomials, while the time-domain convolution-based filtering is faster and simpler to implement. Both the forward and inverse transforms' interfaces are given here for other interested programmers; the user is referred to the included code listings and extensive commenting contained therein for further examples of how to use the transform functions.
The user may want to use a compiler's optimization
options to increase the performance of the produced run-time code,
as filtering is computation-intensive.
II. Lifted wavelet transform
The following functions are defined in lifted_wavelet_transforms.h:
A. Neville's algorithm for polynomial interpolation
and extrapolation.
float
interpolate(float* xa, float* ya, int N,
float x)
This algorithm was taken from Pressí
Numerical Recipes and translated into C++ from the original
FORTRAN. Given an array of x-values in xa and an array of y-values
in ya, this function uses Nth order polynomial interpolation to
find an interpolated/extrapolated value with argument x. Returns
the interpolated y-value associated with the input argument x.
This function is used in the flwt and iflwt functions below.
B. Forward, lifted wavelet transform.
int
flwt(float* input_buffer, int num_channels,
int num_frames, int N)
Performs one iteration of the forward, lifted
wavelet transform. This function can handle interleaved data,
which is useful for multi-channel audio buffers. One frame is
defined as one sample value per channel input. For example, a
four-channel input buffer contains four samples per frame. To
illustrate the structure of the input buffer to this function,
the following is the buffer structure for a two-channel interleaved
input. Frames are presented sequentially in the buffer, with the
channel data being presented sequentially within each frame:
| frame1 | frame2 | frame3 | frame4 | ...etc. | |||||
| ch1(L) | ch2(R) | ch1(L) | ch2(R) | ch1(L) | ch2(R) | ch1(L) | ch2(R) | ...etc. | |
| input buffer array index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ...etc. |
The wavelet and scaling coefficients are the
outputs of the forward transform, and are replaced in the input
buffer with the scaling coefficients occupying the first half
of the input buffer, and the wavelet coefficients occupying the
second half of the input buffer. To continue with the two-channel
example, the input buffer would have the following structure for
a two-channel audio input after processing:
where F is the value of the input argument num_frames.
The N input argument controls the number of
vanishing moments to use in performing the transform. Note that
in order to achieve perfect reconstruction, the same number of
vanishing moments must be specified in both the forward and inverse
lifted wavelet transform function calls.
Use
N = 1 for linear interpolation (one vanishing moment)
N = 2 for cubic interpolation (three vanishing moments)
N = 3 for fifth order interpolation (5 vanishing moments)
N = j for 2j-1 order interpolation (2j-1
vanishing moments)
This function returns: non-zero for an error.
To achieve the standard two-channel-filter-bank
wavelet transform of a desired number of levels of wavelet coefficients,
this function should be called recursively on the same buffer
of data with a two-fold decrease in the num_frames input argument
for each successive recursion. In this manner, all of the wavelet
coefficients will lie in the latter portion of the array, while
the first portion of the array will contain the "final average"
scaling coefficients when the recursion stops at the desired level
(usually 5 or 6 levels). Because of the recursion involved, the
input buffer should contain a sufficiently-high-power-of-2 frames
of data.
C. Inverse, lifted wavelet transform
int iflwt(float* input_buffer, int num_channels,
int num_frames, int N)
Performs one iteration of the inverse, lifted
wavelet transform. This function can handle interleaved data,
typically useful for multi-channel audio buffers. One frame is
defined as one sample value per channel input. For example, a
four-channel input buffer contains four samples per frame. To
illustrate the structure of the input buffer to this function,
the following is the buffer structure for a two-channel interleaved
input. Frames are presented sequentially in the buffer, with the
channel data being presented sequentially within each frame. The
inverse transform expects the scaling coefficients to lie in the
first half of the input buffer, and the wavelet coefficients to
lie in the second half of the buffer:
where F is the value of the input argument num_frames.
The reconstructed output is placed in the
input buffer. To continue with the two-channel example, the input
buffer would have the following structure for a two-channel audio
input after processing:
| frame1 | frame2 | frame3 | frame4 | ...etc. | |||||
| ch1(L) | ch2(R) | ch1(L) | ch2(R) | ch1(L) | ch2(R) | ch1(L) | ch2(R) | ...etc. | |
| input buffer array index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ...etc. |
The N input argument controls the number of
vanishing moments to use in performing the transform. Note that
in order to achieve perfect reconstruction, the same number of
vanishing moments must be specified in both the forward and inverse
lifted wavelet transform function calls.
Use
N = 1 for linear interpolation (one vanishing moment)
N = 2 for cubic interpolation (three vanishing moments)
N = 3 for fifth order interpolation (5 vanishing moments)
N = j for 2j-1 order interpolation (2j-1
vanishing moments)
This function returns: non-zero for an error.
To achieve the standard two-channel-filter-bank
inverse wavelet transform of existing wavelet coefficients and
an existing final average, this function should be called recursively
on the same buffer of data with a two-fold increase in the num_frames
input argument for each successive recursion. In this manner,
the recursion can reconstruct in place from more and more wavelet
coefficients as the recursion continues. Because of the recursion
involved, the input buffer should contain a sufficiently-high-power-of-2
frames of data.
III. Normal wavelet transform, circular
convolution
The following functions are defined in normal_wavelet_transforms.h.
Note the similarity of the usage of these functions to those listed
in II above with respect to the structure of the input_buffer.
A. Forward, normal wavelet transform.
int
fwt(float* input_buffer, long num_frames,
int num_channels,
float* low_pass_coefficients,
int num_low_pass_coefficients,
float* high_pass_coefficients,
int num_high_pass_coefficients)
Performs one iteration of the forward, normal
wavelet transform, using standard circular convolution techniques
to deal with the window boundaries. This function can handle interleaved
data, typically useful for multi-channel audio buffers. One frame
is defined as one sample value per channel input. For example,
a four-channel input buffer contains four samples per frame. To
illustrate the structure of the input buffer to this function,
the following is the buffer structure for a two-channel interleaved
input. Frames are presented sequentially in the buffer, with the
channel data being presented sequentially within each frame. The
inverse transform expects the scaling coefficients to lie in the
first half of the input buffer, and the wavelet coefficients to
lie in the second half of the buffer:
| frame1 | frame2 | frame3 | frame4 | ...etc. | |||||
| ch1(L) | ch2(R) | ch1(L) | ch2(R) | ch1(L) | ch2(R) | ch1(L) | ch2(R) | ...etc. | |
| input buffer array index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ...etc. |
The wavelet and scaling coefficients are the
outputs of the forward transform, and are replaced in the input
buffer with the scaling coefficients occupying the first half
of the input buffer, and the wavelet coefficients occupying the
second half of the input buffer. To continue with the two-channel
example, the input buffer would have the following structure for
a two-channel audio input after processing:
where F is the value of the input argument num_frames.
The num_low_pass coefficients, low_pass_coefficients
input arguments, num_high_pass_coefficients, and high_pass_coefficients
input parameters allow the user to specify a certain pair of analysis
filters. The num_* parameters determine how many coefficients
to use in the low or high pass coefficients arrays. If num_low_pass_coefficients
is 6, for example, then the values corresponding to indices 0,
1, 2, 3, 4, and 5 of the low_pass_coefficients array will specify
the 0th, 1st, 2nd, 3rd, 4th, and 5th filter coefficients of the
low_pass analysis filter, respectively. Please note that the user
is responsible for specifying the correct filter coefficients
for both the low and high pass channels of the analysis and reconstruction
filterbanks, as this function does no error checking for perfect
reconstruction.
To achieve the standard two-channel-filter-bank
inverse wavelet transform of existing wavelet coefficients and
an existing final average, this function should be called recursively
on the same buffer of data with a two-fold increase in the num_frames
input argument for each successive recursion. In this manner,
the recursion can reconstruct in place from more and more wavelet
coefficients as the recursion continues. Because of the recursion
involved, the input buffer should contain a sufficiently-high-power-of-2
frames of data.
This function returns non-zero for an error.
B. Inverse, normal wavelet transform
int
ifwt(float* input_buffer, long num_frames,
int num_channels,
float* low_pass_coefficients,
int num_low_pass_coefficients,
float* high_pass_coefficients,
int num_high_pass_coefficients)
Performs one iteration of the inverse, normal
wavelet transform, using standard circular convolution techniques
to deal with the window boundaries. This function can handle
interleaved data, typically useful for multi-channel audio buffers.
One frame is defined as one sample value per channel input. For
example, a four-channel input buffer contains four samples per
frame. To illustrate the structure of the input buffer to this
function, the following is the buffer structure for a two-channel
interleaved input. Frames are presented sequentially in the buffer,
with the channel data being presented sequentially within each
frame. The inverse transform expects the scaling coefficients
to lie in the first half of the input buffer, and the wavelet
coefficients to lie in the second half of the buffer:
where F is the value of the input argument num_frames.
The reconstructed output is placed in the
input buffer. To continue with the two-channel example, the input
buffer would have the following structure for a two-channel audio
input after processing:
| frame1 | frame2 | frame3 | frame4 | ...etc. | |||||
| ch1(L) | ch2(R) | ch1(L) | ch2(R) | ch1(L) | ch2(R) | ch1(L) | ch2(R) | ...etc. | |
| input buffer array index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ...etc. |
The num_low_pass coefficients, low_pass_coefficients
input arguments, num_high_pass_coefficients, and high_pass_coefficients
input parameters allow the user to specify a certain pair of resynthesis
filters. The num_* parameters determine how many coefficients
to use in the low or high pass coefficients arrays. If num_low_pass_coefficients
is 6, for example, then the values corresponding to indices 0,
1, 2, 3, 4, and 5 of the low_pass_coefficients array will specify
the 0th, 1st, 2nd, 3rd, 4th, and 5th filter coefficients of the
low_pass synthesis filter, respectively. Please note that the
user is responsible for specifying the correct filter coefficients
for both the low and high pass channels of the analysis and reconstruction
filterbanks, as this function does no error checking for perfect
reconstruction.
This function returns: non-zero for an error.
To achieve the standard two-channel-filter-bank
inverse wavelet transform of existing wavelet coefficients and
an existing final average, this function should be called recursively
on the same buffer of data with a two-fold increase in the num_frames
input argument for each successive recursion. In this manner,
the recursion can reconstruct in place from more and more wavelet
coefficients as the recursion continues. Because of the recursion
involved, the input buffer should contain a sufficiently-high-power-of-2
frames of data.
Go to: Title Page Chapter 1 Appendix A Appendix J Copyright Chapter 2 Appendix B Appendix K Abstract Chapter 3 Appendix C Appendix L Acknowledgements Chapter 4 Appendix D References Table of Contents Chapter 5 Appendix E List of Figure Conclusions/ Appendix F List of Tables Future Directions Appendix G List of Audio Examples Appendix H List of Programs Appendix I