Image analysis – Image enhancement or restoration – Image filter
Reexamination Certificate
2001-10-18
2004-11-09
Patel, Kanji (Department: 2625)
Image analysis
Image enhancement or restoration
Image filter
C382S279000, C345S611000
Reexamination Certificate
active
06816622
ABSTRACT:
TECHNICAL FIELD
This invention relates generally to image processing and, more particularly, relates to an image processing technique for eliminating ripples that occur within images that are resized.
BACKGROUND OF THE INVENTION
Image filtering and reconstruction are computational processes used commonly within computer software applications to affect how digital images, picture files and other graphic elements are rendered to a computer display device, such as a monitor. Typically, these image-processing techniques are used for resizing, repositioning and/or rotating an image, which in effect is a modification of the pixel data comprising the image. Pixels, short for picture elements, are the smallest addressable units that appear on a display screen. Multiple pixels, or samples, of varying color intensities are combined to represent a given image. The higher the pixel resolution (the more rows and columns of pixels), the more information can be displayed to the screen. Image filtering is a process by which a new image is generated as a result of processing the pixels of an existing image.
As an example of image filtering applied within software, consider the commonly used word processing application Microsoft Word. A useful feature of Word is that it allows a user to insert digitally sampled images, such as those scanned into the computer using a scanner, directly into a text document. This is particularly useful for creating newsletters, reports, and other published works that require high graphic content. Whenever the user wants to alter the natural size of an image embedded within the document (e.g. shrink it), they need only adjust it manually by toggling it with the mouse or by selecting the appropriate user commands. In resizing the image from its natural size or scale (100%) to a smaller size (x %; x<100), an image-filtering algorithm is applied to the source image pixel data to yield the appropriately resized output image. In computer graphics terms, shrinking an image is the process of representing the signal (waveform) representative of the source image with a similarly shaped output signal (waveform) of reduced size.
According to conventional techniques, a scaled down version of the original (sampled) image is generated using convolution filtering. Convolution filtering is an operation wherein the intensity value of a pixel to be placed into the output image is determined by summing up the intensity contributions of a group of pixels in the neighborhood of a source pixel. A neighborhood is defined as a range of pixels surrounding the source pixel. The number of pixels within the range is determined by the width of a filter kernel. Simply defined, the filter kernel is an array of values (weights) that characterize the type of filtering operation to be performed on the source image.
Filter kernels are not restricted to any particular size, and can be of varying shapes, including box shaped, tent shaped (bilinear) or an approximation to the sinc function (e.g., bi-cubic). Regardless of the shape, the filter kernel is typically symmetric about a two dimensional axis, and is designed so that the area, or response of the filter with respect to varying scale factors (x) is always unity. This is achieved by resizing the kernel width by the scale factor (x), while the height is resized to be the reciprocal of the scale factor (1/x). Unity response is maintained so that as the filter is applied to the source image, it is filtered as a constant value function, and not a periodic one. From a mathematical standpoint, this corresponds to filtering the waveform representative of the source image at a constant rate (constant number of pixels) to ensure the intensity contribution for each pixel is accounted for to represent the resized image. A non-unity filter kernel response can lead to pixel contributions that are not accounted for during the filtering process, thus creating unwanted visual effects in the output image.
In general, the filtering process begins by centering the filter kernel at a row/column position within the source image that corresponds to the location of the desired output pixel. Based on the width of the kernel, a number of pixels will lie beneath the kernel as it is centered accordingly. The resulting output pixel is calculated by multiplying the pixel values with the weight of the filter kernel at each respective row/column position of the pixels underneath the kernel. These values are then summed to reveal the total output pixel value, and placed into the output image. This process is repeated by shifting the filter, pixel by pixel, until each source pixel within the source image has been processed. The typical filtering process described above results in a desirable output image being generated. Because of the inverse relationship between the filter kernel width and height as set according to the selected rescale factor (x); a unity filter response is often maintained. As long as the number of pixels underneath the kernel remains constant throughout the filtering process—as the filter is shifted from pixel to pixel, the contribution for each pixel is accounted for in calculating the output pixel value. However, when a rescale factor (x) is selected that results in the filter kernel being resized to a non-integer width and height, unity area under the kernel is not maintained. This results in highly objectionable visual artifacts, such as ripples, being displayed in the output image. Ripples appear within digital images as longitudinal gaps of obscure color. They are visible within each of the color channels—red, blue, green and a (transparent)—that comprise a color image. Ripples occur whenever the filter kernel is set to a non-integer width as a result of resealing the image by the designated value x. For instance, if the rescale factor (x) is selected as 2.5, the filter width and height is adjusted from its default setting to 2.5 and 1/2.5 respectively. Because of this non-integer setting, the number of pixels that lie underneath the kernel as it is moved from pixel to pixel changes as opposed to remaining constant. This results in a cyclical pattern of increasing and decreasing filter kernel response that manifests as patterns of light and dark lines in the resized image. Clearly, this is not acceptable visual quality, particularly for those applications requiring rich graphic content.
Fortunately, there are some standard processes available for eliminating the ripple effect that occurs within images. For instance, one such method is to increase the size of the filter kernel such that significantly more pixels lie under the kernel as it is moved across the source image. This reduces the possibility of a non-constant filter response, and provides a more accurate approximation of the output pixel value. Also, there are other processes such as edge reduction and stochastic filtering, which also reduce unwanted visual peculiarities within digitally sampled images. However, these techniques are not always practical because they require a considerable amount of random-access memory (RAM) to operate on source image representations. This impedes the performance of software applications, such as word-processing or publishing software, that demand quick image processing capability. Moreover, the resource usage required to perform these techniques increases the software development and test process, negatively impacting the cost to the developer and consumer. To overcome these challenges, a way is needed to provide ripple free image rendering techniques that require only modest processing and memory resources.
SUMMARY OF THE INVENTION
The present invention is directed to a method and system for resizing an image to produce an output image that is free of ripples. Particularly, the invention eliminates the ripple effect that occurs within graphic images as a result of resizing, rescaling, or reconstruction without reliance upon high cost, impractical processing methods.
In accordance with the invention, an optimal filter kernel is formed by convolving a box f
Blinn James F.
Godfrey Andrew C.
Marr Michael D.
Secchia Adrian
LandOfFree
Generating resized images using ripple free image filtering does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Generating resized images using ripple free image filtering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generating resized images using ripple free image filtering will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3335366