SMIL  0.9.1
DMorphoHierarQ.hpp
1 /*
2  * Copyright (c) 2011-2016, Matthieu FAESSEL and ARMINES
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are met:
7  *
8  * * Redistributions of source code must retain the above copyright
9  * notice, this list of conditions and the following disclaimer.
10  * * Redistributions in binary form must reproduce the above copyright
11  * notice, this list of conditions and the following disclaimer in the
12  * documentation and/or other materials provided with the distribution.
13  * * Neither the name of Matthieu FAESSEL, or ARMINES nor the
14  * names of its contributors may be used to endorse or promote products
15  * derived from this software without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS IS'' AND ANY
18  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20  * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS AND CONTRIBUTORS BE LIABLE FOR ANY
21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
26  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28 
29 
30 #ifndef _D_MORPHO_HIERARQ_HPP
31 #define _D_MORPHO_HIERARQ_HPP
32 
33 
34 #include <queue>
35 #include <deque>
36 
37 #include "Core/include/private/DTypes.hpp"
38 #include "Morpho/include/DStructuringElement.h"
39 
40 
41 namespace smil
42 {
50  enum HQ_STATUS
51  {
52  HQ_CANDIDATE,
53  HQ_QUEUED,
54  HQ_LABELED,
55  HQ_WS_LINE,
56  HQ_FINAL
57  };
58 
62  template <class T>
63  class FIFO_Queue
64  {
65  public:
66  FIFO_Queue(size_t newSize=0)
67  {
68  data = NULL;
69  if (newSize)
70  initialize(newSize);
71  }
72  virtual ~FIFO_Queue()
73  {
74  if (data)
75  delete[] data;
76  }
77 
78  void reset()
79  {
80  if (data)
81  delete[] data;
82  data = NULL;
83  _size = realSize = 0;
84  }
85  void initialize(size_t newSize)
86  {
87  reset();
88  realSize = max( newSize+1, size_t(8) ); // Avoid to have to small buffer
89  data = new T[realSize];
90  _size = 0;
91  first = 0;
92  last = 0;
93  }
94  inline size_t size()
95  {
96  return _size;
97  }
98  void swap()
99  {
100  memmove(data, data+first, (last-first)*sizeof(T));
101  first = 0;
102  last = _size;
103  }
104  void push(T val)
105  {
106  if (last==realSize)
107  swap();
108  data[last++] = val;
109  _size++;
110  }
111  inline T front()
112  {
113  return data[first];
114  }
115  inline void pop()
116  {
117  _size--;
118  first++;
119  }
120 
121  static const bool preallocate = true;
122 
123  protected:
124  size_t _size;
125  size_t realSize;
126  size_t first;
127  size_t last;
128  T* data;
129  };
130 
131  template <class TokenType=size_t>
132  class STD_Queue : public queue<TokenType>
133  {
134  public:
135  // Dummy constructor for compatibilty with FIFO_Queue one
136  STD_Queue(size_t /*newSize*/=0)
137  : queue<TokenType>()
138  {
139  }
140  static const bool preallocate = false;
141  };
142 
143  template <class TokenType=size_t>
144  class STD_Stack : public stack<TokenType>
145  {
146  public:
147  // Dummy operator for compatibility with other containers from smil
148  inline TokenType front ()
149  {
150  return this->top();
151  }
152  };
153 
154  template <class T, class TokenType=size_t, class StackType=STD_Queue<TokenType> >
156  {
157  private:
158 
159  size_t GRAY_LEVEL_NBR;
160  size_t GRAY_LEVEL_MIN;
161  StackType **stacks;
162  size_t *tokenNbr;
163  size_t size;
164  size_t higherLevel;
165 
166  bool initialized;
167  const bool reverseOrder;
168 
169  public:
170  HierarchicalQueue(bool rOrder=false)
171  : reverseOrder(rOrder)
172  {
173  stacks = NULL;
174  tokenNbr = NULL;
175  initialized = false;
176  }
178  {
179  reset();
180  delete[] stacks;
181  delete[] tokenNbr;
182  }
183 
184  void reset()
185  {
186  if (!initialized)
187  return;
188 
189  for(size_t i=0;i<GRAY_LEVEL_NBR;i++)
190  {
191  if (stacks[i])
192  {
193  delete stacks[i];
194  stacks[i] = NULL;
195  }
196  }
197 
198  initialized = false;
199  }
200 
201  void initialize(const Image<T> &img)
202  {
203  if (initialized)
204  reset();
205 
206 // vector<T> rVals = rangeVal(img);
207 
208  GRAY_LEVEL_MIN = ImDtTypes<T>::min();
209  GRAY_LEVEL_NBR = ImDtTypes<T>::cardinal();
210 
211  stacks = new StackType*[GRAY_LEVEL_NBR]();
212  tokenNbr = new size_t[GRAY_LEVEL_NBR];
213 
214  if (StackType::preallocate)
215  {
216  size_t *h = new size_t[GRAY_LEVEL_NBR];
217  histogram(img, h);
218 
219  for(size_t i=0;i<GRAY_LEVEL_NBR;i++)
220  {
221  if (h[i]!=0)
222  stacks[i] = new StackType(h[i]);
223  else stacks[i] = NULL;
224  }
225 
226  delete[] h;
227  }
228  else
229  {
230  for(size_t i=0;i<GRAY_LEVEL_NBR;i++)
231  stacks[i] = new StackType();
232  }
233 
234  memset(tokenNbr, 0, GRAY_LEVEL_NBR*sizeof(size_t));
235  size = 0;
236 
237  if (reverseOrder)
238  higherLevel = 0;
239  else
240  higherLevel = ImDtTypes<T>::max();
241 
242  initialized = true;
243  }
244 
245  inline size_t getSize()
246  {
247  return size;
248  }
249 
250  inline bool isEmpty()
251  {
252  return size==0;
253  }
254 
255  inline size_t getHigherLevel()
256  {
257  return GRAY_LEVEL_MIN + higherLevel;
258  }
259 
260  inline void push(T value, TokenType dOffset)
261  {
262  size_t level = size_t(value) - GRAY_LEVEL_MIN;
263  if (reverseOrder)
264  {
265  if (level>higherLevel)
266  higherLevel = level;
267  }
268  else
269  {
270  if (level<higherLevel)
271  higherLevel = level;
272  }
273  stacks[level]->push(dOffset);
274  tokenNbr[level]++;
275  size++;
276  }
277  inline void findNewReferenceLevel()
278  {
279  if (reverseOrder)
280  {
281  for (size_t i=higherLevel-1;i!=numeric_limits<size_t>::max();i--)
282  if (tokenNbr[i]>0)
283  {
284  higherLevel = i;
285  break;
286  }
287  }
288  else
289  {
290  for (size_t i=higherLevel+1;i<GRAY_LEVEL_NBR;i++)
291  if (tokenNbr[i]>0)
292  {
293  higherLevel = i;
294  break;
295  }
296  }
297  }
298 
299  inline TokenType pop()
300  {
301  size_t hlSize = tokenNbr[higherLevel];
302  TokenType dOffset = stacks[higherLevel]->front();
303  stacks[higherLevel]->pop();
304  size--;
305 
306  if (hlSize>1)
307  tokenNbr[higherLevel]--;
308  else if (size>0) // Find new ref level (non empty stack)
309  {
310  tokenNbr[higherLevel] = 0;
311  findNewReferenceLevel();
312  }
313  else // Empty -> re-initilize
314  {
315  tokenNbr[higherLevel] = 0;
316  if (reverseOrder)
317  higherLevel = 0;
318  else
319  higherLevel = ImDtTypes<size_t>::max();
320  }
321  return dOffset;
322  }
323  };
324 
325 
328 } // namespace smil
329 
330 
331 
332 #endif // _D_MORPHO_HIERARQ_HPP
333 
Definition: DColorConvert.h:38
Definition: DMorphoHierarQ.hpp:132
Preallocated FIFO Queue.
Definition: DMorphoHierarQ.hpp:63
Definition: DMorphoHierarQ.hpp:144
Definition: DMorphoHierarQ.hpp:155
Definition: DTypes.hpp:78
Main Image class.
Definition: DQVtkViewer.hpp:44