Method and apparatus for digital image segmentation using an iterative method

• US 6,803,920 B2
• Filed: 07/31/2001
• Issued: 10/12/2004
• Est. Priority Date: 08/04/2000
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: PTS Corporation
• Inventors: Gossett, Phil, Ratner, Edward
• Primary Examiner(s): Luu, Matthew
• Application Number:
  US09/919,671
• Publication Number:
  US 20030002732A1
• Time in Patent Office: 1,169 Days
• Field of Search: 345/589, 345/591, 345/593, 345/597, 345/598, 382/164, 382/171, 382/173
• US Class Current: 345/591
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 5/20 using local operators
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation
• CPC Class Codes: G06T 7/90 Determination of colour characteristics

Abstract

A digital image is divided into segments, wherein the digital image comprises an array of pixels each having a pixel location and a pixel color value. A method comprises obtaining an image frame comprising an array of pixels each having a pixel color value, assigning an initial segment identifier to each pixel in the image frame independent of each pixel'"'"'s pixel color value, testing, using an appropriateness test, pixels for possible reassignment from a current segment to a neighboring segment, and if the appropriateness test indicates a pixel should be reassigned, reassigning the segment identifier of the pixel.

Claims

1. A method of dividing a digital image into segments, wherein the digital image comprises an array of pixels each having a pixel location and a pixel color value, the method comprising:

obtaining an image frame comprising an array of pixels each having a pixel color value;

assigning an initial segment identifier to each pixel in the image frame independent of each pixel'"'"'s pixel color value;

testing, using an appropriateness test, pixels for possible reassignment from a current segment to a neighboring segment; and

if the appropriateness test indicates a pixel should be reassigned, reassigning the segment identifier of the pixel.

2. The method of claim 1, further comprising reassigning the pixel color of outlier pixels to the representative color of the immediately adjacent pixels.

3. The method of claim 1, wherein the pixel segment identifier is based upon the pixel'"'"'s location with a logical grid, the logical grid having a unique segment identifier corresponding initially to a logical grid section.

4. The method of claim 1, wherein reassigning comprises:

obtaining a boundary pixel, wherein a boundary pixel is a pixel located proximate to a pixel having a different segment identifier than that of the boundary pixel;

considering pixel values in a neighborhood adjacent to the boundary pixel;

logically grouping the neighboring pixels by commonality of segment identifiers;

computing a representative color value for each pixel group; and

reassigning the segment identifier of the boundary pixel to match the group whose representative color value most closely matches the color of the boundary pixel.

5. The method of claim 1, further comprising repeating the steps of testing and reassigning until the segment boundaries converge such that the testing step results in no possible reassignments.

6. The method of claim 1, further comprising repeating the steps of testing and reassigning until the segment boundaries converge such that the testing step results in less than a threshold amount of reassignment.

7. The method of claim 6, wherein the threshold amount of reassignment is measured as a predetermined number of pixels.

8. A method of dividing a digital image into segments, wherein the digital image comprises an array of pixels each having a pixel location and a pixel color value, the method comprising:

obtaining an image frame comprising an array of pixels each having a pixel color value;

overlaying a logical grid over the image data such that initially each subsection of the grid encompasses at least two pixels; and

adjusting the grid subsection boundaries to create at least one segment.

9. The method of claim 8, wherein moving further comprises the steps of:

obtaining a boundary pixel;

considering pixel values in the grid subsections adjacent to and including the boundary pixel;

computing a representative pixel color value for each considered grid subsection; and

adjusting the grid subsection boundaries such that the considered boundary pixel is associated with the grid subsection with the closest color value to the boundary pixel'"'"'s color value.

10. The method of claim 8, the method further comprising reassigning the pixel color of outlier pixels to a representative color of immediately adjacent pixels.

11. The method of claim 8, wherein considering the pixels comprises considering only the pixels within a given neighborhood of the boundary pixel.