DE19758760B4 - Adaptive encoding method for digitised video signal - determining shortest video block which can be used to optimise signal encoding not to exceed bandwidth and precessing power threshold - Google Patents

Abstract

The method involves dividing a video image into blocks which are subsequently encoded. A number of coding processes are used on every block resulting in the shortest code used. The method involves intercoding of the blocks to produce an intracode with the shortest code being transmitted. The code to be selected has to be shorter than a threshold value or else a second code will be generated. The rate at which the processor is used determines the imposed load of the encoded data, which load is monitored not to exceed another threshold value. The transmitting channel is monitored as well not to exceed the assigned bandwidth for the data transmission.

Description

The The invention relates to methods of encoding an image.

Lots Types of video encoders compress video images to the crowd to reduce data over transmit digital channels or stored in memory or other media. typically, receives a video encoder a digital video frame as pixel tables, which represent a series of frames, one after the other to give a moving picture. The video encoder translate the pixel tables into encoded video data, which is less Bits for her Need expression. An ideal coding method for A video encoder has a low computational cost for fast encoding with minimal processor circuitry overhead, high compression, around the for the transfer or saving the video data needed to reduce bandwidth and receives nevertheless a high image quality the coding upright. Such ideal coding methods are difficult to achieve. Usually, the computational effort elevated and / or the picture quality be lowered to improve the compression. coding, which the compression without corresponding increase in the computational effort improve or reduce the computational burden without a corresponding Loss of compression or image quality will be needed.

One ideal coding method does not exist. Suitable for certain applications Coding methods typically become consistent with compression selected, the for the available bandwidth needed and from the available Computing power available can be made. A use case where video over a Channel is transmitted with very limited bandwidth, often used a complicated coding to increase the amount of data considerably reduce that needed is used to accurately transfer a video image. This requires computational resources adequate performance to complex coding at the frame rate of the video image. Complicated codings may be inappropriate for use cases with limited or used by several computational resources and a channel with a relatively large transmission bandwidth be.

The Choose a suitable video coding method for a software coder, on a variety of platforms at different levels the available Processing power is running, raises additional Problems on. If a coding process of minimum difficulty for a platform low performance is selected, the video compression suffers often, so that the transmission channel bandwidth is overloaded can not (she is then unable to get the desired frame rate to comply) while wastes the computing power of higher performance platforms becomes. In contrast, if a highly complex coding method is used, can Platforms may be low performance unable to encode video at the desired frame rate, and transmission channel bandwidth can be wasted at the expense of processing power for others Purposes could be used.

Out IEEE Transactions on Image Processing, Vol. 3, No. 2, 1994, Pages 207 to 219 is known, representing a gray scale image Divide pixel matrix into a Quadverzweigungsstruktur and this Structure to encode the information about a pixel in the gray scale image consists of a component.

The IEEE Transactions on Image Processing, Vol. 5, No. 1, 1996, pages 4-15, discloses a tree structure associated with black and white images, the tree structure used to structure and localize the Image information is used in different levels. The levels differ in their importance in terms of image reconstruction, lower levels are more important in image reconstruction due.

The Television and Cinema Technology, No. 5, 1994, pages 227 to 237 an overview of the MPEG-2 video standard, essentially presenting algorithms of video coding become.

DE 195 01 551 A1 discloses a motion vector detecting means. In a color image, the pixel matrix comprises multi-component entries for each one pixel, the components in combination indicating the color of the corresponding pixel. An encoding of this color image is not possible by means of the method, since the encoding of multicomponent entries is not provided.

task It is therefore an object of the invention to provide a method which is efficient a colored image using the Quadverzweigungsstruktur coded.

These Task is solved according to the method of claim 1.

This makes it possible to code a color image whose information has a plurality of components per pixel, wherein the first components of the pixels are coded in a first quad branching structure and a further component in a further quadrangular structure, the one Sub-tree of the first quad branching structure is divided and coded. Improved compression is possible because a coding representing the further component provides stems of the first quad branching structure and only the additional branches in the first quad branching structure need to be coded.

advantageous Further developments can be found in the dependent claims.

The The invention will be apparent from the illustrated in the accompanying drawings embodiments described in more detail.

1A respectively. 1B illustrate a quad branching distribution of a block and the associated quad branching structure.

2 FIG. 12 illustrates relationships between quad-squared divisions and quad-branch structures of three color components in a coding method according to an embodiment. FIG.

3 FIG. 10 is a flowchart of an intra-coding process according to an embodiment. FIG.

4 is a flowchart of a known inter coding process.

5A and 5B illustrate a video coding process and an encoder according to an embodiment.

6A and 6B illustrate a video coding process and an encoder according to another embodiment.

7 FIG. 16 shows graphs showing percentages of inter-coded lengths less than a threshold, intra-codes used, and a reduction in bit-rate as functions of one in the coding method of FIG 6A illustrate the threshold used.

8th FIG. 10 is a flowchart of a process that changes the coding complexity according to the application of a processor or a communication channel.

9 illustrates the relationships between coding complexity, bits-image (compression) and coded image quality for a coding process according to one embodiment.

One Video image conventionally consists of a sequence of individual images, which times in the video image represent and which are sequential reproduced to create the illusion of movement. Each frame of a video image can be digital through pixel tables be represented the one or more two-dimensional matrices of pixel values each pixel value being a characteristic of an area (pixel or pixel) in the video image at a time corresponding to Single image identified. For example, in a rendition a video frame, usually referred to as YUV color rendering, each frame three corresponding two-dimensional matrices of pixel values, where one matrix is the Y components (i.e., luminances) of the pixels in the frame and two matrices U and V components (i.e., chrominances) of pixels in represent the frame.

The Coding translates the pixel matrix values into codes which are fewer Need bits as the original matrices to express these. The video picture can then saved or transmitted which requires less memory or bandwidth. In a kind of coding process, as by the H.263 protocol for Videophones, each frame of a video image is either an intra-frame, which is intra-coded, or an inter-frame, that is inter-coded. Intra coding encodes a single frame below Use only the pixel values for the Single frame and is on still images and frames or blocks within a moving picture applicable. Inter coding combines pixel values a running frame with information from previous frames and is generally applicable to mobile picture coding.

During encoding, a frame is typically divided into root blocks, typically 16 by 16 or 32 by 32 pixels, to avoid the computational difficulties that may arise from manipulating larger arrays of pixel values. The root blocks are then coded. US 5,446,806 describes a quad-branch structured coding process that applies a fixed number of Walsh transform coefficients to represent the contents of the blocks (or sub-blocks). The content of this document is expressly incorporated by reference. According to a quad-branching structure coding process, sub-blocks of a predetermined initial division of a root block are merged to form a larger sub-block if the content of the larger sub-block can be adequately described by a few code values.

1A respectively. 1B show an exemplary quad or quadruple branching distribution 100 of a block of pixel values and the resulting quad branching structure 150 for the block. The quad branching split 100 contains sub-blocks a to s of pixel values which are from the original block through a merge process to be selected. US 5,446,806 describes a merge process in which a fixed number of Walsh transform coefficients describe the contents of each sub-block a to s and blocks are merged to form sub-blocks a to s when the set number of Walsh transform coefficients for the merged block repeats the error per pixel increased less than a threshold. The quad branching structure 150 consists of branches connecting nodes to four levels 0 to 3, each level n being a preselected division of the block 100 in 4 ⁿ subblocks. The level 0 corresponds to a division with a single sub-block, ie the original block, and dividing each block into a preselected division corresponding to a level (n-1) into four smaller blocks forms the preselected division corresponding to each level n Level may include one pixel value per block, or as many pixel values as there are coefficients, one block corresponding to a leaf node of the quad branching structure 150 to describe.

Each node in the quad branching structure 150 identifies a block in a preselected split according to the level of the node. Nodes with branches to a next higher level identify blocks that are not in the quad branching split 100 are. Leaf node of the quad branching structure 150 (ie, nodes with no branches extending to higher levels) indicate blocks a to s that are in the quad-branch split 100 are located. A quad branching code generated for the root block indexes the quad branching structure 150 and includes values describing the content of the blocks associated with the leaf node of the quad branching structure 150 (ie the contents of blocks a to s).

at YUV color video become three components Y (luminance), U and V (chrominances) of a root block represented by three matrices of pixel values. Matrices for the representation Of components U and V often contain fewer pixel values than those Matrix representing the Y component of the root block For example, in a known YUV 4: 1: 1 format, an area in a frame has represented by four Y values (usually four pixels) only one U-value and one V-value. Accordingly, a 16 by 16 pixel root block through a 16 by 16 matrix of Y values, an 8 by 8 matrix of U values and an 8 by 8 matrix of V values represents. The matrices of the Y-values, the U-values and the V-values have been assigned Quad branching structures, here as the Y-tree, the U-tree and the V-tree designates become.

According to one aspect of the invention, the V-tree for a frame is to be a subtree of the U-tree for the frame, which in turn should be a subtree of the Y-tree for the frame. 2 illustrates an example of the relationship between a Y-tree 235 a U-tree 225 and a V-tree 215 for a single image and corresponding quad branching divisions 230 . 220 respectively. 210 a 16 by 16 matrix of Y values, an 8 by 8 matrix of U values, and an 8 by 8 matrix of V values.

The requirements regarding the Y-tree 235 , U-tree 225 and V-tree 215 simplify the coding of a root block because of the branching Y-tree 235 the U-tree 225 generated and the branching U-tree 225 the V-tree 215 generated. Specifically, a coding method begins with a preselected division of the matrix of Y values at the highest level (e.g. level 3) and determines which sets of four blocks should be merged in the highest level division. Merging forms an intermediate partition containing blocks from the preselected highest level split (eg Level 3) and next lower level (eg Level 2) blocks of the preselected split. Merging continues to examine and merge blocks at progressively lower levels until no further merge is needed and the quad branching split 230 is reached. The quad branching split 230 defines the structure of the Y-tree 235 ,

The Y-tree 235 in turn defines an incipient division 221 from which the division 220 and the U-tree 225 be determined. The breakdown 221 contains blocks of U-values, assigned to the Y-tree 235 , For example, if block U has predetermined divisions corresponding to each level of the Y-tree 235 has, identify the leaf nodes of the Y-tree 235 Blocks in the split 221 , If the matrix of U-values has a lower number of levels of the predetermined divisions because the U-matrix is smaller, the branches of the highest level become 235 branches when the U-tree 221 is formed. For example, if the quad branching split 230 is a 16 by 16 matrix of Y values, each block g, h, i, j, o, p, q, and r contains one pixel in the division of level 3 of the Y matrix. The breakdown 220 , which is an 8 by 8 pixel value matrix, has no level 3 division since the level 2 of the predetermined partition has only one U value per block. The branching of the third level from the Y-tree 235 provides a quad-branching structure with three levels, the beginning of splitting 221 equivalent. Block merge tests set four blocks of the same level to determine if any set of four blocks in the split 221 should be connected. In 2 the blocks m, n, o 'and s combine to form the block m'.

The V-tree 215 is made from an incipient branching through the U-tree 225 is defined, determined. The joining of blocks in the beginning branch creates the quad branching split 210 , that of the quad branching structure of the V-tree 215 assigned. In 2 Blocks of V values associated with blocks a, b, c and d combine to form block a '. In an alternative embodiment of the invention, the V-tree 215 a subtree of the Y-tree 235 be, and some U-tree 225 should be a subtree of the V-tree 215 be. In yet another alternative embodiment, the V-tree 215 and the U-tree 225 Sub-trees from the Y-tree 235 be, but not under each other form sub-trees.

For natural videos generate the subtree constraints little distortion in the decoded video, because the three color components related to each other. If a block of Y values is similar, chances are good that U-values and V values in the block are sufficiently similar so that combining the values in a single block no big distortion in the encoded Image causes. The coding difficulty is reduced because the Determination of underground trees and V-trees from a developed quad branch with fewer possible Check connections starts. Compression tends to get better because a code representing the V-tree strains of U-tree creates and only the extra branches in the U-tree encoded to represent the U-tree. In similar Way, the U-tree supplies trunks of the Y-tree, and only the extra ones Branches in the Y-tree are coded. The alternative is the relationship between the first coded quad branching structure and a second coded quad branching structure indicated by branches, taken from or added to the first quad branching structure, to form the second quad branching structure.

One Advantage of the subtree restrictions in reduced difficulty of decoding calculation. There a for Y values of assembled Block always has a set of U and V values, if one can Color conversion to the RGB domain needed will, the entire surface of the block can be filled with a single RGB vector, and no more Operation check or Distribution is required. The limitations on Quad branching structures for the Color components not only affect YUV color, they are Applicable to other color formats including RGB colors.

The restrictions with regard to the quad branching structures, which Y, U and V matrices for a Single frame of a video are on intracoding and Intercoding applicable. According to one Another Aspect of the Invention Improves Intrablock Differential Pulse Code Modulation (DPCM) the compression of intra-coded blocks with or without the restrictions the quad branches for Farbkomponentenmatrizen. For Intra-block DPCM coding becomes a difference between a base vector and code vector which is the Content of a block or sub-block within a frame determines, determined before the codevector is quantized and the entropy or the run length be encoded. If the base vector is selected correctly, the difference is small and the compression is improved.

An example of application of intra-block DPCM coding is described for the quad branch, where the structured Walsh transform coding is applied to the block according to FIG 1 although the intra-block DPCM is also applied to intra-coding with or without split blocks according to a quad branch structure or code vectors which are Walsh transform coefficients. Quad branch-structured Walsh transform coding stores a fixed number of Walsh transform coefficients per leaf node in a quad branch structure, regardless of the size of the sub-block represented by the leaf node. For example, if the sub-blocks a and g are represented by 4-by-4 and 2 by 2-matrices of pixel values, respectively, the Walsh transforms of the blocks a and g are 4-by-4 and 2-times, respectively -2-matrices of Walsh transform coefficients. A single coefficient w00 or four coefficients w00, w01, w10 and w11 from the Walsh transformations can be encoded per leaf node. Here, the coded coefficients are denoted by a codevector W, and for the exemplarily selected coding method, the codevector W is {w00} or {w00, w01, w10, w11}. The code vector W for a node a is referred to as Wa and similar for the other nodes. An exemplary quad branching code provides the codevectors in a one-dimensional order Wa, Wb, Wc, Wd,..., Wr, Ws that pass zigzag through the sub-blocks in the quad-branch split 100 follows, so that the code vectors consecutive in the quad branching code are typically close to each other in the root block.

An example embodiment of the DPCM intra-coding uses a basis vector W * that starts with the same known value for each root block, but changes its value during the encoding of each root block. An example of a one-dimensional DPCM, as an example The selected DPCM intracoding method comprises four steps for each sub-block x of an intra-coded block, (1) calculate Wx-W *, (2) quantized Wx-W * with a quantizer of equal step size, (3) set W * equal to W * plus the quantized one Value Wx - W * and (4) encode the quantized value Wx - W * with an entropy coder. After each block is coded, the basis vector W * is equal to the decoded value for the currently coded vector Wx. When the next code vector W (x + 1) represents an area near the area represented by Wx, the coded vectors Wx and W (x + 1) will often be similar, and the difference W (x + 1) -Wx will be small. Accordingly, the entropy coding efficiently compresses the quantized differences.

3 illustrates a more general DPCM intra-coding technique that is incorporated herein by reference 310 begins with selecting a sub-block x of an intra-code block to be sub-coded. The order in which the sub-blocks are selected and encoded determines the information available to a decoder at 320 select the basis vector W * for subsequently encoded sub-blocks. In one embodiment of the invention, the selected basis vector W * has a fixed value known to the encoder as well as the decoder for the first sub-block of each root block. Alternatively, the base vector W * could be reset to the fixed value less frequently, for example, at the beginning of each frame. Some advantages of starting with a fixed basis vector W * are that no bits are needed to transmit an initial basis vector, and starting each root block with the fixed base vector resets the coding and stabilizes it by reducing the propagation of errors.

After the initially set value for the base vector W *, the base vector W * changes according to the previously coded vectors. For example, when the code vectors Wa to Ws are transmitted in this order, the base vector W * selected for the sub-block b may depend on the code of the vector Wa. The basis vector W * selected for sub-block c may depend on the encoded vectors Wa and Wb, and the base vector for a selected sub-block may generally depend on the code vectors provided before the code vector for the selected sub-block. One-dimensional DPCM intra-coding uses decoded vectors W (x-1) for the base vector W * when vector Wx is encoded. If the sequence a to s zigzag way through the quad branching division 100 follows, the base vector W * will often but not always be a codevector of a sub-block near the sub-block currently being coded.

A two-dimensional DPCM intracoding technique selects W * as a function of the previously encoded vectors that follow the ones in step 310 adjoin selected sub-block. For example, W * is selected as equal to Wa for the subblocks b and c, and W * is selected as Wb, Wc, or a weighted average of Wa, Wb, and Wc when the subblock d is coded. In two-dimensional DPCM intra-coding, the base vector is chosen for geometric proximity to the sub-block to be coded, rather than for proximity in the code sequence. The encoder and decoder may have any desired predefined rule for selecting the base vector W * in step 320 use.

Once the basis vector W * is selected, the difference Wx-W * in step 330 determined, this difference is in the step 340 quantized and in step 350 entropy. The quantization in step 340 is done using a uniform step size which divides the difference Wx-W * by a fixed step size and truncates the result to a specified number of bits. Equal step size quantization provides a simple quantization method that, in combination with entropy coding, efficiently compresses the video data. The entropy coding may be, for example, Huffman coding or arithmetic coding. After the entropy coding 350 the DPCM intra coding of the root block is continued by at 310 another sub-block is selected, or it is terminated after the last sub-block.

intra-coded Frames are those in which all root blocks are intra-coded are. Intercoded frames may have some inter-coded root blocks and some intra-coded root blocks to have. Intercoding of a root block usually begins with motion estimation, wherein after a previously decoded frame with respect to a predictive Blocks is sought, which adapts closely to the current frame. If once such a predictive Block for The root block is found, a quadgebzweigungsstrukturierter Coding process or some other coding process that Code difference between the root block of the predictive block. Ideally contains a coded difference block exclusively or almost all zeros or another combination of values that compress efficiently are. In some cases however, if the motion estimation no well fitting predictive Block results in little or no compression.

4 illustrates a relatively simple coding method 400 that the intercoding 410 at each root block of an intra-frame image and at 420 stores the resulting intercode. The coding method 400 uses the intercodes and the motion vectors representing the predictive blocks regardless of the resulting degree of compression. The applications of coding methods 400 include a video encoder that receives an output from a video camera and stores compressed video in a data buffer or other memory of a storage medium such as a hard disk or optical disk. The compressed video data may also be transmitted over a channel, for example after storing the compressed data in a video data buffer. In cases where a video image changes rapidly, the coding process may be 400 may not cause much compression and storage, or the available bandwidth may be exhausted before a video image is complete.

5A and 5B illustrate a video coding method 500 which provides better compression than coding 400 or a video encoder 550 who uses the video coding method 500 implemented. The video coding method 500 works on blocks of an internal image, stored in a memory 560 , In initial steps 510 and 520 of the video coding method 500 intercode or encode coding elements 570 respectively. 574 in the intercode (step 510 ) or intracode (step 520 ) a root block. Coding 570 and 575 may be separate circuits which independently execute the respective coding processes or software processes which are sequentially executed by a processor and the coding steps 510 and 520 are executed either serially or in parallel, depending on the capabilities of the video encoder 550 , Since the Intrablock encoding is the same for single frame images, Encoding Element 575 also encode blocks of the intra-frame images. The coding elements 570 and 575 deliver approximately the same quality in a decoded picture. For example, equivalent quantization step sizes (and splicing thresholds for quad branching encoding) maintain similar levels of distortion in decoded images.

A size comparator 580 compares in step 530 an intercode from the coding element 570 with an intracode from the coding element 575 to determine which of the two codes is shorter. The size comparator 580 generates a control bit that is a multiplexer 590 is created to select whether the intercode from coding element 570 or the intracode of coding element 575 into a coded bit stream from the video encoder 550 is inserted. The control bit is also inserted into the bit stream to indicate to a decoder whether the block is intra-coded or inter-coded. The step 540 or 545 stores those of the codes containing the fewest bits and the unused code is discarded. The coding method 500 encodes each root block twice (steps 510 and 520 ) and accordingly requires more calculations than the coding method 400 which simply sets an intercode for each root block. The coding method 500 however, improves the mean compression because smaller intra codes sometimes replace larger intercodes.

6A respectively. 6B illustrate a coding method 600 or a video encoder 670 with which the coding method 600 is performed. The video encoder 670 contains many of the same elements as the video encoder 550 out 5B , and the above description of the elements of the video encoder 550 also reads elements of the video encoder 670 which have the same reference character. The video encoder 670 also contains a threshold comparator 685 who is in the step 620 a threshold length tH with the length (in bits) of an intercode of inter coding element 570 compares. If the intercode is longer than the threshold length tH, the threshold comparator will unlock 685 the coding element 575 that in the step 640 the root block is encoded, and then the magnitude comparator compares 680 in step 650 the lengths of the intracode and the intercode. After the comparison in the step 650 is in the step 630 respectively. 660 the shortest used by intracode and intercode.

If the intercode is shorter than the threshold length tH, the coding element becomes 575 locked, and the size comparator 680 automatically generates a control bit to indicate that the block is inter-coded. multiplexer 590 selects the intercode and the coding of the block is completed without ever calculating the intracode for the block. In an embodiment where the coding elements 570 and 575 operating sequentially, omitting the intra-coding for already intra-coded blocks increases the coding speed of the video encoder 670 relative to the video encoder 550 ,

The complexity (ie the required number of calculations) for the coding process 600 depends on the number of root blocks for which both intercoding 610 as well as intra coding 640 be executed. Threshold length tH controls the complexity of the video encoder 670 and can be set in a software encoder to be applied in a plurality of different platforms with different sizes of available computing power and transmission bandwidth.

7 shows a record 710 the percentage of intercodes longer than the threshold length tH. At one extreme, the threshold length tH is zero, so that 100% of the inter-codes are longer than the threshold tH, and a video encoder determines that an inter-code and an intra-code are formed for each root block. This threshold length tH is useful for software encoders running on platforms employing high performance processors and operate with low-bandwidth transmission channels, such as a high-performance workstation connected to traditional telephone lines and executing software videophone applications. In the other extreme case, the threshold tH is very large, and the video encoder 670 interprets only root blocks of intermediate images. This is best for a computer that is not powerful, but is connected to a high-bandwidth transmission channel such as the IsoEthernet. In different systems, the threshold length tH can be preset, depending on the capabilities of the video encoder, the encoding method 600 performs.

The record 720 in 7 shows a percentage indicating how large the ratio of the number of intra codes from the video coder 670 to the number of intracodes from the video encoder 550 is. If the threshold length tH is zero, the video encoder determines 670 an intracode and an intercode for each root block, and is able to find all the shorter intracodes that come from the video encoder 550 being found. As the threshold length tH is increased, the video encoder computes 670 no intra-code for each block, and the video encoder 670 provides less compression than the video encoder 550 because video coders 670 calculated some of the shorter intra codes. The record 730 shows the percentage of compression improvement achieved by the video encoder 550 that too from the video encoder 670 is reached. The record 710 is concave while the records 720 and 730 are convex. Accordingly, a threshold length tH0 that causes very little loss of compression eliminates the intra-coding of many blocks.

In most video conferencing systems, the balance between the computational power and the available bandwidth for video data changes, and no threshold length tH always matches such systems. According to one aspect of the invention, shown in FIG 8th , checks a feedback path 800 periodically in step 810 the processor and the bandwidth used and then regulates in step 820 or 830 the threshold length tH, the coding method 600 is used to operate at optimal computational power that balances processor and bandwidth loads. The feedback path 800 can be executed once before each root block is encoded when the encoding process 600 is applied. Alternatively, the feedback path becomes 800 at regular time intervals or at other intervals once per frame data.

To check for bandwidth bottlenecks, the video encoder may check the amount of data stored in a video data buffer to determine if the bandwidth of the transmission channel is sufficient to transmit the compressed data as generated. When the video data buffer is almost full, the threshold length tH in step 830 lowered to increase computing power and compression. Alternatively, if the video data buffer has room for more data and the processor utilization is high, the threshold length tH is increased to reduce the computational power.

Some processors have a utilization index stored in a register for indicating the processor utilization level. Such utilization indices, if available, can be read directly when in step 810 looking for bottlenecks. Alternatively, operating systems such as Windows NT and Windows 95 have user-accessible registers that indicate the degree of utilization of the processor.

For older systems, where the degree of processor utilization is difficult to determine, the method can 800 check only the transmission buffer to compare the coding rate with the transmission rate. If the coding rate is higher (ie the transmit buffer is nearly full), the computational power is increased to select an optimal computing power for the available transmission rate. If the coding rate is lower (ie, the transmit buffer is empty), the computational power is reduced to maximize the use of available bandwidth or to achieve the possible minimum computational power for the encoding process.

Changing the threshold length tH does not change the format of the resulting intercode or the quality of the image achieved by a code. Accordingly, the threshold length tH is irrelevant to a decoder and need not be transmitted. Changing the threshold length tH only makes a tradeoff between the compression (the number of bits in the code) and the computational power (or the number of computations needed for encoding). Changing the computational power of a coding method without changing the code format or the picture quality is achieved by other than changing the threshold length tH, which determines whether intra-coding should be attempted. For example, determines the size of a search window in the motion estimation influencing the Kodierrechenaufwandes. A large search window contains more points to examine and therefore requires more calculations. Alternatively, motion estimation methods may switch between searching each point in a search window for a hierarchical search technique that examines only selected points in the search window. Generally, more search points increase the chance of finding the best predictive block and improving the compression at the expense of extra computation. Changing the procedure or the amount of searching for a predictive block during motion estimation does not change the format of the codes or the quality of the picture.

If further compression enhancement is needed, image quality can be sacrificed to reduce the bit rate. For example, the quantization step sizes may be increased to reduce the average number of bits per frame. 9 Figure 3 shows a three-dimensional graph showing the computational effort, the average number of bits per frame and the peak signal-to-noise ratio (PSNR) for the encoding method described above 600 relates. A software encoder may adjust the parameters of the encoding process to maintain computational effort, bit rate, image quality, or a combination of these three depending on the application of the encoder.

curves 910 and 915 are curves of constant computational effort. Curve 910 is the maximum computation required when the threshold tH is zero. The line 915 shows minimal computational effort that occurs when the threshold length tH is high. A desired bit rate and PSNR can be achieved by reasonable choice of computational effort, provided that the desired bit rate and PSNR are within the range of the surface boundary through the curves 910 and 915 lie. Once the curve 910 maximum computational effort is achieved, PSNR can be lowered to achieve the desired bit rate. The computational effort within the range, that of the maximum curve and the minimum curve of the lines 910 respectively. 915 can be selected and maintained by adjusting the bit rate and / or the PSNR. The curves 920 . 922 . 924 and 926 show how the computational effort and / or bitrate change for a constant image quality (PSNR), and the curves 930 . 932 . 934 and 936 show how the computational effort and / or quality changed for a constant bit rate. In accordance with one aspect of the invention, the coding computational effort adds an additional degree of freedom that is adjustable to achieve the goals of the limitations of a video encoder.

Claims (5)

Method for coding an image, in which a uniform Subdivision of a first matrix, the first color components of Contains pixels in the picture, is merged according to a first merger rule, to create a first quad branching structure a second Matrix, which contains second color components of the pixels in the image, into one first subdivision associated with the first quad branching structure is divided, blocks in the first subdivision of the second matrix corresponding to one second merger rule together to create a second subdivision of the second matrix, which is associated with a second Quadverzweigungsstruktur, the one by removing branches the first Quadverzweigungsstruktur resulting sub-tree of the first Quad branching structure is, and a code is generated that the second quad branching structure, second color components for each Block in the second subdivision of the second matrix, the of the first Quadverzweigungsstruktur distant branches and first color components for each Block associated in one of the first quad branching structure Subdivision represents. The method of claim 1, wherein blocks corresponding the first and second merger regulations only then merged if this causes the error per pixel to be less than a threshold increases. The method of claim 1, wherein a third Matrix, which contains third color components of the pixels in the image, into one subdivided into the second quad branching structure, Blocks in the Subdivision of the third matrix according to a third merger rule together to be assigned to a third quad branching structure Subdivision to create one by removing branches of the second Quad branching structure resulting sub-tree of the second Quadverzweigungsstruktur is, in which the code represents the second quad branching structure, by the third Quadverzweigungsstruktur and that of the second Quad branching structure represents distant branches. The method of claim 3, wherein corresponding the first merger rule a decision, whether blocks together based on the first color components of pixels in the image without consideration the second and third color components are hit, corresponding the second merger rule a decision, whether blocks together based on the second color components of pixels in the image without consideration the first and third color components are taken, and corresponding the third merger rule a decision, whether blocks together based on the third color components of pixels in the image without consideration the first and second color components are hit. The method of claim 1, wherein corresponding the first merger rule a decision, whether blocks together based on the first color components of pixels in the image without consideration the second color component is hit, and corresponding the second merger rule a decision, whether blocks together based on the second color components of pixels in the image without consideration the first color component is hit.