ITK  4.1.0
Insight Segmentation and Registration Toolkit
itkShapeUniqueLabelMapFilter.h
Go to the documentation of this file.
00001 /*=========================================================================
00002  *
00003  *  Copyright Insight Software Consortium
00004  *
00005  *  Licensed under the Apache License, Version 2.0 (the "License");
00006  *  you may not use this file except in compliance with the License.
00007  *  You may obtain a copy of the License at
00008  *
00009  *         http://www.apache.org/licenses/LICENSE-2.0.txt
00010  *
00011  *  Unless required by applicable law or agreed to in writing, software
00012  *  distributed under the License is distributed on an "AS IS" BASIS,
00013  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00014  *  See the License for the specific language governing permissions and
00015  *  limitations under the License.
00016  *
00017  *=========================================================================*/
00018 #ifndef __itkShapeUniqueLabelMapFilter_h
00019 #define __itkShapeUniqueLabelMapFilter_h
00020 
00021 #include "itkInPlaceLabelMapFilter.h"
00022 #include "itkShapeLabelObjectAccessors.h"
00023 #include <queue>
00024 
00025 namespace itk
00026 {
00040 template< class TImage >
00041 class ITK_EXPORT ShapeUniqueLabelMapFilter:
00042   public InPlaceLabelMapFilter< TImage >
00043 {
00044 public:
00046   typedef ShapeUniqueLabelMapFilter       Self;
00047   typedef InPlaceLabelMapFilter< TImage > Superclass;
00048   typedef SmartPointer< Self >            Pointer;
00049   typedef SmartPointer< const Self >      ConstPointer;
00050 
00052   typedef TImage                              ImageType;
00053   typedef typename ImageType::Pointer         ImagePointer;
00054   typedef typename ImageType::ConstPointer    ImageConstPointer;
00055   typedef typename ImageType::PixelType       PixelType;
00056   typedef typename ImageType::IndexType       IndexType;
00057   typedef typename ImageType::LabelObjectType LabelObjectType;
00058   typedef typename LabelObjectType::LineType  LineType;
00059 
00060   typedef typename LabelObjectType::AttributeType AttributeType;
00061 
00063   itkStaticConstMacro(ImageDimension, unsigned int,
00064                       TImage::ImageDimension);
00065 
00067   itkNewMacro(Self);
00068 
00070   itkTypeMacro(ShapeUniqueLabelMapFilter,
00071                InPlaceLabelMapFilter);
00072 
00073 #ifdef ITK_USE_CONCEPT_CHECKING
00074 
00075 /*  itkConceptMacro(InputEqualityComparableCheck,
00076     (Concept::EqualityComparable<InputImagePixelType>));
00077   itkConceptMacro(IntConvertibleToInputCheck,
00078     (Concept::Convertible<int, InputImagePixelType>));
00079   itkConceptMacro(InputOStreamWritableCheck,
00080     (Concept::OStreamWritable<InputImagePixelType>));*/
00081 
00083 #endif
00084 
00091   itkGetConstMacro(ReverseOrdering, bool);
00092   itkSetMacro(ReverseOrdering, bool);
00093   itkBooleanMacro(ReverseOrdering);
00095 
00100   itkGetConstMacro(Attribute, AttributeType);
00101   itkSetMacro(Attribute, AttributeType);
00102   void SetAttribute(const std::string & s)
00103   {
00104     this->SetAttribute( LabelObjectType::GetAttributeFromName(s) );
00105   }
00107 
00108 protected:
00109   ShapeUniqueLabelMapFilter();
00110   ~ShapeUniqueLabelMapFilter() {}
00111 
00112   void GenerateData();
00113 
00114   template< class TAttributeAccessor >
00115   void TemplatedGenerateData(const TAttributeAccessor & accessor)
00116   {
00117     // Allocate the output
00118     this->AllocateOutputs();
00119 
00120     // the priority queue to store all the lines of all the objects sorted
00121     typedef typename std::priority_queue< LineOfLabelObject, std::vector< LineOfLabelObject >,
00122                                           LineOfLabelObjectComparator > PriorityQueueType;
00123     PriorityQueueType pq;
00124 
00125     ProgressReporter progress(this, 0, 1);
00126     // TODO: really report the progress
00127 
00128     for ( typename ImageType::Iterator it2( this->GetLabelMap() );
00129           ! it2.IsAtEnd();
00130           ++it2 )
00131       {
00132       LabelObjectType *lo = it2.GetLabelObject();
00133 
00134       // may reduce the number of lines to proceed
00135       lo->Optimize();
00136 
00137       typename LabelObjectType::ConstLineIterator lit( lo );
00138       while( ! lit.IsAtEnd() )
00139         {
00140         pq.push( LineOfLabelObject(lit.GetLine(), lo) );
00141         ++lit;
00142         }
00143 
00144       // clear the lines to readd them later
00145       lo->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 ( unsigned 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         OffsetValueType prevLength = prev.line.GetLength();
00189         OffsetValueType length = l.line.GetLength();
00190 
00191         if ( prevIdx[0] + 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
00195           // used to choose
00196           // which line to keep. This is necessary to avoid the case where a
00197           // part of a label is over
00198           // a second label, and below in another part of the image.
00199           bool keepCurrent;
00200           typename TAttributeAccessor::AttributeValueType prevAttr = accessor(prev.labelObject);
00201           typename TAttributeAccessor::AttributeValueType attr = accessor(l.labelObject);
00202           // this may be changed to a single boolean expression, but may become
00203           // quite difficult to read
00204           if ( attr == prevAttr  )
00205             {
00206             if ( l.labelObject->GetLabel() > prev.labelObject->GetLabel() )
00207               {
00208               keepCurrent = !m_ReverseOrdering;
00209               }
00210             else
00211               {
00212               keepCurrent = m_ReverseOrdering;
00213               }
00214             }
00215           else
00216             {
00217             if ( attr > prevAttr )
00218               {
00219               keepCurrent = !m_ReverseOrdering;
00220               }
00221             else
00222               {
00223               keepCurrent = m_ReverseOrdering;
00224               }
00225             }
00226 
00227           if ( keepCurrent )
00228             {
00229             // keep the current one. We must truncate the previous one to remove
00230             // the
00231             // overlap, and take care of the end of the previous line if it
00232             // extends
00233             // after the current one.
00234             if ( prevIdx[0] + prevLength > idx[0] + length )
00235               {
00236               // the previous line is longer than the current one. Lets take its
00237               // tail and
00238               // add it to the priority queue
00239               IndexType newIdx = idx;
00240               newIdx[0] = idx[0] + length;
00241               OffsetValueType newLength = prevIdx[0] + prevLength - newIdx[0];
00242               pq.push( LineOfLabelObject(LineType(newIdx, newLength), prev.labelObject) );
00243               }
00244             // truncate the previous line to let some place for the current one
00245             prevLength = idx[0] - prevIdx[0];
00246             if ( prevLength != 0 )
00247               {
00248               lines.back(). line.SetLength(idx[0] - prevIdx[0]);
00249               }
00250             else
00251               {
00252               // length is 0 - no need to keep that line
00253               lines.pop_back();
00254               }
00255             // and push the current one
00256             lines.push_back(l);
00257             }
00258           else
00259             {
00260             // keep the previous one. If the previous line fully overlap the
00261             // current one,
00262             // the current one is fully discarded.
00263             if ( prevIdx[0] + prevLength > idx[0] + length )
00264               {
00265               // discarding the current line - just do nothing
00266               }
00267             else
00268               {
00269               IndexType newIdx = idx;
00270               newIdx[0] = prevIdx[0] + prevLength;
00271               OffsetValueType newLength = idx[0] + length - newIdx[0];
00272               l.line.SetIndex(newIdx);
00273               l.line.SetLength(newLength);
00274               lines.push_back(l);
00275               }
00276             }
00277           }
00278         else
00279           {
00280           // no overlap - things are just fine already
00281           lines.push_back(l);
00282           }
00283         }
00284 
00285       // store the current line as the previous one, and go to the next one.
00286       prev = lines.back();
00287       prevIdx = prev.line.GetIndex();
00288       }
00289 
00290     // put the lines in their object
00291     for ( unsigned int i = 0; i < lines.size(); i++ )
00292       {
00293       LineOfLabelObject & l = lines[i];
00294       l.labelObject->AddLine(l.line);
00295       }
00296 
00297     // remove objects without lines
00298     typename ImageType::Iterator it( this->GetLabelMap() );
00299     while ( ! it.IsAtEnd() )
00300       {
00301       typename LabelObjectType::LabelType label = it.GetLabel();
00302       LabelObjectType *labelObject = it.GetLabelObject();
00303 
00304       if ( labelObject->Empty() )
00305         {
00306         // must increment the iterator before removing the object to avoid
00307         // invalidating the iterator
00308         ++it;
00309         this->GetLabelMap()->RemoveLabel(label);
00310         }
00311       else
00312         {
00313         ++it;
00314         }
00315       }
00316   }
00317 
00318   void PrintSelf(std::ostream & os, Indent indent) const;
00319 
00320   AttributeType m_Attribute;
00321 private:
00322   ShapeUniqueLabelMapFilter(const Self &); //purposely not implemented
00323   void operator=(const Self &);            //purposely not implemented
00324 
00325   bool m_ReverseOrdering;
00326   struct LineOfLabelObject {
00327     typedef typename LabelObjectType::LineType LineType;
00328     LineOfLabelObject(const LineType _line, LabelObjectType *_lo)
00329     {
00330       this->line = _line;
00331       this->labelObject = _lo;
00332     }
00333 
00334     LineType line;
00335     LabelObjectType *labelObject;
00336   };
00337 
00338   class LineOfLabelObjectComparator
00339   {
00340 public:
00341     bool operator()(const LineOfLabelObject & lla, const LineOfLabelObject & llb)
00342     {
00343       for ( int i = ImageDimension - 1; i >= 0; i-- )
00344         {
00345         if ( lla.line.GetIndex()[i] > llb.line.GetIndex()[i] )
00346           {
00347           return true;
00348           }
00349         else if ( lla.line.GetIndex()[i] < llb.line.GetIndex()[i] )
00350           {
00351           return false;
00352           }
00353         }
00354       return false;
00355     }
00356   };
00357 }; // end of class
00358 } // end namespace itk
00359 
00360 #ifndef ITK_MANUAL_INSTANTIATION
00361 #include "itkShapeUniqueLabelMapFilter.hxx"
00362 #endif
00363 
00364 #endif
00365