Documentation for WPKTDEMO.EXE
(Wavelet Packet Transform Demonstration Program)

by

Mac A. Cody

INTRODUCTION

The program WPKTDEMO.EXE is a demonstration of the wavelet packet transform as
described in my article "The Wavelet Packet Transform" which appeared in the
April, 1994 issue of Dr. Dobb's Journal. The following files are included:

WPKTDEMO.EXE - The wavelet packet transform demonstration program.
WPKTDEMO.DOC - The file you are reading.
CHIRP.DAT - Signal data file of a sine chirp function.
CHIRP1.COF - Wavelet packet transform coefficient file for the chirp function.
Subband basis of the entire binary tree.
CHIRP2.COF - Wavelet packet transform coefficient file for the chirp function.
Wavelet basis of the entire binary tree.
CHIRP2.COF - Wavelet packet transform coefficient file for the chirp function.
An arbitrary basis which localizes on higher frequency subbands.
CVESA41.ZIP - Archive of Kendall Bennett's Universal VESA VBE driver TSR,
Version 4.1 (requires PKUNZIP 2.0 or greater to unzip).

The program will run on any IBM PC-compatible computer with an 80286 (or
greater) processor. A Super VGA graphics card and monitor are also required.
The graphics card must be capable of supporting VESA* Video BIOS Extension
(VBE*) 1.0 (or greater) and VBE mode 0x104 (1024 x 768, 16 colors).

Most Super VGA graphics cards already have support for VESA VBE, either
through the ROM BIOS on the graphics card or via a driver TSR. To determine if
your graphics card supports VESA VBE, run WPKTDEMO at the DOS prompt. If your
graphics card does not have support for VESA VBE, the following message will be
displayed:

"No VESA support with this display card".

Check the documentation which comes with your graphics card to see if a TSR
driver is available. Also, contact the manufacturer of the graphics card.

Even if there is a VESA VBE driver with your graphics card, WPKTDEMO may still
not run. If there is insufficient memory available for mode 0x104 (or if the
mode is not supported by the driver the following message will be displayed:

"Requested VESA mode is not available".

Check your documentation to see if you can install additional video memory (512
kbytes are required, usually, to support mode 0x104) or contact the manufacturer
for an updated VESA BIOS or driver.

As an immediate (if temporary) solution, I have enclosed a copy of Kendall
Bennett's Universal VESA VBE driver TSR, Version 4.1 to allow you to get up and
running. I MAKE NO GUARANTEE OF THE SUITABILITY OF THIS DRIVER WITH YOUR
GRAPHICS CARD AND I WILL NOT BE HELD RESPONSIBLE FOR ANY DAMAGES RESULTING FROM
THE USE OF HIS DRIVER (or my program for that matter). Installation
instructions for the driver are included with the driver in archive.


USING WPKTDEMO

Once WPKTDEMO is loaded correctly, the screen should display a signal in the
brown region. The signal is a "chirp", i.e., a sinewave with increasing
frequency over time. The signal is generated within the program itself. Below
the signal is four rows of alternating dark and light gray bands. These rows
represent redundant approximation (dark gray) and detail (light gray) data. The
data display in these bands are intermediate results in the calculation of the
wavelet packet basis. Below the redundant data levels is a single row of
alternating green and cyan bands. These rows represent the approximation
(green) and detail (cyan) coefficients of the wavelet packet basis. The initial
disjoint cover represented is a fifth-level subband basis. The full binary tree
is displayed. No transform has been calculated, so all values are zeroed.

Along the left-hand side of the wavelet packet display are labels indicating
the levels of the wavelet packet transform (4 through 0). Each level represents
a different level of scale. Each level is one half the resolution of the level
above and twice the resolution of the level below. The numbers between each
pair of dark gray/light gray and green/cyan bands indicate the basis function
pairs (or subband pairs) in the binary tree.

Below the signal and wavelet packet displays is the menu entry field used to
control the program. Starting on the left-hand side of the menu and working
down and to the right is displayed the following items:

Signal File - Name of the signal file to load or save. The string entered in the field should follow standard DOS file path and file name conventions. The entry is not case sensitive. The format for the file is as follows:

1024 (Integer value indicating number of samples in file.)
0.0000000000000e+00
1.5707632441631e-04
6.2830514264364e-04 (Sample values in floating point format.)
1.4136850594884e-03
2.5132106492058e-03
.
.
.
.

Transform File - Name of the wavelet packet transform coefficient file to load
or save. The string entered in the field should follow standard DOS file path
and file name conventions. The entry is not case sensitive. The format for the
file is as follows:

(Integer values indicating number of samples in original signal
1024 5 and the number of levels in the transform [always 5].)
0.0000000000000e+00 0.0000000000000e+00 (Values of alpha and beta.)
T
T (Thirty-one text characters indicating the states of thirty-one
T nodes representing the subband pairs of the wavelet packet
. transform binary tree. 'T' indicates an active subband pair,
. while 'F' indicates an inactive subband pair. Active subband pairs
. are used in calculating the wavelet packet basis represented by the
F disjoint cover.)
F
T
-0.0000000000000e+00
5.3722339838268e-06 (Coefficients of the wavelet packet transform for the
-1.9663178747461e-06 given basis including the undisplayed terminating
-5.8379489037445e-05 coefficients of the convolutions at the end of each
2.1475008461388e-04 subband. No redundant data is stored in the file.)
.
.
.
.

Pollen Parameterization - This method for generating orthogonal wavelet filter
coefficients was presented in my first article (see bibliography in the wavelet
packet article). The parameterization values are entered in the fields below:
Alpha - The current value of alpha (-pi <= alpha < pi).
Beta - The current value of beta (-pi <= alpha < pi).

Coefficients - The wavelet filter coefficients generated from the values of
alpha and beta. Two, four, or six coefficients will be generated depending upon
the values of alpha and beta.

Basis Function Pair - The quadriture mirror filter (QMF) pairs of the transform
generate adjacent frequency subbands at each level in the binary tree. Each QMF
pair also represents a basis function pair for each level at each 'node' in the
binary tree. These functions are recursively defined according to the
application of the scaling and wavelet functions while working from the top of
the tree down through the particular QMF pair. The values are entered in the
fields below:
Level - The level of the basis function pair in the binary tree.
Subband - The selected subband pair at the given level in the binary tree.
Active - A value of 'T' indicates an active subband pair, while 'F' indicates
an inactive subband pair. Active subband pairs are used in
calculating the wavelet packet basis represented by the disjoint
cover. An inactive pairs is set to black and are not in use. Active
pairs are displayed and are set to a color according to whether they
are part of the disjoint cover (green or cyan) or redundant data
(dark orlight gray) used in the calculation of the wavelet packet
coefficients in the disjoint cover

The two function displays on the right-hand side of the menu field represent
the recursively defined basis functions for the selected subband pair. For
example, if level 0 and subband 0 were selected, the functions would represent
the scaling function (green) and wavelet function (cyan) used in the fast
wavelet transform.

The blue help screen displayed in the middle of the screen lists the available
operations in the program. Note that the caret (^) represents holding down the
control key on the keyboard while pressing the appropriate function key.

F1: Display Help List - Displays the list of available functions.

F2: Load signal data file - Loads the file listed in the Signal File field. If
the file is not found or cannot be opened a beep will sound.

^F2: Save signal data file - Saves the file listed in the Signal File field. If
the cannot be opened a beep will sound. No warning is given if the file already
exists.

F3: Load transform coefficient file - Loads the file listed in the Transform
File field. If the file is not found or cannot be opened a beep will sound.

^F3: Save transform coefficient file - Saves the file listed in the Transform
File field. If the file cannot be opened a beep will sound. No warning is
given if the file already exists.

F4: Decompose signal - Generate the wavelet packet transform coefficients in the
disjoint cover from the signal and the decomposition wavelet filters.

^F4: Reconstruct signal - Reconstruct the signal from the wavelet packet
transform coefficients in the disjoint cover and the reconstruction wavelet
filters.

F5: Zero approximation coefficients selected - Sets the data values in the
approximation half of the selected subband pair to zero. Useful when analyzing
which coefficients are significant to the perfect reconstruction of the original
signal.

^F5: Zero detail coefficients selected - As above but for the detail half of the
selected subband pair.

F6: Zero all redundant coefficients - Used to show that only the wavelet packet

transform coefficients in the disjoint cover are needed to reconstruct the
original signal.

F7: Restore binary tree structure - Makes all basis function (subband) pairs
active. This is faster than manually activating them.

F10: Program exit - Return to the DOS prompt. No prompt is made for saving any
data generated.


Feel free to experiment with the program! The disjoint cover can be free
modified to create alternate wavelet packet bases. Try different wavelet
filters to correlate with the signal or concentrate the signal energy at lower
frequency bands. The following table presents a list of Pollen parameters for
'interesting' wavelets:

|---------------------------------------------------------------|
| Wavelet | Alpha | Beta |
|--------------------------+-----------------+------------------|
| Harr | 0.0* | 0.0* |
| Daubechies 4-coefficient | 1.047179551 | 0.0 |
| Daubechies 6-coefficient | 1.359803732 | -0.782106385 |
| Hat | 1.125930376 | 0.375465743 |
| City | 2.713208667 | -1.992853802 |
| Wall | 1.952966255 | -1.443386598 |
| Car Alarm | 0.0 | -3.141592654 |
|---------------------------------------------------------------|
*Any value is acceptable as long as Alpha = Beta.


WHERE'S THE SOURCE CODE!? (or the shameless plug!)

Unlike my previous articles, I have not provided source code listings to the
demo program beyond the wavelet packet transform routines themselves. This is
ecause the demo program is written using a wavelet software library I am
developing. The library is called Tsunami Plus. This name was chosen because
"tsunami" means, in Japanese, a tidal wave usually caused by an earthquake. The
wavelet transform "surged" onto the scene in the last six years and has
generated a great deal of interest in the mathematics and engineering
communities. The "plus" indicates that the library is more than just a
collection of wavelet transform routines.

The library contains routines which implement various forward and inverse
wavelet transforms, such as block-mode transforms, recursive transforms
(oriented towards real time processing), and two-dimensional fast wavelet
transforms for image processing applications. Support routines are provided to
allow the programmer to quickly develop DOS applications with the VESA* VBE*
graphics standard (Tsunami Plus is VESA VBE 1.0, 1.1, and 1.2 compatible) and
XMS support. Not only can wavelet transforms be executed; their input
parameters can be modified and displayed with a menuing system and the data can
be displayed in various formats. The library also contains support routines for
the management and display of transform data and the design and verification of
orthonormal wavelet coefficients. The library is written in Standard 'C' and
80X86-specific code (80286 and greater) is confined to the display functions.

Tsunanami Plus will be shipped as source code only, except for 80X86 DOS
executables of the demo programs. Instructions will be provided for compiling
the code with various compilers. Documentation for the various routines in the
library, the demo programs, and tutorial materials will also be provided.
Availability and price will be announced at a later date in 1994.

Below is a partial list of the routines that will be in Tsunami Plus (note
that this is a preliminary list and its content may change):

FAST WAVELET TRANSFORM ROUTINES

MakeFWTstruct - Create a FWT data structure on the heap.
DestroyFWTstruct - Remove a FWT data structure from the heap.
PFWT - Periodic Fast Wavelet Transform routine.
IPFWT - Inverse periodic Fast Wavelet Transform routine.
AFWT - Aperiodic Fast Wavelet Transform routine.
IAFWT - Inverse aperiodic Fast Wavelet Transform routine.
RecursiveFWT - Recursive Fast Wavelet Transform routine.


WAVELET PACKET TRANSFORM ROUTINES

MakeWPTstruct - Create a WPT data structure on the heap.
DestroyWPTstruct - Remove a WPT data structure from the heap.
MakeCoverStruct - Create a disjoint cover management structure on the heap.
DestroyCoverStruct - Remove a disjoint cover management structure from the heap.
SetCoverNode - Set/clear a node on the disjoint cover management structure.
PWPT - Periodic Wavelet Packet Transform routine.
IPWPT - Inverse periodic Wavelet Packet Transform routine.
AWPT - Aperiodic Wavelet Packet Transform routine.
IAWPT - Inverse aperiodic Wavelet Packet Transform routine.
RecursiveWPT - Recursive Wavelet Packet Transform routine.


TWO-DIMENSIONAL FAST WAVELET TRANSFORM ROUTINES

Make2DFWTstruct - Create a two-dimensional FWT data structure on the heap.
Destroy2DFWTstruct - Remove a two-dimensional FWT data structure from the heap.
2D_FWT - Two-dimensional Fast Wavelet Transform routine.
I2D_FWT - Inverse Two-dimensional Fast Wavelet Transform routine.


WAVELET FILTER CREATION, CONVERSION, AND SUPPORT ROUTINES

DilationCoeffs - Generate orthogonal wavelet filter coefficients from the
TeKolste parameterization angles.
AngularCoeffs - Generate TeKolste parameterization angles from the orthogonal
wavelet filter coefficients.
PollenToTeKolste - Convert Pollen parameterization angles to TeKolste
parmeterization angles.
TeKolsteToPollen - Convert TeKolste parameterization angles to Pollen
parmeterization angles.
CheckAngles - Validate TeKolste parmeterization angles.
CheckCoeffs - Validate orthogonal wavelet filter coefficients.
MakeWaveletFilters - Generate wavelet quadriture mirror filter (QMF) pairs.
from wavelet filter coefficients.
CascadePhiAndPsi - Generate recursively-defined scaling and wavelet functions.


EXTENDED MEMORY MANAGEMENT ROUTINES (support for the 2D FWT routines)

InitXMS - Initialize access to the XMS driver.
XMSversion - Retrieve the XMS driver version number.
QueryFreeXMSmem - Determine amount of free XMS memory.
AllocateXMSblock - Allocate an XMS block.
FreeXMSblock - Free an XMS block.
MoveXMSblock - Move an XMS block.
LockXMSblock - Lock an XMS block.
UnlockXMSblock - Unlock an XMS block.
GetXMShandleInfo - Get information on a handle to an XMS block.
ReallocateXMSblock - Reallocate an XMS block.
RequestUMBblock - Request an upper memory block.
ReleaseUMBblock - Release an upper memory block.
ReallocateUMBblock - Reallocate an upper memory block.


VESA VBE GRAPHICS SUPPORT ROUTINES

InitVESAgraphMode - Initializes selected VESA VBE graphics mode.
InitCharSets - Initializes text characters display capability.
SelectCharSet - Select character set for future text output to display.
GetCharSet - Get current character set in use.
ReadDACregs - Get current VGA DAC register values.
WriteDACregs - Set new VGA DAC register values.
SetDrawColor - Set new color for future drawing.
SetCharColor - Set new color for future character output.
SetDACwidth - Set new effective width of DAC registers (requires VESA VBE 1.2
compatible BIOS which supports change of DAC width).
GetDrawColor - Get current drawing color in use.
GetCharColor - Get current character color in use.
GetDACwidth - Get current effective width of DAC registers (requires VESA VBE
1.2 compatible BIOS which supports change of DAC width).
DrawChar - Draw a character on the display.
DrawStr - Draw a string of characters on the display.
BlockToScreen - Place image block on the display.
RowToScreen - Place array of image data on the display.
DrawRectangle - Draw rectangle on the display.
DrawWaveform - Draw waveform on the display.


OFF-SCREEN IMAGE GENERATION ROUTINES

ShiftImageBlock - Shift image in data block.
CopyImageBlock - Copy image in data block to another data block.
WaveformImageBlock - Draw waveform image in a data block.
ScaleogramImageBlock - Draw wavelet scaleogram image in a data block.
GrayscaleImageBlock - Draw gray scale data in a data block.
DataSetMagnitude - Calculate maximum magnitude of data in an array.


BASIC MENUING SYSTEM ROUTINES FOR VESA VBE GRAPHICS MODES

DrawMenuField - Place new character data in menu field.
DrawGenericMenu - Draw user-defined menu on the display.
ProcessGenericMenu - Process context-sensitive character entry in menu.
IntEntryProc - Process integer-valued data entry in menu field.
RealEntryProc - Process real-valued data entry in menu field.
CharEntryProc - Process character string entry in menu field.


*VESA is a registered trademark of the Video Electronics Standards Association.
VBE is a trademark of the Video Electronics Standards Association.