Tesseract  3.02
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
osdetect.cpp
Go to the documentation of this file.
1 
2 // File: osdetect.cpp
3 // Description: Orientation and script detection.
4 // Author: Samuel Charron
5 // Ranjith Unnikrishnan
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 //
19 
20 #include "osdetect.h"
21 
22 #include "blobbox.h"
23 #include "blread.h"
24 #include "colfind.h"
25 #include "fontinfo.h"
26 #include "imagefind.h"
27 #include "linefind.h"
28 #include "oldlist.h"
29 #include "qrsequence.h"
30 #include "ratngs.h"
31 #include "strngs.h"
32 #include "tabvector.h"
33 #include "tesseractclass.h"
34 #include "textord.h"
35 
36 const int kMinCharactersToTry = 50;
38 
39 const float kSizeRatioToReject = 2.0;
40 const int kMinAcceptableBlobHeight = 10;
41 
42 const float kOrientationAcceptRatio = 1.3;
43 const float kScriptAcceptRatio = 1.3;
44 
45 const float kHanRatioInKorean = 0.7;
46 const float kHanRatioInJapanese = 0.3;
47 
48 const float kNonAmbiguousMargin = 1.0;
49 
50 // General scripts
51 static const char* han_script = "Han";
52 static const char* latin_script = "Latin";
53 static const char* katakana_script = "Katakana";
54 static const char* hiragana_script = "Hiragana";
55 static const char* hangul_script = "Hangul";
56 
57 // Pseudo-scripts Name
58 const char* ScriptDetector::korean_script_ = "Korean";
59 const char* ScriptDetector::japanese_script_ = "Japanese";
60 const char* ScriptDetector::fraktur_script_ = "Fraktur";
61 
62 // Minimum believable resolution.
63 const int kMinCredibleResolution = 70;
64 // Default resolution used if input is not believable.
65 const int kDefaultResolution = 300;
66 
68  float first = orientations[0];
69  float second = orientations[1];
71  if (orientations[0] < orientations[1]) {
72  first = orientations[1];
73  second = orientations[0];
75  }
76  for (int i = 2; i < 4; ++i) {
77  if (orientations[i] > first) {
78  second = first;
79  first = orientations[i];
81  } else if (orientations[i] > second) {
82  second = orientations[i];
83  }
84  }
85  // Store difference of top two orientation scores.
86  best_result.oconfidence = first - second;
87 }
88 
89 void OSResults::set_best_orientation(int orientation_id) {
90  best_result.orientation_id = orientation_id;
92 }
93 
94 void OSResults::update_best_script(int orientation) {
95  // We skip index 0 to ignore the "Common" script.
96  float first = scripts_na[orientation][1];
97  float second = scripts_na[orientation][2];
99  if (scripts_na[orientation][1] < scripts_na[orientation][2]) {
100  first = scripts_na[orientation][2];
101  second = scripts_na[orientation][1];
103  }
104  for (int i = 3; i < kMaxNumberOfScripts; ++i) {
105  if (scripts_na[orientation][i] > first) {
107  second = first;
108  first = scripts_na[orientation][i];
109  } else if (scripts_na[orientation][i] > second) {
110  second = scripts_na[orientation][i];
111  }
112  }
114  (first / second - 1.0) / (kScriptAcceptRatio - 1.0);
115 }
116 
117 int OSResults::get_best_script(int orientation_id) const {
118  int max_id = -1;
119  for (int j = 0; j < kMaxNumberOfScripts; ++j) {
120  const char *script = unicharset->get_script_from_script_id(j);
121  if (strcmp(script, "Common") && strcmp(script, "NULL")) {
122  if (max_id == -1 ||
123  scripts_na[orientation_id][j] > scripts_na[orientation_id][max_id])
124  max_id = j;
125  }
126  }
127  return max_id;
128 }
129 
130 // Print the script scores for all possible orientations.
131 void OSResults::print_scores(void) const {
132  for (int i = 0; i < 4; ++i) {
133  printf("Orientation id #%d", i);
134  print_scores(i);
135  }
136 }
137 
138 // Print the script scores for the given candidate orientation.
139 void OSResults::print_scores(int orientation_id) const {
140  for (int j = 0; j < kMaxNumberOfScripts; ++j) {
141  if (scripts_na[orientation_id][j]) {
142  printf("%12s\t: %f\n", unicharset->get_script_from_script_id(j),
143  scripts_na[orientation_id][j]);
144  }
145  }
146 }
147 
148 // Accumulate scores with given OSResults instance and update the best script.
150  for (int i = 0; i < 4; ++i) {
151  orientations[i] += osr.orientations[i];
152  for (int j = 0; j < kMaxNumberOfScripts; ++j)
153  scripts_na[i][j] += osr.scripts_na[i][j];
154  }
155  unicharset = osr.unicharset;
158 }
159 
160 // Detect and erase horizontal/vertical lines and picture regions from the
161 // image, so that non-text blobs are removed from consideration.
162 void remove_nontext_regions(tesseract::Tesseract *tess, BLOCK_LIST *blocks,
163  TO_BLOCK_LIST *to_blocks) {
164  Pix *pix = tess->pix_binary();
165  ASSERT_HOST(pix != NULL);
166  int vertical_x = 0;
167  int vertical_y = 1;
168  tesseract::TabVector_LIST v_lines;
169  tesseract::TabVector_LIST h_lines;
170  const int kMinCredibleResolution = 70;
171  int resolution = (kMinCredibleResolution > pixGetXRes(pix)) ?
172  kMinCredibleResolution : pixGetXRes(pix);
173 
174  tesseract::LineFinder::FindAndRemoveLines(resolution, false, pix,
175  &vertical_x, &vertical_y,
176  NULL, &v_lines, &h_lines);
177  Pix* im_pix = tesseract::ImageFind::FindImages(pix);
178  if (im_pix != NULL) {
179  pixSubtract(pix, pix, im_pix);
180  pixDestroy(&im_pix);
181  }
182  tess->mutable_textord()->find_components(tess->pix_binary(),
183  blocks, to_blocks);
184 }
185 
186 // Find connected components in the page and process a subset until finished or
187 // a stopping criterion is met.
188 // Returns the number of blobs used in making the estimate. 0 implies failure.
190  OSResults* osr,
191  tesseract::Tesseract* tess) {
192  STRING name = filename; //truncated name
193  const char *lastdot; //of name
194  TBOX page_box;
195 
196  lastdot = strrchr (name.string (), '.');
197  if (lastdot != NULL)
198  name[lastdot-name.string()] = '\0';
199 
200  ASSERT_HOST(tess->pix_binary() != NULL)
201  int width = pixGetWidth(tess->pix_binary());
202  int height = pixGetHeight(tess->pix_binary());
203  int resolution = pixGetXRes(tess->pix_binary());
204  // Zero resolution messes up the algorithms, so make sure it is credible.
205  if (resolution < kMinCredibleResolution)
206  resolution = kDefaultResolution;
207 
208  BLOCK_LIST blocks;
209  if (!read_unlv_file(name, width, height, &blocks))
210  FullPageBlock(width, height, &blocks);
211 
212  // Try to remove non-text regions from consideration.
213  TO_BLOCK_LIST land_blocks, port_blocks;
214  remove_nontext_regions(tess, &blocks, &port_blocks);
215 
216  if (port_blocks.empty()) {
217  // page segmentation did not succeed, so we need to find_components first.
218  tess->mutable_textord()->find_components(tess->pix_binary(),
219  &blocks, &port_blocks);
220  } else {
221  page_box.set_left(0);
222  page_box.set_bottom(0);
223  page_box.set_right(width);
224  page_box.set_top(height);
225  // Filter_blobs sets up the TO_BLOCKs the same as find_components does.
226  tess->mutable_textord()->filter_blobs(page_box.topright(),
227  &port_blocks, true);
228  }
229 
230  return os_detect(&port_blocks, osr, tess);
231 }
232 
233 // Filter and sample the blobs.
234 // Returns a non-zero number of blobs if the page was successfully processed, or
235 // zero if the page had too few characters to be reliable
236 int os_detect(TO_BLOCK_LIST* port_blocks, OSResults* osr,
237  tesseract::Tesseract* tess) {
238  int blobs_total = 0;
239  TO_BLOCK_IT block_it;
240  block_it.set_to_list(port_blocks);
241 
242  BLOBNBOX_CLIST filtered_list;
243  BLOBNBOX_C_IT filtered_it(&filtered_list);
244 
245  for (block_it.mark_cycle_pt(); !block_it.cycled_list();
246  block_it.forward ()) {
247  TO_BLOCK* to_block = block_it.data();
248  if (to_block->block->poly_block() &&
249  !to_block->block->poly_block()->IsText()) continue;
250  BLOBNBOX_IT bbox_it;
251  bbox_it.set_to_list(&to_block->blobs);
252  for (bbox_it.mark_cycle_pt (); !bbox_it.cycled_list ();
253  bbox_it.forward ()) {
254  BLOBNBOX* bbox = bbox_it.data();
255  C_BLOB* blob = bbox->cblob();
256  TBOX box = blob->bounding_box();
257  ++blobs_total;
258 
259  float y_x = fabs((box.height() * 1.0) / box.width());
260  float x_y = 1.0f / y_x;
261  // Select a >= 1.0 ratio
262  float ratio = x_y > y_x ? x_y : y_x;
263  // Blob is ambiguous
264  if (ratio > kSizeRatioToReject) continue;
265  if (box.height() < kMinAcceptableBlobHeight) continue;
266  filtered_it.add_to_end(bbox);
267  }
268  }
269  return os_detect_blobs(&filtered_list, osr, tess);
270 }
271 
272 // Detect orientation and script from a list of blobs.
273 // Returns a non-zero number of blobs if the list was successfully processed, or
274 // zero if the list had too few characters to be reliable
275 int os_detect_blobs(BLOBNBOX_CLIST* blob_list, OSResults* osr,
276  tesseract::Tesseract* tess) {
277  OSResults osr_;
278  if (osr == NULL)
279  osr = &osr_;
280 
281  osr->unicharset = &tess->unicharset;
282  OrientationDetector o(osr);
283  ScriptDetector s(osr, tess);
284 
285  BLOBNBOX_C_IT filtered_it(blob_list);
286  int real_max = MIN(filtered_it.length(), kMaxCharactersToTry);
287  // printf("Total blobs found = %d\n", blobs_total);
288  // printf("Number of blobs post-filtering = %d\n", filtered_it.length());
289  // printf("Number of blobs to try = %d\n", real_max);
290 
291  // If there are too few characters, skip this page entirely.
292  if (real_max < kMinCharactersToTry / 2) {
293  printf("Too few characters. Skipping this page\n");
294  return 0;
295  }
296 
297  BLOBNBOX** blobs = new BLOBNBOX*[filtered_it.length()];
298  int number_of_blobs = 0;
299  for (filtered_it.mark_cycle_pt (); !filtered_it.cycled_list ();
300  filtered_it.forward ()) {
301  blobs[number_of_blobs++] = (BLOBNBOX*)filtered_it.data();
302  }
303  QRSequenceGenerator sequence(number_of_blobs);
304  int num_blobs_evaluated = 0;
305  for (int i = 0; i < real_max; ++i) {
306  if (os_detect_blob(blobs[sequence.GetVal()], &o, &s, osr, tess)
307  && i > kMinCharactersToTry) {
308  break;
309  }
310  ++num_blobs_evaluated;
311  }
312  delete [] blobs;
313 
314  // Make sure the best_result is up-to-date
315  int orientation = o.get_orientation();
316  osr->update_best_script(orientation);
317  return num_blobs_evaluated;
318 }
319 
320 // Processes a single blob to estimate script and orientation.
321 // Return true if estimate of orientation and script satisfies stopping
322 // criteria.
324  ScriptDetector* s, OSResults* osr,
325  tesseract::Tesseract* tess) {
326  tess->tess_cn_matching.set_value(true); // turn it on
327  tess->tess_bn_matching.set_value(false);
328  C_BLOB* blob = bbox->cblob();
329  TBLOB* tblob = TBLOB::PolygonalCopy(blob);
330  TBOX box = tblob->bounding_box();
331  FCOORD current_rotation(1.0f, 0.0f);
332  FCOORD rotation90(0.0f, 1.0f);
333  BLOB_CHOICE_LIST ratings[4];
334  // Test the 4 orientations
335  for (int i = 0; i < 4; ++i) {
336  // Normalize the blob. Set the origin to the place we want to be the
337  // bottom-middle after rotation.
338  // Scaling is to make the rotated height the x-height.
339  float scaling = static_cast<float>(kBlnXHeight) / box.height();
340  float x_origin = (box.left() + box.right()) / 2.0f;
341  float y_origin = (box.bottom() + box.top()) / 2.0f;
342  if (i == 0 || i == 2) {
343  // Rotation is 0 or 180.
344  y_origin = i == 0 ? box.bottom() : box.top();
345  } else {
346  // Rotation is 90 or 270.
347  scaling = static_cast<float>(kBlnXHeight) / box.width();
348  x_origin = i == 1 ? box.left() : box.right();
349  }
350  DENORM denorm;
351  denorm.SetupNormalization(NULL, NULL, &current_rotation, NULL, NULL, 0,
352  x_origin, y_origin, scaling, scaling,
353  0.0f, static_cast<float>(kBlnBaselineOffset));
354  TBLOB* rotated_blob = new TBLOB(*tblob);
355  rotated_blob->Normalize(denorm);
356  tess->AdaptiveClassifier(rotated_blob, denorm, ratings + i, NULL);
357  delete rotated_blob;
358  current_rotation.rotate(rotation90);
359  }
360  delete tblob;
361 
362  bool stop = o->detect_blob(ratings);
363  s->detect_blob(ratings);
364  int orientation = o->get_orientation();
365  stop = s->must_stop(orientation) && stop;
366  return stop;
367 }
368 
369 
371  osr_ = osr;
372 }
373 
374 // Score the given blob and return true if it is now sure of the orientation
375 // after adding this block.
376 bool OrientationDetector::detect_blob(BLOB_CHOICE_LIST* scores) {
377  float blob_o_score[4] = {0.0, 0.0, 0.0, 0.0};
378  float total_blob_o_score = 0.0;
379 
380  for (int i = 0; i < 4; ++i) {
381  BLOB_CHOICE_IT choice_it;
382  choice_it.set_to_list(scores + i);
383  if (!choice_it.empty()) {
384  // The certainty score ranges between [-20,0]. This is converted here to
385  // [0,1], with 1 indicating best match.
386  blob_o_score[i] = 1 + 0.05 * choice_it.data()->certainty();
387  total_blob_o_score += blob_o_score[i];
388  }
389  }
390  // Normalize the orientation scores for the blob and use them to
391  // update the aggregated orientation score.
392  for (int i = 0; total_blob_o_score != 0 && i < 4; ++i) {
393  osr_->orientations[i] += log(blob_o_score[i] / total_blob_o_score);
394  }
395 
396  float first = -1;
397  float second = -1;
398 
399  int idx = -1;
400  for (int i = 0; i < 4; ++i) {
401  if (osr_->orientations[i] > first) {
402  idx = i;
403  second = first;
404  first = osr_->orientations[i];
405  } else if (osr_->orientations[i] > second) {
406  second = osr_->orientations[i];
407  }
408  }
409 
410  return first / second > kOrientationAcceptRatio;
411 }
412 
414  osr_->update_best_orientation();
415  return osr_->best_result.orientation_id;
416 }
417 
418 
420  osr_ = osr;
421  tess_ = tess;
422  katakana_id_ = tess_->unicharset.add_script(katakana_script);
423  hiragana_id_ = tess_->unicharset.add_script(hiragana_script);
424  han_id_ = tess_->unicharset.add_script(han_script);
425  hangul_id_ = tess_->unicharset.add_script(hangul_script);
426  japanese_id_ = tess_->unicharset.add_script(japanese_script_);
427  korean_id_ = tess_->unicharset.add_script(korean_script_);
428  latin_id_ = tess_->unicharset.add_script(latin_script);
429  fraktur_id_ = tess_->unicharset.add_script(fraktur_script_);
430 }
431 
432 
433 // Score the given blob and return true if it is now sure of the script after
434 // adding this blob.
435 void ScriptDetector::detect_blob(BLOB_CHOICE_LIST* scores) {
436  bool done[kMaxNumberOfScripts];
437  for (int i = 0; i < 4; ++i) {
438  for (int j = 0; j < kMaxNumberOfScripts; ++j)
439  done[j] = false;
440 
441  BLOB_CHOICE_IT choice_it;
442  choice_it.set_to_list(scores + i);
443 
444  float prev_score = -1;
445  int script_count = 0;
446  int prev_id = -1;
447  int prev_script;
448  int prev_class_id = -1;
449  int prev_fontinfo_id = -1;
450  const char* prev_unichar = "";
451  const char* unichar = "";
452  float next_best_score = -1.0;
453  int next_best_script_id = -1;
454  const char* next_best_unichar = "";
455 
456  for (choice_it.mark_cycle_pt(); !choice_it.cycled_list();
457  choice_it.forward()) {
458  BLOB_CHOICE* choice = choice_it.data();
459  int id = choice->script_id();
460  // Script already processed before.
461  if (done[id]) continue;
462  done[id] = true;
463 
464  unichar = tess_->unicharset.id_to_unichar(choice->unichar_id());
465  // Save data from the first match
466  if (prev_score < 0) {
467  prev_score = -choice->certainty();
468  script_count = 1;
469  prev_id = id;
470  prev_script = choice->script_id();
471  prev_unichar = unichar;
472  prev_class_id = choice->unichar_id();
473  prev_fontinfo_id = choice->fontinfo_id();
474  } else if (-choice->certainty() < prev_score + kNonAmbiguousMargin) {
475  ++script_count;
476  next_best_score = -choice->certainty();
477  next_best_script_id = choice->script_id();
478  next_best_unichar = tess_->unicharset.id_to_unichar(choice->unichar_id());
479  }
480 
481  if (strlen(prev_unichar) == 1)
482  if (unichar[0] >= '0' && unichar[0] <= '9')
483  break;
484 
485  // if script_count is >= 2, character is ambiguous, skip other matches
486  // since they are useless.
487  if (script_count >= 2)
488  break;
489  }
490  // Character is non ambiguous
491  if (script_count == 1) {
492  // Update the score of the winning script
493  osr_->scripts_na[i][prev_id] += 1.0;
494 
495  // Workaround for Fraktur
496  if (prev_id == latin_id_) {
497  if (prev_fontinfo_id >= 0) {
498  const tesseract::FontInfo &fi =
499  tess_->get_fontinfo_table().get(prev_fontinfo_id);
500  //printf("Font: %s i:%i b:%i f:%i s:%i k:%i (%s)\n", fi.name,
501  // fi.is_italic(), fi.is_bold(), fi.is_fixed_pitch(),
502  // fi.is_serif(), fi.is_fraktur(),
503  // prev_unichar);
504  if (fi.is_fraktur()) {
505  osr_->scripts_na[i][prev_id] -= 1.0;
506  osr_->scripts_na[i][fraktur_id_] += 1.0;
507  }
508  }
509  }
510 
511  // Update Japanese / Korean pseudo-scripts
512  if (prev_id == katakana_id_)
513  osr_->scripts_na[i][japanese_id_] += 1.0;
514  if (prev_id == hiragana_id_)
515  osr_->scripts_na[i][japanese_id_] += 1.0;
516  if (prev_id == hangul_id_)
517  osr_->scripts_na[i][korean_id_] += 1.0;
518  if (prev_id == han_id_)
519  osr_->scripts_na[i][korean_id_] += kHanRatioInKorean;
520  if (prev_id == han_id_)
521  osr_->scripts_na[i][japanese_id_] += kHanRatioInJapanese;
522  }
523  } // iterate over each orientation
524 }
525 
526 bool ScriptDetector::must_stop(int orientation) {
527  osr_->update_best_script(orientation);
528  return osr_->best_result.sconfidence > 1;
529 }
530 
531 // Helper method to convert an orientation index to its value in degrees.
532 // The value represents the amount of clockwise rotation in degrees that must be
533 // applied for the text to be upright (readable).
534 const int OrientationIdToValue(const int& id) {
535  switch (id) {
536  case 0:
537  return 0;
538  case 1:
539  return 270;
540  case 2:
541  return 180;
542  case 3:
543  return 90;
544  default:
545  return -1;
546  }
547 }