DGtal: DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong > Class Template Reference

#include <DistanceTransformation.h>

Collaboration diagram for DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong >:

Collaboration graph

Public Types
typedef TSpace	Space
typedef TPointPredicate	PointPredicate
typedef HyperRectDomain< Space >	Domain
typedef ImageContainerBySTLVector < Domain, IntegerLong >	OutputImage
typedef Space::Vector	Vector
typedef Space::Point	Point
typedef Space::Dimension	Dimension
typedef Space::Size	Size
typedef Space::Point::Coordinate	Abscissa
typedef SeparableMetricHelper < Point, IntegerLong, p >	SeparableMetric

Public Member Functions
	BOOST_CONCEPT_ASSERT ((CSignedInteger< IntegerLong >))
	BOOST_CONCEPT_ASSERT ((CSpace< TSpace >))
	BOOST_CONCEPT_ASSERT ((CPointPredicate< TPointPredicate >))
	DistanceTransformation (const Domain &aDomain, const PointPredicate &predicate)
	~DistanceTransformation ()
OutputImage	compute ()
bool	checkTypesValidity () const

Protected Member Functions
	DistanceTransformation ()

Private Member Functions
void	computeFirstStep (OutputImage &output) const
void	computeFirstStep1D (OutputImage &output, const Point &startingPoint) const
void	computeOtherSteps (const OutputImage &inputImage, OutputImage &output, const Dimension dim) const
void	computeOtherStep1D (const OutputImage &input, OutputImage &output, const Point &row, const Size dim, Abscissa s[], Abscissa t[]) const

Private Attributes
SeparableMetric	myMetric
const Domain &	myDomain
const PointPredicate &	myPointPredicate
Point	myLowerBoundCopy
Point	myUpperBoundCopy
Vector	myDisplacementVector
Point	myExtent
IntegerLong	myInfinity

Detailed Description

template<typename TSpace, typename TPointPredicate, DGtal::uint32_t p, typename IntegerLong = DGtal::int64_t>
class DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong >

Aim: Implementation of the linear in time distance transformation for separable metrics.

Description of template class 'DistanceTransformation'

Given a point predicate and a domain, the compute() method returns for each point of the domain, the closest distance to a point in the domain for which the predicate is false. The result is given as a map point<->values implemented as an image model OutputImage.

The point predicate could be:

the result of the thresholding of an image (for example using SimpleThresholdForegroundPredicate)
a predicate constructed from a digital set (for example using SetPredicate)
...

Template Parameters:

TSpace	type of Digital Space (model of CSpace).
TPointPredicate	point predicate returning true for points from which we compute the distance (model of CPointPredicate)
p	the static integer value to define the l_p metric.
IntegerLong	(optional) type used to represent exact distance value according to p (default: DGtal::uint64_t)

See also:: distancetransform2D.cpp; distancetransform3D.cpp

Definition at line 94 of file DistanceTransformation.h.

Member Typedef Documentation

template<typename TSpace, typename TPointPredicate, DGtal::uint32_t p, typename IntegerLong = DGtal::int64_t>

typedef Space::Point::Coordinate DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong >::Abscissa

Definition at line 121 of file DistanceTransformation.h.

template<typename TSpace, typename TPointPredicate, DGtal::uint32_t p, typename IntegerLong = DGtal::int64_t>

typedef Space::Dimension DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong >::Dimension

Definition at line 119 of file DistanceTransformation.h.

template<typename TSpace, typename TPointPredicate, DGtal::uint32_t p, typename IntegerLong = DGtal::int64_t>

typedef HyperRectDomain<Space> DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong >::Domain

Definition of the underlying domain type.

Definition at line 111 of file DistanceTransformation.h.

template<typename TSpace, typename TPointPredicate, DGtal::uint32_t p, typename IntegerLong = DGtal::int64_t>

typedef ImageContainerBySTLVector< Domain, IntegerLong > DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong >::OutputImage

Type of resulting image.

Definition at line 115 of file DistanceTransformation.h.

template<typename TSpace, typename TPointPredicate, DGtal::uint32_t p, typename IntegerLong = DGtal::int64_t>

typedef Space::Point DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong >::Point

Definition at line 118 of file DistanceTransformation.h.

template<typename TSpace, typename TPointPredicate, DGtal::uint32_t p, typename IntegerLong = DGtal::int64_t>

typedef TPointPredicate DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong >::PointPredicate

Copy of the point predicate type.

Definition at line 108 of file DistanceTransformation.h.

template<typename TSpace, typename TPointPredicate, DGtal::uint32_t p, typename IntegerLong = DGtal::int64_t>

typedef SeparableMetricHelper< Point , IntegerLong , p > DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong >::SeparableMetric

We construct the type associated to the separable metric.

Definition at line 124 of file DistanceTransformation.h.

template<typename TSpace, typename TPointPredicate, DGtal::uint32_t p, typename IntegerLong = DGtal::int64_t>

typedef Space::Size DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong >::Size

Definition at line 120 of file DistanceTransformation.h.

template<typename TSpace, typename TPointPredicate, DGtal::uint32_t p, typename IntegerLong = DGtal::int64_t>

typedef TSpace DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong >::Space

Copy of the space type.

Definition at line 105 of file DistanceTransformation.h.

template<typename TSpace, typename TPointPredicate, DGtal::uint32_t p, typename IntegerLong = DGtal::int64_t>

typedef Space::Vector DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong >::Vector

Definition at line 117 of file DistanceTransformation.h.

Constructor & Destructor Documentation

template<typename S , typename P , DGtal::uint32_t p, typename IntLong >

DGtal::DistanceTransformation< S, P, p, IntLong >::DistanceTransformation	(	const Domain &	aDomain,
		const PointPredicate &	aPredicate
	)

inline

Constructor

Constructor.

Definition at line 47 of file DistanceTransformation.ih.

                                                                                                         :
  myDomain(aDomain), myPointPredicate(aPredicate)
{

}

template<typename S , typename P , DGtal::uint32_t p, typename IntLong >

DGtal::DistanceTransformation< S, P, p, IntLong >::~DistanceTransformation ( )

inline

Default destructor

Destructor.

Definition at line 59 of file DistanceTransformation.ih.

{

}

template<typename TSpace, typename TPointPredicate, DGtal::uint32_t p, typename IntegerLong = DGtal::int64_t>

DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong >::DistanceTransformation ( )

protected

Default Constructor.

Member Function Documentation

template<typename TSpace, typename TPointPredicate, DGtal::uint32_t p, typename IntegerLong = DGtal::int64_t>

DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong >::BOOST_CONCEPT_ASSERT ( (CSignedInteger< IntegerLong >) )

template<typename TSpace, typename TPointPredicate, DGtal::uint32_t p, typename IntegerLong = DGtal::int64_t>

DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong >::BOOST_CONCEPT_ASSERT ( (CSpace< TSpace >) )

template<typename TSpace, typename TPointPredicate, DGtal::uint32_t p, typename IntegerLong = DGtal::int64_t>

DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong >::BOOST_CONCEPT_ASSERT ( (CPointPredicate< TPointPredicate >) )

template<typename S , typename P , DGtal::uint32_t p, typename IntLong >

bool DGtal::DistanceTransformation< S, P, p, IntLong >::checkTypesValidity ( ) const

inline

Check the validity of the transformation. For instance, we check that the output image pixel range is ok with respect to the domain extent and the SeparableMetric.

Warning and advices are printed in the trace system.

Returns:: true if a warning has been raised.

Definition at line 69 of file DistanceTransformation.ih.

References DGtal::trace, and DGtal::Trace::warning().

{
  typename Point::UnsignedComponent maxExtent = ( myDomain.upperBound() - 
                                                  myDomain.lowerBound() ).normInfinity();
  
  //Estimate worst-case bit size (special case for p=0 == Linfinity
  double bitSize;
  
  if (SeparableMetric::p != 0)
    bitSize = SeparableMetric::p * (log ((double) S::dimension * 2 * maxExtent ) / log(2.0));
  else
    bitSize =  sizeof ( typename OutputImage::Value ) * 8;
  
  if ( bitSize > sizeof ( typename OutputImage::Value ) * 8 )
    {
      trace.warning() << "(DistanceTransformation) The output image value range may"
                      <<" not be sufficient to store the exact values  according to"
                      <<" the input domain extent." << endl;
      return false;
    }
  return true;
}

template<typename S , typename P , DGtal::uint32_t p, typename IntLong >

DGtal::DistanceTransformation< S, P, p, IntLong >::OutputImage DGtal::DistanceTransformation< S, P, p, IntLong >::compute ( )

inline

Compute the Distance Transformation of a set of point using a SeparableMetric metric. The method associates to each point with value satisfying the foreground predicate, its distance to the closest background point. This algorithm is O(d.|domain size|).

Precondition:: the foreground point predicate predicate must be defined on the domain aDomain

Returns:: the distance transformation image.

Definition at line 96 of file DistanceTransformation.ih.

References DGtal::ImageContainerBySTLVector< TDomain, TValue >::translateDomain().

{
  //We trace type validdity check result;
  checkTypesValidity ( );
  //We copy the image extent and translate the image domains to (0,..0)x(Upper-Lower)
  myLowerBoundCopy = Point(); //(O,O,...O)
  myUpperBoundCopy = myDomain.upperBound() - myDomain.lowerBound();
  myDisplacementVector = myDomain.lowerBound();
  myExtent = myUpperBoundCopy - myLowerBoundCopy;
  myInfinity  = myMetric.power(static_cast<typename S::Integer>(S::dimension) * 
                               myExtent.normInfinity() + 1);
  
  Domain workingDomain(myLowerBoundCopy, myUpperBoundCopy);
  OutputImage output ( workingDomain );
  OutputImage swap ( workingDomain );
  bool isSwap = true;
  //First step
  computeFirstStep ( output );
  //We process the dimensions swaping the temporary buffers
  for ( Dimension dim = 1; dim < S::dimension ; dim++ )
    {
      if ( isSwap )
        computeOtherSteps ( output, swap, dim );
      else
        computeOtherSteps ( swap, output, dim );
      isSwap = !isSwap;
    }
  //We translate the output image to the correct position and return.
  if ( !isSwap )
    {
      swap.translateDomain(myDisplacementVector);
      return swap;
    }
  else
    {
      output.translateDomain(myDisplacementVector);
      return output;
    }
}

template<typename S , typename P , DGtal::uint32_t p, typename IntLong >

void DGtal::DistanceTransformation< S, P, p, IntLong >::computeFirstStep ( OutputImage & output ) const

inlineprivate

Compute the first step of the separable distance transformation.

Parameters:

output the output image with the first step DT values

Definition at line 148 of file DistanceTransformation.ih.

References DGtal::HyperRectDomain< TSpace >::ConstSubRange::begin(), DGtal::Trace::beginBlock(), DGtal::HyperRectDomain< TSpace >::ConstSubRange::end(), DGtal::Trace::endBlock(), DGtal::HyperRectDomain< TSpace >::subRange(), and DGtal::trace.

{
  trace.beginBlock ( "DT dimension 0" );
  Point startingPoint = myLowerBoundCopy;
  typedef typename Domain::ConstSubRange::ConstIterator ConstDomIt;
  
  //We setup the subdomain iterator
  //the iterator will scan dimension using the order:
  // {n-1, n-2, ... 1} (we skip the '0' dimension.
  std::vector<Size> subdomain;
  subdomain.reserve(S::dimension - 1);
  for (Dimension k = S::dimension-1; k>0 ; --k)
    subdomain.push_back( k );
  Domain localDomain(myLowerBoundCopy, myUpperBoundCopy);
  //We process the dimensions to construct a Point
  for (ConstDomIt it = localDomain.subRange( subdomain ).begin(),
         itend = localDomain.subRange( subdomain ).end(); it != itend; ++it)
    {
      // trace.info()  << "Processing 1D slice starting at =" << (*it) << endl;
      computeFirstStep1D (output, (*it) );
    }
  trace.endBlock();
}

template<typename S , typename P , DGtal::uint32_t p, typename IntLong >

void DGtal::DistanceTransformation< S, P, p, IntLong >::computeFirstStep1D	(	OutputImage &	output,
		const Point &	startingPoint
	)		const

private

Compute the 1D DT associated to the first step.

Parameters:

output	the output image with the first step DT values
startingPoint	a point to specify the starting point of the 1D row

Definition at line 227 of file DistanceTransformation.ih.

References DGtal::ImageContainerBySTLVector< TDomain, TValue >::setValue().

{
  Point prec = startingPoint;
  Point point = startingPoint;
  //PRECOND : output can store 2*(myUpperBoundCopy[0] -  myLowerBoundCopy[0]) in its valuetype
  //INFTY = something > myUpperBoundCopy[0] -  myLowerBoundCopy[0]
  if ( myPointPredicate ( point + myDisplacementVector ) )
    output.setValue ( point, myInfinity );
  else
    output.setValue ( point, 0 );
  //Forward scan 
  for ( point[0] = 1; point[0] <= myUpperBoundCopy[0]; point[0]++ )
    {
      // trace.warning() << point << " ";
      if ( myPointPredicate ( point  + myDisplacementVector ))
        output.setValue ( point, 1 + output ( prec ) );
      else
        output.setValue ( point, 0 );
      prec[0] = point[0];
    }
  //prec is the the rightmost point of "point'
  prec[0] =  myUpperBoundCopy[0];
  //Backward scan
  for ( point[0] = myUpperBoundCopy[0] - 1; point[0] >= 0 ; point[0]-- )
    {
      if ( output ( prec ) < output ( point ) )
        output.setValue ( point, 1 + output ( prec ) );
      prec[0] = point[0];
    }
  //final computation
  for ( point[0] = 0; point[0] <= myUpperBoundCopy[0]; point[0]++ )
    if (output( point ) < myInfinity)
      output.setValue ( point, myMetric.power( (const int)output ( point ) ));
    else
      output.setValue ( point, myInfinity);
}

template<typename S , typename P , DGtal::uint32_t p, typename IntLong >

void DGtal::DistanceTransformation< S, P, p, IntLong >::computeOtherStep1D	(	const OutputImage &	input,
		OutputImage &	output,
		const Point &	row,
		const Size	dim,
		Abscissa	s[],
		Abscissa	t[]
	)		const

private

Compute the 1D DT associated to the steps except the first one.

Parameters:

aImage	the input image
output	the output image with the DT values
row	a point to specify the starting point of the 1D row
dim	the dimension to process
predicate	the predicate to characterize the foreground (e.g. !=0, see DefaultForegroundPredicate)

Todo:: optimize the test here

Definition at line 277 of file DistanceTransformation.ih.

References DGtal::ImageContainerBySTLVector< TDomain, TValue >::setValue(), DGtal::ImageContainerBySTLVector< TDomain, TValue >::spanBegin(), and DGtal::ImageContainerBySTLVector< TDomain, TValue >::spanEnd().

{
  Abscissa w;
  Abscissa q = 0;  //index for the stack "head"
  
  Point sQ = startingPoint;
  Point pU = startingPoint;
  // We look for the first point in the 1D column with distance different from
  // myInfinity
  pU[dim] = myLowerBoundCopy[dim];
  while ((pU[dim] <= myUpperBoundCopy[dim]) && (input ( pU ) == myInfinity))
    pU[dim] ++;
  // All points are set to +infinity, we just copy the infinity value and return
  if ( pU[dim] > myUpperBoundCopy[dim] )
    {
      for(typename OutputImage::SpanIterator it= output.spanBegin(startingPoint,dim), 
            itend=output.spanEnd(startingPoint,dim); 
          it != itend; ++it)
        output.setValue(it, myInfinity);
      return;
    }
  
  //Stack structure
  q = 0;
  s[q] = pU[dim]; // first point with DT!=infinity
  sQ[dim] = s[q]; // nD Point corresponding to the head of the stack
  t[q] = myLowerBoundCopy[dim]; 
  //Forward Scan 
  //We scan all the pixels
  for ( Abscissa u = pU[dim] + 1; u <= myUpperBoundCopy[dim] ; u++ )
    {
      pU[ dim ] = u;
      if ( input( pU ) == myInfinity )
        {
          continue;
        }
      
      while ( ( q >= 0 ) &&
              ( myMetric.F ( t[q], s[q], input ( sQ ) ) >
                myMetric.F ( t[q], u, input ( pU ) ) ) )
        {
          q--;
          if (q>=0)
            sQ[dim] = s[q];
        }
      
      if ( q < 0 )
        {
          q = 0;
          s[0] = u;
          sQ[dim] = u;
          t[0] = myLowerBoundCopy[dim];
        }
      else
        {
          sQ[dim] = s[q];
          w = 1 + myMetric.Sep ( s[q],
                                 input ( sQ ),
                                 u,
                                 input ( pU ) );
    
          if (( w <= myUpperBoundCopy[dim] ) 
              && (w>= myLowerBoundCopy[dim]))
            {
              q++;
              s[q] = u;
              sQ[dim] = u;
              t[q] = w;
            }
        }
    }
  
  Point last = startingPoint;
  
  ASSERT(q>=0);
  
  sQ[dim] = s[q];
  
  //Backward Scan
  for (last[dim] = myUpperBoundCopy[dim];
       last[dim] >= myLowerBoundCopy[dim] ;
       last[dim]-- )
    {
      output.setValue ( last, myMetric.F ( last[dim] , s[q], input ( sQ ) ) );
      if (( last[dim] == t[q] ) && (q > 0))
        {
          q--;
          sQ[dim] = s[q];
        }
    }
}

template<typename S , typename P , DGtal::uint32_t p, typename IntLong >

void DGtal::DistanceTransformation< S, P, p, IntLong >::computeOtherSteps	(	const OutputImage &	inputImage,
		OutputImage &	output,
		const Dimension	dim
	)		const

inlineprivate

Compute the other steps of the separable distance transformation.

Parameters:

inputImage	the image resulting of the first (or intermediate) step
output	the output image
dim	the dimension to process

Definition at line 180 of file DistanceTransformation.ih.

References DGtal::HyperRectDomain< TSpace >::ConstSubRange::begin(), DGtal::Trace::beginBlock(), DGtal::HyperRectDomain< TSpace >::ConstSubRange::end(), DGtal::Trace::endBlock(), DGtal::HyperRectDomain< TSpace >::subRange(), and DGtal::trace.

{
  std::string title = "DT dimension " +  boost::lexical_cast<string>( dim ) ;
  trace.beginBlock ( title );
  typedef typename Domain::ConstSubRange::ConstIterator ConstDomIt;
  
  //We setup the subdomain iterator
  //the iterator will scan dimension using the order:
  // {n-1, n-2, ... 1} (we skip the '0' dimension.
  std::vector<Size> subdomain;
  subdomain.reserve(S::dimension - 1);
  for (unsigned int k = 0; k < S::dimension ; k++)
    if ( (S::dimension - 1 - k) != dim)
      subdomain.push_back( S::dimension - 1 - k );
  Domain localDomain(myLowerBoundCopy, myUpperBoundCopy);
  Size maxSize = myExtent.normInfinity();
  //Stacks used in the envelope computation
  Abscissa *s = new Abscissa[maxSize+1];
  Abscissa *t = new Abscissa[maxSize+1];
  
  ASSERT( s != NULL);
  ASSERT( t != NULL);
  
  //We process the dimensions to construct a Point
  for (ConstDomIt it = localDomain.subRange( subdomain ).begin(),
         itend = localDomain.subRange( subdomain ).end();
       it != itend; ++it)
    {
      computeOtherStep1D ( input, output, (*it), dim, s, t );
    }
  
  delete[] s;
  delete[] t;
  trace.endBlock();
}

Field Documentation

template<typename TSpace, typename TPointPredicate, DGtal::uint32_t p, typename IntegerLong = DGtal::int64_t>

Vector DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong >::myDisplacementVector

private

Displacement vector to translate temporary images.

Definition at line 245 of file DistanceTransformation.h.

template<typename TSpace, typename TPointPredicate, DGtal::uint32_t p, typename IntegerLong = DGtal::int64_t>

const Domain& DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong >::myDomain

private

Copy of the computation domain.

Definition at line 233 of file DistanceTransformation.h.

template<typename TSpace, typename TPointPredicate, DGtal::uint32_t p, typename IntegerLong = DGtal::int64_t>

Point DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong >::myExtent

private

Copy of the domain extent.

Definition at line 248 of file DistanceTransformation.h.

template<typename TSpace, typename TPointPredicate, DGtal::uint32_t p, typename IntegerLong = DGtal::int64_t>

IntegerLong DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong >::myInfinity

private

Value to act as a +infinity value.

Definition at line 251 of file DistanceTransformation.h.

template<typename TSpace, typename TPointPredicate, DGtal::uint32_t p, typename IntegerLong = DGtal::int64_t>

Point DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong >::myLowerBoundCopy

private

Copy of the image lower bound.

Definition at line 239 of file DistanceTransformation.h.

template<typename TSpace, typename TPointPredicate, DGtal::uint32_t p, typename IntegerLong = DGtal::int64_t>

SeparableMetric DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong >::myMetric

private

The separable metric instance.

Definition at line 230 of file DistanceTransformation.h.

template<typename TSpace, typename TPointPredicate, DGtal::uint32_t p, typename IntegerLong = DGtal::int64_t>

const PointPredicate& DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong >::myPointPredicate

private

Copy of the computation domain.

Definition at line 236 of file DistanceTransformation.h.

template<typename TSpace, typename TPointPredicate, DGtal::uint32_t p, typename IntegerLong = DGtal::int64_t>

Point DGtal::DistanceTransformation< TSpace, TPointPredicate, p, IntegerLong >::myUpperBoundCopy

private

Copy of the image lower bound.

Definition at line 242 of file DistanceTransformation.h.

The documentation for this class was generated from the following files: