ITK  4.13.0
Insight Segmentation and Registration Toolkit
itkContourExtractor2DImageFilter.h
Go to the documentation of this file.
1 /*=========================================================================
2  *
3  * Copyright Insight Software Consortium
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 "itkImageToPathFilter.h"
23 #include "itkConceptChecking.h"
24 #include "itksys/hash_map.hxx"
25 #if !defined( ITK_LEGACY_FUTURE_REMOVE )
26 # include "vcl_deque.h"
27 #endif
28 #include <deque>
29 #if !defined( ITK_LEGACY_FUTURE_REMOVE )
30 # include "vcl_list.h"
31 #endif
32 #include <list>
33 
34 namespace itk
35 {
101 template< typename TInputImage >
102 class ITK_TEMPLATE_EXPORT ContourExtractor2DImageFilter:
103  public ImageToPathFilter< TInputImage, PolyLineParametricPath< 2 > >
104 {
105 public:
107  itkStaticConstMacro(InputImageDimension, unsigned int,
108  TInputImage::ImageDimension);
109 
111  typedef TInputImage InputImageType;
113 
119 
121  itkNewMacro(Self);
122 
125 
127  typedef typename InputImageType::Pointer InputImagePointer;
128  typedef typename InputImageType::PixelType InputPixelType;
130  typedef typename InputImageType::OffsetType InputOffsetType;
131  typedef typename InputImageType::RegionType InputRegionType;
135 
138 
139  typedef typename VertexListType::ConstPointer
143  itkSetMacro(ReverseContourOrientation, bool);
144  itkGetConstReferenceMacro(ReverseContourOrientation, bool);
145  itkBooleanMacro(ReverseContourOrientation);
147 
151  itkSetMacro(VertexConnectHighPixels, bool);
152  itkGetConstReferenceMacro(VertexConnectHighPixels, bool);
153  itkBooleanMacro(VertexConnectHighPixels);
155 
158  void SetRequestedRegion(const InputRegionType region);
159 
160  itkGetConstReferenceMacro(RequestedRegion, InputRegionType);
161  void ClearRequestedRegion();
162 
165  itkSetMacro(ContourValue, InputRealType);
166  itkGetConstReferenceMacro(ContourValue, InputRealType);
168 
169 #ifdef ITK_USE_CONCEPT_CHECKING
170  // Begin concept checking
171  itkConceptMacro( DimensionShouldBe2,
172  ( Concept::SameDimension< itkGetStaticConstMacro(InputImageDimension), 2 > ) );
173  itkConceptMacro( InputPixelTypeComparable,
175  itkConceptMacro( InputHasPixelTraitsCheck,
177  itkConceptMacro( InputHasNumericTraitsCheck,
179  // End concept checking
180 #endif
181 
182 protected:
183 
186  void PrintSelf(std::ostream & os, Indent indent) const ITK_OVERRIDE;
187 
188  void GenerateData() ITK_OVERRIDE;
189 
193  virtual void GenerateInputRequestedRegion() ITK_OVERRIDE;
194 
195 private:
196  VertexType InterpolateContourPosition(InputPixelType fromValue,
197  InputPixelType toValue,
198  InputIndexType fromIndex,
199  InputOffsetType toOffset);
200 
201  void AddSegment(const VertexType from, const VertexType to);
202 
203  void FillOutputs();
204 
205  ITK_DISALLOW_COPY_AND_ASSIGN(ContourExtractor2DImageFilter);
206 
207  InputRealType m_ContourValue;
208  bool m_ReverseContourOrientation;
209  bool m_VertexConnectHighPixels;
210  bool m_UseCustomRegion;
211  InputRegionType m_RequestedRegion;
212  unsigned int m_NumberOfContoursCreated;
213 
214  // Represent each contour as deque of vertices to facilitate addition of
215  // nodes at beginning or end. At the end of the processing, we will copy
216  // the contour into a PolyLineParametricPath.
217  // We subclass the deque to store an additional bit of information: an
218  // identification number for each growing contour. We use this number so
219  // that when it becomes necessary to merge two growing contours, we can
220  // merge the newer one into the older one. This helps because then we can
221  // guarantee that the output contour list is ordered from left to right,
222  // top to bottom (in terms of the first pixel of the contour encountered
223  // by the marching squares). Currently we make no guarantees that this
224  // pixel is the first pixel in the contour list, just that the contours
225  // are so ordered in the output. Ensuring this latter condition (first
226  // pixel traversed = first pixel in contour) would be possible by either
227  // changing the merging rules, which would make the contouring operation
228  //slower, or by storing additional data as to which pixel was first.
229  class ContourType:public std::deque< VertexType >
230  {
231 public:
232  unsigned int m_ContourNumber;
233  };
234 
235  // Store all the growing contours in a list. We may need to delete contours
236  // from anywhere in the sequence (when we merge them together), so we need to
237  // use a list instead of a vector or similar.
238  typedef std::list< ContourType > ContourContainer;
239  typedef typename ContourContainer::iterator ContourRef;
240 
241  // declare the hash function we are using for the hash_map.
242  struct VertexHash {
244  inline SizeValueType operator()(const VertexType & k) const
245  {
246  // Xor the hashes of the vertices together, after multiplying the
247  // first by some number, so that identical (x,y) vertex indices
248  // don't all hash to the same bucket. This is a decent if not
249  // optimal hash.
250  const SizeValueType hashVertex1 = this->float_hash(k[0] * 0xbeef);
251  const SizeValueType hashVertex2 = this->float_hash(k[1]);
252  const SizeValueType hashValue = hashVertex1 ^ hashVertex2;
253 
254  return hashValue;
255  }
256 
257  // Define hash function for floats. Based on method from
258  // http://www.brpreiss.com/books/opus4/html/page217.html
259  inline SizeValueType float_hash(const CoordinateType & k) const
260  {
261  if ( k == 0 )
262  {
263  return 0;
264  }
265  int exponent;
266  CoordinateType mantissa = std::frexp(k, &exponent);
267  SizeValueType value = static_cast< SizeValueType >( std::fabs(mantissa) );
268  value = ( 2 * value - 1 ) * ~0U;
269  return value;
270  }
271  };
272 
273  // We use a hash to associate the endpoints of each contour with the
274  // contour itself. This makes it easy to look up which contour we should add
275  // a new arc to.
276  // We can't store the contours themselves in the hashtable because we
277  // need to have two tables (one to hash from beginpoint -> contour and one
278  // for endpoint -> contour), and sometimes will remove a contour from the
279  // tables (if it has been closed or merged with another contour). So in the
280  // hash table we store a reference to the contour. Because sometimes we will
281  // need to merge contours, we need to be able to quickly remove contours
282  // from our list when they have been merged into another. Thus, we store
283  // an iterator pointing to the contour in the list.
284 
285  typedef itksys::hash_map< VertexType, ContourRef, VertexHash > VertexToContourMap;
286  typedef typename VertexToContourMap::iterator VertexMapIterator;
287  typedef typename VertexToContourMap::value_type VertexContourRefPair;
288 
289  // The contours we find in the image are stored here
291 
292  // And indexed by their beginning and ending points here
295 };
296 } // end namespace itk
297 
298 #ifndef ITK_MANUAL_INSTANTIATION
299 #include "itkContourExtractor2DImageFilter.hxx"
300 #endif
301 
302 #endif
Represent a path of line segments through ND Space.
Light weight base class for most itk classes.
SizeValueType float_hash(const CoordinateType &k) const
Base class for filters that take an image as input and produce an path as output. ...
ImageToPathFilter< InputImageType, OutputPathType > Superclass
unsigned long SizeValueType
Definition: itkIntTypes.h:143
NumericTraits< InputPixelType >::RealType InputRealType
SizeValueType operator()(const VertexType &k) const
A templated class holding a point in n-Dimensional image space.
VertexToContourMap::value_type VertexContourRefPair
Define a front-end to the STL &quot;vector&quot; container that conforms to the IndexedContainerInterface.
Control indentation during Print() invocation.
Definition: itkIndent.h:49
itksys::hash_map< VertexType, ContourRef, VertexHash > VertexToContourMap
Define additional traits for native types such as int or float.
Computes a list of PolyLineParametricPath objects from the contours in a 2D image.
#define itkConceptMacro(name, concept)