Modern information technology / 2. Computer Science and Programming

Lishchuk O.O.

Vinnitsa National Technical University, Ukraine

Analysis of lossy image compression algorithms

Coding images according standard JPEG. To achieve large compression ratio using another method (except fractal) impossible. Therefore, the effective image coding is performed using several methods at several stages. This concept and the basis for the standards developed by the International Organization for Standardization (ISO), which are known as standard JPEG (Joint Photographic Expert Group) and MPEG (Motion Picture Experts Group). Standard JPEG is designed for compressing still images and MPEG - Moving Images [1-3].

The process of encoding JPEG scheme is divided into the following stages (Figure1):

Figure 1. The sequence of operations for image compression by JPEG method

1. Convert images to optimum color space (only in the case of the encoding color images).

2. Subsampling difference component color signal by averaging groups of pixels (only when encoding color images).

3. Execution SCE to reduce redundancy image data.

4. Quantized DCT coefficients of each block using weighting functions optimized taking into account human perception.

5. Encoding resulting factors using statistical Huffman coding.

Fractal image compression. Of the known methods of fractal image coding method allows you to receive the largest compression ratio. Fractal archiving based on the fact that the images are in a more compact form – with coefficients of iterated function systems (Iterated Function System – IFS). IFS is a set of three-dimensional affine transformations that transform one image to another. The transformation to be a point in three-dimensional space. The main disadvantage of fractal method is a low encoding rate, which is related to the fact that to produce high quality images for each rank unit must perform exhaustive of all domain blocks, and each block domain must perform at least eight affine transformations.

Recursive (wave) algorithm for image compression. This algorithm is aimed at compressing color and black and white images with smooth transitions, ideal for pictures of type X-ray images. The compression ratio in the range of 5-100. At high compression ratio for sharp borders, especially diagonal, possible distortion [4].

The basic idea of the algorithm is stored the difference between the average values of adjacent image blocks, which usually take values close to zero.

 Recursive Compression is based on the pyramid S-transformation, which can be used to compress photorealistic images almost lossless and lossy.

Compression is performed in two steps: first - S - converting the original image; second - converted data is encoded one of statistical methods. Both operations return that allows you to restore the original image. However, for large compression ratios should decline precision component representing the image obtained as a result of S-transformation, but so that distortions are not visually distinguishable.

Encoding. A challenging problem of ongoing research in fractal image representation is how to choose the ƒ1,...,ƒN such that its fixed point approximates the input image, and how to do this efficiently. A simple approach for doing so is the following:

1. Partition the image domain into blocks Ri of size s×s.

2. For each Ri, search the image to find a block Di of size 2s×2s that is very similar to Ri.

3. Select the mapping functions such that H(Di) = Ri for each i.

In the second step, it is important to find a similar block so that the IFS accurately represents the input image, so a sufficient number of candidate blocks for Di need to be considered. On the other hand, a large search considering many blocks is computationally costly. This bottleneck of searching for similar blocks is why fractal encoding is much slower than for example DCT and wavelet based image representations.

Literature

1. James D. Murray, William vanRyper, Encyclopedia of graphic file formats – 1997. – 672 page.

2. International Standard JPEG ISO/IEC 10918.

3. International Standard MPEG ISO CD 11172.

4. Vatolin D.S. Image compression algorithms. – Publishing Department of the Faculty of Computational Mathematics and Cybernetics, Moscow State University. Lomonosov, 1999. – 76 page.