Patent Publication Number: US-8121434-B2

Title: Multi-pass image resampling

Description:
BACKGROUND 
     Image resampling, which is sometimes called image warping or texture mapping, is the process of geometrically transforming digital images. One type of image resampling is the multi-pass technique. Multi-pass techniques use multiple one-dimensional image re-scaling and/or shearing passes, combined with filtering of varying quality, to implement image affine image transforms. These techniques, while requiring a significant amount of processing power, result in resampled images exhibiting high visual quality. While processing costs are often a concern, today&#39;s central processing unit (CPU) multi-media accelerators and graphics processing units (GPUs) have more than enough power to support multi-pass techniques, especially for applications where visual quality is important, such as photo manipulation, animated slideshows, panoramic image and map viewing, and visual effects. 
     SUMMARY 
     Multi-pass image resampling technique embodiments described herein generally involve using one-dimensional filtering stages to achieve high quality results at low computational cost. Using one dimensional resampling enables the use of small resampling kernels, thus producing highly efficiency. These embodiments also ensure that very little aliasing occurs at each stage by upsampling the image during shearing steps in a direction orthogonal to the shearing to prevent aliasing when necessary, and then downsampling the image to its final size along with high-quality low-pass filtering. 
     In one general four-stage embodiment, the multi-pass image resampling begins with a first pass through the image being resampled. In this first pass a vertical upsampling factor is computed. The vertical upsampling factor represents the degree to which the image is to be upsampled in the vertical direction. It is noted that in computing the vertical upsampling factor a determination is made if the desired horizontal shearing and scaling is likely to cause significant aliasing. If not, no vertical upsampling is necessary, and the vertical upsampling factor can be set to a prescribed value (e.g., 1) that is indicative of the non-aliasing condition. To this end, the image is next upsampled in the vertical direction using the vertical upsampling factor, but only if the vertical upsampling factor does not equal the prescribed value. If the factor equals the prescribed value, the vertical upsampling is skipped. In a second pass through the image, the image is horizontally sheared and scaled in a prescribed manner, which includes employing horizontal filtering. In addition, a horizontal upsampling factor is computed. The horizontal upsampling factor represents the degree to which the image is to be upsampled in the horizontal direction. It is noted in this case that in computing the horizontal upsampling factor a determination is made if the desired vertical shearing and scaling is likely to cause significant aliasing. If not, no horizontal upsampling is necessary, and the horizontal upsampling factor can be set to a prescribed value (e.g., 1) that is indicative of the non-aliasing condition. To this end, the image is next upsampled in the horizontal direction using the horizontal upsampling factor, but only if the horizontal upsampling factor does not equal the prescribed value. If the horizontal factor equals the prescribed value, the horizontal upsampling is skipped. 
     In a third pass through the image, a low pass filtering is applied to the image in the vertical direction. In addition, if the image was vertically upsampled, it is now vertically downsampling to a prescribed degree. The image is also vertically sheared and scaled in a prescribed manner, which includes employing vertical filtering. Then, in fourth pass through the image, a low pass filtering is applied in the horizontal direction. In addition, if the image was horizontally upsampled, it is now horizontally downsampling to a prescribed degree. The result of the fourth pass is the desired resampled image. 
     It should also be noted that this Summary is provided to introduce a selection of concepts, in a simplified form, that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter. 
    
    
     
       DESCRIPTION OF THE DRAWINGS 
       The specific features, aspects, and advantages of the disclosure will become better understood with regard to the following description, appended claims, and accompanying drawings where: 
         FIG. 1  is a series of graphs showing a progressive one-dimensional signal resampling of a signal, where the signal is shown in the upper row of graphs and the Fourier transform of each signal is shown in a graph just below each signal graph in the second row. 
         FIG. 2  is a series of images showing a progressive horizontal resampling, where the top row depicts the image as it undergoes (from left to right) vertical upsampling, then horizontal shear and finally vertical downsampling. The bottom row represents the Fourier transform of the image just above it. 
         FIG. 3  is a series of images showing a progressive four-pass horizontal resampling, where the top row depicts the image as it undergoes (from left to right) vertical upsampling, then horizontal shear and horizontal upsampling, then vertical shear and vertical downsampling, and finally horizontal downsampling. The bottom row represents the Fourier transform of the image just above it. 
         FIGS. 4 and 5  are images geometrically illustrating how u max  and v max  values are determined. 
         FIGS. 6A-B  are a continuing flow diagram generally outlining one embodiment of a process for multi-pass image resampling involving four passes through the image with horizontal shearing and scaling coming before vertical shearing and scaling. 
         FIGS. 7A-B  are a continuing flow diagram generally outlining one embodiment of a process for multi-pass image resampling involving four passes through an image selected from a mipmap or ripmap. 
         FIGS. 8A-B  are a continuing flow diagram generally outlining another embodiment of a process for multi-pass image resampling involving four passes through the image with vertical shearing and scaling coming before horizontal shearing and scaling. 
         FIG. 9  is a diagram depicting a general purpose computing device constituting an exemplary system for implementing multi-pass image resampling technique embodiments described herein. 
     
    
    
     DETAILED DESCRIPTION 
     In the following description of multi-pass image resampling technique embodiments reference is made to the accompanying drawings which form a part hereof, and in which are shown, by way of illustration, specific embodiments in which the technique may be practiced. It is understood that other embodiments may be utilized and structural changes may be made without departing from the scope of the technique. 
     1.0 Multi-Pass Image Resampling 
     The multi-pass image resampling technique embodiments described herein employ a series of one-dimensional filtering stages to achieve good efficiency while maintaining high visual fidelity. In one embodiment, high-quality (multi-tap) image filtering is used inside each one-dimensional resampling stage. Because each stage only uses one-dimensional filtering, the overall computation efficiency is very good and amenable to graphics processing unit (GPU) implementation using pixel shaders. This approach also ensures that none of the stages performs excessive blurring or aliasing, so that the resulting resampled signal contains as much high-frequency detail as possible while avoiding aliasing. In general, this is accomplished by first upsampling the image during shearing steps in a direction orthogonal to the shearing to prevent aliasing, and then downsampling the image to its final size with high-quality low-pass filtering. 
     The following sections provide a more detailed description of the multi-pass image resampling technique embodiments. 
     1.1 One-Dimensional Resampling 
     One-dimensional signal resampling can be envisioned using the framework shown in  FIG. 1 . The original source image (or texture map as the case may be) is represented by a sampled signal f(i), as shown in graph  100 . Because the signal is sampled, its Fourier transform is infinitely replicated along the frequency axis. This is show in graph  102  directly below graph  100 . To resample the signal, it is first (conceptually) converted into a continuous signal g(x) by convolving it with an interpolation filter, h 1 (x), 
                       g   1     ⁡     (   x   )       =       ∑   i     ⁢       f   ⁡     (   i   )       ⁢         h   1     ⁡     (     x   -   i     )       .                 (   1   )               
The result of this convolution is shown in graph  104 . In the frequency domain, this corresponds to multiplying the original signal spectrum F(u)= {f(x)}, with the spectrum of the interpolation filter H 1 (u) to obtain:
 
 G   1 ( u )= F ( u ) H   1 ( u ).  (2)
 
The result of this is shown in graph  106 .
 
     If the filter is of insufficient quality, phantom replicas of the original spectrum persist in higher frequencies, as shown by the dotted line in graph  106 . These replicas correspond to the aliasing introduced during the interpolation process, and are often visible as unpleasant discontinuities (sometimes referred to as jaggies) or motion artifacts (sometimes referred to as crawl). 
     Examples of interpolation filters include linear interpolation, cubic interpolation and windowed sinc interpolation. In tested embodiments, a raised cosine-weighted sinc filter with 4 cycles (9 taps when interpolating) was employed with success in that it maintains high visual fidelity. Next, a spatial transformation is applied to the original signal domain, e.g.,
 
 x=ax′+t,   (3)
 
which is an affine spatial warp where a is a scale factor and t is a translation. Note how the inverse warp is always specified, i.e., the mapping from final pixel coordinates x′ to original coordinates x.
 
     The warped or transformed continuous signal and its Fourier transform (in the affine case) are 
                         g   2     ⁡     (     x   ′     )       =           g   1     ⁡     (       ax   ′     +   t     )       ⇔       G   2     ⁡     (   u   )         =       1   a     ⁢       G   1     ⁡     (     u   /   a     )       ⁢     ⅇ     j   ⁢           ⁢     ut   /   a               ,           (   4   )               
where j is the imaginary number j=√(−1). For the purpose of an example, assume the original signal is being compressed as shown in graph  108 . This causes the Fourier transform to become dilated (stretched) along the frequency axis, as shown in graph  110 . Before resampling the warped signal, it is pre-filtered (e.g., using a low-pass filter) by convolving it with another kernel,
 
 g   3 ( x )= g   2 ( x )* h   2 ( x )   G   3 ( u )= G   2 ( u ) H   2 ( u ).  (5)
 
The results of this are shown in graphs  112  and  114 . This is particularly necessary if the signal is being minified or decimated, i.e., if a&gt;1 in Eq. (3). If this filtering is not performed carefully, some additional aliasing may be introduced into the final sampled signal (see the dotted line in graph  118 ).
 
     Fortunately, because of the linearity of convolution operators, the three stages of filtering and warping can be combined into a single composite filter
 
 H   3 ( u )= H   1 ( u/a ) H   2 ( u ),  (6)
 
which is often just a scaled version of the original interpolation filter h 1 (x). For ideal (sinc) reconstruction and low-pass filtering, the Fourier transform is a box filter of the smaller width, and hence the combined filter is itself a sinc (of larger width). The final discrete convolution can be written as
 
                             f   ′     ⁡     (   i   )       =       g   3     ⁡     (   i   )                   =       ∑   j     ⁢         h   3     ⁡     (     ai   +   t   -   j     )       ⁢     f   ⁡     (   j   )                         =       ∑   j     ⁢       h   ⁡     (       [     ai   +   t   -   j     ]     /   s     )       ⁢     f   ⁡     (   j   )             ,                 (   7   )               
where s=max(1, |a|). where here j refers to the summation index that ranges over all of the pixels (samples) that have non-zero support in the function h 3 ([ai+t−j]/s). The results of this are shown in graph  116  and it associated spectra graph  118 .
 
     The filter in Eq. (7) is a polyphase filter, since the filter coefficients being multiplied with the input signal f(j) are potentially different for every output value of i. To see this, Eq. (7) can be rewritten as 
                         f   ′     ⁡     (   i   )       =         ∑   j     ⁢       h   ⁡     (       [     ai   +   t   -   j     ]     /   s     )       ⁢     f   ⁡     (   j   )           =       ∑   j     ⁢         h   P     ⁡     (         j   *     -   j     ;   ϕ     )       ⁢     f   ⁡     (   j   )               ,           (   8   )               
where j*=└ai+t┘, φ=ai+t−j*, and h P (k;φ)=h([k+φ]/s), where k and φ are the free parameters inside the definition of h P . The values in h(k;φ) can be precomputed for a given value of s and stored in a two-dimensional look-up table if desired. In one embodiment, the values of h(k;φ) are re-normalized so that Σ k h (k; φ)=1. The number of discrete fractional values of φ is related to the desired precision of the convolution, and is typically 2 b , where b is the number of bits of desired precision in the output (e.g., say 10-bits for 8-bit RGB images to avoid error accumulation in multi-pass transforms). Eq. (7) can be written in a functional form as
 
 f ′= ( f;h,s,a,t ).  (9)
 
     In other words,   is an algorithm, parameterized by a continuous filter kernel h(x), scale factors s and a, and a translation t, which takes an input signal f(i) and produces an output signal f′(i). This operator is generalized in the next section to a pair of horizontal and vertical scale/shear operators. 
     1.2 Two-Dimensional Zooming 
     Two-pass separable transforms are accomplished by first resampling the image horizontally and then resampling the resulting image vertically (or vice-versa). These operations can be performed by extending the above-described one-dimensional resampling operator of Eq. (9) to a pair of horizontal and vertical image resampling operators, 
     
       
         
           
             
               
                 
                   
                     
                       f 
                       ′ 
                     
                     = 
                     
                       
                         
                           ⁢ 
                           
                             ( 
                             
                               f 
                               , 
                               h 
                               , 
                               s 
                               , 
                               
                                 a 
                                 0 
                               
                               , 
                               
                                 a 
                                 1 
                               
                               , 
                               t 
                             
                             ) 
                           
                         
                         ⇔ 
                         
                           
 
                         
                         ⁢ 
                         
                           
                             f 
                             ′ 
                           
                           ⁡ 
                           
                             ( 
                             
                               i 
                               , 
                               j 
                             
                             ) 
                           
                         
                       
                       = 
                       
                         
                           ∑ 
                           k 
                         
                         ⁢ 
                         
                           
                             h 
                             ⁡ 
                             
                               ( 
                               
                                 s 
                                 ⁡ 
                                 
                                   [ 
                                   
                                     
                                       
                                         a 
                                         0 
                                       
                                       ⁢ 
                                       i 
                                     
                                     + 
                                     
                                       
                                         a 
                                         1 
                                       
                                       ⁢ 
                                       j 
                                     
                                     + 
                                     t 
                                     - 
                                     k 
                                   
                                   ] 
                                 
                               
                               ) 
                             
                           
                           ⁢ 
                           
                             f 
                             ⁡ 
                             
                               ( 
                               
                                 k 
                                 , 
                                 j 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   and 
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
             
               
                 
                   
                     f 
                     ′ 
                   
                   = 
                   
                     
                       
                         ⁢ 
                         
                           ( 
                           
                             f 
                             , 
                             h 
                             , 
                             s 
                             , 
                             
                               a 
                               0 
                             
                             , 
                             
                               a 
                               1 
                             
                             , 
                             t 
                           
                           ) 
                         
                       
                       ⇔ 
                       
                         
 
                       
                       ⁢ 
                       
                         
                           f 
                           ′ 
                         
                         ⁡ 
                         
                           ( 
                           
                             i 
                             , 
                             j 
                           
                           ) 
                         
                       
                     
                     = 
                     
                       
                         ∑ 
                         k 
                       
                       ⁢ 
                       
                         
                           h 
                           ⁡ 
                           
                             ( 
                             
                               s 
                               ⁡ 
                               
                                 [ 
                                 
                                   
                                     
                                       a 
                                       1 
                                     
                                     ⁢ 
                                     t 
                                   
                                   + 
                                   
                                     
                                       a 
                                       0 
                                     
                                     ⁢ 
                                     j 
                                   
                                   + 
                                   t 
                                   - 
                                   k 
                                 
                                 ] 
                               
                             
                             ) 
                           
                         
                         ⁢ 
                         
                           
                             f 
                             ⁡ 
                             
                               ( 
                               
                                 i 
                                 , 
                                 j 
                               
                               ) 
                             
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
           
         
       
     
     Note that these operators not only support directional scaling and translation, but also support shearing (i.e., using a different translation for each row or column), which is used for more complex transformations. Image minification (zooming out) can be made more efficient using mipmaps or ripmaps as will be described in more detail later. 
     1.3 Shearing 
     In a simplified case of a pure horizontal shear, 
                     [         x           y         ]     =       [             a   0           a   1             0       1         |         t           0           ]     ⁡     [           x   ′               y   ′             1         ]               (   12   )               
This corresponds to a general implementation of    h  with a 1 ≠0.
 
     In the frequency domain (ignoring the effect of the translation parameter t, since it does not affect aliasing), this corresponds to a transformation of 
     
       
         
           
             
               
                 
                   
                     u 
                     ′ 
                   
                   = 
                   
                     
                       
                         A 
                         T 
                       
                       ⁢ 
                       u 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       where 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         A 
                         T 
                       
                     
                     = 
                     
                       
                         [ 
                         
                           
                             
                               
                                 a 
                                 0 
                               
                             
                             
                               0 
                             
                           
                           
                             
                               
                                 a 
                                 1 
                               
                             
                             
                               1 
                             
                           
                         
                         ] 
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
           
         
       
     
     Thus, it can be seen that a horizontal shear in the spatial domain induces a vertical shear in the frequency domain. This can lead to aliasing. However, upsampling the signal vertically first can ameliorate the aliasing effect. Notice how the original frequency (±1,±1) gets mapped to (±a 0 ,±1±a 1 ), which can be beyond the vertical Nyquist frequency. It is noted that from here on the convention that the frequencies range over [−1,+1] will be used to simplify the notation. 
     In order to avoid aliasing, a three phase approach is implemented for the horizontal case, which generally includes: 
     1. upsampling vertically by the factor r≧1+|a 1 |; 
     2. shearing and scaling horizontally, with filtering to avoid aliasing; and 
     3. low-pass filtering and downsampling vertically. 
     In terms of geometric transformation, this corresponds to factoring 
                     A   =           [         1       0           0         1   /   r           ]     ⁡     [           a   0             a   1     /   r             0       1         ]       ⁡     [         1       0           0       r         ]       =       A   1     ⁢     A   2     ⁢     A   3           ,           (   14   )               
and applying the sequence of transformations
 
x=A 1 x 1 , x 1 =A 2 x 2 , x 2 =A 3 x′,  (15)
 
as shown in  FIG. 2 , where the top row depicts the image and the bottom row represents the Fourier transform of the image (i.e. its frequency spectra). Note that the frequency spectra are scaled to a unit square with maximum frequencies (±1,±1) in order to make the upsampling and downsampling more intuitive. The left-most column in  FIG. 2 , corresponds to the original image. The second column from the left corresponds to the image after undergoing vertical upsampling, the third column from the left corresponds to the image after additionally undergoing horizontal shearing, and the right-most column corresponds to the image after undergoing vertical downsampling.
 
     The transpose of the middle matrix A 2  is 
                       A   2   T     =     [           a   0         0               a   1     /   r         1         ]       ,           (   16   )               
which when multiplied by the maximum frequency present in the upsampled signal, (±1,±1/r) still lies inside the Nyquist range u′ε[−1, +1] 2  (after horizontal filtering, which is applied during the scale/shear).
 
     In the aforementioned operational notation, this can be written as
 
 f   1 =   v ( f,h, 1,1 /r, 0,0);  (17)
 
 f   2 =   h ( f   1   ,h ,max(1 ,|a   0 |), a   0   ,a   1   /r,t ); and  (18)
 
 f   3 =   v ( f   2   ,h,r,r, 0,0).  (19)
 
     It is noted that the upsampling rate can get arbitrarily high as |a 1 |&gt;&gt;1. However, in practice, the maximum upsampling rate need never exceed r=3 as some high horizontal frequencies do not appear in the final image, and can therefore be filtered away during the horizontal shear. To compute a value for r, the maximum values of the original frequencies that will appear in the final image (u max ,v max ) are determined first. The value of v max  can be less than 1 if the general form of a shear matrix with vertical scaling included is considered, i.e., 
                     A   =       [           a   00           a   01             0         a   11           ]     =         [         1       0           0           a   11     /   r           ]     ⁡     [           a   00             a   01     /   r             0       1         ]       ⁡     [         1       0           0       r         ]           ,           (   20   )               
Eq. (20) combines the vertical scaling with the initial vertical resampling stage. To avoid aliasing, it should be ensured that
 
                       A   2   T     ⁡     [           ±     u   max                   ±     a   11       ⁢       v   max     /   r             ]       =     [             ±     a   00       ⁢     u   max                     ±     a   01       ⁢       u   max     /   r       ±       a   11     ⁢       v   max     /   r               ]             (   21   )               
lies within the bounding box [−1,+1] 2 . In other words, that |a 01 | u max /r+|a 11 |v max /r≦1 or r≧|a 01 | u max +|a 11 |v max . Whenever |a 11 |v max &gt;1, this value can be clamped to 1, since there is no need to further upsample the signal. When the vertical scaling a 11  is sufficiently small (magnification), r&lt;1. With r&lt;1, there is no risk of aliasing during the horizontal shear. As such, r is set to 1 and the final vertical downsampling stage is dropped. The equation for r can thus become,
 
 r ≧max(1 ,|a   01   |u   max +min(1 ,|a   11   |v   max )).  (22)
 
     The final three (or two as the case may be) stage horizontal resampling is therefore:
 
 f   1 =   v ( f,h, 1/ v   max   ,a/r, 0,0);  (23)
 
 f   2 =   h ( f   1   ,h ,max(1, |a   00 |), a   00   ,a   01   /r,t ); and  (24)
 
 f   3 =   v ( f   2   ,h,r,r, 0,0).  (25)
 
where the last stage is skipped if r=1.
 
     The vertical resampling results in a similar three (or two as the case may be) stage resampling. 
     1.4 The General Affine Case 
     Any 2D affine transform can be decomposed into two shear operations. For example, if the horizontal shear is performed first, 
                     A   =       [             a   00           a   01               a   10           a   11             0       0         |           t   0               t   1             1           ]     =       [             b   0           b   1             0       1           0       0         |           t   2             0           1           ]     ⁡     [           1       0             a   10           a   11             0       0         |         0             t   1             1           ]           ,           (   26   )               
with b 0 =a 00 −a 01 a 10 /a 11 , b 1 =a 01 /a 11 , and t 2 =t 0 −a 01 t 1 /a 11 . Notice that Eq. (26) becomes degenerate as a 11 →0, which is a symptom of a so-called bottleneck problem. Fortunately, it is possible to transpose the input (or output) image and adjust the transform matrix accordingly. To determine whether to transpose the image, the first two rows of A are first re-scaled into unit vectors,
 
                       A   ^     =       [             a   ^     00             a   ^     01                 a   ^     10             a   ^     11           ]     =     [             a   00     /     l   0               a   01     /     l   0                   a   10     /     1   1               a   11     /     l   1             ]         ,           (   27   )               
where l i =√{square root over (a i0   2 +a i1   2 )}. The absolute cosines of these vectors with the x and y axes are then computed, |â 00 | and |â 11 |, and compared to the absolute cosines with the transposed axes, i.e., |â 01 | and |â 10 |. Whenever |â 00 |+|â 11 |&lt;|â 01 |+|â 10 |, the image is transposed prior to resampling. If the input image is transposed, the output image is also transposed.
 
     Having developed a three-pass transform for each of the two shears, it would be possible to concatenate these to obtain a six-pass separable general affine transform. However, it is possible to collapse some of the shears and subsequent upsampling or downsampling operations to obtain a four-pass transform. This is accomplished by performing the horizontal upsampling needed for later vertical shearing at the same time as the original horizontal shearing. In a similar vein, the vertical downsampling is performed in the same pass as the vertical shearing and scaling. This four-pass (stage) approach is illustrated shown in  FIG. 3  using the example of a rotation, where the top row depicts the image and the bottom row represents the Fourier transform of the image (i.e. its frequency spectra). The left-most column in  FIG. 3 , corresponds to the original image. The second column from the left corresponds to the image after undergoing vertical upsampling, the third column from the left corresponds to the image after additionally undergoing horizontal shearing and horizontal upsampling, the fourth column from the left corresponds to the image after next undergoing vertical shearing and vertical downsampling and the right-most column corresponds to the image after undergoing horizontal downsampling. 
     In terms of geometric transformations, this four stage approach corresponds to a factorization of the form, 
     
       
         
           
             
               
                 
                   A 
                   = 
                   
                     
                       [ 
                       
                         
                           
                             
                               1 
                             
                             
                               0 
                             
                           
                           
                             
                               0 
                             
                             
                               
                                 
                                   a 
                                   11 
                                 
                                 / 
                                 
                                   r 
                                   v 
                                 
                               
                             
                           
                           
                             
                               0 
                             
                             
                               0 
                             
                           
                         
                         | 
                         
                           
                             
                               0 
                             
                           
                           
                             
                               0 
                             
                           
                           
                             
                               1 
                             
                           
                         
                       
                       ] 
                     
                     = 
                     
                       
                         [ 
                         
                           
                             
                               
                                 
                                   
                                     b 
                                     0 
                                   
                                   / 
                                   
                                     r 
                                     h 
                                   
                                 
                               
                               
                                 
                                   
                                     a 
                                     01 
                                   
                                   / 
                                   
                                     r 
                                     v 
                                   
                                 
                               
                             
                             
                               
                                 0 
                               
                               
                                 1 
                               
                             
                             
                               
                                 0 
                               
                               
                                 0 
                               
                             
                           
                           | 
                           
                             
                               
                                 
                                   t 
                                   2 
                                 
                               
                             
                             
                               
                                 0 
                               
                             
                             
                               
                                 1 
                               
                             
                           
                         
                         ] 
                       
                       ⁢ 
                       
                           
                         
                           
                             
                               [ 
                               
                                 
                                   
                                     
                                       1 
                                     
                                     
                                       0 
                                     
                                   
                                   
                                     
                                       
                                         
                                           a 
                                           10 
                                         
                                         ⁢ 
                                         
                                           
                                             r 
                                             v 
                                           
                                           / 
                                           
                                             ( 
                                             
                                               
                                                 a 
                                                 11 
                                               
                                               ⁢ 
                                               
                                                 r 
                                                 h 
                                               
                                             
                                             ) 
                                           
                                         
                                       
                                     
                                     
                                       
                                         r 
                                         v 
                                       
                                     
                                   
                                   
                                     
                                       0 
                                     
                                     
                                       0 
                                     
                                   
                                 
                                 | 
                                 
                                   
                                     
                                       0 
                                     
                                   
                                   
                                     
                                       
                                         
                                           t 
                                           1 
                                         
                                         ⁢ 
                                         
                                           
                                             r 
                                             v 
                                           
                                           / 
                                           
                                             a 
                                             11 
                                           
                                         
                                       
                                     
                                   
                                   
                                     
                                       1 
                                     
                                   
                                 
                               
                               ] 
                             
                             ⁡ 
                             
                               [ 
                               
                                 
                                   
                                     
                                       
                                         r 
                                         h 
                                       
                                     
                                     
                                       0 
                                     
                                   
                                   
                                     
                                       0 
                                     
                                     
                                       1 
                                     
                                   
                                   
                                     
                                       0 
                                     
                                     
                                       0 
                                     
                                   
                                 
                                 | 
                                 
                                   
                                     
                                       0 
                                     
                                   
                                   
                                     
                                       0 
                                     
                                   
                                   
                                     
                                       1 
                                     
                                   
                                 
                               
                               ] 
                             
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
     In order to compute the appropriate values for r v  and r h , it is first determined which frequency in the original image needs to be preserved in the final image. Frequencies that get mapped completely outside the final spectrum can be pre-filtered away during the upsampling stages, thereby reducing the total number of samples generated. To compute the values of (u max ,v max ), the corners of the final spectrum at u′=(±1,±1) is first projected into the original spectrum through u=A −T u′, to obtain the dashed parallelogram  400  shown in  FIG. 4 . A standard polygon intersection technique is then used to compute the intersection of this parallelogram with the unit square. The horizontal and vertical extents of the resulting polygon define the values of (u max ,v max ). For example, in  FIG. 5 , the value of u max  can be read off from the intersection point of the parallelogram  500  with the top and bottom sides of the square  502 . 
     Once the (u max ,v max ) extents are known, the upsampling rates are computed using
 
 r   v ≧max(1,| a   01   |u   max +min(1, |a   11   |v   max )) and  (29)
 
 r   h ≧max(1, |a   10   /a   11   |r   v   v   max +min(1, |b   0   |u   max )).  (30)
 
     The final four-stage approach is therefore:
 
 f   1 =   v ( f,h, 1/ v   max   a   11   /r   v ,0, t   1 );  (31)
 
 f   2 =   h ( f   1   ,h, 1/ u   max   ,b   0   /r   h   ,a   01   /r   v   ,t   2 );  (32)
 
 f   3 =   h ( f   2   ,h,r   v   ,r   v   ,a   10   r /( a   11   r   h ),0);  (33)
 
 f   4 = ( f   3   ,h,r   h   ,r   h ,0,0).  (34)
 
     An exemplary process implementing the foregoing multi-pass image resampling embodiments involving four passes through the image is shown in  FIGS. 6A-B . The process begins with a first pass  600  through the image being resampled and involves computing the aforementioned vertical upsampling factor ( 602 ). It is then determined if the vertical upsampling factor is equal to 1 ( 604 ). If not, the image is then upsampled in the vertical direction using the vertical upsampling factor ( 606 ). If the vertical upsampling factor is equal to 1, the vertical upsampling is skipped. Next, in a second pass  608  through the image, the image is horizontally sheared and scaled in a prescribed manner which includes employing horizontal filtering ( 610 ). In addition, the aforementioned horizontal upsampling factor is computed ( 612 ). It is then determined if the horizontal upsampling factor is equal to 1 ( 614 ). If not, the image is upsampled in the horizontal direction using the horizontal upsampling factor ( 616 ). If the horizontal upsampling factor is equal to 1, the horizontal upsampling is skipped. 
     In a third pass  618  through the image, a low pass filtering is applied to the image in the vertical direction ( 620 ). In addition, it is determined if the image was vertically upsampled ( 622 ). If so, the image is vertically downsampled to a prescribed degree ( 624 ). The image is also vertically sheared and scaled in a prescribed manner, which includes employing vertical filtering ( 626 ). Then in fourth pass  628  through the image, a low pass filtering is applied in the horizontal direction ( 630 ). In addition, it is determined if the image was horizontally upsampled ( 632 ). If so, the image is horizontally downsampled to a prescribed degree ( 634 ). The result is the resampled image. 
     1.5 Mipmaps and Ripmaps 
     As indicated previously, the use of mipmaps or ripmaps can increase processing efficiency. Mipmaps are a set of pre-computed images depicting the same scene as an associated full-resolution image, but which represent progressively lower resolution images each exhibiting a reduced level of detail in comparison to the preceding image. In mipmaps, the reduction in detail is isotropic in that the reduction is the same in every direction. Ripmaps are a set of progressively lower resolution images similar to mipmaps except the degree in the reduction of detail is not the same in all directions. In cases where the resampling involves a large degree of minification in a particular direction, the processing required for implementing the multi-pass image resampling technique embodiments described herein can be significantly reduced by using an appropriate mipmap or ripmap image that is closer to the desired scale of the output image as the input image, rather that the aforementioned full resolution image. To this end, the mipmap or ripmap closest to but still having a higher resolution that the desired output image would be chosen as the input image. 
     An exemplary process implementing the foregoing multi-pass image resampling embodiments employing mipmaps or ripmaps is shown in  FIGS. 7A-B . The process begins with accessing a mipmap or ripmap associated with the image being resampled ( 700 ) and selecting the image from the accessed mipmap or ripmap which exhibits a level of detail closest to, but still greater than, the level of detail desired to be exhibited in the resampled image ( 702 ). Then, in a first pass  704  through the selected image, the aforementioned vertical upsampling factor is computed ( 706 ). It is then determined if the vertical upsampling factor is equal to 1 ( 708 ). If not, the selected image is then upsampled in the vertical direction using the vertical upsampling factor ( 710 ). If the vertical upsampling factor is equal to 1, the vertical upsampling is skipped. Next, in a second pass  712  through selected image, the image is horizontally sheared and scaled in a prescribed manner which includes employing horizontal filtering ( 714 ). In addition, the aforementioned horizontal upsampling factor is computed ( 716 ). It is then determined if the horizontal upsampling factor is equal to 1 ( 718 ). If not, the selected image is upsampled in the horizontal direction using the horizontal upsampling factor ( 720 ). If the horizontal upsampling factor is equal to 1, the horizontal upsampling is skipped. 
     In a third pass  722  through the selected image, a low pass filtering is applied in the vertical direction ( 724 ). In addition, it is determined if the selected image was vertically upsampled ( 726 ). If so, the selected image is vertically downsampled to a prescribed degree ( 728 ). The selected image is also vertically sheared and scaled in a prescribed manner, which includes employing vertical filtering ( 730 ). Then in fourth pass  732  through the selected image, a low pass filtering is applied in the horizontal direction ( 734 ). In addition, it is determined if the selected image was horizontally upsampled ( 736 ). If so, the selected image is horizontally downsampled to a prescribed degree ( 738 ). The result is then designated as the resampled image ( 740 ). 
     2.0 Other Embodiments 
     Although the multi-pass image resampling technique embodiments described previously performed horizontal shearing and scaling, before the vertical shearing and scaling, this need not be the case. This sequence can be reversed such that the vertical shearing and scaling occurs first, followed by the horizontal shearing and scaling. An exemplary process implementing the foregoing reversed multi-pass image resampling embodiment is shown in FIGS.  8 A-B. The process begins with a first pass  800  through the image being resampled and involves computing the aforementioned horizontal upsampling factor ( 802 ). It is then determined if the horizontal upsampling factor is equal to 1 ( 804 ). If not, the image is then upsampled in the horizontal direction using the horizontal upsampling factor ( 806 ). If the horizontal upsampling factor is equal to 1, the horizontal upsampling is skipped. Next, in a second pass  808  through the image, the image is vertically sheared and scaled in a prescribed manner which includes employing vertical filtering ( 810 ). In addition, the aforementioned vertical upsampling factor is computed ( 812 ). It is then determined if the vertical upsampling factor is equal to 1 ( 814 ). If not, the image is upsampled in the vertical direction using the vertical upsampling factor ( 816 ). If the vertical upsampling factor is equal to 1, the vertical upsampling is skipped. 
     In a third pass  818  through the image, a low pass filtering is applied to the image in the horizontal direction ( 820 ). In addition, it is determined if the image was horizontally upsampled ( 822 ). If so, the image is horizontally downsampled to a prescribed degree ( 824 ). The image is also horizontally sheared and scaled in a prescribed manner, which includes employing horizontal filtering ( 826 ). Then in fourth pass  828  through the image, a low pass filtering is applied in the vertical direction ( 830 ). In addition, it is determined if the image was vertically upsampled ( 832 ). If so, the image is vertically downsampled to a prescribed degree ( 834 ). The result is the resampled image. 
     It further noted that any or all of the aforementioned embodiments throughout the description may be used in any combination desired to form additional hybrid embodiments. In addition, although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims. 
     3.0 The Computing Environment 
     A brief, general description of a suitable computing environment in which portions of the multi-pass image resampling technique embodiments described herein may be implemented will now be described. The technique embodiments are operational with numerous general purpose or special purpose computing system environments or configurations. Examples of well known computing systems, environments, and/or configurations that may be suitable include, but are not limited to, personal computers, server computers, hand-held or laptop devices, multiprocessor systems, microprocessor-based systems, set top boxes, programmable consumer electronics, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like. 
       FIG. 9  illustrates an example of a suitable computing system environment. The computing system environment is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality of multi-pass image resampling technique embodiments described herein. Neither should the computing environment be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the exemplary operating environment. With reference to  FIG. 9 , an exemplary system for implementing the embodiments described herein includes a computing device, such as computing device  10 . In its most basic configuration, computing device  10  typically includes at least one processing unit  12  and memory  14 . Depending on the exact configuration and type of computing device, memory  14  may be volatile (such as RAM), non-volatile (such as ROM, flash memory, etc.) or some combination of the two. This most basic configuration is illustrated in  FIG. 9  by dashed line  16 . Additionally, device  10  may also have additional features/functionality. For example, device  10  may also include additional storage (removable and/or non-removable) including, but not limited to, magnetic or optical disks or tape. Such additional storage is illustrated in  FIG. 9  by removable storage  18  and non-removable storage  20 . Computer storage media includes volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. Memory  14 , removable storage  18  and non-removable storage  20  are all examples of computer storage media. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can accessed by device  10 . Any such computer storage media may be part of device  10 . 
     Device  10  may also contain communications connection(s)  22  that allow the device to communicate with other devices. Device  10  may also have input device(s)  24  such as keyboard, mouse, pen, voice input device, touch input device, camera, etc. Output device(s)  26  such as a display, speakers, printer, etc. may also be included. All these devices are well know in the art and need not be discussed at length here. 
     The multi-pass image resampling technique embodiments described herein may be further described in the general context of computer-executable instructions, such as program modules, being executed by a computing device. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. The embodiments described herein may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer storage media including memory storage devices.