ITK  5.2.0
Insight Toolkit
itkContourExtractor2DImageFilter.h
Go to the documentation of this file.
1 /*=========================================================================
2  *
3  * Copyright NumFOCUS
4  *
5  * Licensed under the Apache License, Version 2.0 (the "License");
6  * you may not use this file except in compliance with the License.
7  * You may obtain a copy of the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0.txt
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  *
17  *=========================================================================*/
18 #ifndef itkContourExtractor2DImageFilter_h
19 #define itkContourExtractor2DImageFilter_h
20 
21 #include <deque>
22 #include <list>
23 #include <unordered_map>
24 #include "itkConceptChecking.h"
25 #include "itkImageRegionIterator.h"
26 #include "itkImageRegionRange.h"
27 #include "itkImageToPathFilter.h"
28 #include "itkIndexRange.h"
30 
31 namespace itk
32 {
107 template <typename TInputImage>
108 class ITK_TEMPLATE_EXPORT ContourExtractor2DImageFilter
109  : public ImageToPathFilter<TInputImage, PolyLineParametricPath<2>>
110 {
111 public:
112  ITK_DISALLOW_COPY_AND_MOVE(ContourExtractor2DImageFilter);
113 
115  static constexpr unsigned int InputImageDimension{ TInputImage::ImageDimension };
116 
118  using InputImageType = TInputImage;
120 
126 
128  itkNewMacro(Self);
129 
132 
134  using InputImagePointer = typename InputImageType::Pointer;
137  using InputOffsetType = typename InputImageType::OffsetType;
138  using InputPixelType = typename InputImageType::PixelType;
142  using VertexListConstPointer = typename VertexListType::ConstPointer;
144  using VertexValueType = typename VertexType::ValueType;
145 
148 
155 
158  itkSetMacro(ReverseContourOrientation, bool);
159  itkGetConstReferenceMacro(ReverseContourOrientation, bool);
160  itkBooleanMacro(ReverseContourOrientation);
162 
166  itkSetMacro(VertexConnectHighPixels, bool);
167  itkGetConstReferenceMacro(VertexConnectHighPixels, bool);
168  itkBooleanMacro(VertexConnectHighPixels);
170 
172  itkSetMacro(LabelContours, bool);
173  itkGetConstReferenceMacro(LabelContours, bool);
174  itkBooleanMacro(LabelContours);
176 
179  void
180  SetRequestedRegion(const InputRegionType region);
181 
182  itkGetConstReferenceMacro(RequestedRegion, InputRegionType);
183  void
184  ClearRequestedRegion();
185 
188  itkSetMacro(ContourValue, InputRealType);
189  itkGetConstReferenceMacro(ContourValue, InputRealType);
191 
192 #ifdef ITK_USE_CONCEPT_CHECKING
193  // Begin concept checking
195  itkConceptMacro(InputPixelTypeComparable, (Concept::Comparable<InputPixelType>));
196  itkConceptMacro(InputHasPixelTraitsCheck, (Concept::HasPixelTraits<InputPixelType>));
197  itkConceptMacro(InputHasNumericTraitsCheck, (Concept::HasNumericTraits<InputPixelType>));
198  // End concept checking
199 #endif
200 
201 protected:
203  ~ContourExtractor2DImageFilter() override = default;
204  void
205  PrintSelf(std::ostream & os, Indent indent) const override;
206 
207  void
208  GenerateData() override;
209 
213  void
214  GenerateInputRequestedRegion() override;
215 
216 private:
217  using LabelsContainer = std::vector<InputPixelType>;
218  using LabelsConstIterator = typename LabelsContainer::const_iterator;
219  using LabelsIterator = typename LabelsContainer::iterator;
220 
227 
228  // Represent each contour as deque of vertices to facilitate addition of
229  // nodes at beginning or end. At the end of the processing, we will copy
230  // the contour into a PolyLineParametricPath.
231  // We subclass the deque to store an additional bit of information: an
232  // identification number for each growing contour. We use this number so
233  // that when it becomes necessary to merge two growing contours, we can
234  // merge the newer one into the older one. This helps because then we can
235  // guarantee that the output contour list is ordered from left to right,
236  // top to bottom (in terms of the first pixel of the contour encountered
237  // by the marching squares). Currently we make no guarantees that this
238  // pixel is the first pixel in the contour list, just that the contours
239  // are so ordered in the output. Ensuring this latter condition (first
240  // pixel traversed = first pixel in contour) would be possible by either
241  // changing the merging rules, which would make the contouring operation
242  // slower, or by storing additional data as to which pixel was first.
243  class ContourType : public std::deque<VertexType>
244  {
245  public:
246  unsigned int m_ContourNumber;
247  };
248 
249  // Store all the growing contours in a list. We may need to delete contours
250  // from anywhere in the sequence (when we merge them together), so we need to
251  // use a list instead of a vector or similar.
252  using ContourConstIterator = typename ContourType::const_iterator;
253  using ContourContainerType = std::list<ContourType>;
254  using ContourContainerIterator = typename ContourContainerType::iterator;
255  using ContourContainerConstIterator = typename ContourContainerType::const_iterator;
256 
257  // We use a hash to associate the endpoints of each contour with the
258  // contour itself. This makes it easy to look up which contour we should add
259  // a new arc to.
260 
261  // We can't store the contours themselves in the hashtable because we
262  // need to have two tables (one to hash from beginpoint -> contour and one
263  // for endpoint -> contour), and sometimes will remove a contour from the
264  // tables (if it has been closed or merged with another contour). Because
265  // sometimes we will need to merge contours, we need to be able to quickly
266  // remove contours from our list when they have been merged into
267  // another. Thus, we store an iterator pointing to the contour in the list.
268 
269  struct VertexHash
270  {
271  using CoordinateType = typename VertexType::CoordRepType;
272  inline std::size_t
273  operator()(const VertexType & v) const noexcept
274  {
275  return std::hash<CoordinateType>{}(v[0]) ^ (std::hash<CoordinateType>{}(v[1]) << 1);
276  }
277  };
278  using VertexToContourContainerIteratorMap = std::unordered_map<VertexType, ContourContainerIterator, VertexHash>;
279  using VertexToContourContainerIteratorMapIterator = typename VertexToContourContainerIteratorMap::iterator;
280  using VertexToContourContainerIteratorMapConstIterator = typename VertexToContourContainerIteratorMap::const_iterator;
281  using VertexToContourContainerIteratorMapKeyValuePair = typename VertexToContourContainerIteratorMap::value_type;
282 
283  // Subroutine to create contours for a single label.
284  void
285  CreateSingleContour(InputPixelType label,
286  const InputImageType * input,
287  const InputRegionType extendedRegion,
288  SizeValueType totalNumberOfPixels,
289  ContourContainerType & contoursOutput);
290 
291  // Subroutine to handle the case that the supplied values are
292  // labels, which are *not* compared to a contour value.
293  void
294  GenerateDataForLabels();
295 
296  VertexType
297  InterpolateContourPosition(InputPixelType fromValue,
298  InputPixelType toValue,
299  InputIndexType fromIndex,
300  InputOffsetType toOffset);
301 
302  struct ContourData
303  {
307  SizeValueType m_NumberOfContoursCreated = 0;
308  };
309 
310  void
311  AddSegment(const VertexType from, const VertexType to, ContourData & contourData);
312 
313  void
314  FillOutputs(const std::vector<InputPixelType> & allLabels,
315  std::unordered_map<InputPixelType, ContourContainerType> & labelsContoursOutput);
316 
318 };
319 } // end namespace itk
320 
321 #ifndef ITK_MANUAL_INSTANTIATION
322 # include "itkContourExtractor2DImageFilter.hxx"
323 #endif
324 
325 #endif
itk::ContourExtractor2DImageFilter::VertexHash::CoordinateType
typename VertexType::CoordRepType CoordinateType
Definition: itkContourExtractor2DImageFilter.h:271
itkIndexRange.h
itkImageRegionRange.h
itk::ImageRegionRange
Definition: itkImageRegionRange.h:72
itk::Concept::HasNumericTraits
Definition: itkConceptChecking.h:714
itk::ContourExtractor2DImageFilter::LabelsContainer
std::vector< InputPixelType > LabelsContainer
Definition: itkContourExtractor2DImageFilter.h:217
itk::ContourExtractor2DImageFilter
Computes a list of PolyLineParametricPath objects from the contours in a 2D image.
Definition: itkContourExtractor2DImageFilter.h:108
itk::ContourExtractor2DImageFilter::m_UnusedLabel
InputPixelType m_UnusedLabel
Definition: itkContourExtractor2DImageFilter.h:317
itk::ContourExtractor2DImageFilter::ContourData
Definition: itkContourExtractor2DImageFilter.h:302
itk::ContourExtractor2DImageFilter::LabelsIterator
typename LabelsContainer::iterator LabelsIterator
Definition: itkContourExtractor2DImageFilter.h:219
itkImageToPathFilter.h
itk::ContourExtractor2DImageFilter::m_ReverseContourOrientation
bool m_ReverseContourOrientation
Definition: itkContourExtractor2DImageFilter.h:222
itk::ContourExtractor2DImageFilter::InputIndexType
typename InputImageType::IndexType InputIndexType
Definition: itkContourExtractor2DImageFilter.h:135
itk::ContourExtractor2DImageFilter::VertexListType
typename OutputPathType::VertexListType VertexListType
Definition: itkContourExtractor2DImageFilter.h:141
itk::ContourExtractor2DImageFilter::VertexToContourContainerIteratorMapKeyValuePair
typename VertexToContourContainerIteratorMap::value_type VertexToContourContainerIteratorMapKeyValuePair
Definition: itkContourExtractor2DImageFilter.h:281
itkConceptChecking.h
itk::ContourExtractor2DImageFilter::ContourType::m_ContourNumber
unsigned int m_ContourNumber
Definition: itkContourExtractor2DImageFilter.h:246
itk::GTest::TypedefsAndConstructors::Dimension2::SizeType
ImageBaseType::SizeType SizeType
Definition: itkGTestTypedefsAndConstructors.h:49
itk::ContourExtractor2DImageFilter::VertexHash::operator()
std::vcl_size_t operator()(const VertexType &v) const noexcept
Definition: itkContourExtractor2DImageFilter.h:273
itk::ContourExtractor2DImageFilter::ContourContainerIterator
typename ContourContainerType::iterator ContourContainerIterator
Definition: itkContourExtractor2DImageFilter.h:254
itk::SmartPointer< Self >
itkImageRegionIterator.h
itk::Indent
Control indentation during Print() invocation.
Definition: itkIndent.h:49
itk::ContourExtractor2DImageFilter::m_ContourValue
InputRealType m_ContourValue
Definition: itkContourExtractor2DImageFilter.h:221
itk::ContourExtractor2DImageFilter::OutputPathPointer
typename OutputPathType::Pointer OutputPathPointer
Definition: itkContourExtractor2DImageFilter.h:140
itk::ContourExtractor2DImageFilter::InputSizeType
typename InputImageType::SizeType InputSizeType
Definition: itkContourExtractor2DImageFilter.h:136
itk::Concept::SameDimension
Definition: itkConceptChecking.h:694
itk::ImageToPathFilter
Base class for filters that take an image as input and produce an path as output.
Definition: itkImageToPathFilter.h:43
itk::ImageRegionIterator
A multi-dimensional iterator templated over image type that walks a region of pixels.
Definition: itkImageRegionIterator.h:80
itk::GTest::TypedefsAndConstructors::Dimension2::IndexType
ImageBaseType::IndexType IndexType
Definition: itkGTestTypedefsAndConstructors.h:50
itk::LightObject
Light weight base class for most itk classes.
Definition: itkLightObject.h:59
itk::PolyLineParametricPath
Represent a path of line segments through ND Space.
Definition: itkPolyLineParametricPath.h:57
itk::ContourExtractor2DImageFilter::InputRegionType
typename InputImageType::RegionType InputRegionType
Definition: itkContourExtractor2DImageFilter.h:139
itk::ContourExtractor2DImageFilter::ContourData::m_ContourEnds
VertexToContourContainerIteratorMap m_ContourEnds
Definition: itkContourExtractor2DImageFilter.h:306
itk::ContourExtractor2DImageFilter::InputImagePointer
typename InputImageType::Pointer InputImagePointer
Definition: itkContourExtractor2DImageFilter.h:134
itk::GTest::TypedefsAndConstructors::Dimension2::RegionType
ImageBaseType::RegionType RegionType
Definition: itkGTestTypedefsAndConstructors.h:54
itk::ContourExtractor2DImageFilter::ContourData::m_Contours
ContourContainerType m_Contours
Definition: itkContourExtractor2DImageFilter.h:304
itk::ContourExtractor2DImageFilter::VertexToContourContainerIteratorMapIterator
typename VertexToContourContainerIteratorMap::iterator VertexToContourContainerIteratorMapIterator
Definition: itkContourExtractor2DImageFilter.h:279
itk::ContourExtractor2DImageFilter::m_UseCustomRegion
bool m_UseCustomRegion
Definition: itkContourExtractor2DImageFilter.h:225
itk::ContourExtractor2DImageFilter::VertexListConstPointer
typename VertexListType::ConstPointer VertexListConstPointer
Definition: itkContourExtractor2DImageFilter.h:142
itk::ContourExtractor2DImageFilter::ContourConstIterator
typename ContourType::const_iterator ContourConstIterator
Definition: itkContourExtractor2DImageFilter.h:252
itk::Concept::Comparable
Definition: itkConceptChecking.h:330
itk::NumericTraits
Define additional traits for native types such as int or float.
Definition: itkNumericTraits.h:58
itk::ContourExtractor2DImageFilter::ContourData::m_ContourStarts
VertexToContourContainerIteratorMap m_ContourStarts
Definition: itkContourExtractor2DImageFilter.h:305
itk::ContourExtractor2DImageFilter::ContourContainerType
std::list< ContourType > ContourContainerType
Definition: itkContourExtractor2DImageFilter.h:253
itk::ContourExtractor2DImageFilter::m_RequestedRegion
InputRegionType m_RequestedRegion
Definition: itkContourExtractor2DImageFilter.h:226
itk::ContourExtractor2DImageFilter::ContourContainerConstIterator
typename ContourContainerType::const_iterator ContourContainerConstIterator
Definition: itkContourExtractor2DImageFilter.h:255
itk::ContourExtractor2DImageFilter::VertexHash
Definition: itkContourExtractor2DImageFilter.h:269
itkConceptMacro
#define itkConceptMacro(name, concept)
Definition: itkConceptChecking.h:65
itk::ContourExtractor2DImageFilter::VertexType
typename OutputPathType::VertexType VertexType
Definition: itkContourExtractor2DImageFilter.h:143
itk
The "itk" namespace contains all Insight Segmentation and Registration Toolkit (ITK) classes....
Definition: itkAnnulusOperator.h:24
itk::ContinuousIndex
A templated class holding a point in n-Dimensional image space.
Definition: itkContinuousIndex.h:46
itk::ContourExtractor2DImageFilter::InputRealType
typename NumericTraits< InputPixelType >::RealType InputRealType
Definition: itkContourExtractor2DImageFilter.h:147
itk::ContourExtractor2DImageFilter::m_VertexConnectHighPixels
bool m_VertexConnectHighPixels
Definition: itkContourExtractor2DImageFilter.h:223
itk::IndexRange
Definition: itkIndexRange.h:78
itk::ImageRegionConstIterator
A multi-dimensional iterator templated over image type that walks a region of pixels.
Definition: itkImageRegionConstIterator.h:109
itk::ContourExtractor2DImageFilter::VertexToContourContainerIteratorMap
std::unordered_map< VertexType, ContourContainerIterator, VertexHash > VertexToContourContainerIteratorMap
Definition: itkContourExtractor2DImageFilter.h:278
itk::Concept::HasPixelTraits
Definition: itkConceptChecking.h:751
itk::ContourExtractor2DImageFilter::VertexValueType
typename VertexType::ValueType VertexValueType
Definition: itkContourExtractor2DImageFilter.h:144
itk::ContourExtractor2DImageFilter::InputOffsetType
typename InputImageType::OffsetType InputOffsetType
Definition: itkContourExtractor2DImageFilter.h:137
itk::ContourExtractor2DImageFilter::InputImageType
TInputImage InputImageType
Definition: itkContourExtractor2DImageFilter.h:118
itk::ContourExtractor2DImageFilter::ContourType
Definition: itkContourExtractor2DImageFilter.h:243
itkPolyLineParametricPath.h
itk::VectorContainer
Define a front-end to the STL "vector" container that conforms to the IndexedContainerInterface.
Definition: itkVectorContainer.h:48
itk::ContourExtractor2DImageFilter::m_LabelContours
bool m_LabelContours
Definition: itkContourExtractor2DImageFilter.h:224
itk::ContourExtractor2DImageFilter::InputPixelType
typename InputImageType::PixelType InputPixelType
Definition: itkContourExtractor2DImageFilter.h:138
itk::SizeValueType
unsigned long SizeValueType
Definition: itkIntTypes.h:83
itk::ContourExtractor2DImageFilter::VertexToContourContainerIteratorMapConstIterator
typename VertexToContourContainerIteratorMap::const_iterator VertexToContourContainerIteratorMapConstIterator
Definition: itkContourExtractor2DImageFilter.h:280
itk::ContourExtractor2DImageFilter::LabelsConstIterator
typename LabelsContainer::const_iterator LabelsConstIterator
Definition: itkContourExtractor2DImageFilter.h:218