# VIGRA - Seeded Region Growing

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

| Seeded Region Growing |
--- | --- | ---

## Classes

class | SeedRgDirectValueFunctor
| Statistics functor to be used for seeded region growing. More...

## Functions

template<...> void | seededRegionGrowing (SrcImageIterator srcul, SrcImageIterator srclr, SrcAccessor as, SeedImageIterator seedsul, SeedAccessor aseeds, DestImageIterator destul, DestAccessor ad, RegionStatisticsArray &stats, const SRGType srgType)
| Region Segmentation by means of Seeded Region Growing.

## Detailed Description

Region segmentation and voronoi tesselation

## Function Documentation

void 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). 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. This works as follows:

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)

   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.

If `SRGType == CompleteGrow` (the default), this algorithm will produce a complete 4-connected tesselation of the image. If `SRGType == KeepContours`, a one-pixel-wide border will be left between the regions. The border pixels get label 0 (zero).

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.

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>
            void seededRegionGrowing(SrcImageIterator srcul,
                                     SrcImageIterator srclr, SrcAccessor as,
                                     SeedImageIterator seedsul, SeedAccessor aseeds,
                                     DestImageIterator destul, DestAccessor ad,
                                     RegionStatisticsArray & stats,
                                     SRGType srgType = CompleteGrow);
        }

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>
            inline void
            seededRegionGrowing(triple<SrcImageIterator, SrcImageIterator, SrcAccessor> img1,
                                pair<SeedImageIterator, SeedAccessor> img3,
                                pair<DestImageIterator, DestAccessor> img4,
                                RegionStatisticsArray & stats,
                                SRGType srgType = CompleteGrow);
        }

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`.

© Ullrich Köthe (koethe@informatik.uni-hamburg.de) Cognitive Systems Group, University of Hamburg, Germany | html generated using doxygen and Python VIGRA 1.3.2 (27 Jan 2005)