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