[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

multi_shape.hxx VIGRA

1 /************************************************************************/
2 /* */
3 /* Copyright 2011-2012 by Stefan Schmidt and Ullrich Koethe */
4 /* */
5 /* This file is part of the VIGRA computer vision library. */
6 /* The VIGRA Website is */
7 /* http://hci.iwr.uni-heidelberg.de/vigra/ */
8 /* Please direct questions, bug reports, and contributions to */
9 /* ullrich.koethe@iwr.uni-heidelberg.de or */
10 /* vigra@informatik.uni-hamburg.de */
11 /* */
12 /* Permission is hereby granted, free of charge, to any person */
13 /* obtaining a copy of this software and associated documentation */
14 /* files (the "Software"), to deal in the Software without */
15 /* restriction, including without limitation the rights to use, */
16 /* copy, modify, merge, publish, distribute, sublicense, and/or */
17 /* sell copies of the Software, and to permit persons to whom the */
18 /* Software is furnished to do so, subject to the following */
19 /* conditions: */
20 /* */
21 /* The above copyright notice and this permission notice shall be */
22 /* included in all copies or substantial portions of the */
23 /* Software. */
24 /* */
25 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */
26 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */
27 /* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */
28 /* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */
29 /* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */
30 /* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */
31 /* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */
32 /* OTHER DEALINGS IN THE SOFTWARE. */
33 /* */
34 /************************************************************************/
35 
36 #ifndef VIGRA_MULTI_SHAPE_HXX
37 #define VIGRA_MULTI_SHAPE_HXX
38 
39 #include <sys/types.h>
40 #include "tinyvector.hxx"
41 #include "array_vector.hxx"
42 #include "numerictraits.hxx"
43 
44 namespace vigra {
45 
46 /** \addtogroup MultiIteratorGroup Multi-dimensional Shapes and Array Iterators
47 
48  \brief Shape objects and general iterators for arrays of arbitrary dimension.
49 */
50 //@{
51 
52  /** Index type for a single dimension of a MultiArrayView or
53  MultiArray.
54  */
55 typedef std::ptrdiff_t MultiArrayIndex;
56 
57 /********************************************************/
58 /* */
59 /* Singleband and Multiband */
60 /* */
61 /********************************************************/
62 
63 template <class T>
64 struct Singleband // the resulting MultiArray has no explicit channel axis
65  // (i.e. the number of channels is implicitly one)
66 {
67  typedef T value_type;
68 };
69 
70 template <class T>
71 struct Multiband // the last axis is explicitly designated as channel axis
72 {
73  typedef T value_type;
74 };
75 
76 template<class T>
77 struct NumericTraits<Singleband<T> >
78 : public NumericTraits<T>
79 {};
80 
81 template<class T>
82 struct NumericTraits<Multiband<T> >
83 {
84  typedef Multiband<T> Type;
85 /*
86  typedef int Promote;
87  typedef unsigned int UnsignedPromote;
88  typedef double RealPromote;
89  typedef std::complex<RealPromote> ComplexPromote;
90 */
91  typedef Type ValueType;
92 
93  typedef typename NumericTraits<T>::isIntegral isIntegral;
94  typedef VigraFalseType isScalar;
95  typedef typename NumericTraits<T>::isSigned isSigned;
96  typedef typename NumericTraits<T>::isSigned isOrdered;
97  typedef typename NumericTraits<T>::isSigned isComplex;
98 /*
99  static signed char zero() { return 0; }
100  static signed char one() { return 1; }
101  static signed char nonZero() { return 1; }
102  static signed char min() { return SCHAR_MIN; }
103  static signed char max() { return SCHAR_MAX; }
104 
105 #ifdef NO_INLINE_STATIC_CONST_DEFINITION
106  enum { minConst = SCHAR_MIN, maxConst = SCHAR_MIN };
107 #else
108  static const signed char minConst = SCHAR_MIN;
109  static const signed char maxConst = SCHAR_MIN;
110 #endif
111 
112  static Promote toPromote(signed char v) { return v; }
113  static RealPromote toRealPromote(signed char v) { return v; }
114  static signed char fromPromote(Promote v) {
115  return ((v < SCHAR_MIN) ? SCHAR_MIN : (v > SCHAR_MAX) ? SCHAR_MAX : v);
116  }
117  static signed char fromRealPromote(RealPromote v) {
118  return ((v < 0.0)
119  ? ((v < (RealPromote)SCHAR_MIN)
120  ? SCHAR_MIN
121  : static_cast<signed char>(v - 0.5))
122  : (v > (RealPromote)SCHAR_MAX)
123  ? SCHAR_MAX
124  : static_cast<signed char>(v + 0.5));
125  }
126 */
127 };
128 
129 namespace detail {
130 
131 /********************************************************/
132 /* */
133 /* defaultStride */
134 /* */
135 /********************************************************/
136 
137  /* generates the stride for a gapless shape.
138  */
139 template <int N>
140 inline TinyVector <MultiArrayIndex, N>
141 defaultStride(const TinyVector <MultiArrayIndex, N> &shape)
142 {
143  TinyVector <MultiArrayIndex, N> ret;
144  ret [0] = 1;
145  for (int i = 1; i < (int)N; ++i)
146  ret [i] = ret [i-1] * shape [i-1];
147  return ret;
148 }
149 
150  /* generates the stride for a gapless shape.
151  */
152 template <int N>
153 inline TinyVector <MultiArrayIndex, N>
154 defaultMultibandStride(const TinyVector <MultiArrayIndex, N> &shape)
155 {
156  TinyVector <MultiArrayIndex, N> ret;
157  ret [N-1] = 1;
158  for (int i = 0; i < (int)N-1; ++i)
159  {
160  int j = (i + int(N - 1)) % N;
161  ret [i] = ret [j] * shape [j];
162  }
163  return ret;
164 }
165 
166 /********************************************************/
167 /* */
168 /* ResolveMultiband */
169 /* */
170 /********************************************************/
171 
172 template <class T>
173 struct ResolveMultiband
174 {
175  typedef T type;
176  typedef StridedArrayTag Stride;
177  static const bool value = false;
178 
179  template <int N>
180  static TinyVector <MultiArrayIndex, N>
181  defaultStride(const TinyVector <MultiArrayIndex, N> &shape)
182  {
183  return vigra::detail::defaultStride(shape);
184  }
185 };
186 
187 template <class T>
188 struct ResolveMultiband<Singleband<T> >
189 {
190  typedef T type;
191  typedef StridedArrayTag Stride;
192  static const bool value = false;
193 
194  template <int N>
195  static TinyVector <MultiArrayIndex, N>
196  defaultStride(const TinyVector <MultiArrayIndex, N> &shape)
197  {
198  return vigra::detail::defaultStride(shape);
199  }
200 };
201 
202 template <class T>
203 struct ResolveMultiband<Multiband<T> >
204 {
205  typedef T type;
206  typedef StridedArrayTag Stride;
207  static const bool value = true;
208 
209  template <int N>
210  static TinyVector <MultiArrayIndex, N>
211  defaultStride(const TinyVector <MultiArrayIndex, N> &shape)
212  {
213  return vigra::detail::defaultMultibandStride(shape);
214  }
215 };
216 
217 } // namespace detail
218 
219 template <unsigned int N, class T, class C = StridedArrayTag>
220 class MultiArrayView;
221 
222 template <unsigned int N, class T,
223  class A = std::allocator<typename vigra::detail::ResolveMultiband<T>::type> >
224 class MultiArray;
225 
226 
227  /** Traits class for the difference type of all MultiIterator, MultiArrayView, and
228  MultiArray variants.
229  */
230 template <unsigned int N>
232 {
233  public:
234  /** The difference type of all MultiIterator, MultiArrayView, and
235  MultiArray variants.
236  */
238 };
239 
240 typedef MultiArrayShape<1>::type Shape1; ///< shape type for MultiArray<1, T>
241 typedef MultiArrayShape<2>::type Shape2; ///< shape type for MultiArray<2, T>
242 typedef MultiArrayShape<3>::type Shape3; ///< shape type for MultiArray<3, T>
243 typedef MultiArrayShape<4>::type Shape4; ///< shape type for MultiArray<4, T>
244 typedef MultiArrayShape<5>::type Shape5; ///< shape type for MultiArray<5, T>
245 
246  /** \brief Choose the neighborhood system in a dimension-independent way.
247 
248  DirectNeighborhood corresponds to 4-neighborhood in 2D and 6-neighborhood in 3D, whereas
249  IndirectNeighborhood means 8-neighborhood in 2D and 26-neighborhood in 3D. The general
250  formula for N dimensions are 2*N for direct neighborhood and 3^N-1 for indirect neighborhood.
251  */
253  DirectNeighborhood=0, ///< use only direct neighbors
254  IndirectNeighborhood=1 ///< use direct and indirect neighbors
255 };
256 
257 // Helper functions
258 
259 namespace detail {
260 
261 /********************************************************/
262 /* */
263 /* CoordinateToScanOrder */
264 /* */
265 /********************************************************/
266 
267  /* Convert multi-dimensional index (i.e. a grid coordinate) to scan-order index.
268  */
269 template <int K>
270 struct CoordinateToScanOrder
271 {
272  template <int N, class D1, class D2, class D3, class D4>
273  static MultiArrayIndex
274  exec(const TinyVectorBase <MultiArrayIndex, N, D1, D2> &shape,
275  const TinyVectorBase <MultiArrayIndex, N, D3, D4> & coordinate)
276  {
277  return coordinate[N-K] + shape[N-K] * CoordinateToScanOrder<K-1>::exec(shape, coordinate);
278  }
279 };
280 
281 template <>
282 struct CoordinateToScanOrder<1>
283 {
284  template <int N, class D1, class D2, class D3, class D4>
285  static MultiArrayIndex
286  exec(const TinyVectorBase <MultiArrayIndex, N, D1, D2> & /*shape*/,
287  const TinyVectorBase <MultiArrayIndex, N, D3, D4> & coordinate)
288  {
289  return coordinate[N-1];
290  }
291 };
292 
293 /********************************************************/
294 /* */
295 /* ScanOrderToCoordinate */
296 /* */
297 /********************************************************/
298 
299  /* Convert scan-order index to multi-dimensional index (i.e. a grid coordinate).
300  */
301 template <int K>
302 struct ScanOrderToCoordinate
303 {
304  template <int N>
305  static void
306  exec(MultiArrayIndex d, const TinyVector <MultiArrayIndex, N> &shape,
307  TinyVector <MultiArrayIndex, N> & result)
308  {
309  result[N-K] = (d % shape[N-K]);
310  ScanOrderToCoordinate<K-1>::exec(d / shape[N-K], shape, result);
311  }
312 };
313 
314 template <>
315 struct ScanOrderToCoordinate<1>
316 {
317  template <int N>
318  static void
319  exec(MultiArrayIndex d, const TinyVector <MultiArrayIndex, N> & /*shape*/,
320  TinyVector <MultiArrayIndex, N> & result)
321  {
322  result[N-1] = d;
323  }
324 };
325 
326 /********************************************************/
327 /* */
328 /* ScanOrderToOffset */
329 /* */
330 /********************************************************/
331 
332  /* transforms an index in scan order sense to a pointer offset in a possibly
333  strided, multi-dimensional array.
334  */
335 template <int K>
336 struct ScanOrderToOffset
337 {
338  template <int N>
339  static MultiArrayIndex
340  exec(MultiArrayIndex d, const TinyVector <MultiArrayIndex, N> &shape,
341  const TinyVector <MultiArrayIndex, N> & stride)
342  {
343  return stride[N-K] * (d % shape[N-K]) +
344  ScanOrderToOffset<K-1>::exec(d / shape[N-K], shape, stride);
345  }
346 };
347 
348 template <>
349 struct ScanOrderToOffset<1>
350 {
351  template <int N>
352  static MultiArrayIndex
353  exec(MultiArrayIndex d, const TinyVector <MultiArrayIndex, N> & /*shape*/,
354  const TinyVector <MultiArrayIndex, N> & stride)
355  {
356  return stride[N-1] * d;
357  }
358 };
359 
360 /********************************************************/
361 /* */
362 /* ScanOrderToOffset */
363 /* */
364 /********************************************************/
365 
366  /* transforms a multi-dimensional index (grid coordinate) to a pointer offset in a possibly
367  strided, multi-dimensional array.
368  */
369 template <class C>
370 struct CoordinatesToOffest
371 {
372  template <int N>
373  static MultiArrayIndex
374  exec(const TinyVector <MultiArrayIndex, N> & stride, MultiArrayIndex x)
375  {
376  return stride[0] * x;
377  }
378  template <int N>
379  static MultiArrayIndex
380  exec(const TinyVector <MultiArrayIndex, N> & stride, MultiArrayIndex x, MultiArrayIndex y)
381  {
382  return stride[0] * x + stride[1] * y;
383  }
384 };
385 
386 template <>
387 struct CoordinatesToOffest<UnstridedArrayTag>
388 {
389  template <int N>
390  static MultiArrayIndex
391  exec(const TinyVector <MultiArrayIndex, N> & /*stride*/, MultiArrayIndex x)
392  {
393  return x;
394  }
395  template <int N>
396  static MultiArrayIndex
397  exec(const TinyVector <MultiArrayIndex, N> & stride, MultiArrayIndex x, MultiArrayIndex y)
398  {
399  return x + stride[1] * y;
400  }
401 };
402 
403 /********************************************************/
404 /* */
405 /* RelativeToAbsoluteCoordinate */
406 /* */
407 /********************************************************/
408 
409  /* transforms a coordinate object with negative indices into the corresponding
410  'shape - abs(index)'.
411  */
412 template <int M>
413 struct RelativeToAbsoluteCoordinate
414 {
415  template <int N>
416  static void
417  exec(const TinyVector<MultiArrayIndex, N> & shape, TinyVector<MultiArrayIndex, N> & coord)
418  {
419  RelativeToAbsoluteCoordinate<M-1>::exec(shape, coord);
420  if(coord[M] < 0)
421  coord[M] += shape[M];
422  }
423 };
424 
425 template <>
426 struct RelativeToAbsoluteCoordinate<0>
427 {
428  template <int N>
429  static void
430  exec(const TinyVector<MultiArrayIndex, N> & shape, TinyVector<MultiArrayIndex, N> & coord)
431  {
432  if(coord[0] < 0)
433  coord[0] += shape[0];
434  }
435 };
436 
437 /********************************************************/
438 /* */
439 /* BorderTypeImpl */
440 /* */
441 /********************************************************/
442 
443 // a border type is a compact bit-wise encoding of the fact that a
444 // given coordinate is at the border of the ROI. Each border corresponds
445 // to one bit in the encoding, e.g. the left, right, top, bottom borders
446 // of a 2D image are represented by bits 0 to 3 respectively.
447 // If a bit is set, the point in question is at the corresponding border.
448 // A code of all zeros therefore means that the point is in the interior
449 // of the ROI
450 template <unsigned int N, unsigned int DIMENSION=N-1>
451 struct BorderTypeImpl
452 {
453  typedef typename MultiArrayShape<N>::type shape_type;
454 
455  static unsigned int exec(shape_type const & point, shape_type const & shape)
456  {
457  unsigned int res = BorderTypeImpl<N, DIMENSION-1>::exec(point, shape);
458  if(point[DIMENSION] == 0)
459  res |= (1 << 2*DIMENSION);
460  if(point[DIMENSION] == shape[DIMENSION]-1)
461  res |= (2 << 2*DIMENSION);
462  return res;
463  }
464 };
465 
466 template <unsigned int N>
467 struct BorderTypeImpl<N, 0>
468 {
469  typedef typename MultiArrayShape<N>::type shape_type;
470  static const unsigned int DIMENSION = 0;
471 
472  static unsigned int exec(shape_type const & point, shape_type const & shape)
473  {
474  unsigned int res = 0;
475  if(point[DIMENSION] == 0)
476  res |= (1 << 2*DIMENSION);
477  if(point[DIMENSION] == shape[DIMENSION]-1)
478  res |= (2 << 2*DIMENSION);
479  return res;
480  }
481 };
482 
483 /********************************************************/
484 /* */
485 /* makeArrayNeighborhood */
486 /* */
487 /********************************************************/
488 
489 // Create the offsets to all direct neighbors, starting from the given Level (=dimension)
490 // and append them to the given array. The algorithm is designed so that the offsets are
491 // sorted by ascending strides. This has two important consequences:
492 // * The first half of the array contains the causal neighbors (negative strides),
493 // the second half the anti-causal ones (positive strides), where 'causal' refers
494 // to all scan-order predecessors of the center pixel, and 'anticausal' to its successors.
495 // * For any neighbor k, its opposite (=point-reflected) neighbor is located at index
496 // 'N-1-k', where N is the total number of neighbors.
497 // The function 'exists' returns an array of flags that contains 'true' when the corresponding
498 // neighbor is inside the ROI for the given borderType, 'false' otherwise.
499 template <unsigned int Level>
500 struct MakeDirectArrayNeighborhood
501 {
502  template <class Array>
503  static void offsets(Array & a)
504  {
505  typedef typename Array::value_type Shape;
506 
507  Shape point;
508  point[Level] = -1;
509  a.push_back(point);
510  MakeDirectArrayNeighborhood<Level-1>::offsets(a);
511  point[Level] = 1;
512  a.push_back(point);
513  }
514 
515  template <class Array>
516  static void exists(Array & a, unsigned int borderType)
517  {
518  a.push_back((borderType & (1 << 2*Level)) == 0);
519  MakeDirectArrayNeighborhood<Level-1>::exists(a, borderType);
520  a.push_back((borderType & (2 << 2*Level)) == 0);
521  }
522 };
523 
524 template <>
525 struct MakeDirectArrayNeighborhood<0>
526 {
527  template <class Array>
528  static void offsets(Array & a)
529  {
530  typedef typename Array::value_type Shape;
531 
532  Shape point;
533  point[0] = -1;
534  a.push_back(point);
535  point[0] = 1;
536  a.push_back(point);
537  }
538 
539  template <class Array>
540  static void exists(Array & a, unsigned int borderType)
541  {
542  a.push_back((borderType & 1) == 0);
543  a.push_back((borderType & 2) == 0);
544  }
545 };
546 
547 // Likewise, create the offsets to all indirect neighbors according to the same rules.
548 template <unsigned int Level>
549 struct MakeIndirectArrayNeighborhood
550 {
551  template <class Array, class Shape>
552  static void offsets(Array & a, Shape point, bool isCenter = true)
553  {
554  point[Level] = -1;
555  MakeIndirectArrayNeighborhood<Level-1>::offsets(a, point, false);
556  point[Level] = 0;
557  MakeIndirectArrayNeighborhood<Level-1>::offsets(a, point, isCenter);
558  point[Level] = 1;
559  MakeIndirectArrayNeighborhood<Level-1>::offsets(a, point, false);
560  }
561 
562  template <class Array>
563  static void exists(Array & a, unsigned int borderType, bool isCenter = true)
564  {
565  if((borderType & (1 << 2*Level)) == 0)
566  MakeIndirectArrayNeighborhood<Level-1>::exists(a, borderType, false);
567  else
568  MakeIndirectArrayNeighborhood<Level-1>::markOutside(a);
569 
570  MakeIndirectArrayNeighborhood<Level-1>::exists(a, borderType, isCenter);
571 
572  if((borderType & (2 << 2*Level)) == 0)
573  MakeIndirectArrayNeighborhood<Level-1>::exists(a, borderType, false);
574  else
575  MakeIndirectArrayNeighborhood<Level-1>::markOutside(a);
576  }
577 
578  template <class Array>
579  static void markOutside(Array & a)
580  {
581  // Call markOutside() three times, for each possible offset at (Level-1)
582  MakeIndirectArrayNeighborhood<Level-1>::markOutside(a);
583  MakeIndirectArrayNeighborhood<Level-1>::markOutside(a);
584  MakeIndirectArrayNeighborhood<Level-1>::markOutside(a);
585  }
586 
587 };
588 
589 template <>
590 struct MakeIndirectArrayNeighborhood<0>
591 {
592  template <class Array, class Shape>
593  static void offsets(Array & a, Shape point, bool isCenter = true)
594  {
595  point[0] = -1;
596  a.push_back(point);
597  if(!isCenter) // the center point is not a neighbor, it's just convenient to do the enumeration this way...
598  {
599  point[0] = 0;
600  a.push_back(point);
601  }
602  point[0] = 1;
603  a.push_back(point);
604  }
605 
606  template <class Array>
607  static void exists(Array & a, unsigned int borderType, bool isCenter = true)
608  {
609  a.push_back((borderType & 1) == 0);
610  if(!isCenter)
611  {
612  a.push_back(true);
613  }
614  a.push_back((borderType & 2) == 0);
615  }
616 
617  template <class Array>
618  static void markOutside(Array & a)
619  {
620  // Push 'false' three times, for each possible offset at level 0, whenever the point was
621  // outside the ROI in one of the higher levels.
622  a.push_back(false);
623  a.push_back(false);
624  a.push_back(false);
625  }
626 };
627 
628 // Create the list of neighbor offsets for the given neighborhood type
629 // and dimension (the dimension is implicitly defined by the Shape type)
630 // an return it in 'neighborOffsets'. Moreover, create a list of flags
631 // for each BorderType that is 'true' when the corresponding neighbor exists
632 // in this border situation and return the result in 'neighborExists'.
633 template <class Shape>
634 void
635 makeArrayNeighborhood(ArrayVector<Shape> & neighborOffsets,
636  ArrayVector<ArrayVector<bool> > & neighborExists,
637  NeighborhoodType neighborhoodType = DirectNeighborhood)
638 {
639  enum { N = Shape::static_size };
640 
641  neighborOffsets.clear();
642  if(neighborhoodType == DirectNeighborhood)
643  {
644  MakeDirectArrayNeighborhood<N-1>::offsets(neighborOffsets);
645  }
646  else
647  {
648  Shape point; // represents the center
649  MakeIndirectArrayNeighborhood<N-1>::offsets(neighborOffsets, point);
650  }
651 
652  unsigned int borderTypeCount = 1 << 2*N;
653  neighborExists.resize(borderTypeCount);
654 
655  for(unsigned int k=0; k<borderTypeCount; ++k)
656  {
657  neighborExists[k].clear();
658  if(neighborhoodType == DirectNeighborhood)
659  {
660  MakeDirectArrayNeighborhood<N-1>::exists(neighborExists[k], k);
661  }
662  else
663  {
664  MakeIndirectArrayNeighborhood<N-1>::exists(neighborExists[k], k);
665  }
666  }
667 }
668 
669 } // namespace detail
670 
671 //@}
672 
673 } // namespace vigra
674 
675 #endif // VIGRA_MULTI_SHAPE_HXX

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de)
Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany

html generated using doxygen and Python
vigra 1.10.0