30#ifndef DISABLED_LEGACY_ENGINE
58#ifndef GRAPHICS_DISABLED
59static BOOL_VAR(textord_tabfind_show_initial_partitions,
false,
"Show partition bounds");
60static BOOL_VAR(textord_tabfind_show_reject_blobs,
false,
"Show blobs rejected as noise");
61static INT_VAR(textord_tabfind_show_partitions, 0,
62 "Show partition bounds, waiting if >1 (ScrollView)");
63static BOOL_VAR(textord_tabfind_show_columns,
false,
"Show column bounds (ScrollView)");
64static BOOL_VAR(textord_tabfind_show_blocks,
false,
"Show final block bounds (ScrollView)");
66static BOOL_VAR(textord_tabfind_find_tables,
true,
"run table detection");
68#ifndef GRAPHICS_DISABLED
69ScrollView *ColumnFinder::blocks_win_ =
nullptr;
79 bool cjk_script,
double aligned_gap_fraction, TabVector_LIST *vlines,
80 TabVector_LIST *hlines,
int vertical_x,
int vertical_y)
81 :
TabFind(gridsize, bleft, tright, vlines, vertical_x, vertical_y, resolution)
82 , cjk_script_(cjk_script)
84 , mean_column_gap_(tright.x() - bleft.x())
85 , tabfind_aligned_gap_fraction_(aligned_gap_fraction)
88 , rotation_(1.0f, 0.0f)
89 , rerotate_(1.0f, 0.0f)
90 , text_rotation_(0.0f, 0.0f)
91 , best_columns_(nullptr)
92 , stroke_width_(nullptr)
93 , part_grid_(gridsize, bleft, tright)
94 , nontext_map_(nullptr)
95 , projection_(resolution)
97 , equation_detect_(nullptr) {
98 TabVector_IT h_it(&horizontal_lines_);
99 h_it.add_list_after(hlines);
103 for (
auto set : column_sets_) {
106 delete[] best_columns_;
107 delete stroke_width_;
108#ifndef GRAPHICS_DISABLED
109 delete input_blobs_win_;
112 while (denorm_ !=
nullptr) {
113 DENORM *dead_denorm = denorm_;
120 ColPartition_IT part_it(&noise_parts_);
121 for (part_it.mark_cycle_pt(); !part_it.cycled_list(); part_it.forward()) {
128 part_it.set_to_list(&good_parts_);
129 for (part_it.mark_cycle_pt(); !part_it.cycled_list(); part_it.forward()) {
137 BLOBNBOX_IT bb_it(&image_bblobs_);
138 for (bb_it.mark_cycle_pt(); !bb_it.cycled_list(); bb_it.forward()) {
140 delete bblob->
cblob();
154 delete stroke_width_;
158#ifndef GRAPHICS_DISABLED
159 if (textord_tabfind_show_blocks) {
160 input_blobs_win_ =
MakeWindow(0, 0,
"Filtered Input Blobs");
174 stroke_width_->
Clear();
187 BLOBNBOX_CLIST *osd_blobs) {
203 int recognition_rotation) {
204 const FCOORD anticlockwise90(0.0f, 1.0f);
205 const FCOORD clockwise90(0.0f, -1.0f);
206 const FCOORD rotation180(-1.0f, 0.0f);
207 const FCOORD norotation(1.0f, 0.0f);
209 text_rotation_ = norotation;
212 rotation_ = norotation;
213 if (recognition_rotation == 1) {
214 rotation_ = anticlockwise90;
215 }
else if (recognition_rotation == 2) {
216 rotation_ = rotation180;
217 }
else if (recognition_rotation == 3) {
218 rotation_ = clockwise90;
224 if (recognition_rotation & 1) {
225 vertical_text_lines = !vertical_text_lines;
231 if (vertical_text_lines) {
232 rotation_.
rotate(anticlockwise90);
233 text_rotation_.
rotate(clockwise90);
236 rerotate_ =
FCOORD(rotation_.
x(), -rotation_.
y());
237 if (rotation_.
x() != 1.0f || rotation_.
y() != 0.0f) {
252 tprintf(
"Vertical=%d, orientation=%d, final rotation=(%f, %f)+(%f,%f)\n", vertical_text_lines,
253 recognition_rotation, rotation_.
x(), rotation_.
y(), text_rotation_.
x(),
259 denorm_->
SetupNormalization(
nullptr, &rotation_,
nullptr, 0.0f, 0.0f, 1.0f, 1.0f, 0.0f, 0.0f);
289 BLOBNBOX_LIST *diacritic_blobs, TO_BLOCK_LIST *to_blocks) {
290 photo_mask_pix |= nontext_map_;
296 denorm_, cjk_script_, &projection_, diacritic_blobs,
297 &part_grid_, &big_parts_);
300 pixa_debug, &part_grid_, &big_parts_);
303 pixa_debug, &part_grid_, &big_parts_);
309 ColPartition_IT p_it(&big_parts_);
310 for (p_it.mark_cycle_pt(); !p_it.cycled_list(); p_it.forward()) {
311 p_it.data()->DisownBoxesNoAssert();
314 delete stroke_width_;
315 stroke_width_ =
nullptr;
341 ReflectForRtl(input_block, &image_bblobs_);
353 FindTabVectors(&horizontal_lines_, &image_bblobs_, input_block, min_gutter_width_,
354 tabfind_aligned_gap_fraction_, &part_grid_, &deskew_, &reskew_);
356 auto *new_denorm =
new DENORM;
357 new_denorm->
SetupNormalization(
nullptr, &deskew_, denorm_, 0.0f, 0.0f, 1.0f, 1.0f, 0.0f,
359 denorm_ = new_denorm;
365 if (!MakeColumns(
false)) {
374#ifndef GRAPHICS_DISABLED
375 if (textord_tabfind_show_reject_blobs) {
385 GridSplitPartitions();
389 GridMergePartitions();
392 InsertRemainingNoise(input_block);
394 GridInsertHLinePartitions();
395 GridInsertVLinePartitions();
400#ifndef GRAPHICS_DISABLED
401 if (textord_tabfind_show_initial_partitions) {
408#ifndef DISABLED_LEGACY_ENGINE
409 if (equation_detect_) {
413 if (textord_tabfind_find_tables) {
424 GridRemoveUnderlinePartitions();
434#ifndef GRAPHICS_DISABLED
435 if (textord_tabfind_show_partitions) {
437 if (window !=
nullptr) {
442 if (window !=
nullptr && textord_tabfind_show_partitions > 1) {
453 ReleaseBlobsAndCleanupUnused(input_block);
461 TransformToBlocks(blocks, to_blocks);
464 tprintf(
"Found %d blocks, %d to_blocks\n", blocks->length(), to_blocks->length());
467#ifndef GRAPHICS_DISABLED
468 if (textord_tabfind_show_blocks) {
469 DisplayBlocks(blocks);
472 RotateAndReskewBlocks(input_is_rtl, to_blocks);
474#ifndef GRAPHICS_DISABLED
475 if (blocks_win_ !=
nullptr) {
476 bool waiting =
false;
480 if (event->type ==
SVET_INPUT && event->parameter !=
nullptr) {
481 if (*event->parameter ==
'd') {
487 blocks_win_ =
nullptr;
502 deskew->
set_y(-deskew->
y());
505#ifndef DISABLED_LEGACY_ENGINE
507 equation_detect_ = detect;
513#ifndef GRAPHICS_DISABLED
516void ColumnFinder::DisplayBlocks(BLOCK_LIST *blocks) {
517 if (blocks_win_ ==
nullptr) {
520 blocks_win_->
Clear();
523 BLOCK_IT block_it(blocks);
525 for (block_it.mark_cycle_pt(); !block_it.cycled_list(); block_it.forward()) {
526 BLOCK *block = block_it.data();
527 block->pdblk.plot(blocks_win_, serial++,
536 ScrollView *col_win =
MakeWindow(50, 300,
"Columns");
540 ColPartitionSet *columns = best_columns_[i];
541 if (columns !=
nullptr) {
551bool ColumnFinder::MakeColumns(
bool single_column) {
556 if (!single_column) {
562 bool good_only =
true;
565 ColPartitionSet *line_set = part_sets.at(i);
566 if (line_set !=
nullptr && line_set->LegalColumnCandidate()) {
567 ColPartitionSet *column_candidate = line_set->Copy(good_only);
568 if (column_candidate !=
nullptr) {
569 column_candidate->AddToColumnSetsIfUnique(&column_sets_,
WidthCB());
573 good_only = !good_only;
574 }
while (column_sets_.empty() && !good_only);
576 PrintColumnCandidates(
"Column candidates");
579 ImproveColumnCandidates(&column_sets_, &column_sets_);
581 PrintColumnCandidates(
"Improved columns");
584 ImproveColumnCandidates(&part_sets, &column_sets_);
587 if (single_column_set !=
nullptr) {
593 PrintColumnCandidates(
"Final Columns");
595 bool has_columns = !column_sets_.empty();
598 bool any_multi_column = AssignColumns(part_sets);
599#ifndef GRAPHICS_DISABLED
600 if (textord_tabfind_show_columns) {
601 DisplayColumnBounds(&part_sets);
604 ComputeMeanColumnGap(any_multi_column);
606 for (
auto line_set : part_sets) {
607 if (line_set !=
nullptr) {
608 line_set->RelinquishParts();
622 column_sets->clear();
623 if (src_sets == column_sets) {
624 src_sets = &temp_cols;
626 int set_size = temp_cols.size();
628 bool good_only =
true;
630 for (
int i = 0; i < set_size; ++i) {
631 ColPartitionSet *column_candidate = temp_cols.at(i);
633 ColPartitionSet *improved = column_candidate->Copy(good_only);
634 if (improved !=
nullptr) {
635 improved->ImproveColumnCandidate(
WidthCB(), src_sets);
636 improved->AddToColumnSetsIfUnique(column_sets,
WidthCB());
639 good_only = !good_only;
640 }
while (column_sets->empty() && !good_only);
641 if (column_sets->empty()) {
643 *column_sets = temp_cols;
646 for (
auto data : temp_cols) {
653void ColumnFinder::PrintColumnCandidates(
const char *title) {
654 int set_size = column_sets_.size();
655 tprintf(
"Found %d %s:\n", set_size, title);
657 for (
int i = 0; i < set_size; ++i) {
658 ColPartitionSet *column_set = column_sets_.at(i);
673bool ColumnFinder::AssignColumns(
const PartSetVector &part_sets) {
674 int set_count = part_sets.size();
677 best_columns_ =
new ColPartitionSet *[set_count];
678 for (
int y = 0; y < set_count; ++y) {
679 best_columns_[y] =
nullptr;
681 int column_count = column_sets_.size();
691 bool *any_columns_possible =
new bool[set_count];
692 int *assigned_costs =
new int[set_count];
693 int **column_set_costs =
new int *[set_count];
696 for (
int part_i = 0; part_i < set_count; ++part_i) {
697 ColPartitionSet *line_set = part_sets.at(part_i);
698 bool debug = line_set !=
nullptr &&
WithinTestRegion(2, line_set->bounding_box().left(),
699 line_set->bounding_box().bottom());
700 column_set_costs[part_i] =
new int[column_count];
701 any_columns_possible[part_i] =
false;
702 assigned_costs[part_i] = INT32_MAX;
703 for (
int col_i = 0; col_i < column_count; ++col_i) {
704 if (line_set !=
nullptr &&
705 column_sets_.at(col_i)->CompatibleColumns(debug, line_set,
WidthCB())) {
706 column_set_costs[part_i][col_i] = column_sets_.at(col_i)->UnmatchedWidth(line_set);
707 any_columns_possible[part_i] =
true;
709 column_set_costs[part_i][col_i] = INT32_MAX;
711 tprintf(
"Set id %d did not match at y=%d, lineset =%p\n",
712 col_i, part_i,
static_cast<void *
>(line_set));
717 bool any_multi_column =
false;
721 while (BiggestUnassignedRange(set_count, any_columns_possible, &start, &end)) {
723 tprintf(
"Biggest unassigned range = %d- %d\n", start, end);
726 int column_set_id = RangeModalColumnSet(column_set_costs, assigned_costs, start, end);
728 tprintf(
"Range modal column id = %d\n", column_set_id);
729 column_sets_.at(column_set_id)->Print();
732 ShrinkRangeToLongestRun(column_set_costs, assigned_costs, any_columns_possible, column_set_id,
735 tprintf(
"Shrunk range = %d- %d\n", start, end);
740 ExtendRangePastSmallGaps(column_set_costs, assigned_costs, any_columns_possible, column_set_id,
743 ExtendRangePastSmallGaps(column_set_costs, assigned_costs, any_columns_possible, column_set_id,
747 tprintf(
"Column id %d applies to range = %d - %d\n", column_set_id, start, end);
750 AssignColumnToRange(column_set_id, start, end, column_set_costs, assigned_costs);
751 if (column_sets_.at(column_set_id)->GoodColumnCount() > 1) {
752 any_multi_column =
true;
757 if (best_columns_[0] ==
nullptr) {
758 AssignColumnToRange(0, 0,
gridheight_, column_set_costs, assigned_costs);
761 for (
int i = 0; i < set_count; ++i) {
762 delete[] column_set_costs[i];
764 delete[] assigned_costs;
765 delete[] any_columns_possible;
766 delete[] column_set_costs;
767 return any_multi_column;
772bool ColumnFinder::BiggestUnassignedRange(
int set_count,
const bool *any_columns_possible,
773 int *best_start,
int *best_end) {
774 int best_range_size = 0;
775 *best_start = set_count;
776 *best_end = set_count;
778 for (
int start = 0; start <
gridheight_; start = end) {
780 while (start < set_count) {
781 if (best_columns_[start] ==
nullptr && any_columns_possible[start]) {
789 while (end < set_count) {
790 if (best_columns_[end] !=
nullptr) {
793 if (any_columns_possible[end]) {
798 if (start < set_count && range_size > best_range_size) {
799 best_range_size = range_size;
804 return *best_start < *best_end;
808int ColumnFinder::RangeModalColumnSet(
int **column_set_costs,
const int *assigned_costs,
int start,
810 int column_count = column_sets_.size();
811 STATS column_stats(0, column_count - 1);
812 for (
int part_i = start; part_i < end; ++part_i) {
813 for (
int col_j = 0; col_j < column_count; ++col_j) {
814 if (column_set_costs[part_i][col_j] < assigned_costs[part_i]) {
815 column_stats.add(col_j, 1);
820 return column_stats.mode();
827void ColumnFinder::ShrinkRangeToLongestRun(
int **column_set_costs,
const int *assigned_costs,
828 const bool *any_columns_possible,
int column_set_id,
829 int *best_start,
int *best_end) {
831 int orig_start = *best_start;
832 int orig_end = *best_end;
833 int best_range_size = 0;
834 *best_start = orig_end;
835 *best_end = orig_end;
837 for (
int start = orig_start; start < orig_end; start = end) {
839 while (start < orig_end) {
840 if (column_set_costs[start][column_set_id] < assigned_costs[start] ||
841 !any_columns_possible[start]) {
848 while (end < orig_end) {
849 if (column_set_costs[end][column_set_id] >= assigned_costs[start] &&
850 any_columns_possible[end]) {
855 if (start < orig_end && end - start > best_range_size) {
856 best_range_size = end - start;
866void ColumnFinder::ExtendRangePastSmallGaps(
int **column_set_costs,
const int *assigned_costs,
867 const bool *any_columns_possible,
int column_set_id,
868 int step,
int end,
int *start) {
870 tprintf(
"Starting expansion at %d, step=%d, limit=%d\n", *start, step, end);
876 int barrier_size = 0;
882 for (i = *start + step; i != end; i += step) {
883 if (column_set_costs[i][column_set_id] < assigned_costs[i]) {
887 if (any_columns_possible[i]) {
892 tprintf(
"At %d, Barrier size=%d\n", i, barrier_size);
904 for (i += step; i != end; i += step) {
905 if (column_set_costs[i][column_set_id] < assigned_costs[i]) {
907 }
else if (any_columns_possible[i]) {
912 tprintf(
"At %d, good size = %d\n", i, good_size);
915 if (good_size >= barrier_size) {
918 }
while (good_size >= barrier_size);
922void ColumnFinder::AssignColumnToRange(
int column_set_id,
int start,
int end,
923 int **column_set_costs,
int *assigned_costs) {
924 ColPartitionSet *column_set = column_sets_.at(column_set_id);
925 for (
int i = start; i < end; ++i) {
926 assigned_costs[i] = column_set_costs[i][column_set_id];
927 best_columns_[i] = column_set;
932void ColumnFinder::ComputeMeanColumnGap(
bool any_multi_column) {
936 int width_samples = 0;
942 mean_column_gap_ = any_multi_column && gap_samples > 0
943 ? total_gap / gap_samples
944 : width_samples > 0 ? total_width / width_samples : 0;
952static void ReleaseAllBlobsAndDeleteUnused(BLOBNBOX_LIST *blobs) {
953 for (BLOBNBOX_IT blob_it(blobs); !blob_it.empty(); blob_it.forward()) {
954 BLOBNBOX *blob = blob_it.extract();
955 if (blob->owner() ==
nullptr) {
964void ColumnFinder::ReleaseBlobsAndCleanupUnused(TO_BLOCK *block) {
965 ReleaseAllBlobsAndDeleteUnused(&block->blobs);
966 ReleaseAllBlobsAndDeleteUnused(&block->small_blobs);
967 ReleaseAllBlobsAndDeleteUnused(&block->noise_blobs);
968 ReleaseAllBlobsAndDeleteUnused(&block->large_blobs);
969 ReleaseAllBlobsAndDeleteUnused(&image_bblobs_);
973void ColumnFinder::GridSplitPartitions() {
975 GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT> gsearch(&part_grid_);
976 gsearch.StartFullSearch();
977 ColPartition *dont_repeat =
nullptr;
979 while ((part = gsearch.NextFullSearch()) !=
nullptr) {
980 if (part->blob_type() <
BRT_UNKNOWN || part == dont_repeat) {
983 ColPartitionSet *column_set = best_columns_[gsearch.GridY()];
987 part->ColumnRange(
resolution_, column_set, &first_col, &last_col);
997 if (last_col != first_col + 1) {
1001 int y = part->MidY();
1002 TBOX margin_box = part->bounding_box();
1005 tprintf(
"Considering partition for GridSplit:");
1008 ColPartition *column = column_set->GetColumnByIndex(first_col);
1009 if (column ==
nullptr) {
1012 margin_box.set_left(column->RightAtY(y) + 2);
1013 column = column_set->GetColumnByIndex(last_col);
1014 if (column ==
nullptr) {
1017 margin_box.set_right(column->LeftAtY(y) - 2);
1021 GridSearch<BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT> rectsearch(
this);
1023 tprintf(
"Searching box (%d,%d)->(%d,%d)\n", margin_box.left(), margin_box.bottom(),
1024 margin_box.right(), margin_box.top());
1027 rectsearch.StartRectSearch(margin_box);
1029 while ((bbox = rectsearch.NextRectSearch()) !=
nullptr) {
1030 if (bbox->bounding_box().overlap(margin_box)) {
1034 if (bbox ==
nullptr) {
1036 gsearch.RemoveBBox();
1037 int x_middle = (margin_box.left() + margin_box.right()) / 2;
1039 tprintf(
"Splitting part at %d:", x_middle);
1042 ColPartition *split_part = part->SplitAt(x_middle);
1043 if (split_part !=
nullptr) {
1047 split_part->Print();
1049 part_grid_.
InsertBBox(
true,
true, split_part);
1053 tprintf(
"Split had no effect\n");
1058 gsearch.RepositionIterator();
1060 tprintf(
"Part cannot be split: blob (%d,%d)->(%d,%d) in column gap\n",
1061 bbox->bounding_box().left(), bbox->bounding_box().bottom(),
1062 bbox->bounding_box().right(), bbox->bounding_box().top());
1069void ColumnFinder::GridMergePartitions() {
1071 GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT> gsearch(&part_grid_);
1072 gsearch.StartFullSearch();
1074 while ((part = gsearch.NextFullSearch()) !=
nullptr) {
1075 if (part->IsUnMergeableType()) {
1079 ColPartitionSet *columns = best_columns_[gsearch.GridY()];
1080 TBOX box = part->bounding_box();
1083 tprintf(
"Considering part for merge at:");
1086 int y = part->MidY();
1087 ColPartition *left_column = columns->ColumnContaining(box.left(), y);
1088 ColPartition *right_column = columns->ColumnContaining(box.right(), y);
1089 if (left_column ==
nullptr || right_column != left_column) {
1091 tprintf(
"In different columns\n");
1095 box.set_left(left_column->LeftAtY(y));
1096 box.set_right(right_column->RightAtY(y));
1098 bool modified_box =
false;
1099 GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT> rsearch(&part_grid_);
1100 rsearch.SetUniqueMode(
true);
1101 rsearch.StartRectSearch(box);
1102 ColPartition *neighbour;
1104 while ((neighbour = rsearch.NextRectSearch()) !=
nullptr) {
1105 if (neighbour == part || neighbour->IsUnMergeableType()) {
1108 const TBOX &neighbour_box = neighbour->bounding_box();
1110 tprintf(
"Considering merge with neighbour at:");
1113 if (neighbour_box.right() < box.left() || neighbour_box.left() > box.right()) {
1116 if (part->VSignificantCoreOverlap(*neighbour) && part->TypesMatch(*neighbour)) {
1122 const TBOX &part_box = part->bounding_box();
1125 if (neighbour_box.left() > part->right_margin() &&
1126 part_box.right() < neighbour->left_margin()) {
1129 if (neighbour_box.right() < part->left_margin() &&
1130 part_box.left() > neighbour->right_margin()) {
1133 int h_gap = std::max(part_box.left(), neighbour_box.left()) -
1134 std::min(part_box.right(), neighbour_box.right());
1136 part_box.width() < mean_column_gap_ || neighbour_box.width() < mean_column_gap_) {
1138 tprintf(
"Running grid-based merge between:\n");
1142 rsearch.RemoveBBox();
1143 if (!modified_box) {
1145 gsearch.RemoveBBox();
1146 rsearch.RepositionIterator();
1147 modified_box =
true;
1149 part->Absorb(neighbour,
WidthCB());
1151 tprintf(
"Neighbour failed hgap test\n");
1154 tprintf(
"Neighbour failed overlap or typesmatch test\n");
1165 gsearch.RepositionIterator();
1172void ColumnFinder::InsertRemainingNoise(TO_BLOCK *block) {
1173 BLOBNBOX_IT blob_it(&block->noise_blobs);
1174 for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
1175 BLOBNBOX *blob = blob_it.data();
1176 if (blob->owner() !=
nullptr) {
1179 TBOX search_box(blob->bounding_box());
1184 rsearch.SetUniqueMode(
true);
1185 rsearch.StartRectSearch(search_box);
1187 ColPartition *best_part =
nullptr;
1188 int best_distance = 0;
1189 while ((part = rsearch.NextRectSearch()) !=
nullptr) {
1190 if (part->IsUnMergeableType()) {
1195 if (best_part ==
nullptr ||
distance < best_distance) {
1200 if (best_part !=
nullptr &&
1201 best_distance < kMaxDistToPartSizeRatio * best_part->median_height()) {
1204 tprintf(
"Adding noise blob with distance %d, thr=%g:box:", best_distance,
1206 blob->bounding_box().print();
1211 best_part->AddBox(blob);
1212 part_grid_.
InsertBBox(
true,
true, best_part);
1213 blob->set_owner(best_part);
1214 blob->set_flow(best_part->flow());
1215 blob->set_region_type(best_part->blob_type());
1222 block->DeleteUnownedNoise();
1226static TBOX BoxFromHLine(
const TabVector *hline) {
1227 int top = std::max(hline->startpt().y(), hline->endpt().y());
1228 int bottom = std::min(hline->startpt().y(), hline->endpt().y());
1229 top += hline->mean_width();
1230 if (top == bottom) {
1237 return TBOX(hline->startpt().x(), bottom, hline->endpt().x(), top);
1242void ColumnFinder::GridRemoveUnderlinePartitions() {
1243 TabVector_IT hline_it(&horizontal_lines_);
1244 for (hline_it.mark_cycle_pt(); !hline_it.cycled_list(); hline_it.forward()) {
1245 TabVector *hline = hline_it.data();
1246 if (hline->intersects_other_lines()) {
1249 TBOX line_box = BoxFromHLine(hline);
1250 TBOX search_box = line_box;
1251 search_box.pad(0, line_box.height());
1253 part_search.SetUniqueMode(
true);
1254 part_search.StartRectSearch(search_box);
1255 ColPartition *covered;
1256 bool touched_table =
false;
1257 bool touched_text =
false;
1258 ColPartition *line_part =
nullptr;
1259 while ((covered = part_search.NextRectSearch()) !=
nullptr) {
1261 touched_table =
true;
1263 }
else if (covered->IsTextType()) {
1265 int text_bottom = covered->median_bottom();
1266 if (line_box.bottom() <= text_bottom && text_bottom <= search_box.top()) {
1267 touched_text =
true;
1269 }
else if (covered->blob_type() ==
BRT_HLINE && line_box.contains(covered->bounding_box()) &&
1271 !
TBOX(covered->bounding_box()).contains(line_box)) {
1272 line_part = covered;
1275 if (line_part !=
nullptr && !touched_table && touched_text) {
1283void ColumnFinder::GridInsertHLinePartitions() {
1284 TabVector_IT hline_it(&horizontal_lines_);
1285 for (hline_it.mark_cycle_pt(); !hline_it.cycled_list(); hline_it.forward()) {
1286 TabVector *hline = hline_it.data();
1287 TBOX line_box = BoxFromHLine(hline);
1288 ColPartition *part =
1290 line_box.bottom(), line_box.right(), line_box.top());
1292 bool any_image =
false;
1294 part_search.SetUniqueMode(
true);
1295 part_search.StartRectSearch(line_box);
1296 ColPartition *covered;
1297 while ((covered = part_search.NextRectSearch()) !=
nullptr) {
1298 if (covered->IsImageType()) {
1312void ColumnFinder::GridInsertVLinePartitions() {
1314 for (vline_it.mark_cycle_pt(); !vline_it.cycled_list(); vline_it.forward()) {
1315 TabVector *vline = vline_it.data();
1316 if (!vline->IsSeparator()) {
1319 int left = std::min(vline->startpt().x(), vline->endpt().x());
1320 int right = std::max(vline->startpt().x(), vline->endpt().x());
1321 right += vline->mean_width();
1322 if (left == right) {
1332 bool any_image =
false;
1334 part_search.SetUniqueMode(
true);
1335 part_search.StartRectSearch(part->bounding_box());
1336 ColPartition *covered;
1337 while ((covered = part_search.NextRectSearch()) !=
nullptr) {
1338 if (covered->IsImageType()) {
1353void ColumnFinder::SetPartitionTypes() {
1354 GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT> gsearch(&part_grid_);
1355 gsearch.StartFullSearch();
1357 while ((part = gsearch.NextFullSearch()) !=
nullptr) {
1358 part->SetPartitionType(
resolution_, best_columns_[gsearch.GridY()]);
1364void ColumnFinder::SmoothPartnerRuns() {
1366 GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT> gsearch(&part_grid_);
1367 gsearch.StartFullSearch();
1369 while ((part = gsearch.NextFullSearch()) !=
nullptr) {
1370 ColPartition *partner = part->SingletonPartner(
true);
1371 if (partner !=
nullptr) {
1372 if (partner->SingletonPartner(
false) != part) {
1373 tprintf(
"Ooops! Partition:(%d partners)", part->upper_partners()->length());
1375 tprintf(
"has singleton partner:(%d partners", partner->lower_partners()->length());
1377 tprintf(
"but its singleton partner is:");
1378 if (partner->SingletonPartner(
false) ==
nullptr) {
1381 partner->SingletonPartner(
false)->Print();
1384 ASSERT_HOST(partner->SingletonPartner(
false) == part);
1385 }
else if (part->SingletonPartner(
false) !=
nullptr) {
1386 ColPartitionSet *column_set = best_columns_[gsearch.GridY()];
1388 part->SmoothPartnerRun(column_count * 2 + 1);
1395void ColumnFinder::AddToTempPartList(ColPartition *part, ColPartition_CLIST *temp_list) {
1396 int mid_y = part->MidY();
1397 ColPartition_C_IT it(temp_list);
1398 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1399 ColPartition *test_part = it.data();
1403 if (test_part == part->SingletonPartner(
false)) {
1406 int neighbour_bottom = test_part->median_bottom();
1407 int neighbour_top = test_part->median_top();
1408 int neighbour_y = (neighbour_bottom + neighbour_top) / 2;
1409 if (neighbour_y < mid_y) {
1412 if (!part->HOverlaps(*test_part) && !part->WithinSameMargins(*test_part)) {
1416 if (it.cycled_list()) {
1417 it.add_to_end(part);
1419 it.add_before_stay_put(part);
1424void ColumnFinder::EmptyTempPartList(ColPartition_CLIST *temp_list, WorkingPartSet_LIST *work_set) {
1425 ColPartition_C_IT it(temp_list);
1426 while (!it.empty()) {
1433void ColumnFinder::TransformToBlocks(BLOCK_LIST *blocks, TO_BLOCK_LIST *to_blocks) {
1434 WorkingPartSet_LIST work_set;
1435 ColPartitionSet *column_set =
nullptr;
1436 ColPartition_IT noise_it(&noise_parts_);
1440 ColPartition_CLIST temp_part_list;
1442 GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT> gsearch(&part_grid_);
1443 gsearch.StartFullSearch();
1444 int prev_grid_y = -1;
1446 while ((part = gsearch.NextFullSearch()) !=
nullptr) {
1447 int grid_y = gsearch.GridY();
1448 if (grid_y != prev_grid_y) {
1449 EmptyTempPartList(&temp_part_list, &work_set);
1450 prev_grid_y = grid_y;
1452 if (best_columns_[grid_y] != column_set) {
1453 column_set = best_columns_[grid_y];
1458 tprintf(
"Changed column groups at grid index %d, y=%d\n", gsearch.GridY(),
1463 noise_it.add_to_end(part);
1465 AddToTempPartList(part, &temp_part_list);
1468 EmptyTempPartList(&temp_part_list, &work_set);
1470 WorkingPartSet_IT work_it(&work_set);
1471 while (!work_it.empty()) {
1472 WorkingPartSet *working_set = work_it.extract();
1482static void ReflectBlobList(BLOBNBOX_LIST *bblobs) {
1483 BLOBNBOX_IT it(bblobs);
1484 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1485 it.data()->reflect_box_in_y_axis();
1495void ColumnFinder::ReflectForRtl(TO_BLOCK *input_block, BLOBNBOX_LIST *bblobs) {
1496 ReflectBlobList(bblobs);
1497 ReflectBlobList(&input_block->blobs);
1498 ReflectBlobList(&input_block->small_blobs);
1499 ReflectBlobList(&input_block->noise_blobs);
1500 ReflectBlobList(&input_block->large_blobs);
1502 auto *new_denorm =
new DENORM;
1503 new_denorm->SetupNormalization(
nullptr,
nullptr, denorm_, 0.0f, 0.0f, -1.0f, 1.0f, 0.0f, 0.0f);
1504 denorm_ = new_denorm;
1510static void RotateAndExplodeBlobList(
const FCOORD &blob_rotation, BLOBNBOX_LIST *bblobs,
1511 STATS *widths, STATS *heights) {
1512 BLOBNBOX_IT it(bblobs);
1513 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1514 BLOBNBOX *blob = it.data();
1515 C_BLOB *cblob = blob->cblob();
1516 C_OUTLINE_LIST *outlines = cblob->out_list();
1517 C_OUTLINE_IT ol_it(outlines);
1518 if (!outlines->singleton()) {
1521 for (; !ol_it.empty(); ol_it.forward()) {
1522 C_OUTLINE *outline = ol_it.extract();
1527 it.add_after_stay_put(new_blob);
1532 if (blob_rotation.x() != 1.0f || blob_rotation.y() != 0.0f) {
1533 cblob->rotate(blob_rotation);
1535 blob->compute_bounding_box();
1536 widths->add(blob->bounding_box().width(), 1);
1537 heights->add(blob->bounding_box().height(), 1);
1554void ColumnFinder::RotateAndReskewBlocks(
bool input_is_rtl, TO_BLOCK_LIST *blocks) {
1557 FCOORD tmp = deskew_;
1561 TO_BLOCK_IT it(blocks);
1562 int block_index = 1;
1563 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1564 TO_BLOCK *to_block = it.data();
1565 BLOCK *block = to_block->block;
1569 block->reflect_polygon_in_y_axis();
1571 block->rotate(reskew_);
1573 block->set_right_to_left(input_is_rtl);
1575 block->set_skew(reskew_);
1576 block->pdblk.set_index(block_index++);
1577 FCOORD blob_rotation = ComputeBlockAndClassifyRotation(block);
1580 STATS widths(0, block->pdblk.bounding_box().width() - 1);
1581 STATS heights(0, block->pdblk.bounding_box().height() - 1);
1582 RotateAndExplodeBlobList(blob_rotation, &to_block->blobs, &widths, &heights);
1583 TO_ROW_IT row_it(to_block->get_rows());
1584 for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
1585 TO_ROW *row = row_it.data();
1586 RotateAndExplodeBlobList(blob_rotation, row->blob_list(), &widths, &heights);
1588 block->set_median_size(
static_cast<int>(widths.median() + 0.5),
1589 static_cast<int>(heights.median() + 0.5));
1591 tprintf(
"Block median size = (%d, %d)\n", block->median_size().x(), block->median_size().y());
1601FCOORD ColumnFinder::ComputeBlockAndClassifyRotation(BLOCK *block) {
1610 FCOORD classify_rotation(text_rotation_);
1611 FCOORD block_rotation(1.0f, 0.0f);
1617 if (rerotate_.
x() == 0.0f) {
1618 block_rotation = rerotate_;
1620 block_rotation = FCOORD(0.0f, -1.0f);
1622 block->rotate(block_rotation);
1623 classify_rotation = FCOORD(1.0f, 0.0f);
1625 block_rotation.rotate(rotation_);
1629 FCOORD blob_rotation(block_rotation);
1630 block_rotation.set_y(-block_rotation.y());
1631 block->set_re_rotation(block_rotation);
1632 block->set_classify_rotation(classify_rotation);
1634 tprintf(
"Blk %d, type %d rerotation(%.2f, %.2f), char(%.2f,%.2f), box:", block->pdblk.index(),
1635 block->pdblk.poly_block()->isA(), block->re_rotation().x(), block->re_rotation().y(),
1636 classify_rotation.x(), classify_rotation.y());
1637 block->pdblk.bounding_box().print();
1639 return blob_rotation;
#define BOOL_VAR(name, val, comment)
#define INT_VAR(name, val, comment)
UnicodeText::const_iterator::difference_type distance(const UnicodeText::const_iterator &first, const UnicodeText::const_iterator &last)
void tprintf(const char *format,...)
const int kMaxIncompatibleColumnCount
bool PSM_COL_FIND_ENABLED(int pageseg_mode)
bool textord_debug_printable
GridSearch< ColPartition, ColPartition_CLIST, ColPartition_C_IT > ColPartitionGridSearch
bool PSM_SPARSE(int pageseg_mode)
int textord_debug_tabfind
std::vector< ColPartitionSet * > PartSetVector
const double kHorizontalGapMergeFraction
const double kMaxDistToPartSizeRatio
const double kMinGutterWidthGrid
static BLOBNBOX * RealBlob(C_OUTLINE *outline)
void ReSetAndReFilterBlobs()
BLOBNBOX_LIST small_blobs
void plot_graded_blobs(ScrollView *to_win)
BLOBNBOX_LIST large_blobs
BLOBNBOX_LIST noise_blobs
void ComputeEdgeOffsets(Image thresholds, Image grey)
const DENORM * predecessor() const
void SetupNormalization(const BLOCK *block, const FCOORD *rotation, const DENORM *predecessor, float x_origin, float y_origin, float x_scale, float y_scale, float final_xshift, float final_yshift)
bool right_to_left() const
TDimension y() const
access_function
void set_y(float yin)
rewrite function
void rotate(const FCOORD vec)
static bool WithinTestRegion(int detail_level, int x, int y)
const ICOORD & bleft() const
const ICOORD & tright() const
void DisplayBoxes(ScrollView *window)
void AssertNoDuplicates()
void Init(int gridsize, const ICOORD &bleft, const ICOORD &tright)
void InsertBBox(bool h_spread, bool v_spread, BBC *bbox)
ScrollView * MakeWindow(int x, int y, const char *window_name)
void RemoveBBox(BBC *bbox)
Image ComputeNonTextMask(bool debug, Image photo_map, TO_BLOCK *blob_block)
void GetDeskewVectors(FCOORD *deskew, FCOORD *reskew)
bool IsVerticallyAlignedText(double find_vertical_text_ratio, TO_BLOCK *block, BLOBNBOX_CLIST *osd_blobs)
ColumnFinder(int gridsize, const ICOORD &bleft, const ICOORD &tright, int resolution, bool cjk_script, double aligned_gap_fraction, TabVector_LIST *vlines, TabVector_LIST *hlines, int vertical_x, int vertical_y)
void SetEquationDetect(EquationDetectBase *detect)
int FindBlocks(PageSegMode pageseg_mode, Image scaled_color, int scaled_factor, TO_BLOCK *block, Image photo_mask_pix, Image thresholds_pix, Image grey_pix, DebugPixa *pixa_debug, BLOCK_LIST *blocks, BLOBNBOX_LIST *diacritic_blobs, TO_BLOCK_LIST *to_blocks)
void SetupAndFilterNoise(PageSegMode pageseg_mode, Image photo_mask_pix, TO_BLOCK *input_block)
void CorrectOrientation(TO_BLOCK *block, bool vertical_text_lines, int recognition_rotation)
static ColPartition * MakeLinePartition(BlobRegionType blob_type, const ICOORD &vertical, int left, int bottom, int right, int top)
void ExtractPartitionsAsBlocks(BLOCK_LIST *blocks, TO_BLOCK_LIST *to_blocks)
void SetTabStops(TabFind *tabgrid)
void RefinePartitionPartners(bool get_desperate)
void GridFindMargins(ColPartitionSet **best_columns)
bool MakeColPartSets(PartSetVector *part_sets)
void FindPartitionPartners()
void DeleteUnknownParts(TO_BLOCK *block)
ColPartitionSet * MakeSingleColumnSet(WidthCallback cb)
void FindFigureCaptions()
void ReTypeBlobs(BLOBNBOX_LIST *im_blobs)
void AccumulateColumnWidthsAndGaps(int *total_width, int *width_samples, int *total_gap, int *gap_samples)
void DisplayColumnEdges(int y_bottom, int y_top, ScrollView *win)
void AddToColumnSetsIfUnique(PartSetVector *column_sets, const WidthCallback &cb)
virtual int FindEquationParts(ColPartitionGrid *part_grid, ColPartitionSet **best_columns)=0
static void FindImagePartitions(Image image_pix, const FCOORD &rotation, const FCOORD &rerotation, TO_BLOCK *block, TabFind *tab_grid, DebugPixa *pixa_debug, ColPartitionGrid *part_grid, ColPartition_LIST *big_parts)
static void TransferImagePartsToImageMask(const FCOORD &rerotation, ColPartitionGrid *part_grid, Image image_mask)
void FindTextlineDirectionAndFixBrokenCJK(PageSegMode pageseg_mode, bool cjk_merge, TO_BLOCK *input_block)
void CorrectForRotation(const FCOORD &rerotation, ColPartitionGrid *part_grid)
void RemoveLineResidue(ColPartition_LIST *big_part_list)
void GradeBlobsIntoPartitions(PageSegMode pageseg_mode, const FCOORD &rerotation, TO_BLOCK *block, Image nontext_pix, const DENORM *denorm, bool cjk_script, TextlineProjection *projection, BLOBNBOX_LIST *diacritic_blobs, ColPartitionGrid *part_grid, ColPartition_LIST *big_parts)
void SetNeighboursOnMediumBlobs(TO_BLOCK *block)
void FindLeaderPartitions(TO_BLOCK *block, ColPartitionGrid *part_grid)
bool TestVerticalTextDirection(double find_vertical_text_ratio, TO_BLOCK *block, BLOBNBOX_CLIST *osd_blobs)
TabVector_LIST * dead_vectors()
static void RotateBlobList(const FCOORD &rotation, BLOBNBOX_LIST *blobs)
void InsertBlobsToGrid(bool h_spread, bool v_spread, BLOBNBOX_LIST *blobs, BBGrid< BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT > *grid)
void ResetForVerticalText(const FCOORD &rotate, const FCOORD &rerotate, TabVector_LIST *horizontal_lines, int *min_gutter_width)
void DontFindTabVectors(BLOBNBOX_LIST *image_blobs, TO_BLOCK *block, FCOORD *deskew, FCOORD *reskew)
int resolution_
Of source image in pixels per inch.
bool FindTabVectors(TabVector_LIST *hlines, BLOBNBOX_LIST *image_blobs, TO_BLOCK *block, int min_gutter_width, double tabfind_aligned_gap_fraction, ColPartitionGrid *part_grid, FCOORD *deskew, FCOORD *reskew)
void TidyBlobs(TO_BLOCK *block)
void SetBlockRuleEdges(TO_BLOCK *block)
ICOORD vertical_skew_
Estimate of true vertical in this image.
ScrollView * FindInitialTabVectors(BLOBNBOX_LIST *image_blobs, int min_gutter_width, double tabfind_aligned_gap_fraction, TO_BLOCK *block)
ScrollView * DisplayTabVectors(ScrollView *tab_win)
void Init(int grid_size, const ICOORD &bottom_left, const ICOORD &top_right)
void set_resolution(int resolution)
void InsertCleanPartitions(ColPartitionGrid *grid, TO_BLOCK *block)
void set_left_to_right_language(bool order)
void LocateTables(ColPartitionGrid *grid, ColPartitionSet **columns, WidthCallback width_cb, const FCOORD &reskew)
int DistanceOfBoxFromPartition(const TBOX &box, const ColPartition &part, const DENORM *denorm, bool debug) const
SVEvent * AwaitEvent(SVEventType type)