US7283666B2 - Digital image exposure correction - Google Patents

Abstract

Techniques are disclosed for correcting the exposure of a digital image. An exposure predictor may be generated based on a set of images for which ground truth data are known. After identifying an optimal set of features, the exposure of the digital image may be corrected by extracting values of the selected optimal features from the image, using the predictor to predict a desired exposure correction for the image, and correcting the exposure of the image by the predicted desired amount. Exposure correction is based on a model that relates intensity of light in the world to the RGB digits of the digital image. The model comprises a gamma function that models the response of a typical monitor and a S-shaped curve that compresses the large dynamic range of the world to the small dynamic range of the RGB digit space.

Description

BACKGROUND

1. Field of the Invention

The present invention relates to digital image processing and, more particularly, to correcting the exposure of digital images.

2. Related Art

It is essential to properly expose a digital image to obtain a good quality rendition of the original scene on an output device such as a monitor or a printer. The “exposure” of a digital image refers to the quantity of light allowed to act on the image capture sensor; exposure is a product of the intensity (controlled by the aperture and intensity of the illuminant) and the duration (controlled by the shutter speed) of light striking the sensor. Large exposure values will result in brighter images and vice versa. Relying on the original exposure set by the input device (e.g., a digital camera) usually does not yield the best quality for several reasons. For example, a wide variety of picture-taking conditions and scene compositions may make the original exposure quite variable and differ from the preferred exposure. Furthermore, input devices typically have limited dynamic range and therefore err on the side of under-exposing an image to avoid losing information in an image due to clipping. Although underexposed images may appear darker than desired, they tend to retain more information than overexposed images and therefore are amenable to post-acquisition exposure correction to make them more suitable for printing or displaying on an output device.

It is desirable that output devices be equipped to produce properly-exposed renderings from images acquired using a variety of (possibly unknown) image acquisition devices. For example, a desktop digital photo printer or a photo-vending kiosk may be capable of receiving digital images acquired using any of a wide variety of digital cameras, scanners, or other input devices under a wide variety of conditions. It is desirable that such a printer or kiosk be capable of correcting the exposure of any images it receives so that such images may be printed with optimal exposures.

What is needed, therefore, are improved techniques for correcting the exposure of digital images.

SUMMARY

Techniques are disclosed for correcting the exposure of a digital image. An exposure predictor may be generated based on a set of images for which ground truth data are known. An optimal feature set may be identified that strikes a balance between minimizing prediction error and producing good results across a wide range of images. The exposure of an image may be corrected by extracting values of the selected optimal features from the image, using the predictor to predict a desired exposure correction for the image, and correcting the exposure of the image by the predicted desired amount. To facilitate the exposure correction, we propose a model that relates intensity of light in the world to the RGB digits of the digital image. This model comprises a gamma function that models the response of a typical monitor and a S-shaped curve that allows us to compress the large dynamic range of the world to the small dynamic range of the RGB digit space. The exposure of the image may then be corrected by employing the inverse of this model to transform the image to logarithmic intensities in the world, adding or subtracting an offset (given by the desired exposure correction) from the image, and then mapping the image back to the RGB digit space using the above model. For example, in one aspect of the present invention, a method is provided for correcting the exposure of a source image. The method includes steps of: (A) transforming the source image from an image capture space into a nonlinear intensity space to produce a first transformed image; (B) correcting the exposure of the transformed image in the nonlinear intensity space to produce a corrected transformed image; and (C) transforming the corrected transformed image into the image capture space to produce a second transformed image. The step (C) may include steps of: (C)(1) transforming the corrected transformed image into a third transformed image using an S-shaped curve; and (C)(2) transforming the third transformed image into the second transformed image using a gamma function.

If i represents an intensity in the nonlinear intensity space, the step (C) may include a step of transforming the corrected transformed image into the second transformed image using the formula:
T(i)=(A+Btanh(−s(i+o)))^1/γ,
the step (A) may transform gray level g in the source image by applying the function T⁻¹(g) to the gray level to produce transformed intensities, and the step (B) may include a step of adding an exposure offset Δe to the transformed intensities to produce corrected transformed intensities.

In another aspect of the present invention, a method is provided for processing an image. The method includes steps of: (A) extracting from the image values of at least one feature selected from a set of features including: a thumbnail of the image, a luminance channel of the image, a region of interest in the image, and a subset of the image including a plurality of pixels satisfying an activity threshold; (B) predicting a desired exposure correction of the image based on the extracted feature values; and (C) correcting the exposure of the image by the predicted exposure correction to produce an exposure-corrected image. The set of features may include other features instead of or in addition to the features just listed.

The region of interest may have the following properties: (1) the average activity within the region is above a predetermined minimum activity threshold; and (2) the absolute logarithm of the ratio of the average luminance of the region to the average luminance of that portion of the image not including the region is the highest such absolute logarithm for a predetermined plurality of regions in the image. The region of interest may have a base size that is proportional to the dimensions of the image, and the dimensions of the region of interest may be proportional to the base size multiplied by a measure of average activity in the image.

In another aspect of the present invention, a method is provided for selecting a set of features for use in a system for adjusting the exposure of images. The method includes steps of: (A) placing a set of features in a master feature set M; (B) initializing a current feature set C to a null value; (C) for each feature F in the master set M, performing steps of: (1) placing the union of the current feature set C and the feature F in a temporary feature set S; (2) computing a leave-n-out error E for a plurality of images using set S as a feature set; (3) if the error E is less than a minimum error E_MIN, assigning the value of E to E_MINand recording the identity of feature F in a variable F_MIN; (D) if E_MINis less than a global error E_G, assigning the value of E_MINto E_G, adding the feature F recorded in F_MINto the set C, and deleting the feature F recorded in F_MINfrom the set M; (E) if the set M is not empty, returning to step (C); and (F) if the set M is empty or the value of E_MINis greater than the value of E_G, selecting the set C as the set of features for use in the system for adjusting the exposure of images.

Other features and advantages of various aspects and embodiments of the present invention will become apparent from the following description and from the claims.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1A is a flowchart of a method for correcting the exposure of an image according to one embodiment of the present invention;

FIG. 1B is a flowchart of a method for reducing an image according to one embodiment of the present invention;

FIG. 1C is a flowchart of a method for extracting features from an image according to one embodiment of the present invention;

FIG. 2A is a dataflow diagram illustrating operations performed by the method shown inFIG. 1A;

FIG. 2B is a dataflow diagram illustrating operations performed by the method shown inFIG. 1B;

FIGS. 2C is a dataflow diagram illustrating the operations performed by the method shown inFIG. 1C;

FIG. 3 is a flowchart of a method for identifying a region of interest in an image according to one embodiment of the present invention;

FIG. 4 is a flowchart of a method for extracting features from an image according to one embodiment of the present invention;

FIG. 5 is a flowchart of a method for generating a predictor for predicting desired image exposures according to one embodiment of the present invention;

FIG. 6 is a dataflow diagram illustrating the operations performed by the method shown inFIG. 5;

FIG. 7A is a flowchart of a method for generating ground truth data for a set of ground truth images according to one embodiment of the present invention;

FIG. 7B is a dataflow diagram illustrating the operations performed by the method ofFIG. 7A according to one embodiment of the present invention;

FIG. 7C is a dataflow diagram illustrating the generation of ground truth data for an image in a ground truth set of images according to one embodiment of the present invention;

FIG. 7D is a dataflow diagram illustrating the computation of a prediction error for a test set image according to one embodiment of the present invention;

FIG. 7E is a dataflow diagram illustrating the computation of an average prediction error for a plurality of images in a ground truth image set according to one embodiment of the present invention;

FIG. 8 is a flowchart of a method for computing the average prediction error for a plurality of images in a ground truth image set according to one embodiment of the present invention;

FIG. 9 is a flowchart of a method for selecting an optimal number and combination of features for use in exposure correction according to one embodiment of the present invention;

FIG. 10 is a graph illustrating a family of exposure adjustment curves for use in exposure correction according to one embodiment of the present invention;

FIG. 11 is a flowchart of a method for applying an exposure correction to an image to produce an exposure-corrected image according to one embodiment of the present invention; and

FIG. 12 is a flowchart of a method in which color mapping and exposure correction are integrated according to one embodiment of the present invention.

DETAILED DESCRIPTION

In general, the exposure correction algorithm disclosed herein may be divided into two parts. The first part extracts, from the input image, the values of a set of features that contain the information that is most relevant to the exposure of the image. The second part finds a predictor that operates on the extracted features to generate a predicted exposure correction to apply to the image. The predicted exposure correction is applied to the image to produce an exposure-corrected image. The predictor may, for example, be a linear predictor that is chosen so that the error between the predicted exposure and desired exposure of images is minimized in a least square sense. Since the theory for generating the best linear predictor is well known in the statistical and signal processing arts, the disclosure herein will emphasize techniques both for identifying good features that correlate very well with the desired exposure and for determining an optimal feature set that yields the best linear predictor given the ground truth data.

Referring toFIG. 1A, a flowchart is shown of amethod100 for correcting the exposure of an image according to one embodiment of the present invention. Referring toFIG. 2A, a dataflow diagram200 is shown which illustrates the operations performed by themethod100 shown inFIG. 1A.

Themethod100 operates on an input image202 (FIG. 2A), which may be received from any of a variety of sources such as a digital camera or scanner. Theinput image202 may be represented in any of a variety of formats for representing digital images, such as the JPEG format.

Themethod100 extracts from theimage202 the values208 of a set of selected features218 (step106). The selected features218 may, for example, be identifiers or other descriptors which identify the particular features to be extracted instep106. Examples of features that may be extracted instep106, and examples of techniques for extracting them, will be described below with respect toFIG. 1B,FIG. 1C,FIG. 2C,FIG. 3, andFIG. 4. Techniques that may be used to select the set offeatures218 will be described below with respect toFIG. 9.

Themethod100 generates apredictor216 based onground truth data210 for a set of ground truth images (step108). Note thatstep108 need not be performed each time themethod100 is performed. Rather, thepredictor216 may be generated once, prior to execution of themethod100. The generatedpredictor216 may then be used each time themethod100 is performed, without the need to performstep108. Techniques that may be used to generate thepredictor216 will be described below with respect toFIGS. 5-9. Themethod100 uses thepredictor216 to generate a predicted exposure offset212 based on the extracted feature values208 (step110).

Themethod100 corrects the exposure of theinput image202 by shifting the exposure of theinput image202 by the predicted exposure offset212, thereby producing an exposure-corrected image214 (step112). Techniques that may be used to perform the exposure correction will be described below with respect toFIG. 11.

Various techniques may optionally be applied to improve the contrast of theimage202. For example, the range of intensities in theimage202 may be stretched to cover the range of available intensities (e.g., [0,255]) as follows. The red channel R of theinput image202 may be linearized, thereby producing a linearized red channel R_L, using the formula R_L=(R/255)^γ. Linearized green and blue channels G_Land B_Lmay be produced similarly. Applying the gamma function to theRGB space image202 transforms it to a linear intensity space that more closely reflects the original dynamic range of theimage202. The term “RGB space” as used herein refers to any space in which an image may be captured (referred to herein as an “image capture space”).

A minimum intensity value mn and a maximum intensity value mx for theimage202 may be obtained using the following formulas: mn=min(R_L,G_L,B_L) and mx=max(R_L,G_L,B_L). The linearized red channel R_Lmay be stretched to produce a stretched linearized red channel R_L′ using the formula R_L′=(R_L−mn)/(mx−mn). Stretched linearized green and blue channels G_L′ and B_L′ may be produced similarly. Subsequent operations (such as feature extraction) described below may be performed on the channels R_L′, G_L′, and B_L′.

The channel R_L′ may be transformed back into the channel R′ using the formula R=255(R_L′)^1/γ. The channels G′ and B′ may be obtained from the channels G_L′ and B_L′ in a similar manner. In the following description, operations that are described as being performed on channels R_L, G_L, and B_Lor R, G, and B may alternatively be performed on channels R_L′, G_L′, and B_L′ or R′, G′, and B′.

The present invention may be used in conjunction with any individual features and with any combination of features. Examples of techniques that may be used to select an optimal set of features for extraction, from among an initial set of features, will be described below with respect toFIG. 9. Once a particular set of features is selected using such techniques, values208 of the selected features218 may be extracted from the image202 (step106). Particular examples of features that may be used in conjunction with embodiments of the present invention, and techniques for extracting values of such features, will now be described.

In one embodiment of the present invention, the size of theinput image202 is reduced as a part of feature extraction. Theinput image202 may be reduced because, in general, any particular image may carry a significant amount of information that is irrelevant to its desired exposure. For example, the chrominance channels of a color image are independent of the exposure of the image and therefore do not yield any information regarding the desired exposure. Such extraneous information may be discarded both to reduce the computational complexity of the exposure correction techniques described herein and to accurately estimate the coefficients526 (FIG. 6) of thepredictor216, as described in more detail below. Failure to exclude such extraneous information may decrease the accuracy of coefficient estimation because, in practice, there is only a limited training image set for which the desired exposure (ground truth) is known. This tends to bias the estimation of thepredictor coefficients526 when the number of images in the training set716 (FIG. 7D) cannot adequately support the number of selected features in the feature set208. Determining the optimal number of features is an important and difficult problem, and will be described in more detail below with respect toFIG. 9.

Referring toFIG. 1B, a flowchart is shown of a method that may be used to reduce theimage202 according to one embodiment of the present invention. Referring toFIG. 2B, a dataflow diagram220 is shown which illustrates the operations performed by themethod102 shown inFIG. 1B. Themethod102 generates a thumbnail222 of the input image202 (step122). In general, a thumbnail of an image is a reduced-dimension version of the image that is produced by some form of downsampling. Techniques for producing thumbnails are well-known to those of ordinary skill in the art.

In one embodiment of the present invention, it is assumed that most of the exposure information in theinput image202 is contained in the luminance channel of theimage202. Themethod102 therefore extracts a linear luminance channel224 (step124) and a non-linear luminance channel226 (step126) from the thumbnail222 so that subsequent processing is performed only on thelinear luminance channel224 and thenon-linear luminance channel226. If, for example, the R, G, and B channels of theinput image202 have been linearized into channels R_L, G_L, and B_L, respectively, thelinear luminance channel224 andnon-linear luminance channel226 may be produced as follows. The linearizedluminance channel224, represented by L_L, may be produced using the formula L_L=aR_L+bG_L+cB_L, where a, b, and c are constants. Thenon-linear luminance channel226, represented by L, may be produced from the linearized luminance channel224 L_Lby the following formula:
L=255(L_L)^1/γ.

Referring toFIG. 1C, a flowchart is shown of a method that may be used to extract additional features from theinput image202 according to one embodiment of the present invention. Referring toFIG. 2C, a dataflow diagram240 is shown which illustrates the operations performed by themethod140 shown inFIG. 1C. Theinput image202 is reduced to produce thelinear luminance channel224 and thenon-linear luminance channel226 using the techniques described above with respect toFIGS. 1B and 2B (step102).

A subset of thenon-linear luminance channel226 may be isolated to improve the performance of thepredictor216. A subset of thenon-linear luminance channel226, for example, rather than the entirenon-linear luminance channel226, may be used for exposure correction based on the observation that, in the typical case, all parts of an image do not equally influence our subjective judgment of the image's preferred exposure. For example, the desired exposure of an image with a subject standing in front of flat texture-less wall will most likely not be determined by the luminance values of the wall. The performance of thepredictor216 may therefore be improved by not using the wall pixels to compute the histogram described below. Although the factors that influence exposure are highly subjective, we have found that objects with little or no “activity” typically do not influence exposure. Thenon-linear luminance channel226 may therefore first be screened for activity to produce anactive image map206 which identifies the locations of pixels in thenon-linear luminance channel226 that satisfy the activity threshold (step104).

An activenon-linear luminance image209 may be extracted207 from thenon-linear luminance channel226 based on theactive image map206. Theactive image209 may also be referred to as the “active luminance channel” in embodiments which operate only upon thenon-linear luminance channel226 of theinput image202. Techniques that may be used to measure activity are described in more detail in commonly-owned U.S. Pat. No. 5,724,456 to Boyack et al., entitled “Brightness Adjustment of Images Using Digital Scene Analysis,” issued on Mar. 3, 1998 and incorporated by reference herein.

Themethod140 generates a histogram244 (referred to as the “active histogram,” or as the “active luminance histogram” (ALH) in embodiments in which only the luminance channel is being used) based on the active image209 (step130). Theactive histogram244 is one example of a feature whose value may be extracted instep106.

Using the entireactive histogram244 as a feature, however, may be inadequate to deal with images that are shot outdoors with the subject against a brightly lit background or with images that are shot indoors using the camera flash. Such images are distinguished by the fact that the exposures of the subject and background differ significantly from each other. If the subject occupies a small fraction of the image and there is sufficient activity in the background, an exposure predictor generated using the entireactive histogram244 will favor the background, thereby underexposing the subject in the outdoor case and overexposing the subject in the indoor case.

To address this problem, we introduce the concept of a region of interest (ROT): an area of the reduced image204 that is most likely to determine the exposure of theoriginal input image202. Themethod140 may identify a region ofinterest242 using thelinear luminance channel224 and the active image map206 (step132). Themethod140 may then generate a histogram246 of the portion of theactive image209 that is within the identified region of interest242 (step134). Both theactive histogram244 and the ROI histogram246 are examples of features that may be extracted instep106.

Themethod140 may also generate an average histogram248 by taking the weighted average of the ROT histogram246 and the active histogram244 (step136). The average histogram is another example of a feature that may be extracted instep106. Techniques for generating the average histogram248 will be described below with respect toFIG. 4.

Examples of techniques will now be described for using a variable-size rectangular window to search for and identify theROI242 of the thumbnail image222 (step132). In one embodiment of the present invention, theROT242 is defined as a rectangular window that satisfies the following conditions:

• (1) the average activity within the ROT242 (defined as the ratio of the number of active pixels in the ROT to the total number of pixels in the ROI) is above a specified minimum activity threshold A_MIN; and
  • (2) the absolute logarithm of the ratio of the average linear luminance within the ROI to the average linear luminance of the remaining image (i.e., the portion of the linearizedluminance channel224 not including the ROI242) is the highest in the thumbnail image222.

In this embodiment, the average luminance is computed over all the pixels in the linearizedluminance channel224 and not just the pixels in theactive image206.

Condition (1) ensures that theROI242 encompasses some interesting content of the thumbnail image222. Condition (2) serves to identify the subject in in-door flash scenes and out-door backlit scenes. For scenes in which there are no significant differences in luminance between any one portion of the linearizedluminance channel224 as compared to the rest of the linearizedluminance channel224, theROI242 encompasses an arbitrary region of theluminance channel226 satisfying both condition (1) and (2). However, in this case theROI242 will not have any significant contribution to the exposure of the final exposure-correctedimage214, a property that will become clear from the description below.

Referring toFIG. 3, a flowchart is shown of techniques that may be used to identify the region of interest242 (step132). First, the dimensions D_R(e.g., width and height) of the region ofinterest242 are selected. The aspect ratio of the region ofinterest242 may be the same as the aspect ratio of the thumbnail222, and the base dimensions of the region ofinterest242 may be equal to a fixed fraction of the dimensions of the thumbnail222. For example, if D_Irepresents the dimensions of the thumbnail222 (step302) and F is a predetermined fractional multiplier (step304), the base size B_Rof the region ofinterest242 may be set equal to F*D_I(step306).

The actual dimensions D_Rof the region ofinterest242 scale linearly from the base dimensions B_Rwith the average activity of thenon-linear luminance channel226. In other words, if A_Iis the average activity of the entire active image map206 (step308), then the dimensions D_Rof the region ofinterest242 are equal to B_R*A_I(step310). Intuitively, an image with sparse activity will tend to have a small region of interest and vice versa. The scaling property represented bystep310 also helps the region ofinterest242 to pass condition (1).

Having selected the dimensions D_Rof the region ofinterest242, a region that satisfies both conditions (1) and (2), stated above, may be selected as the region ofinterest242. Referring again toFIG. 3, the region ofinterest242 may be selected as follows.

A variable LOG_MAXis initialized to zero and a variable r_ROIis initialized to one (step312). The meaning of the values of LOG_MAXand r_ROIwill become clear below. Themethod132 sets the value of a variable ROI_found to FALSE (step313). As its name implies, ROI_found indicates whether themethod132 has yet found a region of interest.

Themethod132 enters a loop over each candidate region C in the thumbnail222 (step314). The average activity A_Cof the region C is calculated (step316). Themethod132 determines whether A_C≧A_MIN(step318), thereby determining whether condition (1) is satisfied. If A_C<A_MIN, themethod132 continues to the next region (step334).

If A_C≧A_MIN, themethod132 calculates the average luminance L_Cof region C of the linear luminance channel224 (step322) and the average linear luminance L_Iof the remainder of the linear luminance channel224 (i.e., of the portion of thelinear luminance channel224 not including region C) (step324). The ratio of L_Cto L_Iis assigned to the variable r_ROI, and the absolute logarithm of r_ROI(i.e., |log₂L_C/L_I|) is calculated and assigned to a variable named LOG_CUR(step326).

Themethod132 determines whether the value of LOG_CURis greater than the value of LOG_MAX(step328). In other words, themethod132 determines whether the absolute log of the ratio of the average luminance in region C to the average luminance of the remainder of thelinear luminance channel224 is the highest encountered so far in thelinear luminance channel224. If LOG_CURis greater than LOG_MAX, a variable ROI is assigned the value of C (step330) and the variable LOG_MAXis assigned the value of LOG_CUR(step332). Because a region of interest has been found, the value of ROI_found is set to TRUE (step333). Steps316-333 are repeated for the remaining regions C in the thumbnail222 (step334).

Upon completion of the loop, themethod132 determines whether the value of ROI_found is equal to TRUE (step336). If it is, themethod132 terminates. Otherwise, a region of interest has not been found, and themethod132 sets the variable ROI to encompass the entire input image202 (step338).

Upon completion of themethod132, the value of the variable ROI identifies a region in theimage202 that satisfies both conditions (1) and (2), if such a region exists, and that may therefore be used as the region ofinterest242.

Referring toFIG. 4, a flowchart is shown of a method that may be used to extract additional features from the active ROI histogram246 and theactive histogram244. By way of background, associated with the region ofinterest242 may be a likelihood number that denotes the probability that the region ofinterest242 influences the desired exposure of theimage202. Let r_ROIbe the ratio of the average ROI linear luminance to the average linear luminance of the remaining image (i.e., L_C/L_I, where C=ROI). Then the likelihood associated with the region ofinterest242 is given by Equation 1 (FIG. 4, step402):

$\begin{array}{cc}p\left(\mathrm{ROI}\right)=\frac{1}{1+\exp \left(-s\left({\log }_2{r}_{\mathrm{ROI}}-o\right)\right)},& \mathrm{Equation}1\end{array}$

where s and o are adjustable parameters. The parameter o represents the luminance difference in stops between the region ofinterest242 and the remaining image when the likelihood associated with the region ofinterest242 is 0.5. The parameter s is proportional to the slope of the likelihood function at |log₂r_ROI|=o. Since p(ROI)→1.0 as |log₂r_ROI|→∞, it follows that a large difference between the average linear luminance of the region ofinterest242 and the rest of thelinear luminance channel224 implies a higher likelihood of the region ofinterest242 influencing the final exposure of theimage202 and vice versa. Techniques will now be described for determining how the ROI likelihood p(ROI) weights the ROI contribution towards the final vector of feature values208.

Let H_ROI(•)denote the active ROI luminance histogram246 (FIG. 4, step404). Let H_I(•) denote the active luminance histogram244 (step406). Then the overall average histogram H(•)248 is given by Equation 2 (step408):
H(•)=(1−p(ROI))H_I(•)+p(ROI)H_ROI(•)  Equation 2

The histogram H(•)248 is an example of a feature that may be extracted instep106. However, the dimensionality of the feature space may be further reduced by extracting several linear and non-linear features from the histogram H(•)248 (steps410 and412). Such features are examples of features that may be extracted instep106. Examples of non-linear features that may be extracted include the different percentiles of the histogram H(•)248. Examples of linear features that may be extracted include the different moments of the histogram H(•)248.

As mentioned above, thepredictor216 may be generated (step108) based onground truth data210 for the set ofground truth images522. In one embodiment of the present invention, thepredictor216 is a linear predictor.

Let N be total number of feature values208 and let f_idenote the i^thfeature value in the feature values vector208. Let x_idenote the coefficients526 (FIG. 6) of thepredictor216. Then the exposure shift prediction Δê212 may be generated instep110 as shown in Equation 3:

$\begin{array}{cc}\Delta \hat{e}=\sum _{i=0}^{N-1}{x}_i{f}_i=x^{T}f,& \mathrm{Equation}3\end{array}$
where f is the feature value vector208 and x is thecoefficient vector526.

Referring toFIG. 5, a flowchart is shown of a method500 for generating the predictor216 (step108) according to one embodiment of the present invention. Referring toFIG. 6, a dataflow diagram520 is shown illustrating the operations performed by themethod108 shown inFIG. 5. Themethod108 obtainsground truth data210 for all images in a set of ground truth images522 (step502). Examples of techniques for obtaining theground truth data210 will be described below with respect toFIG. 7B. Themethod108 selects the optimal set offeatures218 based on the ground truth data210 (step504). Examples of techniques for selecting the feature set218 will be described below with respect toFIG. 9. Themethod108 computescoefficients526 for thepredictor216 based on theground truth data210 and the selected features218 (step506). Referring toFIG. 6, step506 may be performed, for example, by extracting532 a set of training features534 from a set oftraining images528 based on the selected features218, and by generating the predictor coefficients (step506) based on theground truth data210 and the training features534. The training set528 may be any set of images that is used to train thepredictor216 and is a subset of the ground truth set522. Themethod108 generates thepredictor216 based on the selected features218 and the selected coefficients526 (step508).

Themethod108 shown inFIG. 5 will now be described in more detail. Referring toFIG. 7A, a flowchart is shown of amethod700 that may be used to generate the ground truth data210 (FIG. 5, step502). Referring toFIG. 7B, a dataflow diagram750 is shown which illustrates the operations performed by themethod700 shown inFIG. 7A.

Theground truth data210 may be acquired by conducting a psychophysical scaling test in which human subjects are asked to determine the best exposure for each of theimages522a-din the ground truth set522. Although only fourimages522a-dare shown inFIG. 7B, in practice there may be a much larger number of ground truth images.

Themethod700 may enter a loop over each image I in the ground truth set210 (step702). Referring toFIG. 7C, a dataflow diagram720 is shown illustrating, by way of example, the generation ofground truth data736afor asingle image522ain the ground truth set522. For each human subject S in a plurality of human subjects722a-d(step704), themethod700 receives an indication from the subject of the desired exposure for image I (step706). For example, referring toFIG. 10, agraph1000 is shown of a family of exposure adjustment curves, the particular characteristics of which are described in more detail below. Each such curve may be applied to an image to perform a particular exposure correction on the image.

In one embodiment of the present invention, each of the exposure adjustment curves shown in thegraph1000 is applied to the image I, and the resulting exposure adjusted images are displayed to the subject S. Associated with each of the exposure adjustment curves is a single number Δe_ireflecting the particular exposure adjustment associated with the curve. The subject S selects a particular one of the exposure-adjusted images that the subject believes has the best exposure among all of the exposure adjusted images. The exposure correction Δe_iassociated with the exposure adjustment curve corresponding to the image selected by the subject S is provided as the desired exposure indication instep706.

For example, as shown inFIG. 7C, subject722aindicates desiredexposure724aby selecting a particular one of the exposure-adjusted images as having the best exposure. Themethod700 similarly receives desired exposure indications from the remaining subjects (step708). For example, as shown inFIG. 7C, subject722bindicates desiredexposure724b,subject722cindicates desiredexposure724c,and subject722dindicates desiredexposure724d.

Themethod700 averages all of the exposure indications received in the loop in steps704-708 to produce a single exposure correction number Δe, referred to as the “ground truth data” for image I (step710). For example, as shown inFIG. 7C,ground truth data736ais produced forimage522a.The inverse of the variance of the desired exposures724a-dindicated by the subjects722a-dmay be used to weight the mean-square error in the design of thepredictor216. This allows the influence of any image in the determination of the prediction weights to be reduced when the subjects differed significantly in their opinions regarding the best exposure of image I.

Themethod700 generates ground truth data for the remaining images in the ground truth set522 using the same techniques (step712). For example, as shown inFIG. 7B,ground truth data736bmay be generated for training setimage522b,ground truth data736cmay be generated for ground truth setimage522c,andground truth data736dmay be generated for ground truth setimage522d.

Before describing how feature selection (step504) may be performed, techniques will be described for generating thepredictor coefficients526 given a particular set of features. For example, let e denote the column vector containing theground truth data210 for all of theimages522a-din the ground truth set522. Let the feature vectors of each of theimages522a-dof the ground truth set522 form the rows of a matrix F. Then the predictor coefficients x526 may be generated (step506) using Equation 4:
x=(F^TF)⁻¹F^Te.  Equation 4

Alternatively, if W is a diagonal weight matrix computed using the inverse variance of theground truth data210, the coefficients x526 may be generated (step506) using Equation 5:
x=(F^TWF)⁻¹F^TWe.  Equation 5

In either case, once the number and type of features are determined (FIG. 9), the coefficients x526 may be generated using the closed form expressions in Equation 4 or Equation 5. The remaining problem is to determine which features to select as the selected features218.

Examples of techniques will now be described for determining which and how many features are optimal for inclusion in the set of selected features218. In one embodiment of the present invention, the set ofground truth images522 is divided into two subsets: a training set (such as training set716 shown inFIG. 7D) and a test set (not shown). The training set is used to design a training predictor726 (FIG. 7D). The test set is used to test thepredictor726 and to compute the prediction error.

In practice, the number of ground truth images in the ground truth set522 is limited. Dividing the images in the ground truth set522 into subsets further limits the number of design or test samples, thereby potentially reducing the quality of thepredictor216. Referring toFIG. 8, a flowchart is shown of amethod800 that may be used to address this problem.

In general, themethod800 uses a leave-n-out approach which cycles through the entire ground truth image set522, n images at a time. In theparticular method800 shown inFIG. 8, n=1. In each cycle, only one image from the ground truth set522 is chosen for the test set and the rest of the images from the ground truth set522 are used to design thepredictor726. The prediction error is then computed on the single image in the test set. The entire procedure is repeated for the next image in the ground truth set522 and so on. The advantage of this method is that all images but one are used to design thepredictor726 and all images are used to test thepredictor726. This minimizes the bias in the design and test error of thepredictor726. However, the downside of this procedure is that the design procedure has to be repeated as many times as the number of images in the ground truth set522.

The procedure described generally above will now be described in more detail. Referring toFIG. 8, a loop is entered over each image I in the ground truth image set G522 (step802). The single image I is placed into the test set (step804), and all of theground truth images522a-dexcept for image I are placed into the training set (step806).

Referring toFIG. 7D, a dataflow diagram760 is shown which illustrates the calculation of aprediction error766aby themethod800 based on the test set image I762 and thecurrent training set716. Themethod800 generatestraining predictor coefficients744 based on the training set (step808) using, for example, Equation 4 or Equation 5. In particular, themethod800 may extract718features728 from the training set716 based on a current set offeatures734. Themethod800 may generatetraining coefficients744 based onground truth data770 for the training set716 and the extracted training set features728.

Themethod800 generates atraining predictor726 based on the current set offeature identifiers734 and the training predictor coefficients744 (based on the structure of Equation 3)(step810). The current set offeatures734 may be selected as described below with respect toFIG. 9.

Themethod800 extracts the current selected features734 from the test set image I762-to produce test set image features746 (step812). Themethod800 uses thetraining predictor726 to generate a predictedexposure shift768 for the test setimage762 based on the extracted features746 using Equation 3 (step814). Themethod800 calculates aprediction error E_I766afor the test setimage762 by subtracting the predictedexposure shift768 from theground truth data764 for the test set image I762 (step816). Prediction errors are generated in the same manner for the remaining images in the ground truth set G522 (step818).

Referring toFIG. 7E, for example, a dataflow diagram754 is shown illustrating the generation of a plurality ofprediction errors766, one for each of theimages522a-din the ground truth set522. As each of theground truth images522a-dis used as the test setimage762, a corresponding prediction error is generated. For example,prediction error766ais generated forimage522a,prediction error766bis generated forimage522b,prediction error766cis generated forimage522c, andprediction error766dis generated forimage522d. Onceprediction errors E_I766a-dare generated for each image in the ground truth set522, the root mean square (RMS) is taken of all of theprediction errors E_I766a-dto produce an averageprediction error E758 for the ground truth set522 (step820). The averageprediction error E758 may be used to select an optimal number and combination of features for use as the selected features218, as will now be described in more detail.

Referring toFIG. 9, a flowchart is shown of amethod900 that may be used to select an optimal number and combination of features for use as the selected features218. All available features are placed into a master feature set M (step902). The master set of features may be selected in any manner. Examples of features that may be placed into the master feature set M include the ROI histogram246, theactive histogram244, the average histogram248, and linear and non-linear features extracted from the features just listed. A current feature set C is initialized to a null set (step904), a global error value E_Gis initialized to infinity (step906), and a minimum error value E_MINis initialized to infinity (step908).

A loop is entered over each feature F in the master set M (step910). A set S is formed by adding the feature F to the current feature set C (step912). Themethod800 shown inFIG. 8 is used to compute an average leave-n-out error E for theimages522a-din the ground truth image set522 using set S as the set of current selected features734 (step800).

If the average error E is less than the minimum error E_MIN(step914), the minimum error E_MINis assigned the value of E (step916) and a variable F_MINis assigned the value of F (the current feature) (step918). The loop initiated instep910 is repeated for each of the features F in the current set C (step920).

Upon completion of the loop performed in steps910-920, E_MINcontains the minimum leave-n-out prediction error obtained in any iteration of the loop, and F_MINindicates the feature that resulted in the minimum error E_MIN. Themethod900 determines whether the minimum error E_MINis greater than the global error E_G(step922). If E_MIN>E_G, the current feature set C is provided as the set of selected features218. If E_MIN≦E_G, then E_Gis assigned the value of E_MIN(step924), and the feature F_MINis added to the current feature set C and removed from the master set M (step926).

Themethod900 determines whether the master set M is empty (step928). If the master set M is not empty, the procedure described above with respect to steps910-926 is performed again using the updated master set M and current set C. If the master set M is empty, the current feature set C is provided as the set of selected features218.

In summary, themethod900 identifies the single best feature that results in the minimum average prediction error in the first iteration of the loop initiated instep910. In the second iteration of the loop, themethod900 identifies the next best feature that in combination with the first feature achieves the minimum error. Themethod900 continues in this fashion until the minimum average prediction error E_MINeventually starts to increase with the addition of more features. At this point themethod900 terminates. The features that are in the current set C upon termination of themethod900 represent a set of optimal features that may be provided as the selected features218.

As described above with respect toFIG. 5 andFIG. 6, once the selected features218 are selected (FIG. 9), thepredictor coefficients526 may be generated based on theground truth data210 andfeature identifiers218 using, for example, Equation 4 or Equation 5 (step506), and thepredictor216 may be generated based on thefeatures218 and thecoefficients526 using, for example, the structure of Equation 3 (step508).

Note that if the entire ground truth set522 were used to design and test thepredictor216, the minimum error E_MINwould always decrease upon the addition of a new feature to the current set C. In fact, if there are m images in the ground truth set522, the minimum error E_MINbe made to be exactly zero by choosing m independent features. This follows from the fact that the column space of F spans the ground truth vector e. In such a case, the predictor that is generated may not be optimal. Rather, the predictor that is generated may merely predict the m images in the ground truth set522 perfectly, while the performance for other images may not be specified. In practice, a predictor designed in this fashion may perform poorly in the field because it may not generalize its prediction well enough for images outside the ground truth set. By testing with a set that is independent of the training set, we ensure that only those features that generalize well for other images are included in the final feature set218 and features that just fit the noise are excluded.

Having described how to generate thepredictor216, techniques will now be disclosed for changing (correcting) the exposure of theimage202 to the desired value (step112). An algorithm that causes an exposure change should not alter the color balance of the image in the process. This may be achieved by operating solely on the luminance channel of the image in a luminance/chrominance space. Alternatively, if the exposure correction algorithm operates in the RGB space, the same transformation should be applied to all of the channels so as not to alter the color balance of the image. Techniques using the latter approach will now be described because it is desirable to transform the image such that at least one of its channels occupies the entire gray scale, and it is particularly easy to do this in the RGB space.

Once thepredictor216 is generated, the predicted exposure offset212 for theimage202 may be generated based on the extracted feature values208 using Equation 3 (step110). Referring toFIG. 11, a flowchart is shown of a method for applying the exposure offset212 to theinput image202 to produce the exposure-corrected image214 (step112) according to one embodiment of the present invention. Themethod112 transforms theinput image202 from RGB space back to intensities in the original scene (i.e., the world intensity space) (step1102). Themethod112 performs exposure correction on the transformed image (step1104). The method1100 transforms the exposure-corrected image back from world intensity space to RGB space to produce the exposure-corrected image214 (step1106).

In one embodiment of the present invention, the forward transformation from the world log intensity space to the RGB space (step1106) is modeled by an S-shaped curve that serves to compress the tones in the highlight and the shadow regions. This is followed by a gamma function designed to model the inverse response of a typical monitor. The combination of the S-shaped tone reproduction curve and gamma forms a complete forward transformation represented herein as T(•).

Let i denote the world log intensity. Then T(i) is defined by Equation 6:
T(i)=(A+Btanh(−s(i+o)))^1/γ,   Equation 6
where A, B, s and o are parameters of the S-shaped tone reproduction curve and γ is the monitor gamma. It should be appreciated that the parameters s and o in Equation 6 are not the same as the parameters s and o inEquation 1.

The reverse transformation from RGB space to log world intensity space (step1102) for a particular gray level g in RGB space may therefore be represented as T⁻¹(g). The exposure correction of gray level g by a desired exposure offset Δe (measured in stops) in world intensity space (steps1102 and1104) may therefore be represented by T⁻¹(g)+Δe. The complete exposure correction of an RGB-space gray level g, including reverse and forward transformations, performed by the exposure correction method1100 illustrated inFIG. 11, may therefore be represented by Equation 7:
g′=T(T⁻¹(g)+Δe),   Equation 7
where g′ is the exposure-corrected gray level in RGB space. Thegraph1000 inFIG. 10 illustrates a family of curves, each of which corresponds to a different value of Δe.

Once the predicted exposure offset Δe212 is generated, the result of Equation 7 may be calculated for all gray levels, and pairs of gray levels and corresponding corrected gray levels may be stored in a lookup table (LUT). Exposure correction may thereafter be performed on each channel of an image using the lookup table rather than by calculating the results of Equation 7 for each pixel or gray level in the image, thereby significantly increasing the speed with which exposure correction may be performed.

One advantage of the techniques just described is that they perform exposure correction based on a model that models a mapping from world intensity space to the intensity space (e.g., RGB space) of the capturedimage202. As described above, the model includes a gamma function that models the response of a typical monitor and an S-shaped curve that compresses the large dynamic range of the world to the small dynamic range of the image capture (e.g., RGB) space. Using such a model enables the exposure of theimage202 to be corrected by employing the inverse of the model to transform the image to logarithmic intensities in the world, adding or subtracting an offset (given by the desired exposure correction) from the image, and then mapping the image back to the RGB digit space using the above model. One advantage of using such a model is that it enables exposure corrections to be applied in the world intensity space, where such corrections are more likely to have their intended effect across the full range of intensities, assuming that the model reasonably reflects the transfer function that was used to capture theimage202.

Embodiments of the present invention may be integrated with the color mapping process that is typically performed on digital images when output to a rendering device such as a printer. For example, referring toFIG. 12, a flowchart is shown of amethod1200 in which color mapping and exposure correction are integrated according to one embodiment of the present invention. Themethod1200 receives an image from a source such as a digital camera (step1202) and performs JPEG decompression on the image (step1204). Themethod1200 reduces the image using the techniques described above with respect toFIGS. 1B and 2B (step102). Themethod1200 then performs automatic color balancing and automatic exposure correction on the image using an integrated process. Color balancing, for example, is often performed in the RGB space using three one-dimensional lookup tables. Such lookup tables may be combined with the exposure correction lookup tables described above to generate three one-dimensional lookup tables that perform both color balancing and exposure correction with a single set of one-dimensional lookups.

For example, exposure correction estimation may be performed (step1218) using the techniques disclosed herein to generate three one-dimensional exposure correction lookup tables (step1219). Three one-dimensional color-balancing lookup tables may also be computed (step1220) and combined with the exposure correction lookup tables generated in step1219 (step1222). Themethod1200 may perform any of a variety of image processing steps on the decompressed image, such as rotating the image (step1206) and sharpening the image (step1208). These particular image processing steps are shown merely for purposes of example and do not constitute limitations of the present invention.

Themethod1200 performs color mapping on the image (step1210). Color mapping often involves several operations, including a one-dimensional pre-lookup table, a three-dimensional matrix or three-dimensional lookup, and a one-dimensional post-lookup table. Exposure correction may be integrated into the one-dimensional pre-lookup table operation of color mapping using the single set of three one-dimensional lookup tables (generated in step1222) that perform the combined function of exposure correction, color balance, and the one-dimensional pre-lookup table portion of color mapping.

The method prepares the image for printing (or other output) by upsizing the image (step1214). Themethod1200 then prints the image (step1216). It should be appreciated that various steps in the method1200 (such assteps1204,1206,1208,1214, and1216) are provided merely as examples of steps that may be performed in conjunction with processing of theinput image202 and do not constitute limitations of the present invention.

One advantage of the techniques disclosed herein is that they may operate in the RGB space, thereby making them susceptible to being integrated with color mapping as just described. Integrating exposure correction with color mapping reduces the number of steps that are required to optimize an image for printing and may therefore make it possible to perform such processing more quickly than other methods which correct image exposure in a luminance-chrominance space or other non-linear space.

It is to be understood that although the invention has been described above in terms of particular embodiments, the foregoing embodiments are provided as illustrative only, and do not limit or define the scope of the invention. Various other embodiments, including but not limited to the following, are also within the scope of the claims.

Elements and components described herein may be further divided into additional components or joined together to form fewer components for performing the same functions.

The techniques described above may be implemented, for example, in hardware, software, firmware, or any combination thereof. The techniques described above may be implemented in one or more computer programs executing on a programmable computer including a processor, a storage medium readable by the processor (including, for example, volatile and non-volatile memory and/or storage elements), at least one input device, and at least one output device. Program code may be applied to input entered using the input device to perform the functions described and to generate output. The output may be provided to one or more output devices.

Each computer program within the scope of the claims below may be implemented in any programming language, such as assembly language, machine language, a high-level procedural programming language, or an object-oriented programming language. The programming language may, for example, be a compiled or interpreted programming language.

Each such computer program may be implemented in a computer program product tangibly embodied in a machine-readable storage device for execution by a computer processor. Method steps of the invention may be performed by a computer processor executing a program tangibly embodied on a computer-readable medium to perform functions of the invention by operating on input and generating output. Suitable processors include, by way of example, both general and special purpose microprocessors. Generally, the processor receives instructions and data from a read-only memory and/or a random access memory. Storage devices suitable for tangibly embodying computer program instructions include, for example, all forms of non-volatile memory, such as semiconductor memory devices, including EPROM, EEPROM, and flash memory devices; magnetic disks such as internal hard disks and removable disks; magneto-optical disks; and CD-ROMs. Any of the foregoing may be supplemented by, or incorporated in, specially-designed ASICs (application-specific integrated circuits). A computer can generally also receive programs and data from a storage medium such as an internal disk (not shown) or a removable disk. These elements will also be found in a conventional desktop or workstation computer as well as other computers suitable for executing computer programs implementing the methods described herein, which may be used in conjunction with any digital print engine or marking engine, display monitor, or other raster output device capable of producing color or gray scale pixels on paper, film, display screen, or other output medium.

Claims (11)

What is claimed is:

1. A method for correcting the exposure of a source image, the method comprising steps of:

(A) transforming the source image from an image capture space into a nonlinear intensity space to produce a first transformed image;

(B) correcting the exposure of the transformed image in the nonlinear intensity space to produce a corrected transformed image; and

(C) transforming the corrected transformed image back into the image capture space to produce a second transformed image by steps comprising:

(C)(1) transforming the corrected transformed image into a third transformed image using an S-shaped curve; and

(C)(2) transforming the third transformed image into the second transformed image using a gamma functions;

wherein the step (C) comprises a step of transforming the corrected transformed image into the second transformed image using the formula:

T(i)=(A+Btanh(−s(+o)))^1/γ

wherein i represents an intensity in the nonlinear intensity space, wherein A, B. s and o are parameters of said S-shaped curve and wherein γ is a gamma value of an output device for rendering the corrected transformed image.

2. The method ofclaim 1,

wherein the formula transforms intensities i in the nonlinear intensity space into gray levels in the image capture space and

wherein the step (A) comprises a step of transforming gray levels g in the source image by applying the function T⁻(g) to the gray levels to produce transformed intensities.

3. The method ofclaim 2, wherein the step (B) comprises a step of adding an exposure offset Δe to the transformed intensities to produce shifted transformed intensities.

4. The method ofclaim 1, wherein the steps (A)-(C) are performed using at least one lookup table which maps intensities in the image capture space to transformed intensities in the image capture space according to steps (A)-(C).

5. The method ofclaim 4, wherein the at least one lookup table further performs color mapping on the source image.

6. An apparatus for correcting the exposure of a source image, the apparatus comprising:

first transformation means for transforming the source image from an image capture space into a nonlinear intensity space to produce a first transformed image;

correction means for correcting the exposure of the transformed image in the nonlinear intensity space to produce a corrected transformed image; and

second transformation means for transforming the corrected transformed image into the image capture space to produce a second transformed image, wherein the second transformation means comprises:

means for transforming the corrected transformed image into a third transformed image using an S-shaped curve; and

means for transforming the third transformed image into the second transformed image using a gamma function;

wherein the second transformation means comprises means for transforming the corrected transformed image into the second transformed image using the formula:

T(i)=(A+Btanh(−s(i+o)))^1/γ

wherein i represents an intensity in the nonlinear intensity space, wherein A, B. s and o are parameters of said S-shaped curve and wherein γ is a gamma value of an output device for rendering the corrected transformed image.

7. The apparatus ofclaim 6, wherein the formula transforms intensities i in the nonlinear intensity space into gray levels in the image capture space and

wherein the first transformation means comprises means transforming gray levels g in the source image by applying the function T⁻¹(g) to the gray levels to produce transformed intensities.

8. The apparatus ofclaim 7, wherein the correction means comprises means for adding an exposure offset Δe to the transformed intensities to produce shifted transformed intensities.

9. The apparatus ofclaim 6, wherein the first transformation means, the correction means, and the second transformation means are implemented in at least one lookup table which maps intensities in the image capture space to transformed intensities in the image capture space.

10. The apparatus ofclaim 9, wherein the at least one lookup table further performs color mapping on the source image.

11. A computer-readable medium having computer-executable instructions for correcting the exposure of a source image, the computer-executable instructions performing:

(A) transforming the source image from an image capture space into a nonlinear intensity space to produce a first transformed image;

(B) correcting the exposure of the transformed image in the nonlinear intensity space to produce a corrected transformed image; and

(C) transforming the corrected transformed image back into the image capture space to produce a second transformed image by steps comprising:

(C)( 1) transforming the corrected transformed image into a third transformed image using an S-shaped curve; and

(C)(2) transforming the third transformed image into the second transformed image using a gamma function;

wherein the step (C) comprises a step of transforming the corrected transformed image into the second transformed image using the formula:

T(i)=(A+Btanh(−s(i+o)))^l/γ

wherein i represents an intensity in the nonlinear intensity space, wherein A, B, s and o are parameters of said S-shaped curve and wherein γ is a gamma value of an output device for rendering the corrected transformed image.

Images