itkContourExtractor2DImageFilter.h

Go to the documentation of this file.

/*=========================================================================

  Program:   Insight Segmentation & Registration Toolkit
  Module:    $RCSfile: itkContourExtractor2DImageFilter.h,v $
  Language:  C++
  Date:      $Date: 2008-12-06 13:28:10 $
  Version:   $Revision: 1.10 $

  Copyright (c) Insight Software Consortium. All rights reserved.
  See ITKCopyright.txt or http://www.itk.org/HTML/Copyright.htm for details.

     This software is distributed WITHOUT ANY WARRANTY; without even 
     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
     PURPOSE.  See the above copyright notices for more information.

=========================================================================*/

#ifndef __itkContourExtractor2DImageFilter_h
#define __itkContourExtractor2DImageFilter_h

#include "itkImageToPathFilter.h"
#include "itkNumericTraits.h"
#include "itkPolyLineParametricPath.h"
#include "itkConceptChecking.h"
#include "itk_hash_map.h"
#include "vcl_deque.h"
#include "vcl_list.h"

namespace itk
{
template <class TInputImage>
class ITK_EXPORT ContourExtractor2DImageFilter :
    public ImageToPathFilter< TInputImage, PolyLineParametricPath<2> >
{
public:
  itkStaticConstMacro(InputImageDimension, unsigned int,
    TInputImage::ImageDimension);

  typedef TInputImage                               InputImageType;
  typedef PolyLineParametricPath<2>                 OutputPathType;

  typedef ContourExtractor2DImageFilter                     Self;
  typedef ImageToPathFilter<InputImageType, OutputPathType> Superclass;
  typedef SmartPointer<Self>                                Pointer;
  typedef SmartPointer<const Self>                          ConstPointer;

  itkNewMacro(Self);

  itkTypeMacro(ContourExtractor2DImageFilter, ImageToPathFilter);

  typedef typename InputImageType::Pointer                  InputImagePointer;
  typedef typename InputImageType::PixelType                InputPixelType;
  typedef typename InputImageType::IndexType                InputIndexType;
  typedef typename InputImageType::OffsetType               InputOffsetType;
  typedef typename InputImageType::RegionType               InputRegionType;  
  typedef typename OutputPathType::Pointer                  OutputPathPointer;
  typedef typename OutputPathType::VertexType               VertexType;
  typedef typename OutputPathType::VertexListType           VertexListType;

  typedef typename NumericTraits<InputPixelType>::RealType  InputRealType;

  typedef typename VertexListType::ConstPointer 
                                                       VertexListConstPointer;
  itkSetMacro(ReverseContourOrientation, bool);
  itkGetConstReferenceMacro(ReverseContourOrientation, bool);
  itkBooleanMacro(ReverseContourOrientation);

  itkSetMacro(VertexConnectHighPixels, bool);
  itkGetConstReferenceMacro(VertexConnectHighPixels, bool);
  itkBooleanMacro(VertexConnectHighPixels);

  void SetRequestedRegion(const InputRegionType region);
  itkGetConstReferenceMacro(RequestedRegion, InputRegionType);
  void ClearRequestedRegion();

  itkSetMacro(ContourValue,InputRealType);
  itkGetConstReferenceMacro(ContourValue, InputRealType);


#ifdef ITK_USE_CONCEPT_CHECKING

  itkConceptMacro(DimensionShouldBe2,
    (Concept::SameDimension<itkGetStaticConstMacro(InputImageDimension),2>));
  itkConceptMacro(InputPixelTypeComparable,
    (Concept::Comparable<InputPixelType>));
  itkConceptMacro(InputHasPixelTraitsCheck,
    (Concept::HasPixelTraits<InputPixelType>));
  itkConceptMacro(InputHasNumericTraitsCheck,
    (Concept::HasNumericTraits<InputPixelType>));

#endif

protected:

  ContourExtractor2DImageFilter(); 
  virtual ~ContourExtractor2DImageFilter();
  void PrintSelf(std::ostream& os, Indent indent) const;
  
  void GenerateData();
  
  virtual void GenerateInputRequestedRegion() 
            throw(InvalidRequestedRegionError);  

private:
  VertexType InterpolateContourPosition(InputPixelType fromValue, 
                                        InputPixelType toValue,
                                        InputIndexType fromIndex,
                                        InputOffsetType toOffset);
  void AddSegment(const VertexType from, const VertexType to);
  void FillOutputs();
  ContourExtractor2DImageFilter(const Self&); //purposely not implemented
  void operator=(const Self&); //purposely not implemented
  
  InputRealType                                   m_ContourValue;
  bool                                            m_ReverseContourOrientation;
  bool                                            m_VertexConnectHighPixels;
  bool                                            m_UseCustomRegion;
  InputRegionType                                 m_RequestedRegion;
  unsigned int                                    m_NumberOfContoursCreated;
  
  // Represent each contour as deque of vertices to facilitate addition of
  // nodes at beginning or end. At the end of the processing, we will copy 
  // the contour into a PolyLineParametricPath.
  // We subclass the deque to store an additional bit of information: an 
  // identification number for each growing contour. We use this number so
  // that when it becomes necessary to merge two growing contours, we can 
  // merge the newer one into the older one. This helps because then we can
  // guarantee that the output contour list is ordered from left to right,
  // top to bottom (in terms of the first pixel of the contour encountered
  // by the marching squares). Currently we make no guarantees that this 
  // pixel is the first pixel in the contour list, just that the contours 
  // are so ordered in the output. Ensuring this latter condition (first 
  // pixel traversed = first pixel in contour) would be possible by either 
  // changing the merging rules, which would make the contouring operation 
  //slower, or by storing additional data as to which pixel was first.
  class ContourType : public vcl_deque<VertexType>
    {
    public:
      unsigned int m_ContourNumber;
    };
  
  // Store all the growing contours in a list. We may need to delete contours
  // from anywhere in the sequence (when we merge them together), so we need to
  // use a list instead of a vector or similar.
  typedef vcl_list<ContourType>                         ContourContainer;
  typedef typename ContourContainer::iterator           ContourRef;
  
  // declare the hash function we are using for the hash_map.
  struct VertexHash
    {
    typedef typename VertexType::CoordRepType CoordinateType;
    inline size_t operator()(const VertexType& k) const 
      {
      // Xor the hashes of the vertices together, after multiplying the 
      // first by some number, so that identical (x,y) vertex indices 
      // don't all hash to the same bucket. This is a decent if not 
      // optimal hash. 
      const size_t hashVertex1 = this->float_hash(k[0] * 0xbeef);
      const size_t hashVertex2 = this->float_hash(k[1]);
      const size_t hashValue = hashVertex1 ^ hashVertex2;
      return hashValue;
      }
      
    // Define hash function for floats. Based on method from
    // http://www.brpreiss.com/books/opus4/html/page217.html
    inline size_t float_hash(const CoordinateType &k) const 
      {
      if (k == 0) 
        {
        return 0;
        }
      int exponent;
      CoordinateType mantissa = vcl_frexp(k, &exponent);
      size_t value = static_cast<size_t>(vcl_fabs(mantissa));
      value = ( 2 * value - 1 ) * ~0U;
      return value;
      }
    };
  
  // We use a hash to associate the endpoints of each contour with the 
  // contour itself. This makes it easy to look up which contour we should add
  // a new arc to.
  // We can't store the contours themselves in the hashtable because we
  // need to have two tables (one to hash from beginpoint -> contour and one 
  // for endpoint -> contour), and sometimes will remove a contour from the 
  // tables (if it has been closed or merged with another contour). So in the
  // hash table we store a reference to the contour. Because sometimes we will
  // need to merge contours, we need to be able to quickly remove contours 
  // from our list when they have been merged into another. Thus, we store 
  // an iterator pointing to the contour in the list.

  typedef hash_map<VertexType, ContourRef, VertexHash>    VertexToContourMap;
  typedef typename VertexToContourMap::iterator           VertexMapIterator;
  typedef typename VertexToContourMap::value_type         VertexContourRefPair;

  // The contours we find in the image are stored here
  ContourContainer                                        m_Contours;

  // And indexed by their beginning and ending points here
  VertexToContourMap                                      m_ContourStarts;
  VertexToContourMap                                      m_ContourEnds;

};
  
} // end namespace itk

#ifndef ITK_MANUAL_INSTANTIATION
#include "itkContourExtractor2DImageFilter.txx"
#endif

#endif