1 #ifndef __FPA__BASE__EXTRACTENDPOINTSANDBIFURCATIONSFROMMINIMUMSPANNINGTREE__HXX__
2 #define __FPA__BASE__EXTRACTENDPOINTSANDBIFURCATIONSFROMMINIMUMSPANNINGTREE__HXX__
8 // -------------------------------------------------------------------------
9 template< class _TMST >
11 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
13 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
14 GetMinimumSpanningTree( )
17 dynamic_cast< const _TMST* >( this->itk::ProcessObject::GetInput( 0 ) )
21 // -------------------------------------------------------------------------
22 template< class _TMST >
24 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
25 SetMinimumSpanningTree( TMinimumSpanningTree* mst )
27 this->itk::ProcessObject::SetNthInput( 0, const_cast< _TMST* >( mst ) );
30 // -------------------------------------------------------------------------
31 template< class _TMST >
33 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
35 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
39 dynamic_cast< TVertices* >( this->itk::ProcessObject::GetOutput( 0 ) )
43 // -------------------------------------------------------------------------
44 template< class _TMST >
46 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
48 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
52 dynamic_cast< TVertices* >( this->itk::ProcessObject::GetOutput( 1 ) )
56 // -------------------------------------------------------------------------
57 template< class _TMST >
59 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
61 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
65 dynamic_cast< TVertices* >( this->itk::ProcessObject::GetOutput( 2 ) )
69 // -------------------------------------------------------------------------
70 template< class _TMST >
71 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
72 ExtractEndPointsAndBifurcationsFromMinimumSpanningTree( )
75 this->SetNumberOfRequiredInputs( 1 );
76 this->SetNumberOfRequiredOutputs( 3 );
77 typename TVertices::Pointer ep = TVertices::New( );
78 typename TVertices::Pointer bf = TVertices::New( );
79 typename TVertices::Pointer co = TVertices::New( );
80 this->itk::ProcessObject::SetNthOutput( 0, ep.GetPointer( ) );
81 this->itk::ProcessObject::SetNthOutput( 1, bf.GetPointer( ) );
82 this->itk::ProcessObject::SetNthOutput( 2, co.GetPointer( ) );
85 // -------------------------------------------------------------------------
86 template< class _TMST >
87 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
88 ~ExtractEndPointsAndBifurcationsFromMinimumSpanningTree( )
92 // -------------------------------------------------------------------------
93 template< class _TMST >
95 fpa::Base::ExtractEndPointsAndBifurcationsFromMinimumSpanningTree< _TMST >::
98 typedef std::multimap< double, TVertex > _TQueue;
99 typedef std::pair< TVertex, TVertex > _TBranch;
100 typedef std::vector< _TBranch > _TBranches;
101 typedef typename _TQueue::value_type _TQueueValue;
103 // 0. Useful objects and values
104 auto mst = this->GetMinimumSpanningTree( );
105 auto endpoints = this->GetEndPoints( );
106 auto bifurcations = this->GetBifurcations( );
107 auto collisions = this->GetCollisions( );
109 endpoints->Get( ).clear( );
110 bifurcations->Get( ).clear( );
111 collisions->Get( ).clear( );
113 // 1. Get priority queue
114 auto& q = mst->GetNodeQueue( );
116 // 2. Main loop: iterate in inverse order (max-priority)
117 unsigned long label = 0;
118 for( auto qIt = q.rbegin( ); qIt != q.rend( ); ++qIt )
120 auto gCost = qIt->first;
121 auto vertex = qIt->second;
123 // 2.1. Check if the vertex has already been visited
124 if( this->_Mark( vertex ) > 0 )
127 // 2.2. Get path from front seed
128 auto path = mst->GetPath( vertex );
130 // 2.3. Prepare new branch data and prepare new end-point
132 branches.push_back( _TBranch( vertex, vertex ) );
133 endpoints->Get( ).push_back( vertex );
136 auto pIt = path.begin( );
137 TVertex last_collision;
138 bool inCollision = false;
139 while( pIt != path.end( ) )
141 auto mark = this->_SkeletonMark( *pIt );
142 if( mark > 0 && mark != label )
144 // 2.4.1. A bifurcation has been reached
145 bifurcations->Get( ).push_back( *pIt );
148 auto coll_branch = branches[ mark ];
149 branches[ mark ] = _TBranch( coll_branch.first, *pIt );
150 branches[ label - 1 ] = _TBranch( qIt->second, *pIt );
151 branches.push_back( _TBranch( *pIt, coll_branch.second ) );
153 // Mark skeleton (b,coll_branch_second) with the new label
155 while( *pIt != coll_branch.second && pIt != path.end( ) )
157 this->_MarkSkeleton( *pIt, label );
162 // Force inner loop termination
169 mark = this->_Mark( *pIt );
170 if( mark > 0 && mark != label )
172 // 2.4.2. A collision has been reached
173 last_collision = *pIt;
174 collisions->Get( ).push_back( *pIt );
179 // 2.4.3. Just mark sphere and skeleton
180 double r = this->_Radius( *pIt );
181 this->_MarkSkeleton( *pIt, label );
182 this->_MarkSphere( *pIt, r, label );
183 branches[ label - 1 ].second = *pIt;
185 // 2.4.4. Is this a seed? -> add it to endpoints
188 if( sIt == path.end( ) )
189 endpoints->Get( ).push_back( *pIt );
202 endpoints->SetReferenceImage( mst );
203 bifurcations->SetReferenceImage( mst );
204 collisions->SetReferenceImage( mst );
207 #endif // __FPA__BASE__EXTRACTENDPOINTSANDBIFURCATIONSFROMMINIMUMSPANNINGTREE__HXX__