[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

| Region Segmentation Algorithms |

## Classes
class | SeedRgDirectValueFunctor
| Statistics functor to be used for seeded region growing. More...
## Functions
template<... >
void | seededRegionGrowing (...)
| Region Segmentation by means of Seeded Region Growing.
template<... >
void | seededRegionGrowing3D (...)
| Three-dimensional Region Segmentation by means of Seeded Region Growing.
template<... >
unsigned int | watersheds (...)
| Region Segmentation by means of the watershed algorithm.
template<... >
unsigned int | watersheds3D (...)
| Region Segmentation by means of the watershed algorithm.

## Detailed Description

Region growing, watersheds, and voronoi tesselation

Region segmentation and voronoi tesselation

## Function Documentation

template<... >
void vigra::seededRegionGrowing | ( |  | ... | ) |

Region Segmentation by means of Seeded Region Growing.

This algorithm implements seeded region growing as described in

R. Adams, L. Bischof: "<em> Seeded Region Growing</em>", IEEE Trans. on Pattern Analysis and Maschine Intelligence, vol 16, no 6, 1994, and

Ullrich Köthe: Primary Image Segmentation, in: G. Sagerer, S. Posch, F. Kummert (eds.): Mustererkennung 1995, Proc. 17. DAGM-Symposium, Springer 1995

The seed image is a partly segmented image which contains uniquely labeled regions (the seeds) and unlabeled pixels (the candidates, label 0). Seed regions can be as large as you wish and as small as one pixel. If there are no candidates, the algorithm will simply copy the seed image into the output image. Otherwise it will aggregate the candidates into the existing regions so that a cost function is minimized. Candidates are taken from the neighborhood of the already assigned pixels, where the type of neighborhood is determined by parameter `neighborhood` which can take the values `FourNeighborCode()` (the default) or `EightNeighborCode()`. The algorithm basically works as follows (illustrated for 4-neighborhood, but 8-neighborhood works in the same way):

1. Find all candidate pixels that are 4-adjacent to a seed region. Calculate the cost for aggregating each candidate into its adajacent region and put the candidates into a priority queue.

2. While( priority queue is not empty and termination criterion is not fulfilled)

   1. Take the candidate with least cost from the queue. If it has not already been merged, merge it with it's adjacent region.

   2. Put all candidates that are 4-adjacent to the pixel just processed into the priority queue.

`SRGType` can take the following values:

`CompleteGrow`
  produce a complete tesselation of the volume (default).
`KeepContours`
  keep a 1-voxel wide unlabeled contour between all regions.
`StopAtThreshold`
  stop when the boundary indicator values exceed the threshold given by parameter `max_cost`.
`KeepContours | StopAtThreshold`
  keep 1-voxel wide contour and stop at given `max_cost`.

The cost is determined jointly by the source image and the region statistics functor. The source image contains feature values for each pixel which will be used by the region statistics functor to calculate and update statistics for each region and to calculate the cost for each candidate. The `RegionStatisticsArray` must be compatible to the ArrayOfRegionStatistics functor and contains an array of statistics objects for each region. The indices must correspond to the labels of the seed regions. The statistics for the initial regions must have been calculated prior to calling `seededRegionGrowing()` (for example by means of inspectTwoImagesIf()).

For each candidate `x` that is adjacent to region `i`, the algorithm will call `stats[i].cost(as(x))` to get the cost (where `x` is a `SrcImageIterator` and `as` is the SrcAccessor). When a candidate has been merged with a region, the statistics are updated by calling `stats[i].operator()(as(x))`. Since the `RegionStatisticsArray` is passed by reference, this will overwrite the original statistics.

If a candidate could be merged into more than one regions with identical cost, the algorithm will favour the nearest region. If `StopAtThreshold` is active, and the cost of the current candidate at any point in the algorithm exceeds the optional `max_cost` value (which defaults to `NumericTraits<double>::max()`), region growing is aborted, and all voxels not yet assigned to a region remain unlabeled.

In some cases, the cost only depends on the feature value of the current pixel. Then the update operation will simply be a no-op, and the `cost()` function returns its argument. This behavior is implemented by the SeedRgDirectValueFunctor. With `SRGType == KeepContours`, this is equivalent to the watershed algorithm.

Declarations:

pass arguments explicitly:

        namespace vigra {
            template <class SrcImageIterator, class SrcAccessor,
                      class SeedImageIterator, class SeedAccessor,
                      class DestImageIterator, class DestAccessor,
                      class RegionStatisticsArray, class Neighborhood>
            void
            seededRegionGrowing(SrcImageIterator srcul, SrcImageIterator srclr, SrcAccessor as,
                                SeedImageIterator seedsul, SeedAccessor aseeds,
                                DestImageIterator destul, DestAccessor ad,
                                RegionStatisticsArray & stats,
                                SRGType srgType = CompleteGrow,
                                Neighborhood neighborhood = FourNeighborCode(),
                                double max_cost = NumericTraits<double>::max());
        }

use argument objects in conjunction with Argument Object Factories :

        namespace vigra {
            template <class SrcImageIterator, class SrcAccessor,
                      class SeedImageIterator, class SeedAccessor,
                      class DestImageIterator, class DestAccessor,
                      class RegionStatisticsArray, class Neighborhood>
            void
            seededRegionGrowing(triple<SrcImageIterator, SrcImageIterator, SrcAccessor> src,
                                pair<SeedImageIterator, SeedAccessor> seeds,
                                pair<DestImageIterator, DestAccessor> dest,
                                RegionStatisticsArray & stats,
                                SRGType srgType = CompleteGrow,
                                Neighborhood neighborhood = FourNeighborCode(),
                                double max_cost = NumericTraits<double>::max());
        }

Usage:

#include <vigra/seededregiongrowing.hxx>
Namespace: vigra

Example: implementation of the voronoi tesselation

        vigra::BImage points(w,h);
        vigra::FImage dist(x,y);

        // empty edge image
        points = 0;
        dist = 0;

        int max_region_label = 100;

        // throw in some random points:
        for(int i = 1; i <= max_region_label; ++i)
               points(w * rand() / RAND_MAX , h * rand() / RAND_MAX) = i;

        // calculate Euclidean distance transform
        vigra::distanceTransform(srcImageRange(points), destImage(dist), 2);

        // init statistics functor
        vigra::ArrayOfRegionStatistics<vigra::SeedRgDirectValueFunctor<float> >
                                                  stats(max_region_label);

        // find voronoi region of each point
       vigra:: seededRegionGrowing(srcImageRange(dist), srcImage(points),
                                   destImage(points), stats);

Required Interface:

        SrcImageIterator src_upperleft, src_lowerright;
        SeedImageIterator seed_upperleft;
        DestImageIterator dest_upperleft;

        SrcAccessor src_accessor;
        SeedAccessor seed_accessor;
        DestAccessor dest_accessor;

        RegionStatisticsArray stats;

        // calculate costs
        RegionStatisticsArray::value_type::cost_type cost =
            stats[seed_accessor(seed_upperleft)].cost(src_accessor(src_upperleft));

        // compare costs
        cost < cost;

        // update statistics
        stats[seed_accessor(seed_upperleft)](src_accessor(src_upperleft));

        // set result
        dest_accessor.set(seed_accessor(seed_upperleft), dest_upperleft);

Further requirements are determined by the `RegionStatisticsArray`.

template<... >
void vigra::seededRegionGrowing3D | ( |  | ... | ) |

Three-dimensional Region Segmentation by means of Seeded Region Growing.

This algorithm implements seeded region growing as described in

The seed image is a partly segmented multi-dimensional array which contains uniquely labeled regions (the seeds) and unlabeled voxels (the candidates, label 0). Seed regions can be as large as you wish and as small as one voxel. If there are no candidates, the algorithm will simply copy the seed array into the output array. Otherwise it will aggregate the candidates into the existing regions so that a cost function is minimized. Candidates are taken from the neighborhood of the already assigned pixels, where the type of neighborhood is determined by parameter `neighborhood` which can take the values `NeighborCode3DSix()` (the default) or `NeighborCode3DTwentySix()`. The algorithm basically works as follows (illustrated for 6-neighborhood, but 26-neighborhood works in the same way):

1. Find all candidate pixels that are 6-adjacent to a seed region. Calculate the cost for aggregating each candidate into its adajacent region and put the candidates into a priority queue.

2. While( priority queue is not empty)

   1. Take the candidate with least cost from the queue. If it has not already been merged, merge it with it's adjacent region.

   2. Put all candidates that are 4-adjacent to the pixel just processed into the priority queue.

`SRGType` can take the following values:

`CompleteGrow`
  produce a complete tesselation of the volume (default).
`KeepContours`
  keep a 1-voxel wide unlabeled contour between all regions.
`StopAtThreshold`
  stop when the boundary indicator values exceed the threshold given by parameter `max_cost`.
`KeepContours | StopAtThreshold`
  keep 1-voxel wide contour and stop at given `max_cost`.

The cost is determined jointly by the source array and the region statistics functor. The source array contains feature values for each pixel which will be used by the region statistics functor to calculate and update statistics for each region and to calculate the cost for each candidate. The `RegionStatisticsArray` must be compatible to the ArrayOfRegionStatistics functor and contains an array of statistics objects for each region. The indices must correspond to the labels of the seed regions. The statistics for the initial regions must have been calculated prior to calling `seededRegionGrowing3D()`

For each candidate `x` that is adjacent to region `i`, the algorithm will call `stats[i].cost(as(x))` to get the cost (where `x` is a `SrcImageIterator` and `as` is the SrcAccessor). When a candidate has been merged with a region, the statistics are updated by calling `stats[i].operator()(as(x))`. Since the `RegionStatisticsArray` is passed by reference, this will overwrite the original statistics.

If a candidate could be merged into more than one regions with identical cost, the algorithm will favour the nearest region. If `StopAtThreshold` is active, and the cost of the current candidate at any point in the algorithm exceeds the optional `max_cost` value (which defaults to `NumericTraits<double>::max()`), region growing is aborted, and all voxels not yet assigned to a region remain unlabeled.

In some cases, the cost only depends on the feature value of the current voxel. Then the update operation will simply be a no-op, and the `cost()` function returns its argument. This behavior is implemented by the SeedRgDirectValueFunctor.

Declarations:

pass arguments explicitly:

        namespace vigra {
            template <class SrcImageIterator, class Shape, class SrcAccessor,
                      class SeedImageIterator, class SeedAccessor,
                      class DestImageIterator, class DestAccessor,
                      class RegionStatisticsArray, class Neighborhood>
            void
            seededRegionGrowing3D(SrcImageIterator srcul, Shape shape, SrcAccessor as,
                                  SeedImageIterator seedsul, SeedAccessor aseeds,
                                  DestImageIterator destul, DestAccessor ad,
                                  RegionStatisticsArray & stats,
                                  SRGType srgType = CompleteGrow,
                                  Neighborhood neighborhood = NeighborCode3DSix(),
                                  double max_cost = NumericTraits<double>::max());
        }

use argument objects in conjunction with Argument Object Factories :

        namespace vigra {
            template <class SrcImageIterator, class Shape, class SrcAccessor,
                      class SeedImageIterator, class SeedAccessor,
                      class DestImageIterator, class DestAccessor,
                      class RegionStatisticsArray, class Neighborhood>
            void
            seededRegionGrowing3D(triple<SrcImageIterator, Shape, SrcAccessor> src,
                                  pair<SeedImageIterator, SeedAccessor> seeds,
                                  pair<DestImageIterator, DestAccessor> dest,
                                  RegionStatisticsArray & stats,
                                  SRGType srgType = CompleteGrow,
                                  Neighborhood neighborhood = NeighborCode3DSix(),
                                  double max_cost = NumericTraits<double>::max());
        }

template<... >
unsigned int vigra::watersheds | ( |  | ... | ) |

Region Segmentation by means of the watershed algorithm.

This function implements the union-find version of the watershed algorithms as described in

J. Roerdink, R. Meijster: "The watershed transform: definitions, algorithms, and parallelization stretegies", Fundamenta Informaticae, 41:187-228, 2000

The source image is a boundary indicator such as the gradient magnitude of the trace of the boundaryTensor(). Local minima of the boundary indicator are used as region seeds, and all other pixels are recursively assigned to the same region as their lowest neighbor. Pass vigra::EightNeighborCode or vigra::FourNeighborCode to determine the neighborhood where pixel values are compared. The pixel type of the input image must be `LessThanComparable`. The function uses accessors.

Note that VIGRA provides an alternative implementaion of the watershed transform via seededRegionGrowing(). It is slower, but handles plateaus better and allows to keep a one pixel wide boundary between regions.

Declarations:

pass arguments explicitly:

        namespace vigra {
            template <class SrcIterator, class SrcAccessor,
                      class DestIterator, class DestAccessor,
                      class Neighborhood = EightNeighborCode>
            unsigned int
            watersheds(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
                       DestIterator upperleftd, DestAccessor da,
                       Neighborhood neighborhood = EightNeighborCode())
        }

use argument objects in conjunction with Argument Object Factories :

        namespace vigra {
            template <class SrcIterator, class SrcAccessor,
                      class DestIterator, class DestAccessor,
                      class Neighborhood = EightNeighborCode>
            unsigned int
            watersheds(triple<SrcIterator, SrcIterator, SrcAccessor> src,
                       pair<DestIterator, DestAccessor> dest,
                       Neighborhood neighborhood = EightNeighborCode())
        }

Usage:

#include <vigra/watersheds.hxx>
Namespace: vigra

Example: watersheds of the gradient magnitude.

        vigra::BImage in(w,h);
        ... // read input data

        vigra::FImage gradx(x,y), grady(x,y), gradMag(x,y);
        gaussianGradient(srcImageRange(src), destImage(gradx), destImage(grady), 3.0);
        combineTwoImages(srcImageRange(gradx), srcImage(grady), destImage(gradMag),
                         vigra::MagnitudeFunctor<float>());

        // the pixel type of the destination image must be large enough to hold
        // numbers up to 'max_region_label' to prevent overflow
        vigra::IImage labeling(x,y);
        int max_region_label = watersheds(srcImageRange(gradMag), destImage(labeling));

Required Interface:

        SrcImageIterator src_upperleft, src_lowerright;
        DestImageIterator dest_upperleft;

        SrcAccessor src_accessor;
        DestAccessor dest_accessor;

        // compare src values
        src_accessor(src_upperleft) <= src_accessor(src_upperleft)

        // set result
        int label;
        dest_accessor.set(label, dest_upperleft);

template<... >
unsigned int vigra::watersheds3D | ( |  | ... | ) |

Region Segmentation by means of the watershed algorithm.

Declarations:

pass arguments explicitly:

        namespace vigra {
            template <class SrcIterator, class SrcAccessor,class SrcShape,
                      class DestIterator, class DestAccessor,
                      class Neighborhood3D>
            unsigned int watersheds3D(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
                                      DestIterator d_Iter, DestAccessor da,
                                      Neighborhood3D neighborhood3D);
        }

use argument objects in conjunction with Argument Object Factories :

        namespace vigra {
            template <class SrcIterator, class SrcAccessor,class SrcShape,
                      class DestIterator, class DestAccessor,
                      class Neighborhood3D>
            unsigned int watersheds3D(triple<SrcIterator, SrcShape, SrcAccessor> src,
                                      pair<DestIterator, DestAccessor> dest,
                                      Neighborhood3D neighborhood3D);
        }

use with 3D-Six-Neighborhood:

        namespace vigra {

            template <class SrcIterator, class SrcAccessor,class SrcShape,
                      class DestIterator, class DestAccessor>
            unsigned int watersheds3DSix(triple<SrcIterator, SrcShape, SrcAccessor> src,
                                         pair<DestIterator, DestAccessor> dest);

        }

use with 3D-TwentySix-Neighborhood:

        namespace vigra {

            template <class SrcIterator, class SrcAccessor,class SrcShape,
                      class DestIterator, class DestAccessor>
            unsigned int watersheds3DTwentySix(triple<SrcIterator, SrcShape, SrcAccessor> src,
                                               pair<DestIterator, DestAccessor> dest);

        }

This function implements the union-find version of the watershed algorithms as described in

J. Roerdink, R. Meijster: "The watershed transform: definitions, algorithms, and parallelization stretegies", Fundamenta Informaticae, 41:187-228, 2000

The source volume is a boundary indicator such as the gradient magnitude of the trace of the boundaryTensor(). Local minima of the boundary indicator are used as region seeds, and all other voxels are recursively assigned to the same region as their lowest neighbor. Pass vigra::NeighborCode3DSix or vigra::NeighborCode3DTwentySix to determine the neighborhood where voxel values are compared. The voxel type of the input volume must be `LessThanComparable`. The function uses accessors.

...probably soon in VIGRA: Note that VIGRA provides an alternative implementaion of the watershed transform via seededRegionGrowing3D(). It is slower, but handles plateaus better and allows to keep a one pixel wide boundary between regions.

Usage:

#include <vigra/watersheds3D.hxx>
Namespace: vigra

Example: watersheds3D of the gradient magnitude.

        typedef vigra::MultiArray<3,int> IntVolume;
        typedef vigra::MultiArray<3,double> DVolume;
        DVolume src(DVolume::difference_type(w,h,d));
        IntVolume dest(IntVolume::difference_type(w,h,d));

        float gauss=1;

        vigra::MultiArray<3, vigra::TinyVector<float,3> > temp(IntVolume::difference_type(w,h,d));
        vigra::gaussianGradientMultiArray(srcMultiArrayRange(vol),destMultiArray(temp),gauss);

        IntVolume::iterator temp_iter=temp.begin();
        for(DVolume::iterator iter=src.begin(); iter!=src.end(); ++iter, ++temp_iter)
            *iter = norm(*temp_iter);

        // find 6-connected regions
        int max_region_label = vigra::watersheds3DSix(srcMultiArrayRange(src), destMultiArray(dest));

        // find 26-connected regions
        max_region_label = vigra::watersheds3DTwentySix(srcMultiArrayRange(src), destMultiArray(dest));

Required Interface:

        SrcIterator src_begin;
        SrcShape src_shape;
        DestIterator dest_begin;

        SrcAccessor src_accessor;
        DestAccessor dest_accessor;

        // compare src values
        src_accessor(src_begin) <= src_accessor(src_begin)

        // set result
        int label;
        dest_accessor.set(label, dest_begin);

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de) Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany | html generated using doxygen and Python vigra 1.7.1 (3 Dec 2010)