ITK  4.2.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 <queue>
24 
25 namespace itk
26 {
40 template< class TImage >
41 class ITK_EXPORT ShapeUniqueLabelMapFilter:
42  public InPlaceLabelMapFilter< TImage >
43 {
44 public:
50 
52  typedef TImage ImageType;
53  typedef typename ImageType::Pointer ImagePointer;
54  typedef typename ImageType::ConstPointer ImageConstPointer;
55  typedef typename ImageType::PixelType PixelType;
56  typedef typename ImageType::IndexType IndexType;
57  typedef typename ImageType::LabelObjectType LabelObjectType;
58  typedef typename LabelObjectType::LineType LineType;
59 
60  typedef typename LabelObjectType::AttributeType AttributeType;
61 
63  itkStaticConstMacro(ImageDimension, unsigned int,
64  TImage::ImageDimension);
65 
67  itkNewMacro(Self);
68 
70  itkTypeMacro(ShapeUniqueLabelMapFilter,
72 
73 #ifdef ITK_USE_CONCEPT_CHECKING
74 
75 /* itkConceptMacro(InputEqualityComparableCheck,
76  (Concept::EqualityComparable<InputImagePixelType>));
77  itkConceptMacro(IntConvertibleToInputCheck,
78  (Concept::Convertible<int, InputImagePixelType>));
79  itkConceptMacro(InputOStreamWritableCheck,
80  (Concept::OStreamWritable<InputImagePixelType>));*/
81 
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< class 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 private:
322  ShapeUniqueLabelMapFilter(const Self &); //purposely not implemented
323  void operator=(const Self &); //purposely not implemented
324 
327  typedef typename LabelObjectType::LineType LineType;
329  {
330  this->line = _line;
331  this->labelObject = _lo;
332  }
333 
336  };
337 
339  {
340 public:
341  bool operator()(const LineOfLabelObject & lla, const LineOfLabelObject & llb)
342  {
343  for ( int i = ImageDimension - 1; i >= 0; i-- )
344  {
345  if ( lla.line.GetIndex()[i] > llb.line.GetIndex()[i] )
346  {
347  return true;
348  }
349  else if ( lla.line.GetIndex()[i] < llb.line.GetIndex()[i] )
350  {
351  return false;
352  }
353  }
354  return false;
355  }
356  };
357 }; // end of class
358 } // end namespace itk
359 
360 #ifndef ITK_MANUAL_INSTANTIATION
361 #include "itkShapeUniqueLabelMapFilter.hxx"
362 #endif
363 
364 #endif
365