Blur detection system

[0001] The present invention relates to the processing of digital images, and specifically, to a system for estimating and/or reducing the amount of image blur in digital images.

[0002] Digital representation of an image presents a wide array of advantages over analog representation of images, e.g. negative film, positive slide, etc. Digital images, for example, may be electronically stored, transmitted, and copied without degradation of the image. Digital images of objects and events may be captured by traditional devices such as a digital camera, scanned from a negative or picture by a scanner or may be computer-generated. Digital images may also be digitally processed and manipulated to change image characteristics such as color and contrast, or reduce defects or artifacts in the image, such as red-eye from a camera flash or image blur.

[0003] Image blur is one of the most important factors in the perception of image quality due to the attendant loss of image detail and sharpness. Image blur may be the result of a number of things, including for example, camera lenses not focused on the subject, aperture blur of the foreground and/or the background, relative motion of the subject with respect to the camera, and even atmospheric haze. Image blur in traditional, analog images such as color photographs historically could not be perceptibly reduced. Image blur in digital images, however, can be perceptibly reduced. Existing processing techniques for reducing image blur typically include both a blur estimation component and a blur reduction component. If the blur estimation component detects image blur beyond a predetermined threshold, the image is processed by the blur reduction component. Some existing processing techniques for reducing image blur quantify the image blur and adjust the correction accordingly. Other techniques for reducing image blur employ an iterative process that repeatedly cycles the image through the blur reduction component until the estimated amount of image blur is below the predetermined threshold.

[0004] One existing system of estimating image blur is done in the spatial domain. In this system, sharp edges are used to generate a point-spread function and the amount of image blur is estimated from this function. A frequent problem encountered with this system is that many real-world images lack sufficiently sharp edges to reliably estimate image blur.

[0005] Another system of estimating image blur estimates the amount image blur from the power spectrum of the image in the frequency domain. This system takes advantage of the assumption that the power spectrum of most real-world, non-blurred images is relatively invariant where the power at non-zero frequencies is generally inversely proportional to the square of frequency. Blurred images, conversely, exhibit a characteristic where the power falls more rapidly as frequency increases. This phenomenon is illustrated in FIG. 1, which shows the power spectrum of both a blurred image and a non-blurred image. As can be seen from FIG. 1, the power of the blurred image is approximately equal to that of the non-blurred image at very low frequencies, but quickly drops below that of the non-blurred image at frequencies greater than approximately 0.05 cycles/sample. Because they uses scene statistics, systems that estimate image blur from the power spectrum of the image are generally considered to be more reliable than systems that estimate image blur from a point spread function derived from image structure, such as sharp edges. Systems that estimate image blur from the power spectrum of the image, however, are computationally complex, making implementation difficult in many applications, such as a photo printer.

[0006] Yet another system for estimating image blur is disclosed by Zhang et al., U.S. Pat. No. 6,298,145 B1. This system estimates the amount of image blur in a digital image from a weighted occurrence histogram of all non-zero DCT coefficients contained in the digital image file that stores the digital image. As stated in this reference, however, this system “does not use the [DCT] coefficients directly since their values are closely related to the type of image they depict.” Instead, the DCT components are used to construct the aforementioned occurrence histogram, which must then be mathematically manipulated, adding computational complexity.

[0007] What is desired, then, is a computationally efficient system for estimating and/or reducing image blur.

[0016] FIG. 2 illustrates a typical blur estimation and reduction system where an input image is sent to a blur estimation module to determine if blur exists, and if so, estimate the amount of blur. A blur reduction module determines whether to apply a blur reduction process, and if so, how much blur to reduce. The process may be iterative, if desired, such as repeatedly processing the input image through the blur estimation and reduction system until a blur threshold is reached.

[0017] Most digital images are stored in image formats that encode an image using the forward discrete cosine transform (DCT) function

[0018] $F\left(u,v\right)=\frac{2}{n}C\left(u\right)C\left(v\right)\sum _{k=0}^{n-1}\sum _{l=0}^{n-1}f\left(k,l\right)\cos \left[\frac{\left(2k+1\right)u\pi }{2n}\right]\cos \left[\frac{\left(2l+1\right)v\pi }{2n}\right]$
and decode an image using the inverse DCT transform function

[0019] $f\left(k,l\right)=\frac{2}{n}\sum _{u=0}^{n-1}\sum _{v=0}^{n-1}C\left(u\right)C\left(v\right)F\left(u,v\right)\cos \left[\frac{\left(2k+1\right)u\pi }{2n}\right]\cos \left[\frac{\left(2l+1\right)v\pi }{2n}\right]$

[0020] The forward DCT transform converts pixel information of a digital image in the spatial domain to energy, or power information in the frequency domain. Converting a digital image to the frequency domain allows the image to be compressed significantly, saving storage space. By way of illustration, a black and white digital image stored in the spatial domain requires that every pixel be encoded with a number, of arbitrary bit-length, that represents the pixel's shade on a gray-scale. For convenience, digital images are usually organized into 8×8 blocks of pixels when stored in a digital image file. Thus if an 8-bit gray-scale is used to store pixel information of a black and white image in a digital image file, the digital image file will comprise a series of numbers, organized into sequential 8×8 arrays, each number valued between 0 and 255, and representing the shade of their corresponding pixels. This requires a good deal of storage space to store. If higher bit-lengths are used, even greater space is required.

[0021] Color images stored in the spatial domain require even more storage space because each pixel may be represented by three components (or any number) to properly preserve the color information of the pixel, such as [R, G, B] or [L, Cr, Cb]. For example, if a 24-bit Y, Cr, Cb digital image file stores a color image, the digital file will comprise three separate series of 8×8 arrays, each series representing one component of the chosen color coordinate system. Each number in each array will be an 8-bit number, 0 to 255, representing the shade of its corresponding color coordinate for its corresponding pixel.

[0022] The forward DCT transform converts each array from pixel information in the spatial domain into energy information in the frequency domain at discrete vertical and horizontal frequency components, respectively. Like image formats that store images in the spatial domain, image formats that store images in the frequency domain typically organize the power information of an image into 8×8 blocks. In other words, the power information of an image may be stored at eight discrete vertical frequency components and eight discrete horizontal frequency components, graphically represented in the 8×8 grid shown in FIG. 3. The C00 term 10 shown in FIG. 3 represents the DC frequency component of the image, i.e. image power at both zero horizontal and vertical frequency. The C07 term 12 represents the power of an image at zero vertical frequency and the highest horizontal frequency, while the C70 term 14 represents the power of an image at zero horizontal and the highest vertical frequency. The C77 term 16 represents the power of an image at both the highest vertical frequency and the highest horizontal frequency.

[0023] Digital images encoded in the frequency domain can be more easily compressed because the vast majority of the energy, or power, within real-world images is contained in the low frequency blocks. Accordingly, if the digital image file were to discard image information at high vertical and horizontal frequencies, the image could still be decoded into the spatial domain for display while retaining most of the image's detail. One commonly used digital image format that uses a forward DCT transform to characterize an image is the JPEG format, though other digital image formats use this transform as well. The JPEG format is commonly used to characterize an image because it allows the image to be compressed dramatically without significant loss of image quality.

[0024] The forward DCT transform set forth above is markedly similar to the continuous Fourier transform used in power spectrum analysis. From this fact, the present inventor deduced that, just as the amount of image blur may be estimated from the power spectrum of an image, the image blur should also be discernible from the DCT information already embedded in most compressed digital image files. Thus the computational complexity involved in performing a power spectrum analysis should be avoidable when estimating image blur in a digital image that includes DCT coefficients.

[0025] With this idea, the present inventor determined that there was indeed a variety of information already embedded within the digital image file that could be used to estimate the amount of image blur in a digital image. As an example, FIGS. 4 and 5 show one such measure of image blur, referred to as a “blur indicator.” FIG. 4 is a table that shows the standard deviation of DCT values at each frequency for a non-blurred image as a result of processing a plurality of blocks. FIG. 5 is a table that shows the standard deviation of DCT coefficients at each frequency for a blurred image as a result of processing a plurality of blocks. As can be observed from a comparison of these two tables, the standard deviations of the blurred and the non-blurred images at low frequencies are approximately the same. However, as frequency increases in both the vertical and horizontal components, the standard deviation values for the blurred image fall more dramatically than those of the non-blurred image. Thus the standard deviation of DCT coefficients in a digital image file may be used effectively as a blur indicator. Other indicators that have been found to effectively estimate image blur include maximum DCT coefficients, minimum DCT coefficients, variance, and kertosis. In addition, image blur may be estimated from the sum of the standard deviations of the coefficients in an image block, graphically represented in FIG. 6 as the volume underneath the surface that represents the standard deviation of DCT coefficients as a function of the 2-dimensional (horizontal and vertical) DCT frequency components.

[0026] A blur indicator may be a single DCT coefficient (raw or modified), a set of DCT coefficients (raw or modified), or a comparison of one or more DCT coefficients to other DCT coefficients (raw or modified). IN any case, the change in the magnitude of the DCT coefficients, other than zero or nonzero, may result in a change in the blur estimation and or reduction.

[0027] It should be noted that in typical digital image formats, such as JPEG, a digital image file may contain many blocks of DCT coefficients where each block corresponds to pixel information in the spatial domain for a spatial portion of the image. Thus, with the selection of an appropriate blur indicator from one or more sets of DCT coefficients (either “raw” or statistically modified) from different spatial portions of the image, the technique permits the detection of image blur in individual regions of the image. This is a powerful tool, as many images are intended to be focused on a subject in one portion of the image, while the remainder of the image is blurred. A blur indicator that may be used to indicate whether any region in the image is not blurred is the maximum DCT coefficient in a digital image at a given frequency. With the ability to examine individual regions of an image, comprising one or more blocks of DCT coefficients for the presence of blur, such partially blurred images can be identified so they are not inadvertently modified.

[0028] FIG. 7 illustrates one example of a blur estimation and reduction technique. In this example, a two-dimensional (“2D”) histogram is constructed from the digital image file such that each DCT coefficient in the image file is associated with its corresponding frequency component, where the frequency component is two-dimensional, i.e. it indicates both the vertical and horizontal frequency value.

[0029] Each image block in the digital image file may contain 64 coefficients that correspond to the two-dimensional (8×8) DCT frequency components illustrated in FIG. 3. The two-dimensional histogram organizes each of the DCT coefficients in the image file according to the particular two-dimensional frequency component with which it is associated. Most digital image encoding schemes, such as JPEG, further modify the DCT coefficients after they are calculated from the forward DCT transform. JPEG, for example, quantizes the respective DCT coefficients in each block according to a quantization table (Q-table) and then encodes the values with a Huffman encoding scheme in order to provide more efficient compression. Accordingly, when a JPEG file is being used in this process, the Huffman coding and quantization should be removed before the two-dimensional histogram is obtained.

[0030] This 2D histogram may then be reduced to a one-dimensional (“1D”) histogram generally equivalent to a radial frequency power spectrum. The 2D histogram may be reduced to a 1D histogram according to a mapping function. FIG. 8 shows one suitable mapping function. As can be seen in FIG. 8, the 64 DCT frequency components are divided into a plurality of groups (e.g. 0 to 7) according to their position in the block. The groups may be roughly organized into concentric regions about the DC frequency component. The regions in this particular mapping function are selected because it has generally been observed that, in a given image block, each of the DCT coefficients within these regions have values close to one another. One technique to reduce the two-dimensional histogram to a one-dimensional histogram is for a plurality of the DCT coefficients corresponding to each region in a given image block to be averaged together to provide a median value. Alternatively, one value within each region may simply be selected to represent the value for that region. Essentially, this reduces the two-dimensional histogram to a one-dimensional histogram, or otherwise reduce the quantity of data, where the values 0 to 7 generally represent radially increasing frequency components.

[0031] The steps just described may be reversed. That is to say, as each image block is read from the digital image file, the mapping function shown in FIG. 8 may be used to first reduce the block to one dimension by obtaining median values for each region 0 to 7. A one-dimensional histogram may then be constructed as additional image blocks are read, reduced, and their median values categorized into their associated regions.

[0032] Preferably the selection of different sets of DCT coefficients are non-overlapping, though they may be partially overlapping, if desired. The sets preferably include different frequency components, such as a higher frequency and a lower frequency. The different frequency values readily permit a comparison of the change in magnitude as a function of the frequency.

[0033] From the one-dimensional histogram, one or more blur indicators may be obtained. A first blur indicator that may be used is the maximum DCT coefficient in region 5 (Or any other region or coefficient). The present inventor has determined that a threshold of 100 in this region for the first blur indicator is a suitable indicator for blur of an image obtained from a digital camera. By testing whether the maximum DCT coefficient is less than a threshold, it can be reliably determined whether any portion of the image is in focus. In other words, if the maximum DCT coefficient within region 5 is less than 100, the entire image will typically be blurred. Conversely, if the maximum DCT coefficient within region 5 is greater than 100, then it is likely that at least a portion of the image is in focus.

[0034] A second blur indicator that may be used is the ratio of the standard deviation of the first region to the standard deviation of the third region (or any other comparison between two or more regions). The standard deviation of DCT coefficients in blurred images tend to fall more rapidly as frequency increases than do non-blurred images. Thus a relatively high ratio indicates a blurred image, while a relatively low ratio indicates a focused image. The inventor has determined that a threshold of 5 for this blur indicator is an appropriate measure of image blur for an image from a digital camera. Because the measure of standard deviation averages information over the entire image, this blur indicator will not tend to detect isolated portions of the image that are in focus, but instead will tend to measure the overall image blur.

[0035] Though the aforementioned technique uses the maximum DCT coefficient in region 5 as a first blur indicator, and the ratio of the standard deviation of the region 1 DCT coefficient to the region 3 DCT coefficient as a second blur indicator, other techniques may use other blur indicators from other regions. Similarly, other statistical values, such as the minimum coefficient value, etc., may be used as blur indicators as well. Also, though the described technique calculates the blur indicators from a one-dimensional histogram, the blur indicators may be derived without a histogram. For example, the selected blur indicators may be the maximum region 5 coefficient and the ratio of the average region 1 coefficient to the average region 3 coefficient. In this instance, each of these blur indicators can simply be calculated and updated as data is read from the digital image file.

[0036] From the two blur indicators shown in FIG. 7, different estimates of blur may be calculated. First, if the first blur indicator is less than 100 and the second blur indicator is greater than 5 then the entire image is likely to be considerably blurred. If this condition exists then a maximum de-blur filter may be applied to enhance the image.

[0037] Second, if the first blur indicator is less than 100 and the second blur indicator is less than 5, then the entire image is likely to be marginally blurred. In this instance a medium de-blur filter may be applied to enhance the image.

[0038] Third, if the first blur indicator is greater than 100 and the second blur indicator is less than 5 but greater than 3, then the image is likely focused upon an object within the image, but the image marginally lacks sharpness. A normal sharpness enhancement filter may then be applied to enhance the image.

[0039] Fourth, if the first blur indicator is greater than 100 and the second blur indicator is greater than 5, then the image significantly lacks sharpness and a strong sharpness enhancement filter may be applied. The filters described in this paragraph are well known, and their design is straightforward to those skilled in the art. Though FIG. 7 indicates that the technique terminates after application of one of the four described filters, it is also possible to repeat the process with the corrected image to see whether further blur correction may be needed.

[0040] The terms and expressions that have been employed in the foregoing specification are used therein as terms of description and not of limitation, and there is no intention, in the use of such terms and expressions, of excluding equivalents of the features shown and described or portions thereof, it being recognized that the scope of the invention is defined and limited only by the claims that follow.