Medical Imaging Interaction Toolkit  2018.4.99-6aa36ba9
Medical Imaging Interaction Toolkit
itkContourExtractor2DImageFilter.h
Go to the documentation of this file.
1 /*============================================================================
2 
3 The Medical Imaging Interaction Toolkit (MITK)
4 
5 Copyright (c) German Cancer Research Center (DKFZ)
6 All rights reserved.
7 
8 Use of this source code is governed by a 3-clause BSD license that can be
9 found in the LICENSE file.
10 
11 ============================================================================*/
12 
13 /*===================================================================
14 
15 This file is based heavily on a corresponding ITK filter.
16 
17 ===================================================================*/
18 
19 #ifndef __itkContourExtractor2DImageFilter_h
20 #define __itkContourExtractor2DImageFilter_h
21 
22 #include "itkConceptChecking.h"
23 #include "itkImageToPathFilter.h"
24 #include "itkNumericTraits.h"
25 #include "itkPolyLineParametricPath.h"
26 #include "vcl_deque.h"
27 #include "vcl_list.h"
28 #include <itksys/hash_map.hxx>
29 
30 namespace itk
31 {
92  template <class TInputImage>
93  class ITK_EXPORT ContourExtractor2DImageFilter : public ImageToPathFilter<TInputImage, PolyLineParametricPath<2>>
94  {
95  public:
97  itkStaticConstMacro(InputImageDimension, unsigned int, TInputImage::ImageDimension);
98 
100  typedef TInputImage InputImageType;
101  typedef PolyLineParametricPath<2> OutputPathType;
102 
108 
110  itkFactorylessNewMacro(Self) itkCloneMacro(Self)
111 
112 
114 
116  typedef typename InputImageType::Pointer InputImagePointer;
117  typedef typename InputImageType::PixelType InputPixelType;
118  typedef typename InputImageType::IndexType InputIndexType;
119  typedef typename InputImageType::OffsetType InputOffsetType;
120  typedef typename InputImageType::RegionType InputRegionType;
121  typedef typename OutputPathType::Pointer OutputPathPointer;
122  typedef typename OutputPathType::VertexType VertexType;
123  typedef typename OutputPathType::VertexListType VertexListType;
124 
126  typedef typename NumericTraits<InputPixelType>::RealType InputRealType;
127 
128  typedef typename VertexListType::ConstPointer VertexListConstPointer;
131  itkSetMacro(ReverseContourOrientation, bool);
132  itkGetConstReferenceMacro(ReverseContourOrientation, bool);
133  itkBooleanMacro(ReverseContourOrientation);
134 
138  itkSetMacro(VertexConnectHighPixels, bool);
139  itkGetConstReferenceMacro(VertexConnectHighPixels, bool);
140  itkBooleanMacro(VertexConnectHighPixels);
141 
144  void SetRequestedRegion(const InputRegionType region);
145  itkGetConstReferenceMacro(RequestedRegion, InputRegionType);
146  void ClearRequestedRegion();
147 
150  itkSetMacro(ContourValue, InputRealType);
151  itkGetConstReferenceMacro(ContourValue, InputRealType);
152 
153 #ifdef ITK_USE_CONCEPT_CHECKING
154 
155  itkConceptMacro(DimensionShouldBe2, (Concept::SameDimension<itkGetStaticConstMacro(InputImageDimension), 2>));
156  itkConceptMacro(InputPixelTypeComparable, (Concept::Comparable<InputPixelType>));
157  itkConceptMacro(InputHasPixelTraitsCheck, (Concept::HasPixelTraits<InputPixelType>));
158  itkConceptMacro(InputHasNumericTraitsCheck, (Concept::HasNumericTraits<InputPixelType>));
160 #endif
161 
162  protected:
163  ContourExtractor2DImageFilter();
164  ~ContourExtractor2DImageFilter() override;
165  void PrintSelf(std::ostream &os, Indent indent) const override;
166 
167  void GenerateData() override;
168 
172  void GenerateInputRequestedRegion() override;
173 
174  private:
175  VertexType InterpolateContourPosition(InputPixelType fromValue,
176  InputPixelType toValue,
177  InputIndexType fromIndex,
178  InputOffsetType toOffset);
179  void AddSegment(const VertexType from, const VertexType to);
180  void FillOutputs();
181  ContourExtractor2DImageFilter(const Self &); // purposely not implemented
182  void operator=(const Self &); // purposely not implemented
183 
184  InputRealType m_ContourValue;
185  bool m_ReverseContourOrientation;
186  bool m_VertexConnectHighPixels;
187  bool m_UseCustomRegion;
188  InputRegionType m_RequestedRegion;
189  unsigned int m_NumberOfContoursCreated;
190 
191  // Represent each contour as deque of vertices to facilitate addition of
192  // nodes at beginning or end. At the end of the processing, we will copy
193  // the contour into a PolyLineParametricPath.
194  // We subclass the deque to store an additional bit of information: an
195  // identification number for each growing contour. We use this number so
196  // that when it becomes necessary to merge two growing contours, we can
197  // merge the newer one into the older one. This helps because then we can
198  // guarantee that the output contour list is ordered from left to right,
199  // top to bottom (in terms of the first pixel of the contour encountered
200  // by the marching squares). Currently we make no guarantees that this
201  // pixel is the first pixel in the contour list, just that the contours
202  // are so ordered in the output. Ensuring this latter condition (first
203  // pixel traversed = first pixel in contour) would be possible by either
204  // changing the merging rules, which would make the contouring operation
205  // slower, or by storing additional data as to which pixel was first.
206  class ContourType : public vcl_deque<VertexType>
207  {
208  public:
209  unsigned int m_ContourNumber;
210  };
211 
212  // Store all the growing contours in a list. We may need to delete contours
213  // from anywhere in the sequence (when we merge them together), so we need to
214  // use a list instead of a vector or similar.
215  typedef vcl_list<ContourType> ContourContainer;
216  typedef typename ContourContainer::iterator ContourRef;
217 
218  // declare the hash function we are using for the hash_map.
219  struct VertexHash
220  {
221  typedef typename VertexType::CoordRepType CoordinateType;
222  inline size_t operator()(const VertexType &k) const
223  {
224  // Xor the hashes of the vertices together, after multiplying the
225  // first by some number, so that identical (x,y) vertex indices
226  // don't all hash to the same bucket. This is a decent if not
227  // optimal hash.
228  const size_t hashVertex1 = this->float_hash(k[0] * 0xbeef);
229  const size_t hashVertex2 = this->float_hash(k[1]);
230  const size_t hashValue = hashVertex1 ^ hashVertex2;
231  return hashValue;
232  }
233 
234  // Define hash function for floats. Based on method from
235  // http://www.brpreiss.com/books/opus4/html/page217.html
236  inline size_t float_hash(const CoordinateType &k) const
237  {
238  if (k == 0)
239  {
240  return 0;
241  }
242  int exponent;
243  CoordinateType mantissa = vcl_frexp(k, &exponent);
244  size_t value = static_cast<size_t>(vcl_fabs(mantissa));
245  value = (2 * value - 1) * ~0U;
246  return value;
247  }
248  };
249 
250  // We use a hash to associate the endpoints of each contour with the
251  // contour itself. This makes it easy to look up which contour we should add
252  // a new arc to.
253  // We can't store the contours themselves in the hashtable because we
254  // need to have two tables (one to hash from beginpoint -> contour and one
255  // for endpoint -> contour), and sometimes will remove a contour from the
256  // tables (if it has been closed or merged with another contour). So in the
257  // hash table we store a reference to the contour. Because sometimes we will
258  // need to merge contours, we need to be able to quickly remove contours
259  // from our list when they have been merged into another. Thus, we store
260  // an iterator pointing to the contour in the list.
261 
262  typedef itksys::hash_map<VertexType, ContourRef, VertexHash> VertexToContourMap;
263  typedef typename VertexToContourMap::iterator VertexMapIterator;
264  typedef typename VertexToContourMap::value_type VertexContourRefPair;
265 
266  // The contours we find in the image are stored here
267  ContourContainer m_Contours;
268 
269  // And indexed by their beginning and ending points here
270  VertexToContourMap m_ContourStarts;
271  VertexToContourMap m_ContourEnds;
272  };
273 
274 } // end namespace itk
275 
276 #ifndef ITK_MANUAL_INSTANTIATION
278 #endif
279 
280 #endif
float k(1.0)
Base class for filters that take an image as input and produce an path as output. ...
ImageToPathFilter< InputImageType, OutputPathType > Superclass
unsigned short PixelType
Computes a list of PolyLineParametricPath objects from the contours in a 2D image.
NumericTraits< InputPixelType >::RealType InputRealType