lib/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   typename TSeedsInterface::TSeeds::const_iterator sIt = this->BeginSeeds( );
 119   for( ; sIt != this->EndSeeds( ); ++sIt )
 120     q.push_back( _TNode( *sIt, *sIt, frontId++ ) );
 121
 122   // Main loop
 123   while( q.size( ) > 0 )
 124   {
 125     // Get next candidate
 126     std::pop_heap( q.begin( ), q.end( ) );
 127     _TNode node = q.back( );
 128     q.pop_back( );
 129     if( this->_IsMarked( node.Vertex ) )
 130       continue;
 131     this->_Mark( node.Vertex, node.FrontId );
 132
 133     // Ok, pixel lays inside region
 134     this->_SetOutputValue( node.Vertex, node.Cost );
 135     mst->SetParent( node.Vertex, node.Parent );
 136
 137     // Add neighborhood
 138     TVertices neighbors = this->_GetNeighbors( node.Vertex );
 139     for( TVertex neigh: neighbors )
 140     {
 141       if( this->_IsMarked( neigh ) )
 142       {
 143         // Invoke stop at collisions
 144         unsigned long nColl = this->_Collisions( node.Vertex, neigh );
 145         if(
 146           this->StopAtOneFront( ) &&
 147           this->GetNumberOfSeeds( ) > 1 &&
 148           nColl == 1
 149           )
 150           q.clear( );
 151       }
 152       else
 153       {
 154         // Compute new cost
 155         TOutputValue ncost =
 156           this->m_VertexFunctor->Evaluate( neigh, node.Vertex );
 157         if( this->m_IntensityFunctor.IsNotNull( ) )
 158           ncost = this->m_IntensityFunctor->Evaluate( ncost );
 159
 160         // This algorithm only supports positive values
 161         if( ncost >= TOutputValue( 0 ) )
 162         {
 163           // Insert new node
 164           _TNode nn( neigh, node.Vertex, node.FrontId );
 165           nn.Cost = node.Cost + ncost;
 166           q.push_back( nn );
 167           std::push_heap( q.begin( ), q.end( ) );
 168
 169         } // fi
 170
 171       } // fi
 172
 173     } // rof
 174
 175   } // elihw
 176   this->_FreeMarks( );
 177
 178   // Complete data into minimum spanning tree
 179   mst->ClearSeeds( );
 180   mst->SetCollisions( this->m_Collisions );
 181   for( TVertex seed: this->GetSeeds( ) )
 182     mst->AddSeed( seed );
 183 }
 184
 185 #endif // __fpa__Base__Dijkstra__hxx__
 186
 187 // eof - $RCSfile$