ITK  6.0.0
Insight Toolkit
itkRankHistogram.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// histogram from the moving histogram operations
19#ifndef itkRankHistogram_h
20#define itkRankHistogram_h
21
22#include "itkIntTypes.h"
23#include "itkNumericTraits.h"
24
25#include <map>
26#include <vector>
27
28namespace itk
29{
30namespace Function
31{
32
33/* \class RankHistogram
34 * \brief A simple histogram class hierarchy. One specialization will
35 * be maps, the other vectors.
36 *
37 * This version is intended for keeping track of arbitrary ranks. It
38 * is based on the code from consolidatedMorphology.
39 *
40 * This is a modified version for use with masks. Need to allow for
41 * the situation in which the map is empty.
42 *
43 * This code was contributed in the Insight Journal paper:
44 * "Efficient implementation of kernel filtering"
45 * by Beare R., Lehmann G
46 * https://doi.org/10.54294/igq8fn
47 *
48 * /sa VectorRankHistogram
49 */
50template <typename TInputPixel>
52{
53public:
54 using Compare = std::less<TInputPixel>;
55
57 {
58 m_Rank = 0.5;
59 m_Below = m_Entries = 0;
60 // can't set m_RankIt until something has been put in the histogram
61 m_Initialized = false;
63 {
65 }
66 else
67 {
69 }
71 m_RankIt = m_Map.begin(); // equivalent to setting to the initial value
72 }
73
74 ~RankHistogram() = default;
75
78 {
79 if (this != &hist)
80 {
81 m_Map = hist.m_Map;
82 m_Rank = hist.m_Rank;
83 m_Below = hist.m_Below;
84 m_Entries = hist.m_Entries;
85 m_InitVal = hist.m_InitVal;
88 if (m_Initialized)
89 {
91 }
92 }
93 return *this;
94 }
95
96 void
97 AddPixel(const TInputPixel & p)
98 {
99 m_Map[p]++;
100 if (!m_Initialized)
101 {
102 m_Initialized = true;
103 m_RankIt = m_Map.begin();
104 m_Entries = m_Below = 0;
105 m_RankValue = p;
106 }
107 if (m_Compare(p, m_RankValue) || p == m_RankValue)
108 {
109 ++m_Below;
110 }
111 ++m_Entries;
112 }
113
114 void
115 RemovePixel(const TInputPixel & p)
116 {
117 m_Map[p]--;
118 if (m_Compare(p, m_RankValue) || p == m_RankValue)
119 {
120 --m_Below;
121 }
122 --m_Entries;
123 // this is the change that makes this version less efficient. The
124 // simplest approach I can think of with maps, though
125 if (m_Entries <= 0)
126 {
127 m_Initialized = false;
128 m_Below = 0;
129 m_Map.clear();
130 }
131 }
132
133 bool
135 {
136 return m_Initialized;
137 }
138
139 TInputPixel
141 {
142 SizeValueType count = 0;
143 SizeValueType target = static_cast<int>(m_Rank * (m_Entries - 1)) + 1;
144 for (typename MapType::iterator it = m_Map.begin(); it != m_Map.end(); ++it)
145 {
146 count += it->second;
147 if (count >= target)
148 {
149 return it->first;
150 }
151 }
153 }
154
155 TInputPixel
156 GetValue(const TInputPixel &)
157 {
158 SizeValueType target = (SizeValueType)(m_Rank * (m_Entries - 1)) + 1;
159 SizeValueType total = m_Below;
160 SizeValueType ThisBin;
161 bool eraseFlag = false;
162
163 if (total < target)
164 {
165 auto searchIt = m_RankIt;
166 typename MapType::iterator eraseIt;
167
168 while (searchIt != m_Map.end())
169 {
170 // cleaning up the map - probably a better way of organising
171 // the loop. Currently makes sure that the search iterator is
172 // incremented before deleting
173 ++searchIt;
174 ThisBin = searchIt->second;
175 total += ThisBin;
176 if (eraseFlag)
177 {
178 m_Map.erase(eraseIt);
179 eraseFlag = false;
180 }
181 if (ThisBin <= 0)
182 {
183 eraseFlag = true;
184 eraseIt = searchIt;
185 }
186 if (total >= target)
187 {
188 break;
189 }
190 }
191 if (searchIt == m_Map.end())
192 {
193 --searchIt;
194 }
195 m_RankValue = searchIt->first;
196 m_RankIt = searchIt;
197 }
198 else
199 {
200 auto searchIt = m_RankIt;
201 typename MapType::iterator eraseIt;
202
203 while (searchIt != m_Map.begin())
204 {
205 ThisBin = searchIt->second;
206 unsigned int tbelow = total - ThisBin;
207 if (tbelow < target) // we've overshot
208 {
209 break;
210 }
211 if (eraseFlag)
212 {
213 m_Map.erase(eraseIt);
214 eraseFlag = false;
215 }
216 if (ThisBin <= 0)
217 {
218 eraseIt = searchIt;
219 eraseFlag = true;
220 }
221 total = tbelow;
222
223 --searchIt;
224 }
225 m_RankValue = searchIt->first;
226 m_RankIt = searchIt;
227 }
228
229 m_Below = total;
230 itkAssertInDebugAndIgnoreInReleaseMacro(m_RankValue == GetValueBruteForce());
231 return (m_RankValue);
232 }
233
234 void
235 SetRank(float rank)
236 {
237 m_Rank = rank;
238 }
239
240 void
242 {}
243
244 void
246 {}
247
248 static bool
250 {
251 return false;
252 }
253
254protected:
255 float m_Rank;
256
257private:
258 using MapType = typename std::map<TInputPixel, SizeValueType, Compare>;
259
263 TInputPixel m_RankValue;
264 TInputPixel m_InitVal;
267
268 // This iterator will point at the desired rank value
269 typename MapType::iterator m_RankIt;
270};
271
272
273template <typename TInputPixel>
275{
276public:
277 using Compare = std::less<TInputPixel>;
278
280 {
283 m_Vec.resize(m_Size, 0);
285 {
287 }
288 else
289 {
291 }
292 m_Entries = m_Below = 0;
294 m_Rank = 0.5;
295 }
296
298
299 bool
301 {
302 return m_Entries > 0;
303 }
304
305 TInputPixel
307 {
308 SizeValueType count = 0;
309 SizeValueType target = (SizeValueType)(m_Rank * (m_Entries - 1)) + 1;
310 for (SizeValueType i = 0; i < m_Size; ++i)
311 {
312 count += m_Vec[i];
313 if (count >= target)
314 {
316 }
317 }
319 }
320
321 TInputPixel
322 GetValue(const TInputPixel &)
323 {
324 return GetValueBruteForce();
325 }
326
327 void
328 AddPixel(const TInputPixel & p)
329 {
331
332 m_Vec[q]++;
333 if (m_Compare(p, m_RankValue) || p == m_RankValue)
334 {
335 ++m_Below;
336 }
337 ++m_Entries;
338 }
339
340 void
341 RemovePixel(const TInputPixel & p)
342 {
344
345 itkAssertInDebugAndIgnoreInReleaseMacro(q >= 0);
346 itkAssertInDebugAndIgnoreInReleaseMacro(q < static_cast<int>(m_Vec.size()));
347 itkAssertInDebugAndIgnoreInReleaseMacro(m_Entries >= 1);
348 itkAssertInDebugAndIgnoreInReleaseMacro(m_Vec[q] > 0);
349
350 m_Vec[q]--;
351 --m_Entries;
352
353 if (m_Compare(p, m_RankValue) || p == m_RankValue)
354 {
355 --m_Below;
356 }
357 }
358
359 void
360 SetRank(float rank)
361 {
362 m_Rank = rank;
363 }
364
365 void
367 {}
368
369 void
371 {}
372
373 static bool
375 {
376 return true;
377 }
378
379protected:
380 float m_Rank;
381
382private:
383 using VecType = typename std::vector<SizeValueType>;
384
388 TInputPixel m_RankValue;
389 TInputPixel m_InitVal;
392};
393
394// now create MorphologicalGradientHistogram specializations using the VectorMorphologicalGradientHistogram
395// as base class
396
398
399template <>
400class RankHistogram<unsigned char> : public VectorRankHistogram<unsigned char>
401{};
402
403template <>
404class RankHistogram<signed char> : public VectorRankHistogram<signed char>
405{};
406
407template <>
408class ITK_TEMPLATE_EXPORT RankHistogram<bool> : public VectorRankHistogram<bool>
409{};
410
412
413} // end namespace Function
414} // end namespace itk
415#endif
std::less< TInputPixel > Compare
TInputPixel GetValue(const TInputPixel &)
typename std::map< TInputPixel, SizeValueType, Compare > MapType
RankHistogram & operator=(const RankHistogram &hist)
void AddPixel(const TInputPixel &p)
void RemovePixel(const TInputPixel &p)
typename std::vector< SizeValueType > VecType
void RemovePixel(const TInputPixel &p)
void AddPixel(const TInputPixel &p)
std::less< TInputPixel > Compare
TInputPixel GetValue(const TInputPixel &)
Define additional traits for native types such as int or float.
static constexpr T NonpositiveMin()
static constexpr T max(const T &)
The "itk" namespace contains all Insight Segmentation and Registration Toolkit (ITK) classes....
unsigned long SizeValueType
Definition: itkIntTypes.h:86
long OffsetValueType
Definition: itkIntTypes.h:97