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

itkContourExtractor2DImageFilter.h

Go to the documentation of this file.
00001 /*=========================================================================
00002 
00003   Program:   Insight Segmentation & Registration Toolkit
00004   Module:    $RCSfile: itkContourExtractor2DImageFilter.h,v $
00005   Language:  C++
00006   Date:      $Date: 2008-12-06 13:28:10 $
00007   Version:   $Revision: 1.10 $
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 
00018 #ifndef __itkContourExtractor2DImageFilter_h
00019 #define __itkContourExtractor2DImageFilter_h
00020 
00021 #include "itkImageToPathFilter.h"
00022 #include "itkNumericTraits.h"
00023 #include "itkPolyLineParametricPath.h"
00024 #include "itkConceptChecking.h"
00025 #include "itk_hash_map.h"
00026 #include "vcl_deque.h"
00027 #include "vcl_list.h"
00028 
00029 namespace itk
00030 {
00091 template <class TInputImage>
00092 class ITK_EXPORT ContourExtractor2DImageFilter :
00093     public ImageToPathFilter< TInputImage, PolyLineParametricPath<2> >
00094 {
00095 public:
00097   itkStaticConstMacro(InputImageDimension, unsigned int,
00098     TInputImage::ImageDimension);
00099 
00101   typedef TInputImage                               InputImageType;
00102   typedef PolyLineParametricPath<2>                 OutputPathType;
00103 
00105   typedef ContourExtractor2DImageFilter                     Self;
00106   typedef ImageToPathFilter<InputImageType, OutputPathType> Superclass;
00107   typedef SmartPointer<Self>                                Pointer;
00108   typedef SmartPointer<const Self>                          ConstPointer;
00109 
00111   itkNewMacro(Self);
00112 
00114   itkTypeMacro(ContourExtractor2DImageFilter, ImageToPathFilter);
00115 
00117   typedef typename InputImageType::Pointer                  InputImagePointer;
00118   typedef typename InputImageType::PixelType                InputPixelType;
00119   typedef typename InputImageType::IndexType                InputIndexType;
00120   typedef typename InputImageType::OffsetType               InputOffsetType;
00121   typedef typename InputImageType::RegionType               InputRegionType;  
00122   typedef typename OutputPathType::Pointer                  OutputPathPointer;
00123   typedef typename OutputPathType::VertexType               VertexType;
00124   typedef typename OutputPathType::VertexListType           VertexListType;
00125 
00127   typedef typename NumericTraits<InputPixelType>::RealType  InputRealType;
00128 
00129   typedef typename VertexListType::ConstPointer 
00130                                                        VertexListConstPointer;
00133   itkSetMacro(ReverseContourOrientation, bool);
00134   itkGetConstReferenceMacro(ReverseContourOrientation, bool);
00135   itkBooleanMacro(ReverseContourOrientation);
00137 
00141   itkSetMacro(VertexConnectHighPixels, bool);
00142   itkGetConstReferenceMacro(VertexConnectHighPixels, bool);
00143   itkBooleanMacro(VertexConnectHighPixels);
00145 
00148   void SetRequestedRegion(const InputRegionType region);
00149   itkGetConstReferenceMacro(RequestedRegion, InputRegionType);
00150   void ClearRequestedRegion();
00152 
00155   itkSetMacro(ContourValue,InputRealType);
00156   itkGetConstReferenceMacro(ContourValue, InputRealType);
00158 
00159 
00160 #ifdef ITK_USE_CONCEPT_CHECKING
00161 
00162   itkConceptMacro(DimensionShouldBe2,
00163     (Concept::SameDimension<itkGetStaticConstMacro(InputImageDimension),2>));
00164   itkConceptMacro(InputPixelTypeComparable,
00165     (Concept::Comparable<InputPixelType>));
00166   itkConceptMacro(InputHasPixelTraitsCheck,
00167     (Concept::HasPixelTraits<InputPixelType>));
00168   itkConceptMacro(InputHasNumericTraitsCheck,
00169     (Concept::HasNumericTraits<InputPixelType>));
00170 
00172 #endif
00173 
00174 protected:
00175 
00176   ContourExtractor2DImageFilter(); 
00177   virtual ~ContourExtractor2DImageFilter();
00178   void PrintSelf(std::ostream& os, Indent indent) const;
00179   
00180   void GenerateData();
00181   
00185   virtual void GenerateInputRequestedRegion() 
00186             throw(InvalidRequestedRegionError);  
00187 
00188 private:
00189   VertexType InterpolateContourPosition(InputPixelType fromValue, 
00190                                         InputPixelType toValue,
00191                                         InputIndexType fromIndex,
00192                                         InputOffsetType toOffset);
00193   void AddSegment(const VertexType from, const VertexType to);
00194   void FillOutputs();
00195   ContourExtractor2DImageFilter(const Self&); //purposely not implemented
00196   void operator=(const Self&); //purposely not implemented
00197   
00198   InputRealType                                   m_ContourValue;
00199   bool                                            m_ReverseContourOrientation;
00200   bool                                            m_VertexConnectHighPixels;
00201   bool                                            m_UseCustomRegion;
00202   InputRegionType                                 m_RequestedRegion;
00203   unsigned int                                    m_NumberOfContoursCreated;
00204   
00205   // Represent each contour as deque of vertices to facilitate addition of
00206   // nodes at beginning or end. At the end of the processing, we will copy 
00207   // the contour into a PolyLineParametricPath.
00208   // We subclass the deque to store an additional bit of information: an 
00209   // identification number for each growing contour. We use this number so
00210   // that when it becomes necessary to merge two growing contours, we can 
00211   // merge the newer one into the older one. This helps because then we can
00212   // guarantee that the output contour list is ordered from left to right,
00213   // top to bottom (in terms of the first pixel of the contour encountered
00214   // by the marching squares). Currently we make no guarantees that this 
00215   // pixel is the first pixel in the contour list, just that the contours 
00216   // are so ordered in the output. Ensuring this latter condition (first 
00217   // pixel traversed = first pixel in contour) would be possible by either 
00218   // changing the merging rules, which would make the contouring operation 
00219   //slower, or by storing additional data as to which pixel was first.
00220   class ContourType : public vcl_deque<VertexType>
00221     {
00222     public:
00223       unsigned int m_ContourNumber;
00224     };
00225   
00226   // Store all the growing contours in a list. We may need to delete contours
00227   // from anywhere in the sequence (when we merge them together), so we need to
00228   // use a list instead of a vector or similar.
00229   typedef vcl_list<ContourType>                         ContourContainer;
00230   typedef typename ContourContainer::iterator           ContourRef;
00231   
00232   // declare the hash function we are using for the hash_map.
00233   struct VertexHash
00234     {
00235     typedef typename VertexType::CoordRepType CoordinateType;
00236     inline size_t operator()(const VertexType& k) const 
00237       {
00238       // Xor the hashes of the vertices together, after multiplying the 
00239       // first by some number, so that identical (x,y) vertex indices 
00240       // don't all hash to the same bucket. This is a decent if not 
00241       // optimal hash. 
00242       const size_t hashVertex1 = this->float_hash(k[0] * 0xbeef);
00243       const size_t hashVertex2 = this->float_hash(k[1]);
00244       const size_t hashValue = hashVertex1 ^ hashVertex2;
00245       return hashValue;
00246       }
00247       
00248     // Define hash function for floats. Based on method from
00249     // http://www.brpreiss.com/books/opus4/html/page217.html
00250     inline size_t float_hash(const CoordinateType &k) const 
00251       {
00252       if (k == 0) 
00253         {
00254         return 0;
00255         }
00256       int exponent;
00257       CoordinateType mantissa = vcl_frexp(k, &exponent);
00258       size_t value = static_cast<size_t>(vcl_fabs(mantissa));
00259       value = ( 2 * value - 1 ) * ~0U;
00260       return value;
00261       }
00262     };
00263   
00264   // We use a hash to associate the endpoints of each contour with the 
00265   // contour itself. This makes it easy to look up which contour we should add
00266   // a new arc to.
00267   // We can't store the contours themselves in the hashtable because we
00268   // need to have two tables (one to hash from beginpoint -> contour and one 
00269   // for endpoint -> contour), and sometimes will remove a contour from the 
00270   // tables (if it has been closed or merged with another contour). So in the
00271   // hash table we store a reference to the contour. Because sometimes we will
00272   // need to merge contours, we need to be able to quickly remove contours 
00273   // from our list when they have been merged into another. Thus, we store 
00274   // an iterator pointing to the contour in the list.
00275 
00276   typedef hash_map<VertexType, ContourRef, VertexHash>    VertexToContourMap;
00277   typedef typename VertexToContourMap::iterator           VertexMapIterator;
00278   typedef typename VertexToContourMap::value_type         VertexContourRefPair;
00279 
00280   // The contours we find in the image are stored here
00281   ContourContainer                                        m_Contours;
00282 
00283   // And indexed by their beginning and ending points here
00284   VertexToContourMap                                      m_ContourStarts;
00285   VertexToContourMap                                      m_ContourEnds;
00286 
00287 };
00288   
00289 } // end namespace itk
00290 
00291 #ifndef ITK_MANUAL_INSTANTIATION
00292 #include "itkContourExtractor2DImageFilter.txx"
00293 #endif
00294 
00295 #endif
00296 

Generated at Tue Sep 15 02:41:16 2009 for ITK by doxygen 1.5.8 written by Dimitri van Heesch, © 1997-2000