CN106600657A - Adaptive contourlet transformation-based image compression method - Google Patents

Abstract

The invention claims protection of an image compression method based on adaptive Contourlet transform, which belongs to the technical field of signal processing. In order to improve the sparsity of image representation, the present invention proposes an adaptive Contourlet transform based on the theory of pseudo-polar Fourier transform. This transformation can formulate different direction decomposition schemes according to different input images, and perform optimal sparse representation of images, thereby improving the effect of compression and reconstruction. In addition, this solution does not involve the design of traditional directional filter banks, and has low design complexity. The self-adaptive Contourlet transformation proposed by the invention has the advantage of matching the non-uniform direction distribution characteristics of images, and has universal significance in practical applications. Using adaptive Contourlet transform for image compression can avoid the poor image reconstruction effect caused by the fixed direction decomposition scheme.

Description

Image Compression Method Based on Adaptive Contourlet Transform

technical field

The invention belongs to the technical field of signal processing, in particular to an image compression method based on adaptive Contourlet transform.

Background technique

About 60% of the information obtained by humans is visual information, about 20% is auditory information, and the sum of information obtained through other channels is less than 20% of the total information obtained by humans. Image has become an important way for people to identify and obtain signals because of its intuitive, specific, and vivid characteristics. However, with the rapid development of information technology, the amount of image data increasing at a geometric rate far exceeds the speed of hard disk capacity expansion. Therefore, the research on image compression methods has always been a hot spot that people pay attention to.

Wavelet transform has been widely used in the field of image compression because of its time-frequency localization and multi-scale characteristics. It can effectively describe the point singularity characteristics of one-dimensional signals, and realize the optimal representation of one-dimensional signals. However, with the deepening of the application and research, people also found some shortcomings of the wavelet transform. Because of its limited directionality, the separable wavelet formed by the one-dimensional wavelet cannot "optimally approximate" the wavelet transform with a line or surface singularity. function, so the wavelet transform cannot achieve the "sparse" representation of the important features of two-dimensional images or high-dimensional images, and the theory of compressed sensing shows that: the sparser the image representation, the better the effect after compression and reconstruction.

It is the above shortcomings of wavelet analysis that prompt people to look for a more effective representation method. After years of efforts by researchers, Multiscale Geometric Analysis (MGA) was proposed and developed rapidly. Among them, the Contourlet transform proposed by Do et al. is a "true" two-dimensional image representation method. It provides a basis function whose length and width of the support interval vary with the scale, and can describe the inherent geometric characteristics of the image in a near-optimal manner, and is more compact and sparse than the wavelet image representation. The transformation mainly consists of two parts: first, the "point" singularity in the image is captured by the Laplacian Pyramid Filter Bank (LP) for multi-scale decomposition; then the direction filter bank (DFB) distributes the points in the same direction The singular points above synthesize a coefficient to realize multi-directional decomposition. Contourlet transform can represent geometric features such as image edges and textures in a sparser way, and has better direction selectivity than wavelet transform in the high frequency part, which is very beneficial to image compression. However, the DFB is limited by the tree structure in the transformation, and the direction division scheme and the number of direction subbands are fixed. However, the orientation distribution of most natural images is arbitrary, and a fixed orientation decomposition will definitely affect the effectiveness of image sparse representation. In this context, this paper proposes an adaptive Contourlet transform that can adaptively perform orientation decomposition according to the orientation distribution characteristics of the input image. Based on this transform, an image compression method based on adaptive Contourlet transform is proposed.

Contents of the invention

The object of the present invention is to address the deficiencies in the prior art, and propose a new MGA tool—adaptive Contourlet transform, which can adaptively match the direction distribution of an input image and perform a sparse representation algorithm for non-uniform direction decomposition. And based on this algorithm, an image compression based on adaptive Contourlet transform is proposed. This method first designs an adaptive directional filter bank (ADFB) based on pseudopolar Fourier transform theory, and combines it with LP to form a new multi-scale and multi-directional decomposition structure. The new scheme first performs scale decomposition on the input image, and then adaptively decomposes on the medium and high frequency sub-images, so as to improve the sparsity of the image representation, thereby improving the effect of the reconstructed image.

The adaptive direction division scheme in the new algorithm can more accurately describe the unique direction features of different natural images, and preserve the inherent geometric structure features (contours and edges) in the image to the greatest extent. Its simple design complexity also greatly improves the practicability of the algorithm. This algorithm helps to improve the sparsity after image decomposition. The principle is that the traditional DFB in Contourlet transform is limited by the tree structure, and the sparsity is greatly reduced when representing images with uneven distribution of directions. Therefore, in order to more accurately describe different input images, it is necessary to design an adaptive non-uniform directional filter bank. The present invention adopts a threshold judgment method, and formulates a matching direction division scheme according to the distribution characteristics of the image. The invention detects the energy distribution of the image in each ray direction (through the origin of the frequency plane) through the pseudo-polar Fourier transform and decomposes the direction. The biggest advantage is that it can realize non-uniform two-dimensional in one-dimensional design complexity. Orientation filtering, and improving image sparse representation effectiveness. In order to prevent the low-frequency components of the image from leaking into several directional subbands, the combination of the multi-resolution decomposition module LP and the invented directional decomposition module ADFB is promoted to obtain an adaptive Contourlet transform. Obviously, adaptive contourlet transform also has the advantage of adaptive non-uniform orientation decomposition. In summary, the present invention has great significance in practical application.

Description of drawings

Pseudopolar grid of the present invention of Fig. 1;

Fig. 2 BV and BH part based on Cartesian grid of the present invention;

The adjusted pseudo-polar Fourier transform result X _PPFFT (k ₁ , k ₂ ) grid of the present invention;

Fig. 4 is the flow chart of compressed sensing based on adaptive Contourlet transform of the present invention;

The ray direction energy level diagram of Fig. 5 about Barbara of the present invention;

The adaptive non-uniform frequency division scheme about Barbara of the present invention of Fig. 6;

Fig. 7 is a comparison chart of reconstructed image PSNR under different sampling rates about Barbara of the present invention;

detailed description

Pseudopolar Fourier transform is to perform Fourier transform on the image on the pseudopolar grid, and the image is transformed into a Fourier representation on uniform polar coordinates or logarithmic polar coordinates. The pseudopolar grid is composed of points distributed at equal intervals along the ray, and these different rays are equally spaced along the slope direction, including two types of samples, the basic vertical (BV) part and the basic horizontal (BH) part, as shown in Figure 1 (solid dots represent BV, hollow dots represent BH). For an N×N image Its two-dimensional Fourier transform is:

For ω _x and ω _y in the above formula, the following variable substitutions are carried out in sequence,

The BV and BH parts can be obtained accordingly, as shown in Figure 2,

Wherein, in X _BV (m,l), m represents the slope direction ω _x /ω _y , and in X _BH (m,l), m represents the slope direction ω _y /ω _x ; l represents the radial direction. It has the same computational complexity O(N ² logN) as the fast calculation Fourier transform algorithm in Cartesian coordinates. At the same time, it is also proved that the fast algorithm is stable and reversible, and only needs one-dimensional operation to realize the inverse transformation of pseudopolar Fourier transform.

Due to the rotation characteristics of the pseudopolar Fourier transform, a rectangular support region on the pseudopolar grid corresponds to a wedge-shaped region on the frequency plane, that is, the pseudopolar Fourier transform and the wedge-shaped direction filter bank have similar geometric characteristics. Based on the above principles, we can properly adjust and extract the pseudo-polar Fourier transform results to achieve non-uniform wedge direction decomposition. Because the BH and BV parts are sequentially obtained through different variable substitutions, in order to simplify the design and ensure the smoothness of the slope direction, we merge them through the following steps:

1. Translate X _BH (m,l) to the left along m by N/2;

2. Reverse X _BH (m,l) on the m axis;

3. Translate the inverted X _BH (m,l) to the right along m by N/2.

Get the adjusted pseudo-polar Fourier transform result X _PPFT (k ₁ , k ₂ ), as shown in Figure 3,

Among them, _k1 represents the ray direction, which has a continuous and smooth interval after adjustment _; k2 represents the radial direction.

In order to achieve self-adaptability, it is necessary to quantify the different support intervals in the non-uniform partition scheme, and the data on which the quantization is based is the energy distribution of the input image in the frequency domain. Obviously, it is impractical to over-consider the amplitude of each frequency sampling point, so we adopted a compromise solution: calculate the energy level of each wedge-shaped sub-band, and then make threshold discrimination. Specific steps are as follows:

(1) Perform an adjusted pseudo-polar Fourier transform on the input image x(n ₁ ,n ₂ ) to obtain X _PPFT (k ₁ ,k ₂ );

(2) Calculate the sum of elements in each column in X _PPFT (k ₁ ,k ₂ ) to obtain S ₁ (k ₁ ). The elements in S ₁ represent the energy level of a ray direction component on the frequency plane [-π, π) ² ;

(3) Divide it into 2 ⁱ (i∈N ⁺ ) equal parts, calculate the sum of each part, and get S ₂ (k ₃ ). The elements in S ₂ represent the energy level of a wedge-shaped direction subband on the frequency plane [-π, π) ² ;

(4) set the threshold, That is, the energy minima of 2 ⁱ wedge-shaped subbands times;

(5) Compare the elements in S ₂ with th,

Among them, a _k = {1,1} means two direction sub-bands marked by S ₂ (2k-1) and S ₂ (2k), a _k = {2} means a direction marked by sub-band S ₂ (2k-1) Combined with S ₂ (2k), the direction subband that doubles the support interval is obtained. That is, there are two non-uniform partitioning schemes with sub-band composition in different support interval directions The number of elements in a M=length(a) represents the number of subbands, which is in the interval [2 ^i-1 , 2 ⁱ ]. Although the number M is variable in size, there is always established.

According to the decomposition scheme obtained above, the direction decomposition is realized through the multiplication operation in the frequency domain. First design a group of matrices composed of 0 and 1 (with the same size as X _PPFT (k ₁ ,k ₂ )), which correspond to the above decomposition scheme. Then multiply this set of matrices with the adjusted Fourier transform results in turn to accurately capture the desired frequency components. make represents the direction subband extracted from X _PPFT (k ₁ ,k ₂ ), and assuming a[0]=0, then we have

The spatial form of the directional subband supported by the wedge-shaped frequency can be obtained by performing inverse pseudopolar Fourier transform on the subband _Xp .

In order to eliminate the data redundancy generated in the above steps, it is necessary to add a sampling link at the back end of the direction decomposition stage. According to the multidimensional sampling theorem, in order to ensure that the output is rectangular, the sampling matrix must be in diagonal form. Because of the non-uniform division characteristics in this scheme, the sampling rate of the sampling matrix S _p required for the direction sub-bands with different frequency support intervals is also different, and the selection method is as follows:

in, with Corresponding to the BV part and the BH part respectively. From the above analysis, it can be seen that there are 2M-2 ⁱ direction subbands marked by 1, and the sampling rate of the sampling matrix is 1/2 ⁱ ; there are 2 ⁱ -M direction subbands marked by 2, and the sampling rate of the sampling matrix is 1/ ^2i-1 . Then the decomposed data volume is

That is, after the image is decomposed by direction, the total amount of data does not change, which is very suitable for image compression. To sum up, an image can adaptively obtain a set of non-uniform and redundant direction sub-bands through ADFB. The invention does not relate to the design process of the traditional directional filter bank, but realizes two-dimensional directional filtering in a more convenient way.

Like traditional DFB, to avoid low-frequency leakage, ADFB cannot provide image sparse representation alone. Therefore, we combine it with LP to form a new multi-scale and multi-directional analysis tool-adaptive contourlet transform. Each layer of LP decomposition obtains a low-pass image (generally regarded as non-sparse) and a band-pass image, which can be adaptively decomposed into a set of non-uniform orientation subbands by ADFB to match the orientation distribution characteristics of the image. The selection of the sampling matrix also ensures that the sub-bands after sampling can be completely reconstructed. The corresponding inverse transformation is performed on each sub-image, and the image can be reconstructed. The implementation process of image compression based on adaptive Contourlet transform is shown in Figure 4. In order to illustrate the effectiveness of the invention, we input the Barbara image for simulation, and take i=4, the energy level distribution in the ray direction is shown in Figure 5, and the generated non-uniform division scheme is shown in Figure 6. Finally, the image compression reconstruction effect comparison with the Contourlet transform of 4-layer DFB and the Contourlet transform of 3-layer DFB is shown in Figure 7. Among them, the random observation method and the orthogonal matching pursuit algorithm (OMP) were used in the experiment to achieve compression and reconstruction, and the performance index selected for the reconstruction effect was the peak signal-to-noise ratio (PSNR).

Claims (3)

1. An image compression method based on self-adaptive Contourlet transform includes the steps of firstly carrying out scale decomposition on an input image to obtain a low-pass image and a band-pass image, and further carrying out pseudo-polar Fourier transform after the low-pass image and the band-pass image are adjusted. And then generating a matched directional decomposition scheme according to the transformation result, wherein the matched directional decomposition scheme is obtained by carrying out threshold value discrimination on the energy level of each wedge-shaped directional sub-band of the image. And decomposing according to the scheme and carrying out two-dimensional sampling. Since the spectral partitioning scheme is not uniform, the sampling rate of the sampling matrix changes accordingly. And finally, randomly observing the sampled sub-images, and finishing reconstruction by adopting an OMP algorithm to observe the reconstruction effect.

2. The image compression method based on adaptive Contourlet transform as claimed in claim 1, wherein the adaptive directional decomposition of the input band pass image to match its directional distribution characteristics proposes an adaptive directional filter bank, and its specific decomposition process includes the following steps:

(1) for input image x (n)₁,n₂) Performing the adjusted pseudo-pole Fourier transform to obtain X_PPFT(k₁,k₂)；

(2) Calculating X_PPFT(k₁,k₂) The sum of each column of elements in (1) to obtain S₁(k₁)，S₁The element in (1) represents a frequency plane [ - π, π)²The energy level of the last ray direction component;

(3) divide into 2ⁱ(i∈N⁺) Dividing into equal parts, and calculating the sum of each part to obtain S₂(k₃)，S₂The element in (1) represents a frequency plane [ - π, π)²The energy level of the previous wedge direction sub-band;

(4) a threshold value is set, and the threshold value is set,i.e. 2ⁱOf energy minima of wedge-shaped sub-bandsDoubling;

(5) handle S₂The medium element is compared with th,

mergingObtaining a division scheme a, and performing directional decomposition based on the division scheme a。

3. The image compression method based on adaptive Contourlet transform as claimed in claim 1, wherein the sampling matrix with different sampling rates is sampled to realize the non-redundant directional decomposition according to the following formula:

according to the sampling scheme, the data redundancy of image direction decomposition can be completely eliminated.