Method and apparatus for digital image segmentation

Claim 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.

Claim 2

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.

Claim 4

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.

Claim 5

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.