modules/saupePredictor.h

   1 #ifndef SAUPEPREDICTOR_HEADER_
   2 #define SAUPEPREDICTOR_HEADER_
   3
   4 #include "../headers.h"
   5 #include "../kdTree.h"
   6
   7 /// \ingroup modules
   8 /** Predictor for MStdEncoder based on a theorem proven in Saupe's work.
   9  *      It resizes the blocks to 4x4 and normalizes them.
  10  *      Domains for every level are stored in a KDTree instance and searched.
  11  *      The user can set the size of returned chunks of the blocks
  12  *      and the maximal part of domains returned. */
  13 class MSaupePredictor: public IStdEncPredictor {
  14         DECLARE_debugModule;
  15
  16         DECLARE_TypeInfo( MSaupePredictor, "Saupe predictor"
  17         , "Predictor for standard encoder using multi-dimensional nearest neighbour search"
  18         , {
  19                 label:  "Prediction chunk size",
  20                 desc:   "The number of predicted domains in a chunk",
  21                 type:   settingInt(1,8,32)
  22         }, {
  23                 label:  "Max. predicted part",
  24                 desc:   "The maximal part of domains predicted for a range block",
  25                 type:   settingInt(-20,-10,0,IntLog2)
  26         } )
  27
  28 protected:
  29         /** Indices for settings */
  30         enum Settings { ChunkSize, MaxPredPart };
  31
  32         /**  maxPredCoeff() * "the number of domains" == "max. number of predictions" */
  33         Real maxPredCoeff()     { return ldexp( Real(1), settingsInt(MaxPredPart) ); }
  34
  35 public:
  36         typedef float KDReal;           ///< The floating point type used in the KD-tree
  37         typedef KDTree<KDReal> Tree;///< The version of KDTree in use
  38 protected:
  39 //      Module's data
  40         std::vector<Tree*> levelTrees; ///< The predicting Tree for every level (can be missing)
  41         #ifndef NDEBUG // the stats about the domain counts predicted
  42         long predicted, maxpred;
  43         #endif
  44
  45 protected:
  46 //      Construction and destruction
  47         #ifndef NDEBUG
  48         MSaupePredictor(): predicted(0), maxpred(0) {}
  49         #endif
  50         /** Only call ::cleanUp */
  51         ~MSaupePredictor() { cleanUp(); }
  52
  53 public:
  54 /**     \name IStdEncPredictor interface
  55  *      @{ */
  56         IOneRangePredictor* newPredictor(const NewPredictorData &data);
  57
  58         void cleanUp() {
  59                 clearContainer(levelTrees);
  60                 levelTrees.clear();
  61         }
  62 ///     @}
  63
  64 protected:
  65         /** Computes the level for predictions based on the actual level */
  66         int getPredLevel(int /*realLevel*/) const
  67                 { return 2; }
  68
  69         /** Builds a new tree for one level of range blocks using passed domain blocks */
  70         Tree* createTree(const NewPredictorData &data);
  71
  72         /** Normalizes and possibly shrinks a domain block */
  73         static void refineDomain( const SummedPixels &pixMatrix, int x0, int y0
  74                 , bool allowInversion, int realLevel, int predLevel, SReal *pixelResult );
  75         /** Normalizes and possibly shrinks a range block */
  76         static void refineRange
  77                 ( const NewPredictorData &data, int predLevel, SReal *pixelResult );
  78
  79
  80 protected:
  81         /** Implementation of the one-range-predictor from IStdEncPredictor interface */
  82         class OneRangePredictor: public IOneRangePredictor {
  83                 friend class MSaupePredictor;
  84
  85                 /** Struct representing one node of the KD-tree and its distance form the range block */
  86                 struct HeapInfo {
  87                         int index;              ///< The index of the node in the tree
  88                         float bestError;///< The SE-distance of the node from the range's point
  89
  90                         /** Only initializes members from the parameters */
  91                         HeapInfo(int index_,float bestError_)
  92                         : index(index_), bestError(bestError_) {}
  93
  94                         /** Reverse comparison operator according to the ::bestError (lowest first) */
  95                         bool operator<(const HeapInfo &other) const
  96                                 { return bestError>other.bestError; }
  97                 };
  98
  99                 /** A convertor from SE in regular space to SE in normalized space */
 100                 class SEnormalizator {
 101                         Real errorAccel; ///< Accelerator for conversion of SEs to the real values
 102                 public:
 103                         /** Initializes the normalizator for a range block, needed to call ::normSE */
 104                         void initialize(const NewPredictorData &data,int predLevel) {
 105                                 int shift= 2 * (predLevel - data.rangeBlock->level);
 106                                 errorAccel= ldexp( data.pixCount/data.rnDev2, shift );
 107                                 //errorAccel= data.pixCount/data.rnDev2;
 108                         }
 109                         /** Computes normalized-tree-error from real SE (::initialize has been called) */
 110                         Real normSE(Real error) const {
 111                                 Real result= std::ldexp( 1-sqrt(1-error*errorAccel), 1 );
 112                                 if ( isNaN(result) )
 113                                         result= numeric_limits<Real>::infinity();
 114                                 return result;
 115                         }
 116                 } errorNorm; ///< used to compute SE in the normalized space (from normal SE)
 117
 118                 typedef Tree::PointHeap PointHeap;
 119         protected:
 120                 std::vector<PointHeap*> heaps;  ///< Pointers to the heaps for every rotation and inversion
 121                 std::vector<HeapInfo> infoHeap; ///< Heap built from ::heaps according to their best SEs
 122                 KDReal *points; ///< Normalized range rotations and inversions used by the heaps (owned)
 123                 int chunkSize   ///  The suggested count for predicted ranges returned at once
 124                 , predsRemain   ///  Max.\ remaining count of predictions to be returned
 125                 , heapCount;    ///< The number of heaps
 126                 bool firstChunk ///  True if nothing has been predicted yet, false otherwise
 127                 , allowRotations///  Like NewPredictorData::allowRotations
 128                 , isRegular;    ///< Indicates regularity of the range block (see RangeNode::isRegular)
 129
 130         DEBUG_ONLY( public: long *predicted; )
 131
 132         protected:
 133                 /** Creates a new predictor for a range block (prepares tree-heaps, etc.) */
 134                 OneRangePredictor( const NewPredictorData &data, int chunkSize_
 135                         , const Tree &tree, int maxPredicts );
 136         public:
 137         /**     \name IOneRangePredictor interface
 138          *      @{ */
 139                 Predictions& getChunk(float maxPredictedSE,Predictions &store);
 140                 ~OneRangePredictor() {
 141                         clearContainer(heaps);
 142                         delete[] points;
 143                 }
 144         ///     @}
 145         }; // OneRangePredictor class
 146 };
 147
 148 #endif // SAUPEPREDICTOR_HEADER_