Optimize fractal image coding speed by means of a generation differential genetic algorithm
Source: Application of Electronic Technology: Wang Jianming
Summary: The distribution characteristics of the degree of interlayer domain block and defining domain block in fractal coding process are studied, and propose to optimize its coding speed using the generation differential generator. The experimental results prove the effectiveness of the method.
Keywords: image compression fractal encoding genetic algorithm
The fractal image compression technology is an intrinsic self-similarity inherent to the digital image itself. Under the guidance of the fractal theory, the image data is converted to the associated fractal parameters, thereby achieving the purpose of compressing the data. In some cases, fractal compression can reach a very high compression ratio, so this is an image compression technology that is very developing.
The concept of fractal image compression is first proposed by Barnsley, but BarnselY is based on IFS-based fractal compression, and the automated compression process cannot be realized when the IFS is required. In 1990, Janquin used a local affine transformation to replace global affine transformations, proposed a fully automatic fractal image compression, so that this image compression technology moves into the first step. Although the Janquin mode solves the subgraph segmentation problem of Barnsley, the amount of calculation of the best match block is very considerable. In order to reduce the amount of calculation, there are many improvement methods from the 1990s, such as classification search, quadruple search, and so on. Although these methods saves search times to some extent, they still need to further reduce the time required for the encoding.
The genetic algorithm is a random search algorithm that has developed under the inspiration of natural evolution, and has a quick self-optimistic ability in front of the large computation. At present, people have begun to optimize the coding speed of fractal coding by the genetic algorithm. In order to further improve the coding speed of fractal compression, the distribution characteristics of each value domain block, all defined domain blocks and its similaritic extent, derived a generation of differential genetic algorithms suitable for fractal encoding; then utilize the generation differential generator algorithm Optimize fractal coding. Experiments show that the generation differential genetic algorithm has a faster convergence rate.
1 Basic principle of fractal image compression
The fractal theory is a very active and extensive discipline in modern nonlinear science. In particular, with the development of computer technology, fractal thinking and approach in pattern identification, natural image simulation, signal processing and other fields have achieved huge success.
The main process of fractal encoding is as follows: First split the image I to the value domain block {ri} mutually incompatible, for each value domain, to find the best match definition domain under compression, affine transformation Block DI, record the definition domain block and the transformation used, complete the encoding of a sub-block; repeat the above procedures, respectively, find the respective optimal match definition domain block, complete the entire image Code.
Under affine transformations, the error defining the domain and value domain can be determined by the following formula:
The optimal match definition domain of a value domain block RI is: Under the F mapping, define the domain block and value domain block to minimize (1). Using the Janquin method, in order to find defined domain blocks with minimum error ERR, the optimal match define domain block, each value domain block RI needs to match the number of defined domain blocks (assuming images, defining domain blocks, and value domain block) Both squares):
Num = (Image Size - Defining Domain Size 1) 2 × Sollation Transform
For example, for an image having a size of 256 × 256, if the value domain block is 16 × 16, the block is 32 × 32, then the defined domain block to be searched for each value domain is 50625. It can be seen that this matching process is very large.
The basic idea of 2 generation difference bibotics algorithm
The genetic algorithm is an optimization algorithm with intrinsic parallelism, and this paper tries to improve the encoding process using the optimization capability of the genetic algorithm. At the same time, the characteristics of the fractal coding process are improved in order to improve the convergence speed of the algorithm, and the genetic algorithm has been improved, and the genetic algorithm with generation of differential hybrid operators is proposed.
The hybrid operator in the genetic algorithm is a very important operator, and the sexuality of the hybrid operator also directly affects the convergence speed of the entire algorithm. This paper proposed in the generation of differential cream integration is: genetic algorithm is an optimization algorithm developed according to the idea of biological evolution in nature; with the increase of population evolution, in selecting operators, etc. Under the action, the average adaptation value of the population will increase in a large probability. Thus, it is assumed that the adaptation value of the population will increase in the increase of the evolution algebra, randomly select an individual from the adjacent two generation population, and the difference between the two individuals represents the direction increasing in the population adaptation value, also It is the desired evolutionary direction. It can therefore be used to form a new hybrid operator using the difference in neighboring two generation populations to produce a new individual, which will be close to the highest probability vector. In this paper, the genetic algorithm using the generation of differential hybrid operators is referred to as a generation difference generator algorithm without confusion. 3 Fast fractal compression algorithm based on generation differential genetic algorithm
3.1 Distribution characteristics of fractal coding median domain block and defining domain block
After a large number of studies have found that the similaritic distribution of a certain value block and all defined domain blocks during fractal coding:
(1) This distribution is a multipolar value, so finding the best matching definition domain block for a certain value domain block is actually a maximum problem with a multipolar value function;
(2) The value of the distribution function is changed in the vicinity of each of the extreme, that is, the definition domain block near the maximum similar block, (5) It is gradually changing with the similarity of the value domain block.
1 is a case where a value domain block is similar to all defined domain blocks in the LENA image and the TREE image, and the value domain block is randomly selected from 8 × 8 and 16 × 16 cases. The similarity is determined by (2). :
ADA = 1 / ERR (2)
Where ERR is determined by (1).
The distribution of the similarity is given by Figures 1 (b), (c) and 1 (e), (f), and it can be seen that the distribution of the similarity meets the above two features.
3.2 Constructing a differential hybrid operator
Since the fractal coding median domain block and the defined domain block similarity distribution have the above characteristics, the idea of the generation difference generator algorithm is applied here, so the fractal coding process can be optimized using the generation differential generator algorithm. The following constructs a generation differential hybrid operator that can be used for fractal encoding processes.
The space to be searched herein is configured by an image defining domain block. For each definition block, the coordinate of the left corner pixel point can be represented, one of the corresponding genetic algorithms may be represented as: x = (x, y) . The adaptation degree of individuals in the population is determined by the (3).
The generation differential hybrid operator can be expressed as:
Where [·] represents the normal number of hiestation functions, α, β, λ is less than 1. XNBest, XN-1BEST is the best individual in the N-generation and N-1 generation. Calculate the individual x:
That is, after the new population is generated, the following operation is performed: randomly select one individual from the new population, if the individual is appropriate to be X, then remain unchanged, otherwise the individual is replaced with the individual. (4) The value of α, λ in the formula may be the same as (3), and the value is the same herein.
3.3 Implementation of differential genetic algorithm
The size of the population is N, the basic structure of the generation differential generator is:
{
The memory matching of the three-generation evolution population is assigned, and its memory pointer is represented by PT-1, P 1;
T = 1; random initialized population PT-1, PT, PT 1;
Calculate the adaptation value of individuals in PT-1, PT;]
While (do not meet the termination conditions) DO
{
According to the individual adaptation value and the selection strategy, the selection probability Pi of the individual body in PT-1 and PT is calculated; the most suitable individuals in the PT are best to PT 1;
While (the individual in PT 1 is updated) DO
{
From PT-1, randomly select an individual, generate new individuals in accordance with the hybrid probability to generate a differential hybrid operator;
The new individual is used to use a variant operator according to variation probability;
}
Calculate the adaptive value of individuals in PT 1;
Press (3) to calculate XI and calculate the adaptation value of the XI, randomly select x (t 1) L from PI 1;
If the adaptation value of the XI is better than X (t 1) L, the xi copied to X (T 1) L in the position of PT 1; otherwise remain unchanged;
PTMP = PT-1;
PT-1 = Pt;
Pt = PTMP;
T = T 1;
}
} 4 experimental results
In order to verify the effectiveness of the generation differential generator in fractal coding, the JANQUIN coding method is optimized by the conventional generator algorithm and the generation differential genetic algorithm, and the optimization results are compared.
It is important to point out that this article only describes the optimization of an Anquin encoding method. In fact, the generation differential genetic algorithm is equally applicable to other improved fractal coding algorithms, such as quadruple search methods, etc.
The parameters employed in this paper are as follows: The number of populations is 50, the hybrid probability is 0.8, the genetic probability is 0.1, and the mutation probability is 0.1.
The parameters of the generation differential hybrid operator are:
For other improved fractal coding algorithms, such as four-fork tree search method, etc.
The parameters employed in this paper are as follows: The number of populations is 50, the hybrid probability is 0.8, the genetic probability is 0.1, and the mutation probability is 0.1.
The parameters of the generation differential hybrid operator are:
α = 1, β = 0.2, λ = 0.8.
Take the experiment with 256 × 256 grayscale Lena images, the value domain is 8 × 8, and the defined domain block is 16 × 16. The encoding process is optimized by the genetic algorithm and the generation differential generator, and then the same decoding algorithm is then decoded 10 times, and the results of partial decoding are given.
Where (A) is the original image of the Lena, (b) is the result of directly using the JANQUIn encoding method.
When experimenting, the change of the PSNR of the image is observed under the conditions of the same evolution algebra. Since the genetic algorithm is a random optimization algorithm, 10 calculations are performed by the same evolutionary algorithm, and the average PSNR of the decoded image is calculated, as shown in Table 1. The last column indicates the PSNR that decodes the image using an anquin method.
Table 1 experimental results
4 6 12 16 20 J GA 22 23.5 25.4 26.1 26.4 28.2 IDGA 22.4 24 26.5 27 27.8
The analysis of Table 1 can be known that since the generation differential generator makes full utilization of the distribution characteristics of the value domain block, under the same evolutionary algebra, the PSNR obtained by the generation differential generator is large, indicated. When the fractal coding is optimized, the former has a higher convergence speed than the latter.
