Medical Imaging Interaction Toolkit  2023.12.99-4c75e429
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 <deque>
27 #include <list>
28 #include <unordered_map>
29 
30 namespace itk
31 {
90  template <class TInputImage>
91  class ITK_EXPORT ContourExtractor2DImageFilter : public ImageToPathFilter<TInputImage, PolyLineParametricPath<2>>
92  {
93  public:
95  itkStaticConstMacro(InputImageDimension, unsigned int, TInputImage::ImageDimension);
96 
98  typedef TInputImage InputImageType;
99  typedef PolyLineParametricPath<2> OutputPathType;
100 
106 
108  itkFactorylessNewMacro(Self);
109  itkCloneMacro(Self);
110 
113 
115  typedef typename InputImageType::Pointer InputImagePointer;
116  typedef typename InputImageType::PixelType InputPixelType;
117  typedef typename InputImageType::IndexType InputIndexType;
118  typedef typename InputImageType::OffsetType InputOffsetType;
119  typedef typename InputImageType::RegionType InputRegionType;
120  typedef typename OutputPathType::Pointer OutputPathPointer;
121  typedef typename OutputPathType::VertexType VertexType;
122  typedef typename OutputPathType::VertexListType VertexListType;
123 
125  typedef typename NumericTraits<InputPixelType>::RealType InputRealType;
126 
127  typedef typename VertexListType::ConstPointer VertexListConstPointer;
130  itkSetMacro(ReverseContourOrientation, bool);
131  itkGetConstReferenceMacro(ReverseContourOrientation, bool);
132  itkBooleanMacro(ReverseContourOrientation);
133 
137  itkSetMacro(VertexConnectHighPixels, bool);
138  itkGetConstReferenceMacro(VertexConnectHighPixels, bool);
139  itkBooleanMacro(VertexConnectHighPixels);
140 
143  void SetRequestedRegion(const InputRegionType region);
144  itkGetConstReferenceMacro(RequestedRegion, InputRegionType);
145  void ClearRequestedRegion();
146 
149  itkSetMacro(ContourValue, InputRealType);
150  itkGetConstReferenceMacro(ContourValue, InputRealType);
151 
152 #ifdef ITK_USE_CONCEPT_CHECKING
153 
154  itkConceptMacro(DimensionShouldBe2, (Concept::SameDimension<itkGetStaticConstMacro(InputImageDimension), 2>));
155  itkConceptMacro(InputPixelTypeComparable, (Concept::Comparable<InputPixelType>));
156  itkConceptMacro(InputHasPixelTraitsCheck, (Concept::HasPixelTraits<InputPixelType>));
157  itkConceptMacro(InputHasNumericTraitsCheck, (Concept::HasNumericTraits<InputPixelType>));
159 #endif
160 
161  protected:
163  ~ContourExtractor2DImageFilter() override;
164  void PrintSelf(std::ostream &os, Indent indent) const override;
165 
166  void GenerateData() override;
167 
171  void GenerateInputRequestedRegion() override;
172 
173  private:
174  VertexType InterpolateContourPosition(InputPixelType fromValue,
175  InputPixelType toValue,
176  InputIndexType fromIndex,
177  InputOffsetType toOffset);
178  void AddSegment(const VertexType from, const VertexType to);
179  void FillOutputs();
180  ContourExtractor2DImageFilter(const Self &); // purposely not implemented
181  void operator=(const Self &); // purposely not implemented
182 
183  InputRealType m_ContourValue;
184  bool m_ReverseContourOrientation;
185  bool m_VertexConnectHighPixels;
186  bool m_UseCustomRegion;
187  InputRegionType m_RequestedRegion;
188  unsigned int m_NumberOfContoursCreated;
189 
190  // Represent each contour as deque of vertices to facilitate addition of
191  // nodes at beginning or end. At the end of the processing, we will copy
192  // the contour into a PolyLineParametricPath.
193  // We subclass the deque to store an additional bit of information: an
194  // identification number for each growing contour. We use this number so
195  // that when it becomes necessary to merge two growing contours, we can
196  // merge the newer one into the older one. This helps because then we can
197  // guarantee that the output contour list is ordered from left to right,
198  // top to bottom (in terms of the first pixel of the contour encountered
199  // by the marching squares). Currently we make no guarantees that this
200  // pixel is the first pixel in the contour list, just that the contours
201  // are so ordered in the output. Ensuring this latter condition (first
202  // pixel traversed = first pixel in contour) would be possible by either
203  // changing the merging rules, which would make the contouring operation
204  // slower, or by storing additional data as to which pixel was first.
205  class ContourType : public std::deque<VertexType>
206  {
207  public:
208  unsigned int m_ContourNumber;
209  };
210 
211  // Store all the growing contours in a list. We may need to delete contours
212  // from anywhere in the sequence (when we merge them together), so we need to
213  // use a list instead of a vector or similar.
214  typedef std::list<ContourType> ContourContainer;
215  typedef typename ContourContainer::iterator ContourRef;
216 
217  // declare the hash function we are using for the hash_map.
218  struct VertexHash
219  {
220  typedef typename VertexType::CoordRepType CoordinateType;
221  inline size_t operator()(const VertexType &k) const
222  {
223  // Xor the hashes of the vertices together, after multiplying the
224  // first by some number, so that identical (x,y) vertex indices
225  // don't all hash to the same bucket. This is a decent if not
226  // optimal hash.
227  const size_t hashVertex1 = this->float_hash(k[0] * 0xbeef);
228  const size_t hashVertex2 = this->float_hash(k[1]);
229  const size_t hashValue = hashVertex1 ^ hashVertex2;
230  return hashValue;
231  }
232 
233  // Define hash function for floats.
234  inline size_t float_hash(const CoordinateType &k) const
235  {
236  if (k == 0)
237  {
238  return 0;
239  }
240  int exponent;
241  CoordinateType mantissa = std::frexp(k, &exponent);
242  size_t value = static_cast<size_t>(std::fabs(mantissa));
243  value = (2 * value - 1) * ~0U;
244  return value;
245  }
246  };
247 
248  // We use a hash to associate the endpoints of each contour with the
249  // contour itself. This makes it easy to look up which contour we should add
250  // a new arc to.
251  // We can't store the contours themselves in the hashtable because we
252  // need to have two tables (one to hash from beginpoint -> contour and one
253  // for endpoint -> contour), and sometimes will remove a contour from the
254  // tables (if it has been closed or merged with another contour). So in the
255  // hash table we store a reference to the contour. Because sometimes we will
256  // need to merge contours, we need to be able to quickly remove contours
257  // from our list when they have been merged into another. Thus, we store
258  // an iterator pointing to the contour in the list.
259 
260  typedef std::unordered_map<VertexType, ContourRef, VertexHash> VertexToContourMap;
261  typedef typename VertexToContourMap::iterator VertexMapIterator;
262  typedef typename VertexToContourMap::value_type VertexContourRefPair;
263 
264  // The contours we find in the image are stored here
265  ContourContainer m_Contours;
266 
267  // And indexed by their beginning and ending points here
268  VertexToContourMap m_ContourStarts;
269  VertexToContourMap m_ContourEnds;
270  };
271 
272 } // end namespace itk
273 
274 #ifndef ITK_MANUAL_INSTANTIATION
275 #include "itkContourExtractor2DImageFilter.txx"
276 #endif
277 
278 #endif
itk::ContourExtractor2DImageFilter
Computes a list of PolyLineParametricPath objects from the contours in a 2D image.
Definition: itkContourExtractor2DImageFilter.h:91
itk::ContourExtractor2DImageFilter::InputImagePointer
InputImageType::Pointer InputImagePointer
Definition: itkContourExtractor2DImageFilter.h:112
itkImageToPathFilter.h
itk::ContourExtractor2DImageFilter::InputOffsetType
InputImageType::OffsetType InputOffsetType
Definition: itkContourExtractor2DImageFilter.h:118
itk::ContourExtractor2DImageFilter::InputIndexType
InputImageType::IndexType InputIndexType
Definition: itkContourExtractor2DImageFilter.h:117
itk::SmartPointer< Self >
itk::ImageToPathFilter
Base class for filters that take an image as input and produce an path as output.
Definition: itkImageToPathFilter.h:36
itk::ContourExtractor2DImageFilter::ConstPointer
SmartPointer< const Self > ConstPointer
Definition: itkContourExtractor2DImageFilter.h:105
itk::ContourExtractor2DImageFilter::InputRegionType
InputImageType::RegionType InputRegionType
Definition: itkContourExtractor2DImageFilter.h:119
itk::ContourExtractor2DImageFilter::VertexType
OutputPathType::VertexType VertexType
Definition: itkContourExtractor2DImageFilter.h:121
itk::ContourExtractor2DImageFilter::InputPixelType
InputImageType::PixelType InputPixelType
Definition: itkContourExtractor2DImageFilter.h:116
itk::ContourExtractor2DImageFilter::Self
ContourExtractor2DImageFilter Self
Definition: itkContourExtractor2DImageFilter.h:102
itk::ContourExtractor2DImageFilter::Pointer
SmartPointer< Self > Pointer
Definition: itkContourExtractor2DImageFilter.h:104
itk
SET FUNCTIONS.
Definition: itkIntelligentBinaryClosingFilter.h:30
itk::ContourExtractor2DImageFilter::VertexListType
OutputPathType::VertexListType VertexListType
Definition: itkContourExtractor2DImageFilter.h:122
itk::ContourExtractor2DImageFilter::VertexListConstPointer
VertexListType::ConstPointer VertexListConstPointer
Definition: itkContourExtractor2DImageFilter.h:127
itk::ContourExtractor2DImageFilter::OutputPathPointer
OutputPathType::Pointer OutputPathPointer
Definition: itkContourExtractor2DImageFilter.h:120
itk::ContourExtractor2DImageFilter::InputRealType
NumericTraits< InputPixelType >::RealType InputRealType
Definition: itkContourExtractor2DImageFilter.h:125
itk::ContourExtractor2DImageFilter::InputImageType
TInputImage InputImageType
Definition: itkContourExtractor2DImageFilter.h:98
itk::ContourExtractor2DImageFilter::OutputPathType
PolyLineParametricPath< 2 > OutputPathType
Definition: itkContourExtractor2DImageFilter.h:99
itk::ContourExtractor2DImageFilter::Superclass
ImageToPathFilter< InputImageType, OutputPathType > Superclass
Definition: itkContourExtractor2DImageFilter.h:103