CN103065336A - Directional pyramid coding method of image - Google Patents

Abstract

The invention discloses a directional pyramid coding method of an image. By changing a data structure of a traditional set partitioning in hierarchical tree (SPIHT) algorithm, a directional pyramid of coding of the algorithm is possible to realize. Because a directional pyramid SPIHT algorithm is characterized by being high in redundancy and practical, the directional pyramid SPIHT algorithm is put forward and is preferable, and therefore rebuilding effects of the whole, especially rebuilding effects of image edges and other features are better improved. The algorithm can effectively code and compress images applied to the field of machine visions.

Description

Coding Method of Image Orientation Pyramid

technical field

The invention relates to the field of image compression, in particular to a method for image directional pyramid compression and encoding. the

Background technique

1. Signal transformation and image pyramid

Signals are carriers of information. How to achieve effective representation of signals is a core issue in the field of signal processing. From a mathematical point of view, an image is a two-dimensional matrix of gray values. In an image, it is common to see regions of connected textures and similar gray levels that combine to form objects. If the object size is large or the contrast is strong (the whole of the image), usually only a lower resolution is required (Fig. 1(a), (b)); if the object size is small or the contrast is not high (the details of the image ), you need to use a higher resolution observation (Figure 1 (c), (d)). If objects vary in size, or in contrast, it is advantageous to study them at several resolutions. Of course, this is where the charm of multi-resolution processing lies. the

When the sampling rate of the signal meets the Nyquist requirement, the normalized frequency band must be limited between [-π, π]. At this time, ideal low-pass and ideal high-pass filters L(ω) and H(ω) can be used to decompose it into (for the positive frequency part) the low-frequency part with the frequency band in [0, π/2] and the frequency band in [ π/2, π] The high-frequency part reflects the overview and details of the signal respectively, as shown in Figure 2. Because the frequency bands do not overlap, the two output signals are orthogonal after processing. And because the bandwidth of both outputs is halved, the sampling rate can be halved without loss of information. This is the reason why "double decimation" can be introduced after filtering (the symbol ↓2 in Figure 2 represents the "two decimation" operation). The so-called double decimation is to output the input sequence every other time to form a new sequence whose length is shortened by half. A similar process can be repeated for each decomposed low-frequency part, that is, each level of decomposition decomposes the input signal of this level into a low-frequency rough approximation (overview) and a high-frequency detail part. Moreover, the output sampling rate of each stage can be further halved, so that the original signal x(n) is decomposed into multiple resolutions. the

An efficient but conceptually simple structure for interpreting images at multiple resolutions is the image pyramid. Image pyramids were originally used in machine vision and image compression. An image pyramid is a series of images that are arranged in a pyramid and whose resolution is gradually reduced. As shown in Figure 3, the bottom of the pyramid is a high-resolution representation of the image to be processed, and the top is a low-resolution approximation. As one moves to the upper levels of the pyramid, the size and resolution decrease. The size of the upper layer of the J-th layer of the pyramid (that is, the (J-1)th layer) is 1/4 of the J-th layer. Usually low-resolution images of pyramids are used to analyze large structures or the overall content of images, while high-resolution images are used to analyze the characteristics of individual objects. Such a coarse-to-fine analysis strategy is especially applicable in pattern recognition. the

Pyramid structure is an important method for signal multiscale/multiresolution analysis. Gaussian Pyramid (Guassian Pyramid) and Laplacian Pyramid (Laplacian Pyramid) structures are mainly used in compression coding algorithms for digital images. The Gaussian pyramid is obtained by continuously downsampling the original image, which is equivalent to continuous low-pass filtering in the frequency domain. Different layers of Gaussian pyramids are expanded and subtracted at the same scale, and the amount of subtraction is equivalent to high-pass filtering in the frequency domain, so that a Laplacian pyramid can be generated. In principle, the detail signal of this scale (that is, this layer) can be obtained by removing the low-pass smoothed signal from the input signal, but since the sampling rate of the smoothed signal is lower than that of the input signal, the two signals cannot be directly subtracted. In order to obtain the detail signal, it is necessary to interpolate the output signal of the previous step, interpolate M-1 pixels, and perform filtering to generate an image with the same resolution as the input signal, and then subtract it from the input signal to obtain the detail signal. Since the interpolation operation is performed on the smooth signal, the interpolation filter determines the similarity between the predicted value and the input value. In order to reconstruct the input signal, as long as the smooth signal is processed by the same low-pass filter to obtain an approximate signal, and then added to the detail signal, the original image can be completely reconstructed. the

2. Wavelet transform

The two-dimensional orthogonal wavelet transform of the image is another important image technology related to multi-resolution analysis, and it is also an important form of image pyramid, which can obtain the detailed information of the image in the horizontal, vertical and diagonal directions . Wavelet transform has a wide range of applications, mainly including image compression coding, image restoration, image denoising, feature value extraction and so on. The multi-resolution analysis composed of separable two-dimensional orthogonal wavelet transform is the most widely used type of two-dimensional wavelet transform. the

From the perspective of digital filters, Figure 4 shows the process of two-dimensional wavelet coefficient decomposition. Among them, L and H represent one-dimensional low-pass and high-pass filters, respectively, and the subscripts x and y represent filtering the matrix along the row direction and column direction, respectively. The feature of the separable situation is that it can be processed in two steps along the x and y directions (first filter the x direction and then filter the y direction). Due to the band-pass filter processing, the bandwidth is smaller than that of the original image. Subbands can be sampled without loss of information, so each level of processing has to go through two binary samplings. Among them, LL passes through the low-pass in the x and y directions, corresponding to the low-frequency components of the original discrete image on the next scale (ie, the next layer); LH passes through the low-pass in the x-direction and the high-pass in the y-direction, corresponding to the original image level The low frequency components in the direction and the high frequency components in the vertical direction; correspondingly, HL represents the high frequency components in the x direction and the low frequency components in the y direction; HH represents the high frequency components in the x and y directions. Figure 5 shows the spectral representation of the two-dimensional wavelet transform. The initial input matrix is regarded as a two-dimensional discrete image, and the four parts of the output obtained after a decomposition pass through different filters respectively, representing the general appearance of the original image (that is, the low-frequency ) information and detailed information in vertical, horizontal and diagonal directions. After a wavelet transform, the total output data volume is the same as the input data volume, but each component is classified according to the frequency information, which is convenient for signal processing. If we continue to decompose the overview part after the first decomposition, we can get the multi-scale analysis of the discrete image, that is, its details and overview at different scales. the

Similarly, after interpolation, filtering, and superposition of individual subbands, together with detailed information at different scales, the overview components at any fine scale can be reconstructed until the original image is finally completely reconstructed. the

3-way pyramid

Discrete orthogonal wavelet transform has become a commonly used representation method in multi-scale signal and image analysis because of its good time-frequency analysis characteristics, but it has a shortcoming that it lacks translation invariance due to uniform sampling of translation parameters. When the input signal occurs When the displacement changes small, the wavelet subband coefficient energy will change greatly. At the same time, for the rotation and scale changes of the two-dimensional image, the energy of the wavelet transform coefficients is also unstable. Another shortcoming of wavelet transform is that its direction selectivity is limited. In each scale space, it can only be decomposed into three directions: horizontal, vertical and diagonal. It is difficult to meet the continuous direction requirements of images. the

The Orientation Pyramid can be seen as a Laplace Pyramid that can choose an orientation and was invented by Eero Simoncelli in 1993. It is a linear multi-scale and multi-directional image representation framework, which is applied in the fields of image processing and computer vision. It can decompose the image into a series of sub-bands of different scales and directions. It can not only maintain translation and rotation invariance, but also control the direction, thus providing more abundant direction information than wavelet analysis. the

分别为原始图像和重构图像；空心圆圈表示该系统的嵌套。由图6可知，首先该算法被分解为高通和低通两个子带，信号经过互补的高低通滤波器并且不进行下抽样计算。随后低频子带被进一步分解为一组带通子带的图像和一个(更)低通的子带图像。经过带通滤波器B_i(ω)处理得到的带通子带具有不同的方向性。把这些作为基函数子带，通过调整它们的频率响应的线性组合就可以得到任意方向的方向子带。带通子带不进行下抽样计算。实际应用中，可以设计个数K的基函数方向子带，这些基函数的方向分别为

i＝0，...，K-1，例如，若K＝4，则基函数的4个方向分别为0°，45°，90°，135°。分解后的(更)低通子带进行下采样后再进行分解，重复以上过程，实现多分辨率分解算法。同样，经过内插、滤波和叠加每个子带的处理，可以恢复不同尺度上的细节信息，可以完全重构出原始图像。  Fig. 6 shows the system block diagram of one-layer directional pyramid decomposition and reconstruction of an image, and the subbands obtained by directional pyramid decomposition are polarity separable. Among them, H ₀ (ω) is a high-pass filter, L ₀ (ω), L ₁ (ω) are low-pass filters of different scales, B _i (ω), i=0, ..., K are bands in different directions pass filter; ↓2 and ↑2 represent the process of downsampling and upsampling respectively; X(ω) and

Original and reconstructed images, respectively; open circles indicate the nesting of this system. It can be seen from Figure 6 that the algorithm is firstly decomposed into two sub-bands, high-pass and low-pass, and the signal passes through complementary high- and low-pass filters without down-sampling calculation. The low frequency subbands are then further decomposed into a set of bandpass subband images and a (more) low pass subband image. The band-pass sub-bands obtained by processing the band-pass filter B _i (ω) have different directivities. Using these as basis function subbands, direction subbands in arbitrary directions can be obtained by adjusting the linear combination of their frequency responses. Bandpass subbands are not computed for downsampling. In practical applications, a number K of basis function direction subbands can be designed, and the directions of these basis functions are

i=0, . . . , K−1, for example, if K=4, the four directions of the basis function are 0°, 45°, 90°, and 135° respectively. The decomposed (more) low-pass sub-bands are down-sampled and then decomposed, and the above process is repeated to realize the multi-resolution decomposition algorithm. Similarly, after interpolation, filtering, and superposition of each sub-band, detailed information at different scales can be recovered, and the original image can be completely reconstructed.

Fig. 7 shows the spectrum representation of the four direction decompositions of the three scales (ie three layers) of the direction pyramid. where the frequency axis is [-π, π]. In the frequency domain, each subband of the directional pyramid decomposition is polarity separable. In the first step of preprocessing decomposition, the high-frequency subbands correspond to the four corners of the spatial frequency domain, and the low-frequency subbands correspond to the great circle area; in the second step of the decomposition process, the shaded area corresponds to the basis function bandpass subband in one direction; The centermost small circle area corresponds to the final low-frequency subband on the third scale after decomposition. the

Fig. 8 shows that for an input (e), the direction pyramid representation (a)-(d) of the image is obtained through calculation, and the process of reconstructing (f) through (a)-(d). Figures (a)-(c) are the subbands of the three-scale four-direction (0°, 45°, 90°, 135°) direction pyramid decomposition, and (d) is the low flux, and the high frequency is not shown. the

其中K为方向子带的个数。这相当于，若输入一副6x6的图像，金字塔的方向个数为4，不限制分解的尺度个数(即层数)，输出的方向金字塔将含有192个像素点，远超出原输入图像的36个像素点。尽管过完备性会限制金字塔算法的计算效率和储存成本，但也给许多图像处理方法提供了方便。  The main shortcoming of the direction pyramid is its over-completeness, and its over-completeness is

where K is the number of direction sub-bands. This is equivalent to, if a 6x6 image is input, the number of directions of the pyramid is 4, and the number of decomposition scales (that is, the number of layers) is not limited, the output direction pyramid will contain 192 pixels, far exceeding the original input image. 36 pixels. Although over-completeness will limit the computational efficiency and storage cost of the pyramid algorithm, it also provides convenience for many image processing methods.

4 Image coding method based on embedded wavelet transform

Due to the multi-resolution nature of wavelet transform, the coefficients obtained after wavelet transform have good distribution characteristics in space and frequency domains, so various image compression techniques based on wavelet transform have achieved great success. At present, there are two effective wavelet transform compression methods: one is that in 1993, J.M.Shapiro proposed an embedded zero tree wavelet coding method (EZW: Embedded Zerotree) based on the similarity between different levels of wavelet transform of an image. Wavelet); the other is that in 1996, A. Said proposed a new implementation method based on the basic idea of the EZW algorithm, that is, the multilevel tree set splitting algorithm (SPIHT: Set Partitioning in Hierarchical Trees). the

The idea of EZW coding is based on the assumption that there is still a strong correlation between wavelet coefficients at different levels, and this correlation is shown in the parent-child coefficient relationship of the wavelet tree. In fact, if the wavelet coefficients in the lower frequency layer are smaller than a certain threshold, the wavelet coefficients in the same direction and spatial position in the higher frequency layer are more likely to be smaller than the threshold. If a coefficient on the lower frequency layer is smaller than a certain threshold, and there are several coefficients in the next higher frequency layer and the descendant coefficient set corresponding to the coefficient on the higher frequency layer are greater than the threshold, the lower frequency layer This coefficient is defined as a zero tree, and then the threshold is halved, and then the image is scanned, and so on, and the zero tree is continuously generated. Throughout the successive approximation quantization process, scanning and symbol encoding are repeated by continually halving the current threshold until the target bitrate requirement is met. the

EZW is an embedded zerotree coding scheme based on wavelet transform. Its encoder can sort the bit streams to be encoded according to the importance, and end the encoding at any time according to the target code rate or distortion level; similarly, for a given code stream, the decoder can end the decoding at any time, and can get the corresponding code stream The reconstructed image at the target bitrate where the truncation is performed. the

The distribution characteristics of the wavelet coefficients are that the lower the sub-band coefficient value is, the greater the information content is, and the higher the high-frequency sub-band coefficient value is, the smaller the information content is. The EZW algorithm makes full use of the distribution characteristics of the coefficients after wavelet decomposition, first transmits the important bits of the lower frequency coefficients, and then transmits the important bits of the higher frequency coefficients. the

EZW first defines the zero tree structure: choose an image coefficient C _{i, j} after wavelet transformation, for a given threshold T, if |C _{i, j|} ≥ T, then the wavelet coefficient C _{i, j} is called An important coefficient, otherwise it is defined as an unimportant coefficient. If a wavelet coefficient is insignificant with respect to a given threshold T on a coarse scale, and all wavelet coefficients in the same spatial position corresponding to the coefficient are also insignificant with respect to the threshold T on a finer scale, these wavelet coefficients are said to form A zero tree is constructed, and the wavelet coefficients on the coarse scale are defined as the parent or root of the zero tree. The wavelet coefficients at corresponding positions on a finer scale are descendants.

The SPIHT (Set Partitioning in Hierarchical Trees) algorithm also realizes wavelet image compression by constructing a zero tree, and uses the theory of progressive transmission for encoding. The progressive transmission theory is to arrange the absolute values of the values from large to small, and then transmit the most important values first, and the restored image quality will gradually become better during restoration. The output of SPIHT is a series of bit streams, and SPIHT can stop transmission at any point without affecting the correctness of decoding. The criterion of coefficient importance used by SPIHT is similar to that of EZW. It has a threshold T _l , which represents the maximum value of matrix elements, but it adopts bit coding, first encodes high-order bits of important elements, and its coding parameter n _l =[log ₂ T _l .

SPIHT generates and decomposes sets of coefficients using a structure called a spatially oriented tree, which exploits the spatial relationship of the wavelet coefficients at different levels of the image pyramid: experience shows that the subbands at each level of the pyramid exhibit spatial similarity, and any particular , such as straight edges or uniform areas, are visible at the same location on all layers. the

The data structure (i.e., spatial orientation tree) used by SPIHT is shown in Fig. 9. In the figure, LL1 and HL2 marks respectively represent the LL subband of the first layer and the HL subband of the second layer, and the other marks can be deduced by analogy. In addition to the second layer (high pass) and the first layer (low pass) in the figure, each layer is divided into four subbands (LL, LH, HL, HH), and the subband LL1 is divided into four coefficient groups. The shaded area is the group located in the upper left corner. Each of the 4 coefficients in each group (except the square area in the upper left corner where the black solid circle is located) becomes the root of the spatial orientation tree. The arrows show how the different layers of these numbers are related together, and the arrows point to the children of the subband. The positions of the children of the coefficients at position (i, j) in the image are (2i, 2j), (2i+1, 2j), (2i, 2j+1), (2i+1, 2j+1). Since the data near the upper left corner represents significant low-frequency volume, it should be encoded first. the

Contents of the invention

The purpose of the present invention is to study a method for effective encoding and storage in view of the difficulties brought about by the extremely high redundancy of the image orientation pyramid data structure to transmission and storage. the

The implementation steps of the encoding method of the image direction pyramid of the present invention are as follows:

The first step is to decompose the image into the form of a direction pyramid with any given number of directions and scales, and the image pyramid is stored in layers according to the number of directions and the number of scales;

In the second step, a direction basis function of the direction pyramid decomposed in the first step can be arbitrarily given, and in the third step, the subband corresponding to the direction will be preferentially encoded;

In the third step, the SPIHT algorithm is used to encode the low-frequency and band-frequency components of the image-oriented pyramid, but different thresholds are used for the low-frequency and band-frequency quantities. the

The beneficial effects of the present invention are:

1. By changing the traditional data structure of the traditional SPIHT algorithm, it is possible to encode the direction pyramid of the algorithm. the

2. For the highly redundant data structure of the directional pyramid, SPIHT is optimized, which greatly improves the coding of the directional derivative and the overall reconstruction effect. the

3. A priority encoding direction can be selected to reduce the number of bits expressing redundant information, thereby achieving a better data compression effect. the

Description of drawings

Figure 1 is a histogram of natural images and their local changes;

Figure 2 is an ideal division of frequency bands;

Figure 3 is the structure of the image pyramid;

Fig. 4 is a first-level two-dimensional wavelet decomposition flow chart;

Fig. 5 is a multilevel wavelet decomposition spectrogram;

Fig. 6 is a block diagram of the direction pyramid system with K directions;

Figure 7 is a 3-layer, 4-direction ideal directional decomposition spectrum diagram;

Figure 8 is an example of pyramid decomposition and reconstruction of an image; the original image is (e), and the direction pyramid representation (a)-(d) of the image is obtained through calculation, and the image (f) is reconstructed through (a)-(d) . the

Figure 9 is a schematic diagram of the SPIHT data structure;

Fig. 10 is a schematic diagram of the data structure of the codable image direction pyramid of the present invention;

Fig. 11 is the schematic diagram of the data structure with priority encoding direction of the present invention;

Fig. 12 is the original image (a) used by the present invention to test the SPIHT algorithm, the reconstructed image (b), and the direction pyramid (c) after encoding and quantization, the first row is the band throughput of the first layer, the second row is the band-frequency component of the second layer;

Figure 13 is the original image (a) tested by the present invention, the SPIHT reconstruction effect (b), the reconstruction effect (c) using the direction pyramid SPIHT algorithm, and the reconstruction effect (d) using the priority direction pyramid SPIHT algorithm, where the left side is the reconstruction The reconstructed image, the right side is the reconstructed direction pyramid, the first row is the band flux of the first layer, and the second row is the band flux of the second layer;

Figure 14 is a comparison of the effect of reconstructing images with different algorithms;

Figure 15 is a comparison of the effects of reconstructing images using three different data structures, the overall reconstruction effect (a) and the reconstruction of directional derivatives for different layers and directions (b). the

Detailed ways

In order to make the content and advantages of the technical solution of the present invention more clear, the encoding system and method for the image orientation pyramid of the present invention will be further described in detail below in conjunction with the accompanying drawings. the

The coding system and method for image decomposition of direction pyramids of the present invention is a coding system and method for image direction pyramids based on SPIHT. Based on the defects of the data structure of the image orientation pyramid, a new data structure and a coding system for the image orientation pyramid combined with the data structure are proposed. the

From the data structure diagram of SPIHT (Figure 9), it can be seen that the tree in the shaded area (that is, the highest-level LL subband) can only be extended along the three directions corresponding to elements 2, 3, and 4, which cannot satisfy the requirements for encoding any number of elements. Number of orientation pyramid requirements. This data structure needs to be modified. the

This algorithm firstly removes the high-frequency part that contributes little to the overall image effect and feature extraction, and only codes the low-frequency and band-frequency parts. Fig. 10 is a schematic diagram of the data structure of the codable image orientation pyramid of the present invention. This data structure breaks through the data structure of traditional SPIHT coding that puts the coefficients of different layers in different areas of a square shape, and the data structure of different layers and different directions The coefficients are placed in squares of different sizes. And for convenience of representation, in Fig. 10, define " the first layer " to be the low-frequency component of image pyramid data structure (corresponding to the inside of circle L in Fig. 7); "Second layer" is the lowest band frequency component of image pyramid frequency, corresponding The inside of the ring where B1 is located in Figure 7; the "third layer" corresponds to the inside of the ring where B2 is located in Figure 7, and so on. For each layer, the coefficients in each direction are encoded one by one. The low-frequency volume is located in the first layer, which contains important information of the image and needs to be encoded first. Then encode the second layer, the third layer, and so on. The next layer corresponding to each layer is the child of this layer, and the child coefficient is stored in another square. For example, children of coefficients in the upper left part of the first layer (low frequency part) in two directions are represented by squares filled with dots in the middle of the second layer. In the children shown, the children of the coefficients in the lower right corner (that is, the grandchildren of the coefficients in the upper left part of the low frequency) are represented by squares filled with the middle line of the third layer. In practical applications, a number K of basis function direction subbands can be designed, and the directions of these basis functions are i=0, . . . , K−1, for example, if K=4, the four directions of the basis function are 0°, 45°, 90°, and 135° respectively. This data structure can encode any number of directional band-frequency components, so it can meet the needs of encoding directional pyramids.

Fig. 11 is a schematic diagram of the data structure with priority encoding direction of the present invention. This data structure changes the data structure relationship of the original band-frequency components, first selects a preferentially coded direction sub-band B (direction 1 in this example) as the second layer of the pyramid, and then uses the rest of the band-frequency components and B's A higher layer acts as the third layer, and so on. Experiments show that selecting the priority direction before encoding can save bits used to represent unimportant information. the

和

In addition, in view of the fact that the value of the directional band-frequency part of the image decomposed by the directional pyramid is much smaller than the low-frequency component, the threshold of the low-frequency decomposition is separated from the threshold of the band-frequency decomposition, using two thresholds T _l and T _h respectively, T _l and T _h represent the maximum value of the low-frequency amount and the band-frequency amount, respectively. Thus two encoding parameters are determined

and

Finally, the algorithm generates a bitstream (ie, a sequence of bits) representing the image that can be decoded and reconstructed without error if the received bitstream is interrupted at any point. the

The ordered list and set marks introduced by this algorithm are the same as the SPIHT algorithm. When encoding, first select a direction sub-band B that is preferentially coded as the second layer of the pyramid, and then use the remaining frequency components and a higher layer of B as the third layer. the

We call the image orientation pyramid encoding algorithm using the data structure in Figure 10 the orientation pyramid SPIHT algorithm, and the image orientation pyramid encoding algorithm using the data structure in Figure 11 as the priority orientation pyramid SPIHT algorithm. the

Since the directional pyramid SPIHT algorithm and the priority directional pyramid SPIHT algorithm are only different in data structure, the pseudo codes for specific implementation are the same. Their pseudo codes are as follows:

(1) Initialization

Input two initial thresholds T _l and Th _h , respectively representing the maximum value of the low frequency amount and the band frequency amount. Thereby, two encoding parameters n _l and n _h are determined;

The initial coordinate set is LIP={(r,c)|(r,c)∈H}, LIS={D _r,c |(r,c)∈H}.

(2) sort scan

1) Scan the LIP queue

Determine the importance of each entry (r, c) of the LIP queue;

If (r, c) is important

Output the sign bit of 'r' and (r, c) to Sn;

Delete (r, c) from the LIP queue and add it to the end of the LSP queue. the

If (r, c) is not important

Output '0' to Sn. the

2) Scan the LIS queue

If it is a 'D' type entry, that is, D _{r, c} , determine the importance;

If D _{r, c} is important

Output '1' to Sn;

For each (rO, cO) ∈ O _{r, r} , judge the importance

If important, output the sign bit of '1' and (rO, cO) to Sn, and add O _{r, c} to the end of LIS;

If not important, add (rO, cO) to the end of LIP. the

Determine whether L _{r, c} is an empty set

If not empty, add L _{r, c} to the end of LIS;

If it is an empty set, delete D _{r, c} from LIS.

If D _{r, c} is not important

Output '0' to Sn. the

If it is an 'L' type entry, that is, L _{r, c} , judge the importance;

If L _{r, c} is important

Output '1' to Sn and add D _{rO, cO} to the tail of LIS, remove L _{r, c} from LIS;

If L _{r, c} is not important

Output '0' to Sn. the

(3) Fine scanning

Convert the absolute values of the coefficients in LSP to binary representation and output the nth most significant bit to Rn. the

(4) Update the threshold index

Reduce the threshold index n _l to n _l -1, n _h to n _h-1 , and return to step (2) for the next level of encoding scanning.

actual effect:

Because the direction pyramid is over-complete, in order to prevent misunderstanding, we do not use the compression rate as the implementation and evaluation index, but limit the number of bits of its bit stream. We first use the standard SPIHT algorithm to encode the test image Girl (256×256) in Figure 12(a) with 10 ⁷ bits to obtain the reconstructed image (Figure 12(b)) and the corresponding orientation pyramid (Figure 12(c) ).

The encoded bit allocation is: RnList: 25930 bits; SnList: 975672 bits. The fact that the total number of bits is more than 10 ⁷ is caused by the delimiter of the bit stream. It can be seen that the restoration effect of the image is good, but it consumes too many bits.

The used test image Lena (64×64) ( FIG. 13( a )) is calculated to have T _l =816 and T _h =105. Three algorithms: SPIHT algorithm, directional pyramid SPIHT algorithm and priority directional pyramid SPIHT algorithm are tested respectively, and different algorithms are used to encode with 5×10 ⁴ bits. The reconstructed image and directional pyramid are shown in Figure 13(b) - As shown in (d), where the priority direction of Algorithm II is 0°. Since 0° is the direction of priority encoding, compared with other directions, the reconstruction effect of 0° using Algorithm II has a greater improvement than that of Algorithm I, and the overall reconstruction effect of the image has also been greatly improved.

Comparing the three algorithms with different bit overheads for Lena (64×64) (the bit overheads range from 5×10 ³ bit to 8×10 ⁴ bits), the preferred coding direction for Algorithm II is 0°. The specific PSNR curve is shown in Figure 14. It can be seen that compared with SPIHT, Algorithm I and Algorithm II have significantly improved the reconstruction effect of the direction pyramid, especially the reconstruction effect of the direction derivative. In addition, since 0° is the priority direction, Algorithm II encodes it first, so it can be found that the reconstruction effect of Algorithm II on the 0° direction is significantly higher than other data structures tested at low bit rates.

Claims (4)

1. an encoding method of an image direction pyramid, is characterized in that, comprises the following steps: A. Decompose the image into pyramids with any given number of directions and scales. For the direction subbands of the basis functions with the number K, the directions of these basis functions are respectively

i=0,...,K-1; B. The image pyramid is stored hierarchically according to the number of directions and the number of scales; C. establish the basis function direction of a priority encoding from the K basis function directions in step A; D. Using the priority direction pyramid SPIHT algorithm, using different thresholds for low-frequency and band-frequency components; E. Using the bit stream to encode, generating a bit stream to represent the low frequency and band frequency of the image. 2. method according to claim 1, in step A described direction pyramid is decomposed into some band frequency components of high frequency amount, low frequency amount and different layers; Each layer of generation direction pyramid needs following filter : High-pass filter, low-pass filter of different scales, band-pass filter of different scales and directions. 3. the method according to claim 1, described priority direction pyramid SPIHT algorithm has introduced two thresholds T _l , T _h ; Use three ordered tables to store important information: important coefficient table LSP; Unimportant coefficient table LIP; the unimportant subset table LIS; and introduce the following collection symbols: the coordinate set H of all tree roots is the low frequency of the pyramid and the layer closest to the low frequency band; the tree is the descendant of the tree root and the tree must have children; node (r, c) the set O _{r of all children, c} ; the set D r, c of all descendants of the node (r, _c ), which is called a D-type tree; the set L _{r of all non-direct descendants of the node (r, c), c} is called L-type tree; if at least one coefficient in the above-mentioned tree set is important, the tree is said to be important; the embedded bit stream of SPIHT is divided into sorted bit stream Sn and refined bit stream Rn. 4. according to the method for claim 3, the step of wherein said preferential direction pyramid SPIHT algorithm is as follows: The first step: set the threshold T _l , T _h ; let LIP be the coefficient of all tree root coordinate sets; LIS be the D-type tree; LSP be the empty set; Step 2: Detect the importance of all coefficients in LIP; if important, output 1 and sign bit, and move the coefficients into LSP; if not important, output 0; Step 3: Check the importance of all trees in the LIS according to the type of the tree, as follows: For a class D tree: output 1 if it matters, and encode its children; If the child is important, output 1, and then output a bit to represent the sign of the coefficient, and add this child to the LSP; If the child is not important, output 0, add it to the end of LIP; If the child has descendants, change the D-type tree to an L-type tree and move it to the end of the LIS, otherwise delete it from the LIS; If not important, output 0; For L-like trees: If it is important, output 1, and add each child's D-type tree to the end of the LIS, and remove the original L-type tree from the LIS; If not important, output 0; Step 4: Change the thresholds T _l and T _h to determine whether the shutdown condition is met, and if not, move to the second step.

Images