Method for determining document background for adjusting the dynamic range of an image of the document

• US 6,198,845 B1
• Filed: 07/01/1997
• Issued: 03/06/2001
• Est. Priority Date: 07/01/1997
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Yeh, Thomas I., Fox, Richard S., Blaakman, Andre M., Lahue, George W., Nagarajan, Ramesh, Tse, Francis K., Farrell, Barbara L.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Mariam, Daniel G.
• Application Number:
  US08/886,205
• Time in Patent Office: 1,344 Days
• Field of Search: 382/167, 382/169, 382/268, 382/171, 382/260, 382/262, 382/264, 382/274, 382/275, 358/464, 358/522, 358/455, 358/461, 345/147
• US Class Current: 382/169
• CPC Class Codes: G06T 2207/10008 from scanner, fax or copier
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/136 involving thresholding
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation
• CPC Class Codes: H04N 1/4074 using histograms

Abstract

The background grey-level of a document is determined based on the gain of the document. A histogram is generated and compressed. The standard deviation of the distribution curve of the compressed histogram is determined. A gain factor is determined using the mean and standard deviation. Using the background grey-level, the dynamic range of the document is adjusted.

Claims

1. A method for determining a background grey-level of a document, comprising:

generating a histogram of grey-level values from a sampling window of the document;

smoothing the histogram;

determining a curve approximating a shape of the smoothed histogram;

determining a mean and standard deviation of the curve;

determining a gain of the document based on the mean and standard deviation and a maximum grey-level value of the histogram; and

determining the background grey-level of the document based on the gain.

2. The method of claim 1, wherein smoothing the histogram comprises:

dividing the grey-level values of the histogram into a plurality of subsets, each subset including a plurality of the grey-level values;

determining, for each subset, a sum of frequency values of the plurality of the grey-level values; and

dividing, for each subset, the sum of frequency values by a number of the plurality of the grey-level values in that subset.

3. The method of claim 1, wherein determining the curve comprises:

determining a peak frequency value for the smoothed histogram;

identifying a plurality of grey-level values adjacent to the grey-level value having the peak frequency value;

identifying frequency values of the plurality of adjacent grey-level values; and

determining the curve which passes through the peak frequency value and the frequency values of the plurality of adjacent grey-level values.

4. The method of claim 3, wherein the curve is a second-order polynomial.

5. The method of claim 3, wherein the plurality of adjacent grey-level values includes the two grey-level values immediately adjacent to the grey-level value having the peak frequency.

6. The method of claim 3, wherein the adjacent grey-level values include the grey-level values of the histogram whose frequency values are closest to F_ve⁻

0.5, where e is the base of the natural logarithm and F_v is the peak frequency value.

7. The method of claim 1, further comprising adjusting a dynamic range of a pixel of an image of the document based on the determined background grey-level.

8. The method of claim 7, wherein adjusting the dynamic range comprises:

determining an original pixel value of the image;

determining a largest possible dynamic range of the image;

determining an image reflectance value such that a sum of image areas containing reflectances below the determined image reflectance value is less than a predetermined percentage of a total area of the image;

determining a difference between the original pixel value and the determined image reflectance value;

determining a difference between the determined background grey-level and the determined image reflectance value; and

determining a new pixel value of the image based on the original pixel value, the determined image reflectance value, the largest possible dynamic range of the image and the determined background grey-level of the image.

9. A method for determining the background grey level of a document, comprising:

generating a histogram of grey-level values from a sampling window of the document;

compressing the histogram;

determining a distribution curve of the compressed histogram;

determining a mean and standard deviation of the distribution curve;

determining a gain factor based on the mean and standard deviation; and

determining the background grey-level of the document based on the gain factor.

10. The method of claim 9, wherein compressing the histogram comprises:

dividing the grey-level values of the histogram into a plurality of subsets, each subset including a plurality of the grey-level values;

determining, for each subset, a sum of frequency values of the plurality of the grey-level values; and

dividing, for each subset, the sum of frequency values by a number of the plurality of the grey-level values of that subset.

11. The method according to claim 9, wherein determining the distribution curve comprises:

determining a peak frequency value for the compressed histogram;

identifying a plurality of grey-level values adjacent to the grey-level value having the peak frequency value;

identifying frequency values of the plurality of adjacent grey-level values; and

determining the distribution curve which passes through the peak frequency value and the frequency values of the plurality of adjacent grey-level values.

12. The method of claim 11, wherein the distribution curve is a second-order polynomial.

13. The method of claim 11, wherein the plurality of adjacent grey-level values include the two grey-level values immediately adjacent to the grey-level value having the peak frequency.

14. The method of claim 9, further comprising adjusting a dynamic range of a pixel of an image of the document based on the determined background grey-level.

15. The method of claim 14, wherein adjusting the dynamic range comprises:

determining an original pixel value of the image;

determining a largest possible dynamic range of the image;

determining an image reflectance value such that a sum of image areas containing reflectances below the determined image reflectance value is less than a predetermined percentage of a total area of the image; and

determining a new pixel value of the image based on the original pixel value, the determined image reflectance value, the largest possible dynamic range of the image and the determined background grey-level of the image.

28. The method of claim 15, further comprising:

determining a difference between the original pixel value and the determined image reflectance value; and

determining a difference between the determined background grey-level and the determined image reflectance value;

wherein determining the new pixel value of the image is based on the determined difference between the original pixel value and the image reflectance value and the determined difference between the background grey-level of the image and the image reflectance value.

16. A method for adjusting a dynamic range of a pixel of an image of a document, comprising:

obtaining an original pixel grey-level value of the image;

determining a largest possible dynamic range of the image;

determining an image reflectance value such that a sum of image areas containing reflectances below the determined image reflectance value is less than a predetermined percentage of a total area of the image;

determining a background grey-level of the image; and

determining a new pixel value of the image of the document based on the original pixel value, the determined image reflectance value, the largest possible dynamic range of the image and the determined background grey-level of the image.

29. The method of claim 16, further comprising:

determining a difference between the original pixel value and the determined image reflectance value; and

determining a difference between the determined background grey-level and the determined image reflectance value;

wherein determining the new pixel value of the image is based on the determined difference between the original pixel value and the image reflectance value and the determined difference between the background grey-level of the image and the image reflectance value.

17. A method for adjusting a dynamic range of a pixel of an image of a document, comprising:

determining an original pixel value of the image;

determining a largest possible dynamic range of the image;

determining an image reflectance value such that a sum of image areas containing reflectances below the determined image reflectance value is less than a predetermined percentage of a total area of the image;

determining a background grey-level of the image, comprising;

generating a histogram from a sampling window of the document,

smoothing the histogram,

determining a curve approximating a shape of the smoothed histogram,

determining a mean and standard deviation of the curve,

determining a gain of the document based on the mean and standard deviation and a maximum grey-level value of the histogram, and

estimating the background grey-level of the document based on the gain, and

determining a new pixel value of the image of the document based on the original pixel value, the largest possible dynamic range of the image, the determined image reflectance value, and the determined background grey-level of the image.

18. The method for adjusting the dynamic range of an image according to claim 17, wherein smoothing the histogram comprises:

dividing the grey-level values of the histogram into a plurality of subsets, each subset including a plurality of the grey-level values;

determining, for each subset, a sum of frequency values of the plurality of the grey-level values; and

dividing, for each subset, the sum of frequency values by a number of the plurality of the grey-level values of that subset.

19. The method for adjusting the dynamic range of an image according to claim 17, wherein determining the curve comprises:

determining a peak frequency value for the histogram;

identifying a plurality of grey-level values adjacent to the grey-level value having the peak frequency value;

identifying frequency values of the plurality of adjacent grey-level values; and

determining the curve which passes through the peak frequency value and the frequency values of the plurality of adjacent grey-level values.

20. The method for adjusting the dynamic range of an image according to claim 19, wherein the curve is a second-order polynomial.

21. The method for adjusting the dynamic range of an image according to claim 19, wherein the plurality of adjacent grey-level values include the two grey-level values immediately adjacent to the grey-level value having the peak frequency.

22. The method for adjusting the dynamic range of an image according to claim 19, wherein the adjacent grey-level values include the grey-level values of the histogram whose frequency values are closest to F_ve⁻

0.5, where e is the base of the natural logarithm and F_v is the peak frequency value.

23. A method for adjusting a dynamic range of a pixel of an image of a document, comprising:

determining an original pixel value of the image;

determining a largest possible dynamic range of the image;

determining an image reflectance value such that a sum of image areas containing reflectances below the determined image reflectance value is less than a predetermined percentage of a total area of the image;

determining a background grey-level of the image, comprising;

generating a histogram of grey-level values from a sampling window of the document,

compressing the histogram,

determining a distribution curve of the compressed histogram,

determining a standard deviation of the distribution curve,

determining a gain factor based on the standard deviation, and

determining the background grey-level of the document based on the gain factor; and

determining a new pixel value of the image of the document based on the original pixel value, the largest possible dynamic range of the image, the determined image reflectance value, and the determined background grey-level of the image.

24. The method for adjusting the dynamic range of an image according to claim 23, wherein compressing the histogram comprises:

dividing the grey-level values of the histogram into a plurality of subsets, each subset including a plurality of the grey-level values;

determining, for each subset, a sum of frequency values of the plurality of the grey-level values; and

dividing, for each subset, the sum of frequency values by a number of the plurality of the grey-level values of that subset.

25. The method for adjusting the dynamic range of an image according to claim 23, wherein determining the distribution curve comprises:

determining a peak frequency value for the compressed histogram;

identifying a plurality of grey-level values adjacent to the grey-level value having the peak frequency value;

identifying frequency values of the plurality of adjacent grey-level values; and

determining the distribution curve which passes through the peak frequency value and the frequency values of the plurality of adjacent grey-level values.

26. The method of claim 25, wherein the plurality of adjacent grey-level values include the two grey-level values immediately adjacent to the grey-level value having the peak frequency.

27. A method for adjusting a dynamic range of a pixel of an image of an input document, the method comprising:

generating a histogram of grey-level values from a sampling window of the document;

smoothing the histogram;

determining a curve approximating a shape of the smoothed histogram;

determining a mean and standard deviation of the curve; and

determining a gain of the document based on the mean and standard deviation and a maximum grey-level value of the histogram;

determine the background grey-level of the document based on the gain;

determining an original pixel value of the image;

determining a largest possible dynamic range of the image;

determining an image reflectance value such that a sum of image areas containing reflectances below the determined image reflectance value is less than a predetermined percentage of a total area of the image;

determining a difference between the original pixel value and the determined image reflectance value;

determining a difference between the determined background grey-level and the determined image reflectance value; and

determining a new pixel value of the image based on the original pixel value, the determined image reflectance value, the largest possible dynamic range of the image and the determined background grey-level of the image.