itkWatershedSegmentTree.h

Go to the documentation of this file.

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

  Program:   Insight Segmentation & Registration Toolkit
  Module:    $RCSfile: itkWatershedSegmentTree.h,v $
  Language:  C++
  Date:      $Date: 2009-01-27 19:30:19 $
  Version:   $Revision: 1.13 $

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

#include "itkObjectFactory.h"
#include "itkDataObject.h"
#include "itkProcessObject.h"
#include <deque>
#include <functional>

namespace itk
{
namespace watershed
{
/* \class SegmentTree
 * A data structure for storing segment merge information used in filters of  
 * the watershed segmentation algorithm.  See itk::WatershedImageFilter for an
 * overview.
 *
 * \par
 * This class is the implemenation of the ``merge tree'' referred to in the
 * documentation for itk::WatershedImageFilter and other watershed segmentation 
 * component classes.  It holds a list of merges among image segments at
 * various saliency levels. The list is actually a representation of a binary
 * tree, whose nodes are segments and edges are saliencies.
 * \ingroup WatershedSegmentation
 * \sa itk::WatershedImageFilter */
template <class TScalarType>
class ITK_EXPORT SegmentTree : public DataObject
{
public:
  typedef SegmentTree              Self;
  typedef DataObject               Superclass;
  typedef SmartPointer<Self>       Pointer;
  typedef SmartPointer<const Self> ConstPointer;
  itkNewMacro(Self);
  itkTypeMacro(WatershedSegmentTree, DataObject);
  typedef TScalarType ScalarType;

  struct merge_t
    {
    unsigned long from;
    unsigned long to;
    ScalarType saliency;
    };

  typedef std::deque<merge_t>                DequeType;
  typedef typename DequeType::iterator       Iterator;
  typedef typename DequeType::const_iterator ConstIterator;
  typedef typename DequeType::value_type     ValueType;

  struct merge_comp : public std::binary_function<bool, const merge_t&,
                      const merge_t& >
    {
    bool operator()(const merge_t &a, const merge_t &b)
      {
      return b.saliency < a.saliency;
      }
    };

  struct sort_comp : public std::binary_function<bool, const merge_t&,
                     const merge_t& >
    {
    bool operator()(const merge_t &a, const merge_t &b)
      {
      return a.saliency < b.Saliency;
      }
    };

  typename DequeType::size_type Size() const
    { return m_Deque.size(); }

  bool Empty() const
    { return m_Deque.empty();    }

  const merge_t &Front() const
    { return m_Deque.front(); }

  const merge_t &Back() const
    { return m_Deque.back(); } 

  merge_t &Front()
    { return m_Deque.front(); }

  merge_t &Back()
    { return m_Deque.back(); }

  void PushFront(const ValueType &t)
    { m_Deque.push_front(t); }

  void PushBack( const ValueType &t)
    { m_Deque.push_back(t); }

  void PopFront()
    { m_Deque.pop_front(); }

  void PopBack()
    { m_Deque.pop_back(); }

  Iterator Begin()
    { return m_Deque.begin(); }

  ConstIterator Begin() const
    { return m_Deque.begin(); }

  Iterator End()
    { return m_Deque.end(); }

  ConstIterator End() const
    { return m_Deque.end(); }

  void Clear()
    { m_Deque.clear(); }

  void Initialize();

protected:
  SegmentTree() {}
  virtual ~SegmentTree() {}
  SegmentTree(const Self&) {}
  void operator=(const Self&) {}
  void PrintSelf(std::ostream& os, Indent indent) const;

  DequeType m_Deque;
};
}// end namespace watershed
}// end namespace itk

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

#endif