ITK  4.3.0
Insight Segmentation and Registration Toolkit
itkConnectedComponentImageFilter.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 __itkConnectedComponentImageFilter_h
19 #define __itkConnectedComponentImageFilter_h
20 
21 #include "itkImageToImageFilter.h"
22 #include "itkImage.h"
23 #include <vector>
24 #include <map>
25 #include "itkProgressReporter.h"
26 #include "itkBarrier.h"
27 
28 namespace itk
29 {
54 template< class TInputImage, class TOutputImage, class TMaskImage = TInputImage >
56  public ImageToImageFilter< TInputImage, TOutputImage >
57 {
58 public:
64 
68  typedef typename Superclass::InputImagePointer InputImagePointer;
69 
74  typedef typename TOutputImage::PixelType OutputPixelType;
75  typedef typename TOutputImage::InternalPixelType OutputInternalPixelType;
76  typedef typename TInputImage::PixelType InputPixelType;
77  typedef typename TInputImage::InternalPixelType InputInternalPixelType;
78  typedef typename TMaskImage::PixelType MaskPixelType;
79  itkStaticConstMacro(ImageDimension, unsigned int,
80  TOutputImage::ImageDimension);
81  itkStaticConstMacro(OutputImageDimension, unsigned int,
82  TOutputImage::ImageDimension);
83  itkStaticConstMacro(InputImageDimension, unsigned int,
84  TInputImage::ImageDimension);
86 
90  typedef TInputImage InputImageType;
91  typedef TMaskImage MaskImageType;
92  typedef typename TInputImage::IndexType IndexType;
93  typedef typename TInputImage::SizeType SizeType;
94  typedef typename TInputImage::OffsetType OffsetType;
95 
96  typedef TOutputImage OutputImageType;
97  typedef typename TOutputImage::RegionType RegionType;
98  typedef typename TOutputImage::IndexType OutputIndexType;
99  typedef typename TOutputImage::SizeType OutputSizeType;
100  typedef typename TOutputImage::OffsetType OutputOffsetType;
101  typedef typename TOutputImage::PixelType OutputImagePixelType;
102 
103  typedef std::list< IndexType > ListType;
104  typedef typename MaskImageType::Pointer MaskImagePointer;
105 
111 
116 
120  itkNewMacro(Self);
121 
128  itkSetMacro(FullyConnected, bool);
129  itkGetConstReferenceMacro(FullyConnected, bool);
130  itkBooleanMacro(FullyConnected);
132 
134  typedef IdentifierType LabelType;
135 
136  // only set after completion
137  itkGetConstReferenceMacro(ObjectCount, LabelType);
138 
139  // Concept checking -- input and output dimensions must be the same
140  itkConceptMacro( SameDimension,
141  ( Concept::SameDimension< itkGetStaticConstMacro(InputImageDimension),
142  itkGetStaticConstMacro(OutputImageDimension) > ) );
143  itkConceptMacro( OutputImagePixelTypeIsInteger, ( Concept::IsInteger< OutputImagePixelType > ) );
144 
145  void SetMaskImage(TMaskImage *mask)
146  {
147  this->SetNthInput( 1, const_cast< TMaskImage * >( mask ) );
148  }
149 
150  const TMaskImage * GetMaskImage() const
151  {
152  return ( static_cast< const TMaskImage * >( this->ProcessObject::GetInput(1) ) );
153  }
154 
157  itkSetMacro(BackgroundValue, OutputImagePixelType);
158  itkGetConstMacro(BackgroundValue, OutputImagePixelType);
160 
161 protected:
163  {
164  m_FullyConnected = false;
165  m_ObjectCount = 0;
167  }
168 
170  void PrintSelf(std::ostream & os, Indent indent) const;
171 
175  void BeforeThreadedGenerateData();
176 
177  void AfterThreadedGenerateData();
178 
179  void ThreadedGenerateData(const RegionType & outputRegionForThread, ThreadIdType threadId);
180 
184  void GenerateInputRequestedRegion();
185 
190  void EnlargeOutputRequestedRegion( DataObject * itkNotUsed(output) );
191 
193 
194 private:
195  ConnectedComponentImageFilter(const Self &); //purposely not implemented
196  void operator=(const Self &); //purposely not implemented
197 
200 
201  // some additional types
202  typedef typename TOutputImage::RegionType::SizeType OutSizeType;
203 
204  // types to support the run length encoding of lines
205  class runLength
206  {
207 public:
208  // run length information - may be a more type safe way of doing this
210  typename TInputImage::IndexType where; // Index of the start of the run
211  LabelType label; // the initial label of the run
212  };
213 
214  typedef std::vector< runLength > lineEncoding;
215 
216  // the map storing lines
217  typedef std::vector< lineEncoding > LineMapType;
218 
219  typedef std::vector< typename TInputImage::OffsetValueType > OffsetVec;
220 
221  // the types to support union-find operations
222  typedef std::vector< LabelType > UnionFindType;
225 
226  // functions to support union-find operations
227  void InitUnion( SizeValueType size )
228  {
229  m_UnionFind = UnionFindType(size + 1);
230  }
231 
232  void InsertSet(const LabelType label);
233 
234  SizeValueType LookupSet(const LabelType label);
235 
236  void LinkLabels(const LabelType lab1, const LabelType lab2);
237 
238  SizeValueType CreateConsecutive();
239 
241  bool CheckNeighbors(const OutputIndexType & A,
242  const OutputIndexType & B);
243 
244  void CompareLines(lineEncoding & current, const lineEncoding & Neighbour);
245 
246  void FillOutput(const LineMapType & LineMap,
247  ProgressReporter & progress);
248 
249  void SetupLineOffsets(OffsetVec & LineOffsets);
250 
251  void Wait()
252  {
253  // use m_NumberOfLabels.size() to get the number of thread used
254  if ( m_NumberOfLabels.size() > 1 )
255  {
256  m_Barrier->Wait();
257  }
258  }
259 
260  typename std::vector< IdentifierType > m_NumberOfLabels;
261  typename std::vector< IdentifierType > m_FirstLineIdToJoin;
262 
264 
265  typename TInputImage::ConstPointer m_Input;
266 #if !defined( CABLE_CONFIGURATION )
268 #endif
269 };
270 } // end namespace itk
271 
272 #ifndef ITK_MANUAL_INSTANTIATION
273 #if !defined( CABLE_CONFIGURATION )
274 #include "itkConnectedComponentImageFilter.hxx"
275 #endif
276 #endif
277 
278 #endif
279