libs/fpa/Base/Dijkstra.hxx

   1 // =========================================================================
   2 // @author Leonardo Florez Valencia
   3 // @email florez-l@javeriana.edu.co
   4 // =========================================================================
   5
   6 #ifndef __fpa__Base__Dijkstra__hxx__
   7 #define __fpa__Base__Dijkstra__hxx__
   8
   9 // -------------------------------------------------------------------------
  10 template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
  11 typename
  12 fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
  13 TMST* fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
  14 GetMinimumSpanningTree( )
  15 {
  16   return(
  17     dynamic_cast< TMST* >(
  18       this->itk::ProcessObject::GetOutput( this->m_MSTIndex )
  19       )
  20     );
  21 }
  22
  23 // -------------------------------------------------------------------------
  24 template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
  25 const typename
  26 fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
  27 TMST* fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
  28 GetMinimumSpanningTree( ) const
  29 {
  30   return(
  31     dynamic_cast< const TMST* >(
  32       this->itk::ProcessObject::GetOutput( this->m_MSTIndex )
  33       )
  34     );
  35 }
  36
  37 // -------------------------------------------------------------------------
  38 template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
  39 const typename
  40 fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
  41 TIntensityFunctor*
  42 fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
  43 GetIntensityFunctor( ) const
  44 {
  45   return( this->m_IntensityFunctor );
  46 }
  47
  48 // -------------------------------------------------------------------------
  49 template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
  50 const typename
  51 fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
  52 TVertexFunctor*
  53 fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
  54 GetVertexFunctor( ) const
  55 {
  56   return( this->m_VertexFunctor );
  57 }
  58
  59 // -------------------------------------------------------------------------
  60 template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
  61 void fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
  62 SetFunctor( TIntensityFunctor* functor )
  63 {
  64   if( this->m_IntensityFunctor.GetPointer( ) != functor )
  65   {
  66     this->m_IntensityFunctor = functor;
  67     this->Modified( );
  68
  69   } // fi
  70 }
  71
  72 // -------------------------------------------------------------------------
  73 template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
  74 void fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
  75 SetFunctor( TVertexFunctor* functor )
  76 {
  77   if( this->m_VertexFunctor.GetPointer( ) != functor )
  78   {
  79     this->m_VertexFunctor = functor;
  80     this->Modified( );
  81
  82   } // fi
  83 }
  84
  85 // -------------------------------------------------------------------------
  86 template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
  87 fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
  88 Dijkstra( )
  89   : Superclass( ),
  90     _TMarksInterface( this ),
  91     _TSeedsInterface( this )
  92 {
  93   this->m_MSTIndex = this->GetNumberOfRequiredOutputs( );
  94   this->SetNumberOfRequiredOutputs( this->m_MSTIndex + 1 );
  95   this->itk::ProcessObject::SetNthOutput( this->m_MSTIndex, TMST::New( ) );
  96 }
  97
  98 // -------------------------------------------------------------------------
  99 template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
 100 fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
 101 ~Dijkstra( )
 102 {
 103 }
 104
 105 // -------------------------------------------------------------------------
 106 template< class _TFilter, class _TMarksInterface, class _TSeedsInterface, class _TMST >
 107 void fpa::Base::Dijkstra< _TFilter, _TMarksInterface, _TSeedsInterface, _TMST >::
 108 GenerateData( )
 109 {
 110   // Init objects
 111   this->_ConfigureOutputs( TOutputValue( 0 ) );
 112   this->_InitMarks( this->GetNumberOfSeeds( ) );
 113   TMST* mst = this->GetMinimumSpanningTree( );
 114
 115   // Init queue
 116   std::vector< _TNode > q;
 117   unsigned long frontId = 1;
 118   for( TVertex seed: this->GetSeeds( ) )
 119     q.push_back( _TNode( seed, seed, frontId++ ) );
 120
 121   // Main loop
 122   while( q.size( ) > 0 )
 123   {
 124     // Get next candidate
 125     std::pop_heap( q.begin( ), q.end( ) );
 126     _TNode node = q.back( );
 127     q.pop_back( );
 128     if( this->_IsMarked( node.Vertex ) )
 129       continue;
 130     this->_Mark( node.Vertex, node.FrontId );
 131
 132     // Ok, pixel lays inside region
 133     this->_SetOutputValue( node.Vertex, node.Cost );
 134     mst->SetParent( node.Vertex, node.Parent );
 135
 136     // Add neighborhood
 137     TVertices neighbors = this->_GetNeighbors( node.Vertex );
 138     for( TVertex neigh: neighbors )
 139     {
 140       if( this->_IsMarked( neigh ) )
 141       {
 142         // Invoke stop at collisions
 143         unsigned long nColl = this->_Collisions( node.Vertex, neigh );
 144         if(
 145           this->StopAtOneFront( ) &&
 146           this->GetNumberOfSeeds( ) > 1 &&
 147           nColl == 1
 148           )
 149           q.clear( );
 150       }
 151       else
 152       {
 153         // Compute new cost
 154         TOutputValue ncost =
 155           this->m_VertexFunctor->Evaluate( neigh, node.Vertex );
 156         if( this->m_IntensityFunctor.IsNotNull( ) )
 157           ncost = this->m_IntensityFunctor->Evaluate( ncost );
 158
 159         // This algorithm only supports positive values
 160         if( ncost >= TOutputValue( 0 ) )
 161         {
 162           // Insert new node
 163           _TNode nn( neigh, node.Vertex, node.FrontId );
 164           nn.Cost = node.Cost + ncost;
 165           q.push_back( nn );
 166           std::push_heap( q.begin( ), q.end( ) );
 167
 168         } // fi
 169
 170       } // fi
 171
 172     } // rof
 173
 174   } // elihw
 175   this->_FreeMarks( );
 176
 177   // Complete data into minimum spanning tree
 178   mst->ClearSeeds( );
 179   mst->SetCollisions( this->m_Collisions );
 180   for( TVertex seed: this->GetSeeds( ) )
 181     mst->AddSeed( seed );
 182 }
 183
 184 #endif // __fpa__Base__Dijkstra__hxx__
 185
 186 // eof - $RCSfile$