[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]
Classes | |
class | SeedOptions |
Options object for generateWatershedSeeds(). More... | |
class | SeedRgDirectValueFunctor< Value > |
Statistics functor to be used for seeded region growing. More... | |
class | WatershedOptions |
Options object for watershedsRegionGrowing(). More... |
Enumerations | |
enum | SRGType |
Functions | |
template<... > | |
unsigned int | generateWatershedSeeds (...) |
Generate seeds for watershed computation and seeded region growing. | |
template<... > | |
unsigned int | generateWatershedSeeds3D (...) |
Generate seeds for watershed computation and seeded region growing. | |
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 | watersheds3D (...) |
Region Segmentation by means of the watershed algorithm. | |
template<... > | |
unsigned int | watershedsRegionGrowing (...) |
Region segmentation by means of a flooding-based watershed algorithm. | |
template<... > | |
unsigned int | watershedsUnionFind (...) |
Region segmentation by means of the union-find watershed algorithm. |
Region growing, watersheds, and voronoi tesselation
enum SRGType |
Choose between different types of Region Growing
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). 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):
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.
While( priority queue is not empty and termination criterion is not fulfilled)
Take the candidate with least cost from the queue. If it has not already been merged, merge it with it's adjacent region.
Put all candidates that are 4-adjacent to the pixel just processed into the priority queue.
SRGType
can take the following values:
CompleteGrow
KeepContours
StopAtThreshold
max_cost
. KeepContours | StopAtThreshold
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 arguments explicitly:
use argument objects in conjunction with Argument Object Factories :
Usage:
#include <vigra/seededregiongrowing.hxx>
Namespace: vigra
Example: implementation of the voronoi tesselation
Required Interface:
Further requirements are determined by the RegionStatisticsArray
.
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):
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.
While( priority queue is not empty)
Take the candidate with least cost from the queue. If it has not already been merged, merge it with it's adjacent region.
Put all candidates that are 4-adjacent to the pixel just processed into the priority queue.
SRGType
can take the following values:
CompleteGrow
KeepContours
StopAtThreshold
max_cost
. KeepContours | StopAtThreshold
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:
use argument objects in conjunction with Argument Object Factories :
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 vigra::EightNeighborCode or vigra::FourNeighborCode to determine the neighborhood where pixel values are compared.
The function uses accessors.
Declarations:
pass arguments explicitly:
use argument objects in conjunction with Argument Object Factories :
Usage:
#include <vigra/watersheds.hxx>
Namespace: vigra
For detailed examples see watershedsRegionGrowing().
unsigned int vigra::watershedsUnionFind | ( | ... | ) |
Region segmentation by means of the union-find watershed algorithm.
This function implements the union-find version of the watershed algorithms as described in
J. Roerdink, R. Meijster: "<em>The watershed transform: definitions, algorithms, and parallelization strategies</em>", 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 arguments explicitly:
use argument objects in conjunction with Argument Object Factories :
Usage:
#include <vigra/watersheds.hxx>
Namespace: vigra
Example: watersheds of the gradient magnitude.
Required Interface:
unsigned int vigra::watershedsRegionGrowing | ( | ... | ) |
Region segmentation by means of a flooding-based watershed algorithm.
This function implements variants of the watershed algorithm described in
L. Vincent and P. Soille: "<em>Watersheds in digital spaces: An efficient algorithm based on immersion simulations</em>", 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 pixel 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:
[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. Note that VIGRA provides an alternative implementation of the watershed transform via watershedsUnionFind().
Declarations:
pass arguments explicitly:
use argument objects in conjunction with Argument Object Factories :
Usage:
#include <vigra/watersheds.hxx>
Namespace: vigra
Example: watersheds of the gradient magnitude.
Required Interface:
unsigned int vigra::generateWatershedSeeds3D | ( | ... | ) |
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 vigra::EightNeighborCode or vigra::FourNeighborCode to determine the neighborhood where pixel values are compared.
The function uses accessors.
Declarations:
pass arguments explicitly:
use argument objects in conjunction with Argument Object Factories :
Usage:
#include <vigra/watersheds.hxx>
Namespace: vigra
For detailed examples see watershedsRegionGrowing().
unsigned int vigra::watersheds3D | ( | ... | ) |
Region Segmentation by means of the watershed algorithm.
Declarations:
pass arguments explicitly:
use argument objects in conjunction with Argument Object Factories :
use with 3D-Six-Neighborhood:
use with 3D-TwentySix-Neighborhood:
This function implements the union-find version of the watershed algorithms as described in
J. Roerdink, R. Meijster: "<em>The watershed transform: definitions, algorithms, and parallelization strategies</em>", 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 implementation 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.
Required Interface:
© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de) |
html generated using doxygen and Python
|