tesseract 4.1.1
Loading...
Searching...
No Matches
segsearch.cpp
Go to the documentation of this file.
1
2// File: segsearch.cpp
3// Description: Segmentation search functions.
4// Author: Daria Antonova
5//
6// (C) Copyright 2009, Google Inc.
7// Licensed under the Apache License, Version 2.0 (the "License");
8// you may not use this file except in compliance with the License.
9// You may obtain a copy of the License at
10// http://www.apache.org/licenses/LICENSE-2.0
11// Unless required by applicable law or agreed to in writing, software
12// distributed under the License is distributed on an "AS IS" BASIS,
13// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14// See the License for the specific language governing permissions and
15// limitations under the License.
16//
18
19#include <cstdint> // for INT32_MAX
20#include "blamer.h" // for BlamerBundle
21#include "errcode.h" // for ASSERT_HOST
22#include "genericvector.h" // for GenericVector
23#include "lm_pain_points.h" // for LMPainPoints, LM_PPTYPE_SHAPE, LMPainPoi...
24#include "lm_state.h" // for BestChoiceBundle, ViterbiStateEntry
25#include "matrix.h" // for MATRIX_COORD, MATRIX
26#include "pageres.h" // for WERD_RES
27#include "params.h" // for BoolParam, IntParam, DoubleParam
28#include "ratngs.h" // for BLOB_CHOICE_LIST, BLOB_CHOICE_IT
29#include "strngs.h" // for STRING
30#include "tesscallback.h" // for TessResultCallback2
31#include "tprintf.h" // for tprintf
32#include "wordrec.h" // for Wordrec, SegSearchPending (ptr only)
33
34namespace tesseract {
35
37 BestChoiceBundle best_choice_bundle(word_res->ratings->dimension());
38 // Run Segmentation Search.
39 SegSearch(word_res, &best_choice_bundle, nullptr);
40}
41
43 BestChoiceBundle* best_choice_bundle,
44 BlamerBundle* blamer_bundle) {
49 // Compute scaling factor that will help us recover blob outline length
50 // from classifier rating and certainty for the blob.
51 float rating_cert_scale = -1.0 * getDict().certainty_scale / rating_scale;
53 InitialSegSearch(word_res, &pain_points, &pending, best_choice_bundle,
54 blamer_bundle);
55
56 if (!SegSearchDone(0)) { // find a better choice
57 if (chop_enable && word_res->chopped_word != nullptr) {
58 improve_by_chopping(rating_cert_scale, word_res, best_choice_bundle,
59 blamer_bundle, &pain_points, &pending);
60 }
61 if (chop_debug) SEAM::PrintSeams("Final seam list:", word_res->seam_array);
62
63 if (blamer_bundle != nullptr &&
64 !blamer_bundle->ChoiceIsCorrect(word_res->best_choice)) {
65 blamer_bundle->SetChopperBlame(word_res, wordrec_debug_blamer);
66 }
67 }
68 // Keep trying to find a better path by fixing the "pain points".
69
70 MATRIX_COORD pain_point;
71 float pain_point_priority;
72 int num_futile_classifications = 0;
73 STRING blamer_debug;
74 while (wordrec_enable_assoc &&
75 (!SegSearchDone(num_futile_classifications) ||
76 (blamer_bundle != nullptr &&
77 blamer_bundle->GuidedSegsearchStillGoing()))) {
78 // Get the next valid "pain point".
79 bool found_nothing = true;
80 LMPainPointsType pp_type;
81 while ((pp_type = pain_points.Deque(&pain_point, &pain_point_priority)) !=
83 if (!pain_point.Valid(*word_res->ratings)) {
84 word_res->ratings->IncreaseBandSize(
85 pain_point.row - pain_point.col + 1);
86 }
87 if (pain_point.Valid(*word_res->ratings) &&
88 !word_res->ratings->Classified(pain_point.col, pain_point.row,
89 getDict().WildcardID())) {
90 found_nothing = false;
91 break;
92 }
93 }
94 if (found_nothing) {
95 if (segsearch_debug_level > 0) tprintf("Pain points queue is empty\n");
96 break;
97 }
98 ProcessSegSearchPainPoint(pain_point_priority, pain_point,
100 &pending, word_res, &pain_points, blamer_bundle);
101
102 UpdateSegSearchNodes(rating_cert_scale, pain_point.col, &pending,
103 word_res, &pain_points, best_choice_bundle,
104 blamer_bundle);
105 if (!best_choice_bundle->updated) ++num_futile_classifications;
106
107 if (segsearch_debug_level > 0) {
108 tprintf("num_futile_classifications %d\n", num_futile_classifications);
109 }
110
111 best_choice_bundle->updated = false; // reset updated
112
113 // See if it's time to terminate SegSearch or time for starting a guided
114 // search for the true path to find the blame for the incorrect best_choice.
115 if (SegSearchDone(num_futile_classifications) &&
116 blamer_bundle != nullptr &&
117 blamer_bundle->GuidedSegsearchNeeded(word_res->best_choice)) {
118 InitBlamerForSegSearch(word_res, &pain_points, blamer_bundle,
119 &blamer_debug);
120 }
121 } // end while loop exploring alternative paths
122 if (blamer_bundle != nullptr) {
123 blamer_bundle->FinishSegSearch(word_res->best_choice,
124 wordrec_debug_blamer, &blamer_debug);
125 }
126
127 if (segsearch_debug_level > 0) {
128 tprintf("Done with SegSearch (AcceptableChoiceFound: %d)\n",
129 language_model_->AcceptableChoiceFound());
130 }
131}
132
133// Setup and run just the initial segsearch on an established matrix,
134// without doing any additional chopping or joining.
135// (Internal factored version that can be used as part of the main SegSearch.)
138 BestChoiceBundle* best_choice_bundle,
139 BlamerBundle* blamer_bundle) {
140 if (segsearch_debug_level > 0) {
141 tprintf("Starting SegSearch on ratings matrix%s:\n",
142 wordrec_enable_assoc ? " (with assoc)" : "");
143 word_res->ratings->print(getDict().getUnicharset());
144 }
145
146 pain_points->GenerateInitial(word_res);
147
148 // Compute scaling factor that will help us recover blob outline length
149 // from classifier rating and certainty for the blob.
150 float rating_cert_scale = -1.0 * getDict().certainty_scale / rating_scale;
151
154 segsearch_max_char_wh_ratio, rating_cert_scale);
155
156 // Initialize blamer-related information: map character boxes recorded in
157 // blamer_bundle->norm_truth_word to the corresponding i,j indices in the
158 // ratings matrix. We expect this step to succeed, since when running the
159 // chopper we checked that the correct chops are present.
160 if (blamer_bundle != nullptr) {
161 blamer_bundle->SetupCorrectSegmentation(word_res->chopped_word,
163 }
164
165 // pending[col] tells whether there is update work to do to combine
166 // best_choice_bundle->beam[col - 1] with some BLOB_CHOICEs in matrix[col, *].
167 // As the language model state is updated, pending entries are modified to
168 // minimize duplication of work. It is important that during the update the
169 // children are considered in the non-decreasing order of their column, since
170 // this guarantees that all the parents would be up to date before an update
171 // of a child is done.
172 pending->init_to_size(word_res->ratings->dimension(), SegSearchPending());
173
174 // Search the ratings matrix for the initial best path.
175 (*pending)[0].SetColumnClassified();
176 UpdateSegSearchNodes(rating_cert_scale, 0, pending, word_res,
177 pain_points, best_choice_bundle, blamer_bundle);
178}
179
181 float rating_cert_scale,
182 int starting_col,
184 WERD_RES *word_res,
185 LMPainPoints *pain_points,
186 BestChoiceBundle *best_choice_bundle,
187 BlamerBundle *blamer_bundle) {
188 MATRIX *ratings = word_res->ratings;
189 ASSERT_HOST(ratings->dimension() == pending->size());
190 ASSERT_HOST(ratings->dimension() == best_choice_bundle->beam.size());
191 for (int col = starting_col; col < ratings->dimension(); ++col) {
192 if (!(*pending)[col].WorkToDo()) continue;
193 int first_row = col;
194 int last_row = std::min(ratings->dimension() - 1,
195 col + ratings->bandwidth() - 1);
196 if ((*pending)[col].SingleRow() >= 0) {
197 first_row = last_row = (*pending)[col].SingleRow();
198 }
199 if (segsearch_debug_level > 0) {
200 tprintf("\n\nUpdateSegSearchNodes: col=%d, rows=[%d,%d], alljust=%d\n",
201 col, first_row, last_row,
202 (*pending)[col].IsRowJustClassified(INT32_MAX));
203 }
204 // Iterate over the pending list for this column.
205 for (int row = first_row; row <= last_row; ++row) {
206 // Update language model state of this child+parent pair.
207 BLOB_CHOICE_LIST *current_node = ratings->get(col, row);
208 LanguageModelState *parent_node =
209 col == 0 ? nullptr : best_choice_bundle->beam[col - 1];
210 if (current_node != nullptr &&
211 language_model_->UpdateState((*pending)[col].IsRowJustClassified(row),
212 col, row, current_node, parent_node,
213 pain_points, word_res,
214 best_choice_bundle, blamer_bundle) &&
215 row + 1 < ratings->dimension()) {
216 // Since the language model state of this entry changed, process all
217 // the child column.
218 (*pending)[row + 1].RevisitWholeColumn();
219 if (segsearch_debug_level > 0) {
220 tprintf("Added child col=%d to pending\n", row + 1);
221 }
222 } // end if UpdateState.
223 } // end for row.
224 } // end for col.
225 if (best_choice_bundle->best_vse != nullptr) {
226 ASSERT_HOST(word_res->StatesAllValid());
227 if (best_choice_bundle->best_vse->updated) {
228 pain_points->GenerateFromPath(rating_cert_scale,
229 best_choice_bundle->best_vse, word_res);
230 if (!best_choice_bundle->fixpt.empty()) {
231 pain_points->GenerateFromAmbigs(best_choice_bundle->fixpt,
232 best_choice_bundle->best_vse, word_res);
233 }
234 }
235 }
236 // The segsearch is completed. Reset all updated flags on all VSEs and reset
237 // all pendings.
238 for (int col = 0; col < pending->size(); ++col) {
239 (*pending)[col].Clear();
240 ViterbiStateEntry_IT
241 vse_it(&best_choice_bundle->beam[col]->viterbi_state_entries);
242 for (vse_it.mark_cycle_pt(); !vse_it.cycled_list(); vse_it.forward()) {
243 vse_it.data()->updated = false;
244 }
245 }
246}
247
249 float pain_point_priority,
250 const MATRIX_COORD &pain_point, const char* pain_point_type,
251 GenericVector<SegSearchPending>* pending, WERD_RES *word_res,
252 LMPainPoints *pain_points, BlamerBundle *blamer_bundle) {
253 if (segsearch_debug_level > 0) {
254 tprintf("Classifying pain point %s priority=%.4f, col=%d, row=%d\n",
255 pain_point_type, pain_point_priority,
256 pain_point.col, pain_point.row);
257 }
258 ASSERT_HOST(pain_points != nullptr);
259 MATRIX *ratings = word_res->ratings;
260 // Classify blob [pain_point.col pain_point.row]
261 if (!pain_point.Valid(*ratings)) {
262 ratings->IncreaseBandSize(pain_point.row + 1 - pain_point.col);
263 }
264 ASSERT_HOST(pain_point.Valid(*ratings));
265 BLOB_CHOICE_LIST *classified = classify_piece(word_res->seam_array,
266 pain_point.col, pain_point.row,
267 pain_point_type,
268 word_res->chopped_word,
269 blamer_bundle);
270 BLOB_CHOICE_LIST *lst = ratings->get(pain_point.col, pain_point.row);
271 if (lst == nullptr) {
272 ratings->put(pain_point.col, pain_point.row, classified);
273 } else {
274 // We can not delete old BLOB_CHOICEs, since they might contain
275 // ViterbiStateEntries that are parents of other "active" entries.
276 // Thus if the matrix cell already contains classifications we add
277 // the new ones to the beginning of the list.
278 BLOB_CHOICE_IT it(lst);
279 it.add_list_before(classified);
280 delete classified; // safe to delete, since empty after add_list_before()
281 classified = nullptr;
282 }
283
284 if (segsearch_debug_level > 0) {
285 print_ratings_list("Updated ratings matrix with a new entry:",
286 ratings->get(pain_point.col, pain_point.row),
287 getDict().getUnicharset());
288 ratings->print(getDict().getUnicharset());
289 }
290
291 // Insert initial "pain points" to join the newly classified blob
292 // with its left and right neighbors.
293 if (classified != nullptr && !classified->empty()) {
294 if (pain_point.col > 0) {
295 pain_points->GeneratePainPoint(
296 pain_point.col - 1, pain_point.row, LM_PPTYPE_SHAPE, 0.0,
297 true, segsearch_max_char_wh_ratio, word_res);
298 }
299 if (pain_point.row + 1 < ratings->dimension()) {
300 pain_points->GeneratePainPoint(
301 pain_point.col, pain_point.row + 1, LM_PPTYPE_SHAPE, 0.0,
302 true, segsearch_max_char_wh_ratio, word_res);
303 }
304 }
305 (*pending)[pain_point.col].SetBlobClassified(pain_point.row);
306}
307
308// Resets enough of the results so that the Viterbi search is re-run.
309// Needed when the n-gram model is enabled, as the multi-length comparison
310// implementation will re-value existing paths to worse values.
312 BestChoiceBundle* best_choice_bundle,
314 // TODO(rays) More refactoring required here.
315 // Delete existing viterbi states.
316 for (int col = 0; col < best_choice_bundle->beam.size(); ++col) {
317 best_choice_bundle->beam[col]->Clear();
318 }
319 // Reset best_choice_bundle.
320 word_res->ClearWordChoices();
321 best_choice_bundle->best_vse = nullptr;
322 // Clear out all existing pendings and add a new one for the first column.
323 (*pending)[0].SetColumnClassified();
324 for (int i = 1; i < pending->size(); ++i)
325 (*pending)[i].Clear();
326}
327
329 LMPainPoints *pain_points,
330 BlamerBundle *blamer_bundle,
331 STRING *blamer_debug) {
332 pain_points->Clear(); // Clear pain points heap.
335 static_cast<double>(segsearch_max_char_wh_ratio), word_res);
336 blamer_bundle->InitForSegSearch(word_res->best_choice, word_res->ratings,
337 getDict().WildcardID(), wordrec_debug_blamer,
338 blamer_debug, pp_cb);
339 delete pp_cb;
340}
341
342} // namespace tesseract
void print_ratings_list(const char *msg, BLOB_CHOICE_LIST *ratings, const UNICHARSET &current_unicharset)
Definition: ratngs.cpp:837
#define ASSERT_HOST(x)
Definition: errcode.h:88
_ConstTessMemberResultCallback_5_0< false, R, T1, P1, P2, P3, P4, P5 >::base * NewPermanentTessCallback(const T1 *obj, R(T2::*member)(P1, P2, P3, P4, P5) const, typename Identity< P1 >::type p1, typename Identity< P2 >::type p2, typename Identity< P3 >::type p3, typename Identity< P4 >::type p4, typename Identity< P5 >::type p5)
Definition: tesscallback.h:258
DLLSYM void tprintf(const char *format,...)
Definition: tprintf.cpp:35
void init_to_size(int size, const T &t)
bool empty() const
Definition: genericvector.h:91
int size() const
Definition: genericvector.h:72
T get(ICOORD pos) const
Definition: matrix.h:231
void put(ICOORD pos, const T &thing)
Definition: matrix.h:223
void SetChopperBlame(const WERD_RES *word, bool debug)
Definition: blamer.cpp:318
bool GuidedSegsearchStillGoing() const
Definition: blamer.cpp:514
bool ChoiceIsCorrect(const WERD_CHOICE *word_choice) const
Definition: blamer.cpp:119
void FinishSegSearch(const WERD_CHOICE *best_choice, bool debug, STRING *debug_str)
Definition: blamer.cpp:519
void InitForSegSearch(const WERD_CHOICE *best_choice, MATRIX *ratings, UNICHAR_ID wildcard_id, bool debug, STRING *debug_str, TessResultCallback2< bool, int, int > *pp_cb)
Definition: blamer.cpp:484
bool GuidedSegsearchNeeded(const WERD_CHOICE *best_choice) const
Definition: blamer.cpp:471
void SetupCorrectSegmentation(const TWERD *word, bool debug)
Definition: blamer.cpp:415
int bandwidth() const
Definition: matrix.h:538
int dimension() const
Definition: matrix.h:536
Definition: matrix.h:578
void print(const UNICHARSET &unicharset) const
Definition: matrix.cpp:112
bool Classified(int col, int row, int wildcard_id) const
Definition: matrix.cpp:36
void IncreaseBandSize(int bandwidth)
Definition: matrix.cpp:49
bool Valid(const MATRIX &m) const
Definition: matrix.h:618
GenericVector< SEAM * > seam_array
Definition: pageres.h:214
WERD_CHOICE * best_choice
Definition: pageres.h:241
void ClearWordChoices()
Definition: pageres.cpp:1129
TWERD * chopped_word
Definition: pageres.h:212
bool StatesAllValid()
Definition: pageres.cpp:458
MATRIX * ratings
Definition: pageres.h:237
static void PrintSeams(const char *label, const GenericVector< SEAM * > &seams)
Definition: seam.cpp:167
Definition: strngs.h:45
virtual Dict & getDict()
Definition: classify.h:107
double certainty_scale
Definition: dict.h:627
bool GeneratePainPoint(int col, int row, LMPainPointsType pp_type, float special_priority, bool ok_to_extend, float max_char_wh_ratio, WERD_RES *word_res)
void GenerateInitial(WERD_RES *word_res)
bool GenerateForBlamer(double max_char_wh_ratio, WERD_RES *word_res, int col, int row)
void GenerateFromPath(float rating_cert_scale, ViterbiStateEntry *vse, WERD_RES *word_res)
static const char * PainPointDescription(LMPainPointsType type)
void GenerateFromAmbigs(const DANGERR &fixpt, ViterbiStateEntry *vse, WERD_RES *word_res)
LMPainPointsType Deque(MATRIX_COORD *pp, float *priority)
bool updated
set to true if the entry has just been created/updated
Definition: lm_state.h:194
Struct to store information maintained by various language model components.
Definition: lm_state.h:200
Bundle together all the things pertaining to the best choice/state.
Definition: lm_state.h:222
DANGERR fixpt
Places to try to fix the word suggested by ambiguity checking.
Definition: lm_state.h:234
ViterbiStateEntry * best_vse
Best ViterbiStateEntry and BLOB_CHOICE.
Definition: lm_state.h:240
bool updated
Flag to indicate whether anything was changed.
Definition: lm_state.h:232
PointerVector< LanguageModelState > beam
Definition: lm_state.h:238
void ResetNGramSearch(WERD_RES *word_res, BestChoiceBundle *best_choice_bundle, GenericVector< SegSearchPending > *pending)
Definition: segsearch.cpp:311
int segsearch_max_pain_points
Definition: wordrec.h:235
void UpdateSegSearchNodes(float rating_cert_scale, int starting_col, GenericVector< SegSearchPending > *pending, WERD_RES *word_res, LMPainPoints *pain_points, BestChoiceBundle *best_choice_bundle, BlamerBundle *blamer_bundle)
Definition: segsearch.cpp:180
WERD_CHOICE * prev_word_best_choice_
Definition: wordrec.h:476
void improve_by_chopping(float rating_cert_scale, WERD_RES *word, BestChoiceBundle *best_choice_bundle, BlamerBundle *blamer_bundle, LMPainPoints *pain_points, GenericVector< SegSearchPending > *pending)
Definition: chopper.cpp:454
int segsearch_debug_level
Definition: wordrec.h:233
void DoSegSearch(WERD_RES *word_res)
Definition: segsearch.cpp:36
bool assume_fixed_pitch_char_segment
Definition: wordrec.h:225
virtual BLOB_CHOICE_LIST * classify_piece(const GenericVector< SEAM * > &seams, int16_t start, int16_t end, const char *description, TWERD *word, BlamerBundle *blamer_bundle)
Definition: pieces.cpp:50
bool wordrec_debug_blamer
Definition: wordrec.h:231
double segsearch_max_char_wh_ratio
Definition: wordrec.h:239
bool SegSearchDone(int num_futile_classifications)
Definition: wordrec.h:486
void InitBlamerForSegSearch(WERD_RES *word_res, LMPainPoints *pain_points, BlamerBundle *blamer_bundle, STRING *blamer_debug)
Definition: segsearch.cpp:328
bool wordrec_enable_assoc
Definition: wordrec.h:198
void SegSearch(WERD_RES *word_res, BestChoiceBundle *best_choice_bundle, BlamerBundle *blamer_bundle)
Definition: segsearch.cpp:42
std::unique_ptr< LanguageModel > language_model_
Definition: wordrec.h:471
void ProcessSegSearchPainPoint(float pain_point_priority, const MATRIX_COORD &pain_point, const char *pain_point_type, GenericVector< SegSearchPending > *pending, WERD_RES *word_res, LMPainPoints *pain_points, BlamerBundle *blamer_bundle)
Definition: segsearch.cpp:248
void InitialSegSearch(WERD_RES *word_res, LMPainPoints *pain_points, GenericVector< SegSearchPending > *pending, BestChoiceBundle *best_choice_bundle, BlamerBundle *blamer_bundle)
Definition: segsearch.cpp:136