Segmentation of digital images

• US 6,963,664 B2
• Filed: 09/04/2001
• Issued: 11/08/2005
• Est. Priority Date: 09/07/2000
• Status: Expired due to Fees

• Current Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Ernst, Fabian Edgar, Wilinski, Piotr, Braspenning, Ralph Antonius Cornelius, Van Overveld, Cornelius Wilhelmus Antonius Marie
• Primary Examiner(s): Ahmed, Samir
• Assistant Examiner(s): LE, BRIAN Q
• Application Number:
  US09/945,874
• Publication Number:
  US 20020048402A1
• Time in Patent Office: 1,526 Days
• Field of Search: 382/133, 382/171, 382173-206
• US Class Current: 382/173
• CPC Class Codes: G06T 2207/20041 Distance transform
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/155 involving morphological operators
• CPC Class Codes: G06T 7/181 involving edge growing; involving edge linking

Abstract

A method for segmenting a digital image composed of pixels, including determining hard border fragments in the digital image by means of an edge detection process, determining respective sides of each of said hard border fragments, and forming segments by determining for each pixel a closest side and by uniquely assigning each pixel of said digital image to a single segment, corresponding with the determined closest side to the respective pixel.

Claims

1. A method of segmenting a digital image (10) composed of pixels, the method comprising the steps of:

determining hard border fragments (a, b, c) in the digital image (10) by means of an edge detection process, comprising the steps of;

determining respective sides (I, II, III, IV, V, VI, VII) of each of said hard border fragments (a, b, c),

forming segments (A, B, C, D, E) by determining for each pixel a closest side (I, II, III, IV, V, VI, VII), and by assigning each pixel of said digital image (10) to a segment (A, B, C, D, E) corresponding with the determined closest side (I, II, III, IV, V, VI, VII) to the respective pixel;

determining boundaries of said formed segments, by determining borders for each segment by taking the respective hard border fragments (a, b, c) at least partially bounding respective segments (A, B, C, D, E),

determining for each segment soft border fragments essentially contiguous to said hard border fragments (a, b, c) and at least partially bounding respective segments (A, B, C, D, E), by determining a distance to a closest hard segment border fragment (a, b, c), and

determining digital image segments (A, B, C, D, E) bordered by respective determined hard border fragments (a, b, c) and said soft border fragments.

2. A method according to claim 1, the method further comprising the steps of:

associating an individual seed comprising seed points, to each of the determined sides,

assigning an unique identifier to each seed,

determining for each pixel a distance to a closest seed point using a distance determination rule and storing the distance for each pixel in a distance map (d(x,y)), and

determining for each pixel the closest seed based on the determined distance to a closest seed point and storing the identity for the determined closest seed for each pixel in an item buffer (b(x,y)).

3. A method according to claim 2, wherein the seed points of a seed are determined as the pixels of the image that are closest to a respective determined side.

4. A method according to claim 1, the method further comprising the steps of:

examining the formed segments for oversegmentation, and

removing redundant segments by merging.

5. A method according to claim 1, wherein the edge detection process is based on detecting high contrast border sections.

6. A computer program stored on a computer readable medium for enabling a computer processor to carry out the processing steps of:

determining hard border fragments (a, b, c) in the digital image (10) by means of an edge detection process, comprising the steps of;

determining respective sides (I, II, III, IV, V, VI, VII) of each of said hard border fragments (a, b, c),

forming segments (A, B, C, D, E) by determining for each pixel a closest side (I, II, III, IV, V, VI, VII), and by assigning each pixel of said digital image (10) to a segment (A, B, C, D, E) corresponding with the determined closest side (I, II, III, IV, V, VI, VII) to the respective pixel;

determining boundaries of said formed segments, by determining borders for each segment by taking the respective hard border fragments (a, b, c) at least partially bounding respective segments (A, B, C, D, E),

determining for each segment soft border fragments essentially contiguous to said hard border fragments (a, b, c) and at least partially bounding respective segments (A, B, C, D, E), by determining a distance to a closest hard segment border fragment (a, b, c), and

determining digital image segments (A, B, C, D, E) bordered by respective determined hard border fragments (a, b, c) and said soft border fragments.

7. A computer readable medium containing a computer program thereon, said computer programming operable for causing a computer to execute the steps of:

determining hard border fragments (a, b, c) in the digital image (10) by means of an edge detection process, comprising the steps of;

determining respective sides (I, II, III, IV, V, VI, VII) of each of said hard border fragments (a, b, c),

forming segments (A, B, C, D, E) by determining for each pixel a closest side (I, II, III, IV, V, VI, VII), and by assigning each pixel of said digital image (10) to a segment (A, B, C, D, E) corresponding with the determined closest side (I, II, III, IV, V, VI, VII) to the respective pixel;

determining boundaries of said formed segments, by determining borders for each segment by taking the respective hard border fragments (a, b, c) at least partially bounding respective segments (A, B, C, D, E),

determining for each segment soft border fragments essentially contiguous to said hard border fragments (a, b, c) and at least partially bounding respective segments (A, B, C, D, E), by determining a distance to a closest hard segment border fragment (a, b, c,), and

determining digital image segments (A, B, C, D, E) bordered by respective determined hard border fragments (a, b, c) and said soft border fragments.

8. A computer program stored on a computer readable medium for generating a signal said signal operable for executing the steps of:

determining hard border fragments (a, b, c) in the digital image (10) by means of an edge detection process, comprising the steps of;

determining respective sides (I, II, III, IV, V, VI, VII) of each of said hard border fragments (a, b, c),

forming segments (A, B, C, D, E) by determining for each pixel a closest side (I, II, III, IV, V, VI, VII), and by assigning each pixel of said digital image (10) to a segment (A, B, C, D, E) corresponding with the determined closest side (I, II, III, IV, V, VI, VII) to the respective pixel

determining boundaries of said formed segments, by determining borders for each segment by taking the respective hard border fragments (a, b, c) at least partially bounding respective segments (A, B, C, D, E),

determining for each segment soft border fragments essentially contiguous to said hard border fragments (a, b, c) and at least partially bounding respective segments (A, B, C, D, E), by determining a distance to a closest hard segment border fragment (a, b, c), and

determining digital image segments (A, B, C, D, E) bordered by respective determined hard border fragments (a, b, c) and said soft border fragments.

9. Device for segmenting a digital image, the device comprising:

input section (420) for receiving digital images;

means (410) for determining hard border fragments (a, b, c) in the digital image (10) by means of an edge detection process;

means (410) for determining respective sides (I, II, III, IV, V, VI, VII) of each of said hard border fragments (a, b, c),

means (410) for forming segments (A, B, C, D, E) by determining for each pixel a closest side (I, II, III, IV, V, VI, VII), and by assigning each pixel of said digital image (10) to a segment (A, B, C, D, E) corresponding with the determined closest side (I, II, III, IV, V, VI, VII) to the respective pixel,

means for determining boundaries of said formed segments, by determining borders for each segment by taking the respective hard border fragments (a, b, c) at least partially bounding respective segments (A, B, C, D, E),

means for determining for each segment soft border fragments essentially contiguous to said hard border fragments (a, b, c) and at least partially bounding respective segments (A, B, C, D, E), by determining a distance to a closest hard segment border fragment (a, b, c),

means for determining digital image segments (A, B, C, D, E) bordered by respective determined hard border fragments (a, b, c) and said soft border fragments; and

an output section (430) for providing segmented images.

10. Display apparatus comprising a device, said device comprising:

an input section (420) for receiving digital images;

means (410) for determining hard border fragments (a, b, c) in the digital image (10) by means of an edge detection process;

means (410) for determining respective sides (I, II, III, IV, V, VI, VII) of each of said hard border fragments (a, b, c),

means (410) for forming segments (A, B, C, D, E) by determining for each pixel a closest side (I, II, III, IV, V, VI, VII), and by assigning each pixel of said digital image (10) to a segment (A, B, C, D, E) corresponding with the determined closest side (I, II, III, IV, V, VI, VII) to the respective pixel,

means for determining boundaries of said formed segments, by determining borders for each segment by taking the respective hard border fragments (a, b, c) at least partially bounding respective segments (A, B, C, D, E),

means for determining for each segment soft border fragments essentially contiguous to said hard border fragments (a, b, c) and at least partially bounding respective segments (A, B, C, D, E), by determining a distance to a closest hard segment border fragment (a, b, c),

means for determining digital image segments (A, B, C, D, E) bordered by respective determined hard border fragments (a, b, c) and said soft border fragments; and

an output section (430) for providing segmented images.