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