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 {
43 template <typename TImage>
44 class ITK_TEMPLATE_EXPORT ShapeUniqueLabelMapFilter : public InPlaceLabelMapFilter<TImage>
45 {
46 public:
47  ITK_DISALLOW_COPY_AND_MOVE(ShapeUniqueLabelMapFilter);
48 
54 
56  using ImageType = TImage;
57  using ImagePointer = typename ImageType::Pointer;
58  using ImageConstPointer = typename ImageType::ConstPointer;
59  using PixelType = typename ImageType::PixelType;
60  using IndexType = typename ImageType::IndexType;
61  using LabelObjectType = typename ImageType::LabelObjectType;
62  using LineType = typename LabelObjectType::LineType;
63 
64  using AttributeType = typename LabelObjectType::AttributeType;
65 
67  static constexpr unsigned int ImageDimension = TImage::ImageDimension;
68 
70  itkNewMacro(Self);
71 
74 
75 #ifdef ITK_USE_CONCEPT_CHECKING
76  // Begin concept checking
77 /* itkConceptMacro(InputEqualityComparableCheck,
78  (Concept::EqualityComparable<InputImagePixelType>));
79  itkConceptMacro(IntConvertibleToInputCheck,
80  (Concept::Convertible<int, InputImagePixelType>));
81  itkConceptMacro(InputOStreamWritableCheck,
82  (Concept::OStreamWritable<InputImagePixelType>));*/
83 // End concept checking
84 #endif
85 
91  itkGetConstMacro(ReverseOrdering, bool);
92  itkSetMacro(ReverseOrdering, bool);
93  itkBooleanMacro(ReverseOrdering);
95 
100  itkGetConstMacro(Attribute, AttributeType);
101  itkSetMacro(Attribute, AttributeType);
102  void
103  SetAttribute(const std::string & s)
104  {
105  this->SetAttribute(LabelObjectType::GetAttributeFromName(s));
106  }
108 
109 protected:
111  ~ShapeUniqueLabelMapFilter() override = default;
112 
113  void
114  GenerateData() override;
115 
116  template <typename TAttributeAccessor>
117  void
118  TemplatedGenerateData(const TAttributeAccessor & accessor)
119  {
120  // Allocate the output
121  this->AllocateOutputs();
122 
123  // the priority queue to store all the lines of all the objects sorted
124  using PriorityQueueType =
125  typename std::priority_queue<LineOfLabelObject, std::vector<LineOfLabelObject>, LineOfLabelObjectComparator>;
126  PriorityQueueType priorityQueue;
127 
128  ProgressReporter progress(this, 0, 1);
129  // TODO: really report the progress
130 
131  for (typename ImageType::Iterator it(this->GetLabelMap()); !it.IsAtEnd(); ++it)
132  {
133  LabelObjectType * labelObject = it.GetLabelObject();
134 
135  // may reduce the number of lines to proceed
136  labelObject->Optimize();
137 
138  typename LabelObjectType::ConstLineIterator lit(labelObject);
139  while (!lit.IsAtEnd())
140  {
141  priorityQueue.push(LineOfLabelObject(lit.GetLine(), labelObject));
142  ++lit;
143  }
144 
145  // clear the lines to read them later
146  labelObject->Clear();
147 
148  // go to the next label
149  // progress.CompletedPixel();
150  }
151 
152  if (priorityQueue.empty())
153  {
154  // nothing to do
155  return;
156  }
157 
158  using LinesType = typename std::deque<LineOfLabelObject>;
159  LinesType lines;
160 
161  lines.push_back(priorityQueue.top());
162  LineOfLabelObject prev = lines.back();
163  IndexType prevIdx = prev.line.GetIndex();
164  priorityQueue.pop();
165 
166  while (!priorityQueue.empty())
167  {
168  LineOfLabelObject l = priorityQueue.top();
169  IndexType idx = l.line.GetIndex();
170  priorityQueue.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 (Math::ExactlyEquals(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  priorityQueue.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 (size_t 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
320  PrintSelf(std::ostream & os, Indent indent) const override;
321 
323 
324 private:
327  {
328  using LineType = typename LabelObjectType::LineType;
330  {
331  this->line = _line;
332  this->labelObject = _lo;
333  }
334 
337  };
338 
340  {
341  public:
342  bool
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
itk::ShapeUniqueLabelMapFilter::SetAttribute
void SetAttribute(const std::string &s)
Definition: itkShapeUniqueLabelMapFilter.h:103
itk::ShapeUniqueLabelMapFilter::LineOfLabelObject::line
LineType line
Definition: itkShapeUniqueLabelMapFilter.h:335
itk::ShapeUniqueLabelMapFilter::LabelObjectType
typename ImageType::LabelObjectType LabelObjectType
Definition: itkShapeUniqueLabelMapFilter.h:61
itk::ShapeUniqueLabelMapFilter::LineOfLabelObjectComparator::operator()
bool operator()(const LineOfLabelObject &lla, const LineOfLabelObject &llb)
Definition: itkShapeUniqueLabelMapFilter.h:343
itk::InPlaceLabelMapFilter
Base class for filters that takes an image as input and overwrites that image as the output.
Definition: itkInPlaceLabelMapFilter.h:83
itk::ShapeUniqueLabelMapFilter::LineOfLabelObjectComparator
Definition: itkShapeUniqueLabelMapFilter.h:339
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:336
itk::SmartPointer< Self >
itk::Indent
Control indentation during Print() invocation.
Definition: itkIndent.h:49
itk::ShapeUniqueLabelMapFilter::AttributeType
typename LabelObjectType::AttributeType AttributeType
Definition: itkShapeUniqueLabelMapFilter.h:64
itk::ShapeUniqueLabelMapFilter
Remove some pixels in the label object according to the value of their shape attribute to ensure that...
Definition: itkShapeUniqueLabelMapFilter.h:44
itkShapeLabelObjectAccessors.h
itk::GTest::TypedefsAndConstructors::Dimension2::IndexType
ImageBaseType::IndexType IndexType
Definition: itkGTestTypedefsAndConstructors.h:50
itk::ShapeUniqueLabelMapFilter::IndexType
typename ImageType::IndexType IndexType
Definition: itkShapeUniqueLabelMapFilter.h:60
itk::LightObject
Light weight base class for most itk classes.
Definition: itkLightObject.h:59
itk::ShapeUniqueLabelMapFilter::LineType
typename LabelObjectType::LineType LineType
Definition: itkShapeUniqueLabelMapFilter.h:62
itk::ShapeUniqueLabelMapFilter::LineOfLabelObject::LineOfLabelObject
LineOfLabelObject(const LineType _line, LabelObjectType *_lo)
Definition: itkShapeUniqueLabelMapFilter.h:329
itk::ShapeUniqueLabelMapFilter::PixelType
typename ImageType::PixelType PixelType
Definition: itkShapeUniqueLabelMapFilter.h:59
itkInPlaceLabelMapFilter.h
itk::ShapeUniqueLabelMapFilter::ImageConstPointer
typename ImageType::ConstPointer ImageConstPointer
Definition: itkShapeUniqueLabelMapFilter.h:58
itk::ShapeUniqueLabelMapFilter::ImageType
TImage ImageType
Definition: itkShapeUniqueLabelMapFilter.h:56
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:322
itk::OffsetValueType
signed long OffsetValueType
Definition: itkIntTypes.h:94
itk::ShapeUniqueLabelMapFilter::TemplatedGenerateData
void TemplatedGenerateData(const TAttributeAccessor &accessor)
Definition: itkShapeUniqueLabelMapFilter.h:118
itk::ShapeUniqueLabelMapFilter::m_ReverseOrdering
bool m_ReverseOrdering
Definition: itkShapeUniqueLabelMapFilter.h:325
itk::ProgressReporter
Implements progress tracking for a filter.
Definition: itkProgressReporter.h:60
itk::ShapeUniqueLabelMapFilter::LineOfLabelObject
Definition: itkShapeUniqueLabelMapFilter.h:326
itk::ShapeUniqueLabelMapFilter::ImagePointer
typename ImageType::Pointer ImagePointer
Definition: itkShapeUniqueLabelMapFilter.h:57
itkMath.h
itk::ShapeUniqueLabelMapFilter::LineOfLabelObject::LineType
typename LabelObjectType::LineType LineType
Definition: itkShapeUniqueLabelMapFilter.h:328