Image scaling

• US 6,825,857 B2
• Filed: 01/18/2002
• Issued: 11/30/2004
• Est. Priority Date: 01/19/2001
• Status: Expired due to Fees

• Current Assignee: Rambus Inc.
• Original Assignee: ClearSpeed Technology Ltd. (ZF Acquisitions Ltd.)
• Inventors: Harasimiuk, Michal
• Primary Examiner(s): Tung, Kee M.
• Assistant Examiner(s): Richer, Aaron M.
• Application Number:
  US10/050,880
• Publication Number:
  US 20020154123A1
• Time in Patent Office: 1,047 Days
• Field of Search: 345/660, 345/502, 345/505, 345/564, 345/667, 345/670, 345/671, 345/698, 382/260, 382/298, 382/299
• US Class Current: 345/660
• CPC Class Codes: G06T 3/4023 based on decimating pixels or lines of pixels; based on inserting pixels or lines of pixels

Abstract

A method and a system for scaling a digital source image consisting of a grid of X by Y pixels into a target image of a different resolution comprises the steps of/tools for:

mapping the source pixels onto the target pixels;

scaling the source image in the X or Y direction to produce intermediate pixels that are scaled in one direction by determining contributions to each intermediate pixel using a digital filter and accumulating the contributions for each intermediate pixel, wherein each source pixel contributes to one or more intermediate pixels and each intermediate pixel receives contributions from one or more source pixels; and subsequently

scaling the intermediate pixels in the other direction by determining the contributions to each target pixel using the filter and accumulating the contributions for each target pixel;

wherein each intermediate pixel contributes to one or more target pixels and each target pixel receives contributions from one or more intermediate pixels.

The method is preferably carried out on a PE array in an SIMD (Simple Instruction Multiple Data) device.

Claims

1. A parallel processing method of scaling a digital source image consisting of a matrix of X by Y pixels into a target image, comprising the steps of:

mapping the source pixels onto the target pixels;

scaling the source image in the X or Y direction in parallel using a processing element (PE) array, each PE including a number of addressable memory cells for storing values corresponding to one or more pixels, to produce intermediate pixels that are scaled in one direction by determining contributions to each intermediate pixel using a digital filter and accumulating the contributions for each intermediate pixel, wherein each source pixel contributes to one or more intermediate pixels and each intermediate pixel receives contributions from one or more source pixels, and in which values are shifted in said memory cells during Y scaling such that they are shifted up the array one position when the process crosses a cluster boundary; and

subsequently

scaling the intermediate pixels in the other direction in parallel to produce target pixels by determining the contributions to each target pixel using the filter and accumulating the contributions for each target pixel;

wherein each intermediate pixel contributes to one or more target pixels and each target pixel receives contributions from one or more intermediate pixels.

2. A method according to claim 1, including the step of mapping a cluster of adjacent higher-resolution pixels onto each of the lower resolution pixels, in which a higher resolution pixel belongs to the cluster of a lower resolution pixel if its centre falls within that lower resolution pixel.

3. A method according to claim 2, including the step of calculating the distance from the cluster boundary as the source pixels are read in and defining process changes or increments to occur when the cluster border is crossed.

4. A method according to claim 1, including the step of calculating the distance between the centre of each higher resolution pixel and the centre of each lower resolution pixel to which it contributes or from which it receives contributions in the X and Y directions.

5. A method according to claim 1, in which integral filter function values for the filter function are determined for the X direction in an X preparation step.

6. A method according to claim 5, in which the X preparation step is performed prior to reading the pixel value data.

7. A method according to claim 1, in which the filter function for each lower resolution pixel is evaluated at any suitable number of points known as the filter footprint number, each point corresponding to a source pixel in downscaling or to a target pixel in upsealing;

the filter footprint number being determined by the footprint of the filter function in source space or target space respectively.

8. A method according to claim 1, in which integration of the filter function is determined analytically, without approximation of the integration.

9. A method according to claim 1, in which in downscaling, (and in each direction) each source pixel contributes to a number of target pixels determined by the filter width and in upscaling (and in each direction) each target pixel receives contributions from a number of source pixels determined by the filter width.

10. A method according to claim 1 in which one PE is provided per pixel of the higher resolution image and the memory cell array is of the same length as the filter width.

11. A method according to claim 1 in which one PE is used per pixel of the lower resolution image and each PE processes two or more neighbouring higher resolution pixels which are read into the PE sequentially.

12. A method according to claim 1, in which a PE-pixel mapping is automatically selected according to process conditions.

13. A method according to claim 1, using SIMD processing on each line of source pixels.

14. A method according to claim 1, in which data is swazzled between PEs for X scaling;

the data being swazzled a certain distance across a predetermined number of cluster boundaries until it reaches the correct PE for accumulation to make up target pixels.

15. A method according to claim 1, including the steps of reading the source image before scaling and analysing the source and target dimensions and writing the target pixels to external memory after scaling.

16. A computer program, algorithm or method of controlling a computer for use in SIMD processing to scale a digital source image consisting of a matrix of X by Y pixels into a target image using a method as defined in claim 1.

17. A computer program product comprising the program according to claim 16 loaded on a carrier, such as a CD or ROM memory or transported on a carrier wave.

18. A parallel processing method of scaling a digital source image consisting of a matrix of X by Y pixels into a target image, comprising the steps of:

mapping the source pixels onto the target pixels;

scaling the source image in the X or Y direction in parallel to produce intermediate pixels that are scaled in one direction by determining contributions to each intermediate pixel using a digital filter and accumulating the contributions for each intermediate pixel, wherein each source pixel contributes to one or more intermediate pixels and each intermediate pixel receives contributions from one or more source pixels; and

subsequently

scaling the intermediate pixels in the other direction in parallel to produce target pixels by determining the contributions to each target pixel using the filter and accumulating the contributions for each target pixel;

wherein each intermediate pixel contributes to one or more target pixels and each target pixel receives contributions from one or more intermediate pixels, and

in which a processing element (PE) array is used, in which interconnections allow data to be moved (swazzled) along the PE array, each PE including a number of addressable memory cells, in which values corresponding to one or more pixels may be stored, and between which the values may be shifted, and

in which the Y scaling step for downscaling includes the steps of multiplying the source pixel by the appropriate filter function values and reading the resultant contributions for each source pixel into the cells in the memory cell array, adding them to any contributions from one or more lines above the present scanline which are already in the cell; and

incrementing to shift the feed into the array by one position and move the top cell value out when a cluster border is crossed.

19. A parallel Processing method of scaling a digital source image consisting of a matrix of X by Y pixels into a target image, comprising the steps of:

mapping the source pixels onto the target pixels;

scaling the source image in the X or Y direction in parallel to produce intermediate pixels that are scaled in one direction by determining contributions to each intermediate pixel using a digital filter and accumulating the contributions for each intermediate pixel, wherein each source pixel contributes to one or more intermediate pixels and each intermediate pixel receives contributions from one or more source pixels; and

subsequently

scaling the intermediate pixels in the other direction in parallel to produce target pixels by determining the contributions to each target pixel using the filter and accumulating the contributions for each target pixel;

wherein each intermediate pixel contributes to one or more target pixels and each target pixel receives contributions from one or more intermediate pixels, and

in which a processing element (PE) array is used, in which interconnections allow data to be moved (swazzled) along the PE array, each PE including a number of addressable memory cells, in which values corresponding to one or more pixels may be stored, and between which the values may be shifted, and

in which the Y scaling step for upsealing includes the steps of reading each pixel value into a cell, calculating the contributions for each pixel in the array using the filter function;

summing the contributions (in a number corresponding to the filter width) for each target pixel; and

shifting the source pixel values up one position, to read in a new source pixel and discard an old source pixel when the target boundary is crossed.

20. A parallel processing method of scaling a digital source image consisting of a matrix of X by Y pixels into a target image, comprising the steps of:

mapping the source pixels onto the target pixels;

scaling the source image in the X or Y direction in parallel to produce intermediate pixels that are scaled in one direction by determining contributions to each intermediate pixel using a digital filter and accumulating the contributions for each intermediate pixel, wherein each source pixel contributes to one or more intermediate pixels and each intermediate pixel receives contributions from one or more source pixels; and

subsequently

scaling the intermediate pixels in the other direction in parallel to produce target pixels by determining the contributions to each target pixel using the filter and accumulating the contributions for each target pixel;

wherein each intermediate pixel contributes to one or more target pixels and each target pixel receives contributions from one or more intermediate pixels, and

in which a processing element (PE) array is used, in which interconnections allow data to be moved (swazzled) along the PE array, each PE including a number of addressable memory cells, in which values corresponding to one or more pixels may be stored, and between which the values may be shifted, and

in which X scaling involves accumulating contributions in one accumulating PE per cluster, the contributions for each source pixels being swazzled across the PE array to their correct accumulating PE.

21. A parallel processing method of scaling a digital source image consisting of a matrix of X by Y pixels into a target image, comprising the steps of:

mapping the source pixels onto the target pixels;

scaling the source image in the X or Y direction in parallel to produce intermediate pixels that are scaled in one direction by determining contributions to each intermediate pixel using a digital filter and accumulating the contributions for each intermediate pixel, wherein each source pixel contributes to one or more intermediate pixels and each intermediate pixel receives contributions from one or more source pixels; and

subsequently

scaling the intermediate pixels in the other direction in parallel to produce target pixels by determining the contributions to each target pixel using the filter and accumulating the contributions for each target pixel;

wherein each intermediate pixel contributes to one or more target pixels and each target pixel receives contributions from one or more intermediate pixels, and

in which a processing element (PE) array is used, in which interconnections allow data to be moved (swazzled) along the PE array, each PE including a number of addressable memory cells, in which values corresponding to one or more pixels may be stored, and between which the values may be shifted, and

in which the method for the X scaling step for downscaling calculates the contributions for each source pixel;

addresses them according to the distance they must travel and stores them in a memory cell array, then shifts each contribution in turn along the PE array to the correct accumulating PE.

22. A parallel processing method of scaling a digital source image consisting of a matrix of X by Y pixels into a target image, comprising the steps of:

mapping the source pixels onto the target pixels;

scaling the source image in the X or Y direction in parallel to produce intermediate pixels that are scaled in one direction by determining contributions to each intermediate pixel using a digital filter and accumulating the contributions for each intermediate pixel, wherein each source pixel contributes to one or more intermediate pixels and each intermediate pixel receives contributions from one or more source pixels; and

subsequently

scaling the intermediate pixels in the other direction in parallel to produce target pixels by determining the contributions to each target pixel using the filter and accumulating the contributions for each target pixel;

wherein each intermediate pixel contributes to one or more target pixels and each target pixel receives contributions from one or more intermediate pixels, and

in which a processing element (PE) array is used, in which interconnections allow data to be moved (swazzled) along the PE array, each PE including a number of addressable memory cells, in which values corresponding to one or more pixels may be stored, and between which the values may be shifted, and

in which the method for the X scaling step for upsealing involves loading the PE array with a repeating sequence of the source pixels in the corresponding cluster of the target pixels.

23. A method according to claim 22 in which the sequence is indexed to increase by one and restart each time a cluster boundary is crossed, the sequence restarting with the first pixel in the sequence and having a length equal to the filter width.

24. A method according to claim 22, in which the value loaded is held in one cell of the array of memory cells and the preferred swazzle movement moves the values one step at a time to fill a different cell with its value.

25. A parallel processing system for scaling a digital source image consisting of a matrix of X by Y pixels into a target image, comprising:

a processing element (PE) array, each PE including a number of addressable memory cells for storing values corresponding to one or more pixels;

a mapping tool for mapping the source pixels onto the target pixels;

a first parallel processing scaling tool for scaling the source image in the X or Y direction in parallel to produce intermediate pixels that are scaled in one direction;

a digital filter for determining contributions to each intermediate pixel;

an accumulator for accumulating the contributions for each intermediate pixel, wherein each source pixel contributes to one or more intermediate pixels and each intermediate pixel receives contributions from one or more source pixels;

shift means for shifting values in the memory cells during Y scaling such that they are shifted up the array one position when the process crosses a cluster boundary;

a second parallel processing scaling tool for scaling the intermediate pixels in the other direction in parallel by determining the contributions to each target pixel using the filter and accumulating the contributions for each target pixel; and

means for moving data between PEs for X scaling, the data being swazzled a certain distance across a predetermined number of cluster boundaries until it reaches the correct PE for accumulation to make up target pixels,

wherein each intermediate pixel contributes to one or more target pixels and each target pixel receives contributions from one or more intermediate pixels.

26. A parallel processing method of scaling a digital source image consisting of a matrix of X by Y pixels into a target image, comprising the steps of:

mapping the source pixels onto the target pixels;

scaling the source image in the X or Y direction in parallel using a processing element (PE) array, each PE including a number of addressable memory cells for storing values corresponding to one or more pixels, to produce intermediate pixels that are scaled in one direction by determining contributions to each intermediate pixel using a digital filter and accumulating the contributions for each intermediate pixel, wherein each source pixel contributes to one or more intermediate pixels and each intermediate pixel receives contributions from one or more source pixels; and

subsequently

scaling the intermediate pixels in the other direction in parallel to produce target pixels by determining the contributions to each target pixel using the filter and accumulating the contributions for each target pixel, and in which data is moved (swazzled) between PEs for X scaling, the data being swazzled a certain distance across a predetermined number of cluster boundaries until it reaches the correct PE for accumulation to make up target pixels;

wherein each intermediate pixel contributes to one or more target pixels and each target pixel receives contributions from one or more intermediate pixels.

27. A method according to claim 26, including the step of mapping a cluster of adjacent higher-resolution pixels onto each of the lower resolution pixels, in which a higher resolution pixel belongs to the cluster of a lower resolution pixel if its centre falls within that lower resolution pixel.

28. A method according to claim 27, including the step of calculating the distance from the cluster boundary as the source pixels are read in and defining process changes or increments to occur when the cluster border is crossed.

29. A method according to claim 26, including the step of calculating the distance between the centre of each higher resolution pixel and the centre of each lower resolution pixel to which it contributes or from which it receives contributions in the X and Y directions.

30. A method according to claim 26, in which integral filter function values for the filter function are determined for the X direction in an X preparation step.

31. A method according to claim 30, in which the X preparation step is performed prior to reading the pixel value data.

32. A method according to claim 26, in which the filter function for each lower resolution pixel is evaluated at any suitable number of points known as the filter footprint number, each point corresponding to a source pixel in downscaling or to a target pixel in upsealing;

the filter footprint number being determined by the footprint of the filter function in source space or target space respectively.

33. A method according to claim 26, in which integration of the filter function is determined analytically, without approximation of the integration.

34. A method according to claim 26, in which in downscaling, (and in each direction) each source pixel contributes to a number of target pixels determined by the filter width and in upsealing (and in each direction) each target pixel receives contributions from a number of source pixels determined by the filter width.

35. A method according to claim 26 in which one PE is provided per pixel of the higher resolution image and the memory cell array is of the same length as the filter width.

36. A method according to claim 26 in which one PE is used per pixel of the lower resolution image and each PE processes two or more neighbouring higher resolution pixels which are read into the PE sequentially.

37. A method according to claim 26, in which a PE-pixel mapping is automatically selected according to process conditions.

38. A method according to claim 26, using SIMD processing on each line of source pixels.

39. A method according to claim 26, including the steps of reading the source image before scaling and analysing the source and target dimensions and writing the target pixels to external memory after scaling.

40. A computer program, algorithm or method of controlling a computer for use in SIMD processing to scale a digital source image consisting of a matrix of X by Y pixels into a target image using a method as defined in claim 26.

41. A computer program product comprising the program according to claim 26 loaded on a carrier, such as a CD or ROM memory or transported on a carrier wave.