RU2321184C2 - Method for increasing encoding speed when vector quantizing and fractal encoding of images are used in conjunction - Google Patents

Abstract

FIELD: digital processing of images, possible use for transmitting images through low speed communication channels.

SUBSTANCE: in accordance to the invention, the image is divided onto rank blocks, for each rank block of original image a domain or a block is found in the code book and a corresponding transformation, which best covers the given rank block, if no sufficiently precise match is found, then rank blocks are divided onto blocks of smaller size, continuing the process, until acceptable match is achieved, or the size of rank blocks reaches certain predetermined limit, while after the division of the image onto rank blocks, classification of the blocks is performed, in accordance to which each domain is related to one of three classes, also except classification of domain blocks of original image, code book blocks classification is also performed, and further domain-rank matching is only performed for those domains, which belong to similarity class of given rank area. As a result, during the encoding, the search for area, which is similar to a rank block, is performed not only among the domains which are blocks of the image being encoded, but also among the code book blocks which match the rank area class.

EFFECT: increased speed of encoding with preserved speed of transmission and frame format length.

3 dwg

Description

The invention relates to the field of digital image processing and can be used when transmitting images on low-speed communication channels. The technical result of the invention is the development of a method that increases the coding rate when sharing vector quantization and fractal coding of images.

The closest in technical essence to the claimed method of increasing speed when sharing vector quantization and fractal coding of images is US patent No. 4941193, 1990 [1]. The authors of the patent M. Barnsley and A. Sloan first saw the possibility of applying the theory of systems of iterable functions to the problem of image compression.

Compression of images in the specified prototype is as follows [2]. For each ranking block of the source image, find the domain and the corresponding transformation that best covers the ranking block. This is usually an affine transformation. The affine transformation consists of three stages. First, one of eight basic rotations / reflections (four rotations of 90 degrees and mirror reflection in each orientation) is applied to the selected domain. Secondly, the rotated domain region is compressed to fit the size of the ranking region. And finally, the least squares method calculates the contrast parameters α and brightness β corresponding to the optimal values at which expression (1) is minimized:

where: E (R, D) is the metric between the rank block R and the domain block D reduced to it in size;

n is the number of rows in the processed rank block;

m is the number of columns in the processed rank block.

If the exact match did not work out, then the rank blocks are divided into smaller ones. Continue this process until they reach an acceptable match, or the size of the rank blocks reaches a certain predetermined limit.

The disadvantages of the prototype is that when encoding ranking areas with a large dynamic range, it is difficult to choose a domain with an even larger dynamic range, which leads to a decrease in the quality of image recovery. In addition, fractal coding requires a large amount of computation, because, firstly, for each rank block, it is necessary to search among a large number of domains and, secondly, in connection with the calculations that are required for each comparison of a domain with a rank block.

The aim of the present invention is to develop a method for increasing the coding rate with the combined use of vector quantization and fractal coding of images, providing an increase in the coding rate compared to the fractal compression method for any type of image while maintaining the transmission speed and frame length.

One way to increase speed when sharing vector quantization and fractal coding of images is to classify the domains and blocks that make up the codebook. A large coding time is the result of having to make a large number of comparisons of rank areas with domains and blocks from the codebook. The total encoding time is the product of the number of comparisons and the time required to complete each match. Each mapping is a computationally-intensive pixel processing involving rotation, compression, and fitting of a domain block or block from a codebook to a rank block.

In this invention, the classification proposed by Fisher in [3] is used, according to which each domain belongs to one of three classes. Further domain-rank comparisons are performed only for those domains that belong to the similarity class of a given rank domain.

Grade 1 A ₁ ≥A ₂ ≥A ₃ ≥A ₄

Grade 2 A ₁ ≥A ₂ ≥A ₄ ≥A ₃

Grade 3 A ₁ ≥A ₄ ≥A ₂ ≥A ₃

where A ₁ , A ₂ , A ₃ , A ₄ - the sum of the pixel values of the classified domain block in the upper left, upper right, lower left and lower right quadrants, respectively.

The specified classification can be used when sharing vector quantization and fractal coding of images. In this case, in addition to the domain blocks of the source image, the blocks from the codebook are also classified. As a result, when encoding, the search for a region similar to a rank block is carried out not only among the domains - blocks of the encoded image, but also among the blocks from the codebook corresponding to the class of the rank region.

The claimed method is illustrated by drawings:

- Figure 1 - image encoding algorithm when sharing vector quantization and fractal coding of images, taking into account the classification of domains and blocks from the codebook;

- Fig.2 is a diagram of the division into classes of domains and blocks from the codebook;

- Figure 3 - the ratio of the encoding time and the peak signal to noise ratio (PSNR) when encoding an image using a combination of fractal coding and vector quantization without classification and with classification.

The image coding algorithm when using vector quantization and fractal coding of images, taking into account the classification of domains and blocks from the codebook, is shown in FIG. 1. The original image is divided into non-overlapping rank and domain blocks, which are classified. After that, for each ranking block, a domain is found that belongs to the similarity class of a given ranking domain, and the corresponding transformation that best covers the ranking block. This is usually an affine transformation. The domains may be the domain regions of the source image or codebook blocks also corresponding to the class of the encoded rank domain. Encoding is completed when each rank block is covered by a domain region with a given error.

Figure 2 presents the scheme of classifying domains and blocks from the codebook. Each domain or block from the codebook is divided into four quadrants and the sum of the pixel values is calculated in each quadrant.

where: k is the number of rows (columns) in the quadrant;

r _j is the value of the jth pixel of the quadrant.

The brightness levels of each quadrant show the corresponding partition classes.

Figure 3 presents the ratio of the encoding time and the peak signal to noise ratio (PSNR) when encoding an image using a combination of fractal coding and vector quantization without classification and with classification. Studies performed when encoding a test image "Lena" on a computer with an AMD Athlon 1900 processor showed that the image encoding time when using the classification of domain blocks and blocks from the codebook is reduced by 2 times (from 8 minutes to 4 minutes) with a decrease quality of the reconstructed image at 0.2 dB, which is negligible.

The proposed method can be implemented on modern digital signal processing processors and can find its application in the transmission of images over low-speed communication channels

BIBLIOGRAPHIC LIST

1. Barnsley M., Sloan A., Methods and apparatus for image compression by iterated function system. U.S. Patent No. 4,941,193, 1990.

2. S. Welstead, Fractals and wavelets for compressing images in action. Textbook - M .: Triumph Publishing House, 2003.

3. Y. Fisher, Fractal image compression with quadtrees. Fractal Image Compression - Theory and Application, Springer-Verlag, New York, 1994.

Claims (1)

A way to increase the coding rate when using vector quantization and fractal coding of images together, namely, that the image is divided into ranking blocks, for each ranking block of the source image, find the domain or block from the codebook and the corresponding transformation that best covers this ranking block, if a sufficiently accurate match did not work out, then they break down the rank blocks into smaller ones, continuing this process until they reach an acceptable co the correspondence or size of the rank blocks does not reach a certain predetermined limit, and after dividing the image into rank blocks, they are classified, after which a domain or block from the codebook is found for each rank block of the source image from image blocks from the class corresponding to the class of the encoded rank block and the transformation that best covers the given rank block, if a fairly accurate match does not work out, then break the rank blocks into smaller ones, continue This process until an acceptable match is reached or the size of the rank blocks reaches a certain predetermined limit.

Images