Image analysis – Image transformation or preprocessing – Changing the image coordinates
Reexamination Certificate
1998-09-18
2001-01-30
Lee, Thomas D. (Department: 2724)
Image analysis
Image transformation or preprocessing
Changing the image coordinates
C382S300000, C358S445000, C358S451000, C358S451000
Reexamination Certificate
active
06181834
ABSTRACT:
BACKGROUND OF THE INVENTION
This application relates to the digital image processing arts. More particularly, the application relates to a method and apparatus for digital image reduction in an efficient and cost-effective manner, with good suppression of moir{acute over (e)} and other undesirable artifacts as often become more pronounced in a downsampled image such as a reduced-size digital image. Such undesirable moir{acute over (e)} has been found to be especially severe upon reduction of a scanned halftone image.
Digital image reduction is essentially a down-sampling process whereby image pixel data for a bitmap of n rows×m columns is used to construct a smaller bitmap of k rows×l columns, where k≦n and/or l≦m. Of course, while the location of each pixel in the new, reduced-size bitmap is known, its “gray” value is unknown and must be determined with reference to the original image.
Many methods are known for determining the gray value of each pixel in the reduced image. A relatively simple method is commonly referred to as “nearest neighbor” interpolation. In such case, if the reduced-size bitmap is viewed as being superimposed over the original image bitmap, the gray value for each new pixel is simply the value of the spatially closest pixel in the original bitmap. Although fast, nearest neighbor interpolation is often not satisfactory in terms of the quality of the resulting reduced-size image.
Another common interpolation technique used in digital image downsampling is bilinear interpolation. Using bilinear interpolation, the newly generated pixel gray value is set to be the weighted sum of the four nearest original pixels. The weights are determined linearly—i.e., each weight is inversely proportional to the distance from each original pixel. Bilinear interpolation has been found to yield higher quality reduced-size images relative to nearest neighbor interpolation. Of course, bilinear interpolation also requires significantly more computational effort compared to nearest neighbor interpolation. Additionally, bilinear interpolation still often results in severe moir{acute over (e)} and other undesirable artifacts in the new image.
Techniques have been proposed and implemented for reducing moir{acute over (e)} which becomes apparent due to downsampling. One prior method involves the application of a two-dimensional low-pass filter to the pixel data of the original image prior to the downsampling operation. The low-pass filter has the effect of reducing high-frequency content in the original image—i.e., the filter has the effect of somewhat “blurring” the original image. This filtered image data is then used in the scaling operation and results in a reduced-size image with less severe moir{acute over (e)}. Unfortunately, the circuitry required to apply a useful two-dimensional filter to the original image data is expensive to implement. In particular, a relatively large number of scanline buffers are needed to store pixel data from multiple scanlines of the original image. For example, in order to apply a 5×5 filter, at least four scanline buffers would typically be needed for the incoming original image data. These scanline buffers add significant expense to the reduction apparatus. Furthermore, reduction of color digital images requires this circuitry to buffer the original image data for each color separation of the original image.
Another prior technique used to reduce moir{acute over (e)} resulting from downsampling is sometimes referred to as “perspective projection.” Perspective projection creates a new pixel from the original image data by averaging a correspondingly located area of the original image. While perspective projection has also been found to be generally effective in reducing moir{acute over (e)}, in certain cases, such as in the downsampling of halftone image data, moir{acute over (e)} is still apparent in the resulting image.
Moir{acute over (e)} apparent after downsampling using perspective projection reduction has resulted from the fact that, heretofore, perspective projection has been implemented so that the size of the area of the original image that is averaged is a linear function of the image reduction ratio. The reduction ratio is defined as 1/scale, where scale=a scaling factor such as 0.5 (a reduction to 50% original size), 0.8 (a reduction to 80% original size), etc. For example, in reducing an image to 50% of original size, a reduction ratio of 2 results (i.e., 1/0.5=2), and a 2×2 pixel area in the original image is used for averaging. In another example, in reducing an image to 80% of original size, a reduction ratio of 1.25 results (i.e., 1/0.8=1.25), and a 1.25×1.25 pixel area in the original image is averaged.
It should be apparent from the foregoing that prior perspective projection techniques have not provided any means by which the area averaged in the original image can be controlled separately from the reduction ratio. Accordingly, prior perspective projection methods have not allowed for any control of moir{acute over (e)} suppression v. sharpness, with enhanced moir{acute over (e)} suppression provided by a larger averaging area and enhanced sharpness provided by a smaller averaging area.
Accordingly, in light of the foregoing and other deficiencies associated with prior digital image downsampling methods and apparatus, it has been deemed desirable to develop a method and apparatus for digital image reduction using an improved “extendible” perspective projection technique which allows for flexible control of the averaging cell or window size separately from the reduction ratio to improve moir{acute over (e)} suppression or sharpness as desired in the resulting reduced-size image.
Furthermore, it has been deemed desirable to provide a method and apparatus wherein the extendible perspective projection technique is implemented together with ordinary perspective projection or together with a combined one-dimensional filter and linear interpolation technique to produce a reduced-size image of a quality comparable to those produced by the prior technique of using a two-dimensional pre-filter prior to interpolation at a much lesser cost due to the reduced number of required scanline buffers.
SUMMARY OF THE INVENTION
In accordance with the present invention, a hybrid image reduction method and apparatus are provided for cost-effective scale reduction of digital images with flexible control of moir{acute over (e)} suppression v. image sharpness.
In accordance with a first aspect of the invention, a method of downsampling an input digital image defined by plural image pixel gray values arranged in n rows extending in a fast scan direction and m columns extending in a slow scan direction to a reduced-size output image defined by plural image pixel gray values arranged in k rows and l columns, wherein k≦n and/or l≦m includes determining a plurality of averaging areas in said input image, each averaging area corresponding to an image pixel gray value location in said output image and defined by dimensions efs in the fast scan direction and ess in the slow scan direction, wherein efs and ess are determined according to
efs=fs_factor/fs_scale
ess=ss_factor/ss_scale
and wherein fs_scale and ss scale are scaling factors for the input image in the fast scan and slow scan directions, respectively. The parameters fs_factor and ss_factor are selected independently of each other according to:
fs_factor>0
ss_factor>0
wherein at least one of fs_factor and ss_factor≠1. For each of said plurality of averaging areas of said input image, an average of the input image pixel gray values at least partially encompassed thereby is obtained and the correspondingly located image pixel gray value location in the output image is assigned the average of the input image pixel gray values at least partially encompassed by the averaging area.
In accordance with another aspect of the present invention, a hybrid method for downsampling image pixel data of an input digital image by f
Li Xing
Tse Francis K.
Fay Sharpe Fagan Minnich & McKee LLP
Lee Thomas D.
Xerox Corporation
LandOfFree
Hybrid image reduction method and apparatus with moir{acute... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hybrid image reduction method and apparatus with moir{acute..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hybrid image reduction method and apparatus with moir{acute... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2502395