Abstract:
A method and system for calculating an interpolated color value for a destination pixel from color values of source pixels adjacent to the destination pixel, where calculation of the color value of the destination pixel uses one of a plurality of interpolation functions selected according to the location of the destination pixel relative to one of the adjacent source pixels. Selection of the particular interpolation may be accomplished by defining a corresponding plurality of regions within the area covered by the adjacent source pixels and assigning an interpolation function to each of the regions. The region in which the destination pixel is located is identified, and the interpolation function assigned to the identified region is applied in the destination pixel color value calculation.

Description:
TECHNICAL FIELD 
     The present invention is related generally to the field of computer graphics, and more particularly, to calculating color values during a scaling operation in a computer graphics processing system. 
     BACKGROUND OF THE INVENTION 
     In the area of computer graphics, scaling graphics images is an important function that is used in a variety of applications. When enlarging images, various methods and systems have been used to calculate color values for the destination pixels of the scaled image in order for the scaled image to retain acceptable detail. A conventional method for generating destination pixel colors for the scaled image from source pixel colors of the original image is to use bilinear interpolation. As is well known in the art, bilinear interpolation applies a linear function in calculating a weighting value for each color of four adjacent source pixels P s0 -P s3  based on the “location” of the destination pixel P d  relative to the four source pixels. The location of the destination pixel is usually provided as fractional coordinates rU and rV, which indicate the relative position of the destination pixel P d  with respect to the source pixel P s0 . The resulting destination pixel color is the sum of the color values of the four source pixels, weighted by the appropriate weighting value. Bilinear interpolation is frequently used because circuits that implement such a function are relatively inexpensive and well understood. Another conventional system uses a bicubic interpolation function. Although such a scaling system is more costly, the resulting color values calculated for the destination pixels produce a more realistic scaled image. 
     Although the conventional interpolation methods applied during scaling operations provide scaled images having reasonably acceptable resolution, there are several disadvantages to conventional scaling systems. For example, although circuits that implement a bilinear interpolation function for scaling operations are well known in the art, and are relatively inexpensive, the resulting scaled image may appear blurry or fuzzy because of the color averaging resulting from the bilinear interpolation function. The color averaging is in part due to the fact that a bilinear interpolation function is not ideally suited for scaling operations. The bilinear interpolation function begins weighting the color values immediately starting from one edge of a source pixel to the opposite edge, regardless of the scaling factor. As a result, the color values for the destination pixels appear averaged. 
     With respect to systems implementing bicubic interpolation, such systems are typically complicated and costly. Moreover, although a scaled image produced using a bicubic interpolation function has a better appearance than an image scaled using a bilinear interpolation function, bicubic interpolation may cause “ringing” artifacts in the scaled image, especially near sharp edges in the source content, such as with dark colored text against a light colored background. 
     Therefore, there is a need for a system and method for calculating the color values of destination pixels in a scaled graphics image which applies an interpolation function that accounts for the amount by which the image is scaled. 
     SUMMARY OF THE INVENTION 
     The present invention is directed to a method and system for calculating an interpolated color value for a destination pixel from color values of source pixels adjacent to the destination pixel, where calculation of the color value of the destination pixel uses one of a plurality of interpolation functions selected according to the location of the destination pixel relative to one of the adjacent source pixels. In one aspect of the invention, selection of the particular interpolation may be accomplished by defining a corresponding plurality of regions within the area covered by the adjacent source pixels and assigning an interpolation function to each of the regions. The region in which the destination pixel is located is identified, and the interpolation function assigned to the identified region is applied in the destination pixel color value calculation. In another aspect of the invention, the resultant values of the identified interpolation function are provided to a conventional bilinear interpolation circuit, and the color value of the destination pixel is calculated therefrom. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram of a computer system in which embodiments of the present invention are implemented. 
     FIG. 2 is a block diagram of a graphics processing system in the computer system of FIG.  1 . 
     FIGS. 3 a  and  b  are illustrations of a source pixel and a scaled destination pixel, and an original image and a scaled image displayed on a display device. 
     FIGS. 4 a-c  are illustrations of three domains for an area covered by adjacent source pixels according to an embodiment of the present invention. 
     FIG. 5 is a block diagram of an interpolation circuit according to an embodiment of the present invention. 
     FIG. 6 is an illustration of a interpolation function according to an embodiment of the present invention. 
     FIG. 7 is a block diagram of an interpolation circuit according to another embodiment of the present invention. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Embodiments of the present invention apply a non-linear interpolation function that is a function of the scaling factor for scaling operations, particularly where the scaling operation is enlarging the graphics image. The resultant values of the non-linear interpolation function are provided to a conventional bilinear interpolation circuit for calculating the color value of destination pixels. Certain details are set forth below to provide a sufficient understanding of the invention. However, it will be clear to one skilled in the art that the invention may be practiced without these particular details. In other instances, well-known circuits, control signals, timing protocols, and software operations have not been shown in detail in order to avoid unnecessarily obscuring the invention. 
     FIG. 1 illustrates a computer system  100  in which embodiments of the present invention are implemented. The computer system  100  includes a processor  104  coupled to a host memory  108  through a memory/bus interface  112 . The memory/bus interface  112  is coupled to an expansion bus  116 , such as an industry standard architecture (ISA) bus or a peripheral component interconnect (PCI) bus. The computer system  100  also includes one or more input devices  120 , such as a keypad or a mouse, coupled to the processor  104  through the expansion bus  116  and the memory/bus interface  112 . The input devices  120  allow an operator or an electronic device to input data to the computer system  100 . One or more output devices  120  are coupled to the processor  104  to provide output data generated by the processor  104 . The output devices  124  are coupled to the processor  104  through the expansion bus  116  and memory/bus interface  112 . Examples of output devices  124  include printers and a sound card driving audio speakers. One or more data storage devices  128  are coupled to the processor  104  through the memory/bus interface  112  and the expansion bus  116  to store data in, or retrieve data from, storage media (not shown). Examples of storage devices  128  and storage media include fixed disk drives, floppy disk drives, tape cassettes and compact-disc read-only memory drives. 
     The computer system  100  further includes a graphics processing system  132  coupled to the processor  104  through the expansion bus  116  and memory/bus interface  112 . Optionally, the graphics processing system  132  may be coupled to the processor  104  and the host memory  108  through other types of architectures. For example, the graphics processing system  132  may be coupled through the memory/bus interface  112  and a high speed bus  136 , such as an accelerated graphics port (AGP), to provide the graphics processing system  132  with direct memory access (DMA) to the host memory  108 . That is, the high speed bus  136  and memory bus interface  112  allow the graphics processing system  132  to read and write host memory  108  without the intervention of the processor  104 . Thus, data may be transferred to, and from, the host memory  108  at transfer rates much greater than over the expansion bus  116 . A display  140  is coupled to the graphics processing system  132  to display graphics images. The display  140  may be any type of display, such as a cathode ray tube (CRT), a field emission display (FED), a liquid crystal display (LCD), or the like, which are commonly used for desktop computers, portable computers, and workstation or server applications. As will be explained in more detail below, a scaling circuit  212  may be included in the display  140  to perform scaling operations on graphics images prior to rendering. 
     FIG. 2 illustrates circuitry included within the graphics processing system  132  for performing various graphics functions. As shown in FIG. 2, a bus interface  200  couples the graphics processing system  132  to the expansion bus  116 . In the case where the graphics processing system  132  is coupled to the processor  104  and the host memory  108  through the high speed data bus  136  and the memory/bus interface  112 , the bus interface  200  will include a DMA controller (not shown) to coordinate transfer of data to and from the host memory  108  and the processor  104 . A graphics processor  204  is coupled to the bus interface  200  and is designed to perform various graphics and video processing functions. A memory controller  216  coupled to the graphics processor  204  handles memory requests to and from a local memory  220 . The local memory  220  stores graphics data, such as source pixel color values and destination pixel color values. A display controller  224  coupled to the local memory  220  and to a first-in first-out (FIFO) buffer  228  controls the transfer of destination color values to the FIFO  228 . Destination color values stored in the FIFO  336  are provided to a scaling circuit  212  that facilitates resizing or rescaling graphics images. As will be explained below, the scaling circuit  212  may be programmed so that the transformations performed during a scaling operation of graphics images are adaptable. A display driver  232  coupled to the output of the scaling circuit  212  includes circuitry to provide digital color signals, or convert digital color signals to red, green, and blue analog color signals, to drive the display  140  (FIG.  1 ). 
     Although the scaling circuit  212  is illustrated in FIG. 2 as being a separate circuit, it will be appreciated that the scaling circuit may be included in one of the aforementioned circuit blocks of the graphics processing system  132 . For example, the scaling circuit  212  may be included in the graphics processor  204  or the display controller  224 . In other embodiments, the scaling circuit  212  may be included in the display  140  (FIG. 1) coupled to a dedicated FIFO and processor (not shown). It will be further appreciated that the scaling circuit  212  may be relocated in FIG. 2 to an alternative location, such as coupled between the graphics processor  204  and the memory controller  216  without losing any functionality. Therefore, the particular location of the scaling circuit  212  is a detail that may be modified without deviating from the subject matter of the invention, and should not be used in limiting the scope of the present invention. 
     In scaling a graphics image, a ratio may be calculated that represents the relative size of the pixels of the source image and the pixels of the destination image. For example, if the source image is displayed at a resolution of S w ×S h  and the destination image is displayed at a resolution of D w ×D h , the relative size of the source pixels to the destination pixels is: 
     
       
           p   u   =S   w   /D   w  and  p   v   =S   w   /D   w . 
       
     
     The ratios p u  and p v  represent the relative “size” of the destination pixels compared to the source pixel along a horizontal axis u and a vertical axis v, respectively. As illustrated in FIG. 3 a , if the source pixel P s  is assumed to have a unit length of one for both its width and height (i.e., the pixel P s  is a square), the destination pixel P d  will have a width equal to p u  and a height equal to p v . From this analysis, it can be seen that each destination pixel P d  in the scaled image represents “less” information than each pixel P s  in the source image where the image is enlarged. The ratios p u  and p v  represent the relative size of the destination pixel P d  and the source pixel P s . 
     Another way to describe the reduction in content of each destination pixel is described with respect to FIG. 3 b . An original image  302  and an enlarged image  304  of a one inch square  300  is displayed. If the square  300  is enlarged, the image size increases, however, the square is still one inch per side. What has occurred is that the number of pixels representing the image has increased. Assuming that in the original image  302  one inch is represented by 10 pixels, doubling the image size (i.e., enlarging by 100%) doubles the number of pixels to 20 pixels per side in the enlarged image  304 . Consequently, each destination pixel P d  in the enlarged image  304  represents half as much as each source pixel P s  did in the original image  302 . 
     Despite the fact that the relative size of the destination pixel P d  changes in a scaling operation, in bilinear interpolation it is assumed that the source pixel P s  and destination pixels P d  are the same size, and as a result, the destination pixel P d  will necessarily overlap at least two of the four adjacent source pixels P s . Otherwise, the destination pixel P d  would fall squarely on a source pixel P s , and determining the color value would not require interpolation. However, this assumption ignores the fact that each destination pixel P d  of the enlarged image is relatively smaller (or conveys less information) than a source pixel P s  in the original image, and as a result, fails to account for the scaling factor in calculating the color values of the destination pixels P d . 
     In embodiments of the present invention, the fact that a destination pixel P d  is smaller than a source pixel P s  for enlarging operations is accommodated in the color value calculation by applying a non-linear interpolation function that is a function of the scaling factor for enlarging operations. As mentioned previously, a destination pixel P d  represents relatively less information than a source pixel P s , or conceptually, is smaller than the source pixel P s . A result of this fact is that the position of a destination pixel P d  within four adjacent source pixels P s0 -P s3  can be conceptually separated into three different domains: (1) the destination pixel P d  is located entirely within a source pixel P s0 ; (2) the center of a destination pixel P d  is located within a source pixel P s0 , but at least a portion of the destination pixel is overlapping a different source pixel P s1 -P s3  (i.e., edge overlap); or (3) the center of the destination pixel is located within a different source pixel P s1 -P s3  (i.e., center overlap). The three domains are illustrated in FIGS. 4 a-c , respectively. If the upper left comer of the source pixels P s0 -P s3  and the destination pixel P d  is used to identify the location of a pixel in a two-axes (u, v) coordinate system, the fractional coordinates (rU, rV) will represent the distance between the upper left comer of the source pixel P s0  and the upper left comer of the destination pixel P d . More specifically, rU is the horizontal distance of the left edge of the destination pixel P d  from the left edge of the source pixel P s0 , and rV is the vertical distance of the upper edge of the destination pixel P d  from the upper edge of the source pixel P s0 . 
     As discussed previously, the first domain is where the destination pixel P d  is located entirely within the source pixel P s0 , the second domain is the edge overlap condition, and the third domain is the center overlap condition. These domains may be defined in terms of the p u  and p v  values previously described. In the following description of the domain definitions, discussion regarding the vertical axis v, has been omitted. The relative position of the destination pixel P d  is described with respect to source pixels P s0 -P s1 . However, it will be appreciated that the domain definitions are symmetrical for the horizontal and vertical axes, u and v, respectively. Consequently, the following description for the domain definitions along the horizontal axis may be applied for the vertical axis as well. 
     The first domain is defined as the range: 
     
       
         0 ≦rU &lt;(1 −p   u ). 
       
     
     That is, if rU ≦(1−p u ), the destination pixel P d  will be (ignoring position along the vertical axis v) entirely within the source pixel P s0 . The second domain is defined as the range: 
     
       
         (1 −p   u )≦ rU &lt;(1 −p   u /2). 
       
     
     The upper bound of the second domain may be thought of as the boundary between the source pixels P s o and P s1 . The center of the destination pixel will be positioned on the boundary between source pixels P s0  and P s1  when rU=(1−p u /2). If rU is less than (1−p u /2), the center of the destination pixel P d  remains in the source pixel P s0 , but a portion overlaps the source pixel P s1 . The third domain is defined as the range: 
     
       
         (1 −p   u /2)≦ rU &lt;1. 
       
     
     In this domain, the center of the destination pixel P d  is located within the source pixel P s1 , but has a portion that overlaps the source pixel P s0 . For each of the domains defined above, a different interpolation function may be applied. Thus, each of the functions can be tailored to create an overall non-linear interpolation function having desired interpolation characteristics during a scaling operation. The resulting non-linear interpolation function is defined as:            f        (   rU   )       =     {               f   0          (   rU   )                     if                 rU                   ε   [     0   ,     1   -     p   u         )                     f   1          (   rU   )                     if                 rU                   ε   [       1   -     p   u       ,     1   -       p   u     2         )                     f   2          (   rU   )                     if                 rU                   ε              [       1   -       p   u     2       ,   1     )             }       ,                          
     where f 0 (rU) represents the interpolation function applied in the destination pixel&#39;s color value calculation for the first domain, f 1 (rU) represents the interpolation function applied for the second domain, and f 2 (rU) represents the interpolation function applied for the third domain. 
     As mentioned previously, the description of the different domains along the horizontal axis u may be similarly used to describe the different domains along the vertical axis v. Each domain may also have a different interpolation function such that the resulting non-linear interpolation function may be defined as:            g        (   rV   )       =     {               g   0          (   rV   )                     if                 rV                   ε   [     0   ,     1   -     p   v         )                     g   1          (   rV   )                     if                 rV                   ε   [       1   -     p   v       ,     1   -       p   v     2         )                     g   2          (   rV   )                     if                 rV                   ε              [       1   -       p   v     2       ,   1     )             }       ,                          
     where g 0 (rV) represents the interpolation function applied for the first domain, g 1 (rV) represents the interpolation function applied for the second domain, and g 2 (rV) represents the interpolation function applied for the third domain. As with the interpolation function along the horizontal axis, each function can be tailored to create a resulting non-linear interpolation function having the interpolation characteristics desired during a scaling operation. 
     FIG. 5 illustrates a scaling circuit  500  that may be used to implement a different interpolation function for each of the domains. The scaling circuit  500  includes a programmable processor  504  that is capable of performing three different interpolation functions for each domain of both u and v axes. Programmable interpolation circuits  508   a-c  receive the fractional coordinates rU and rV of the destination pixel P d  and determine whether to perform the programmed interpolation function. Ratios p u  and p v  are provided to each of the programmable interpolation circuits  508   a-c  in order for each circuit to identify whether the fractional coordinates are within the respective domains. As illustrated, programmable interpolation circuit  508 a performs the interpolation functions f 0 (rU) and g 0 (rV) for rU and rV values within the first domain; programmable interpolation circuit  508   b  performs the interpolation functions f 1 (rU) and g 1 (rV) for rU and rV values within the second domain; and programmable interpolation circuit  508   c  performs the interpolation functions f 2 (rU) and g 2 (rV) for rU and rV values within the third domain. 
     The resultant output f(rU) and g(rV) of the programmable interpolation circuits  508   a-c  is provided to a conventional bilinear interpolation circuit  512 . The bilinear interpolation circuit  512  also receives the color values C s0 -C s3  of the four source pixels P s0 -P s3  adjacent to the destination pixel P d  based on its fractional coordinates rU and rV. It will be appreciated by those of ordinary skill in the art that the color of the destination pixel P d  and the color of the four adjacent source pixels C s0 -C s3  typically consist of several color components. For example, the destination pixel color value C d  and the source pixel colors C s0 -C s3  may be the combination of red, green, and blue color components. Consequently, as it is well known in the art that the bilinear interpolation circuit  512  includes circuitry to perform bilinear interpolation for each of the color components although the circuitry is not shown in FIG.  5 . As is well known in the art, the bilinear interpolation circuit  512  calculates the color value C d  of the destination pixel P d  from the following equation: 
     
       
           C   d =Weight 0   ·C   s0 +Weight 1   ·C   s1 +Weight 2   ·C   s2 +Weight 3   ·C   s3 . 
       
     
     where 
     
       
         Weight 0 =(1 −rU )·(1 −rV ), Weight 1 =( rU )·(1 −rV ), 
       
     
     
       
         Weight 2 =(1 −rU )·( rV ), and Weight 3 =( rU )·( rV ). 
       
     
     With the input to the bilinear interpolation circuit  512  being f(rU) and g(rV), the weighting values are: 
     
       
         Weight 0 =(1 −f ( rU ))·(1 −g ( rV )), Weight 1   =f ( rU )·(1 −g ( rV )), 
       
     
     
       
         Weight 2 =(1 −f ( rU ))· g ( rV ), and Weight 3   =f ( rU )· g ( rV ). 
       
     
     As mentioned previously, each function can be tailored to create a resulting non-linear interpolation function having the interpolation characteristics desired during a scaling operation. 
     In an embodiment of the present invention, the non-linear interpolation function applied for the first domain, that is, where the destination pixel P d  is located entirely within a source pixel P s0 , ignores the color values of the other three adjacent source pixels P s1 -P s3 , and calculates the color value of the destination pixel P d  based solely on the color value of the source pixel in which it is located. However, in the second and third domains, that is, where a portion of the destination pixel P d  overlaps at least another one of the other three adjacent source pixels P s0 -P s3 , a linear interpolation function is applied to determine the weighting values for the color of the source pixels P s0 -P s3  according to the relative position of the destinations pixel P d . The non-linear interpolation function is defined as:            f        (   rU   )       =     {           0                 if                 rU                   ε   [     0   ,     1   -     p   u         )                     1     p   u       ·     (     rU   +     p   u     -   1     )                     if                 rU                   ε   [       1   -     p   u       ,     1   -       p   u     2         )                     1     p   u       ·     (     rU   +     p   u     -   1     )                     if                 rU                   ε              [       1   -       p   u     2       ,   1     )             }       ,              and             g        (   rV   )       =     {           0                 if                 rV                   ε   [     0   ,     1   -     p   v         )                     1     p   v       ·     (     rV   +     p   v     -   1     )                     if                 rV                   ε   [       1   -     p   v       ,     1   -       p   v     2         )                     1     p   v       ·     (     rV   +     p   v     -   1     )                     if                 rV                   ε              [       1   -       p   v     2       ,   1     )             }                            
     where f(rU) is the non-linear interpolation function along the horizontal axis, g(rV) is the non-linear interpolation function along the vertical axis, and p u  and p v  represent the relative size of the destination pixel P d  and source pixels P s  along the horizontal and vertical axes, respectively. 
     FIG. 6 illustrates a conventional linear interpolation function  610  and non-linear interpolation function  620  representative of the previously described function for a scaling operation that enlarges a source image having a 640×480 pixel resolution to a destination image having a 1024×768 pixel resolution. The relative size of the destination pixels to the source pixels along each axis is: 
     
       
           p   u =1024/640=0.625, and 
       
     
     
       
           p   v =768/480=0.625. 
       
     
     As illustrated in FIG. 6, the contribution to the color value of the destination pixel Pd by the source pixels P s1 -P s3  for fractional coordinates rU or rV less than 0.375 (i.e., rU and rV in the first domain) is kept to zero. The color value of the destination pixel P d  is based solely on the color value of the source pixel P s0  when the fractional coordinates are within the first domain. As the fractional coordinates exceed 0.325 (i.e., rU and rV are in the second or third domain), a linear interpolation function is used to determine the weighting values for calculating the color value of the destination pixel P d . 
     FIG. 7 illustrates an adaptive scaling circuit  700  that may be alternatively used to implement embodiments of the present invention. The scaling circuit  700  is described in co-pending U.S. patent application Ser. No. 09/607,757 to Wright et al., entitled APPARATUS AND METHOD FOR ADAPTIVE TRANSFORMATION OF FRACTIONAL PIXEL COORDINATES FOR CALCULATING COLOR VALUES, filed on Jun. 29, 2000, which is incorporated herein by reference. The adaptive scaling circuit  700  includes two multiplexed look-up tables (LUTs)  716  and  718  coupled to a conventional bilinear interpolation circuit  730 . Each LUT  716  and  718  stores values f(rU) 0 -f(rU) n  and f(rV) 0 -f(rV) n  that are resultants of a respective interpolation function which is associated with each axis. The fractional coordinates rU and rV of the destination pixel P d  are used as indices to select values stored in the respective LUTs  716  and  718  to be provided to the bilinear interpolation circuit  730 . The values provided by the LUTs  716  and  718  are used by the bilinear interpolation circuit  730  to calculate weighting values for the color value calculation of the destination pixel P d . Use of the LUTs  716  and  718  takes advantage of the well known conventional bilinear interpolation circuit  730 , and enables the resulting scaling circuit  700  to perform various interpolation functions. A more detailed explanation of the scaling circuit  700  is provided in the previously referenced patent application. 
     As applied to embodiments of the present invention, the LUTs  716  and  718  of the scaling circuit  700  may be programmed to store the resultant values of the non-linear interpolation functions f(rU) and g(rV) described previously. That is, for a scaling operation, the appropriate resultant values are programmed into the LUTs  716  and  718  that represent the respective interpolation function applied for each of the domains. New resultant values may need to be programmed into the LUTs  716  and  718  for each scaling operation since the domains are defined as a function of the scaling ratio. The interpolation function applied for a domain may be a function of the scaling ratio as well. 
     Although the examples provided herein have assumed that scaling along the horizontal and vertical axes are symmetrical, and that the same non-linear interpolation function is applied along both axes, it will be appreciated that the scaling function along the horizontal axis may be different than that applied along the vertical, and that the scaling ratio for each axis may be different. Moreover, it will be appreciated that although embodiments of the present invention have discussed three different domains, more or less domains may be defined without exceeding the scope of the present invention. 
     From the foregoing it will be appreciated that, although specific embodiments of the invention have been described herein for purposes of illustration, various modifications may be made without deviating from the spirit and scope of the invention. Accordingly, the invention is not limited except as by the appended claims.