Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/tesseract/src/ccmain/equationdetect.cpp @ 2:b50eed0cc0ef upstream

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