RU2313917C2 - Method for transmitting additional information during combined usage of vector quantization and fractal encoding of images - Google Patents

Abstract

FIELD: electric communications, namely, area connected to reduction of excessiveness of information being transmitted.

SUBSTANCE: in accordance to the invention, during encoding of image by means of combined usage of vector quantization and fractal compression method, additional information is integrated into lower bits of domain indexes or code book blocks. Testing inversion procedure is applied to remaining bits of domain indexes of original image or code book blocks. After integration of additional information and optimization of domain indexes and code book blocks, these data together with information about indexes of their orientation, brightness and contrast coefficients are transferred through a communication channel. At receiving side, additional information is extracted and original image is restored.

EFFECT: transmission of image with additional information (concealed information, another image or other useful message) without increasing the volume of transferred data.

3 dwg, 1 tbl

Description

The invention relates to the field of telecommunications, and in particular to the field associated with reducing the redundancy of transmitted information. The basis for this is essentially the fact that with the help of modern technologies for encoding and data compression, it is possible to significantly reduce the frequency range required for image transmission. The technical result of the invention is the development of a method for transmitting additional information when sharing vector quantization and fractal coding of images, providing the transfer of additional information without increasing the amount of transmitted data.

In digital video technology, in order to increase the transmitted amount of information, it has already been proposed to replace the scanning data contained in the interval of blanking additional information in a digital signal, for example, with digital audio signals, and thereby ensure the transmission of additional information (Ulrich Schmidt, Digital Video Equipment, Franzis Verlag Publishing House, Feldkirchen, 1996) [1].

The closest in technical essence to the claimed method of transmitting additional information when encoding images is the method described in patent No. 2212769, IPC ⁷ H04N 7/08 [2]. The prototype method eliminates the unnecessary part of the image information, i.e. the physiologically subtle or hardly perceived fine structure of the image, due to irreversible compaction and subsequent decompression of the image signal, i.e. performs data reduction and inserts useful and control information into the free space thus obtained.

However, the total frequency band occupied by the transmission of the main image and additional information remains the same, as before the irreversible compression of the original image.

The aim of the present invention is to develop a method that allows encoding any type of image to transmit additional useful information while maintaining the transmission speed and length of the frame format. This goal is achieved by the fact that when compressing the original image using the combined vector quantization and fractal coding, additional information is introduced into the lower digits of the domain indices or blocks from the codebook, thereby reducing the list of domains and blocks from the codebook, which leads to a significant reduction the total encoding time with a slight deterioration in the quality of the reconstructed image. The test inversion procedure is applied to the remaining bits.

Consider the algorithm for transmitting additional information when sharing vector quantization and fractal coding of images (figure 1).

Previously, the original image is divided into non-overlapping rank blocks, and then covered with a sequence of domain blocks, possibly overlapping. Domains can be of different sizes. Also in the encoder and decoder identical codebooks are preformed. After that, additional information is embedded in the lower digits of the domain indices or blocks from the codebook.

Further, the basic algorithm of fractal coding of images is applied to the original image [3]. The main computational step in fractal coding is the comparison of the domain and rank domains. For each rank block, find the domain and the corresponding transformation that best covers the rank block. This is usually an affine transformation.

where α _i is a constant that extends or narrows the range of values of the function f (controls the contrast of the image);

β _i is a constant that increases or decreases the values of grayscale (controls the brightness of the image);

w _i is the affine transformation;

- пространственная составляющая преобразования w_i;

is the spatial component of the transformation w _i ;

f (x, y) - image pixel value with coordinates (x, y).

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 and brightness parameters corresponding to the optimal values at which the expression is minimized

where n and m are the number of rows and columns in the processed rank block;

R _ij and D _ij are the pixel values of the rank and domain domains.

Continue this process until they reach an acceptable match or the size of the rank blocks reaches a certain predetermined limit.

In addition, the search for the necessary domain is carried out from the previously generated codebook, taking into account the built-in additional information in the lower bits of the codebook fragments. The codebook is formed by an iterative cluster algorithm, also known as the k-means algorithm described in [4]. In accordance with this algorithm, a certain sequence of images belonging to different classes is selected. Next, this sequence is converted into a sequence of input vectors or a training sequence by which a code book is formed. In this case, the input vectors should have a large dynamic range, since the codebook should contain blocks that display sharp edges between the image fragments, since it is in such cases that problems may arise with finding a suitable domain. Such a situation usually arises due to restrictions on the dynamic range of the desired domain, which, as a rule, should be greater than the dynamic range of the rank domain. In areas with sharp boundaries, the dynamic range is very large, and it often turns out that it reaches its maximum value. In this case, there is no domain with a strictly large dynamic range, and the ranking area is replaced by the most similar block from the codebook.

If the rank block is better displayed by the domain block, the index of the corresponding domain is transmitted to the decoder, upon receipt of which the decoder carries out fractal decoding of the original block. When a fragment for a rank block is selected from the codebook, the index is transmitted to the decoder, according to which the necessary fragment is selected from the codebook in the decoder, with which, after fractal decoding, the restored image is filled.

путем пробной инверсии ее каждого элемента. Процесс поиска оптимальных элементов вектора в заявленном способе предлагается осуществить в виде следующей последовательности действий:In the proposed method, in each vector of the index of domains or a block from the codebook, consisting of n bits, m bits of additional information are introduced instead of the lower bits of this vector (Fig. 2). As a result of this introduction, the list of domains and blocks from the codebook for processing a particular rank block is noticeably reduced, which leads to a decrease in both the search time for suitable domains and fragments of the codebook, and the overall encoding time as a whole. The test inversion procedure is applied to the remaining k = nm discharges. In this procedure, in order to reduce computational complexity compared to the exhaustive search method, it is proposed to use the well-known Gauss-Seidel method. The trial inversion procedure optimizes the elements of domain indexes

by trial inversion of each element. The process of searching for optimal vector elements in the claimed method is proposed to be implemented in the form of the following sequence of actions:

1. Put t = 1;

2. Generate a domain or block index vector from the codebook, taking into account the input of additional information

3. Put r = 1;

;4. Select the appropriate orientation of the domain or block from the codebook, calculate conversion parameters, such as contrast and brightness, and determine expression (2) for the vector

;

5. Invert the rth element of the vector

where x _r ∈ {0,1},

6. Form a vector:

1. Select the appropriate orientation of the domain or block from the codebook, adjust the conversion parameters, such as contrast and brightness, to minimize expression (2) when the rth element of the vector is inverted

;8. Calculate

;

и значению x_r, присвоить

; если u<0, то значения e² и х_r оставить без изменения;9. Execute: if u> 0, then assign the value e ²

and the value x _r , assign

; if u <0, then leave the values of e ² and x _r unchanged;

10. Perform: if r <k, then increase r by one and go to step 4; if r = k, then put t = t + 1 and go to step 2 to optimize the following domain indices or blocks from the codebook.

After embedding additional information and optimizing the indexes of domains and blocks from the codebook, this data, together with information about the indexes of their orientation, brightness and contrast coefficients, are transmitted through the communication channel. In the decoder, additional information is extracted and the original image is restored. Image decoding is performed by iteratively applying the affine transform to an arbitrary initial image. In accordance with the theorem on squeezing mappings, iterations will converge regardless of the choice of the initial image. A compression mapping is defined as a separate transformation for each rank block. Each rank block has a transformation and domain associated with it. The contents of this rank block are computed by applying the transform to the domain block. One iteration ends when all rank blocks are processed.

In the case of encoding a rank with a block from the codebook, this fragment of the codebook, taking into account its orientation index, brightness and contrast factors, fills the corresponding area of the reconstructed image.

The claimed method is illustrated by drawings:

- Figure 1 represents the image encoding algorithm when sharing vector quantization and fractal compression method, taking into account the built-in additional information;

- Figure 2 - procedure for recording additional information;

- Figure 3 - scheme for the transmission of additional information when sharing vector quantization and fractal coding of the image.

Figure 1 presents the image encoding algorithm when sharing vector quantization and fractal compression method, taking into account the built-in additional information. The original image is divided into non-overlapping rank and domain blocks. After that, additional information is embedded in the domain blocks. As you can see, after inserting additional information, the trial inversion procedure is applied to the remaining source bits, in which the well-known Gauss-Seidel method is used to solve optimization problems. After that, for each rank block, the domain and the corresponding transformation that best covers the rank block are found. This is usually an affine transformation. The domains may be domain regions of the source image or codebook blocks. Encoding is completed when each rank block is covered by a domain region with a given error.

Figure 2 shows the procedure for recording additional information. In the proposed method, in each vector of the index of domains or blocks from the codebook, consisting of n bits, instead of the lower bits, m bits of additional information are introduced. Since this data is not added in addition to the original signal, but replaces part of the original signal, the signal bandwidth does not increase by adding this information.

Figure 3 presents the scheme for transmitting additional information when sharing vector quantization and fractal coding of an image. Previously, identical codebooks are formed in the encoder and decoder. After that, additional information is embedded in the lower digits of the domain indices or blocks from the codebook. Next, fractal coding of rank blocks is carried out taking into account the built-in additional information, as well as the search for the most suitable block from the previously generated code book. If the rank block is better displayed by the domain block, the index of the corresponding domain is transmitted to the decoder, upon receipt of which the decoder carries out fractal decoding of the original block. When a fragment for a rank block is selected from the codebook, the index is transmitted to the decoder, according to which the necessary fragment is selected from the codebook in the decoder, with which, after fractal decoding, the restored image is filled.

Table 1 shows the results of simulation modeling the insertion of additional information in the test image "Lena" with a size of 256 × 256 pixels. The size of the rank block was 8 × 8 pixels, and their total number in the image would be 1024. The peak signal-to-noise ratio (PSNR) before inserting additional information was 29 dB.

Table 1 The number of bits embedded in the indexes of domains and blocks from the codebook 1 bit 2 bits 3 bits 4 bits 5 bit 6 bit 7 bit 8 bit 9 bit PSNR on the image of "Lena", [DB] 28.9 28.4 27.8 27.3 26.5 25.6 24.5 23.4 23 The maximum allowable amount of add. information, [bit] 1024 2048 3072 4096 5120 6144 7168 8192 9216

This method of transmitting additional information when sharing vector quantization and fractal coding of images can be implemented on modern signal processing processors. The specified method can find its application in the transmission of additional information on low-speed communication channels. As additional information, hidden information, another image or another useful message can be used.

Literature

1. Ulrich Schmidt, Digital Video Technology. Franzis Verlag, Feldkirchen, 1996.

2. Patent No. 2212769, IPC ⁷ H 04 N 7/08, bull. No 26 on 09/20/2003

3. Welstead S. Fractals and wavelets for image compression in action. Tutorial. - M .: Triumph Publishing House, 2003 - 320 p.

4. Satellite TV. New transmission methods. / N.G. Kharatishvili, E.I.Kumysh, V.Yu. Yepanechnikov, O.G. Zumburidze. / Ed. N.G. Kharatishvili. - M .: Radio and communications, 1993.

Claims (1)

A method for transmitting additional information when encoding images, comprising the steps of a) digitizing the original image, b) compressing it using an irreversible compression method, c) inserting digital useful information, d) decompressing the compressed image, e) extracting digital useful information the fact that after compression of the original image using the combined use of vector quantization and fractal coding, insert m bits of additional information instead of the lower bits in each the index vector sector or block from the codebook, consisting of n bits, apply the trial inversion procedure to the remaining k = n-m source bits, in which the Gauss-Seidel method is used, after which they are transmitted along the communication channel with additional information.

Images