Complexity-constrained best-basis wavelet packet algorithm for image compression

The concept of adapted waveform analysis using a best-basis selection out of a predefined library of wavelet packet (WP) bases allows an efficient image representation for the purpose of compression. Image coding methods based on the best-basis WP representation have shown significant coding gains for some image classes compared with methods using a fixed dyadic structured wavelet basis, at the expense however, of considerably higher computational complexity. A modification of the best-basis method, the so-called complexity constrained best-basis algorithm (CCBB), is proposed which parameterises the complexity gap between the fast (standard) wavelet transform and the best wavelet packet basis of a maximal WP library. This new approach allows a 'suboptimal' best basis to be found with respect to a given budget of computational complexity or, in other words, it offers an instrument to control the trade-off between compression speed and coding efficiency. Experimental results are presented for image coding applications showing a highly nonlinear relationship between the rate-distortion (RD) performance and the computational complexity in such a way that a relatively small increase in complexity with respect to the standard wavelet basis results in a relatively high RD gain.