00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018 #ifndef __itkConnectedComponentImageFilter_h
00019 #define __itkConnectedComponentImageFilter_h
00020
00021 #include "itkImageToImageFilter.h"
00022 #include "itkImage.h"
00023 #include "itkConceptChecking.h"
00024 #include <vector>
00025 #include <map>
00026 #include "itkProgressReporter.h"
00027 #include "itkBarrier.h"
00028
00029 namespace itk
00030 {
00031
00052 template <class TInputImage, class TOutputImage, class TMaskImage=TInputImage>
00053 class ITK_EXPORT ConnectedComponentImageFilter :
00054 public ImageToImageFilter< TInputImage, TOutputImage >
00055 {
00056 public:
00060 typedef ConnectedComponentImageFilter Self;
00061 typedef ImageToImageFilter< TInputImage, TOutputImage > Superclass;
00062
00066 typedef typename Superclass::InputImagePointer InputImagePointer;
00067
00072 typedef typename TOutputImage::PixelType OutputPixelType;
00073 typedef typename TOutputImage::InternalPixelType OutputInternalPixelType;
00074 typedef typename TInputImage::PixelType InputPixelType;
00075 typedef typename TInputImage::InternalPixelType InputInternalPixelType;
00076 typedef typename TMaskImage::PixelType MaskPixelType;
00077 itkStaticConstMacro(ImageDimension, unsigned int,
00078 TOutputImage::ImageDimension);
00079 itkStaticConstMacro(OutputImageDimension, unsigned int,
00080 TOutputImage::ImageDimension);
00081 itkStaticConstMacro(InputImageDimension, unsigned int,
00082 TInputImage::ImageDimension);
00084
00088 typedef TInputImage InputImageType;
00089 typedef TMaskImage MaskImageType;
00090 typedef typename TInputImage::IndexType IndexType;
00091 typedef typename TInputImage::SizeType SizeType;
00092 typedef typename TInputImage::OffsetType OffsetType;
00093
00094 typedef TOutputImage OutputImageType;
00095 typedef typename TOutputImage::RegionType RegionType;
00096 typedef typename TOutputImage::IndexType OutputIndexType;
00097 typedef typename TOutputImage::SizeType OutputSizeType;
00098 typedef typename TOutputImage::OffsetType OutputOffsetType;
00099 typedef typename TOutputImage::PixelType OutputImagePixelType;
00100
00101 typedef std::list<IndexType> ListType;
00102 typedef typename MaskImageType::Pointer MaskImagePointer;
00103
00107 typedef SmartPointer<Self> Pointer;
00108 typedef SmartPointer<const Self> ConstPointer;
00109
00113 itkTypeMacro(ConnectedComponentImageFilter, ImageToImageFilter);
00114
00118 itkNewMacro(Self);
00119
00126 itkSetMacro(FullyConnected, bool);
00127 itkGetConstReferenceMacro(FullyConnected, bool);
00128 itkBooleanMacro(FullyConnected);
00130
00131
00133 typedef unsigned long int LabelType;
00134
00135
00136 itkGetConstReferenceMacro(ObjectCount, LabelType);
00137
00138
00139 itkConceptMacro(SameDimension,
00140 (Concept::SameDimension<itkGetStaticConstMacro(InputImageDimension),
00141 itkGetStaticConstMacro(OutputImageDimension)>));
00142
00143
00144 void SetMaskImage(TMaskImage* mask)
00145 {
00146 this->SetNthInput(1, const_cast<TMaskImage *>( mask ));
00147 }
00148
00149 const TMaskImage* GetMaskImage() const
00150 {
00151 return (static_cast<const TMaskImage*>(this->ProcessObject::GetInput(1)));
00152 }
00153
00156 itkSetMacro(BackgroundValue, OutputImagePixelType);
00157 itkGetConstMacro(BackgroundValue, OutputImagePixelType);
00159
00160 protected:
00161 ConnectedComponentImageFilter()
00162 {
00163 m_FullyConnected = false;
00164 m_ObjectCount = 0;
00165 m_BackgroundValue = NumericTraits< OutputImagePixelType >::Zero;
00166 }
00167 virtual ~ConnectedComponentImageFilter() {}
00168 ConnectedComponentImageFilter(const Self&) {}
00169 void PrintSelf(std::ostream& os, Indent indent) const;
00170
00174 void BeforeThreadedGenerateData ();
00175 void AfterThreadedGenerateData ();
00176 void ThreadedGenerateData (const RegionType& outputRegionForThread, int threadId);
00178
00182 void GenerateInputRequestedRegion();
00183
00188 void EnlargeOutputRequestedRegion(DataObject *itkNotUsed(output));
00189
00190 bool m_FullyConnected;
00191
00192 private:
00193 LabelType m_ObjectCount;
00194 OutputImagePixelType m_BackgroundValue;
00195
00196
00197 typedef typename TOutputImage::RegionType::SizeType OutSizeType;
00198
00199
00200 class runLength
00201 {
00202 public:
00203
00204 long int length;
00205 typename InputImageType::IndexType where;
00206 LabelType label;
00207 };
00208
00209 typedef std::vector<runLength> lineEncoding;
00210
00211
00212 typedef std::vector<lineEncoding> LineMapType;
00213
00214 typedef std::vector<long> OffsetVec;
00215
00216
00217 typedef std::vector<LabelType> UnionFindType;
00218 UnionFindType m_UnionFind;
00219 UnionFindType m_Consecutive;
00220
00221
00222 void InitUnion(const unsigned long int size)
00223 {
00224 m_UnionFind = UnionFindType(size + 1);
00225 }
00226 void InsertSet(const unsigned long int label);
00227 unsigned long int LookupSet(const LabelType label);
00228 void LinkLabels(const LabelType lab1, const LabelType lab2);
00229 unsigned long int CreateConsecutive();
00231 bool CheckNeighbors(const OutputIndexType &A,
00232 const OutputIndexType &B);
00233
00234 void CompareLines(lineEncoding ¤t, const lineEncoding &Neighbour);
00235
00236 void FillOutput(const LineMapType &LineMap,
00237 ProgressReporter &progress);
00238
00239 void SetupLineOffsets(OffsetVec &LineOffsets);
00240
00241 void Wait()
00242 {
00243
00244 if( m_NumberOfLabels.size() > 1 )
00245 {
00246 m_Barrier->Wait();
00247 }
00248 }
00249
00250 typename std::vector< long > m_NumberOfLabels;
00251 typename std::vector< long > m_FirstLineIdToJoin;
00252 typename Barrier::Pointer m_Barrier;
00253 typename TInputImage::ConstPointer m_Input;
00254 #if !defined(CABLE_CONFIGURATION)
00255 LineMapType m_LineMap;
00256 #endif
00257 };
00258
00259 }
00260
00261 #ifndef ITK_MANUAL_INSTANTIATION
00262 #if !defined(CABLE_CONFIGURATION)
00263 #include "itkConnectedComponentImageFilter.txx"
00264 #endif
00265 #endif
00266
00267 #endif
00268