itkContourExtractor2DImageFilter.h

Go to the documentation of this file.

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

The Medical Imaging Interaction Toolkit (MITK)

Copyright (c) German Cancer Research Center,
Division of Medical and Biological Informatics.
All rights reserved.

This software is distributed WITHOUT ANY WARRANTY; without
even the implied warranty of MERCHANTABILITY or FITNESS FOR
A PARTICULAR PURPOSE.

See LICENSE.txt or http://www.mitk.org for details.

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

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

This file is based heavily on a corresponding ITK filter.

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

#ifndef __itkContourExtractor2DImageFilter_h
#define __itkContourExtractor2DImageFilter_h

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

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;

    itkFactorylessNewMacro(Self) itkCloneMacro(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 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 "itkContourExtractor2DImageFilter.txx"
#endif

#endif