Abstract:
A hybrid bilinear scaling (Qscale) scheme produces output images that have comparable quality to traditional bilinear interpolation algorithms, but requires a less complex hardware implementation. The Qscale system does not reverse-map output pixels back to arbitrary locations in the input space as defined by the mapping function. Rather all pixel values and locations are calculated after all of the original input pixels are mapped to the output. That is, all of the original image pixels are used “as-is” in the resultant scaled image. New pixels are generated from the original input pixels to meet the desired output pixel dimensions. Because only new pixels are computed, the Qscale system is less computationally complex. The computational requirements are further reduced because new pixels are computed between original pixel pairs meaning only two pixels are involved in the computation. Coefficients can be chosen to be fractional powers of two (0.5, 0.25, 0.125, etc) for the interpolation calculation between pixel pairs. By selecting coefficients this way, the linear computation reduces to a “shift-and-add” operation, which is easily implemented in hardware.

Description:
BACKGROUND OF THE INVENTION 
     The invention relates to changing the size of images and more particularly to a hybrid bilinear scaling system that provides high quality output images. 
     The process of changing the size of an image is commonly referred to as scaling. There are several well-defined and well-understood methods used for image scaling. An overview of the subject is described in A  Simplified Approach to Image Processing , R. Crane, Prentice Hall, Inc., 1997. 
     Scaling methods range from trivial, pixel-replication techniques to more complex, higher order algorithms. When selecting a particular scaling technique for a given application, a tradeoff is made between computational complexity and resultant image quality. For applications with stringent computational limits or loose image quality requirements, pixel-replication is a popular method used for scaling. Conversely, if an application can afford higher computational costs, or if there are tighter constraints on the output image quality, more complex scaling schemes are used. The most common alternative to pixel replication is bilinear interpolation, which provides improvement in image quality at a moderate computational expense. 
     With bilinear interpolation, new or scaled pixels are computed as a weighted sum of neighboring pixels. Weights are computed linearly and proportionally to the distance the new pixel is to existing or neighboring pixels. The new pixel locations, relative to the input (original) pixels, are determined by reverse-mapping the desired, destination pixels back to the input space. In most cases, the original input pixels are not used in the resultant output image. The only time input pixels are directly mapped to an output pixel is when the reverse-mapping of the output pixel location happens to land exactly on a grid location in the original input space. Thus, techniques, like bilinear interpolation, are computationally exhaustive and require complex scaling circuitry. Accordingly, a need remains for a simple scaling technique that produces high image quality. 
     SUMMARY OF THE INVENTION 
     A hybrid bilinear scaling scheme, dubbed Qscale, produces output images that have comparable quality to traditional bilinear interpolation algorithms, but requires a less complex hardware implementation. The Qscale algorithm system takes a different approach to determine the location and value of output pixels. Rather than reverse-mapping output pixels back to arbitrary locations in the input space (as defined by the mapping function), all output pixel values and locations are calculated after all of the original input pixels are mapped to the output image. That is, all of the original image pixels are used “as-is” in the resultant scaled output image. New pixels are generated from the original input pixels to meet the desired output pixel dimensions. The new pixel values are linearly interpolated between pixel pairs. Since all original pixels in the input image are used in the output image, the Qscale system is less computationally complex because fewer new pixels have to be generated, and there is not a “reverse-mapping” requirement in the computation. 
     The computational requirements are further reduced because new pixels are computed between original pixel pairs, meaning that there are only two pixels involved in the interpolation computation of a new pixel. Since new pixels are computed linearly from existing pixels, coefficients can be chosen to be fractional powers of two (0.5, 0.25, 0.125, etc.) for the interpolation calculation between pixel pairs. By selecting coefficients this way, the linear computation reduces to a “shift-and-add” operation, which is extremely efficient in hardware. By constraining the computation to be between two existing pixels, a fixed set of coefficients can be selected such that new pixels are computed as a weighted average that is proportional to the relative location of the new pixel between the existing pixels. The number of new pixels generated between each pair of pixels is proportional to the desired scale factor. 
     The foregoing and other objects, features and advantages of the invention will become more readily apparent from the following detailed description of a preferred embodiment of the invention which proceeds with reference to the accompanying drawings. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a diagram showing a prior art bilinear scaling technique. 
     FIG. 2 is a diagram showing a hybrid bilinear scaling scheme (Qscale) according to the invention. 
     FIG. 3A is a detailed diagram showing how Qscale is performed in FIG.  2 . 
     FIG. 3B is a table of sample Qscale interpolation coefficients. 
     FIG. 4 is a block diagram showing one hardware implementation of the Qscale system according to the invention. 
     FIG. 5 is a block diagram showing a hardware example of a Qscale system that can insert N≦8 new pixels between original input pixels. 
     FIG. 6 shows one implementation example for a Qscale coefficient generator shown in  5 . 
     FIG. 7 shows one implementation example for a Qscale accumulation circuit shown in FIG.  5 . 
     FIG. 8 is a diagram showing how the accumulation circuit in FIG. 7 operates. 
    
    
     DETAILED DESCRIPTION 
     An example of a prior art bilinear interpolation is shown in FIG.  1 . Small “x&#39;s” denote the locations of the reverse-mapped output pixels  20 . The “x&#39;s” denote where the new pixels  16  would be located if resolution of an input image  14  were increased to match the number of pixels  20  in an output or destination image  22 . The actual values of the new pixels  16  are computed using interpolation. That is, the values for new pixels  16  are computed as a weighted-average of the four original nearest neighbor pixels  18 . The weights are linearly proportional to the distance from the neighboring original pixels  18  to the new pixel  16 . 
     Referring to a cutaway  24  in FIG. 1, the prior art bilinear interpolation operation is illustrated. Values at points A and B are both computed by performing a linear interpolation between the original pixels  26 ,  28  and  30 ,  32 , respectively. After values for points A and B are computed, a final pixel  34  is computed by performing another linear interpolation between the values derived from points A and B. 
     To compute the new pixel value  34 , three linear interpolations are required. Each linear interpolation involves two multiplies, a shift, and an add. In addition, the reverse mapping requires multiply/divide type operations to compute the new pixel locations. The computational requirements are shown in the following equations: 
     Typical Interpolation Calculation: 
     
       
         Pnew=P1+(x−x1)/(x2−x1)·(P2−P1)  (1) 
       
     
     Where: P1, P2=Pixels to interpolate between; x=Position of new pixel relative to the given pixels; and x1, x2=Positions of pixels used for the interpolation. 
     Typical Reverse-Mapping Calculation: 
     
       
         (x,y)=(x out /SF,y out /SF)  (2) 
       
     
     Where: x,y=Positional coordinates of the new pixel relative to the input space; 
     X out , Y out =Positional coordinates of the new pixel relative to the output space (integer indices); and SF=Specified scale factor. 
     Referring to FIG. 2, small “x&#39;s” denote the new pixel locations  16 . Circles denote existing pixels  18  in the original image  14 . Since new pixels  16  are computed from existing pixel pairs  18 , the Qscale process is broken down into horizontal and vertical interpolation steps. First, new pixels  16  are interpolated between existing pixel pairs in a horizontal direction, and then a similar step is performed in the vertical direction. It would be equally effective to perform the vertical interpolation step first, followed by the horizontal interpolation step. In either case, the second step involves computing new pixels from pixel pairs that came from the previous interpolation step. 
     The new pixels derived during horizontal scaling that are vertically adjacent to each other, are used along with the original pixel values by the Qscale system to generate the new pixels that reside between each adjacent row in the original image  14 . For example, during horizontal scaling, original pixels  15  and  27  are used to derive new pixel  23 . During vertical scaling, original pixels  15  and  17  are used to generate new pixels  19 . However, the new pixels  21  are derived from the new pixels  23  and  25  that were previously derived during the horizontal scaling. As shown in FIG. 2, all of the original image pixels  18  are preserved in the output image  22  and are represented by non-shade circles. Shaded circles represent the new pixels  16  in the output image  22 . Thus, computations are only required for the new pixels  16 . 
     There are also new pixels  16  in columns  36  and rows  38  on the right-most and bottom-most edges of output image  22 , which do not reside between existing pixels  18 . This is a boundary condition that is encountered whenever pixel processing is required outside of the boundary of the original image  14 . The boundary condition is handled by duplicating the last row  40  and column  42  of the original image  14 . 
     Hybrid-Bilinear Interpolation 
     FIG. 3A is a detailed diagram showing how new pixels  16  are generated between an original pixel pair  44 ,  46  in the input image  14 . The number of new pixels  16  that are computed is proportional to an applied scale factor. The values of the new pixels  16  are linearly proportional to their relative distances to the existing pixels  44  and  46 . The value for the new pixels  16  are, therefore, dependent upon the number of new pixels, and indirectly proportional to the scale factor. The number of new pixels  16  generated between adjacent pairs of original pixels  44  and  46  and the values of the new pixels  16  for scale factors of 2.0, 3.0, 4.0, 5.0 and 6.0 are shown in boxes  48 ,  50 ,  52 ,  54  and  56 , respectively. A set of coefficients are defined which specify the linear interpolation between existing pixels  44  and  46  based upon the number of new pixels  16  being generated. Since it is desired that the results model a linear interpolation, the only constraint is that the coefficients used to derive the new pixel values must have a sum equal to unity. 
     The coefficients are defined mathematically as follows: 
     
       
         Pn=Σ n [α n ·P1+β n ·P2]; n=1,2, . . . , N  (3) 
       
     
     Where: α n , β n =Coefficients; α n +β n =1, for all n; Pn=n th  new pixel; P1, P2=a selected input pair of pixel values; and N=Number of new pixels to be computed. 
     From equation 3, it can be seen that the coefficients α n  and β n  come in pairs. Each coefficient of the pair corresponds to a weight that is applied to the respective pixel from the given input pixel pair  44 ,  46 . For each scale factor, there will be a set of N coefficient pairs, where N is computed from the specified scale factor. 
     For example, two new pixels  16 A and  16 B are inserted between original pixels  44  and  46  in box  50 . The coefficient α 1  for the first new pixel  16 A is ¾ and the coefficient β 1  for the first new pixel  16 A is ¼. Because the new pixel  16 A is closer to original pixel  44  (P1), the coefficient α 1  applied to original pixel P1 is larger and the coefficient β 1  applied to original pixel  46 (P2) is smaller. The coefficient α 2  for the second new pixel  16 B is ¼ and the coefficient β 2  for the second new pixel  16 B is ¾. Accordingly, the coefficient α 2  is applied to original pixel P1 is smaller and the coefficient β 2  applied to original pixel  46 (P2) is larger. 
     Since the coefficients α 2  and β n  are computed linearly between two pixels  44  and  46 , and since the two given pixels are either horizontally or vertically aligned, the Qscale interpolation is termed as hybrid-bilinear. The Qscale system produces scaled image quality that is comparable to higher-order schemes. For (N&lt;16), experimental results indicate that Qscale produces an output image quality that is indistinguishable from bilinear interpolation for most images. Note, however, that the same fundamental principles hold true with regards to quality for higher values of N. Higher values of N (&gt;16) can be used in the selection of coefficients and can be implemented in hardware or software. 
     Coefficient values α n  and β n  can be any rational number as long as they satisfy the conditions above. There are values that can be selected which are trivial to implement in hardware. In particular, rational coefficients that are powers of two are well suited for hardware implementations. One particular set of coefficients is shown in table 1 of FIG.  3 B. This particular set of coefficients defines the values of N new pixels for inserting between any pair of original pixels where N≦8. FIG. 3B is simply one possible set of coefficients. This set has been shown experimentally to be effective, but any given set of coefficients for any number of new pixels can be used without affecting the Qscale system. 
     It is important to note that while the examples above use only integer scaling factors, non-integer or fractional scaling factors can also be accommodated with the Qscale system. For example, if the scale factor is set to 3.333, then two new pixels would be inserted between the given pixel pairs for every two consecutive pairs of input pixels. Then, three new pixels would be inserted between every third set of pixel pairs. This would have the net effect of scaling by 3.333 across the entire scanline. 
     The actual mechanism used to accomplish this is a modified Bresenham accumulation function, which essentially counts the number of new pixels  16  to be generated between each existing pixel pair. This counting or accumulation process properly distributes the new pixels to maintain the specified scale-factor. The Bresenham accumulation function is used in several existing image processing functions, including interpolation schemes. 
     The Qscale system can be applied to both horizontally aligned and vertically aligned pixels with independent scale factors in each dimension. Therefore, the Qscale system enables arbitrary and independent fractional scaling in both the vertical and horizontal directions. 
     Hardware Implementation 
     As mentioned above, the Qscale system is well suited for an efficient hardware implementation. There are many possible implementations of the Qscale system, therefore, the implementation details described below are kept fairly generic. Specific implementation examples are also described for illustrative purposes which should not be interpreted to limit the scope of the invention. Considerations related to the actual speed, size, or relative Qscale throughput are implementation details that can vary depending upon the specific processing requirement of the application and these variations come within the scope of the present invention. Design issues such as line buffering, two-dimensional versus one-dimensional interpolation, and scanline orientation are not discussed but would be readily implemented by one having average skill. These are items common to all scaling implementations, and they too can vary on a per-implementation basis and come within the scope of the present invention. 
     FIG. 4 is a diagram of a generic implementation for the Qscale system  60 . An interpolation engine comprises essentially two MUXes  62  and  64  and an adder  66 . The MUXes  62  and  64  select which hard-wired coefficients α n  and β n  to use from a coefficient generator  61 . A control line  66  is coupled between an accumulation circuit  94  and MUXes  62  and  64  and determines the number of new pixels (N) that will be derived between consecutive pairs of existing pixels P1 and P2 (FIG. 3A) according to a scale factor. The coefficient generator  61  generates the coefficients α n  and β n  for each n th  new pixel and applies the coefficients α n  and β n  to the two consecutive original pixels P1 and P2 from original image  14 . The two coefficients are applied to the original pixel values and are then added together with the adder  66  to generate the new pixel value Pn(n). 
     The interpolation circuit  60  generates the new pixel values Pn(n) between original pixels P1 and P2. Then the new pixel values are determined for the next two vertically or horizontally adjacent pixels P2 and P3, and so on, repeating for the entire dimension. After all the new pixels are derived for all horizontal rows (or alternatively for all vertical columns), then the new pixels are derived for all vertical columns (or alternatively for all horizontal rows). 
     FIG. 5 shows one Qscale implementation for generating new pixels using Table 1 in FIG. 3B for N≦8. FIG. 6 is a detailed circuit diagram of the coefficient generator  61  in FIG.  5 . Note that no multiplication operations are actually required. That is, each of the coefficient values α n  and β n  are computed from a simple shift-and-add operation. A coefficient value ½ is generated using a one-bit shifter  72  in circuit  70 . Similarly, a coefficient value ¼ is generated in circuit  74  using a two bit shifter  76  and a ⅛ coefficient value is generated in circuit  78  by using a three bit shifter  80 . A ¾ coefficient value is generated in circuit  82  by first shifting the original pixel P1 one bit to the left (2P1) with shifter  84  and then adding the output of shifter  84  with the original pixel value P1 with adder  83  (3P1). The value 3P1 is then divided by ¼ by shifting the output of adder  83  two bits to the right (¾P1). Similar shifting is used to generate the coefficient values ⅜ in circuit  88 , ⅝ in circuit  90  and the ⅞ in circuit  92 . 
     Note that no multiplication operations are actually required. That is, each of the coefficient values α n  and β n  are computed from a simple shift-and-add operation. It should also be appreciated that other shift and add operations can generate the same results. For example, in circuit  82 , the coefficient value ¾P1 can be generated by first shifting the value of P1 one bit to the right (½P). The output of adder  83  is then {fraction (3/2)}P1. The shifter  86  could then generate the value ¾P1 by shifting the output of adder  83  one bit to the right (½). 
     The example shown in FIG. 6 shows the Qscale coefficients applied to the original pixel P1 but the same circuitry is used for generating the coefficients applied to the value for original pixel P2. The single-stage Qscale system shown in FIGS. 5 and 6 can be duplicated to compute up to 8 new pixels in parallel. If throughput constraints allow, the coefficient generator  61  can be implemented as a single-stage computational unit that generates up to 8 pixels in a serial fashion. Alternatively, separate vertical and horizontal stages can be used at the same time. After new pixels are derived for two rows or two columns of the original image, the other stage can begin generating the new pixels in the perpendicular direction. Thus, the new pixels in the output image  22  can be generated in less time. 
     A particular hardware implementation for a modified Bresenham accumulator circuit  94  is shown in FIG.  7 . The accumulator circuit  94  keeps track of the number of new pixels to insert between each original pair of adjacent pixels according to a given scale factor. The accumulation circuit  94  is a fixed-integer implementation of a floating-point procedure. The output of the accumulator circuit  94  is used as one of the MUX controls  66  for the interpolation engine shown in FIG.  5 . In other words, the accumulator circuit  94  computes the number of new pixels N. 
     An example of how the accumulator works is shown in FIG.  8 . Referring to FIGS. 7 and 8, a scale factor 2.625 is loaded into a register  96 . The upper  8  bits of register  96  stores the integer value of the scale factor (2) and the lower 8 bits of register  96  store the fractional portion of the scale factor (0.625). Latch  100  in FIG. 7 is originally initialized to zero. On the first iteration through the accumulation circuit  94 , the value 2.625 is added to the zero value in the lower 8 bits of latch  100  for a value of 2.625. Since the upper 8 integer bits of latch  100  (N+1) is equal to 2, the value of N equal to 1. Accordingly, one new pixel  106  is generated by the Qscalc system between the first pair of original pixels  102  and  104 . The coefficient values for N=1 in the coefficient table 1 in FIG. 3B are α 1 =½ and β 1 =½. The interpolation engine MUX  62  in FIG. 5 selects the ½ P1 output from circuit  70  in coefficient generator  61 . Similarly, the interpolation engine MUX  64  in FIG. 5 selects the ½ P2 output from coefficient generator  61  in FIG.  5 . Interpolation engine adder  66  then generates the new pixel value  106 . 
     On the second iteration, the accumulation circuit  94  determines the number of new pixels that are to be interpolated between the next adjacent pair of original pixels  104  and  108 . The scale factor 2.625 in register  96  is added to the fraction value 0.625 in the lower 8 bits of latch  100  from the previous iteration. The adder  98  generates the value 2.625+0.625=3.25. 
     The integer value of latch  100  (N+1) is equal to 3 and therefore the number of new pixels inserted between original pixels  104  and  108  is equal to N=2. 
     Table 1 in FIG. 3B is then referenced to determine the set of coefficient values for N=2. The first new pixel  110  is derived using the coefficient values α 1 =¾ and β 1 =¼ and the second new pixel  112  is derived using the coefficient values α 1 =¼and β 2 =¾. The new pixel values are then interpolated from the original pixels  104  and  108  using the interpolation engine shown in FIG. 5 as described above. 
     A next iteration of the accumulation circuit  94  adds the fractional value from the previous iteration (0.25) to the scale factor 2.625 to generate a new value 2.875 in latch  100 . Thus, only one new pixel  116  is generated between the next pair of original pixels  108  and  114 . In a similar manner, two new pixels  118  and  120  are generated on the next iteration of accumulation circuit  94 . On the average for the horizontal line shown in FIG. 8, approximately 2.625 new pixels are generated for every original input pixel for a total of 10 pixels. 
     Thus, the Qscale system provides selectable interpolated scalability using simple adder and shifter circuitry while at the same time reducing processing by using all the original pixels as part of the scaled output image. The Qscale system can be used in printers, digital cameras, video processors, or any other image processing system that needs to change the size of an image. 
     Having described and illustrated the principles of the invention in a preferred embodiment thereof, it should be apparent that the invention can be modified in arrangement and detail without departing from such principles. I claim all modifications and variation coming within the spirit and scope of the following claims.