Newer
Older
Karsten Suehring
committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/* The copyright in this software is being made available under the BSD
* License, included below. This software may be subject to other third party
* and contributor rights, including patent rights, and no such rights are
* granted under this license.
*
* Copyright (c) 2010-2018, ITU/ISO/IEC
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* * Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
* * Neither the name of the ITU/ISO/IEC nor the names of its contributors may
* be used to endorse or promote products derived from this software without
* specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS
* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
* THE POSSIBILITY OF SUCH DAMAGE.
*/
/** \file BinaryDecisionTree.h
* \brief declares a binary decision tree that can be used for automated optimal coding of multi-level cascaded decisions
*/
#ifndef __BINARYDECISIONTREE__
#define __BINARYDECISIONTREE__
#include "CommonDef.h"
#define MAX_DEPTH_DECISION_TREE 5
#define MAX_NODES_DECISION_TREE ( 2 * ( 1 << MAX_DEPTH_DECISION_TREE ) )
// decision tree template describes the trees and contains mappings between node ids and their in-tree positions
struct DecisionTreeTemplate
{
DecisionTreeTemplate( unsigned _depth );
unsigned depth;
unsigned ids [MAX_NODES_DECISION_TREE]; // maps the in-tree position to node-id
bool hasSub [MAX_NODES_DECISION_TREE]; // stores, for each in-tree position, the information if the node is an end-node ('false'), or a decision-node ('true')
unsigned mapping[MAX_NODES_DECISION_TREE]; // maps the node-ids to the in-tree positions
};
// decision tree contains sparsity information (node availability) and the context ids needed to encode a decision
// the tree topology described by the decision tree template 'dtt' is used for the tree structure
struct DecisionTree
{
DecisionTree( const DecisionTreeTemplate& _dtt );
const DecisionTreeTemplate &dtt;
bool isAvail[MAX_NODES_DECISION_TREE];
unsigned ctxId [MAX_NODES_DECISION_TREE];
// if an end-node is not available, some coding bins can be skipped - availability of the end-nodes can be set using this function
void setAvail( unsigned id, bool _isAvail );
// for decision nodes, the context for decision encoding can be set here. don't set any context to code as a EP bin
void setCtxId( unsigned id, unsigned _ctxId );
// propagate the end-nodes availability across decision nodes (call with default parameters for correct results)
void reduce ( unsigned offset = 0, int depth = -1 );
};
struct DecisionTreeBuilder;
// use this function to easily create decision trees from the output of decision(...) functions (allows for nice human-readable form)
DecisionTreeTemplate compile( DecisionTreeBuilder *dtb );
// parameter naming
// id: name of the node
// id0: name of a direct outcome for the '0'-case
// id1: name of a direct outcome for the '1'-case
// a simple decision node with two direct outcomes
DecisionTreeBuilder* decision( unsigned id, unsigned id0, unsigned id1 );
// a decision node with decision sub-tree on the left side (the '0'-case) and a direct outcome on the right (the '1'-case)
DecisionTreeBuilder* decision( unsigned id, DecisionTreeBuilder* sub0, unsigned id1 );
// a decision node with direct outcome on the left side and a decision sub-tree on the right
DecisionTreeBuilder* decision( unsigned id, DecisionTreeBuilder* sub0, DecisionTreeBuilder* sub1 );
// a decision with two decision sub-trees
DecisionTreeBuilder* decision( unsigned id, unsigned id0, DecisionTreeBuilder* sub1 );
#endif