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

multi_shape.hxx
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 "multi_fwd.hxx"
40#include <sys/types.h>
41#include "tinyvector.hxx"
42#include "array_vector.hxx"
43#include "numerictraits.hxx"
44
45namespace vigra {
46
47/** \addtogroup RangesAndPoints
48*/
49//@{
50
51/********************************************************/
52/* */
53/* Singleband and Multiband */
54/* */
55/********************************************************/
56
57template <class T>
58struct Singleband // the resulting MultiArray has no explicit channel axis
59 // (i.e. the number of channels is implicitly one)
60{
61 typedef T value_type;
62};
63
64template <class T>
65struct Multiband // the last axis is explicitly designated as channel axis
66{
67 typedef T value_type;
68};
69
70// check if a type is a multiband type
71template<class T>
72struct IsMultiband : VigraFalseType{
73};
74
75template<class T>
76struct IsMultiband<Multiband<T> > : VigraTrueType{
77};
78
79template <class T>
80struct ChunkedMemory // the array is organised in chunks
81{
82 typedef T value_type;
83};
84
85template<class T>
86struct NumericTraits<Singleband<T> >
87: public NumericTraits<T>
88{};
89
90template<class T>
91struct NumericTraits<Multiband<T> >
92{
93 typedef Multiband<T> Type;
94/*
95 typedef int Promote;
96 typedef unsigned int UnsignedPromote;
97 typedef double RealPromote;
98 typedef std::complex<RealPromote> ComplexPromote;
99*/
100 typedef Type ValueType;
101
102 typedef typename NumericTraits<T>::isIntegral isIntegral;
103 typedef VigraFalseType isScalar;
104 typedef typename NumericTraits<T>::isSigned isSigned;
105 typedef typename NumericTraits<T>::isSigned isOrdered;
106 typedef typename NumericTraits<T>::isSigned isComplex;
107/*
108 static signed char zero() { return 0; }
109 static signed char one() { return 1; }
110 static signed char nonZero() { return 1; }
111 static signed char min() { return SCHAR_MIN; }
112 static signed char max() { return SCHAR_MAX; }
113
114#ifdef NO_INLINE_STATIC_CONST_DEFINITION
115 enum { minConst = SCHAR_MIN, maxConst = SCHAR_MIN };
116#else
117 static const signed char minConst = SCHAR_MIN;
118 static const signed char maxConst = SCHAR_MIN;
119#endif
120
121 static Promote toPromote(signed char v) { return v; }
122 static RealPromote toRealPromote(signed char v) { return v; }
123 static signed char fromPromote(Promote v) {
124 return ((v < SCHAR_MIN) ? SCHAR_MIN : (v > SCHAR_MAX) ? SCHAR_MAX : v);
125 }
126 static signed char fromRealPromote(RealPromote v) {
127 return ((v < 0.0)
128 ? ((v < (RealPromote)SCHAR_MIN)
129 ? SCHAR_MIN
130 : static_cast<signed char>(v - 0.5))
131 : (v > (RealPromote)SCHAR_MAX)
132 ? SCHAR_MAX
133 : static_cast<signed char>(v + 0.5));
134 }
135*/
136};
137
138namespace detail {
139
140/********************************************************/
141/* */
142/* defaultStride */
143/* */
144/********************************************************/
145
146 /* generates the stride for a gapless shape.
147 */
148template <int N>
149inline TinyVector <MultiArrayIndex, N>
150defaultStride(const TinyVector <MultiArrayIndex, N> &shape)
151{
152 TinyVector <MultiArrayIndex, N> ret;
153 ret [0] = 1;
154 for (int i = 1; i < (int)N; ++i)
155 ret [i] = ret [i-1] * shape [i-1];
156 return ret;
157}
158
159 /* generates the stride for a gapless shape.
160 */
161template <int N>
162inline TinyVector <MultiArrayIndex, N>
163defaultMultibandStride(const TinyVector <MultiArrayIndex, N> &shape)
164{
165 TinyVector <MultiArrayIndex, N> ret;
166 ret [N-1] = 1;
167 for (int i = 0; i < (int)N-1; ++i)
168 {
169 int j = (i + int(N - 1)) % N;
170 ret [i] = ret [j] * shape [j];
171 }
172 return ret;
173}
174
175/********************************************************/
176/* */
177/* resolve Multiband and ChunkedMemory tags */
178/* */
179/********************************************************/
180
181template <class T>
182struct ResolveMultiband
183{
184 typedef T type;
185 typedef StridedArrayTag Stride;
186 static const bool value = false;
187
188 template <int N>
189 static TinyVector <MultiArrayIndex, N>
190 defaultStride(const TinyVector <MultiArrayIndex, N> &shape)
191 {
192 return vigra::detail::defaultStride(shape);
193 }
194};
195
196template <class T>
197struct ResolveMultiband<Singleband<T> >
198{
199 typedef T type;
200 typedef StridedArrayTag Stride;
201 static const bool value = false;
202
203 template <int N>
204 static TinyVector <MultiArrayIndex, N>
205 defaultStride(const TinyVector <MultiArrayIndex, N> &shape)
206 {
207 return vigra::detail::defaultStride(shape);
208 }
209};
210
211template <class T>
212struct ResolveMultiband<Multiband<T> >
213{
214 typedef T type;
215 typedef StridedArrayTag Stride;
216 static const bool value = true;
217
218 template <int N>
219 static TinyVector <MultiArrayIndex, N>
220 defaultStride(const TinyVector <MultiArrayIndex, N> &shape)
221 {
222 return vigra::detail::defaultMultibandStride(shape);
223 }
224};
225
226template <class T>
227struct ResolveChunkedMemory
228{
229 typedef T type;
230};
231
232template <class T>
233struct ResolveChunkedMemory<ChunkedMemory<T> >
234{
235 typedef T type;
236};
237
238} // namespace detail
239
240 /** Metafucntion to obtain the difference type of all MultiIterator, MultiArrayView, and
241 MultiArray variants.
242
243 <b>Usage:</b>
244
245 This metafunction is mainly used in functions weren the array dimension <tt>N</tt> is
246 provided as a templat parameter, and we need a shape object of the corresponding length.
247 Then, a typedef like this is typically placed at the beginning of the function:
248
249 \code
250 typedef typename MultiArrayShape<N>::type Shape;
251
252 Shape shape(1); // all ones of dimension N
253 \endcode
254
255 The following typedefs are provided for convenience:
256
257 \code
258 typedef MultiArrayShape<1>::type Shape1;
259 typedef MultiArrayShape<2>::type Shape2;
260 typedef MultiArrayShape<3>::type Shape3;
261 typedef MultiArrayShape<4>::type Shape4;
262 typedef MultiArrayShape<5>::type Shape5;
263 \endcode
264 */
265template <unsigned int N>
267{
268 public:
269 /** The difference type of all MultiIterator, MultiArrayView, and
270 MultiArray variants.
271 */
273};
274
276typedef MultiArrayShape<2>::type Shape2;
280
281namespace detail
282{
283
284/********************************************************/
285/* */
286/* default chunk shapes */
287/* */
288/********************************************************/
289
290template <unsigned int N, class T = int>
291struct ChunkShape
292{
293 typedef typename MultiArrayShape<N>::type Shape;
294 static Shape defaultShape()
295 {
296 Shape res(1);
297 res.template subarray<0,5>() = ChunkShape<5,T>::defaultShape();
298 return res;
299 }
300};
301
302template <class T>
303struct ChunkShape<0, T>
304{
305 static Shape1 defaultShape()
306 {
307 return Shape1(1);
308 }
309};
310
311template <class T>
312struct ChunkShape<1, T>
313{
314 static Shape1 defaultShape()
315 {
316 return Shape1(1 << 18);
317 }
318};
319
320template <class T>
321struct ChunkShape<2, T>
322{
323 static Shape2 defaultShape()
324 {
325 return Shape2(1 << 9, 1 << 9);
326 }
327};
328
329template <class T>
330struct ChunkShape<3, T>
331{
332 static Shape3 defaultShape()
333 {
334 return Shape3(1 << 6, 1 << 6, 1 << 6);
335 }
336};
337
338template <class T>
339struct ChunkShape<4, T>
340{
341 static Shape4 defaultShape()
342 {
343 return Shape4(1 << 6, 1 << 6, 1 << 4, 1 << 2);
344 }
345};
346
347template <class T>
348struct ChunkShape<5, T>
349{
350 static Shape5 defaultShape()
351 {
352 return Shape5(1 << 6, 1 << 6, 1 << 4, 1 << 2, 1 << 2);
353 }
354};
355
356} // namespace detail
357
358// Helper functions
359
360namespace detail {
361
362/********************************************************/
363/* */
364/* CoordinateToScanOrder */
365/* */
366/********************************************************/
367
368 /* Convert multi-dimensional index (i.e. a grid coordinate) to scan-order index.
369 */
370template <int K>
371struct CoordinateToScanOrder
372{
373 template <int N, class D1, class D2, class D3, class D4>
374 static MultiArrayIndex
375 exec(const TinyVectorBase <MultiArrayIndex, N, D1, D2> &shape,
376 const TinyVectorBase <MultiArrayIndex, N, D3, D4> & coordinate)
377 {
378 return coordinate[N-K] + shape[N-K] * CoordinateToScanOrder<K-1>::exec(shape, coordinate);
379 }
380};
381
382template <>
383struct CoordinateToScanOrder<1>
384{
385 template <int N, class D1, class D2, class D3, class D4>
386 static MultiArrayIndex
387 exec(const TinyVectorBase <MultiArrayIndex, N, D1, D2> & /*shape*/,
388 const TinyVectorBase <MultiArrayIndex, N, D3, D4> & coordinate)
389 {
390 return coordinate[N-1];
391 }
392};
393
394/********************************************************/
395/* */
396/* ScanOrderToCoordinate */
397/* */
398/********************************************************/
399
400 /* Convert scan-order index to multi-dimensional index (i.e. a grid coordinate).
401 */
402template <int K>
403struct ScanOrderToCoordinate
404{
405 template <int N>
406 static void
407 exec(MultiArrayIndex d, const TinyVector <MultiArrayIndex, N> &shape,
408 TinyVector <MultiArrayIndex, N> & result)
409 {
410 result[N-K] = (d % shape[N-K]);
411 ScanOrderToCoordinate<K-1>::exec(d / shape[N-K], shape, result);
412 }
413};
414
415template <>
416struct ScanOrderToCoordinate<1>
417{
418 template <int N>
419 static void
420 exec(MultiArrayIndex d, const TinyVector <MultiArrayIndex, N> & /*shape*/,
421 TinyVector <MultiArrayIndex, N> & result)
422 {
423 result[N-1] = d;
424 }
425};
426
427/********************************************************/
428/* */
429/* ScanOrderToOffset */
430/* */
431/********************************************************/
432
433 /* transforms an index in scan order sense to a pointer offset in a possibly
434 strided, multi-dimensional array.
435 */
436template <int K>
437struct ScanOrderToOffset
438{
439 template <int N>
440 static MultiArrayIndex
441 exec(MultiArrayIndex d, const TinyVector <MultiArrayIndex, N> &shape,
442 const TinyVector <MultiArrayIndex, N> & stride)
443 {
444 return stride[N-K] * (d % shape[N-K]) +
445 ScanOrderToOffset<K-1>::exec(d / shape[N-K], shape, stride);
446 }
447};
448
449template <>
450struct ScanOrderToOffset<1>
451{
452 template <int N>
453 static MultiArrayIndex
454 exec(MultiArrayIndex d, const TinyVector <MultiArrayIndex, N> & /*shape*/,
455 const TinyVector <MultiArrayIndex, N> & stride)
456 {
457 return stride[N-1] * d;
458 }
459};
460
461/********************************************************/
462/* */
463/* ScanOrderToOffset */
464/* */
465/********************************************************/
466
467 /* transforms a multi-dimensional index (grid coordinate) to a pointer offset in a possibly
468 strided, multi-dimensional array.
469 */
470template <class C>
471struct CoordinatesToOffest
472{
473 template <int N>
474 static MultiArrayIndex
475 exec(const TinyVector <MultiArrayIndex, N> & stride, MultiArrayIndex x)
476 {
477 return stride[0] * x;
478 }
479 template <int N>
480 static MultiArrayIndex
481 exec(const TinyVector <MultiArrayIndex, N> & stride, MultiArrayIndex x, MultiArrayIndex y)
482 {
483 return stride[0] * x + stride[1] * y;
484 }
485};
486
487template <>
488struct CoordinatesToOffest<UnstridedArrayTag>
489{
490 template <int N>
491 static MultiArrayIndex
492 exec(const TinyVector <MultiArrayIndex, N> & /*stride*/, MultiArrayIndex x)
493 {
494 return x;
495 }
496 template <int N>
497 static MultiArrayIndex
498 exec(const TinyVector <MultiArrayIndex, N> & stride, MultiArrayIndex x, MultiArrayIndex y)
499 {
500 return x + stride[1] * y;
501 }
502};
503
504/********************************************************/
505/* */
506/* RelativeToAbsoluteCoordinate */
507/* */
508/********************************************************/
509
510 /* transforms a coordinate object with negative indices into the corresponding
511 'shape - abs(index)'.
512 */
513template <int M>
514struct RelativeToAbsoluteCoordinate
515{
516 template <int N>
517 static void
518 exec(const TinyVector<MultiArrayIndex, N> & shape, TinyVector<MultiArrayIndex, N> & coord)
519 {
520 RelativeToAbsoluteCoordinate<M-1>::exec(shape, coord);
521 if(coord[M] < 0)
522 coord[M] += shape[M];
523 }
524};
525
526template <>
527struct RelativeToAbsoluteCoordinate<0>
528{
529 template <int N>
530 static void
531 exec(const TinyVector<MultiArrayIndex, N> & shape, TinyVector<MultiArrayIndex, N> & coord)
532 {
533 if(coord[0] < 0)
534 coord[0] += shape[0];
535 }
536};
537
538/********************************************************/
539/* */
540/* BorderTypeImpl */
541/* */
542/********************************************************/
543
544// a border type is a compact bit-wise encoding of the fact that a
545// given coordinate is at the border of the ROI. Each border corresponds
546// to one bit in the encoding, e.g. the left, right, top, bottom borders
547// of a 2D image are represented by bits 0 to 3 respectively.
548// If a bit is set, the point in question is at the corresponding border.
549// A code of all zeros therefore means that the point is in the interior
550// of the ROI
551template <unsigned int N, unsigned int DIMENSION=N-1>
552struct BorderTypeImpl
553{
554 typedef TinyVectorView<MultiArrayIndex, N> shape_type;
555
556 static unsigned int exec(shape_type const & point, shape_type const & shape)
557 {
558 unsigned int res = BorderTypeImpl<N, DIMENSION-1>::exec(point, shape);
559 if(point[DIMENSION] == 0)
560 res |= (1 << 2*DIMENSION);
561 if(point[DIMENSION] == shape[DIMENSION]-1)
562 res |= (2 << 2*DIMENSION);
563 return res;
564 }
565};
566
567template <unsigned int N>
568struct BorderTypeImpl<N, 0>
569{
570 typedef TinyVectorView<MultiArrayIndex, N> shape_type;
571 static const unsigned int DIMENSION = 0;
572
573 static unsigned int exec(shape_type const & point, shape_type const & shape)
574 {
575 unsigned int res = 0;
576 if(point[DIMENSION] == 0)
577 res |= (1 << 2*DIMENSION);
578 if(point[DIMENSION] == shape[DIMENSION]-1)
579 res |= (2 << 2*DIMENSION);
580 return res;
581 }
582};
583
584/********************************************************/
585/* */
586/* makeArrayNeighborhood */
587/* */
588/********************************************************/
589
590// Create the offsets to all direct neighbors, starting from the given Level (=dimension)
591// and append them to the given array. The algorithm is designed so that the offsets are
592// sorted by ascending strides. This has two important consequences:
593// * The first half of the array contains the causal neighbors (negative strides),
594// the second half the anti-causal ones (positive strides), where 'causal' refers
595// to all scan-order predecessors of the center pixel, and 'anticausal' to its successors.
596// * For any neighbor k, its opposite (=point-reflected) neighbor is located at index
597// 'N-1-k', where N is the total number of neighbors.
598// The function 'exists' returns an array of flags that contains 'true' when the corresponding
599// neighbor is inside the ROI for the given borderType, 'false' otherwise.
600template <unsigned int Level>
601struct MakeDirectArrayNeighborhood
602{
603 template <class Array>
604 static void offsets(Array & a)
605 {
606 typedef typename Array::value_type Shape;
607
608 Shape point;
609 point[Level] = -1;
610 a.push_back(point);
611 MakeDirectArrayNeighborhood<Level-1>::offsets(a);
612 point[Level] = 1;
613 a.push_back(point);
614 }
615
616 template <class Array>
617 static void exists(Array & a, unsigned int borderType)
618 {
619 a.push_back((borderType & (1 << 2*Level)) == 0);
620 MakeDirectArrayNeighborhood<Level-1>::exists(a, borderType);
621 a.push_back((borderType & (2 << 2*Level)) == 0);
622 }
623};
624
625template <>
626struct MakeDirectArrayNeighborhood<0>
627{
628 template <class Array>
629 static void offsets(Array & a)
630 {
631 typedef typename Array::value_type Shape;
632
633 Shape point;
634 point[0] = -1;
635 a.push_back(point);
636 point[0] = 1;
637 a.push_back(point);
638 }
639
640 template <class Array>
641 static void exists(Array & a, unsigned int borderType)
642 {
643 a.push_back((borderType & 1) == 0);
644 a.push_back((borderType & 2) == 0);
645 }
646};
647
648// Likewise, create the offsets to all indirect neighbors according to the same rules.
649template <unsigned int Level>
650struct MakeIndirectArrayNeighborhood
651{
652 template <class Array, class Shape>
653 static void offsets(Array & a, Shape point, bool isCenter = true)
654 {
655 point[Level] = -1;
656 MakeIndirectArrayNeighborhood<Level-1>::offsets(a, point, false);
657 point[Level] = 0;
658 MakeIndirectArrayNeighborhood<Level-1>::offsets(a, point, isCenter);
659 point[Level] = 1;
660 MakeIndirectArrayNeighborhood<Level-1>::offsets(a, point, false);
661 }
662
663 template <class Array>
664 static void exists(Array & a, unsigned int borderType, bool isCenter = true)
665 {
666 if((borderType & (1 << 2*Level)) == 0)
667 MakeIndirectArrayNeighborhood<Level-1>::exists(a, borderType, false);
668 else
669 MakeIndirectArrayNeighborhood<Level-1>::markOutside(a);
670
671 MakeIndirectArrayNeighborhood<Level-1>::exists(a, borderType, isCenter);
672
673 if((borderType & (2 << 2*Level)) == 0)
674 MakeIndirectArrayNeighborhood<Level-1>::exists(a, borderType, false);
675 else
676 MakeIndirectArrayNeighborhood<Level-1>::markOutside(a);
677 }
678
679 template <class Array>
680 static void markOutside(Array & a)
681 {
682 // Call markOutside() three times, for each possible offset at (Level-1)
683 MakeIndirectArrayNeighborhood<Level-1>::markOutside(a);
684 MakeIndirectArrayNeighborhood<Level-1>::markOutside(a);
685 MakeIndirectArrayNeighborhood<Level-1>::markOutside(a);
686 }
687
688};
689
690template <>
691struct MakeIndirectArrayNeighborhood<0>
692{
693 template <class Array, class Shape>
694 static void offsets(Array & a, Shape point, bool isCenter = true)
695 {
696 point[0] = -1;
697 a.push_back(point);
698 if(!isCenter) // the center point is not a neighbor, it's just convenient to do the enumeration this way...
699 {
700 point[0] = 0;
701 a.push_back(point);
702 }
703 point[0] = 1;
704 a.push_back(point);
705 }
706
707 template <class Array>
708 static void exists(Array & a, unsigned int borderType, bool isCenter = true)
709 {
710 a.push_back((borderType & 1) == 0);
711 if(!isCenter)
712 {
713 a.push_back(true);
714 }
715 a.push_back((borderType & 2) == 0);
716 }
717
718 template <class Array>
719 static void markOutside(Array & a)
720 {
721 // Push 'false' three times, for each possible offset at level 0, whenever the point was
722 // outside the ROI in one of the higher levels.
723 a.push_back(false);
724 a.push_back(false);
725 a.push_back(false);
726 }
727};
728
729// Create the list of neighbor offsets for the given neighborhood type
730// and dimension (the dimension is implicitly defined by the Shape type)
731// an return it in 'neighborOffsets'. Moreover, create a list of flags
732// for each BorderType that is 'true' when the corresponding neighbor exists
733// in this border situation and return the result in 'neighborExists'.
734template <class Shape>
735void
736makeArrayNeighborhood(ArrayVector<Shape> & neighborOffsets,
737 ArrayVector<ArrayVector<bool> > & neighborExists,
738 NeighborhoodType neighborhoodType = DirectNeighborhood)
739{
740 enum { N = Shape::static_size };
741
742 neighborOffsets.clear();
743 if(neighborhoodType == DirectNeighborhood)
744 {
745 MakeDirectArrayNeighborhood<N-1>::offsets(neighborOffsets);
746 }
747 else
748 {
749 Shape point; // represents the center
750 MakeIndirectArrayNeighborhood<N-1>::offsets(neighborOffsets, point);
751 }
752
753 unsigned int borderTypeCount = 1 << 2*N;
754 neighborExists.resize(borderTypeCount);
755
756 for(unsigned int k=0; k<borderTypeCount; ++k)
757 {
758 neighborExists[k].clear();
759 if(neighborhoodType == DirectNeighborhood)
760 {
761 MakeDirectArrayNeighborhood<N-1>::exists(neighborExists[k], k);
762 }
763 else
764 {
765 MakeIndirectArrayNeighborhood<N-1>::exists(neighborExists[k], k);
766 }
767 }
768}
769
770} // namespace detail
771
772//@}
773
774} // namespace vigra
775
776#endif // VIGRA_MULTI_SHAPE_HXX
Definition multi_shape.hxx:267
TinyVector< MultiArrayIndex, N > type
Definition multi_shape.hxx:272
Class for a single RGB value.
Definition rgbvalue.hxx:128
Class for fixed size vectors.
Definition tinyvector.hxx:1008
NeighborhoodType
Choose the neighborhood system in a dimension-independent way.
Definition multi_fwd.hxx:186
@ DirectNeighborhood
use only direct neighbors
Definition multi_fwd.hxx:187
std::ptrdiff_t MultiArrayIndex
Definition multi_fwd.hxx:60

© 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.12.2