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.cpp
Go to the documentation of this file.
1 /**********************************************************************
2 * File: search_node.cpp
3 * Description: Implementation 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 #include "search_node.h"
21
22 namespace tesseract {
23
24 // The constructor updates the best paths and costs:
25 // mean_char_reco_cost_ (returned by BestRecoCost()) is the mean
26 // char_reco cost of the best_path, including this node.
27 // best_path_reco_cost is the total char_reco_cost of the best_path,
28 // but excludes the char_reco_cost of this node.
29 // best_cost is the mean mixed cost, i.e., mean_char_reco_cost_ +
30 // current language model cost, all weighted by the cube context's
31 // RecoWgt parameter
32 SearchNode::SearchNode(CubeRecoContext *cntxt, SearchNode *parent_node,
33 int char_reco_cost, LangModEdge *edge, int col_idx) {
34 // copy data members
35 cntxt_ = cntxt;
36 lang_mod_edge_ = edge;
37 col_idx_ = col_idx;
38 parent_node_ = parent_node;
39 char_reco_cost_ = char_reco_cost;
40
41 // the string of this node is the same as that of the language model edge
42 str_ = (edge == NULL ? NULL : edge->EdgeString());
43
44 // compute best path total reco cost
45 best_path_reco_cost_ = (parent_node_ == NULL) ? 0 :
46 parent_node_->CharRecoCost() + parent_node_->BestPathRecoCost();
47
48 // update best path length
49 best_path_len_ = (parent_node_ == NULL) ?
50 1 : parent_node_->BestPathLength() + 1;
51 if (edge != NULL && edge->IsRoot() && parent_node_ != NULL) {
52 best_path_len_++;
53 }
54
55 // compute best reco cost mean cost
56 mean_char_reco_cost_ = static_cast<int>(
57 (best_path_reco_cost_ + char_reco_cost_) /
58 static_cast<double>(best_path_len_));
59
60 // get language model cost
61 int lm_cost = LangModCost(lang_mod_edge_, parent_node_);
62
63 // compute aggregate best cost
64 best_cost_ = static_cast<int>(cntxt_->Params()->RecoWgt() *
65 (best_path_reco_cost_ + char_reco_cost_) /
66 static_cast<double>(best_path_len_)
67 ) + lm_cost;
68 }
69
70 SearchNode::~SearchNode() {
71 if (lang_mod_edge_ != NULL) {
72 delete lang_mod_edge_;
73 }
74 }
75
76 // update the parent_node node if provides a better (less) cost
77 bool SearchNode::UpdateParent(SearchNode *new_parent, int new_reco_cost,
78 LangModEdge *new_edge) {
79 if (lang_mod_edge_ == NULL) {
80 if (new_edge != NULL) {
81 return false;
82 }
83 } else {
84 // to update the parent_node, we have to have the same target
85 // state and char
86 if (new_edge == NULL || !lang_mod_edge_->IsIdentical(new_edge) ||
87 !SearchNode::IdenticalPath(parent_node_, new_parent)) {
88 return false;
89 }
90 }
91
92 // compute the path cost and combined cost of the new path
93 int new_best_path_reco_cost;
94 int new_cost;
95 int new_best_path_len;
96
97 new_best_path_reco_cost = (new_parent == NULL) ?
98 0 : new_parent->BestPathRecoCost() + new_parent->CharRecoCost();
99
100 new_best_path_len =
101 (new_parent == NULL) ? 1 : new_parent->BestPathLength() + 1;
102
103 // compute the new language model cost
104 int new_lm_cost = LangModCost(new_edge, new_parent);
105
106 new_cost = static_cast<int>(cntxt_->Params()->RecoWgt() *
107 (new_best_path_reco_cost + new_reco_cost) /
108 static_cast<double>(new_best_path_len)
109 ) + new_lm_cost;
110
111 // update if it is better (less) than the current one
112 if (best_cost_ > new_cost) {
113 parent_node_ = new_parent;
114 char_reco_cost_ = new_reco_cost;
115 best_path_reco_cost_ = new_best_path_reco_cost;
116 best_path_len_ = new_best_path_len;
117 mean_char_reco_cost_ = static_cast<int>(
118 (best_path_reco_cost_ + char_reco_cost_) /
119 static_cast<double>(best_path_len_));
120 best_cost_ = static_cast<int>(cntxt_->Params()->RecoWgt() *
121 (best_path_reco_cost_ + char_reco_cost_) /
122 static_cast<double>(best_path_len_)
123 ) + new_lm_cost;
124 return true;
125 }
126 return false;
127 }
128
129 char_32 *SearchNode::PathString() {
130 SearchNode *node = this;
131
132 // compute string length
133 int len = 0;
134
135 while (node != NULL) {
136 if (node->str_ != NULL) {
137 len += CubeUtils::StrLen(node->str_);
138 }
139
140 // if the edge is a root and does not have a NULL parent, account for space
141 LangModEdge *lm_edge = node->LangModelEdge();
142 if (lm_edge != NULL && lm_edge->IsRoot() && node->ParentNode() != NULL) {
143 len++;
144 }
145
146 node = node->parent_node_;
147 }
148
149 char_32 *char_ptr = new char_32[len + 1];
150 if (char_ptr == NULL) {
151 return NULL;
152 }
153
154 int ch_idx = len;
155
156 node = this;
157 char_ptr[ch_idx--] = 0;
158
159 while (node != NULL) {
160 int str_len = ((node->str_ == NULL) ? 0 : CubeUtils::StrLen(node->str_));
161 while (str_len > 0) {
162 char_ptr[ch_idx--] = node->str_[--str_len];
163 }
164
165 // if the edge is a root and does not have a NULL parent, insert a space
166 LangModEdge *lm_edge = node->LangModelEdge();
167 if (lm_edge != NULL && lm_edge->IsRoot() && node->ParentNode() != NULL) {
168 char_ptr[ch_idx--] = (char_32)' ';
169 }
170
171 node = node->parent_node_;
172 }
173
174 return char_ptr;
175 }
176
177 // compares the path of two nodes and checks if its identical
178 bool SearchNode::IdenticalPath(SearchNode *node1, SearchNode *node2) {
179 if (node1 != NULL && node2 != NULL &&
180 node1->best_path_len_ != node2->best_path_len_) {
181 return false;
182 }
183
184 // backtrack until either a root or a NULL edge is reached
185 while (node1 != NULL && node2 != NULL) {
186 if (node1->str_ != node2->str_) {
187 return false;
188 }
189
190 // stop if either nodes is a root
191 if (node1->LangModelEdge()->IsRoot() || node2->LangModelEdge()->IsRoot()) {
192 break;
193 }
194
195 node1 = node1->parent_node_;
196 node2 = node2->parent_node_;
197 }
198
199 return ((node1 == NULL && node2 == NULL) ||
200 (node1 != NULL && node1->LangModelEdge()->IsRoot() &&
201 node2 != NULL && node2->LangModelEdge()->IsRoot()));
202 }
203
204 // Computes the language model cost of a path
205 int SearchNode::LangModCost(LangModEdge *current_lm_edge,
206 SearchNode *parent_node) {
207 int lm_cost = 0;
208 int node_cnt = 0;
209
210 do {
211 // check if root
212 bool is_root = ((current_lm_edge != NULL && current_lm_edge->IsRoot()) ||
213 parent_node == NULL);
214 if (is_root) {
215 node_cnt++;
216 lm_cost += (current_lm_edge == NULL ? 0 : current_lm_edge->PathCost());
217 }
218
219 // continue until we hit a null parent
220 if (parent_node == NULL) {
221 break;
222 }
223
224 // get the previous language model edge
225 current_lm_edge = parent_node->LangModelEdge();
226 // back track
227 parent_node = parent_node->ParentNode();
228 } while (true);
229
230 return static_cast<int>(lm_cost / static_cast<double>(node_cnt));
231 }
232 } // namespace tesseract