[Insight-users] Line or Path object as Initial LevelSet in FastMarchingImageFiler
Dan Mueller
dan.muel at gmail.com
Thu Aug 7 10:47:14 EDT 2008
Hi Claude,
> I'm interested in a true Distance Map output like in FastMarchingImageFiler,
> rather than discrete levelset in all other (?) Segmentation
> filters.
Have you tried the itkSignedMaurerDistanceMapImageFilter or
itkSignedDanielssonDistanceMapImageFilter? These filters compute the
"Euclidean distance transform of a binary image". Is the Euclidean
distance the "true" distance you are referring to?
> Am I forced to iterate on seed nodes to input them in the filter?
Assuming the above distance filters are _not_ what you are after: yes,
you need to iterate the set of desired seeds and add each one. I wrote
my own version of itkFastMarchingImageFilter which does this
automagically. I have attached it below for your reference. The method
of interest is SetTrialPointsFromImage. In retrospect I should have
just subclassed the filter to add the new functionality (and probably
submitted it to the Insight Journal)...
Hope this helps.
Cheers, Dan
2008/8/7 GOUEDARD Claude <claude.gouedard at cea.fr>:
> Hi all ,
> I'm interested in a true Distance Map output like in FastMarchingImageFiler,
> rather than discrete levelset in all other (?) Segmentation
> filters.
> However, all examples about FastMarching start from only one seed point.*
> I'm rather interested in constructing a line seed points (in 2D) or a
> surface seed points (in 3D) from a computed vector or surface.
>
> In the user mailing list, I can see that "one of the best way to get a set
> of seed point is to use/ ReinitializeLevelSetImageFilter
> /from a binary image". ( 2003-June/004061.html )
>
> Is there a simpler method to get, as input seeds , a line ( or a plan), let
> say as an example, parallel to one axis.
> Am I forced to iterate on seed nodes to input them in the filter?
>
> Regards,
>
> Claude
/*=========================================================================
Program: Insight Segmentation & Registration Toolkit
Module: $RCSfile: itkFastMarchingImageFilter.h,v $
Language: C++
Date: $Date: 2007-08-31 22:17:25 +0200 (Fri, 31 Aug 2007) $
Version: $Revision: 2 $
Copyright (c) Insight Software Consortium. All rights reserved.
See ITKCopyright.txt or http://www.itk.org/HTML/Copyright.htm for details.
This software is distributed WITHOUT ANY WARRANTY; without even
the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE. See the above copyright notices for more information.
=========================================================================*/
#ifndef _itkFastMarchingImageFilter_h
#define _itkFastMarchingImageFilter_h
#include "itkImageToImageFilter.h"
#include "itkLevelSet.h"
#include "itkIndex.h"
#include "vnl/vnl_math.h"
#include <functional>
#include <queue>
namespace itk
{
/** \class FastMarchingImageFilter
* \brief Solve an Eikonal equation using Fast Marching
*
* Fast marching solves an Eikonal equation where the speed is always
* non-negative and depends on the position only. Starting from an
* initial position on the front, fast marching systematically moves the
* front forward one grid point at a time.
*
* Updates are preformed using an entropy satisfy scheme where only
* "upwind" neighborhoods are used. This implementation of Fast Marching
* uses a std::priority_queue to locate the next proper grid position to
* update.
*
* Fast Marching sweeps through N grid points in (N log N) steps to obtain
* the arrival time value as the front propagates through the grid.
*
* Implementation of this class is based on Chapter 8 of
* "Level Set Methods and Fast Marching Methods", J.A. Sethian,
* Cambridge Press, Second edition, 1999.
*
* This class is templated over the level set image type and the speed
* image type. The initial front is specified by two containers: one
* containing the known points and one containing the trial
* points. Alive points are those that are already part of the
* object, and trial points are considered for inclusion.
* In order for the filter to evolve, at least some trial
* points must be specified. These can for instance be specified as
the layer of
* pixels around the alive points.
* The speed function can be specified as a speed image or a
* speed constant. The speed image is set using the method
* SetInput(). If the speed image is NULL, a constant speed function
* is used and is specified using method the SetSpeedConstant().
*
* If the speed function is constant and of value one, fast marching results
* in an approximate distance function from the initial alive points.
* FastMarchingImageFilter is used in the ReinitializeLevelSetImageFilter
* object to create a signed distance function from the zero level set.
*
* The algorithm can be terminated early by setting an appropriate stopping
* value. The algorithm terminates when the current arrival time being
* processed is greater than the stopping value.
*
* There are two ways to specify the output image information
* ( LargestPossibleRegion, Spacing, Origin): (a) it is copied directly from
* the input speed image or (b) it is specified by the user. Default values
* are used if the user does not specify all the information.
*
* The output information is computed as follows.
* If the speed image is NULL or if the OverrideOutputInformation is set to
* true, the output information is set from user specified parameters. These
* parameters can be specified using methods SetOutputRegion(),
SetOutputSpacing()
* and SetOutputOrigin(). Else if the speed image is not NULL, the
output information
* is copied from the input speed image.
*
* Possible Improvements:
* In the current implemenation, std::priority_queue only allows
* taking nodes out from the front and putting nodes in from the back.
* To update a value already on the heap, a new node is added to the heap.
* The defunct old node is left on the heap. When it is removed from the
* top, it will be recognized as invalid and not used.
* Future implementations can implement the heap in a different way
* allowing the values to be updated. This will generally require
* some sift-up and sift-down functions and
* an image of back-pointers going from the image to heap in order
* to locate the node which is to be updated.
*
* \sa LevelSetTypeDefault
* \ingroup LevelSetSegmentation
*/
template <
class TLevelSet,
class TSpeedImage =
Image<float,::itk::GetImageDimension<TLevelSet>::ImageDimension> >
class ITK_EXPORT FastMarchingImageFilter :
public ImageToImageFilter<TSpeedImage,TLevelSet>
{
public:
/** Standard class typdedefs. */
typedef FastMarchingImageFilter Self;
typedef ImageSource<TLevelSet> Superclass;
typedef SmartPointer<Self> Pointer;
typedef SmartPointer<const Self> ConstPointer;
/** Method for creation through the object factory. */
itkNewMacro(Self);
/** Run-time type information (and related methods). */
itkTypeMacro(FastMarchingImageFilter, ImageSource);
/** Typedef support of level set method types. */
typedef LevelSetTypeDefault<TLevelSet> LevelSetType;
typedef typename LevelSetType::LevelSetImageType LevelSetImageType;
typedef typename LevelSetType::LevelSetPointer LevelSetPointer;
typedef typename LevelSetType::PixelType PixelType;
typedef typename LevelSetType::NodeType NodeType;
typedef typename LevelSetType::NodeContainer NodeContainer;
typedef typename LevelSetType::NodeContainerPointer NodeContainerPointer;
typedef typename LevelSetImageType::SizeType OutputSizeType;
typedef typename LevelSetImageType::RegionType OutputRegionType;
typedef typename LevelSetImageType::SpacingType OutputSpacingType;
typedef typename LevelSetImageType::PointType OutputPointType;
class AxisNodeType : public NodeType
{
public:
int GetAxis() const { return m_Axis; }
void SetAxis( int axis ) { m_Axis = axis; }
const AxisNodeType & operator=(const NodeType & node)
{ this->NodeType::operator=(node); return *this; }
private:
int m_Axis;
};
/** SpeedImage typedef support. */
typedef TSpeedImage SpeedImageType;
/** SpeedImagePointer typedef support. */
typedef typename SpeedImageType::Pointer SpeedImagePointer;
typedef typename SpeedImageType::ConstPointer SpeedImageConstPointer;
/** Dimension of the level set and the speed image. */
itkStaticConstMacro(SetDimension, unsigned int,
LevelSetType::SetDimension);
itkStaticConstMacro(SpeedImageDimension, unsigned int,
SpeedImageType::ImageDimension);
/** Index typedef support. */
typedef Index<itkGetStaticConstMacro(SetDimension)> IndexType;
/** Enum of Fast Marching algorithm point types. FarPoints represent far
* away points; TrialPoints represent points within a narrowband of the
* propagating front; and AlivePoints represent points which have already
* been processed. */
enum LabelType { FarPoint, AlivePoint, TrialPoint };
/** LabelImage typedef support. */
typedef unsigned char LabelPixelType;
typedef Image<typename LabelPixelType,
itkGetStaticConstMacro(SetDimension)> LabelImageType;
typedef typename LabelImageType::Pointer LabelImagePointer;
/** Set the container of Alive Points representing the initial front.
* Alive points are represented as a VectorContainer of LevelSetNodes. */
void SetAlivePoints( NodeContainer * points )
{
m_AlivePoints = points;
this->Modified();
};
/** Set the alive points from an image.
* All pixels greater than zero are immediately added to the
* collection of alive points. */
void SetAlivePointsFromImage( LabelImagePointer image );
/** Get the container of Alive Points representing the initial front. */
NodeContainerPointer GetAlivePoints( )
{ return m_AlivePoints; };
/** Set the container of Trial Points representing the initial front.
* Trial points are represented as a VectorContainer of LevelSetNodes. */
void SetTrialPoints( NodeContainer * points )
{
m_TrialPoints = points;
this->Modified();
};
/** Set the trial points from an image.
* All pixels greater than zero are immediately added to the
* collection of trial points. */
void SetTrialPointsFromImage( LabelImagePointer image );
/** Get the container of Trial Points representing the initial front. */
NodeContainerPointer GetTrialPoints( )
{ return m_TrialPoints; };
/** Get the point type label image. */
LabelImagePointer GetLabelImage() const
{ return m_LabelImage; };
/** Manually set the label image.
* Call this method instead of calling SetAlivePoints() and SetTrialPoints().
* By calling this method any subsequent calls to SetAlivePoints() or
* SetTrialPoints() will be ignored, and the label image will be set
* directly as the given image. The label image must have FarPoints
* (points not yet processed), AlivePoints (points known to be included
* in the level-set), and TrialPoints (points from which the front is
* expanded). */
void SetLabelImage( LabelImagePointer image );
/** Set the label image from the given alive image.
* The given image is assumed to be binary (0 or not 0).
* Trial points are extracted by creating a contour around the given
* binary image, by morphologically eroding the given image.
* Alive points are are those remaining after the erosion,
* trial points are those eroded. By calling this method any subsequent
* calls to SetAlivePoints() or SetTrialPoints() will be ignored. */
void SetLabelImageFromContour( LabelImagePointer image );
/** Set the Speed Constant. If the Speed Image is NULL,
* the SpeedConstant value is used for the whole level set.
* By default, the SpeedConstant is set to 1.0. */
void SetSpeedConstant( double value )
{
m_SpeedConstant = value;
m_InverseSpeed = -1.0 * vnl_math_sqr( 1.0 / m_SpeedConstant );
this->Modified();
}
/** Get the Speed Constant. */
itkGetConstReferenceMacro( SpeedConstant, double );
/** Set/Get the Normalization Factor for the Speed Image.
The values in the Speed Image is divided by this
factor. This allows the use of images with
integer pixel types to represent the speed. */
itkSetMacro( NormalizationFactor, double );
itkGetMacro( NormalizationFactor, double );
/** Set the Fast Marching algorithm Stopping Value. The Fast Marching
* algorithm is terminated when the value of the smallest trial point
* is greater than the stopping value. */
itkSetMacro( StoppingValue, double );
/** Get the Fast Marching algorithm Stopping Value. */
itkGetConstReferenceMacro( StoppingValue, double );
/** Set the Collect Points flag. Instrument the algorithm to collect
* a container of all nodes which it has visited. Useful for
* creating Narrowbands for level set algorithms that supports
* narrow banding. */
itkSetMacro( CollectPoints, bool );
/** Get thConste Collect Points flag. */
itkGetConstReferenceMacro( CollectPoints, bool );
itkBooleanMacro( CollectPoints );
/** Get the container of Processed Points. If the CollectPoints flag
* is set, the algorithm collects a container of all processed nodes.
* This is useful for defining creating Narrowbands for level
* set algorithms that supports narrow banding. */
NodeContainerPointer GetProcessedPoints() const
{ return m_ProcessedPoints; }
/** The output largeset possible, spacing and origin is computed as follows.
* If the speed image is NULL or if the OverrideOutputInformation is true,
* the output information is set from user specified parameters. These
* parameters can be specified using methods SetOutputRegion(),
SetOutputSpacing()
* and SetOutputOrigin(). Else if the speed image is not NULL, the
output information
* is copied from the input speed image. */
virtual void SetOutputSize( const OutputSizeType& size )
{ m_OutputRegion = size; }
virtual OutputSizeType GetOutputSize() const
{ return m_OutputRegion.GetSize(); }
itkSetMacro( OutputRegion, OutputRegionType );
itkGetConstReferenceMacro( OutputRegion, OutputRegionType );
itkSetMacro( OutputSpacing, OutputSpacingType );
itkGetConstReferenceMacro( OutputSpacing, OutputSpacingType );
itkSetMacro( OutputOrigin, OutputPointType );
itkGetConstReferenceMacro( OutputOrigin, OutputPointType );
itkSetMacro( OverrideOutputInformation, bool );
itkGetConstReferenceMacro( OverrideOutputInformation, bool );
itkBooleanMacro( OverrideOutputInformation );
#ifdef ITK_USE_CONCEPT_CHECKING
/** Begin concept checking */
itkConceptMacro(SameDimensionCheck,
(Concept::SameDimension<SetDimension, SpeedImageDimension>));
itkConceptMacro(SpeedConvertibleToDoubleCheck,
(Concept::Convertible<typename TSpeedImage::PixelType, double>));
itkConceptMacro(DoubleConvertibleToLevelSetCheck,
(Concept::Convertible<double, PixelType>));
itkConceptMacro(LevelSetOStreamWritableCheck,
(Concept::OStreamWritable<PixelType>));
/** End concept checking */
#endif
protected:
FastMarchingImageFilter();
~FastMarchingImageFilter(){};
void PrintSelf( std::ostream& os, Indent indent ) const;
virtual void Initialize( LevelSetImageType * );
virtual void UpdateNeighbors( const IndexType& index,
const SpeedImageType *, LevelSetImageType * );
virtual double UpdateValue( const IndexType& index,
const SpeedImageType *, LevelSetImageType * );
const AxisNodeType& GetNodeUsedInCalculation(unsigned int idx) const
{ return m_NodesUsed[idx]; }
void GenerateData();
/** Generate the output image meta information. */
virtual void GenerateOutputInformation();
virtual void EnlargeOutputRequestedRegion(DataObject *output);
/** Get Large Value. This value is used to
represent the concept of infinity for the time assigned to pixels that
have not been visited. This value is set by default to half the
max() of the pixel type used to represent the time-crossing map. */
itkGetConstReferenceMacro( LargeValue, PixelType );
OutputRegionType m_BufferedRegion;
typedef typename LevelSetImageType::IndexType LevelSetIndexType;
LevelSetIndexType m_StartIndex;
LevelSetIndexType m_LastIndex;
itkGetConstReferenceMacro( StartIndex, LevelSetIndexType );
itkGetConstReferenceMacro( LastIndex, LevelSetIndexType );
private:
FastMarchingImageFilter(const Self&); //purposely not implemented
void operator=(const Self&); //purposely not implemented
NodeContainerPointer m_AlivePoints;
NodeContainerPointer m_TrialPoints;
bool m_ManualLabelImage;
LabelImagePointer m_LabelImage;
double m_SpeedConstant;
double m_InverseSpeed;
double m_StoppingValue;
bool m_CollectPoints;
NodeContainerPointer m_ProcessedPoints;
OutputRegionType m_OutputRegion;
OutputSpacingType m_OutputSpacing;
OutputPointType m_OutputOrigin;
bool m_OverrideOutputInformation;
typename LevelSetImageType::PixelType m_LargeValue;
AxisNodeType m_NodesUsed[SetDimension];
/** Trial points are stored in a min-heap. This allow efficient access
* to the trial point with minimum value which is the next grid point
* the algorithm processes. */
typedef std::vector<AxisNodeType> HeapContainer;
typedef std::greater<AxisNodeType> NodeComparer;
typedef std::priority_queue< AxisNodeType, HeapContainer,
NodeComparer > HeapType;
HeapType m_TrialHeap;
double m_NormalizationFactor;
};
} // namespace itk
#ifndef ITK_MANUAL_INSTANTIATION
#include "itkFastMarchingImageFilter.txx"
#endif
#endif
/*=========================================================================
Program: Insight Segmentation & Registration Toolkit
Module: $RCSfile: itkFastMarchingImageFilter.txx,v $
Language: C++
Date: $Date: 2007-08-31 22:17:25 +0200 (Fri, 31 Aug 2007) $
Version: $Revision: 2 $
Copyright (c) Insight Software Consortium. All rights reserved.
See ITKCopyright.txt or http://www.itk.org/HTML/Copyright.htm for details.
This software is distributed WITHOUT ANY WARRANTY; without even
the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE. See the above copyright notices for more information.
=========================================================================*/
#ifndef _itkFastMarchingImageFilter_txx
#define _itkFastMarchingImageFilter_txx
#include "itkBinaryBallStructuringElement.h"
#include "itkBinaryThresholdImageFilter.h"
#include "itkBinaryErodeImageFilter.h"
#include "itkImageRegionConstIteratorWithIndex.h"
#include "itkImageRegionIterator.h"
#include "itkNumericTraits.h"
#include "vnl/vnl_math.h"
#include <algorithm>
#include "itkFastMarchingImageFilter.h"
namespace itk
{
/*
*
*/
template <class TLevelSet, class TSpeedImage>
FastMarchingImageFilter<TLevelSet,TSpeedImage>
::FastMarchingImageFilter()
: m_TrialHeap( )
{
this->ProcessObject::SetNumberOfRequiredInputs(0);
OutputSizeType outputSize;
outputSize.Fill( 16 );
typename LevelSetImageType::IndexType outputIndex;
outputIndex.Fill( 0 );
m_OutputRegion.SetSize( outputSize );
m_OutputRegion.SetIndex( outputIndex );
m_OutputOrigin.Fill( 0.0 );
m_OutputSpacing.Fill( 1.0 );
m_OverrideOutputInformation = false;
m_AlivePoints = NULL;
m_TrialPoints = NULL;
m_ProcessedPoints = NULL;
m_SpeedConstant = 1.0;
m_InverseSpeed = -1.0;
m_ManualLabelImage = false;
m_LabelImage = LabelImageType::New();
typedef typename LevelSetImageType::PixelType PixelType;
m_LargeValue = static_cast<PixelType>(
NumericTraits<PixelType>::max() / 2.0 );
m_StoppingValue = static_cast<double>( m_LargeValue );
m_CollectPoints = false;
m_NormalizationFactor = 1.0;
}
/*
*
*/
template <class TLevelSet, class TSpeedImage>
void
FastMarchingImageFilter<TLevelSet,TSpeedImage>
::PrintSelf(std::ostream& os, Indent indent) const
{
Superclass::PrintSelf(os,indent);
os << indent << "Alive points: " << m_AlivePoints.GetPointer() << std::endl;
os << indent << "Trial points: " << m_TrialPoints.GetPointer() << std::endl;
os << indent << "Speed constant: " << m_SpeedConstant << std::endl;
os << indent << "Stopping value: " << m_StoppingValue << std::endl;
os << indent << "Large Value: "
<< static_cast<typename NumericTraits<PixelType>::PrintType>(m_LargeValue)
<< std::endl;
os << indent << "Normalization Factor: " << m_NormalizationFactor <<
std::endl;
os << indent << "Collect points: " << m_CollectPoints << std::endl;
os << indent << "OverrideOutputInformation: ";
os << m_OverrideOutputInformation << std::endl;
os << indent << "OutputRegion: " << m_OutputRegion << std::endl;
os << indent << "OutputSpacing: " << m_OutputSpacing << std::endl;
os << indent << "OutputOrigin: " << m_OutputOrigin << std::endl;
}
/*
*
*/
template <class TLevelSet, class TSpeedImage>
void
FastMarchingImageFilter<TLevelSet,TSpeedImage>
::SetAlivePointsFromImage( LabelImagePointer image )
{
// Setup
typedef ImageRegionConstIteratorWithIndex< LabelImageType > IteratorType;
NodeContainer::Pointer nodes = NodeContainer::New();
nodes->Initialize();
IteratorType it( image, image->GetLargestPossibleRegion() );
// Walk image
unsigned int count = 0;
for (it.GoToBegin(); !it.IsAtEnd(); ++it)
{
if (it.Get() > NumericTraits< LabelPixelType >::Zero)
{
NodeType node;
node.SetIndex( it.GetIndex() );
nodes->InsertElement( count, node );
count++;
}
}
// Set nodes
this->SetAlivePoints( nodes );
this->Modified();
}
/*
*
*/
template <class TLevelSet, class TSpeedImage>
void
FastMarchingImageFilter<TLevelSet,TSpeedImage>
::SetTrialPointsFromImage( LabelImagePointer image )
{
// Setup
typedef ImageRegionConstIteratorWithIndex< LabelImageType > IteratorType;
NodeContainer::Pointer nodes = NodeContainer::New();
nodes->Initialize();
IteratorType it( image, image->GetLargestPossibleRegion() );
// Walk image
unsigned int count = 0;
for (it.GoToBegin(); !it.IsAtEnd(); ++it)
{
if (it.Get() > NumericTraits< LabelPixelType >::Zero)
{
NodeType node;
node.SetIndex( it.GetIndex() );
nodes->InsertElement( count, node );
count++;
}
}
// Set nodes
this->SetTrialPoints( nodes );
this->Modified();
}
/*
*
*/
template <class TLevelSet, class TSpeedImage>
void
FastMarchingImageFilter<TLevelSet,TSpeedImage>
::SetLabelImage( LabelImagePointer image )
{
m_ManualLabelImage = true;
m_LabelImage = image;
this->Modified();
}
/*
*
*/
template <class TLevelSet, class TSpeedImage>
void
FastMarchingImageFilter<TLevelSet,TSpeedImage>
::SetLabelImageFromContour( LabelImagePointer image )
{
if ( image.IsNull() )
{
return;
}
// Record that the user has set the label image
m_ManualLabelImage = true;
// allocate memory for the LabelTypeImage
m_LabelImage->CopyInformation( image );
m_LabelImage->SetBufferedRegion( image->GetBufferedRegion() );
m_LabelImage->Allocate();
// threshold the given image
typedef BinaryThresholdImageFilter< LabelImageType, LabelImageType >
ThresholdFilterType;
ThresholdFilterType::Pointer filterThreshold = ThresholdFilterType::New();
filterThreshold->SetInput( image );
filterThreshold->SetLowerThreshold( NumericTraits<LabelPixelType>::One );
filterThreshold->SetUpperThreshold( NumericTraits<LabelPixelType>::max() );
// setup the structuring element
typedef BinaryBallStructuringElement< LabelPixelType,
TLevelSet::ImageDimension >
KernelType;
KernelType kernel;
kernel.SetRadius( 1 );
kernel.CreateStructuringElement( );
// erode the thresholded image
typedef BinaryErodeImageFilter< LabelImageType, LabelImageType, KernelType >
ErodeFilterType;
ErodeFilterType::Pointer filterErode = ErodeFilterType::New();
filterErode->SetInput( filterThreshold->GetOutput() );
filterErode->SetKernel( kernel );
filterErode->Update( );
// walk the given and eroded images to set label values
typedef ImageRegionIterator< LabelImageType > LabelIteratorType;
LabelIteratorType itLabel( m_LabelImage,
m_LabelImage->GetLargestPossibleRegion() );
typedef ImageRegionConstIteratorWithIndex< LabelImageType > IteratorType;
IteratorType itImage( image, image->GetLargestPossibleRegion() );
IteratorType itErode( filterErode->GetOutput(),
filterErode->GetOutput()->GetLargestPossibleRegion() );
for (itLabel.GoToBegin(), itImage.GoToBegin(), itErode.GoToBegin();
!itLabel.IsAtEnd();
++itLabel, ++itImage, ++itErode)
{
if (itErode.Get() > NumericTraits< LabelPixelType >::Zero)
{
// an alive point
itLabel.Set( AlivePoint );
}
else if (itImage.Get() > NumericTraits< LabelPixelType >::Zero)
{
// a trial point
itLabel.Set( TrialPoint );
}
else
{
// a far point
itLabel.Set( FarPoint );
}
}
this->Modified();
}
/*
*
*/
template <class TLevelSet, class TSpeedImage>
void
FastMarchingImageFilter<TLevelSet,TSpeedImage>
::GenerateOutputInformation()
{
// copy output information from input image
Superclass::GenerateOutputInformation();
// use user-specified output information
if ( this->GetInput() == NULL || m_OverrideOutputInformation )
{
LevelSetPointer output = this->GetOutput();
output->SetLargestPossibleRegion( m_OutputRegion );
output->SetSpacing( m_OutputSpacing );
output->SetOrigin( m_OutputOrigin );
}
}
/*
*
*/
template <class TLevelSet, class TSpeedImage>
void
FastMarchingImageFilter<TLevelSet,TSpeedImage>
::EnlargeOutputRequestedRegion(
DataObject *output )
{
// enlarge the requested region of the output
// to the whole data set
TLevelSet * imgData;
imgData = dynamic_cast<TLevelSet*>( output );
if ( imgData )
{
imgData->SetRequestedRegionToLargestPossibleRegion();
}
else
{
// Pointer could not be cast to TLevelSet *
itkWarningMacro(<< "itk::FastMarchingImageFilter" <<
"::EnlargeOutputRequestedRegion cannot cast "
<< typeid(output).name() << " to "
<< typeid(TLevelSet*).name() );
}
}
/*
*
*/
template <class TLevelSet, class TSpeedImage>
void
FastMarchingImageFilter<TLevelSet,TSpeedImage>
::Initialize( LevelSetImageType * output )
{
// allocate memory for the output buffer
output->SetBufferedRegion( output->GetRequestedRegion() );
output->Allocate();
// cache some buffered region information
m_BufferedRegion = output->GetBufferedRegion();
m_StartIndex = m_BufferedRegion.GetIndex();
m_LastIndex = m_StartIndex + m_BufferedRegion.GetSize();
typename LevelSetImageType::OffsetType offset;
offset.Fill( 1 );
m_LastIndex -= offset;
// set all output value to infinity
typedef ImageRegionIterator<LevelSetImageType>
OutputIterator;
OutputIterator outIt ( output, output->GetBufferedRegion() );
PixelType outputPixel;
outputPixel = m_LargeValue;
for ( outIt.GoToBegin(); !outIt.IsAtEnd(); ++outIt )
{
outIt.Set( outputPixel );
}
// make sure the heap is empty
while ( !m_TrialHeap.empty() )
{
m_TrialHeap.pop();
}
// check if we need to create the label image
if (m_ManualLabelImage)
{
// walk the image and add trial points to heap and output
typedef ImageRegionConstIteratorWithIndex< LabelImageType > IteratorType;
IteratorType it( m_LabelImage, m_LabelImage->GetLargestPossibleRegion() );
for (it.GoToBegin(); !it.IsAtEnd(); ++it)
{
if (it.Get() == static_cast< LabelPixelType >(TrialPoint))
{
AxisNodeType node;
node.SetIndex( it.GetIndex() );
m_TrialHeap.push( node );
output->SetPixel( it.GetIndex(), 0.0F );
}
else if (it.Get() == static_cast< LabelPixelType >(AlivePoint))
{
output->SetPixel( it.GetIndex(), 0.0F );
}
}
// no more work, return
return;
}
// only get this far if creating label image from points
// allocate memory for the LabelTypeImage
m_LabelImage->CopyInformation( output );
m_LabelImage->SetBufferedRegion( output->GetBufferedRegion() );
m_LabelImage->Allocate();
// set all points type to FarPoint
typedef ImageRegionIterator< LabelImageType >
LabelIterator;
LabelIterator typeIt( m_LabelImage, m_LabelImage->GetBufferedRegion() );
for ( typeIt.GoToBegin(); !typeIt.IsAtEnd(); ++typeIt )
{
typeIt.Set( FarPoint );
}
// process input alive points
AxisNodeType node;
if ( m_AlivePoints )
{
typename NodeContainer::ConstIterator pointsIter = m_AlivePoints->Begin();
typename NodeContainer::ConstIterator pointsEnd = m_AlivePoints->End();
for ( ; pointsIter != pointsEnd; ++pointsIter )
{
// get node from alive points container
node = pointsIter.Value();
// check if node index is within the output level set
if ( !m_BufferedRegion.IsInside( node.GetIndex() ) )
{
continue;
}
// make this an alive point
m_LabelImage->SetPixel( node.GetIndex(), AlivePoint );
output->SetPixel( node.GetIndex(), node.GetValue() );
}
}
// process the input trial points
if ( m_TrialPoints )
{
typename NodeContainer::ConstIterator pointsIter = m_TrialPoints->Begin();
typename NodeContainer::ConstIterator pointsEnd = m_TrialPoints->End();
for ( ; pointsIter != pointsEnd; ++pointsIter )
{
// get node from trial points container
node = pointsIter.Value();
// check if node index is within the output level set
if ( !m_BufferedRegion.IsInside( node.GetIndex() ) )
{
continue;
}
// make this a trial point
m_LabelImage->SetPixel( node.GetIndex(), TrialPoint );
outputPixel = node.GetValue();
output->SetPixel( node.GetIndex(), outputPixel );
m_TrialHeap.push( node );
}
}
}
/*
*
*/
template <class TLevelSet, class TSpeedImage>
void
FastMarchingImageFilter<TLevelSet,TSpeedImage>
::GenerateData()
{
LevelSetPointer output = this->GetOutput();
SpeedImageConstPointer speedImage = this->GetInput();
this->Initialize( output );
if ( m_CollectPoints )
{
m_ProcessedPoints = NodeContainer::New();
}
// process points on the heap
AxisNodeType node;
double currentValue;
double oldProgress = 0;
this->UpdateProgress( 0.0 ); // Send first progress event
while ( !m_TrialHeap.empty() )
{
// get the node with the smallest value
node = m_TrialHeap.top();
m_TrialHeap.pop();
// does this node contain the current value ?
currentValue = (double) output->GetPixel( node.GetIndex() );
if ( node.GetValue() != currentValue )
{
continue;
}
// is this node already alive ?
if ( m_LabelImage->GetPixel( node.GetIndex() ) != TrialPoint )
{
continue;
}
if ( currentValue > m_StoppingValue )
{
break;
}
if ( m_CollectPoints )
{
m_ProcessedPoints->InsertElement( m_ProcessedPoints->Size(), node );
}
// set this node as alive
m_LabelImage->SetPixel( node.GetIndex(), AlivePoint );
// update its neighbors
this->UpdateNeighbors( node.GetIndex(), speedImage, output );
// Send events every certain number of points.
const double newProgress = currentValue / m_StoppingValue;
if( newProgress - oldProgress > 0.01 ) // update every 1%
{
this->UpdateProgress( newProgress );
oldProgress = newProgress;
if( this->GetAbortGenerateData() )
{
this->InvokeEvent( AbortEvent() );
this->ResetPipeline();
ProcessAborted e(__FILE__,__LINE__);
e.SetDescription("Process aborted.");
e.SetLocation(ITK_LOCATION);
throw e;
}
}
}
}
/*
*
*/
template <class TLevelSet, class TSpeedImage>
void
FastMarchingImageFilter<TLevelSet,TSpeedImage>
::UpdateNeighbors(
const IndexType& index,
const SpeedImageType * speedImage,
LevelSetImageType * output )
{
IndexType neighIndex = index;
for ( unsigned int j = 0; j < SetDimension; j++ )
{
// update left neighbor
if( index[j] > m_StartIndex[j] )
{
neighIndex[j] = index[j] - 1;
}
if ( m_LabelImage->GetPixel( neighIndex ) != AlivePoint )
{
this->UpdateValue( neighIndex, speedImage, output );
}
// update right neighbor
if ( index[j] < m_LastIndex[j] )
{
neighIndex[j] = index[j] + 1;
}
if ( m_LabelImage->GetPixel( neighIndex ) != AlivePoint )
{
this->UpdateValue( neighIndex, speedImage, output );
}
//reset neighIndex
neighIndex[j] = index[j];
}
}
/*
*
*/
template <class TLevelSet, class TSpeedImage>
double
FastMarchingImageFilter<TLevelSet,TSpeedImage>
::UpdateValue(
const IndexType& index,
const SpeedImageType * speedImage,
LevelSetImageType * output )
{
IndexType neighIndex = index;
typename TLevelSet::PixelType neighValue;
PixelType outputPixel;
AxisNodeType node;
for ( unsigned int j = 0; j < SetDimension; j++ )
{
node.SetValue( m_LargeValue );
// find smallest valued neighbor in this dimension
for( int s = -1; s < 2; s = s + 2 )
{
neighIndex[j] = index[j] + s;
if( neighIndex[j] > m_LastIndex[j] ||
neighIndex[j] < m_StartIndex[j] )
{
continue;
}
if ( m_LabelImage->GetPixel( neighIndex ) == AlivePoint )
{
outputPixel = output->GetPixel( neighIndex );
neighValue = outputPixel ;
if( node.GetValue() > neighValue )
{
node.SetValue( neighValue );
node.SetIndex( neighIndex );
}
}
}
// put the minimum neighbor onto the heap
m_NodesUsed[j] = node;
m_NodesUsed[j].SetAxis(j);
// reset neighIndex
neighIndex[j] = index[j];
}
// sort the local list
std::sort( m_NodesUsed, m_NodesUsed + SetDimension );
// solve quadratic equation
double aa, bb, cc;
double solution = m_LargeValue;
aa = 0.0;
bb = 0.0;
if ( speedImage )
{
typedef typename SpeedImageType::PixelType SpeedPixelType;
cc = (double) speedImage->GetPixel( index ) / m_NormalizationFactor;
cc = -1.0 * vnl_math_sqr( 1.0 / cc );
}
else
{
cc = m_InverseSpeed;
}
OutputSpacingType spacing = this->GetOutput()->GetSpacing();
double discrim;
for ( unsigned int j = 0; j < SetDimension; j++ )
{
node = m_NodesUsed[j];
if ( solution >= node.GetValue() )
{
const int axis = node.GetAxis();
const double spaceFactor = vnl_math_sqr( 1.0 / spacing[axis] );
const double value = double(node.GetValue());
aa += spaceFactor;
bb += value * spaceFactor;
cc += vnl_math_sqr( value ) * spaceFactor;
discrim = vnl_math_sqr( bb ) - aa * cc;
if ( discrim < 0.0 )
{
// Discriminant of quadratic eqn. is negative
ExceptionObject err(__FILE__, __LINE__);
err.SetLocation( ITK_LOCATION );
err.SetDescription( "Discriminant of quadratic equation is negative" );
throw err;
}
solution = ( vcl_sqrt( discrim ) + bb ) / aa;
}
else
{
break;
}
}
if ( solution < m_LargeValue )
{
// write solution to m_OutputLevelSet
outputPixel = static_cast<PixelType>( solution );
output->SetPixel( index, outputPixel );
// insert point into trial heap
m_LabelImage->SetPixel( index, TrialPoint );
node.SetValue( static_cast<PixelType>( solution ) );
node.SetIndex( index );
m_TrialHeap.push( node );
}
return solution;
}
} // namespace itk
#endif
More information about the Insight-users
mailing list