Superpixel Creation

Modules
	Parallel Processing

Classes
class	SeedOptions
	Options object for generateWatershedSeeds(). More...
class	SeedRgDirectValueFunctor< Value >
	Statistics functor to be used for seeded region growing. More...
struct	SlicOptions
	Options object for slicSuperpixels(). More...
class	WatershedOptions
	Options object for watershed algorithms. More...

Enumerations
enum	SRGType

Functions
template<... >
unsigned int	generateSlicSeeds (...)
	Generate seeds for SLIC superpixel computation in arbitrary dimensions. More...
template<... >
unsigned int	generateWatershedSeeds (...)
	Generate seeds for watershed computation and seeded region growing. More...
template<... >
void	seededRegionGrowing (...)
	Region Segmentation by means of Seeded Region Growing. More...
template<... >
void	seededRegionGrowing3D (...)
	Three-dimensional Region Segmentation by means of Seeded Region Growing. More...
template<... >
unsigned int	slicSuperpixels (...)
	Compute SLIC superpixels in arbitrary dimensions. More...
template<... >
unsigned int	unionFindWatershedsBlockwise (...)
	Blockwise union-find watersheds transform for MultiArrays and ChunkedArrays. More...
template<... >
unsigned int	watersheds3D (...)
	Region Segmentation by means of the watershed algorithm. More...
template<... >
Label	watershedsMultiArray (...)
	Watershed segmentation of an arbitrary-dimensional array. More...
template<... >
unsigned int	watershedsRegionGrowing (...)
	Region segmentation by means of a flooding-based watershed algorithm. More...
template<... >
unsigned int	watershedsUnionFind (...)
	Region segmentation by means of the union-find watershed algorithm. More...

Detailed Description

Watersheds, SLIC superpixels, and seeded region growing.

Enumeration Type Documentation

enum SRGType

Choose between different types of Region Growing

Function Documentation

unsigned int vigra::unionFindWatershedsBlockwise

(

...

)

Blockwise union-find watersheds transform for MultiArrays and ChunkedArrays.

Declaration:

namespace vigra { namespace blockwise {
    template <unsigned int N, class Data, class S1,
                              class Label, class S2>
    Label
    unionFindWatershedsBlockwise(MultiArrayView<N, Data, S1> data,
                                 MultiArrayView<N, Label, S2> labels,
                                 BlockwiseLabelOptions const & options);

    template <unsigned int N, class Data, class Label>
    Label
    unionFindWatershedsBlockwise(const ChunkedArray<N, Data>& data,
                                 ChunkedArray<N, Label>& labels,
                                 BlockwiseLabelOptions const & options = BlockwiseLabelOptions());

    // provide temporary directions storage
    template <unsigned int N, class Data, class Label>
    Label
    unionFindWatershedsBlockwise(const ChunkedArray<N, Data>& data,
                                 ChunkedArray<N, Label>& labels,
                                 BlockwiseLabelOptions const & options,
                                 ChunkedArray<N, unsigned short>& temporary_storage);
}}

The resulting labeling is equivalent to a labeling by watershedsUnionFind, that is, the components are the same but may have different ids. If temporary_storage is provided, this array is used for intermediate result storage. Otherwise, a newly created vigra::ChunkedArrayLazy is used.

Return: the number of labels assigned (=largest label, because labels start at one)

Usage:

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

Shape3 shape = Shape3(10);
Shape3 chunk_shape = Shape3(4);
ChunkedArrayLazy<3, int> data(shape, chunk_shape);
// fill data ...

ChunkedArrayLazy<3, size_t> labels(shape, chunk_shape);

unionFindWatershedsBlockwise(data, labels, IndirectNeighborhood);

Label vigra::watershedsMultiArray

(

...

)

Watershed segmentation of an arbitrary-dimensional array.

See also unionFindWatershedsBlockwise() for a parallel version of the watershed algorithm.

This function implements variants of the watershed algorithms described in

[1] L. Vincent and P. Soille: "Watersheds in digital spaces: An efficient algorithm based on immersion simulations", IEEE Trans. Patt. Analysis Mach. Intell. 13(6):583-598, 1991

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

The source array data is a boundary indicator such as the gaussianGradientMagnitude() or the trace of the boundaryTensor(), and the destination labels is a label array designating membership of each point in one of the regions found. Plateaus in the boundary indicator are handled via simple tie breaking strategies. Argument neighborhood specifies the connectivity between points and can be DirectNeighborhood (meaning 4-neighborhood in 2D and 6-neighborhood in 3D, default) or IndirectNeighborhood (meaning 8-neighborhood in 2D and 26-neighborhood in 3D).

The watershed variant to be applied can be selected in the WatershedOptions object: When you call WatershedOptions::regionGrowing() (default), the flooding algorithm from [1] is used. Alternatively, WatershedOptions::unionFind() uses the scan-line algorithm 4.7 from [2]. The latter is faster, but does not support any options (if you pass options nonetheless, they are silently ignored).

The region growing algorithm needs a seed for each region. Seeds can either be provided in the destination array labels (which will then be overwritten with the result) or computed automatically by an internal call to generateWatershedSeeds(). In the former case you have full control over seed placement, while the latter is more convenient. Automatic seed computation is performed when you provide seeding options via WatershedOptions::seedOptions() or when the array labels is empty (all zeros), in which case default seeding options are chosen. The destination image should be zero-initialized for automatic seed computation.

Further options to be specified via WatershedOptions are:

• keepContours(): Whether to keep a 1-pixel-wide contour (with label 0) between regions (otherwise, a complete grow is performed, i.e. all pixels are assigned to a region).
• stopAtThreshold(): Whether to stop growing when the boundaryness exceeds a threshold (remaining pixels keep label 0).
• biasLabel(): Whether one region (label) is to be preferred or discouraged by biasing its cost with a given factor (smaller than 1 for preference, larger than 1 for discouragement).

The option turboAlgorithm() is implied by method regionGrowing() (this is in contrast to watershedsRegionGrowing(), which supports an additional algorithm in 2D only).

watershedsMultiArray() returns the number of regions found (= the highest region label, because labels start at 1).

Declaration:

namespace vigra {
    template <unsigned int N, class T, class S1,
                              class Label, class S2>
    Label
    watershedsMultiArray(MultiArrayView<N, T, S1> const & data,
                         MultiArrayView<N, Label, S2> labels,  // may also hold input seeds
                         NeighborhoodType neighborhood = DirectNeighborhood,
                         WatershedOptions const & options = WatershedOptions());
}

Usage:

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

Example: watersheds of the gradient magnitude (the example works likewise for higher dimensions).

MultiArray<2, unsigned char> src(Shape2(w, h));
... // read input data

// compute gradient magnitude at scale 1.0 as a boundary indicator
MultiArray<2, float> gradMag(src.shape());
gaussianGradientMagnitude(srcImageRange(src), destImage(gradMag), 1.0);

// example 1
{
    // the pixel type of the destination image must be large enough to hold
    // numbers up to 'max_region_label' to prevent overflow
    MultiArray<2, unsigned int> labeling(src.shape());

    // call region-growing algorithm for 4-neighborhood, leave a 1-pixel boundary between
    // regions, and autogenerate seeds from all gradient minima where the magnitude is
    // less than 2.0.
    unsigned int max_region_label =
          watershedsMultiArray(gradMag, labeling, DirectNeighborhood,
                               WatershedOptions().keepContours()
                                  .seedOptions(SeedOptions().minima().threshold(2.0)));
}

// example 2
{
    MultiArray<2, unsigned int> labeling(src.shape());

    // compute seeds beforehand (use connected components of all pixels
    // where the gradient is below 4.0)
    unsigned int max_region_label = generateWatershedSeeds(gradMag, labeling,
                                                   SeedOptions().levelSets(4.0));

    // quantize the gradient image to 256 gray levels
    float m, M;
    gradMag.minmax(&m, &M);

    using namespace multi_math;
    MultiArray<2, unsigned char> gradMag256(255.0 / (M - m) * (gradMag - m));

    // call region-growing algorithm with 8-neighborhood,
    // since the data are 8-bit, a faster priority queue will be used
    watershedsMultiArray(gradMag256, labeling, IndirectNeighborhood);
}

// example 3
{
    MultiArray<2, unsigned int> labeling(src.shape());

    .. // put seeds in 'labeling', e.g. from an interactive labeling program,
       // make sure that label 1 corresponds to the background

    // bias the watershed algorithm so that the background is preferred
    // by reducing the cost for label 1 to 90%
    watershedsMultiArray(gradMag, labeling,
                         WatershedOptions().biasLabel(1, 0.9));
}

// example 4
{
    MultiArray<2, unsigned int> labeling(src.shape());

    // use the fast union-find algorithm with 4-neighborhood
    watershedsMultiArray(gradMag, labeling, WatershedOptions().unionFind());
}

Examples:

graph_agglomerative_clustering.cxx, and watershed.cxx.

void vigra::seededRegionGrowing

(

...

)

Region Segmentation by means of Seeded Region Growing.

This algorithm implements seeded region growing as described in

R. Adams, L. Bischof: "Seeded Region Growing", 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). The highest seed label found in the seed image is returned by the algorithm.

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 adjacent 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 SrcIterator 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 2D array views:

namespace vigra {
    template <class T1, class S1,
              class TS, class AS,
              class T2, class S2,
              class RegionStatisticsArray, class Neighborhood>
    TS
    seededRegionGrowing(MultiArrayView<2, T1, S1> const & src,
                        MultiArrayView<2, TS, AS> const & seeds,
                        MultiArrayView<2, T2, S2>         labels,
                        RegionStatisticsArray &           stats,
                        SRGType                           srgType = CompleteGrow,
                        Neighborhood                      n = FourNeighborCode(),
                        double                            max_cost = NumericTraits<double>::max());
}

show deprecated declarations

pass Image Iterators and Data Accessors :

namespace vigra {
    template <class SrcIterator, class SrcAccessor,
              class SeedImageIterator, class SeedAccessor,
              class DestIterator, class DestAccessor,
              class RegionStatisticsArray, class Neighborhood>
    typename SeedAccessor::value_type
    seededRegionGrowing(SrcIterator srcul, SrcIterator srclr, SrcAccessor as,
                        SeedImageIterator seedsul, SeedAccessor aseeds,
                        DestIterator 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 SrcIterator, class SrcAccessor,
              class SeedImageIterator, class SeedAccessor,
              class DestIterator, class DestAccessor,
              class RegionStatisticsArray, class Neighborhood>
    typename SeedAccessor::value_type
    seededRegionGrowing(triple<SrcIterator, SrcIterator, SrcAccessor> src,
                        pair<SeedImageIterator, SeedAccessor> seeds,
                        pair<DestIterator, 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

MultiArray<2, int>      points(w,h);
MultiArray<2, float>    dist(x,y);

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
distanceTransform(points, dist, 2);

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

// find voronoi region of each point (the point image is overwritten with the
// voronoi region labels)
seededRegionGrowing(dist, points, points, stats);

show deprecated examples

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:

SrcIterator src_upperleft, src_lowerright;
SeedImageIterator seed_upperleft;
DestIterator 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.

Examples:

voronoi.cxx.

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 adjacent 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 3D array views:

namespace vigra {
    template <class T1, class S1,
              class TS, class AS,
              class T2, class S2,
              class RegionStatisticsArray, class Neighborhood>
    void
    seededRegionGrowing3D(MultiArrayView<3, T1, S1> const & src,
                          MultiArrayView<3, TS, AS> const & seeds,
                          MultiArrayView<3, T2, S2>         labels,
                          RegionStatisticsArray &           stats,
                          SRGType                           srgType = CompleteGrow,
                          Neighborhood                      neighborhood = NeighborCode3DSix(),
                          double                            max_cost = NumericTraits<double>::max());
}

show deprecated declarations

pass MultiIterators and Data Accessors :

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());
}

Usage:

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

See seededRegionGrowing() for an example

unsigned int vigra::generateSlicSeeds

(

...

)

Generate seeds for SLIC superpixel computation in arbitrary dimensions.

The source array src must be a scalar boundary indicator such as the gradient magnitude. Seeds are initially placed on a regular Cartesian grid with spacing seedDist und then moved to the point with smallest boundary indicator within a search region of radius searchRadius around the initial position. The resulting points are then marked in the output array seeds by consecutive labels.

The function returns the number of selected seeds, which equals the largest seed label because labeling starts at 1.

Declaration:

use arbitrary-dimensional arrays:

namespace vigra {
    template <unsigned int N, class T, class S1,
                              class Label, class S2>
    unsigned int
    generateSlicSeeds(MultiArrayView<N, T, S1> const & src,
                      MultiArrayView<N, Label, S2>     seeds,
                      unsigned int                     seedDist,
                      unsigned int                     searchRadius = 1);
}

Usage:

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

MultiArray<2, RGBValue<float> > src(Shape2(w, h));
... // fill src image

// transform image to Lab color space
transformImage(srcImageRange(src), destImage(src), RGBPrime2LabFunctor<float>());

// compute image gradient magnitude at scale 1.0 as a boundary indicator
MultiArray<2, float> grad(src.shape());
gaussianGradientMagnitude(srcImageRange(src), destImage(grad), 1.0);

MultiArray<2, unsigned int>  seeds(src.shape());
int seedDistance = 15;

// place seeds on a grid with distance 15, but then move it to the lowest gradient
// poistion in a 3x3 window
generateSlicSeeds(grad, seeds, seedDistance);

For more details and examples see slicSuperpixels().

unsigned int vigra::slicSuperpixels

(

...

)

Compute SLIC superpixels in arbitrary dimensions.

This function implements the algorithm described in

R. Achanta et al.: "SLIC Superpixels Compared to State-of-the-Art Superpixel Methods", IEEE Trans. Patt. Analysis Mach. Intell. 34(11):2274-2281, 2012

The value type T of the source array src must provide the necessary functionality to compute averages and squared distances (i.e. it must fulfill the requirements of a LinearSpace and support squaredNorm(T const &)). This is true for all scalar types as well as vigra::TinyVector and vigra::RGBValue. The output array labels will be filled with labels designating membership of each point in one of the superpixel regions.

The output array can optionally contain seeds (which will be overwritten by the output) to give you full control over seed placement. If labels is empty, seeds will be created automatically by an internal call to generateSlicSeeds().

The parameter seedDistance specifies the radius of the window around each seed (or, more precisely, around the present regions centers) where the algorithm looks for potential members of the corresponding superpixel. It thus places an upper limit on the superpixel size. When seeds are computed automatically, this parameter also determines the grid spacing for seed placement.

The parameter intensityScaling is used to normalize (i.e. divide) the color/intensity difference before it is compared with the spatial distance. This corresponds to parameter m in equation (2) of the paper.

The options object can be used to specify the number of iterations (SlicOptions::iterations()) and an explicit minimal superpixel size (SlicOptions::minSize()). By default, the algorithm merges all regions that are smaller than 1/4 of the average superpixel size.

The function returns the number of superpixels, which equals the largest label because labeling starts at 1.

Declaration:

use arbitrary-dimensional arrays:

namespace vigra {
    template <unsigned int N, class T, class S1,
                              class Label, class S2,
              class DistanceType>
    unsigned int
    slicSuperpixels(MultiArrayView<N, T, S1> const &  src,
                    MultiArrayView<N, Label, S2>      labels,
                    DistanceType                      intensityScaling,
                    unsigned int                      seedDistance,
                    SlicOptions const &               options = SlicOptions());
}

Usage:

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

MultiArray<2, RGBValue<float> > src(Shape2(w, h));
... // fill src image

// transform image to Lab color space
transformMultiArray(srcMultiArrayRange(src), destMultiArray(src), RGBPrime2LabFunctor<float>());

MultiArray<2, unsigned int>  labels(src.shape());
int seedDistance = 15;
double intensityScaling = 20.0;

// compute seeds automatically, perform 40 iterations, and scale intensity differences
// down to 1/20 before comparing with spatial distances
slicSuperpixels(src, labels, intensityScaling, seedDistance, SlicOptions().iterations(40));

This works for arbitrary-dimensional arrays.

unsigned int vigra::generateWatershedSeeds

(

...

)

Generate seeds for watershed computation and seeded region growing.

The source image is a boundary indicator such as the gradient magnitude or the trace of the boundaryTensor(). Seeds are generally generated at locations where the boundaryness (i.e. the likelihood of the point being on the boundary) is very small. In particular, seeds can be placed by either looking for local minima (possibly including minimal plateaus) of the boundaryness, of by looking at level sets (i.e. regions where the boundaryness is below a threshold). Both methods can also be combined, so that only minima below a threshold are returned. The particular seeding strategy is specified by the options object (see SeedOptions).

The pixel type of the input image must be LessThanComparable. The pixel type of the output image must be large enough to hold the labels for all seeds. (typically, you will use UInt32). The function will label seeds by consecutive integers (starting from 1) and returns the largest label it used.

Pass IndirectNeighborhood or DirectNeighborhood (first form of the function) or vigra::EightNeighborCode or vigra::FourNeighborCode (second and third forms) to determine the neighborhood where pixel values are compared.

Declarations:

use arbitrary-dimensional arrays:

namespace vigra {
    template <unsigned int N, class T, class S1,
                              class Label, class S2>
    Label
    generateWatershedSeeds(MultiArrayView<N, T, S1> const & data,
                           MultiArrayView<N, Label, S2> seeds,
                           NeighborhoodType neighborhood = IndirectNeighborhood,
                           SeedOptions const & options = SeedOptions());
}

show deprecated declarations

pass Image Iterators and Data Accessors :

namespace vigra {
    template <class SrcIterator, class SrcAccessor,
              class DestIterator, class DestAccessor,
              class Neighborhood = EightNeighborCode>
    unsigned int
    generateWatershedSeeds(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
                           DestIterator upperleftd, DestAccessor da,
                           Neighborhood neighborhood = EightNeighborCode(),
                           SeedOptions const & options = SeedOptions());
}

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
    generateWatershedSeeds(triple<SrcIterator, SrcIterator, SrcAccessor> src,
                           pair<DestIterator, DestAccessor> dest,
                           Neighborhood neighborhood = EightNeighborCode(),
                           SeedOptions const & options = SeedOptions());
}

Usage:

#include <vigra/multi_watersheds.hxx> (MultiArray variant)
#include <vigra/watersheds.hxx> (deprecated variants)
Namespace: vigra

For detailed examples see watershedsMultiArray() and watershedsRegionGrowing().

unsigned int vigra::watershedsUnionFind

(

...

)

Region segmentation by means of the union-find watershed algorithm.

Note: This function is largely obsolete, watershedsMultiArray() should be preferred unless top speed is required.

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

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

The source image is a boundary indicator such as the gaussianGradientMagnitude() or 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 implementation of the watershed transform via watershedsRegionGrowing(). It is slower, but offers many more configuration options.

Declarations:

pass 2D array views:

namespace vigra {
    template <class T1, class S1,
              class T2, class S2,
              class Neighborhood>
    unsigned int
    watershedsUnionFind(MultiArrayView<2, T1, S1> const & src,
                        MultiArrayView<2, T2, S2> dest,
                        Neighborhood neighborhood = EightNeighborCode());
}

show deprecated declarations

pass Image Iterators and Data Accessors :

namespace vigra {
    template <class SrcIterator, class SrcAccessor,
              class DestIterator, class DestAccessor,
              class Neighborhood = EightNeighborCode>
    unsigned int
    watershedsUnionFind(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
    watershedsUnionFind(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.

MultiArray<2, float> in(w,h);
... // read input data

// compute gradient magnitude as boundary indicator
MultiArray<2, float> gradMag(w, h);
gaussianGradientMagnitude(src, gradMag, 3.0);

// the pixel type of the destination image must be large enough to hold
// numbers up to 'max_region_label' to prevent overflow
MultiArray<2, unsigned int> labeling(w,h);
unsigned int max_region_label = watershedsUnionFind(gradMag, labeling);

show deprecated examples

Example: watersheds of the gradient magnitude.

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

// compute gradient magnitude as boundary indicator
vigra::FImage gradMag(w, h);
gaussianGradientMagnitude(srcImageRange(src), destImage(gradMag), 3.0);

// 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(w,h);
int max_region_label = watershedsUnionFind(srcImageRange(gradMag), destImage(labeling));

Required Interface:

SrcIterator src_upperleft, src_lowerright;
DestIterator 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);

unsigned int vigra::watershedsRegionGrowing

(

...

)

Region segmentation by means of a flooding-based watershed algorithm.

Note: This function is largely obsolete, watershedsMultiArray() should be preferred unless top speed is required.

This function implements variants of the watershed algorithm described in

L. Vincent and P. Soille: "Watersheds in digital spaces: An efficient algorithm based on immersion simulations", IEEE Trans. Patt. Analysis Mach. Intell. 13(6):583-598, 1991

The source image is a boundary indicator such as the gaussianGradientMagnitude() or the trace of the boundaryTensor(), and the destination is a label image designating membership of each point in one of the regions. Plateaus in the boundary indicator (i.e. regions of constant gray value) are handled via a Euclidean distance transform by default.

By default, the destination image is assumed to hold seeds for a seeded watershed transform. Seeds may, for example, be created by means of generateWatershedSeeds(). Note that the seeds will be overridden with the final watershed segmentation.

Alternatively, you may provide SeedOptions in order to instruct watershedsRegionGrowing() to generate its own seeds (it will call generateWatershedSeeds() internally). In that case, the destination image should be zero-initialized.

You can specify the neighborhood system to be used by passing FourNeighborCode or EightNeighborCode (default).

Further options to be specified via WatershedOptions are:

• Whether to keep a 1-pixel-wide contour (with label 0) between regions or perform complete grow (i.e. all pixels are assigned to a region).
• Whether to stop growing when the boundaryness exceeds a threshold (remaining pixels keep label 0).
• Whether to use a faster, but less powerful algorithm ("turbo algorithm"). It is faster because it orders pixels by means of a BucketQueue (therefore, the boundary indicator must contain integers in the range [0, ..., bucket_count-1], where bucket_count is specified in the options object), it only supports complete growing (no contour between regions is possible), and it handles plateaus in a simplistic way. It also saves some memory because it allocates less temporary storage.
• Whether one region (label) is to be preferred or discouraged by biasing its cost with a given factor (smaller than 1 for preference, larger than 1 for discouragement).

Note that VIGRA provides an alternative implementation of the watershed transform via watershedsUnionFind().

Declarations:

pass 2D array views:

namespace vigra {
    template <class T1, class S1,
              class T2, class S2,
              class Neighborhood = EightNeighborCode>
    unsigned int
    watershedsRegionGrowing(MultiArrayView<2, T1, S1> const & src,
                            MultiArrayView<2, T2, S2> dest,
                            Neighborhood neighborhood = EightNeighborCode(),
                            WatershedOptions const & options = WatershedOptions());

    template <class T1, class S1,
              class T2, class S2>
    unsigned int
    watershedsRegionGrowing(MultiArrayView<2, T1, S1> const & src,
                            MultiArrayView<2, T2, S2> dest,
                            WatershedOptions const & options = WatershedOptions());
}

show deprecated declarations

pass Image Iterators and Data Accessors :

namespace vigra {
    template <class SrcIterator, class SrcAccessor,
              class DestIterator, class DestAccessor,
              class Neighborhood = EightNeighborCode>
    unsigned int
    watershedsRegionGrowing(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
                            DestIterator upperleftd, DestAccessor da,
                            Neighborhood neighborhood = EightNeighborCode(),
                            WatershedOptions const & options = WatershedOptions());

    template <class SrcIterator, class SrcAccessor,
              class DestIterator, class DestAccessor>
    unsigned int
    watershedsRegionGrowing(SrcIterator upperlefts, SrcIterator lowerrights, SrcAccessor sa,
                            DestIterator upperleftd, DestAccessor da,
                            WatershedOptions const & options = WatershedOptions());
}

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
    watershedsRegionGrowing(triple<SrcIterator, SrcIterator, SrcAccessor> src,
                            pair<DestIterator, DestAccessor> dest,
                            Neighborhood neighborhood = EightNeighborCode(),
                            WatershedOptions const & options = WatershedOptions());

    template <class SrcIterator, class SrcAccessor,
              class DestIterator, class DestAccessor>
    unsigned int
    watershedsRegionGrowing(triple<SrcIterator, SrcIterator, SrcAccessor> src,
                            pair<DestIterator, DestAccessor> dest,
                            WatershedOptions const & options = WatershedOptions());
}

Usage:

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

Example: watersheds of the gradient magnitude.

MultiArray<2, float> src(w, h);
... // read input data

// compute gradient magnitude at scale 1.0 as a boundary indicator
MultiArray<2, float> gradMag(w, h);
gaussianGradientMagnitude(src, gradMag, 1.0);

// example 1
{
    // the pixel type of the destination image must be large enough to hold
    // numbers up to 'max_region_label' to prevent overflow
    MultiArray<2, unsigned int> labeling(w, h);

    // call watershed algorithm for 4-neighborhood, leave a 1-pixel boundary between regions,
    // and autogenerate seeds from all gradient minima where the magnitude is below 2.0
    unsigned int max_region_label =
          watershedsRegionGrowing(gradMag, labeling,
                                  FourNeighborCode(),
                                  WatershedOptions().keepContours()
                                       .seedOptions(SeedOptions().minima().threshold(2.0)));
}

// example 2
{
    MultiArray<2, unsigned int> labeling(w, h);

    // compute seeds beforehand (use connected components of all pixels
    // where the gradient  is below 4.0)
    unsigned int max_region_label =
          generateWatershedSeeds(gradMag, labeling,
                                 SeedOptions().levelSets(4.0));

    // quantize the gradient image to 256 gray levels
    MultiArray<2, unsigned char> gradMag256(w, h);
    FindMinMax<float> minmax;
    inspectImage(gradMag, minmax); // find original range
    transformImage(gradMag, gradMag256,
                   linearRangeMapping(minmax, 0, 255));

    // call the turbo algorithm with 256 bins, using 8-neighborhood
    watershedsRegionGrowing(gradMag256, labeling,
                            WatershedOptions().turboAlgorithm(256));
}

// example 3
{
   MultiArray<2, unsigned int> labeling(w, h);

    .. // get seeds from somewhere, e.g. an interactive labeling program,
       // make sure that label 1 corresponds to the background

    // bias the watershed algorithm so that the background is preferred
    // by reducing the cost for label 1 to 90%
    watershedsRegionGrowing(gradMag, labeling,
                            WatershedOptions().biasLabel(1, 0.9));
}

show deprecated examples

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

// compute gradient magnitude at scale 1.0 as a boundary indicator
vigra::FImage gradMag(w, h);
gaussianGradientMagnitude(srcImageRange(src), destImage(gradMag), 1.0);

// example 1
{
    // 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(w, h);

    // call watershed algorithm for 4-neighborhood, leave a 1-pixel boundary between regions,
    // and autogenerate seeds from all gradient minima where the magnitude is below 2.0
    unsigned int max_region_label =
          watershedsRegionGrowing(srcImageRange(gradMag), destImage(labeling),
                                  FourNeighborCode(),
                                  WatershedOptions().keepContours()
                                       .seedOptions(SeedOptions().minima().threshold(2.0)));
}

// example 2
{
    vigra::IImage labeling(w, h);

    // compute seeds beforehand (use connected components of all pixels
    // where the gradient  is below 4.0)
    unsigned int max_region_label =
          generateWatershedSeeds(srcImageRange(gradMag), destImage(labeling),
                                 SeedOptions().levelSets(4.0));

    // quantize the gradient image to 256 gray levels
    vigra::BImage gradMag256(w, h);
    vigra::FindMinMax<float> minmax;
    inspectImage(srcImageRange(gradMag), minmax); // find original range
    transformImage(srcImageRange(gradMag), destImage(gradMag256),
                   linearRangeMapping(minmax, 0, 255));

    // call the turbo algorithm with 256 bins, using 8-neighborhood
    watershedsRegionGrowing(srcImageRange(gradMag256), destImage(labeling),
                            WatershedOptions().turboAlgorithm(256));
}

// example 3
{
    vigra::IImage labeling(w, h);

    .. // get seeds from somewhere, e.g. an interactive labeling program,
       // make sure that label 1 corresponds to the background

    // bias the watershed algorithm so that the background is preferred
    // by reducing the cost for label 1 to 90%
    watershedsRegionGrowing(srcImageRange(gradMag), destImage(labeling),
                            WatershedOptions().biasLabel(1, 0.9));
}

Required Interface:

SrcIterator src_upperleft, src_lowerright;
DestIterator 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);

unsigned int vigra::watersheds3D

(

...

)

Region Segmentation by means of the watershed algorithm.

This function is deprecated, use watershedsMultiArray() instead.

Declarations:

show deprecated declarations

pass MultiIterators and Data Accessors :

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 strategies", 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.

Usage:

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

Example: watersheds3D of the gradient magnitude.

Shape3 shape(w, h, d);

MultiArray<3, float> src(shape), grad(shape);
...

double scale = 1;
gaussianGradientMagnitude(src, grad, scale);

MultiArray<3, int> labels(shape);

// find 6-connected regions
int max_region_label = watersheds3DSix(grad, labels);

// find 26-connected regions
max_region_label = watersheds3DTwentySix(grad, labels);

show deprecated examples

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);