Abstract:
Embodiments of the present invention provide systems, methods, and computer storage media directed at image resampling with geometric transformation. In embodiments the method may begin by determining a two-dimensional filter for application to an original image to produce a resampled image. This determining may be based on a specified geometric transformation. The method can proceed by computing identifiers for pixel locations in the resampled image that indicate a position of the two-dimensional filter with respect to the original image. Additionally, the method can include applying the two-dimensional filter to the original image in accordance with the computed identifiers to produce the resampled image. Other embodiments may be described and/or claimed.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application is a continuation of and claims priority from U.S. application Ser. No. 10/714,513, filed Nov. 14, 2003, entitled “IMAGE RESAMPLING WITH GEOMETRIC TRANSFORMATION,” which claims the benefit of U.S. Provisional Application Ser. No. 60/506,250, filed Sep. 26, 2003, and of U.S. Provisional Application Ser. No. 60/506,249, filed Sep. 26, 2003. All of these applications are hereby incorporated by reference in the entirety. This application is also related to U.S. application Ser. No. 10/714,514 titled “IMAGE RESAMPLING USING VARIABLE QUANTIZATION BINS,” which is incorporated herein by reference. 
     
    
     BACKGROUND 
       [0002]    This invention relates to resampling of images. 
         [0003]    Images are typically represented in digital form as raster images in which a rectangular grid of pixel values define the image. These pixel values can be thought of as samples of a continuous two-dimensional image at the coordinates of the pixels in the rectangular grid. Changing the array of pixel locations, or scaling the image while keeping the pixel locations fixed, involves computing new pixel values. This process of computing the new pixel values is referred to as resampling the image. 
         [0004]    In general, resampling an image with an increased number of pixels involves interpolating image values at locations between the original pixel locations. Similarly, scaling up (magnification of) the image for a fixed grid of pixel locations involves interpolating image values. On the other hand, sampling an image with fewer pixels involves a loss of spatial resolution that is generally handled by spatially low-pass filtering (anti-alias filtering) the image prior to or in the process of determining the new pixel values. Both interpolation and low-pass filtering can be implemented by computing a filtered version of the originally spatially sampled image at the new desired pixel locations. 
         [0005]    One technique for increasing the efficiency of the resampling process is to pre-compute a spatially quantized (“binned”) representation of the interpolation/low-pass filter. For example, a fixed number of bins per unit pixel spacing are used. Computing a new pixel value then involves using the appropriate bins when combining the filter and the original pixel values. 
         [0006]    In some software applications, a user has control over the type of filter that is used in the resampling. For example, in some applications, the user can choose between a “linear” and a “cubic” filter. The choice has implications for the resulting image quality as well as the computation required to perform the resampling. 
       SUMMARY 
       [0007]    In one aspect, in general, the invention features a method and a corresponding system and software for processing a first image. A specification of a geometric transformation is accepted for application to the first image to produce a second image. A two-dimensional filter for application to the first image is then determined using the specification of the geometric transformation. Data characterizing relationships between pixel locations in the second image and pixel locations in the first image is computed. Pixel values of a second image are then computed by applying the two-dimensional filter to the first image, including for each of a plurality of pixels locations of the second image, computing a value for the second image at said pixel location by applying the second filter according to the data characterizing the relationships between pixel locations. 
         [0008]    Aspects of the invention can include one or more of the following features. 
         [0009]    The computing of the data characterizing the relationships between the pixel locations is completed prior to the computing of the pixel values of the second image. 
         [0010]    The computing of the data characterizing the relationships between the pixel locations includes computing a corresponding pixel location in the first image for each of at least some of the plurality of pixels locations of the second image. Applying the two-dimensional filter to the first image can then include applying the second filter relative to the computed corresponded pixel location. 
         [0011]    Computing the two-dimensional filter includes computing a spatially-quantized representation of said filter. Applying the two-dimensional filter at the computed corresponding pixel locations and then include combining values of the spatially-quantized representation of the said filter and pixel values of the first image. 
         [0012]    The computing of the data characterizing the relationships between the pixel locations includes storing a data structure associating each of at least some of the plurality of pixel locations of the second image with a corresponding pixel location in the first image. Computing the pixel values of the second image can then include accessing said stored data structure. The data structure can include a data address referencing the corresponding pixel of the first image for each of the at least some of the plurality of pixel locations of the second image. Applying the two-dimensional filter to the first image can then include accessing pixel values of the first image stored at addresses determined relative a data address stored in the data structure. 
         [0013]    The two-dimensional filter is a separable filter determined from one or more one-dimensional filters. Computing the values at each of the pixel locations in the second image then includes evaluating a two-dimensional sum over pixel locations in the first image. Evaluating the two-dimensional sum can include evaluating multiple one-dimensional sums using a first of the one-dimensional filters, and then evaluating a sum over the results to those sums using a second of the one-dimensional filters. 
         [0014]    The two-dimensional filter is an interpolation filter or an anti-aliasing filter. 
         [0015]    The specification of the geometric transformation includes a specification of an affine transformation. 
         [0016]    Determining the two-dimensional filter includes determining a measure of scale from the specification of the affine transformation, and determining the two-dimensional filter based on said measure of scale. 
         [0017]    The specification of the affine transformation includes a specification of a rotation or of a scaling. The specification of a scaling can includes a specification of a magnification or of a minification. 
         [0018]    The method can further include determining a fringe for the first image, which can include determining a size (e.g., a number of pixels) of the fringe based on a size of the two-dimensional filter. 
         [0019]    The determined size of the fringe is provided, for example, to a user of the method, and the first image is then accepted in a storage area that accommodates the size of the fringe. The accepted first image in the storage area can includes image values stored in the fringe. Alternatively, image values for the fringe are computed from image values for the accepted first image in the storage area, and the computed image values for the fringe are stored in the storage area. 
         [0020]    In another aspect, in general, the invention features a method and a corresponding system and software for processing a first image. A two-dimensional filter for application to the first image is determined. A fringe for the first image is the determined. This includes determining a size of the fringe based on a size of the two-dimensional filter. The determined size of the fringe is provided, and in return the first image is accepted in a storage area that accommodates the size of the fringe. The two-dimensional filter is then applied to the first image. This includes applying the filter to image regions that include both the first image and the fringe. 
         [0021]    In yet another aspect, in general, the invention features a method and a corresponding system and software for processing a first image. A two-dimensional filter for application to the first image is determined. This filter is a separable filter determined from one or more one-dimensional filters. Pixel values of a second Image are computed by applying the two-dimensional filter to the first image. This includes, for each of a set of pixels locations of the second image, computing a value for the second image at that pixel location by applying the separable filter at a corresponding location in the first image. Computing the values at each of the pixel locations in the second image includes evaluating a two-dimensional sum over pixel locations in the first image. 
         [0022]    Aspects of the invention can include one or more of the following advantages. 
         [0023]    The approach can avoid the need for storage of an intermediate image when both a geometric transformation and a resampling are performed. This can be significant in devices with limited storage, for example, in cameras, telephones or other portable devices. 
         [0024]    By avoiding the use of an intermediate image, which may have limited precision (e.g., a limited integer representation), the resulting quality of an image subject to both geometric transformation and resampling may be higher than with a two-stage approach. Therefore, even if a device had storage capacity for an intermediate image, applying the one-pass approach may be preferable. 
         [0025]    Characterizing the relationship between pixel locations in a first image and an image produced by applying a geometric transformation before computing the pixels values of the resulting image allows the procedure for resampling the transformed image to be independent of the details of the geometric transformation. The also allows the resampling code to be more efficient and relatively smaller in memory size. Furthermore, the implementation of the resampling code may make better use of certain computer architectures, for example, by keeping pipelined stages or parallel computation units relatively utilized as compared to software that performs both the transformation and resampling computations in a combined procedure. 
         [0026]    Performing a geometric transformation and a resampling in one pass can produce a more accurate computation than using an intermediate image prior to resampling. For example, this one-pass approach may avoid cascaded conversions to limited precision (e.g., integer) representations of the pixel values. Also, the one-pass approach avoids the necessity of providing storage for an intermediate image. Furthermore, the overall computation may involve fewer total arithmetic operations, for example in the case of a rotation followed by a thumbnail minification. 
         [0027]    Implementation of a convolution with a separable two-dimensional filter in one pass as a two-dimensional sum can be more efficient in its memory access because the computation can be arranged to access pixel storage in continuous sections (e.g., along rows of an image) with relatively little or no access in discontinuous segments (e.g., along columns of an image). Therefore, at least for relatively small filters, the overall efficiency of the two-dimensions sum approach can be higher that an approach that makes use of the separable nature of the filter to perform relatively fewer arithmetic operations. This approach to implementing the convolution may also me well-suited to certain SIMD processor architectures, for example by using SIMD instructions to perform the sums along one dimension, and then using CISC instructions to perform the sums along the other dimension. 
         [0028]    Separation of the geometric transformation phase from the resampling phase enables the different phases to be performed on different computers or on different types of processors within a single system or device. For example, the resampling phase can be performed in special-purpose code, such as in a portable device such as a telephone or a camera. 
         [0029]    Explicitly accounting for the fringe area, for example, by enabling an application to provide storage for a fringe area can reduce the amount of storage required as compared to copying an image into a storage area with an adequate fringe and can reduce the computation required as compared to an implementation that does not require a fringe area and instead uses program logic to not exceed the bounds of the valid image area. Furthermore, the treatment of the fringe area allows for alternative computations of fringe images requiring modification of the resampling and geometric transformation code. 
         [0030]    Other features and advantages of the invention are apparent from the following description, and from the claims. 
     
    
     
       DESCRIPTION OF DRAWINGS 
         [0031]      FIG. 1  is a block diagram of a resampling system. 
           [0032]      FIG. 2  is an illustration of an image minification. 
           [0033]      FIG. 3  is an illustration of image resampling with a geometric transformation. 
           [0034]      FIGS. 4A ,  4 B and  4 C illustrate a one-dimensional filter.  FIG. 4A  is an illustration of a continuous filter.  FIG. 4B  is an illustration of a spatially quantized filter.  FIG. 4C  is a data structure for storing values of the quantized filter. 
           [0035]      FIG. 5  is a diagram that illustrates a two-pass filtering computation. 
       
    
    
     DESCRIPTION 
       [0036]    Referring to  FIG. 1 , a resampling system  100  is used to process an original image  110  producing a resampled image  140 . A fringe calculator  115  and a resampler  130  together implement the computation of the resampled image. The fringe calculator and the resampler use precomputed configuration data that is determined by a pre-computation module  120  based on the specific characteristics of the resampling that is to be performed on the original image. As is discussed further below, the fringe calculator accepts the original image  110  and produces an extended image  118  that extends the original image beyond the original edges in a “fringe” area. The pre-computation module  120  determines the extent to which the image has to be extended according to factors such as the size (spatial extent) of filters that are to be applied to the original image and the area of the original image that is to be resampled. The pre-computation module  120  computes data, including a filter, that are used by the resampler  130  in computing the resampled image  140 . 
         [0037]    The pre-computation module  120  uses a number of inputs in computing the data that it passes to the resampler, including inputs related to one or more of a scale factor  121 , a geometric transformation  122  to be applied to the original image, user specified characteristics  123  such as degrees of visual characteristics (for example sharpness) of the resampled image, computation factors  124  such as the processor characteristics of a device hosting resampler  130 , and a filter kernel  125  that is to be used for filtering-related computations by the resampler. 
         [0038]    The pre-computation module  120 , fringe calculator  115 , and resampler  130  may be hosted on a variety of different types of computation devices, including on general purpose programmable computers as well as embedded in special-purpose devices such as cameras and portable telephones. Also, the pre-computation module  120 , fringe calculator  115 , and resampler  130  are not necessarily hosted on the same device. For example, the pre-computation module may be hosted on a general purpose computer, such as on a networked server computer, while the fringe calculator  115  and resampler  130  may be embedded in a special-purpose device. These modules can be implemented using software instructions stored on a computer medium (e.g., computer disk or ROM), or using a combination of special-purpose hardware and software controlled processors. Also, the modules, including the resampler, may be distributed and executed in parallel using a number of processors in order to achieve reduced overall computation time. 
         [0039]    Both the original image  110  and its associated extended image  118 , as well as the resampled image  140 , are spatially sampled images in which a discrete set of pixels represent the image. Each pixel includes data representing the visual characteristics of the image in a region associated with the pixel, typically including a grayscale value for a black-and-white image or including multiple color values for a color image (for example values for red, green, and blue components of the image). Each pixel is rendered at a particular region in the image, and a pixel value can be considered to be a spatial sample of an underlying spatially-continuous image at a spatial location associated with that pixel (e.g. at the center of the pixel region). In the discussion below, the pixel locations are typically chosen to lie on a square grid (lattice), although other arrangements, such as rectangular or other geometric grids, can be used. 
         [0040]    The resampling implemented by the resampling system  100  supports both magnification (scaling up) as well as minification (scaling down) of images, as well as a more general class of affine geometric transformations. For a fixed pixel separation, magnification generally results in more pixels being produced to represent the image while minification generally results in fewer pixels being produced to represent the image. If the image dimensions are considered fixed, then magnification is related to reducing the pixel separation (up-sampling) while minification is related to increasing the pixel separation (down-sampling). 
         [0041]    Determining pixel values for an image at spatial locations not sampled in the original image involves an interpolation of the existing pixel values, which can be implemented as a filtering of the image, and for at least some spatial locations near the edge of the original image involves use of an extrapolation of the image to a fringe area beyond the extent of the original image. Furthermore, when increasing the spatial separation between pixel locations, it is understood that an original image should, in general, be spatially low-pass filtered to avoid an aliasing effect in which high spatial frequency components of the original image may degrade the resulting image if not filtered. Therefore, resampling of the original image involves filtering to address possible aliasing and/or to interpolate pixel values at pixel location in the new image. 
         [0042]    Referring to  FIG. 2 , an example of an original image  110  and a resulting resampled image  140  are shown for the case of minification (down-sampling). In this example, the image is being down-sampled by a minification factor of 4 such that the original image has 16×12 pixels and the resampled image has 4×3 pixels. In practice, the actual number of pixels in the original is typically much higher, for example in the range 1600×1200 pixels for camera images. Also, the down-sampling factor may smaller than 4 or greater than 4, for example, a factor of 40 might be used when computing a “thumbnail” image of 40×30 pixels from a 1600×1200 camera image. Also, as is discussed further below, it is not necessary that the scale factor be an integer. 
         [0043]    In  FIG. 2 , each pixel of the original image  110  or the resampled image  140  is associated with a pixel region  220 ,  230 , respectively, and with a particular pixel location  222 ,  232 , respectively, within that region (e.g., the center). In  FIG. 2 , only the top-left pixel of each of the images have been labeled with reference numerals for clarity. In this example, the entire image area of the original image  110  is represented in the resampled image  140 . That is, the image is resampled but otherwise not transformed geometrically or clipped. 
         [0044]    Computation of a new pixel value (or each of the multiple separate color values for a color pixel) involves computing a filtered version of the original image at a location in the original image corresponding to the new pixel value. For example, a pixel location  242  in the resampled image corresponds to a location  241  in the original image  110 , as is indicated by an arrow  240 . Note that the corresponding location  241  in the original image need not correspond to an original pixel location in that image. 
         [0045]    In this system, filters that are applied to the original images have finite support. That is, they have a limited spatial range over which they have non-zero values. Computing a filtered value at a particular location in the original image is equivalent to computing a weighted sum of pixel values of the original image at the pixel locations within the support of the filter being applied, with the weights being determined by the shape of filter. In  FIG. 2 , a spatial extent  250  of a filter being applied to compute the pixel value at location  241  in the original image is illustrated. Various approaches to efficiently computing and approximating the weighted sum are described below. 
         [0046]    Referring to  FIG. 3 , in another example, an original image  110  is not only resampled at a new scale pixel spacing, but it is also subject to a geometric transformation, in this example a rotation. As in  FIG. 2 , each pixel location in the resampled image corresponds to a location in the original image, which is not necessarily at a pixel location of the original image. A representative correspondence is shown between resampled pixel location  342  and an original image location  341  as indicated by an arrow  340 . 
         [0047]    Resampling system  100  supports a wide range of possible geometric transformations. In particular, rather than (or optionally in addition to) specifying a scalar scale factor  121 , a geometric transformation  122  is specified by an affine transformation of the form  y =A x + b  where  y  is a (vector) coordinate of a pixel location in the resampled image,  x  is the corresponding location in the original image, and A is a matrix and  b  is a vector that together define the coordinate transformation. Such an affine transformation can represent various forms of scaling, rotation, skew, etc. The range of coordinate values in the resampled image also can define a clipping of the original image, as is the case illustrated in  FIG. 3 . 
         [0048]    The filtering operation described above is a two-dimensional filtering. For example, in  FIG. 3 , the support  350  for a filter centered at original coordinates  341  is a two-dimensional region. For clarity of explanation, a one-dimensional version of the filter calculation is addressed in  FIGS. 4A and 4B . Referring to  FIG. 4A  a particular continuously defined filter  410  is illustrated centered at an original location  241 . Various forms of filters can be used. The illustrated filter (centered at x=0) has the functional form 
         [0000]    
       
         
           
             
               
                 ( 
                 x 
                 ) 
               
               = 
               
                 
                   
                     2 
                      
                     
                       
                          
                         
                           4 
                            
                           x 
                         
                          
                       
                       3 
                     
                   
                   - 
                   
                     3 
                      
                     
                       
                          
                         
                           4 
                            
                           x 
                         
                          
                       
                       2 
                     
                   
                   + 
                   1 
                 
                 4 
               
             
             , 
             
               
                 for 
                  
                 
                     
                 
                  
                 x 
               
               ∈ 
               
                 
                   [ 
                   
                     
                       - 
                       2 
                     
                     , 
                     2 
                   
                   ] 
                 
                 . 
               
             
           
         
       
     
         [0000]    Calculation of an original image value at an original location  241  that corresponds to a resampled pixel location  242  involves calculating a weighted sum by multiplying pixel values at pixel locations  222  by corresponding non-zero values of the filter  410  centered at location  241 . In general, the original location  241  can fall at any point between a pair of pixel locations  241 , therefore one approach to calculating the weighted sum is to evaluate the functional form for the filter at each of the needed values. 
         [0049]    In resampling system  100 , particular values of the filter  410  are precomputed and stored for use during the resampling computation, thereby reducing the amount of computation required during resampling, and also removing the specifics of the filter calculation from that resampling computation. In particular, the filter is precomputed for arguments (locations) that are multiples of the original pixel spacing divided by a spatial quantization factor M, which is an integer that is greater than or equal to one. In  FIG. 4B , M is illustrated to be 2. These spatially sampled values of the filter are sufficient to compute the weighted sum of original pixel values when the filter is centered exactly at one of the M quantized equally spaced spatial location (bins) in each original pixel spacing. For example, in  FIG. 4B , the computation when the original image location  441  is at the midpoint between two pixel locations involves using the filter samples  420 , which are illustrated with the filled circles. If the original image location corresponding to a resampled pixel location had been coincident with an original pixel location, then the filter samples  430 , which are illustrated with the open circles, would have been used. 
         [0050]    In  FIG. 4B , the desired original image location  241  that corresponds to the resampled pixel location  242  does not fall precisely at one of the quantized spatial locations for which the filter values have been pre-computed. Therefore, the image value at original image location  441 , which is the closest of the quantized locations, is used instead. The resulting filtered image value is not generally exactly equal to that which would be calculated using the continuous filter at the desired location  241  (as shown in  FIG. 4A ), however the error (for example measured as a mean squared error, or as a signal-to-noise ratio) can be made relatively smaller by increasing the value of M. The error can also be viewed as a spatial ‘jitter”  440  in the filtered image in the range of ±½M of the original pixel spacing. That is, the original pixel spacing can be viewed as being divided into M spatial bins, and the value of the original image at a desired original image location in that bin can be computed using a representative (quantized) original image location within that bin. 
         [0051]    In order to preserve the unit magnitude of the filter as applied at any of the spatially quantized locations, the sum of the filter values corresponding to any particular spatial bin are renormalized (dividing by a constant) to sum to unity. In  FIG. 4B , this corresponds to renormalizing the filter values  420  (the filled circles), and separately renormalizing the filter values  430  (open circles). In general, the M sums of every M th  sample of the filter are each renormalized to unity. 
         [0052]    Resampling system  100  performs a two dimensional filtering of the original image. In one form of filter used by the system, the filter is separable in that it can be represented as a product f(x, y)=f horiz (x)·f vert (y). For such separable filters, both the horizontal and vertical pixel spacing is divided into bins, and spatially quantized values of each of f horiz (x) and f vert  (y) are precomputed. When the same filter is used for both the horizontal and vertical components, and the quantization factor is common, then a single quantized one-dimensional filter is stored. When the image value at a desired original image location is to be computed, each of the coordinates are separately quantized to one of the binned original locations. 
         [0053]    Returning to  FIG. 1 , an output of the filter pre-computation module  120  is a value of the spatial quantization factor M and the corresponding spatially quantized filter values (e.g.,  420 ,  430  in  FIG. 3 ) for the filter to be applied. The filter pre-computation makes use of a filter kernel f(x) that is non-zero over a continuous support [−f 0 , f 0 ] of width N=2f 0 , which is used to form a separable two-dimensional filter as introduced above. A built-in filter kernel can be used, or optionally, a custom filter kernel  125  can be provided to the filter pre-computation module. 
         [0054]    For magnification, this filter is used to interpolate the original image values at all pixel locations in the magnified image. The value M 0  of the spatial quantization factor is chosen based on factors other than the magnification scale factor. For example, the value is fixed (for example at 10, 32, 33.3, 64, or 100). That is, N·M 0  spatially quantized values of the (one-dimensional) filter are precomputed regardless of the magnification scale factor. 
         [0055]    For minification, the filter is “stretched” in order to so that the magnified image adheres to the Nyquist rate. For example, for a minification (downsampling) by a minification scale factor of K=4, a continuous filter g(x)=f(x/K)/K, which has a width K·N(over a range [−g 0 ,g 0 ] for g 0 =K·f 0 ), is used. For example, if the original filter kernel f(x) attenuates signals with spatial periods smaller than twice the original pixel spacing (i.e., at the Nyquist frequency for the pixel sampling frequency), then the filter stretched by a factor K will attenuate signals above the Nyquist frequency for the resampled pixel sampling frequency. 
         [0056]    In practice, the filter kernel f(x) is not an ideal lowpass filter at the Nyquist frequency, and represents tradeoffs allowing some higher spatial frequencies above the Nyquist frequency to pass while providing for less attenuation, or even amplification, of spatial frequencies below the Nyquist frequency. These trade-offs affect visual characteristics of the resampled image. 
         [0057]    For minification, rather than using a spatial quantization factor M 0  which would result in K·N·M 0  precomputed values of the filter, a smaller value of the spatial quantization factor M&lt;M 0  is generally used. The particular value of M is computed in the filter pre-computation module  120  according to one or more factors, such as according to the scale factor. A particular mapping from a minification scale factor K to a spatial quantization factor M(K) has been determined by experimentation with a set of sample images resampled at a number of different scale factors and evaluated both quantitatively according to the error introduced (mean squared error or signal-to-noise ratio) and qualitatively by human subjects. An empirically chosen mapping takes the approximate form M(K)≈M 0 /K, which as K grows results in the total number of samples of the filter, K·N·M(K) asymptoting to approximately a limit of N·M 0 . More specifically, the mapping takes the form of an affine transformation M 
         [0000]    
       
         
           
             
               ( 
               K 
               ) 
             
             = 
             
               ⌈ 
               
                 
                   
                     M 
                     0 
                   
                   K 
                 
                 + 
                 c 
               
               ⌉ 
             
           
         
       
     
         [0000]    for a small constant c less than 1. 
         [0058]    For more general geometric transformations, determining the degree of spatial filtering required to avoid the possibility of, or to reduce the effect of, aliasing depends on the specific characteristics of the transformation. For geometric transformations defined by an affine transformation, including rotations and non-uniform scaling in different directions, an equivalent (scalar) scale factor, which is a measure of scale of the geometric transformation, is computed from the transformation matrix, A, of the transformation. The filter pre-computation module determines the equivalent minification scale factor, K, by computing the effect of mapping a unit circle from the original image to an ellipse in the resampled image using the matrix A. Specifically, if the matrix has the form 
         [0000]    
       
         
           
             A 
             = 
             
               [ 
               
                 
                   
                     a 
                   
                   
                     b 
                   
                 
                 
                   
                     c 
                   
                   
                     d 
                   
                 
               
               ] 
             
           
         
       
     
         [0059]    then the radii of the ellipse are computed as 
         [0000]    
       
         
           
             
               
                 
                   ( 
                   
                     
                       a 
                       2 
                     
                     + 
                     
                       b 
                       2 
                     
                   
                   ) 
                 
                 + 
                 
                   
                     ( 
                     
                       
                         c 
                         2 
                       
                       + 
                       
                         d 
                         2 
                       
                     
                     ) 
                   
                   ± 
                   
                     
                       
                         4 
                          
                         
                           
                             ( 
                             
                               
                                 a 
                                  
                                 
                                     
                                 
                                  
                                 c 
                               
                               + 
                               bd 
                             
                             ) 
                           
                           2 
                         
                       
                       + 
                       
                         
                           ( 
                           
                             
                               ( 
                               
                                 
                                   a 
                                   2 
                                 
                                 + 
                                 
                                   b 
                                   2 
                                 
                               
                               ) 
                             
                             - 
                             
                               ( 
                               
                                 
                                   c 
                                   2 
                                 
                                 + 
                                 
                                   d 
                                   2 
                                 
                               
                               ) 
                             
                           
                           ) 
                         
                         2 
                       
                     
                   
                 
               
               2 
             
           
         
       
     
         [0060]    The equivalent scale factor (inverse of the equivalent minification scale factor K) is then based on the lengths of principal axes of the mapped ellipse. In particular, for a general transformation matrix A, if one of the axes has a length Jess than one (i.e. minification, down-sampling), then the scale factor is taken to be the minimum of the two. If one or both of the axes have lengths greater than one, the equivalent scale factor is taken to be the average of the two axes. As an alternative and somewhat more conservative approach is to use the minimum scale factor in all cases, but this may result in images that are subjectively overly smooth and/or require unnecessary computation because of a relatively larger filter. 
         [0061]    The resampling system  100  supports the use of different filter kernels according to the scale factor (or the measure of scale of a geometric transformation). For example, a parametric kernel f(x;θ) is used where the parameter value(s) θ affect the characteristics of the filter such as a spatial cutoff frequency or a degree of attenuation or accentuation (sharpening) of spatial frequencies below the cutoff frequency. The filter-precomputation module chooses the parameter values according to the scale factor. For example, for minification the parameters are chosen to provide generally increasing sharpening for an increasing minification factor. For a magnification by a factor of 2, parameters are chosen to provide some sharpening of the image, with progressively less sharpening as the magnification factor increases until at approximately a magnification factor of 5, the parameters are chosen to provide a smoothing of the image which has a visual effect of reducing the “tiling” appearance of the resampled image. 
         [0062]    Examples of filter kernels include the following, each of which is non-zero only on the interval (−2, 2): 
         [0000]    
       
         
           
             
               CubicFilter 
                
               
                 ( 
                 x 
                 ) 
               
             
             = 
             
               { 
               
                 
                   
                     
                       
                         
                           
                             
                               ( 
                               
                                 A 
                                 + 
                                 2 
                               
                               ) 
                             
                              
                             
                               
                                  
                                 x 
                                  
                               
                               3 
                             
                           
                           - 
                           
                             
                               ( 
                               
                                 A 
                                 + 
                                 3 
                               
                               ) 
                             
                              
                             
                               x 
                               2 
                             
                           
                           + 
                           1 
                         
                       
                       
                         
                           
                             for 
                              
                             
                                 
                             
                              
                             0 
                           
                           ≤ 
                           
                              
                             x 
                              
                           
                           &lt; 
                           1 
                         
                       
                     
                     
                       
                         
                           
                             A 
                              
                             
                               
                                  
                                 x 
                                  
                               
                               3 
                             
                           
                           - 
                           
                             5 
                              
                             
                               Ax 
                               2 
                             
                           
                           + 
                           
                             8 
                              
                             A 
                              
                             
                                
                               x 
                                
                             
                           
                           - 
                           
                             4 
                              
                             A 
                           
                         
                       
                       
                         
                           
                             for 
                              
                             
                                 
                             
                              
                             1 
                           
                           ≤ 
                           
                              
                             x 
                              
                           
                           &lt; 
                           2 
                         
                       
                     
                   
                    
                   
                     
 
                   
                    
                   and 
                    
                   
                     
 
                   
                    
                   
                     Mitchell 
                      
                     
                       ( 
                       x 
                       ) 
                     
                   
                 
                 = 
                 
                   { 
                   
                     
                       
                         
                           
                             
                               ( 
                               
                                 12 
                                 - 
                                 
                                   9 
                                    
                                   B 
                                 
                                 - 
                                 
                                   6 
                                    
                                   C 
                                 
                               
                               ) 
                             
                              
                             
                               
                                  
                                 x 
                                  
                               
                               3 
                             
                           
                           + 
                           
                             
                               ( 
                               
                                 
                                   - 
                                   18 
                                 
                                 + 
                                 
                                   12 
                                    
                                   B 
                                 
                                 + 
                                 
                                   6 
                                    
                                   C 
                                 
                               
                               ) 
                             
                              
                             
                               x 
                               2 
                             
                           
                           + 
                           
                             ( 
                             
                               6 
                               - 
                               
                                 2 
                                  
                                 B 
                               
                             
                             ) 
                           
                         
                       
                       
                         
                           
                             for 
                              
                             
                                 
                             
                              
                             0 
                           
                           ≤ 
                           
                              
                             x 
                              
                           
                           &lt; 
                           1 
                         
                       
                     
                     
                       
                         
                           
                             
                               
                                 
                                   
                                     ( 
                                     
                                       
                                         - 
                                         B 
                                       
                                       - 
                                       
                                         6 
                                          
                                         C 
                                       
                                     
                                     ) 
                                   
                                    
                                   
                                     
                                        
                                       x 
                                        
                                     
                                     3 
                                   
                                 
                                 + 
                                 
                                   
                                     ( 
                                     
                                       
                                         6 
                                          
                                         B 
                                       
                                       + 
                                       
                                         30 
                                          
                                         C 
                                       
                                     
                                     ) 
                                   
                                    
                                   
                                     x 
                                     2 
                                   
                                 
                                 + 
                               
                             
                           
                           
                             
                               
                                 
                                   
                                     ( 
                                     
                                       
                                         
                                           - 
                                           12 
                                         
                                          
                                         B 
                                       
                                       - 
                                       
                                         48 
                                          
                                         C 
                                       
                                     
                                     ) 
                                   
                                    
                                   
                                      
                                     x 
                                      
                                   
                                 
                                 + 
                                 
                                   ( 
                                   
                                     
                                       8 
                                        
                                       B 
                                     
                                     + 
                                     
                                       24 
                                        
                                       C 
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                         
                       
                       
                         
                           
                             for 
                              
                             
                                 
                             
                              
                             1 
                           
                           ≤ 
                           
                              
                             x 
                              
                           
                           &lt; 
                           2 
                         
                       
                     
                   
                 
               
             
           
         
       
     
         [0063]    As another alternative, the resampling system  100  supports use of different filter kernels for different ranges of scale factor. 
         [0064]    The resampling system  100  also optionally accepts user-specified characteristics  123  that are used to determine the characteristics of the filter to be used in resampling. In one example of such user-specified characteristics, a user inputs a desired degree of “sharpness,” for example by adjusting a slider in a graphical user interface. This degree of sharpness is then used to modify parameter values of the filter kernel (either augmenting the mapping from scale factor to parameter values or replacing the mapping) to provide increased response to high spatial frequency components. Other examples of possible user-specified characteristics include “ringing”, which affects the degree of spatial aliasing, and “quality”. 
         [0065]    The resampling system  100  optionally takes account of computation factors  124  in determining data it provides the resampler. For example, the selection of the spatial quantization factor M determines the number of filter samples that will be used by the resampler. One example of a computation factor is the cache size of the target processor. The spatial quantization factor is then chosen so that the number of spatially quantized samples is not so large as to result in poor cache behavior. Other computation factors that can be used include the number of floating point registers and the computation speed of the target processor, and the precision and representation of the pixel values (e.g., 8 vs. 16 vs. 32 bits, fixed point/integer vs. floating point). 
         [0066]    The resampling system optionally uses a cascade filtering approach for large degrees of minification. For a minification factor K, the resampling is essentially carried out in two stages. First, a minification by an integer factor K 1 &lt;K is carried out using a first filter kernel f 1 (x/K 1 )/K 1 , followed by a minification by a factor K 2 =K/K 1  using a second filter. The first filter is chosen to enable efficient computation, for example, having a constant value within its support (e.g., a rectangular window filter). The second filter can be parameterized, as described above, and the parameter values are optionally chosen so that the cascade of the two filtering operations has desired effect. For example, the first filter may attenuate the higher spatial frequencies, while the second filter may compensate for this attenuation through the appropriate setting of its parameters. The calculation of these filters can be performed in the frequency domain to achieve a desired (e.g., flat) spatial frequency response. 
         [0067]    Referring to  FIG. 4C , a data structure that holds the K·N·M values of the filter g(x)=f(x/K)/K includes an array  450  of M elements, each of which points to an array  460  of └K·N├ elements, where as discussed above K·N corresponds to the length of the filter in units of pixels. Each of these arrays holds samples of the filter with unit pixel spacing, but with a different fractional pixel location of the center of the filter. That is, if we consider the m th  row in array  450 , and the k th  entry  462  in the corresponding array  460 , that entry holds the value g(m/M+k), where k can range from −[g 0 ] to [g 0 ]−1 across the array. When applying the filter at a particular fractional pixel location, for each dimension the samples of the filter in one of the arrays  460  are used, and can therefore be accessed efficiently. 
         [0068]    In summary of the above description, the filter pre-processing module  120  computes data that include: the filter spatial quantization factor M, the total integer filter size, which is the size of the filter kernel for the magnification case and a scaling up of that size for the minification case, and the filter samples spatially quantized according to the spatial quantization factor. 
         [0069]    The data also characterizes the quantized locations in the original image that correspond to each of the resampled pixel locations. For each scan line of the resampled image, the filter pre-processing module  120  computes a location corresponding to the first pixel in the scan line in the original image  110 . The module also computes the separation of pixels in the scan line which includes a component in each of the dimensions of the original image. This enables the resampler  130  to incrementally step through the original image in computing a scan line of pixels of the resampled image. 
         [0070]    To further reduce the computation that is required by the resampler  130  during the resampling computation, the computed location that is associated with a pixel location in the resampled image identifies the top-left corner pixel in the support for the filter, as well as an index identifying which of the series of (the every M th ) samples of the filter are to be used. These computed locations are stored in a data structure that is passed to the resampler. To further reduce computation during the resampling process, this top-left location is optionally represented as a memory address. The computation of this top-left pixel location in the support takes account of the conventions used to associate pixel coordinates with the continuation pixel regions that support the coordinates. For example, one convention is that a pixel at (integer) coordinates (i,j) is associated with a pixel region which is centered at (i,j) and has spatial extent [i−½,i+½)×[j−½, j+½). Another convention is that a pixel at coordinates (i, j) is associated with a pixel region which is centered at (i+½,j+½) and a pixel region [i,i+1)·[j, j+1). The computation maps the pixel centers between the original and resampled images and computes the pixel coordinates according to the convention used for each of the images. 
         [0071]    Referring back to  FIG. 1 , the pre-processing module  120  determines the extent to which the fringe calculator  115  is to extend the original image  110  to form the extended image  118 . As described above, the pre-computation module  120  determines the filter that is to be applied to the original image and the set of (fractional pixel) locations in the original image  110  at which the filter is to be applied. In general, some of the original locations at which the filter is to be applied may be near the edge of the original image, and therefore the filter centered at the original image location would extend beyond the edge of the original image. One approach to handling this situation would be for the resampler  130  to test for this condition and not include the original pixel locations that are not within the original area of original image  110 . This system uses an alternative approach in which the pre-computation module  120  determines the maximum size of the fringe that is necessary such that when the filter is applied by the resampler  130  at any of the required original image locations. All the pixel values to which the filter is applied then fall within the area of the extended image  118  and tests related to the edge of the image  110  are not necessary. The fringe pixel values are determined from the original image itself by replicating the pixel values at the edge of the image. In this way, the resampler does not have to incorporated tests related to the filter extending beyond the edge of the original image, or special-purpose code for filtering near the edge of the original image. Note that the size of the fringe can depend on a number of factors, including the degree of magnification which affects the size of the filter, and the geometric transformation of the original image. Also, alternative fringe computations can be used, for example, by setting the fringe to a fixed color or reflecting the image into the fringe area, extrapolation of the image (e.g., linear extrapolation, or using a user-specified value or function). 
         [0072]    As part of the fringe calculator  115  the original image is stored in a canonical form (e.g. interlaced color values represented as 32-bit integers). For example, the image is decompressed (for example in the case of a JPEG image) and the pixel values are arranged in a predetermined order in memory. 
         [0073]    In an optional mode, which is illustrated in  FIG. 1  by the broken line from the original image  110  to the resampler  130 , the fringe calculator is not required and the original image includes a sufficient fringe area. For example, if a large image is being resampled in a series of tiles that together form the entire original image, interior tiles (tiles that are not at the edge of the image) might have sufficient fringe to not require computation of an extended image  118 . On the other hand, tiles at or near the edge of the original image may require allocation of memory for and/or computation for a fringe image prior to processing by the resampler. 
         [0074]    In another optional mode, the fringe calculator does not necessarily allocate memory for a second copy of the original image. Rather, the pre-processing module  120  determines the minimum required size of the required fringe, and provides that information to the module that supplies the original image  110 . The original image is then stored within a larger memory area, and the fringe calculator  115  populates the pixel values in the required fringe area with the already allocated memory. In this way, a second memory area does not need to be allocated for the extended image. 
         [0075]    Referring to  FIG. 6 , the resampler  130  loops over the resampled pixels, and for each pixel applies the filter according to the stored data that identifies the top-left pixel of the original image and the subset of the filter samples that are to be applied. This identification of the top-left original pixel is represented by an arrow  640  that relates a representative resampled pixel  242  with a top-left pixel  650 . The separable filter calculation is applied for each pixel in two passes. In the first pass, the one dimensional filter is applied to each row of the original image to produce a partial row-sum result  672  for that row. The preprocessed original image is stored so that the rows of pixel values are contiguous so this pass uses relatively localized memory accesses. After all the row sums have been computed, the one-dimensional filter is applied to the column  670  of the computed row-sums  672  in a second pass. This final result then provides the resampled pixel value for the pixel, as is illustrated by an arrow  680 . In the case of color images, each of the color values are computed in the same way, either together, or as a loop over the different colors. As introduced above, the image includes a fringe of valid pixel values so that the computation is applied in the same way for pixels near the edge of the original image. 
         [0076]    In one implementation of this separable filtering approach, the pre-computation module computes different data representations of the filter applied to the rows and the filter applied to the column of partial results. The row filter is computed as an array of integer values. For example, 12-bit values are used. If the image uses 8-bit values, each term in the row sum uses 20 bits. The length of the row filter is also extended to a data access boundary for the processor being used to increase data access efficiency. For example, if the processor uses 8-byte (64-bit), the row filter is extended to a multiple of 8 bytes for example by zero padding. The column filter is represented using floating point values, and the column sum is accumulated as a floating point value, thereby limiting dynamic range limitations. 
         [0077]    In an alternative implementation, or as an optional calculation, a non-separable filter is used by the resampler. The computation is similar to that described above in that each resampled pixel value is computed in tum. However, the two-dimensional weighted sum is computed in one pass, iterating along each row and then from row to row in the support of the filter. 
         [0078]    Alternative versions of the system can be implemented in software, in firmware, in digital electronic circuitry, or in computer hardware, or in combinations of them. The system can include a computer program product tangibly embodied in a machine-readable storage device for execution by a programmable processor, and method steps can be performed by a programmable processor executing a program of instructions to perform functions by operating on input data and generating output. The system can be implemented in one or more computer programs that are executable on a programmable system including at least one programmable processor coupled to receive data and instructions from, and to transmit data and instructions to, a data storage system, at least one input device, and at least one output device. Each computer program can be implemented in a high-level procedural or object-oriented programming language, or in assembly or machine language if desired; and in any case, the language can be a compiled or interpreted language. Suitable processors include, by way of example, both general and special purpose microprocessors. Generally, a processor will receive instructions and data from a read-only memory and/or a random access memory. Generally, a computer will include one or more mass storage devices for storing data files; such devices include magnetic disks, such as internal hard disks and removable disks; magneto-optical disks; and optical disks. Storage devices suitable for tangibly embodying computer program instructions and data include all forms of non-volatile memory, including by way of example semiconductor memory devices, such as EPROM, EEPROM, and flash memory devices; magnetic disks such as internal hard disks and removable disks; magneto-optical disks; and CD-ROM disks. Any of the foregoing can be supplemented by, or incorporated in, ASICs (application-specific integrated circuits). 
         [0079]    To provide for interaction with a user, the invention can be implemented on a computer system having a display device such as a monitor or screen for displaying information to the user and a keyboard and a pointing device such as a mouse or a trackball by which the user can provide input to the computer system. The computer system can be programmed to provide a graphical user interface through which computer programs interact with users. 
         [0080]    It is to be understood that the foregoing description is intended to illustrate and not to limit the scope of the invention, which is defined by the scope of the appended claims. Other embodiments are within the scope of the following claims.