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
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;
37 const int kMaxCharactersToTry = 5 * kMinCharactersToTry;
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
67 void OSResults::update_best_orientation() {
68 float first = orientations[0];
69 float second = orientations[1];
70 best_result.orientation_id = 0;
71 if (orientations[0] < orientations[1]) {
72 first = orientations[1];
73 second = orientations[0];
74 best_result.orientation_id = 1;
75 }
76 for (int i = 2; i < 4; ++i) {
77 if (orientations[i] > first) {
78 second = first;
79 first = orientations[i];
80 best_result.orientation_id = 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;
91 best_result.oconfidence = 0;
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];
98 best_result.script_id = 1;
99 if (scripts_na[orientation][1] < scripts_na[orientation][2]) {
100 first = scripts_na[orientation][2];
101 second = scripts_na[orientation][1];
102 best_result.script_id = 2;
103 }
104 for (int i = 3; i < kMaxNumberOfScripts; ++i) {
105 if (scripts_na[orientation][i] > first) {
106 best_result.script_id = i;
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 }
113 best_result.sconfidence =
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.
149 void OSResults::accumulate(const OSResults& osr) {
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;
156 update_best_orientation();
157 update_best_script(best_result.orientation_id);
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.
189 int orientation_and_script_detection(STRING& filename,
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.
323 bool os_detect_blob(BLOBNBOX* bbox, OrientationDetector* o,
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
370 OrientationDetector::OrientationDetector(OSResults* osr) {
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
413 int OrientationDetector::get_orientation() {
414 osr_->update_best_orientation();
415 return osr_->best_result.orientation_id;
416 }
417
418
419 ScriptDetector::ScriptDetector(OSResults* osr, tesseract::Tesseract* tess) {
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 }