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