Tesseract  3.02
 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
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
110  public:
112  memset(bin_size_array_, 0, sizeof(bin_size_array_));
113  }
114 
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 &&
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