+// =========================================================================
+// @author Leonardo Florez Valencia
+// @email florez-l@javeriana.edu.co
+// =========================================================================
+
#ifndef __fpa__Base__Dijkstra__hxx__
#define __fpa__Base__Dijkstra__hxx__
-#include <algorithm>
-#include <limits>
-
// -------------------------------------------------------------------------
-template< class _TSuperclass, class _TMST >
-_TMST* fpa::Base::Dijkstra< _TSuperclass, _TMST >::
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
+typename
+fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
+TMST* fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
GetMinimumSpanningTree( )
{
return(
- dynamic_cast< _TMST* >(
+ dynamic_cast< TMST* >(
this->itk::ProcessObject::GetOutput( this->m_MSTIndex )
)
);
}
// -------------------------------------------------------------------------
-template< class _TSuperclass, class _TMST >
-const _TMST* fpa::Base::Dijkstra< _TSuperclass, _TMST >::
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
+const typename
+fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
+TMST* fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
GetMinimumSpanningTree( ) const
{
return(
- dynamic_cast< const _TMST* >(
+ dynamic_cast< const TMST* >(
this->itk::ProcessObject::GetOutput( this->m_MSTIndex )
)
);
}
// -------------------------------------------------------------------------
-template< class _TSuperclass, class _TMST >
-fpa::Base::Dijkstra< _TSuperclass, _TMST >::
-Dijkstra( )
- : Superclass( )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
+const typename
+fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
+TIntensityFunctor*
+fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
+GetIntensityFunctor( ) const
{
- this->m_InitResult = TOutput( 0 );
- this->m_MSTIndex = this->GetNumberOfRequiredOutputs( );
- this->SetNumberOfRequiredOutputs( this->m_MSTIndex + 1 );
- this->itk::ProcessObject::SetNthOutput( this->m_MSTIndex, _TMST::New( ) );
+ return( this->m_IntensityFunctor );
}
// -------------------------------------------------------------------------
-template< class _TSuperclass, class _TMST >
-fpa::Base::Dijkstra< _TSuperclass, _TMST >::
-~Dijkstra( )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
+const typename
+fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
+TVertexFunctor*
+fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
+GetVertexFunctor( ) const
{
+ return( this->m_VertexFunctor );
}
// -------------------------------------------------------------------------
-template< class _TSuperclass, class _TMST >
-void fpa::Base::Dijkstra< _TSuperclass, _TMST >::
-_AfterGenerateData( )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
+void fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
+SetFunctor( TIntensityFunctor* functor )
{
- this->Superclass::_AfterGenerateData( );
-
- auto mst = this->GetMinimumSpanningTree( );
- mst->ClearSeeds( );
- for( auto s = this->m_Seeds.begin( ); s != this->m_Seeds.end( ); ++s )
- mst->AddSeed( s->Vertex );
- mst->SetCollisions( this->m_Collisions );
-}
+ if( this->m_IntensityFunctor.GetPointer( ) != functor )
+ {
+ this->m_IntensityFunctor = functor;
+ this->Modified( );
-// -------------------------------------------------------------------------
-template< class _TSuperclass, class _TMST >
-void fpa::Base::Dijkstra< _TSuperclass, _TMST >::
-_UpdateResult( const _TQueueNode& n )
-{
- this->Superclass::_UpdateResult( n );
- this->GetMinimumSpanningTree( )->SetParent( n.Vertex, n.Parent );
+ } // fi
}
// -------------------------------------------------------------------------
-template< class _TSuperclass, class _TMST >
-bool fpa::Base::Dijkstra< _TSuperclass, _TMST >::
-_UpdateValue( _TQueueNode& v, const _TQueueNode& p )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
+void fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
+SetFunctor( TVertexFunctor* functor )
{
- v.Result = this->m_CostFunction->Evaluate( p.Vertex, v.Vertex );
- if( this->m_CostConversionFunction.IsNotNull( ) )
- v.Result = this->m_CostConversionFunction->Evaluate( v.Result );
- if( v.Result >= TOutput( 0 ) )
- {
- v.Result += p.Result;
- return( true );
- }
- else
+ if( this->m_VertexFunctor.GetPointer( ) != functor )
{
- v.Result = this->m_InitResult;
- return( false );
+ this->m_VertexFunctor = functor;
+ this->Modified( );
} // fi
}
// -------------------------------------------------------------------------
-template< class _TSuperclass, class _TMST >
-unsigned long fpa::Base::Dijkstra< _TSuperclass, _TMST >::
-_QueueSize( ) const
-{
- return( this->m_Queue.size( ) );
-}
-
-// -------------------------------------------------------------------------
-template< class _TSuperclass, class _TMST >
-void fpa::Base::Dijkstra< _TSuperclass, _TMST >::
-_QueueClear( )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
+fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
+Dijkstra( )
+ : Superclass( ),
+ _TMarksInterface( this ),
+ _TSeedsInterface( this )
{
- this->m_Queue.clear( );
+ this->m_MSTIndex = this->GetNumberOfRequiredOutputs( );
+ this->SetNumberOfRequiredOutputs( this->m_MSTIndex + 1 );
+ this->itk::ProcessObject::SetNthOutput( this->m_MSTIndex, TMST::New( ) );
}
// -------------------------------------------------------------------------
-template< class _TSuperclass, class _TMST >
-void fpa::Base::Dijkstra< _TSuperclass, _TMST >::
-_QueuePush( const _TQueueNode& node )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
+fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
+~Dijkstra( )
{
- static _TQueueNodeCompare cmp;
- this->m_Queue.push_back( node );
- std::push_heap( this->m_Queue.begin( ), this->m_Queue.end( ), cmp );
}
// -------------------------------------------------------------------------
-template< class _TSuperclass, class _TMST >
-typename fpa::Base::Dijkstra< _TSuperclass, _TMST >::
-_TQueueNode fpa::Base::Dijkstra< _TSuperclass, _TMST >::
-_QueuePop( )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
+void fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
+GenerateData( )
{
- static _TQueueNodeCompare cmp;
- std::pop_heap( this->m_Queue.begin( ), this->m_Queue.end( ), cmp );
- _TQueueNode f = this->m_Queue.back( );
- this->m_Queue.pop_back( );
- return( f );
+ // Init objects
+ this->_ConfigureOutputs( std::numeric_limits< TOutputValue >::max( ) );
+ this->_InitMarks( this->GetNumberOfSeeds( ) );
+ TMST* mst = this->GetMinimumSpanningTree( );
+
+ // Init queue
+ std::vector< _TNode > q;
+ unsigned long frontId = 1;
+ typename TSeedsInterface::TSeeds::const_iterator sIt = this->BeginSeeds( );
+ for( ; sIt != this->EndSeeds( ); ++sIt )
+ q.push_back( _TNode( *sIt, *sIt, frontId++ ) );
+
+ // Main loop
+ while( q.size( ) > 0 )
+ {
+ // Get next candidate
+ std::pop_heap( q.begin( ), q.end( ) );
+ _TNode node = q.back( );
+ q.pop_back( );
+ if( this->_IsMarked( node.Vertex ) )
+ continue;
+ this->_Mark( node.Vertex, node.FrontId );
+
+ // Ok, pixel lays inside region
+ this->_SetOutputValue( node.Vertex, node.Cost );
+ mst->SetParent( node.Vertex, node.Parent );
+
+ // Add neighborhood
+ TVertices neighbors = this->_GetNeighbors( node.Vertex );
+ typename TVertices::const_iterator neighIt = neighbors.begin( );
+ bool coll = false;
+ while( neighIt != neighbors.end( ) && !coll )
+ {
+ TVertex neigh = *neighIt;
+ if( this->_IsMarked( neigh ) )
+ {
+ // Invoke stop at collisions
+ unsigned long nColl = this->_Collisions( node.Vertex, neigh );
+ if(
+ this->StopAtOneFront( ) &&
+ this->GetNumberOfSeeds( ) > 1 &&
+ nColl == 1
+ )
+ {
+ q.clear( );
+ coll = true;
+
+ } // fi
+ }
+ else
+ {
+ // Compute new cost
+ TOutputValue ncost =
+ this->m_VertexFunctor->Evaluate( neigh, node.Vertex );
+ if( this->m_IntensityFunctor.IsNotNull( ) )
+ ncost = this->m_IntensityFunctor->Evaluate( ncost );
+
+ // This algorithm only supports positive values
+ if( ncost >= TOutputValue( 0 ) )
+ {
+ // Insert new node
+ _TNode nn( neigh, node.Vertex, node.FrontId );
+ nn.Cost = node.Cost + ncost;
+ q.push_back( nn );
+ std::push_heap( q.begin( ), q.end( ) );
+
+ } // fi
+
+ } // fi
+ ++neighIt;
+
+ } // elihw
+
+ } // elihw
+ this->_FreeMarks( );
+
+ // Complete data into minimum spanning tree
+ mst->ClearSeeds( );
+ mst->SetCollisions( this->m_Collisions );
+ for( sIt = this->BeginSeeds( ); sIt != this->EndSeeds( ); ++sIt )
+ mst->AddSeed( *sIt );
}
#endif // __fpa__Base__Dijkstra__hxx__
git://git.creatis.insa-lyon.fr / FrontAlgorithms.git / blobdiff