Method of encoding digital images using discrete wavelet transformation of adaptively defined basis

FIELD: information technology.

SUBSTANCE: adaptive definition of the wavelet-basis for discrete wavelet transformation is possible through selection from a library or calculation. The wavelet-basis can be defined using: characteristics obtained using statistical, correlation and spectral analysis methods for blocks and sub-bands of blocks of the initial image; image block reconstruction error.

EFFECT: fewer transmitted or stored data through adaptive definition of the basis function for discrete wavelet transformation for initial image blocks.

12 cl, 5 dwg

 

The present invention relates to the field of image compression. The invention can be used in systems for the transmission and storage of video and images. More specifically, discusses the encoding of images using subpoenae image conversion with subsequent entropy coding. Subpoenae transformation is considered in detail in [Theory and practice of the wavelet transform. Vorob'ev V.I., Gribunin VG MAS, 1999].

Many of the common video systems use different ways of encoding that are necessary to reduce the time of data transmission via communication channels and reducing media for recording data.

With the advent of high-resolution video systems the need for a digital image coding has increased. Were achieved such compression ratios, in which it became possible to build systems of high definition TV, including wireless.

Many of the standard algorithms of image compression (e.g. JPEG) and video (e.g. MPEG-1, 2, 4, n and H.264) use the discrete cosine transform (DCT). This is due to the fact that DCT, which can be implemented based on the algorithm of the fast Fourier transform (FFT), fairly well approximates the transformation of karunen-Loev, which gives p is low Gaussian decorrelation of the signal and there is no quick calculation. Simultaneously, even for fast calculation algorithms for DCT observed exponential dependence of the amount of calculations of the size of the processed images, including, leads to the need to process the image not as a whole, and block by block: the image is divided into blocks, which are transformed using the DCT. Typically, the blocks have dimensions 8×8, 16×16, 32×32, 64×64 of pixels. In particular, in the well-known JPEG algorithm uses blocks of size 8×8. This approach leads to a substantial disadvantage is the occurrence of blocking artifact, that is, to the presence of visible boundaries between blocks of pixels in the decoded images, which significantly impairs their subjective perception. Learn more about using DCT for image compression can be found in the ISO/IEC 10918-1: 1993.

Another scheme is based on subpoena image conversion with subsequent elimination of the interstrip redundancy using tree structures. Fundamental work, which describes this scheme can be considered [A.Said, W.Pearlman. Image Compression Using the Spatial-Orientation Tree. IEEE Int. Symp. On Circuits and Systems, Vol.1, pp.279-282, May 1993].

Using subpoenae transformation, the image is converted into a set of subpoles, each of which is a matrix of transform coefficients. As the sub is olosega convert the most widely used method of wavelet decomposition scheme Malla. In this case, the implementation of the wavelet transform in the form of a quadrature mirror filter with a kernel that depends on the wavelet basis. A detailed description of this scheme can be found in the work "A theory for multiresolution signal decomposition: the wavelet representation", IEEE Transaction on Pattern Analysis and Machine Intelligence, vol.11, p.674-693, July 1989.

After corpolongo conversion, use joint coding subpoles. The purpose of this encoding is to obtain the sequence of bits (bit stream), suitable for recovery of subpoles. Feature of joint encoding subpoles is the possibility of using the initial part of arbitrary size from the received stream. The larger size is used to recover part of the bitstream, the smaller the variance of the transform coefficients recovered subpoles with encoded. This property bit stream is achieved through a certain sequence encoding the transform coefficients of the encoding matrix. The transform coefficients with large absolute value start to be encoded before the conversion factor with a smaller value. Elimination of interstrip redundancy is achieved by combining transform coefficients of different subpoles and encode them using a hierarchical tree. Such methods on isany in U.S. patent No. 5764807, 5216423, 5321776, and J. Shapiro, "Embedded image coding using zero tree of wavelet coefficients", IEEE Trans. On Signal Processing, vol.41, pp.3445-3462, Dec. 1993.

The purpose of the present invention is reducing the amount of transmitted or stored data compared with the original data.

Compression and decompression of the B image are presented in figure 1. The input image 1 is subjected to the conversion of color spaces in stage 2, the result of which is the matrix of pixels corresponding to the color space of the image (for example, matrix brightness, contrast matrix and the matrix of color). Each of these matrices is transmitted to the phase 3 sample image, which is its segmentation and formed blocks of the original image (hereinafter - bija). Then stage 4 adaptive coding using statistical methods, correlation and spectral analysis: adaptive determination of wavelet bases for the bija, is the discrete wavelet transform (hereinafter referred to as the DVP), and perform other actions on the coding bija. The method of determining the wavelet basis can be one for all the bija, and to vary from block to block. In addition, when calculating the coefficients of fiberboard subpoles bija, for each of these subpoles can be used your a wavelet basis. Final this is Ohm 5 is the formation of a bitstream image. The received bit sequence for each of the bija complemented service information (for example, information about the block size, the dimensions of the image used wavelet bases, etc) and are combined in a bit-stream image. The end of step 5 means the end of compression And the input image 1 and the resulting bit sequence in step 6 can be recorded storage device or transmitted over the communication channel.

If necessary, restore the image, recorded or transmitted bit sequence is subjected to decompression B. At step 7, the decompression B is the analysis of the bitstream image, extracting service information and selection of sequences of bits corresponding to the coded coefficients fiberboard bija. Received service information, and the bit sequence allow decoding at step 8 and return fiberboard for the respective basic funcity in step 9 to get the blocks of the reconstructed image. Obtained in step 9, the blocks of the reconstructed image in accordance with service information on the stage 10 are combined into a matrix of color spaces of the reconstructed image. After all the image matrix is restored, comes the stage of converting the color protrans is 11, representing the restored image in the form of a matrix of the desired color space. The result of decompression B is restored image 12.

Figure 2 illustrates the stages of the adaptive coding variant adaptation through characteristics bija. Figure 2 bija 1 is used to calculate the wavelet basis in step 2. The calculation of the wavelet basis can be implemented as shown in [R.R.Coifman and M.V.Wickerhauser. Entropy-based algorithms for best basis selection. IEEE Trans. Information Theory, 38: 1241-1243, March 1992]. Phase 3 is the choice of wavelet basis from a library. Phase 4 is the definition of the wavelet basis by calculating the characteristics of the bija using the results of steps 2 and 3. To obtain the characteristics of the bija can be used to assess the extent of correlation with the pixels bija, for example, the mutual correlation function between the wavelet basis and a subset of pixels in one row or in one column block. Given a block of the original image X of size (M×N) pixels. It is possible to select subsets of pixels Xibelonging to the block X. Then for a given set of bases W it is possible to find many evaluations of Fi(Xi, W), which can be used the sum of the values or the maximum values

- mutual correlation function between the one-dimensional wavelet basis and one-dimensional the subsets of X iblock X (in particular, such a one-dimensional subsets are rows and columns of block X);

- two-dimensional cross correlation function between two-dimensional wavelet basis W and two-dimensional subsets of Xiblock X (in particular, such a two-dimensional subsets are blocks of pixels of size (mi×ni)belonging to the block X, i.e. mi≤M, ni≤N).

To obtain the characteristics of the bija H(W) the following relationship:

The wavelet basis W, is the maximum characteristic value H(W), is used when performing the next iteration stage fiberboard 5. As the source data for the first iteration of the fiberboard used bija, and for each of the subsequent iterations are coefficients fiberboard obtained at the previous iteration. For each iteration can be determined by its wavelet basis by repeating steps 2 and 4. The source data for these stages are the same as for the current iteration fiberboard. After calculation of all factors fiberboard, they are coding in step 6, the result of which is a sequence of bit 7.

There is another way adaptive coding based on the calculation of the characteristics of subpoles bija. In this case, the stages of adaptation are presented in figure 3. The input is the bija 1. At stages 2 and 3 generates the I set of wavelet bases, for each element which iterates fiberboard in step 4. Initial data for calculation of the wavelet basis in step 2 is equal to the source data of the current iteration fiberboard. As a result of executing each iteration of step 4 for a set of wavelet bases is a set of subpoles coefficients fiberboard, the definition of the wavelet basis in step 5 by using the characteristics of subpoles bija, calculated by the formula:

where S is the set of subpoles bija selected for the evaluation of F; f is a non-decreasing function.

Evaluation of F is calculated as a non-decreasing function of the sum of absolute values of coefficients fiberboard, built in some degree and belonging to one of subpoles set S. In step 6 selects subpoles coefficients fiberboard, and selects subpolicy, which were obtained using the wavelet basis W is the minimum characteristic value H(W). The coefficients fiberboard belonging to the selected at step 6 subprasom, subject to encoding 7, the result of which is the 8 bit sequence.

The set S can also be obtained after the stage of quantization, which is part of the encoding step. In this case, is an adaptive encoding according to a characteristic of the quantization errors of the coefficients fiberboard. Stages DL is this the case considered in figure 4. Bija 1 and stages 2, 3, 4 are repeated in accordance with the bija 1 and stages 2, 3, 4 figure 3. When encoding coefficients fiberboard in step 5, the quantized values of the coefficients fiberboard is transferred to step 6, which is the definition of the wavelet bases by calculating the characteristics of the quantization errors in the formula (2). In this case, F is calculated as a non-decreasing function of the sum of absolute values of the quantization errors of the coefficients fiberboard, built in some degree and belonging to one of subpoles set. At step 7, there is a choice of subpoles coefficients fiberboard, and selects subpolicy, which were obtained using the wavelet basis W is the minimum characteristic value H(W). The remaining phase 5 steps for coding coefficients fiberboard are not performed for the entire set of subpoles coefficients fiberboard, and only for those subpoles that were selected in step 7. The result of step 5 is the sequence of bits is 8.

Another option adaptation based on the evaluation of error recovery of image blocks. Adaptive coding for this option are presented in figure 5. Bija 1 and stages 2, 3, 4 are exactly the same steps of the previous method. Phase 5 is the encoding of all subpoles coefficients fiberboard for each wavelet basis of a given set. The resulting successor to the spine of the bits are aligned along the length by discarding a certain number of bits from their end. In step 6, the bit sequence is restored to power with the use of wavelet bases, which were used for fiberboard before encoding. The restored blocks and bija 1 are involved in the calculation of the error recovery of image blocks. The definition of the wavelet bases on the step 7 is carried out according to the formula:

where- the restored pixel block image, and for encoding the bit sequence and decoding the applied wavelet basis W; xi,j- pixel bija; f is a non-decreasing function.

On stage 8 is selected in such a bit sequence, which is the minimum absolute value of H(W)obtained in step 7. The result of step 8 is the bit sequence 9.

1. A method of encoding a digitized image, containing the following steps: discretization of the image; adaptive coding; forming a bit stream, and wherein the original image is divided into blocks, and these blocks is performed discrete wavelet transform using the wavelet bases, which were defined adaptive phase adaptive encoding.

2. The method according to claim 1, characterized in that the definition of the wavelet basis is based on the characteristic values obtained for the block ishodnoj the image statistical methods, correlation and spectral analysis.

3. The method according to claim 2, characterized in that for the discrete wavelet transform is chosen such wavelet basis, for which the assessment of the degree of correlation with the pixel values of the block of the original image maximum.

4. The method according to claim 3, characterized in that for determining the degree of correlation between the wavelet basis and the values of the pixels of the block of the original image is mutual correlation function.

5. The method according to claim 3, characterized in that for the determination of the degree of correlation between the wavelet basis and the values of the pixels of the block of the original image are used subset of pixels in one row or in one column belonging to the block.

6. The method according to claim 1, characterized in that the definition of the wavelet basis is made after the discrete wavelet transform on the blocks of the original image based on the characteristic values obtained for subpoles these units statistical methods, correlation and spectral analysis.

7. The method according to claim 6, characterized in that the quality characteristics to determine a wavelet basis for performing discrete wavelet transform on the block of the source image is a non-decreasing function of the sum of absolute values of coefficients of discrete wavelet pre is obrazovaniya, elevated to some degree and belong to a pre-selected subprasom block.

8. The method according to claim 7, characterized in that for the discrete wavelet transform is chosen wavelet basis, which provides the minimum value of a non-decreasing function of the sum of absolute values of coefficients of discrete wavelet transform, erected in some degree and belong to a pre-selected subprasom block of the source image.

9. The method according to claim 7 or 8, characterized in that for the calculation of non-decreasing function of the sum of absolute values of coefficients of discrete wavelet transform, erected in some degree determines the coefficients of the discrete wavelet transform, belong not to all subprasom blocks, but only part of them.

10. The method according to claim 1, characterized in that for the discrete wavelet transform on the block of the original image is selected such wavelet basis, for which the function value of the error recovery block image will be minimal.

11. The method according to claim 10, characterized in that the function of the error recovery is defined as a non-decreasing function of the sum of absolute values of the quantization errors of the conversion factors built in some degree and owned subprasom block of the original image subjected kVA is tovani.

12. The method according to claim 10, characterized in that the function of the error recovery block image is determined as a non-decreasing function of the sum of absolute values, erected in some degree, and calculated as the deviation of the pixels of the restored block image from pixels of the original block image.



 

Same patents:

FIELD: information technology.

SUBSTANCE: method of highlighting an object in an electronic document such that, the highlighted object retains colour and formatting properties to allow for maintenance of visual fidelity relative the pre-highlighted view of the highlighted object and which allows for a semi-transparent background underneath a highlighted object which allows a user to see and appreciate the colouring and any visual properties applied to the background underneath the highlighting applied to the selected object.

EFFECT: high efficiency of searching for objects in electronic documents.

20 cl, 6 dwg

FIELD: information technology.

SUBSTANCE: position of pulse noise on the image is evaluated first, after which four auxiliary masks are formed, as well as eight control vectors (two vectors based on each auxiliary mask), and coefficients of corresponding four differently aligned Prewitt masks are then changed using given vectors. Further, the given masks are used to calculated the approximate value of the modulus of the image gradient, and contours of the object on the image are obtained through its threshold conversion.

EFFECT: higher sensitivity of the noise-immune gradient method of detecting contours to useful contour features of the image.

5 dwg

FIELD: information technology.

SUBSTANCE: snap-shot of a graphic image is reduced by resising by 4 times. The snap-shot is compressed and stored as a compressed file, which can be decompressed and increased by 4 times. The initial snap-shot of the graphic image is then superimposed onto a decompressed increased snap-shot. Differences of pixel values between the initial snap-shot of the graphical image and the decompressed increased snap-shot are searched for, from a given contrast, based on contrast elements using arithmetical subtraction. After that a snap-shot with contour values is obtained, and contrast elements are compressed and stored as a compressed file.

EFFECT: increased efficiency of compressing files and reducing amount of memory required with retention of definition of the graphical image after decompression of files.

8 dwg

FIELD: physics, computation equipment.

SUBSTANCE: the invention claims method of image blur compensation involving: calculation of difference between measured image pixel brightness and brightness assessment obtained earlier on the basis of previous frame sequence; movement detection by comparison of obtained difference to threshold value; defining of movement direction for each pixel; combination of adjoining pixels with the same movement direction in a single object; outlining contours of moving objects by adding their initial B(k) and gradient ▿(B(k)) of images; and generation of output image where k1, k2 are weight factors. Device of image blur compensation includes: image sensor, controller, mode movement detection module, object detection module, correction module, first RAM device, second RAM device, third RAM device, counter, first comparator, second comparator, first multiplexor, second multiplexor, third multiplexor, fourth multiplexor, fifth multiplexor, sixth multiplexor, seventh multiplexor, first demultiplexor, second demultiplexor.

EFFECT: blur compensation for moving object image in real-time mode.

2 cl, 11 dwg

FIELD: physics, computation equipment.

SUBSTANCE: the invention claims method of image blur compensation involving: calculation of difference between measured image pixel brightness and brightness assessment obtained earlier on the basis of previous frame sequence; movement detection by comparison of obtained difference to threshold value; defining of movement direction for each pixel; combination of adjoining pixels with the same movement direction in a single object; outlining contours of moving objects by adding their initial B(k) and gradient ▿(B(k)) of images; and generation of output image where k1, k2 are weight factors. Device of image blur compensation includes: image sensor, controller, mode movement detection module, object detection module, correction module, first RAM device, second RAM device, third RAM device, counter, first comparator, second comparator, first multiplexor, second multiplexor, third multiplexor, fourth multiplexor, fifth multiplexor, sixth multiplexor, seventh multiplexor, first demultiplexor, second demultiplexor.

EFFECT: blur compensation for moving object image in real-time mode.

2 cl, 11 dwg

FIELD: information technology.

SUBSTANCE: snap-shot of a graphic image is reduced by resising by 4 times. The snap-shot is compressed and stored as a compressed file, which can be decompressed and increased by 4 times. The initial snap-shot of the graphic image is then superimposed onto a decompressed increased snap-shot. Differences of pixel values between the initial snap-shot of the graphical image and the decompressed increased snap-shot are searched for, from a given contrast, based on contrast elements using arithmetical subtraction. After that a snap-shot with contour values is obtained, and contrast elements are compressed and stored as a compressed file.

EFFECT: increased efficiency of compressing files and reducing amount of memory required with retention of definition of the graphical image after decompression of files.

8 dwg

FIELD: information technology.

SUBSTANCE: position of pulse noise on the image is evaluated first, after which four auxiliary masks are formed, as well as eight control vectors (two vectors based on each auxiliary mask), and coefficients of corresponding four differently aligned Prewitt masks are then changed using given vectors. Further, the given masks are used to calculated the approximate value of the modulus of the image gradient, and contours of the object on the image are obtained through its threshold conversion.

EFFECT: higher sensitivity of the noise-immune gradient method of detecting contours to useful contour features of the image.

5 dwg

FIELD: information technology.

SUBSTANCE: method of highlighting an object in an electronic document such that, the highlighted object retains colour and formatting properties to allow for maintenance of visual fidelity relative the pre-highlighted view of the highlighted object and which allows for a semi-transparent background underneath a highlighted object which allows a user to see and appreciate the colouring and any visual properties applied to the background underneath the highlighting applied to the selected object.

EFFECT: high efficiency of searching for objects in electronic documents.

20 cl, 6 dwg

FIELD: information technology.

SUBSTANCE: adaptive definition of the wavelet-basis for discrete wavelet transformation is possible through selection from a library or calculation. The wavelet-basis can be defined using: characteristics obtained using statistical, correlation and spectral analysis methods for blocks and sub-bands of blocks of the initial image; image block reconstruction error.

EFFECT: fewer transmitted or stored data through adaptive definition of the basis function for discrete wavelet transformation for initial image blocks.

12 cl, 5 dwg

FIELD: information technologies.

SUBSTANCE: in the method for identification of contours of a moving object, in a video sequence of low resolution, information is used from auxiliary photographs of the specified object, taken with high resolution, mutual identification of contours is carried out from a photograph and a video sequence at appropriate moments of time in the same sequence with correlation and modelling of high-resolution frames.

EFFECT: increased resolution and dynamic range of a video sequence.

5 cl, 1 dwg

FIELD: information technology.

SUBSTANCE: method of compressing graphics files involves predetermining the number of gradations of reducing geometric dimensions of a source frame of a graphic image. For each gradation, geometric dimensions of the source frame of the graphic image are reduced, compressed and stored in a compressed file, and then latter decompressed and enlarged to the initial size. Pixel values of the enlarged decompressed frame are then subtracted from pixel values of the source frame of the graphic image and the result with values of the contrast element loop is compressed in form of a file. All values of the reduced compressed files and corresponding values of the compressed contrast element loop are then summed. The least of the obtained sums is selected as the result.

EFFECT: high rate of data transmission.

6 cl, 5 dwg

FIELD: information technology.

SUBSTANCE: image decoding device comprises decoding aid of variable length and a loop filter. Decoding process of variable length is carried out with respect to the parameter for generating prediction signals and compressed differential image with respect to information associated with a plurality of blocks constituting the decoded image and indicating whether the filtering process must be carried out with respect to each of the blocks. The loop filter performs a filtering process with respect to the decoded image obtained by summarizing the prediction image and the differential image, determines a class for each pixel of the decoded image and performs the filtering process using the filter corresponding to the determined class. The filtering process is not performed for a block when the information indicates that the filtering process must not be performed for the block.

EFFECT: improved image quality.

2 cl, 18 dwg

Up!