+// =========================================================================
+// @author Leonardo Florez Valencia
+// @email florez-l@javeriana.edu.co
+// =========================================================================
+
#ifndef __fpa__Image__SkeletonFilter__hxx__
#define __fpa__Image__SkeletonFilter__hxx__
-#include <queue>
-#include <itkImageRegionConstIteratorWithIndex.h>
+#include <itkImage.h>
+#include <itkImageRegionIteratorWithIndex.h>
+#include <itkMinimumMaximumImageCalculator.h>
+#include <fpa/Image/Functors/Dijkstra/Invert.h>
// -------------------------------------------------------------------------
-#define fpa_Image_SkeletonFilter_InputMacro( i_n, i_t, i_i ) \
- template< class _TDistanceMap, class _TCostMap > \
- typename fpa::Image::SkeletonFilter< _TDistanceMap, _TCostMap >:: \
- i_t* fpa::Image::SkeletonFilter< _TDistanceMap, _TCostMap >:: \
- Get##i_n( ) \
- { \
- return( \
- dynamic_cast< i_t* >( this->Superclass::GetInput( i_i ) ) \
- ); \
- } \
- template< class _TDistanceMap, class _TCostMap > \
- const \
- typename fpa::Image::SkeletonFilter< _TDistanceMap, _TCostMap >:: \
- i_t* fpa::Image::SkeletonFilter< _TDistanceMap, _TCostMap >:: \
- Get##i_n( ) const \
- { \
- return( \
- dynamic_cast< const i_t* >( this->Superclass::GetInput( i_i ) ) \
- ); \
- } \
- template< class _TDistanceMap, class _TCostMap > \
- void fpa::Image::SkeletonFilter< _TDistanceMap, _TCostMap >:: \
- Set##i_n( i_t* input ) \
- { \
- this->Superclass::SetNthInput( i_i, input ); \
- }
-
-fpa_Image_SkeletonFilter_InputMacro( DistanceMap, TDistanceMap, 0 );
-fpa_Image_SkeletonFilter_InputMacro( CostMap, TCostMap, 1 );
-fpa_Image_SkeletonFilter_InputMacro( MinimumSpanningTree, TMST, 2 );
+template< class _TInputImage, class _TDistanceMap >
+fpa::Image::SkeletonFilter< _TInputImage, _TDistanceMap >::_TDijkstra::
+_TDijkstra( )
+ : Superclass( )
+{
+ // Prepare weight function
+ typedef fpa::Image::Functors::Dijkstra::Invert< TOutputImage, TScalar > _TWeight;
+ typename _TWeight::Pointer weight = _TWeight::New( );
+ weight->SetAlpha( 1 );
+ weight->SetBeta( 1 );
+ this->SetWeightFunction( weight );
+}
// -------------------------------------------------------------------------
-#define fpa_Image_SkeletonFilter_OutputMacro( o_n, o_t, o_i ) \
- template< class _TDistanceMap, class _TCostMap > \
- typename fpa::Image::SkeletonFilter< _TDistanceMap, _TCostMap >:: \
- o_t* fpa::Image::SkeletonFilter< _TDistanceMap, _TCostMap >:: \
- Get##o_n( ) \
- { \
- return( \
- dynamic_cast< o_t* >( this->Superclass::GetOutput( o_i ) ) \
- ); \
- } \
- template< class _TDistanceMap, class _TCostMap > \
- const typename \
- fpa::Image::SkeletonFilter< _TDistanceMap, _TCostMap >:: \
- o_t* fpa::Image::SkeletonFilter< _TDistanceMap, _TCostMap >:: \
- Get##o_n( ) const \
- { \
- return( \
- dynamic_cast< const o_t* >( this->Superclass::GetOutput( o_i ) ) \
- ); \
- }
-
-fpa_Image_SkeletonFilter_OutputMacro( Skeleton, TSkeleton, 0 );
-fpa_Image_SkeletonFilter_OutputMacro( EndPoints, TIndices, 1 );
-fpa_Image_SkeletonFilter_OutputMacro( Bifurcations, TIndices, 2 );
-fpa_Image_SkeletonFilter_OutputMacro( Marks, TMarks, 3 );
+template< class _TInputImage, class _TDistanceMap >
+fpa::Image::SkeletonFilter< _TInputImage, _TDistanceMap >::_TDijkstra::
+~_TDijkstra( )
+{
+}
// -------------------------------------------------------------------------
-template< class _TDistanceMap, class _TCostMap >
-fpa::Image::SkeletonFilter< _TDistanceMap, _TCostMap >::
-SkeletonFilter( )
- : Superclass( )
+template< class _TInputImage, class _TDistanceMap >
+void fpa::Image::SkeletonFilter< _TInputImage, _TDistanceMap >::_TDijkstra::
+_BeforeGenerateData( )
{
- this->SetNumberOfRequiredInputs( 3 );
- this->SetNumberOfRequiredOutputs( 3 );
-
- typename TIndices::Pointer end_points = TIndices::New( );
- typename TIndices::Pointer bifurcations = TIndices::New( );
- typename TSkeleton::Pointer skeleton = TSkeleton::New( );
- typename TMarks::Pointer marks = TMarks::New( );
- this->SetNthOutput( 0, skeleton.GetPointer( ) );
- this->SetNthOutput( 1, end_points.GetPointer( ) );
- this->SetNthOutput( 2, bifurcations.GetPointer( ) );
- this->SetNthOutput( 3, marks.GetPointer( ) );
+ this->Superclass::_BeforeGenerateData( );
+ this->m_SkeletonQueue.clear( );
}
// -------------------------------------------------------------------------
-template< class _TDistanceMap, class _TCostMap >
-fpa::Image::SkeletonFilter< _TDistanceMap, _TCostMap >::
-~SkeletonFilter( )
+template< class _TInputImage, class _TDistanceMap >
+void fpa::Image::SkeletonFilter< _TInputImage, _TDistanceMap >::_TDijkstra::
+_UpdateOutputValue( const TNode& n )
+{
+ typedef typename _TSkeletonQueue::value_type _TSkeletonQueueValue;
+
+ this->Superclass::_UpdateOutputValue( n );
+ double d = double( this->GetInput( )->GetPixel( n.Vertex ) );
+ if( d >= double( 0 ) )
+ {
+ // Update skeleton candidates
+ d += double( 1e-5 );
+ double v = double( n.Value ) / ( d * d );
+ this->m_SkeletonQueue.insert( _TSkeletonQueueValue( v, n.Vertex ) );
+
+ } // fi
+}
+
+// -------------------------------------------------------------------------
+template< class _TInputImage, class _TDistanceMap >
+itk::ModifiedTimeType
+fpa::Image::SkeletonFilter< _TInputImage, _TDistanceMap >::
+GetMTime( ) const
{
+ itk::ModifiedTimeType t = this->Superclass::GetMTime( );
+ itk::ModifiedTimeType q = this->m_DistanceMap->GetMTime( );
+ return( ( q < t )? q: t );
}
// -------------------------------------------------------------------------
-template< class _TDistanceMap, class _TCostMap >
-void fpa::Image::SkeletonFilter< _TDistanceMap, _TCostMap >::
-GenerateData( )
+template< class _TInputImage, class _TDistanceMap >
+void fpa::Image::SkeletonFilter< _TInputImage, _TDistanceMap >::
+SetInput( TInputImage* input )
{
- // 0. I/O objects
- const TDistanceMap* dmap = this->GetDistanceMap( );
- const TCostMap* cmap = this->GetCostMap( );
- const TMST* mst = this->GetMinimumSpanningTree( );
- TIndices* ep = this->GetEndPoints( );
- TIndices* bi = this->GetBifurcations( );
- TSkeleton* sk = this->GetSkeleton( );
-
- // 1. Check input correspondance
- // TODO
-
- // 2. Detect end-points
- this->_EndPoints( dmap, cmap, mst, ep->Get( ) );
-
- // 3. Build skeleton and keep track of bifurcations
- this->_Skeleton( dmap, cmap, mst, ep->Get( ), bi->Get( ), sk );
+ this->Superclass::SetNthInput( 0, input );
}
// -------------------------------------------------------------------------
-template< class _TDistanceMap, class _TCostMap >
-void fpa::Image::SkeletonFilter< _TDistanceMap, _TCostMap >::
-_EndPoints(
- const TDistanceMap* dmap,
- const TCostMap* cmap,
- const TMST* mst,
- TIndicesData& end_points
- )
+template< class _TInputImage, class _TDistanceMap >
+typename fpa::Image::SkeletonFilter< _TInputImage, _TDistanceMap >::
+TInputImage* fpa::Image::SkeletonFilter< _TInputImage, _TDistanceMap >::
+GetInput( )
{
- typedef itk::ImageRegionConstIteratorWithIndex< _TDistanceMap > _TDistMapIt;
- typedef itk::ImageRegionConstIteratorWithIndex< _TCostMap > _TCostMapIt;
- typedef std::multimap< double, TIndex, std::greater< double > > _TQueue;
- typedef typename _TQueue::value_type _TQueueValue;
- typedef itk::Image< unsigned char, _TCostMap::ImageDimension > _TMarks;
+ return( dynamic_cast< TInputImage* >( this->Superclass::GetInput( 0 ) ) );
+}
- // Some values
- // typename _TMarks::Pointer marks = _TMarks::New( );
- auto marks = this->GetMarks( );
- marks->SetLargestPossibleRegion( dmap->GetLargestPossibleRegion( ) );
- marks->SetRequestedRegion( dmap->GetRequestedRegion( ) );
- marks->SetBufferedRegion( dmap->GetBufferedRegion( ) );
- marks->SetSpacing( dmap->GetSpacing( ) );
- marks->SetOrigin( dmap->GetOrigin( ) );
- marks->SetDirection( dmap->GetDirection( ) );
- marks->Allocate( );
- marks->FillBuffer( 0 );
-
- // Create queue
- _TQueue queue;
- _TDistMapIt dIt( dmap, dmap->GetRequestedRegion( ) );
- _TCostMapIt cIt( cmap, cmap->GetRequestedRegion( ) );
- dIt.GoToBegin( );
- cIt.GoToBegin( );
- for( ; !dIt.IsAtEnd( ) && !cIt.IsAtEnd( ); ++dIt, ++cIt )
+// -------------------------------------------------------------------------
+template< class _TInputImage, class _TDistanceMap >
+const typename fpa::Image::SkeletonFilter< _TInputImage, _TDistanceMap >::
+TInputImage* fpa::Image::SkeletonFilter< _TInputImage, _TDistanceMap >::
+GetInput( ) const
+{
+ return(
+ dynamic_cast< const TInputImage* >( this->Superclass::GetInput( 0 ) )
+ );
+}
+
+// -------------------------------------------------------------------------
+template< class _TInputImage, class _TDistanceMap >
+typename fpa::Image::SkeletonFilter< _TInputImage, _TDistanceMap >::
+TSkeleton* fpa::Image::SkeletonFilter< _TInputImage, _TDistanceMap >::
+GetOutput( )
+{
+ return( dynamic_cast< TSkeleton* >( this->Superclass::GetOutput( 0 ) ) );
+}
+
+// -------------------------------------------------------------------------
+template< class _TInputImage, class _TDistanceMap >
+const typename fpa::Image::SkeletonFilter< _TInputImage, _TDistanceMap >::
+TSkeleton* fpa::Image::SkeletonFilter< _TInputImage, _TDistanceMap >::
+GetOutput( ) const
+{
+ return(
+ dynamic_cast< const TSkeleton* >( this->Superclass::GetOutput( 0 ) )
+ );
+}
+
+// -------------------------------------------------------------------------
+template< class _TInputImage, class _TDistanceMap >
+fpa::Image::SkeletonFilter< _TInputImage, _TDistanceMap >::
+SkeletonFilter( )
+ : Superclass( ),
+ m_SeedFromMaximumDistance( false )
+{
+ this->SetNumberOfRequiredInputs( 1 );
+ this->SetNumberOfRequiredOutputs( 1 );
+ this->SetNthOutput( 0, TSkeleton::New( ) );
+
+ this->m_DistanceMap = TDistanceMap::New( );
+}
+
+// -------------------------------------------------------------------------
+template< class _TInputImage, class _TDistanceMap >
+fpa::Image::SkeletonFilter< _TInputImage, _TDistanceMap >::
+~SkeletonFilter( )
+{
+}
+
+// -------------------------------------------------------------------------
+template< class _TInputImage, class _TDistanceMap >
+void fpa::Image::SkeletonFilter< _TInputImage, _TDistanceMap >::
+GenerateData( )
+{
+ // Update distance map
+ this->m_DistanceMap->SetInput( this->GetInput( ) );
+ this->m_DistanceMap->Update( );
+
+ // Correct seed
+ if( this->m_SeedFromMaximumDistance )
{
- double d = double( dIt.Get( ) );
- if( d > 0 )
+ typedef itk::MinimumMaximumImageCalculator< TOutputImage > _TMinMax;
+ typename _TMinMax::Pointer minmax = _TMinMax::New( );
+ minmax->SetImage( this->m_DistanceMap->GetOutput( ) );
+ minmax->Compute( );
+ this->m_Seed = minmax->GetIndexOfMaximum( );
+
+ } // fi
+
+ // Compute MST
+ typename _TDijkstra::Pointer dijkstra = _TDijkstra::New( );
+ dijkstra->SetInput( this->m_DistanceMap->GetOutput( ) );
+ dijkstra->AddSeed( this->m_Seed );
+ dijkstra->Update( );
+
+ // Compute end-points
+ const _TMST* mst = dijkstra->GetMinimumSpanningTree( );
+ std::vector< TIndex > end_points;
+ this->_EndPoints(
+ end_points, this->m_DistanceMap->GetOutput( ),
+ mst, dijkstra->GetSkeletonQueue( )
+ );
+
+ // Compute symbolic branches
+ typedef std::map< TIndex, TIndex, typename TIndex::LexicographicCompare > _TTags;
+ _TTags tags, branches;
+ typename std::vector< TIndex >::const_iterator eIt = end_points.begin( );
+ for( ; eIt != end_points.end( ); ++eIt )
+ {
+ // Tag path
+ TIndex it = *eIt;
+ TIndex p = mst->GetParent( it );
+ typename _TTags::iterator bIt = tags.end( );
+ while( it != p && bIt == tags.end( ) )
+ {
+ typename _TTags::iterator tIt = tags.find( it );
+ if( tIt != tags.end( ) )
+ {
+ // Ok, a bifurcation point has been found
+ // branch1: tIt->second <-> it (ok)
+ branches[ tIt->second ] = it;
+
+ // branch2: *eit <-> it (ok)
+ branches[ *eIt ] = it;
+
+ // branch3: it <-> until next bifurcation
+ bIt = tIt;
+ }
+ else
+ tags[ it ] = *eIt;
+ it = p;
+ p = mst->GetParent( it );
+
+ } // elihw
+ if( bIt != tags.end( ) )
+ {
+ TIndex pTag = bIt->second;
+ TIndex nTag = bIt->first;
+ it = bIt->first;
+ p = it;
+ while( tags[ it ] == pTag )
+ {
+ tags[ it ] = nTag;
+ p = it;
+ it = mst->GetParent( it );
+
+ } // elihw
+ tags[ it ] = nTag;
+ branches[ bIt->first ] = p;
+ }
+ else
{
- double v = double( cIt.Get( ) ) / ( d * d );
- queue.insert( _TQueueValue( v, dIt.GetIndex( ) ) );
+ tags[ it ] = *eIt;
+ branches[ *eIt ] = it;
} // fi
} // rof
- // BFS from maximum queue
- auto region = dmap->GetRequestedRegion( );
- double init_v = queue.begin( )->first;
- while( queue.size( ) > 0 )
+ // Fill full branches
+ typedef typename _TMST::TVertices _TVertices;
+ typedef typename TSkeleton::TPath _TPath;
+
+ TSkeleton* sk = this->GetOutput( );
+ typename _TTags::const_iterator bIt = branches.begin( );
+ for( ; bIt != branches.end( ); ++bIt )
{
- // Get node
- auto nIt = queue.begin( );
- auto n = *nIt;
- queue.erase( nIt );
+ _TVertices v = mst->GetPath( bIt->first, bIt->second );
+ typename _TPath::Pointer path = _TPath::New( );
+ path->SetReferenceImage( this->GetInput( ) );
+ typename _TVertices::const_reverse_iterator vIt = v.rbegin( );
+ for( ; vIt != v.rend( ); ++vIt )
+ path->AddVertex( *vIt );
+ sk->AddBranch( path );
- unsigned char m = marks->GetPixel( n.second );
- // if( ( m & 0x01 ) == 0x01 )
- if( m != 0 || ( n.first / init_v ) < double( 1e-1 ) )
- continue;
+ } // rof
+}
- // Mark it and update end-points
- m |= 0x01;
- marks->SetPixel( n.second, m );
- end_points.insert( n.second );
-
- // Get path
- typename TMST::TPath::Pointer path;
- mst->GetPath( path, n.second );
- for( unsigned long i = 0; i < path->GetSize( ); ++i )
- {
- TIndex idx = path->GetVertex( i );
- typename _TCostMap::PointType cnt;
- cmap->TransformIndexToPhysicalPoint( idx, cnt );
- double d = double( 2 ) * double( dmap->GetPixel( idx ) );
-
- // Mark sphere
- std::queue< TIndex > q;
- q.push( idx );
- while( q.size( ) > 0 )
- {
- TIndex v = q.front( );
- q.pop( );
- unsigned char m = marks->GetPixel( v );
- if( ( m & 0x02 ) == 0x02 )
- continue;
- m |= 0x02;
- marks->SetPixel( v, m );
-
- for( unsigned int x = 0; x < _TCostMap::ImageDimension; ++x )
- {
- for( int y = -1; y <= 1; y += 2 )
- {
- TIndex w = v;
- w[ x ] += y;
- if( region.IsInside( w ) )
- {
- typename _TCostMap::PointType p;
- cmap->TransformIndexToPhysicalPoint( w, p );
- if( cnt.EuclideanDistanceTo( p ) <= d )
- q.push( w );
-
- } // fi
-
- } // rof
-
- } // rof
+// -------------------------------------------------------------------------
+template< class _TInputImage, class _TDistanceMap >
+template< class _TMarksPointer >
+void fpa::Image::SkeletonFilter< _TInputImage, _TDistanceMap >::
+_MarkSphere(
+ _TMarksPointer& marks, const TOutputImage* dmap, const TIndex& center
+ )
+{
+ typedef typename _TMarksPointer::ObjectType _TMarks;
+ typedef itk::ImageRegionIteratorWithIndex< _TMarks > _TMarksIt;
- } // elihw
+ static const double _eps = std::sqrt( double( Self::Dimension + 1 ) );
+ typename _TMarks::SpacingType spac = dmap->GetSpacing( );
+ typename _TMarks::RegionType region = dmap->GetRequestedRegion( );
+
+ typename _TMarks::PointType cnt;
+ dmap->TransformIndexToPhysicalPoint( center, cnt );
+ double r = double( dmap->GetPixel( center ) ) * _eps;
+
+ TIndex i0, i1;
+ for( unsigned int d = 0; d < Self::Dimension; ++d )
+ {
+ long off = long( std::ceil( r / double( spac[ d ] ) ) );
+ if( off < 3 )
+ off = 3;
+ i0[ d ] = center[ d ] - off;
+ i1[ d ] = center[ d ] + off;
+
+ if( i0[ d ] < region.GetIndex( )[ d ] )
+ i0[ d ] = region.GetIndex( )[ d ];
- } // rof
+ if( i1[ d ] >= region.GetIndex( )[ d ] + region.GetSize( )[ d ] )
+ i1[ d ] = region.GetIndex( )[ d ] + region.GetSize( )[ d ] - 1;
- } // elihw
+ } // rof
+
+ typename _TMarks::SizeType size;
+ for( unsigned int d = 0; d < Self::Dimension; ++d )
+ size[ d ] = i1[ d ] - i0[ d ] + 1;
+
+ typename _TMarks::RegionType neighRegion;
+ neighRegion.SetIndex( i0 );
+ neighRegion.SetSize( size );
+
+ _TMarksIt mIt( marks, neighRegion );
+ for( mIt.GoToBegin( ); !mIt.IsAtEnd( ); ++mIt )
+ mIt.Set( true );
}
// -------------------------------------------------------------------------
-template< class _TDistanceMap, class _TCostMap >
-void fpa::Image::SkeletonFilter< _TDistanceMap, _TCostMap >::
-_Skeleton(
- const TDistanceMap* dmap,
- const TCostMap* cmap,
- const TMST* mst,
- const TIndicesData& end_points,
- TIndicesData& bifurcations,
- TSkeleton* skeleton
+template< class _TInputImage, class _TDistanceMap >
+void fpa::Image::SkeletonFilter< _TInputImage, _TDistanceMap >::
+_EndPoints(
+ std::vector< TIndex >& end_points,
+ const TOutputImage* dmap,
+ const _TMST* mst,
+ const _TSkeletonQueue& queue
)
{
- typedef typename TMST::TPath _TPath;
+ typedef typename _TSkeletonQueue::value_type _TSkeletonQueueValue;
- for( auto eIt = end_points.begin( ); eIt != end_points.end( ); ++eIt )
+ // Some values
+ typedef itk::Image< bool, Self::Dimension > _TMarks;
+ typename _TMarks::Pointer marks = _TMarks::New( );
+ marks->SetLargestPossibleRegion( mst->GetLargestPossibleRegion( ) );
+ marks->SetRequestedRegion( mst->GetRequestedRegion( ) );
+ marks->SetBufferedRegion( mst->GetBufferedRegion( ) );
+ marks->SetSpacing( mst->GetSpacing( ) );
+ marks->SetOrigin( mst->GetOrigin( ) );
+ marks->SetDirection( mst->GetDirection( ) );
+ marks->Allocate( );
+ marks->FillBuffer( false );
+
+ // Get candidates in maximum to minimum iteration
+ typename _TSkeletonQueue::const_reverse_iterator nIt = queue.rbegin( );
+ for( ; nIt != queue.rend( ); ++nIt )
{
- typename _TPath::Pointer path;
- mst->GetPath( path, *eIt );
- skeleton->AddBranch( path );
+ // Mark it and update end-points
+ if( !( marks->GetPixel( nIt->second ) ) )
+ {
+ marks->SetPixel( nIt->second, true );
+ end_points.push_back( nIt->second );
+
+ // Mark path
+ TIndex it = nIt->second;
+ TIndex p = mst->GetParent( it );
+ while( it != p )
+ {
+ this->_MarkSphere( marks, dmap, it );
+ it = p;
+ p = mst->GetParent( it );
+
+ } // elihw
+ this->_MarkSphere( marks, dmap, it );
+
+ } // fi
} // rof
}
git://git.creatis.insa-lyon.fr / FrontAlgorithms.git / blobdiff