Pixel prediction for video coding

A method of encoding an input video frame into an encoded video frame comprises the steps of disassembling the input video frame into a plurality of blocks of pixels. For each block being a current block, the method further comprises generating a corresponding predicted block from already reconstructed pixels, generating a residual block by subtracting the predicted block from the current block, generating a reconstructed block from the residual block and the predicted block, and generating the encoded video frame from the residual block The method further entails creating a local structure of reconstructed pixels in a region of the predicted block and aligning the predicted block with the local structure to produce an aligned predicted block, wherein the aligned predicted block is used in the steps of generating the residual block and generating the corresponding reconstructed block.

FIELD OF THE INVENTION

The invention relates to a method of encoding a video frame into an encoded video frame, a method of video decoding, a video encoding apparatus, a video decoding apparatus, a computer readable medium with a computer program for a video encoding apparatus and a computer readable medium with a computer program for a video decoding apparatus. The invention more specifically relates to video encoding and video decoding having block prediction.

BACKGROUND

In video encoding/decoding an input video frame is encoded into an encoded video frame for storage or transmission, which encoded video frame is decoded in order to obtain a reconstruction of the original video signal. The encoding enables compression of the original video signal allowing that the compressed video signal can be stored on a storage medium requiring storage capacity which is only a small fraction of storage capacity that would be needed if the original video signal would be stored or transmission to another device requiring much less bandwidth, i.e. bits to be transmitted, compared to the bandwidth needed to transmit the original video signal.

In the art of video coding (H.264 [7] which is hereby incorporated by reference, H.263, MPEG2, MPEG4) the encoder performs all steps and makes all decisions necessary to compress the input video signal. All decisions taken by the encoder with respect to the encoding process are subsequently transmitted or stored for receipt or retrieval by the decoder and subsequently used in the decompression process. The decoder is passive in this respect and does not make any decisions on its own, operates dependently on the encoder. In recent contributions to Video Coding Expert Group (VCEG) of the International Telecommunication Union (ITU) adaptive filters have been proposed [1,2]. These filters are optimized on a frame by frame basis and coefficients are coded. They provide better coding efficiency than filters used in video compression standard H.264 for example.

Also there has been work on giving the decoder more freedom using template matching [3, 4, 5, 6], wherein the template refers to a region of previously decoded pixels adjacent to the block to be coded. All this has been attempted in an urge to further improve video encoding/decoding to achieve yet higher compression rates and/or improved perceived reconstructed image quality. In an attempt to further improve prediction, solutions have been investigated for adaptation of a prediction on a local basis.

Adaptation of a prediction on a local basis however costs many bits and can not be afforded for efficient video coding, where a more local adaptation potentially could reduce the prediction error. Local adaptive filters for inter-frame prediction could achieve this object, but are difficult to implement due the cost of coding filter coefficient and will cost many bits in storage or transmission.

Template matching is one way to achieve more local adaptation of a prediction without side information but in the matching search an area outside the predicted block is used. In other words the template matching search is based on reconstructed pixels other than the ones used for the actual prediction according to the best match. Errors in previously decoded regions due to communication channel errors or coding errors can propagate to the predicted block without any adjustments. It is therefore an object of the invention to enhance accuracy of predictions, i.e. predicted blocks, while preserving or limited increase of bandwidth, i.e. required bit capacity or bits to be encoded.

SUMMARY

The object is achieved according to a first aspect of the invention in a method of encoding an input video frame into an encoded video frame. The method comprises the steps of:disassembling the input video frame into a plurality of blocks of pixels; and for each block being a current block, performing the steps of:generating a corresponding predicted block from already reconstructed pixels;generating a residual block by subtracting the predicted block from the current block; andgenerating a reconstructed block from the residual block and the predicted block;generating the encoded video frame from the residual block; the method further comprising the steps of:creating a local structure of reconstructed pixels in a region of the predicted block; andaligning the predicted block with the local structure to produce an aligned predicted block; andwherein the aligned predicted block is used in the steps of generating the residual block and generating the corresponding reconstructed block.

The object is also achieved according to a second aspect of the invention in a method of decoding an encoded video frame into an decoded video frame. The method according to the second aspect of the invention comprises the steps of:generating an inverse transformed/dequantized residual block from the encoded video frame;
for each generated inverse transformed/dequantized residual block performing the steps of:generating a predicted block from already reconstructed pixels;generating a reconstructed frame from the encoded video frame and the predicted block;
the method further comprising the steps ofcreating a local structure of reconstructed pixels in a region of the predicted block;aligning the predicted block with the local structure into an aligned predicted block; andwherein the aligned predicted block is used in the step of generating the corresponding reconstructed block.

By creating a local structure of reconstructed pixels in a region of the predicted block, a synthetic original is created with which the predicted block can be aligned where no previously reconstructed pixels are yet available. Pixels in the local structure are within the region of the predicted block and not outside as in template matching. The local structure of reconstructed pixels is derived or extended from previously reconstructed pixels, thus information from previously reconstructed pixels can be used more efficiently. The creation of a local structure of reconstructed pixels and subsequent alignment of the predicted block allows improved prediction of predicted blocks. Since the creation of local structure and alignment may take place within the encoding and decoding independently, no further bit capacity, i.e. bits to be coded, is required, from the encoding process to the decoding process or from the encoder to the decoder. Thus a further improvement in either reduced bit capacity for the encoded video frame or improved perceived reconstructed video quality is achieved.

The deployment of a local structure, i.e. a synthetic original, enables local modification of a predicted block on a region-by-region basis. Since a predicted block can be aligned with previously reconstructed pixels adjacent to the predicted block better robustness in the encoding and decoding and more particularly to communication channel errors is achieved. The use of an in-loop de-blocking filter as in H.264 can be reduced due to a better match between a prediction and previously reconstructed pixels in the local structure.

In an embodiment according to the invention, the step of generating a predicted block comprises generating a predicted block from reconstructed pixels in a previously reconstructed frame using inter-frame prediction information.

In another embodiment according to the invention, the step of generating a predicted block comprises generating a predicted block from reconstructed pixels in the current reconstructed frame using intra-frame prediction information. Thus the invention can be applied to both inter and intra-frame predicted blocks.

According to another embodiment of the invention the step of creating a local structure of reconstructed pixels in a region of the predicted block comprises generating pixels of the local structure using reconstructed pixels from the current reconstructed frame (intra-frame prediction).

This is similar to intra-frame prediction, which can be advantageously used to spatially extend known patterns and texture into the local structure.

According to another embodiment of the invention the step of creating a local structure of reconstructed pixels in a region of the predicted block comprises generating pixels of the local structure using previously reconstructed pixels from a previously reconstructed frame. This is similar to inter-frame prediction, whereby reconstructed pixels extend in temporal sense into the local structure. Temporal and spatial extensions however may also be combined to create a local structure.

Essentially according to the invention any prediction block, inter-frame or intra-frame, can be aligned to a local structure which may be created from any other method of generating a prediction either from a current reconstructed frame or a previously reconstructed frame.

According to another embodiment of the invention the step of creating a local structure of reconstructed pixels in a region of the predicted block comprises interpolating reconstructed pixels of the current reconstructed frame or the previously reconstructed frame into the region of the predicted block.

Reconstructed pixels surrounding the region of the predicted block from the current reconstructed frame can be used to interpolate not yet reconstructed pixels by linear or polynomial interpolation as an alternative method of intra-frame prediction to create the local structure. Alternatively, reconstructed pixels in a previously reconstructed frame can be interpolated as well to create the local structure.

According to another embodiment of the invention the step of creating a local structure of reconstructed pixels in a region of the predicted block comprises generating pixels of the local structure by extrapolating reconstructed pixels into a region of the predicted block.

Pixels from the current reconstructed frame or previously reconstructed frame or previously reconstructed frames can thus be extrapolated. This has the effect of extending the local structure to the pixel positions of the predicted block to enable an improved alignment of the predicted block to the local structure.

According to another embodiment of the invention the step of creating a local structure of reconstructed pixels in a region of the predicted block comprises applying reconstructed pixels from another previously reconstructed frame according to inter-frame prediction information of a neighbouring block into the region of the current reconstructed frame. This has the effect of extending the local structure of a neighbouring block to enable an improved alignment of a predicted block to the local structure.

Any method of performing creating a local structure of reconstructed pixels can be combined with at least one other method of performing creating a local structure of reconstructed pixels for example by interpolating between pixel values, or spatial interpolation between the pixels of the respective methods. This has the advantage that accuracy can be further enhanced using a plurality of approaches.

According to another embodiment of the invention the step of creating a local structure of reconstructed pixels in a region of the predicted block comprises determining a transfer function for predicting a row and/or column of the predicted block. The transfer function may be determined from pixels of at least one row and/or column of pixels to at least one next row and or column of reconstructed pixels adjacent to the predicted block.

By applying the transfer function to reconstructed pixels adjacent to the region of the block to be predicted to predict not yet reconstructed pixels in the region of the predicted block may be predicted. This has the effect of modelling how the local structure varies from one row to another row or from one column to another column. Thus the local structure can be extended to a region of a predicted block and enable improved alignment of a predicted block to the local structure. The transfer function may have temporal and spatial properties.

According to another embodiment of the invention the step of aligning the predicted block with the local structure comprises matching properties of pixels of at least part of the predicted block with corresponding properties of pixels of the local structure, and adapting the properties of the predicted block to the corresponding properties of the local structure based on the best match.

This has the effect of determining alignment of the predicted block based on the parts of local structure allowing improvement of the visual quality of the aligned predicted block and reducing residual error using the aligned predicted block in combination with residual coding. Alignment can thus be interpreted broadly as being brought into correspondence and is not limited to a position of the predicted block with respect to the local structure, but any property relating to the pixels in the predicted block and local structure may be aligned, such as and not limited to luminance, chrominance, texture, and also spectral content, phase relationship.

According to another embodiment of the invention the step of matching properties of pixels of at least part of the predicted block with corresponding properties of pixels of the local structure comprises establishing a sum of squared differences or of absolute differences of the value of properties of pixels of at least part of the predicted block and the value of the corresponding properties of pixels of the local structure, and wherein the best match is determined by the lowest sum.

This has the effect that a variety matches may be evaluated, wherein the one that gives least difference is selected.

According to a another embodiment of the invention the step of matching properties of pixels of at least part of the predicted block with corresponding properties of pixels of the local structure comprises determining a spatial transfer function between at least part of the predicted block and the local structure and the step of adapting the properties of the predicted block to the corresponding properties of the local structure based on the best match comprises applying the spatial transfer function to the predicted block to obtain an aligned predicted block.

This has the effect of establishing a modification for modifying the predicted block and applying the modification to get similar characteristics as the local structure. Some examples of characteristics are displacement, but also texture, smoothness/sharpness. It can be noted that the reconstructed pixels that are used for the generation of the predicted block can be used directly in the step of producing an aligned predicted block according to the invention.

According to another embodiment of the invention, the step of determining a spatial transfer function between part of the predicted block and the local structure is performed by selecting a spatial transfer function from a set of predetermined spatial transfer functions.

This has the advantage that a spatial transfer function may be selected from for example transfer functions already present according to H.264 [7] standard. By selecting a transfer function from a set instead of calculating coefficients, computation time may be saved.

According to another embodiment of the invention the step of aligning the predicted block on the location of the best match comprises sub-pel interpolating pixels of the predicted block or of the local structure to allow sub-pel matching and positioning of the predicted block with respect of the local structure.

This has the effect of further fine tuning the aligning of the predicted block with the local structure, for example by displacement of the predicted block vertically and horizontally or rotating the predicted block, to get a better match with the characteristics of the local structure.

According to another embodiment of the invention, the step of matching properties of pixels of at least part of the predicted block with corresponding properties of pixels of the local structure and the step of adapting the properties of the predicted block to the corresponding properties of the local structure based on the best match is performed on pixels originating the predicted block.

This has the advantage that the predicted block is aligned in a single step of computing without actually generating the predicted block, saving computation time.

According to another embodiment of the invention, the properties of pixels of at least part of the predicted block and corresponding properties of pixels of the local structure are based upon a transform of pixels of the local structure, and wherein the predicted block is adapted according to the transform of pixels of the local structure on the basis of the best match.

This has the effect of enabling alignment according to for example frequency domain, for example emphasizing high frequency features such as edges, phase domain features, for example a line representation in the phase domain, or visual error.

According to another embodiment of the invention, the step of matching properties of pixels of at least part of the predicted block with corresponding properties of pixels of the local structure comprises determining a position best matching pixel values of the predicted block with pixel values of the local structure of reconstructed pixels, and wherein the step of adapting the properties of the predicted block to the corresponding properties of the local structure comprises positioning the predicted block to the position best matching pixel values of the predicted block with pixel values of the local structure of reconstructed pixels.

This allows accurate positioning of a predicted block with respect to a local structure.

The object of the invention is also achieved in a third aspect of the invention in a video encoding apparatus comprising an input interface for receiving an input video frame, an output interface for outputting an encoded video frame and processing means and a memory and/or dedicated hardware means, arranged for performing the steps of the above described method and embodiments.

The object of the invention is also achieved in a fourth aspect of the invention in a video decoding apparatus comprising an input interface for receiving an encoded video frame, an output interface for outputting a decoded video frame, and processing means and a memory and/or dedicated hardware means arranged for performing the steps of the above described method and associated embodiments.

The object of the invention is also achieved in a fifth aspect of the invention in computer readable medium having stored thereon computer instructions which, when loaded into the memory and processed by the processor of the above mentioned encoding apparatus, perform the steps of the above described method and associated embodiments.

The object of the invention is also achieved in a sixth aspect of the invention in computer readable medium having stored thereon computer instructions which, when loaded into the memory and processed by the processor of the above mentioned decoding apparatus, perform the steps of the above described method and associated embodiments.

DETAILED DESCRIPTION OF THE INVENTION

The invention will be explained in detail below by exemplary embodiments and will be better understood if read with reference to the accompanying figures. Through the figures each block represents a processing step having data and/or control information as input and/or output. Data are represented by solid arrows and can be a block or a frame of pixels. Control information is represented by dashed arrows. Through the figures like reference numerals are used for like features.

Each of the blocks in the figures may however be implemented in dedicated hardware processors. Likewise data and control information may be implemented in hardware as electronic signals, used for communicating between and controlling the various hardware processors respectively.

The general concept of video encoding is based upon a process or method of encoding an input video frame comprising the steps of disassembling input video frames into blocks of pixels of various sizes, e.g. 4×4, 8×8 or 16×16, whereby a difference or residual block is generated by subtracting a predicted block from a current block of the input video frame. The residual block is encoded into an encoded video frame. The residual block is used to create a reconstructed block from the predicted block and the residual block, which is assembled together with previously reconstructed blocks into a reconstructed frame from which the predicted block is generated.

By providing a decoding process or method generating a reconstructed frame the same way as in the encoding process, a reconstructed frame is generated in the decoding process, which may after some post-processing be output as a decoded video frame.

Since the encoding process and decoding process both produce a current reconstructed frame from which a predicted block is generated, it is possible for the decoding process to follow the encoding process and produce a decoded video frame resembling the original input video frame.

FIG. 1Ashows a block diagram of a process for encoding an input video frame47according to the state of the art (H.26x, MPEG2, MPEG4), wherein the input video frame47is disassembled46in a plurality of blocks1, whereby each disassembled block1is successively processed in a processing cycle. Current block1, one of the disassembled generated blocks from the input video frame47, is encoded into an encoded video frame18, which is to be transmitted to a decoding process as depicted inFIG. 1B. Thus input video frame47is blockwise encoded and transferred to a decoding process. It is clear that by consecutively encoding input video frames47, streaming video can be encoded into a continuous encoded video frame18. Intermediate storage can be performed between encoding and decoding in encoded form such as for example on a Compact Disc (CD) or Digital Versatile Disc (DVD) or any other storage medium.

InFIG. 1A, in a cycle of the encoding process, for a current block1, a predicted block9is used to generate a residual block3by subtracting2the predicted block9from the current block1. Subtracting2the predicted block9from the current block1may be performed by subtracting pixelvalues of pixels of the predicted block9from pixelvalues of corresponding pixels of the current block1.

The residual block3is optionally transformed/quantized4(optional blocks are indicated with dashed lines) into a transformed block6, which in turn is encoded5, to generate the encoded video frame18. The step of optionally transforming/quantizing4residual block3into a transformed block6may involve for example Discrete Cosine Transformation (DCT). The step of transforming4the residual block3may additionally involve quantization of the resulting transformed block to limit the number of possible values of the transformed residual block6. This will reduce the workload of the encoding step5. Encoding5may involve entropy coding, i.e. for example Huffman coding or any other coding scheme for reducing the amount of bits required for digital transmission.

The transformed block6is optionally inverse transformed and/or dequantized7into an inverse transformed/dequantized residual block25. The inverse transformed/dequantized residual block25, representing the residual block3, is then added8to the predicted block9to generate a reconstructed block43. This reconstructed block43is assembled44together with previously reconstructed blocks43to form at least part of a current reconstructed frame10, which can thus be used for intra-frame prediction in the next cycle. The current reconstructed frame10is stored to provide a previously reconstructed frame12. In the description below, it is assumed for completeness sake that the optional steps of transforming/quantizing4and inverse transforming7are in place.

The predicted block9is generated42A according to the state of the art by inter-frame prediction using the previously reconstructed frame12or by inter-frame prediction using the current reconstructed frame10.

Prediction control information45from the prediction generation step42A may be coded5along with the transformed residual block6to be included into the encoded video frame18. Examples of prediction control information45, but not limited to, are block partition information, motion vectors, reference frame numbers indicating from which previously reconstructed video frames12the predicted block9shall come from in the case of inter-frame prediction and block partition information and intra-frame prediction modes in the case of intra-frame prediction.

The current reconstructed frame10may be de-blocked11and stored to create the previously reconstructed frame12whereby block boundaries are filtered out such that they are no longer apparent for a viewer. It should be noted that variations are possible to this general approach.

FIG. 1Bshows a block diagram of a process for decoding an encoded video frame18into an decoded video frame29according to the state of the art.

The decoding process is shown from right to left inFIG. 1B. The encoded video frame18is first decoded19and inverse transformed7into an inverse transformed/dequantized residual block25. A predicted block9is added8to the inverse transformed/dequantized residual block25to generate a reconstructed block43. Adding9may be performed by adding pixel values of pixels of the predicted block the inverse transformed/dequantized residual block25to pixel values of pixels of the predicted block9. The reconstructed block43is assembled44together with previously reconstructed blocks43to form a current reconstructed frame10. The current reconstructed frame10is further stored to provide a previously reconstructed frame12.

As inFIG. 1A, the current reconstructed frame10may be de-blocked11and stored to create the previously reconstructed frame12whereby block boundaries are filtered out such that they are no longer apparent for a viewer, thus producing the resulting decoded video frame29, which can for example be forwarded to a display for viewing.

The predicted block9is generated42B according to the state of the art by inter-frame prediction using the previously reconstructed frame12or by inter-frame prediction using the current reconstructed frame10. Prediction control information45from the prediction generation step42A in the encoding process may be decoded19along with the encoded transformed residual block6to be used in the predicted block generation42B.

The process of decoding the encoded video frame18is similar to the encoding process in that both the encoding process and the decoding process need to generate a current reconstructed frame10and a previously reconstructed frame12from which a predicted block9is to be generated either by inter-frame prediction or by intra-frame prediction. It must be ensured that for each corresponding cycle in the encoding process ofFIG. 1Aand the decoding process ofFIG. 1Bthe predicted blocks9are identical. If the predicted block generation42A/42B of the encoding and decoding processes respectively were different, the resulting decoded video frame29would not be an accurate representation of the input video frame47.

FIG. 2Ashows an example of predicted block generation42A in the encoding process according to the state of the art. Inter-frame prediction and intra-frame prediction can both be performed. In inter-frame prediction motion estimation13is performed of the current block with respect to the previously reconstructed frame12. The result of motion estimation13, inter-frame prediction information23, can be a motion vector and an indication which block from the previously stored frame12is used. An inter-frame predicted block31can be generated by means of inter-frame prediction compensation14using the previously reconstructed frame12and the inter-frame prediction information23.

In intra-frame prediction, an intra-frame prediction mode can be determined in step15by comparing the current block1to already reconstructed pixels in the current reconstructed frame10. The intra prediction mode together with an indication which block is to be used for intra-frame prediction form intra-frame prediction information24. An intra-frame predicted block32can be generated based upon the current reconstructed frame10and intra-frame prediction information24by performing the step of intra-frame prediction generation16.

The best matching prediction is selected in a selection step17A for further processing resulting in the predicted block9and corresponding prediction information45.

InFIG. 2Ban example of prediction generation42B is shown for the decoding process. Depending on the decoded prediction information45the selection step17B selects the prediction established in the predicted block generation42A ofFIG. 2A. Either inter-frame prediction is selected, wherein motion compensation14is performed using motion prediction information23generating an inter-frame predicted block31using a previously reconstructed frame12or intra-frame prediction is selected, wherein intra-frame prediction information24is provided to perform intra-frame predicted block generation16, generating an intra-frame predicted block32based on the intra-frame prediction information24and the current reconstructed frame10. The resulting predicted block9is used in the decoding process ofFIG. 1B.

FIG. 3Ashows a block diagram of a process for decoding an input video frame47into an encoded video frame18according to an embodiment of the invention. The process ofFIG. 3Ais similar to the process ofFIG. 1Ain that for each current block1, a predicted block9and according to the invention an aligned block22is used to generate a residual block3by pixelwise subtracting2the aligned predicted block22from the current block1. The residual block3is transformed4into a transformed block6, which in turn is encoded5, to generate the encoded video frame18. The step of transforming4residual block3into a transformed block6may involve for example Discrete Cosine Transform (DCT) and/or quantisation of the resulting transform to limit the number of possible values of the transformed residual blocks. This will reduce the workload of the encoding step5. Encoding5may involve entropy coding, i.e. for example Huffman coding or any other coding scheme for reducing the amount of bits required for digital transmission.

The transformed block6is inverse transformed7into an inverse transformed/dequantized residual block25. The inverse transformed/dequantized residual block25, representing the residual block3, is then added8to the aligned predicted block22to generate a reconstructed block43. This reconstructed block43is assembled44together with previously reconstructed blocks43to form at least part of a current reconstructed frame10, which can thus be used for intra-frame prediction in the next cycle. The current reconstructed frame10is stored to provide a previously reconstructed frame12.

The aligned predicted block22is an improved version of predicted block9. Predicted block9is generated according to the state of the art by performing predicted block generation42A, further detailed inFIG. 2A. However according to the invention this predicted block9is aligned21with a local structure of reconstructed pixels30, resulting in aligned predicted block22.

According to the invention, a step of creating20of a local structure of reconstructed pixels30is performed in a region of the predicted block9, where not yet reconstructed pixels in the current reconstructed frame are to be created. The purpose of the local structure of reconstructed pixels30is to create an as good as possible representation of the pixel values in at least some aspect or in at least part of the region of the predicted block9.

The region of not yet reconstructed pixels overlaps with predicted block9using reconstructed pixels from the current reconstructed frame10and/or from a previously reconstructed frame12, meaning that generally the local structure of reconstructed pixels30may extend beyond the limits of the predicted block9. Some examples of creating20a local structure of reconstructed pixels30will be detailed further below.

The predicted block9is aligned with the local structure of reconstructed pixels30in the step of alignment21resulting in an aligned predicted block22. This enables a fine tuning of the predicted block9. It is this aligned predicted block22which is then subsequently used in the step of generating the residual block3by subtracting2the aligned predicted block22from the current block1. It will be clear that since the aligned predicted block22is fine tuned to the local structure of reconstructed pixels30, the resulting reconstructed block43and subsequent resulting current reconstructed frame10and the ultimately resulting de-blocked decoded video frame29are of better quality than according to the state of the art.

FIG. 3Bshows a block diagram of a process for decoding an encoded video frame into a reconstructed video signal according to an embodiment of the invention. The step of generating42B a predicted block9is performed similar to the state of the art as described inFIG. 1B. Furthermore, similar to the encoding process according to the invention shown inFIG. 3A, a local structure of reconstructed pixels30is created20in a region corresponding to the predicted block9. The predicted block9can then be aligned21with the local structure of reconstructed pixels30to generate the aligned predicted block22. The step of generating the reconstructed block43is then performed by the adder8in pixelwise adding an inverse transformed/quantized residual block25to the aligned predicted block22and assembling44the thus formed reconstructed block43to the current reconstructed frame10. The inverse transformed/dequantized residual block25in turn has been generated by decoding the encoded video frame18as inFIG. 1B.

In a further improvement of the invention the step of creating20a local structure of reconstructed pixels30and/or the step of aligning21a predicted block9to the local structure of reconstructed pixels30in the process of encoding a not shown input video frame47as discussed above may signal creation information and alignment information together with prediction information to the corresponding decoding process as discussed above and illustrated inFIG. 3B. In this way the encoder can select for which blocks the creating20a local structure of reconstructed pixels30and alignment21according to the invention shall be used. Also the corresponding decoding process can be informed beforehand how the creating20a local structure of reconstructed pixels30can be performed and how the predicted block9is alignment21is to be performed according to the invention by incorporating corresponding instructions in the creation information and alignment information respectively. This can limit the amount of work for the decoding process and also give some further guidance for the decoding process to best create a local structure of reconstructed pixels30and/or to know where alignment21is best applied. Some additional bits may be required in the encoding step5to generate the encoded video frame18, but the quality of the current reconstructed frame10is improved.

FIG. 4Ashows an example of a predicted block9to be fitted into a current reconstructed frame10according to the state of the art. The predicted block9may be generated42A or42B by inter- or intra-frame prediction. FromFIG. 3Ait is clear that the predicted block9does not quite fit in with the surrounding pixels of the current reconstructed frame10.

FIG. 4Bshows an example of creating20a local structure of reconstructed pixels30using pixels from the current reconstructed frame10according to an embodiment of the invention. The local structure of reconstructed pixels30in this example may be based upon extending features from already reconstructed pixels in the current reconstructed frame10, for example by means of intra-frame prediction.

FIG. 4Cshows the predicted block9ofFIG. 3Aaligned21with the local structure of reconstructed pixels30ofFIG. 3Bresulting in an aligned predicted block22according to an embodiment of the invention. The predicted block9was positioned according to a best match with corresponding pixels of the local structure of reconstructed pixels30fromFIG. 3B.

In the sections below embodiments of creating20a local structure of reconstructed pixels and alignment22will be discussed in more detail.

Spatial Transfer Functions

In creating20a local structure of reconstructed pixels30and in the step of aligning the predicted block to the local structure of reconstructed pixels30, spatial transfer functions are used providing for a mathematical model.

In the art of inter-frame prediction and also intra-frame prediction a spatial transfer function can be applied on pixels of a reference frame such as the current reconstructed frame10or previously reconstructed frame12in order to obtain a predicted block9. The aim of the spatial transfer function is to re-position pixels of the reference frame according to prediction information from the reference frame to the pixel positions of current block1. In Equation 1 the general case of applying a two dimensional spatial transfer function is described:

The reference frame may be the current reconstructed frame10in the case of intra-frame prediction or the previously reconstructed frame12in the case of inter-frame prediction, whereas the prediction information is intra-frame prediction information24and inter-frame prediction information23respectively.

The use of spatial transfer functions is known from [7], wherein a set of spatial transfer functions relating to displacement of pixels has been defined. Two examples of spatial transfer functions are shown below. In Equation 2 a transfer function that re-positions pixel values to a regular spaced grid by bi-linear interpolation from positions exactly half way from the grid points in both the vertical and the horizontal direction is shown.

f=[0.250.250.250.25](Eq.⁢2)
In Equation 3 a transfer function that filters pixel values without re-positioning is shown.

Frame adaptive transfer functions have also been deployed in the art, see reference [1,2]. In this case a frame adaptive spatial transfer function is determined for different categories of re-positioning according to prediction information45. An adaptive spatial transfer function is a spatial transfer function having modifiable coefficients. By modifying the coefficients of the adaptive spatial transfer function the resulting pixels can be matched with already reconstructed pixels in the previously reconstructed frame12as reference pixels. The adaptive transfer function for each category that minimizes the squared error between predicted block9and current block of the current input frame47is selected by the encoding process, e.g. by means of least square minimization. The determined frame adaptive transfer function is encoded and selectively used to produce predicted block9. The encoded adaptive spatial transfer function may then be decoded19and used by the decoding process.

Creating a Local Structure of Reconstructed Pixels

Below some exemplary embodiments of creating20a local structure of reconstructed pixels30will be discussed. According to an embodiment of the invention creating20a local structure of reconstructed pixels30can be performed using prediction techniques, i.e. inter-frame prediction and/or intra-frame prediction, similar to generating42A/42B a predicted block9.

Generally creating20a local structure of reconstructed pixels30is performed according to a different scheme for generating42A/42B the predicted block9, so that in the alignment step21of the predicted block9is performed on a local structure of reconstructed pixels30which have been created20differently from the pixels of the predicted block9itself. Thus a predicted block9generated by inter-frame prediction may be aligned21with a local structure of reconstructed pixels30created by intra-frame prediction techniques or vice versa, a predicted block9generated by intra-frame prediction techniques may be combined with a local structure of reconstructed pixels30using inter-frame prediction techniques, i.e. derived from a previously reconstructed frame12.

It is however also possible to both perform the step of creating20a local structure of reconstructed pixels30and predicted block generation42A/42B using both inter-frame prediction or using both intra-frame prediction, as long as the techniques used respectively are different.

Creating20a local structure of reconstructed pixels30can be performed in various ways. First creating20a local structure of reconstructed pixels30using pixel information from the current reconstructed frame10is discussed. As discussed above, the current reconstructed frame10is created by assembling reconstructed blocks43from the current and preceding processing cycles. The current reconstructed frame10thus contains previously reconstructed pixels which can be used to predict yet to be reconstructed pixels, similar to intra-frame prediction. In fact any method of intra-frame prediction can be used.

Pixels yet to be reconstructed, which will be forming the local structure of reconstructed pixels30, in the region of the predicted block can for example be created by extrapolating pixel values from one or more rows or columns of already reconstructed pixels in one or more reconstructed block43or from rows and/or columns of previously reconstructed pixels in one or more reconstructed block43outside the block to be generated.

To create20the local structure30in the region of the predicted block9a spatial transfer function for displacement (see Equation 2 using interpolation with pixel re-positioning or Equation 3 without pixel re-positioning) can be used. In this example pixel values from one column of already reconstructed pixels of the current reconstructed frame10are used to determine pixels in another column, e.g. the adjacent column which forms part of the local structure30, as shown in Equation 4:

In this way the local structure of reconstructed pixels30in a region of the predicted block9can be produced according to the nearby pixel values of the currently reconstructed frame10. In another embodiment the transfer function is applied on one row of pixels of the current reconstructed frame to produce another row in the local structure30and so forth.

In an embodiment a spatial transfer function is selected from a predetermined set of spatial transfer functions, that minimizes the squared error or the absolute error between the local structure and corresponding pixels of the current reconstructed frame10. Such a set a spatial transfer functions is well known for a person skilled in the art, but is not limited to, from [7], wherein spatial transfer functions relating to displacement of pixels have been defined. Particularly spatial transfer functions performing displacement in combination with sub-pel interpolation and/or different degrees of low pass filtering can be advantageously utilized according to this embodiment of the invention.

In another embodiment an adaptive transfer function is determined by least square minimization of the error function of Equation 5 below.

E=∑k=0K-1⁢(L⁡(k,l)-R⁡(k,l))2,(Eq.⁢5)
wherein E is the computed error and K is the number of pixel positions that are used in the minimization, R(k,l) represents pixels in the current reconstructed frame10. In this case the error function for column-wise transfer function is shown (k in the range of 0, . . . , K).

Equation can be used for selecting a spatial transfer function, by performing least squares minimization by evaluating the summed squared difference for a set of spatial transfer functions as available in for example H.264 [7].

Alternatively, by taking derivatives with respect to the coefficients of a single spatial transfer function and setting the result to zero, a set of linear equations are obtained, from which the coefficients of the alignment transfer function can be solved numerically.

By taking the derivatives with respect to the coefficients of the transfer function and setting the result to zero, a set of linear equations are obtained, from which the coefficients of the transfer function can be solved numerically.

By performing this optimisation for part of the already decoded pixels and testing it on another part closer to the block to be generated, the generated block of the local structure of reconstructed pixels30may be used depending on the test result. The robustness of the method can be increased by considering several reconstructed columns in the error function. Similarly a row-wise transfer function can be determined.

In another example creating20a local structure of reconstructed pixels30can also be performed by polynomial modelling of previously reconstructed pixels from the current reconstructed frame10. A polynomial model is a representation of pixel values in a region using basic spatial transfer functions that are constant for all pixel values in the region, and using polynomials up to a certain power of horizontal (x) and vertical (y) positions, see Equation 6. A polynomial model or any other smooth model can also be used in combination with a local extrapolation approach to enable a local structure of reconstructed pixels30to be created that also maintains strong edges and lines from the previously reconstructed pixels in current reconstructed frame10.

The local structure of reconstructed pixels can be represented below by a polynomial model of Equation 6:

L⁡(k,l)=∑p=0P-1⁢∑q=0Q-1⁢a⁡(q,p)⁢kq⁢lp(Eq.⁢6)
wherein L(k,l) is a pixel of the local structure30at row k and column l, a(q,p) is the value of respective polynomial coefficient, and P and Q is the order of the polynomial in respective direction. The polynomial coefficients can be determined on nearby pixels from the currently reconstructed frame10using least squares minimization, similar as shown in Equation 5.

The above approaches of creating20a local structure of reconstructed pixels30of extrapolation and polynomial modelling use already reconstructed pixels in the current reconstructed frame10. Alternatively it is also possible to perform creating20a local structure of reconstructed pixels30from pixels from one or more previously reconstructed frames12, similar to inter-frame prediction.

Creating20a local structure of reconstructed pixels30can be performed by inter-frame prediction using the inter-frame prediction information23or motion compensated block31(not shown inFIGS. 2A and 2B) corresponding to predicted block9.

Likewise, creating20a local structure of reconstructed pixels30can alternatively be performed by inter-frame prediction of the current predicted block using inter-frame prediction information of a neighbouring block.

Depending on the characteristics of the pixel variations it can be beneficial to use combinations of pixels from the current reconstructed frame10and from the previously reconstructed frame12, or simply switch between them when creating20a local structure of reconstructed pixels30. One example is to use the current reconstructed frame10when the Sum of Absolute Differences (SAD) between the pixels outside the current block in the current reconstructed frame10and the corresponding pixels in the previously reconstructed frame12is larger than the SAD between the predicted block9and the local structure of reconstructed pixels30generated from the current reconstructed frame10.

Furthermore regions that are difficult to predict, but which are important for alignment, may have coded residual side information added to the local structure30, to enable a better match with the original. This residual side information is generated in the encoding process and is coded for use in the decoding process.

Re-sampling or interpolation may be part of the creating20a local structure of reconstructed pixels30when the created local structure30does not completely match the underlying pixel grid. Interpolation and re-sampling resolves this mismatch, for example by means of bi-linear interpolation, well known in the art.

Alignment

Alignment21can be achieved according to an embodiment of the invention by positioning the predicted block9with respect to the local structure of reconstructed pixels30according to the location of the best match of pixels from the predicted block9and corresponding pixels from the local structure. Positioning may involve translation and/or rotation of the predicted block9in any direction with respect to the local structure of reconstructed pixels30. Below some exemplary embodiments of alignment21of a predicted block9will be discussed in order to achieve an aligned predicted block22.

According to an embodiment of the invention a spatial transfer function for pixel displacement from the above defined set (see [7]) is applied to align21a predicted block9with the local structure30. This is performed in both the encoder and the decoder so the selected alignment transfer function need not to be encoded in step5, however may be encoded5in order to speed up the process of decoding ofFIG. 3B.

In an embodiment of the invention the alignment transfer function is applied on a predicted block9as shown in Equation 7.

A⁡(k,l)=∑i=0N-1⁢∑j=0M-1⁢wa⁢a⁡(i,j)⁢P⁡(k-i+int⁡(N2),l-j+int⁡(M2))+oa,(Eq.⁢7)
wherein A(k,l) is a pixel at row k and column l of the aligned predicted block22, a(i,j) is a spatial alignment transfer function at position (i,j), wais an alignment scaling factor and oais an alignment offset. It can be noted that the predicted block9usually can be made somewhat larger than the current block1so that useful sample values are available for the transfer function coefficients when determining values near the border of the aligned predicted block22, depending on the size of the spatial transfer function a(i,j) N, M in any direction. One advantage of applying the alignment transfer function a(i,j) directly to the predicted block9is that in this way the alignment transfer function is independent of the method used for obtaining the predicted block9. This can for example be advantageous if the predicted block9is obtained by a non-linear transfer function.

In another embodiment of the invention an alignment transfer function as described above is applied directly to the reference frame, i.e. the current reconstructed frame12or the previously reconstructed frame10, instead of applying a transfer function to the reference frame to obtain the predicted block9and subsequently applying another transfer function for aligning to the local structure. An equation to this effect is shown below in Equation 8:

In another embodiment of the invention a transfer function ƒ(i,j) indicated by the prediction information45is used as a starting point and an alignment transfer function a(i,j) performs a refinement of the transfer function ƒ(i,j), as shown in Equation 9:

In the Equations 7 to 9 above the spatial support of the transfer function ƒ(i,j) and the alignment transfer function a(i,j) is the same. It can also be the case that the spatial support of the alignment transfer function a(i,j) is different from the spatial support of the transfer function ƒ(i,j). In other words the alignment transfer function a(i,j) can have a different number of coefficients than the number of coefficients for the transfer function ƒ(i,j).

In an embodiment of the invention different a set of predetermined alignment transfer functions is established, each having different properties with respect to transfer function properties such as lowpass or high pass and/or displacement. Each of the predetermined alignment transfer functions is tested and the one that gives a best match with the local structure30is selected for alignment21of the predicted block9.

In another embodiment of the invention an adaptive alignment transfer function is used. The alignment transfer function a(i,j) that gives an aligned predicted block22with best match with the local structure30is selected. The best match can be evaluated as the sum of squared differences (SSD) or sum of absolute differences (SAD) between the local structure30and corresponding pixels of the aligned predicted block22, where the best match is the transfer function with the lowest sum. The best match can also be weighted according to Fourier properties of the differences to for example punish low frequency differences which are more visible more than high frequency differences which are less visible.

Least square minimization between the aligned predicted block22and the local structure30is used as shown below.

E=∑k=0K-1⁢∑l=0L-1⁢(L⁡(k,l)-A⁡(k,l))2,(Eq.⁢10)
wherein L(k,l) is the value of the local structure at row k and column l, K and L specify a region used in the alignment within the local structure of reconstructed pixels30, A(k,l) is the resulting aligned predicted block22after applying a spatial transfer function as described above. K and L are usually equal or smaller than the size of the aligned predicted block22.

As in Equation 5, Equation 10 can be used for performing least squares minimization by evaluating the summed squared difference for a set of spatial transfer functions as available in for example H.264 [7].

Alternatively, by taking derivatives with respect to the coefficients of a single alignment transfer function and setting the result to zero, a set of linear equations are obtained, from which the coefficients of the alignment transfer function can be solved numerically. This is similar to what is done when finding optimal transfer functions in [1] but in this case by minimizing Equation 10.

It can be noted that the region used for the alignment can be irregular. The region may contain for example an edge along which predicted block9is to be aligned, so pixel values around the edge in the local structure30can be used.

When applying one of the above described spatial transfer functions, a mismatch may exist in gain and/or offset. In an embodiment according to the invention, a predicted block9may be also aligned to the local structure of reconstructed pixels30by rescaling and applying an offset to the predicted block9, using the Equations 8 or 9 above, wherein waand oadenote a scaling factor and offset for alignment21respectively.

Furthermore the spatial transfer function a(i,j), can be established on the basis of a transform of the predicted block9and a transform of corresponding pixels of the local structure of reconstructed pixels30. A transform may for example be obtained by means of Fourier transformation, whereby either the transformed phase diagram or the transformed amplitude diagram of (part of) a predicted block9is used for matching with a transform of the created local structure. This can be particularly useful for aligning an edge in the predicted block9with an edge in the local structure of reconstructed pixels30, whereby the phase diagram of a Fourier transformed image can be used to align the faces of the corresponding edges.

Another example of performing alignment21using transforms is matching using Fourier frequency content. A row in an initial predicted block9can be smoothed or sharpened to better match the Fourier frequency content of previously reconstructed pixels in the local structure of reconstructed pixels30. Smoothing can be considered as enhancing error resiliency when similarity between the local structure of reconstructed pixels30and the predicted block9is weak due to for example errors that may arise during transmission or storage and retrieval in the encoded video frame18.

Alignment21using pixel values of the predicted block9and alignment21using transformed pixels of the predicted block9may be used successively, wherein the alignment21of transformed pixels can be used to further refine a previous alignment.

Furthermore, alignment21can be performed by matching other properties associated with pixels in the predicted block9and pixels in the local structure of reconstructed pixels30. Examples of such properties are motion vectors, average pixel values (DC), chrominance, luminance, or any other function derived from or associated with pixel values.

Any method of creating20a local structure of reconstructed pixels30can be used in combination with any method of alignment21. During encoding/decoding an optimal approach for creating20a local structure of reconstructed pixels30and/or alignment21can be chosen. Pixel positions of the local structure of reconstructed pixels30with strong local image gradient may be more important in finding a best match with a row/column/part of the predicted block9than pixel positions with weak local gradient. Weak gradients may be coding noise. Such a region may be avoided. Thus pixels having a higher gradient value may be weighed more than pixels with a low gradient in establishing a match between pixels of the predicted block9with the local structure30.

Transfer functions may also be used in template matching according to the state of the art. In template matching the best transfer function is selected from a set of displacement transfer functions in both the encoder and decoder, see reference [3]. It uses the vertical and horizontal displacements vland vkfrom the prediction information45to select the area of interest for the search of the transfer function. Then it refines the initial displacement by testing small variations of full pixel displacements. The transfer function is determined by applying different re-positioning transfer functions on an area outside the area pointed out by the integer displacements int(vl) and int(vk) and select the one that gives least absolute error compared to the corresponding area outside the predicted block, e.g. the template. The selected displacement and transfer function are then used to produce predicted block9. Template matching conventionally according to the state of the art typically uses reconstructed pixels outside the region of the predicted block9. According to the invention template matching may be used in alignment according to an embodiment of the invention when the template matching is applied to the local structure of reconstructed pixels30.

EXAMPLES

Below some more examples of combinations of creating20a local structure of reconstructed pixels30and alignment21will be described.

Inter-Frame Prediction by Alignment to Pixels in Current Frame

This describes how an embodiment according the invention can be used for improving the inter-frame prediction of a H.264 like coder. To create a local structure of reconstructed pixels30according to the invention, inter-frame prediction information23which costs few bits to encode is selected, like for example the P16×16 macroblock type in H.264. The selected macroblock type is then used as in the standard to obtain a predicted block9. Then row-wise and column-wise analysis is performed to establish the local structure of reconstructed pixels30. The inter-frame predicted block9is then aligned21with the local structure of reconstructed pixels30.

The alignment transfer function that gives least SAD compared to the local structure of reconstructed pixels30is selected. Alignment21can be performed such that the predicted block9is filtered to obtain a good match. To improve the accuracy of the alignment21, individual 4×4 blocks of the 16×16 predicted block9can be tuned and coded block by block to generate up to 16 adjustments of the 16×16 macroblock. Rate distortion (RD) optimization can be performed to select which macroblock type to use, e.g. same as in the standard case, but in this applying the teachings of the invention to the standard P16×16 macroblock mode.

Inter-Frame Prediction by Alignment to a Prediction According to Neighbouring Inter-Frame Prediction Information

Creating20a local structure of reconstructed pixels30can be performed by applying inter-frame prediction information from a neighbouring block for inter-frame prediction of the current block1. The predicted block9of the current reconstructed frame10using the current inter-frame prediction information can then be aligned21to make a better match with the local structure of reconstructed pixels30, especially along the block border to the neighbouring block where the other inter-frame prediction information comes from.

Using the Local Structure as an Intra-Frame Prediction

An embodiment of the invention can be used for improving the intra-frame prediction of an H.26X-like encoder. In this case one of the intra-frame prediction information24, for example an Intra4×4 coding mode in H.264, has been modified to make a combination of two predictions. One of the predictions is the predicted block9according to standard intra-frame prediction information24and the other prediction is chosen to be the local structure of reconstructed pixels30. The two predictions are combined, i.e. the by aligning21the intra-frame prediction block9with the local structure of reconstructed pixels30by for example weighted averaging, to produce the aligned predicted block22.

Alternatively, a local structure of reconstructed pixels30can be created20by analysing previously reconstructed pixels in10, at least two rows and two columns above respectively to the left of the block to be predicted block9. A transfer function, i.e. spatial extrapolation function, for predicting a row below or a column to the left is determined. This can be done by minimization of the squared difference between the prediction of a row/column and the reconstructed values of the row/col. The local structure30is then generated by applying the selected transfer function on one row/column to obtain the next row/column and so on.

Rate distortion optimization can be performed to select which intra-frame prediction information24to use for each 4×4 block predicted block9, e.g. same as is typically done in the standard case, but in this case using the aligned predicted block22as one of the intra-frame prediction information24as described above. This means that the prediction that gives the best RD performance will be selected, which can be signalled24to the decoding process.

Intra-Frame Prediction by Alignment to an Inter-Frame Prediction

Creating20a local structure of reconstructed pixels30can be performed by inter-frame prediction using the global inter-frame prediction information23such as global motion of the frame or the motion from neighbouring macroblocks. Then an intra-frame predicted block9can be aligned21with the created local structure of reconstructed pixels30to obtain an aligned predicted block22. Since the intra-frame prediction only is guided by the inter-frame prediction but the actual prediction is performed from previously decoded pixels in the current reconstructed frame10the aligned predicted block will potentially be better than the intra-frame prediction block9but still have good error resilience properties. Further improved error resilience can be achieved by avoiding aligning21of the intra-frame predicted block9if the block border pixels of the local structure of reconstructed pixels30are very different from the main structure of the intra-frame predicted block9.

Intra-Frame Prediction by Alignment with a Local Structure

In the step of generating a predicted block9, one or several intra-frame predictions can be generated by any user preferred method and the parameters for selection17of the method can be coded. The invention can then be used to align21one or several of those predictions to produce an aligned predicted block22which is better aligned with the local structure of reconstructed pixels30. Additional intra-frame prediction information24can also be added to describe how the aligned predicted block22is produced.

Use of Local Structure in Prediction Information Decision

A local structure of reconstructed pixels30is created20using either surrounding pixels in the current reconstructed frame10or pixels from previous frames12(using inter-frame prediction information from neighbouring blocks) for the whole or part of the current block1that is to be encoded. This local structure of reconstructed pixels30can then be used to perform intra-frame prediction information decision16and possibly inter-frame prediction information estimation13(based on for example rate-distortion optimization with respect to the local structure of reconstructed pixels30). Since the local structure of reconstructed pixels30is available in both the encoding process and the decoding process there is no need to encode/transmit the prediction information. Therefore bit rate savings can be achieved.

Improved Template Matching

A local structure of reconstructed pixels30can be used to improve template matching by switching between template matching and matching based on the local structure of reconstructed pixels30. Another approach is to constrain the template matching to predictions with similarity between the adjacent previously decoded pixels in10and the border pixels of the predicted block9. A prediction from a template matching approach can also be fine tuned according to a local structure of reconstructed pixels30to produce an aligned predicted block22.

Constrained Inter-Frame Prediction Information Estimation

A local structure of reconstructed pixels30can be used for inter-frame prediction information estimation in a standard encoding process. In this case the inter-frame prediction information estimation can be constrained to give a prediction with similarity between the adjacent previously decoded pixels in10and the border pixels of the predicted block9.

Mutual Alignment of Adjacent Blocks

In an embodiment the invention can be extended so that the alignment operation21is not only performed on the current block1that is to be encoded but also that it affects the pixels in a neighbouring block so that structures will be reconstructed smoothly across the block borders. Alignment21can be performed before or after the addition of the inverse transformed/dequantized residual block25.

Use of a Local Structure to Adjust Inter-Frame Prediction

In alignment21of a predicted block9with the local structure of reconstructed pixels30a transfer function can be determined to locally tune the transfer function used for inter-frame prediction.

FIG. 5Ashows a block diagram of an encoding apparatus according to an exemplary embodiment of the invention. An encoding apparatus generally comprises an input interface34for acquiring a input video frame12, a processing means35and a memory37and/or dedicated hardware for video encoding, and an output interface36for outputting an encoded video frame18.

The encoding apparatus can be comprised in, for example, a communication terminal such as a telephone or mobile phone or personal computer or any other device equipped with a camera, arranged for digital communication or storage of video captured with the camera or any other device for processing video frames. Furthermore devices for storing, transmitting or transcoding digitised video may apply.

An input video frame47as described can be received or acquired via input interface34. Input video frames47may be received as an electronic video signal, in analog or digital form. In the case of receiving analog video signals, the input interface is equipped with an analog-to-digital converter. In the case of receiving a digital video signal the input interface is arranged accordingly, well known for an average person skilled in the art. The input video frame47may for example be received from a camera, camcorder, video player, CD-ROM/DVD player and the like.

The processing means35may comprise a microprocessor, DSP, microcontroller or any device suitable for executing program instructions and dedicated hardware. Dedicated hardware may comprise specialized integrated circuits, Field Programmable Gate Arrays and the like for performing some or all steps the steps of encoding the input video frames47as a whole or in part as shown inFIG. 3A.

The program instructions of the video encoding apparatus may be loaded into the memory37from a computer readable medium such as a CD-ROM, DVD, a hard disk, a floppy disc, or from any other medium having previously stored program instructions, via an appropriate interface according to the state of the art. The program instructions are arranged such that they, when executed by the processing means35, perform the steps of encoding the input video frame47as described above.

The result of the encoding of the input video frame47, the encoded video frame18, may be output as a digital signal for transmission to another device for decoding, for storage or any other purpose via output interface36arranged for such purpose and well known to the average person skilled in the art.

FIG. 5Bshows a block diagram of a decoding apparatus according to an exemplary embodiment of the invention. A decoding apparatus generally has an input interface38for receiving an encoded video frame18, processing means39and a memory41and/or dedicated hardware for video decoding, and an output interface40for outputting a decoded video frame29.

The decoding apparatus can be, but is not limited to a communication terminal such as a telephone or mobile phone or personal computer or any other device equipped with a display, arranged for digital communication or display of encoded video. Furthermore devices for storing, receiving or transcoding digitised video or any other device for processing video frames may apply. The decoding apparatus may also be comprised in any one of such devices.

The input interface38is arranged for receiving the encoded video frame18, which may be output from a video encoding apparatus and sent to the video decoding apparatus though a communication link, e.g. a wired or wireless connection. The encoded video frames18may also be output from any storage device known in the art, such as a CD-ROM, DVD, PC hard disk etc.

The processing means39may comprise a microprocessor, DSP, microcontroller or any device suitable for executing program instructions and dedicated hardware. Dedicated hardware may comprise specialized integrated circuits, Field Programmable Gate Arrays and the like for performing some or all steps the steps of decoding the encoded video frames18as a whole or in part as shown inFIG. 3B.

The program instructions of the video encoding apparatus may be loaded into the memory41from a computer readable medium such as a CD-ROM, DVD, a hard disk, a floppy disc, or from any other medium having previously stored program instructions, via an appropriate interface according to the state of the art. The program instructions are arranged such that they, when executed by the processing means39, perform the steps of decoding the encoded video frame18as described above.

The result of the decoding process, the decoded video frame29, may be output for display or any other purpose via decoder output interface40. The decoded video frame23may be output as an analog video signal. For that purpose the output interface40may have a digital-to-analog converter.

It must be understood that the embodiments in the description and figures are given by way of example only and that modifications may be made without departing from the scope of the invention as defined by the claims below.

REFERENCES