1 #ifndef SAUPEPREDICTOR_HEADER_
2 #define SAUPEPREDICTOR_HEADER_
4 #include "../headers.h"
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
{
16 DECLARE_TypeInfo( MSaupePredictor
, "Saupe predictor"
17 , "Predictor for standard encoder using multi-dimensional nearest neighbour search"
19 label
: "Prediction chunk size",
20 desc
: "The number of predicted domains in a chunk",
21 type
: settingInt(1,16,64)
23 label
: "Max. predicted part",
24 desc
: "The maximal part of domains predicted for a range block",
25 type
: settingInt(-20,-8,0,IntLog2
)
29 /** Indices for settings */
30 enum Settings
{ ChunkSize
, MaxPredPart
};
32 /** maxPredCoeff() * "the number of domains" == "max. number of predictions" */
33 Real
maxPredCoeff() { return ldexp( Real(1), settingsInt(MaxPredPart
) ); }
36 typedef float KDReal
; ///< The floating point type used in the KD-tree
37 typedef KDTree
<KDReal
> Tree
;///< The version of KDTree in use
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
;
46 // Construction and destruction
48 MSaupePredictor(): predicted(0), maxpred(0) {}
50 /** Only call ::cleanUp */
51 ~MSaupePredictor() { cleanUp(); }
54 /** \name IStdEncPredictor interface
56 IOneRangePredictor
* newPredictor(const NewPredictorData
&data
);
59 clearContainer(levelTrees
);
65 /** Computes the level for predictions based on the actual level */
66 int getPredLevel(int /*realLevel*/) const
69 /** Builds a new tree for one level of range blocks using passed domain blocks */
70 Tree
* createTree(const NewPredictorData
&data
);
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
);
81 /** Implementation of the one-range-predictor from IStdEncPredictor interface */
82 class OneRangePredictor
: public IOneRangePredictor
{
83 friend class MSaupePredictor
;
85 /** Struct representing one node of the KD-tree and its distance form the range block */
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
90 /** Only initializes members from the parameters */
91 HeapInfo(int index_
,float bestError_
)
92 : index(index_
), bestError(bestError_
) {}
94 /** Reverse comparison operator according to the ::bestError (lowest first) */
95 bool operator<(const HeapInfo
&other
) const
96 { return bestError
>other
.bestError
; }
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
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;
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 );
113 result
= numeric_limits
<Real
>::infinity();
116 } errorNorm
; ///< used to compute SE in the normalized space (from normal SE)
118 typedef Tree::PointHeap PointHeap
;
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)
130 DEBUG_ONLY( public: long *predicted
; )
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
);
137 /** \name IOneRangePredictor interface
139 Predictions
& getChunk(float maxPredictedSE
,Predictions
&store
);
140 ~OneRangePredictor() {
141 clearContainer(heaps
);
145 }; // OneRangePredictor class
148 #endif // SAUPEPREDICTOR_HEADER_