Method of transmission of additional data in combined use of vector quantisation and fractal conding of images allowing for classifications of domains and units from code book

FIELD: electrical engineering.

SUBSTANCE: invention relates to communication, in particular, to reducing the message redundancy. The developed method allows transmitting additional data without increasing the volume of transmitted data with the transmission rate left intact. First, the initial image is separated into not overlapping range units to be classified. Here, note that every range unit is refereed to one of the three classes, and the said classification is applied to the domains and units from the code book as well. Additional data is entered into lower category of the domain or units indices, to the rest categories of indices of the domain of the initial image or units from the code book applied is the trial inversion procedure. Now, the domain indices and units from the code book are optimised to be transmitted, along with the data on indices of their orientation, over the communication channel. The receiving party isolates the additional data and restores the initial image.

EFFECT: transmission of additional data without increasing the common volume of transmitted data at the required transmission rate.

4 dwg, 1 tbl

 

The invention relates to telecommunications, and in particular to the field associated with the reduction of the redundancy of the transmitted information. The reason for this, essentially, is that with the help of modern technology coding and data compression can significantly reduce the frequency range required for image transfer. The technical result of the invention is to develop a method for the transmission of additional information when combined vector quantization and fractal image coding based classification domains and blocks of code books for the transmission of additional information without increasing the amount of transmitted data.

In digital video technology to increase the transmitted amount of information has already been proposed to replace the digital signal scan data contained in the interval blanking additional information, such as digital audio signals, and to transmit additional information (Ulrich Schmidt, Digital video equipment, Publishing Franzis Verlag, Feldkirchen, 1996) [1].

The closest in technical essence to the claimed method for the transmission of additional information in the image coding method is described in patent No. 2212769, IPC704N 7/08 [2]. The prototype method is the replacement of the AET is not required part of the information image, i.e. physiologically barely or not at all perceive the fine structure of the image, due to irreversible compaction and subsequent decompression of the image signal, i.e. data reduction, and thus obtained the free space inserts the useful and control information.

However, the total bandwidth occupied in the transmission of the main image and additional information, remains the same as before irreversible compaction of the source image.

The purpose of this invention to provide a method which allows for the coding of any type of images to convey more useful information while maintaining the transmission rate and the length of the frame format. This objective is achieved in that during compression of the original image through the joint use of a vector quantization and fractal coding with regard to the classification of domains and blocks of code books in the low-order bits of the index of the domain or blocks of code books introduce additional information that reduces the list of used domains and blocks of code book that leads to a significant decrease in the total encoding time with a slight deterioration in the quality of the reconstructed image. The remaining bits of the applied procedure test inversion.

Consider the algorithm for the transmission of additional information when combined vector quantization and fractal image coding based classification domains and blocks of code book (figure 1).

Previously the original image is divided into nonoverlapping rank blocks and classify them. The present invention uses the classification proposed by Fisher in [3], according to which each rank unit belongs to one of three classes (figure 2):

class 1And1≥A2≥And3≥A4
class 2And1≥And2≥And4≥A3
class 3And1≥And4≥And2≥A3

where a1And2And3And4the sum of the values of pixels classified domain block in the upper left, upper right, lower left and lower right quadrants, respectively.

This classification can be used when combined vector quantization and fractal image coding. In addition to the rank and domain blocks of the original image is also carried out classification of the blocks of the code book. After that, in the low-order bits of the Indus is xov domain or blocks of code books embed additional information.

Next to the original image uses the algorithm of fractal image coding [4]. The search region that is similar to the ranking unit is not only the domain blocks of the encoded image, but also among the blocks of code books corresponding to a class of rank field.

The main computational step in fractal coding is a comparison of the domain and rank areas. For each rank of the block, find the domain and the corresponding transformation that best covers the ranking unit. This is usually an affine transformation:

where αi- a constant that expands or narrows the range of values of the function f (controls the contrast of the image);

βi- a constant that increases or reduces the value of the grayscale (controls the brightness of the image);

wi- affine transform;

- spatial component of the transformation wi;

f(x, y) is the pixel value of the image with coordinates (x, y).

An affine transformation consists of three steps. First, the selected domain is one of the eight basic rotations/reflections (four 90-degree rotation and mirror reflection in each orientation). Secondly, rotating domain scope gripping the edge of your is raised, to fit the size rantovoe area. And, finally, by the method of least squares is calculated contrast and brightness corresponding to the optimal values that minimize the expression:

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

Rijand Dij- the pixel values of rank and domain fields.

The application of the classification domain, the ranking of regions and blocks codebook reduces the encoding time due to the fact that these mappings are only for those domains and blocks of code books that belong to the class of similarity of the encoded rank field.

Continue coding until then, until you get an acceptable match or the size ranking of blocks reaches a predetermined limit.

In the proposed method, each vector index of the domain or block of code book consisting of n digits, enter the m bits of the additional information instead of the least significant bits of this vector (figure 3). As a result of this introduction of a list of domains and blocks of code books to handle the specific rank of the unit is significantly reduced, resulting in less time searching for suitable domains and fragments of code books, and the total time to the investments in General. The remaining k=n-m digits of the procedure test inversion. In this procedure, with the aim of reducing computational complexity in comparison with the method of complete enumeration is proposed to use the well-known method of Gauss-Seidel. Procedure test inversion performs optimization of the elements of domain indexesby test inversion for each element. The process of finding the optimal vector elements in the claimed method are proposed to be implemented in the form of the following sequence of actions:

1. Put t=1;

2. To form the vector index of the domain or block of code book including additional information

3. Put r=1;

4. To choose the appropriate orientation of the domain or block of code books, to calculate the conversion settings, such as contrast and brightness, and to determine the expression (2) for vector;

5. To perform the inversion of the r-th element of the vectorwhere

6. To form a vector:

7. To choose the appropriate orientation of the domain or block of code books, to customize the conversion settings, such as contrast and brightness, to minimize the expression (2) in the inversion of the r-th element of the vector ;

8. Calculate:

9. Run: if u>0, then the value of e2assign the value ofand the value of xrassign; if u<0, then the values of e2and xrremain unchanged;

10. To do: 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 indexes domain or blocks of code book.

After embedding additional information and optimizing indexes, domains and blocks of code books these data, together with information about the indexes of their orientation, the coefficients of brightness and contrast are transmitted over the communication channel. The decoder is the allocation of additional information and restore the original image. The decoding of the image is performed by an iterative application of the affine transformation to an arbitrary initial image. In accordance with theorem on contractive mappings iteration will converge regardless of the choice of the initial image. Compressive mapping is defined as a separate transformation for each rank of the block. Each rank unit has associated with it transformation and domain. The contents of this rank of the block is calculated by applying a transform to the domain of the th block. One iteration is completed when you are ranking the blocks.

In the case of encoding the rank of a block of code books this snippet of code book with the index of its orientation, the ratios of brightness and contrast fills in the appropriate area of the reconstructed image.

The claimed method is illustrated by drawings.

Figure 1 - Algorithm for the transmission of additional information when combined vector quantization and fractal compression method taking into account the classification of domains and blocks of code book.

Figure 2 - the Scheme split into classes of domains and blocks of code book.

Figure 3 - write Procedure for more information.

4 is a Diagram of the transmission of additional information when combined vector quantization and fractal encoding of images.

Figure 1 presents the algorithm for the transmission of additional information when combined vector quantization and fractal compression method taking into account the classification of domains and blocks of code book. The original image is divided into nonoverlapping rank and domain blocks, which are classified. Then in the domain blocks embedded additional information. After inserting the additional information for the remaining source categories used procedure fish inversion, to the ora use a known method Gauss-Seidel for solving optimization problems. Then, for each rank of the block, find the domain that belongs to the class of similarity of the encoded rank of the block and the corresponding transformation that best covers the ranking unit. This is usually an affine transformation. As a domain can be a domain area of the original image or blocks of code book. Coding ends when coating each rank of domain block area with a given error.

Figure 2 presents the scheme of partition classes of domains and blocks of code book. Each domain or block of code book is divided into four quadrants and each quadrant is calculated the sum of the pixel values.

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

rj- value of the j-th pixel quadrant.

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

Figure 3 shows the procedure to record additional information. In the proposed method, each vector index domains or blocks of code book consisting of n bits, instead of the least significant bits is entered m bits of additional information. Because these data are not added in addition to the original signal, and replace part of the original signal, the bandwidth of the signal is not increased by adding e is th information.

Figure 4 shows a diagram of the transmission of additional information when combined vector quantization and fractal image coding. Previously in the encoder and the decoder generate identical code book including breaking them into classes. After that, in the low-order bits of the index of the domain or blocks of code books embed additional information. Following is the fractal encoding rank blocks taking into account additional embedded information, and finding the best matching block of the previously generated code book. If rank better block displays the domain block, the decoder is passed the index of the corresponding domain, the reception of which the decoder is fractal decoding the source block. When choosing for rank block fragments from the codebook to the decoder is passed to the index at which the character from the books in the decoder selects the required fragment, which after the fractal decoding is filled with restored image.

Table 1 shows the simulation results for the insertion of additional information in the test image "Lena" of size 256×256 pixels. The size rank of the block was 8×8 pixels, while their total number in the image is 1024. Peak ratio signalscan (PSNR) to insert additional information was 29 dB.

Table 1
The number of bits embedded in the index domain and blocks of code book
1 bit2 bits3 bits4 bits5-bit6-bit7-bit
PSNR

in the image "Lena", [dB]
28.027.126.225.625.124.523.5
The maximum amount of supplementary information [bit]1024204830724096512061447168

This way the transmission of additional information when combined vector quantization and fractal image coding can be implemented on modern processors signal processing. The method may find its application in the transmission of additional data over a slow communication channels. As additional information can be hidden information, another image or any other useful information.

BIBLIOGRAPHIC LIST

1. Ulrich Schmidt, Digital video equipment. Publisher Franzis Verlag, Feldkirchen, 1996.

2. Patent No. 2212769, IPC7 04N 7/08, bull. No. 26 from 20.09.2003,

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

4. With. Walsted, Fractals and wavelets for image compression in action. The tutorial. - M.: Publishing house Triumph, 2003. - 320 S.

Method for the transmission of additional information when encoding images with stage a) digitization of the original image, (b) compression via joint use of vector quantization and fractal coding of images, (C) insertion of additional information, (d) decompressing the compressed image, (e) the allocation of additional information, characterized in that the compression of the original image through the joint use of a vector quantization and fractal coding domains and blocks of code books are classified, followed by the insertion of additional information in the index domain and blocks of code book, then, for each rank of the block of the original image are domain or unit of code book including additional information from the class corresponding to the class of the encoded rank of the block, then the indexes domains or blocks of code book including additional embedded information is transferred over the communication channel.



 

Same patents:

FIELD: physics.

SUBSTANCE: said utility invention relates to a method of signal transmission in a digital television network. The ground digital television network is used for the transmission of IP datagrams to receiving devices using multiprotocol encapsulation (MPE). MPE datagram sections and, if using the forward error correction (FEC), MPE FEC datagram sections are transmitted in time-slotted packet signals. The time slotting parameters determining the minimum time between packet signal transmissions, and data output from the time slotting buffer of the receiving device at the transmission bit rate are used to save power and enhance the quality of service.

EFFECT: increased reliability of signal transmission.

9 cl, 19 dwg, 10 tbl

FIELD: information management systems.

SUBSTANCE: method for controlling import of content into a domain comprising number of devices consists in checking for the presence of a domain watermark in the content, and if the domain watermark is found in the content, refusing import of the content into the domain, and if the domain watermark is not found in the content, allowing import of the content into the domain and causing the domain watermark to be embedded into the content. Optionally, re-importing into the "original" domain might be allowed. The method further comprises refusing import of the content into the domain if the domain watermark is found in the content unless the identifier matches an identifier for the domain. Other payloads in the domain watermark can be used to e.g. implement location- or time-based restrictions on import.

EFFECT: providing a method for discerning the input of legitimate unencrypted content from illegally copied unencrypted content.

14 cl, 3 dwg

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

FIELD: broadcast program translation systems, and, in particular, systems for identification and insertion of advertisement into broadcast programs.

SUBSTANCE: in accordance to method, broadcasting data stream is received, advertisement is identified in broadcast data stream and schedule of advertisements is renewed, including information, identifying advertisement and position of advertisement in program for broadcast data stream. During reproduction, advertisement or substituting advertisement are inserted into program in aforementioned position or different position in program.

EFFECT: creation of secondary broadcasting service for increasing efficiency of advertisements.

2 cl, 10 dwg

FIELD: electric communications, namely, communications with decreased excessiveness of transferred information.

SUBSTANCE: in accordance to method, during encoding of image by means of method of fractal compression, into lower bits of domain indexes, additional information is inserted. To remaining bits of indexes of source image domain, sample inversion procedure is applied. After building in additional information and optimization of domain indexes these data together with information about domain orientation indexes, brightness and contrast are transferred via communication channel. At receiving side, additional information is separated and original image is restored.

EFFECT: transfer of additional information.

5 dwg

FIELD: method and systems for injecting command into device being controlled.

SUBSTANCE: in accordance to method, watermark is formed, containing inbuilt control command, which should be executed by device being controlled, control command being related to representation of advertisement, signal is generated, containing watermark, inbuilt in information block represented by it and transferred into device being controlled, generated signal is transferred with watermark into device being controlled for showing advertisement to user by executing control command, related to showing advertisement, user is questioned to determine his preferences and on basis of questioning user profile is generated with consideration of sales data for devices being controlled, product identification is added to control command, while control command contains value of parameter, specific for advertisement, while device being controlled receives advertisement, wherein parameter values are used.

EFFECT: creation of method and system for injecting command into device being controlled, wherein direct transfer of command into device is provided.

3 cl, 4 dwg

FIELD: engineering of communication system between transmitter and receiver, where transmitter sends digital data and data descriptors to receiver via communication channel.

SUBSTANCE: communication system provides identification of multiply used data in transmitter by means of data descriptors, inserted into data stream being transferred from transmitter to receiver, data stream, being received at receiving end, is analyzed to detect presence of data descriptors, which signify presence of multiple use data, when such a descriptor is detected, it is locally saved at receiver level jointly with data to which it is related, and multiple use data saved in such a way may be utilized not only immediately after receipt at receiving end, but also later, without need to request transmission from the transmitter.

EFFECT: decreased load on transfer channel.

4 cl, 7 dwg

FIELD: technology for applying subtitles for interactive video equipment, in particular, interactive video equipment and software method for applying subtitles, used in current video equipment.

SUBSTANCE: control level of interactive video equipment receives information from user about subtitles necessary to be generated, in the coder of interactive video equipment on transferring assembly following stages are performed: receipt of information about subtitles from control level and following generation of subtitle image on transparent background in accordance to aforementioned received information; application of aforementioned image of subtitles to digital service image before encoding, sent from transferring node, with production of digital image, mixed with image of subtitles, and encoding of aforementioned mixed digital image with its following transmission to remote node.

EFFECT: simplification of used technical means, decreased cost of system, simplified generation and application of subtitles.

2 cl, 4 dwg

The invention relates to signal transmission, in particular the United containing podzagnuli corresponding to two or more different protocols on the same wire

The invention relates to a method and apparatus for transmitting additional data associated with the audio/video signal with multiple levels

FIELD: video data encoding, in particular, masking of distortions introduced by errors.

SUBSTANCE: method and device are claimed which are meant for masking errors in video sequences. When a transition between scenes exists in a video sequence and an error is present in the image which is subject to transition between scenes, error masking procedure is used, which is based on type of transition between scenes, to conceal the error. Information about transition between scenes together with information about the type of transition between scenes is transferred to video decoder in the message of additional extension information, if the transition between the scenes represents a gradual transition between the scenes, algorithm of spatial-temporal masking of errors is used for masking the image, if the transition between the scenes represents a scene cut, and only a part of the image is lost or damaged, then spatial error masking is used to mask the lost or damaged part of the image, and if the whole image belonging to scene cut is lost or damaged, and the image begins a new scene, it is not masked.

EFFECT: creation of method, by means of which the appropriate form of error masking may be selected for frames which are subject to transitions between scenes in a video series.

3 cl, 3 dwg, 11 tbl

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

FIELD: technology for processing digital images, namely, encoding and decoding of images.

SUBSTANCE: in the system and the method, serial conversion and encoding of digital images are performed by means of application of transformation with superposition (combination) of several resolutions, ensuring serial visualization and reduction of distortions of image block integrity and image contour when compared to many standard data compression systems. The system contains a converter of color space, block for transformation with superposition of several resolutions, quantizer, scanner and statistical encoder. Transformation by scanning with usage of several resolutions outputs transformation coefficients, for example, first transformation coefficients and second transformation coefficients. Representation with usage of several resolutions may be produced using second transformation coefficients with superposition of several resolutions. The transformer of color space transforms the input image to representation of color space of the input image. Then, the representation of color space of input image is used for transformation with superposition of several resolutions. The quantizer receives first transformation coefficients and/or second transformation coefficients and outputs quantized coefficients for use by scanner and/or statistical encoder. The scanner scans quantized coefficients for creating a one-dimensional vector, which is used by statistical encoder. The statistical encoder encodes quantized coefficients received from quantizer and/or scanner, which results in compression of data.

EFFECT: increased traffic capacity and increased precision of image reconstruction.

27 cl, 19 dwg

FIELD: image processing systems, in particular, methods and systems for encoding and decoding images.

SUBSTANCE: in accordance to the invention, input image is divided onto several image blocks (600), containing several image elements (610), further image blocks (600) are encoded to form encoded representations (700) of blocks, which contains color code word (710), intensity code word (720) and intensity representations series (730). Color code word (710) is a representation of colors of elements (610) of image block (600). Intensity code word (720) is a representation of a set of several intensity modifiers for modification of intensity of elements (610) in image block (600), and series (730) of representations includes representation of intensity for each element (610) in image block (600), where the series identifies one of intensity modifiers in a set of intensity modifiers. In process of decoding, code words (710, 720) of colors and intensity and intensity representation (730) are used to generate decoded representation of elements (610) in image block (600).

EFFECT: increased efficiency of processing, encoding/decoding of images for adaptation in mobile devices with low volume and productivity of memory.

9 cl, 21 dwg, 3 tbl

FIELD: method for encoding and decoding digital data transferred by prioritized pixel transmission method or stored in memory.

SUBSTANCE: in accordance to the invention, informational content being encoded and decoded consists of separate pixel groups, where each pixel group contains value of position, at least one pixel value and priority value assigned to it, where at least one key is used, with which value of position and/or pixel value/values of pixels of pixel group are selectively encoded or decoded. Depending on used keys and on parts of informational content which are encoded, for example, value of positions and/or values of pixel groups, many various requirements may be taken into consideration during encoding.

EFFECT: ensured scaling capacity of encoding and decoding of digital data.

8 cl, 5 dwg, 3 tbl

FIELD: systems for encoding and decoding video signals.

SUBSTANCE: method and system for statistical encoding are claimed, where parameters which represent the encoded signal are transformed to indexes of code words, so that decoder may restore the encoded signal from aforementioned indexes of code words. When the parameter space is limited in such a way that encoding becomes inefficient and code words are not positioned in ordered or continuous fashion in accordance with parameters, sorting is used to sort parameters into various groups with the goal of transformation of parameters from various groups into indexes of code words in different manner, so that assignment of code word indexes which correspond to parameters is performed in continuous and ordered fashion. Sorting may be based on absolute values of parameters relatively to selected value. In process of decoding, indexes of code words are also sorted into various groups on basis of code word index values relatively to selected value.

EFFECT: increased efficiency of compression, when encoding parameters are within limited range to ensure ordered transformation of code word indexes.

6 cl, 3 dwg

FIELD: technology for encoding and decoding of given three-dimensional objects, consisting of point texture data, voxel data or octet tree data.

SUBSTANCE: method for encoding data pertaining to three-dimensional objects includes following procedures as follows: forming of three-dimensional objects data, having tree-like structure, with marks assigned to nodes pointing out their types; encoding of data nodes of three-dimensional objects; and forming of three-dimensional objects data for objects, nodes of which are encoded into bit stream.

EFFECT: higher compression level for information about image with depth.

12 cl, 29 dwg

The invention relates to the representation of three-dimensional objects on the basis of images with depth

The invention relates to the representation of three-dimensional objects on the basis of images with depth

The invention relates to the representation of three-dimensional objects obtained using photos of real objects

FIELD: technology for encoding and decoding of given three-dimensional objects, consisting of point texture data, voxel data or octet tree data.

SUBSTANCE: method for encoding data pertaining to three-dimensional objects includes following procedures as follows: forming of three-dimensional objects data, having tree-like structure, with marks assigned to nodes pointing out their types; encoding of data nodes of three-dimensional objects; and forming of three-dimensional objects data for objects, nodes of which are encoded into bit stream.

EFFECT: higher compression level for information about image with depth.

12 cl, 29 dwg

Up!