Computer graphics processing and selective visual display system – Computer graphics processing – Graphic manipulation
Reexamination Certificate
1999-03-18
2001-10-23
Brier, Jeffery (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Graphic manipulation
C345S660000, C345S669000
Reexamination Certificate
active
06307569
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to digital image processing, and specifically to an improved method of image processing which results in a high quality, single enlarged image.
BACKGROUND OF THE INVENTION
The classic approach for digital image enlargement is to use direct spatial interpolation. This, however, results in image blur, as a result of bilinear interpolation; or image aliasing, as a result of pixel replication.
Resolution enhancement requires that a small image be enlarged to several times its actual size while avoiding blurring, ringing or other artifacts. Classic methods include bilinear or bi-cubic interpolation schemes, followed by an edge sharpening method, such as unsharp masking. Spatial interpolation schemes, however, tend to blur the images when applied indiscriminately. Unsharp masking, which involves subtracting a properly scaled Laplacian of the image from itself, enhances artifacts and image noise. More sophisticated schemes, such as those involving Wavelet or Fractal based techniques, have also been used. Such schemes extrapolate the signal in either the Wavelet or Fractal domain, which leads to objectionable artifacts when the assumptions behind such extrapolation are violated. It may also be noted that such extrapolatory assumptions predict and actively enhance the high frequency content within the image thus increasing any noise present in the sub-sampled image.
I have previously developed an iterative method, which improves the performance of any given base interpolation scheme while not making explicit “high frequency enhancing” assumptions. The main assumption is: interpolation is good until the interpolated data crosses an edge. Instead of making ad hoc extrapolatory assumptions, interpolation is performed in the “right fashion.” Other methods have been developed which selectively interpolate across edges. Such methods, however, tend to promote false edges, which lead to noticeable artifacts. This occurs because the location of the edges in the magnified image is itself imprecise because the selectively interpolated across edge technique uses a sub-sampled image, i.e., the given small image and the algorithms make one-step decisions as to the course of action in edge-areas of the image. The iterative nature of the scheme is aimed at avoiding such an error by not committing blindly to a predetermined course of action at edge locations.
High quality image enlargement is needed in desktop imaging applications which demand high quality input and output images. In such applications, classical spatial interpolation methods do not deliver sufficient quality, especially at high enlargement factors, particularly when high-quality displays or printers are used. Blurring or aliasing artifacts become evident as images are enlarged to larger sizes and are viewed or printed on high quality displays or printers. High quality image enlargement may be utilized for high quality printing at different sizes. An enlargement algorithm may be incorporated in a printer. An enlargement algorithm may also be implemented in a scanner to improve the image resolution over the physical resolution capability of the scanner via post-processing, as is commonly done in modern day scanners.
SUMMARY OF THE INVENTION
A method for enlarging a digital input image includes the steps of: defining a model image that is of the same size (pN×pN), (p>1) as a desired large image; selecting an initial estimate of the enlarged version of the input image, wherein the input image is of size N×N and the initial estimate image is of size pN×pN for a factor of p enlargement in both dimensions; taking the N×N and pN×pN fast Fourier transform (FFT) of these two images, respectively; replacing the first N×N FFT coefficients of the FFT of the initial estimate image with the N×N coefficients of the FFT of the input image; taking the pN×pN inverse FFT (I-FFT) of the intermediate estimate to transform it to the spatial pixel domain to obtain an intermediate estimate of the desired large image; making corrections at each pixel of the resulting pN×pN intermediate estimate image such that each pixel's variation from the corresponding pixel of the model image is within predetermined lower and upper bounds, wherein these bounds vary according to pixel location, to generate the next intermediate estimate; replacing the initial estimate by the resulting intermediate estimate and repeating the above two cycles iteratively for K times and taking the final estimate resulting from K iterations as the estimate of the desired enlarged image. The first cycle corresponds to imposing the following constraint on the final estimate: Its low-frequency, N×N FFT coefficients should match with those of the input image, up to a scale factor, and the second cycle corresponds to constraining the final estimate to vary from a predetermined model image within predetermined, pixel-location dependent bounds.
It is an object of the invention to provide a method of enlarging an image using projections onto convex sets (POCS).
Another object of the invention is to provide a method of enlarging a single image.
A further object of the invention is to provide a method of enlarging an image using a priori information about the desired large image to perform a ‘smart’ interpolation.
Yet another object of the invention is to provide a method of enlarging an image using edge location and low-frequency information extracted from the image about the desired large image.
Another object of the invention is to extend the enlarging techniques of the invention to color images.
Still another object of the invention is to remove ringing artifacts which may appear about the edges of an enlarged image.
These and other objects and advantages of the invention will become more fully apparent as the description which follows is read in conjunction with the drawings.
REFERENCES:
patent: 5251037 (1993-10-01), Busenberg
patent: 5467439 (1995-11-01), Lee et al.
patent: 5469274 (1995-11-01), Iwasaki et al.
patent: 5481275 (1996-01-01), Mical et al.
patent: 5604825 (1997-02-01), Hirota et al.
patent: 5621870 (1997-04-01), Shyu et al.
patent: 5642203 (1997-06-01), Sawano et al.
patent: 5649034 (1997-07-01), Sonobe
patent: 5719594 (1998-02-01), Potu
patent: 6130966 (2000-10-01), Sekine et al.
Jae S. Lim,Two-Dimensional Signal and Image Processing, Book, 1990, pp549-553, Prentice Hall, USA.
M. Ibrahim Sezan, An Overview of Convex Projection Theory and its Application to Image Recovery Problems, Paper, 1992, pp 55-67, Ultramicroscopy 40, Elsevier Science Publishers B.V., North Holland.
Milan Sonka, Vaclav Hlavac and Roger Boyle,Image Processing Analysis and Machine Vision, Book, 1993, pp 88-91, Chapman & Hall Computing, U.K.
K. Ratakonda and N. Ahuja, POCS Based Adaptive Image Magnification, Paper, 1998, pp 203-207, 1998 Internationsl Conference on Image Processing, U.S.A.
Brier Jeffery
Good-Johnson Motilewa
Sharp Laboratories of America Inc.
Varitz PC Robert D.
LandOfFree
POCS-based method for digital image interpolation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with POCS-based method for digital image interpolation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and POCS-based method for digital image interpolation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2598512