Abstract:
A method and device form a prediction value. A prediction direction is locally described by nonlinear trajectories. The prediction direction can be used in forming a prediction value to achieve a more accurate prediction determination. The method and device can be used in image compression or image-sequence compression.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application is based on and hereby claims priority to International Application No. PCT/EP2012/050133 filed on Jan. 5, 2012 and German Application Nos. 10 2011 002 732.7 filed on Jan. 14, 2011 and 10 2011 006 036.7 filed on Mar. 24, 2011, the contents of which are hereby incorporated by reference. 
     
    
     BACKGROUND 
       [0002]    The invention relates to methods and to a device for forming a prediction value. 
         [0003]    In image and video coding, when images of a video are compressed for example, some images in the image sequence are coded without reference to at least parts of other images. This is necessary at the beginning of an image sequence for example because at that time no previously coded image content is available as yet. It is also necessary in the case of groups of images GOPs (GOP—Group Of Pictures) which are intended to be decodable independently of one another. 
         [0004]    Image or video coding which does not resort to image contents of an image that has already been coded in the past is referred to as intra coding. Even in the case of images which would be able to access image contents of said type it can be advantageous to perform intra coding if no good time predictor can be found in a reference frame of a previously coded image. This occurs for example at the time of scene changes or discovery of new image contents in the image. 
         [0005]    With intra coding, however, already coded image contents of the image that is currently to be coded can be referred to for prediction purposes. This enables a decoder wanting to decode a coded or compressed image sequence to draw upon already decoded image contents and so avoid drift due to errors in decoding. 
         [0006]    Different intra prediction directions are defined in a standard ITU H.264/AVC (ITU—International Telecommunications Union, AVC—Advanced Video Coding).  FIG. 1  shows this by way of example, where the numbers 0 to 1 and 3 to 8 represent predefinable prediction directions. 
         [0007]      FIG. 2  shows an image region composed of 5×5 pixels. In order to determine a position of the respective pixel, a coordinate system has been introduced in  FIG. 2 : horizontal with the values 0, 1, 2, 3, 4 and vertical with the values a, b, c, d, e. Thus, the pixel in the corner at bottom right has the position e 4 . In addition  FIG. 2  shows a hatched image region and an unhatched image region. The hatched image region comprises only reconstructed pixels, i.e. pixels which have already been coded and decoded and therefore are available in a reconstructed form for the intra coding, such as the pixels a 0  to a 4 , b 0 , c 0 , d 0  and e 0 . 
         [0008]    In contrast, the unhatched region, in this case embodied as a 4×4 block, describes a prediction image region to which e.g. the intra prediction mode  4 , i.e. a diagonal prediction direction—see FIG.  1 —is to be applied. The prediction is symbolized in  FIG. 2  by small arrows. Thus, for example, a prediction value PRW is implemented for the pixel b 1  on the basis of the reconstructed image value a 0 , i.e. PRW(b 1 )=W(a 0 ). The image value W of a pixel, like the prediction value also, describes an amplitude value for a luminance and/or chrominance value of the respective pixel. The prediction value is then used for example as a basis for forming a difference in order to determine a differential value RES(.) for further coding of the pixel b 1 , such as e.g. this 
         [0000]        RES ( b 1)= W ( b 1)− PRW ( b 1)= W ( b 1)− W ( a 0).
 
         [0009]    In this way a respective prediction value can be calculated for all image values within the unhatched region. 
         [0010]    In a step following the prediction the respective differential image value is quantized and coded. The coded image values result in a coded image data stream. The reconstructed image values are produced following decoding, inverse quantization of the coded image values and addition with the prediction value. 
         [0011]    As is evident from  FIG. 1  and  FIG. 2 , all the predictions follow linear trajectories, in  FIG. 2 , for example, from the reconstructed pixel a 0  in a straight line to a pixel e 4  that is to be predicted. Textural information that is contained within the image region that is to be predicted and that does not follow this linear prediction rule would only be predicted to an inadequate degree and result in a low compression rate or, as the case may be, poor image quality following the reconstruction. 
         [0012]    Two similar coding modes called “line-based interprediction” are described in recently published documents “Description of Video Coding Technology Proposal by Huawei Technologies &amp; Hisilicon Technologies” by H. Yang et al. (2010) and “Description of Video Coding Technology Proposal by Microsoft” by F. Wu et al. (2010). In said modes a weighted averaging of neighbor pixels can be employed for a pixel that is to be predicted. 
       SUMMARY 
       [0013]    One possible object is to enable improved prediction. 
         [0014]    The inventors propose a method for forming a prediction value for a first image value of a first pixel of an image on the basis of a second image value of at least one reconstructed pixel of the image, the method comprising: 
         [0015]    forming at least one trajectory that has a third image value, an image value along the respective trajectory corresponding to the respective third image value and the respective trajectory having a shape that is not a straight line; 
         [0016]    assigning the second image value to the respective third image value; 
         [0017]    determining at least one of the trajectories as an auxiliary trajectory that is at a distance from a position of the first image value, the distance constituting the shortest distance to the position; 
         [0018]    generating the prediction value on the basis of the third image value of the auxiliary trajectory. 
         [0019]    The present method has the advantage that a more accurate prediction can be carried out on the basis of the nonlinear prediction directions taken by the respective trajectory. This results in an improvement in image quality at the same bit rate of a coded data stream or, assuming the image quality remains the same, a reduction in the bit rate or in the storage space of the coded video data stream. The reason for this improvement is to be seen in the fact that the more accurate prediction enables a more precise estimation of the prediction value of the first image value that is to be coded and as a result a smaller differential value requiring to be compressed is yielded for differential coding. 
         [0020]    A local location of the trajectories can either be permanently predefined, for example through a selection of possible trajectory locations or shapes, or can result on the basis of already coded and reconstructed image values or pixels. In this way an environment of the first image value requiring to be coded can be analyzed and from this a calculation rule established for a location or shape of the trajectories that are to be formed. 
         [0021]    For the assignment of the second image value it is furthermore possible to select that second image value that minimizes a distance between the second image value and the trajectory assigned to the third image value. Alternatively hereto the third image value can be generated by a reconstructed image value that results after coding and decoding of the first image value. It is moreover possible to make a change to the third pixel following completion of the formation of the prediction value, the second image value, generated by a reconstruction of the first image value after coding and decoding, then being used for forming the prediction value for a further first image value. What is achieved as a result of this extension of the method is that a second image value of a reconstructed pixel is used as the third image value of the respective trajectory, which second image value represents good prospects for a good determination of the prediction value. What is therefore achieved as a result of the minimization, for example, is that the third image value is assigned that second image value which on the basis of its local location is most similar to the third image value. Known or standardized image or video compression methods for example can be used for coding and decoding, such as e.g. ITU H.263, H.264 or MPEG-2 (ITU—International Telecommunications Union, MPEG—Moving Pictures Expert Group). 
         [0022]    In an extension of the method only one trajectory is taken into account for generating the first image value if the distance is equal to zero. In this case the third image value of the considered auxiliary trajectory is assigned to the first image value. The effect of this extension is that in the event that the trajectory comes to lie on the first image value, a good determination for the prediction value is made possible. Furthermore a less complex implementation of the method is made possible as a result of this extension. 
         [0023]    In an alternative embodiment variant to the last extension at least two auxiliary trajectories are determined in such a way that the distance between the respective auxiliary trajectory and the position of the first image value constitutes a shortest distance. In this case the prediction value is formed by the third image values of the at least two auxiliary trajectories. In this embodiment variant the prediction value is formed by the third image values of the at least two auxiliary trajectories in such a way that those auxiliary trajectories are taken into account which from the set of all available auxiliary trajectories have the shortest distances. Thus, on the one hand the auxiliary trajectory having the shortest distance is used and in addition the further auxiliary trajectory that has the next shortest distance to the position is taken into consideration. 
         [0024]    In a development of this embodiment variant the prediction value is formed by a weighted averaging of the third image values of the at least two auxiliary trajectories. What is achieved hereby is that the prediction value can be estimated with maximum accuracy in respect of the first image value. Furthermore the weighted averaging can take the distances into account as reciprocal values in each case. This is advantageous because the third value of the auxiliary trajectory that is located closer to the first image value is taken into greater account than the third value of a further auxiliary trajectory that is located further away. In general it is also possible to use more than two auxiliary trajectories. In this case a weighted averaging is taken into account that considers more than two selected auxiliary trajectories, for example according to their distances or the reciprocal value of their distances. 
         [0025]    Furthermore a new trajectory can be formed in such a way that the new trajectory is arranged on the basis of the position of the first image value, a third value of the new trajectory being assigned the prediction value or the first image value or a reconstructed image value of the first image value. 
         [0026]    What is achieved through the use of the new auxiliary trajectory is that a more accurate estimation of the respective first image value is made possible in the formation of a prediction value for further pixels within the image. This is because in addition to the consideration of the formed trajectories, a refined estimation of the prediction value can be achieved based on the new auxiliary trajectory or trajectories. It should be noted that the third image value of the new trajectory can be formed by the prediction value itself, by the first image value or by a reconstructed image value of the first image value. 
         [0027]    This extension can be supplemented in that the new trajectory is arranged between two auxiliary trajectories in such a way that at an arbitrary point on the new trajectory a ratio of the shortest distances between the arbitrary point and the two auxiliary trajectories is identical to a ratio of the distances of the two auxiliary trajectories to the first image value. This extension describes a possible location and consequently a possible shape of the new trajectory. It is advantageous in this case that the new location of the new auxiliary trajectory can be determined in a simple manner. 
         [0028]    The inventor also proposes a device for forming a prediction value for a first image value of a first pixel of an image on the basis of a second image value of at least one reconstructed pixel of the image, the device comprising the following units: 
         [0029]    first unit for forming at least one trajectory that has a third image value in each case, an image value along the respective trajectory corresponding to the respective third image value and the respective trajectory having a shape that is not a straight line; 
         [0030]    second unit for assigning the second image value to the respective third image value; 
         [0031]    third unit for determining at least one of the trajectories as an auxiliary trajectory that is at a distance from a position of the first image value, the distance constituting a shortest distance to the position; 
         [0032]    fourth unit for generating the prediction value on the basis of the third image value of the auxiliary trajectory. 
         [0033]    The method can be realized and carried out with the aid of the device. The advantages are analogous to the corresponding method. 
         [0034]    The device can additionally have at least one further unit, wherein individual portions of the method of the preceding developments or alternative embodiment variants can be implemented by the further unit. The advantages are analogous to the description of the illustrated embodiment variants. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0035]    These and other objects and advantages of the present invention will become more apparent and more readily appreciated from the following description of the preferred embodiments, taken in conjunction with the accompanying drawings of which: 
           [0036]      FIG. 1  shows possible prediction directions according to the ITU H.264 standard (related art); 
           [0037]      FIG. 2  provides a general description of a procedure for predicting image values of reconstructed pixels; 
           [0038]      FIG. 3  shows an exemplary embodiment of the proposed method with several trajectories; 
           [0039]      FIG. 4  shows an exemplary embodiment for forming a new trajectory on the basis of two existing trajectories; 
           [0040]      FIG. 5  shows an exemplary embodiment for forming nonlinear trajectories for determining prediction values; 
           [0041]      FIG. 6  shows an exemplary embodiment in respect of adaptive nonlinear trajectories for determining prediction values; and 
           [0042]      FIG. 7  shows a device for determining a prediction value. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
       [0043]    Reference will now be made in detail to the preferred embodiments of the present invention, examples of which are illustrated in the accompanying drawings, wherein like reference numerals refer to like elements throughout. 
         [0044]      FIGS. 1 and 2  were explained at length in the introduction, so no further description will be provided at this point. 
         [0045]    A first embodiment variant of the proposals is explained in more detail with reference to  FIG. 3 . 
         [0046]      FIG. 3  shows an image B made up of 352×288 pixels. Pixels are organized therein into image blocks BB, for example at a size of 4×4 pixels. Each of the pixels has an image value in each case representing a chrominance value and/or a luminance value, for example in the form of an 8-bit resolution. Each square within the image block BB represents a pixel, such as for example a first pixel, BP 1  and an associated first image value W 1 . For this discussion it is assumed that the image value has a position within the pixel designated by the square, for example a point at which diagonals of the square intersect. 
         [0047]      FIG. 3  further shows a hatched area containing reconstructed pixels BR 1 , BR 2  and the associated second pixel values W 21 , W 22 . The reconstructed pixels were coded at an early point in time and are available in their decoded, i.e. reconstructed form, for the purpose of forming the prediction value. 
         [0048]    In a first step at least two trajectories T 0 , T 1 , T 2 , T 3 , T 4  are formed. In the first exemplary embodiment said trajectories are drawn as quadrants and so do not represent a straight line. An image value along the respective trajectory corresponds to a respective third image value W 31 , W 32 . In the present exemplary embodiment the respective trajectory starts in the second image value which corresponds exactly to the third image value of the respective trajectory. 
         [0049]    In a second step two auxiliary trajectories HT 1 , HT 2  are determined from the set of available trajectories T 0 , T 1 , T 2 , T 3 , T 4  in such a way that a respective distance A 1 , A 2  between the auxiliary trajectory HT 1 , HT 2  that is to be determined and the position P 1  of the first image value W 1  is minimal, i.e. constitutes a shortest distance in each case. In the present exemplary embodiment the trajectories T 1  and T 2  are the nearest neighbors to the first pixel, such that HT 1 =T 1  and HT 2 =T 2 . 
         [0050]      FIG. 3  shows the respective distance A 2  of the trajectory T 2  from the position T 1  and A 1  of the trajectory T 1  between trajectory T 1  and position P 1 . Since this is the shortest distance, the distance of the respective trajectory forms a 90° angle to the position P 1 . 
         [0051]    In a following step the prediction value PRW is formed by weighted averaging of the third image values W 31 , W 32  of the two auxiliary trajectories HT 1 =T 1 , HT 2 =T 2  taking into account the associated distances A 1 , A 2 , as follows: 
         [0000]    
       
         
           
             
               PRW 
                
               
                 ( 
                 
                   W 
                    
                   
                       
                   
                    
                   1 
                 
                 ) 
               
             
             = 
             
               
                 
                   
                     
                       
                         1 
                         
                           A 
                            
                           
                               
                           
                            
                           1 
                         
                       
                       · 
                       W 
                     
                      
                     
                         
                     
                      
                     31 
                   
                   + 
                   
                     
                       
                         1 
                         
                           A 
                            
                           
                               
                           
                            
                           2 
                         
                       
                       · 
                       W 
                     
                      
                     
                         
                     
                      
                     32 
                   
                 
                 
                   
                     1 
                     
                       A 
                        
                       
                           
                       
                        
                       1 
                     
                   
                   + 
                   
                     1 
                     
                       
                         A 
                          
                         
                             
                         
                          
                         2 
                       
                        
                       
                           
                       
                     
                   
                 
               
               = 
               
                 
                   
                     A 
                      
                     
                         
                     
                      
                     
                       2 
                       · 
                       W 
                     
                      
                     
                         
                     
                      
                     31 
                   
                   + 
                   
                     A 
                      
                     
                         
                     
                      
                     
                       1 
                       · 
                       W 
                     
                      
                     
                         
                     
                      
                     32 
                   
                 
                 
                   
                     A 
                      
                     
                         
                     
                      
                     1 
                   
                   + 
                   
                     A 
                      
                     
                         
                     
                      
                     2 
                   
                 
               
             
           
         
       
     
         [0052]    This approach is known as bilinear interpolation. 
         [0053]    An extension of the proposals is described with the aid of  FIG. 4 .  FIG. 4  shows a detail from  FIG. 3  with the auxiliary trajectories HT 1  and HT 2 , as well as the first image value W 1  and the position P 1 . First the prediction value is formed, as explained with reference to  FIG. 3 . The prediction value PRW corresponds to a weighted averaging of the third image values W 31 , W 32  of the trajectories T 1 , T 2 . In a further step a new trajectory T 5 , referred to in the following as T 5 , is now generated between the existing trajectories T 1  and T 2 . The new trajectory T 5  runs at least through the first image value W 1  at the position P 1 . Furthermore the new trajectory T 5  can run between the auxiliary trajectories HT 1 , HT 2  in such a way that at an arbitrary point on the new trajectories a ratio of the shortest distances between the arbitrary point and the two auxiliary trajectories is identical to a ratio of the distances A 1 , A 2  in the first image value. A third image value W 35  of the new trajectory T 5  is equal to the prediction value PRW for the first image value. 
         [0054]    In an alternative embodiment variant hereto a reconstructed image value WR can also be determined for the third image value W 35  of the new trajectory T 5 . For that purpose a differential value can first be formed from the first image value W 1  and the prediction value PRW to yield 
         [0000]        RES ( BP 1)= W 1 −PRW    
         [0055]    In the following step the differential value is coded in quantized form, for example by a Huffmann coding scheme, decoded and inversely quantized. A plurality of differential values can optionally be transformed in addition prior to the quantization and back-transformed after the inverse quantization. Finally a reconstructed differential value RES′(BP 1 ) results which is different from the differential value RES(BP 1 ). The reconstructed image value WR is then formed into 
         [0000]        WR=PRW+RES ′( BP 1)
 
         [0056]    This reconstructed image value is used as the third image value W 35  of the new trajectory T 5  in subsequent formations of a further prediction value, e.g. for BPX, see position c 3 . 
         [0057]    Another exemplary embodiment is explained with reference to  FIG. 5 . In this case five trajectories T 0 , T 1 , T 2 , T 3 , T 4  are shown, each of the trajectories having a nonlinear shape. The trajectories start in each case in one of the second image values W 22  and therefore have the second image value W 22  as third image value W 32 . 
         [0058]    In this example the first pixel BP 1  is located on position c 3 . In  FIG. 5  the trajectories were constructed in such a way that they lie precisely on a position of the respective image value. In this case only one auxiliary trajectory HT 2  is determined, for which the distance A 2  is zero. It is of course possible for hybrid shapes to occur in which one or more of the positions do not come to lie on a trajectory or auxiliary trajectory. 
         [0059]    In the present case the trajectory T 2  is chosen as the auxiliary trajectory HT 2 , because the distance A 2  between the auxiliary trajectory HT 2  and the position of the first image value is zero. Thus, the prediction value PRW is equal to the third image value W 32  of the trajectory T 2 , said third image value W 32  being equal to the second image value W 22  of the reconstructed pixel BR 2 . 
         [0060]    In a third exemplary embodiment a combination of conventional prediction using straight lines and trajectories that are not straight is explained. In the previous examples predefined prediction patterns were presented in some cases with the aid of the trajectories. In the following example an adaptive intra prediction is described. In this case a prediction is performed one step at a time, wherein after a pass through a prediction a prediction direction for a following prediction can be adaptively adjusted. 
         [0061]    Contrary to the previous representation in  FIGS. 3 to 5 , a trajectory is now formed by a plurality of arrows which represent a continuous connection. In a first step a first row of first image values (see associated pixels at the positions b 1 , b 2 , b 3 , b 4  in the coordinate system) is predicted on the basis of the second image values W 21 , W 22 , W 23 , W 24  of the reconstructed pixels PR 1 , PR 2 , PR 3 , PR 4  lying directly above. 
         [0062]    In a second step a second row of first image values (see first pixels at positions c 1 , c 2 , c 3 , c 4  in the coordinate system) is predicted on the basis of a diagonal prediction direction leading from top left to bottom right. This corresponds for example to the prediction direction  4  from  FIG. 1 . This prediction direction is implemented in the second step also for the first image values having first pixels at the positions d 1  and e 1 . 
         [0063]    In a third and fourth step a downward-directed prediction takes place, marked by the numbers  3  and  4  in  FIG. 6 . 
         [0064]    The trajectory T 1  leads from a 1 , b 1 , c 2 , d 2  to e 2 . The trajectories T 2  and T 3  are formed in an analogous manner thereto. 
         [0065]    As already mentioned in the introduction with reference to  FIG. 2 , a second image value of the reconstructed pixel is used for the prediction in  FIG. 6 , for example the second image value W 21  of the reconstructed pixel BR 1  in order to generate a prediction value for a first image value at position e 2 . Thus, only reconstructed pixels according to the hatched pixels in  FIG. 6  are used in this case. 
         [0066]    Analogously to the preceding exemplary embodiments, after the prediction value for the first image value has been determined an associated reconstructed image value WR can be determined and used for the following prediction step. For example, a prediction value is determined for the first image value at the position b 1 . After generation of the associated differential value of the coding and decoding a second image value is generated for the reconstructed pixel at position b 1 . This second image value is then used for determining a prediction value for the first image value at the position c 2 , instead of the second image value of the reconstructed pixel from the position a 1 . This procedure can also be applied analogously for other first pixels requiring to be coded along the respective trajectory. This approach can also find application for other embodiment variants. 
         [0067]    The embodiment variants described can be implemented and executed with the aid of specific devices, see  FIG. 7 . The devices VOR have units E 1 , E 2 , E 3 , E 4 , EW which realize and perform individual steps of the embodiment variants. In this case the units can be realized and embodied in software, in hardware and/or in a combination of software and hardware. In such an arrangement the units can run on a processor, in which case individual steps of the method can be stored in a memory and loaded into the processor. The image values, such as the first, second and third image values, and other information relating to the image, as well as further operations for coding and decoding image values can also be stored in the memory. 
         [0068]    The invention has been described in detail with particular reference to preferred embodiments thereof and examples, but it will be understood that variations and modifications can be effected within the spirit and scope of the invention covered by the claims which may include the phrase “at least one of A, B and C” as an alternative expression that means one or more of A, B and C may be used, contrary to the holding in  Superguide V. DIRECTV,  69 USPQ2d 1865 (Fed. Cir. 2004).