Method and apparatus for digital image segmentation

• US 6,778,698 B1
• Filed: 06/09/2000
• Issued: 08/17/2004
• Est. Priority Date: 06/11/1999
• Status: Expired due to Term

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: PTS Corporation
• Inventors: Prakash, Adityo, Chen, John S., Ratner, Edward R., Cook, David L.
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): SUKHAPHADHANA, CHRISTOPHER T
• Application Number:
  US09/591,438
• Time in Patent Office: 1,530 Days
• Field of Search: 382/162, 382/164, 382/173, 382/242, 358/1.9
• US Class Current: 382/164
• CPC Class Codes: G06V 10/267 by performing operations on regions, e.g. growing, shrinking or watersheds

Abstract

An image segmenter uses one or more techniques to accurately segment an image, including the use of a progressive flood fill to fill incompletely bounded segments, the use of a plurality of scaled transformations and guiding segmentation at one scale with segmentation results from another scale, detecting edges using a composite image that is a composite of multiple color planes, generating edge chains using multiple classes of edge pixels, generating edge chains using the plurality of scaled transformations, and/or filtering spurious edges at one scale based on edges detected at another scale.

Claims

1. A method of detecting edges in a digital image, where the digital image comprises a rectangular array of pixels each having a pixel location and a pixel color value and where an edge represents a transition in the array between the pixels representing one segment of the digital image and pixels representing another segment of the digital image, the method comprising the steps of:

identifying edge points of the digital image, where an edge point is a point in the array of pixels between point locations that are pixel locations;

locating each edge point at the center of a rectangle defined by four mutually adjacent pixels in the pixel array;

identifying a plurality of classes of edge points, including a more certain class of edge points and a less certain class of edge points where an edge point in the more certain class is more likely to be representative of an edge of a segment of the digital image than an edge point in the less certain class; and

identifying edges by linking adjacent edge points of the more certain class for forming edge point chains;

when gaps are present between edge point chains, identifying edge points in the less certain class to span gaps in the edge point chains; and

using the edge point chains as representations of the edges in the digital image.

2. The method of claim 1 where the plurality of classes include more than two classes and each class has a relative certainty associated with the edge points in the class with the relative certainties of each class being orderable and distinct from the relative certainties of other classes, the method further comprising a step of identifying edge points in a class for use in joining edge chains, before edge points in less certain classes are used, but after edge points in more certain classes are used.

3. A method of segmenting a digital image into a plurality of segments defined by edges of objects in the digital image, where the digital image comprises an array of pixels each having a pixel location and a pixel color value and where an edge represents a transition in the array between the pixels representing one segment of the digital image and pixels representing another segment of the digital image, the method comprising the steps of:

identifying a set of edge chains, where an edge chain represents a border between two segments and at least one edge chain is not part of a closed loop enclosing and defining a segment;

setting a maximum allowable threshold for gaps in edge chains;

positioning a first brush in a first location in the array such that the first brush does not overlap any edge chains, wherein a brush is a pixel window movable over the array and wherein the first brush is a pixel window of a size such that the first brush cannot pass through a gap in edge chains that is no wider than the maximum allowable threshold without the first brush overlapping an edge chain;

associating pixels with a segment where each pixel associated with the segment is a pixel reachable by the first brush from the first location without the first brush having to pass through a gap smaller than a width of the first brush;

associating other pixels with other segments using the first brush positioned in second and subsequent locations in the array; and

repeating the steps of positioning and associating using a second brush that is smaller than the first brush, to associate pixels that were not already associated in the steps of positioning and associating.

4. The method of claim 3, wherein the first brush is a square pixel window with each side of the square being a number of pixels one greater than the maximum allowable threshold.

5. The method of claim 3, wherein the step of repeating is performed with successively smaller brushes until a brush with an area of a single pixel is used.

6. The method of claim 5, further comprising a step of assigning unassigned pixels to segments when unassigned pixels remain after the processes of repeating have been performed for each brush.