Overview
blitzwave is a c++ wavelet library building on the blitz++ array template library. blitzwave is heavily templated and supports wavelet decompositions of n-dimensional arrays of various numerical data types. You can define and use your own wavelets, a number of pre-defined, ready-to-use wavelets are available.
Performance is quite good, similar to the WAILI library (using datatype int for blitzwave).
The blitzwave library is placed under the GNU General Public License.
It is hosted on GitHub, also take a look at the project page.
What's new?
Version 0.7.0
- Made code compatible to newer GCC versions.
- blitzwave now uses namespaces. All classes and functions are available under the namespace "bwave". Please add "using namespace bwave;" or similar to your code to use blitzwave
- Changed build system to automake+autoconf.
- Moved test code to separate files.
- Changed C++ file suffix from .cc to .cxx.
Version 0.6.0
- A standard installer has been added ("make install").
- pkg-config is now supported for library detection (i.e. of blitz++).
- Improved compiler compatibility and language conformance. blitzwave will now compile with g++ -Wall -Werror -pedantic-errors -Wundef -Wno-long-long.
Version 0.5.0
- Blitzwave works with the blitz++ BZ_DEBUG option now.
- A TinyVector range-violation has been fixed.
Version 0.4.0
- More small bugfixes.
Version 0.3.0
- Some small changes and bugfixes.
Version 0.2.0
- A few Bugs have been found and fixed.
- There are more predefined wavelets now.
- API Documentation has been improved a lot.
- Lot's of small code changes and some small API changes.
Status
blitzwave is stable and produces mathematically correct results. It has been used in production for several different scientific projects (that I know of). The API may still be subject to minor changes.
Several popular wavelets are pre-defined in the library, more may be added over time.
If you should find bugs/errors, both in code or underlying math, please let me know. Corrections, patches and code contributions are always welcome.
Details
Wavelet Algorithm
blitzwave uses the fast and well-known lifting scheme for it's wavelet transformations. See the references for literature on the subject.
Boundary handling
Boundary handling is done via data extension. The extension is done anew in every lifting step, ensuring perfect reconstruction after decomposition-recomposition independent of extension scheme. Currently, only zero- and constant extension are implemented, symmetric extension and other methods will follow.
Documentation
The API-Documentation is available here.
Download
Releases
The source code of current and past blitzwave releases is available here.
Development
Since version 0.7.0, the blitzwave source code is managed with Git. You can clone the blitzwave Git repository on GitHub.
Installation
Blitzwave can be installed as a library with "make install". However, blitzwave consists of only 6 files, so it might be appropriate to just copy them into your Project.
The only library dependency is blitz++, you need to have that installed. Apart from blitz++ you will need an ISO-C++ compliant compiler, because both blitz++ and blitzwave make use of advanced C++ features. GCC 3.x will do nicely.
FAQ
How do i get started?
Run "./configure" and "make", then move to the "src" directory. Execute the "WaveletDecomp-test" binary which will demonstrate image compression and wavelet form reconstruction. There is a such a test-function included in each header file. Look at its implementation for some usage examples. (There is also an "examples" directory, but it's still quite empty.)
Which predefined wavelets are available?
blitzwave currently comes with the Cohen-Daubechies-Feauveau CDF(1,1) (= Haar Wavelet), CDF(2,2) (= LeGall(5,3), JPEG 2000), CDF(3,1), CDF(3,3), CDF(4,2) (Cubic-Spline, a variant, is also included), CDF(9,7) (also called Daubechies 9/7, JPEG 2000) wavelets and the well-known Daubechies D4 wavelet.
How do I define a wavelet?
To define a wavelet, you create a Wavelet object by specifying the appropriate lifting steps and normalization factors:
Wavelet myWavelet( "CDF(2,2)", sqrt(2.0), sqrt(2.0)/2,
Wavelet::LiftingStep(Wavelet::LiftingStep::DUAL, 0, 2, -1, -1),
Wavelet::LiftingStep(Wavelet::LiftingStep::PRIMAL, -1, 4, 1, 1)
);
You can then check if you've give the right values at the right place:
cout << myWavelet << endl;
This will result in a control output:
Wavelet: CDF(2,2)
Lifting steps:
dual lifting: d(i) = d(i) + 1/2 ( - s(i) - s(i+1) )
primal lifting: s(i) = s(i) + 1/4 ( d(i-1) + d(i) )
Normalisation:
s(i) = s(i) * 1.41421
d(i) = d(i) * 0.707107
Why are compile times so high?
This is because of the extensive use of templates in blitzwave and blitz++. I'm not sure yet if it's possible to speed up compiling while maintaining flexibility.
However, if compile times are unacceptably high for your needs, you can easily write a non-templated wrapper for a specific data-type and -dimensionality. Because blitz++ arrays can be created to use preexisting data without copying, neither blitz++ nor blitzwave need to be used by the interface of your wrapper. Therefore, blitzwave can be easily integrated into applications without using any of it's data-types.
Simple example for such a wrapper:
// simpleDecompose.h typedef short numtype; void simpleDecompose(numtype *data, int rows, int cols);
// simpleDecompose.cxx
#include "simpleDecompose.h"
#include <WaveletDecomp.h>
void simpleDecompose(numtype *data, int rows, int cols) {
using namespace blitz;
using namespace bwave;
// Create a blitz array on data assuming C-style memory layout
// (data is used directly, not copied):
GeneralArrayStorage<2> storage;
storage.ordering() = secondDim, firstDim;
Array<numtype, 2> array(data, shape(rows, cols), neverDeleteData,
storage);
// Create a CDF(2,2) nonstandard wavelet decomposition in 2 dimensions:
WaveletDecomp<2> decomp(WL_CDF_2_2, NONSTD_DECOMP);
// Apply the decomposition on the data (in situ):
decomp.apply(array);
}
Performance seems to depend on array size in a strange way. Why?
Decomposition speed will break down to about 10% for certain array sizes on some machines. This is because blitzwave need to do strided memory access (which is provided by blitz++). There reason for the performance breakdown does not lie within blitz++, however. Some machine architectures will to strided memory writes very slow for some specific stride lengths, especially greater powers of 2.
I've seen this behavior on Intel and AMD machines, on an Alpha to a lesser degree, but not on a Sun Sparc, for example. I don't know the technical reason, try this code snippet for a demonstration of the problem.
References
W. Sweldens. The lifting scheme: A new philosophy in biorthogonal wavelet constructions. In A. F. Laine and M. Unser, editors, Wavelet Applications in Signal and Image Processing III, pages 68-79. Proc. SPIE 2569, 1995.
W. Sweldens. The lifting scheme: A custom-design construction of biorthogonal wavelets. Appl. Comput. Harmon. Anal., 3(2):186-200, 1996.
R. Calderbank, I. Daubechies, W. Sweldens, and B.-L. Yeo. Wavelet transforms that map integers to integers. Technical report, Department of Mathematics, Princeton University, 1996.
B. Wohlberg and C. Brislawn, Reversible integer-to-integer transforms and symmetric extension of even-length filter banks, Proceedings of Visual Communication and Image Processing (VCIP) 2003.