Wavelet compression is the general name for a class of image encoding methods using two-dimensional wavelet decomposition of an encoded image or its parts. Usually implies compression with loss of quality.
A significant role in wavelet compression algorithms is played by the concept of representing the results of the wavelet decomposition in the form of a zero-tree .
The bit planes of the wavelet decomposition coefficients ordered in a null tree are coarsened and encoded further using statistical compression methods.
Content
The essence of the method
Wavelet compression in modern image compression algorithms allows significantly (up to two times). to increase the compression ratio of black and white and color images with comparable visual quality with respect to the previous generation algorithms based on discrete cosine transform , such as, for example, JPEG .
To work with discrete images, a wavelet transform is used, known as the Mall algorithm , named after its inventor Stephane Mallat ( French: Stephane Mallat ). The original image is decomposed into two components - high-frequency parts (consisting mainly of sharp changes in brightness), and a smoothed smaller version of the original. This is achieved by using a pair of filters, and each of the resulting components is half the size of the original image. As a rule, filters with a finite impulse response are used, in which the pixels that fall into a small “window” are multiplied by a given set of coefficients, the obtained values are summed, and the window is shifted to calculate the next output value. There is a close relationship between wavelets and filters. Wavelets do not directly appear in the algorithms, but if you iterate the appropriate filters on images consisting of a single bright dot, then the wavelets will more clearly appear on the output.
Since the images are two-dimensional, filtering is performed both vertically and horizontally. This process is repeated many times, and each time a smoothed version from the previous step is used as an input. Since the images of "details" usually consist of a set of sharp boundaries and contain vast areas where the intensity is close to zero. If it is permissible to neglect a certain amount of small details, then all these values can simply be reset. The result is a version of the original image that is highly compressible. To restore the original, the Mall algorithm is again applied, but with a couple of filters inverse to the original ones.
The JPEG algorithm, unlike the wavelet one, compresses individually each block of the original image of size 8 by 8 pixels. As a result, at high compression ratios, a block structure may be noticeable in the reconstructed image. With wavelet compression, such a problem does not arise, but distortions of another type may appear, having the form of a “ghostly” ripple near sharp boundaries. It is believed that such artifacts, on average, are less noticeable to the observer than the "squares" created by JPEG.
The Federal Bureau of Investigation ( FBI ), USA , has introduced a standard for wavelet fingerprint image compression. However, the freedom to choose filters can be very useful in the compression problem: algorithms based on the “best basis” principle select the optimal filter for individual image sections, and algorithms using wavelet packets achieve effective representation of details by varying the filtering depth in different areas .
Video Compression
Another problem is how to effectively use the similarity of consecutive frames in video compression. In early algorithms, such as Motion JPEG , this factor was ignored, and frames were compressed individually. MPEG uses a block comparison algorithm, which tries to isolate areas that changed when the frame was changed. Blocks that have not changed can not be saved. In the third approach, which is convenient for wavelet compression, time is considered as the third dimension of the data array to which the Mall algorithm is applied. The lack of movement is manifested in the zeroing of the corresponding parts in the temporary direction. Finally, it should be noted that the wavelet transform itself does not compress anything. It only carries out image preprocessing, after which the efficiency of conventional compression methods increases dramatically, even when using universal algorithms and programs (such as LZW and PKZIP ) that are not adapted to a specific task. However, the use of encoding methods that take into account the structure of the wavelet transform can significantly increase the degree of compression. One of the widely used methods of this type is the zero-tree compression method. It is based on the assumption that if a certain area of the image does not contain non-trivial information at a certain level of resolution, then with a high probability it will not be informative at a finer level of resolution. The wavelet transform of the image can be stored in the form of a tree, the root of which is a highly smoothed version of the original, and the branches representing individual blocks break off at a level where further processing does not give a noticeable refinement. Such a tree can be successfully compressed using conventional methods such as arithmetic coding, which are used in almost all compression algorithms.
Implementations
The most famous wavelet compression algorithm is JPEG 2000 . Wavelet compression is also used when encoding to the DjVu format. There are also many non-standardized image encoding algorithms and video sequences based on wavelet compression designed for specialized applications. For example, one of the best-known algorithms used in video surveillance systems is Motion Wavelet and 3D Wavelet .
Examples of wavelet compression:
- Dirac
- ECW
- Ezw
- JPEG 2000
- Motion wavelet
- Mrsid
- Pixlet
- Rodudu
- Sif1
- Snow
- SPIHT
- Streamlogic
- Tarkin
- Windows HD Photo
- ICER