1 #ifndef __FPA__BASE__EXTRACTENDPOINTSANDBIFURCATIONSFROMMINIMUMSPANNINGTREE__HXX__
2 #define __FPA__BASE__EXTRACTENDPOINTSANDBIFURCATIONSFROMMINIMUMSPANNINGTREE__HXX__
7 // -------------------------------------------------------------------------
8 template< class _TMST >
10 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
12 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
13 GetMinimumSpanningTree( )
16 dynamic_cast< const _TMST* >( this->itk::ProcessObject::GetInput( 0 ) )
20 // -------------------------------------------------------------------------
21 template< class _TMST >
23 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
24 SetMinimumSpanningTree( TMinimumSpanningTree* mst )
26 this->itk::ProcessObject::SetNthInput( 0, const_cast< _TMST* >( mst ) );
29 // -------------------------------------------------------------------------
30 template< class _TMST >
32 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
34 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
38 dynamic_cast< TVertices* >( this->itk::ProcessObject::GetOutput( 0 ) )
42 // -------------------------------------------------------------------------
43 template< class _TMST >
45 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
47 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
51 dynamic_cast< TVertices* >( this->itk::ProcessObject::GetOutput( 1 ) )
55 // -------------------------------------------------------------------------
56 template< class _TMST >
58 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
60 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
64 dynamic_cast< TVertices* >( this->itk::ProcessObject::GetOutput( 2 ) )
68 // -------------------------------------------------------------------------
69 template< class _TMST >
71 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
73 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
77 dynamic_cast< TBranches* >( this->itk::ProcessObject::GetOutput( 3 ) )
81 // -------------------------------------------------------------------------
82 template< class _TMST >
83 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
84 ExtractEndPointsAndBifurcationsFromMinimumSpanningTree( )
87 this->SetNumberOfRequiredInputs( 1 );
88 this->SetNumberOfRequiredOutputs( 4 );
89 typename TVertices::Pointer ep = TVertices::New( );
90 typename TVertices::Pointer bf = TVertices::New( );
91 typename TVertices::Pointer co = TVertices::New( );
92 typename TBranches::Pointer br = TBranches::New( );
93 this->itk::ProcessObject::SetNthOutput( 0, ep.GetPointer( ) );
94 this->itk::ProcessObject::SetNthOutput( 1, bf.GetPointer( ) );
95 this->itk::ProcessObject::SetNthOutput( 2, co.GetPointer( ) );
96 this->itk::ProcessObject::SetNthOutput( 3, br.GetPointer( ) );
99 // -------------------------------------------------------------------------
100 template< class _TMST >
101 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
102 ~ExtractEndPointsAndBifurcationsFromMinimumSpanningTree( )
106 // -------------------------------------------------------------------------
107 template< class _TMST >
109 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
112 typedef std::multimap< double, TVertex > _TQueue;
113 typedef std::pair< TVertex, TVertex > _TBranch;
114 typedef std::vector< _TBranch > _TBranches;
115 typedef typename _TQueue::value_type _TQueueValue;
117 // 0. Useful objects and values
118 auto mst = this->GetMinimumSpanningTree( );
119 auto endpoints = this->GetEndPoints( );
120 auto bifurcations = this->GetBifurcations( );
121 auto collisions = this->GetCollisions( );
122 auto branches = this->GetBranches( );
123 endpoints->Get( ).clear( );
124 bifurcations->Get( ).clear( );
125 collisions->Get( ).clear( );
126 branches->Get( ).clear( );
128 // 1. Get priority queue
129 auto& q = mst->GetNodeQueue( );
131 // 2. Main loop: iterate in inverse order (max-priority)
132 unsigned long label = 0;
133 for( auto qIt = q.rbegin( ); qIt != q.rend( ); ++qIt )
135 auto gCost = qIt->first;
136 auto vertex = qIt->second;
138 // 2.1. Check if the vertex has already been visited
139 if( this->_Mark( vertex ) > 0 )
142 // 2.2. Get path from front seed
143 auto path = mst->GetPath( vertex );
145 // 2.3. Prepare new branch data and prepare new end-point
147 branches->Get( ).push_back( _TBranch( vertex, vertex ) );
148 endpoints->Get( ).push_back( vertex );
151 auto pIt = path.begin( );
152 TVertex last_collision;
153 bool inCollision = false;
154 while( pIt != path.end( ) )
156 auto mark = this->_SkeletonMark( *pIt );
157 if( mark > 0 && mark != label )
159 // 2.4.1. A bifurcation has been reached
160 bifurcations->Get( ).push_back( *pIt );
163 auto coll_branch = branches->Get( )[ mark ];
164 branches->Get( )[ mark ] = _TBranch( coll_branch.first, *pIt );
165 branches->Get( )[ label - 1 ] = _TBranch( qIt->second, *pIt );
166 branches->Get( ).push_back( _TBranch( *pIt, coll_branch.second ) );
168 // Mark skeleton (b,coll_branch_second) with the new label
170 while( *pIt != coll_branch.second && pIt != path.end( ) )
172 this->_MarkSkeleton( *pIt, label );
177 // Force inner loop termination
184 mark = this->_Mark( *pIt );
185 if( mark > 0 && mark != label )
187 // 2.4.2. A collision has been reached
188 last_collision = *pIt;
189 collisions->Get( ).push_back( *pIt );
194 // 2.4.3. Just mark sphere and skeleton
195 double r = this->_Radius( *pIt );
196 this->_MarkSkeleton( *pIt, label );
197 this->_MarkSphere( *pIt, r, label );
198 branches->Get( )[ label - 1 ].second = *pIt;
200 // 2.4.4. Is this a seed? -> add it to endpoints
203 if( sIt == path.end( ) )
204 endpoints->Get( ).push_back( *pIt );
217 endpoints->SetReferenceImage( mst );
218 bifurcations->SetReferenceImage( mst );
219 collisions->SetReferenceImage( mst );
222 #endif // __FPA__BASE__EXTRACTENDPOINTSANDBIFURCATIONSFROMMINIMUMSPANNINGTREE__HXX__