Locally adapted histogram equalization

• US 6,650,774 B1
• Filed: 10/01/1999
• Issued: 11/18/2003
• Est. Priority Date: 10/01/1999
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Szeliski, Richard S.
• Primary Examiner(s): Au, Amelia M.
• Assistant Examiner(s): LAROSE, COLIN M
• Application Number:
  US09/411,619
• Time in Patent Office: 1,509 Days
• Field of Search: 382/264, 382/169, 382/274, 382/284, 382/172, 382/268, 382/271, 382/273, 382/168, 382/167, 358/461, 358/525, 358/520, 348/672, 348/225.1, 348/683, 348/655, 348/256, 348/223.1
• US Class Current: 382/169
• CPC Class Codes: G06T 2207/20012 Locally adaptive
• CPC Class Codes: G06T 2207/20216 Image averaging
• CPC Class Codes: G06T 5/40 using histogram techniques
• CPC Class Codes: G06T 5/94 based on local image properties, e.g. for local contrast enhancement

Abstract

A system and method for improving the uniformity in exposure and tone of a digital image using a locally adapted histogram equalization approach. This approach involves first segmenting the digital image into a plurality of image patches. For each of these patches, a pixel brightness level histogram is created. The histogram for each patch is then optionally averaged with the histograms associated with a prescribed number of neighboring image patches. A normalized cumulative distribution function is generated for each patch based on the associated averaged histogram. This normalized-cumulative distribution function identifies a respective new pixel brightness level for each of the original pixel brightness levels. For each of the original pixel brightness levels, the 1s associated new pixel brightness levels from one or more of the image patches are blended. Preferably, this blending is accomplished using either a bilinear or biquadratic interpolator function. Finally, for each image patch, the original pixel brightness level of each pixel in the image patch is replaced with the blended pixel brightness level corresponding to that original brightness level. A further refinement can also be implemented to mitigate the effects of noise caused by areas of a single color in the scene depicted in patch. In one embodiment, this refinement entails employing a partially equalization approach. In another embodiment, the refinement entails limiting the gain exhibited by any of the blended pixel brightness levels associated with an image patch, in comparison to its associated original pixel brightness level, to a prescribed level.

Claims

1. A computer-implemented process for improving the uniformity in exposure and tone of a digital image, said process comprising using a computer to perform the following acts:

segmenting the digital image into a plurality of image patches;

for each image patch, creating a pixel brightness level histogram which identifies a respective pixel count for each of a plurality of original pixel brightness levels exhibited by the pixels of the patch;

averaging said pixel brightness level histogram with the histograms associated with a prescribed number of neighboring image patches to produce an averaged histogram;

for each image patch, generating a normalized cumulative distribution function based on the histogram, wherein a maximum cumulative count value thereof corresponds to a maximum original pixel brightness level, and wherein said normalized cumulative distribution function identifies a respective new pixel brightness level for each of the original pixel brightness levels as represented by the normalized pixel count value corresponding to each respective original pixel brightness level;

for each image patch, respectively blending the new pixel brightness level associated with each of the original pixel brightness levels with the new pixel brightness level associated with the same original pixel brightness level in at least one neighboring image patch; and

for each image patch, replacing the original pixel brightness level of each pixel in the image patch with the blended pixel brightness level corresponding to that original brightness level, to produce a final image exhibiting improved uniformity in exposure and tone.

2. The process of claim 1, wherein the act of segmenting comprises the act of segmenting the digital image into a plurality of square image patches of equal size.

3. The process of claim 1, wherein the act of averaging comprises the act of using kernel averaging.

4. The process of claim 3, wherein the act of kernel averaging comprises the act of weighting the pixel brightness histograms involved in the averaging process so as to give preference to the histogram of the image patch being averaged.

5. The process of claim 4, wherein the act of weighting comprises the act of weighting the histograms of the neighboring patches in such a way that the contribution of a histogram of a neighboring patch to said averaged histogram decreases with the distance of that patch from the patch whose histogram is being averaged.

6. The process of claim 1, further comprising the act of repeating the act of averaging a prescribed number of times.

7. The process of claim 1, wherein the pixel brightness levels comprise pixel gray levels.

8. The process of claim 1, wherein the digital image being processed comprises a color image and the pixel brightness level is modeled by the Y-luminance channel, and wherein the red, green and blue pixel levels of each pixel in the final image are determined in accordance with a change in the Y-luminance channel.

9. A system for improving the uniformity in exposure and tone of a digital image, comprising:

a general purpose computing device;

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

segment the digital image into a plurality of sub-image sectors referred to hereinafter as image patches,

for each image patch, create a histogram which identifies a respective pixel count for each of a plurality of original pixel brightness levels exhibited by the pixels of the patch, said pixel count representing the number of image patch pixels exhibiting a particular pixel brightness level,

performing an averaging of the pixel count of each of the plurality of original pixel brightness levels with the pixels counts associated with the corresponding brightness levels of a prescribed number of neighboring image patches to produce an averaged histogram for each image patch,

for each image patch, generate a cumulative distribution function based on the histogram,

for each image patch, normalize the cumulative distribution function so that a maximum cumulative count value thereof corresponds to the maximum original pixel brightness level,

for each image patch, create a look-up table from the normalized cumulative distribution function that associates each original pixel brightness level to a new pixel brightness level represented by the normalized pixel count value associated with that original pixel brightness level,

for each image patch, respectively blend the new pixel brightness level associated with each of the original pixel brightness levels with the new pixel brightness level associated with the same original pixel brightness level in at least one neighboring image patch, and

for each image patch, replace the original pixel brightness level of each pixel in the image patch with the blended pixel brightness level of the patch'"'"'s look-up table corresponding to that original brightness level, to produce a final image exhibiting improved uniformity in exposure and tone.

10. The system of claim 9, wherein the segmenting program module comprises a sub-module for segmenting the digital image into a plurality of square image patches of equal size.

11. The system of claim 9, wherein the averaging program module comprises a sub-module for using kernel averaging.

12. The system of claim 11, wherein the sub-module for kernel averaging comprises a sub-module for weighting the pixel brightness histograms involved in the averaging module so as to give preference to the histogram of the image patch being averaged.

13. The system of claim 12, wherein the weighting sub-module comprises a sub-module for weighting the histograms of the neighboring patches in such a way that the contribution of a histogram of a neighboring patch to said averaged histogram decreases with the distance of that patch from the patch whose histogram is being averaged.

14. The system of claim 9, further comprising a program module for repeating the averaging module a prescribed number of times.

15. A computer-readable memory for causing a computer to improve the uniformity in exposure and tone of a digital image, comprising:

a computer-readable storage medium; and

a computer program comprising program modules stored in the storage medium, wherein the storage medium is so configured by the computer program that it causes the computer to,

segment the digital image into a plurality of image patches,

for each image patch, create a histogram which identifies a respective pixel count for each of a plurality of original pixel brightness levels exhibited by the pixels of the patch,

performing an averaging of the pixel count of each of the plurality of original pixel brightness levels with the pixels counts associated with the corresponding brightness levels of a prescribed number of neighboring image patches to Produce an averaged histogram for each image patch,

for each image patch, generate a cumulative distribution function based on the histogram,

for each image patch, normalize the cumulative distribution function so that a maximum cumulative count value thereof corresponds to the maximum original pixel brightness level, and wherein said normalized cumulative distribution function identifies a respective new pixel brightness level for each of the original pixel brightness levels as represented by the normalized pixel count value corresponding to each respective original pixel brightness level,

for each image patch, respectively blend the new pixel brightness level associated with each of the original pixel brightness levels with the new pixel brightness level associated with the same original pixel brightness level in at least one neighboring image patch, and

for each image patch, replace the original pixel brightness level of each pixel in the image patch with the blended pixel brightness level corresponding to that original brightness level, to produce a final image exhibiting improved uniformity in exposure and tone.

16. The computer-readable memory of claim 15, wherein the segmenting program module comprises a sub-module for segmenting the digital image into a plurality of square image patches of equal size.

17. The computer-readable memory of claim 15, wherein the averaging program module comprises a sub-module for using kernel averaging.

18. The computer-readable memory of claim 17, wherein the sub-module for kernel averaging comprises a sub-module for weighting the pixel brightness histograms involved in the averaging module so as to give preference to the histogram of the image patch being averaged.

19. The computer-readable memory of claim 18, wherein the weighting sub-module comprises a sub-module for weighting the histograms of the neighboring patches in such a way that the contribution of a histogram of a neighboring patch to said averaged histogram decreases with the distance of that patch from the patch whose histogram is being averaged.

20. The computer-readable memory of claim 15 further comprising the a program module for repeating the averaging module a prescribed number of times.

21. The computer-readable memory of claim 15, wherein the blending program module comprises a sub-module for using a bilinear interpolator function to blend the new pixel brightness levels.

22. The computer-readable memory of claim 15, wherein the blending program module comprises a sub-module for using a biquadratic interpolator function to blend the new pixel brightness levels.

23. The computer-readable memory of claim 15, further comprising a program module for blending the normalized cumulative distribution function of an image patch exhibiting noise caused by areas of a single color in the scene depicted in the patch with a straight line function to produce a blended distribution function which reduces the reduces the effects of said noise, wherein said blended normalized cumulative distribution function is employed to identify the respective new pixel brightness level for each of the original pixel brightness levels as represented by the blended and normalized pixel count value corresponding to each respective original pixel brightness level.

24. The computer-readable memory of claim 23, wherein the program module for blending the normalized cumulative distribution function with a straight line function comprises a sub-module for assigning a weighting factor to the straight line function that determines a degree to which the straight line function contributes to the blended distribution function.

25. The computer-readable memory of claim 15, further comprising a program module for limiting the gain exhibited by any of the blended pixel brightness levels associated with an image patch, in comparison to its associated original pixel brightness level, to a prescribed level, said prescribed level being chosen so as to mitigate the effects of noise caused by areas of a single color in the scene depicted in the image patch.

26. A computer-implemented process for improving the uniformity in exposure and tone of a digital image, said process comprising using a computer to perform the following acts:

segmenting the digital image into a plurality of image patches;

for each image patch, creating a pixel brightness level histogram which identifies a respective pixel count for each of a plurality of original pixel brightness levels exhibited by the pixels of the patch;

for each image patch, averaging said pixel brightness level histogram with the histograms associated with a prescribed number of neighboring image patches to produce an averaged histogram;

for each image patch, generating a normalized cumulative distribution function based on the averaged histogram, wherein a maximum cumulative count value thereof corresponds to a maximum original pixel brightness level, and wherein said normalized cumulative distribution function identifies a respective new pixel brightness level for each of the original pixel brightness levels as represented by the normalized pixel count value corresponding to each respective original pixel brightness level;

for each image patch, replacing the original pixel brightness level of each pixel in the image patch with the new pixel brightness level corresponding to that original brightness level, to produce a final image exhibiting improved uniformity in exposure and tone.

27. A computer-implemented process for generating a composite image that exhibits an improved uniformity in both exposure and tone in comparison to a set of digital input images each of which exhibits a different exposure level, said process comprising using a computer to perform the following acts:

accessing said set of digital images;

computing a summed brightness level for each pixel set in the set of images by adding the brightness level exhibited by each pixel in a pixel set to produce a summed brightness image, wherein a pixel set comprises a pixel from each image of the image set which represents the same portion of the scene depicted by the set of images;

segmenting the summed brightness image into a plurality of image patches;

for each image patch, creating a pixel brightness level histogram which identifies a respective pixel count for each of a plurality of original summed brightness levels exhibited by the pixel sets of the patch;

for each image patch, averaging said pixel brightness level histogram with the histograms associated with a prescribed number of neighboring image patches to produce an averaged histogram;

for each image patch, generating a normalized cumulative distribution function based on the averaged histogram, wherein a maximum cumulative count value thereof corresponds to a maximum original summed brightness level, and wherein said normalized cumulative distribution function identifies a respective new summed brightness level for each of the original summed brightness levels as represented by the normalized pixel count value corresponding to each respective original summed brightness level;

for each image patch, respectively blending the new pixel brightness level associated with each of the original pixel brightness levels with the new pixel brightness level associated with the same original pixel brightness level in at least one neighboring image patch;

for each image patch, replacing the original summed brightness level of each pixel in the image patch with the blended summed brightness level corresponding to that original summed brightness level; and

for each image patch, dividing each blended summed brightness level by the number of digital images in the set of images to produce a final image exhibiting improved uniformity in exposure and tone.

28. A computer-implemented process for improving the uniformity in exposure and tone of a digital image, said process comprising using a computer to perform the following acts:

segmenting the digital image into a plurality of image patches;

for each image patch, creating a pixel brightness level histogram which identifies a respective pixel count for each of a plurality of original pixel brightness levels exhibited by the pixels of the patch;

for each image patch, generating a normalized cumulative distribution function based on the histogram, wherein a maximum cumulative count value thereof corresponds to a maximum original pixel brightness level, and wherein said normalized cumulative distribution function identifies a respective new pixel brightness level for each of the original pixel brightness levels as represented by the normalized pixel count value corresponding to each respective original pixel brightness level;

for each image patch, respectively blending the new pixel brightness level associated with each of the original pixel brightness levels with the new pixel brightness level associated with the same original pixel brightness level in at least one neighboring image patch using a bilinear interpolator function to blend the new pixel brightness levels; and

for each image patch, replacing the original pixel brightness level of each pixel in the image patch with the blended pixel brightness level corresponding to that original brightness level, to produce a final image exhibiting improved uniformity in exposure and tone.

29. A computer-implemented process for improving the uniformity in exposure and tone of a digital image, said process comprising using a computer to perform the following acts:

segmenting the digital image into a plurality of image patches;

for each image patch, creating a pixel brightness level histogram which identifies a respective pixel count for each of a plurality of original pixel brightness levels exhibited by the pixels of the patch;

for each image patch, generating a normalized cumulative distribution function based on the histogram, wherein a maximum cumulative count value thereof corresponds to a maximum original pixel brightness level, and wherein said normalized cumulative distribution function identifies a respective new pixel brightness level for each of the original pixel brightness levels as represented by the normalized pixel count value corresponding to each respective original pixel brightness level;

for each image patch, respectively blending the new pixel brightness level associated with each of the original pixel brightness levels with the new pixel brightness level associated with the same original pixel brightness level in at least one neighboring image patch using a biquadratic interpolator function to blend the new pixel brightness levels; and

for each image patch, replacing the original pixel brightness level of each pixel in the image patch with the blended pixel brightness level corresponding to that original brightness level, to produce a final image exhibiting improved uniformity in exposure and tone.

30. A computer-implemented process for improving the uniformity in exposure and tone of a digital image, said process comprising using a computer to perform the following acts:

segmenting the digital image into a plurality of image patches;

for each image patch, creating a pixel brightness level histogram which identifies a respective pixel count for each of a plurality of original pixel brightness levels exhibited by the pixels of the patch;

for each image patch, generating a normalized cumulative distribution function based on the histogram, wherein a maximum cumulative count value thereof corresponds to a maximum original pixel brightness level, and wherein said normalized cumulative distribution function identifies a respective new pixel brightness level for each of the original pixel brightness levels as represented by the normalized pixel count value a corresponding to each respective original pixel brightness level;

for each image patch, respectively blending the new pixel brightness level associated with each of the original pixel brightness levels with the new pixel brightness level associated with the same original pixel brightness level in at least one neighboring image patch;

for each image patch, replacing the original pixel brightness level of each pixel in the image patch with the blended pixel brightness level corresponding to that original brightness level, to produce a final image exhibiting improved uniformity in exposure and tone; and

blending the normalized cumulative distribution function of an image patch exhibiting noise caused by areas of a single color in the scene depicted in the patch with a straight line function to produce a blended distribution function which reduces the reduces the effects of said noise, wherein said blended normalized cumulative distribution function is employed to identify the respective new pixel brightness level for each of the original pixel brightness levels as represented by the blended and normalized pixel count value corresponding to each respective original pixel brightness level.

31. The process of claim 30, wherein the act of blending the normalized cumulative distribution function with a straight line function comprises the act of assigning a weighting factor to the straight line function that determines a degree to which the straight line function contributes to the blended distribution function.

32. The process of claim 31, wherein the weighting factor associated with the straight line function varies in a range which causes the contribution of the straight line function to the blended distribution function to vary anywhere from 0 percent to 100 percent.

33. A computer-implemented process for improving the uniformity in exposure and tone of a digital image, said process comprising using a computer to perform the following acts:

segmenting the digital image into a plurality of image patches;

for each image patch, creating a pixel brightness level histogram which identifies a respective pixel count for each of a plurality of original pixel brightness levels exhibited by the pixels of the patch;

for each image patch, generating a normalized cumulative distribution function based on the histogram, wherein a maximum cumulative count value thereof corresponds to a maximum original pixel brightness level, and wherein said normalized cumulative distribution function identifies a respective new pixel brightness level for each of the original pixel brightness levels as represented by the normalized pixel count value corresponding to each respective original pixel brightness level;

for each image patch, respectively blending the new pixel brightness level associated with each of the original pixel brightness levels with the new pixel brightness level associated with the same original pixel brightness level in at least one neighboring image patch;

for each image patch, replacing the original pixel brightness level of each pixel in the image patch with the blended pixel brightness level corresponding to that original brightness level, to produce a final image exhibiting improved uniformity in exposure and tone; and

limiting the gain exhibited by any of the blended pixel brightness levels associated with an image patch, in comparison to its associated original pixel brightness level, to a prescribed level, said prescribed level being chosen so as to mitigate the effects of noise caused by areas of a single color in the scene depicted in the image patch.

34. A system for improving the uniformity in exposure and tone of a digital image, comprising:

a general purpose computing device;

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

segment the digital image into a plurality of sub-image sectors referred to hereinafter as image patches,

for each image patch, create a histogram which identifies a respective pixel count for each of a plurality of original pixel brightness levels exhibited by the pixels of the patch, said pixel count representing the number of image patch pixels exhibiting a particular pixel brightness level,

performing an averaging of the pixel count of each of the plurality of original pixel brightness levels with the pixels counts associated with the corresponding brightness levels of a prescribed number of neighboring image patches to produce an averaged histogram for each image patch,

for each image patch, generate a cumulative distribution function based on the histogram,

for each image patch, normalize the cumulative distribution function so that a maximum cumulative count value thereof corresponds to the maximum original pixel brightness level,

for each image patch, create a look-up table from the normalized cumulative distribution function that associates each original pixel brightness level to a new pixel brightness level represented by the normalized pixel count value associated with that original pixel brightness level,

for each image patch, respectively blend the new pixel brightness level associated with each of the original pixel brightness levels with the new pixel brightness level associated with the same original pixel brightness level in at least one neighboring image patch, and

for each image patch, replace the original pixel brightness level of each pixel in the image patch with the blended pixel brightness level of the patch'"'"'s look-up table corresponding to that original brightness level, to produce a final image exhibiting improved uniformity in exposure and tone.

35. A system for improving the uniformity in exposure and tone of a digital image, comprising:

a general purpose computing device;

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

segment the digital image into a plurality of sub-image sectors referred to hereinafter as image patches,

for each image patch, create a histogram which identifies a respective pixel count for each of a plurality of original pixel brightness levels exhibited by the pixels of the patch, said pixel count representing the number of image patch pixels exhibiting a particular pixel brightness level,

for each image patch, generate a cumulative distribution function based on the histogram,

for each image patch, normalize the cumulative distribution function so that a maximum cumulative count value thereof corresponds to the maximum original pixel brightness level,

for each image patch, create a look-up table from the normalized cumulative distribution function that associates each original pixel brightness level to a new pixel brightness level represented by the normalized pixel count value associated with that original pixel brightness level,

for each image patch, respectively blend the new pixel brightness level associated with each of the original pixel brightness levels with the new pixel brightness level associated with the same original pixel brightness level in at least one neighboring image patch, said blending comprising any of a sub-module for using a bilinear interpolator function to blend the new pixel brightness levels, and a sub-module for using a biquadratic interpolator function to blend the new pixel brightness levels, and

for each image patch, replace the original pixel brightness level of each pixel in the image patch with the blended pixel brightness level of the patch'"'"'s look-up table corresponding to that original brightness level, to produce a final image exhibiting improved uniformity in exposure and tone.

36. A system for improving the uniformity in exposure and tone of a digital image, comprising:

a general purpose computing device;

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

segment the digital image into a plurality of sub-image sectors referred to hereinafter as image patches,

for each image patch, create a histogram which identifies a respective pixel count for each of a plurality of original pixel brightness levels exhibited by the pixels of the patch, said pixel count representing the number of image patch pixels exhibiting a particular pixel brightness level,

for each image patch, generate a cumulative distribution function based on the histogram,

for each image patch, normalize the cumulative distribution function so that a maximum cumulative count value thereof corresponds to the maximum original pixel brightness level,

blending the normalized cumulative distribution function of an image patch exhibiting noise caused by areas of a single color in the scene depicted in the patch with a straight line function to produce a blended distribution function which reduces the reduces the effects of said noise, wherein said blended normalized cumulative distribution function is employed to identify the respective new pixel brightness level for each of the original pixel brightness levels as represented by the blended and normalized pixel count value corresponding to each respective original pixel brightness level,

for each image patch, create a look-up table from the normalized cumulative distribution function that associates each original pixel brightness level to a new pixel brightness level represented by the normalized pixel count value associated with that original pixel brightness level,

for each image patch, respectively blend the new pixel brightness level associated with each of the original pixel brightness levels with the new pixel brightness level associated with the same original pixel brightness level in at least one neighboring image patch, and

for each image patch, replace the original pixel brightness level of each pixel in the image patch with the blended pixel brightness level of the patch'"'"'s look-up table corresponding to that original brightness level, to produce a final image exhibiting improved uniformity in exposure and tone.

37. The system of claim 36, wherein the program module for blending the normalized cumulative distribution function with a straight line function comprises a sub-module for assigning a weighting factor to the straight line function that determines a degree to which the straight line function contributes to the blended distribution function.

38. A system for improving the uniformity in exposure and tone of a digital image, comprising:

a general purpose computing device;

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

segment the digital image into a plurality of sub-image sectors referred to hereinafter as image patches,

for each image patch, create a histogram which identifies a respective pixel count for each of a plurality of original pixel brightness levels exhibited by the pixels of the patch, said pixel count representing the number of image patch pixels exhibiting a particular pixel brightness level,

for each image patch, generate a cumulative distribution function based on the histogram,

for each image patch, normalize the cumulative distribution function so that a maximum cumulative count value thereof corresponds to the maximum original pixel brightness level,

for each image patch, create a look-up table from the normalized cumulative distribution function that associates each original pixel brightness level to a new pixel brightness level represented by the normalized pixel count value associated with that original pixel brightness level,

for each image patch, respectively blend the new pixel brightness level associated with each of the original pixel brightness levels with the new pixel brightness level associated with the same original pixel brightness level in at least one neighboring image patch,

limiting the gain exhibited by any of the blended pixel brightness levels associated with an image patch, in comparison to its associated original pixel brightness level, to a prescribed level, said prescribed level being chosen so as to mitigate the effects of noise caused by areas of a single color in the scene depicted in the image patch, and

for each image patch, replace the original pixel brightness level of each pixel in the image with the blended pixel brightness level of the patch'"'"'s look-up table corresponding to that original brightness level, to produce a final image exhibiting improved uniformity in exposure and tone.