ITK  5.3.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  * 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 // 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 
28 namespace itk
29 {
30 namespace 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://www.insight-journal.org/browse/publication/160
47  *
48  * /sa VectorRankHistogram
49  */
50 template <typename TInputPixel>
52 {
53 public:
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 
77  operator=(const RankHistogram & hist)
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;
86  m_RankValue = hist.m_RankValue;
88  if (m_Initialized)
89  {
90  m_RankIt = m_Map.find(m_RankValue);
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 = (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 
254 protected:
255  float m_Rank;
256 
257 private:
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 
273 template <typename TInputPixel>
275 {
276 public:
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 
297  ~VectorRankHistogram() = default;
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 < (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 
379 protected:
380  float m_Rank;
381 
382 private:
383  using VecType = typename std::vector<SizeValueType>;
384 
388  TInputPixel m_RankValue;
389  TInputPixel m_InitVal;
390  int m_Below;
392 };
393 
394 // now create MorphologicalGradientHistogram specializations using the VectorMorphologicalGradientHistogram
395 // as base class
396 
398 
399 template <>
400 class RankHistogram<unsigned char> : public VectorRankHistogram<unsigned char>
401 {};
402 
403 template <>
404 class RankHistogram<signed char> : public VectorRankHistogram<signed char>
405 {};
406 
407 template <>
408 class ITK_TEMPLATE_EXPORT RankHistogram<bool> : public VectorRankHistogram<bool>
409 {};
410 
412 
413 } // end namespace Function
414 } // end namespace itk
415 #endif
itk::Function::RankHistogram::m_Below
SizeValueType m_Below
Definition: itkRankHistogram.h:261
itk::Function::VectorRankHistogram
Definition: itkRankHistogram.h:274
itk::Function::RankHistogram::GetValueBruteForce
TInputPixel GetValueBruteForce()
Definition: itkRankHistogram.h:140
itk::Function::VectorRankHistogram::RemovePixel
void RemovePixel(const TInputPixel &p)
Definition: itkRankHistogram.h:341
itk::Function::RankHistogram::operator=
RankHistogram & operator=(const RankHistogram &hist)
Definition: itkRankHistogram.h:77
itk::Function::RankHistogram::UseVectorBasedAlgorithm
static bool UseVectorBasedAlgorithm()
Definition: itkRankHistogram.h:249
itk::Function::RankHistogram::IsValid
bool IsValid()
Definition: itkRankHistogram.h:134
itk::Function::VectorRankHistogram::m_InitVal
TInputPixel m_InitVal
Definition: itkRankHistogram.h:389
itk::Function::RankHistogram::RankHistogram
RankHistogram()
Definition: itkRankHistogram.h:56
itk::Function::RankHistogram::RemovePixel
void RemovePixel(const TInputPixel &p)
Definition: itkRankHistogram.h:115
itk::NumericTraits::NonpositiveMin
static constexpr T NonpositiveMin()
Definition: itkNumericTraits.h:97
itk::Function::VectorRankHistogram::m_Compare
Compare m_Compare
Definition: itkRankHistogram.h:387
itk::Function::VectorRankHistogram::m_Rank
float m_Rank
Definition: itkRankHistogram.h:380
itk::Function::VectorRankHistogram::VectorRankHistogram
VectorRankHistogram()
Definition: itkRankHistogram.h:279
itk::Function::RankHistogram::RemoveBoundary
void RemoveBoundary()
Definition: itkRankHistogram.h:245
itk::Function::VectorRankHistogram::m_Vec
VecType m_Vec
Definition: itkRankHistogram.h:385
itk::Function::VectorRankHistogram::UseVectorBasedAlgorithm
static bool UseVectorBasedAlgorithm()
Definition: itkRankHistogram.h:374
itk::Function::VectorRankHistogram::AddPixel
void AddPixel(const TInputPixel &p)
Definition: itkRankHistogram.h:328
itk::Function::VectorRankHistogram::GetValue
TInputPixel GetValue(const TInputPixel &)
Definition: itkRankHistogram.h:322
itk::Function::VectorRankHistogram::m_Size
SizeValueType m_Size
Definition: itkRankHistogram.h:386
itk::Function::VectorRankHistogram::SetRank
void SetRank(float rank)
Definition: itkRankHistogram.h:360
itk::Function::RankHistogram::m_RankIt
MapType::iterator m_RankIt
Definition: itkRankHistogram.h:269
itk::Function::RankHistogram::~RankHistogram
~RankHistogram()=default
itk::Function::RankHistogram::AddBoundary
void AddBoundary()
Definition: itkRankHistogram.h:241
itk::Function::RankHistogram::m_InitVal
TInputPixel m_InitVal
Definition: itkRankHistogram.h:264
itk::Function::RankHistogram::Compare
std::less< TInputPixel > Compare
Definition: itkRankHistogram.h:54
itk::Function::VectorRankHistogram::m_RankValue
TInputPixel m_RankValue
Definition: itkRankHistogram.h:388
itk::Function::VectorRankHistogram::~VectorRankHistogram
~VectorRankHistogram()=default
itk::Function::VectorRankHistogram::IsValid
bool IsValid()
Definition: itkRankHistogram.h:300
itk::Function::VectorRankHistogram::Compare
std::less< TInputPixel > Compare
Definition: itkRankHistogram.h:277
itk::Function::VectorRankHistogram::m_Entries
int m_Entries
Definition: itkRankHistogram.h:391
itk::Function::RankHistogram::m_Map
MapType m_Map
Definition: itkRankHistogram.h:260
itkIntTypes.h
itk::Function::VectorRankHistogram::AddBoundary
void AddBoundary()
Definition: itkRankHistogram.h:366
itk::NumericTraits
Define additional traits for native types such as int or float.
Definition: itkNumericTraits.h:58
itk::NumericTraits::max
static constexpr T max(const T &)
Definition: itkNumericTraits.h:167
itk::Function::VectorRankHistogram::VecType
typename std::vector< SizeValueType > VecType
Definition: itkRankHistogram.h:383
itk::Function::RankHistogram::GetValue
TInputPixel GetValue(const TInputPixel &)
Definition: itkRankHistogram.h:156
itk::Function::RankHistogram::m_RankValue
TInputPixel m_RankValue
Definition: itkRankHistogram.h:263
itk
The "itk" namespace contains all Insight Segmentation and Registration Toolkit (ITK) classes....
Definition: itkAnnulusOperator.h:24
itk::Function::RankHistogram::m_Rank
float m_Rank
Definition: itkRankHistogram.h:255
itk::Function::VectorRankHistogram::RemoveBoundary
void RemoveBoundary()
Definition: itkRankHistogram.h:370
itk::OffsetValueType
signed long OffsetValueType
Definition: itkIntTypes.h:94
itk::Function::VectorRankHistogram::GetValueBruteForce
TInputPixel GetValueBruteForce()
Definition: itkRankHistogram.h:306
itk::Function::VectorRankHistogram::m_Below
int m_Below
Definition: itkRankHistogram.h:390
itkNumericTraits.h
itk::Function::RankHistogram
Definition: itkRankHistogram.h:51
itk::Function::RankHistogram::m_Compare
Compare m_Compare
Definition: itkRankHistogram.h:265
itk::Function::RankHistogram::m_Entries
SizeValueType m_Entries
Definition: itkRankHistogram.h:262
itk::Function::RankHistogram::SetRank
void SetRank(float rank)
Definition: itkRankHistogram.h:235
itk::Function::RankHistogram::AddPixel
void AddPixel(const TInputPixel &p)
Definition: itkRankHistogram.h:97
itk::SizeValueType
unsigned long SizeValueType
Definition: itkIntTypes.h:83
itk::Function::RankHistogram::m_Initialized
bool m_Initialized
Definition: itkRankHistogram.h:266
itk::Function::RankHistogram::MapType
typename std::map< TInputPixel, SizeValueType, Compare > MapType
Definition: itkRankHistogram.h:258