Adaptive enlarging and/or sharpening of a digital image

[0001] 1. Field of the Invention

[0002] The present invention relates to graphical image processing and, more particularly, to enlarging and sharpening digital images.

[0003] 2. Description of the Related Art

[0004] Image resizing, such as digital zoom, is a common task in digital image processing. The most commonly used methods of resizing rely on interpolation. Techniques such as fuzzy logic, inter-resolution look-up tables, fractals, and intentional blurring along lines after interpolation have also been used. Current methods face difficulty when the enlargement ratio desired is larger than 2 (two). Image enlargement by interpolation involves mapping pixels in an original image to an enlarged image in which the original image pixels are spaced farther apart in the enlarged image and the intensity values of intervening pixels are determined through interpolation of the original image pixel intensities.

[0005] While interpolation algorithms, such as bi-cubic or bilinear techniques, can produce images that are visually pleasing over most of the image area, at or near high contrast edges there are at least three objectionable problems. The first of these problems is blockiness or jaggedness at high contrast diagonal (not horizontal or vertical) edges. The second problem is ringing, or overshoot and undershoot at high contrast edges. The third problem with resizing by interpolation is the blurring of what should be a near step-change in luminance into a more gradual transition.

[0006] These problems with interpolation techniques can be minimized by carefully selecting the interpolation coefficients, or by blending the images resulting from multiple interpolation methods. For example, U.S. Pat. No. 5,327,257 describes a method in which enlarged images obtained by both a sharp interpolation method and a soft interpolation method are blended using local image characteristics to determine the relative contribution of each image. This technique can successfully eliminate the ringing at high contrast edges, but it can worsen the blur at the same edges compared to using only the sharp interpolation, and will not eliminate the jaggedness, which is generally regarded as more disturbing than the ringing.

[0007] No interpolation technique can eliminate the jaggedness at high contrast diagonal edges. While different interpolation techniques will return differing pixel values for the new pixels in an enlarged image, they will all return the same values for the pixels in the original image. Interpolation algorithms estimate new values for pixels in an enlarged image that lie between values for known pixels, and do not alter the original pixel values. Stated in another way, as an interpolated pixel location gets closer to an original pixel location, the value of the interpolated pixel is more and more constrained by the value of only the nearby original pixel. At high contrast diagonal edges, this causes jaggedness.

[0008] Image sharpening is normally a separate procedure, performed independently of any enlargement processing. By tailoring the image sharpening to the amount of enlargement and with the knowledge of where the most blurring is introduced in the enlargement process, a much improved result can be achieved.

[0009] One common technique used to sharpen images is called unsharp masking. Unsharp masking is effectively an extrapolation of an image to be sharpened away from a blurred version of the image. The technique does result in a sharper image, but has several drawbacks. At high contrast edges, unsharp masking results in overshoots and undershoots. This is particularly true with larger operator (enlargement) sizes, which would be required for enlargement factors greater than 200%. Unsharp masking also tends to amplify any noise in the image and make any artifacts in the image more visible.

[0010] From the discussion above, it should be apparent that there is a need for improved enlarging and sharpening of digital images. The present invention fulfills this need.

[0011] The present invention is directed to enlarging and sharpening of digital images. In accordance with the invention, an enlarged approximated version of an original image is combined with a residual image to produce an output image of desired size, or enlarged resolution. Every pixel in the enlarged approximated image is computed by a two-dimensional (2-D) approximation, rather than an interpolation. The 2-D approximated image will generally be less sharp than an image that is enlarged by a bi-cubic interpolation technique, but it should not have the problems of severe ringing or jaggedness. The residual image is the pixel intensity difference between pixels in the approximated image and corresponding pixels in the original image. When computed, the residual image is the same size as the original image, but may be enlarged to the size of the desired output image. Combining the residual image with the approximated image adds information contained in the residual image that returns the detail (sharpness) that might have been lost in the 2-D approximation process. In accordance with the invention, the residual image data is selectively added to the approximated image such that image information is added everywhere in the image except at continuous edges. The residual information is preferably added to the approximated image in accordance with a continuous function, to avoid artifacts such as jaggedness and overshoot and undershoot. In this way, the present invention provides techniques to both enlarge and sharpen digital images with artifact-free output images that retain or even enhance their details, but do not accentuate image noise.

[0012] Other features and advantages of the present invention should be apparent from the following description, which illustrates, by way of example, the principles of the invention.

[0013] FIG. 1 is a flow diagram that illustrates image processing performed in accordance with the present invention.

[0014] FIG. 2 is a flow diagram of the preferred embodiment, including an image enlargement stage and two image sharpening stages.

[0015] FIG. 3 is a graphical illustration of the lookup table used in the improved unsharp masking algorithm to map a local gradient to an extrapolation factor.

[0016] FIG. 4 is a graphical illustration of the effects of limiting the overshoots inherent in unsharp masking.

[0017] FIG. 5 is a graphical illustration of the effects of the second sharpening technique.

[0018] FIG. 6 is a block diagram representation of an image capture device constructed in accordance with the present invention.

[0019] FIG. 7 is a block diagram representation of a computing device constructed in accordance with the present invention.

[0020] FIG. 1 shows a flow diagram that illustrates image processing that is carried out in accordance with a preferred embodiment of the present invention. The invention can advantageously be implemented on a computing device that is associated with a display, to permit observation of the processing results, and can be performed in real time. Real time operation permits a user to contemporaneously observe the results of the image processing performed in accordance with the invention and to make any changes or modifications to the output image, as desired. The invention may also be implemented in an image capture device, such as a digital camera, as well as a computing device such as a personal computer or graphics workstation. The technique may be used for image resizing, including enlargement and reduction in resolution. The preferred embodiment will be described in the context of image enlargement, but those skilled in the art will be able to understand the description below and identify how the described features and operation can be applied to image reduction.

[0021] Operation in Accordance With the Invention

[0022] In the first operation, represented by the FIG. 1 flow diagram box numbered 102, processing begins with original input image data. The original input image comprises digital data that specifies pixel intensities of an image. The input image may comprise, for example, what is known as a bitmap image and may specify a resolution of 800600 pixels. Each pixel of the image data corresponds to a point on an output display, such as a video display, flat panel device, or printer output. A typical display, for example, includes pixels with a diameter of 0.29 mm.

[0023] Those skilled in the art will understand that conventional image enlargement often occurs by interpolation, which involves mapping pixels in an original image to an enlarged image in which the original image pixels are spaced farther apart in the enlarged image and the intensity values of intervening pixels are determined through interpolation of the original image pixel intensities. For example, the image resolution or image size will double if pixels that were adjacent in the original image are now separated by one intervening pixel in the enlarged image. A similar resizing involving removal of pixels may occur for image reduction. Typically, the input image referenced in box 102 is obtained from data storage or is received from the output of an image capture device. In the next operation, an approximated image is computed from the original input image. Computing the approximated image is represented by the flow diagram box numbered 104.

[0024] In the preferred embodiment, the approximated image has an image size that corresponds to the desired size of the output image. In general, it is preferred that the approximated image is as close as practical to the final output size, so that no additional resizing is needed later in the processing operations. Every pixel in the enlarged approximated image is computed by a two-dimensional (2-D) approximation. This avoids using an interpolation technique, which typically has unpleasant artifacts associated with high contrast edges. Alternatively, the approximated image may have a size different from that of the desired final output size. In that situation, the computation of the approximated image will be easier if the enlargement ratio of the approximated image is an integer ratio. If a non-integer ratio of enlargement is desired, then the approximated image may be enlarged to the nearest integer ratio and then additional resizing may be performed to obtain the desired image size, in accordance with conventional techniques that will be known to those skilled in the art.

[0025] FIG. 1 shows that, in a preferred embodiment, the approximated image is computed using convolution kernels that are computed in an operation represented by the box numbered 106. The convolution kernels (preferably for a least squares approximation) are applied to the original image data, as represented by the multiplication operator 108. The image produced from the applied convolution kernels is the enlarged approximated image, indicated by the flow diagram box numbered 110.

[0026] In the next operation, a residual image is determined. This operation is represented by the flow diagram box numbered 112. Each pixel of the residual image comprises the pixel intensity difference between a pixel in the original image and a corresponding pixel in the approximated image. The residual image therefore is the same size as the original image, but it may be enlarged to the size of the desired output image. Enlarging the residual image to the output image size generally provides an improved quality output image and simplifies processing for the combining operation, described further below.

[0027] The residual image may be enlarged using a variety of techniques, such as interpolation techniques. For example, it has been found that bi-cubic interpolation works well to enlarge the residual image. Using the residual image at the original image size, without enlargement, is equivalent to using a nearest neighbor interpolation technique.

[0028] In addition to using the original input image to produce an enlarged approximated image and the residual image, the input image is also used to compute a set of weighting factors, W. This operation is represented by the flow diagram box numbered 114. The weighting factors govern how the residual image is combined with the enlarged approximated image to produce the output image in accordance with the invention. As described further below, the weighting factor for each pixel is computed based on local image characteristics of the original image. For example, each weighting factor may be computed from a luminance channel of the original image, and the same weighting factor value may be used for all channels associated with the image. Those skilled in the art will be familiar with luminance channel information and other channels associated with a digital image. In addition, each weighting factor may be determined in accordance with a local gaussian curvature value for the corresponding original image pixel, or further in accordance with a local gaussian curvature value and a local image gradient for the corresponding original image pixel. Computational procedures for determining the weighting factors are described further below.

[0029] After the weighting factors are determined at box 114, the weighting factors are used to selectively combine pixels of the residual image with pixels of the enlarged approximated image. That is, the weighting factors provide a means of selectively adding information from the residual image to the approximated image, such that image information is added everywhere in the approximated image except at continuous edges. The residual information is preferably added to the approximated image in accordance with a continuous function, as described further below, to avoid artifacts. The resulting combined image, the output image of desired enlargement, may then be viewed on a display device or printed on an output surface such as paper stock, or may be stored for later retrieval and display or printing.

[0030] To selectively combine the residual image information with the approximated image, the preferred embodiment combines the weighting factors with the residual image data, as represented by the multiplication operator 116. A different weighting factor may be determined for each pixel of the residual image. The processed (weighted) residual image is then combined with the approximated image. This operation is represented by the addition operator 118. It should be apparent that any weighting factor of zero, applied to a pixel of the residual image, will effectively eliminate that residual image pixel from being added into the approximated image. In this way, pixels of the residual image are selectively added into the approximated image at the operator 118 to produce the output image at box 120.

[0031] An optional post processing phase may be implemented to further enhance the output image produced in accordance with the invention. The post processing is represented by the flow diagram box numbered 122.

[0032] In one aspect of the optional post processing of box 122, any sharpness that was lost in producing the approximated image is restored in a modification procedure that sharpens the enlarged output image along high contrast edges. The modification procedure preferably involves an unsharp masking procedure and a local histogram modification procedure. In this way, the enlarged image is processed serially by two algorithms that together achieve a sharp and pleasing image.

[0033] The unsharp masking technique in accordance with the invention is a technique that limits overshoots and undershoots and does not amplify the noise in the image to be sharpened. Overshoots and undershoots are limited by searching an area around the pixel to be modified for maximum and minimum intensities and bringing any modified pixel value outside the range between the maximum and the minimum back towards the range. The size of the search area is a function of either the enlargement ratio or the amount of blur used in the unsharp mask algorithm. The modification that limits noise, while sharpening image detail, varies the amount of sharpening for each pixel based on the image gradient at that pixel, using a lookup table.

[0034] The second post processing sharpening technique is applied mainly at high contrast continuous edges, where little of the residual image is added back in and where blur is the most apparent to the human visual system. The second algorithm is a local histogram modification technique in which intermediate pixel values are remapped towards the dark or light extremes of the blurred edge. The result is a sharper edge profile.

[0035] Thus, the preferred embodiment, which utilizes the post processing techniques, comprises a two-pronged approach to achieving high-quality digitally enlarged images. It has been found that the unsharp masking and local histogram modification provide superior final images, and these operations are used in the preferred embodiment. Similarly, resizing the residual image to the output image size is optional, but provides superior results and is performed by the preferred embodiment. First, a weighted combination of the 2-D least-squares approximation and its residual image is used to enlarge the image with minimal artifacts. Then, two sharpening algorithms that depend on the scale factor to reduce the blurriness follow the enlargement step. The end result is an enlarged, sharp image with minimal artifacts.

[0036] Processing of an original input image in accordance with the invention as described above permits enlarging and sharpening digital images with artifact-free output images that retain or even enhance their details, but do not accentuate image noise.

[0037] Optional Operations

[0038] Additional processing may be performed to further enhance the output images obtained in accordance with the invention. These operations, as well as other details of processing in accordance with a preferred embodiment of the invention, are described with reference to FIG. 2, which shows processing that is especially suited to a digital zoom image.

[0039] Image processing in accordance with the invention begins with an original digital image, indicated at the flow diagram box numbered 202. The next operation in the digital image processing is to pad the original input image, as indicated at box 204. This is performed to prevent image boundary effects in the processing stages from affecting the final image. In the preferred embodiment, mirroring the image at each boundary is the method used to pad the image. The image boundary, for a quadrilateral image, is defined with boundary (1) as the top edge, boundary (2) as the bottom edge, boundary (3) as the left vertical edge, and boundary (4) as the right vertical edge. The padding effectively creates a border around the image boundaries and will be removed after the various processing operations are performed.

[0040] As noted above, the 2-D least-squares approximation can advantageously be performed by convolution if the scaling factor (enlargement ratio) is an integer value, the same sub-pixel locations (relative to each original pixel) are to be approximated for each pixel interval in the original image. For example, for a scaling factor or resolution enlargement of 2.0, the locations would be: (0, 0), (0.5, 0),

[0041] (0, 0.5), and (0.5, 0.5). Each sub-pixel location needs its own convolution kernel, but once the kernel is computed (indicated at box 206), the approximated value for that relative location can be computed for every pixel interval in the original image by convolution (indicated by the summing operator). Those skilled in the art will understand details of how such approximated values may be computed.

[0042] Prior to performing the 2-D least-squares approximation at box 208, the convolution kernels are pre-computed, as indicated at box 206. In the preferred embodiment, only integer multiples of the resolution will be computed in this manner, so that the pre-computed kernels can be reused at each location in the original image. If a non-integer scaling factor is desired, the image will be enlarged up to the next highest integer multiple of the desired resolution, and then resampled back down to the desired final resolution using bi-cubic interpolation. An 88 fifth-order convolution kernel is computed for each (dx, dy) combination (each approximated pixel). For example, for a four-times expansion in each direction, sixteen convolution kernels are needed, because the resolution increases by a factor of four squared and the (dx, dy) combinations are (0, 0), (0, 0.25), (0, 0.5), . . . , and (0.75, 0.75).

[0043] In the preferred embodiment, the weighted least squares convolution kernels are computed using Equation (1) below:

[0044] where assuming a fifth order fit and an 88 kernel, $A=\left[\begin{array}{cccc}{}_1\left(x_1,y_1\right)& {}_2\left(x_1,y_1\right)& & {}_m\left(x_1,y_1\right)\\ {}_1\left(x_2,y_2\right)& {}_2\left(x_2,y_2\right)& & {}_m\left(x_2,y_2\right)\\ & & & \\ {}_1\left(x_n,y_n\right)& {}_2\left(x_n,y_n\right)& & {}_m\left(x_n,y_n\right)\end{array}\right]$

[0045] then: $u=\left[\begin{array}{c}{}_1\\ {}_2\\ \\ {}_m\end{array}\right]$

[0046] with one column for each (x, y) combination.

[0047] Those skilled in the art will understand that Equation (1) is derived using a Moore-Penrose inverse found by singular value decomposition.

[0048] In the above Equation (1), the vector z is of length n and contains the pixel intensities that will be used in the approximation, and W is an n x n matrix containing the weighting factors of the error components. The weights are from a gaussian distribution with a standard deviation (SD) of one pixel to prevent any ringing in the image. Those skilled in the art will understand that, for a fifth order fit, m21 and, for an 88 kernel, n64. Combinations (x₁, y₁), (x₂, y₂), . . . , and (x_{n, yn}) are the x and y positions, respectively, of the 88 pixels in the original image, relative to the chosen origin, and are used to approximate the desired pixel in the least-squares approximated image.

[0049] If the origin is chosen to coincide with the location of the pixel to be approximated, only the constant part of the column vector u (₁) is needed, since x and y will be zero for that point. The n64 values in the first row of the matrix (A^TWA)¹A^TW becomes the 88 convolution kernel. One convolution kernel needs to be computed for each (dx, dy) combination. For a scaling factor of four, sixteen convolution kernels are needed. The sixteen convolution kernels can be pre-computed at box 206 and used repeatedly to compute the least-squares approximated image.

[0050] Each convolution kernel is multiplied pixel by pixel with the same eight by eight patch of the Red, Green, Blue (RGB) data in the original image to approximate the pixel intensity for all (dx, dy) combinations, thereby producing the approximated image. Using a 66 kernel instead of an 88 kernel can, depending on the convolution method, improve the speed. The smaller kernel, however, does not perform as well on diagonal edges, and some ringing may be evident.

[0051] Once the least-squares approximated image is computed at box 208, a residual image is computed, as indicated at box 210. If the enlargement is accomplished by interpolation and not least-squares approximation, then every n point would have the same intensity as the corresponding point in the original image, where n is the integer scale multiplier. This is because in interpolation, unlike approximation, the fitting functions are constrained to pass through the original pixel points. The least-squares image produced in accordance with the invention does not have this constraint.

[0052] The residual image, which will be the same size as the original scale padded image, is computed by taking the difference between the original pixel value and the approximated pixel value of the corresponding point. This image is then enlarged by the desired multiplication (enlargement) factor using bi-cubic interpolation. The interpolation operation is indicated by the flow diagram box numbered 212.

[0053] It has been found that, to obtain a suitable enlarged image, at each pixel a fraction (which depends on a weighting factor computed using local image characteristics) of this residual image is added to the least-squares approximated image. The weighting factor should indicate the presence of continuous edges, since continuous edges are what can lead to artifacts. It has been found that a combination of the gaussian curvature and the gradient of the image performs well in indicating the presence of continuous edges.

[0054] In the preferred embodiment, the first step in computing the weighting factor is to convert the original sized padded image (typically in RGB color space) into YCC space, a luminance-chrominance color space known to those skilled in the art. The YCC conversion is indicated by the flow diagram box numbered 220. The purpose of this operation is to obtain one weighting factor that will be applied to the three channels of the color image. The weighting factor will be computed using the Y, or luminance, channel of the YCC image. Any combination of the RGB channels that approximates luminance can be used to produce the YCC image. The following equation, Equation (2), based on the National TV Standards Committee (NTSC) primaries, is used for the YCC conversion: $\begin{array}{cc}\left[\begin{array}{c}Y\\ Cb\\ Cr\end{array}\right]=\left[\begin{array}{ccc}0.2989& 0.5866& 0.1145\\ -0.1687& -0.3312& 0.5000\\ 0.5000& -0.4183& -0.0816\end{array}\right]\left[\begin{array}{c}R\\ G\\ B\end{array}\right]& \left(2\right)\end{array}$

[0055] If the starting RGB values are sRGB, then the ITU-R BT.709-2 primaries should be used. The equation for sRGB is given by Equation (3): $\begin{array}{cc}\left[\begin{array}{c}Y\\ Cb\\ Cr\end{array}\right]=\left[\begin{array}{ccc}0.2126& 0.7152& 0.0722\\ -0.1146& -0.3854& 0.5000\\ 0.5000& -0.4542& -0.0458\end{array}\right]\left[\begin{array}{c}R\\ G\\ B\end{array}\right]& \left(3\right)\end{array}$

[0056] Once the Y-channel image is obtained, the gaussian curvature at each pixel is computed using a finite difference technique shown in Equation (4). $\begin{array}{cc}\begin{array}{c}\mathrm{C1}\left(x,y\right)=\frac{Zxx\left(x,y\right)*Zyy\left(x,y\right)-Z^{2}xy\left(x,y\right)}{{\left(1+Z^{2}x\left(x,y\right)+Z^{2}y\left(x,y\right)\right)}^2}\\ W\mathrm{he}reZx\left(x,y\right)=\frac{Z\left(x+1,y\right)-Z\left(x-1,y\right)}{2}\\ Zy\left(x,y\right)=\frac{Z\left(x,y+1\right)-Z\left(x,y-1\right)}{2}\\ Zxx\left(x,y\right)=Z\left(x+1,y\right)-2*Z\left(x,y\right)+Z\left(x-1,y\right)\\ Zyy\left(x,y\right)=Z\left(x,y+1\right)-2*Z\left(x,y\right)+Z\left(x,y-1\right)\\ Zxy\left(x,y\right)=\frac{Z\left(x+1,y+1\right)+Z\left(x-1,y-1\right)-Z\left(x+1,y-1\right)-Z\left(x-1,y+1\right)}{4}\end{array}& \left(4\right)\end{array}$

[0057] The gaussian curvature computation is indicated by the flow diagram box numbered 222. Prior to computing the finite differences, each pixel intensity value, Z, is divided by two. This is to adjust for the different scales of the three dimensions. The values x and y denote distances, but Z is a measure of intensity. Dividing by two has been found to achieve the desired results of near zero values at sharp edges and higher values elsewhere in the image.

[0058] The values of the gaussian curvature cover a very wide range, with relatively few pixels obtaining high values. To compress the range, the base-10 logarithm of each value plus one is computed, and a typical image is scaled from zero to approximately twenty for pixel intensity values. These operations are shown in Equation (5).

[0059] The Equation (5) denominator value of 3.2 has been found to yield pleasing results. Similar values should produce similar results and alternative values may be determined by experimentation according to individual preference. At this point, the gaussian curvature image is blurred by convolving with a gaussian (SD1) to smooth it out. Any resultant value greater than one is clipped to one. All of these operations are represented by the FIG. 2 flow diagram box numbered 222.

[0060] In the preferred embodiment, a gradient image is computed by convolving the Y (intensity) image with both a horizontal (H) and a vertical (V) Prewitt operator, shown in Equation (6): $\begin{array}{cc}H=\left[\begin{array}{ccc}-1& -1& -1\\ 0& 0& 0\\ 1& 1& 1\end{array}\right]V=\left[\begin{array}{ccc}-1& 0& 1\\ -1& 0& 1\\ -1& 0& 1\end{array}\right]& \left(6\right)\end{array}$

[0061] Those skilled in the art will be familiar with other alternative gradient detectors that would provide a suitable result. The gradient computation is represented by the flow diagram box numbered 224.

[0062] A single gradient value at each pixel is computed by taking the square root of the sum of the squares of the vertical and horizontal gradient values. The gradient image is then scaled by dividing each value by 530.00 and clipping the resulting number to 1 (one). Any scaled value less than 0.07 is set to be equal to 0.07. The number 530.00 has been found to be about the largest gradient value found in typical images. The gradient computation process is represented by box 224.

[0063] A weighting factor (w) is determined by computing the ratio of the squares of the gaussian curvature and gradient values, as shown in Equation (7) below. Computation of the weighting factor is represented in FIG. 2 by the flow diagram box numbered 226. $\begin{array}{cc}w\left(x,y\right)={\log }_{10}\left(\frac{{C\left(x,y\right)}^2}{\mathrm{Grad}{\left(x,y\right)}^2}\right)/2.3& \left(7\right)\end{array}$

[0064] Any value of w greater than one is clipped to one. Near-zero values of w are achieved at high contrast edges, where the gaussian curvature is small and the gradient is large. If both the gaussian curvature and the gradient are small, the image region is very smooth and very little information will be contained in the residual image rendering the value of w unimportant. Because of the floor put on the value of the gradient, a ceiling is placed on the value of the weighting factor. If both the gaussian curvature and the gradient are large, the weighting factor will be larger than the case of a high contrast edge. The final case, where the value of the gaussian curvature is large and the gradient is small (large w) would indicate fine details, where all of the information in the residual image should be added back in. The computation of weighting factors is indicated by the box numbered 226.

[0065] The resized (enlarged) image (I) is a combination of the least-squares (LS) image and the residual image (R). They are combined using the weighting factor (w) from box 226 by the following equation, Equation (8):

[0066] Combining the weighting factor with the residual image data is represented by box 228 and the multiplication operator, and combining with the least squares image data is represented by the summing operator. The technique described above results in a smooth, reasonably detailed image at box 230; but the blended, interpolated image is one that is undeniably blurry. This is particularly true at the high contrast edges, where the enlargement contains information from only the least-squares approximation. Since both the cause of the blur and image locations where the blur is the worst (small w) are known, a good sharpening technique was determined for application to the resized image.

[0067] The second part of the preferred operation in accordance with the invention includes two image-dependent sharpening techniques, applied serially. The first sharpening technique is a modification of the commonly used unsharp masking technique. The second sharpening technique is a local histogram modification method.

[0068] In order to reduce the computational time and to minimize any color changes, both sharpening algorithms are applied to only a luminance channel Y. Conversion of the image to be sharpened into YCC space is performed at box 232. Equation (2) or (3) may be used to convert from RGB to YCC. After sharpening the Y channel, the image is converted back to RGB space using either Equation (9): $\begin{array}{cc}\left[\begin{array}{c}R\\ G\\ B\end{array}\right]=\left[\begin{array}{ccc}1.0000& 0.0000& 1.4022\\ 1.0000& -0.3456& -0.7145\\ 1.0000& 1.7710& 0.0000\end{array}\right]\left[\begin{array}{c}Y\\ Cb\\ Cr\end{array}\right]& \left(9\right)\end{array}$

[0069] for NTSC primaries, or Equation (10): $\begin{array}{cc}\left[\begin{array}{c}R\\ G\\ B\end{array}\right]=\left[\begin{array}{ccc}1.0000& 0.0000& 1.5748\\ 1.0000& -0.1873& -0.4681\\ 1.0000& 1.8556& 0.0000\end{array}\right]\left[\begin{array}{c}Y\\ Cb\\ Cr\end{array}\right]& \left(10\right)\end{array}$

[0070] for ITU-R BT.709-2 primaries.

[0071] In the preferred embodiment, the unsharp masking operation is performed at box 234 by extrapolating away from a blurred version of the image to be sharpened. The first step is to blur the enlarged image. This is preferably achieved by convolving the enlarged image with a gaussian of standard deviation equal to half the image enlargement factor, and a kernel size of plus and minus four standard deviations. The extrapolation is computed using the following Equation (11):

[0072] wherein S is the sharpened image, I is the enlarged image, B is the blurred version of the enlarged image and a controls the sharpening. If a is less than one, Equation (9) will result in a blurred version of I. If, however, is greater than one, S is extrapolated away from the blurred image and the resultant image is sharper. In most unsharp masking routines in the prior art, is a constant value if some threshold condition in the image is met. That is not the case in the present invention.

[0073] The value of is computed for each pixel in the image to be sharpened. The first step in computing a is to blur the gradient map computed for the resizing algorithm. This is indicated at the flow diagram box numbered 236. In the preferred embodiment, the blurring is performed by convolving with a gaussian standard deviation equal to 1 (one). Next, the blurred gradient map is resized using bi-cubic interpolation up to the size of the image to be sharpened, as indicated at box 238. The blurred gradient value at each pixel is then mapped using a look-up table to a value of . For very low gradient values, little or no sharpening is desired and a is set to near 1 (one). The value of then increases linearly as the gradient value increases up to a maximum value. A range of gradient values map to the highest value of ; but above a cutoff value, decreases linearly down to a minimum value as the gradient increases. An example look-up table of gradient values versus output values is shown in FIG. 3.

[0074] Computing in this manner has the effect of sharpening the edges and texture of the image without accentuating image noise. It also avoids many artifacts that are visible when applying a standard unsharp mask. The operation of unsharp masking with the blurred interpolated gradient image and a processing is represented by box 234.

[0075] One problem with unsharp masking often remains: overshoot. An unsharp mask can result in severe overshoot at sharp edges. This is most apparent when an image transitions from a light gray region to a dark gray region at a step edge. If unsharp masking is applied, on the light side of the edge the overshoot will cause a white line, and on the dark gray side it will cause a black line. If strong unsharp masking is applied, the overshoot can be quite disturbing.

[0076] In accordance with the preferred embodiment, the first step in minimizing any overshoot is to find minimum and maximum pixel values surrounding the pixel to be modified. When sharpening an enlarged image, the size of the range to be searched is a function of the scale factor of the image. Otherwise, it is a function of the amount of blur in the blurred version of the image. It has been found that a good search range to use is plus and minus the scale factor around the pixel to be modified, or twice the standard deviation of the gaussian used to blur the image. If the pixel value returned by the unsharp mask algorithm is outside the range of the maximum and the minimum, it is adjusted most of the way back to the minimum or the maximum. It has been found that a value of about 85% provides useful and pleasing results. Overshoots can be eliminated by reducing the value all the way back to the local maximum or minimum at the cost of flat, unchanging regions of the image near edges and a slight loss in apparent sharpness.

[0077] FIG. 4 demonstrates the effect of limiting the overshoot in this way. It shows the pixel intensity values for a horizontal slice through a high contrast edge of a digital photograph that has been enlarged by a factor of 6 in each direction. Three levels of overshoot are shown, 0%, 20%, and 100%. For all levels of overshoot, the edge gradient is increased by the same amount.

[0078] Thus, improved image sharpening in accordance with the present invention involves sharpening the resized output image by computing a gradient image for the original input image and extrapolating the intensity of each resized image pixel away from a blurred version of the resized image. Preferably, the extrapolation is performed in accordance with a corresponding gradient value, thereby producing a sharpened image, and then for each pixel in the unsharpened image searching the image area surrounding the pixel and finding the maximum and minimum pixel intensity value in the searched area, wherein the size of the area to be searched is a function of the resolution factor of the resized output image in comparison with the original input image. Lastly, the improved sharpening involves, for each pixel in the sharpened image produced from extrapolating the pixel intensity, comparing the intensity value of a sharpened image pixel to the corresponding maximum and minimum intensity values found in pixels of the unsharpened image from the search operation, and modifying the intensity value of the sharpened image pixel in response to the comparison. Thus, pixel intensity values are identified where the intensity value of the sharpened pixel is outside the range of the maximum and the minimum intensity values found in the unsharpened image, and then the sharpened intensity values are modified to be closer to the nearer of the maximum or the minimum of the found intensity values.

[0079] The process can be described as follows for the case where the sharpened intensity values are less than the minimum values:

[0080] The sharpened image is modified by identifying when the value of the sharpened pixel is greater than the maximum intensity value, and modifying the sharpened pixel intensity value to a value given by F(x, y), wherein F(x, y) is specified according to the relationship of Equation (12):

[0081] wherein F(x, y) is the final sharpened pixel intensity value, min(x, y) is the minimum intensity value found for that pixel location, a is a value that specifies the fraction of the overshoot to allow, and S(x, y) is the value of the sharpened pixel intensity. As noted above, it is noted that a0.15 that is, (10.85) adjustment has been found to provide good results, but other values may be utilized, depending on the desired effect and characteristics of the image.

[0082] The process can be described as follows for the case where the sharpened intensity values are less than the minimum values:

[0083] The sharpened image is modified by identifying when the value of the sharpened pixel is less than the minimum intensity value, and modifying the sharpened pixel intensity value to a value given by F(x, y), wherein F(x, y) is specified according to the relationship of Equation (13):

[0084] wherein F(x, y) is the final sharpened pixel intensity value, min(x, y) is the minimum intensity value found for that pixel location, a is a value that specifies the fraction of the overshoot to allow, and S(x, y) is the value of the sharpened pixel intensity. As before, it is noted that a0.15 an adjustment of (10.85) has been found to provide good results, but other values may be utilized, depending on desired effect and characteristics of the image.

[0085] These modifications to unsharp masking result in a much-improved process for producing output images. The process is useful on any image that is in need of sharpening, whether or not it has been enlarged by the operations described in accordance with the present invention.

[0086] The unsharp masking performs well for sharpening the overall image, but does not necessarily reduce the blur in the enlarged image enough at high contrast edges. This is partially because the high contrast edges are enlarged using only the least-squares fit and partially because the human visual system is very sensitive to blur at high contrast edges. A highly specific sharpening technique is desired for the high contrast edges in enlarged images.

[0087] Since an edge map (referred to as the weighting factor previously) and a gradient map have already been computed, applying a sharpening routine only to the edges can be achieved for relatively little computational cost. The method selected is a form of local histogram modification. The local histogram modification pushes the pixel values at edges towards the brightest or darkest neighboring pixels, which has the effect of sharpening edges.

[0088] A weighting factor that will scale the effects of the local histogram modification routine is a modification to the weighting factor computed earlier for the enlargement. The new weighting factor (W) is computed with the following equation, Equation (14):

[0089] wherein W is the new weighting factor, w is the weighting factor computed in the enlarging stage (from box 226) and G is the gradient map computed in the smart unsharp masking stage. Any values higher than one are clipped to one. Most pixels in the image should have a W value close to zero (not edge pixels). The calculation of the new weighting factor W is represented by box 240, and the combining with the gradient image from box 236, 238 processing is represented by the flow diagram box numbered 242.

[0090] The histogram modification is applied to any pixel with a W value greater than a threshold value (0.2 to 0.3 preferably). When such a pixel is located, a square region (plus and minus half the scale factor from the pixel to be modified) is searched for other pixels with a suprathreshold value of W. Both the maximum and the minimum intensity values (Y) of these pixels are determined.

[0091] The maximum and minimum intensity values of the surrounding pixels are used to compute a new intensity value for the pixel to be modified. A logistic function is used to map the pixel intensity to a new intensity. The function used is given by Equation (15): $\begin{array}{cc}S\left(x,y\right)=x\mathrm{Min}\left(x,y\right)+a*\frac{1}{1+{}^{\frac{I\left(x,y\right)-\mathrm{Mid}}{B}}}& \left(15\right)\end{array}$

[0092] where $\mathrm{Mid}=\frac{x\mathrm{Max}\left(x,y\right)+x\mathrm{Min}\left(x,y\right)}{2},$

[0093] and $B=\frac{x\mathrm{Max}\left(x,y\right)-x\mathrm{Min}\left(x,y\right)}{12}$

[0094] wherein S is the new computed pixel intensity, I is the pixel intensity to be remapped and xMin and xMax are the minimum and maximum surrounding pixel intensities of each pixel with a suprathreshold W.

[0095] In order to avoid any artifacts due to a sudden change in image sharpness, the intensity computed with the logistic function is blended with the original pixel intensity using the following equation, Equation (16):

[0096] wherein V is the final pixel value, W is the weighting factor, S is the intensity computed by the logistic function and I is the unsharpened image intensity. This processing results in a sharpened Y channel image, indicated at box 242.

[0097] FIG. 5 demonstrates the effect of sharpening in this manner. It shows the pixel intensity values for a horizontal slice through a high contrast edge of a digital photograph that has been enlarged by a factor of six in each direction. There is an increase in the edge slope and no pixels beyond the edge have been altered.

[0098] The image resulting from the preferred embodiment of this invention is ten converted back to RGB representation, indicated at box 244, and the image padding added initially at box 204 can be removed at box 246. The resized output image produced from the operations described above has sharp high contrast edges, with minimal apparent artifacts.

[0099] The processing described above in accordance with the invention may be performed in an image capture device or any computing device with user input and a suitable associated display, such as a video display (CRT) device, flat panel display, or printer. FIG. 6 is a block diagram representation of an image capture device constructed in accordance with the present invention. FIG. 7 is a block diagram representation of a computing device constructed in accordance with the present invention.

[0100] Image Capture Device

[0101] FIG. 6 shows a digital camera 600 or other similar image capture device that incorporates image processing operations in accordance with the present invention. The camera includes an image capture module 602 that may comprise an optical lens and capture array, such as a CCD array. The module provides its output to an image memory 604 over a system bus 606 for temporary storage, operating under control of a central processing unit (CPU) 608. The image data may be retrieved from memory and provided to a graphics processor 610, which processes the image data in accordance with the description above. The graphics processor may comprise the CPU operating to process pixel data or may be a dedicated graphics processor. The memory 604 may be partitioned or managed by the CPU to have segments comprising buffers for temporarily storing the image data, coefficients, and the like.

[0102] The processing results may be observed by a user via a display output device 612, such as an LCD screen or an output port connection to a printer or other display device. An operator interface 614 is used to receive user commands, such as specifying enlargement ratios or other processing choices. The memory 604 may receive image data from external stores, such as flash memory devices used in conjunction with the digital camera, or may receive the image data from other data sources associated with the digital camera.

[0103] Computer Construction

[0104] The image processing in accordance with FIG. 1 and FIG. 2 above may be implemented in a computer device, such as a personal computer, or any other of a variety of processing devices, such as a handheld computing device, a Personal Digital Assistant (PDA), and any conventional computer suitable for implementing the functionality described herein.

[0105] FIG. 7 is a block diagram of an exemplary computer device 700 such as might comprise a graphics image processor that implements the operation described in FIG. 1 or FIG. 2. The computer 700 operates under control of a central processor unit (CPU) 702, such as an application specific integrated circuit (ASIC) from a number of vendors, or a Pentium-class microprocessor and associated integrated circuit chips, available from Intel Corporation of Santa Clara, Calif., USA. Commands and data can be input from a user control panel, remote control device, or a keyboard and mouse combination 704 and inputs and output can be viewed at a display 706. The display is typically a video monitor or flat panel display device.

[0106] The computer device 700 may comprise a personal computer or, in the case of a networked client machine, the computer device may comprise a Web appliance or other suitable network communications device. In the case of a personal computer, the device 700 preferably includes a direct access storage device (DASD) 708, such as a fixed hard disk drive (HDD). The memory 710 typically comprises volatile semiconductor random access memory (RAM). If the computer device 700 is a personal computer, it preferably includes a program product reader 712 that accepts a program product storage device 714, from which the program product reader can read data (and to which it can optionally write data). The program product reader can comprise, for example, a disk drive, and the program product storage device can comprise removable storage media such as a floppy disk, an optical CD-ROM disc, a CD-R disc, a CD-RW disc, a DVD disk, or the like. Semiconductor memory devices for data storage and corresponding readers may also be used. The computer device 700 can optionally communicate with other computers over a network, though the image processing operations in accordance with the present invention do not depend on any networked communications. If the computer 700 is networked, then the computer can communicate with the other connected computers over a network 716 (such as the Internet) through a network interface 718 that enables communication over a connection 720 between the network and the computer device.

[0107] The CPU 702 operates under control of programming steps that are temporarily stored in the memory 710 of the computer 700. When the programming steps are executed, the pertinent system component performs its functions. Thus, the programming steps implement the image processing operations described in accordance with FIG. 1 and FIG. 2. The programming steps can be received from the DASD 708, through the program product 714, or through the network connection 720, or can be incorporated into an ASIC as part of the production process for the computer device. If the computer device includes a storage drive 712, then it can receive a program product, read programming steps recorded thereon, and transfer the programming steps into the memory 710 for execution by the CPU 702. As noted above, the program product storage device can comprise any one of multiple removable media having recorded computer-readable instructions, including magnetic floppy disks, CD-ROM, and DVD storage discs. Other suitable program product storage devices can include magnetic tape and semiconductor memory chips. In this way, the processing steps necessary for operation in accordance with the invention can be embodied on a program product.

[0108] Alternatively, the program steps can be received into the operating memory 710 over the network 716. In the network method, the computer receives data including program steps into the memory 710 through the network interface 718 after network communication has been established over the network connection 720 by well-known methods that will be understood by those skilled in the art without further explanation. The program steps are then executed by the CPU 702 to implement the processing of the system.

[0109] The memory 710 may be partitioned or managed by the CPU or other memory controller to have segments comprising one or more buffers for temporarily storing the image data. Alternatively, the memory may include other forms of data storage that provide the necessary data buffers and storage for implementing the processing described above.

[0110] The present invention has been described with reference to the specific embodiments above so that an understanding of the present invention can be conveyed. It should be understood, however, that various changes may be made and equivalents may be substituted without departing from the true spirit and scope of the invention. In addition, many modifications (for example, operating steps) may be made to adapt to a particular situation. The present invention should therefore not be seen as limited to the particular embodiments described herein, but rather, it should be understood that the present invention has wide applicability with respect to image processing generally. All modifications, variations, or equivalent arrangements and implementations that are within the scope of the claims should therefore be considered within the scope of the invention.