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

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

 

The invention relates to the field of digital image processing and can be used when transferring images over a slow communication channels. The technical result of the invention is to develop a method which increases the encoding speed when combined vector quantization and fractal image encoding.

The closest to the technical nature of the claimed method of increasing the speed when combined vector quantization and fractal image coding is U.S. patent No. 4941193, 1990 [1]. The authors of the patent Mbarki and Asloan first saw the possibility of applying systems theory iterative functions to the problem of image compression.

Compressing images in the specified prototype is as follows [2]. For each rank of the block of the original image are the domain and the corresponding transformation that best covers this rank unit. This is usually an affine transformation. 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 region is compressed to fit the size of the rank field. And, finally,by the method of least squares is calculated contrast α and brightness β the corresponding optimal values that minimize the expression (1):

where: E(R, D) is a metric between the rank R block and brought to him the size of the domain block D;

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

m - number of columns processed in the rank block.

If the exact match does not work, then break rank blocks into smaller. Continue this process until, until you get an acceptable match, or the size of the rank of blocks reaches a predetermined limit.

The disadvantages of the prototype is that when encoding rank areas with a large dynamic range, it is difficult to choose a domain with more dynamic range, resulting in lower quality of image reconstruction. In addition, fractal coding requires a large amount of computation, because, firstly, for each rank of the 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 domain rank block.

The purpose of this invention is to develop methods for increasing the coding rate, when combined vector quantization and fractal coding from the interests of, providing increased encoding speed compared to the fractal compression method for any type of images while maintaining the transmission rate and the length of the frame format.

One way to increase the speed when combined vector quantization and fractal image coding is the classification of domains and blocks that make up the code book. A great time coding is a result of the fact that you have to produce a large number of comparisons rank domains with domains and blocks of code book. The total encoding time is the product of the number of comparisons and the time required to perform each mapping. Each mapping is requiring large computing pixel-by-pixel processing, including rotation, compression and matching domain block or block of code book to rank the block.

The present invention uses the classification proposed by Fisher in [3], according to which each domain belongs to one of the three classes. Further domain-rank mapping is performed only for those domains, which belong to the class of equivalence of this rank field.

1 class a1≥And2≥And3≥And4

2 class a1≥And2≥And4≥And3

3 class a1≥And4≥And2 ≥And3

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 this case, in addition to domain blocks of the original image, also is the classification of the blocks of the code book. As a result, when coding 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 the code book corresponding to the class rank of the field.

The claimed method is illustrated by drawings:

- Figure 1 - algorithm for encoding image when combined vector quantization and fractal image coding based classification domains and blocks of code books;

- Figure 2 - the scheme split into classes of domains and blocks of code books;

- 3 - the ratio of the encoding time and the peak signal to noise ratio (PSNR) when encoding the image using the joint use of fractal coding and vector quantization without classification and classification.

The encoding algorithm of the image when sovmescheny.spalnya vector quantization and fractal image coding based classification domains and blocks of code book shown in figure 1. The original image is divided into nonoverlapping rank and domain blocks, which are classified. Then, for each rank of the block, find the domain that belongs to the class of equivalence of this rank field, 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 books corresponding to the encoded class rank region. 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 presents the ratio of the encoding time and the peak signal to noise ratio (PSNR) when encoding the image using the joint use of fractal coding and vector quantization without classification and classification. Conducted the surveys when encoding the test image "Lena" on a computer with an AMD Athlon 1900 showed that time, the image encoding using the classification of domain blocks and blocks of code books is reduced in 2 times (from 8 minutes to 4 minutes) by reducing the quality of the reconstructed image by 0.2 dB, which is negligible.

The proposed method can be implemented on modern digital processing of signals, and can find its application in the transmission of images over a slow communication channels

BIBLIOGRAPHIC LIST

1. Barnsley M., Sloan, A., Methods and apparatus for image compression by iterated function system. U.S. patent No. 4941193, 1990.

2. Swelstad, Fractals and wavelets for image compression in action. Tutorial - M.: Publishing house Triumph, 2003.

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

The way to increase the coding rate, when combined vector quantization and fractal image coding, which consists in the fact that the image is divided into a rank blocks, for each rank of the block of the original image to find the domain or block of code books and the corresponding transformation that best covers this rank unit, if sufficiently exact match does not work, then break rank blocks into smaller, continuing this process until you achieve an acceptable according the or the size ranking of blocks reaches a predetermined limit, and after breaking the image to rank the blocks classified, then for each rank of the block of the original image to find the domain or block of code books, blocks images from the class corresponding to the class of the encoded rank of the block and the transform that best covers this rank unit, if sufficiently exact match does not work, then break rank blocks into smaller, continuing this process until you achieve an acceptable match or the size ranking of blocks reaches a predetermined limit.



 

Same patents:
The invention relates to the field of digital signal processing image and can be used when transmitting video over narrowband communication channels and implementing quick view large archival databases

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

The invention relates to photo - and video system technology

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

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: 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: 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: 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: 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: 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: 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

FIELD: information technology.

SUBSTANCE: invention refers to method and electronic device for determination of applicability of the encoded file in an application, which allows for using such type of files but has some restrictions related to properties of such file type, as well as to the computer-readable medium containing the computer programme for performing the said method. To fulfill the above method, the electronic device contains at least one block for correlating the files associated with the application, which accepts (50) at least one property of the encoded file and correlates (52) the property with the application, creates (54) an indicator showing whether the file can be used by the application relying on correlation, and connects (56) the indicator with the encrypted file for further provision of quick decision making regarding usage of the file by the application.

EFFECT: provision of quick choosing encoded files for usage by the application without preliminary decoding of the file.

16 cl, 7 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

Up!