ITK  6.0.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 * https://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
27namespace itk
28{
43template <typename TImage>
44class ITK_TEMPLATE_EXPORT ShapeUniqueLabelMapFilter : public InPlaceLabelMapFilter<TImage>
45{
46public:
47 ITK_DISALLOW_COPY_AND_MOVE(ShapeUniqueLabelMapFilter);
48
54
56 using ImageType = TImage;
59 using PixelType = typename ImageType::PixelType;
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
73 itkOverrideGetNameOfClassMacro(ShapeUniqueLabelMapFilter);
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);
100 itkGetConstMacro(Attribute, AttributeType);
101 itkSetMacro(Attribute, AttributeType);
102 void
103 SetAttribute(const std::string & s)
104 {
105 this->SetAttribute(LabelObjectType::GetAttributeFromName(s));
106 }
109protected:
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 assert(newMainLine || (idx[0] >= prevIdx[0]));
183
184 if (newMainLine)
185 {
186 // just push the line
187 lines.push_back(l);
188 }
189 else
190 {
191 OffsetValueType prevLength = prev.line.GetLength();
192 OffsetValueType length = l.line.GetLength();
193
194 if (prevIdx[0] + prevLength > idx[0])
195 {
196 // the lines are overlapping. We need to choose which line to keep.
197 // the label, the only "attribute" to be guaranteed to be unique, is
198 // used to choose
199 // which line to keep. This is necessary to avoid the case where a
200 // part of a label is over
201 // a second label, and below in another part of the image.
202 bool keepCurrent;
203 typename TAttributeAccessor::AttributeValueType prevAttr = accessor(prev.labelObject);
204 typename TAttributeAccessor::AttributeValueType attr = accessor(l.labelObject);
205 // this may be changed to a single boolean expression, but may become
206 // quite difficult to read
207 if (Math::ExactlyEquals(attr, prevAttr))
208 {
209 if (l.labelObject->GetLabel() > prev.labelObject->GetLabel())
210 {
211 keepCurrent = !m_ReverseOrdering;
212 }
213 else
214 {
215 keepCurrent = m_ReverseOrdering;
216 }
217 }
218 else
219 {
220 if (attr > prevAttr)
221 {
222 keepCurrent = !m_ReverseOrdering;
223 }
224 else
225 {
226 keepCurrent = m_ReverseOrdering;
227 }
228 }
229
230 if (keepCurrent)
231 {
232 // keep the current one. We must truncate the previous one to remove
233 // the
234 // overlap, and take care of the end of the previous line if it
235 // extends
236 // after the current one.
237 if (prevIdx[0] + prevLength > idx[0] + length)
238 {
239 // the previous line is longer than the current one. Lets take its
240 // tail and
241 // add it to the priority queue
242 IndexType newIdx = idx;
243 newIdx[0] = idx[0] + length;
244 OffsetValueType newLength = prevIdx[0] + prevLength - newIdx[0];
245 priorityQueue.push(LineOfLabelObject(LineType(newIdx, newLength), prev.labelObject));
246 }
247 // truncate the previous line to let some place for the current one
248 prevLength = idx[0] - prevIdx[0];
249 if (prevLength != 0)
250 {
251 assert(prevIdx[0] <= idx[0]);
252 lines.back().line.SetLength(idx[0] - prevIdx[0]);
253 }
254 else
255 {
256 // length is 0 - no need to keep that line
257 lines.pop_back();
258 }
259 // and push the current one
260 lines.push_back(l);
261 }
262 else
263 {
264 // keep the previous one. If the previous line fully overlap the
265 // current one,
266 // the current one is fully discarded.
267 if (prevIdx[0] + prevLength >= idx[0] + length)
268 {
269 // discarding the current line - just do nothing
270 }
271 else
272 {
273 IndexType newIdx = idx;
274 newIdx[0] = prevIdx[0] + prevLength;
275 OffsetValueType newLength = idx[0] + length - newIdx[0];
276 if (newLength > 0)
277 {
278 l.line.SetIndex(newIdx);
279 l.line.SetLength(newLength);
280 // The front of this line is trimmed, it may occur after a line in the queue
281 // so the queue is used for the proper ordering.
282 priorityQueue.push(l);
283 }
284 }
285 }
286 }
287 else
288 {
289 // no overlap - things are just fine already
290 lines.push_back(l);
291 }
292 }
293
294 // store the current line as the previous one, and go to the next one.
295 prev = lines.back();
296 prevIdx = prev.line.GetIndex();
297 }
298
299 // put the lines in their object
300 for (size_t i = 0; i < lines.size(); ++i)
301 {
302 LineOfLabelObject & l = lines[i];
303 l.labelObject->AddLine(l.line);
304 }
305
306 // remove objects without lines
307 typename ImageType::Iterator it(this->GetLabelMap());
308 while (!it.IsAtEnd())
309 {
310 typename LabelObjectType::LabelType label = it.GetLabel();
311 LabelObjectType * labelObject = it.GetLabelObject();
312
313 if (labelObject->Empty())
314 {
315 // must increment the iterator before removing the object to avoid
316 // invalidating the iterator
317 ++it;
318 this->GetLabelMap()->RemoveLabel(label);
319 }
320 else
321 {
322 ++it;
323 }
324 }
325 }
326
327 void
328 PrintSelf(std::ostream & os, Indent indent) const override;
329
330 AttributeType m_Attribute{};
331
332private:
333 bool m_ReverseOrdering{};
335 {
336 using LineType = typename LabelObjectType::LineType;
338 {
339 this->line = _line;
340 this->labelObject = _lo;
341 }
342
345 };
346
348 {
349 public:
350 bool
352 {
353 for (int i = ImageDimension - 1; i >= 0; i--)
354 {
355 if (lla.line.GetIndex()[i] > llb.line.GetIndex()[i])
356 {
357 return true;
358 }
359 else if (lla.line.GetIndex()[i] < llb.line.GetIndex()[i])
360 {
361 return false;
362 }
363 }
364 return false;
365 }
366 };
367}; // end of class
368} // end namespace itk
369
370#ifndef ITK_MANUAL_INSTANTIATION
371# include "itkShapeUniqueLabelMapFilter.hxx"
372#endif
373
374#endif
Base class for filters that takes an image as input and overwrites that image as the output.
Control indentation during Print() invocation.
Definition: itkIndent.h:50
Light weight base class for most itk classes.
Implements progress tracking for a filter.
bool operator()(const LineOfLabelObject &lla, const LineOfLabelObject &llb)
Remove some pixels in the label object according to the value of their shape attribute to ensure that...
typename ImageType::IndexType IndexType
typename ImageType::PixelType PixelType
void TemplatedGenerateData(const TAttributeAccessor &accessor)
void PrintSelf(std::ostream &os, Indent indent) const override
typename LabelObjectType::AttributeType AttributeType
typename ImageType::Pointer ImagePointer
typename ImageType::ConstPointer ImageConstPointer
typename LabelObjectType::LineType LineType
typename ImageType::LabelObjectType LabelObjectType
~ShapeUniqueLabelMapFilter() override=default
SmartPointer< const Self > ConstPointer
SmartPointer< Self > Pointer
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:722
The "itk" namespace contains all Insight Segmentation and Registration Toolkit (ITK) classes....
long OffsetValueType
Definition: itkIntTypes.h:97
LineOfLabelObject(const LineType _line, LabelObjectType *_lo)