1. Field of the Invention
The invention relates to scaling digital images and more specifically to scaling images using non integer factors to reduce artifacts and errors in resultant output images.
2. Statement of the Problem
Digitization of images has provided many benefits in terms of portability, storage, and reproduction. Often, digitized images can be processed to alter the image, (e.g., change the image size). For example, once an image is digitized, it is converted into image data represented by a two dimensional array of pixels, with each pixel having some color or grayscale value. This two dimensional array of pixels can be reduced in size by removing a certain number of pixels from the array in a manner that still provides an adequate representation of the original image. Similarly, pixels can be added to the array to increase the size of the image.
One basic approach to scaling includes the “nearest neighbor” method, which uses sample values that are nearest to a pixel being analyzed. This is generally known as a zero-order or proximal interpolation and generally produces relatively good high frequency response, but degrades image quality due to aliasing. To illustrate, a 240 dots per inch (DPI) image as it would be printed on a 360 DPI printer is now discussed. In this example, the scaling factor is a non integer 1.5 (i.e., 360 dpi/240 dpi=1.5). The scaling ratio is converted to the nearest ratio which is all integer. For this case, the ratio is three to two, meaning that for every two PELs in the input space there are three PELs created in the output space. Using a nearest neighbor pixel replication algorithm, the algorithm outputs one copy of the first pixel, two copies of the second, and so on, in a 1-2-1-2-1-2 . . . pattern. This pattern satisfies the two PELs becoming three in the output space requirement. The same holds true for scanlines in the image in that the first scanline appears once, the second is repeated twice, etc. The problem with this scaling approach is that it can cause undesirable artifacts in the output image, especially if the scaling factor is not an integer. Consider the following image pattern with the same proposed scaling of 1.5, where a 1 in the pattern indicates a black pixel and a 0 indicates a white pixel.
  111  000  000.Suppose, with this scaling, the image is to be replicated 3 times down a page. The output of this 1D scaling would then appear as follows:
DATANumber of repeats111100020000001111211100010002000111100020000001
In this diagram, the left side shows the scaled and replicated pattern. The horizontal lines provide a visual aid to the reader to distinguish the copies of the replicated pattern. The right column shows how many copies of the input line are output by the scaling algorithm. Notice how the first copy of the pattern has a black line that is one pixel wide, but the second copy has a black line that is two pixels wide. These inconsistencies are easily recognized when viewed (e.g., on a printed medium), because a single pixel in the input becomes a varying larger number of pixels in the output, generally referred to as an artifact. If the scaling factor is an integer value, no artifact occurs because each pixel is scaled the same.
One method used to overcome these artifacts is a bilinear approach which is regarded as a first-order scaling method. In the bilinear approach, the output pixel value changes linearly according to sampling position. Other more complex methods include the bicubic approach, the use of polynomials, adaptive algorithms, or correlations, but these methods require significant processing capabilities due to their complexities. Additionally, certain images are composed of transparent areas that cause problems in scaling. For example, the image of the font character “O” printed in black on a red background does not overwrite the center of the image or the corners with white data because these pixels are transparent. If the font character was created at a fixed resolution and must be scaled, an efficient scaling is needed that preserves the transparent regions without causing a “halo” effect of white or gray pixels adjacent to the black pixels of the scaled character image.
USPTO Backgrounds
USPTO Backgrounds