Abstract:
A method of generating an upsampled target pixel positioned between two lines of input source data includes the step of comparing pixels of different lines of the source data in a region surrounding the upsampled target pixel to be generated in at least two different directions. An interpolation direction based on the comparison is selected and interpolations between selected pixels of the source data in the determined interpolation direction are carried out to compute intermediate pixels on a line segment passing through the upsampled target pixel. An interpolation between the intermediate pixels is carried out to generate the upsampled target pixel. An apparatus for performing the method is also disclosed.

Description:
This application is a continuation application Ser. No. 08/555,289 , filed Nov. 8, 1995, now U.S. Pat. No. 5,991,463. 
    
    
     FIELD OF THE INVENTION 
     The present invention relates to data interpolation and in particular to a method of generating an upsampled target pixel from input source data and an apparatus for performing the method. 
     BACKGROUND OF THE INVENTION 
     Video images can be represented as a two-dimensional array of digital data with each data point in the array representing a pixel of the digitized video image. The value assigned to each pixel determines its intensity and/or colour when the video image is recreated. In the video imaging art, it is often desired to magnify a video image to arbitrary magnification factors to create enlarged video images. When creating an enlarged image from an original image represented by a digital data array, it is necessary to interpolate between pixels of the original digital data array to generate upsampled pixels between consecutive lines and pixels of the original digital data array to “fill” in pixels of the enlarged image. Prior art techniques to create these enlarged video images have been considered. 
     It is common practice in the prior art to use an orthogonal, Cartesian approach to interpolate separately the vertical and horizontal dimensions of the digitized video image to be enlarged. However, this technique typically results in enlarged video images which suffer from jagged edges commonly referred to as “stairstepping”. Improvements in the interpolation method used may reduce the stairstepping, but it cannot be completely avoided because it is inherent when using this technique. 
     A directional interpolation scheme addresses the stairstepping problem. Directional interpolation recognizes the geometric structure in images. With directional interpolation, it has been found that interpolation along the edges produces improved results over interpolation across the edges. Directional interpolation involves analysing local image structure and performing the interpolation based on the image structure. 
     U.S. Pat. No. 5,019,903 to Dougall et al. discloses an apparatus for directionally interpolating between lines of a supersampled digital signal. The apparatus calculates gradient vectors for use in directionally interpolating a vertically upsampled line. This operation makes the apparatus best suited for line-doubling deinterlacing applications. 
     U.S. Pat. No. 5,347,599 to Yamashita et al. discloses an adaptive interpolation method and an apparatus using correlation detection. The apparatus performs calculations on lines of pixels of the source data to select the desired upsampling direction. However, similar to Dougall et al, this apparatus is also best suited for line-doubling deinterlacing applications. 
     Although Dougall et al. and Yamashita et al. disclose alternative directional interpolation methods to generate upsampled pixels, their design is such as to support only fixed, integral vertical resize factors. Accordingly, there exists a need for an improved interpolation method and apparatus that supports arbitrary, fractional resize factors in both vertical and horizontal dimensions. 
     It is therefore an object of the present invention to provide a novel method and apparatus for generating an upsampled target pixel from input source data. 
     SUMMARY OF THE INVENTION 
     The present invention performs directional interpolation to arbitrary, fractional resize factors. First, an interpolation direction is selected corresponding to any low-frequency edges in the source data. Next, directional interpolation is performed to generate intermediate pixels. The intermediate pixels are then interpolated, possibly non-orthogonally, to generated the desired upsampled pixel. 
     More specifically, according to one aspect of the present invention there is provided a method of generating an upsampled target pixel from input source data comprising the steps of: 
     (i) comparing pixels of different lines of said source data in a region surrounding an upsampled target pixel to be generated in at least two different directions; 
     (ii) selecting an interpolation direction based on the comparisons of step (i); 
     (iii) interpolating between selected pixels of different lines of said source data in the interpolation direction determined at step (ii) and computing intermediate pixels on a line segment passing through said upsampled target pixel; and 
     (iv) interpolating between the intermediate pixels to generate said upsampled target pixel. 
     In the preferred embodiment, the line segment is parallel to the lines of the source data. Restricting the line segment to be horizontal as such, greatly simplifies the calculation of the intermediate pixels and the upsampled target pixel. 
     In one possible embodiment, pixels of different lines of source data are compared in three different directions, including a vertical direction, and opposite oblique directions forming an angle with the vertical direction that is in the range 0&lt;angle&lt;90°. During the comparisons of step (i), difference values between the compared pixels are generated, the difference values being used to select the interpolation direction at step (ii). 
     In this embodiment, prior to step (ii), the difference values resulting from the comparisons in the three directions are compared to determine whether the differences therebetween are within a threshold. The direction associated with the smallest difference value is selected as the interpolation direction when none of the differences are within the threshold. When the differences between the difference values resulting from the comparisons in all three directions are within the threshold, the vertical direction is selected as the interpolation direction. When the difference between the difference values resulting from the comparisons in the vertical direction and only one of the oblique directions is within the threshold, that oblique direction is selected as the interpolation direction. When the difference between the difference values resulting from the comparison in the two oblique directions is within the threshold, additional pixels of the different lines of source data are compared in the opposite oblique directions. The difference values generated as a result of these comparisons are compared. When the difference between the difference values resulting from the comparisons of the additional pixels is within the threshold, the vertical interpolation direction is selected as the interpolation direction. 
     In another embodiment the line segment is once again parallel to the lines of the source data but this time pixels of the different lines of source data are compared in seven directions are at step (i). These directions include the vertical direction and three pairs of opposite oblique directions forming varying angles with the vertical direction that are within the range 0&lt;angle&lt;90°. Difference values between the compared pixels of step (i) are calculated. 
     In this embodiment, the set of difference values to the left of the set under consideration and the set to the right are also examined. The three difference values for each possible oblique interpolation direction are summed and compared to determine if the differences therebetween are within a threshold. When none of the differences are sufficiently small to indicate a low-frequency edge in the source image, then the vertical direction is selected as the interpolation direction. When none of the differences are within the threshold, then the oblique direction associated with the smallest difference value is selected as the interpolation direction. When difference values associated with a “right-ward” oblique direction and a “left-ward” oblique direction are within the threshold, then the vertical direction is once again selected as the interpolation direction. Otherwise one of the oblique directions is selected. 
     According to another aspect of the present invention there is provided an apparatus for generating an upsampled target pixel from input source data comprising: 
     comparison means for comparing pixels of different lines of said source data in a region surrounding an upsampled target pixel to be generated, in at least two different directions; 
     selection means for selecting an interpolation direction in response to said comparison means; and 
     upsampling means for interpolating between selected pixels of different lines of said source data in the interpolation direction selected by said selection means to compute intermediate pixels on a line segment passing through said upsampled target pixel and for interpolating between the intermediate pixels to generate said upsampled target pixel. 
     The present invention provides advantages in that upsampled target pixels can be generated to allow large magnified images to be created with reduced stairstepping, particularly in the case of large magnification factors. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     Embodiments of the present invention will now be described more fully with reference to the accompanying drawings in which: 
     FIG. 1 is a diagram showing the pixels of three consecutive lines of video image source data, the position of an upsampled target pixel to be generated and the region surrounding pixels of the source data used to generate the upsampled target pixel; 
     FIG. 2 is a diagram showing the comparisons that are made between pixels of the source data in order to determine the interpolation direction to be used when generating an upsampled target pixel; 
     FIG. 3 is a diagram illustrating additional comparisons that are made between pixels of the source data when comparisons in two oblique directions yield similar values; 
     FIG. 4 is a diagram showing a vertical upsampling technique used to generate an upsampled target pixel; 
     FIG. 5 is a diagram showing a negative slope oblique upsampling technique used to generate an upsampled target pixel; 
     FIG. 6 is a diagram showing a positive slope oblique upsampling technique used to generate an upsampled target pixel; 
     FIGS. 7 a  and  7   b  are flowcharts showing the steps performed in the first method when generating an upsampled target pixel from the source data; 
     FIG. 8 is a block diagram showing an apparatus for generating upsampled target pixels from input source data; 
     FIG. 9 is a schematic of a delay circuit forming part of the apparatus illustrated in FIG. 8; 
     FIG. 10 is a schematic of a decision circuit forming part of the apparatus illustrated in FIG. 8; 
     FIG. 11 is a schematic of a β calculator forming part of the apparatus illustrated in FIG. 8; 
     FIG. 12 is a schematic of an oblique upsampler forming part of the apparatus illustrated in FIG. 8; 
     FIG. 13 is a diagram illustrating the comparisons between source pixels made in determining the interpolation direction for a second embodiment; 
     FIG. 14 is a diagram illustrating a boundary crossing situation; 
     FIG. 15 is a diagram showing a vertical upsampling technique used to generate an upsampled target pixel; 
     FIG. 16 is a diagram showing a positive 45° slope oblique upsampling technique used to generate an upsampled target pixel; 
     FIG. 17 is a diagram showing a negative 45° slope oblique upsampling technique used to generate an upsampled target pixel; 
     FIG. 18 is a diagram showing the source pixels used in a 26.6° slope oblique upsampling technique. 
     FIG. 19 is a diagram showing a positive 26.6° slope oblique upsampling technique used to generate an upsampled target pixel; 
     FIG. 20 is a diagram showing a negative 26.6° slope oblique upsampling technique used to generate an upsampled target pixel; 
     FIG. 21 is a diagram showing a positive 63.4° slope oblique upsampling technique used to generate an upsampled target pixel; 
     FIG. 22 is a diagram showing a negative 63.4° slope oblique upsampling technique used to generate an upsampled target pixel; 
     FIGS. 23 a  and  23   b  are flowcharts showing the steps performed in a second method when generating an upsampled target pixel from the source data; 
     FIG. 24 is a block diagram showing a second apparatus for generating upsampled target pixels from input source data; 
     FIG. 25 is a schematic of a delay circuit forming part of the apparatus illustrated in FIG. 24; 
     FIG. 26 is a schematic of a decision circuit forming part of the apparatus illustrated in FIG. 24; 
     FIG. 27 is a schematic of a β calculator forming part of the apparatus illustrated in FIG. 24; and 
     FIG. 28 is a schematic of an oblique upsampler forming part of the apparatus illustrated in FIG.  24 . 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     When upsampling input video image digital source data to create an enlarged video image, it is necessary to generate upsampled target pixels between the lines and pixels of the digital source data. The resize factor and the resize direction (i.e. vertical and/or horizontal) determine the number as well as the position of the upsampled target pixels to be generated. 
     In order to reduce stairstepping and create enlarged video images of high resolution, it is necessary to calculate accurately the values for the various upsampled target pixels to be generated. Thus, the upsampling interpolation direction used to generate the values of the upsampled target pixels should be selected to achieve this goal. Failure to select an upsampling interpolation direction which results in accurate values for the upsampled target pixels will result in the generation of enlarged images with noticeable stairstepping. 
     The present method and apparatus generates an upsampled target pixel by calculating the difference in values of pixels of the digital source data in a region surrounding the upsampled target pixel to be generated in a number of directions. The calculated difference values are then examined in order to select an interpolation direction. Interpolations between selected pixels of the digital source data in the determined interpolation direction are then performed to generate intermediate pixels on a line segment that passes through the upsampled target pixel to be generated. Restricting the line segment to be parallel to the source data—that is, horizontal—simplifies the calculation of the intermediate pixels. Interpolations between the intermediate pixels are then performed to generate the upsampled target pixel. 
     An embodiment of the present method of generating an upsampled target pixel from input source data will now be described with particular reference to FIGS. 1 to  7   b.    
     When an upsampled target pixel w is to be generated, the closest pixel to the upsampled target pixel in the digital source data is determined and is used as a reference pixel P R  in the interpolation method. The two consecutive lines of source data between which the upsampled target pixel is located are also determined. The reference pixel, the adjacent pixel on the same line of source data as the reference pixel P R  and the two pixels on the other line of source data that form a rectangular region R surrounding the upsampled target pixel are determined (see block  50  in FIG. 7 a ). The four source pixels that define the boundary of region R are used initially to determine the interpolation direction as will be described. The region R may correspond to any one of the four quadrants, namely top-left, top-right, bottom-left or bottom-right surrounding the reference pixel P R . 
     FIG. 1 shows a small segment of digital source data. The source pixels are labelled relative to the reference pixel P R =U 00 . The first line of source data is represented by five pixels U -1-2  to U -12 , the second line of source is represented by pixels U 0-2  to U 02  and the third line of source is represented by pixels U 1-2  to U 12 . Clearly, pixel U 00  is the closest pixel to upsampled target pixel w and is the designated reference pixel P R . In this example, the upsampled target pixel w is positioned between the first and second lines in the top-left quadrant of region R. Pixels U -1-1 , U -10 , U 0-1  and U 00  are the pixels that define the region R surrounding the upsampled target pixel w and are used in the interpolation direction making decision. The following chart shows the pixels of the source data that define the region R in the four quadrants surrounding the reference pixel: 
     
       
         
               
               
               
             
           
               
                   
                   
               
               
                   
                 Quadrant 
                 Pixels in Region R 
               
               
                   
                   
               
             
             
               
                   
                 Top-Left 
                 U 00 , U 0-1 , U −1-1 , U −10   
               
               
                   
                 Top-Right 
                 U 00 , U 01 , U −11 , U −10   
               
               
                   
                 Bottom-Left 
                 U 00 , U 0-1 , U 1-1 , U 10   
               
               
                   
                 Bottom-Right 
                 U 00 , U 01 , U 11 , U 10   
               
               
                   
                   
               
             
          
         
       
     
     Once the four pixels of region R have been determined, calculations are performed corresponding to three interpolation directions (see block  52 ). In the example of FIG. 1, region R is defined by pixels: U -1-1 , U -10 , U 0-1  and U 00  and the following calculations are performed: 
     
       
         
               
               
               
               
             
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 Calculation 
                 Associated Interpolation Direction 
                   
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 abs[U 00  − U −1-1 ] 
                 oblique 45° line up-left 
                 O L   
                 (1) 
               
               
                   
                 abs[U 0-1  − U −10 ] 
                 oblique 45° line up-right 
                 O R   
                 (2) 
               
               
                   
                 abs[U 00  − U −10]   
                 vertical 
                 V 
                 (3) 
               
               
                   
                   
               
             
          
         
       
     
     FIG. 2 illustrates the interpolation directions O L , O R  and V associated with the three calculations performed on pixels U -1-1 , U -10 , U 0-1  and U 00 . Similar calculations apply for the other three quadrants. 
     The calculation which yields the smallest difference value is usually associated with the interpolation direction which will yield an upsampled target pixel w having a value which is most similar to the values of the surrounding pixels of the source data. However before the interpolation direction is selected based on the results of these calculations, the calculated difference values are compared with each other to determine whether the differences are within a threshold of one another (see blocks  54  and  56 ). 
     If one of the calculated difference values is clearly smaller than the other two values, the interpolation direction associated with the smallest calculated value is selected (block  58 ). If all three calculated difference values are within the threshold, the vertical interpolation direction V is selected (blocks  66  and  68 ). 
     If the calculated difference value associated with the vertical interpolation direction V and the calculated difference value associated with only one of the oblique directions O L  or O R  are within the threshold of one another, the oblique interpolation direction is selected (blocks  70  and  72 ). 
     In the case where the calculated difference values associated with the two oblique interpolation directions O L  and O R  are within the threshold of one another, it is important to select the proper interpolation direction since an incorrect decision will yield an enlarged image with noticeable discontinuities in diagonal lines. To assist in the selection process, calculations using additional pixels from the same lines of source data are performed (block  74 ). FIG. 3 shows these additional calculations for the example of FIGS.  1  and  2 : 
     
       
         
               
               
               
               
             
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 Calculation 
                 Associated Interpolation Direction 
                   
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 abs[U 00  − U −11 ] 
                 oblique 45° up-right 
                 O1 AR   
                 (4) 
               
               
                   
                 abs[U 0-1  − U −1-2 ] 
                 oblique 45° up-left 
                 O1 AL   
                 (5) 
               
               
                   
                   
               
             
          
         
       
     
     These additional calculated difference values are then compared to determine if they are within the threshold of one another (block  76 ). If one of these difference values is clearly smaller than the other, the oblique interpolation direction O L  or O R  associated with that calculated difference value is selected (block  58 ). However, if these two additional calculated difference values are within the threshold of one another, the additional following calculations using additional pixels from the same lines of source data are performed (block  78 ): 
     
       
         
               
               
               
               
             
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 Calculation 
                 Associated Interpolation Direction 
                   
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 abs[U 0-2  − U −1-1 ] 
                 oblique 45° up-right 
                 O2 AR   
                 (6) 
               
               
                   
                 abs[U 01  − U −10 ] 
                 oblique 45° up-left 
                 O2 AL   
                 (7) 
               
               
                   
                   
               
             
          
         
       
     
     Similarly, these additional calculated difference values are compared to determine if they are within the threshold of one another (block  80 ). If one of these difference values is clearly smaller than the other, the oblique interpolation direction O L  or O R  associated with that calculated difference value is selected (block  58 ). However, if these two additional calculated difference values are within the threshold of one another, the vertical interpolation direction V is selected as a default to avoid the resolution problems which would occur if the incorrect oblique interpolation direction was selected (block  82 ). 
     Once the interpolation direction is determined, selected pixels of the source data are determined based on the interpolation direction (block  60 ) and the interpolation direction is used to interpolate between the selected pixels of the source data to generate intermediate pixels v (block  62 ). The intermediate pixels are then interpolated horizontally to generate the upsampled target pixel w (block  64 ). 
     Before the upsampled target pixel w can be generated, the location of the upsampled target pixel w must be determined. The upsampled target pixel w is defined by its distances from the reference pixel P R  both in the vertical and horizontal directions. These distances are represented by the terms α y  and α x  where: 
     −0.5&lt;α y ≦0.5; and 
     −0.5&lt;α x ≦0.5; 
     α y  being positive downward and α x  being positive to the right. The signs of α y  and α x  are related to the quadrant as follows: 
     
       
         
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 Quadrant 
                 α x   
                 α y   
               
               
                   
                   
               
             
             
               
                   
                 Top-Left 
                 α x  &lt; 0 
                 α y  &lt; 0 
               
               
                   
                 Top-Right 
                 α x ≧ 0   
                 α y  &lt; 0 
               
               
                   
                 Bottom-Left 
                 α x  &lt; 0 
                 α y  ≧ 0 
               
               
                   
                 Bottom-Right 
                 α x  ≧ 0 
                 α y  ≧ 0 
               
               
                   
                   
               
             
          
         
       
     
     With the values of α x  and α y  known, interpolations are performed between the selected pixels of the source data in the determined interpolation direction. The resulting intermediate pixels v, are positioned on a horizontal line segment which passes through the upsampled target pixel w. In the present embodiment linear upsampling is described, however higher orders of interpolation can be used. 
     FIG. 4 shows an upsampled target pixel w positioned in the bottom-right quadrant. In this case, both α x  and α y  are positive. The region R is defined by pixels U 00 , U 01 , U 10  and U 11  and pixel U 00  defines the reference pixel P R . Intermediate pixels v 0 , v 1 , and v 2  are also shown and have been computed using linear upsampling in the vertical direction. The internediate pixels v 0 , v 1  and v 2  in this case are computed using the following equations: 
     
       
           v   0 =(1−α y ) U   0-1 +α y   U   1-1   (8)  
       
     
     
       
           v   1 =(1−α y ) U   00 +α y   U   10   (9)  
       
     
     
       
           v   2 =(1−α y ) U   01 +α y   U   11   (10)  
       
     
     After the three upsampled intermediate pixels have been computed, interpolations are performed orthogonally horizontally between the two intermediate pixels on opposite sides of the upsampled target pixel w to determine the value of the upsampled target pixel. Therefore, before the upsampled target pixel w can be computed, it is necessary to determine which two intermediate pixels to select. In order to select the intermediate pixels, the term β is defined as the horizontal distance from the middle intermediate pixel v 1  to the upsampled target pixel w. The term β. is positive to the right. For vertical interpolation, β=α x . The sign of β determines which two intermediate pixels surround the target pixel w. In the example of FIG. 4, β≧2 0 so the interpolation is performed between v 1  and v 2 . The value of the upsampled target pixel w is computed using the following equation: 
     
       
           w =(1−α x ) v   1 +α x   v   2   (11)  
       
     
     In other quadrants, that is, cases for α y  and α x , the intermediate pixels v and the upsampled target pixel w are calculated in a similar manner using different pixels of the source data that surround the reference pixel P R . 
     When the oblique up-left interpolation direction O L  is selected, the intermediate pixels v 0 , v 1  and v 2  are computed by interpolating linearly between selected pixels of the source data along negatively sloped diagonal lines. When linearly interpolating, the important parameter is the ratio of the distance of the interpolated pixel endpoints. Since the lines of source data and the horizontal line segment defined by the intermediate pixels are parallel, the intermediate pixels can be defined by α y , similar to the vertical upsampling case. 
     FIG. 5 shows the case of an upsampled target pixel w positioned in the bottom-right quadrant with α y  and α x  once again positive. Region R is defined by pixels U 00 , U 01 , U 10  and U 11  with pixel U 00  defining the reference pixel P R  Intermediate pixels v 0 , v 1 , and v 2  are also shown and have been computed using oblique up-left interpolation. The intermediate pixels v 0 , v 1  and v 2  are computed using the following equations: 
     
       
           v   0 =(1−αa y ) U   0-1 +α y   U   10   (12)  
       
     
     
       
           v   1 =(1−α y ) U   00 +α y   U   11   (13)  
       
     
     
       
           v   2 =(1−α y ) U   01 +α y   U   12   (14)  
       
     
     After the three upsampled intermediate pixels have been computed, interpolations are performed non-orthogonally horizontally between the two intermediate pixels on opposite sides of the upsampled target pixel w to determine the value of the upsampled target pixel. In the example of FIG. 5, since upsampling has been performed along 45° diagonal lines, the horizontal distance from intermediate pixel v 1  to reference pixel U 00  is the same as the vertical distance, namely α y . Thus, the distance β from the upsampled target pixel w to the intermediate pixel v 1  is equal to α x −α y . In fact this equation for β in oblique up-left upsampling is valid for all quadrants. −β is negative in this case implying that the interpolation is between intermediate pixels v 1  and v 0 . Therefore, the value of the upsampled target pixel w is computed using the following equation: 
     
       
           w =(1−(−β)) v   1 +(−β) v   0   (15)  
       
     
     In other quadrants, the intermediate pixels v and the upsampled target pixel w are calculated in a similar manner using different selected pixels of the source data that surround the reference pixel P R . 
     When the oblique up-right interpolation direction O R  is selected, the intermediate pixels v 0 , v 1  and v 2  are computed by interpolating linearly between selected pixels of the source data located along positively sloped diagonal lines in a similar manner to that described above with reference to FIG.  5 . 
     FIG. 6 shows an upsampled target pixel w positioned in the region R defined by pixels U 00 , U 01 , U 10  and U 11  with pixel Use defining the reference pixel PR Intermediate pixels v 0 , v 1  and v 2  are also shown and have been computed using oblique up-right interpolation. The intermediate pixels v 0 , v 1  and v 2  are computed using the following equations: 
     
       
           v   0 =(1−α y ) U   01 +α y   U   1-2   (16)  
       
     
     
       
           V   1 =(1−α y ) U   00 +α y   U   1-1   (17)  
       
     
     
       
           v   2 =(1−α y ) U   01 +α y   U   10   (18)  
       
     
     After the three upsampled intermediate pixels have been computed, interpolations are performed non-orthogonally horizontally between the two intermediate pixels on opposite sides of the upsampled target pixel w to determine the value of the upsampled target pixel. For oblique up-right upsampling it can be shown that β=α x +α y . In the case of FIG. 6, β is positive implying that the interpolation is between intermediate pixels v 1  and v 2 . The value of the upsampled target pixel w is computed using the following equation: 
     
       
           w =(1−β) v   1   +βv   2   (19)  
       
     
     In other quadrants, the intermediate pixels v and the upsampled target pixel w are calculated in a similar manner using different selected pixels of the source data that surround the reference pixel P R . 
     The above-described method shows access to three lines of source data to demonstrate the cases for the four possible quadrants. It should be noted, however, that once the upsampling quadrant is known only two lines of source data are needed to perform the interpolations and generate the upsampled target pixel. 
     Referring now to FIG. 8, a source data interpolation apparatus for carrying out the above described method is shown and is generally indicated by reference numeral  100 . The apparatus  100  receives a stream of input digital source data D in  and interpolates between selected pixels U of the source data in order to generate upsampled target pixels w. 
     The apparatus  100  includes a delay circuit  102  receiving the stream of source data. The delay circuit extracts the required pixels of the source data necessary to generate the desired upsampled target pixel w and passes the required pixels of source data to a decision circuit  104  as well as to an oblique upsampler  106 . The decision circuit  104  performs calculations numbered 1 to 3 and 4 to 7 on the pixels of source data if necessary and compares the calculated difference values with the threshold to determine the desired interpolation direction. The interpolation direction output of the decision circuit  104  is fed to the oblique upsampler  106  and to a β calculator  108 . The output of the β calculator  108  is applied to the oblique upsampler  106  which uses the input data to generate the desired upsampled target pixel w. 
     FIG. 9 better illustrates the delay circuit  102 . As can be seen, the delay circuit has an input line  112  receiving the stream of input source data necessary to generate the desired upsampled target pixel w. The input line branches, with one branch  114  leading directly to three delay elements  120 ,  122  and  124  connected in series. The other branch  116  leads to a line store  126 . The output of the line store  126  leads to three delay elements  128 ,  130  and  132  connected in series. The line store and the delay elements in each branch allow the delay circuit  102  to output four pixels from two consecutive lines of input source data simultaneously. For the case of interpolating in the bottom-right quadrant, with both α x  and α y  positive, the eight pixels extracted correspond to pixels U 0-1 , U 00 , U 01 , U 02 , U 1-1 , U 10 , U 11 , and U 12  as shown. 
     The decision circuit  104  is best seen in FIG.  10  and has six input lines, each of which receives a selected pixel output by the delay circuit  102 . The inputs are applied pairwise to subtracters  140 ,  146 , and  150 . The outputs of the subtracters are applied through delay elements  142 ,  144 ,  148 ,  152  and  154  to the selection logic  156  and represent the difference value results of calculations numbered 1 to 3. The delay elements are necessary in order provide the difference value results corresponding to calculations numbered 4 to 7. Specifically, the output of subtracter  140 , corresponds to O1 AR , a “future” value of O R . This value is applied to delay element  142  to give O R , which is then applied to delay element  144  to give O2 AR . Likewise, the output of subtracter  150  corresponding to O2 AL , is applied to delay element  152  to give O L  which is then applied to delay element  154  to give O1 AL . To “equalize” the latency, delay element  148  is necessary to delay the output of subtracter  146 . This value corresponds to V. All these values are passed to the selection logic  156 . 
     The selection logic  156  which receives the q and a constants as well as the threshold value compares the calculated difference values to determine if any two or all three calculated values are within the threshold. In the cases where clearly one calculated difference value is the smallest where the calculated difference value associated with the vertical interpolation direction and the calculated difference value associated with only one oblique interpolation direction are both within the threshold; or all three-calculated difference values are within the threshold, the selection logic  156  outputs the selected interpolation direction to the β calculator  108  as well as to the oblique upsampler  106 . In the case where the calculated difference values associated with the two oblique directions are within the threshold, the values O1 AR  and O1 AL  and possibly O2 AR  and O2 AL  are used to determine which interpolation direction to output to the β calculator  108  and to the oblique upsampler  106 . 
     The source pixels shown in FIG. 10 correspond to the source pixels used in interpolating in the bottom-right quadrant. These source pixels represent the “future” value of the differences. 
     The β calculator  108  is best seen in FIG.  11  and includes a multiplexer  160  which receives the α y  and −α y  constants as well as the interpolation direction output by the selection logic  156 . The multiplexer output is supplied to an adder  162  which also receives the α x  constant. The output of the adder  162  constitutes the β constant output of the β calculator  108 . 
     FIG. 12 best illustrates the oblique upsampler  106  and as can be seen it comprises three linear interpolators  106   a ,  106   b  and  106   c , although in principle higher order interpolations could be used. Each linear interpolator includes two adders and a multiplier. Two linear interpolators are used for directional interpolation and one for horizontal interpolation. The oblique upsampler also includes four multiplexers  165  to  168 , which receive the sign of the β constant and four multiplexers  170  to  176 , each of which receives the interpolation direction from the selection logic  156 . Multiplexers  165  and  166  provide output to multiplexer  170  and multiplexers  167  and  168  provide output to multiplexer  172 . 
     The source pixels input to multiplexers  165  to  168  and multiplexers  174  to  176  illustrate the case for interpolating the bottom right quadrant. Multiplexers  170  and  172  provide output to linear interpolator  106   a . Linear interpolator  106   a  includes an adder  178  receiving input from multiplexers  170  and  172  which supplies input to a multiplier  180 . The multiplier  180  which receives the α y  constant provides input to another adder  182  which also receives input from multiplexer  172 . 
     Similarly, multiplexers  174  and  176  provide output to linear interpolator  106   b . Linear interpolator  106   b  includes an adder  184  receiving input from multiplexers  174  and  176  which supplies input to a multiplier  186 . The multiplier  186  which receives the α y  constant provides input to another adder  188  which also receives input from multiplexer  176 . 
     The output of the two linear interpolators  106   a  and  106   b  respectively are supplied to linear interpolator  106   c . Linear interpolator  106   c  includes an adder  190  receiving input from the adders  182  and  188  which supplies input to multiplier  192 . The multiplier  192  receives the β constant from the β calculator  108  and supplies input to adder  194 . Adder  194  also receives the output of adder  188  and generates as its output the value of the upsampled target pixel w. 
     The input pixels and shifting of the multiplexers  174  and  176  are controlled so that the output of adder  188  represents intermediate pixel v 1  (i.e. the intermediate pixel closest to the reference pixel PR). The input pixels and shifting of the multiplexers  165  to  168 ,  170  and  172  are controlled so that the output of adder  182  represents either intermediate pixel v 0  or intermediate pixel v 2  depending upon the position of the upsampled target pixel w on the intermediate line segment. The designators V, O R  and O L  input to multiplexers  170  to  176  in FIG. 12 refer to the source pixels that are used to interpolate in the vertical, oblique right and oblique left directions respectively. 
     The linear interpolator  106   c  constituted by adders  190  and  194  and multiplier  192  performs the calculation representing the non-orthogonal horizontal interpolation between the intermediate pixels. 
     The following chart sets out the directional interpolations performed by the oblique upsampler  106  for all values of α x  and α y  in order to generate the intermediate pixels v. The value of β for each interpolation direction is also included. 
     
       
         
               
               
               
               
             
           
               
                   
               
               
                   
                   
                 Intermediate 
                   
               
               
                 Interpolation 
                   
                 Pixels 
               
               
                 Direction 
                 α y   
                 v 0 , v 1 , v 2   
                 β 
               
               
                   
               
             
             
               
                 Vertical 
                 α y  ≧ 0 
                 v 0  = u 0-1  + (u 1-1  − u 0-1 )α y   
                 β = a x   
               
               
                   
                   
                 v 1  = u 00  + (u 10  − u 00 )α y   
               
               
                   
                   
                 v 2  = u 01  + (u 11  − u 01 )α y   
               
               
                   
                 α y  &lt; 0 
                 v 0  = u 0-1  + (u −1-1  − u 0-1 )(−α y ) 
               
               
                   
                   
                 v 1  = u 00  + (u −10  − u 00 )(−α y ) 
               
               
                   
                   
                 v 2  = u 01  + (u −11  − u 01 )(−α y ) 
               
               
                 Oblique Up-Left 
                 α y  ≧ 0 
                 v 0  = u 0-1 + (u   10  − u 0-1 )α y   
                 β = α x  − a y   
               
               
                   
                   
                 v 1  = u 00  + (u 11  − u 00 )α y   
               
               
                   
                   
                 v 2  = u 01  + (u 12  − u 01 )α y   
               
               
                   
                 α y  &lt; 0 
                 v 0  = u 0-1  + (u −1-2  − u 0-1 )(−α y ) 
               
               
                   
                   
                 v 1  = u 00  + (u −10  − u 01 )(−α y ) 
               
               
                   
                   
                 v 2  = u 01  + (u −10  − u 01 )(−β y ) 
               
               
                 Oblique Up-Right 
                 α y  ≧ 0 
                 v 0  = u 0-1  + (u 1-2  − u 0-1 )α y   
                 β = α x  + α y   
               
               
                   
                   
                 v 1  = u 00  + (u 1-1  − u 00 )α y   
               
               
                   
                   
                 v 2  = u 01  + (u 01  − u 01 )α y   
               
               
                   
                 α y  &lt; 0 
                 v 0  = u 0-1  + (u −10  − u 0-1 )(−α y ) 
               
               
                   
                   
                 v 1  = u 00  + (u −11  − u 00 )(−α y ) 
               
               
                   
                   
                 v 2  = u 01  + (u −12  − u 01 )(−α y ) 
               
               
                   
               
             
          
         
       
     
     As one of skill in the art will appreciate, once the intermediate pixels v and the value of β are known, the upsampled target pixel w can be generated by horizontal interpolation using one of the following equations: 
     
       
           w=v   1 +( v   2   −v   1 )β; β≧0  (20)  
       
     
     
       
           w=v   1 +( v   0   −v   1 )(−β); β&lt;0  (21)  
       
     
     Referring now to FIGS. 13 to  28 , another embodiment of a method for generating upsampled target pixels using seven possible interpolation directions and a four-point interpolator will now be described. 
     Similar to the previous embodiment, the input source data is examined to determine the closest source pixel to the upsampled target pixel w and that source pixel is used as a reference pixel P R . Source pixels from the two source lines above the upsampled target pixel, and th e two source lines below the upsampled target pixel are determined (see block  210  in FIG. 23 a ) and selected pixels of the source lines are compared to determine the interpolation direction to be selected where generating the upsampled target pixel. The source pixels are used to calculate difference values for six possible oblique directions (block  212 ). The calculations vary depending upon the quadrant of interpolation and are shown in the following chart: 
     
       
         
               
               
               
               
               
             
               
               
               
               
               
               
               
             
           
               
                   
               
               
                 Top-Left 
                 Top-Right 
                 Bottom-Left 
                 Bottom-Right 
                 Associated Interpolation Direction 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 abs[U 0-1  − U −10 ] 
                 abs[U 00  − U −11 ] 
                 abs[U 00  − U 1-1 ] 
                 abs[U 01  − U 10 ] 
                 45° line up-right 
                 O UR   
                 (1) 
               
               
                 abs[U 00  − U −1-1 ] 
                 abs[U 01  − U −10 ] 
                 abs[U 0-1  − U 10 ] 
                 abs[U 00  − U −11 ] 
                 45° line up-left 
                 O UL   
                 (2) 
               
               
                 abs[U 0-1  − U −11 ] 
                 abs[U 00  − U −12 ] 
                 abs[U 00  − U 1-2 ] 
                 abs[U 01  − U 1-1 ] 
                 26.6° line up-right-right 
                 O URR   
                 (3) 
               
               
                 abs[U 00  − U −1-2 ] 
                 abs[U 01  − U −1-1 ] 
                 abs[U 0-1  − U 11 ] 
                 abs[U 00  − U 12 ] 
                 26.6° line up-left-left 
                 O ULL   
                 (4) 
               
               
                 abs[U 1-1  − U −10 ] 
                 abs[U 00  − U −21 ] 
                 abs[U 00  − U 2-1 ] 
                 abs[U −11  − U 10 ] 
                 63.4° line up-up-right 
                 O UUR   
                 (5) 
               
               
                 abs[U 00  − U −−2-1 ] 
                 abs[U 11  − U −10 ] 
                 abs[U −1-1  − U −10 ] 
                 abs[U 00  − U 21 ] 
                 63.4° line up-up-left 
                 O UUL   
                 (6) 
               
               
                   
                   
                   
                   
                 vertical 
                 V 
                 (7) 
               
               
                   
               
             
          
         
       
     
     The interpolation directions O UR , O UL , O URR , O UUL , O UUR , O UUL  and V are illustrated in FIG. 13 for the top-left quadrant. No difference values are calculated for the vertical direction V shown. 
     The calculations yield a set of difference values associated with each oblique interpolation direction. The set of difference values to the right of the reference pixel under consideration and the set of difference values to the left of the reference pixel are also used. The three sets of difference values are summed for each oblique interpolation direction yielding a “working” set of difference values. The difference values of this working set are compared with each other to determine the smallest differences within a threshold (blocks  214  and  216 ). If the smallest differences are sufficiently small to indicate low-frequency edges then they yield a set of possible interpolation directions. 
     The possible interpolation directions are then examined to see if a “boundary crossing” situation occurs (blocks  218  and  220 ). FIG. 14 demonstrates this situation. Here the up-left-left direction representing a white line joining pixels U 00  and U -1-2  is being considered, however there is a dark grey “boundary” joining pixels U 0-1 , and U -1-1 . Selecting the up-left-left direction would cross the boundary, and therefore the up-left-left direction can not be considered. This situation is detected by examining differences B 1  and B 2 . 
     The possible interpolation directions are then examined and a single interpolation direction is selected (block  222 ). Block  222  is expanded in FIG. 23 b . If only one oblique interpolation direction is possible then that direction is chosen (blocks  230  and  232 ). If no low-frequency edges are detected then the vertical interpolation direction is chosen as default (blocks  238  and  240 ). If both a leftward and a rightward oblique interpolation direction are possible, then the vertical direction is again chosen as default (blocks  248  and  250 ). 
     Otherwise only either rightward or leftward oblique interpolation directions are under consideration. If only one of the “extreme” directions (either 26.6° or 63.4° obliques) and the 45° oblique direction are possible then that extreme direction is chosen (blocks  252  and  254 ). Otherwise both extremes are possible and the “middle” direction (the 45° oblique) is chosen (block  256 ). 
     Once the interpolation direction is chosen, the pixels required for the directional interpolation must be determined (block  224 ). The source data is then directionally interpolated to generate the intermediate pixels (block  226 ). Finally the intermediate pixels are interpolated horizontally to generate the desired upsampled target pixel w (block  228 ). 
     The location of the upsampled target pixel w, is defined by its distances from the reference pixel P R  both in the x and y directions. These distances are represented by the terms α x  and α y  where: 
     −0.5&lt;α x ≦0.5; and 
     −0.5&lt;α y ≦0.5; 
     α x  being positive to the right and α y  being positive downward. 
     In this embodiment, a four-point “filter” interpolator is used. Interpolated upsampled target pixels w are calculated as a function of four source pixels, S 0 , S 1 , S 2  and S 3 , and a parameter a representing the distance of the desired pixel from S 1 : 
     w=ƒ(S 0 , S 1 , S 2 , S 3 , α) 
     This function may be a four-tap filter with coefficients read from a ROM indexed by parameter α. 
     FIG. 15 shows the case when the vertical interpolation direction V is selected. The target pixel w is positioned in the “Top-Left” quadrant with α x  and α y  both negative. The intermediate horizontal line segment represented by the values v i , is determined by vertical four-point interpolation as follows: 
     v 0 =ƒ(U 1-2 , U 0-2 , U -1-2 , U -2-2 , −α y ) 
     v 1 =ƒ(U 1-1 , U 0-1 , U -1-1 , U -2-1 , −α y ) 
     v 2 =ƒ(U 10 , U 00 , U -10 , U -20 , −α y ) 
     v 3 =ƒ(U 11 , U 01 , U -11 , U -21 , −α y ) 
     v 4 =ƒ(U 12 , U 02 , U -12 , U -22 , −α y ) 
     After the five intermediate pixels are calculated, interpolations are performed on these pixels to calculate the value of the desired upsampled target pixel. The distance β, representing the horizontal distance from the target pixel w to the middle intermediate pixel, v 2  must first be calculated. The calculation of β for the other three quadrants is also shown in FIG.  15 . In the vertical direction case, β is simply equal to a for all quadrants. In the case of FIG. 15, upsampled target pixel w is in the Top-Left quadrant and β is negative. Thus, the upsampled target pixel is represented by: 
     w=ƒ(v 3 , v 2 , v 1 , v 0 , −β) 
     In the other quadrants around the reference pixel P R , the upsampled target pixel w can be similarly calculated. 
     When the oblique up-right direction O UR  is selected, the intermediate pixels are interpolated along positively sloped 45° diagonals. FIG. 16 shows the up-right case. The target pixel w, is positioned in the Top-Right quadrant with α x  positive and α y  negative. Using four-point interpolation along the indicated diagonals yields: 
     v 0 =ƒ(U 1-3 , U 0-2 , U -1-1 , U -20 , −α y ) 
     v 1 =ƒ(U 1-2 , U 0-1 , U -10 , U -21 , −α y   
     v 2 =ƒ(U 1-1 , U 00 , U -11 , U -22 , −α y ) 
     v 3 =ƒ(U 10 , U 01 , U -12 , U -23 , −α y ) 
     v 4 =ƒ(U 11 , U 02 , U -13 , U -24 , −α y ) 
     After the five intermediate pixels have been computed non-orthogonal, horizontal interpolation is performed to determine the upsampled target pixel w. Since the interpolation is on a 45° angle, the horizontal distance from the reference pixel P R  to intermediate pixel v 2  is simply the vertical distance, namely, −α y . Thus, β is simply α x +α y . In the present case, β is positive so the upsampled target pixel is represented by: 
     w=ƒ(v 1 , v 2 , v 3 , v 4 , β) 
     For other quadrants, a similar method may be used to determine the upsampled target pixel. The intermediate pixels used and β vary from quadrant to quadrant. FIG. 16 also demonstrates the calculation of β for each quadrant. These results are summarized in Table A below. 
     Interpolating in the oblique up-left direction O UL  is very similar to the up-right direction. Intermediate pixels are interpolated along negatively sloped 45° diagonals. In FIG. 17, the upsampled target pixel w is in the Bottom-Right quadrant with both α x  and α y  positive. Using four-point interpolation along the diagonals: 
     v 0 =ƒ(U -1-3 , U 0-2 , U 1-1 , U 20 , α y ) 
     v 1 =ƒ(U -1-2 , U 0-1 , U 10 , U 21 , α y ) 
     v 2 =ƒ(U -1-1 , U 00 , U 11 , U 22 , α y ) 
     v 3 =ƒ(U -10 , U 01 , U 12 , U 23 , α y ) 
     v 4 =ƒ(U -11 , U 02 , U 13 , U 24 , α y ) 
     The upsampled target pixel is computed by performing non- orthogonal,horizontal interpolation on the intermediate pixels. Again, since the interpolation is along a 45° diagonal, the horizontal distances to the intermediate pixels are equal to the vertical distances. For the Bottom-Right quadrant, β=α x −α y . With β positive, the upsampled target pixel is represented by: 
     w=ƒ(v 1 , v 2 , v 3 , v 4 , β) 
     Again a similar method applies for the other quadrants with β varying from quadrant to quadrant. FIG. 17 demonstrates the calculation of β for the other quadrants with the results in Table A. 
     When the oblique up-right-right (O URR  or up-left-left (O ULL ) interpolation directions are selected, interpolation is along the 26.6° diagonals. The source pixels/diagonals used for four-point interpolation are shown for both the up-right-right and up-left-left directions in FIG.  18 . 
     FIG. 19 shows some of the source pixels used in up-right-right O URR  interpolation for an upsampled target pixel w in the Bottom-Left quadrant, with α x  negative and α y  positive. Using four-point interpolation along the positively sloped 26.6° diagonals: 
     v 0 =ƒ(U -10 , U 0-2 , U 1-4 , U 2-6 , α y ) 
     v 1 =ƒ(U -11 , U 0-1 , U 1-3 , U 2-5 , α y ) 
     v 2 =ƒ(U -12 , U 00 , U 1-2 , U 2-4 , α y ) 
     v 3 =ƒ(U -13 , U 01 , U 1-1 , U 2-3 , α y ) 
     v 4 =ƒ(U -14 , U 02 , U 10 , U 2-2 , α y ) 
     The upsampled target pixel is calculated by horizontal interpolation. Since interpolation is along the 26.6° diagonals, horizontal distances to the intermediate pixels are twice the vertical distance. For the Bottom-Left quadrant β=2α y (−α x )=α x +2α y . With β positive, the upsampled target pixel is represented by: 
     w=ƒ(v 1 , v 2 , v 3 , v 4 , β) 
     Similarly for other quadrants. FIG. 19 shows the calculation of β for other quadrants as summarized in Table A. 
     When the up-left-left interpolation direction O ULL  is selected for interpolation, intermediate pixels are interpolated along negatively sloped 26.6° diagonals. Some of the source pixels used are shown in FIG. 20 for the Top-Left quadrant with both ox and α y  negative. Using four-point interpolation: 
     v 0 =ƒ(U 10 , U 0-2 , U -1-4 , U -2-6 , −α y ) 
     v 1 =ƒ(U 11 , U 0-1 , U -1-3 , U -2-5 , −α y ) 
     v 2 =ƒ(U 12 , U 00 , U -1-2 , U -2-4 , −α y ) 
     v 3 =ƒ(U 13 , U 01 , U -1-1 , U -2-3 , −α y ) 
     v 4 =ƒ(U 14 , U 02 , U -10, U   -2-2 , −α y ) 
     Again since interpolation is along 26.6° diagonals, the horizontal distance to the intermediate pixels is equal to twice the vertical. For the Top-Left quadrant β=−2α y ,−(−α x )=α x −2α y . With β positive, the upsampled target pixel is represented by: 
     w=ƒ(v 1 , v 2 , v 3 , v 4 , β) 
     A similar method applies for the other quadrant with varying β. FIG. 20 demonstrates the calculation of β for other quadrants. The results are summarized in Table A. 
     When either the oblique up-up-right (O UUR ) or up-up-left (O UUL ) interpolation directions are selected, the directional interpolation involves interpolating across more source lines than in the previous cases. To avoid requiring too many source lines, linear interpolation is used for directional interpolation for the up-up-right and up-up-left directions. 
     FIG. 21 illustrates the interpolations required for the up-up-right, O UUR , interpolation direction. The upsampled target pixel w, is in the Bottom-Right quadrant with both α x  and α y  positive. Interpolation is along positively sloped, 63.4° diagonals. There are two types of these offsetting diagonals, namely the “inside” and “outside” diagonals as represented by the lines U 1-1 , U -10  and U 00  O 2-1  respectively. The linear upsampling parameter for the outside diagonal is given by the vertical distance α y  from the intermediate pixel to the source pixel. Since interpolation skips a source line, the linear upsampling parameter is halved, i.e. α y /2. Similarly for the inside diagonal, the parameter is (1−α y )/2. Using linear interpolation, the intermediate pixels are calculated as follows: 
     
       
           v   0 =(1−0.5(1−α y )) U   1-1 +0.5(1−α y )U -10    
       
     
     
       
           v   1 =(1−0.5α y )U 00 +0.5α y   U   2-1    
       
     
     
       
           v   2 =(1−0.5(1−α y )) U   10 +0.5(1−α y ) U   -11    
       
     
     
       
           v   3 =(1−0.5α y ) U   01 +0.5α y   U   20    
       
     
     
       
           v   4 =(1−0.5(1−α y )) U   11 +0.5(1−α y ) U   -12    
       
     
     The upsampled target pixel is calculated by non-orthogonal horizontal interpolation. Four-point interpolation is still used horizontally. Since interpolation is along the 63.4° diagonals, horizontal distances to the intermediate pixels are half the vertical distance. Additionally, since the spacing between intermediate pixels is half the spacing for the previous interpolation directions, β is twice the distance from the centre intermediate pixel to the target pixel. For the Bottom-Right quadrant 0.5=α x −0.5β+0.5α y . So β=−1+2α x +α y . With β negative, the upsampled target pixel is represented by: 
     w=ƒ(v 3 , v 2 , v 1 , V 0 , −β) 
     Similarly for other quadrants. FIG. 21 shows the calculation of β for other quadrants as summarized in Table A. 
     For the oblique up-up-left O UUL , interpolation direction shown in FIG. 22 the upsampled target pixel w, is in the Top-Right quadrant with α x  positive and α y  negative. Interpolation is along the negatively sloped 63.4° diagonals. The linear upsampling parameter for the inside diagonal is (1+α y )/2 and the parameter for the outside diagonals is−α y /2. Once again using linear interpolation: 
     
       
           v   0 =(1−0.5(1+α y )) U   -1-1 +0.5(1+α y ) U   10    
       
     
     
       
           v   1 =(1−0.5(−α y )) U   00 +0.5(−α y ) U   -2-1    
       
     
     
       
           v   2 =(1−0.5(1+α y )) U   -10 +0.5(1+α y ) U   11    
       
     
     
       
           v   3 =(1−0.5(−α y )) U   01 +0.5(−α y ) U   -20    
       
     
     
       
           v   4 =(1−0.5(1+α y )) U   -11 +0.5(1+α y ) U   12    
       
     
     Four-point horizontal interpolation is performed on the intermediate pixels. Once again the horizontal distances to the intermediate pixels are half the vertical distances, and β is twice the distance from the centre intermediate pixel to the target pixel. For the case of the upsampled target pixel w being in the Top-Right quadrant, β=2(α x +(−0.5α y )−1)=−1+2α x −α y . Since β is positive, the upsampled target pixel is represented by: 
     w=ƒ(v 1 , v 2 , v 3 , v 4 , β) 
     A similar method applies for the other quadrants. FIG. 22 shows the calculation of β for other quadrants as summarized in Table A 
     FIG. 24 shows a basic source data interpolation apparatus  300  for performing the above method. As can be seen, apparatus  300  is the same as the apparatus used in the first embodiment. The same block diagram applies to the second embodiment just described. Source data D in . is passed through a delay circuit  302  which extracts the necessary source pixels required for interpolation. These source pixels are used by the decision circuit  304  to select an interpolation direction. The selected interpolation direction is passed to the β calculator  308  to determine the value of β. The source pixels, interpolation direction, and β are all passed to the oblique upsampler  306  for directional interpolation to generate the upsampled target pixel w. 
     FIG. 25 better illustrates the delay circuit  302  of the present embodiment. It includes three line stores  344 ,  370 , and  396  which give access to four consecutive source lines and forty-eight delay elements  320  to  342 ,  346  to  368 ,  372  to  394 , and  398  to  420  which in turn give access to thirteen adjacent source pixels on each of the four source lines. The delay circuit extracts the 13×4 source matrix needed for interpolation. When interpolating in the upper quadrants, the pixels extracted correspond to the source pixels labelled. 
     The decision circuit  304  is better illustrated in FIG.  26 . Input source pixels are fed to six subtractors  446 ,  452 ,  458 ,  464 ,  470 , and  476 . Each subtractor calculates a difference value corresponding to one of the six possible oblique directions. Two delay elements for each difference value  448 ,  450 ,  454 ,  456 ,  460 ,  462 ,  466 ,  468 ,  472 ,  474 ,  478 , and  480  provide access to three consecutive difference values for each direction. These difference values are passed to a selection means  482  which selects either one of the six possible oblique interpolation directions or the vertical interpolation direction. The source pixels labelled correspond to interpolation in the top-left quadrant. 
     The β calculator shown in FIG. 27 comprises a three input adder 508. The adder inputs are the outputs of three multiplexers  502 ,  504 , and  506 . The output of multiplexer  502  is 0, 1, or −1 depending on the output of decoder  500  which takes the interpolation direction selected and the quadrant of the upsampled target pixel. Multiplexer  504  outputs either α x  or 2α x  depending on the interpolation direction selected. Finally multiplexer 506 outputs either α y , −α y , 2α y , or −2α y  depending also on the interpolation direction. The output of adder  508  is β. 
     The oblique upsampler  306  is best illustrated in FIG.  28 . It comprises three main parts; namely an input decoder  532 , a directional interpolator  306   a  and a horizontal interpolator  306   b . The input source pixels are decoded in the input decoder  532  according to the quadrant in which the upsampled target pixel is located and the interpolation direction. The required source pixels are sent to the directional interpolator  306   a  which performs four 4-point interpolations to generate four intermediate pixels. The 4-point directional interpolation is performed by four 4-tap filters  534 ,  536 ,  538 , and  540  whose coefficients are supplied from a ROM 530, addressed by |α y |. The four intermediate pixels are passed to the 4-point horizontal interpolator  306   b  to calculate the upsampled target pixel w. The horizontal interpolator  306   b  is composed of a 4-tap filter  544  and a ROM,  542 , addressed by A. 
     Table A below outlines the directional interpolations performed to generate the intermediate pixels for each of the seven interpolation directions. The Table also includes the formula for calculating β for the various directions and quadrants. 
     
       
         
               
               
               
               
             
           
               
                 TABLE A 
               
               
                   
               
               
                 Interpolation 
                   
                 Intermediate Pixels 
                   
               
               
                 Direction 
                 Quadrant 
                 v 0 , v 1 , v 2 , v 3 , v 4   
                 β 
               
               
                   
               
             
             
               
                 Vertical 
                 Top-Left 
                 v 0  = f(U 1-2 , U 0-2 , U −1-2 , U −2-2 , −α y ) 
                 α x   
               
               
                 V 
                 α x  &lt; 0, α y  &lt; 0 
                 v 1  = f(U 1-1 , U 0-1 , U −1-1 , U −2-1 , −α y ) 
               
               
                   
                   
                 v 2  = f(U 10 , U 00 , U −10 , U −20 , −α y ) 
               
               
                   
                   
                 v 3  = f(U 11 , U 01 , U −11 , U −21 , −α y ) 
               
               
                   
                   
                 v 4  = f(U 12 , U 02 , U −12 , U −22 , −α y ) 
               
               
                   
                 Top-Right 
                 v 0  = f(U 1-2 , U 0-2 , U −1-2 , U −2-2 , −α y ) 
                 α x   
               
               
                   
                 α x  ≧ 0, α y  &lt; 0 
                 v 1  = f(U 1-1 , U 0-1 , U −1-1 , U −2-1 , −α y ) 
               
               
                   
                   
                 v 2  = f(U 10 , U 00 , U −10 , U −20 , −α y ) 
               
               
                   
                   
                 v 3  = f(U 11 , U 01 , U −11 , U −21 , α y ) 
               
               
                   
                   
                 v 4  = f(U 12 , U 02 , U −12 , U −22 , −α y ) 
               
               
                   
                 Bottom-Left 
                 v 0  = f(U −1-2 , U 0-2 , U 1-2 , U 2-2 , α y ) 
                 α x   
               
               
                   
                 α x  &lt; 0, α y  ≧ 0 
                 v 1  = f(U −1-2 , U 0-2 , U 1-2 , U 2-2 , α y ) 
               
               
                   
                   
                 v 2  = f(U −10 , U 00 , U 10 , U 20 , α y ) 
               
               
                   
                   
                 v 3  = f(U −11 , U 01 , U 11 , U 21 , α y ) 
               
               
                   
                   
                 v 4  = f(U −12 , U 02 , U 12 , U 22 , α y ) 
               
               
                   
                 Bottom-Right 
                 v 0  = f(U −1-2 , U 0-2 , U 1-2 , U 2-2 , α y ) 
                 α x   
               
               
                   
                 α x  ≧ 0, α y  ≧ 0 
                 v 1  = f(U −1-1 , U 0-1 , U 1-1 , U 2-1 , α y ) 
               
               
                   
                   
                 v 2  = f(U −10 , U 00 , U 10 , U 20 , α y ) 
               
               
                   
                   
                 v 3  = f(U −11 , U 01 , U 11 , U 21 , α y ) 
               
               
                   
                   
                 v 4  = f(U −12 , U 02 , U 12 , U 22 , α y ) 
               
               
                 Up-Right 
                 Top-Left 
                 v 0  = f(U 1-4 , U 0-3 , U −1-2 , U −2-1 , −α y ) 
                 1 + α x  + α y   
               
               
                 O UR   
                 α x  &lt; 0, α y  &lt; 0 
                 v 1  = f(U 1-3 , U 0-2 , U −1-1 , U −20 , −α y ) 
               
               
                   
                   
                 v 2  = f(U 1-2 , U 0-1 , U −10 , U −21 , −α y ) 
               
               
                   
                   
                 v 3  = f(U 1-1 , U 00 , U −11 , U −22 , −α y ) 
               
               
                   
                   
                 v 4  = f(U 10 , U 01 , U −12 , U −23 , −α y ) 
               
               
                   
                 Top-Right 
                 v 0  = f(U 1-3 , U 0-2 , U −1-1 , U −20 , −α y ) 
                 α x  + α y   
               
               
                   
                 α x  ≧ 0, α y  &lt; 0 
                 v 1  = f(U 1-2 , U 0-1 , U −10 , U −21 , −α y ) 
               
               
                   
                   
                 v 2  = f(U 1-1 , U 00 , U −11 , U −22 , −α y ) 
               
               
                   
                   
                 v 3  = f(U 10 , U 01 , U −12 , U −23 , −α y ) 
               
               
                   
                   
                 v 4  = f(U 11 , U 02 , U −13 , U −24 , −α y ) 
               
               
                   
                 Bottom-Left 
                 v 0  = f(U −1-1 , U 0-2 , U 1-3 , U 2-4 , α y ) 
                 α x  + α y   
               
               
                   
                 α x  &lt; 0, α y  ≧ 0 
                 v 1  = f(U −0 , U 0-1 , U 1-2 , U 2-3 , α y ) 
               
               
                   
                   
                 v 2  = f(U −11 , U 00 , U 1-1 , U 2-2 , α y ) 
               
               
                   
                   
                 v 3  = f(U −12 , U 01 , U 10 , U 2-1 , α y ) 
               
               
                   
                   
                 v 4  = f(U −13 , U 02 , U 11 , U 20 , α y ) 
               
               
                   
                 Bottom-Right 
                 v 0  = f(U −10 , U 0-1 , U 1-2 , U 2-3 , α y ) 
                 1 + α x  + α y   
               
               
                   
                 α x  ≧ 0, α y  ≧ 0 
                 v 1  = f(U −11 , U 00 , U 1-1 , U 2-2 , α y ) 
               
               
                   
                   
                 v 2  = f(U −12 , U 01 , U 10 , U 2-1 , α y ) 
               
               
                   
                   
                 v 3  = f(U −13 , U 02 , U 11 , U 20 , α y ) 
               
               
                   
                   
                 v 4  = f(U −14 , U 03 , U 12 , U 21 , α y ) 
               
               
                 Up-Left 
                 Top-Left 
                 v 0  = f(U 1-1 , U 0-2 , U −1-3 , U −2-4 , −α y ) 
                 α x  − α y   
               
               
                 O UL   
                 α x  &lt; 0, α y  &lt; 0 
                 v 1  = f(U 10 , U 0-1 , U −1-2 , U −2-3 , −α y ) 
               
               
                   
                   
                 v 2  = f(U 11 , U 00 , U −1-1 , U −2-2 , −α y ) 
               
               
                   
                   
                 v 3  = f(U 12 , U 01 , U −10 , U −2-1 , −α y ) 
               
               
                   
                   
                 v 4  = f(U 13 , U 02 , U −11 , U −20 , −α y ) 
               
               
                   
                 Top-Right 
                 v 0  = f(U 10 , U 0-1 , U −1-2 , U −2-3 , −α y ) 
                 −1 + a z  − a y   
               
               
                   
                 α x  ≧ 0, α y  &lt; 0 
                 v 1  = f(U 11 , U 00 , U −1-1 , U −2-2 , −α y ) 
               
               
                   
                   
                 v 2  = f(U 12 , U 01 , U −10 , U −2-1 , −α y ) 
               
               
                   
                   
                 v 3  = f(U 13 , U 02 , U −11 , U −20 , −α y ) 
               
               
                   
                   
                 v 4  = f(U 14 , U 03 , U −12 , U −21 , −α y ) 
               
               
                   
                 Bottom-Left 
                 v 0  = f(U −1-4 , U 0-3 , U 1-2 , U 2-1 , α y ) 
                 1 + a x  − a y   
               
               
                   
                 α x  &lt; 0, α y  ≧ 0 
                 v 1  = f(U −1-3 , U 0-3 , U 1-2 , U 2-1 , α y ) 
               
               
                   
                   
                 v 2  = f(U −1-2 , U 0-1 , U 10 , U 21 , α y ) 
               
               
                   
                   
                 v 3  = f(U −1-1 , U 00 , U 11 , U 22 , α y ) 
               
               
                   
                   
                 v 4  = f(U −10 , U 01 , U 12 , U 23 , α y ) 
               
               
                   
                 Bottom-Right 
                 v 0  = f(U −1-3 , U 0-2 , U 1-1 , U 20 , α y ) 
                 α x  − α y   
               
               
                   
                 α x  ≧ 0, α y  ≧ 0 
                 v 1  = f(U −1-2 , U 0-1 , U 10 , U 21 , α y ) 
               
               
                   
                   
                 v 2  = f(U −1-1 , U 00 , U 11 , U 22 , α y ) 
               
               
                   
                   
                 v 3  = f(U −10 , U 01 , U 12 , U 23 , α y ) 
               
               
                   
                   
                 v 4  = f(U −11 , U 02 , U 13 , U 24 , α y ) 
               
               
                 Up-Right-Right 
                 Top-Left 
                 v 0  = f(U 1-5 , U 0-3 , U −1-1 , U −21 , −α y ) 
                 1 + α x  + 2α y   
               
               
                 O URR   
                 α x  &lt; 0, α y  &lt; 0 
                 v 1  = f(U 1-4 , U 0-2 , U −10 , U −22 , −α y ) 
               
               
                   
                   
                 v 2  = f(U 1-3 , U 0-1 , U −11 , U −23 , −α y ) 
               
               
                   
                   
                 v 3  = f(U 1-2 , U 00 , U −12 , U −24 , −α y ) 
               
               
                   
                   
                 v 4  = f(U 1-1 , U 01 , U −13 , U −25 , −α y ) 
               
               
                   
                 Top-Right 
                 v 0  = f(U 1-4 , U 0-2 , U −10 , U −22 , −α y ) 
                 α x  + 2α y   
               
               
                   
                 α x  ≧ 0, α y  &lt; 0 
                 v 1  = f(U 1-3 , U 0-1 , U −11 , U −23 , −α y ) 
               
               
                   
                   
                 v 2  = f(U 1-2 , U 00 , U −12 , U −24 , −α y ) 
               
               
                   
                   
                 v 3  = f(U 1-1 , U 01 , U −13 , U −25 , −α y ) 
               
               
                   
                   
                 v 4  = f(U 10 , U 02 , U −14 , U −26 , −α y ) 
               
               
                   
                 Bottom-Left 
                 v 0  = f(U −10 , U 0-2 , U 1-4 , U 2-6 , α y ) 
                 α x  +2α y   
               
               
                   
                 α x  &lt; 0, α y  ≧ 0 
                 v 1  = f(U −11 , U 0-1 , U 1-3 , U 2-5 , α y ) 
               
               
                   
                   
                 v 2  = f(U −12 , U 00 , U 1-2 , U 2-4 , α y ) 
               
               
                   
                   
                 v 3  = f(U −13 , U 01 , U 1-1 , U 2-3 , α y ) 
               
               
                   
                   
                 v 4  = f(U −14 , U 02 , U 10 , U 2-2 , α y ) 
               
               
                   
                 Bottom-Right 
                 v 0  = f(U −11 , U 0-1 , U 1-3 , U 2-5 , α y ) 
                 1 + α x  + 2α y   
               
               
                   
                 α x  ≧ 0, α y  ≧ 0 
                 v 1  = f(U −12 , U 00 , U 1-2 , U 2-4 , α y ) 
               
               
                   
                   
                 v 2  = f(U −13 , U 01 , U 1-1 , U 2-3 , α y ) 
               
               
                   
                   
                 v 3  = f(U −14 , U 02 , U 10 , U 2-2 , α y ) 
               
               
                   
                   
                 v 4  = f(U −15 , U 03 , U 11 , U 2-1 , α y ) 
               
               
                 Up-Left-Left 
                 Top-Left 
                 v 0  = f(U 10 , U 0-2 , U −1-4 , U −2-6 , −α y ) 
                 α x  − 2α y   
               
               
                 O ULL   
                 α x  &lt; 0, α y  &lt; 0 
                 v 1  = f(U 11 , U 0-1 , U −1-3 , U −2-5 , −α y ) 
               
               
                   
                   
                 v 2  = f(U 12 , U 00 , U −1-2 , U −2-4 , −α y ) 
               
               
                   
                   
                 v 3  = f(U 13 , U 01 , U −1-1 , U −2-3 , −α y ) 
               
               
                   
                   
                 v 4  = f(U 14 , U 02 , U −10 , U −2-2 , −α y ) 
               
               
                   
                 Top-Right 
                 v 0  = f(U 11 , U 0-1 , U −1-3 , U −2-5 , −α y ) 
                 −1 + α x  − 2α y   
               
               
                   
                 α x  ≧ 0, α y  &lt; 0) 
                 v 1  = f(U 12 , U 00 , U −1-2 , U −2-4 , −α y ) 
               
               
                   
                   
                 v 2  = f(U 13 , U 01 , U −1-1 , U —2-3 , −α y ) 
               
               
                   
                   
                 v 3  = f(U 14 , U 02 , U −10 , U −2-2 , −α y ) 
               
               
                   
                   
                 v 4  = f(U 15 , U 03 , U −11 , U −2-1 , −α y ) 
               
               
                   
                 Bottom-Left 
                 v 0  = f(U −1-5 , U 0-3 , U 1-1 , U 21 , α y ) 
                 1 + α x  − 2α y   
               
               
                   
                 α x  &lt; 0, α y  ≧ 0 
                 v 1  = f(U −1-4 , U 0-2 , U 10 , U 22 , α y ) 
               
               
                   
                   
                 v 2  = f(U −1-3 , U 0-1 , U 11 , U 23 , α y ) 
               
               
                   
                   
                 v 3  = f(U −1-2 , U 00 , U 12 , U 24 , α y ) 
               
               
                   
                   
                 v 4  = f(U −1-1 , U 01 , U 13 , U 25 , α y ) 
               
               
                   
                 Bottom Right 
                 v 0  = f(U −1-4 , U 0-2 , U 10 , U 22 , α y ) 
                 α x  − 2α y   
               
               
                   
                 α x  ≧ 0, α y  ≧ 0 
                 v 1  = f(U −1-3 , U 0-1 , U 11 , U 23 , α y ) 
               
               
                   
                   
                 v 2  = f(U −1-2 , U 00 , U 12 , U 24 , α y ) 
               
               
                   
                   
                 v 3  = f(U −1-1 , U 01 , U 13 U 25 , α y ) 
               
               
                   
                   
                 v 4  = f(U −10 , U 02 , U 14 , U 26 , α y ) 
               
               
                 Up-Up-Right 
                 Top-Left 
                 v 0  = U −1-1  + (U 1-2  − U −1-1 )(0.5 + 0.5α y ) 
                 1 + 2α x  + α y   
               
               
                 O UUR   
                 α x  &lt; 0, α y  &lt; 0 
                 v 1  = U 0-1  + (U −20  − U 0-1 )(−0.5α y ) 
               
               
                   
                   
                 v 2  = U −10  + (U 1-1  − U −10 )(0.5 + 0.5α y ) 
               
               
                   
                   
                 v 3  = U 00  + (U −21  − U 00 )(−0.5α y ) 
               
               
                   
                   
                 v 4  = U −11  + (U 10  − U −11 )(0.5 + 0.5α y ) 
               
               
                   
                 Top-Right 
                 v 0  = U 0-1  + (U −20  − U 0-1 )(−0.5α y ) 
                 2α x  + α y   
               
               
                   
                 α x  ≧ 0, α y  &lt; 0 
                 v 1  = U −10  + (U 1-1  − 10)(0.5 + 0.5α y ) 
               
               
                   
                   
                 v 2  = U 00  + (U −21  − U 00 )(−0.5α y ) 
               
               
                   
                   
                 v 3  = U −11  + (U 10  − U −11 )(0.5 + 0.5α y ) 
               
               
                   
                   
                 v 4  = U 01  + (U −22  − U 01 )(−0.5α y ) 
               
               
                   
                 Bottom-left 
                 v 0  = U 0-1  + (U 2-2  − U 0-1 )(0.5α y ) 
                 2 α x  + α y   
               
               
                   
                 α x  &lt; 0, α y  ≧ 0 
                 v 1  = U 1-1  + (U −10  − U 1-1 )(0.5 − 0.5α y ) 
               
               
                   
                   
                 v 2  = U 00  + (U 2-1  − U 00 )(0.5α y ) 
               
               
                   
                   
                 v 3  = U 10  + (U −11  − U 10 )(0.5 − 0.5α y ) 
               
               
                   
                   
                 v 4  = U 01  + (U 20  − U 01 )(0.5α y ) 
               
               
                   
                 Bottom-Right 
                 v 0  = U 1-1  + (U −10  − U 1-1 )(0.5 − 0.5α y ) 
                 1 + 2α x  + α y   
               
               
                   
                 α x  ≧ 0, α y  ≧ 0 
                 v 1  = U 00  + (U 2-1  − U 00 )(0.5α y ) 
               
               
                   
                   
                 v 2  = U 10  + (U −11  − U 10 )(0.5 − 0.5α y ) 
               
               
                   
                   
                 v 3  = U 01  + (U 20  − U 01 )(0.5α y ) 
               
               
                   
                   
                 v 4  = U 11  + (U −12  − U 11 )(0.5 − 0.5α y ) 
               
               
                 Up-Up-Left 
                 Top-Left 
                 v 0  = U 0-1  + (U −2-2  − U 0-1 )(−0.5α y ) 
                 2α x  − α y   
               
               
                 O UUL   
                 α x  &lt; 0, α y  &lt; 0 
                 v 1  = U −1-1  + (U 10  − U −1-1 )(0.5 + 0.5α y ) 
               
               
                   
                   
                 v 2  = U 00  + (U −2-1  − U 00 )(−0.5α y ) 
               
               
                   
                   
                 v 3  = U −10  + (U 11  − U −10 )(0.5 + 0.5α y ) 
               
               
                   
                   
                 v 4  = U 01  + U −20  − U 01 )(−0.5α y ) 
               
               
                   
                 Top-Right 
                 v 0  = U −1-1  + (U 10  − U −1-1 )(0.5 + 0.5α y ) 
                 −1 + 2α x  − α y   
               
               
                   
                 α x  ≧ 0, α y  &lt; 0 
                 v 1  = U 00  + (U −2-1  − U 00 )(−0.5α y ) 
               
               
                   
                   
                 v 2  = U −10  + (U 11  − U −10 )(0.5 + 0.5α y ) 
               
               
                   
                   
                 v 3  = U 01  + (U −20  − U 01 )(−0.5α y ) 
               
               
                   
                   
                 v 4  = U −11  + (U 12  − U −11 )(0.5 + 0.5α y ) 
               
               
                   
                 Bottom-Left 
                 v 0  = U 1-1  + (U −1-2  − U 1-1 )(0.5 − 0.5α y ) 
                 1 + 2α x  − α y   
               
               
                   
                 α x  &lt; 0, α y  ≧ 0 
                 v 1  = U 0-1  + (U 20  − U 0-1 )(0.5α y ) 
               
               
                   
                   
                 v 2  = U 10  + (U −1-1  − U 10 )(0.5 − 0.5α y ) 
               
               
                   
                   
                 v 3  = U 00  + (U 21  − U 00 )(0.5α y ) 
               
               
                   
                   
                 v 4  = U 1-1  + (U −10  − U 1-1 )(0.5 − 0.5α y ) 
               
               
                   
                 Bottom-Right 
                 v 0  = U 0-1  + (U 20  − U 0-1 )(0.5α y ) 
                 2α x  − α y   
               
               
                   
                 α x  ≧ 0, α y  ≧ 0 
                 v 1  = (U −1-1  − U 10 )(0.5 − 0.5α y ) 
               
               
                   
                   
                 v 2  = U 00  + (U 21  − U 00 )(0.5α y ) 
               
               
                   
                   
                 v 3  = U 1-1  + (U −10  − U 1-1 )(0.5 − 0.5α y ) 
               
               
                   
                   
                 v 4  = U 01  + (U 22  − U 01 )(0.5α y ) 
               
               
                   
               
             
          
         
       
     
     As mentioned previously, once the intermediate pixels are generated four-point horizontal interpolation is performed on the intermediate pixels to generate the desired upsampled target pixel w. 
     w=ƒ(v 1 , v 2 , v 3 , v 4 , β) β≧0 
     w=ƒ(v 3 , v 2 , v 1 , v 0 , β) β&lt;0 
     The present methods and apparatuses allow upsampled target pixels to be generated so that when an image of the source data is to be enlarged and recreated, the resolution of the enlarged image is high and stairstepping is minimized. 
     As should be apparent to those of skill in the art, various modifications may be made to the present invention without departing from its scope as defined by the appended claims. For example, although two embodiments of the invention have been described herein, it should be apparent that other embodiments are possible and that the number of oblique directions in each set can be chosen arbitrarily.