tesseract 4.1.1
Loading...
Searching...
No Matches
equationdetect.cpp
Go to the documentation of this file.
1
2// File: equationdetect.cpp
3// Description: Helper classes to detect equations.
4// Author: Zongyi (Joe) Liu (joeliu@google.com)
5//
6// (C) Copyright 2011, 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#ifdef __MINGW32__
20#include <limits.h>
21#endif
22
23#include <algorithm>
24#include <cfloat>
25#include <limits>
26#include <memory>
27
28// Include automatically generated configuration file if running autoconf.
29#ifdef HAVE_CONFIG_H
30#include "config_auto.h"
31#endif
32
33#include "equationdetect.h"
34
35#include "bbgrid.h"
36#include "classify.h"
37#include "colpartition.h"
38#include "colpartitiongrid.h"
39#include "colpartitionset.h"
40#include "helpers.h"
41#include "ratngs.h"
42#include "tesseractclass.h"
43
44// Config variables.
45static BOOL_VAR(equationdetect_save_bi_image, false, "Save input bi image");
46static BOOL_VAR(equationdetect_save_spt_image, false, "Save special character image");
47static BOOL_VAR(equationdetect_save_seed_image, false, "Save the seed image");
48static BOOL_VAR(equationdetect_save_merged_image, false, "Save the merged image");
49
50namespace tesseract {
51
53// Utility ColParition sort functions.
55static int SortCPByTopReverse(const void* p1, const void* p2) {
56 const ColPartition* cp1 = *static_cast<ColPartition* const*>(p1);
57 const ColPartition* cp2 = *static_cast<ColPartition* const*>(p2);
58 ASSERT_HOST(cp1 != nullptr && cp2 != nullptr);
59 const TBOX &box1(cp1->bounding_box()), &box2(cp2->bounding_box());
60 return box2.top() - box1.top();
61}
62
63static int SortCPByBottom(const void* p1, const void* p2) {
64 const ColPartition* cp1 = *static_cast<ColPartition* const*>(p1);
65 const ColPartition* cp2 = *static_cast<ColPartition* const*>(p2);
66 ASSERT_HOST(cp1 != nullptr && cp2 != nullptr);
67 const TBOX &box1(cp1->bounding_box()), &box2(cp2->bounding_box());
68 return box1.bottom() - box2.bottom();
69}
70
71static int SortCPByHeight(const void* p1, const void* p2) {
72 const ColPartition* cp1 = *static_cast<ColPartition* const*>(p1);
73 const ColPartition* cp2 = *static_cast<ColPartition* const*>(p2);
74 ASSERT_HOST(cp1 != nullptr && cp2 != nullptr);
75 const TBOX &box1(cp1->bounding_box()), &box2(cp2->bounding_box());
76 return box1.height() - box2.height();
77}
78
79// TODO(joeliu): we may want to parameterize these constants.
80const float kMathDigitDensityTh1 = 0.25;
81const float kMathDigitDensityTh2 = 0.1;
82const float kMathItalicDensityTh = 0.5;
83const float kUnclearDensityTh = 0.25;
84const int kSeedBlobsCountTh = 10;
86
87// Returns true if PolyBlockType is of text type or equation type.
89 return PTIsTextType(type) || type == PT_EQUATION;
90}
91
93 return type == EquationDetect::LEFT_INDENT ||
95}
96
98 return type == EquationDetect::RIGHT_INDENT ||
100}
101
102EquationDetect::EquationDetect(const char* equ_datapath,
103 const char* equ_name) {
104 const char* default_name = "equ";
105 if (equ_name == nullptr) {
106 equ_name = default_name;
107 }
108 lang_tesseract_ = nullptr;
109 resolution_ = 0;
110 page_count_ = 0;
111
112 if (equ_tesseract_.init_tesseract(equ_datapath, equ_name,
114 tprintf("Warning: equation region detection requested,"
115 " but %s failed to load from %s\n", equ_name, equ_datapath);
116 }
117
118 cps_super_bbox_ = nullptr;
119}
120
122
124 lang_tesseract_ = lang_tesseract;
125}
126
127void EquationDetect::SetResolution(const int resolution) {
128 resolution_ = resolution;
129}
130
132 if (to_block == nullptr) {
133 tprintf("Warning: input to_block is nullptr!\n");
134 return -1;
135 }
136
138 blob_lists.push_back(&(to_block->blobs));
139 blob_lists.push_back(&(to_block->large_blobs));
140 for (int i = 0; i < blob_lists.size(); ++i) {
141 BLOBNBOX_IT bbox_it(blob_lists[i]);
142 for (bbox_it.mark_cycle_pt (); !bbox_it.cycled_list();
143 bbox_it.forward()) {
144 bbox_it.data()->set_special_text_type(BSTT_NONE);
145 }
146 }
147
148 return 0;
149}
150
152 BLOBNBOX *blobnbox, const int height_th) {
153 ASSERT_HOST(blobnbox != nullptr);
154 if (blobnbox->bounding_box().height() < height_th && height_th > 0) {
155 // For small blob, we simply set to BSTT_NONE.
157 return;
158 }
159
160 BLOB_CHOICE_LIST ratings_equ, ratings_lang;
161 C_BLOB* blob = blobnbox->cblob();
162 // TODO(joeliu/rays) Fix this. We may have to normalize separately for
163 // each classifier here, as they may require different PolygonalCopy.
164 TBLOB* tblob = TBLOB::PolygonalCopy(false, blob);
165 const TBOX& box = tblob->bounding_box();
166
167 // Normalize the blob. Set the origin to the place we want to be the
168 // bottom-middle, and scaling is to make the height the x-height.
169 const float scaling = static_cast<float>(kBlnXHeight) / box.height();
170 const float x_orig = (box.left() + box.right()) / 2.0f, y_orig = box.bottom();
171 std::unique_ptr<TBLOB> normed_blob(new TBLOB(*tblob));
172 normed_blob->Normalize(nullptr, nullptr, nullptr, x_orig, y_orig, scaling, scaling,
173 0.0f, static_cast<float>(kBlnBaselineOffset),
174 false, nullptr);
175 equ_tesseract_.AdaptiveClassifier(normed_blob.get(), &ratings_equ);
176 lang_tesseract_->AdaptiveClassifier(normed_blob.get(), &ratings_lang);
177 delete tblob;
178
179 // Get the best choice from ratings_lang and rating_equ. As the choice in the
180 // list has already been sorted by the certainty, we simply use the first
181 // choice.
182 BLOB_CHOICE *lang_choice = nullptr, *equ_choice = nullptr;
183 if (ratings_lang.length() > 0) {
184 BLOB_CHOICE_IT choice_it(&ratings_lang);
185 lang_choice = choice_it.data();
186 }
187 if (ratings_equ.length() > 0) {
188 BLOB_CHOICE_IT choice_it(&ratings_equ);
189 equ_choice = choice_it.data();
190 }
191
192 const float lang_score = lang_choice ? lang_choice->certainty() : -FLT_MAX;
193 const float equ_score = equ_choice ? equ_choice->certainty() : -FLT_MAX;
194
195 const float kConfScoreTh = -5.0f, kConfDiffTh = 1.8;
196 // The scores here are negative, so the max/min == fabs(min/max).
197 // float ratio = fmax(lang_score, equ_score) / fmin(lang_score, equ_score);
198 const float diff = fabs(lang_score - equ_score);
200
201 // Classification.
202 if (fmax(lang_score, equ_score) < kConfScoreTh) {
203 // If both score are very small, then mark it as unclear.
204 type = BSTT_UNCLEAR;
205 } else if (diff > kConfDiffTh && equ_score > lang_score) {
206 // If equ_score is significantly higher, then we classify this character as
207 // math symbol.
208 type = BSTT_MATH;
209 } else if (lang_choice) {
210 // For other cases: lang_score is similar or significantly higher.
212 lang_tesseract_->unicharset, lang_choice->unichar_id());
213 }
214
215 if (type == BSTT_NONE && lang_tesseract_->get_fontinfo_table().get(
216 lang_choice->fontinfo_id()).is_italic()) {
217 // For text symbol, we still check if it is italic.
219 } else {
220 blobnbox->set_special_text_type(type);
221 }
222}
223
225 const UNICHARSET& unicharset, const UNICHAR_ID id) const {
226 const STRING s = unicharset.id_to_unichar(id);
227 if (unicharset.get_isalpha(id)) {
228 return BSTT_NONE;
229 }
230
231 if (unicharset.get_ispunctuation(id)) {
232 // Exclude some special texts that are likely to be confused as math symbol.
233 static GenericVector<UNICHAR_ID> ids_to_exclude;
234 if (ids_to_exclude.empty()) {
235 static const STRING kCharsToEx[] = {"'", "`", "\"", "\\", ",", ".",
236 "〈", "〉", "《", "》", "」", "「", ""};
237 int i = 0;
238 while (kCharsToEx[i] != "") {
239 ids_to_exclude.push_back(
240 unicharset.unichar_to_id(kCharsToEx[i++].string()));
241 }
242 ids_to_exclude.sort();
243 }
244 return ids_to_exclude.bool_binary_search(id) ? BSTT_NONE : BSTT_MATH;
245 }
246
247 // Check if it is digit. In addition to the isdigit attribute, we also check
248 // if this character belongs to those likely to be confused with a digit.
249 static const STRING kDigitsChars = "|";
250 if (unicharset.get_isdigit(id) ||
251 (s.length() == 1 && kDigitsChars.contains(s[0]))) {
252 return BSTT_DIGIT;
253 } else {
254 return BSTT_MATH;
255 }
256}
257
259 // Set configuration for Tesseract::AdaptiveClassifier.
260 equ_tesseract_.tess_cn_matching.set_value(1); // turn it on
261 equ_tesseract_.tess_bn_matching.set_value(0);
262
263 // Set the multiplier to zero for lang_tesseract_ to improve the accuracy.
264 const int classify_class_pruner = lang_tesseract_->classify_class_pruner_multiplier;
265 const int classify_integer_matcher =
269
271 ColPartition *part = nullptr;
272 gsearch.StartFullSearch();
273 while ((part = gsearch.NextFullSearch()) != nullptr) {
274 if (!IsTextOrEquationType(part->type())) {
275 continue;
276 }
278 BLOBNBOX_C_IT bbox_it(part->boxes());
279 // Compute the height threshold.
280 GenericVector<int> blob_heights;
281 for (bbox_it.mark_cycle_pt (); !bbox_it.cycled_list();
282 bbox_it.forward()) {
283 if (bbox_it.data()->special_text_type() != BSTT_SKIP) {
284 blob_heights.push_back(bbox_it.data()->bounding_box().height());
285 }
286 }
287 blob_heights.sort();
288 const int height_th = blob_heights[blob_heights.size() / 2] / 3 * 2;
289 for (bbox_it.mark_cycle_pt (); !bbox_it.cycled_list();
290 bbox_it.forward()) {
291 if (bbox_it.data()->special_text_type() != BSTT_SKIP) {
292 IdentifySpecialText(bbox_it.data(), height_th);
293 }
294 }
295 }
296
297 // Set the multiplier values back.
299 classify_class_pruner);
301 classify_integer_matcher);
302
303 if (equationdetect_save_spt_image) { // For debug.
304 STRING outfile;
305 GetOutputTiffName("_spt", &outfile);
306 PaintSpecialTexts(outfile);
307 }
308}
309
311 ASSERT_HOST(part);
312 BLOBNBOX_C_IT blob_it(part->boxes());
313
314 for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
315 // At this moment, no blob should have been joined.
316 ASSERT_HOST(!blob_it.data()->joined_to_prev());
317 }
318 for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
319 BLOBNBOX* blob = blob_it.data();
320 if (blob->joined_to_prev() || blob->special_text_type() == BSTT_SKIP) {
321 continue;
322 }
323 TBOX blob_box = blob->bounding_box();
324
325 // Search if any blob can be merged into blob. If found, then we mark all
326 // these blobs as BSTT_SKIP.
327 BLOBNBOX_C_IT blob_it2 = blob_it;
328 bool found = false;
329 while (!blob_it2.at_last()) {
330 BLOBNBOX* nextblob = blob_it2.forward();
331 const TBOX& nextblob_box = nextblob->bounding_box();
332 if (nextblob_box.left() >= blob_box.right()) {
333 break;
334 }
335 const float kWidthR = 0.4, kHeightR = 0.3;
336 const bool xoverlap = blob_box.major_x_overlap(nextblob_box),
337 yoverlap = blob_box.y_overlap(nextblob_box);
338 const float widthR = static_cast<float>(
339 std::min(nextblob_box.width(), blob_box.width())) /
340 std::max(nextblob_box.width(), blob_box.width());
341 const float heightR = static_cast<float>(
342 std::min(nextblob_box.height(), blob_box.height())) /
343 std::max(nextblob_box.height(), blob_box.height());
344
345 if (xoverlap && yoverlap && widthR > kWidthR && heightR > kHeightR) {
346 // Found one, set nextblob type and recompute blob_box.
347 found = true;
349 blob_box += nextblob_box;
350 }
351 }
352 if (found) {
354 }
355 }
356}
357
359 ColPartitionGrid* part_grid, ColPartitionSet** best_columns) {
360 if (!lang_tesseract_) {
361 tprintf("Warning: lang_tesseract_ is nullptr!\n");
362 return -1;
363 }
364 if (!part_grid || !best_columns) {
365 tprintf("part_grid/best_columns is nullptr!!\n");
366 return -1;
367 }
368 cp_seeds_.clear();
369 part_grid_ = part_grid;
370 best_columns_ = best_columns;
372 STRING outfile;
373 page_count_++;
374
375 if (equationdetect_save_bi_image) {
376 GetOutputTiffName("_bi", &outfile);
377 pixWrite(outfile.string(), lang_tesseract_->pix_binary(), IFF_TIFF_G4);
378 }
379
380 // Pass 0: Compute special text type for blobs.
382
383 // Pass 1: Merge parts by overlap.
385
386 // Pass 2: compute the math blob density and find the seed partition.
388 // We still need separate seed into block seed and inline seed partition.
390
391 if (equationdetect_save_seed_image) {
392 GetOutputTiffName("_seed", &outfile);
393 PaintColParts(outfile);
394 }
395
396 // Pass 3: expand block equation seeds.
397 while (!cp_seeds_.empty()) {
398 GenericVector<ColPartition*> seeds_expanded;
399 for (int i = 0; i < cp_seeds_.size(); ++i) {
400 if (ExpandSeed(cp_seeds_[i])) {
401 // If this seed is expanded, then we add it into seeds_expanded. Note
402 // this seed has been removed from part_grid_ if it is expanded.
403 seeds_expanded.push_back(cp_seeds_[i]);
404 }
405 }
406 // Add seeds_expanded back into part_grid_ and reset cp_seeds_.
407 for (int i = 0; i < seeds_expanded.size(); ++i) {
408 InsertPartAfterAbsorb(seeds_expanded[i]);
409 }
410 cp_seeds_ = seeds_expanded;
411 }
412
413 // Pass 4: find math block satellite text partitions and merge them.
415
416 if (equationdetect_save_merged_image) { // For debug.
417 GetOutputTiffName("_merged", &outfile);
418 PaintColParts(outfile);
419 }
420
421 return 0;
422}
423
425 while (true) {
426 ColPartition* part = nullptr;
427 // partitions that have been updated.
428 GenericVector<ColPartition*> parts_updated;
430 gsearch.StartFullSearch();
431 while ((part = gsearch.NextFullSearch()) != nullptr) {
432 if (!IsTextOrEquationType(part->type())) {
433 continue;
434 }
435 GenericVector<ColPartition*> parts_to_merge;
436 SearchByOverlap(part, &parts_to_merge);
437 if (parts_to_merge.empty()) {
438 continue;
439 }
440
441 // Merge parts_to_merge with part, and remove them from part_grid_.
442 part_grid_->RemoveBBox(part);
443 for (int i = 0; i < parts_to_merge.size(); ++i) {
444 ASSERT_HOST(parts_to_merge[i] != nullptr && parts_to_merge[i] != part);
445 part->Absorb(parts_to_merge[i], nullptr);
446 }
447 gsearch.RepositionIterator();
448
449 parts_updated.push_back(part);
450 }
451
452 if (parts_updated.empty()) { // Exit the loop
453 break;
454 }
455
456 // Re-insert parts_updated into part_grid_.
457 for (int i = 0; i < parts_updated.size(); ++i) {
458 InsertPartAfterAbsorb(parts_updated[i]);
459 }
460 }
461}
462
464 ColPartition* seed,
465 GenericVector<ColPartition*>* parts_overlap) {
466 ASSERT_HOST(seed != nullptr && parts_overlap != nullptr);
467 if (!IsTextOrEquationType(seed->type())) {
468 return;
469 }
471 const TBOX& seed_box(seed->bounding_box());
472 const int kRadNeighborCells = 30;
473 search.StartRadSearch((seed_box.left() + seed_box.right()) / 2,
474 (seed_box.top() + seed_box.bottom()) / 2,
475 kRadNeighborCells);
476 search.SetUniqueMode(true);
477
478 // Search iteratively.
479 ColPartition *part;
481 const float kLargeOverlapTh = 0.95;
482 const float kEquXOverlap = 0.4, kEquYOverlap = 0.5;
483 while ((part = search.NextRadSearch()) != nullptr) {
484 if (part == seed || !IsTextOrEquationType(part->type())) {
485 continue;
486 }
487 const TBOX& part_box(part->bounding_box());
488 bool merge = false;
489
490 const float x_overlap_fraction = part_box.x_overlap_fraction(seed_box),
491 y_overlap_fraction = part_box.y_overlap_fraction(seed_box);
492
493 // If part is large overlapped with seed, then set merge to true.
494 if (x_overlap_fraction >= kLargeOverlapTh &&
495 y_overlap_fraction >= kLargeOverlapTh) {
496 merge = true;
497 } else if (seed->type() == PT_EQUATION &&
498 IsTextOrEquationType(part->type())) {
499 if ((x_overlap_fraction > kEquXOverlap && y_overlap_fraction > 0.0) ||
500 (x_overlap_fraction > 0.0 && y_overlap_fraction > kEquYOverlap)) {
501 merge = true;
502 }
503 }
504
505 if (merge) { // Remove the part from search and put it into parts.
506 search.RemoveBBox();
507 parts_overlap->push_back(part);
508 }
509 }
510}
511
513 ASSERT_HOST(part);
514
515 // Before insert part back into part_grid_, we will need re-compute some
516 // of its attributes such as first_column_, last_column_. However, we still
517 // want to preserve its type.
518 BlobTextFlowType flow_type = part->flow();
519 PolyBlockType part_type = part->type();
520 BlobRegionType blob_type = part->blob_type();
521
522 // Call SetPartitionType to re-compute the attributes of part.
523 const TBOX& part_box(part->bounding_box());
524 int grid_x, grid_y;
526 part_box.left(), part_box.bottom(), &grid_x, &grid_y);
528
529 // Reset the types back.
530 part->set_type(part_type);
531 part->set_blob_type(blob_type);
532 part->set_flow(flow_type);
533 part->SetBlobTypes();
534
535 // Insert into part_grid_.
536 part_grid_->InsertBBox(true, true, part);
537}
538
541 ColPartition *part = nullptr;
542 gsearch.StartFullSearch();
543
544 GenericVector<ColPartition*> seeds1, seeds2;
545 // The left coordinates of indented text partitions.
546 GenericVector<int> indented_texts_left;
547 // The foreground density of text partitions.
548 GenericVector<float> texts_foreground_density;
549 while ((part = gsearch.NextFullSearch()) != nullptr) {
550 if (!IsTextOrEquationType(part->type())) {
551 continue;
552 }
554 const bool blobs_check = CheckSeedBlobsCount(part);
555 const int kTextBlobsTh = 20;
556
558 blobs_check) {
559 // Passed high density threshold test, save into seeds1.
560 seeds1.push_back(part);
561 } else {
562 IndentType indent = IsIndented(part);
563 if (IsLeftIndented(indent) && blobs_check &&
565 // Passed low density threshold test and is indented, save into seeds2.
566 seeds2.push_back(part);
567 } else if (!IsRightIndented(indent) &&
568 part->boxes_count() > kTextBlobsTh) {
569 // This is likely to be a text part, save the features.
570 const TBOX&box = part->bounding_box();
571 if (IsLeftIndented(indent)) {
572 indented_texts_left.push_back(box.left());
573 }
574 texts_foreground_density.push_back(ComputeForegroundDensity(box));
575 }
576 }
577 }
578
579 // Sort the features collected from text regions.
580 indented_texts_left.sort();
581 texts_foreground_density.sort();
582 float foreground_density_th = 0.15; // Default value.
583 if (!texts_foreground_density.empty()) {
584 // Use the median of the texts_foreground_density.
585 foreground_density_th = 0.8 * texts_foreground_density[
586 texts_foreground_density.size() / 2];
587 }
588
589 for (int i = 0; i < seeds1.size(); ++i) {
590 const TBOX& box = seeds1[i]->bounding_box();
591 if (CheckSeedFgDensity(foreground_density_th, seeds1[i]) &&
592 !(IsLeftIndented(IsIndented(seeds1[i])) &&
593 CountAlignment(indented_texts_left, box.left()) >=
595 // Mark as PT_EQUATION type.
596 seeds1[i]->set_type(PT_EQUATION);
597 cp_seeds_.push_back(seeds1[i]);
598 } else { // Mark as PT_INLINE_EQUATION type.
599 seeds1[i]->set_type(PT_INLINE_EQUATION);
600 }
601 }
602
603 for (int i = 0; i < seeds2.size(); ++i) {
604 if (CheckForSeed2(indented_texts_left, foreground_density_th, seeds2[i])) {
605 seeds2[i]->set_type(PT_EQUATION);
606 cp_seeds_.push_back(seeds2[i]);
607 }
608 }
609}
610
612 Pix *pix_bi = lang_tesseract_->pix_binary();
613 const int pix_height = pixGetHeight(pix_bi);
614 Box* box = boxCreate(tbox.left(), pix_height - tbox.top(),
615 tbox.width(), tbox.height());
616 Pix *pix_sub = pixClipRectangle(pix_bi, box, nullptr);
617 l_float32 fract;
618 pixForegroundFraction(pix_sub, &fract);
619 pixDestroy(&pix_sub);
620 boxDestroy(&box);
621
622 return fract;
623}
624
625bool EquationDetect::CheckSeedFgDensity(const float density_th,
626 ColPartition* part) {
627 ASSERT_HOST(part);
628
629 // Split part horizontall, and check for each sub part.
630 GenericVector<TBOX> sub_boxes;
631 SplitCPHorLite(part, &sub_boxes);
632 float parts_passed = 0.0;
633 for (int i = 0; i < sub_boxes.size(); ++i) {
634 const float density = ComputeForegroundDensity(sub_boxes[i]);
635 if (density < density_th) {
636 parts_passed++;
637 }
638 }
639
640 // If most sub parts passed, then we return true.
641 const float kSeedPartRatioTh = 0.3;
642 bool retval = (parts_passed / sub_boxes.size() >= kSeedPartRatioTh);
643
644 return retval;
645}
646
648 GenericVector<ColPartition*>* parts_splitted) {
649 ASSERT_HOST(part && parts_splitted);
650 if (part->median_width() == 0 || part->boxes_count() == 0) {
651 return;
652 }
653
654 // Make a copy of part, and reset parts_splitted.
655 ColPartition* right_part = part->CopyButDontOwnBlobs();
656 parts_splitted->delete_data_pointers();
657 parts_splitted->clear();
658
659 const double kThreshold = part->median_width() * 3.0;
660 bool found_split = true;
661 while (found_split) {
662 found_split = false;
663 BLOBNBOX_C_IT box_it(right_part->boxes());
664 // Blobs are sorted left side first. If blobs overlap,
665 // the previous blob may have a "more right" right side.
666 // Account for this by always keeping the largest "right"
667 // so far.
668 int previous_right = INT32_MIN;
669
670 // Look for the next split in the partition.
671 for (box_it.mark_cycle_pt(); !box_it.cycled_list(); box_it.forward()) {
672 const TBOX& box = box_it.data()->bounding_box();
673 if (previous_right != INT32_MIN &&
674 box.left() - previous_right > kThreshold) {
675 // We have a split position. Split the partition in two pieces.
676 // Insert the left piece in the grid and keep processing the right.
677 const int mid_x = (box.left() + previous_right) / 2;
678 ColPartition* left_part = right_part;
679 right_part = left_part->SplitAt(mid_x);
680
681 parts_splitted->push_back(left_part);
682 left_part->ComputeSpecialBlobsDensity();
683 found_split = true;
684 break;
685 }
686
687 // The right side of the previous blobs.
688 previous_right = std::max(previous_right, static_cast<int>(box.right()));
689 }
690 }
691
692 // Add the last piece.
693 right_part->ComputeSpecialBlobsDensity();
694 parts_splitted->push_back(right_part);
695}
696
698 GenericVector<TBOX>* splitted_boxes) {
699 ASSERT_HOST(part && splitted_boxes);
700 splitted_boxes->clear();
701 if (part->median_width() == 0) {
702 return;
703 }
704
705 const double kThreshold = part->median_width() * 3.0;
706
707 // Blobs are sorted left side first. If blobs overlap,
708 // the previous blob may have a "more right" right side.
709 // Account for this by always keeping the largest "right"
710 // so far.
711 TBOX union_box;
712 int previous_right = INT32_MIN;
713 BLOBNBOX_C_IT box_it(part->boxes());
714 for (box_it.mark_cycle_pt(); !box_it.cycled_list(); box_it.forward()) {
715 const TBOX& box = box_it.data()->bounding_box();
716 if (previous_right != INT32_MIN &&
717 box.left() - previous_right > kThreshold) {
718 // We have a split position.
719 splitted_boxes->push_back(union_box);
720 previous_right = INT32_MIN;
721 }
722 if (previous_right == INT32_MIN) {
723 union_box = box;
724 } else {
725 union_box += box;
726 }
727 // The right side of the previous blobs.
728 previous_right = std::max(previous_right, static_cast<int>(box.right()));
729 }
730
731 // Add the last piece.
732 if (previous_right != INT32_MIN) {
733 splitted_boxes->push_back(union_box);
734 }
735}
736
738 const GenericVector<int>& indented_texts_left,
739 const float foreground_density_th,
740 ColPartition* part) {
741 ASSERT_HOST(part);
742 const TBOX& box = part->bounding_box();
743
744 // Check if it is aligned with any indented_texts_left.
745 if (!indented_texts_left.empty() &&
746 CountAlignment(indented_texts_left, box.left()) >=
748 return false;
749 }
750
751 // Check the foreground density.
752 if (ComputeForegroundDensity(box) > foreground_density_th) {
753 return false;
754 }
755
756 return true;
757}
758
760 const GenericVector<int>& sorted_vec, const int val) const {
761 if (sorted_vec.empty()) {
762 return 0;
763 }
764 const int kDistTh = static_cast<int>(roundf(0.03 * resolution_));
765 const int pos = sorted_vec.binary_search(val);
766 int count = 0;
767
768 // Search left side.
769 int index = pos;
770 while (index >= 0 && abs(val - sorted_vec[index--]) < kDistTh) {
771 count++;
772 }
773
774 // Search right side.
775 index = pos + 1;
776 while (index < sorted_vec.size() && sorted_vec[index++] - val < kDistTh) {
777 count++;
778 }
779
780 return count;
781}
782
786 const int textparts_linespacing = EstimateTextPartLineSpacing();
787 IdentifyInlinePartsVertical(true, textparts_linespacing);
788 IdentifyInlinePartsVertical(false, textparts_linespacing);
789}
790
793 ColPartition *part = nullptr;
794 gsearch.StartFullSearch();
795 delete cps_super_bbox_;
796 cps_super_bbox_ = new TBOX();
797 while ((part = gsearch.NextFullSearch()) != nullptr) {
798 (*cps_super_bbox_) += part->bounding_box();
799 }
800}
801
805 const int kMarginDiffTh = IntCastRounded(
807 const int kGapTh = static_cast<int>(roundf(
810 search.SetUniqueMode(true);
811 // The center x coordinate of the cp_super_bbox_.
812 const int cps_cx = cps_super_bbox_->left() + cps_super_bbox_->width() / 2;
813 for (int i = 0; i < cp_seeds_.size(); ++i) {
814 ColPartition* part = cp_seeds_[i];
815 const TBOX& part_box(part->bounding_box());
816 const int left_margin = part_box.left() - cps_super_bbox_->left(),
817 right_margin = cps_super_bbox_->right() - part_box.right();
818 bool right_to_left;
819 if (left_margin + kMarginDiffTh < right_margin &&
820 left_margin < kMarginDiffTh) {
821 // part is left aligned, so we search if it has any right neighbor.
822 search.StartSideSearch(
823 part_box.right(), part_box.top(), part_box.bottom());
824 right_to_left = false;
825 } else if (left_margin > cps_cx) {
826 // part locates on the right half on image, so search if it has any left
827 // neighbor.
828 search.StartSideSearch(
829 part_box.left(), part_box.top(), part_box.bottom());
830 right_to_left = true;
831 } else { // part is not an inline equation.
832 new_seeds.push_back(part);
833 continue;
834 }
835 ColPartition* neighbor = nullptr;
836 bool side_neighbor_found = false;
837 while ((neighbor = search.NextSideSearch(right_to_left)) != nullptr) {
838 const TBOX& neighbor_box(neighbor->bounding_box());
839 if (!IsTextOrEquationType(neighbor->type()) ||
840 part_box.x_gap(neighbor_box) > kGapTh ||
841 !part_box.major_y_overlap(neighbor_box) ||
842 part_box.major_x_overlap(neighbor_box)) {
843 continue;
844 }
845 // We have found one. Set the side_neighbor_found flag.
846 side_neighbor_found = true;
847 break;
848 }
849 if (!side_neighbor_found) { // Mark part as PT_INLINE_EQUATION.
851 } else {
852 // Check the geometric feature of neighbor.
853 const TBOX& neighbor_box(neighbor->bounding_box());
854 if (neighbor_box.width() > part_box.width() &&
855 neighbor->type() != PT_EQUATION) { // Mark as PT_INLINE_EQUATION.
857 } else { // part is not an inline equation type.
858 new_seeds.push_back(part);
859 }
860 }
861 }
862
863 // Reset the cp_seeds_ using the new_seeds.
864 cp_seeds_ = new_seeds;
865}
866
869
870 // Get the y gap between text partitions;
871 ColPartition *current = nullptr, *prev = nullptr;
872 gsearch.StartFullSearch();
873 GenericVector<int> ygaps;
874 while ((current = gsearch.NextFullSearch()) != nullptr) {
875 if (!PTIsTextType(current->type())) {
876 continue;
877 }
878 if (prev != nullptr) {
879 const TBOX &current_box = current->bounding_box();
880 const TBOX &prev_box = prev->bounding_box();
881 // prev and current should be x major overlap and non y overlap.
882 if (current_box.major_x_overlap(prev_box) &&
883 !current_box.y_overlap(prev_box)) {
884 int gap = current_box.y_gap(prev_box);
885 if (gap < std::min(current_box.height(), prev_box.height())) {
886 // The gap should be smaller than the height of the bounding boxes.
887 ygaps.push_back(gap);
888 }
889 }
890 }
891 prev = current;
892 }
893
894 if (ygaps.size() < 8) { // We do not have enough data.
895 return -1;
896 }
897
898 // Compute the line spacing from ygaps: use the mean of the first half.
899 ygaps.sort();
900 int spacing = 0, count;
901 for (count = 0; count < ygaps.size() / 2; count++) {
902 spacing += ygaps[count];
903 }
904 return spacing / count;
905}
906
908 const bool top_to_bottom, const int textparts_linespacing) {
909 if (cp_seeds_.empty()) {
910 return;
911 }
912
913 // Sort cp_seeds_.
914 if (top_to_bottom) { // From top to bottom.
915 cp_seeds_.sort(&SortCPByTopReverse);
916 } else { // From bottom to top.
917 cp_seeds_.sort(&SortCPByBottom);
918 }
919
921 for (int i = 0; i < cp_seeds_.size(); ++i) {
922 ColPartition* part = cp_seeds_[i];
923 // If we sort cp_seeds_ from top to bottom, then for each cp_seeds_, we look
924 // for its top neighbors, so that if two/more inline regions are connected
925 // to each other, then we will identify the top one, and then use it to
926 // identify the bottom one.
927 if (IsInline(!top_to_bottom, textparts_linespacing, part)) {
929 } else {
930 new_seeds.push_back(part);
931 }
932 }
933 cp_seeds_ = new_seeds;
934}
935
936bool EquationDetect::IsInline(const bool search_bottom,
937 const int textparts_linespacing,
938 ColPartition* part) {
939 ASSERT_HOST(part != nullptr);
940 // Look for its nearest vertical neighbor that hardly overlaps in y but
941 // largely overlaps in x.
943 ColPartition *neighbor = nullptr;
944 const TBOX& part_box(part->bounding_box());
945 const float kYGapRatioTh = 1.0;
946
947 if (search_bottom) {
948 search.StartVerticalSearch(part_box.left(), part_box.right(),
949 part_box.bottom());
950 } else {
951 search.StartVerticalSearch(part_box.left(), part_box.right(),
952 part_box.top());
953 }
954 search.SetUniqueMode(true);
955 while ((neighbor = search.NextVerticalSearch(search_bottom)) != nullptr) {
956 const TBOX& neighbor_box(neighbor->bounding_box());
957 if (part_box.y_gap(neighbor_box) > kYGapRatioTh *
958 std::min(part_box.height(), neighbor_box.height())) {
959 // Finished searching.
960 break;
961 }
962 if (!PTIsTextType(neighbor->type())) {
963 continue;
964 }
965
966 // Check if neighbor and part is inline similar.
967 const float kHeightRatioTh = 0.5;
968 const int kYGapTh = textparts_linespacing > 0 ?
969 textparts_linespacing + static_cast<int>(roundf(0.02 * resolution_)):
970 static_cast<int>(roundf(0.05 * resolution_)); // Default value.
971 if (part_box.x_overlap(neighbor_box) && // Location feature.
972 part_box.y_gap(neighbor_box) <= kYGapTh && // Line spacing.
973 // Geo feature.
974 static_cast<float>(std::min(part_box.height(), neighbor_box.height())) /
975 std::max(part_box.height(), neighbor_box.height()) > kHeightRatioTh) {
976 return true;
977 }
978 }
979
980 return false;
981}
982
984 if (!part) {
985 return false;
986 }
987 const int kSeedMathBlobsCount = 2;
988 const int kSeedMathDigitBlobsCount = 5;
989
990 const int blobs = part->boxes_count(),
991 math_blobs = part->SpecialBlobsCount(BSTT_MATH),
992 digit_blobs = part->SpecialBlobsCount(BSTT_DIGIT);
993 if (blobs < kSeedBlobsCountTh || math_blobs <= kSeedMathBlobsCount ||
994 math_blobs + digit_blobs <= kSeedMathDigitBlobsCount) {
995 return false;
996 }
997
998 return true;
999}
1000
1002 const float math_density_high,
1003 const float math_density_low,
1004 const ColPartition* part) const {
1005 ASSERT_HOST(part);
1006 float math_digit_density = part->SpecialBlobsDensity(BSTT_MATH)
1008 float italic_density = part->SpecialBlobsDensity(BSTT_ITALIC);
1009 if (math_digit_density > math_density_high) {
1010 return true;
1011 }
1012 if (math_digit_density + italic_density > kMathItalicDensityTh &&
1013 math_digit_density > math_density_low) {
1014 return true;
1015 }
1016
1017 return false;
1018}
1019
1021 ASSERT_HOST(part);
1022
1024 ColPartition *neighbor = nullptr;
1025 const TBOX& part_box(part->bounding_box());
1026 const int kXGapTh = static_cast<int>(roundf(0.5 * resolution_));
1027 const int kRadiusTh = static_cast<int>(roundf(3.0 * resolution_));
1028 const int kYGapTh = static_cast<int>(roundf(0.5 * resolution_));
1029
1030 // Here we use a simple approximation algorithm: from the center of part, We
1031 // perform the radius search, and check if we can find a neighboring partition
1032 // that locates on the top/bottom left of part.
1033 search.StartRadSearch((part_box.left() + part_box.right()) / 2,
1034 (part_box.top() + part_box.bottom()) / 2, kRadiusTh);
1035 search.SetUniqueMode(true);
1036 bool left_indented = false, right_indented = false;
1037 while ((neighbor = search.NextRadSearch()) != nullptr &&
1038 (!left_indented || !right_indented)) {
1039 if (neighbor == part) {
1040 continue;
1041 }
1042 const TBOX& neighbor_box(neighbor->bounding_box());
1043
1044 if (part_box.major_y_overlap(neighbor_box) &&
1045 part_box.x_gap(neighbor_box) < kXGapTh) {
1046 // When this happens, it is likely part is a fragment of an
1047 // over-segmented colpartition. So we return false.
1048 return NO_INDENT;
1049 }
1050
1051 if (!IsTextOrEquationType(neighbor->type())) {
1052 continue;
1053 }
1054
1055 // The neighbor should be above/below part, and overlap in x direction.
1056 if (!part_box.x_overlap(neighbor_box) || part_box.y_overlap(neighbor_box)) {
1057 continue;
1058 }
1059
1060 if (part_box.y_gap(neighbor_box) < kYGapTh) {
1061 const int left_gap = part_box.left() - neighbor_box.left();
1062 const int right_gap = neighbor_box.right() - part_box.right();
1063 if (left_gap > kXGapTh) {
1064 left_indented = true;
1065 }
1066 if (right_gap > kXGapTh) {
1067 right_indented = true;
1068 }
1069 }
1070 }
1071
1072 if (left_indented && right_indented) {
1073 return BOTH_INDENT;
1074 }
1075 if (left_indented) {
1076 return LEFT_INDENT;
1077 }
1078 if (right_indented) {
1079 return RIGHT_INDENT;
1080 }
1081 return NO_INDENT;
1082}
1083
1085 if (seed == nullptr || // This seed has been absorbed by other seeds.
1086 seed->IsVerticalType()) { // We skip vertical type right now.
1087 return false;
1088 }
1089
1090 // Expand in four directions.
1091 GenericVector<ColPartition*> parts_to_merge;
1092 ExpandSeedHorizontal(true, seed, &parts_to_merge);
1093 ExpandSeedHorizontal(false, seed, &parts_to_merge);
1094 ExpandSeedVertical(true, seed, &parts_to_merge);
1095 ExpandSeedVertical(false, seed, &parts_to_merge);
1096 SearchByOverlap(seed, &parts_to_merge);
1097
1098 if (parts_to_merge.empty()) { // We don't find any partition to merge.
1099 return false;
1100 }
1101
1102 // Merge all partitions in parts_to_merge with seed. We first remove seed
1103 // from part_grid_ as its bounding box is going to expand. Then we add it
1104 // back after it absorbs all parts_to_merge partitions.
1105 part_grid_->RemoveBBox(seed);
1106 for (int i = 0; i < parts_to_merge.size(); ++i) {
1107 ColPartition* part = parts_to_merge[i];
1108 if (part->type() == PT_EQUATION) {
1109 // If part is in cp_seeds_, then we mark it as nullptr so that we won't
1110 // process it again.
1111 for (int j = 0; j < cp_seeds_.size(); ++j) {
1112 if (part == cp_seeds_[j]) {
1113 cp_seeds_[j] = nullptr;
1114 break;
1115 }
1116 }
1117 }
1118
1119 // part has already been removed from part_grid_ in function
1120 // ExpandSeedHorizontal/ExpandSeedVertical.
1121 seed->Absorb(part, nullptr);
1122 }
1123
1124 return true;
1125}
1126
1128 const bool search_left,
1129 ColPartition* seed,
1130 GenericVector<ColPartition*>* parts_to_merge) {
1131 ASSERT_HOST(seed != nullptr && parts_to_merge != nullptr);
1132 const float kYOverlapTh = 0.6;
1133 const int kXGapTh = static_cast<int>(roundf(0.2 * resolution_));
1134
1136 const TBOX& seed_box(seed->bounding_box());
1137 const int x = search_left ? seed_box.left() : seed_box.right();
1138 search.StartSideSearch(x, seed_box.bottom(), seed_box.top());
1139 search.SetUniqueMode(true);
1140
1141 // Search iteratively.
1142 ColPartition *part = nullptr;
1143 while ((part = search.NextSideSearch(search_left)) != nullptr) {
1144 if (part == seed) {
1145 continue;
1146 }
1147 const TBOX& part_box(part->bounding_box());
1148 if (part_box.x_gap(seed_box) > kXGapTh) { // Out of scope.
1149 break;
1150 }
1151
1152 // Check part location.
1153 if ((part_box.left() >= seed_box.left() && search_left) ||
1154 (part_box.right() <= seed_box.right() && !search_left)) {
1155 continue;
1156 }
1157
1158 if (part->type() != PT_EQUATION) { // Non-equation type.
1159 // Skip PT_LINLINE_EQUATION and non text type.
1160 if (part->type() == PT_INLINE_EQUATION ||
1161 (!IsTextOrEquationType(part->type()) &&
1162 part->blob_type() != BRT_HLINE)) {
1163 continue;
1164 }
1165 // For other types, it should be the near small neighbor of seed.
1166 if (!IsNearSmallNeighbor(seed_box, part_box) ||
1167 !CheckSeedNeighborDensity(part)) {
1168 continue;
1169 }
1170 } else { // Equation type, check the y overlap.
1171 if (part_box.y_overlap_fraction(seed_box) < kYOverlapTh &&
1172 seed_box.y_overlap_fraction(part_box) < kYOverlapTh) {
1173 continue;
1174 }
1175 }
1176
1177 // Passed the check, delete it from search and add into parts_to_merge.
1178 search.RemoveBBox();
1179 parts_to_merge->push_back(part);
1180 }
1181}
1182
1184 const bool search_bottom,
1185 ColPartition* seed,
1186 GenericVector<ColPartition*>* parts_to_merge) {
1187 ASSERT_HOST(seed != nullptr && parts_to_merge != nullptr &&
1188 cps_super_bbox_ != nullptr);
1189 const float kXOverlapTh = 0.4;
1190 const int kYGapTh = static_cast<int>(roundf(0.2 * resolution_));
1191
1193 const TBOX& seed_box(seed->bounding_box());
1194 const int y = search_bottom ? seed_box.bottom() : seed_box.top();
1195 search.StartVerticalSearch(
1197 search.SetUniqueMode(true);
1198
1199 // Search iteratively.
1200 ColPartition *part = nullptr;
1202 int skipped_min_top = std::numeric_limits<int>::max(), skipped_max_bottom = -1;
1203 while ((part = search.NextVerticalSearch(search_bottom)) != nullptr) {
1204 if (part == seed) {
1205 continue;
1206 }
1207 const TBOX& part_box(part->bounding_box());
1208
1209 if (part_box.y_gap(seed_box) > kYGapTh) { // Out of scope.
1210 break;
1211 }
1212
1213 // Check part location.
1214 if ((part_box.bottom() >= seed_box.bottom() && search_bottom) ||
1215 (part_box.top() <= seed_box.top() && !search_bottom)) {
1216 continue;
1217 }
1218
1219 bool skip_part = false;
1220 if (part->type() != PT_EQUATION) { // Non-equation type.
1221 // Skip PT_LINLINE_EQUATION and non text type.
1222 if (part->type() == PT_INLINE_EQUATION ||
1223 (!IsTextOrEquationType(part->type()) &&
1224 part->blob_type() != BRT_HLINE)) {
1225 skip_part = true;
1226 } else if (!IsNearSmallNeighbor(seed_box, part_box) ||
1227 !CheckSeedNeighborDensity(part)) {
1228 // For other types, it should be the near small neighbor of seed.
1229 skip_part = true;
1230 }
1231 } else { // Equation type, check the x overlap.
1232 if (part_box.x_overlap_fraction(seed_box) < kXOverlapTh &&
1233 seed_box.x_overlap_fraction(part_box) < kXOverlapTh) {
1234 skip_part = true;
1235 }
1236 }
1237 if (skip_part) {
1238 if (part->type() != PT_EQUATION) {
1239 if (skipped_min_top > part_box.top()) {
1240 skipped_min_top = part_box.top();
1241 }
1242 if (skipped_max_bottom < part_box.bottom()) {
1243 skipped_max_bottom = part_box.bottom();
1244 }
1245 }
1246 } else {
1247 parts.push_back(part);
1248 }
1249 }
1250
1251 // For every part in parts, we need verify it is not above skipped_min_top
1252 // when search top, or not below skipped_max_bottom when search bottom. I.e.,
1253 // we will skip a part if it looks like:
1254 // search bottom | search top
1255 // seed: ****************** | part: **********
1256 // skipped: xxx | skipped: xxx
1257 // part: ********** | seed: ***********
1258 for (int i = 0; i < parts.size(); i++) {
1259 const TBOX& part_box(parts[i]->bounding_box());
1260 if ((search_bottom && part_box.top() <= skipped_max_bottom) ||
1261 (!search_bottom && part_box.bottom() >= skipped_min_top)) {
1262 continue;
1263 }
1264 // Add parts[i] into parts_to_merge, and delete it from part_grid_.
1265 parts_to_merge->push_back(parts[i]);
1266 part_grid_->RemoveBBox(parts[i]);
1267 }
1268}
1269
1271 const TBOX& part_box) const {
1272 const int kXGapTh = static_cast<int>(roundf(0.25 * resolution_));
1273 const int kYGapTh = static_cast<int>(roundf(0.05 * resolution_));
1274
1275 // Check geometric feature.
1276 if (part_box.height() > seed_box.height() ||
1277 part_box.width() > seed_box.width()) {
1278 return false;
1279 }
1280
1281 // Check overlap and distance.
1282 if ((!part_box.major_x_overlap(seed_box) ||
1283 part_box.y_gap(seed_box) > kYGapTh) &&
1284 (!part_box.major_y_overlap(seed_box) ||
1285 part_box.x_gap(seed_box) > kXGapTh)) {
1286 return false;
1287 }
1288
1289 return true;
1290}
1291
1293 ASSERT_HOST(part);
1294 if (part->boxes_count() < kSeedBlobsCountTh) {
1295 // Too few blobs, skip the check.
1296 return true;
1297 }
1298
1299 // We check the math blobs density and the unclear blobs density.
1300 if (part->SpecialBlobsDensity(BSTT_MATH) +
1303 return true;
1304 }
1305
1306 return false;
1307}
1308
1310 // Iterate over part_grid_, and find all parts that are text type but not
1311 // equation type.
1312 ColPartition *part = nullptr;
1315 gsearch.StartFullSearch();
1316 while ((part = gsearch.NextFullSearch()) != nullptr) {
1317 if (part->type() == PT_FLOWING_TEXT || part->type() == PT_HEADING_TEXT) {
1318 text_parts.push_back(part);
1319 }
1320 }
1321 if (text_parts.empty()) {
1322 return;
1323 }
1324
1325 // Compute the medium height of the text_parts.
1326 text_parts.sort(&SortCPByHeight);
1327 const TBOX& text_box = text_parts[text_parts.size() / 2]->bounding_box();
1328 int med_height = text_box.height();
1329 if (text_parts.size() % 2 == 0 && text_parts.size() > 1) {
1330 const TBOX& text_box =
1331 text_parts[text_parts.size() / 2 - 1]->bounding_box();
1332 med_height = static_cast<int>(roundf(
1333 0.5 * (text_box.height() + med_height)));
1334 }
1335
1336 // Iterate every text_parts and check if it is a math block satellite.
1337 for (int i = 0; i < text_parts.size(); ++i) {
1338 const TBOX& text_box(text_parts[i]->bounding_box());
1339 if (text_box.height() > med_height) {
1340 continue;
1341 }
1342 GenericVector<ColPartition*> math_blocks;
1343 if (!IsMathBlockSatellite(text_parts[i], &math_blocks)) {
1344 continue;
1345 }
1346
1347 // Found. merge text_parts[i] with math_blocks.
1348 part_grid_->RemoveBBox(text_parts[i]);
1349 text_parts[i]->set_type(PT_EQUATION);
1350 for (int j = 0; j < math_blocks.size(); ++j) {
1351 part_grid_->RemoveBBox(math_blocks[j]);
1352 text_parts[i]->Absorb(math_blocks[j], nullptr);
1353 }
1354 InsertPartAfterAbsorb(text_parts[i]);
1355 }
1356}
1357
1359 ColPartition* part, GenericVector<ColPartition*>* math_blocks) {
1360 ASSERT_HOST(part != nullptr && math_blocks != nullptr);
1361 math_blocks->clear();
1362 const TBOX& part_box(part->bounding_box());
1363 // Find the top/bottom nearest neighbor of part.
1364 ColPartition *neighbors[2];
1365 int y_gaps[2] = {std::numeric_limits<int>::max(), std::numeric_limits<int>::max()};
1366 // The horizontal boundary of the neighbors.
1367 int neighbors_left = std::numeric_limits<int>::max(), neighbors_right = 0;
1368 for (int i = 0; i < 2; ++i) {
1369 neighbors[i] = SearchNNVertical(i != 0, part);
1370 if (neighbors[i]) {
1371 const TBOX& neighbor_box = neighbors[i]->bounding_box();
1372 y_gaps[i] = neighbor_box.y_gap(part_box);
1373 if (neighbor_box.left() < neighbors_left) {
1374 neighbors_left = neighbor_box.left();
1375 }
1376 if (neighbor_box.right() > neighbors_right) {
1377 neighbors_right = neighbor_box.right();
1378 }
1379 }
1380 }
1381 if (neighbors[0] == neighbors[1]) {
1382 // This happens when part is inside neighbor.
1383 neighbors[1] = nullptr;
1384 y_gaps[1] = std::numeric_limits<int>::max();
1385 }
1386
1387 // Check if part is within [neighbors_left, neighbors_right].
1388 if (part_box.left() < neighbors_left || part_box.right() > neighbors_right) {
1389 return false;
1390 }
1391
1392 // Get the index of the near one in neighbors.
1393 int index = y_gaps[0] < y_gaps[1] ? 0 : 1;
1394
1395 // Check the near one.
1396 if (IsNearMathNeighbor(y_gaps[index], neighbors[index])) {
1397 math_blocks->push_back(neighbors[index]);
1398 } else {
1399 // If the near one failed the check, then we skip checking the far one.
1400 return false;
1401 }
1402
1403 // Check the far one.
1404 index = 1 - index;
1405 if (IsNearMathNeighbor(y_gaps[index], neighbors[index])) {
1406 math_blocks->push_back(neighbors[index]);
1407 }
1408
1409 return true;
1410}
1411
1413 const bool search_bottom, const ColPartition* part) {
1414 ASSERT_HOST(part);
1415 ColPartition *nearest_neighbor = nullptr, *neighbor = nullptr;
1416 const int kYGapTh = static_cast<int>(roundf(resolution_ * 0.5));
1417
1419 search.SetUniqueMode(true);
1420 const TBOX& part_box(part->bounding_box());
1421 int y = search_bottom ? part_box.bottom() : part_box.top();
1422 search.StartVerticalSearch(part_box.left(), part_box.right(), y);
1423 int min_y_gap = std::numeric_limits<int>::max();
1424 while ((neighbor = search.NextVerticalSearch(search_bottom)) != nullptr) {
1425 if (neighbor == part || !IsTextOrEquationType(neighbor->type())) {
1426 continue;
1427 }
1428 const TBOX& neighbor_box(neighbor->bounding_box());
1429 int y_gap = neighbor_box.y_gap(part_box);
1430 if (y_gap > kYGapTh) { // Out of scope.
1431 break;
1432 }
1433 if (!neighbor_box.major_x_overlap(part_box) ||
1434 (search_bottom && neighbor_box.bottom() > part_box.bottom()) ||
1435 (!search_bottom && neighbor_box.top() < part_box.top())) {
1436 continue;
1437 }
1438 if (y_gap < min_y_gap) {
1439 min_y_gap = y_gap;
1440 nearest_neighbor = neighbor;
1441 }
1442 }
1443
1444 return nearest_neighbor;
1445}
1446
1448 const int y_gap, const ColPartition *neighbor) const {
1449 if (!neighbor) {
1450 return false;
1451 }
1452 const int kYGapTh = static_cast<int>(roundf(resolution_ * 0.1));
1453 return neighbor->type() == PT_EQUATION && y_gap <= kYGapTh;
1454}
1455
1457 STRING* image_name) const {
1458 ASSERT_HOST(image_name && name);
1459 char page[50];
1460 snprintf(page, sizeof(page), "%04d", page_count_);
1461 *image_name = STRING(lang_tesseract_->imagebasename) + page + name + ".tif";
1462}
1463
1464void EquationDetect::PaintSpecialTexts(const STRING& outfile) const {
1465 Pix *pix = nullptr, *pixBi = lang_tesseract_->pix_binary();
1466 pix = pixConvertTo32(pixBi);
1468 ColPartition* part = nullptr;
1469 gsearch.StartFullSearch();
1470 while ((part = gsearch.NextFullSearch()) != nullptr) {
1471 BLOBNBOX_C_IT blob_it(part->boxes());
1472 for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
1473 RenderSpecialText(pix, blob_it.data());
1474 }
1475 }
1476
1477 pixWrite(outfile.string(), pix, IFF_TIFF_LZW);
1478 pixDestroy(&pix);
1479}
1480
1481void EquationDetect::PaintColParts(const STRING& outfile) const {
1482 Pix *pix = pixConvertTo32(lang_tesseract_->BestPix());
1484 gsearch.StartFullSearch();
1485 ColPartition* part = nullptr;
1486 while ((part = gsearch.NextFullSearch()) != nullptr) {
1487 const TBOX& tbox = part->bounding_box();
1488 Box *box = boxCreate(tbox.left(), pixGetHeight(pix) - tbox.top(),
1489 tbox.width(), tbox.height());
1490 if (part->type() == PT_EQUATION) {
1491 pixRenderBoxArb(pix, box, 5, 255, 0, 0);
1492 } else if (part->type() == PT_INLINE_EQUATION) {
1493 pixRenderBoxArb(pix, box, 5, 0, 255, 0);
1494 } else {
1495 pixRenderBoxArb(pix, box, 5, 0, 0, 255);
1496 }
1497 boxDestroy(&box);
1498 }
1499
1500 pixWrite(outfile.string(), pix, IFF_TIFF_LZW);
1501 pixDestroy(&pix);
1502}
1503
1505 ASSERT_HOST(part);
1506 TBOX box(part->bounding_box());
1507 int h = pixGetHeight(lang_tesseract_->BestPix());
1508 tprintf("Printing special blobs density values for ColParition (t=%d,b=%d) ",
1509 h - box.top(), h - box.bottom());
1510 box.print();
1511 tprintf("blobs count = %d, density = ", part->boxes_count());
1512 for (int i = 0; i < BSTT_COUNT; ++i) {
1513 auto type = static_cast<BlobSpecialTextType>(i);
1514 tprintf("%d:%f ", i, part->SpecialBlobsDensity(type));
1515 }
1516 tprintf("\n");
1517}
1518
1519} // namespace tesseract
@ PT_HEADING_TEXT
Definition: capi.h:131
@ PT_INLINE_EQUATION
Definition: capi.h:134
@ PT_FLOWING_TEXT
Definition: capi.h:130
@ PT_EQUATION
Definition: capi.h:133
BlobSpecialTextType
Definition: blobbox.h:96
@ BSTT_NONE
Definition: blobbox.h:97
@ BSTT_MATH
Definition: blobbox.h:100
@ BSTT_UNCLEAR
Definition: blobbox.h:101
@ BSTT_SKIP
Definition: blobbox.h:102
@ BSTT_ITALIC
Definition: blobbox.h:98
@ BSTT_DIGIT
Definition: blobbox.h:99
@ BSTT_COUNT
Definition: blobbox.h:103
BlobTextFlowType
Definition: blobbox.h:114
BlobRegionType
Definition: blobbox.h:72
@ BRT_HLINE
Definition: blobbox.h:74
const int kBlnBaselineOffset
Definition: normalis.h:25
const int kBlnXHeight
Definition: normalis.h:24
PolyBlockType
Definition: publictypes.h:53
bool PTIsTextType(PolyBlockType type)
Definition: publictypes.h:82
#define ASSERT_HOST(x)
Definition: errcode.h:88
int IntCastRounded(double x)
Definition: helpers.h:175
#define BOOL_VAR(name, val, comment)
Definition: params.h:306
DLLSYM void tprintf(const char *format,...)
Definition: tprintf.cpp:35
int UNICHAR_ID
Definition: unichar.h:34
LIST search(LIST list, void *key, int_compare is_equal)
Definition: oldlist.cpp:258
int count(LIST var_list)
Definition: oldlist.cpp:95
@ OEM_TESSERACT_ONLY
Definition: publictypes.h:269
const float kUnclearDensityTh
const int kSeedBlobsCountTh
const int kLeftIndentAlignmentCountTh
bool IsTextOrEquationType(PolyBlockType type)
const float kMathDigitDensityTh2
bool IsRightIndented(const EquationDetect::IndentType type)
const float kMathItalicDensityTh
const float kMathDigitDensityTh1
bool IsLeftIndented(const EquationDetect::IndentType type)
int push_back(T object)
bool empty() const
Definition: genericvector.h:91
int size() const
Definition: genericvector.h:72
bool bool_binary_search(const T &target) const
void delete_data_pointers()
int binary_search(const T &target) const
bool CheckSeedDensity(const float math_density_high, const float math_density_low, const ColPartition *part) const
EquationDetect(const char *equ_datapath, const char *equ_language)
void GetOutputTiffName(const char *name, STRING *image_name) const
bool CheckSeedBlobsCount(ColPartition *part)
void SetResolution(const int resolution)
void SplitCPHorLite(ColPartition *part, GenericVector< TBOX > *splitted_boxes)
int LabelSpecialText(TO_BLOCK *to_block) override
bool CheckForSeed2(const GenericVector< int > &indented_texts_left, const float foreground_density_th, ColPartition *part)
bool CheckSeedNeighborDensity(const ColPartition *part) const
bool IsNearMathNeighbor(const int y_gap, const ColPartition *neighbor) const
IndentType IsIndented(ColPartition *part)
void ExpandSeedVertical(const bool search_bottom, ColPartition *seed, GenericVector< ColPartition * > *parts_to_merge)
ColPartitionGrid * part_grid_
BlobSpecialTextType EstimateTypeForUnichar(const UNICHARSET &unicharset, const UNICHAR_ID id) const
float ComputeForegroundDensity(const TBOX &tbox)
void PaintSpecialTexts(const STRING &outfile) const
ColPartitionSet ** best_columns_
void InsertPartAfterAbsorb(ColPartition *part)
ColPartition * SearchNNVertical(const bool search_bottom, const ColPartition *part)
bool IsNearSmallNeighbor(const TBOX &seed_box, const TBOX &part_box) const
void ExpandSeedHorizontal(const bool search_left, ColPartition *seed, GenericVector< ColPartition * > *parts_to_merge)
void IdentifyInlinePartsVertical(const bool top_to_bottom, const int textPartsLineSpacing)
void SplitCPHor(ColPartition *part, GenericVector< ColPartition * > *parts_splitted)
bool ExpandSeed(ColPartition *seed)
int CountAlignment(const GenericVector< int > &sorted_vec, const int val) const
bool IsInline(const bool search_bottom, const int textPartsLineSpacing, ColPartition *part)
bool CheckSeedFgDensity(const float density_th, ColPartition *part)
int FindEquationParts(ColPartitionGrid *part_grid, ColPartitionSet **best_columns) override
void IdentifyBlobsToSkip(ColPartition *part)
bool IsMathBlockSatellite(ColPartition *part, GenericVector< ColPartition * > *math_blocks)
void SearchByOverlap(ColPartition *seed, GenericVector< ColPartition * > *parts_overlap)
GenericVector< ColPartition * > cp_seeds_
void PrintSpecialBlobsDensity(const ColPartition *part) const
void PaintColParts(const STRING &outfile) const
void SetLangTesseract(Tesseract *lang_tesseract)
int init_tesseract(const char *arg0, const char *textbase, const char *language, OcrEngineMode oem, char **configs, int configs_size, const GenericVector< STRING > *vars_vec, const GenericVector< STRING > *vars_values, bool set_only_init_params, TessdataManager *mgr)
Definition: tessedit.cpp:286
Pix * pix_binary() const
Pix * BestPix() const
int source_resolution() const
void set_special_text_type(BlobSpecialTextType new_type)
Definition: blobbox.h:292
BlobSpecialTextType special_text_type() const
Definition: blobbox.h:289
const TBOX & bounding_box() const
Definition: blobbox.h:230
C_BLOB * cblob() const
Definition: blobbox.h:268
bool joined_to_prev() const
Definition: blobbox.h:256
BLOBNBOX_LIST blobs
Definition: blobbox.h:772
BLOBNBOX_LIST large_blobs
Definition: blobbox.h:776
Definition: blobs.h:284
TBOX bounding_box() const
Definition: blobs.cpp:468
static TBLOB * PolygonalCopy(bool allow_detailed_fx, C_BLOB *src)
Definition: blobs.cpp:327
float certainty() const
Definition: ratngs.h:83
int16_t fontinfo_id() const
Definition: ratngs.h:86
UNICHAR_ID unichar_id() const
Definition: ratngs.h:77
Definition: rect.h:34
bool x_overlap(const TBOX &box) const
Definition: rect.h:401
double x_overlap_fraction(const TBOX &box) const
Definition: rect.h:457
double y_overlap_fraction(const TBOX &box) const
Definition: rect.h:479
int16_t top() const
Definition: rect.h:58
void print() const
Definition: rect.h:278
int16_t width() const
Definition: rect.h:115
int16_t height() const
Definition: rect.h:108
bool y_overlap(const TBOX &box) const
Definition: rect.h:428
int16_t left() const
Definition: rect.h:72
int y_gap(const TBOX &box) const
Definition: rect.h:233
int16_t bottom() const
Definition: rect.h:65
bool major_x_overlap(const TBOX &box) const
Definition: rect.h:412
bool major_y_overlap(const TBOX &box) const
Definition: rect.h:439
int x_gap(const TBOX &box) const
Definition: rect.h:225
int16_t right() const
Definition: rect.h:79
UNICHARSET unicharset
Definition: ccutil.h:73
STRING imagebasename
Definition: ccutil.h:70
Definition: strngs.h:45
int32_t length() const
Definition: strngs.cpp:189
bool contains(char c) const
Definition: strngs.cpp:185
const char * string() const
Definition: strngs.cpp:194
bool get_ispunctuation(UNICHAR_ID unichar_id) const
Definition: unicharset.h:519
bool get_isalpha(UNICHAR_ID unichar_id) const
Definition: unicharset.h:491
bool get_isdigit(UNICHAR_ID unichar_id) const
Definition: unicharset.h:512
const char * id_to_unichar(UNICHAR_ID id) const
Definition: unicharset.cpp:291
UNICHAR_ID unichar_to_id(const char *const unichar_repr) const
Definition: unicharset.cpp:210
int classify_class_pruner_multiplier
Definition: classify.h:501
void AdaptiveClassifier(TBLOB *Blob, BLOB_CHOICE_LIST *Choices)
Definition: adaptmatch.cpp:191
int classify_integer_matcher_multiplier
Definition: classify.h:505
UnicityTable< FontInfo > & get_fontinfo_table()
Definition: classify.h:386
void StartFullSearch()
Definition: bbgrid.h:665
void RepositionIterator()
Definition: bbgrid.h:892
BBC * NextFullSearch()
Definition: bbgrid.h:675
void GridCoords(int x, int y, int *grid_x, int *grid_y) const
Definition: bbgrid.cpp:52
void InsertBBox(bool h_spread, bool v_spread, BBC *bbox)
Definition: bbgrid.h:486
void RemoveBBox(BBC *bbox)
Definition: bbgrid.h:533
BlobTextFlowType flow() const
Definition: colpartition.h:155
BLOBNBOX_CLIST * boxes()
Definition: colpartition.h:188
float SpecialBlobsDensity(const BlobSpecialTextType type) const
int SpecialBlobsCount(const BlobSpecialTextType type)
PolyBlockType type() const
Definition: colpartition.h:182
ColPartition * CopyButDontOwnBlobs()
ColPartition * SplitAt(int split_x)
BlobRegionType blob_type() const
Definition: colpartition.h:149
void set_blob_type(BlobRegionType t)
Definition: colpartition.h:152
const TBOX & bounding_box() const
Definition: colpartition.h:110
bool IsVerticalType() const
Definition: colpartition.h:442
void set_type(PolyBlockType t)
Definition: colpartition.h:185
void SetPartitionType(int resolution, ColPartitionSet *columns)
void Absorb(ColPartition *other, WidthCallback *cb)
void set_flow(BlobTextFlowType f)
Definition: colpartition.h:158
static void RenderSpecialText(Pix *pix, BLOBNBOX *blob)