A method for coding a sequence of digital images The invention refers to a method for coding a sequence of digital images as well as to a corresponding decoding method. Furthermore, the invention refers to an apparatus for coding a sequence of digital images and an apparatus for decoding a sequence of digital images.

In many different applications, e.g. in surveillance systems or in medical imagery apparatus, a great amount of image and video data is produced. Hence, there is a need to compress this data in order to save storage capacity or to reduce the bandwidth when transmitting the data.

In the prior art, there exist a lot of standards in order to compress image and video data. Prominent examples of the standards are H.264/AVC (AVC = Advanced Video Coding, see document [1]) as well as the draft standard HEVC (HEVC = High Efficiency Video Coding, see also document [2]), which will likely be standardized also as ITU-T Recommendation H.265. The standard HEVC will also allow the real-time transmission of lossless coded image sequences. The standards HEVC and H.264/AVC include different intra prediction modes based on blocks in the same image. In those modes, a current block is predicted for already reconstructed pixels in the neighbor ^¬ hood. An encoder usually tests different prediction types and choses the one with minimal cost with respect to certain dis- tortion criterion. The prediction error is built for the current block and is transmitted to the decoder together with the prediction type. Block-wise prediction has the disad ^¬ vantage that pixels which are far away from the reference pixels used for prediction do not correlate well with the reference pixels. Hence, the prediction error is usually higher for those pixels. In order to improve the prediction, the size of a block can be reduced. However, this results in a higher number of blocks in an image, which leads to a high- er bitrate for signaling of the prediction type. Furthermore, if the reference pixels contain noise, those pixels become suboptimal for prediction. In document [3], an intra-prediction mode based on template matching is described. In this method, a candidate block used for prediction of a current block is determined in a search region on the basis of templates of neighboring pixels adja ^¬ cent to the candidate block and the block to be predicted. The candidate block with the best matched template in compar ^¬ ison to the template of the block to be predicted will be used for prediction. The prediction scheme has the disad ^¬ vantage that the predicted block is still noisy, which is suboptimal for compression of noisy images.

A simple and efficient pixel-wise prediction method is pro ^¬ posed in document [4] . This prediction method named LOCO-I uses a simple and straight forward algorithm to predict a pixel based on three surrounding pixels. This prediction method is not optimal for compression for noisy images, ei ^¬ ther .

In document [5], least-squares based methods for prediction are presented. In those methods, a weighted average of recon- structed pixels in the neighborhood to be predicted is per ^¬ formed. In order to get optimal weights for the averaging process, a complex system of equations has to be solved re ^¬ sulting in an enormous computational overhead. Hence, such prediction methods are not used in practical applications.

It is an object of the invention to provide a coding of se ^¬ quence of digital images overcoming the above disadvantages and enabling an efficient compression with low complexity. Furthermore, it is an object of the invention to provide a corresponding decoding method as well as an apparatus for coding and an apparatus for decoding. This object is solved by the independent patent claims. Pre ^¬ ferred embodiments of the invention are defined in the de ^¬ pendent claims. The method for coding a sequence of digital images according to the invention uses a number of prediction modes (i.e. at least one prediction mode) for predicting values of pixels in the images based on reconstructed values of pixels in image areas processed previously. The term "reconstructed values of pixels" is to be interpreted broadly and depends on the used coding scheme. For lossless coding, the reconstructed values of pixels correspond to the original value of pixels. In case of a lossy coding, the reconstructed values of pixels corre ^¬ spond to coded and thereafter decoded values of pixels. More- over, the reconstructed values of pixels may also refer to predicted values of pixels determined in the corresponding prediction mode. Predicted values of pixels are used in case that a coding and decoding of the respective pixel has not yet been performed when predicting the current pixel.

In a coding method, a prediction error between predicted values and the original values of pixels is processed for gener ^¬ ating the coded sequence of digital images. The method of the invention is characterized by a special preset prediction mode, which is an intra-prediction mode based on pixels of a single image. This preset prediction mode comprises steps i) and ii) as explained in the follow ^¬ ing .

In step i) , for a region of pixels with reconstructed values in a single image and for a template of an image area, a first patch of pixels in the region which surround a first pixel to be predicted based on the template is compared with several second patches, each second patch being assigned to a second pixel in the region and consisting of pixels in the region which surround the second pixel based on the template. Based on this comparison, a similarity measure for each se- cond pixel is determined which describes the similarity be ^¬ tween reconstructed values of the pixels of the second patch assigned to the respective second pixel and the reconstructed values of the pixels of the first patch.

In a step ii) of the method according to the invention, a predicted value of each first pixel is determined based on a weighted sum of (reconstructed) values of the second pixels, where the value of each second pixel is weighted by a

weighting factor, which is monotonously decreasing in dependency on a decreasing similarity described by the similarity measure for the respective second pixel. Here and in the fol ^¬ lowing, the term "monotonously decreasing" means that the weighting factor will decrease at least for larger decreases of the similarity. In other words, for smaller decreases in the similarity it may happen that the weighting factor re ^¬ mains constant.

The coding method according to the invention is based on the idea that a non-local means algorithm, which is known for denoising pixels (see document [6]), can be adapted in order to be used for prediction. To do so, the templates used for prediction are restricted to a (causal) region only including reconstructed values of pixels in the image. The method of the invention provides an efficient coding without the need of solving a linear system of equations as it is the case in prior art methods. Furthermore, there is no restriction in the number of second pixels to be used for predicting a first pixel. Moreover, there is no need of transmitting side infor- mation from the encoder to the decoder because the prediction scheme according to the invention is backward adaptive. Fur ^¬ thermore, the prediction is carried out sample-based so that the prediction error does not depend on the pixel position. In one embodiment of the invention, the weighting factors are the similarity measures or approximated values of the simi ^¬ larity measures so that no separate calculation of the weighting factors has to be performed. However, the weighting factors may also be the similarity measures normalised over all similarity measures determined in step i) or approximated values of the similarity measures normalised over all simi ^¬ larity measures determined in step i) .

In another embodiment of the invention, the preset prediction mode is performed block-wise for first pixels in predeter ^¬ mined image blocks. Hence, the method can be easily combined with block-based coding schemes.

In a particularly preferred embodiment, the similarity meas ^¬ ure is based on the sum of absolute or squared differences between corresponding (reconstructed) pixels in the first patch and the respective second patch. Preferably, the sum of absolute or squared differences is included in the similarity measure as at least a part of a negative exponent of a basis. For an easy and straight-forward calculation of the similari ^¬ ty measure, the basis has preferably the value 2. However, other values for the basis can be used as well.

In a particularly preferred embodiment of the invention, the similarity measure in step i) and/or the predicted value of each first pixel in step ii) are determined based on an inte ^¬ ger arithmetic. This enables a coding with low computational efforts. In the detailed description, an example is described how an integer arithmetic may be implemented in the coding method of the invention.

In another embodiment of the invention, a look-up in a prede- fined table is used for determining the similarity measures in step i) . By using such a predefined table, the computing time for coding can be further reduced. Preferably, the table provides values of the similarity measure for values of the sum of absolute or squared differences between corresponding pixels in the first patch and the respective second patch.

In a particularly preferred embodiment, the preset prediction mode is used for lossless coding of the sequence of images. In this case, reconstructed values of pixels used in step i) are equal to the original values of pixels.

In another embodiment of the invention, the preset prediction mode is used for lossy coding of the sequence of images.

Preferably, the lossy coding includes the known steps of a transform and/or the quantization of the (transformed) prediction errors, where an inverse transform and/or a

dequantization of the prediction errors are performed for de- termining reconstructed values of pixels. In case that a pre ^¬ diction error for a pixel has not yet been subjected to the transform and/or quantization, the predicted value of the pixel is used as the reconstructed value. In a particularly preferred embodiment, the processing of the prediction error includes an entropy coding step enhancing the coding efficiency.

In another embodiment of the invention, it is determined for each first pixel to be predicted based on arbitrary criteria whether the preset prediction mode or another prediction mode is to be used for the first pixel and/or which parameter or parameters of the first prediction mode are used. In another variant of the invention, another prediction mode than the preset prediction mode is used for the first pixel in case that all similarity measures determined in step i) are zero. In the method of the invention, one or more of the parameters of the preset prediction mode may be fixed and/or variable. Said one or more parameters preferably comprise the form and the size of the template and/or the form and the size of the region and/or one or more parameters referring to the deter- mination of the similarity measures and/or a determination of predicted values of first pixels. E.g., the parameters may refer to the value of the above described basis exponent used for calculating the similarity measure. In another embodiment of the invention, the preset prediction mode and/or parameters of the preset prediction mode are sig ^¬ naled in the coding sequence of images. In the detailed de- scription, different variants for signaling the prediction mode or corresponding parameters are described.

In a particularly preferred variant of the invention, the preset prediction mode is used as a prediction mode in the standard HEVC/H.265, for which a draft version exists at the moment .

Besides the above method, the invention also refers to a method for decoding a sequence of digital images, which is decoded by the method of the invention or one or more pre ^¬ ferred embodiments of the method of the invention. In the de ^¬ coding method, the prediction error is reconstructed from the coded sequence of images and the values of the pixels in the coded sequence of images which are processed by the preset prediction mode during coding and are subjected to a special decoding process which comprises steps i) to iii) as de ^¬ scribed in the following.

In a step i) , for a region of pixels with decoded values in a single image which have been determined previously in the de ^¬ coding processing and for a template of an image area, a first patch of pixels in the region which surrounds a first pixel to be predicted based on the template is compared with several second patches, each second patch being assigned to a second pixel in the region and consisting of pixels in the region which surrounds the second pixel based on the tem ^¬ plate, thereby determining a similarity measure for each se ^¬ cond pixel describing the similarity between decoded values of the pixels of the second patch assigned to the respective second pixel and the decoded values of the pixels of the first patch. In a step ii) , a predicted value of each first pixel is de ^¬ termined based on a weighted sum of (decoded) values of the second pixels, where the value of each second pixel is weighted by a weighting factor which is monotonously decreas- ing in dependency on a decreasing similarity described by the similarity measure for the respective second pixel.

In a step iii) , the predicted value of each first pixel is corrected by the corresponding reconstructed prediction error for the first pixel resulting in a decoded value of the first pixel .

The invention also refers to a method for coding and decoding a sequence of digital images, wherein the sequence of digital images is coded by the coding method of the invention and wherein the coded sequence of digital images is decoded by the decoding method of the invention.

The invention also comprises an apparatus for coding a se- quence of images wherein the apparatus includes a means for performing an number of prediction modes for predicting values of pixels in the images based on reconstructed values of pixels in image areas processed previously, where the predic ^¬ tion error between predicted values and the original values of pixels is processed for generating the coded sequence of digital images.

In this apparatus, the means for performing a number of pre ^¬ diction modes comprises a means for performing a preset pre- diction mode which is an intra-prediction mode based on pixels of a single image, where said means for performing the preset prediction mode comprises:

a means for determining similarity measures which is adapted to perform a step in which

- for a region of pixels with reconstructed values in the single image and for a template of an image area, a first patch of pixels in the region which surround a first pixel to be predicted based on the template is compared with several second patches, each second patch being assigned to a second pixel in the region and con ^¬ sisting of pixels in the region which surround the sec ^¬ ond pixel based on the template, thereby determining a similarity measure for each second pixel describing the similarity between reconstructed values of the pixels of the second patch assigned to the respective second pixel and the reconstructed values of the pixels of the first patch;

a second means for predicting values of first pixels which is adapted to perform a step in which

a predicted value of each first pixel is determined based on a weighted sum of values of the second pixels, where the value of each second pixel is weighted by a weighting factor which is monotonously decreasing in dependency on a decreasing similarity described by the similarity measure for the respective second pixel.

The above coding apparatus preferably includes one or more additional means for performing one or more preferred embodi ^¬ ments of the coding method according to the invention.

The invention also refers to an apparatus for decoding a se ^¬ quence of digital images which is coded by the method of the invention. The apparatus includes a decoding means to recon ^¬ struct the prediction error from the coded sequence of images and to decode the values of the pixels in the coded sequence of images which are processed by the preset prediction mode during coding.

The decoding means of the apparatus comprises:

a means for determining similarity measures which is adapted to perform a step in which

for a region of pixels with decoded values in the single image which have been determined previously in the de ^¬ coding processing and for a template of an image area, a first patch of pixels in the region which surround a first pixel to be predicted based on the template is compared with several second patches, each second patch being assigned to a second pixel in the region and con ^¬ sisting of pixels in the region which surround the sec ^¬ ond pixel based on the template, thereby determining a similarity measure for each second pixel describing the similarity between decoded values of the pixels of the second patch assigned to the respective second pixel and the decoded values of the pixels of the first patch; a means for predicting values of first pixels which is adapted to perform a step in which

a predicted value of each first pixel is determined based on a weighted sum of values of the second pixels, where the value of each second pixel is weighted by a weighting factor which is monotonously decreasing in de- pendency on a decreasing similarity described by the similarity measure for the respective second pixel;

a means for correcting the predicted values of first pixels which is adapted to perform a step in which

the predicted value of each first pixel is corrected by the corresponding reconstructed prediction error for the first pixel resulting in a decoded value of the first pixel .

The invention also comprises a codec for coding and decoding a sequence of digital images, comprising a coding apparatus according to the invention and a decoding apparatus according to the invention.

Embodiments of the invention will now be described with re- spect to the accompanying drawings, wherein:

Fig. 1 illustrates a known method for image denoising

based on a non-local means algorithm; Fig. 2 shows different templates which may be used in the prediction method according to the invention; Fig. 3 illustrates the prediction of a pixel based on an embodiment of the invention;

Fig. 4 is a flowchart showing an enhanced prediction based on an embodiment of the invention;

Fig. 5 is a schematic illustration of a coding method implementing the prediction mode according to the invention ;

Fig. 6 is a schematic illustration of a decoding method implementing the prediction mode according to the invention ; Fig. 7 illustrates the use of the prediction mode accord ^¬ ing to the invention in a block-based lossless cod ^¬ ing;

Fig. 8 illustrates the prediction method according to the invention in a block-based lossless coding; and

Fig. 9 is a schematic illustration of a coding and decod ^¬ ing apparatus according to an embodiment of the in ^¬ vention .

Before describing the invention in detail, a prior art method used for image denoising is explained. The invention as de ^¬ scribed later on is based on the idea to use aspects of this prior art method for predicting pixel values. Fig. 1 shows an image which shall be denoised based on a so-called non-local means algorithm (also abbreviated as NLM) which is described in document [6] . In this NLM denoising method, an estimate for a denoised version of a noising pixel is established by averaging all the pixels in the local as well as the non- local neighborhood of the corresponding image. This averaging is based on a weighted sum taken into account the similari ^¬ ties between a number of local neighboring pixels of noisy pixels and a number of non-local neighboring pixels of other pixels in a predetermined area around the noisy pixel. In this way, the NLM algorithm exploits the fact that similar image content is present in different areas of an image and should therefore be considered during an average process. Ac- cording to Fig. 1, the pixel i having the pixel value g[ i ] shall be denoised. To do so, a weighted average of all pixels in the area S surrounding pixel i is calculated. The weights for calculating the average are calculated based on a first patch around the noisy pixel and a second patch around the pixel for which the weight is to be calculated. The patches are based on a predetermined template which is a square in Fig. 1 indicated by a dashed border. Fig. 1 shows as example pixels ji, j ₂ and j ₃ with corresponding pixel values g[ji], g[j ₂ ], and g[j ₃ ], respectively. For the calculation of the weights of those pixels, the corresponding patches based on the template around the pixels are compared with the patch around the noisy pixel i , which is indicated by a solid line. For calculating the similarity, the pixels in the patch around pixel i are compared with the corresponding pixels of patches around other pixels in the area S . In the example shown in Fig. 1, the pixel j ₃ will get a higher weight than the pixels ji and j ₂ . This is because the patch of pixel i and of pixel j ₃ lie along the same border in the image and are, thus, more similar to each other than the patch of pixel i to the patch of pixel ji or the patch of pixel i to the patch of pixel j ₂ .

A formal description of the above described NLM algorithm is given in the following. The averaging process is based on the following formula:

where g[ i ] is the noisy value of pixel i , p _NLM [ i ] is the NLM- processed image (i.e., the denoised value of the pixel i ) and S is the region for denoising (usually a square area of (2D _max + l)*(2D _max + 1) samples, where D _max is the maximum spatial distance) . Furthermore, w[i, j] are the weights for the sam ^¬ ples/pixels in the area S. The weights w[i,j] are defined as

where ^p „ L*J determines a square patch of

pixels with the center pixel i. For calculation of the Eu ^¬ clidian norm ||·||, the whole square neighborhood is used:

wh where (x,y) refers to a 2-dimensional position of a pixel in the image .

From the above equations, it is clear that pixels with a sim ^¬ ilar neighborhood get higher weights whereas pixels with dif ^¬ ferent neighborhoods get lower weights for the non-local av ^¬ eraging .

Contrary to the invention as described in the following, the above algorithm does not follow causal relations in the sense that a predetermined coding sequence is taken into account. I.e., the above denoising method does not consider the fact that a coding method can only process pixels which have al ^¬ ready been at least partially coded and reconstructed before because otherwise a proper decoding is not possible.

The prediction method described in the following adapts the above NLM algorithm by considering causal relations. The pre ^¬ diction method is based on intra-prediction and uses for a pixel to be predicted patches around pixels in a predeter- mined region of already reconstructed pixels. The prediction method is implemented as a prediction mode in a coding method and can be particularly used in the video coding (draft) standard HEVC/H.265.

Fig. 2 illustrates different forms and sizes SI1, SI2, SI6 of templates for patches which may be used in an embodiment of the invention. In this figure, a first pixel to be pre ^¬ dicted in an image is designated as PI and has the pixel val- ue X. In this figure, the coding order is line by line where all pixels in lines above the pixel PI and all pixels in the line of pixel PI at the left side of this pixel have already been coded. In order to calculate a similarity measure, patches based on templates according to sizes SI1 to SI6 can be used. The corresponding templates TE are indicated as dashed pixels for each form and size. I.e., the template of form and size SI1 comprises pixels a, b, c, the template of form and size SI2 comprises pixels a, b, c, d, the template of form and size SE3 comprises the pixels e, a, b, c, d, f and so on. In the following, the term weight correspond to a similarity measure as defined in the claims. Furthermore, the weight normalized by the sum of weights in a region corre ^¬ sponds to a weighting factor as defined in the claims. Fig. 2 also illustrates a region R, which defines a neighborhood region of those pixels which are taken into account when predicting the value for pixel PI . According to the region R, the pixels a, b and c corresponding to second patches adja ^¬ cent to those pixels based on the template TE are used for calculating a similarity measure SM (see Fig.3) . I.e., the first patch including the pixels a, b, and c is compared with the second patch of pixels around pixel a (namely pixels e, g, and b) , with the second patch of the pixels around pixel b (namely pixels g, k, and h) and with the second patch around the pixel c (namely pixels b, h, and f) in order to determine similarity measures/weights between the first and the respec ^¬ tive second patch. Hence, the neighborhood region is based on the patches around the pixels defining a template. This is also the case for the other template sizes SI2 to SI6. Hence, the definition of the template sizes also correspond to a definition of a neighborhood region size. The above described calculation of similarity measures for predicting a first pixel PI is further illustrated in Fig. 3. Fig. 3 uses for the prediction of the pixel PI patches based on the template of the size SI2 in Fig. 2. Those templates have an L-form and comprise four pixels. To determine the predicted value of pixel PI, the first patch including pixels a, b, c, and d around PI is compared to second patches around the pixels n, s, and w in Fig. 1. Those pixels are second pixels P2. The corresponding weight or similarity measure SM for each of those pixels is calculated by comparing the pixel values of the first patch PA1 with the corresponding pixels values of the second patch surrounding the corresponding pixel P2. E.g., for pixel P2 having the value s, the difference between the pixel value a of PA2 and a of PA1, the difference of pixel value m' of PA2 and pixel value g of PA1, the dif- ference of pixel value n' of PA2 and pixel value c of PA1 and the difference of pixel value o' of PA2 and pixel value d of PA1 are summed for calculating the weight of pixel P2 having the value s. In the embodiment of Fig. 3, all pixels in the region corresponding to the pixels indicated by dashed lines in size SI6 of Fig. 2 are used as second pixels for which a weight is calculated.

As there is no knowledge about the pixel PI to be predicted, only asymmetrical patches are used for calculating weights contrary to the method of Fig. 1. As the prediction method has to be used in both the encoder and decoder, the choice of the patch sizes and the regions of second patches has to be done carefully with respect to the prediction computational complexity since increasing the number of second patches or the patch size can dramatically increase the runtime for pre ^¬ diction. For accurate prediction, an increase in the patch sizes may also require a dramatic increase in the number of second patches used for averaging. This is because, if the patch becomes larger, the structural complexity of the patch becomes higher, so it becomes harder to find similar patches. The computations as described with respect to the NLM algo ^¬ rithm of Fig. 1 is adapted for a prediction method of the invention by using a different size of patches/templates and considering only causal pixels for calculating a pixel value. Furthermore, in order to speed up the computations, some sim ^¬ plifications are used in a preferred embodiment of the inven ^¬ tion. The problem of using the original equations of the NLM algorithm shown in Fig. 1 is that the implementation requires a float or double arithmetic. This is because the original NLM algorithm for denoising requires weights that are in the range between 0 and 1. In order to simplify these computa ^¬ tions, the following equation for calculating the predicted pixel value p _NLM [i] is used:

NML [i] -< r · -1 (4)

The weights/similarity measures w[i,j] are considered to be integer values. A second modification has to be done for the calculation of the weights in order to support an integer version of the calculation. This modification is described by the following calculation of the weights w[i,j]:

The term d( ^p ^[i]- ^p ^[j]) is defined in a preferred embodiment as | ^ρ ί['] ^_ρ ί[ί]| according to equation (3) but with different patch size. Furthermore, different basis values b for the exponen tial function may be used. Also, different distance measure functions d(., .) may be allowed. The factor a in the above equation is a scaling factor because the result of the expo nential function can become very small rapidly which would introduce coarse quantization into the weights if integer arithmetic implementation is used. The above adjusting parameter h _d depends on the used distance measure. In a preferred embodiment, the weights w[i,j] are calculated using floating ^¬ point arithmetic but rounded to integer values.

The computation of this measure of the original NLM algorithm for denoising can be simplified by skipping the normalizing of the distance. I.e., the sum of squared errors SSE as de ^¬ scribed by:

∑ (g [i - n] - g [j - n]) (6)

neN„ can be replaced by the measure of the sum of absolute dis ^¬ tance SAD described by: ^d sAD =∑ — n]— ^ [j— n]| (7) .

neN„

In a particularly preferred embodiment, the value of the pa ^¬ rameter a should be chosen to be high in order to get differ- ent integer values. Furthermore, the basis b should be chosen to be low, e.g. 2 or "e".

The above sizes SI1 to SI6 also give so-called neighborhood sizes which refer to those pixels for which a patch of sur- rounding pixels is compared with a patch of pixels surround ^¬ ing pixels PI. The pixels processed according to the neigh ^¬ borhood size SE1 are included in the region R.

In another preferred embodiment, the weights calculated ac- cording to above equation (7) are discarded in case that those weights are lower than a predetermined threshold. This reduces the number of operations to calculate the predictor.

In the following, further enhancements of the above descrip- tion method are described. Fig. 4 shows a flowchart for an enhanced prediction of pixels where irregular cases are taken into account during processing. The prediction starts at step SI with a pixel PI. In step S2, it is determined whether pix ^¬ el PI is a bounding pixel BP at the border of the image. If not (branch N) , the weights w[i,j] are calculated in step S3 as described above. In step S4, it is determined whether all weights are 0. If this is the case (branch Y) , an exception algorithm for predicting the pixel value is used in step S5. If not all pixels are 0 (branch N) , the regular NLM algorithm is used in step S6. In case that the pixel PI is a boundary pixel (branch Y out of step S2), it is determined whether the NLM algorithm shall be used at all. Any criteria may be used for this determination. E.g., it may be indicated beforehand whether NLM shall be used or not by a corresponding flag set in the encoder. In case that the NLM algorithm shall be used (branch Y) , new NLM parameters for boundary pixels are determined in step S8. Thereafter, the method continuous with steps S3, S4, S5, and S6. In case that NLM shall not be used according to step S7 (branch N) , an appropriate exception algorithm for the boundary pixel is used in step S9.

Summarized, in case that the pixel to be predicted in Fig. 4 is a boundary pixel where not all of the needed reference pixels are available, another algorithm is chosen for predic ^¬ tion of this pixel or some parameters of the NLM prediction are changed to meet the requirements for availability of the needed reference pixels. If the NLM algorithm is determined to be used, the weights for NLM averaging are estimated as described above. If at least one weight is not 0, the regular NLM averaging process is performed for prediction of the cur- rent pixel. Otherwise, an exception algorithm is used for prediction. In this case and in the case of boundary pixels, different variants of the exception prediction algorithm can be implemented, i.e.:

the mean value of surrounding pixels can be used for prediction;

the well-known LOCO-I predictor (see document [4]) is used as a prediction of the current pixel, or the parameters of the NLM predictor can be changed in order to perform a new test for prediction calculation.

In the following, a preferred embodiment of an NLM prediction method used in the invention is described. This embodiment is based on the patch size and neighborhood size SI1 shown in Fig. 2. For the distance calculation within the predictor, the sum of absolute differences SAD (see equation (7)) is used. Instead of using an exp-basis, the basis b = 2 is used for calculating the weights, and the division by h _d (see equation (5)) is realized by a right shift of 3 bits. I.e., the weights are calculated using the following formula: w[i_X, j_ ] = 2 ^Λ (- (dSAD (i_X, j_ )»3)) (8),

where i_X is the position of the pixel X to be predicted and where j_ is the position of the pixel a with a = {a, b, c} are the pixels which are used for averaging. dSAD is calcu ^¬ lated based on the corresponding pixels of the patches sur- rounding the pixel a by using the above equation (7) . The symbol ">>3" represents the above mentioned shift of 3 bits. For calculating a predicted value of pixel X, an integer arithmetic based on the following equations is used: X = (a · w[i_X, j_a] + b · w[i_X, j_b] + c · w[i_X, j_c] +

(w[i_X, j_a] + w[i_X, j_b] + w[i_X, j_c] ) /2 ) / (w[i_X, j_a] + w[i_X, j_b] + w[i_X, j_c]) (9),

w[i_X, j_ ] = TableSAD [dSAD (i_X, j_ ) ] (10),

TableSAD [dSAD (i_X, j_ ) ] = 100000 · 2 ^A ( - (dSAD (i X, j_ )»3))

(11) .

The term (w[i_X, j_a] + w[i_X, j_b] + w[i_X, j_c])/2 in equa- tion (9) represents a rounding operation. The above symbol "TableSAD" represents a one-dimensional ta ^¬ ble including predetermined calculations for different values of dSAD. I.e., the differences dSAD are calculated in the method and thereafter, a lookup is done in the table in order to calculate the above value TableSAD. Hence, the above table operation can be described by the following formula: dSAD = dSAD(i_X, j_ ) (12) ,

TableSAD [dSAD] = 100000 · 2 ^Λ (- (dSAD»3) ) (13).

The above formulas explicitly express that the function dSAD is not calculated during the determination of the table but is used as a one-dimensional index for the table.

The scaling of the table by 100000 is necessary as the expo ^¬ nential term tends fast to small values, which are coarsely quantized if integer implementation is used. In cases where all table values give 0 for all weights, an escape for divi- sion by 0 is used. In this case, another predictor is used for the pixel X.

In the following, the implementation of the above described prediction method in a conventional coding and decoding meth- od, which is preferably based on the draft standard

HEVC/H.265, is described.

Fig. 5 shows a block-based encoder receiving the sequence of images I to be decoded. The encoder includes at several posi- tions a switch Is which is in a position describing a lossless coding mount which uses the prediction method of the in ^¬ vention. In case that the switch NS is switched in a second position, a known coding is performed where a prediction error PE obtained by the differentiator is subjected to a transformation T and a quantization Q. This prediction error is then subjected to an entropy encoding EC so that a se ^¬ quence of coded images CI is obtained. During this conven- tional coding, another prediction method than the method of the invention is used. To do so, the prediction error after quantization is dequantized and subjected to an inverse transform IT. This reconstructed prediction error is combined with a prediction value from the prediction module so that reconstructed pixel values of the corresponding block are ob ^¬ tained. These reconstructed values are stored in a buffer BF and used for performing prediction in the prediction module PR. The predicted value calculated in the module PR is then fed to the differentiator DI to provide a prediction error PE . Furthermore, a loop-filter LF is used for filtering the signal obtained by the adder AD.

In case that the lossless switch Is is put in the position as shown in Fig. 5, a lossless coding using the prediction method of the invention is performed. To do so, the blocks for transformation T, quantization Q, dequantization DQ, inverse transform IT, and loop-filter LF are bypassed. In this mode, the reconstructed prediction error PE fed to the adder AD corresponds to the original prediction error PE . Furthermore, the values of pixels in the causal region used for averaging are the original pixels because the original pixel values are available during decoding as the coding is lossless. The loop-filter block LF may refer to different loop-filters, i.e. a deblocking filter, an SAO filter (SAO = Sample Adaptive Offset), and the like. When using the lossless coding, the prediction method based on the above described NLM algo ^¬ rithm is used in the prediction module PR. The dotted lines L in Fig. 5 illustrate the inclusion of parameters of the pre ^¬ diction in the lossless and lossy coding mode in the sequence of coded images. Those parameters are also subjected to en ^¬ tropy coding. The state of the above lossless switch Is can be signaled explicitly for each block, slice, frame, or se- quence separately. However, the state can also be inferred for each block, slice, frame, or sequence from some other pa ^¬ rameters, e.g. by using the quantization parameter QP. E.g., in case that the quantization parameter has the value of 0, this can be the indication that the lossless mode is to be used .

Fig. 6 shows a decoder of the coded sequence of images CI ob- tained by the encoder of Fig. 5. At first, the images are subjected to an entropy decoding ED resulting in a prediction error PE . In case of a lossless encoding, the switches S are in the first positions as shown in Fig. 6. As a consequence, the prediction error is used directly by the prediction mod- ule PR. To do so, the original pixel value is obtained by the adder AD and stored in the buffer BF. The stored values in the buffer BF are used for further prediction by the prediction module PR. Eventually, the sequence of decoded images DI being identical to the original images I is obtained. In case of a lossy encoding, more switches are put in the second po ^¬ sition so that in a known manner a dequantization DQ, an inverse transform IT and loop-filters LF are applied to the signal in order to perform another prediction in the prediction module PR. As a consequence, a decoded sequence of imag- es is obtained where some information is lost due to quanti ^¬ zation and transformation. The dotted line L in Fig. 6 represents the provision of parameters originally included in the coded sequence of images which are needed by the predictor module PR to perform appropriate prediction. In the lossy coding mode, well-known prediction techniques based on INTRA as well as on INTER prediction may be used.

Fig. 7 illustrates the above described pixel-wise NLM predic ^¬ tion in a block-based lossless coding scheme. In Fig. 7, the block B in the right lower edge of image I is currently pre ^¬ dicted. This block refers to a so-called transform unit where all pixels in those block are subjected to a transform in case that the lossy coding mode is used. Instead of a trans ^¬ form unit, the block may also be a coding unit or a predic- tion unit. The blocks with white background colors and exclu ^¬ sively including black pixels are already reconstructed and are used for prediction of the current block B. Fig. 7 shows the scenario in which the pixel PI is currently predicted in the block B. The black pixels in the block B have already been reconstructed and refer to the original pixels due to the lossless coding. The prediction in Fig. 8 is performed in a line-scan order but also other scan orders may also be used. The pixel-based NLM prediction begins with the top left pixel and the block B. This pixel is predicted using the described NLM prediction algorithm. The top left pixel of the prediction error is calculated by the difference between the original pixel and the predicted pixel. After ^¬ wards, the original pixel is immediately written into the re ^¬ constructed buffer in order to be used for the prediction of the next pixel and so on. Hence, when the pixel PI shown in Fig. 7 is predicted, the predictor can only use the already available pixels represented by black circles for prediction. This procedure continuous until all white pixels which have to be compressed are predicted in the block B.

As mentioned above, the prediction method according to the invention is to be implemented in the draft standard

HEVC/H.264. Preferably, the prediction method is used for lossless coding as described above. If a corresponding coding unit is coded in a lossless way, the transformation, quanti ^¬ zation and loop-filtering within the encoder are disabled as shown in Fig. 5. Similarly, the inverse transformation, the dequantization and the loop-filtering are disabled within the decoder, too. The following options may be used in order to incorporate the NLM prediction method into the HEVC syntax: a certain prediction mode for NLM prediction is used in addition to the modes INTRA and INTER;

a certain prediction type for the NLM prediction mode in addition to the defined prediction types in INTRA prediction is used;

certain prediction modes or prediction types within the HEVC syntax are replaced by the prediction mode of the invention ;

a combination of existing prediction modes and prediction types with the NLM prediction mode is used; a certain value (e.g. 0) is used for the quantization parameter .

Different parameters of the NLM prediction method can be sent as side information:

the patch form and the patch size;

the neighborhood form and the neighborhood size;

the parameters a (scaling factor) , b (exponential ba ^¬ sis) , d (distance measure) and the modeling parameter h _d (divisor in the exponent) .

The above parameters can be sent frequently, e.g. for each picture, slice (i.e. partition of a picture) or coding unit in order to adapt to the statistics of the image signal. The parameters can also be sent only once for an image sequence or jointly for several images, e.g. within a parameter set like the sequence parameter set or the picture parameter set. As an alternative, the parameters could also be estimated by a defined algorithm. As another alternative, these parameters can be fixed in a certain profile and/or level of the stand ^¬ ard and, thus, need not be transmitted or estimated at all.

Furthermore, the entropy coding of the prediction error can be adapted with respect to the statistical properties of the prediction error of the NLM prediction method. Therefore, a special binarization scheme as well as context modeling can improve the compression results.

The following adaptations with respect to the coding order using the NLM prediction mode can be optionally implemented: the causal neighborhood for the NLM prediction mode can be linked to the coding unit order or prediction unit order. In this case, the prediction and reconstruction follows the original prediction and reconstruction order of the HEVC draft standard;

the casual neighborhood for the NLM prediction mode can be limited by the size for a coding unit and the cod ^¬ ing/decoding order. In this case, different coding units can be encoded and decoded in parallel depending on the already reconstructed neighboring coding units or other partitions in the image;

the causal neighborhood for the NLM prediction mode can be limited by a size of a prediction unit and the cod ^¬ ing/decoding order. In this case, different prediction units can be encoded and decoded in parallel depending on the already reconstructed neighboring prediction units or other encoding units.

Generally, the NLM prediction method can be used in block- wise coding methods as well as in pixel-based coding methods. Hence, the combination of different pixel-based prediction methods with the NLM prediction method can be used. Further- more, the NLM prediction method can be used for both lossless coding and transform-based coding.

In one embodiment of the invention, the NLM prediction algo ^¬ rithm is used in combination with the above mentioned LOCO-I algorithm. Particularly, if the LOCO-I algorithm does not detect a vertical or horizontal edge, the NLM prediction algo ^¬ rithm is used for prediction of the current pixel.

Furthermore, the NLM prediction can also be used for lossy pixel-wise coding. To do so, the NLM prediction mode is con ^¬ structed as described before using the NLM prediction algo ^¬ rithm. Afterwards, the prediction error for the corresponding pixel is built which is quantized in order to achieve redun ^¬ dancy reduction. This procedure is performed for each pixel individually.

Moreover, the NLM prediction method may also be used for los ^¬ sy transform coding. To do so, the prediction error block has to be built before transform and quantization is performed. When performing prediction, the causal available reconstruct ^¬ ed pixels are used for prediction of the neighboring pixels. The predicted pixels and the causally available pixels are used for prediction of further pixels until the prediction block is filled. The block is used for prediction error building which is transformed and quantized afterwards. Fig. 8 shows an example of such a block-based lossy coding. In this figure, circles represent pixels of a certain image area analogously to Fig. 7. The area is divided in several blocks which are coded separately. The blocks with the white background color are already reconstructed and are used for prediction of the current block B forming a transform unit. In this block, the pixel PI is currently predicted. The hatched pixels in Fig. 8 represent predicted values of pix ^¬ els. According to Fig. 8, the prediction is performed in a line-scan order but other scan orders may also be used. The pixel-based NLM prediction begins with the top left pixel of block B. This pixel is predicted using the above described

NLM prediction algorithm. For prediction of the top left pixel, all black circles from other blocks can be used if they are already reconstructed. The pixel is predicted and the predicted value indicated by the corresponding hedged circle is further used as a reference sample for the prediction of other pixels, and so on. For the prediction of the pixel PI in Fig. 8, the already reconstructed pixels from other blocks (black circles) and the already predicted pixels from the current block (orange circles) can be used. The process con- tinuous until all pixels within the block B are predicted. Thus, a prediction block is generated, which is subtracted from the current block in order to get a prediction error block. The prediction error block can then be transformed, quantized, dequantized, and inverse transformed as it is com- mon in a lossy transform encoder. At the decoder, the quantized transform coefficients are dequantized, inverse trans ^¬ formed, and added to the NLM predicted block in order to get the lossy reconstructed block. The invention as described in the foregoing has several ad ^¬ vantages. Particularly, an automatic backward adaptive pre ^¬ diction method is provided based on a non-local means algo ^¬ rithm for image denoising. This algorithm can inherently denoise the prediction without explicit denoising of the ref ^¬ erence pixels. The prediction technique according to the in ^¬ vention has considerable performance increase. Also the com ^¬ plexity of the method is relatively low, which makes it easi- er to be used in technical applications. Particularly, no set of (linear) equations has to be solved in comparison to least-squares prediction methods in the prior art. The accu ^¬ racy of the prediction method can be adapted with the number of patches for forming the predictor. Furthermore, no side information (e.g. weights) needs to be transmitted, thus keeping the total data rate of the image stream low. Moreo ^¬ ver, different enhancements may be implemented in order to improve the quality of the predictor or reduce the complexity as has been described in the foregoing.

The prediction method of the invention can be adapted for lossless coding in conventional block-based image encoders and decoders which means that no transform quantization, loop-filtering, dequantization, and inverse transform have to be performed and the prediction can be carried out pixel- wise. This means that the prediction error does not depend on the pixel position. I.e., the prediction error is not increasing with increasing distance to the neighboring blocks. An example of the NLM prediction algorithm according to the invention has been tested by the inventors. A version of this algorithm has been implemented in a reference software based on the draft standard HEVC . The DC prediction type or the PLANAR prediction type according to the reference software were replaced by an NLM predictor according to the invention. For coding tests, ten frames of different video sequences were coded. The coding tests have been performed using dif ^¬ ferent sets of video sequences. The simulation results for the NLM prediction are summarized in Table 1 below. In this table, the first column refers to different videos named as SVTshort, MedicoISI, ClassD and ClassF. The second column refers to a comparison of an inte- ger version of the NLM prediction with the DC prediction mode. The third column refers to a comparison of an integer version of the NLM prediction with the PLANAR prediction mode. In the lines for each video, the reduction of the bi- trate for the NLM prediction algorithm in comparison to the DC and PLANAR mode as well as the encoding and decoding time in percent for the NLM prediction algorithm in comparison to the DC and PLANAR mode are shown. An encoding and decoding time of 100 % refers to the encoding and decoding time of the DC and PLANAR mode, respectively.

Table 1:

As can be seen from the table, the bitrate is saved when us ^¬ ing the NLM predictor. Moreover, also a considerable runtime decrease is achieved in the decoder and the encoder when us ^¬ ing the NLM prediction mode. Hence, a considerably better coding performance can be achieved by the NLM prediction mode according to the invention in comparison to prediction modes according to the prior art.

Fig. 9 shows a schematic illustration of a codec comprising a coding apparatus and a decoding apparatus using the predic- tion mode based on the invention. In the scenario of Fig. 9, a sequence of images is fed to an encoder EN. For performing the NLM prediction mode, the encoder comprises a means Ml for determining similarity measures. Based on a region of pixels with reconstructed values in a single image and for a tem ^¬ plate of an image area, this means compares a first patch of pixels in this region which surround a first pixel to be pre ^¬ dicted based on the template with several second patches, each second patch being assigned to a second pixel in the re ^¬ gion and consisting of pixels in the region which surround the second pixel based on the template. As a result, a simi- larity measure for each second pixel describing the similari ^¬ ty between reconstructed values of the pixels of the second patch assigned to the respective second pixel and the recon ^¬ structed values of the pixels of the first patch is deter ^¬ mined .

The encoder further comprises a means M2 for predicting values of first pixels. To do so, a predicted value of each first pixel is determined based on a weighted sum of values of the second pixels, where a weight of a value of a second pixel is monotonously decreasing in dependency on a decreas ^¬ ing similarity described by the similarity measure for the second pixel.

Based on this prediction, a prediction error is obtained, which is transmitted as the coded sequence of images CI to a decoder DEC. In the decoder DEC, the prediction method used in the encoder is analogously implemented. Particularly, the decoder comprises a means M3 for determining similarity measures. For a region of pixels with decoded values in a single image which have been determined previously in the de ^¬ coding processing and for a template of an image area, this means compares a first patch of pixels in the region which surrounds the first pixel to be predicted based on the tem ^¬ plate with several second patches, each second patch being assigned to a second pixel in the region and consisting of pixels in the region which surround the second pixel based on the template. As a result, a similarity measure for each se ^¬ cond pixel describing the similarity between decoded values of the pixels of the second patch assigned to the respective second pixel and the decoded values of the pixels of the first patch is determined.

Furthermore, the decoder DEC comprises a means M4 for pre ^¬ dicting values of first pixels. To do so, a predicted value of each first pixel is determined based on a weighted sum of values of the second pixels, where a weight of a value of a second pixel is monotonously decreasing in dependency on a decreasing similarity described by the similarity measure for the second pixel.

Moreover, the decoder DEC comprises a means M5 for correcting the predicted value of the first pixel. To do so, the pre ^¬ dicted value of the first pixel is corrected by the corre ^¬ sponding prediction error for the first pixel resulting in a decoded value of the first pixel. The prediction error is in ^¬ cluded in the received sequence of images CI. Eventually, a sequence of images DI is obtained by the decoder which corre ^¬ sponds to the original sequence of images I in case that a lossless coding and decoding has been used.

List of references:

[1] Thomas Wiegand, Gary J. Sullivan, Gisle Bj0ntegaard, and Ajay Luthra. Overview of the H.264/AVC Video Coding

Standard. IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, VOL. 13, NO. 7, JULY 2003

[2] Gary J. Sullivan, Jens-Rainer Ohm, Woo-Jin Han, and Tho- mas Wiegand. Overview of the High Efficiency Video Cod ^¬ ing (HEVC) Standard. PRE-PUBLICATION DRAFT, TO APPEAR IN IEEE TRANS. ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, DEC. 2012 [3] Thiow Keng Tan, Choong Seng Boon, and Yoshinori Suzuki, Intra Prediction by Template Matching, IEEE Interna ^¬ tional Conference on Image Processing (ICIP 2006), At ^¬ lanta, GA, USA, October 2006 [4] Marcelo J. Weinberger, Gadiel Seroussi, and Guillermo Sapiro. The LOCO-I lossless image compression algorithm: Principles and standardization into JPEG-LS . IEEE Trans ^¬ actions on Image Processing, August 2000 [5] Xin Li and Michael T. Orchard, "Edge-Directed Prediction for Lossless Compression of Natural Images", IEEE Trans ^¬ action on Image Processing, June 2001

[6] A. Buades, B. Coll, and J.-M. Morel. A non-local algo- rithm for image denoising. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2005), Washington, DC, USA, June 2005