Image edge extraction via fuzzy reasoning

• US 7,400,766 B1
• Filed: 02/19/2004
• Issued: 07/15/2008
• Est. Priority Date: 02/19/2004
• Status: Expired due to Fees

• Current Assignee: United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration
• Original Assignee: United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration
• Inventors: Klinko, Steve, Dominguez, Jesus A.
• Primary Examiner(s): Wu; Jingge
• Assistant Examiner(s): Krasnic; Bernard
• Application Number:
  US10/783,295
• Time in Patent Office: 1,608 Days
• Field of Search: 382/173, 382/174, 382/175, 382/176, 382/205, 382/266, 358/462, 358/463, 358/464, 358/465, 358/466
• US Class Current: 382/173
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06T 7/143 involving probabilistic approaches, e.g. Markov random field [MRF] modelling
• CPC Class Codes: G06V 10/443 by matching or filtering

Abstract

A computer-based technique for detecting edges in gray level digital images employs fuzzy reasoning to analyze whether each pixel in an image is likely on an edge. The image is analyzed on a pixel-by-pixel basis by analyzing gradient levels of pixels in a square window surrounding the pixel being analyzed. An edge path passing through the pixel having the greatest intensity gradient is used as input to a fuzzy membership function, which employs fuzzy singletons and inference rules to assigns a new gray level value to the pixel that is related to the pixel'"'"'s edginess degree.

Claims

1. A computer-based method for detecting one or more edges in a multiple pixel digital image comprising the steps of:

loading a multiple pixel digital gray scale image to be analyzed from an external source of images into an operating memory of a computer;

analyzing said image for edges with an image edge detection application run by said computer, said application comprising the steps of;

1) selecting a pixel in said image to be analyzed;

2) identifying a plurality of potential edge paths which pass through said selected pixel;

3) calculating an average pixel intensity gradient value for each of said edge paths by comparing a gray level intensity of pixels on one side of each of said edge paths to a gray level intensity of pixels on an opposite side of each of said edge paths;

4) selecting the greatest of said average pixel intensity gradient values of said edge paths as an input to a single fuzzy membership function and generating with said function, a plurality of output values that are related to a degree to which said pixel represents an edge in said image;

5) combining said plurality of output values using a weighted averaging analysis comprising an averaging union of truncated output singletons to assign a crisp edginess value to said pixel;

6) assigning a new edginess based gray level value to said pixel by multiplying an original gray level value of said selected pixel by said crisp edginess value, said new edginess based gray level value being proportional to an edginess degree of said selected pixel; and

7) repeating steps (1)-(6) for additional pixels in said image.

2. The computer-based method of claim 1, wherein four edge paths are identified that pass through said pixel.

3. The computer-based method of claim 1, wherein said average pixel intensity gradient value for each of said edge paths is calculated by:

selecting an n×

n pixel window, where n is an odd number greater than or equal to 3 and said pixel to be analyzed is located at a center of said window;

calculating a first, average pixel intensity value of pixels in said window on a first side of said edge path;

calculating a second, average pixel intensity value of pixels in said window on a second, opposite side of said edge path; and

,

calculating a difference between said first and second values to obtain said average pixel intensity gradient value.

4. The computer-based method of claim 1, wherein said step of generating a plurality of output values with said single membership function comprises:

employing an input membership function to generate a plurality of input values relating said average pixel intensity gradient value to a plurality of degrees of intensity;

applying a plurality of inference rules in an output membership function that relate the plurality of intensity degrees to a corresponding plurality of edginess degrees and thereby generate said plurality of output values.

5. The computer-based method of claim 4, wherein three of said input values, three of said inference rules and three of said output values are employed;

said input values being small, medium and large;

said output values being no edge, mild edge and edge; and

said inference rules being if the average pixel intensity gradient value is small, the pixel is not an edge;

if the average pixel intensity gradient value is medium, the pixel is a mild edge; and

, if the average pixel intensity gradient value is large, the pixel is an edge.

6. A computer-based method for detecting one or more edges in a multiple pixel digital image comprising the steps of:

loading a multiple pixel digital gray scale image to be analyzed from an external source of images into an operating memory of a computer;

analyzing said image for edges with an image edge detection application run by said computer, said application comprising the steps of;

1) selecting a pixel in said image to be analyzed;

2) selecting an n×

n pixel window, where n is an odd number greater than or equal to 3 and said window includes a center pixel, wherein said center pixel is said pixel to be analyzed;

3) identifying a plurality of edge paths that run through said center pixel and divide said window into first and second groups of pixels;

4) for each of said edge paths, calculating a first, average pixel intensity value of pixels in said first group and a second, average pixel intensity value of pixels in said second group; and

, calculating a difference between said first and second values to obtain an average pixel intensity gradient value for each said edge path;

5) selecting the greatest of said average pixel intensity gradient values as an input to a single fuzzy membership function to generate a plurality of input values relating said average pixel intensity gradient value to a plurality of degrees of intensity;

6) applying a plurality of inference rules in an output membership function that relate the plurality of intensity degrees to a corresponding plurality of edginess degrees and generate a plurality of output values that are related to a degree to which said center pixel represents an edge in said image;

7) combining said plurality of output values using a weighted averaging analysis comprising an averaging union of truncated output singletons to assign a crisp edginess value to said center pixel;

8) assigning a new edginess based gray level value to said pixel by multiplying an original gray level value of said selected pixel by said crisp edginess value, said new edginess based gray level value being proportional to an edginess degree of said selected pixel; and

,

9) repeating steps (1)-(8) for additional pixels in said image.

7. The computer-based method of claim 6, wherein four edge paths are identified that pass through said pixel.

8. The computer-based method of claim 6, wherein three of said input values, three of said inference rules and three of said output values are employed;

said input values being small, medium and large;

said output values being no edge, mild edge and edge; and

said inference rules being if the average pixel intensity gradient value is small, the pixel is not an edge;

if the average pixel intensity gradient value is medium, the pixel is a mild edge; and

, if the average pixel intensity gradient value is large, the pixel is an edge.

9. A computer system for detecting one or more edges in a multiple pixel digital image comprising:

a processor;

an operating memory interfaced to and readable by said processor;

an external source of multiple pixel digital gray scale images to be analyzed for edges; and

an image edge detection application 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 detecting edges in said image, said process steps comprising the steps of;

1) retrieving an image to be analyzed from said source of images;

2) selecting a pixel in said image to be analyzed;

3) identifying a plurality of edge paths which pass through said selected pixel;

4) calculating an average pixel intensity gradient value for each of said edge paths by comparing a gray level intensity of pixels on one side of each of said edge paths to a gray level intensity of pixels on an opposite side of each of said edge paths;

5) selecting the greatest of said average pixel intensity gradient values of said edge paths as an input to a single fuzzy membership function and generating with said function, a plurality of output values that are related to a degree to which said pixel represents an edge in said image;

6) combining said plurality of output values using a weighted averaging analysis comprising an averaging union of truncated output singletons to assign a crisp edginess value to said pixel;

7) assigning a new edginess based gray level value to said pixel by multiplying an original gray level value of said selected pixel by said crisp edginess value, said new edginess based gray level value being proportional to an edginess degree of said selected pixel; and

,

8) repeating steps (2)-(7) for additional pixels in said image.

10. The computer system of claim 9, wherein said application identifies four edge paths that pass through said pixel.

11. The computer system of claim 9, wherein said application calculates said average pixel intensity gradient value by:

selecting an n×

n pixel window, where n is an odd number greater than or equal to 3 and said pixel to be analyzed is located at a center of said window;

calculating a first, average pixel intensity value of pixels in said window on a first side of said edge path;

calculating a second, average pixel intensity value of pixels in said window on a second, opposite side of said edge path; and

,

calculating a difference between said first and second values to obtain said average pixel intensity gradient value.

12. The computer system of claim 9, wherein said application carries out said step of generating a plurality of output values with said single membership function by:

employing an input membership function to generate a plurality of input values relating said average pixel intensity gradient value to a plurality of degrees of intensity;

applying a plurality of inference rules in an output membership function that relate the plurality of intensity degrees to a corresponding plurality of edginess degrees and thereby generate said plurality of output values.

13. The computer-based method of claim 12, wherein three of said input values, three of said inference rules and three of said output values are employed;

said input values being small, medium and large;

said output values being no edge, mild edge and edge; and

said inference rules being if the average pixel intensity gradient value is small, the pixel is not an edge;

if the average pixel intensity gradient value is medium, the pixel is a mild edge; and

, if the average pixel intensity gradient value is large, the pixel is an edge.

14. A computer system for detecting one or more edges in a multiple pixel digital image comprising:

a processor;

an operating memory interfaced to and readable by said processor;

an external source of multiple pixel digital gray scale images to be analyzed for edges; and

,

an image edge detection application 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 detecting edges in said image, said process steps comprising the steps of;

1) retrieving an image to be analyzed from said source of images;

2) selecting a pixel in said image to be analyzed;

3) selecting an n×

n pixel window, where n is an odd number greater than or equal to 3 and said window includes a center pixel, wherein said center pixel is said pixel to be analyzed;

4) identifying a plurality of edge paths that run through said center pixel and divide said window into first and second groups of pixels;

5) for each of said edge paths, calculating a first, average pixel intensity value of pixels in said first group and a second, average pixel intensity value of pixels in said second group; and

, calculating a difference between said first and second values to obtain an average pixel intensity gradient value for each said edge path;

6) selecting the greatest of said average pixel intensity gradient values as an input to a single fuzzy membership function to generate a plurality of input values relating said average pixel intensity gradient value to a plurality of degrees of intensity;

7) applying a plurality of inference rules in an output membership function that relate the plurality of intensity degrees to a corresponding plurality of edginess degrees and generate a plurality of output values that are related to a degree to which said center pixel represents an edge in said image;

8) combining said plurality of output values using a weighted averaging analysis comprising an averaging union of truncated output singletons to assign a crisp edginess value to said center pixel;

9) assigning a new edginess based gray level value to said pixel by multiplying an original gray level value of said selected pixel by said crisp edginess value, said new edginess based gray level value being proportional to an edginess degree of said selected pixel; and

,

10) repeating steps (2)-(9) for additional pixels in said image.

15. The computer system of claim 14, wherein said application identifies four edge paths that pass through said pixel.

16. The computer-based method of claim 14, wherein three of said input values, three of said inference rules and three of said output values are employed;

said input values being small, medium and large;

said output values being no edge, mild edge and edge; and

said inference rules being if the average pixel intensity gradient value is small, the pixel is not an edge;

if the average pixel intensity gradient value is medium, the pixel is a mild edge; and

, if the average pixel intensity gradient value is large, the pixel is an edge.