Fractal tone compression
Fractal sound compression is a method for lossy compression of digitized, one-dimensional signals, such as B. Sound signals, in which the self-similarity in the signals is exploited.
This process found its origin in fractal image compression , which goes back to the theoretical foundations of Michael F. Barnsley and Alan D. Sloan .
principle
Here, too, the idea is based on a certain type of fractals, the Iterated Function System (IFS). Here, complex maps are created with a set of affine maps of the signal in itself.
In contrast to images, audio signals do not have a second dimension, but are one-dimensional signals. Nevertheless, the basic function of the fractal algorithms from image compression can be easily transferred to this type of signal.
The coding process itself is identical to that of the image compression. The main difference lies in the number of possible transformations that can be applied to a one-dimensional signal. Due to the lack of a second dimension, there are significantly fewer options. Specifically, there are seven relevant transformations:
- Identity s (t) → s (t)
- Vertical shift (offset) s (t) → s (t) + o
- Horizontal shift (time) s (t) → s (t + Δ t)
- Stretching / compressing (dynamics) s (t) → d × s (t)
- Vertical mirroring (phase shift) s (t) → -1 × s (t)
- Horizontal reflection (time inversion) s (t) → s (-t)
- Contraction (time dilation) s (t) → s (a × t)
The transformations 4 and 5 as well as 6 and 7 can be combined so that effectively only five possible transformations are available.
The coding then proceeds according to a simple scheme. The algorithm divides the signal into a defined number of target blocks a and source blocks b and tries to find a transformation for each of these target blocks that transforms an original block and thus maps the target block as ideally as possible.
It should be noted that the block must be larger than the block , since fractal compressions are based on contracting functions. If a corresponding transformation has been found for each target block, the actual signal is discarded and only the identified transformations are saved in its place. The compression factor that can be achieved with this method is only determined by the number of (sample) values per target block. The more values a target block contained, the greater the compression factor. Theoretically, arbitrarily high compression factors can be achieved.
The search for a set of such transformations is extremely time-consuming, which, along with various unsolved quality problems, is the main reason why fractal compression of audio signals has never been seriously considered.
A sound signal is reconstructed iteratively. Any signal is started, the total length of which must correspond to the original signal. Then all stored transformations are carried out. The signal obtained in this way is used again as the output signal for the next iteration. With each iteration, the reconstructed signal becomes more similar to the original signal. These iterations are repeated until no further improvement is achieved.
quality
The achievable acoustic quality of a fractal tone compression depends on the one hand strongly on the compression factor to be achieved, on the other hand it is also dependent on some special features caused by the method. In general, the higher the compression factor, the worse the quality. With the process as such, there are two major problems that have a lasting effect on quality. Fractal compressions are based on contracting functions. This means that there is always a loss of high-frequency signal components. The reason for this lies in the sampling theorem and cannot be circumvented. In addition, due to the block-based compression, there are phase jumps at the block boundaries in the decoded signal, which are acoustically expressed as crackling. This problem can be avoided by appropriate post-processing of the decoded signal with e.g. B. wavelet transformations can be mitigated or even eliminated.
In general, however, fractal compression does not achieve the quality of e.g. B. psychoacoustic processes like MP3 or RealAudio .
See also
literature
- Michael F. Barnsley, Lyman P. Hurd: Image Compression with Fractals. Vieweg, Braunschweig et al. 1996, ISBN 3-528-05464-6 .
- Reiko Klimpsch: Development and analysis of a fractal method for tone compression. Diploma thesis, 2002, [1] .
- Stephan Schneider: Development and analysis of a fractal coding method for speech signals (= series of process models. Vol. 4). Köster, Berlin 2001, ISBN 3-89574-416-6 (also: Cottbus, Technical University, dissertation, 2001).