Tesseract 3.02

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
search_node.h
Go to the documentation of this file.
1 /**********************************************************************
2 * File: search_node.h
3 * Description: Declaration of the Beam Search Node Class
4 * Author: Ahmad Abdulkader
5 * Created: 2008
6 *
7 * (C) Copyright 2008, Google Inc.
8 ** Licensed under the Apache License, Version 2.0 (the "License");
9 ** you may not use this file except in compliance with the License.
10 ** You may obtain a copy of the License at
11 ** http://www.apache.org/licenses/LICENSE-2.0
12 ** Unless required by applicable law or agreed to in writing, software
13 ** distributed under the License is distributed on an "AS IS" BASIS,
14 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 ** See the License for the specific language governing permissions and
16 ** limitations under the License.
17 *
18 **********************************************************************/
19
20 // The SearchNode class abstracts the search lattice node in the lattice
21 // generated by the BeamSearch class
22 // The SearchNode class holds the lang_mod_edge associated with the lattice
23 // node. It also holds a pointer to the parent SearchNode in the search path
24 // In addition it holds the recognition and the language model costs of the
25 // node and the path leading to this node
26
27 #ifndef SEARCH_NODE_H
28 #define SEARCH_NODE_H
29
30 #include "lang_mod_edge.h"
31 #include "cube_reco_context.h"
32
33 namespace tesseract {
34
35 class SearchNode {
36 public:
37 SearchNode(CubeRecoContext *cntxt, SearchNode *parent_node,
38 int char_reco_cost, LangModEdge *edge, int col_idx);
39
40 ~SearchNode();
41
42 // Updates the parent of the current node if the specified path yields
43 // a better path cost
44 bool UpdateParent(SearchNode *new_parent, int new_reco_cost,
45 LangModEdge *new_edge);
46 // returns the 32-bit string corresponding to the path leading to this node
47 char_32 *PathString();
48 // True if the two input nodes correspond to the same path
49 static bool IdenticalPath(SearchNode *node1, SearchNode *node2);
50
51 inline const char_32 *NodeString() { return str_; }
52 inline void SetString(char_32 *str) { str_ = str; }
53
54 // This node's character recognition cost.
55 inline int CharRecoCost() { return char_reco_cost_; }
56 // Total character recognition cost of the nodes in the best path,
57 // excluding this node.
58 inline int BestPathRecoCost() { return best_path_reco_cost_; }
59 // Number of nodes in best path.
60 inline int BestPathLength() { return best_path_len_; }
61 // Mean mixed cost, i.e., mean character recognition cost +
62 // current language model cost, all weighted by the RecoWgt parameter
63 inline int BestCost() { return best_cost_; }
64 // Mean character recognition cost of the nodes on the best path,
65 // including this node.
66 inline int BestRecoCost() { return mean_char_reco_cost_ ; }
67
68 inline int ColIdx() { return col_idx_; }
69 inline SearchNode *ParentNode() { return parent_node_; }
70 inline LangModEdge *LangModelEdge() { return lang_mod_edge_;}
71 inline int LangModCost() { return LangModCost(lang_mod_edge_, parent_node_); }
72
73 // A comparer function that allows the SearchColumn class to sort the
74 // nodes based on the path cost
75 inline static int SearchNodeComparer(const void *node1, const void *node2) {
76 return (*(reinterpret_cast<SearchNode * const *>(node1)))->best_cost_ -
77 (*(reinterpret_cast<SearchNode * const *>(node2)))->best_cost_;
78 }
79
80 private:
81 CubeRecoContext *cntxt_;
82 // Character code
83 const char_32 *str_;
84 // Recognition cost of most recent character
85 int char_reco_cost_;
86 // Mean mixed cost, i.e., mean character recognition cost +
87 // current language model cost, all weighted by the RecoWgt parameter
88 int best_cost_;
89 // Mean character recognition cost of the nodes on the best path,
90 // including this node.
91 int mean_char_reco_cost_ ;
92 // Total character recognition cost of the nodes in the best path,
93 // excluding this node.
94 int best_path_reco_cost_;
95 // Number of nodes in best path.
96 int best_path_len_;
97 // Column index
98 int col_idx_;
99 // Parent Node
100 SearchNode *parent_node_;
101 // Language model edge
102 LangModEdge *lang_mod_edge_;
103 static int LangModCost(LangModEdge *lang_mod_edge, SearchNode *parent_node);
104 };
105
106 // Implments a SearchNode hash table used to detect if a Search Node exists
107 // or not. This is needed to make sure that identical paths in the BeamSearch
108 // converge
109 class SearchNodeHashTable {
110 public:
111 SearchNodeHashTable() {
112 memset(bin_size_array_, 0, sizeof(bin_size_array_));
113 }
114
115 ~SearchNodeHashTable() {
116 }
117
118 // inserts an entry in the hash table
119 inline bool Insert(LangModEdge *lang_mod_edge, SearchNode *srch_node) {
120 // compute hash based on the edge and its parent node edge
121 unsigned int edge_hash = lang_mod_edge->Hash();
122 unsigned int parent_hash = (srch_node->ParentNode() == NULL ?
123 0 : srch_node->ParentNode()->LangModelEdge()->Hash());
124 unsigned int hash_bin = (edge_hash + parent_hash) % kSearchNodeHashBins;
125
126 // already maxed out, just fail
127 if (bin_size_array_[hash_bin] >= kMaxSearchNodePerBin) {
128 return false;
129 }
130
131 bin_array_[hash_bin][bin_size_array_[hash_bin]++] = srch_node;
132
133 return true;
134 }
135
136 // Looks up an entry in the hash table
137 inline SearchNode *Lookup(LangModEdge *lang_mod_edge,
138 SearchNode *parent_node) {
139 // compute hash based on the edge and its parent node edge
140 unsigned int edge_hash = lang_mod_edge->Hash();
141 unsigned int parent_hash = (parent_node == NULL ?
142 0 : parent_node->LangModelEdge()->Hash());
143 unsigned int hash_bin = (edge_hash + parent_hash) % kSearchNodeHashBins;
144
145 // lookup the entries in the hash bin
146 for (int node_idx = 0; node_idx < bin_size_array_[hash_bin]; node_idx++) {
147 if (lang_mod_edge->IsIdentical(
148 bin_array_[hash_bin][node_idx]->LangModelEdge()) == true &&
149 SearchNode::IdenticalPath(
150 bin_array_[hash_bin][node_idx]->ParentNode(), parent_node) == true) {
151 return bin_array_[hash_bin][node_idx];
152 }
153 }
154
155 return NULL;
156 }
157
158 private:
159 // Hash bin size parameters. These were determined emperically. These affect
160 // the speed of the beam search but have no impact on accuracy
161 static const int kSearchNodeHashBins = 4096;
162 static const int kMaxSearchNodePerBin = 512;
163 int bin_size_array_[kSearchNodeHashBins];
164 SearchNode *bin_array_[kSearchNodeHashBins][kMaxSearchNodePerBin];
165 };
166 }
167
168 #endif // SEARCH_NODE_H