ITK
4.1.0
Insight Segmentation and Registration Toolkit
|
00001 /*========================================================================= 00002 * 00003 * Copyright Insight Software Consortium 00004 * 00005 * Licensed under the Apache License, Version 2.0 (the "License"); 00006 * you may not use this file except in compliance with the License. 00007 * You may obtain a copy of the License at 00008 * 00009 * http://www.apache.org/licenses/LICENSE-2.0.txt 00010 * 00011 * Unless required by applicable law or agreed to in writing, software 00012 * distributed under the License is distributed on an "AS IS" BASIS, 00013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 00014 * See the License for the specific language governing permissions and 00015 * limitations under the License. 00016 * 00017 *=========================================================================*/ 00018 #ifndef __itkContourExtractor2DImageFilter_h 00019 #define __itkContourExtractor2DImageFilter_h 00020 00021 #include "itkImageToPathFilter.h" 00022 #include "itkPolyLineParametricPath.h" 00023 #include "itkConceptChecking.h" 00024 #include "itksys/hash_map.hxx" 00025 #include "vcl_deque.h" 00026 #include "vcl_list.h" 00027 00028 namespace itk 00029 { 00095 template< class TInputImage > 00096 class ITK_EXPORT ContourExtractor2DImageFilter: 00097 public ImageToPathFilter< TInputImage, PolyLineParametricPath< 2 > > 00098 { 00099 public: 00101 itkStaticConstMacro(InputImageDimension, unsigned int, 00102 TInputImage::ImageDimension); 00103 00105 typedef TInputImage InputImageType; 00106 typedef PolyLineParametricPath< 2 > OutputPathType; 00107 00109 typedef ContourExtractor2DImageFilter Self; 00110 typedef ImageToPathFilter< InputImageType, OutputPathType > Superclass; 00111 typedef SmartPointer< Self > Pointer; 00112 typedef SmartPointer< const Self > ConstPointer; 00113 00115 itkNewMacro(Self); 00116 00118 itkTypeMacro(ContourExtractor2DImageFilter, ImageToPathFilter); 00119 00121 typedef typename InputImageType::Pointer InputImagePointer; 00122 typedef typename InputImageType::PixelType InputPixelType; 00123 typedef typename InputImageType::IndexType InputIndexType; 00124 typedef typename InputImageType::OffsetType InputOffsetType; 00125 typedef typename InputImageType::RegionType InputRegionType; 00126 typedef typename OutputPathType::Pointer OutputPathPointer; 00127 typedef typename OutputPathType::VertexType VertexType; 00128 typedef typename OutputPathType::VertexListType VertexListType; 00129 00131 typedef typename NumericTraits< InputPixelType >::RealType InputRealType; 00132 00133 typedef typename VertexListType::ConstPointer 00134 VertexListConstPointer; 00137 itkSetMacro(ReverseContourOrientation, bool); 00138 itkGetConstReferenceMacro(ReverseContourOrientation, bool); 00139 itkBooleanMacro(ReverseContourOrientation); 00141 00145 itkSetMacro(VertexConnectHighPixels, bool); 00146 itkGetConstReferenceMacro(VertexConnectHighPixels, bool); 00147 itkBooleanMacro(VertexConnectHighPixels); 00149 00152 void SetRequestedRegion(const InputRegionType region); 00153 00154 itkGetConstReferenceMacro(RequestedRegion, InputRegionType); 00155 void ClearRequestedRegion(); 00156 00159 itkSetMacro(ContourValue, InputRealType); 00160 itkGetConstReferenceMacro(ContourValue, InputRealType); 00162 00163 #ifdef ITK_USE_CONCEPT_CHECKING 00164 00165 itkConceptMacro( DimensionShouldBe2, 00166 ( Concept::SameDimension< itkGetStaticConstMacro(InputImageDimension), 2 > ) ); 00167 itkConceptMacro( InputPixelTypeComparable, 00168 ( Concept::Comparable< InputPixelType > ) ); 00169 itkConceptMacro( InputHasPixelTraitsCheck, 00170 ( Concept::HasPixelTraits< InputPixelType > ) ); 00171 itkConceptMacro( InputHasNumericTraitsCheck, 00172 ( Concept::HasNumericTraits< InputPixelType > ) ); 00173 00175 #endif 00176 protected: 00177 00178 ContourExtractor2DImageFilter(); 00179 virtual ~ContourExtractor2DImageFilter(); 00180 void PrintSelf(std::ostream & os, Indent indent) const; 00181 00182 void GenerateData(); 00183 00187 virtual void GenerateInputRequestedRegion() 00188 throw( InvalidRequestedRegionError ); 00189 00190 private: 00191 VertexType InterpolateContourPosition(InputPixelType fromValue, 00192 InputPixelType toValue, 00193 InputIndexType fromIndex, 00194 InputOffsetType toOffset); 00195 00196 void AddSegment(const VertexType from, const VertexType to); 00197 00198 void FillOutputs(); 00199 00200 ContourExtractor2DImageFilter(const Self &); //purposely not implemented 00201 void operator=(const Self &); //purposely not implemented 00202 00203 InputRealType m_ContourValue; 00204 bool m_ReverseContourOrientation; 00205 bool m_VertexConnectHighPixels; 00206 bool m_UseCustomRegion; 00207 InputRegionType m_RequestedRegion; 00208 unsigned int m_NumberOfContoursCreated; 00209 00210 // Represent each contour as deque of vertices to facilitate addition of 00211 // nodes at beginning or end. At the end of the processing, we will copy 00212 // the contour into a PolyLineParametricPath. 00213 // We subclass the deque to store an additional bit of information: an 00214 // identification number for each growing contour. We use this number so 00215 // that when it becomes necessary to merge two growing contours, we can 00216 // merge the newer one into the older one. This helps because then we can 00217 // guarantee that the output contour list is ordered from left to right, 00218 // top to bottom (in terms of the first pixel of the contour encountered 00219 // by the marching squares). Currently we make no guarantees that this 00220 // pixel is the first pixel in the contour list, just that the contours 00221 // are so ordered in the output. Ensuring this latter condition (first 00222 // pixel traversed = first pixel in contour) would be possible by either 00223 // changing the merging rules, which would make the contouring operation 00224 //slower, or by storing additional data as to which pixel was first. 00225 class ContourType:public vcl_deque< VertexType > 00226 { 00227 public: 00228 unsigned int m_ContourNumber; 00229 }; 00230 00231 // Store all the growing contours in a list. We may need to delete contours 00232 // from anywhere in the sequence (when we merge them together), so we need to 00233 // use a list instead of a vector or similar. 00234 typedef vcl_list< ContourType > ContourContainer; 00235 typedef typename ContourContainer::iterator ContourRef; 00236 00237 // declare the hash function we are using for the hash_map. 00238 struct VertexHash { 00239 typedef typename VertexType::CoordRepType CoordinateType; 00240 inline SizeValueType operator()(const VertexType & k) const 00241 { 00242 // Xor the hashes of the vertices together, after multiplying the 00243 // first by some number, so that identical (x,y) vertex indices 00244 // don't all hash to the same bucket. This is a decent if not 00245 // optimal hash. 00246 const SizeValueType hashVertex1 = this->float_hash(k[0] * 0xbeef); 00247 const SizeValueType hashVertex2 = this->float_hash(k[1]); 00248 const SizeValueType hashValue = hashVertex1 ^ hashVertex2; 00249 00250 return hashValue; 00251 } 00252 00253 // Define hash function for floats. Based on method from 00254 // http://www.brpreiss.com/books/opus4/html/page217.html 00255 inline SizeValueType float_hash(const CoordinateType & k) const 00256 { 00257 if ( k == 0 ) 00258 { 00259 return 0; 00260 } 00261 int exponent; 00262 CoordinateType mantissa = vcl_frexp(k, &exponent); 00263 SizeValueType value = static_cast< SizeValueType >( vcl_fabs(mantissa) ); 00264 value = ( 2 * value - 1 ) * ~0U; 00265 return value; 00266 } 00267 }; 00268 00269 // We use a hash to associate the endpoints of each contour with the 00270 // contour itself. This makes it easy to look up which contour we should add 00271 // a new arc to. 00272 // We can't store the contours themselves in the hashtable because we 00273 // need to have two tables (one to hash from beginpoint -> contour and one 00274 // for endpoint -> contour), and sometimes will remove a contour from the 00275 // tables (if it has been closed or merged with another contour). So in the 00276 // hash table we store a reference to the contour. Because sometimes we will 00277 // need to merge contours, we need to be able to quickly remove contours 00278 // from our list when they have been merged into another. Thus, we store 00279 // an iterator pointing to the contour in the list. 00280 00281 typedef itksys::hash_map< VertexType, ContourRef, VertexHash > VertexToContourMap; 00282 typedef typename VertexToContourMap::iterator VertexMapIterator; 00283 typedef typename VertexToContourMap::value_type VertexContourRefPair; 00284 00285 // The contours we find in the image are stored here 00286 ContourContainer m_Contours; 00287 00288 // And indexed by their beginning and ending points here 00289 VertexToContourMap m_ContourStarts; 00290 VertexToContourMap m_ContourEnds; 00291 }; 00292 } // end namespace itk 00293 00294 #ifndef ITK_MANUAL_INSTANTIATION 00295 #include "itkContourExtractor2DImageFilter.hxx" 00296 #endif 00297 00298 #endif 00299