Wavelet encoded images.
Files "IWImage.h" and "IWImage.cpp" implement the DjVu IW44 wavelet scheme for the compression of gray-level images (see class IWBitmap) and color images (see class IWPixmap). Programs c44 and d44 demonstrate how to encode and decode IW44 files.IW44 File Structure --- The IW44 files are structured according to the EA IFF85 specifications (see IFFByteStream.h). Gray level IW44 Images consist of a single "FORM:BM44" chunk composed of an arbitrary number of "BM44" data chunks. Color IW44 Images consist of a single "FORM:PM44" chunk composed of an arbitrary number of "PM44" data chunks. The successive "PM44" or "BM44" data chunks contain successive refinements of the encoded image. Each chunk contains a certain number of ``data slices''. The first chunk also contains a small image header. You can use program djvuinfo to display all this structural information:
% djvuinfo lag.iw4 lag.iw4: FORM:PM44 [62598] PM44 [10807] #1 - 74 slices - v1.2 (color) - 684x510 PM44 [23583] #2 - 13 slices PM44 [28178] #3 - 10 slicesEmbedded IW44 Images --- These IW44 data chunks can also appear within other contexts. Files representing a DjVu page, for instance, consist of a single "FORM:DJVU" composite chunk. This composite chunk may contain "BG44" chunks encoding the background layer and "FG44" chunks encoding the foreground color layer. These "BG44" and "FG44" chunks are actually regular IW44 data chunks with a different chunk identifier. This information too can be displayed using program djvuinfo.
% djvuinfo graham1.djvu graham1.djvu: FORM:DJVU [32553] INFO [5] 3156x2325, version 17 Sjbz [17692] BG44 [2570] #1 - 74 slices - v1.2 (color) - 1052x775 FG44 [1035] #1 - 100 slices - v1.2 (color) - 263x194 BG44 [3048] #2 - 10 slices BG44 [894] #3 - 4 slices BG44 [7247] #4 - 9 slicesPerformance --- The main design objective for the DjVu wavelets consisted of allowing progressive rendering and smooth scrolling of large images with limited memory requirements. Decoding functions process the compressed data and update a memory efficient representation of the wavelet coefficients. Imaging function then can quickly render an arbitrary segment of the image using the available data. Both process can be carried out in two threads of execution. This design plays an important role in the DjVu system. We have investigated various state-of-the-art wavelet compression schemes: although these schemes may achieve slightly smaller file sizes, the decoding functions did not even approach our requirements.
The IW44 wavelets satisfy these requirements today. It performs very well for quality settings resulting in high compression ratios. It should not be used for quasi-lossless compression because certain design choices deliberately sacrifice the IW44 quasi-lossless performance in order to improve the image quality at high compression ratios.
Little care however has been taken to make the IW44 encoder memory efficient. This code uses two copies of the wavelet coefficient data structure (one for the raw coefficients, one for the quantized coefficients). A more sophisticated implementation should considerably reduce the memory requirements.
Masking --- When we create a DjVu image, we often know that certain pixels of the background image are going to be covered by foreground objects like text or drawings. The DjVu IW44 wavelet decomposition routine can use an optional bilevel image named the mask. Every non zero pixel in the mask means the value of the corresponding pixel in the background image is irrelevant. The wavelet decomposition code will replace these masked pixels by a color value whose coding cost is minimal (see http://www.research.att.com/~leonb/DJVU/mask).
ToDo --- There are many improvements to be made. Besides better quantization algorithms (such as trellis quantization and bitrate allocation), we should allow for more wavelet transforms. These improvements may be implemented in future version, if (and only if) they can meet our decoding constraints. Future versions will probably split file "IWImage.cpp" which currently contains everything.
Alphabetic index Hierarchy of classes