tesseract  5.0.0-alpha-619-ge9db
colfind.cpp
Go to the documentation of this file.
1 // 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 
42 namespace 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.
49 const double kHorizontalGapMergeFraction = 0.5;
50 // Minimum gutter width as a fraction of gridsize
51 const double kMinGutterWidthGrid = 0.5;
52 // Max multiple of a partition's median size as a distance threshold for
53 // adding noise blobs.
54 const double kMaxDistToPartSizeRatio = 1.5;
55 
56 static BOOL_VAR(textord_tabfind_show_initial_partitions,
57  false, "Show partition bounds");
58 static BOOL_VAR(textord_tabfind_show_reject_blobs,
59  false, "Show blobs rejected as noise");
60 static INT_VAR(textord_tabfind_show_partitions, 0,
61  "Show partition bounds, waiting if >1");
62 static BOOL_VAR(textord_tabfind_show_columns, false, "Show column bounds");
63 static BOOL_VAR(textord_tabfind_show_blocks, false, "Show final block bounds");
64 static BOOL_VAR(textord_tabfind_find_tables, true, "run table detection");
65 
66 ScrollView* 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.
179 bool 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  }
248  if (textord_debug_tabfind) {
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.
285 int 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).
343  ReflectInYAxis();
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);
464  if (textord_debug_tabfind) {
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.
509 void 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_.
533 void 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.
548 bool 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.
611 void 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.
639 void 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.
659 bool 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.
762 bool 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.
796 int 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.
815 void 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.
854 void 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.
904 void 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_.
915 void 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().
937 static 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.
950 void 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.
959 void 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.
1051 void 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.
1153 void 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.
1197  blob->set_region_type(BRT_NOISE);
1198  }
1199  }
1200  // Delete the marked blobs, clearing neighbour references.
1201  block->DeleteUnownedNoise();
1202 }
1203 
1204 // Helper makes a box from a horizontal line.
1205 static 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.
1220 void 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.
1258 void 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.
1286 void 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.
1325 void 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.
1337 void 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.
1370 void 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.
1396 void 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.
1407 void 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.
1458 static 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.
1471 void 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.
1487 static 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.
1534 void 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) {
1550  block->reflect_polygon_in_y_axis();
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.
1584 FCOORD 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);
1615  if (textord_debug_tabfind) {
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.
TO_BLOCK::ComputeEdgeOffsets
void ComputeEdgeOffsets(Pix *thresholds, Pix *grey)
Definition: blobbox.cpp:1038
TBOX
Definition: cleanapi_test.cc:19
tesseract::ColumnFinder::CorrectOrientation
void CorrectOrientation(TO_BLOCK *block, bool vertical_text_lines, int recognition_rotation)
Definition: colfind.cpp:197
tesseract::TableFinder
Definition: tablefind.h:130
GenericVector::delete_data_pointers
void delete_data_pointers()
Definition: genericvector.h:872
TO_BLOCK::small_blobs
BLOBNBOX_LIST small_blobs
Definition: blobbox.h:774
ScrollView
Definition: scrollview.h:97
tesseract::ColumnFinder::SetEquationDetect
void SetEquationDetect(EquationDetectBase *detect)
Definition: colfind.cpp:502
TO_BLOCK::plot_graded_blobs
void plot_graded_blobs(ScrollView *to_win)
Definition: blobbox.cpp:1054
INT_VAR
#define INT_VAR(name, val, comment)
Definition: params.h:300
normalis.h
SVET_DESTROY
Definition: scrollview.h:45
tesseract::ColPartitionGrid::MakeSingleColumnSet
ColPartitionSet * MakeSingleColumnSet(WidthCallback cb)
Definition: colpartitiongrid.cpp:815
tesseract::TableFinder::set_resolution
void set_resolution(int resolution)
Definition: tablefind.h:137
tesseract::ColPartitionSet::AccumulateColumnWidthsAndGaps
void AccumulateColumnWidthsAndGaps(int *total_width, int *width_samples, int *total_gap, int *gap_samples)
Definition: colpartitionset.cpp:571
tesseract::TabFind::Reset
void Reset()
Definition: tabfind.cpp:1345
tesseract::ColPartitionGrid::GridFindMargins
void GridFindMargins(ColPartitionSet **best_columns)
Definition: colpartitiongrid.cpp:960
tesseract::BBGrid::AssertNoDuplicates
void AssertNoDuplicates()
Definition: bbgrid.h:638
tesseract::ColPartitionSet::DisplayColumnEdges
void DisplayColumnEdges(int y_bottom, int y_top, ScrollView *win)
Definition: colpartitionset.cpp:385
C_BLOB::out_list
C_OUTLINE_LIST * out_list()
Definition: stepblob.h:69
tesseract::TabFind::FindTabVectors
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
PDBLK::bounding_box
void bounding_box(ICOORD &bottom_left, ICOORD &top_right) const
get box
Definition: pdblock.h:58
tesseract::BBGrid::InsertBBox
void InsertBBox(bool h_spread, bool v_spread, BBC *bbox)
Definition: bbgrid.h:486
tesseract::ColPartitionGrid::DeleteUnknownParts
void DeleteUnknownParts(TO_BLOCK *block)
Definition: colpartitiongrid.cpp:1017
tesseract::GridBase::gridheight_
int gridheight_
Definition: bbgrid.h:88
SVET_INPUT
Definition: scrollview.h:49
tesseract::BBGrid< BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT >::MakeWindow
ScrollView * MakeWindow(int x, int y, const char *window_name)
Definition: bbgrid.h:589
BRT_NOISE
Definition: blobbox.h:72
tesseract::kMaxDistToPartSizeRatio
const double kMaxDistToPartSizeRatio
Definition: colfind.cpp:54
TO_BLOCK::noise_blobs
BLOBNBOX_LIST noise_blobs
Definition: blobbox.h:773
tesseract::PSM_COL_FIND_ENABLED
bool PSM_COL_FIND_ENABLED(int pageseg_mode)
Definition: publictypes.h:194
tesseract::kMinGutterWidthGrid
const double kMinGutterWidthGrid
Definition: colfind.cpp:51
tesseract::StrokeWidth::GradeBlobsIntoPartitions
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)
Definition: strokewidth.cpp:343
ASSERT_HOST
#define ASSERT_HOST(x)
Definition: errcode.h:87
linefind.h
blobbox.h
tesseract::GridBase::tright_
ICOORD tright_
Definition: bbgrid.h:91
TBOX::overlap
bool overlap(const TBOX &box) const
Definition: rect.h:350
params.h
BRT_UNKNOWN
Definition: blobbox.h:77
FCOORD::y
float y() const
Definition: points.h:209
ICOORD
integer coordinate
Definition: points.h:30
tesseract::ColPartitionGrid::DeleteParts
void DeleteParts()
Definition: colpartitiongrid.cpp:1002
tesseract::ColPartitionGrid::FindFigureCaptions
void FindFigureCaptions()
Definition: colpartitiongrid.cpp:1054
BLOBNBOX::set_flow
void set_flow(BlobTextFlowType value)
Definition: blobbox.h:297
PDBLK::set_index
void set_index(int value)
Definition: pdblock.h:67
BLOBNBOX::compute_bounding_box
void compute_bounding_box()
Definition: blobbox.h:239
tesseract::BBGrid::RemoveBBox
void RemoveBBox(BBC *bbox)
Definition: bbgrid.h:533
TBOX::print
void print() const
Definition: rect.h:277
BLOCK::set_right_to_left
void set_right_to_left(bool value)
Definition: ocrblock.h:81
TO_BLOCK::DeleteUnownedNoise
void DeleteUnownedNoise()
Definition: blobbox.cpp:1020
FCOORD::x
float x() const
Definition: points.h:206
TBOX::top
int16_t top() const
Definition: rect.h:57
TBOX::contains
bool contains(const FCOORD pt) const
Definition: rect.h:330
tesseract::BBGrid::Clear
void Clear()
Definition: bbgrid.h:455
PT_NOISE
Definition: capi.h:122
ScrollView::Clear
void Clear()
Definition: scrollview.cpp:588
TO_BLOCK::blobs
BLOBNBOX_LIST blobs
Definition: blobbox.h:771
tesseract::StrokeWidth
Definition: strokewidth.h:57
TO_BLOCK
Definition: blobbox.h:691
PDBLK::index
int index() const
Definition: pdblock.h:66
colpartitionset.h
BLOBNBOX::RealBlob
static BLOBNBOX * RealBlob(C_OUTLINE *outline)
Definition: blobbox.h:157
ScrollView::Pen
void Pen(Color color)
Definition: scrollview.cpp:717
colpartition.h
PT_TABLE
Definition: capi.h:114
equationdetectbase.h
tesseract::ColPartitionGridSearch
GridSearch< ColPartition, ColPartition_CLIST, ColPartition_C_IT > ColPartitionGridSearch
Definition: colpartition.h:935
tesseract::ColumnFinder::GetDeskewVectors
void GetDeskewVectors(FCOORD *deskew, FCOORD *reskew)
Definition: colfind.cpp:496
ICOORD::x
int16_t x() const
access function
Definition: points.h:51
FCOORD
Definition: points.h:187
DENORM::predecessor
const DENORM * predecessor() const
Definition: normalis.h:262
FCOORD::set_y
void set_y(float yin)
rewrite function
Definition: points.h:217
tesseract::TabFind::InsertBlobsToGrid
void InsertBlobsToGrid(bool h_spread, bool v_spread, BLOBNBOX_LIST *blobs, BBGrid< BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT > *grid)
Definition: tabfind.cpp:91
BLOBNBOX
Definition: blobbox.h:142
ScrollView::BLUE
Definition: scrollview.h:108
BRT_HLINE
Definition: blobbox.h:73
tesseract::ColPartitionSet::AddToColumnSetsIfUnique
void AddToColumnSetsIfUnique(PartSetVector *column_sets, WidthCallback cb)
Definition: colpartitionset.cpp:174
PT_VERTICAL_TEXT
Definition: capi.h:115
C_BLOB
Definition: stepblob.h:36
tesseract::ColPartition
Definition: colpartition.h:67
C_OUTLINE
Definition: coutln.h:71
tesseract::PartSetVector
GenericVector< ColPartitionSet * > PartSetVector
Definition: colpartitionset.h:33
tesseract::GridBase::tright
const ICOORD & tright() const
Definition: bbgrid.h:75
BLOCK::right_to_left
bool right_to_left() const
Definition: ocrblock.h:78
TBOX::height
int16_t height() const
Definition: rect.h:107
BLOCK::set_median_size
void set_median_size(int x, int y)
Definition: ocrblock.h:154
GenericVector::move
void move(GenericVector< T > *from)
Definition: genericvector.h:1087
BLOCK::set_re_rotation
void set_re_rotation(const FCOORD &rotation)
Definition: ocrblock.h:136
tesseract::TabFind::FindInitialTabVectors
ScrollView * FindInitialTabVectors(BLOBNBOX_LIST *image_blobs, int min_gutter_width, double tabfind_aligned_gap_fraction, TO_BLOCK *block)
Definition: tabfind.cpp:514
strokewidth.h
tesseract::TabFind::ReflectInYAxis
void ReflectInYAxis()
Definition: tabfind.cpp:1356
TBOX::set_right
void set_right(int x)
Definition: rect.h:81
tesseract::PSM_SPARSE
bool PSM_SPARSE(int pageseg_mode)
Definition: publictypes.h:197
BLOCK
Definition: ocrblock.h:28
TO_BLOCK::ReSetAndReFilterBlobs
void ReSetAndReFilterBlobs()
Definition: blobbox.cpp:994
colfind.h
BLOCK::pdblk
PDBLK pdblk
Page Description Block.
Definition: ocrblock.h:189
tesseract::ColPartitionGrid::RefinePartitionPartners
void RefinePartitionPartners(bool get_desperate)
Definition: colpartitiongrid.cpp:1287
DENORM::SetupNormalization
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:95
tesseract::TabFind::resolution_
int resolution_
Of source image in pixels per inch.
Definition: tabfind.h:367
TO_BLOCK::large_blobs
BLOBNBOX_LIST large_blobs
Definition: blobbox.h:775
textord_debug_printable
bool textord_debug_printable
Definition: alignedblob.cpp:33
tesseract::ColumnFinder::FindBlocks
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
BLOCK::reflect_polygon_in_y_axis
void reflect_polygon_in_y_axis()
Definition: ocrblock.cpp:100
PDBLK::poly_block
POLY_BLOCK * poly_block() const
Definition: pdblock.h:54
TO_BLOCK::block
BLOCK * block
Definition: blobbox.h:776
tesstrain_utils.int
int
Definition: tesstrain_utils.py:154
tesseract::AlignedBlob::WithinTestRegion
static bool WithinTestRegion(int detail_level, int x, int y)
Definition: alignedblob.cpp:150
tesseract::ColumnFinder::SetupAndFilterNoise
void SetupAndFilterNoise(PageSegMode pageseg_mode, Pix *photo_mask_pix, TO_BLOCK *input_block)
Definition: colfind.cpp:142
tesseract::StrokeWidth::FindTextlineDirectionAndFixBrokenCJK
void FindTextlineDirectionAndFixBrokenCJK(PageSegMode pageseg_mode, bool cjk_merge, TO_BLOCK *input_block)
Definition: strokewidth.cpp:156
GenericVector::empty
bool empty() const
Definition: genericvector.h:86
TBOX::width
int16_t width() const
Definition: rect.h:114
tesseract::TabFind::DontFindTabVectors
void DontFindTabVectors(BLOBNBOX_LIST *image_blobs, TO_BLOCK *block, FCOORD *deskew, FCOORD *reskew)
Definition: tabfind.cpp:452
BOOL_VAR
#define BOOL_VAR(name, val, comment)
Definition: params.h:303
TBOX::bottom
int16_t bottom() const
Definition: rect.h:64
BLOCK::set_classify_rotation
void set_classify_rotation(const FCOORD &rotation)
Definition: ocrblock.h:142
BLOBNBOX::set_owner
void set_owner(tesseract::ColPartition *new_owner)
Definition: blobbox.h:354
tesseract::GridBase::bleft_
ICOORD bleft_
Definition: bbgrid.h:90
tesseract::ImageFind::FindImagePartitions
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
tesseract::StrokeWidth::CorrectForRotation
void CorrectForRotation(const FCOORD &rerotation, ColPartitionGrid *part_grid)
Definition: strokewidth.cpp:250
tesseract::kMaxIncompatibleColumnCount
const int kMaxIncompatibleColumnCount
Definition: colfind.cpp:46
tesseract
Definition: baseapi.h:65
BLOBNBOX::set_region_type
void set_region_type(BlobRegionType new_type)
Definition: blobbox.h:285
STATS::median
double median() const
Definition: statistc.cpp:218
distance
UnicodeText::const_iterator::difference_type distance(const UnicodeText::const_iterator &first, const UnicodeText::const_iterator &last)
Definition: unicodetext.cc:44
tesseract::ColPartitionGrid::ReflectInYAxis
void ReflectInYAxis()
Definition: colpartitiongrid.cpp:640
PT_VERT_LINE
Definition: capi.h:121
FCOORD::rotate
void rotate(const FCOORD vec)
Definition: points.h:736
tesseract::DebugPixa
Definition: debugpixa.h:10
tesseract::TableFinder::InsertCleanPartitions
void InsertCleanPartitions(ColPartitionGrid *grid, TO_BLOCK *block)
Definition: tablefind.cpp:193
STATS
Definition: statistc.h:30
BLOBNBOX::bounding_box
const TBOX & bounding_box() const
Definition: blobbox.h:229
tesseract::TabFind::vertical_skew_
ICOORD vertical_skew_
Estimate of true vertical in this image.
Definition: tabfind.h:366
tesseract::StrokeWidth::TestVerticalTextDirection
bool TestVerticalTextDirection(double find_vertical_text_ratio, TO_BLOCK *block, BLOBNBOX_CLIST *osd_blobs)
Definition: strokewidth.cpp:208
BLOCK::median_size
const ICOORD & median_size() const
Definition: ocrblock.h:151
tesseract::ColPartitionSet::ColumnCount
int ColumnCount() const
Definition: colpartitionset.h:54
tesseract::kHorizontalGapMergeFraction
const double kHorizontalGapMergeFraction
Definition: colfind.cpp:49
tesseract::EquationDetectBase
Definition: equationdetectbase.h:32
tesseract::TableFinder::set_left_to_right_language
void set_left_to_right_language(bool order)
Definition: tablefind.cpp:177
BLOCK::rotate
void rotate(const FCOORD &rotation)
Definition: ocrblock.cpp:77
SVET_ANY
Definition: scrollview.h:55
tesseract::TabFind::SetBlockRuleEdges
void SetBlockRuleEdges(TO_BLOCK *block)
Definition: tabfind.cpp:133
ScrollView::AwaitEvent
SVEvent * AwaitEvent(SVEventType type)
Definition: scrollview.cpp:443
TO_BLOCK::get_rows
TO_ROW_LIST * get_rows()
Definition: blobbox.h:703
tesseract::GridBase::gridsize
int gridsize() const
Definition: bbgrid.h:63
tesseract::ImageFind::TransferImagePartsToImageMask
static void TransferImagePartsToImageMask(const FCOORD &rerotation, ColPartitionGrid *part_grid, Pix *image_mask)
Definition: imagefind.cpp:1245
tesseract::ColPartition::set_type
void set_type(PolyBlockType t)
Definition: colpartition.h:184
tesseract::TabFind::DisplayTabVectors
ScrollView * DisplayTabVectors(ScrollView *tab_win)
Definition: tabfind.cpp:497
tesseract::BBGrid::DisplayBoxes
void DisplayBoxes(ScrollView *window)
Definition: bbgrid.h:613
tesseract::TextlineProjection::DistanceOfBoxFromPartition
int DistanceOfBoxFromPartition(const TBOX &box, const ColPartition &part, const DENORM *denorm, bool debug) const
Definition: textlineprojection.cpp:157
TBOX::pad
void pad(int xpad, int ypad)
Definition: rect.h:130
tesseract::ColPartitionGrid::FindPartitionPartners
void FindPartitionPartners()
Definition: colpartitiongrid.cpp:1179
tesseract::GridBase::gridsize_
int gridsize_
Definition: bbgrid.h:86
tesseract::BBGrid::Init
void Init(int gridsize, const ICOORD &bleft, const ICOORD &tright)
Definition: bbgrid.h:445
tesseract::TabFind::WidthCB
WidthCallback WidthCB()
Definition: tabfind.h:157
tesseract::TableFinder::Init
void Init(int grid_size, const ICOORD &bottom_left, const ICOORD &top_right)
Definition: tablefind.cpp:181
tesseract::TabFind::ResetForVerticalText
void ResetForVerticalText(const FCOORD &rotate, const FCOORD &rerotate, TabVector_LIST *horizontal_lines, int *min_gutter_width)
Definition: tabfind.cpp:1300
tesseract::ColumnFinder::ColumnFinder
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
C_BLOB::rotate
void rotate(const FCOORD &rotation)
Definition: stepblob.cpp:379
tesseract::StrokeWidth::FindLeaderPartitions
void FindLeaderPartitions(TO_BLOCK *block, ColPartitionGrid *part_grid)
Definition: strokewidth.cpp:259
tesseract::PageSegMode
PageSegMode
Definition: publictypes.h:159
tesseract::ColPartitionGrid::ReTypeBlobs
void ReTypeBlobs(BLOBNBOX_LIST *im_blobs)
Definition: colpartitiongrid.cpp:870
BRT_VLINE
Definition: blobbox.h:74
tesseract::TabFind
Definition: tabfind.h:52
tesseract::CCNonTextDetect
Definition: ccnontextdetect.h:31
TBOX::left
int16_t left() const
Definition: rect.h:71
tesseract::StrokeWidth::SetNeighboursOnMediumBlobs
void SetNeighboursOnMediumBlobs(TO_BLOCK *block)
Definition: strokewidth.cpp:142
GenericVector::get
T & get(int index) const
Definition: genericvector.h:716
SVEvent
Definition: scrollview.h:60
STATS::add
void add(int32_t value, int32_t count)
Definition: statistc.cpp:87
ScrollView::GREEN
Definition: scrollview.h:106
tesseract::ColPartitionGrid::SetTabStops
void SetTabStops(TabFind *tabgrid)
Definition: colpartitiongrid.cpp:753
tesseract::CCNonTextDetect::ComputeNonTextMask
Pix * ComputeNonTextMask(bool debug, Pix *photo_map, TO_BLOCK *blob_block)
Definition: ccnontextdetect.cpp:85
TBOX::right
int16_t right() const
Definition: rect.h:78
tesseract::ColPartition::DeleteBoxes
void DeleteBoxes()
Definition: colpartition.cpp:305
ccnontextdetect.h
tprintf
DLLSYM void tprintf(const char *format,...)
Definition: tprintf.cpp:34
PDBLK::plot
void plot(ScrollView *window, int32_t serial, ScrollView::Color colour)
Definition: pdblock.cpp:174
TO_ROW
Definition: blobbox.h:543
ScrollView::Update
static void Update()
Definition: scrollview.cpp:708
tesseract::StrokeWidth::RemoveLineResidue
void RemoveLineResidue(ColPartition_LIST *big_part_list)
Definition: strokewidth.cpp:279
tesseract::TabFind::dead_vectors
TabVector_LIST * dead_vectors()
Definition: tabfind.h:175
workingpartset.h
BLOBNBOX::cblob
C_BLOB * cblob() const
Definition: blobbox.h:267
tesseract::TabFind::TidyBlobs
void TidyBlobs(TO_BLOCK *block)
Definition: tabfind.cpp:465
BLOBNBOX::owner
tesseract::ColPartition * owner() const
Definition: blobbox.h:351
tesseract::TableFinder::LocateTables
void LocateTables(ColPartitionGrid *grid, ColPartitionSet **columns, WidthCallback width_cb, const FCOORD &reskew)
Definition: tablefind.cpp:259
BLOCK::re_rotation
FCOORD re_rotation() const
Definition: ocrblock.h:133
POLY_BLOCK::isA
PolyBlockType isA() const
Definition: polyblk.h:58
PT_HORZ_LINE
Definition: capi.h:120
tesseract::ColPartitionGrid::MakeColPartSets
bool MakeColPartSets(PartSetVector *part_sets)
Definition: colpartitiongrid.cpp:777
GenericVector::size
int size() const
Definition: genericvector.h:71
textord_debug_tabfind
int textord_debug_tabfind
Definition: alignedblob.cpp:27
scrollview.h
tesseract::GridBase::gridheight
int gridheight() const
Definition: bbgrid.h:69
tesseract::GridBase::bleft
const ICOORD & bleft() const
Definition: bbgrid.h:72
tablefind.h
tesseract::ColPartitionGrid::ExtractPartitionsAsBlocks
void ExtractPartitionsAsBlocks(BLOCK_LIST *blocks, TO_BLOCK_LIST *to_blocks)
Definition: colpartitiongrid.cpp:668
tesseract::ColPartition::MakeLinePartition
static ColPartition * MakeLinePartition(BlobRegionType blob_type, const ICOORD &vertical, int left, int bottom, int right, int top)
Definition: colpartition.cpp:148
BLOCK::set_skew
void set_skew(const FCOORD &skew)
Definition: ocrblock.h:148
tesseract::ColumnFinder::~ColumnFinder
~ColumnFinder() override
Definition: colfind.cpp:97
TBOX::set_left
void set_left(int x)
Definition: rect.h:74
TO_ROW::blob_list
BLOBNBOX_LIST * blob_list()
Definition: blobbox.h:599
ICOORD::y
int16_t y() const
access_function
Definition: points.h:55
tesseract::ColumnFinder::IsVerticallyAlignedText
bool IsVerticallyAlignedText(double find_vertical_text_ratio, TO_BLOCK *block, BLOBNBOX_CLIST *osd_blobs)
Definition: colfind.cpp:179
tesseract::EquationDetectBase::FindEquationParts
virtual int FindEquationParts(ColPartitionGrid *part_grid, ColPartitionSet **best_columns)=0
TBOX
Definition: rect.h:33
DENORM
Definition: normalis.h:49
tesseract::TabFind::RotateBlobList
static void RotateBlobList(const FCOORD &rotation, BLOBNBOX_LIST *blobs)
Definition: tabfind.cpp:1256