Optimal binarization of gray-scaled digital images via fuzzy reasoning

• US 7,298,897 B1
• Filed: 02/11/2004
• Issued: 11/20/2007
• Est. Priority Date: 02/11/2004
• Status: Expired due to Fees

• Current Assignee: National Aeronautics and Space Administration US Government As Represented By The Administrator of The
• Original Assignee: United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration
• Inventors: Dominguez, Jesus A., Klinko, Steven J.
• Primary Examiner(s): Do; Anh Hong
• Application Number:
  US10/779,551
• Time in Patent Office: 1,378 Days
• Field of Search: 382/133, 382/143, 382/172, 382/168, 382/128, 382/224, 382/270, 356/73.1
• US Class Current: 382/172
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06V 10/28 Quantising the image, e.g. histogram thresholding for discrimination between background and foreground patterns

Abstract

A technique for finding an optimal threshold for binarization of a gray scale image employs fuzzy reasoning. A triangular membership function is employed which is dependent on the degree to which the pixels in the image belong to either the foreground class or the background class. Use of a simplified linear fuzzy entropy factor function facilitates short execution times and use of membership values between 0.0 and 1.0 for improved accuracy. To improve accuracy further, the membership function employs lower and upper bound gray level limits that can vary from image to image and are selected to be equal to the minimum and the maximum gray levels, respectively, that are present in the image to be converted. To identify the optimal binarization threshold, an iterative process is employed in which different possible thresholds are tested and the one providing the minimum fuzzy entropy measure is selected.

Claims

1. A computer-based method for converting a gray-scale multiple pixel image to a binary image comprising the steps of:

a) loading a gray-scale image from an external source of images into an operating memory of a computer;

b) determining an optimal threshold value for converting said gray scale image to binary by executing an application with said computer, said application carrying out the steps of;

1) forming a fuzzy membership function which identifies a membership value for each pixel in said image, said membership function including a first group of gray level values at or below a selected intensity threshold that are designated as corresponding to pixels belonging to a first characteristic class of the image and a second group of gray level values above said selected intensity threshold that are designated as corresponding to pixels belonging to a second characteristic class of said image, said first and second classes being selected from the group comprising a background class and a foreground class;

2) calculating an entropy factor for each possible membership value by applying a linear entropy factor function to said membership values;

3) employing said entropy factor to calculate a fuzzy entropy measure for said image with said selected intensity threshold;

4) repeating steps (1)-(3) for a plurality of additional selected intensity thresholds;

5) selecting as optimal, a one of said intensity thresholds that provides the lowest fuzzy entropy measure; and

c) converting said gray scale image to a binary image using said optimal intensity threshold by assigning any pixels in said gray scale image having a gray level above said optimal intensity threshold to a first binary value and assigning any pixels in said gray scale image having a gray level at or below said optimal intensity threshold to a second binary value.

2. The method of claim 1, wherein said membership values are selected to range from 0.0 to 1.0.

3. The method of claim 2, wherein the step of forming said membership function includes identifying a lowest gray level value MinZ and a highest gray level value MaxZ that are present in said image and employing said lowest and highest gray level values as a lower bound and an upper bound respectively, of said membership function, said lowest and highest gray levels each being assigned a membership value of 0.0.

4. The method of claim 3, wherein said entropy measure, S(T), is defined as:

$S<br><br>\left(T\right)=\left\{1/\left[\mathrm{MN}<br><br><br><br>\log <br><br><br><br>2\right]\right\}<br><br>\underset{\mathrm{Min}<br><br><br><br>Z}{\overset{\mathrm{Max}<br><br><br><br>Z}{\sum <br><br>}}<br><br><br><br>H<br><br>\left(z\right)<br><br>\mathrm{Se}<br><br>\left[{\mathrm{\mu <br><br>}}_1<br><br>\left(z\right)\right]$

where, M=number of pixel row in said image;

N=number of pixel columns in said image;

H(z)=number of pixels in said image having a gray level z; and

, Se[μ

_I(z)]=fuzzy entropy factor function.

5. The method of claim 4, wherein said linear entropy factor function is defined as 1−

μ

_I(z), where μ

_I(z) is the membership value for a gray level z as defined by said membership function.

6. The method of claim 5, wherein a graph of said membership function includes a first triangle representing gray levels belonging to said first characteristic class and having a lower bound at said lowest gray level in said image, an upper bound at said threshold intensity and a peak at an average gray level intensity of said first characteristic class where said membership value is 1.0;

and, a second triangle representing gray levels belonging to said second characteristic class and having a lower bound at said threshold intensity, an upper bound at said highest gray level in said image and a peak at an average gray level intensity of said second characteristic class where said membership value is 1.0.

7. The method of claim 3, wherein a graph of said membership function includes a first triangle representing gray levels belonging to said first characteristic class and having a lower bound at said lowest gray level in said image, an upper bound at said threshold intensity and a peak at an average gray level intensity of said first characteristic class where said membership value is 1.0;

and, a second triangle representing gray levels belonging to said second characteristic class and having a lower bound at said threshold intensity, an upper bound at said highest gray level in said image and a peak at an average gray level intensity of said second characteristic class where said membership value is 1.0.

8. The method of claim 2, wherein said linear entropy factor function is defined as 1−

μ

_I(z), where μ

_I(z) is the membership value for a gray level z as defined by said membership function.

9. A computer-based method for converting a gray-scale multiple pixel image to a binary image comprising the steps of:

a) loading a gray-scale image from an external source of images into an operating memory of a computer;

b) determining an optimal threshold value for converting said gray scale image to binary by executing an application with said computer, said application carrying out the steps of;

1) forming a fuzzy membership function which identifies a membership value for each gray level in said image, said membership function including a first group of gray level values at or below a selected intensity threshold that are designated as corresponding to pixels belonging to a first characteristic class of the image and a second group of gray level values above said selected intensity threshold that are designated as corresponding to pixels belonging to a second characteristic class of said image, said first and second classes being selected from the group comprising a background class and a foreground class;

a graph of said membership function including a first triangle representing gray levels belonging to said first characteristic class and having a lower bound at a lowest gray level MinZ that is present in said image where a membership value of 0.0 is assigned to MinZ, an upper bound at said selected threshold intensity T and a peak at an average gray level intensity of said first characteristic class where said membership value is 1.0; and

, a second triangle representing gray levels belonging to said second characteristic class and having a lower bound at said selected threshold intensity T, an upper bound at a highest gray level MaxZ that is present in said image and a peak membership value at an average gray level intensity of said second characteristic class where said membership value is 1.0;

2) calculating an entropy factor for each possible membership value by applying a linear entropy factor function, Se[μ

_I(z)], to said membership values, μ

_i(z), where SE[μ

_I(z)]=1−

_I(z) for each gray level z in said image;

3) employing said entropy factor to calculate a fuzzy entropy measure S(T) for said image with said selected intensity threshold T by using the equation;

$S<br><br>\left(T\right)=\left\{1/\left[\mathrm{MN}<br><br><br><br>\log <br><br><br><br>2\right]\right\}<br><br>\underset{\mathrm{Min}<br><br><br><br>Z}{\overset{\mathrm{Max}<br><br><br><br>Z}{\sum <br><br>}}<br><br><br><br>H<br><br>\left(z\right)<br><br>\mathrm{Se}<br><br>\left[{\mathrm{\mu <br><br>}}_1<br><br>\left(z\right)\right]$

where, M=number of pixel row in said image;

N=number of pixel columns in said image; and

,

H(z)=number of pixels in said image having gray level z;

4) repeating steps

     1)-3) for a plurality of additional selected intensity thresholds; and

5) selecting as optimal, a one of said intensity thresholds that provides the lowest fuzzy entropy measure; and

c) converting said gray scale image to a binary image using said optimal intensity threshold by assigning any pixels in said gray scale image having a gray level above said optimal intensity threshold to a first binary value and assigning any pixels in said gray scale image having a gray level at or below said optimal intensity threshold to a second binary value.

10. A computer system for converting for converting a gray-scale multiple pixel image to a binary image comprising:

a) a processor;

b) an operating memory readable by said processor;

c) an external source of multiple pixel gray scale digital images; and

d) a program embodied in said operating memory and executable by said processor for performing process steps for retrieving a multiple pixel gray scale digital image from said external source and converting said multiple pixel gray scale digital image into a binary image, said process steps comprising;

1) forming a fuzzy membership function which identifies a membership value for each pixel in said image, said membership function including a first group of gray level values at or below a selected intensity threshold that are designated as corresponding to pixels belonging to a first characteristic class of the image and a second group of gray level values above said selected intensity threshold that are designated as corresponding to pixels belonging to a second characteristic class of said image, said first and second classes being selected from the group comprising a background class and a foreground class;

2) calculating an entropy factor for each possible membership value by applying a linear entropy factor function to said membership values;

3) employing said entropy factor to calculate a fuzzy entropy measure for said image with said selected intensity threshold;

4) repeating steps

     1)-3) for a plurality of additional selected intensity thresholds;

5) selecting as optimal, a one of said intensity thresholds that provides the lowest fuzzy entropy measure; and

6) converting said gray scale image to a binary image using said optimal intensity threshold by assigning any pixels in said gray scale image having a gray level above said optimal intensity threshold to a first binary value and assigning any pixels in said gray scale image having a gray level at or below said optimal intensity threshold to a second binary value.

11. The system of claim 10, wherein said membership values are selected to range from 0.0 to 1.0.

12. The system of claim 11, wherein the step of forming said membership function includes identifying a lowest gray level value MinZ and a highest gray level value MaxZ that are present in said image and employing said lowest and highest gray level values as a lower bound and an upper bound respectively, of said membership function, said lowest and highest gray levels each being assigned a membership value of 0.0.

13. The system of claim 12, wherein said entropy measure, S(T), is defined as:

$S<br><br>\left(T\right)=\left\{1/\left[\mathrm{MN}<br><br><br><br>\log <br><br><br><br>2\right]\right\}<br><br>\underset{\mathrm{Min}<br><br><br><br>Z}{\overset{\mathrm{Max}<br><br><br><br>Z}{\sum <br><br>}}<br><br><br><br>H<br><br>\left(z\right)<br><br>\mathrm{Se}<br><br>\left[{\mathrm{\mu <br><br>}}_1<br><br>\left(z\right)\right]$

where, M=number of pixel row in said image;

N=number of pixel columns in said image;

H(z)=number of pixels in said image having gray level z; and

, Se[μ

_I(z)]=fuzzy entropy factor function.

14. The system of claim 13, wherein said linear entropy factor function is defined as 1−

μ

_I(z), where μ

_I(z) is the membership value for a gray level z as defined by said membership function.

15. The system of claim 14, wherein a graph of said membership function includes a first triangle representing gray levels belonging to said first characteristic class and having a lower bound at said lowest gray level in said image, an upper bound at said threshold intensity and a peak at an average gray level intensity of said first characteristic class where said membership value is 1.0;

and, a second triangle representing gray levels belonging to said second characteristic class and having a lower bound at said threshold intensity, an upper bound at said highest gray level in said image and a peak at an average gray level intensity of said second characteristic class where said membership value is 1.0.

16. The system of claim 12, wherein a graph of said membership function includes a first triangle representing gray levels belonging to said first characteristic class and having a lower bound at said lowest gray level in said image, an upper bound at said threshold intensity and a peak at an average gray level intensity of said first characteristic class where said membership value is 1.0;

and, a second triangle representing gray levels belonging to said second characteristic class and having a lower bound at said threshold intensity, an upper bound at said highest gray level in said image and a peak at an average gray level intensity of said second characteristic class where said membership value is 1.0.

17. The system of claim 11, wherein said linear entropy factor function is defined as 1−

μ

_I(z), where μ

_I(z) is the membership value for a gray level z as defined by said membership function.

18. A computer system for converting for converting a gray-scale multiple pixel image to a binary image comprising:

a) a processor;

b) an operating memory readable by said processor;

c) an external source of multiple pixel gray scale digital images; and

d) a program embodied in said operating memory and executable by said processor for performing process steps for retrieving a multiple pixel gray scale digital image from said external source and converting said multiple pixel gray scale digital image into a binary image said process steps comprising;

;

1) forming a fuzzy membership function which identifies a membership value for each gray level in said image, said membership function including a first group of gray level values at or below a selected intensity threshold that are designated as corresponding to pixels belonging to a first characteristic class of the image and a second group of gray level values above said selected intensity threshold that are designated as corresponding to pixels belonging to a second characteristic class of said image, said first and second classes being selected from the group comprising a background class and a foreground class;

a graph of said membership function including a first triangle representing gray levels belonging to said first characteristic class and having a lower bound at a lowest gray level MinZ that is present in said image where a membership value of 0.0 is assigned to MinZ, an upper bound at said selected threshold intensity T and a peak at an average gray level intensity of said first characteristic class where said membership value is 1.0; and

, a second triangle representing gray levels belonging to said second characteristic class and having a lower bound at said selected threshold intensity T, an upper bound at a highest gray level MaxZ that is present in said image and a peak membership value at an average gray level intensity of said second characteristic class where said membership value is 1.0;

2) calculating an entropy factor for each possible membership value by applying a linear entropy factor function, Se[μ

_I(z)], to said membership values, μ

_I(z), where Se[μ

_I(z)]=1−

μ

_I(z) for each gray level z in said image;

3) employing said entropy factor to calculate a fuzzy entropy measure S(T) for said image with said selected intensity threshold T by using the equation;

$S<br><br>\left(T\right)=\left\{1/\left[\mathrm{MN}<br><br><br><br>\log <br><br><br><br>2\right]\right\}<br><br>\underset{\mathrm{Min}<br><br><br><br>Z}{\overset{\mathrm{Max}<br><br><br><br>Z}{\sum <br><br>}}<br><br><br><br>H<br><br>\left(z\right)<br><br>\mathrm{Se}<br><br>\left[{\mathrm{\mu <br><br>}}_1<br><br>\left(z\right)\right]$

where, M=number of pixel row in said image;

N=number of pixel columns in said image; and

, H(z)=number of pixels in said image having gray level z;

4) repeating steps

     1)-3) for a plurality of additional selected intensity thresholds;

5) selecting as optimal, a one of said intensity thresholds that provides the lowest fuzzy entropy measure; and

6) converting said gray scale image to a binary image using said optimal intensity threshold by assigning any pixels in said gray scale image having a gray level above said optimal intensity threshold to a first binary value and assigning any pixels in said gray scale image having a gray level at or below said optimal intensity threshold to a second binary value.