itkOrthogonalContourExtractor2DImageFilter.h

Go to the documentation of this file.

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

 NifTK: A software platform for medical image computing.

 NOTE: This class has been modified from itkContourExtractor2DImageFilter.h/.txx
 The original class would produce diagonal lines at corners. This class aims
 to strictly produce contours that use vertical and horizontal lines only.

 For this reason, apart from this header, and a class name change, there is
 as little code change as possible, so a simple diff should highlight the differences.

 The Copyright should therefore still belong to Insight Software Consortium.
============================================================================*/

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

  Program:   Insight Segmentation & Registration Toolkit
  Module:    itkContourExtractor2DImageFilter.h
  Language:  C++
  Date:      $Date$
  Version:   $Revision$

  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 itkOrthogonalContourExtractor2DImageFilter_h
#define itkOrthogonalContourExtractor2DImageFilter_h

#include <itkImageToPathFilter.h>
#include <itkNumericTraits.h>
#include <itkPolyLineParametricPath.h>
#include <itkConceptChecking.h>
#include <itksys/hash_map.hxx>
#include <vcl_deque.h>
#include <vcl_list.h>

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

  typedef TInputImage                               InputImageType;
  typedef PolyLineParametricPath<2>                 OutputPathType;

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

  itkNewMacro(Self);

  itkTypeMacro(OrthogonalContourExtractor2DImageFilter, 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:

  OrthogonalContourExtractor2DImageFilter();
  virtual ~OrthogonalContourExtractor2DImageFilter();
  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();
  OrthogonalContourExtractor2DImageFilter(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 itksys::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 "itkOrthogonalContourExtractor2DImageFilter.txx"
#endif

#endif