1 /************************************************************************/ 2 /* */ 3 /* Copyright 2011-2012 by 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_ACCUMULATOR_GRAMMAR_HXX 37 #define VIGRA_ACCUMULATOR_GRAMMAR_HXX 38 39 #ifdef _MSC_VER 40 #pragma warning (disable: 4503) 41 #endif 42 43 #include "config.hxx" 44 #include "metaprogramming.hxx" 45 46 namespace vigra { 47 48 namespace acc { 49 50 /**************************************************************************/ 51 /* */ 52 /* irreducible basic accumulators */ 53 /* */ 54 /**************************************************************************/ 55 56 57 class CoordinateSystem; // returns an identity matrix of appropriate size 58 59 template <unsigned N> class PowerSum; // sum over powers of values 60 template <unsigned N> class AbsPowerSum; // sum over powers of absolute values 61 62 class Skewness; // skewness 63 class UnbiasedSkewness; // unbiased estimator for skewness 64 class Kurtosis; // excess kurtosis 65 class UnbiasedKurtosis; // unbiased estimator for excess kurtosis 66 class FlatScatterMatrix; // flattened upper-triangular part of the scatter matrix 67 class ScatterMatrixEigensystem; // eigenvalues and eigenvectors of the scatter matrix 68 69 // in all histogram classes: set bin count at runtime if BinCount == 0 70 template <int BinCount> class IntegerHistogram; // use data values directly as bin indices 71 template <int BinCount> class UserRangeHistogram; // set min/max explicitly at runtime 72 template <int BinCount> class AutoRangeHistogram; // get min/max from accumulators 73 template <int BinCount> class GlobalRangeHistogram; // like AutoRangeHistogram, but use global min/max rather than region min/max 74 75 class FirstSeen; // remember the first value seen 76 class Minimum; // minimum 77 class Maximum; // maximum 78 class Range; // minimum and maximum as a <tt>std::pair</tt> 79 template <class Hist> class StandardQuantiles; // compute (min, 10%, 25%, 50%, 75%, 90%, max) quantiles from 80 // min/max accumulators and given histogram 81 82 class ArgMinWeight; // store the value (or coordinate) where weight was minimal 83 class ArgMaxWeight; // store the value (or coordinate) where weight was maximal 84 85 // FIXME: not yet implemented 86 template <unsigned NDim> class MultiHistogram; // multi-dimensional histogram 87 // (always specify number of bins at runtime) 88 89 class Centralize; // cache centralized values 90 class PrincipalProjection; // cache values after principal projection 91 // FIXME: not yet implemented 92 class Whiten; // cache values after whitening 93 class RangeMapping; // map value from [min, max] to another range and cache result (e.g. for histogram creation) 94 95 template <int INDEX> class DataArg; // specifiy the index of the data member in a CoupledHandle 96 template <int INDEX> class WeightArg; // specifiy the index of the weight member in a CoupledHandle 97 template <int INDEX> class LabelArg; // specifiy the index of the label member in a CoupledHandle 98 template <int INDEX> class CoordArg; // specifiy the index of the coord member in a CoupledHandle 99 100 class RegionContour; // compute the contour of a 2D region 101 class RegionPerimeter; // compute the perimeter of a 2D region 102 class RegionCircularity; // compare perimeter of a 2D region with a circle of same area 103 class RegionEccentricity; // ecentricity of a 2D region from major and minor axis 104 105 #ifdef WITH_LEMON 106 class ConvexHull; // base class for convex hull computation 107 class ConvexHullFeatures; // base class for convex hull features 108 #endif 109 110 /* 111 Quantiles other than minimum and maximum require more thought: 112 -------------------------------------------------------------- 113 * Exact quantiles can be found in time O(n) using recursive partitioning (quickselect), 114 but this requires the data (or an auxiliary index array) to be re-arranged. 115 * Exact quantiles can be found in time O(k*n) using recursive histogram refinement, 116 were k = O(log(n)/log(BinCount)) is the expected number of required passes over the 117 data, provided that bins are filled approximately evenly. If data can be re-arranged, 118 such that we remember the items corresponding to each bin, running time reduces to O(n) 119 (this is Tibshirani's 'binmedian' algorithm). For the median, Tibshirani proves that 120 the initial histogram only needs to cover the interval [Mean-StdDev, Mean+StdDev]. 121 * Both strategies can be combined: perform k passes to reduce bin size to about 122 n/(BinCount)^k, and then perform quickselect on an auxiliary array of size 123 O(n/(BinCount)^k) which has been filled during the final pass. 124 * Good approximate results can be obtained by early stopping of histogram refinement 125 (Tibshirani's 'binapprox' algorithm). A 2-pass algorithm for the median achieves 126 accuracy of StdDev/BinCount: Mean and StdDev are computed during pass 1, 127 and a histogram over [Mean-StdDev, Mean+StdDev] during pass 2. 128 * A 1-pass approximation method is described in Chen et al. However, it assumes that 129 samples arrive in random order which is usually not true in image data. 130 */ 131 132 /**************************************************************************/ 133 /* */ 134 /* modifiers for composite accumulators */ 135 /* */ 136 /**************************************************************************/ 137 138 // data normalization w.r.t. number of samples 139 template <class A> class DivideByCount; // A / count 140 template <class A> class RootDivideByCount; // sqrt(A / count) 141 template <class A> class DivideUnbiased; // A / (count - 1) 142 template <class A> class RootDivideUnbiased; // sqrt(A / (count - 1)) 143 144 // data access 145 template <class A> class Coord; // use pixel coordinate instead of pixel value (index 0 of CoupledHandle) 146 template <class A> class Weighted; // use (value, weight) pairs (index 1 and 2 of CoupledHandle) 147 template <class A> class CoordWeighted; // use (coord, weight) pairs(index 0 and end of CoupledHandle) 148 template <class A> class DataFromHandle; // extract data from index 1 of a CoupledHandle 149 150 // data preparation 151 template <class A> class Central; // subtract mean 152 template <class A> class Principal; // subtract mean and rotate to principal coordinates 153 154 // FIXME: not implemented yet 155 template <class A> class Whitened; // transform to principal coordinates and scale to unit variance 156 157 template <class A> class Global; // compute statistic A globally rather than per region 158 159 /**************************************************************************/ 160 /* */ 161 /* alias names for important features */ 162 /* */ 163 /**************************************************************************/ 164 165 /** \brief Alias. Count. */ 166 typedef PowerSum<0> Count; 167 /** \brief Alias. Sum. */ 168 typedef PowerSum<1> Sum; 169 /** \brief Alias. Sum of squares. */ 170 typedef PowerSum<2> SumOfSquares; 171 172 /** \brief Alias. Mean. */ 173 typedef DivideByCount<Sum> Mean; 174 /** \brief Alias. Root mean square. */ 175 typedef RootDivideByCount<SumOfSquares> RootMeanSquares; 176 177 // desired pseudocode (unfortunately not legal in C++) 178 // 179 // template <unsigned N> 180 // typedef DivideByCount<PowerSum<N> > Moment; 181 // 182 // actual definition (desired behavior is realised by rules below) 183 // 184 /** \brief Alias. Moment<N>. */ 185 template <unsigned N> class Moment; 186 /** \brief Alias. CentralMoment<N>. */ 187 template <unsigned N> class CentralMoment; 188 189 /** \brief Alias. Sum of squared differences. */ 190 typedef Central<PowerSum<2> > SumOfSquaredDifferences; 191 /** \brief Alias. Sum of squared differences. */ 192 typedef SumOfSquaredDifferences SSD; 193 194 /** \brief Alias. Variance. */ 195 typedef DivideByCount<Central<PowerSum<2> > > Variance; 196 /** \brief Alias. Standard deviation. */ 197 typedef RootDivideByCount<Central<PowerSum<2> > > StdDev; 198 /** \brief Alias. Unbiased variance. */ 199 typedef DivideUnbiased<Central<PowerSum<2> > > UnbiasedVariance; 200 /** \brief Alias. Unbiased standard deviation. */ 201 typedef RootDivideUnbiased<Central<PowerSum<2> > > UnbiasedStdDev; 202 203 /** \brief Alias. Covariance. */ 204 typedef DivideByCount<FlatScatterMatrix> Covariance; 205 /** \brief Alias. Unbiased covariance. */ 206 typedef DivideUnbiased<FlatScatterMatrix> UnbiasedCovariance; 207 /** \brief Alias. Covariance eigensystem. */ 208 typedef DivideByCount<ScatterMatrixEigensystem> CovarianceEigensystem; 209 210 /** \brief Alias. Absolute sum. */ 211 typedef AbsPowerSum<1> AbsSum; 212 /** \brief Alias. Sum of absolute differences. */ 213 typedef Central<AbsSum> SumOfAbsDifferences; 214 /** \brief Alias. Mean absolute deviation. */ 215 typedef DivideByCount<SumOfAbsDifferences> MeanAbsoluteDeviation; 216 217 /** \brief Alias. Rectangle enclosing the region, as a <tt>std::pair</tt> of coordinates. */ 218 typedef Coord<Range> BoundingBox; 219 /** \brief Alias. Anchor point (first point of the region seen by scan-order traversal. */ 220 typedef Coord<FirstSeen> RegionAnchor; 221 222 /** \brief Alias. Region center. */ 223 typedef Coord<Mean> RegionCenter; 224 /** \brief Alias. Region radii. */ 225 typedef Coord<Principal<StdDev> > RegionRadii; 226 /** \brief Alias. Region axes. */ 227 typedef Coord<Principal<CoordinateSystem> > RegionAxes; 228 229 /** \brief Alias. Center of mass. */ 230 typedef Weighted<RegionCenter> CenterOfMass; 231 /** \brief Alias. Region center weighted by the region intensity (center of mass). */ 232 typedef Weighted<RegionCenter> WeightedRegionCenter; 233 /** \brief Alias. Moments of inertia. */ 234 typedef Weighted<Coord<Principal<Variance> > > MomentsOfInertia; 235 /** \brief Alias. Region radius weighted by region intensity (square root of the moments of inertia). */ 236 typedef Weighted<RegionRadii> WeightedRegionRadii; 237 /** \brief Alias. Axes of inertia. */ 238 typedef Weighted<RegionAxes> AxesOfInertia; 239 240 /**************************************************************************/ 241 /* */ 242 /* Tag standardization rules */ 243 /* */ 244 /**************************************************************************/ 245 246 namespace acc_detail { 247 248 template <class A> 249 struct ModifierRule 250 { 251 typedef A type; 252 }; 253 254 } // namespace acc_detail 255 256 template <class A> 257 struct Error___Tag_modifiers_of_same_kind_must_not_be_combined; 258 259 // apply rules as long as the Tag type changes ... 260 template <class A, class S=typename acc_detail::ModifierRule<A>::type> 261 struct StandardizeTag 262 { 263 typedef typename StandardizeTag<S>::type type; 264 }; 265 266 // ... and stop otherwise ... 267 template <class A> 268 struct StandardizeTag<A, A> 269 { 270 typedef A type; 271 }; 272 273 // ... or fail when the tag spec was non-conforming 274 template <class A, class B> 275 struct StandardizeTag<A, Error___Tag_modifiers_of_same_kind_must_not_be_combined<B> > 276 : public Error___Tag_modifiers_of_same_kind_must_not_be_combined<B> 277 {}; 278 279 namespace acc_detail { 280 281 // Assign priorities to modifiers to determine their standard order (by ascending priority). 282 // SubstitutionMask determines which modifiers must be automatically transferred to dependencies. 283 enum { MinPriority = 1, 284 AccumulatorPriority = 32, 285 PrepareDataPriority = 16, 286 NormalizePriority = 8, 287 AccessDataPriority = 4, 288 WeightingPriority = 2, 289 GlobalPriority = 1, 290 MaxPriority = 32, 291 SubstitutionMask = PrepareDataPriority | AccessDataPriority | WeightingPriority | GlobalPriority }; 292 293 template <class A> 294 struct ModifierPriority 295 { 296 static const int value = AccumulatorPriority; 297 }; 298 299 #define VIGRA_MODIFIER_PRIORITY(MODIFIER, VALUE) \ 300 template <class A> \ 301 struct ModifierPriority<MODIFIER<A> > \ 302 { \ 303 static const int value = VALUE; \ 304 }; 305 306 VIGRA_MODIFIER_PRIORITY(Global, GlobalPriority) 307 308 VIGRA_MODIFIER_PRIORITY(Weighted, WeightingPriority) 309 310 VIGRA_MODIFIER_PRIORITY(Coord, AccessDataPriority) 311 VIGRA_MODIFIER_PRIORITY(DataFromHandle, AccessDataPriority) 312 313 VIGRA_MODIFIER_PRIORITY(DivideByCount, NormalizePriority) 314 VIGRA_MODIFIER_PRIORITY(RootDivideByCount, NormalizePriority) 315 VIGRA_MODIFIER_PRIORITY(DivideUnbiased, NormalizePriority) 316 VIGRA_MODIFIER_PRIORITY(RootDivideUnbiased, NormalizePriority) 317 318 VIGRA_MODIFIER_PRIORITY(Central, PrepareDataPriority) 319 VIGRA_MODIFIER_PRIORITY(Principal, PrepareDataPriority) 320 VIGRA_MODIFIER_PRIORITY(Whitened, PrepareDataPriority) 321 322 // explicitly set priority for base accumulators that look like modifiers 323 VIGRA_MODIFIER_PRIORITY(StandardQuantiles, AccumulatorPriority) 324 325 #undef VIGRA_MODIFIER_PRIORITY 326 327 // check if the tag A contains a modifier with TARGET_PRIORITY 328 template <class A, int TARGET_PRIORITY, int PRIORITY=ModifierPriority<A>::value> 329 struct HasModifierPriority 330 { 331 typedef VigraFalseType type; 332 static const bool value = false; 333 }; 334 335 template <class A, int TARGET_PRIORITY> 336 struct HasModifierPriority<A, TARGET_PRIORITY, TARGET_PRIORITY> 337 { 338 typedef VigraTrueType type; 339 static const bool value = true; 340 }; 341 342 template <class A, template <class> class B, int TARGET_PRIORITY, int PRIORITY> 343 struct HasModifierPriority<B<A>, TARGET_PRIORITY, PRIORITY> 344 : public HasModifierPriority<A, TARGET_PRIORITY> 345 {}; 346 347 template <class A, template <class> class B, int TARGET_PRIORITY> 348 struct HasModifierPriority<B<A>, TARGET_PRIORITY, TARGET_PRIORITY> 349 { 350 typedef VigraTrueType type; 351 static const bool value = true; 352 }; 353 354 // three-way compare 355 template <class A, class B> 356 struct ModifierCompare 357 { 358 static const int p1 = ModifierPriority<A>::value; 359 static const int p2 = ModifierPriority<B>::value; 360 static const int value = p1 < p2 361 ? -1 362 : p2 < p1 363 ? 1 364 : 0; 365 }; 366 367 template <class A> 368 struct ModifierCompareToInner; 369 370 template <class A, template <class> class B> 371 struct ModifierCompareToInner<B<A> > 372 : public ModifierCompare<B<A>, A> 373 {}; 374 375 // sort modifiers by ascending priority 376 template <class A, int compare=ModifierCompareToInner<A>::value> 377 struct ModifierOrder; 378 379 // do nothing if the order is correct (compare == -1) 380 template <class A> 381 struct ModifierOrder<A, -1> 382 { 383 typedef A type; 384 }; 385 386 // fail if there are two modifiers with the same priority (compare == 0) 387 template <class A, template <class> class B, template <class> class C> 388 struct ModifierOrder<C<B<A> >, 0> 389 { 390 typedef Error___Tag_modifiers_of_same_kind_must_not_be_combined<C<B<A> > > type; 391 }; 392 393 // sort if the order is reversed (compare == 1) 394 template <class A, template <class> class B, template <class> class C> 395 struct ModifierOrder<C<B<A> >, 1> 396 { 397 typedef B<C<A> > type; 398 }; 399 400 #define VIGRA_CLEANUP_DATA_PREPARATION_MODIFIERS(OUTER, INNER, RESULT) \ 401 template <class A> \ 402 struct ModifierOrder<OUTER<INNER<A > >, 0> \ 403 { \ 404 typedef RESULT<A > type; \ 405 }; 406 407 // drop duplicates 408 VIGRA_CLEANUP_DATA_PREPARATION_MODIFIERS(Central, Central, Central) 409 VIGRA_CLEANUP_DATA_PREPARATION_MODIFIERS(Principal, Principal, Principal) 410 VIGRA_CLEANUP_DATA_PREPARATION_MODIFIERS(Whitened, Whitened, Whitened) 411 412 // the strongest data preparation modifier takes precendence 413 VIGRA_CLEANUP_DATA_PREPARATION_MODIFIERS(Principal, Central, Principal) 414 VIGRA_CLEANUP_DATA_PREPARATION_MODIFIERS(Whitened, Central, Whitened) 415 VIGRA_CLEANUP_DATA_PREPARATION_MODIFIERS(Whitened, Principal, Whitened) 416 417 // Coord takes precendence over DataFromHandle 418 VIGRA_CLEANUP_DATA_PREPARATION_MODIFIERS(DataFromHandle, Coord, Coord) 419 420 #undef VIGRA_CLEANUP_DATA_PREPARATION_MODIFIERS 421 422 // drop duplicates 423 template <class A, template <class> class B> 424 struct ModifierRule<B<B<A> > > 425 { 426 typedef B<A> type; 427 }; 428 429 template <class A, int PRIORITY=ModifierPriority<A>::value> 430 struct RecurseModifier; 431 432 template <class A, template <class> class B, int PRIORITY> 433 struct RecurseModifier<B<A>, PRIORITY> 434 { 435 typedef typename ModifierOrder<B<typename StandardizeTag<A>::type> >::type type; 436 }; 437 438 template <class A, template <class> class B> 439 struct RecurseModifier<B<A>, AccumulatorPriority> 440 { 441 typedef B<A> type; 442 }; 443 444 // recurse down the modifier chain, but only of B is actually a modifier, 445 // and not a templated base accumulator (i.e. do not recurse if B's 446 // priority is 'AccumulatorPriority') 447 template <class A, template <class> class B> 448 struct ModifierRule<B<A> > 449 : public RecurseModifier<B<A> > 450 {}; 451 452 // reduce the SOURCE modifier to the TARGET modifier, 453 // using the given TEMPLATE arguments 454 // (this is a work-around for the lack of templated typedef in C++) 455 #define VIGRA_REDUCE_MODFIER(TEMPLATE, SOURCE, TARGET) \ 456 template <TEMPLATE > \ 457 struct ModifierRule<SOURCE > \ 458 { \ 459 typedef TARGET type; \ 460 }; 461 462 #define VIGRA_VOID 463 464 // centralizing doesn't change the CoordinateSystem 465 VIGRA_REDUCE_MODFIER(VIGRA_VOID, Central<CoordinateSystem>, CoordinateSystem) 466 // whitened CoordinateSystem are the same as principal CoordinateSystem 467 VIGRA_REDUCE_MODFIER(VIGRA_VOID, Whitened<CoordinateSystem>, Principal<CoordinateSystem>) 468 469 // counting modified data is the same as counting data, except for weighted data and global counting 470 VIGRA_REDUCE_MODFIER(template <class> class A, A<Count>, Count) 471 VIGRA_REDUCE_MODFIER(VIGRA_VOID, Weighted<Count>, Weighted<Count>) 472 VIGRA_REDUCE_MODFIER(VIGRA_VOID, CoordWeighted<Count>, Weighted<Count>) 473 VIGRA_REDUCE_MODFIER(VIGRA_VOID, Global<Count>, Global<Count>) 474 475 // reduce aliases that typedef can't handle 476 VIGRA_REDUCE_MODFIER(unsigned N, Moment<N>, DivideByCount<PowerSum<N> >) 477 VIGRA_REDUCE_MODFIER(unsigned N, CentralMoment<N>, DivideByCount<Central<PowerSum<N> > >) 478 VIGRA_REDUCE_MODFIER(class A, CoordWeighted<A>, Weighted<Coord<A> >) 479 480 // reduce statistics that are inherently centered 481 VIGRA_REDUCE_MODFIER(VIGRA_VOID, Central<Centralize>, Centralize) 482 VIGRA_REDUCE_MODFIER(VIGRA_VOID, Central<Skewness>, Skewness) 483 VIGRA_REDUCE_MODFIER(VIGRA_VOID, Central<Kurtosis>, Kurtosis) 484 VIGRA_REDUCE_MODFIER(VIGRA_VOID, Central<FlatScatterMatrix>, FlatScatterMatrix) 485 VIGRA_REDUCE_MODFIER(VIGRA_VOID, Central<ScatterMatrixEigensystem>, ScatterMatrixEigensystem) 486 487 VIGRA_REDUCE_MODFIER(VIGRA_VOID, Principal<Centralize>, PrincipalProjection) 488 VIGRA_REDUCE_MODFIER(VIGRA_VOID, Whitened<Centralize>, Whiten) 489 VIGRA_REDUCE_MODFIER(VIGRA_VOID, Principal<PrincipalProjection>, PrincipalProjection) 490 VIGRA_REDUCE_MODFIER(VIGRA_VOID, Whitened<PrincipalProjection>, Whiten) 491 VIGRA_REDUCE_MODFIER(VIGRA_VOID, Whitened<Whiten>, Whiten) 492 493 // ignore all modifiers of RegionContour and related features 494 VIGRA_REDUCE_MODFIER(template <class> class A, A<RegionContour>, RegionContour) 495 #ifdef WITH_LEMON 496 VIGRA_REDUCE_MODFIER(template <class> class A, A<ConvexHull>, ConvexHull) 497 VIGRA_REDUCE_MODFIER(template <class> class A, A<ConvexHullFeatures>, ConvexHullFeatures) 498 #endif // WITH_LEMON 499 VIGRA_REDUCE_MODFIER(template <class> class A, A<RegionPerimeter>, RegionPerimeter) 500 VIGRA_REDUCE_MODFIER(template <class> class A, A<RegionCircularity>, RegionCircularity) 501 VIGRA_REDUCE_MODFIER(template <class> class A, A<RegionEccentricity>, RegionEccentricity) 502 VIGRA_REDUCE_MODFIER(VIGRA_VOID, Weighted<RegionEccentricity>, Weighted<RegionEccentricity>) 503 504 // reduce even absolute powers to plain powers 505 template <unsigned N> 506 struct ModifierRule<AbsPowerSum<N> > 507 { 508 typedef typename IfBool<(N % 2 == 0), PowerSum<N>, AbsPowerSum<N> >::type type; 509 }; 510 511 #undef VIGRA_VOID 512 #undef VIGRA_REDUCE_MODFIER 513 514 template <class A> 515 struct ShouldBeWeighted 516 { 517 typedef VigraFalseType type; 518 static const bool value = false; 519 }; 520 521 template <> 522 struct ShouldBeWeighted<ArgMinWeight> 523 { 524 typedef VigraTrueType type; 525 static const bool value = true; 526 }; 527 528 template <> 529 struct ShouldBeWeighted<ArgMaxWeight> 530 { 531 typedef VigraTrueType type; 532 static const bool value = true; 533 }; 534 535 template <class A, template <class> class B> 536 struct ShouldBeWeighted<B<A> > 537 : public ShouldBeWeighted<A> 538 {}; 539 540 } // namespace acc_detail 541 542 template <class A> 543 struct IsCoordinateFeature 544 { 545 typedef VigraFalseType type; 546 static const bool value = false; 547 }; 548 549 template <class A, template <class> class B> 550 struct IsCoordinateFeature<B<A> > 551 { 552 typedef typename IsCoordinateFeature<A>::type type; 553 static const bool value = IsCoordinateFeature<A>::value; 554 }; 555 556 template <class A> 557 struct IsCoordinateFeature<Coord<A> > 558 { 559 typedef VigraTrueType type; 560 static const bool value = true; 561 }; 562 563 template <class A> 564 struct IsPrincipalFeature 565 { 566 typedef VigraFalseType type; 567 static const bool value = false; 568 }; 569 570 template <class A, template <class> class B> 571 struct IsPrincipalFeature<B<A> > 572 { 573 typedef typename IsPrincipalFeature<A>::type type; 574 static const bool value = IsPrincipalFeature<A>::value; 575 }; 576 577 template <class A> 578 struct IsPrincipalFeature<Principal<A> > 579 { 580 typedef VigraTrueType type; 581 static const bool value = true; 582 }; 583 584 template <class A> 585 struct IsPrincipalFeature<Whitened<A> > 586 { 587 typedef VigraTrueType type; 588 static const bool value = true; 589 }; 590 591 /**************************************************************************/ 592 /* */ 593 /* Tag transfer rules */ 594 /* */ 595 /**************************************************************************/ 596 597 namespace acc_detail { 598 599 template <class A> 600 struct DefaultModifier; 601 602 template <class A> 603 struct ModifierPriority<DefaultModifier<A> > 604 { 605 static const int value = ModifierPriority<A>::value << 1; 606 }; 607 608 template <class A, int TargetPriority, int Priority=ModifierPriority<A>::value> 609 struct InsertDefaultModifier 610 { 611 typedef DefaultModifier<typename InsertDefaultModifier<A, (TargetPriority << 1)>::type> type; 612 }; 613 614 template <class A, int TargetPriority> 615 struct InsertDefaultModifier<A, TargetPriority, TargetPriority> 616 { 617 typedef A type; 618 }; 619 620 template <class A, int TargetPriority, int Priority=ModifierPriority<A>::value> 621 struct TagLongForm; 622 623 template <class A, int TargetPriority> 624 struct TagLongForm<A, TargetPriority, MaxPriority> 625 { 626 typedef typename InsertDefaultModifier<A, TargetPriority>::type type; 627 }; 628 629 template <class A, template <class> class B, int TargetPriority> 630 struct TagLongForm<B<A>, TargetPriority, MaxPriority> 631 { 632 typedef typename InsertDefaultModifier<B<A>, TargetPriority>::type type; 633 }; 634 635 template <class A, template <class> class B, int TargetPriority, int Priority> 636 struct TagLongForm<B<A>, TargetPriority, Priority> 637 { 638 typedef typename TagLongForm<A, (Priority << 1)>::type Inner; 639 typedef typename InsertDefaultModifier<B<Inner>, TargetPriority>::type type; 640 }; 641 642 template <class A, template <class> class B, int TargetPriority> 643 struct TagLongForm<B<A>, TargetPriority, TargetPriority> 644 { 645 typedef typename TagLongForm<A, (TargetPriority << 1)>::type Inner; 646 typedef B<Inner> type; 647 }; 648 649 template <class A> 650 struct LongModifierRule 651 { 652 typedef A type; 653 }; 654 655 // apply rules as long as the Tag type changes ... 656 template <class A, class S=typename LongModifierRule<A>::type> 657 struct StandardizeTagLongForm 658 { 659 typedef typename StandardizeTagLongForm<S>::type type; 660 }; 661 662 // ... and stop otherwise ... 663 template <class A> 664 struct StandardizeTagLongForm<A, A> 665 { 666 typedef A type; 667 }; 668 669 template <class A, template <class> class B> 670 struct LongModifierRule<B<A> > 671 { 672 typedef B<typename LongModifierRule<A>::type> type; 673 }; 674 675 template <class A> 676 struct LongModifierRule<DefaultModifier<A> > 677 { 678 typedef A type; 679 }; 680 681 #define VIGRA_DROP_DATA_PREPARATION_MODIFIERS(SOURCE, TARGET) \ 682 template <> \ 683 struct LongModifierRule<SOURCE > \ 684 { \ 685 typedef TARGET type; \ 686 }; 687 688 VIGRA_DROP_DATA_PREPARATION_MODIFIERS(Central<Sum>, Sum) 689 VIGRA_DROP_DATA_PREPARATION_MODIFIERS(Principal<Sum>, Sum) 690 VIGRA_DROP_DATA_PREPARATION_MODIFIERS(Whitened<Sum>, Sum) 691 VIGRA_DROP_DATA_PREPARATION_MODIFIERS(Principal<FlatScatterMatrix>, FlatScatterMatrix) 692 VIGRA_DROP_DATA_PREPARATION_MODIFIERS(Whitened<FlatScatterMatrix>, FlatScatterMatrix) 693 VIGRA_DROP_DATA_PREPARATION_MODIFIERS(Principal<ScatterMatrixEigensystem>, ScatterMatrixEigensystem) 694 VIGRA_DROP_DATA_PREPARATION_MODIFIERS(Whitened<ScatterMatrixEigensystem>, ScatterMatrixEigensystem) 695 696 #undef VIGRA_DROP_DATA_PREPARATION_MODIFIERS 697 698 template <class A> 699 struct CheckSubstitutionFlag 700 { 701 static const bool value = (ModifierPriority<A>::value & SubstitutionMask) != 0; 702 }; 703 704 template <class A, class B, 705 bool substitute=CheckSubstitutionFlag<A>::value> 706 struct SubstituteModifiers; 707 708 template <class A, class B> 709 struct SubstituteModifiers<A, B, false> 710 { 711 typedef B type; 712 }; 713 714 template <class A, template <class> class AA, class B, template <class> class BB> 715 struct SubstituteModifiers<AA<A>, BB<B>, true> 716 { 717 typedef AA<typename SubstituteModifiers<A, B>::type> type; 718 }; 719 720 template <class A, class B, template <class> class BB> 721 struct SubstituteModifiers<DefaultModifier<A>, BB<B>, true> 722 { 723 typedef BB<typename SubstituteModifiers<A, B>::type> type; 724 }; 725 726 template <class A, template <class> class AA, class B, template <class> class BB> 727 struct SubstituteModifiers<AA<A>, BB<B>, false> 728 { 729 typedef BB<typename SubstituteModifiers<A, B>::type> type; 730 }; 731 732 } // namespace acc_detail 733 734 template <class A, class B> 735 struct TransferModifiers 736 { 737 typedef typename StandardizeTag<A>::type StdA; 738 typedef typename StandardizeTag<B>::type StdB; 739 typedef typename acc_detail::TagLongForm<StdA, acc_detail::MinPriority>::type AA; 740 typedef typename acc_detail::TagLongForm<StdB, acc_detail::MinPriority>::type BB; 741 typedef typename acc_detail::SubstituteModifiers<AA, BB>::type AB; 742 typedef typename acc_detail::StandardizeTagLongForm<AB>::type StdAB; 743 typedef typename StandardizeTag<StdAB>::type type; 744 }; 745 746 template <class A, class HEAD, class TAIL> 747 struct TransferModifiers<A, TypeList<HEAD, TAIL> > 748 { 749 typedef TypeList<typename TransferModifiers<A, HEAD>::type, 750 typename TransferModifiers<A, TAIL>::type> type; 751 }; 752 753 template <class A> 754 struct TransferModifiers<A, void> 755 { 756 typedef void type; 757 }; 758 759 template <class TargetTag, class A=typename TargetTag::Dependencies> 760 struct StandardizeDependencies 761 #ifndef DOXYGEN 762 : public StandardizeDependencies<TargetTag, typename A::type> 763 #endif 764 {}; 765 766 template <class TargetTag, class HEAD, class TAIL> 767 struct StandardizeDependencies<TargetTag, TypeList<HEAD, TAIL> > 768 { 769 typedef typename StandardizeTag<TargetTag>::type Target; 770 typedef typename TransferModifiers<Target, TypeList<HEAD, TAIL> >::type type; 771 }; 772 773 template <class TargetTag> 774 struct StandardizeDependencies<TargetTag, void> 775 { 776 typedef void type; 777 }; 778 779 }} // namespace vigra::acc 780 781 #endif // VIGRA_ACCUMULATOR_GRAMMAR_HXX 782