Video compression method

A video

The invention relates to a video compression method and in particular to a video compression method which is intended to be applied when transmitting a video image as a digital video signal at very low transmission rates.

The video image is digitized by dividing it into pixels and assigning digitized values ​​to the pixels. In the case of a black-and-white image, the pixel value may simply be the brightness value corresponding to the brightness of the corresponding dot in the image in digital form, for example represented by eight bits. Multiple signals are required to represent a color image, and thus digital, such as Y, U, and V pixels and Digitized values ​​for them that contain image brightness and color information. The invention is similarly applied to the compression of all pixel information, and therefore in this application mostly mostly only pixels and pixel values ​​or value information are discussed.

In particular, due to the limited capacity of the channels used to transmit digital image information, the information must be compressed before it can be transmitted. For example, in a conventional television image transmission on a UHF channel with a transmission capacity of 32 Mbit / s, it is practically necessary to compress the image information in a ratio of 1: 101: 20. When a video image has to be transmitted on a channel with a very low transmission rate, for example 8 kbit / s, a very strong compression is thus required, thus compromising the image quality.

Numerous different methods have been developed for video image compression, which are used in the encoder of the transmitting end for encoding image information and for decoding image information and reconstructing the image in the receiving end, respectively. Such methods include, for example, variable length VLC coding, predictive coding, motion compensation, run-length coding, and transform coding, such as DCT discrete cosine transform coding. For ease of calculation, the image is usually encoded as blocks, and the commonly used block size is 8 x 8 pixels. The above methods are known to a person skilled in the art, and although some of them, for example variable length coding, can also be used in the video compression method according to the invention to enhance compression, they are not considered further here as not necessary for understanding the invention.

When transferring a video image as a digital video signal at low bit rates, a compression method is also commonly used, in which the image is divided into blocks comprising nxm pixels, the obtained blocks are compared, the pixel information of which may be and is usually already encoded by some compression method. the coded information of the changed blocks is transmitted and the address information indicating their locations is reconstructed at the receiving end using this information and the known information of said previously processed image. The use of this compression method is very advantageous when transferring a video image at low transfer rates, and therefore the method according to the invention is also intended to be applied primarily in connection with this method, without in any way limiting its use.

The following example illustrates the conditions for video image transmission in a case where the capacity of the available transmission channel is very low and where the application of the method according to the invention is advantageous. The image has a QCIF resolution of 176 pixels / line and the image has 144 lines. The image is divided into 16 x 16 pixel macroblocks of 9 x 11 or 99. Each macroblock consists of four Y-blocks (8x8 pixels) and one U-block and one V-block (8x8 pixels). So there are a total of 4 x 99 + 2 x 99 = 594 blocks in the picture. If the channel capacity is assumed

8 kbit / s and the frame rate is set to 8.3 frames per second, is used per frame

963 bits. Assuming further that the proportion of altered macroblocks in the image is 10%, then the number of blocks to be coded is 0.1 x 594, or about 60. Of the 963 bits available, about 50 are spent assigning altered macroblocks using 910/60 bits or 15 bits are available per.

At very low transfer rates, or if the number of image changes is greater than the 10% assumed above, one commonly used means is to reduce the frame rate so that the amount of image information transferred and thus the resolution can be maintained. However, lowering the frequency of Fig. 30 is known to degrade the quality of the moving image perceived by the eye. An alternative to calculating the frame rate is more efficient compression, in which the information contained in the image block is presented with a smaller amount of data than before.

The object of the invention is to develop a video compression method which makes it possible to transmit image information encoded with a very small number of bits and still maintain a reasonable image quality. It is an object of the invention that the image information of a block comprising 8 x 8 pixels can be encoded with 14 bits. In addition, the compression method according to the invention and the corresponding reconstruction method aim at maintaining the continuity and contrast of the contours of the image. The method also makes it possible to improve the resolution of the pixels by interpolating the image when reconstructing, as well as the reconstruction for a larger number of display pixels, without the outlines being staggered.

To achieve these objects, the video compression method according to the invention is characterized by what is stated in claim 1.

In a preferred embodiment of the method according to the invention, the image is encoded in blocks of 8x8 pixels or when the coding remains too inaccurate in sub-blocks of 4x4 pixels. The information contained in the block is divided into character information and related value information. Most often, a block contains a character formed by one or two outline lines, with the character pattern being determined by the contours and the boundaries of the block. In the method according to the invention, a substantially narrow set of pattern patterns is prepared in advance and a correspondingly short, for example 8-bit code is assigned to each pattern. The character pattern models are designed to approximate as many different character patterns as possible with sufficient accuracy. In the preferred embodiment, the pattern pattern closest to it for the block pattern is searched for and the code assigned to said closest pattern pattern is set as the pattern information code. The value information code corresponding to the associated value information is combined with the character information code.

Another possibility of refinement is to divide the block into four smaller sub-blocks, to which the method of the invention for encoding image information contained in a block is applied by searching for sub-blocks of substantially matching pattern patterns from a predefined substantially narrow set of sub-block pattern patterns created by the block.

Previously coded blocks adjacent to the block to be coded can also be used as an aid in coding to ensure contour continuity.

The method for reconstructing a block compressed by the method according to the invention is characterized by what is set forth in claim 12. In a preferred embodiment, a block compressed by the method according to the invention can be reconstructed to a larger number of pixels without staggering the outline of the block.

The invention will now be described in more detail with reference to the accompanying drawings, in which:

Figure 1 shows block and sub-block pattern patterns used in an embodiment of the invention in binary form; Figure 2 shows a set of contour block pattern patterns and corresponding contour direction codes associated with an embodiment of the invention; Figure 3 shows an example of a block associated with a block, one example of a block converted to a binary pattern, interpolation of pixel value information, and Figure 5 shows an example of converting an outline pattern to a larger number of pixels.

As already stated in the general part of the description above, the basic idea of ​​the invention is that in order to encode the image information contained in a block, which consists of its pixel value information, the block character information and the associated value information are first derived from it. The character information can be derived, for example, by generating a block binary image from the block image information. Value information related to character information, e.g., binary image area value information, is obtained from the original image information by determining, for example, the average or median of pixel values ​​in the area or by taking the value of a particular pixel in the area as value information. To encode character information for the character pattern it defines, a character pattern pattern that closely matches it is searched for, and the code assigned to the character pattern pattern is set as the character information code. If the closest congruent pattern differs too much from the pattern, it can be refined or the method of the invention can be applied to parts of a block, sub-blocks for which a number of pattern patterns of sub-blocks have been prepared in advance.

Figure 1 shows as binary images a predetermined set of hah5 pattern patterns used in an 8x8 pixel block and a 4x4 pixel sub-block used in one embodiment of the invention. There are 192 block pattern patterns and 47 sub-block pattern patterns. The character patterns have been designed to represent as many character patterns as possible in practice. Most block pattern models thus have only one contour, but a representative set of two contour models is also included in the models. In addition, the patterns include some checkerboard patterns and denser line patterns, the so-called dense patterns that are useful, for example, in encoding hair or similar miniature characters.

In principle, any suitable codes can be assigned to the character patterns. In the example of Figure 1, for example, 8x8 pixel block pattern patterns, in which the block pattern information can in most cases be presented with sufficient accuracy, can be given 8-bit codes for all, leaving possible 8-bit codes to represent the advanced pattern patterns. On the other hand, it is also possible to use variable length coding in the coding of the character information, whereby the most common character pattern models are given shorter codes and thus save coding capacity to present refinements or, if necessary, to include all four sub-block pattern patterns in the character information code. It is clear to a person skilled in the art that, for example, many different coding options can be implemented within the 8 character information bits allocated per block.

It will also be apparent to one skilled in the art that current image analysis methods offer other possibilities for deriving the character information contained in the block image information in addition to binary image development. In the transmitter end encoder, where the encoding of the image information is performed, a considerable amount of computational capacity is usually available, which allows the use of various image analysis methods. Also, comparing a character pattern corresponding to derived character information to character pattern models can be implemented in many different ways. One useful solution is to simply compare the character pattern in any sequence to all possible models and select the most suitable one. Similarly, refinement of the model can be done, if necessary, simply by experimenting with certain defined refinement options in some order, for example, based on their probability.

Figure 2 relates to an embodiment of the invention in which the direction and location of the lines are analyzed from the character patterns and the character information is encoded by combining the obtained contour direction code and location code. The embodiment is considered in the case where the character pattern has only one outline. Figure 2 shows, by way of example, 12 block diagrams in which each of the reinforced outlines shown has a certain general direction and at the same time a certain shape. In the upper right corner of each drawing is a 4-bit area code corresponding to this direction. The location of the outline in the block is indicated in the drawings by the numbers 1, 3, 5, 7, etc., which can be coded as desired. If that location code is also represented by four bits, a total of eight bits are required to define the pattern patterns in this example.

The following is an example of a way to generate a binary image from a block image information that defines the outline of the character pattern. Let the block size be 8 x 8 pixels. Calculate the absolute values ​​of the line pixel differences horizontally as follows:

Di = IPi-Pj + il D7 = 0, where i has the values ​​0, 1, ..., 6 and

Dj = absolute value of the difference at pixel i,

Pj = value of pixel i.

If the pixels in the line are set to 32, 30, 29, 10, 11, 20, 18, and 19, the corresponding differences are 2, 1, 19, 1, 9, 2, 1, and 0. The differences are converted to binary values ​​using a threshold equal to or greater values ​​are set to one, for example, the quarter of the largest difference, which in this case is 4.75. The threshold differences are:

00101000

Now mark the zeros as zeros from the left until one is found, after which the zeros are marked as ones. If one is still found, the following zeros are marked as zeros. The binary values ​​corresponding to the pixels of the line are obtained:

00111000

By repeating this procedure, the vertical contours contained in the block are separated for each line and a horizontally computed block binary image is obtained, with a binary value derived from the absolute values ​​of the pixel differences for each pixel as described above.

By performing the corresponding calculations on the pixels of the block in rows vertically, the horizontal contours contained in the block are separated and a vertically calculated binary image of the block is obtained. To form the final binary image, for each pixel, the binary value in the horizontally computed binary image and the binary value in the vertically computed binary image are logically added together. Figure 3 shows an example of a binary image that includes a single outline defined by the boundaries between adjacent pixels that receive different binary values. Of the alternatives in Figure 2, the outline closest to this outline is marked in the figure.

Next, the method calculates the direction of the contours contained in the binary image. The calculation proceeds as in the example of Figure 3 as follows. Subtract the binary value of each pixel in horizontal row 1 from the value in the same vertical row of horizontal row 0, each binary value in horizontal row 2 from the corresponding value in horizontal row 1, and so on, and finally each binary value in horizontal row 7 from the corresponding value in horizontal row 6. The differences obtained in each vertical row are marked at the bottom of the drawing in Figure 3 for the vertical rows. The differences are added together and the sum of the differences is denoted by the symbol Zve. Correspondingly, the binary value of each pixel in the vertical row 1 is subtracted from the value in the same horizontal row of the vertical row 0, etc., and finally each binary value in the vertical row 7 is subtracted from the corresponding value in the vertical row 6. The differences obtained are marked on the right side of the drawing for each horizontal row. The differences are added together and the sum is denoted by the symbol Σρε. If Σνε and Σρε are non-zero numbers, the ratio is calculated

R = Σve / Σρε

The area code is determined based on the value of the ratio R in the look-up table. The directions and the corresponding codes can be defined with the desired accuracy. Table 1 below is an example of the lookup table used to determine the area code:

table 1

<td>R - Σνε / Σρε</td><td>Direction</td><td>R = Σ ve / Σρε</td><td>Direction</td>

<td>0 &lt;R &lt;0.35</td><td> 0001</td><td>0&gt; R&gt; -0.35</td><td> 1001</td>

<td>0.35 &lt;R &lt;0.75</td><td> 0010</td><td>- 0.35&gt; R&gt; -0.75</td><td> 1010</td>

<td>0.75 &lt;R &lt;1.3</td><td> 0011</td><td>- 0.75&gt; R&gt; -1.3</td><td> 1011</td>

<td>1.3 &lt;R &lt;3</td><td> 0100</td><td>- 1,3&gt; R&gt; -3</td><td> 1100</td>

<td>R&gt; 3</td><td> 0101</td><td>R &lt;-3</td><td> 1101</td>

If Σνε = Σρε = 0, it is a flat area without contours. If Σνε = 0 and Σρε # 0, the figure has a vertical contour with the code 1000. If Σρε = 0 and Σνε Φ 0, the figure has a horizontal contour with the code 0000. In the example figure of Figure 3, Σνε = 8 and Σρε = 3, where R = 2.67 and the corresponding area code from Table 0100 above.

The position of the outline in the figure can be found by counting the number of ones (or zeros, respectively) in the binary image from horizontal rows starting from the upper left (or lower) corner. The ones are counted along the line until zero is encountered.

In this case, move to the next horizontal line. The sum of the units obtained is compared with the numbers of units tabulated by area code. In the example of Figure 2, there are 29 ones. The closest table value would be 32, based on the closest congruent pattern pattern in Figure 1. A contour corresponding to this value is drawn in Figure 3 with reinforcement. Outline detection can be performed using either the number of ones or zeros.

The location of the outline is indicated coded as desired.

The direction and location codes together form a code on the basis of which, when reconstructing the image, the most suitable character pattern model of the block can be selected, for example from the models of Figure 1.

The difference between the pattern pattern derived from the image information and the pattern pattern closest to it can be determined, for example, by calculating the number of pixels contained in the deviation areas of the contours of the pattern and the pattern pattern. If the difference exceeds the permissible limit value, an attempt is made to refine the model by adding, for example, a cross line two pixels wide, after which the difference is redefined.

One way to find a more accurate model for a block pattern is to divide the block into sub-blocks, each of which is searched for a pattern pattern as described above from a set of pattern patterns preset for the sub-blocks. One possibility is to convert the sub-block to a larger number of pixels, so that the pattern patterns of the block can be used as models for them. In this case, the block code must, of course, be accompanied by information on the zooming of the block, for example by means of a suitable prefix, in order to reconstruct the block to its correct size.

One way to refine the character pattern model is to apply to the block a model that contains the so-called a dense pattern consisting, for example, of low-amplitude streaking on a flat m ii htm base. Dense patterns are useful, for example, in encoding hair or similar hard-to-distinguish characters.

The coded block can be reconstructed on the basis of the pattern pattern and the associated value5 formation, either as such or using appropriate low-pass filtering.

Alternatively, an interpolated reconstruction can be performed, in which, in addition to the pattern pattern, extreme pixels of adjacent blocks, which are limited to the block under consideration, are also utilized. Figure 4 illustrates a reconstruction in which the pixel value information is refined by interpolation. Within the block10, the pixel values ​​of the sub-areas of this pattern are interpolated using the pixels belonging to the adjacent blocks A, B and C. In the light area of ​​Figure 4, the interval C77 to D77 and the interval B77 to D77 are first interpolated, and these interpolated values ​​are used to interpolate the remaining pixels. One possible interpolation order is shown in Figure 4 by arrows. For example, between C77 and D77 are the following interpolated ar15 vo:

(7C77 + 077) / 8, (6C77 + 2077) / 8, (5C77 + 3077) / 8, (4C77 + 4077) / 8, (3C77 + 5077) / 8, (2C77 + 6077) / 8, (C77 + 7077) / 8

The subjective accuracy of the reconstruction can be increased by dividing each pixel in the reconstructed image into four smaller pixels, whereby the size of the reconstruction block will be 16 x 16 pixels. In this case, the outline of the reconstructed image must also be modified. Figure 5 shows the conversion of a block of 8x8 pixels into a block of 16 x 16 pixels by dividing each pixel into four smaller pixels. The dark area in the image is the character after the outline modification. In this way, the image can be reconstructed for a larger number of pixels without staggering the outlines. It should be noted that converting an image to a larger number of pixels when reconstructing an image does not require any additional information during the block encoding step.

When a compression method is used in the transmission of a video image, in which only the information of the changed blocks is transferred, the method according to the invention can encode the changed blocks with a very small amount of data. For example, when reporting a character pattern with eight bits and two value information, e.g., basic 35 grayscale, DPCM-encoded with three bits each, 8 + 3 + 3 = 14 bits are required to encode the block. As shown above, the character pattern code may also be shorter in some cases. For example, a character pattern consisting of a flat area with a horizontal and vertical contour may be indicated by a code that includes a defined flat area code and the value of the corner point of the character in the block.

An advantage of the method over the prior art is that the compression is applied to the character information contained in the 5 blocks. The information defining the value information can be excluded from the compression and thus maintain the contrast of the original image

In addition, the quality of the reconstructed image can be improved by matching the contour of the figure to the figures of adjacent blocks, using interpolation of the block extremes to adjacent blocks in the reconstruction, and converting the reconstructed image to a larger number of pixels and applying contour modification.

The present invention is not limited to the examples given above, but can be applied within the limits permitted by the appended claims.