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