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( std::numeric_limits< TOutputValue >::max( ) );
 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     typename TVertices::const_iterator neighIt = neighbors.begin( );
 140     bool coll = false;
 141     while( neighIt != neighbors.end( ) && !coll )
 142     {
 143       TVertex neigh = *neighIt;
 144       if( this->_IsMarked( neigh ) )
 145       {
 146         // Invoke stop at collisions
 147         unsigned long nColl = this->_Collisions( node.Vertex, neigh );
 148         if(
 149           this->StopAtOneFront( ) &&
 150           this->GetNumberOfSeeds( ) > 1 &&
 151           nColl == 1
 152           )
 153         {
 154           q.clear( );
 155           coll = true;
 156
 157         } // fi
 158       }
 159       else
 160       {
 161         // Compute new cost
 162         TOutputValue ncost =
 163           this->m_VertexFunctor->Evaluate( neigh, node.Vertex );
 164         if( this->m_IntensityFunctor.IsNotNull( ) )
 165           ncost = this->m_IntensityFunctor->Evaluate( ncost );
 166
 167         // This algorithm only supports positive values
 168         if( ncost >= TOutputValue( 0 ) )
 169         {
 170           // Insert new node
 171           _TNode nn( neigh, node.Vertex, node.FrontId );
 172           nn.Cost = node.Cost + ncost;
 173           q.push_back( nn );
 174           std::push_heap( q.begin( ), q.end( ) );
 175
 176         } // fi
 177
 178       } // fi
 179       ++neighIt;
 180
 181     } // elihw
 182
 183   } // elihw
 184   this->_FreeMarks( );
 185
 186   // Complete data into minimum spanning tree
 187   mst->ClearSeeds( );
 188   mst->SetCollisions( this->m_Collisions );
 189   for( sIt = this->BeginSeeds( ); sIt != this->EndSeeds( ); ++sIt )
 190     mst->AddSeed( *sIt );
 191 }
 192
 193 #endif // __fpa__Base__Dijkstra__hxx__
 194
 195 // eof - $RCSfile$