An Improved Fractal Image Coding Algorithm Based on Wavelet Domain

Wavelet image coding and fractal image coding are two different image coding methods, each with its own characteristics and limitations. After an image is transformed by wavelet, its sub-images in the same direction but with different resolutions have strong similarities, which is complementary to the characteristics of fractal coding. Since 1995, Rinaldo and Calvagno first proposed and implemented an algorithm combining wavelet and fractal image coding. Since then, a variety of image coding algorithms combining wavelet transform and fractals have emerged. Some of these algorithms prove that fractal image decoding in the wavelet domain can be achieved by continuous extrapolation of low-resolution wavelet coefficients to high-resolution coefficients, that is, decoding does not require cyclic iterations and is unconditionally convergent; some use smooth wavelet basis to eliminate the block effect of reconstructed images at high compression ratios; some derive that the shrinkage factor of affine transformation is not restricted, which can ensure decoding convergence; at the same time, the tree structure of wavelet coefficients provides a natural and efficient Domain block classification method. In addition, some studies focus on the classification of fractal blocks and fractal prediction based on wavelet zero tree structure.

On this basis, this paper proposes an improved fractal image coding algorithm based on wavelet domain by analyzing the compression algorithm of basic fractal image coding. This improved algorithm includes two parts: (1) According to the different energies contained in each sub-image after wavelet decomposition of the image, considering the direction, texture characteristics and other information represented by each sub-image, a non-uniform fractal coding scheme is adopted for each sub-image, that is, when performing fractal coding in wavelet domain, the fractal blocks selected are not necessarily all squares. For wavelet sub-images with texture characteristics in different directions, fractal blocks of different shapes are selected; (2) According to the correlation between the wavelet transform coefficients of the image in different resolutions in the same direction and in different directions of the same resolution, for each image block, a similar block with the best fractal match is found on the sub-band image of the same direction with a lower resolution. These similar blocks form a prediction tree one by one. The decoding end restores the image blocks at all levels through the fractal prediction of the prediction tree. Experiments have shown that this improved algorithm can greatly improve the speed of fractal coding and achieve a higher compression ratio.

1 Basic fractal coding compression algorithm

The main content of the basic fractal coding compression algorithm is: the image to be encoded is divided into non-overlapping sub-blocks (Range Block), called image blocks R, and the image is divided into larger blocks (Domain Block) that can overlap each other, called similar blocks D. The R blocks and D blocks after segmentation are classified, such as: smooth areas with gentle changes, edge areas with sudden changes, and intermediate areas with gentle changes, so that the matching blocks have the same regional properties. For each R block Rj in the same area after classification, a matching D block Dj is found, so that Dj can be approximated to Rj through the affine function ψj, thereby obtaining a set of affine transformation groups ψ1, ψ2...ψN, that is, a fractal iterative system. As long as the transformation of the system is convergent and simpler than the original system, fractal compression is achieved. The basic fractal coding algorithm mainly searches and matches R blocks and D blocks after image segmentation. Its compression is relatively high, but the amount of calculation during compression is large, and the encoding compression time is very long.

2 Improved fractal image coding algorithm based on wavelet domain

The improved algorithm in this paper consists of two parts: the selection of fractal block shape in the wavelet domain fractal coding process and the formation of fractal prediction tree.

2.1 Selection of fractal block shape in wavelet domain fractal coding

In the above basic fractal compression coding process, when determining the shapes of R blocks and D blocks, each wavelet decomposition sub-image is a square. Since the energy contained in each sub-image after the wavelet decomposition of the image is different, and the characteristic information such as the direction and texture it represents is also different, it can be considered that when performing fractal coding in the wavelet domain, the selection of fractal blocks can be not square, but sub-blocks of different shapes can be selected based on the texture characteristics of different directions of the wavelet decomposition sub-image.

Taking 512×512 8 bit Figure 1 as an example, the experiment is carried out. The calculation results show that due to the different texture feature information of sub-images in different directions, the horizontal and vertical correlations in the LH, HL, and HH regions are different. Therefore, using blocks of different shapes for fractal coding in the decomposed sub-images in different directions can shorten the encoding time and achieve better image recovery effect. For example, in the LH region, through calculation and analysis, the row correlation length is greater than the column correlation length, and the image is mainly horizontal texture. A 4×2 rectangle can be used to segment R blocks and D blocks; in the HL region, the row correlation length is less than the column correlation length, and the image is mainly vertical texture. A 2×4 rectangle can be used to segment R blocks and D blocks; and in the HH region, the row correlation length is close to the column correlation length, so a square can be used for segmentation. At the same time, since the low-frequency sub-image in the upper left corner contains most of the energy of the image, the 2×2 square sub-block is still selected and does not participate in the calculation. The image block segmentation method is shown in Figure 2. The compression effect comparison of uniform and non-uniform block division is shown in Figure 3.

2.2 Formation process of fractal prediction tree

The formation principle of the fractal prediction tree is: Davis introduced the concept of zero tree into the theory of fractal image coding, and expanded the similar blocks and image blocks in fractal image coding to similar trees (Domain Tree) and image trees (Range Tree), so that the fractal matching between similar blocks and image blocks is transformed into the fractal matching between similar trees and image trees. On this basis, the representative blocks with the best fractal matching with the image block R can be found in the sub-images of wavelet decomposition at all levels, and then a representative tree is generated according to the zero tree structure from the representative blocks at all levels. By calculating and comparing the distances between the image trees R at all levels and the representative trees, it is determined that the representative tree with the smallest distance is the prediction tree of the image tree R.

Combined with the analysis of wavelet domain image segmentation shape, the wavelet domain segmentation is performed on Figure 1 as shown in Figure 2, and the formation diagram of the fractal prediction tree based on the wavelet domain is shown in Figure 4. The specific process is:

(1) First, the image is subjected to multiple wavelet transforms to generate sub-band images. The shape of each sub-band wavelet domain image segmentation is determined by calculating and analyzing the correlation between the image rows and columns. In order to ensure the signal-to-noise ratio, the sub-band images LL1, HL1, LH1, and HH1 with the lowest resolution are not encoded.

(2) Image trees, i.e., zero trees, are formed one by one in the horizontal, vertical, and diagonal directions. For example, R=(R1, R2, R3, R4) in the LH direction is one of the image trees, and D=(D1, D2, D3, D4) represents a similar tree in the HL direction. Then, a representative block E1 that best fractally matches the image block R2 is found in LH1, and a representative tree E=(E1, E2, E3) is generated from E1 according to the zero tree structure. Similarly, a representative block F2 that best fractally matches the image block R3 is found in LH2, and a representative tree F=(F1, F2, F3) is generated. A representative block G3 that best fractally matches the image block R4 is found in LH3, and a representative tree G=(G1, G2, G3) is generated.

(3) The distances between the image tree R and the three representative trees E, F, and G are calculated respectively. The representative tree with the smallest distance is the prediction tree of the image tree R. Then the position of the prediction tree at the corresponding level and the geometric transformation and affine transformation it has undergone are used as the fractal prediction code of the image tree R.

(4) The HL and HH directions are encoded in the same way, except that the shapes and sizes of the R and D blocks are different. In this way, in the improved algorithm, encoding only requires fractal encoding of one representative block in the representative tree. During decoding, other representative blocks can be derived from this representative block through the zero tree structure, and then the image block R can be fractally predicted.

Since the non-uniform fractal block shape selection has been adopted for the energy distribution characteristics of the wavelet decomposition graph, combined with this fractal prediction coding method, the result greatly improves the speed of fractal coding, shortens the coding time, and also achieves good results in improving the compression ratio.

3 Experimental Results

The experiment uses the image shown in Figure 1, and the basic fractal coding method and the improved algorithm in this paper are used for experiments. The reconstructed image is shown in Figure 5. In the basic fractal coding, the image block size in each sub-image is 4×4, and the similarity block size is 8×8. The segmentation method of the wavelet decomposition image block in the improved algorithm is shown in Figure 2. The similarity block size is taken as 2×2 times the image block size. The experimental results are shown in Table 1.

The improved fractal image coding algorithm based on wavelet domain proposed in this paper combines wavelet domain fractal with fractal prediction method. As shown in Table 1, compared with the basic fractal algorithm, the compression ratio is increased by about 2 times, the signal-to-noise ratio is reduced by 2 dB, and the encoding time is greatly shortened, which improves the encoding speed. This shows that the effect of improving the compression ratio is good.