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,16,64)
  22         }, {
  23                 label:  "Max. predicted part",
  24                 desc:   "The maximal part of domains predicted for a range block",
  25                 type:   settingInt(-20,-8,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, returns true on success.
  76          *      Failure occurs when the shrunken block contains at most one pixel (pointless to predict). */
  77         static bool refineRange
  78                 ( const NewPredictorData &data, int predLevel, SReal *pixelResult );
  79
  80
  81 protected:
  82         /** Implementation of the one-range-predictor from IStdEncPredictor interface */
  83         class OneRangePredictor: public IOneRangePredictor {
  84                 friend class MSaupePredictor;
  85
  86                 /** Struct representing one node of the KD-tree and its distance form the range block */
  87                 struct HeapInfo {
  88                         int index;              ///< The index of the node in the tree
  89                         float bestError;///< The SE-distance of the node from the range's point
  90
  91                         /** Only initializes members from the parameters */
  92                         HeapInfo(int index_,float bestError_)
  93                         : index(index_), bestError(bestError_) {}
  94
  95                         /** Reverse comparison operator according to the ::bestError (lowest first) */
  96                         bool operator<(const HeapInfo &other) const
  97                                 { return bestError>other.bestError; }
  98                 };
  99
 100                 /** A convertor from SE in regular space to SE in normalized space */
 101                 class SEnormalizator {
 102                         Real errorAccel; ///< Accelerator for conversion of SEs to the real values
 103                 public:
 104                         /** Initializes the normalizator for a range block, needed to call ::normSE */
 105                         void initialize(const NewPredictorData &data,int predLevel) {
 106                                 int shift= 2 * (predLevel - data.rangeBlock->level);
 107                                 errorAccel= ldexp( data.pixCount/data.rnDev2, shift );
 108                                 //errorAccel= data.pixCount/data.rnDev2;
 109                         }
 110                         /** Computes normalized-tree-error from real SE (::initialize has been called) */
 111                         Real normSE(Real error) const {
 112                                 Real result= std::ldexp( 1-sqrt(1-error*errorAccel), 1 );
 113                                 if ( isNaN(result) )
 114                                         result= numeric_limits<Real>::infinity();
 115                                 return result;
 116                         }
 117                 } errorNorm; ///< used to compute SE in the normalized space (from normal SE)
 118
 119                 typedef Tree::PointHeap PointHeap;
 120         protected:
 121                 std::vector<PointHeap*> heaps;  ///< Pointers to the heaps for every rotation and inversion
 122                 std::vector<HeapInfo> infoHeap; ///< Heap built from ::heaps according to their best SEs
 123                 KDReal *points; ///< Normalized range rotations and inversions used by the heaps (owned)
 124                 int chunkSize   ///  The suggested count for predicted ranges returned at once
 125                 , predsRemain   ///  Max.\ remaining count of predictions to be returned
 126                 , heapCount;    ///< The number of heaps
 127                 bool firstChunk ///  True if nothing has been predicted yet, false otherwise
 128                 , allowRotations///  Like NewPredictorData::allowRotations
 129                 , isRegular;    ///< Indicates regularity of the range block (see RangeNode::isRegular)
 130
 131         DEBUG_ONLY( public: long *predicted; )
 132
 133         protected:
 134                 /** Creates a new predictor for a range block (prepares tree-heaps, etc.) */
 135                 OneRangePredictor( const NewPredictorData &data, int chunkSize_
 136                         , const Tree &tree, int maxPredicts );
 137         public:
 138         /**     \name IOneRangePredictor interface
 139          *      @{ */
 140                 Predictions& getChunk(float maxPredictedSE,Predictions &store);
 141                 ~OneRangePredictor() {
 142                         clearContainer(heaps);
 143                         delete[] points;
 144                 }
 145         ///     @}
 146         }; // OneRangePredictor class
 147 };
 148
 149 #endif // SAUPEPREDICTOR_HEADER_