tesseract 5.2.0
Loading...
Searching...
No Matches
colfind.cpp
Go to the documentation of this file.
1
2// File: colfind.cpp
3// Description: Class to hold BLOBNBOXs in a grid for fast access
4// to neighbours.
5// Author: Ray Smith
6//
7// (C) Copyright 2007, Google Inc.
8// Licensed under the Apache License, Version 2.0 (the "License");
9// you may not use this file except in compliance with the License.
10// You may obtain a copy of the License at
11// http://www.apache.org/licenses/LICENSE-2.0
12// Unless required by applicable law or agreed to in writing, software
13// distributed under the License is distributed on an "AS IS" BASIS,
14// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15// See the License for the specific language governing permissions and
16// limitations under the License.
17//
19
20// Include automatically generated configuration file if running autoconf.
21#ifdef HAVE_CONFIG_H
22# include "config_auto.h"
23#endif
24
25#include "colfind.h"
26
27#include "ccnontextdetect.h"
28#include "colpartition.h"
29#include "colpartitionset.h"
30#ifndef DISABLED_LEGACY_ENGINE
31# include "equationdetectbase.h"
32#endif
33#include "blobbox.h"
34#include "linefind.h"
35#include "normalis.h"
36#include "params.h"
37#include "scrollview.h"
38#include "strokewidth.h"
39#include "tablefind.h"
40#include "workingpartset.h"
41
42#include <algorithm>
43
44namespace tesseract {
45
46// When assigning columns, the max number of misfit grid rows/ColPartitionSets
47// that can be ignored.
49// Max fraction of mean_column_gap_ for the gap between two partitions within a
50// column to allow them to merge.
51const double kHorizontalGapMergeFraction = 0.5;
52// Minimum gutter width as a fraction of gridsize
53const double kMinGutterWidthGrid = 0.5;
54// Max multiple of a partition's median size as a distance threshold for
55// adding noise blobs.
56const double kMaxDistToPartSizeRatio = 1.5;
57
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)");
65#endif
66static BOOL_VAR(textord_tabfind_find_tables, true, "run table detection");
67
68#ifndef GRAPHICS_DISABLED
69ScrollView *ColumnFinder::blocks_win_ = nullptr;
70#endif
71
72// Gridsize is an estimate of the text size in the image. A suitable value
73// is in TO_BLOCK::line_size after find_components has been used to make
74// the blobs.
75// bleft and tright are the bounds of the image (or rectangle) being processed.
76// vlines is a (possibly empty) list of TabVector and vertical_x and y are
77// the sum logical vertical vector produced by LineFinder::FindVerticalLines.
78ColumnFinder::ColumnFinder(int gridsize, const ICOORD &bleft, const ICOORD &tright, int resolution,
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)
83 , min_gutter_width_(static_cast<int>(kMinGutterWidthGrid * gridsize))
84 , mean_column_gap_(tright.x() - bleft.x())
85 , tabfind_aligned_gap_fraction_(aligned_gap_fraction)
86 , deskew_(0.0f, 0.0f)
87 , reskew_(1.0f, 0.0f)
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)
96 , denorm_(nullptr)
97 , equation_detect_(nullptr) {
98 TabVector_IT h_it(&horizontal_lines_);
99 h_it.add_list_after(hlines);
100}
101
103 for (auto set : column_sets_) {
104 delete set;
105 }
106 delete[] best_columns_;
107 delete stroke_width_;
108#ifndef GRAPHICS_DISABLED
109 delete input_blobs_win_;
110#endif
111 nontext_map_.destroy();
112 while (denorm_ != nullptr) {
113 DENORM *dead_denorm = denorm_;
114 denorm_ = const_cast<DENORM *>(denorm_->predecessor());
115 delete dead_denorm;
116 }
117
118 // The ColPartitions are destroyed automatically, but any boxes in
119 // the noise_parts_ list are owned and need to be deleted explicitly.
120 ColPartition_IT part_it(&noise_parts_);
121 for (part_it.mark_cycle_pt(); !part_it.cycled_list(); part_it.forward()) {
122 ColPartition *part = part_it.data();
123 part->DeleteBoxes();
124 }
125 // Likewise any boxes in the good_parts_ list need to be deleted.
126 // These are just the image parts. Text parts have already given their
127 // boxes on to the TO_BLOCK, and have empty lists.
128 part_it.set_to_list(&good_parts_);
129 for (part_it.mark_cycle_pt(); !part_it.cycled_list(); part_it.forward()) {
130 ColPartition *part = part_it.data();
131 part->DeleteBoxes();
132 }
133 // Also, any blobs on the image_bblobs_ list need to have their cblobs
134 // deleted. This only happens if there has been an early return from
135 // FindColumns, as in a normal return, the blobs go into the grid and
136 // end up in noise_parts_, good_parts_ or the output blocks.
137 BLOBNBOX_IT bb_it(&image_bblobs_);
138 for (bb_it.mark_cycle_pt(); !bb_it.cycled_list(); bb_it.forward()) {
139 BLOBNBOX *bblob = bb_it.data();
140 delete bblob->cblob();
141 }
142}
143
144// Performs initial processing on the blobs in the input_block:
145// Setup the part_grid, stroke_width_, nontext_map.
146// Obvious noise blobs are filtered out and used to mark the nontext_map_.
147// Initial stroke-width analysis is used to get local text alignment
148// direction, so the textline projection_ map can be setup.
149// On return, IsVerticallyAlignedText may be called (now optionally) to
150// determine the gross textline alignment of the page.
151void ColumnFinder::SetupAndFilterNoise(PageSegMode pageseg_mode, Image photo_mask_pix,
152 TO_BLOCK *input_block) {
153 part_grid_.Init(gridsize(), bleft(), tright());
154 delete stroke_width_;
155 stroke_width_ = new StrokeWidth(gridsize(), bleft(), tright());
156 min_gutter_width_ = static_cast<int>(kMinGutterWidthGrid * gridsize());
157 input_block->ReSetAndReFilterBlobs();
158#ifndef GRAPHICS_DISABLED
159 if (textord_tabfind_show_blocks) {
160 input_blobs_win_ = MakeWindow(0, 0, "Filtered Input Blobs");
161 input_block->plot_graded_blobs(input_blobs_win_);
162 }
163#endif // !GRAPHICS_DISABLED
164 SetBlockRuleEdges(input_block);
165 nontext_map_.destroy();
166 // Run a preliminary strokewidth neighbour detection on the medium blobs.
167 stroke_width_->SetNeighboursOnMediumBlobs(input_block);
168 CCNonTextDetect nontext_detect(gridsize(), bleft(), tright());
169 // Remove obvious noise and make the initial non-text map.
170 nontext_map_ =
171 nontext_detect.ComputeNonTextMask(textord_debug_tabfind, photo_mask_pix, input_block);
172 stroke_width_->FindTextlineDirectionAndFixBrokenCJK(pageseg_mode, cjk_script_, input_block);
173 // Clear the strokewidth grid ready for rotation or leader finding.
174 stroke_width_->Clear();
175}
176
177// Tests for vertical alignment of text (returning true if so), and generates
178// a list of blobs of moderate aspect ratio, in the most frequent writing
179// direction (in osd_blobs) for orientation and script detection to test
180// the character orientation.
181// block is the single block for the whole page or rectangle to be OCRed.
182// Note that the vertical alignment may be due to text whose writing direction
183// is vertical, like say Japanese, or due to text whose writing direction is
184// horizontal but whose text appears vertically aligned because the image is
185// not the right way up.
186bool ColumnFinder::IsVerticallyAlignedText(double find_vertical_text_ratio, TO_BLOCK *block,
187 BLOBNBOX_CLIST *osd_blobs) {
188 return stroke_width_->TestVerticalTextDirection(find_vertical_text_ratio, block, osd_blobs);
189}
190
191// Rotates the blobs and the TabVectors so that the gross writing direction
192// (text lines) are horizontal and lines are read down the page.
193// Applied rotation stored in rotation_.
194// A second rotation is calculated for application during recognition to
195// make the rotated blobs upright for recognition.
196// Subsequent rotation stored in text_rotation_.
197//
198// Arguments:
199// vertical_text_lines true if the text lines are vertical.
200// recognition_rotation [0..3] is the number of anti-clockwise 90 degree
201// rotations from osd required for the text to be upright and readable.
202void ColumnFinder::CorrectOrientation(TO_BLOCK *block, bool vertical_text_lines,
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);
208
209 text_rotation_ = norotation;
210 // Rotate the page to make the text upright, as implied by
211 // recognition_rotation.
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;
219 }
220 // We infer text writing direction to be vertical if there are several
221 // vertical text lines detected, and horizontal if not. But if the page
222 // orientation was determined to be 90 or 270 degrees, the true writing
223 // direction is the opposite of what we inferred.
224 if (recognition_rotation & 1) {
225 vertical_text_lines = !vertical_text_lines;
226 }
227 // If we still believe the writing direction is vertical, we use the
228 // convention of rotating the page ccw 90 degrees to make the text lines
229 // horizontal, and mark the blobs for rotation cw 90 degrees for
230 // classification so that the text order is correct after recognition.
231 if (vertical_text_lines) {
232 rotation_.rotate(anticlockwise90);
233 text_rotation_.rotate(clockwise90);
234 }
235 // Set rerotate_ to the inverse of rotation_.
236 rerotate_ = FCOORD(rotation_.x(), -rotation_.y());
237 if (rotation_.x() != 1.0f || rotation_.y() != 0.0f) {
238 // Rotate all the blobs and tab vectors.
239 RotateBlobList(rotation_, &block->large_blobs);
240 RotateBlobList(rotation_, &block->blobs);
241 RotateBlobList(rotation_, &block->small_blobs);
242 RotateBlobList(rotation_, &block->noise_blobs);
243 TabFind::ResetForVerticalText(rotation_, rerotate_, &horizontal_lines_, &min_gutter_width_);
244 part_grid_.Init(gridsize(), bleft(), tright());
245 // Reset all blobs to initial state and filter by size.
246 // Since they have rotated, the list they belong on could have changed.
247 block->ReSetAndReFilterBlobs();
248 SetBlockRuleEdges(block);
249 stroke_width_->CorrectForRotation(rerotate_, &part_grid_);
250 }
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(),
254 text_rotation_.y());
255 }
256 // Setup the denormalization.
257 ASSERT_HOST(denorm_ == nullptr);
258 denorm_ = new DENORM;
259 denorm_->SetupNormalization(nullptr, &rotation_, nullptr, 0.0f, 0.0f, 1.0f, 1.0f, 0.0f, 0.0f);
260}
261
262// Finds blocks of text, image, rule line, table etc, returning them in the
263// blocks and to_blocks
264// (Each TO_BLOCK points to the basic BLOCK and adds more information.)
265// Image blocks are generated by a combination of photo_mask_pix (which may
266// NOT be nullptr) and the rejected text found during preliminary textline
267// finding.
268// The input_block is the result of a call to find_components, and contains
269// the blobs found in the image or rectangle to be OCRed. These blobs will be
270// removed and placed in the output blocks, while unused ones will be deleted.
271// If single_column is true, the input is treated as single column, but
272// it is still divided into blocks of equal line spacing/text size.
273// scaled_color is scaled down by scaled_factor from the input color image,
274// and may be nullptr if the input was not color.
275// grey_pix is optional, but if present must match the photo_mask_pix in size,
276// and must be a *real* grey image instead of binary_pix * 255.
277// thresholds_pix is expected to be present iff grey_pix is present and
278// can be an integer factor reduction of the grey_pix. It represents the
279// thresholds that were used to create the binary_pix from the grey_pix.
280// If diacritic_blobs is non-null, then diacritics/noise blobs, that would
281// confuse layout analysis by causing textline overlap, are placed there,
282// with the expectation that they will be reassigned to words later and
283// noise/diacriticness determined via classification.
284// Returns -1 if the user hits the 'd' key in the blocks window while running
285// in debug mode, which requests a retry with more debug info.
286int ColumnFinder::FindBlocks(PageSegMode pageseg_mode, Image scaled_color, int scaled_factor,
287 TO_BLOCK *input_block, Image photo_mask_pix, Image thresholds_pix,
288 Image grey_pix, DebugPixa *pixa_debug, BLOCK_LIST *blocks,
289 BLOBNBOX_LIST *diacritic_blobs, TO_BLOCK_LIST *to_blocks) {
290 photo_mask_pix |= nontext_map_;
291 stroke_width_->FindLeaderPartitions(input_block, &part_grid_);
292 stroke_width_->RemoveLineResidue(&big_parts_);
293 FindInitialTabVectors(nullptr, min_gutter_width_, tabfind_aligned_gap_fraction_, input_block);
294 SetBlockRuleEdges(input_block);
295 stroke_width_->GradeBlobsIntoPartitions(pageseg_mode, rerotate_, input_block, nontext_map_,
296 denorm_, cjk_script_, &projection_, diacritic_blobs,
297 &part_grid_, &big_parts_);
298 if (!PSM_SPARSE(pageseg_mode)) {
299 ImageFind::FindImagePartitions(photo_mask_pix, rotation_, rerotate_, input_block, this,
300 pixa_debug, &part_grid_, &big_parts_);
301 ImageFind::TransferImagePartsToImageMask(rerotate_, &part_grid_, photo_mask_pix);
302 ImageFind::FindImagePartitions(photo_mask_pix, rotation_, rerotate_, input_block, this,
303 pixa_debug, &part_grid_, &big_parts_);
304 }
305 part_grid_.ReTypeBlobs(&image_bblobs_);
306 TidyBlobs(input_block);
307 Reset();
308 // TODO(rays) need to properly handle 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();
312 }
313 big_parts_.clear();
314 delete stroke_width_;
315 stroke_width_ = nullptr;
316 // Compute the edge offsets whether or not there is a grey_pix. It is done
317 // here as the c_blobs haven't been touched by rotation or anything yet,
318 // so no denorm is required, yet the text has been separated from image, so
319 // no time is wasted running it on image blobs.
320 input_block->ComputeEdgeOffsets(thresholds_pix, grey_pix);
321
322 // A note about handling right-to-left scripts (Hebrew/Arabic):
323 // The columns must be reversed and come out in right-to-left instead of
324 // the normal left-to-right order. Because the left-to-right ordering
325 // is implicit in many data structures, it is simpler to fool the algorithms
326 // into thinking they are dealing with left-to-right text.
327 // To do this, we reflect the needed data in the y-axis and then reflect
328 // the blocks back after they have been created. This is a temporary
329 // arrangement that is confined to this function only, so the reflection
330 // is completely invisible in the output blocks.
331 // The only objects reflected are:
332 // The vertical separator lines that have already been found;
333 // The bounding boxes of all BLOBNBOXES on all lists on the input_block
334 // plus the image_bblobs. The outlines are not touched, since they are
335 // not looked at.
336 bool input_is_rtl = input_block->block->right_to_left();
337 if (input_is_rtl) {
338 // Reflect the vertical separator lines (member of TabFind).
340 // Reflect the blob boxes.
341 ReflectForRtl(input_block, &image_bblobs_);
342 part_grid_.ReflectInYAxis();
343 }
344
345 if (!PSM_SPARSE(pageseg_mode)) {
346 if (!PSM_COL_FIND_ENABLED(pageseg_mode)) {
347 // No tab stops needed. Just the grid that FindTabVectors makes.
348 DontFindTabVectors(&image_bblobs_, input_block, &deskew_, &reskew_);
349 } else {
350 SetBlockRuleEdges(input_block);
351 // Find the tab stops, estimate skew, and deskew the tabs, blobs and
352 // part_grid_.
353 FindTabVectors(&horizontal_lines_, &image_bblobs_, input_block, min_gutter_width_,
354 tabfind_aligned_gap_fraction_, &part_grid_, &deskew_, &reskew_);
355 // Add the deskew to the denorm_.
356 auto *new_denorm = new DENORM;
357 new_denorm->SetupNormalization(nullptr, &deskew_, denorm_, 0.0f, 0.0f, 1.0f, 1.0f, 0.0f,
358 0.0f);
359 denorm_ = new_denorm;
360 }
361 SetBlockRuleEdges(input_block);
362 part_grid_.SetTabStops(this);
363
364 // Make the column_sets_.
365 if (!MakeColumns(false)) {
366 tprintf("Empty page!!\n");
367 part_grid_.DeleteParts();
368 return 0; // This is an empty page.
369 }
370
371 // Refill the grid using rectangular spreading, and get the benefit
372 // of the completed tab vectors marking the rule edges of each blob.
373 Clear();
374#ifndef GRAPHICS_DISABLED
375 if (textord_tabfind_show_reject_blobs) {
376 ScrollView *rej_win = MakeWindow(500, 300, "Rejected blobs");
377 input_block->plot_graded_blobs(rej_win);
378 }
379#endif // !GRAPHICS_DISABLED
380 InsertBlobsToGrid(false, false, &image_bblobs_, this);
381 InsertBlobsToGrid(true, true, &input_block->blobs, this);
382
383 part_grid_.GridFindMargins(best_columns_);
384 // Split and merge the partitions by looking at local neighbours.
385 GridSplitPartitions();
386 // Resolve unknown partitions by adding to an existing partition, fixing
387 // the type, or declaring them noise.
388 part_grid_.GridFindMargins(best_columns_);
389 GridMergePartitions();
390 // Insert any unused noise blobs that are close enough to an appropriate
391 // partition.
392 InsertRemainingNoise(input_block);
393 // Add horizontal line separators as partitions.
394 GridInsertHLinePartitions();
395 GridInsertVLinePartitions();
396 // Recompute margins based on a local neighbourhood search.
397 part_grid_.GridFindMargins(best_columns_);
398 SetPartitionTypes();
399 }
400#ifndef GRAPHICS_DISABLED
401 if (textord_tabfind_show_initial_partitions) {
402 ScrollView *part_win = MakeWindow(100, 300, "InitialPartitions");
403 part_grid_.DisplayBoxes(part_win);
404 DisplayTabVectors(part_win);
405 }
406#endif
407 if (!PSM_SPARSE(pageseg_mode)) {
408#ifndef DISABLED_LEGACY_ENGINE
409 if (equation_detect_) {
410 equation_detect_->FindEquationParts(&part_grid_, best_columns_);
411 }
412#endif
413 if (textord_tabfind_find_tables) {
414 TableFinder table_finder;
415 table_finder.Init(gridsize(), bleft(), tright());
416 table_finder.set_resolution(resolution_);
417 table_finder.set_left_to_right_language(!input_block->block->right_to_left());
418 // Copy cleaned partitions from part_grid_ to clean_part_grid_ and
419 // insert dot-like noise into period_grid_
420 table_finder.InsertCleanPartitions(&part_grid_, input_block);
421 // Get Table Regions
422 table_finder.LocateTables(&part_grid_, best_columns_, WidthCB(), reskew_);
423 }
424 GridRemoveUnderlinePartitions();
425 part_grid_.DeleteUnknownParts(input_block);
426
427 // Build the partitions into chains that belong in the same block and
428 // refine into one-to-one links, then smooth the types within each chain.
429 part_grid_.FindPartitionPartners();
430 part_grid_.FindFigureCaptions();
431 part_grid_.RefinePartitionPartners(true);
432 SmoothPartnerRuns();
433
434#ifndef GRAPHICS_DISABLED
435 if (textord_tabfind_show_partitions) {
436 ScrollView *window = MakeWindow(400, 300, "Partitions");
437 if (window != nullptr) {
438 part_grid_.DisplayBoxes(window);
440 DisplayTabVectors(window);
441 }
442 if (window != nullptr && textord_tabfind_show_partitions > 1) {
443 delete window->AwaitEvent(SVET_DESTROY);
444 }
445 }
446 }
447#endif // !GRAPHICS_DISABLED
448 part_grid_.AssertNoDuplicates();
449 }
450 // Ownership of the ColPartitions moves from part_sets_ to part_grid_ here,
451 // and ownership of the BLOBNBOXes moves to the ColPartitions.
452 // (They were previously owned by the block or the image_bblobs list.)
453 ReleaseBlobsAndCleanupUnused(input_block);
454 // Ownership of the ColPartitions moves from part_grid_ to good_parts_ and
455 // noise_parts_ here. In text blocks, ownership of the BLOBNBOXes moves
456 // from the ColPartitions to the output TO_BLOCK. In non-text, the
457 // BLOBNBOXes stay with the ColPartitions and get deleted in the destructor.
458 if (PSM_SPARSE(pageseg_mode)) {
459 part_grid_.ExtractPartitionsAsBlocks(blocks, to_blocks);
460 } else {
461 TransformToBlocks(blocks, to_blocks);
462 }
464 tprintf("Found %d blocks, %d to_blocks\n", blocks->length(), to_blocks->length());
465 }
466
467#ifndef GRAPHICS_DISABLED
468 if (textord_tabfind_show_blocks) {
469 DisplayBlocks(blocks);
470 }
471#endif
472 RotateAndReskewBlocks(input_is_rtl, to_blocks);
473 int result = 0;
474#ifndef GRAPHICS_DISABLED
475 if (blocks_win_ != nullptr) {
476 bool waiting = false;
477 do {
478 waiting = false;
479 SVEvent *event = blocks_win_->AwaitEvent(SVET_ANY);
480 if (event->type == SVET_INPUT && event->parameter != nullptr) {
481 if (*event->parameter == 'd') {
482 result = -1;
483 } else {
484 blocks->clear();
485 }
486 } else if (event->type == SVET_DESTROY) {
487 blocks_win_ = nullptr;
488 } else {
489 waiting = true;
490 }
491 delete event;
492 } while (waiting);
493 }
494#endif // !GRAPHICS_DISABLED
495 return result;
496}
497
498// Get the rotation required to deskew, and its inverse rotation.
500 *reskew = reskew_;
501 *deskew = reskew_;
502 deskew->set_y(-deskew->y());
503}
504
505#ifndef DISABLED_LEGACY_ENGINE
507 equation_detect_ = detect;
508}
509#endif
510
512
513#ifndef GRAPHICS_DISABLED
514
515// Displays the blob and block bounding boxes in a window called Blocks.
516void ColumnFinder::DisplayBlocks(BLOCK_LIST *blocks) {
517 if (blocks_win_ == nullptr) {
518 blocks_win_ = MakeWindow(700, 300, "Blocks");
519 } else {
520 blocks_win_->Clear();
521 }
522 DisplayBoxes(blocks_win_);
523 BLOCK_IT block_it(blocks);
524 int serial = 1;
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++,
529 }
530 blocks_win_->Update();
531}
532
533// Displays the column edges at each grid y coordinate defined by
534// best_columns_.
535void ColumnFinder::DisplayColumnBounds(PartSetVector *sets) {
536 ScrollView *col_win = MakeWindow(50, 300, "Columns");
537 DisplayBoxes(col_win);
539 for (int i = 0; i < gridheight_; ++i) {
540 ColPartitionSet *columns = best_columns_[i];
541 if (columns != nullptr) {
542 columns->DisplayColumnEdges(i * gridsize_, (i + 1) * gridsize_, col_win);
543 }
544 }
545}
546
547#endif // !GRAPHICS_DISABLED
548
549// Sets up column_sets_ (the determined column layout at each horizontal
550// slice). Returns false if the page is empty.
551bool ColumnFinder::MakeColumns(bool single_column) {
552 // The part_sets_ are a temporary structure used during column creation,
553 // and is a vector of ColPartitionSets, representing ColPartitions found
554 // at horizontal slices through the page.
555 PartSetVector part_sets;
556 if (!single_column) {
557 if (!part_grid_.MakeColPartSets(&part_sets)) {
558 return false; // Empty page.
559 }
560 ASSERT_HOST(part_grid_.gridheight() == gridheight_);
561 // Try using only the good parts first.
562 bool good_only = true;
563 do {
564 for (int i = 0; i < gridheight_; ++i) {
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());
570 }
571 }
572 }
573 good_only = !good_only;
574 } while (column_sets_.empty() && !good_only);
576 PrintColumnCandidates("Column candidates");
577 }
578 // Improve the column candidates against themselves.
579 ImproveColumnCandidates(&column_sets_, &column_sets_);
581 PrintColumnCandidates("Improved columns");
582 }
583 // Improve the column candidates using the part_sets_.
584 ImproveColumnCandidates(&part_sets, &column_sets_);
585 }
586 ColPartitionSet *single_column_set = part_grid_.MakeSingleColumnSet(WidthCB());
587 if (single_column_set != nullptr) {
588 // Always add the single column set as a backup even if not in
589 // single column mode.
590 single_column_set->AddToColumnSetsIfUnique(&column_sets_, WidthCB());
591 }
593 PrintColumnCandidates("Final Columns");
594 }
595 bool has_columns = !column_sets_.empty();
596 if (has_columns) {
597 // Divide the page into sections of uniform column layout.
598 bool any_multi_column = AssignColumns(part_sets);
599#ifndef GRAPHICS_DISABLED
600 if (textord_tabfind_show_columns) {
601 DisplayColumnBounds(&part_sets);
602 }
603#endif
604 ComputeMeanColumnGap(any_multi_column);
605 }
606 for (auto line_set : part_sets) {
607 if (line_set != nullptr) {
608 line_set->RelinquishParts();
609 delete line_set;
610 }
611 }
612 return has_columns;
613}
614
615// Attempt to improve the column_candidates by expanding the columns
616// and adding new partitions from the partition sets in src_sets.
617// Src_sets may be equal to column_candidates, in which case it will
618// use them as a source to improve themselves.
619void ColumnFinder::ImproveColumnCandidates(PartSetVector *src_sets, PartSetVector *column_sets) {
620 // TODO: optimize.
621 PartSetVector temp_cols = *column_sets;
622 column_sets->clear();
623 if (src_sets == column_sets) {
624 src_sets = &temp_cols;
625 }
626 int set_size = temp_cols.size();
627 // Try using only the good parts first.
628 bool good_only = true;
629 do {
630 for (int i = 0; i < set_size; ++i) {
631 ColPartitionSet *column_candidate = temp_cols.at(i);
632 ASSERT_HOST(column_candidate != nullptr);
633 ColPartitionSet *improved = column_candidate->Copy(good_only);
634 if (improved != nullptr) {
635 improved->ImproveColumnCandidate(WidthCB(), src_sets);
636 improved->AddToColumnSetsIfUnique(column_sets, WidthCB());
637 }
638 }
639 good_only = !good_only;
640 } while (column_sets->empty() && !good_only);
641 if (column_sets->empty()) {
642 // TODO: optimize.
643 *column_sets = temp_cols;
644 temp_cols.clear();
645 } else {
646 for (auto data : temp_cols) {
647 delete data;
648 }
649 }
650}
651
652// Prints debug information on the column candidates.
653void ColumnFinder::PrintColumnCandidates(const char *title) {
654 int set_size = column_sets_.size();
655 tprintf("Found %d %s:\n", set_size, title);
656 if (textord_debug_tabfind >= 3) {
657 for (int i = 0; i < set_size; ++i) {
658 ColPartitionSet *column_set = column_sets_.at(i);
659 column_set->Print();
660 }
661 }
662}
663
664// Finds the optimal set of columns that cover the entire image with as
665// few changes in column partition as possible.
666// NOTE: this could be thought of as an optimization problem, but a simple
667// greedy algorithm is used instead. The algorithm repeatedly finds the modal
668// compatible column in an unassigned region and uses that with the extra
669// tweak of extending the modal region over small breaks in compatibility.
670// Where modal regions overlap, the boundary is chosen so as to minimize
671// the cost in terms of ColPartitions not fitting an approved column.
672// Returns true if any part of the page is multi-column.
673bool ColumnFinder::AssignColumns(const PartSetVector &part_sets) {
674 int set_count = part_sets.size();
675 ASSERT_HOST(set_count == gridheight());
676 // Allocate and init the best_columns_.
677 best_columns_ = new ColPartitionSet *[set_count];
678 for (int y = 0; y < set_count; ++y) {
679 best_columns_[y] = nullptr;
680 }
681 int column_count = column_sets_.size();
682 // column_set_costs[part_sets_ index][column_sets_ index] is
683 // < INT32_MAX if the partition set is compatible with the column set,
684 // in which case its value is the cost for that set used in deciding
685 // which competing set to assign.
686 // any_columns_possible[part_sets_ index] is true if any of
687 // possible_column_sets[part_sets_ index][*] is < INT32_MAX.
688 // assigned_costs[part_sets_ index] is set to the column_set_costs
689 // of the assigned column_sets_ index or INT32_MAX if none is set.
690 // On return the best_columns_ member is set.
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];
694 // Set possible column_sets to indicate whether each set is compatible
695 // with each column.
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;
708 } else {
709 column_set_costs[part_i][col_i] = INT32_MAX;
710 if (debug) {
711 tprintf("Set id %d did not match at y=%d, lineset =%p\n",
712 col_i, part_i, static_cast<void *>(line_set));
713 }
714 }
715 }
716 }
717 bool any_multi_column = false;
718 // Assign a column set to each vertical grid position.
719 // While there is an unassigned range, find its mode.
720 int start, end;
721 while (BiggestUnassignedRange(set_count, any_columns_possible, &start, &end)) {
722 if (textord_debug_tabfind >= 2) {
723 tprintf("Biggest unassigned range = %d- %d\n", start, end);
724 }
725 // Find the modal column_set_id in the range.
726 int column_set_id = RangeModalColumnSet(column_set_costs, assigned_costs, start, end);
727 if (textord_debug_tabfind >= 2) {
728 tprintf("Range modal column id = %d\n", column_set_id);
729 column_sets_.at(column_set_id)->Print();
730 }
731 // Now find the longest run of the column_set_id in the range.
732 ShrinkRangeToLongestRun(column_set_costs, assigned_costs, any_columns_possible, column_set_id,
733 &start, &end);
734 if (textord_debug_tabfind >= 2) {
735 tprintf("Shrunk range = %d- %d\n", start, end);
736 }
737 // Extend the start and end past the longest run, while there are
738 // only small gaps in compatibility that can be overcome by larger
739 // regions of compatibility beyond.
740 ExtendRangePastSmallGaps(column_set_costs, assigned_costs, any_columns_possible, column_set_id,
741 -1, -1, &start);
742 --end;
743 ExtendRangePastSmallGaps(column_set_costs, assigned_costs, any_columns_possible, column_set_id,
744 1, set_count, &end);
745 ++end;
747 tprintf("Column id %d applies to range = %d - %d\n", column_set_id, start, end);
748 }
749 // Assign the column to the range, which now may overlap with other ranges.
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;
753 }
754 }
755 // If anything remains unassigned, the whole lot is unassigned, so
756 // arbitrarily assign id 0.
757 if (best_columns_[0] == nullptr) {
758 AssignColumnToRange(0, 0, gridheight_, column_set_costs, assigned_costs);
759 }
760 // Free memory.
761 for (int i = 0; i < set_count; ++i) {
762 delete[] column_set_costs[i];
763 }
764 delete[] assigned_costs;
765 delete[] any_columns_possible;
766 delete[] column_set_costs;
767 return any_multi_column;
768}
769
770// Finds the biggest range in part_sets_ that has no assigned column, but
771// column assignment is possible.
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;
777 int end = set_count;
778 for (int start = 0; start < gridheight_; start = end) {
779 // Find the first unassigned index in start.
780 while (start < set_count) {
781 if (best_columns_[start] == nullptr && any_columns_possible[start]) {
782 break;
783 }
784 ++start;
785 }
786 // Find the first past the end and count the good ones in between.
787 int range_size = 1; // Number of non-null, but unassigned line sets.
788 end = start + 1;
789 while (end < set_count) {
790 if (best_columns_[end] != nullptr) {
791 break;
792 }
793 if (any_columns_possible[end]) {
794 ++range_size;
795 }
796 ++end;
797 }
798 if (start < set_count && range_size > best_range_size) {
799 best_range_size = range_size;
800 *best_start = start;
801 *best_end = end;
802 }
803 }
804 return *best_start < *best_end;
805}
806
807// Finds the modal compatible column_set_ index within the given range.
808int ColumnFinder::RangeModalColumnSet(int **column_set_costs, const int *assigned_costs, int start,
809 int end) {
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);
816 }
817 }
818 }
819 ASSERT_HOST(column_stats.get_total() > 0);
820 return column_stats.mode();
821}
822
823// Given that there are many column_set_id compatible columns in the range,
824// shrinks the range to the longest contiguous run of compatibility, allowing
825// gaps where no columns are possible, but not where competing columns are
826// possible.
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) {
830 // orig_start and orig_end are the maximum range we will look at.
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;
836 int end = orig_end;
837 for (int start = orig_start; start < orig_end; start = end) {
838 // Find the first possible
839 while (start < orig_end) {
840 if (column_set_costs[start][column_set_id] < assigned_costs[start] ||
841 !any_columns_possible[start]) {
842 break;
843 }
844 ++start;
845 }
846 // Find the first past the end.
847 end = start + 1;
848 while (end < orig_end) {
849 if (column_set_costs[end][column_set_id] >= assigned_costs[start] &&
850 any_columns_possible[end]) {
851 break;
852 }
853 ++end;
854 }
855 if (start < orig_end && end - start > best_range_size) {
856 best_range_size = end - start;
857 *best_start = start;
858 *best_end = end;
859 }
860 }
861}
862
863// Moves start in the direction of step, up to, but not including end while
864// the only incompatible regions are no more than kMaxIncompatibleColumnCount
865// in size, and the compatible regions beyond are bigger.
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) {
869 if (textord_debug_tabfind > 2) {
870 tprintf("Starting expansion at %d, step=%d, limit=%d\n", *start, step, end);
871 }
872 if (*start == end) {
873 return; // Cannot be expanded.
874 }
875
876 int barrier_size = 0;
877 int good_size = 0;
878 do {
879 // Find the size of the incompatible barrier.
880 barrier_size = 0;
881 int i;
882 for (i = *start + step; i != end; i += step) {
883 if (column_set_costs[i][column_set_id] < assigned_costs[i]) {
884 break; // We are back on.
885 }
886 // Locations where none are possible don't count.
887 if (any_columns_possible[i]) {
888 ++barrier_size;
889 }
890 }
891 if (textord_debug_tabfind > 2) {
892 tprintf("At %d, Barrier size=%d\n", i, barrier_size);
893 }
894 if (barrier_size > kMaxIncompatibleColumnCount) {
895 return; // Barrier too big.
896 }
897 if (i == end) {
898 // We can't go any further, but the barrier was small, so go to the end.
899 *start = i - step;
900 return;
901 }
902 // Now find the size of the good region on the other side.
903 good_size = 1;
904 for (i += step; i != end; i += step) {
905 if (column_set_costs[i][column_set_id] < assigned_costs[i]) {
906 ++good_size;
907 } else if (any_columns_possible[i]) {
908 break;
909 }
910 }
911 if (textord_debug_tabfind > 2) {
912 tprintf("At %d, good size = %d\n", i, good_size);
913 }
914 // If we had enough good ones we can extend the start and keep looking.
915 if (good_size >= barrier_size) {
916 *start = i - step;
917 }
918 } while (good_size >= barrier_size);
919}
920
921// Assigns the given column_set_id to the given range.
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;
928 }
929}
930
931// Computes the mean_column_gap_.
932void ColumnFinder::ComputeMeanColumnGap(bool any_multi_column) {
933 int total_gap = 0;
934 int total_width = 0;
935 int gap_samples = 0;
936 int width_samples = 0;
937 for (int i = 0; i < gridheight_; ++i) {
938 ASSERT_HOST(best_columns_[i] != nullptr);
939 best_columns_[i]->AccumulateColumnWidthsAndGaps(&total_width, &width_samples, &total_gap,
940 &gap_samples);
941 }
942 mean_column_gap_ = any_multi_column && gap_samples > 0
943 ? total_gap / gap_samples
944 : width_samples > 0 ? total_width / width_samples : 0;
945}
946
949
950// Helper to delete all the deletable blobs on the list. Owned blobs are
951// extracted from the list, but not deleted, leaving them owned by the owner().
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) {
956 delete blob;
957 }
958 }
959}
960
961// Hoovers up all un-owned blobs and deletes them.
962// The rest get released from the block so the ColPartitions can pass
963// ownership to the output blocks.
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_);
970}
971
972// Splits partitions that cross columns where they have nothing in the gap.
973void ColumnFinder::GridSplitPartitions() {
974 // Iterate the ColPartitions in the grid.
975 GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT> gsearch(&part_grid_);
976 gsearch.StartFullSearch();
977 ColPartition *dont_repeat = nullptr;
978 ColPartition *part;
979 while ((part = gsearch.NextFullSearch()) != nullptr) {
980 if (part->blob_type() < BRT_UNKNOWN || part == dont_repeat) {
981 continue; // Only applies to text partitions.
982 }
983 ColPartitionSet *column_set = best_columns_[gsearch.GridY()];
984 int first_col = -1;
985 int last_col = -1;
986 // Find which columns the partition spans.
987 part->ColumnRange(resolution_, column_set, &first_col, &last_col);
988 if (first_col > 0) {
989 --first_col;
990 }
991 // Convert output column indices to physical column indices.
992 first_col /= 2;
993 last_col /= 2;
994 // We will only consider cases where a partition spans two columns,
995 // since a heading that spans more columns than that is most likely
996 // genuine.
997 if (last_col != first_col + 1) {
998 continue;
999 }
1000 // Set up a rectangle search x-bounded by the column gap and y by the part.
1001 int y = part->MidY();
1002 TBOX margin_box = part->bounding_box();
1003 bool debug = AlignedBlob::WithinTestRegion(2, margin_box.left(), margin_box.bottom());
1004 if (debug) {
1005 tprintf("Considering partition for GridSplit:");
1006 part->Print();
1007 }
1008 ColPartition *column = column_set->GetColumnByIndex(first_col);
1009 if (column == nullptr) {
1010 continue;
1011 }
1012 margin_box.set_left(column->RightAtY(y) + 2);
1013 column = column_set->GetColumnByIndex(last_col);
1014 if (column == nullptr) {
1015 continue;
1016 }
1017 margin_box.set_right(column->LeftAtY(y) - 2);
1018 // TODO(rays) Decide whether to keep rectangular filling or not in the
1019 // main grid and therefore whether we need a fancier search here.
1020 // Now run the rect search on the main blob grid.
1021 GridSearch<BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT> rectsearch(this);
1022 if (debug) {
1023 tprintf("Searching box (%d,%d)->(%d,%d)\n", margin_box.left(), margin_box.bottom(),
1024 margin_box.right(), margin_box.top());
1025 part->Print();
1026 }
1027 rectsearch.StartRectSearch(margin_box);
1028 BLOBNBOX *bbox;
1029 while ((bbox = rectsearch.NextRectSearch()) != nullptr) {
1030 if (bbox->bounding_box().overlap(margin_box)) {
1031 break;
1032 }
1033 }
1034 if (bbox == nullptr) {
1035 // There seems to be nothing in the hole, so split the partition.
1036 gsearch.RemoveBBox();
1037 int x_middle = (margin_box.left() + margin_box.right()) / 2;
1038 if (debug) {
1039 tprintf("Splitting part at %d:", x_middle);
1040 part->Print();
1041 }
1042 ColPartition *split_part = part->SplitAt(x_middle);
1043 if (split_part != nullptr) {
1044 if (debug) {
1045 tprintf("Split result:");
1046 part->Print();
1047 split_part->Print();
1048 }
1049 part_grid_.InsertBBox(true, true, split_part);
1050 } else {
1051 // Split had no effect
1052 if (debug) {
1053 tprintf("Split had no effect\n");
1054 }
1055 dont_repeat = part;
1056 }
1057 part_grid_.InsertBBox(true, true, part);
1058 gsearch.RepositionIterator();
1059 } else if (debug) {
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());
1063 }
1064 }
1065}
1066
1067// Merges partitions where there is vertical overlap, within a single column,
1068// and the horizontal gap is small enough.
1069void ColumnFinder::GridMergePartitions() {
1070 // Iterate the ColPartitions in the grid.
1071 GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT> gsearch(&part_grid_);
1072 gsearch.StartFullSearch();
1073 ColPartition *part;
1074 while ((part = gsearch.NextFullSearch()) != nullptr) {
1075 if (part->IsUnMergeableType()) {
1076 continue;
1077 }
1078 // Set up a rectangle search x-bounded by the column and y by the part.
1079 ColPartitionSet *columns = best_columns_[gsearch.GridY()];
1080 TBOX box = part->bounding_box();
1081 bool debug = AlignedBlob::WithinTestRegion(1, box.left(), box.bottom());
1082 if (debug) {
1083 tprintf("Considering part for merge at:");
1084 part->Print();
1085 }
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) {
1090 if (debug) {
1091 tprintf("In different columns\n");
1092 }
1093 continue;
1094 }
1095 box.set_left(left_column->LeftAtY(y));
1096 box.set_right(right_column->RightAtY(y));
1097 // Now run the rect search.
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;
1103
1104 while ((neighbour = rsearch.NextRectSearch()) != nullptr) {
1105 if (neighbour == part || neighbour->IsUnMergeableType()) {
1106 continue;
1107 }
1108 const TBOX &neighbour_box = neighbour->bounding_box();
1109 if (debug) {
1110 tprintf("Considering merge with neighbour at:");
1111 neighbour->Print();
1112 }
1113 if (neighbour_box.right() < box.left() || neighbour_box.left() > box.right()) {
1114 continue; // Not within the same column.
1115 }
1116 if (part->VSignificantCoreOverlap(*neighbour) && part->TypesMatch(*neighbour)) {
1117 // There is vertical overlap and the gross types match, but only
1118 // merge if the horizontal gap is small enough, as one of the
1119 // partitions may be a figure caption within a column.
1120 // If there is only one column, then the mean_column_gap_ is large
1121 // enough to allow almost any merge, by being the mean column width.
1122 const TBOX &part_box = part->bounding_box();
1123 // Don't merge if there is something else in the way. Use the margin
1124 // to decide, and check both to allow a bit of overlap.
1125 if (neighbour_box.left() > part->right_margin() &&
1126 part_box.right() < neighbour->left_margin()) {
1127 continue; // Neighbour is too far to the right.
1128 }
1129 if (neighbour_box.right() < part->left_margin() &&
1130 part_box.left() > neighbour->right_margin()) {
1131 continue; // Neighbour is too far to the left.
1132 }
1133 int h_gap = std::max(part_box.left(), neighbour_box.left()) -
1134 std::min(part_box.right(), neighbour_box.right());
1135 if (h_gap < mean_column_gap_ * kHorizontalGapMergeFraction ||
1136 part_box.width() < mean_column_gap_ || neighbour_box.width() < mean_column_gap_) {
1137 if (debug) {
1138 tprintf("Running grid-based merge between:\n");
1139 part->Print();
1140 neighbour->Print();
1141 }
1142 rsearch.RemoveBBox();
1143 if (!modified_box) {
1144 // We are going to modify part, so remove it and re-insert it after.
1145 gsearch.RemoveBBox();
1146 rsearch.RepositionIterator();
1147 modified_box = true;
1148 }
1149 part->Absorb(neighbour, WidthCB());
1150 } else if (debug) {
1151 tprintf("Neighbour failed hgap test\n");
1152 }
1153 } else if (debug) {
1154 tprintf("Neighbour failed overlap or typesmatch test\n");
1155 }
1156 }
1157 if (modified_box) {
1158 // We modified the box of part, so re-insert it into the grid.
1159 // This does no harm in the current cell, as it already exists there,
1160 // but it needs to exist in all the cells covered by its bounding box,
1161 // or it will never be found by a full search.
1162 // Because the box has changed, it has to be removed first, otherwise
1163 // add_sorted may fail to keep a single copy of the pointer.
1164 part_grid_.InsertBBox(true, true, part);
1165 gsearch.RepositionIterator();
1166 }
1167 }
1168}
1169
1170// Inserts remaining noise blobs into the most applicable partition if any.
1171// If there is no applicable partition, then the blobs are deleted.
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) {
1177 continue;
1178 }
1179 TBOX search_box(blob->bounding_box());
1180 bool debug = WithinTestRegion(2, search_box.left(), search_box.bottom());
1181 search_box.pad(gridsize(), gridsize());
1182 // Setup a rectangle search to find the best partition to merge with.
1183 ColPartitionGridSearch rsearch(&part_grid_);
1184 rsearch.SetUniqueMode(true);
1185 rsearch.StartRectSearch(search_box);
1186 ColPartition *part;
1187 ColPartition *best_part = nullptr;
1188 int best_distance = 0;
1189 while ((part = rsearch.NextRectSearch()) != nullptr) {
1190 if (part->IsUnMergeableType()) {
1191 continue;
1192 }
1193 int distance =
1194 projection_.DistanceOfBoxFromPartition(blob->bounding_box(), *part, denorm_, debug);
1195 if (best_part == nullptr || distance < best_distance) {
1196 best_part = part;
1197 best_distance = distance;
1198 }
1199 }
1200 if (best_part != nullptr &&
1201 best_distance < kMaxDistToPartSizeRatio * best_part->median_height()) {
1202 // Close enough to merge.
1203 if (debug) {
1204 tprintf("Adding noise blob with distance %d, thr=%g:box:", best_distance,
1205 kMaxDistToPartSizeRatio * best_part->median_height());
1206 blob->bounding_box().print();
1207 tprintf("To partition:");
1208 best_part->Print();
1209 }
1210 part_grid_.RemoveBBox(best_part);
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());
1216 } else {
1217 // Mark the blob for deletion.
1218 blob->set_region_type(BRT_NOISE);
1219 }
1220 }
1221 // Delete the marked blobs, clearing neighbour references.
1222 block->DeleteUnownedNoise();
1223}
1224
1225// Helper makes a box from a horizontal line.
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) {
1231 if (bottom > 0) {
1232 --bottom;
1233 } else {
1234 ++top;
1235 }
1236 }
1237 return TBOX(hline->startpt().x(), bottom, hline->endpt().x(), top);
1238}
1239
1240// Remove partitions that come from horizontal lines that look like
1241// underlines, but are not part of a table.
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()) {
1247 continue;
1248 }
1249 TBOX line_box = BoxFromHLine(hline);
1250 TBOX search_box = line_box;
1251 search_box.pad(0, line_box.height());
1252 ColPartitionGridSearch part_search(&part_grid_);
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) {
1260 if (covered->type() == PT_TABLE) {
1261 touched_table = true;
1262 break;
1263 } else if (covered->IsTextType()) {
1264 // TODO(rays) Add a list of underline sections to ColPartition.
1265 int text_bottom = covered->median_bottom();
1266 if (line_box.bottom() <= text_bottom && text_bottom <= search_box.top()) {
1267 touched_text = true;
1268 }
1269 } else if (covered->blob_type() == BRT_HLINE && line_box.contains(covered->bounding_box()) &&
1270 // not if same instance (identical to hline)
1271 !TBOX(covered->bounding_box()).contains(line_box)) {
1272 line_part = covered;
1273 }
1274 }
1275 if (line_part != nullptr && !touched_table && touched_text) {
1276 part_grid_.RemoveBBox(line_part);
1277 delete line_part;
1278 }
1279 }
1280}
1281
1282// Add horizontal line separators as partitions.
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());
1291 part->set_type(PT_HORZ_LINE);
1292 bool any_image = false;
1293 ColPartitionGridSearch part_search(&part_grid_);
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()) {
1299 any_image = true;
1300 break;
1301 }
1302 }
1303 if (!any_image) {
1304 part_grid_.InsertBBox(true, true, part);
1305 } else {
1306 delete part;
1307 }
1308 }
1309}
1310
1311// Add horizontal line separators as partitions.
1312void ColumnFinder::GridInsertVLinePartitions() {
1313 TabVector_IT vline_it(dead_vectors());
1314 for (vline_it.mark_cycle_pt(); !vline_it.cycled_list(); vline_it.forward()) {
1315 TabVector *vline = vline_it.data();
1316 if (!vline->IsSeparator()) {
1317 continue;
1318 }
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) {
1323 if (left > 0) {
1324 --left;
1325 } else {
1326 ++right;
1327 }
1328 }
1329 ColPartition *part = ColPartition::MakeLinePartition(
1330 BRT_VLINE, vertical_skew_, left, vline->startpt().y(), right, vline->endpt().y());
1331 part->set_type(PT_VERT_LINE);
1332 bool any_image = false;
1333 ColPartitionGridSearch part_search(&part_grid_);
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()) {
1339 any_image = true;
1340 break;
1341 }
1342 }
1343 if (!any_image) {
1344 part_grid_.InsertBBox(true, true, part);
1345 } else {
1346 delete part;
1347 }
1348 }
1349}
1350
1351// For every ColPartition in the grid, sets its type based on position
1352// in the columns.
1353void ColumnFinder::SetPartitionTypes() {
1354 GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT> gsearch(&part_grid_);
1355 gsearch.StartFullSearch();
1356 ColPartition *part;
1357 while ((part = gsearch.NextFullSearch()) != nullptr) {
1358 part->SetPartitionType(resolution_, best_columns_[gsearch.GridY()]);
1359 }
1360}
1361
1362// Only images remain with multiple types in a run of partners.
1363// Sets the type of all in the group to the maximum of the group.
1364void ColumnFinder::SmoothPartnerRuns() {
1365 // Iterate the ColPartitions in the grid.
1366 GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT> gsearch(&part_grid_);
1367 gsearch.StartFullSearch();
1368 ColPartition *part;
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());
1374 part->Print();
1375 tprintf("has singleton partner:(%d partners", partner->lower_partners()->length());
1376 partner->Print();
1377 tprintf("but its singleton partner is:");
1378 if (partner->SingletonPartner(false) == nullptr) {
1379 tprintf("NULL\n");
1380 } else {
1381 partner->SingletonPartner(false)->Print();
1382 }
1383 }
1384 ASSERT_HOST(partner->SingletonPartner(false) == part);
1385 } else if (part->SingletonPartner(false) != nullptr) {
1386 ColPartitionSet *column_set = best_columns_[gsearch.GridY()];
1387 int column_count = column_set->ColumnCount();
1388 part->SmoothPartnerRun(column_count * 2 + 1);
1389 }
1390 }
1391}
1392
1393// Helper functions for TransformToBlocks.
1394// Add the part to the temp list in the correct order.
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();
1400 if (part->type() == PT_NOISE || test_part->type() == PT_NOISE) {
1401 continue; // Noise stays in sequence.
1402 }
1403 if (test_part == part->SingletonPartner(false)) {
1404 break; // Insert before its lower partner.
1405 }
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) {
1410 break; // part is above test_part so insert it.
1411 }
1412 if (!part->HOverlaps(*test_part) && !part->WithinSameMargins(*test_part)) {
1413 continue; // Incompatibles stay in order
1414 }
1415 }
1416 if (it.cycled_list()) {
1417 it.add_to_end(part);
1418 } else {
1419 it.add_before_stay_put(part);
1420 }
1421}
1422
1423// Add everything from the temp list to the work_set assuming correct order.
1424void ColumnFinder::EmptyTempPartList(ColPartition_CLIST *temp_list, WorkingPartSet_LIST *work_set) {
1425 ColPartition_C_IT it(temp_list);
1426 while (!it.empty()) {
1427 it.extract()->AddToWorkingSet(bleft_, tright_, resolution_, &good_parts_, work_set);
1428 it.forward();
1429 }
1430}
1431
1432// Transform the grid of partitions to the output blocks.
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_);
1437 // The temp_part_list holds a list of parts at the same grid y coord
1438 // so they can be added in the correct order. This prevents thin objects
1439 // like horizontal lines going before the text lines above them.
1440 ColPartition_CLIST temp_part_list;
1441 // Iterate the ColPartitions in the grid. It starts at the top
1442 GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT> gsearch(&part_grid_);
1443 gsearch.StartFullSearch();
1444 int prev_grid_y = -1;
1445 ColPartition *part;
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;
1451 }
1452 if (best_columns_[grid_y] != column_set) {
1453 column_set = best_columns_[grid_y];
1454 // Every line should have a non-null best column.
1455 ASSERT_HOST(column_set != nullptr);
1456 column_set->ChangeWorkColumns(bleft_, tright_, resolution_, &good_parts_, &work_set);
1458 tprintf("Changed column groups at grid index %d, y=%d\n", gsearch.GridY(),
1459 gsearch.GridY() * gridsize());
1460 }
1461 }
1462 if (part->type() == PT_NOISE) {
1463 noise_it.add_to_end(part);
1464 } else {
1465 AddToTempPartList(part, &temp_part_list);
1466 }
1467 }
1468 EmptyTempPartList(&temp_part_list, &work_set);
1469 // Now finish all working sets and transfer ColPartitionSets to block_sets.
1470 WorkingPartSet_IT work_it(&work_set);
1471 while (!work_it.empty()) {
1472 WorkingPartSet *working_set = work_it.extract();
1473 working_set->ExtractCompletedBlocks(bleft_, tright_, resolution_, &good_parts_, blocks,
1474 to_blocks);
1475 delete working_set;
1476 work_it.forward();
1477 }
1478}
1479
1480// Helper reflects a list of blobs in the y-axis.
1481// Only reflects the BLOBNBOX bounding box. Not the blobs or outlines below.
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();
1486 }
1487}
1488
1489// Reflect the blob boxes (but not the outlines) in the y-axis so that
1490// the blocks get created in the correct RTL order. Reflects the blobs
1491// in the input_block and the bblobs list.
1492// The reflection is undone in RotateAndReskewBlocks by
1493// reflecting the blocks themselves, and then recomputing the blob bounding
1494// boxes.
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);
1501 // Update the denorm with the reflection.
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;
1505}
1506
1507// Helper fixes up blobs and cblobs to match the desired rotation,
1508// exploding multi-outline blobs back to single blobs and accumulating
1509// the bounding box widths and heights.
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()) {
1519 // This blob has multiple outlines from CJK repair.
1520 // Explode the blob back into individual outlines.
1521 for (; !ol_it.empty(); ol_it.forward()) {
1522 C_OUTLINE *outline = ol_it.extract();
1523 BLOBNBOX *new_blob = BLOBNBOX::RealBlob(outline);
1524 // This blob will be revisited later since we add_after_stay_put here.
1525 // This means it will get rotated and have its width/height added to
1526 // the stats below.
1527 it.add_after_stay_put(new_blob);
1528 }
1529 it.extract();
1530 delete blob;
1531 } else {
1532 if (blob_rotation.x() != 1.0f || blob_rotation.y() != 0.0f) {
1533 cblob->rotate(blob_rotation);
1534 }
1535 blob->compute_bounding_box();
1536 widths->add(blob->bounding_box().width(), 1);
1537 heights->add(blob->bounding_box().height(), 1);
1538 }
1539 }
1540}
1541
1542// Undo the deskew that was done in FindTabVectors, as recognition is done
1543// without correcting blobs or blob outlines for skew.
1544// Reskew the completed blocks to put them back to the original rotated coords
1545// that were created by CorrectOrientation.
1546// If the input_is_rtl, then reflect the blocks in the y-axis to undo the
1547// reflection that was done before FindTabVectors.
1548// Blocks that were identified as vertical text (relative to the rotated
1549// coordinates) are further rotated so the text lines are horizontal.
1550// blob polygonal outlines are rotated to match the position of the blocks
1551// that they are in, and their bounding boxes are recalculated to be accurate.
1552// Record appropriate inverse transformations and required
1553// classifier transformation in the blocks.
1554void ColumnFinder::RotateAndReskewBlocks(bool input_is_rtl, TO_BLOCK_LIST *blocks) {
1555 if (input_is_rtl) {
1556 // The skew is backwards because of the reflection.
1557 FCOORD tmp = deskew_;
1558 deskew_ = reskew_;
1559 reskew_ = tmp;
1560 }
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;
1566 // Blocks are created on the deskewed blob outlines in TransformToBlocks()
1567 // so we need to reskew them back to page coordinates.
1568 if (input_is_rtl) {
1569 block->reflect_polygon_in_y_axis();
1570 }
1571 block->rotate(reskew_);
1572 // Copy the right_to_left flag to the created block.
1573 block->set_right_to_left(input_is_rtl);
1574 // Save the skew angle in the block for baseline computations.
1575 block->set_skew(reskew_);
1576 block->pdblk.set_index(block_index++);
1577 FCOORD blob_rotation = ComputeBlockAndClassifyRotation(block);
1578 // Rotate all the blobs if needed and recompute the bounding boxes.
1579 // Compute the block median blob width and height as we go.
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);
1587 }
1588 block->set_median_size(static_cast<int>(widths.median() + 0.5),
1589 static_cast<int>(heights.median() + 0.5));
1590 if (textord_debug_tabfind >= 2) {
1591 tprintf("Block median size = (%d, %d)\n", block->median_size().x(), block->median_size().y());
1592 }
1593 }
1594}
1595
1596// Computes the rotations for the block (to make textlines horizontal) and
1597// for the blobs (for classification) and sets the appropriate members
1598// of the given block.
1599// Returns the rotation that needs to be applied to the blobs to make
1600// them sit in the rotated block.
1601FCOORD ColumnFinder::ComputeBlockAndClassifyRotation(BLOCK *block) {
1602 // The text_rotation_ tells us the gross page text rotation that needs
1603 // to be applied for classification
1604 // TODO(rays) find block-level classify rotation by orientation detection.
1605 // In the mean time, assume that "up" for text printed in the minority
1606 // direction (PT_VERTICAL_TEXT) is perpendicular to the line of reading.
1607 // Accomplish this by zero-ing out the text rotation. This covers the
1608 // common cases of image credits in documents written in Latin scripts
1609 // and page headings for predominantly vertically written CJK books.
1610 FCOORD classify_rotation(text_rotation_);
1611 FCOORD block_rotation(1.0f, 0.0f);
1612 if (block->pdblk.poly_block()->isA() == PT_VERTICAL_TEXT) {
1613 // Vertical text needs to be 90 degrees rotated relative to the rest.
1614 // If the rest has a 90 degree rotation already, use the inverse, making
1615 // the vertical text the original way up. Otherwise use 90 degrees
1616 // clockwise.
1617 if (rerotate_.x() == 0.0f) {
1618 block_rotation = rerotate_;
1619 } else {
1620 block_rotation = FCOORD(0.0f, -1.0f);
1621 }
1622 block->rotate(block_rotation);
1623 classify_rotation = FCOORD(1.0f, 0.0f);
1624 }
1625 block_rotation.rotate(rotation_);
1626 // block_rotation is now what we have done to the blocks. Now do the same
1627 // thing to the blobs, but save the inverse rotation in the block, as that
1628 // is what we need to DENORM back to the image coordinates.
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();
1638 }
1639 return blob_rotation;
1640}
1641
1642} // namespace tesseract.
#define BOOL_VAR(name, val, comment)
Definition: params.h:359
#define INT_VAR(name, val, comment)
Definition: params.h:356
#define ASSERT_HOST(x)
Definition: errcode.h:54
UnicodeText::const_iterator::difference_type distance(const UnicodeText::const_iterator &first, const UnicodeText::const_iterator &last)
Definition: unicodetext.cc:44
@ TBOX
@ BRT_HLINE
Definition: blobbox.h:76
@ BRT_NOISE
Definition: blobbox.h:75
@ BRT_VLINE
Definition: blobbox.h:77
@ BRT_UNKNOWN
Definition: blobbox.h:80
void tprintf(const char *format,...)
Definition: tprintf.cpp:41
const int kMaxIncompatibleColumnCount
Definition: colfind.cpp:48
@ SVET_DESTROY
Definition: scrollview.h:53
@ SVET_INPUT
Definition: scrollview.h:57
bool PSM_COL_FIND_ENABLED(int pageseg_mode)
Definition: publictypes.h:192
bool textord_debug_printable
Definition: alignedblob.cpp:43
GridSearch< ColPartition, ColPartition_CLIST, ColPartition_C_IT > ColPartitionGridSearch
Definition: colpartition.h:919
bool PSM_SPARSE(int pageseg_mode)
Definition: publictypes.h:195
int textord_debug_tabfind
Definition: alignedblob.cpp:29
std::vector< ColPartitionSet * > PartSetVector
const double kHorizontalGapMergeFraction
Definition: colfind.cpp:51
const double kMaxDistToPartSizeRatio
Definition: colfind.cpp:56
@ PT_VERTICAL_TEXT
Definition: publictypes.h:59
@ PT_HORZ_LINE
Definition: publictypes.h:64
@ PT_VERT_LINE
Definition: publictypes.h:65
const double kMinGutterWidthGrid
Definition: colfind.cpp:53
static BLOBNBOX * RealBlob(C_OUTLINE *outline)
Definition: blobbox.h:169
C_BLOB * cblob() const
Definition: blobbox.h:277
void ReSetAndReFilterBlobs()
Definition: blobbox.cpp:998
BLOBNBOX_LIST blobs
Definition: blobbox.h:776
BLOBNBOX_LIST small_blobs
Definition: blobbox.h:779
void plot_graded_blobs(ScrollView *to_win)
Definition: blobbox.cpp:1058
BLOBNBOX_LIST large_blobs
Definition: blobbox.h:780
BLOBNBOX_LIST noise_blobs
Definition: blobbox.h:778
void ComputeEdgeOffsets(Image thresholds, Image grey)
Definition: blobbox.cpp:1042
void destroy()
Definition: image.cpp:32
const DENORM * predecessor() const
Definition: normalis.h:255
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)
Definition: normalis.cpp:97
bool right_to_left() const
Definition: ocrblock.h:74
integer coordinate
Definition: points.h:36
TDimension y() const
access_function
Definition: points.h:62
void set_y(float yin)
rewrite function
Definition: points.h:217
void rotate(const FCOORD vec)
Definition: points.h:712
float y() const
Definition: points.h:209
float x() const
Definition: points.h:206
static bool WithinTestRegion(int detail_level, int x, int y)
int gridsize() const
Definition: bbgrid.h:63
int gridheight() const
Definition: bbgrid.h:69
const ICOORD & bleft() const
Definition: bbgrid.h:72
ICOORD tright_
Definition: bbgrid.h:91
const ICOORD & tright() const
Definition: bbgrid.h:75
void DisplayBoxes(ScrollView *window)
Definition: bbgrid.h:649
void Clear()
Definition: bbgrid.h:497
void AssertNoDuplicates()
Definition: bbgrid.h:674
void Init(int gridsize, const ICOORD &bleft, const ICOORD &tright)
Definition: bbgrid.h:488
void InsertBBox(bool h_spread, bool v_spread, BBC *bbox)
Definition: bbgrid.h:529
ScrollView * MakeWindow(int x, int y, const char *window_name)
Definition: bbgrid.h:633
void RemoveBBox(BBC *bbox)
Definition: bbgrid.h:575
Image ComputeNonTextMask(bool debug, Image photo_map, TO_BLOCK *blob_block)
void GetDeskewVectors(FCOORD *deskew, FCOORD *reskew)
Definition: colfind.cpp:499
bool IsVerticallyAlignedText(double find_vertical_text_ratio, TO_BLOCK *block, BLOBNBOX_CLIST *osd_blobs)
Definition: colfind.cpp:186
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)
Definition: colfind.cpp:78
void SetEquationDetect(EquationDetectBase *detect)
Definition: colfind.cpp:506
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)
Definition: colfind.cpp:286
void SetupAndFilterNoise(PageSegMode pageseg_mode, Image photo_mask_pix, TO_BLOCK *input_block)
Definition: colfind.cpp:151
void CorrectOrientation(TO_BLOCK *block, bool vertical_text_lines, int recognition_rotation)
Definition: colfind.cpp:202
~ColumnFinder() override
Definition: colfind.cpp:102
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 DeleteUnknownParts(TO_BLOCK *block)
ColPartitionSet * MakeSingleColumnSet(WidthCallback cb)
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)
Definition: imagefind.cpp:1145
static void TransferImagePartsToImageMask(const FCOORD &rerotation, ColPartitionGrid *part_grid, Image image_mask)
Definition: imagefind.cpp:1092
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()
Definition: tabfind.h:170
static void RotateBlobList(const FCOORD &rotation, BLOBNBOX_LIST *blobs)
Definition: tabfind.cpp:1278
void InsertBlobsToGrid(bool h_spread, bool v_spread, BLOBNBOX_LIST *blobs, BBGrid< BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT > *grid)
Definition: tabfind.cpp:89
void ResetForVerticalText(const FCOORD &rotate, const FCOORD &rerotate, TabVector_LIST *horizontal_lines, int *min_gutter_width)
Definition: tabfind.cpp:1323
void DontFindTabVectors(BLOBNBOX_LIST *image_blobs, TO_BLOCK *block, FCOORD *deskew, FCOORD *reskew)
Definition: tabfind.cpp:449
int resolution_
Of source image in pixels per inch.
Definition: tabfind.h:346
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)
Definition: tabfind.cpp:422
void TidyBlobs(TO_BLOCK *block)
Definition: tabfind.cpp:462
WidthCallback WidthCB()
Definition: tabfind.h:152
void SetBlockRuleEdges(TO_BLOCK *block)
Definition: tabfind.cpp:128
ICOORD vertical_skew_
Estimate of true vertical in this image.
Definition: tabfind.h:345
ScrollView * FindInitialTabVectors(BLOBNBOX_LIST *image_blobs, int min_gutter_width, double tabfind_aligned_gap_fraction, TO_BLOCK *block)
Definition: tabfind.cpp:512
ScrollView * DisplayTabVectors(ScrollView *tab_win)
Definition: tabfind.cpp:495
void Init(int grid_size, const ICOORD &bottom_left, const ICOORD &top_right)
Definition: tablefind.cpp:181
void set_resolution(int resolution)
Definition: tablefind.h:128
void InsertCleanPartitions(ColPartitionGrid *grid, TO_BLOCK *block)
Definition: tablefind.cpp:193
void set_left_to_right_language(bool order)
Definition: tablefind.cpp:177
void LocateTables(ColPartitionGrid *grid, ColPartitionSet **columns, WidthCallback width_cb, const FCOORD &reskew)
Definition: tablefind.cpp:261
int DistanceOfBoxFromPartition(const TBOX &box, const ColPartition &part, const DENORM *denorm, bool debug) const
static void Update()
Definition: scrollview.cpp:713
SVEvent * AwaitEvent(SVEventType type)
Definition: scrollview.cpp:445