D:/Programmierung/C/TRTK/include/TRTK/RegionGrowing2D.hpp

Go to the documentation of this file.

/*
    Segmentation of simply connected spaces in 2D data.

    Copyright (C) 2010 - 2014 Christoph Haenisch

    Chair of Medical Engineering (mediTEC)
    RWTH Aachen University
    Pauwelsstr. 20
    52074 Aachen
    Germany

    Version 0.3.0 (2012-07-05)
*/

#ifndef REGION_GROWING_2D_1376134334
#define REGION_GROWING_2D_1376134334

#include <cmath>
#include <cstddef>
#include <deque>
#include <list>
#include <queue>

#include "Coordinate.hpp"


namespace TRTK
{


template <class BinaryDataType, class LabelType = unsigned short>
class RegionGrowing2D
{
public:
    typedef BinaryDataType binary_value_type;
    typedef LabelType label_type;

    typedef Coordinate<unsigned> Point;
    typedef std::deque<Point> Region;
    typedef std::deque<Region> Regions;

    RegionGrowing2D();
    RegionGrowing2D(const BinaryDataType * data, const unsigned width, const unsigned height);
    virtual ~RegionGrowing2D();

    void setData(const BinaryDataType * data, const unsigned width, const unsigned height);
    void setNeighborhoodSize(const unsigned size);

    void compute();
    template <int StrideX, int StrideY> void compute();
    void compute(const Point & seed_point);
    void compute(const std::deque<Point> & seed_points);

    const Regions & getRegions() const;
    const LabelType * getLabelMask() const;

private:

    unsigned getIndexFromPoint(const Point & point) const;
    std::list<Point> getNeighbors(const Point & point, const unsigned size = 2) const;
    Point getPointFromIndex(const unsigned index) const;
    void initLabelMask();

    unsigned height;
    unsigned width;
    unsigned neighborhood_size;
    const BinaryDataType * data;
    LabelType * label_mask;
    Regions regions;
};


template <class BinaryDataType, class LabelType>
RegionGrowing2D<BinaryDataType, LabelType>::RegionGrowing2D() :
    height(0),
    width(0),
    neighborhood_size(2),
    data(NULL),
    label_mask(NULL)
{
}


template <class BinaryDataType, class LabelType>
RegionGrowing2D<BinaryDataType, LabelType>::RegionGrowing2D(const BinaryDataType * data, const unsigned width, const unsigned height) :
    height(height),
    width(width),
    neighborhood_size(2),
    data(data)
{
    label_mask = new LabelType[width * height];
    initLabelMask();
}


template <class BinaryDataType, class LabelType>
RegionGrowing2D<BinaryDataType, LabelType>::~RegionGrowing2D()
{
    if (label_mask) delete[] label_mask;
}


template <class BinaryDataType, class LabelType>
void RegionGrowing2D<BinaryDataType, LabelType>::compute()
{
    // Note: We use Point(x, y) and index = (y * width + x) interchangeably.
    //       Conversions are done with getPointFromIndex() and getIndexFromPoint().

    if (data == NULL) return;

    regions.clear();
    initLabelMask();

    LabelType unique_label = 1;

    // For each point in the binary image, do...

    for (unsigned index = 0; index < width * height; ++index)
    {
        // Skip the point if it is not set, i.e., if its value is zero.

        if (!data[index])
        {
            continue;
        }
        else
        {
            // If the point has a label it was already assigned to a region and
            // thus skip it. Otherwise, this point is part of a new region. Hence,
            // get a new unique region label and add the current point as well as
            // its neighbors to this new region. To be able to process all points
            // and to add new points at the same time, a queue is used (FIFO).

            if (label_mask[index])
            {
                continue;
            }

            LabelType label = unique_label++;
            regions.push_back(Region());

            std::queue<Point> queue;
            queue.push(getPointFromIndex(index));

            while (!queue.empty())
            {
                Point point = queue.front();
                queue.pop();

                // Assign the label of the current region to the current point.

                label_mask[getIndexFromPoint(point)] = label;

                // Save the point in a global list which only contains points of a certain region.

                regions[label - 1].push_back(point);

                // Now, add those points of the neighborhood to the queue which are
                // set within the binary mask but still don't carry any label. Then
                // set the label of these points to the current region. As a result,
                // these points won't be selected a second time.

                std::list<Point> neighbors = getNeighbors(point, neighborhood_size);

                for(std::list<Point>::iterator neighbor = neighbors.begin(); neighbor != neighbors.end(); ++neighbor)
                {
                    const unsigned index = getIndexFromPoint(*neighbor);
                    if (data[index] && !label_mask[index])
                    {
                        label_mask[index] = label;
                        queue.push(*neighbor);
                    }
                }
            }
        }
    }
}


template <class BinaryDataType, class LabelType>
template <int StrideX, int StrideY>
void RegionGrowing2D<BinaryDataType, LabelType>::compute()
{
    // Note: We use Point(x, y) and index = (y * width + x) interchangeably.
    //       Conversions are done with getPointFromIndex() and getIndexFromPoint().

    if (data == NULL) return;

    regions.clear();
    initLabelMask();

    LabelType unique_label = 1;

    // For each point in the binary image, do...

    for (unsigned y = 0; y < height; y += StrideY)
    {
        for (unsigned x = 0; x < width; x += StrideX)
        {
            unsigned index = y * width + x;

            // Skip the point if it is not set, i.e., if its value is zero.

            if (!data[index])
            {
                continue;
            }
            else
            {
                // If the point has a label it was already assigned to a region and
                // thus skip it. Otherwise, this point is part of a new region. Hence,
                // get a new unique region label and add the current point as well as
                // its neighbors to this new region. To be able to process all points
                // and to add new points at the same time, a queue is used (FIFO).

                if (label_mask[index])
                {
                    continue;
                }

                LabelType label = unique_label++;
                regions.push_back(Region());

                std::queue<Point> queue;
                queue.push(getPointFromIndex(index));

                while (!queue.empty())
                {
                    Point point = queue.front();
                    queue.pop();

                    // Assign the label of the current region to the current point.

                    label_mask[getIndexFromPoint(point)] = label;

                    // Save the point in a global list which only contains points of a certain region.

                    regions[label - 1].push_back(point);

                    // Now, add those points of the neighborhood to the queue which are
                    // set within the binary mask but still don't carry any label. Then
                    // set the label of these points to the current region. As a result,
                    // these points won't be selected a second time.

                    std::list<Point> neighbors = getNeighbors(point, neighborhood_size);

                    for(std::list<Point>::iterator neighbor = neighbors.begin(); neighbor != neighbors.end(); ++neighbor)
                    {
                        const unsigned index = getIndexFromPoint(*neighbor);
                        if (data[index] && !label_mask[index])
                        {
                            label_mask[index] = label;
                            queue.push(*neighbor);
                        }
                    }
                }
            }
        }
    }
}


template <class BinaryDataType, class LabelType>
void RegionGrowing2D<BinaryDataType, LabelType>::compute(const Point & seed_point)
{
    std::deque<Point> seed_points;
    seed_points.push_back(seed_point);
    compute(seed_points);
}


template <class BinaryDataType, class LabelType>
void RegionGrowing2D<BinaryDataType, LabelType>::compute(const std::deque<Point> & seed_points)
{
    // Note: We use Point(x, y) and index = (y * width + x) interchangeably.
    //       Conversions are done with getPointFromIndex() and getIndexFromPoint().

    if (data == NULL) return;

    regions.clear();
    initLabelMask();

    LabelType unique_label = 1;

    // For each seed point do...

    for (unsigned i = 0; i < seed_points.size(); ++i)
    {
        unsigned index = getIndexFromPoint(seed_points[i]);

        // Skip the point if it is not set, i.e., if its value is zero.

        if (!data[index])
        {
            continue;
        }
        else
        {
            // If the point has a label it was already assigned to a region and
            // thus skip it. Otherwise, this point is part of a new region. Hence,
            // get a new unique region label and add the current point as well as
            // its neighbors to this new region. To be able to process all points
            // and to add new points at the same time, a queue is used (FIFO).

            if (label_mask[index])
            {
                continue;
            }

            LabelType label = unique_label++;
            regions.push_back(Region());

            std::queue<Point> queue;
            queue.push(getPointFromIndex(index));


            while (!queue.empty())
            {
                Point point = queue.front();
                queue.pop();

                // Assign the label of the current region to the current point.

                label_mask[getIndexFromPoint(point)] = label;

                // Save the point in a global list which only contains points of a certain region.

                regions[label - 1].push_back(point);

                // Now, add those points of the neighborhood to the queue which are
                // set within the binary mask but still don't carry any label. Then
                // set the label of these points to the current region. As a result,
                // these points won't be selected a second time.

                std::list<Point> neighbors = getNeighbors(point, neighborhood_size);

                for(std::list<Point>::iterator neighbor = neighbors.begin(); neighbor != neighbors.end(); ++neighbor)
                {
                    const unsigned index = getIndexFromPoint(*neighbor);
                    if (data[index] && !label_mask[index])
                    {
                        label_mask[index] = label;
                        queue.push(*neighbor);
                    }
                }
            }
        }
    }
}


template <class BinaryDataType, class LabelType>
inline unsigned RegionGrowing2D<BinaryDataType, LabelType>::getIndexFromPoint(const Point & point) const
{
    return point.y() * width + point.x();
}


template <class BinaryDataType, class LabelType>
const LabelType * RegionGrowing2D<BinaryDataType, LabelType>::getLabelMask() const
{
    return label_mask;
}


template <class BinaryDataType, class LabelType>
std::list<typename RegionGrowing2D<BinaryDataType, LabelType>::Point> RegionGrowing2D<BinaryDataType, LabelType>::getNeighbors(const Point & point, const unsigned size) const
{
    // Typical values for size are 0, 1, 2, 4, 8.

    // Return a list with all adjacent neighbors. Also check,
    // whether a neighbor is still within the data.

    std::list<Point> neighbors;

    const int delta = size == 2 ? 1 : int(std::ceil(std::sqrt(float(size))));

    for (int delta_x = -delta; delta_x <= delta; ++delta_x)
    {
        for (int delta_y = -delta; delta_y <= delta; ++delta_y)
        {
            if (unsigned(delta_x * delta_x + delta_y * delta_y) <= size)
            {
                int x = point.x() + delta_x;
                int y = point.y() + delta_y;

                if (0 <= x && x < int(width) && 0 <= y && y < int(height))
                {
                    neighbors.push_back(Point(x, y));
                }
            }
        }
    }

    return neighbors;
}


template <class BinaryDataType, class LabelType>
inline typename RegionGrowing2D<BinaryDataType, LabelType>::Point RegionGrowing2D<BinaryDataType, LabelType>::getPointFromIndex(const unsigned index) const
{
    const Point::value_type x = index % width;
    const Point::value_type y = index / width;

    return Point(x, y);
}


template <class BinaryDataType, class LabelType>
inline const typename RegionGrowing2D<BinaryDataType, LabelType>::Regions & RegionGrowing2D<BinaryDataType, LabelType>::getRegions() const
{
    return regions;
}


template <class BinaryDataType, class LabelType>
void RegionGrowing2D<BinaryDataType, LabelType>::initLabelMask()
{
    for (unsigned i = 0; i < width * height; ++i)
    {
        label_mask[i] = LabelType(0);
    }
}


template <class BinaryDataType, class LabelType>
void RegionGrowing2D<BinaryDataType, LabelType>::setData(const BinaryDataType * data, const unsigned width, const unsigned height)
{
    this->data = data;
    this->width = width;
    this->height = height;

    if (label_mask) delete[] label_mask;

    label_mask = new LabelType[width * height];
    initLabelMask();
}


template <class BinaryDataType, class LabelType>
void RegionGrowing2D<BinaryDataType, LabelType>::setNeighborhoodSize(const unsigned size)
{
    neighborhood_size = size;
}


} // namespace TRTK

#endif // REGION_GROWING_2D_1376134334