ITK  4.3.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 #include "vcl_deque.h"
26 #include "vcl_list.h"
27 
28 namespace itk
29 {
95 template< class TInputImage >
97  public ImageToPathFilter< TInputImage, PolyLineParametricPath< 2 > >
98 {
99 public:
101  itkStaticConstMacro(InputImageDimension, unsigned int,
102  TInputImage::ImageDimension);
103 
105  typedef TInputImage InputImageType;
107 
113 
115  itkNewMacro(Self);
116 
119 
121  typedef typename InputImageType::Pointer InputImagePointer;
122  typedef typename InputImageType::PixelType InputPixelType;
123  typedef typename InputImageType::IndexType InputIndexType;
124  typedef typename InputImageType::OffsetType InputOffsetType;
125  typedef typename InputImageType::RegionType InputRegionType;
129 
132 
133  typedef typename VertexListType::ConstPointer
137  itkSetMacro(ReverseContourOrientation, bool);
138  itkGetConstReferenceMacro(ReverseContourOrientation, bool);
139  itkBooleanMacro(ReverseContourOrientation);
141 
145  itkSetMacro(VertexConnectHighPixels, bool);
146  itkGetConstReferenceMacro(VertexConnectHighPixels, bool);
147  itkBooleanMacro(VertexConnectHighPixels);
149 
152  void SetRequestedRegion(const InputRegionType region);
153 
154  itkGetConstReferenceMacro(RequestedRegion, InputRegionType);
155  void ClearRequestedRegion();
156 
159  itkSetMacro(ContourValue, InputRealType);
160  itkGetConstReferenceMacro(ContourValue, InputRealType);
162 
163 #ifdef ITK_USE_CONCEPT_CHECKING
164 
165  itkConceptMacro( DimensionShouldBe2,
166  ( Concept::SameDimension< itkGetStaticConstMacro(InputImageDimension), 2 > ) );
167  itkConceptMacro( InputPixelTypeComparable,
169  itkConceptMacro( InputHasPixelTraitsCheck,
171  itkConceptMacro( InputHasNumericTraitsCheck,
173 
175 #endif
176 
177 protected:
178 
181  void PrintSelf(std::ostream & os, Indent indent) const;
182 
183  void GenerateData();
184 
188  virtual void GenerateInputRequestedRegion()
190 
191 private:
192  VertexType InterpolateContourPosition(InputPixelType fromValue,
193  InputPixelType toValue,
194  InputIndexType fromIndex,
195  InputOffsetType toOffset);
196 
197  void AddSegment(const VertexType from, const VertexType to);
198 
199  void FillOutputs();
200 
201  ContourExtractor2DImageFilter(const Self &); //purposely not implemented
202  void operator=(const Self &); //purposely not implemented
203 
204  InputRealType m_ContourValue;
205  bool m_ReverseContourOrientation;
206  bool m_VertexConnectHighPixels;
207  bool m_UseCustomRegion;
208  InputRegionType m_RequestedRegion;
209  unsigned int m_NumberOfContoursCreated;
210 
211  // Represent each contour as deque of vertices to facilitate addition of
212  // nodes at beginning or end. At the end of the processing, we will copy
213  // the contour into a PolyLineParametricPath.
214  // We subclass the deque to store an additional bit of information: an
215  // identification number for each growing contour. We use this number so
216  // that when it becomes necessary to merge two growing contours, we can
217  // merge the newer one into the older one. This helps because then we can
218  // guarantee that the output contour list is ordered from left to right,
219  // top to bottom (in terms of the first pixel of the contour encountered
220  // by the marching squares). Currently we make no guarantees that this
221  // pixel is the first pixel in the contour list, just that the contours
222  // are so ordered in the output. Ensuring this latter condition (first
223  // pixel traversed = first pixel in contour) would be possible by either
224  // changing the merging rules, which would make the contouring operation
225  //slower, or by storing additional data as to which pixel was first.
226  class ContourType:public vcl_deque< VertexType >
227  {
228 public:
229  unsigned int m_ContourNumber;
230  };
231 
232  // Store all the growing contours in a list. We may need to delete contours
233  // from anywhere in the sequence (when we merge them together), so we need to
234  // use a list instead of a vector or similar.
235  typedef vcl_list< ContourType > ContourContainer;
236  typedef typename ContourContainer::iterator ContourRef;
237 
238  // declare the hash function we are using for the hash_map.
239  struct VertexHash {
241  inline SizeValueType operator()(const VertexType & k) const
242  {
243  // Xor the hashes of the vertices together, after multiplying the
244  // first by some number, so that identical (x,y) vertex indices
245  // don't all hash to the same bucket. This is a decent if not
246  // optimal hash.
247  const SizeValueType hashVertex1 = this->float_hash(k[0] * 0xbeef);
248  const SizeValueType hashVertex2 = this->float_hash(k[1]);
249  const SizeValueType hashValue = hashVertex1 ^ hashVertex2;
250 
251  return hashValue;
252  }
253 
254  // Define hash function for floats. Based on method from
255  // http://www.brpreiss.com/books/opus4/html/page217.html
256  inline SizeValueType float_hash(const CoordinateType & k) const
257  {
258  if ( k == 0 )
259  {
260  return 0;
261  }
262  int exponent;
263  CoordinateType mantissa = vcl_frexp(k, &exponent);
264  SizeValueType value = static_cast< SizeValueType >( vcl_fabs(mantissa) );
265  value = ( 2 * value - 1 ) * ~0U;
266  return value;
267  }
268  };
269 
270  // We use a hash to associate the endpoints of each contour with the
271  // contour itself. This makes it easy to look up which contour we should add
272  // a new arc to.
273  // We can't store the contours themselves in the hashtable because we
274  // need to have two tables (one to hash from beginpoint -> contour and one
275  // for endpoint -> contour), and sometimes will remove a contour from the
276  // tables (if it has been closed or merged with another contour). So in the
277  // hash table we store a reference to the contour. Because sometimes we will
278  // need to merge contours, we need to be able to quickly remove contours
279  // from our list when they have been merged into another. Thus, we store
280  // an iterator pointing to the contour in the list.
281 
282  typedef itksys::hash_map< VertexType, ContourRef, VertexHash > VertexToContourMap;
283  typedef typename VertexToContourMap::iterator VertexMapIterator;
284  typedef typename VertexToContourMap::value_type VertexContourRefPair;
285 
286  // The contours we find in the image are stored here
288 
289  // And indexed by their beginning and ending points here
292 };
293 } // end namespace itk
294 
295 #ifndef ITK_MANUAL_INSTANTIATION
296 #include "itkContourExtractor2DImageFilter.hxx"
297 #endif
298 
299 #endif
300