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

Generated at Sat Mar 8 2014 15:32:25 for Orfeo Toolbox with doxygen 1.8.3.1