Main Page   Groups   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members   Concepts

itkShapeUniqueLabelMapFilter.h

Go to the documentation of this file.
00001 /*=========================================================================
00002 
00003   Program:   Insight Segmentation & Registration Toolkit
00004   Module:    $RCSfile: itkShapeUniqueLabelMapFilter.h,v $
00005   Language:  C++
00006   Date:      $Date: 2009-08-11 14:24:44 $
00007   Version:   $Revision: 1.6 $
00008 
00009   Copyright (c) Insight Software Consortium. All rights reserved.
00010   See ITKCopyright.txt or http://www.itk.org/HTML/Copyright.htm for details.
00011 
00012      This software is distributed WITHOUT ANY WARRANTY; without even 
00013      the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
00014      PURPOSE.  See the above copyright notices for more information.
00015 
00016 =========================================================================*/
00017 #ifndef __itkShapeUniqueLabelMapFilter_h
00018 #define __itkShapeUniqueLabelMapFilter_h
00019 
00020 #include "itkInPlaceLabelMapFilter.h"
00021 #include "itkShapeLabelObjectAccessors.h"
00022 #include <queue>
00023 
00024 namespace itk {
00036 template<class TImage>
00037 class ITK_EXPORT ShapeUniqueLabelMapFilter : 
00038     public InPlaceLabelMapFilter<TImage>
00039 {
00040 public:
00042   typedef ShapeUniqueLabelMapFilter     Self;
00043   typedef InPlaceLabelMapFilter<TImage> Superclass;
00044   typedef SmartPointer<Self>            Pointer;
00045   typedef SmartPointer<const Self>      ConstPointer;
00046 
00048   typedef TImage                              ImageType;
00049   typedef typename ImageType::Pointer         ImagePointer;
00050   typedef typename ImageType::ConstPointer    ImageConstPointer;
00051   typedef typename ImageType::PixelType       PixelType;
00052   typedef typename ImageType::IndexType       IndexType;
00053   typedef typename ImageType::LabelObjectType LabelObjectType;
00054   typedef typename LabelObjectType::LineType  LineType;
00055 
00056   typedef typename LabelObjectType::AttributeType AttributeType;
00057 
00059   itkStaticConstMacro(ImageDimension, unsigned int,
00060                       TImage::ImageDimension);
00061 
00063   itkNewMacro(Self);
00064 
00066   itkTypeMacro(ShapeUniqueLabelMapFilter, 
00067                InPlaceLabelMapFilter);
00068 
00069 #ifdef ITK_USE_CONCEPT_CHECKING
00070 
00071 /*  itkConceptMacro(InputEqualityComparableCheck,
00072     (Concept::EqualityComparable<InputImagePixelType>));
00073   itkConceptMacro(IntConvertibleToInputCheck,
00074     (Concept::Convertible<int, InputImagePixelType>));
00075   itkConceptMacro(InputOStreamWritableCheck,
00076     (Concept::OStreamWritable<InputImagePixelType>));*/
00077 
00079 #endif
00080 
00087   itkGetConstMacro( ReverseOrdering, bool );
00088   itkSetMacro( ReverseOrdering, bool );
00089   itkBooleanMacro( ReverseOrdering );
00091 
00096   itkGetConstMacro( Attribute, AttributeType );
00097   itkSetMacro( Attribute, AttributeType );
00098   void SetAttribute( const std::string & s )
00099     {
00100     this->SetAttribute( LabelObjectType::GetAttributeFromName( s ) );
00101     }
00103 
00104 
00105 protected:
00106   ShapeUniqueLabelMapFilter();
00107   ~ShapeUniqueLabelMapFilter() {};
00108 
00109   void GenerateData();
00110 
00111   template <class TAttributeAccessor> 
00112   void TemplatedGenerateData( const TAttributeAccessor & accessor )
00113     {
00114     // Allocate the output
00115     this->AllocateOutputs();
00116 
00117     // the priority queue to store all the lines of all the objects sorted
00118     typedef typename std::priority_queue< LineOfLabelObject, std::vector<LineOfLabelObject>, LineOfLabelObjectComparator > PriorityQueueType;
00119     PriorityQueueType pq;
00120 
00121     ProgressReporter progress( this, 0, 1 );
00122     // TODO: really report the progress
00123     
00124     typedef typename ImageType::LabelObjectContainerType LabelObjectsType;
00125 
00126     const LabelObjectsType & labelObjects = this->GetLabelMap()->GetLabelObjectContainer();
00127     for( typename LabelObjectsType::const_iterator it2 = labelObjects.begin();
00128       it2 != labelObjects.end();
00129       it2++ )
00130       {
00131       LabelObjectType * lo = it2->second;
00132       
00133       // may reduce the number of lines to proceed
00134       lo->Optimize();
00135       
00136       typename LabelObjectType::LineContainerType::const_iterator lit;
00137       typename LabelObjectType::LineContainerType & lineContainer = lo->GetLineContainer();
00138     
00139       for( lit = lineContainer.begin(); lit != lineContainer.end(); lit++ )
00140         {
00141         pq.push( LineOfLabelObject( *lit, lo ) );
00142         }
00143       
00144       // clear the lines to readd them later
00145       lineContainer.clear();
00146       
00147       // go to the next label
00148       // progress.CompletedPixel();
00149       }
00150       
00151     if( pq.empty() )
00152       {
00153       // nothing to do
00154       return;
00155       }
00156       
00157     typedef typename std::deque<LineOfLabelObject> LinesType;
00158     LinesType lines;
00159 
00160     lines.push_back( pq.top() );
00161     LineOfLabelObject prev = lines.back();
00162     IndexType prevIdx = prev.line.GetIndex();
00163     pq.pop();
00164     
00165     while( !pq.empty() )
00166       {
00167       LineOfLabelObject l = pq.top();
00168       IndexType idx = l.line.GetIndex();
00169       pq.pop();
00170       
00171       bool newMainLine = false;
00172       // don't check dim 0!
00173       for( int i=1; i<ImageDimension; i++ )
00174         {
00175         if( idx[i] != prevIdx[i] )
00176           {
00177           newMainLine = true;
00178           }
00179         }
00180       
00181       if( newMainLine )
00182         {
00183         // just push the line
00184         lines.push_back( l );
00185         }
00186       else
00187         {
00188         unsigned long prevLength = prev.line.GetLength();
00189         unsigned long length = l.line.GetLength();
00190         
00191         if( prevIdx[0] + (long)prevLength >= idx[0] )
00192           {
00193           // the lines are overlapping. We need to choose which line to keep.
00194           // the label, the only "attribute" to be guarenteed to be unique, is used to choose
00195           // which line to keep. This is necessary to avoid the case where a part of a label is over
00196           // a second label, and below in another part of the image.
00197           bool keepCurrent;
00198           typename TAttributeAccessor::AttributeValueType prevAttr = accessor( prev.labelObject );
00199           typename TAttributeAccessor::AttributeValueType attr = accessor( l.labelObject );
00200           // this may be changed to a single boolean expression, but may become quite difficult to read
00201           if( attr == prevAttr  )
00202             {
00203             if( l.labelObject->GetLabel() > prev.labelObject->GetLabel() )
00204               {
00205               keepCurrent = !m_ReverseOrdering;
00206               }
00207             else
00208               {
00209               keepCurrent = m_ReverseOrdering;
00210               }
00211             }
00212           else
00213             {
00214             if( attr > prevAttr )
00215               {
00216               keepCurrent = !m_ReverseOrdering;
00217               }
00218             else
00219               {
00220               keepCurrent = m_ReverseOrdering;
00221               }
00222             }
00223           
00224           if( keepCurrent )
00225             {
00226             // keep the current one. We must truncate the previous one to remove the
00227             // overlap, and take care of the end of the previous line if it extends
00228             // after the current one.
00229             if( prevIdx[0] + prevLength > idx[0] + length )
00230               {
00231               // the previous line is longer than the current one. Lets take its tail and
00232               // add it to the priority queue
00233               IndexType newIdx = idx;
00234               newIdx[0] = idx[0] + length;
00235               unsigned long newLength = prevIdx[0] + prevLength - newIdx[0];
00236               pq.push( LineOfLabelObject( LineType( newIdx, newLength ), prev.labelObject ) );
00237               }
00238             // truncate the previous line to let some place for the current one
00239             prevLength = idx[0] - prevIdx[0];
00240             if( prevLength != 0 )
00241               {
00242               lines.back().line.SetLength( idx[0] - prevIdx[0] );
00243               }
00244             else
00245               {
00246               // length is 0 - no need to keep that line
00247               lines.pop_back();
00248               }
00249             // and push the current one
00250             lines.push_back( l );
00251             }
00252           else
00253             {
00254             // keep the previous one. If the previous line fully overlap the current one,
00255             // the current one is fully discarded.
00256             if( prevIdx[0] + prevLength > idx[0] + length )
00257               {
00258               // discarding the current line - just do nothing
00259               }
00260             else
00261               {
00262               IndexType newIdx = idx;
00263               newIdx[0] = prevIdx[0] + prevLength;
00264               unsigned long newLength = idx[0] + length - newIdx[0];
00265               l.line.SetIndex( newIdx );
00266               l.line.SetLength( newLength );
00267               lines.push_back( l );
00268               }
00269             
00270             }
00271           }
00272         else
00273           {
00274           // no overlap - things are just fine already
00275           lines.push_back( l );
00276           }
00277         }
00278       
00279       // store the current line as the previous one, and go to the next one.
00280       prev = lines.back();
00281       prevIdx = prev.line.GetIndex();
00282       }
00283     
00284     // put the lines in their object
00285     for( unsigned int i=0; i<lines.size(); i++ )
00286       {
00287       LineOfLabelObject & l = lines[i];
00288       l.labelObject->AddLine( l.line );
00289       }
00290 
00291     // remove objects without lines
00292     typename LabelObjectsType::const_iterator it = labelObjects.begin();
00293     while( it != labelObjects.end() )
00294       {
00295       typename LabelObjectType::LabelType label = it->first;
00296       LabelObjectType * labelObject = it->second;
00297 
00298       if( labelObject->Empty() )
00299         {
00300         // must increment the iterator before removing the object to avoid invalidating the iterator
00301         it++;
00302         this->GetLabelMap()->RemoveLabel( label );
00303         }
00304       else
00305         {
00306         it++;
00307         }
00308 
00309       }
00310     }
00311 
00312   void PrintSelf(std::ostream& os, Indent indent) const;
00313 
00314   AttributeType m_Attribute;
00315 
00316 private:
00317   ShapeUniqueLabelMapFilter(const Self&); //purposely not implemented
00318   void operator=(const Self&); //purposely not implemented
00319 
00320   bool          m_ReverseOrdering;
00321   struct LineOfLabelObject
00322     {
00323     typedef typename LabelObjectType::LineType LineType;
00324     LineOfLabelObject( const LineType _line, LabelObjectType * _lo )
00325       {
00326       this->line = _line;
00327       this->labelObject = _lo;
00328       }
00329     LineType          line;
00330     LabelObjectType * labelObject;
00331     };
00332 
00333   class LineOfLabelObjectComparator
00334     {
00335     public:
00336     bool operator()( const LineOfLabelObject & lla, const LineOfLabelObject & llb )
00337       {
00338       for( int i=ImageDimension-1; i>=0; i-- )
00339         {
00340         if( lla.line.GetIndex()[i] > llb.line.GetIndex()[i] )
00341           {
00342           return true;
00343           }
00344         else if( lla.line.GetIndex()[i] < llb.line.GetIndex()[i] )
00345           {
00346           return false;
00347           }
00348         }
00349       return false;
00350       }
00351     };
00352 
00353 }; // end of class
00354 
00355 } // end namespace itk
00356   
00357 #ifndef ITK_MANUAL_INSTANTIATION
00358 #include "itkShapeUniqueLabelMapFilter.txx"
00359 #endif
00360 
00361 #endif
00362 

Generated at Fri Apr 16 19:40:55 2010 for ITK by doxygen 1.6.1 written by Dimitri van Heesch, © 1997-2000