ITK  4.6.0
Insight Segmentation and Registration Toolkit
itkShapeUniqueLabelMapFilter.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 __itkShapeUniqueLabelMapFilter_h
19 #define __itkShapeUniqueLabelMapFilter_h
20 
23 #include "itkProgressReporter.h"
24 #include <queue>
25 
26 namespace itk
27 {
41 template< typename TImage >
43  public InPlaceLabelMapFilter< TImage >
44 {
45 public:
51 
53  typedef TImage ImageType;
54  typedef typename ImageType::Pointer ImagePointer;
55  typedef typename ImageType::ConstPointer ImageConstPointer;
56  typedef typename ImageType::PixelType PixelType;
57  typedef typename ImageType::IndexType IndexType;
58  typedef typename ImageType::LabelObjectType LabelObjectType;
59  typedef typename LabelObjectType::LineType LineType;
60 
61  typedef typename LabelObjectType::AttributeType AttributeType;
62 
64  itkStaticConstMacro(ImageDimension, unsigned int,
65  TImage::ImageDimension);
66 
68  itkNewMacro(Self);
69 
71  itkTypeMacro(ShapeUniqueLabelMapFilter,
73 
74 #ifdef ITK_USE_CONCEPT_CHECKING
75  // Begin concept checking
76 /* itkConceptMacro(InputEqualityComparableCheck,
77  (Concept::EqualityComparable<InputImagePixelType>));
78  itkConceptMacro(IntConvertibleToInputCheck,
79  (Concept::Convertible<int, InputImagePixelType>));
80  itkConceptMacro(InputOStreamWritableCheck,
81  (Concept::OStreamWritable<InputImagePixelType>));*/
82 // End concept checking
83 #endif
84 
91  itkGetConstMacro(ReverseOrdering, bool);
92  itkSetMacro(ReverseOrdering, bool);
93  itkBooleanMacro(ReverseOrdering);
95 
100  itkGetConstMacro(Attribute, AttributeType);
101  itkSetMacro(Attribute, AttributeType);
102  void SetAttribute(const std::string & s)
103  {
104  this->SetAttribute( LabelObjectType::GetAttributeFromName(s) );
105  }
107 
108 protected:
111 
112  void GenerateData();
113 
114  template< typename TAttributeAccessor >
115  void TemplatedGenerateData(const TAttributeAccessor & accessor)
116  {
117  // Allocate the output
118  this->AllocateOutputs();
119 
120  // the priority queue to store all the lines of all the objects sorted
121  typedef typename std::priority_queue< LineOfLabelObject, std::vector< LineOfLabelObject >,
122  LineOfLabelObjectComparator > PriorityQueueType;
123  PriorityQueueType pq;
124 
125  ProgressReporter progress(this, 0, 1);
126  // TODO: really report the progress
127 
128  for ( typename ImageType::Iterator it2( this->GetLabelMap() );
129  ! it2.IsAtEnd();
130  ++it2 )
131  {
132  LabelObjectType *lo = it2.GetLabelObject();
133 
134  // may reduce the number of lines to proceed
135  lo->Optimize();
136 
137  typename LabelObjectType::ConstLineIterator lit( lo );
138  while( ! lit.IsAtEnd() )
139  {
140  pq.push( LineOfLabelObject(lit.GetLine(), lo) );
141  ++lit;
142  }
143 
144  // clear the lines to readd them later
145  lo->Clear();
146 
147  // go to the next label
148  // progress.CompletedPixel();
149  }
150 
151  if ( pq.empty() )
152  {
153  // nothing to do
154  return;
155  }
156 
157  typedef typename std::deque< LineOfLabelObject > LinesType;
158  LinesType lines;
159 
160  lines.push_back( pq.top() );
161  LineOfLabelObject prev = lines.back();
162  IndexType prevIdx = prev.line.GetIndex();
163  pq.pop();
164 
165  while ( !pq.empty() )
166  {
167  LineOfLabelObject l = pq.top();
168  IndexType idx = l.line.GetIndex();
169  pq.pop();
170 
171  bool newMainLine = false;
172  // don't check dim 0!
173  for ( unsigned int i = 1; i < ImageDimension; i++ )
174  {
175  if ( idx[i] != prevIdx[i] )
176  {
177  newMainLine = true;
178  }
179  }
180 
181  if ( newMainLine )
182  {
183  // just push the line
184  lines.push_back(l);
185  }
186  else
187  {
188  OffsetValueType prevLength = prev.line.GetLength();
189  OffsetValueType length = l.line.GetLength();
190 
191  if ( prevIdx[0] + prevLength >= idx[0] )
192  {
193  // the lines are overlapping. We need to choose which line to keep.
194  // the label, the only "attribute" to be guaranteed to be unique, is
195  // used to choose
196  // which line to keep. This is necessary to avoid the case where a
197  // part of a label is over
198  // a second label, and below in another part of the image.
199  bool keepCurrent;
200  typename TAttributeAccessor::AttributeValueType prevAttr = accessor(prev.labelObject);
201  typename TAttributeAccessor::AttributeValueType attr = accessor(l.labelObject);
202  // this may be changed to a single boolean expression, but may become
203  // quite difficult to read
204  if ( attr == prevAttr )
205  {
206  if ( l.labelObject->GetLabel() > prev.labelObject->GetLabel() )
207  {
208  keepCurrent = !m_ReverseOrdering;
209  }
210  else
211  {
212  keepCurrent = m_ReverseOrdering;
213  }
214  }
215  else
216  {
217  if ( attr > prevAttr )
218  {
219  keepCurrent = !m_ReverseOrdering;
220  }
221  else
222  {
223  keepCurrent = m_ReverseOrdering;
224  }
225  }
226 
227  if ( keepCurrent )
228  {
229  // keep the current one. We must truncate the previous one to remove
230  // the
231  // overlap, and take care of the end of the previous line if it
232  // extends
233  // after the current one.
234  if ( prevIdx[0] + prevLength > idx[0] + length )
235  {
236  // the previous line is longer than the current one. Lets take its
237  // tail and
238  // add it to the priority queue
239  IndexType newIdx = idx;
240  newIdx[0] = idx[0] + length;
241  OffsetValueType newLength = prevIdx[0] + prevLength - newIdx[0];
242  pq.push( LineOfLabelObject(LineType(newIdx, newLength), prev.labelObject) );
243  }
244  // truncate the previous line to let some place for the current one
245  prevLength = idx[0] - prevIdx[0];
246  if ( prevLength != 0 )
247  {
248  lines.back(). line.SetLength(idx[0] - prevIdx[0]);
249  }
250  else
251  {
252  // length is 0 - no need to keep that line
253  lines.pop_back();
254  }
255  // and push the current one
256  lines.push_back(l);
257  }
258  else
259  {
260  // keep the previous one. If the previous line fully overlap the
261  // current one,
262  // the current one is fully discarded.
263  if ( prevIdx[0] + prevLength > idx[0] + length )
264  {
265  // discarding the current line - just do nothing
266  }
267  else
268  {
269  IndexType newIdx = idx;
270  newIdx[0] = prevIdx[0] + prevLength;
271  OffsetValueType newLength = idx[0] + length - newIdx[0];
272  l.line.SetIndex(newIdx);
273  l.line.SetLength(newLength);
274  lines.push_back(l);
275  }
276  }
277  }
278  else
279  {
280  // no overlap - things are just fine already
281  lines.push_back(l);
282  }
283  }
284 
285  // store the current line as the previous one, and go to the next one.
286  prev = lines.back();
287  prevIdx = prev.line.GetIndex();
288  }
289 
290  // put the lines in their object
291  for ( unsigned int i = 0; i < lines.size(); i++ )
292  {
293  LineOfLabelObject & l = lines[i];
294  l.labelObject->AddLine(l.line);
295  }
296 
297  // remove objects without lines
298  typename ImageType::Iterator it( this->GetLabelMap() );
299  while ( ! it.IsAtEnd() )
300  {
301  typename LabelObjectType::LabelType label = it.GetLabel();
302  LabelObjectType *labelObject = it.GetLabelObject();
303 
304  if ( labelObject->Empty() )
305  {
306  // must increment the iterator before removing the object to avoid
307  // invalidating the iterator
308  ++it;
309  this->GetLabelMap()->RemoveLabel(label);
310  }
311  else
312  {
313  ++it;
314  }
315  }
316  }
317 
318  void PrintSelf(std::ostream & os, Indent indent) const;
319 
321 
322 private:
323  ShapeUniqueLabelMapFilter(const Self &); //purposely not implemented
324  void operator=(const Self &); //purposely not implemented
325 
328  typedef typename LabelObjectType::LineType LineType;
330  {
331  this->line = _line;
332  this->labelObject = _lo;
333  }
334 
337  };
338 
340  {
341 public:
342  bool operator()(const LineOfLabelObject & lla, const LineOfLabelObject & llb)
343  {
344  for ( int i = ImageDimension - 1; i >= 0; i-- )
345  {
346  if ( lla.line.GetIndex()[i] > llb.line.GetIndex()[i] )
347  {
348  return true;
349  }
350  else if ( lla.line.GetIndex()[i] < llb.line.GetIndex()[i] )
351  {
352  return false;
353  }
354  }
355  return false;
356  }
357  };
358 }; // end of class
359 } // end namespace itk
360 
361 #ifndef ITK_MANUAL_INSTANTIATION
362 #include "itkShapeUniqueLabelMapFilter.hxx"
363 #endif
364 
365 #endif
bool operator()(const LineOfLabelObject &lla, const LineOfLabelObject &llb)
Light weight base class for most itk classes.
signed long OffsetValueType
Definition: itkIntTypes.h:154
virtual void SetAttribute(AttributeType _arg)
void PrintSelf(std::ostream &os, Indent indent) const
ImageType::LabelObjectType LabelObjectType
Base class for filters that takes an image as input and overwrites that image as the output...
Remove some pixels in the label object according to the value of their shape attribute to ensure that...
Implements progress tracking for a filter.
LabelObjectType::AttributeType AttributeType
void operator=(const Self &)
void TemplatedGenerateData(const TAttributeAccessor &accessor)
LineOfLabelObject(const LineType _line, LabelObjectType *_lo)
Control indentation during Print() invocation.
Definition: itkIndent.h:49
InPlaceLabelMapFilter< TImage > Superclass